[ 뇌를 자극하는 윈도우즈 시스템 프로그래밍 ] Chapter 16. 컴퓨터 구조에 대한 네 번째 이야기

01. 메모리 계층(Memory Hierarchy)

컴퓨터에서 가장 중요한 장치를 꼽으라 한다면, 단연코 CPU라 대답할 것이다. 하지만, 개발자 입장에서는 메모리 또한 CPU 못지않게 중요하다. 왜냐하면, 가급적 높은 성능을 낼 수 있도록 프로그래밍 하기 위해서는 메모리의 특성을 잘 파악해야 하기 때문이다.

 

메모리의 범위와 종류

이제 메모리라 불릴 수 있는 요소들을 나열해 보자.

 

[메인(Main) 메모리]

가장 먼저 떠올릴 수 있는 것은 메인 메모리인 램(RAM)이다. 더 정확하게 말한다면, D-RAM 계열의 메모리이다. 컴퓨터를 구입할 때 CPU 다음으로 중요하게 생각하는 것 중 하나이다. 거의 모든 컴퓨터가 메인 메모리로 램을 사용하기 때문에, 메인 메모리와 램을 동일시한다.

 

[레지스터(Register)]

CPU 안에 내장되어 있어서 연산을 위한 저장소를 제공한다. 이는 앞선 내용에서 많이 언급하였다.

 

[캐쉬(Cache)]

캐쉬는 D램보다 빠른 S램(S-RAM)으로 구성한다. 램과 마찬가지로, 캐쉬 메모리는 그냥 캐쉬라고도 표현한다. 이는 CPU와 램 사이에서 중간 저장소 역할을 하는 메모리이다. 요즘은 CPU 안에 캐쉬가 내장되어 있다고도 하지만, 캐쉬 메모리는 원래 CPU의 일부로 존재하는 메모리 개념이 아니며, CPU에 근접해 있는 메모리 개념이다. 즉, CPU에 가장 근접해 있는 메모리이다.

 

[하드디스크(Hard Disk)와 이외의 저장 장치들]

하드디스크는 크고 작은 파일들을 저장하기 위한 용도로도 사용되지만, 프로그램 실행에 있어서도 중요한 의미를 지닌다. 이외에도 SD 카드, CD-ROM 등과 같은 I/O 장치들도 메모리에 해당한다.

 

따라서, 프로그래머가 개발하는 데에 있어서 메모리를 염두 해야 한다는 말은 다음과 같은 의미이다.

 

“프로그래머는 레지스터, 캐쉬, 메인 메모리, 하드디스크뿐만 아니라 I/O 장치들과의 입출력 타이밍 및 대기 시간 등을 항상 고려해야 한다.”

 

메모리 계층 구조(Memory Hierarchy)

프로그램이 실행되는 동안에 메모리가 하는 역할은 데이터의 입력 및 출력이다. 이러한 메모리들 사이의 가장 큰 차이점은 CPU를 기준으로 얼마나 멀리 떨어져 있는가이다. 레지스터는 CPU에 가깝다 못해 CPU 내부에 존재하고, 캐쉬 메모리는 그다음으로 가깝다. 이후는 메인 메모리, 하드 디스크 순으로 가깝다.

CPU와 가까이 있을수록 빠르고, 멀리 있을수록 느리다. 이는 정말로 가까우니까 빠른 것이다. CPU가 레지스터에 접근할 때에는 별다른 절차가 필요 없지만, 메인 메모리에 접근하는 과정에는 버스 인터페이스 컨트롤 등의 과정을 거쳐야 한다. 이는 거리가 멀기 때문에 데이터 입출력을 위해 메모리 버스를 거치는 과정이 필요하기 때문이다.

물론, 느린 하드디스크 대신, 메인 메모리를 하드디스크만큼 용량을 늘려 사용하는 것이 가장 이상적이겠지만, CPU 근처로 갈수록 기술적인 문제와 비용 문제가 발생한다. 결론적으로 메모리는 다음과 같은 피라미드 계층 구조를 가진다.

 

그림에서, 위에 있을수록 크기는 작지만, 속도는 가장 빠르다. 또한, 위에서 L1 캐쉬와 L2 캐쉬를 확인할 수 있는데 이는 둘 다 캐쉬라는 점이 동일하지만, L1 캐쉬가 CPU에 좀 더 가깝다고 생각하면 된다.

 

 

위 그림의 내용을 설명하면 다음과 같다.

먼저, 하드디스크에 있는 내용은 프로그램의 실행을 위해 메인 메모리로 이동한다. 그리고 메인 메모리에 있는 내용도 L2 캐쉬로, 다음은 L1 캐쉬, 최종적으로 데이터 중에서 연산에 필요한 데이터가 레지스터로 이동한다. 즉, 모든 메모리의 역할이 피라미드 구조에서 자신보다 아래에 있는 메모리를 캐쉬하기 위해서 존재한다.

역순으로는, 연산이 필요한 데이터가 레지스터에 존재하지 않으면 L1 캐쉬를 확인하고, L2 캐쉬-메인 메모리-하드디스크 순으로 확인하게 된다.

위의 과정에서, 많은 메모리를 거쳐 내려가기 때문에 차라리 하드디스크 하나만 확인한다면 좀 더 빠를 거라는 생각을 할 수도 있다. 하지만, 메인 메모리를 제외한 L1 캐쉬와 L2 캐쉬에, 연산에 필요한 데이터가 존재할 확률이 90% 이상 되기 때문에 분명히 캐쉬는 속도를 향상시킨다.

---

02. 캐쉬(Cache)와 캐쉬 알고리즘

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

컴퓨터 프로그램을 유심히 관찰하면, 공통적으로 지니는 일반적인 특성이 존재한다. 이러한 특성을 이용해 하드웨어 구조적으로 캐쉬 메모리라는 것을 등장시켜서 성능 향상을 가져오게 된 것이다.

 

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

int main()
{
	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;
}

 

위의 버블 정렬(Bubble Sort) 알고리즘만 봐도 이러한 특성을 확인할 수 있다. 먼저, 함수 내부적으로 세 개의 지역변수 i, j, temp가 선언되어 있다. 함수를 보면 이러한 지역변수에 얼마나 자주 접근하고 있는지 알 수 있다. 이러한 특성을 가리켜 템퍼럴 로컬리티(Temporal Locality)라 한다. 이는 프로그램 실행 시 한 번 접근이 이뤄진 주소의 메모리 영역은 자주 접근하게 된다는 프로그램 특성을 표현한다.

 

위의 코드 일부에서는 또 다른 특성을 확인할 수 있다.

srcArr[j - 1] = srcArr[j];

 

중요한 것은 j 값의 변화이다. 이는 0부터 시작해서 배열의 크기만큼 증가한다. 이때 j 값이 증가함에 따라 접근하는 메모리 주소값은 4바이트씩 증가한다. 이러한 특성을 가리켜 스페이셜 로컬리티(Spatial Locality)라 한다. 이는 프로그램 실행 시 접근하는 메모리 영역은 이미 접근이 이루어진 영역의 근처일 확률이 높다는 프로그램 성격을 표현한다.

 

또한, 캐쉬의 도움을 많이 받을 수 있도록 구현된 코드를 캐쉬 프렌들리 코드(Cache Friendly Code)라 한다.

 

캐쉬 알고리즘

위에서 설명한 프로그램의 두 가지 특성이 캐쉬에 어떻게 반영되는지 알아보자.

먼저, 캐쉬에 해당 필요로 하는 데이터가 존재한다면, Cache Hit이 발생했다고 하며, 존재하지 않을 경우 Cache Miss가 발생했다 한다. 만약, L1 캐쉬에서 Cache Miss가 발생했다면, L2에서 데이터를 확인하는 과정을 거치게 된다.

이때, L2 캐쉬에서 L1 캐쉬로 이동하는 데이터는 블록 단위로 전송을 한다. 이는 앞서 설명한 특성 중, Spatial Locality를 반영하는 것이다. 현재 접근하는 데이터뿐만 아니라, 블록 단위로 데이터를 가져와 근처에 존재하는 데이터를 함께 가져오는 것이다.

또한, 피라미드 구조상 아래로 내려갈수록 블록 크기는 커지게 된다. 이는 아래에 존재하는 메모리일수록 접근 횟수를 줄일 수 있게 되며, 결론적으로 비교적 속도가 느린 아래 계층 메모리에 접근 횟수가 줄어드는 것이다. 따라서 속도 향상에 도움이 된다.

추가적으로, 운영체제가 동작을 하고, 프로그램이 실행되는 동안에는 하드디스크를 제외한 모든 메모리는 가득 채워져 있다. 따라서, 캐쉬 미스가 발생하여, 아래 계층의 메모리로부터 데이터를 가져올 때 다음과 같은 문제가 발생한다.

 

“어디에 저장하지?”

 

즉, 이미 가득 차 있기 때문에 저장할 공간이 없는 것이다. 따라서, 기존에 갖고 있는 데이터를 밀어내어 저장하게 된다. 이때 아무런 규칙이 없는 것이 아닌 블록 교체 알고리즘에 의해 밀어내게 된다. 블록 교체 알고리즘은 캐쉬 교체 정책에 따라서 달라질 수 있는데 가장 보편적인 방법은 LRU(Least-Recently Used) 알고리즘이다. 즉, 가장 오래전에 참조된 블록을 밀어내는 것이다.

 

Cache Friendly Code 작성 기법

이번엔 간단한 예를 통해 Cache Friendly Code 작성 기법을 알아보자.

먼저, 다음과 같이 2차원 배열에 접근하는 코드가 있다.

int main()
{
	int arr[10][10];

	int total = 0;
	for (int i = 0; i < 10; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			total += arr[j][i];
		}
	}
}

 

위 코드에서는 변수 total 값에 빈번하게 갱신되고 있다는 점에서 Temporal Locality의 특성을 고려했다는 것을 알 수 있다. 하지만, Spatial Locality는 고려하지 못하고 있다. 다음 그림을 보자.

위의 코드는 왼쪽 화살표와 같이 배열을 열 단위로 접근하고 있기 때문에 배열의 크기가 커진다면, 메모리 공간이 근접하지 않는다. 배열 접근 방식을 열 단위가 아닌 행 단위로 접근한다면, 배열의 크기와 무관하게 Spatial Locality 특성을 잘 반영하는 코드인 것이다.

---

03. 가상 메모리(Virtual Memory)

“메인 메모리는 프로세스에 비해 공간이 부족한데, 어떻게 프로그램이 실행되는 것인가?”에 대한 의문은 가상 메모리로부터 해결된다.

 

물리 주소(Physical Address)

우선 물리 주소에 대해 이해하기 위해 임베디드 시스템과 범용 시스템을 생각해 보자.

임베디드 시스템과 범용 시스템의 가장 큰 차이점은 하드디스크의 존재 유무이다. 범용 시스템은 하드디스크가 존재해서 Windows 운영체제에서부터 각종 소프트웨어를 하드디스크에 저장하고, 전원이 켜지면 저장된 소프트웨어를 기반으로 동작한다.

반면에, 임베디드 시스템은 하드디스크가 없기 때문에 플래시 메모리를 이용한다. 즉, 플래시 메모리에 데이터를 저장하고, 전원이 켜지면 램으로 데이터가 이동한다. 이때 데이터는 컴파일이 완료된 운영체제와 그 운영체제를 바탕으로 동작하는 프로그램을 총칭하는 것이다.

그렇다면, 램 용량이 16M 바이트라 가정해 보자. 그러면 CPU와 같은 장치 입장에서 접근 가능한 메모리 영역은 0번지부터 “(16*1024*1024)-1”번지 사이가 된다. 이는 실제 물리적인 메인 메모리의 주소 범위에 해당하며, 이를 물리적 주소 지정(Physical Addressing)이라 한다. 물리적 주소 지정의 특징은 메인 메모리 크기에 따라 지정 가능한 주소의 범위가 결정되는 것이다.

이러한 물리적 주소 지정은 CPU 입장에서는 접근 가능한 주소의 범위가 제한된다. 따라서, 가상 메모리를 사용하는 것이다.

 

가상 주소(Virtual Address) 시스템 1

32비트 시스템에서 프로세스 생성 시 4G 바이트의 메모리를 할당받을 수 있다. 그러나 메인 메모리는 여기에 미치지 못한다. 따라서, 4G 바이트는 실제 존재하지 않는 가상의 주소라는 결론을 내릴 수 있다. 이처럼 가상의 주소를 지정하는 것을 가리켜 가상 주소 지정(Virtual Addressing)이라 하며, 가상 주소 지정을 통해 할당받게 되는 4G 바이트를 가상 메모리 공간(Virtual Address Space)라 한다.

이러한 가상 메모리는 하드디스크를 기반으로 작동하게 된다. 하드디스크라 해서 메인 메모리의 역할을 못하는 것은 아니다. 단지 두 가지의 문제가 있을 뿐이다.

 

[첫 번째 문제: 선 할당으로 인한 부담]

실제로 사용하는 공간은 적어도 프로세스를 생성할 때마다 4G 바이트씩 할당하는 과정은 시간이 엄청나게 걸린다.

 

[두 번째 문제: 느린 속도의 개선 필요]

하드디스크 자체의 속도 문제가 있다.

 

이러한 문제들은 가상 메모리에서 해결하고 있다. 이 책에서는 대부분의 시스템에서 사용하는 페이징(Paging)이라는 기법을 설명한다.

 

Paging 기법에서는 MMU(Memory Management Unit)이라는 CPU와 함께 하나로 패키징 되는 장치가 부족한 메인 메모리를 CPU로 하여금 충분하다고 착각하게 한다.

MMU는 CPU로부터 요청받은 데이터가 포함된 데이터 블록만을 메인 메모리에 할당한다.  데이터 블록 단위로 할당하는 이유는, 앞에서 설명했듯이 Spatial Locality에 의한 것이다. 이러한 과정은 프로그램이 실제로 할당된 용량을 전부 사용하지 않을 확률이 높다는 데에 기반한다.

이러한 데이터 블록을 하드웨어 입장에서는 페이지 프레임(Page Frame)이라 하고, 소프트웨어 입장에서는 페이지(Page)라 한다.

 

이러한 가상 메모리는 다음과 같은 페이지 테이블을 참조한다.

 

페이지 테이블의 Key는 페이지 숫자이다. 또한, Value는 해당 페이지가 존재하는 페이지 프레임의 시작 번지이다. 이를 참조하여 가상 주소를 실제 할당되어 있는 물리 주소로 변환할 수 있다.

 

가상 주소(Virtual Address) 시스템 2

앞에서도 언급했지만, 하드디스크도 램과 비교하여 속도를 제외하면 기능에 부족함이 없다. 이러한 하드디스크를 메인 메모리로 확장해서 문제를 해결한다. 이때 스왑 파일(Swap File)이라는 개념을 도입한다.

 

위처럼 하드디스크의 일부를 메인 메모리로 사용하는 것이다. 이제 메모리 할당 과정에서 부족한 부분은 하드디스크 공간으로 대체할 수 있는 것이다. 하지만, RAM에 비해서 하드디스크는 속도가 느리기 때문에 스왑 파일을 통해 메인 메모리를 보조하는 것이지, 램과 완전히 동일한 역할을 하는 것은 아니다.

 

즉, 앞서 가상 메모리에서 메인 메모리로의 할당한 공간이 부족할 때, 메인 메모리에서 가장 안 쓰이는 블록을 하드디스크에 저장한 뒤, 해당 영역을 새로운 메모리 블록으로 대체하는 것이다. 이때, 램과 하드디스크 사이의 데이터 이동 기본 단위는 페이지 프레임 크기와 동일하다.

 

예시를 통해 지금까지의 내용을 정리해 보자.

프로세스 A가 실행을 멈추고 프로세서 B를 실행시키고자 한다고 가정하자. 현재 RAM에는 프로세스 A를 실행하기 위한 데이터가 존재할 것이다. 이제 프로세스 B를 실행하려면, 현재 RAM에 존재하는 A 관련 데이터를 모두 프로세스 A의 스왑 파일에 저장하게 된다. 이후에 프로세스 B의 실행을 위한 데이터를 프로세스 B의 스왑 파일로부터 램에 가져다 놓게 된다.

---

참고 자료:

윤성우. 『뇌를 자극하는 윈도우즈 시스템 프로그래밍』.한빛미디어, 2007.