가상 메모리, 페이지 교체 [4 / 4]

junto·2024년 3월 17일

Operating System

operating system

목록 보기

10/13

운영체제가 물리 메모리 한계를 넘기 위해서 어떤 기법을 사용하고 있는지 알아본다. 추가로 필요한 페이지가 물리 메모리에 없을 때 동작 과정과 물리 메모리가 가득 찼을 때 페이지를 어떻게 교체하는지 살펴본다.

1. 스왑 공간(swap space)과 요구페이징(demand paging)

현대 가상 메모리는 물리 메모리뿐만 아니라 디스크 일부분을 스왑 공간(swap space)으로 지정하여 페이지들을 저장한다. 프로세스에게 큰 주소 공간을 제공하여 편리한 사용 환경을 제공하기 위함이다.
페이지를 읽어서 스왑 공간에 쓰고(swap out), 스왑 공간에서 페이지를 읽어 메모리에 탑재시킨다(swap in).
스왑 공간은 파일시스템 내부에 둘 수도 있으나 별도의 partition 사용이 일반적이다. 그 이유는 일반적인 파일시스템과 달리 오래 저장할 필요가 없고 속도가 중요하다. 일반 파일보다 자주 참조되므로 seektime을 최대한 줄이는 것이 중요하다.
운영체제는 요구 페이징(demand paging) 정책을 사용하여 "요청된 후 즉시", 페이지가 실제로 접근될 때 해당 페이지를 메모리로 읽어 들인다. 실제로 운영체제는 디스크 전체 파일시스템에서 필요한 메모리를 스왑 공간으로 가져올 수 있다.
Runtime binding을 통해 프로세스의 가상 주소를 물리 주소로 실행 중에 변환할 수 있으며, 이는 요구 페이징 기법과 스왑 공간으로 인해 메모리 가상화 기법을 더욱 효과적으로 만든다.

만약 요청된 페이지가 메모리에 없다면? 하드웨어(MMU)는 주소 변환 중 트랩을 발생시킨다. 운영체제는 페이지 폴트 핸들러 처리 루틴에 따라 처리한다.

2. 페이지 폴트(page fault)

디스크에서 페이지를 가져오는 작업은 I/O 작업(특권 명령)이므로 프로세스가 직접 할 수 없다. 따라서 메모리에 페이지가 없다면 트랩이 발생하여 운영체제가 swap in을 하게 된다.

1) 동작 과정

요청한 페이지가 메모리에 없거나(present bit) 사용 권한이 없을 때(protection bit) MMU는 트랩을 발생시킨다.
운영체제가 CPU 제어권을 얻어 page fault handler를 실행한다.
페이지의 디스크 위치를 파악한 후 메모리로 올린다.
I/O 작업이 완료되면 Blocked된 프로세스는 Ready 상태가 되고, PTE에 올바른 PFN 값으로 갱신한다.
페이지 폴트를 발생시킨 명령어를 재실행한다.

2) 하드웨어 동작(하드웨어 기반 TLB 가정)

VPN = (VirtualAddress & VPN_MASK) >> SHIFT
(Success, TlbEntry) = TLB_Lookup(VPN)
if (Success == True)		// TLB 히트
	if (CanAccess(TlbEntry.ProtectBits) == True)
    	Offset = VirtualAddress & OFFSET_MASK
        PhysAddr = (TlbEntry.PFN << SHIFT) | Offset
        AccessMemory(PhysAddr)
    else
    	RaiseException(PROTECTION_FAULT)
else
	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 미스 발생 시 페이지가 존재하며 유효한 경우, 페이지가 유효하지만 존재하지 않는 경우, 페이지가 유효하지 않은 경우를 나누어 처리하는 것을 볼 수 있다.

3) 운영체제 동작

PFN = FindFreePhysicalPage();
if (PFN == 1)
	PFN = EvictPage()			// 교체 알고리즘 실행
    DiskRead(PTE.DiskAddr, pfn) // I/O 대기
    PTE.present = True			// 페이지가 존재한다고 갱신
    PTE.PFN = PFN				// 비트와 변환(PFN)
    RetryInstruction			// 명령어 재시도

3. 페이지 교체 정책(page replacement policy)

페이지 폴트(page fault)가 발생하고 필요한 페이지를 디스크에서 가지고 왔다면 이를 물리 메모리에 올려야 한다. 하지만 물리 메모리가 가득 차 있다면? 내보낼 페이지를 결정해야 한다. 이를 페이지 교체 정책(page replacement policy)이라고 한다.

1) 최적 교체 정책(The Optimal Replacement Policy)

가장 나중에 접근될 페이지를 교체하는 것이 최적이며, 가장 적은 페이지 폴트를 발생시키는 것을 belady가 증명하였다. 간단하지만 구현하기 어려운 정책이다.
다른 알고리즘을 평가할 때 상한을 제시하여 평가 기준이 된다.
캐시 히트율은 6 / 11 이므로 54.5%가 된다.

2) 선입선출(FIFO, First In First Out)

먼저 들어온 것이 먼저 나가는 선입선출 교체 방식이다. 구현하기 쉬우나 성능은 좋지 않다.
캐시 크기가 커지면 캐시 히트율이 높아져야 하지만 반대로 떨어지는 이상 현상(anomaly)이 발생할 수 있다.
캐시 히트율은 4/11 이므로 36.4%가 된다.

3) 무작위(random)

무작위로 선택한 페이지와 교체하는 방식이다. 운에 의존하며 일반적으로 FIFO보다는 성능이 좋고 최적보다는 성능이 떨어진다.

4) LRU(Least Recently Used)

가장 덜 최근에 사용한, 가장 오래된 페이지를 제거한다.
최근에 참조되었다면 우선순위를 가장 높이는 식으로 구현한다. $O(1)$ 로 검색할 수 있다.

5) LFU(Least Frequently Used)

가장 덜 빈번하게 사용한, 가장 낮은 빈도로 사용된 페이지를 교체한다.
참조되면 비교를 통해 순위를 결정해야 한다. 최소 비교 횟수가 되기 위해 힙 자료구조를 사용한다. $O(log n)$ 시간복잡도를 가진다.

LRU와 LFU는 지역성을 잘 고려한다. 공간 지역성이란 해당 페이지가 참조되었다면 그 주변의 페이지가 참조된다는 경향이 있다는 것이고, 시간 지역성이란 해당 페이지가 참조되었다면 가까운 미래에 다시 접근되는 경향이 있다는 것을 말한다. MFU, MRU와 같은 알고리즘도 있지만 지역성을 무시하기에 잘 동작하지 않는다.

워크로드에 따른 성능

무작위 워크로드에 대해선 어떤 정책을 사용하든 비슷한 성능을 보인다. 이와 비슷하게 캐시가 충분히 커서 모든 워크로드를 포함하는 경우도 마찬가지다.
80대 20 워크로드는 20%의 페이지에서 80%의 참조가 발생하고, 80%의 페이지에서 20%의 참조가 발생한다고 가정한다. 랜덤과 FIFO 정책이 좋은 성능을 보이고, 인기 있는 페이지들을 캐시에 더 오래두는 LRU는 더 좋은 성능을 보인다.
순차탐색 워크로드는 x개의 페이지를 순차적으로 참조한다. 이 경우 LRU와 FIFO에서 가장 안 좋은 성능을 보이고, 무작위 선택 전략은 눈에 띄게 좋은 성능을 보인다.

Clock Algorithm(reference bit, dirty bit)

페이지 교체 정책에서 LRU와 LFU를 구현할 수 있을까? 사실 운영체제만으론 구현할 수 없다. 운영체제는 페이지 폴트가 발생했을 때의 경우에만 프로세스가 어떤 페이지를 참조하는지 알 수 있기 때문이다. 하드웨어의 지원이 필요하다.

LRU를 구현하기 위해서는 페이지 접근이 있을 때마다 하드웨어가 메모리의 시간 필드를 갱신하도록 할 수 있다. 하지만 시스템의 페이지 수가 증가하면 페이지들의 시간 정보 배열을 검색하여 가장 오래전에 사용된 페이지를 찾는 것은 매우 고비용의 연산이 된다.

꼭, 가장 오래된 페이지를 찾아야 할까? 비슷하게 오래된 페이지를 찾으면 되지 않을까?
LRU 근사 알고리즘인 Clock Algorithm에 대해 알아보자.
시침이 시계 방향으로 회전하면서 특정 페이지를 가리킨다. reference bit이 1이라면 0으로 바꾼다. 해당 페이지 reference bit이 0이라면 시곗바늘이 한 바퀴 돌아가는 동안 참조가 없었다는 것을 의미하므로 교체 대상으로 정한다.
페이지 수정 여부(dirty bit)를 고려할 수 있다. 어떤 페이지가 변경되어 dirty상태가 되었다면, 페이지를 내보내기 위해 I/O 작업을 해야 하므로 추가 비용이 든다. 따라서 최근에 참조되지 않았고 수정되지 않은 페이지들을 우선 교체대상으로 정한다.

4. Thrashing

어떤 프로그램에 최소한의 메모리 페이지가 할당되지 않을 때, 시스템이 끊임없이 페이징하는 현상을 말한다.
page fault 비율이 매우 높아지고, CPU 이용률이 매우 낮아진다. 운영체제는 CPU를 더 사용해야 한다고 생각하여 더 많은 프로세스를 메모리에 올린다.

1) Working-set

워킹 셋이란 프로세스가 실행 중에 일정 시간 동안 사용하는 페이지들의 집합을 말한다.
process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않은 경우 모든 frame을 반납한 후 swap out한다. (suspend)
쓰레싱을 방지한다.