Operating Systems : Three Easy Pieces를 보고 번역 및 정리한 내용들입니다.

여태까지는 실행 중인 프로세스의 모든 물리 공간을 메모리에 올려놓을 수 있다고 가정했지만, 이제는 실제 물리 공간보다 더 큰 주소 공간을 사용하고자 한다.

이를 위해서는 추가적인 메모리 계층이 필요하다. 지금까지는 모든 페이지들이 물리 메모리 위에 올라와있었지만, 이제부터 OS는 지금 당장은 크게 필요하지는 않은 주소 공간의 부분들을 어딘가(현대 시스템에서는 보통 하드 디스크 드라이브)에 치워 놓음으로써 더 큰 주소 공간을 사용하는 것처럼 만든다.

왜 한 프로세스가 그렇게 큰 주소 공간을 사용할 수 있게 해야할까? 편하기 때문이다. 큰 주소 공간이 있으면 프로그램의 자료 구조를 위한 충분한 공간이 메모리에 있는지를 걱정할 필요없이, 자연스럽게 프로그램을 작성하고 원하는 만큼 메모리를 할당하면 된다. OS는 동시에 실행되는 여러 프로세스들에게도 큰 가상 공간에 대한 환상을 제공할 수 있다.

어떻게 OS는 더 크고 느린 장치를 이용하면서도 투명하고 큰 가상 주소 공간의 환상을 제공할 수 있을까?

1. Swap Space

우리가 해야할 첫 번째 일은 디스크 공간의 일부를 페이지가 이동을 위해 예약해놓는 것이다. OS에서는 보통 그런 공간을 스왑 공간(swap space)라 부르는데, 우리가 메모리의 페이지를 그 공간으로 내보내고(swap out), 그 공간으로부터 페이지들을 가져오기(swap in) 때문이다.

OS가 페이지 크기의 단위로, 스왑 공간을 읽고 쓸 수 있다고 가정하자. 그러려면 OS는 해당 페이지의 디스크 주소를 기억해야 한다.

스왑 공간의 크기도 중요하다. 스왑 공간의 크기는 궁극적으로 특정 시간에 시스템에서 사용될 수 있는 메모리 페이지의 최대 수를 결정하기 때문이다. 지금은 간단하게 그 크기가 아주 크다고만 가정하자.

위 예시에서는 4 페이지의 물리 메모리, 8 페이지의 스왑 공간을 사용한다. 여기서 세 프로세스들(Proc 0, 1, 2)은 물리 메모리 공간을 공유하고 있는데, 이 프로세스들 각각은 자신의 유효 페이지의 일부만을 메모리에 가지고 있고, 나머지는 디스크의 스왑 공간에 두고 있다. 네 번째 프로세스 Proc3은 현재 실행되고 있지 않으며, 자신의 모든 페이지들을 디스크에 두고 있다.

단 꼭 스왑 공간에서만 스왑이 일어나는 것은 아니다. 예를 들어 어떤 바이너리 프로그램을 실행한다고 해보자. 이 바이너리 파일의 코드 페이지는 처음에는 디스크에 있다가, 프로그램이 실행되면 메모리에 올라간다. 만약 시스템이 어떤 이유로 물리적 메모리에 공간을 만들어야 하게 되면, 시스템은 그냥 그 코드 페이지의 메모리를 재사용하면 된다. 나중에 코드 페이지는 따로 스왑 공간으로 보내지 않고, 나중에 필요할 때 디스크를 읽어 다시 메모리로 불러들이면 된다.

2. The Present Bit

디스크에 공간이 생겼으니, 페이지를 디스크로 스왑 인/아웃하기 위한 장치가 필요하다. 간단히 하드웨어로 관리되는 TLB 시스템을 사용한다고 가정한다.

메모리 참조가 일어나면 어떤 일이 일어나는지 한 번 떠올려보자.

1. 실행 중인 프로세스가 가상 메모리 참조를 만든다.
2. 하드웨어는 이를 물리 주소로 변환한 후 원하는 데이터를 메모리로부터 가져와야 한다.
   1. 우선 가상 주소로부터 VPN을 추출하고, 해당 엔트리가 TLB에 있는지를 확인한다.
   2. (TLB hit) 물리 주소를 만들어 데이터를 메모리로부터 가져온다.
   3. (TLB miss) 메모리의 페이지 테이블로 해당 VPN을 인덱스로 하는 PTE를 찾는다.
   4. 만약 페이지가 유효하고 물리 메모리에 있다면, 하드웨어는 PFN을 PTE로부터 추출하고, 이를 TLB에 캐싱한 후 명령어를 재실행한다. 이번에는 TLB 히트가 일어난다.

만약 페이지를 디스크로 스왑하고 싶다면 추가적인 장치를 이용해야 한다. 하드웨어는 PTE의 present bit을 통해 해당 페이지가 현재 물리 메모리에 있는지, 없는지를 알 수 있다. 만약 present bit가 1이면 해당 페이지가 물리 메모리에 있다는 것이고, 0이라면 페이지가 물리 메모리가 아니라 디스크 어딘가에 있다는 것을 의미한다.

물리 메모리에 있지 않은 페이지에 접근하려 하면 페이지 폴트(page fault)가 일어나며, 페이지 폴트가 일어나는 경우 OS는 페이지 폴트 핸들러를 실행해 이를 처리해야 한다.

3. The Page Fault

TLB에는 하드웨어로 관리되는 TLB와 소프트웨어로 관리되는 TLB, 두 종류가 있는데, 두 시스템에서 모두 페이지 폴트는 OS가 처리한다.

페이지가 메모리에 올라와있지 않아 페이지 폴트가 일어난 경우, OS는 해당 페이지를 디스크로부터 메모리로 스왑 인해야 한다. 어떻게 OS는 원하는 페이지를 어디에서 찾을지 알 수 있을까? 이와 관련한 정보들은 보통 페이지 테이블에 저장된다.

1. OS는 PTE의 비트들을 이용해 PFN을 찾던 것처럼 해당 페이지의 디스크 주소를 찾는다.
2. 페이지 폴트 발생 시 OS는 PTE에서 주소를 찾고, 디스크로부터 해당 페이지를 가져오도록 요청한다.
3. 디스크 I/O 작업이 끝나면 OS는 페이지 테이블에 해당 페이지가 메모리에 있다고 표시하고, PTE의 PFN 필드에 새롭게 가져온 페이지의 메모리 내 주소를 갱신한 후, 명령을 재실행한다.
   1. 이때는 TLB 미스가 일어난다. 해당 페이지 테이블이 메모리에는 올라와있지만 TLB에는 캐싱되지 않았기 때문이다.
   2. TLB 미스가 일어났으므로 OS는 해당 변환을 TLB에 업데이트하고 명령을 재실행한다. 이번에는 TLB에서 변환을 찾을 수 있고, 원하던 데이터나 명령을 변환된 물리 주소로부터 가져올 수 있게 된다.

I/O 작업이 실행 중일 때 프로세스는 BLOCKED 상태에 있다. 따라서 OS는 페이지 폴트가 처리되고 있을 때 다른 대기 중인 프로세스를 실행해, 하드웨어를 효과적으로 활용하곤 한다.

4. What If Memory Is Full?

위에서는 메모리에 스왑 인 해오기에 충분한 공간이 있다고 가정했다. 그런데 메모리가 이미 꽉 차있다면 어떨까? OS는 하나 이상의 페이지들을 쫓아내고 새로운 페이지가 들어올 공간을 확보해야 한다.

이렇게 쫓아낼, 혹은 교체할 페이지를 찾는 과정을 페이지 교체 정책(page-replacement policy)이라 부른다. 잘못된 페이지 교체 정책은 프로그램을 메모리가 아닌 디스크의 속도로 실행되게, 현대의 기술로 따지자면 만 배~십만 배는 느리게 실행되게 할 수도 있다.

5. Page Fault Control Flow

아래는 하드웨어의 페이지 폴트 제어 흐름이다.

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)
			TLB_Insert(VPN, PTE.PFN, PTE.ProtectBits)
			RetryInstruction()
		else if (PTE.Present == False)
			RaiseException(PAGE_FAULT)

TLB 미스가 일어났을 때 고려해야할 세 가지 케이스가 있다.

1. 페이지가 메모리에 있고 유효한 경우(present & valid)
   • TLB 미스 핸들러는 PTE에서 PFN을 찾고 명령을 재실행한다.
2. 페이지가 유효하지만 메모리에는 있지 않은 경우
   • 페이지 폴트 핸들러가 실행된다.
3. 페이지가 유효하지 않은 경우
   • PTE의 다른 내용은 중요하지 않다. 하드웨어는 트랩을 발생시키고 OS 트랩 핸들러가 실행되어 해당 프로세스를 종료시키는 등의 작업을 한다.

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

위는 소프트웨어의 제어 흐름이다. OS는 폴트를 발생시킨 페이지를 위한 물리 프레임을 찾고, 만약 그럴 공간이 없다면 메모리에 해당 페이지를 위한 공간을 만들 때까지 대기한다.

물리 프레임이 들어오면 핸들러는 스왑 공간으로부터 페이지를 불러들이는 I/O 요청을 만들고, 이 작업이 끝나면 OS는 페이지 테이블을 업데이트하고 명령을 재실행한다. 재실행 됐을 때에는 TLB 미스가 일어나고, 다시 해당 명령을 재실행하면 TLB 히트가 일어나서 하드웨어는 원하던 데이터에 접근할 수 있게 된다.

6. When Replacements Really Occur

지금까지 OS는 메모리가 완전히 가득 찼을 때만 페이지를 교체한다고 가정했지만, 이는 실제와는 다르다. OS는 미리 조금의 메모리를 가용 상태로 유지한다. 이를 위해 대부분의 운영체제는 high watermark(HW), low watermark(LW)를 이용하는데, 이것들은 언제 메모리로부터 페이지를 쫓아낼지를 결정하기 위해 사용된다.

만약 LW보다 적은 페이지만 사용하고 있는 경우, OS는 메모리를 해제하는 데 쓰이는 백그라운드 스레드가 실행된다. 이 백그라운드 스레드는 스왑 데몬(swap daemon), 혹은 페이지 데몬(page daemon)이라 불리며, HW만큼의 페이지가 사용 가능해질 때까지 페이지들을 쫓아낸다.

이렇게 여러 개의 교체를 한 번에 수행하면 성능 최적화가 가능해진다. 많은 시스템들은 여러 페이지들을 하나로 묶어 한 번에 디스크의 스왑 파티션에 쓰는데, 이러한 클러스터링은 디스크의 탐색시간과 회전 지연시간을 줄이기에 디스크의 효율성 및 성능을 높인다.

백그라운드 페이징 스레드를 사용하려면 앞서 봤던 소프트웨어 제어 흐름이 조금 바뀌어야 한다. 위에서는 교체를 직접 진행했지만, 이제는 가용 페이지가 있는지의 여부만 간단히 체크하고, 만약 해당 페이지가 없다면 백그라운드 페이징 스레드에 가용 페이지가 필요하다는 걸 알려야 한다. 해당 스레드가 페이지들을 해제하면, 원래 사용하던 스레드를 깨우고 원하던 페이지를 불러들여 작업을 진행한다.

7. Summary

시스템의 물리 메모리보다 크게 메모리를 사용하는 방법에 대해 알아봤다.

페이지 테이블에서는 페이지가 현재 메모리에 있는지 아닌지를 표시하기 위해 present bit을 사용했다. 만약 해당 페이지가 현재 물리 메모리에 올라와 있지 않으면 OS는 페이지 폴트 핸들러를 실행해, 디스크로부터 원하는 페이지를 물리 메모리로 불러옴으로써 페이지 폴트를 처리한다.

이 일련의 행동들이 프로세스에게는 투명하게 일어난다는 점을 잊지 말자. 프로세스의 입장에서는 그저 자신의 고유한, 연속적인 가상 메모리에 접근할 뿐이지만, 사실 페이지는 물리 메모리의 임의의 장소에 위치해있거나, 심지어는 메모리에 있지 않을 수도 있다.