요구 페이징과 페이지 교체 알고리즘, Thrashing

요구 페이징

가상 메모리에서는 프로세스를 실행할 때 필요한 부분만 메모리에 올린다. 요구 페이징(Demand Paging)은 CPU가 해당 페이지를 요구할 때까지 그 페이지를 메모리에 올리지 않는 방식이다.

Page Fault 처리 과정

참조하려는 페이지가 메모리에 없는 경우를 Page Fault(페이지 부재)라고 한다.

1. 특정 페이지를 참조하기 위해 페이지 테이블을 확인해 메모리에 올라와 있는지 본다.
2. 페이지가 메모리에 없으면 MMU가 트랩(인터럽트)을 발생시킨다.
3. 운영체제는 해당 프로세스를 대기 상태로 만들고, 요구된 페이지를 디스크에서 찾는다.
4. 찾은 페이지를 메모리의 자유 프레임(Free Frame)에 적재한다.
5. 페이지 테이블을 갱신한다.
6. 트랩으로 중단되었던 명령을 다시 수행한다. (대기 상태였던 프로세스를 다시 실행한다.)

자유 프레임이 없다면 메모리에 있는 페이지 중 하나를 내보내야 한다. 어떤 페이지를 내보낼지 정하는 것이 페이지 교체 알고리즘이다.

페이지 교체 알고리즘

알고리즘	교체 대상
FIFO	가장 먼저 메모리에 올라온 페이지
LRU (Least Recently Used)	가장 오랫동안 사용되지 않은 페이지
LFU (Least Frequently Used)	참조 횟수가 가장 적은 페이지
MFU (Most Frequently Used)	참조 횟수가 가장 많은 페이지

• FIFO는 단순하지만, 프레임을 늘리면 페이지 부재율이 줄어들어야 하는데 오히려 줄지 않는 경우가 생길 수 있다. (Belady의 모순)
• LRU는 성능이 좋아 가장 널리 쓰이는 방식이다.

LRU가 이용하는 특성

최근에 참조된 정보는 다시 참조될 확률이 높다는 시간 지역성을 이용한다. 반대로 오랫동안 참조되지 않은 페이지는 앞으로도 참조되지 않을 가능성이 높다고 보고 교체한다.

LRU 구현

from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

참조할 때마다 해당 항목을 맨 뒤로 옮기고, 용량을 넘으면 맨 앞(가장 오래전에 사용한 항목)을 제거한다.

Thrashing

프로세스가 집중적으로 사용하는 페이지들의 집합이 메모리에 한꺼번에 적재되지 못해 페이지 부재율이 높아지고, CPU 이용률이 급격하게 떨어지는 현상이다.

발생 과정

다중 프로그래밍 정도(MPD)는 메모리에 동시에 올라가 있는 프로세스의 수다. 프로세스가 I/O 작업을 하느라 준비 큐가 비면, 운영체제는 CPU 이용률을 높이려고 메모리에 올리는 프로세스의 수를 늘린다.

1. MPD가 높아지면 프로세스 하나에 할당되는 메모리의 양이 줄어든다.
2. 프로세스가 원활하게 수행되는 데 필요한 최소한의 페이지 프레임을 할당받지 못해 페이지 부재가 빈번하게 발생한다.
3. 페이지 부재를 처리하려면 디스크 I/O를 거쳐야 하므로 CPU 이용률이 급격히 떨어진다.
4. CPU 이용률이 낮으므로 운영체제는 MPD를 높이려고 또 다른 프로세스를 메모리에 적재한다.
5. 이 악순환이 반복된다.

Thrashing을 완화하는 방법

Working Set

지역성 집합이 메모리에 동시에 올라가도록 보장하는 메모리 관리 알고리즘이다.

• 워킹셋은 한꺼번에 메모리에 올라가 있어야 하는 페이지들의 집합이다. 윈도우 크기 Δ를 정해, 시각 t를 기준으로 직전 Δ 동안 참조된 페이지들의 집합으로 결정한다.
• 프로세스의 워킹셋을 구성하는 페이지들이 한꺼번에 올라갈 메모리 공간이 있을 때만 그 프로세스에 메모리를 할당한다.
• 공간이 충분하지 않으면 프로세스의 페이지들을 디스크로 스왑 아웃해 공간을 확보한다.

Page Fault Frequency (페이지 부재 빈도)

페이지 부재율을 주기적으로 조사하고, 그 값에 따라 각 프로세스에 할당할 메모리 양을 동적으로 조절한다.

• 페이지 부재율이 미리 정해 놓은 상한값을 넘으면 페이지 프레임을 더 할당한다.
• 하한값 아래로 떨어지면 할당한 페이지 프레임을 줄인다.
• 이렇게 해서 메모리에 올라가 있는 프로세스의 수도 조절된다.

참고

• 개선된 LRU 알고리즘