인텔 구조에서 운영체제 가상 메모리 (Virtual Memory)는?

2019. 5. 13. 22:45

안녕하세요? 허니입니다. 오늘은 운영체제 가상메모리에 대해 자세하게 포스팅 하려고 합니다. 운영체제에서 가상 메모리는 매우 중요한 개념입니다. 대부분 이 부분을 자세히 모르기 때문에 운영체제 공부하는데 많은 어려움이 있는 것으로 알고 있습니다.

오늘의 주제

가상 메모리

가상메모리는 1950년대 메모리의 부족, 즉 실행 화일이 메모리보다 더 큰 문제를 해결하기 위해 overlay와 같은 기법을 활용하였지만 많은 문제점을 야기하였습니다. 가상메모리는 메모리 부족 문제에 대한 훌륭한 해법이 되었고, 1960년대에 상업용 운영체제에 적용되어 쓰이게 됩니다. 이후 쓰레싱(Thrashing)이라는 문제점에 대해서 1970년대 후반 워킹셋(Working-Set)을 이용한 해결책이 나오게 되었습니다. 가상메모리의 기본적인 개념은 "가상주소(Virtual Address)"와 "물리주소(Physical Address)"의 분리입니다. 즉, 10번지의 내용물과 20번지의 내용물을 더해서 30번지에 넣으라는 명령어 (Instruction)에 대해서 기존에는 10,20,30이라는 주소는 메모리의 실제 주소(physical address)였다면, VM은 10,20,30이 가상 주소(virtual address)입니다. 따라서 실제로 메모리의 어느 지점의 내용물들이 사용될런지는 이것만으로는 알 길이 없습니다. 따라서 VM을 구현하기 위해서는 MMU(Memory management unit)이라는 CPU내의 특수한 하드웨어가 필요합니다. 이 unit에 의해서 10,20,30이라는 virtual address는 100,200,300 따위의 실제 주소(physical address)로 변환됩니다. 이러한 변환과정(mapping)은 매우 중요합니다. 아시다시피, 그렇지 않아도 빠른 CPU를 따라오지 못하는 메모리 속도가 문제가 되는 시점에서, 1번의 메모리 참조(reference)를 매번 이와 같은 변환 과정을 거쳐서 참조해야 한다는 것은 막대한 성능의 저하를 초래할 것이기 때문입니다. 그렇다면 이러한 성능의 저하를 감수하고라도 가상메모리 기능을 이용할 필요가 있는 것인가? 그렇습니다. 그에 따르는 수많은 장점들이 있기에 현대 CPU가 대부분 이를 사용하겠지요. 그렇다면 맵핑(mapping) 과정에서 일어나는 부하를 최대한으로 줄이는 것이 관건이 됩니다. 이를 위해 사용되는 것이 TLB(Translation Look-aside Buffer)입니다. 가상메모리의 강력함은 그 부수적인 효과에서도 대단한 변화를 가지고 왔습니다. 즉, 가상메모리로 인하여 각 프로세스는 자신만의 4GB라는 거대한 주소 공간을 가지게 된 것입니다. 이 공간은 다른 프로세스에게 보이지 않기 때문에 자신만의 공간이며, 4GB라는 풍족한 주소 공간을 활용하여 이전에는 생각하지 못했던 일들을 할 수 있습니다.

위 그림은 리눅스에서 초기 프로세스의 메모리 맵입니다. 첫 번째 줄에서 0804800 지점에 초기 실행 파일이 올라와 있고, 그외 ld-2.3.2.so 나 libc-2.3.2.so 같은 이미지들이 올라와 있습니다. 이처럼 4GB라는 주소공간이 바로 가상 메모리 주소입니다. 여기에 속한 메모리의 크기는 무려 4GB씩이나 되니 알 수 있는 것이 init이라는 이미지는 ld 와 libc라는 또 다른 이미지들을 사용하고 있다는 것을 알 수 있습니다. ld는 dynamic linker입니다. 즉, 공통으로 사용되는 libc를 init에서 사용하는데, 이 library를 동적으로 불러 주는 것이 ld라는 linker입니다. 이 ld 는 일반적으로 compiling에 사용되는 static linker이기도 하지만, 동시에 dynamic linker로도 쓰이며 또한 dynamic library라는 또 다른 특징이 존재합니다.

Figure 3-12는 인텔에서 제공하여 가지고 온 그림입니다. 인텔 구조에서 linear 주소라고 불리기도 하는 가상주소를 물리 주소로 변환하는 과정을 보여주는 그림입니다. 가상 주소는 3부분으로 나뉘는데, 가장 뒤 12비트는 offset으로서 아무런 변환도 거치지 않습니다. 앞의 10비트는 page directory에서의 index를 나타내는 부분으로 쓰이고, 중간의 10비트는 page table에서의 index를 나타내는 부분으로 쓰입니다. 또한, CPU 내 page directory를 가리킬 하나의 레지스터가 필요합니다. 인텔에서는 CR3라는 레지스터가 있어, 이 레지스터가 Page directory의 주소를 가지고 있게 됩니다. 문맥 교환이 일어나서 다른 프로세스의 가상 주소 공간로 전환하려면 이 CR3의 내용을 해당 프로세스의 page directory의 주소로 넣어줌으로써 각 가상 주소 공간 간의 전환을 하게 됩니다. 앞 포스팅에서 설명했듯이 물리 메모리는 모두 4KB의 단위의 page로 구성되었다고 생각하고, 이러한 page 단위로 접근하기 때문에, 모든 단위는 page로 이루어지는 것이 좋습니다. 따라서 위의 page table과 page directory는 모두 1 page를 차지하게 됩니다. 또한 각 entry는 4byte로 이루어지기 때문에, 자연히 1개의 page는 (위에서 각 page directory와 page table은) 1024개의 entry를 가지게 됩니다. offset은 변환이 완료된 물리 page 안에서 offset만을 나타내기 때문에 아무런 변환이 없이 사용될 수 있습니다. 이제 하나의 메모리 참조를 하기 위해서는 CR3가 가리키는 페이지에서 가상 주소의 앞 10비트를 index로서 사용해서 해당하는 entry를 참조합니다. 10비트이기 때문에 정확히 1024개의 entry를 사용하게 되는 것입니다. 이렇게 얻은 4byte자리 entry는 다시 다음 page table로의 base address를 제공하게 됩니다. 이때 다시 중간의 10bit를 index로서 사용하여, 역시 10bit이기 때문에 1024개의 entry를 사용하게 되고, page-table entry를 얻게 됩니다. 이때 나오는 page-table entry가 비로소 물리 page의 물리적 주소를 제공하게 됩니다. 이 주소에 원래 가상 주소의 마지막 12bit를 합쳐주면 최종적인 물리 주소를 얻게 됩니다. 이러한 과정은 다음 그림과 같은 2-level tree로서 구성해서 이해할 수 있습니다.

그림에서 보듯이 CR3를 root로 해서 tree 구조를 형성하고 있습니다. CR3를 제외한 하나의 사각형은 모두 4KB짜리 페이지를 나타냅니다. 따라서 하나의 사각형당 최대 1024개의 화살표를 가질 수 있습니다. 위의 그림에서 page directory에서부터 각 level에서 가상 주소의 각 10비트씩을 index로 사용하여 최종 단계로 가서 실제 물리 Page의 주소를 얻게 됩니다. 이렇게 얻은 주소에 12bit의 offset을 합치면 물리 주소가 됩니다. 여기서 사각형 안에 있는 번호는 물리 page number임을 주의하시기 바랍니다. 실제 개념도는 tree로 표현하였지만 page directory와 page table등은 모두 실제 메모리를 차지하는 하나의 page이기 때문에 실제로는 각 번호대로 일렬로 그려야 할 것입니다. 이러한 실제 메모리에 대한 그림을 뒤에 넣었으니 참조하시기 바랍니다. 하나의 page table은 1024개의 entry를 가지고, 한 개의 entry가 한 개의 page를 가리키기 때문에, 하나의 page table은 1024개의 page를 가리킬 수 있습니다. 역시 한 개의 page directory에 의해서 1024개의 page table을 가리키기 때문에, 하나의 page directory는 총 1024*1024개의 page를 가리킬 수 있게 됩니다. 이는 곧 4GB의 공간을 나타낼 수 있습니다. 하지만 실제로 이 모든 맵핑을 한다면, page directory와 page table을 위해서 1025개의 page를 소모하는 꼴이 됩니다. 대략 4MB의 용량입니다. 하나의 프로세스가 이 맵핑을 위해 4MB씩을 소모할 수는 없기 때문에 필요로 하는 부분만을 맵핑하여 사용합니다. 위의 그림에서 12번 물리 페이지를 사용하는 page directory는 4개의 화살표만을 가지고 있습니다. 이것은 곧, 5번째 이후의 entry들은 null일테고, mapping이 존재하지 않는다는 뜻입니다. 즉, 해당 가상 주소에 대한 가상 주소 공간가 존재하지 않는다는 것입니다. 한 개의 page directory entry는 1개의 page table에 대응하고, 하나의 page table은 4MB를 커버하기 때문에, 4개의 화살표는 0~16MB의 공간을 뜻합니다. 위 그림에서는 16MB까지만의 가상 주소만 유효한 것으로 생각하시면 됩니다. 다시 말해 Page table에서도 모든 화살표가 있는 것이 아니기 때문에, 화살표가 있는 부분만이 유요한 주소공간이라고 할 수 있습니다. 그렇다면 유효하지 않는 주소 공간으로 접근하게 되면 어떻게 될까요? 이런 경우에는 당연 page fault가 발생합니다.

위 그림에서 확인하듯이 page table entry입니다. 각 페이지 디렉토리나 페이지 테이블은 이와같은 엔트리를 1024개씩 가지게 됩니다. 물론 가장 중요한 정보는 다음 단계로의 포인터역할을 하는 기본 주소이고, 그외에 Read/Write bit은 해당 페이지가 read-only일지를 결정하고, User/Supervisor bit은 해당 페이지를 유저 공간에서 접근가능한지 아니면 커널모드에서만 접근가능한지를 나타냅니다. 그외에는 Access bit이 있는데 해당 페이지가 접근되면 1로 세팅됩니다. 또한 Dirty bit은 해당 페이지가 쓰이면 1로 세팅됩니다. 이러한 비트들은 CPU가 1로 세팅하며 절대 0으로 세팅하지는 않고, 운영체제 만이 0으로 세팅합니다. 운영체제는 이러한 CPU가 주는 정보를 다양한 방식으로 이용하게 됩니다.

위의 그림은 64비트의 경우입니다. 32bit의 경우를 확장한 것인데, 처음 4G의 물리메모리가 부족해지자 인텔은 PAE(Physical address extension)이라는 이름으로 물리 주소를 36비트로 확장하고, page table구조를 바꾸게 됩니다. 각 엔트리는 크기가 2배로 늘어 한 페이지안에는 512개의 엔트리만이 들어가게 되었습니다. AMD가 이 구조를 약간 확장하여 하나의 level을 더 추가하여 64비트에서도 계속 사용합니다.

Page Table Structure
가상메모리의 페이지 매핑을 구현하는데에는 보통 위와같이 tree 구조를 사용합니다. 하지만 그외에도 다양한 방식들도 있습니다. PDP-11에서는 레지스터에 page table을 두기도했지만, 이건 작은 페이지 테이블이었기에 가능합니다. 그외에 Hashed Page Table이 있습니다. Offset을 제외한 가상 주소가 해쉬함수로 들어가서 linked list를 찾아들어가 스캐닝하면서 찾아갑니다. 이 리스트안의 엔트리는 virtual page number, physical page number, pointer to next element in the list 등으로 이루어집니다. 순차적으로 virtual page number를 비교해가며 찾는거죠. 그외에 Inverted Page Table이 있습니다. 이경우엔 거꾸로 각 physical page마다 하나의 엔트리를 가집니다. 그리고 여기에 해당 페이지로의 virtual address들을 넣습니다. 따라서 시스템전체에 하나의 페이지 테이블만이 있게되죠. 검색을 위해서는 보통 ASID를 사용합니다. 그래서 offset이외의 부분과 ASID를 가지고 page table을 검색해서 그 index를 physical page number로 사용하게됩니다. 64비트 UltraSPARC과 PowerPC가 이런방식을 사용합니다. 메모리 사용량은 줄겠지만 그러나 검색에 시간이 듭니다. 전체 테이블을 끝까지 검색할수도 있죠. 이를 위해서는 앞서서의 hashed page table방식을 도입해 합칠수도 있겠습니다. 어떤 아키텍쳐의 경우엔 TLB miss handler도 있습니다. TLB가 미스났을때 불리우는 핸들러로 운영체제가 직접 TLB를 채워주는것입니다. x86의 경우엔 하드웨어가 Page table을 읽은후에 직접 TLB에 값을 채워넣죠. 이 방식이 빠르고 간편한 반면 페이지 테이블의 구조가 하드웨어에 의해 정해진다는 점이 있습니다. HW-defined page table라고도 불리며 x86과 PowerPC가 그렇습니다. 반면 운영체제가 TLB미스를 처리하는경우는 SW-defined page table이라고 합니다. UltraSparc, MIPS, Alpha가 그렇습니다. 이 경우는 오버헤드가 있지만 수정이 가능합니다.

목 차

운영체제를 시작하는 분들을 위해

운영체제의 역사와 구체적으로 어떤 일들을 수행하나요?

운영체제의 목표와 역할이 미래에도 계속 증대될까요?

운영체제를 이해하기 위해 필요한 기본 개념들은 무엇인가요?

운영체제 프로세스 생애주기(Process Lifecycle)는 무엇인가요?

운영체제 프로세스 관리(Process Management)는 어떻게 하나요?

운영체제 프로세스(Process)의 처리 속도는 어떻게 높일까?

운영체제 스레드(Thread)는 무엇인가요?

운영체제 스케줄링 (Scheduling)은 어떻게 하나요?

운영체제 스케줄링 알고리즘의 비교 기준이 있나요?

운영체제 프로세스 동기화가 무엇인가요?

운영체제에서 세마포어(Semaphore)란?

운영체제 메모리 관리(Memory Management)는 어떻게 하나요?

운영체제 메모리 분할 방법은 어떻게 하나요?

운영체제 가상메모리(Virtual Memory)는 무엇인가요?

운영체제 Page in/out, Swapping 등이 Page Table Entry와 어떤 관계인가요?

운영체제 Page replacement (페이지 대체) 알고리즘이란?

운영체제 파일시스템(File System)은 어떻게 운영되나요?