2-14장. 물리 메모리 크기의 극복 : 메커니즘

지금까지 살펴보았던 내용들은 가상 주소 공간이 비현실적으로 작아서 모두 물리 메모리에 탑재가 가능했다. 만약 가상 주소 공간이 큰 프로세스들 여러 개를 실행한다면 물리 메모리는 더 이상 할당을 받을 수 없으므로 문제가 생길 것이다.

 

이 문제를 완화하기 위해서 메모리 계층의 추가가 필요하다. 느리지만 매우 큰 용량의 메모리를 사용하는 것이다. 시스템에서 이 역할을 하드 디스크 드라이브가 담당한다. 이제 메모리 계층에서 크고 느린 하드 디스크 드라이브가 가장 하부에 위치하고, 그 위에 메모리가 있다.

 

왜 굳이 "큰" 주소 공간이 필요한 것일까? 이에 대한 답은 편리함과 사용 용이성이다. 주소 공간이 충분히 크면, 충분한 메모리 공간이 있는지 걱정하지 않아도 된다. 그냥 운영체제에게 요청하기만 하면 된다.

 

스왑 공간이 추가되면 운영체제는 실행되는 각 프로세스들에게 큰 가상 메모리가 있는 것 같은 환상을 줄 수 있다. 멀티프로그래밍 시스템(동시에 여러 프로그램을 실행시키는 것)이 발명되면서 많은 프로세스들의 페이지를 모두 물리 메모리에 저장하는 것이 불가능하게 되었다. 그래서 일부 페이지들을 스왑 아웃하는 기능이 필요하게 되었다.

 

멀티프로그래밍 시스템과 사용 편의성 등을 이유로 더 많은 용량의 메모리가 필요하게 되었다.이제 어떠한 방식으로 큰 용량의 메모리를 가상 메모리로 사용할 수 있는지를 알아보자.

 

스왑 공간

가장 먼저할 일은 디스크에 페이지들을 저장할 수 있는 공간을 확보하는 것이다. 이 용도의 공간을 스왑 공간(swap space)이라고 한다. 운영체제는 스왑 공간에 있는 모든 페이지들의 디스크 주소를 기억해야 한다. 메모리 페이지를 읽어서 스왑 공간에 쓰고, 스왑 공간에 있는 페이지를 읽어 메모리에 탑재시킨다. 그렇기 때문에 스왑 공간의 크기는 매우 중요하다. 시스템이 사용할 수 있는 메모리 페이지의 최대수를 결정하기 때문이다.

 

위 그림을 토대로 간단한 예제를 보도록 하자. 물리 메모리와 스왑 공간에는 각각 4개의 페이지와 8개의 페이지를 위한 공간이 존재한다. 이 예에서는 세 개의 프로세스(Proc 0, 1, 2)가 물리 메모리를 공유하고 있다. 나머지 페이지들은 디스크 공간으로 스왑 아웃 되어 있다. Proc 3은 현재 실행 중이 아닌 것이 분명하다. 

 

스왑 영역에 하나의 블럭이 비어있다. 스왑 공간을 이용하면, 시스템에 실제 물리적으로 존재하는 메모리 공간보다 더 많은 공간이 존재하는 것처럼 가장할 수 있다는 것을 알 수 있다.

 

Present Bit

디스크에 스왑 공간을 확보했으니 이제 페이지 스왑을 위한 기능을 다룰 차례이다. 하드웨어 기반의 TLB를 사용하는 시스템을 가정한다.

 

우선 메모리가 참조되는 과정을 상기해 보자(TLB 과정). 프로세스가 가상 메모리 참조를 생성한다. (명령어 탑재, 데이터 접근 등) 하드웨어는 메모리에서 원하는 데이터를 가져오기 전에, 우선 가상 주소를 물리 주소로 변환한다.

 

하드웨어는 가상 주소에서 VPN을 추출한 후 TLB에 해당 정보가 있는지 검사한다.(TLB 히트) 만약 히트가 되면 물리 주소를 얻은 후 메모리로 가져온다. 정말 빠른 작업이며 추가적인 메모리 접근이 필요없다.

 

만약 VPN을 TLB에서 찾을 수 없다면 (TLB 미스), 하드웨어는 페이지 테이블의 메모리 주소를 파악하고 (페이지 테이블 베이스 레지스터를 사용), VPN을 인덱스로 하여 원하는 페이지 테이블 항목(PTE)을 추출한다. 항목이 유효하고 관련 페이지가 물리 메모리에 존재한다면 하드웨어는 PTE에서 PFN 정보를 추출하고 그 정보를 TLB에 탑재한다. 탑재 후 명령어를 재실행하면 TLB 히트가 될 것이다. 여기까지는 순조롭다.

 

페이지가 디스크로 스왑되는 것을 가능하게 하려면, 많은 기법들이 추가되어야 한다. 특히, 하드웨어가 PTE에서 해당 페이지가 물리 메모리에 존재하지 않는다는 것을 표현해야 한다. 하드웨어는 present bit를 이용하여 각 페이지 테이블 항목에 어떤 페이지가 존재하는지를 표현한다.

 

present bit가 1로 설정되어 있다면, 물리 메모리에 해당 페이지가 존재한다는 것이고 위에 설명한 대로 동작한다. 만약 0으로 설정되어 있다면, 메모리에 해당 페이지가 존재하지 않고 디스크 어딘가에 존재한다는 것을 나타낸다. 물리 메모리에 존재하지 않는 페이지를 접근하는 행위를 일반적으로 페이지 폴트(page fault)라 한다.

 

페이지 폴트가 발생하면, 페이지 폴트를 처리하기 위해 운영체제로 제어권이 넘어간다. 페이지 폴트 핸들러(page fault handler)가 실행된다. 

 

페이지 폴트

페이지 폴트가 발생하면 운영체제에서 처리를 담당하며, 페이지 폴트 핸들러가 그 처리 메커니즘을 규정한다. 

 

만약 요청된 페이지가 메모리에 없고, 디스크로 스왑되었다면, 운영체제는 해당 페이지를 메모리로 스왑해 온다. 많은 시스템들에서 해당 페이지의 스왑 공간상에서의 위치를 페이지 테이블에 저장한다. 운영체제는 PFN과 같은 PTE비트들을 페이지의 디스크 주소를 나타내는 데 사용할 수 있다. 페이지 폴트 발생 시, 운영체제는 페이지 테이블 항목에서 해당 페이지의 디스크 상 위치를 파악하여, 메모리로 탑재한다.

 

디스크 I / O가 완료되면 운영체제는 해당 페이지 테이블 항목의 PFN 값을 탑재된 페이지의 메모리 위치로 갱신한다. 이 작업이 완료되면 페이지 폴트를 발생시킨 명령어가 재실행된다. 재실행하면 TLB 미스가 될것이고 이미 해당 페이지를 가져왔으므로 TLB값이 갱신된다. 마지막으로 재실행 시 TLB 히트가 되며 주소 변환 정보를 찾게 되고, 이를 이용하여 물리 주소에서 원하는 데이터나 명령어를 가져온다.

 

메모리에 빈 공간이 없다면?

메모리에 여유 공간이 없다면, 탑재하고자 하는 새로운 페이지를 위한 공간을 확보하기 위해 하나 또는 그 이상의 페이지들을 먼저 페이지 아웃(page out) 하려고 할 수도 있다. 교체(replace) 페이지를 선택하는 것을 페이지 교체 정책(page-replacement policy)이라고 한다.

 

페이지 교체 정책이 잘못된 선택을 하는 경우 성능에 큰 악영향을 미친다. 잘못된 선택을 할 경우, 프로그램이 메모리 속도로 실행하는 것이 아니라 디스크와 비슷한 속도로 동작할 수도 있기 때문이다.(이는 프로그램이 10000 ~ 100000배 정도 더 느리게 실행되는 것을 의미한다) 

 

페이지 폴트 처리

다음 그림은 페이지 폴트 처리의 과정을 나타낸다.

 

다음은 하드웨어에서의 페이지 폴트 처리 알고리즘이다.

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)

TLB 미스 발생 시, 세 가지의 중요한 경우가 있다는 것을 알 수 있다. 첫째는 페이지가 존재하며 유효한 경우이다. 이 경우에는 TLB 미스 핸들러가 PTE에서 PFN을 가져와서 명령어를 재시도 한다. 두 번째 경우에는 페이지가 유효하지만 존재하지 않는 경우다. 페이지 폴트 핸들러가 반드시 실행되어야 한다. 프로세스가 사용할 수 있는 제대로 된 페이지이기는 하지만 물리 메모리에 존재하지 않기 때문이다. 세 번째, 페이지가 유효하지 않은 경우이다. 프로그램 버그 등으로 잘못된 주소를 접근하는 경우의 처리를 나타낸다. 이 경우에는 PTE의 다른 비트는 의미가 없다. 하드웨어는 이 무효한 접근이 운영체제의 트랩 핸들러에 의해서 처리되도록 한다. 이때 문제를 일으킨 프로세스는 종료될 수 있다.

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 

다음 코드에서 운영체제가 페이지 폴트를 처리하는 과정을 대략적으로 볼 수 있다. 먼저 운영체제는 탑재할 페이지를 위한 물리 프레임을 확보한다. 만약 여유 프레임이 없다면, 교체 알고리즘을 실행하여 메모리에서 페이지를 내보내고 여유 공간을 확보한다. 물리 프레임을 확보한 후, I/O 요청을 통해 스왑 영역에서 페이지를 읽어 온다. 마지막으로 이 느린 작업이 완료되면 운영체제는 테이블을 갱신하고 명령어를 재시도한다. 이때 TLB 미스가 나고, 한 번 더 재실행 하면 TLB 히트가 된다. 그제서야 하드웨어는 원하는 것을 접근할 수 있게 된다.

 

교체는 실제 언제 일어나는가?

메모리에 항상 어느 정도의 여유 공간을 비워두기 위해서, 대부분의 운영체제들은 여유 공간에 관련된 최댓값(high watermark, HW)과 최솟값(low watermark, LW)을 설정하여 교체 알고리즘 작동에 활용한다. 동작 방식은 다음과 같다. 운영체제가 여유 공간의 크기가 최솟값보다 작아지면(즉 메모리가 꽉차면) 여유 공간 확보를 담당하는 백그라운드 쓰레드가 실행된다. 이 쓰레드는 여유 공간의 크기가 최댓값에 이를 때까지 페이지를 제거한다. 이 백그라운드 쓰레드는 일반적으로 스왑 데몬(swap daemon) 또는 페이지 데몬(page daemon)이라고 불린다. 충분한 여유 메모리가 확보되면 이 백그라운드 쓰레드는 슬립모드로 들어간다.