[OS] 21. Beyond Physical Memory: Mechanisms

미쳤어 미쳤어. 어제 골골거리다가 눈뜨니까 12시 반이였어 미쳤나봐
방금 그래도 컴퓨터 네트워크 퀴즈 끝나서 마음은 좀 가뿐한 것 같다.
얼른,, 힘내서 공부 마저 해야지,,

지난 세개 포스트를 통해 Paging의 특징과 장단점에 대해 공부했다.

Paging의 느린 속도는 TLB로 어느정도 해결했고, 과도하게 공간을 잡아먹는 문제는 Hybrid 방식이나, Multi-level Paging, 나아가 Inverted Page table로 해결했다.

그런데 딱 하나, 아직 해결하지 못한 문제가 남았다. 만약 시스템에 존재하는 프로세스에 할당된 메모리 공간이 물리 메모리가 감당 가능한 크기보다 크다면,,? 아직까지는 마땅한 해결 방법에 대해 생각해보지 않았다. 지금 방법대로라면 얄짤없이 쓸 수 없는 메모리가 없으니 OS에서 메모리 할당을 거부하겠지?

OS가 처음부터 각각의 프로세스에게 아주 쬐끔씩만 주소 공간을 할당해주면 되지 않겠냐고 할 수도 있겠지만,, 정말 큰 주소 공간이 필요한 프로그램이 굳이 아니더라도 '곳간에서 인심난다'는 말이 있듯 주소 공간이 처음부터 넉넉하게 주어지면 프로그램을 작성할 때나, 프로세스가 OS에 추가적인 메모리를 요청할 때나 메모리가 혹시 부족하지는 않을지 고민할 필요가 없기 때문에 이왕이면 큰 주소 공간을 쥐어주는게 낫다.

그렇다고 해서 메인 메모리가 막 512GB씩 하기는 힘들 것이고(비싸니까), 또 우리가 사용하고 있는 컴퓨터들이 4GB 8GB 되는 RAM을 가지고 불편할만큼 프로세스를 실행시키지 못하는 것도 아닌데, 그럼 어디서 부족한 메모리를 끌어다 쓰는 걸까?

이젠 시스템에 존재하는 페이지들을 이젠 RAM 같은 물리 메모리 뿐만 아니라 이 가상의 어딘가에도 추가할 수 있다고 생각해보자. 말은 쉽지만.

이 어딘가는 보통 현대 시스템에선 HDD가 담당하게 되는데, 메모리가 부족할 때 일부 공간을 잠시 내려 놓는 역할을 한다고 보면 좋을 것 같다. 기본적으로 메모리는 빠를수록 비싸기 때문에 용량이 상대적으로 적고(레지스터, 캐시 등), 느릴수록 저렴하기 때문에(HDD 등) 이 '느리지만 싸고 넓은' 메모리의 대명사인 HDD같은 메모리를 부족한 메인 메모리의 확장을 위해 사용하는 것이다. 그래서 이번 장의 제목부터가 "Beyond Physical Memory" 다!

21.1 Swap Space

이 HDD 위의 어딘가를 좀 더 구체적으로 'Swap 공간'이라 하자.

왜 Swap 공간이냐고? 메모리가 부족해지면 데이터를 이곳으로 보내고(swap out), 다시 필요해지면 이곳으로부터 메모리로 데이터를 다시 읽어오기(swap in) 때문이다.(swap in/out의 단위를 한 페이지라고 한다면, OS는 swap 공간에 저장된 각각의 페이지의 위치를 모두 파악하고 있어야 할 것이다. 어디 있는지 알아야 불러올 수 있으니까!)

메모리보다 보통 HDD가 훨씬 큰건 사실이니까, 일단은 원하는만큼 사용해도 부족함이 없을만큼 Swap 공간을 엄청 크게 잡아놨다고 가정하자.

보면 프로세스 0, 1, 2가 물리 메모리에 저장되어 있고, Swap 공간에는 이 프로세스 0, 1, 2 뿐만 아니라 프로세스 3에서 사용하고 있던 페이지가 swap out 되어 있다. OS는 각각의 페이지가 어느 위치에 저장되어 있는지(Block) 기록하고 있기 때문에 다시 필요할 때 swap in 할 수 있을 것임을 잘 기억해두자.

어떻게 보면 프로그램이 프로세스로서 생명 주기를 시작할 때 명령어를 메모리에 읽어 오는 것도 일종의 swap in이라고 볼 수 있겠다. 프로세스를 이리저리 실행하다가 공간이 부족해져서 swap out한건 아니지만, 넓게 보면 시스템에 존재하는 모든 명령어를 굳이 처음부터 다 메모리에 올려 놓을 필요는 없으니까.

21.2. The Present Bit

이전에 18장에서 Present bit를 잠깐 언급했는데, 드디어 쓸 때가 왔다!

이 Present bit는 PTE에 저장되는데, 이는 지금까지 배운 메모리 액세스 메커니즘상 무조건 데이터를 TLB로부터 읽어 오도록 구현되어 있기 때문이다. 따라서 메모리에 실제로 값이 있는지 없는지는 VPN만 보고는 당연히 알 수 없고, 연결 정보가 저장된 PTE를 읽어야 메모리가 읽기/쓰기/실행 모드인지, 실제로 메모리 위에 있는지 등등의 정보를 알 수 있다.

즉, 메모리에 접근해서 값을 읽으려고 했더니 메모리에 값이 써있지 않고 swap 영역에 써있는 것을 알게 되는 시점이 바로 TLB Hit 및 PTE 접근 직후라는 것이다.

메모리에 값이 써있지 않은 것을 이 Present bit를 통해 알 수 있는데, present bit의 값이 0이면 '존재하지 않음', 그러니까 Swap 영역에 값이 들어 있음을 의미한다. Present bit가 1이면? 그냥 이전에 했던 것처럼 주소 변환 정보를 사용해서 해당 물리 메모리에 찾아가면 되고, 만약 0이면? 다시 데이터를 Swap in 해서 값을 읽어야 한다.

엄밀히 따져보자면 이렇게 Present bit가 0인 상황에서 해당 메모리에 접근하려 할 때 시스템에서 Page fault가 발생하게 되는데, 정확히는 물리 메모리에 존재하지 않는 페이지에 접근하려 할 때 발생하는 것이 Page fault이다.

Page fault가 발생하면 여태까지 그래왔던 것처럼 이를 처리하기 위한 Page fault handler가 실행되는데, 자세한 작동 원리는 다음 절에서 살펴보자.

21.3. The Page Fault

TLB Miss를 HW, SW 둘 다 처리할 수 있다고 했는데, HW로 처리하든 SW로 처리하든 일단 TLB Miss에서 Page fault가 발생하면 무조건 OS가 이를 처리한다.

OS는 Page fault가 발생함에 따라 Page fault handler에 정의된대로 이를 처리(swap in)하는데, 이는 Page table에 해당 페이지가 swap 공간의 어느 위치에 저장되어 있는지 저장해 두었기 때문에 가능한 것이다.

여하튼 이 정보를 가지고 디스크로부터 값을 읽어오면(이때 프로세스의 상태는 Blocked가 된다!!!), Page fault가 발생한 PTE의 PFN 필드를 방금 디스크로부터 메모리에 올려 놓은 그 위치의 PFN으로 갱신해 놓는다.

TLB Miss의 처리와 마찬가지로 기계어 수준에서 명령어 루틴의 중간으로 돌아가서 다시 실행하는 것은 매우 까다로운 작업이기 때문에, 그냥 메모리 액세스 루틴의 맨 처음으로 돌아가서 명령을 다시 실행해준다. 물론 Disk I/O 자체가 시간이 많이 들어가는 작업이기 때문에 그새 내가 올려놓은 PTE가 없어져서 다시 TLB Miss가 발생할 수도 있는 것이고! (자세한 내용은 21.5절에서 수도 코드로 살펴본다.)

21.4. What If Memory Is Full?

만약 프로세스를 새로 만들거나, 기존의 프로세스가 더 큰 메모리 공간을 요구하는데 메모리에 여유 공간이 남아 있지 않다면 어떤 프로세스의 어떤 페이지를 Swap 공간에 묻어 놓아야 할까?

이를 결정하기 위한 일종의 규칙을 Page-Replacement Policy라 하는데, Swap in/out에 필요한 Disk I/O 자체가 무진장 오래 걸리는 작업이기 때문에 이걸 잘못 설정해놓으면 프로세스가 엄청 느리게 작동할 것이다. TLB에서 그러했듯 자주 사용될 가능성이 높은 Page는 Swap out하지 말고 계속 메모리에 들고 있고, 적게 사용될 가능성이 높은 Page를 Swap out 해야 Disk I/O가 적게 발생할 것이므로 전체적인 시스템 활용률에 도움이 될 것이다.

21.5. Page Fault Control Flow

아까 TLB Miss는 HW든 SW든 둘 다 처리할 수 있다고 했는데, Page fault만큼은 Swap 영역에 저장된 Page의 위치 등을 동적으로 기록하기 위해 OS가 처리해주어야 한다고 했다.

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)

if (Success == True) // TLB Hit
  if (CanAccess(TlbEntry.ProtectBits) == True)
    Offset = VirtualAddress & OFFSET_MASK
    PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
    Register = AccessMemory(PhysAddr)
  else
  	RaiseException(PROTECTION_FAULT)
    
else // TLB Miss
  PTEAddr = PTBR + (VPN * sizeof(PTE))
  PTE = AccessMemory(PTEAddr)
  
  if (PTE.Valid == False)
  	RaiseException(SEGMENTATION_FAULT)
  else
    if (CanAccess(PTE.ProtectBits) == False)
    	RaiseException(PROTECTION_FAULT)
    else if (PTE.Present == True)
    	// assuming hardware-managed TLB
    	TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
    	RetryInstruction()
    else if (PTE.Present == False)
    	RaiseException(PAGE_FAULT)

위와 같이 HW가 주소 변환이나 TLB Miss를 처리한다고 가정해보자. 이전과 딱 한군데 달라졌는데, 맨 아래 PAGE_FAULT가 발생하는 부분이다.

PFN = FindFreePhysicalPage()
if (PFN == -1) // no free page found
  PFN = EvictPage() // run replacement algorithm
  
DiskRead(PTE.DiskAddr, PFN) // sleep (waiting for I/O)
PTE.present = True // update page table with present
PTE.PFN = PFN // bit and translation (PFN)
RetryInstruction() // retry instruction

주소 변환 중 PAGE_FAULT가 발생하면 위의 루틴이 OS의 Page fault handler에 의해 실행되는데, 위에서부터 찬찬히 뜯어보자.

PFN = FindFreePhysicalPage()

말 그대로 물리 메모리 위의 빈 공간을 찾는다는 의미이다. 아마 빈 공간이 있었다면 Page fault가 발생하지 않았을 것 같지만,, 일단은 찾는 시늉이라도 한다고(?) 생각하자.

if (PFN == -1)
  PFN = EvictPage()

FindFreePhysicalPage는 빈 물리 메모리를 찾지 못할 경우 -1을 반환하는데, 만약 비어 있는 물리 메모리 프레임을 찾지 못할 경우 OS의 Page-Replacement Policy에 의해 기존에 쓰고 있던 페이지 하나 중 하나를 골라서 디스크로 Swap out 시키고, 해당 물리 메모리 영역으로 Swap in을 할 수 있도록 준비한다.

DiskRead(PTE.DiskAddr, PFN)
PTE.present = True
PTE.PFN = PFN

어느 영역으로 Swap in 할지 정했으니, PTE에 저장한 이전에 페이지를 swap out 해놓은 위치인 PTE.DiskAddr을 사용해 디스크로부터 해당 PFN이 가리키는 물리 메모리 위치에 페이지를 읽어들인다.

읽어들이고 나면 이젠 Swap 공간이 아니라 물리 메모리 위에 데이터가 들어 있는 것이므로 Present bit를 1로 설정해주고, 이젠 이전의 연결 정보가 아니라 방금 FindFreePhysicalPage나 EvitPage를 통해 얻어온 위치를 가리키는 PFN으로 연결 정보를 변경해줘야 한다.

RetryInstruction()

이제 문제 없이 Swap in을 마쳤으니, 중간부터 다시 시작하는게 아니라 메모리 액세스를 처리하는 맨 첫 부분으로 돌아가 원래 하려던 작업을 처리해주면 된다.

중요한 것이, 이때 TLB Miss를 처리한게 아니라 Page fault를 처리한 것이므로 여전히 TLB에 해당 PTE가 들어 있지 않아 당연히 TLB Miss가 발생하고, HW에서 다시 TLB Miss를 처리하는 부분으로 넘어가 이를 처리해준 다음 또다시 메모리 액세스 작업의 맨 첫부분으로 넘어간다는 것이다. 뭔가 같은 일 두 번 하는 것 같지만,, 저정도의 Low level에선 그게 더 쉬워서 그렇다니까 이해해주자. 규칙만 잘 이해하고 있으면 오히려 이쪽이 더 간단하다.

21.6. When Replacements Really Occur

지금까지 메모리가 부족해서 더이상 물러날 곳이 없는 극한 상황에만 Page replacement가 발생하는 것으로 생각했는데, 이런 저런 이유로 인해 끝까지 메모리 공간을 쥐어짜는게 아니라 어느정도 여유 공간을 확보하고 있어야 한다고 한다.

이 여유 공간을 관리하기 위해 OS는 High Watermark(HW), Low Watermark(LW)를 설정해놓는데, 만약 LW보다 메모리 여유 공간이 없어지면 Swap demon(=Page demon)이라는 백그라운드 스레드가 메모리 여유 공간이 HW에 도달할 때까지 막 swap out을 시켜 놓고 할 일을 마치면 다시 sleep mode로 전환된다고 한다.

또한 요즘은 Disk I/O 성능이 그렇게 나쁘지도 않아서 페이지를 하나씩 swap out하는게 아니라 한 번에 여러 페이지를 Cluster나 Group 단위로 묶어서 Swap 영역에 묻어 놓는다고 한다. DB 시간에 슬쩍 들은 것 같은데, 이런 방법을 통해 디스크의 탐색 작업이나 Rotational delay에서 발생하는 오버헤드를 줄일 수 있다고 한다.

마무리

Beyond Physical memory!

물리 메모리를 무한정 늘릴 수는 없으니, 그보다 싸고 넓은 HDD 따위를 사용하여 Memory hierarchy를 추가함으로써 마치 실제 물리 메모리의 크기보다 더 큰 영역을 사용하는 것처럼 할 수 있게 되었다. 뭔가 Swapping을 배우고 나니 TLB, Physical memory, Swap 영역 순서대로 메모리 계층이 눈에 더 잘 들어오는 것 같다.