윈도우즈 시스템 프로그래밍 16장 - 캐쉬와 캐쉬 알고리즘

 

 

 

윈도우즈 시스템 프로그래밍이라는 책과 해당 책의 저자이신 윤성우님의 강의를 통해 공부한 내용을 정리하는 글입니다.

 

 

 

---

 

 

 

컴퓨터 프로그램의 일반적인 특성

 

 

#define ARR_LEN 5

void bubblesort(int srcArr[], int n)
{
	int i, j, temp;
	for (i = 0; i < n; i++)
	{
		for (j = 1; j < n - 1; i++)
		{
			if (srcArr[j - 1] > srcArr[j])
			{
				temp = srcArr[j - 1];
				srcArr[j - 1] = srcArr[j];
				srcArr[j] = temp;
			}
		}
	}
}

int _tmain(int argc, TCHAR** argv)
{
	int arr[ARR_LEN] = { 5,3,7,6,9 };
	bubblesort(arr, ARR_LEN);
	for (int i = 0; i < ARR_LEN; i++)
		printf("%d, ", arr[i]);
	return 0;
}

 

 

위 코드에서 i, j, temp가 지역변수로 선언되어 있다. 이러한 지역변수는 선언 및 초기화 이후 다양한 값으로 변경도 되고, 값을 얻기 위한 참조도 일어난다. 이러한 특성을 가리켜 템퍼럴 로컬리티(Temporal Locality)라고 한다.

 

템퍼럴 로컬리티란 프로그램 실행 시 한 번 접근이 이뤄진 주소의 메모리 영역은 자주 접근하게 된다는 프로그램 특성을 표현할 때 사용하는 말이다.

 

srcArr[j-1] = srcArr[j]의 경우는 j 값은 0부터 시작해서 배열의 크기만큼 증가할 것이다. j 값이 증가하면 접근하는 메모리 주소값은 4바이트씩 증가한다. 이러한 특성을 스페이셜 로컬리티(Spatial Locality)라 한다.

 

스페이셜 로컬리티란 프로그램 실행 시 접근하는 메모리 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다는 프로그램 성격을 표현할 때 사용하는 말이다.

 

소프트웨어의 이러한 특성 때문에 캐쉬는 성능 향상에 많은 도움이 된다. 캐쉬의 도움을 많이 받을 수 있도록 프로그램을 구현하는 것을 가리켜 캐쉬 프렌들리 코드(Cache Friendly Code)라 한다.

 

 

 

 

캐쉬 알고리즘

 

 

 

ALU 연산과정 중에서 필요한 데이터가 있다면 이를 레지스터로 이동시켜야 한다.

그렇다면 해당 데이터를 L1 캐쉬에서 찾아봐야 한다. 만약 존재한다면 캐쉬 힛(Cache Hit)이 발생했다고 한다.

만약 존재하지 않았다면 캐쉬 미스(Cache Miss)가 발생했다고 한다. 캐쉬 미스가 발생하면 L2 캐쉬에서 찾아보게 된다.

만약 L2 캐쉬에서도 캐쉬 미스가 발생하면 메인 메모리에서 데이터를 가져와야 한다.

 

이때, 데이터의 이동 단위는 블록이다. 레지스터로 이동해야 하는 데이터가 0x1000 번지였는데 이 데이터가 L1 캐쉬에 존재하지 않고 L2 캐쉬에 존재했다면, L2 캐쉬에서 L1 캐쉬로 이동하는 데이터의 단위는 0x1000번지의 데이터를 포함하는 하나의 블록이 된다. 즉, 단순히 필요한 데이터만 보내는 것이 아닌 블록 단위로 전송해서 스페이셜 로컬리티의 특성을 성능 향상에 활용하게 된다.

 

메모리 피라미드 구조상 아래로 내려갈수록 블록 크기는 커진다. 이는 아래에 존재하는 메모리일수록 접근 횟수를 줄이는 효과를 가져다 준다. 아래에 존재하는 메모리일수록 속도가 느리므로 이와같이 접근 횟수를 줄이는 것은 성능 향상에 많은 도움이 된다.

 

운영체제가 동작을 하고, 프로그램이 실행되는 동안에는 하드 디스크를 제외한 모든 메모리가 항상 채워져 있다. L2 캐쉬의 경우를 생각해보면 꽉 채워놓을수록 L1 캐쉬에서 요구하는 데이터를 가지고 있을 확률이 올라간다. 따라서 메모리를 비워둘 필요가 없다.

 

꽉 차있는 L1 캐쉬에서 캐쉬 미스가 발생해서 L2 캐쉬로부터 데이터 블록을 읽어들일 때 어디에 저장할지 결정해야 하는데, 이때 적용되는 규칙이 캐쉬 교체 정책이다. 가장 보편적인 것은 LRU이다. 가장 오래전 참조된 블록을 밀어내는 알고리즘이다. 물론 캐쉬에 따라 달라질 수 있다.