페이지 교체 알고리즘 (Page Replacement Algorithm)

벨라디의 모순

직관적으로는 프레임을 늘리면 페이지 폴트가 줄어야 하지만, FIFO에서는 프레임을 늘렸는데 폴트가 오히려 늘어나는 경우가 있다. 이를 벨라디의 모순(Belady's anomaly)이라고 한다. 참조열 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5를 FIFO로 처리하면 프레임 3개일 때 폴트 9회, 4개일 때 10회가 나온다. LRU처럼 프레임 n개일 때의 내용이 항상 n+1개일 때의 내용에 포함되는 스택 알고리즘(stack algorithm)에서는 이런 모순이 일어나지 않는다. 프레임 증설이 늘 해답은 아니며 알고리즘의 성질이 중요하다는 것을 보여 주는 사례다.

클럭 알고리즘의 동작

정확한 LRU는 매 메모리 접근마다 기록을 갱신해야 해서 부담이 크다. 클럭 알고리즘은 페이지마다 하드웨어가 자동으로 켜 주는 참조 비트(reference bit) 하나만 이용한다.

프레임들을 원형으로 배치하고 시곗바늘을 둔다
교체가 필요할 때:
  바늘이 가리키는 페이지의 참조 비트를 본다
    비트가 1이면: 0으로 지우고 바늘을 다음으로 옮긴다 (한 번 더 기회)
    비트가 0이면: 이 페이지를 희생자로 선택한다
최근에 접근된 페이지는 비트가 1이므로 최소 한 바퀴는 살아남는다

수정 비트(dirty bit)까지 함께 보아, 참조도 안 되고 수정도 안 된 페이지를 최우선으로 내보내는 개선판도 있다. 실제 리눅스는 페이지를 활성(active)과 비활성(inactive) 리스트로 나눠 관리하는 LRU 근사 방식을 쓰며, 최근 커널은 세대 단위로 페이지 나이를 관리하는 다세대 LRU(Multi-Gen LRU)로 정확도와 비용의 균형을 더 끌어올렸다.

스래싱과 작업 집합

교체 알고리즘이 아무리 좋아도 프로세스가 실제로 필요로 하는 페이지 집합이 할당된 프레임보다 크면, 내보낸 페이지를 곧바로 다시 불러오는 일이 반복된다. 시스템이 실질적인 일보다 페이지 교체에 시간을 다 쓰는 이 상태가 스래싱(thrashing)이다. 스래싱이 시작되면 CPU 이용률이 급락하는데, 이를 보고 다중 프로그래밍 정도를 더 올리면 상황이 악화되는 악순환이 생긴다. 해법은 각 프로세스가 최근에 참조한 페이지 집합, 즉 작업 집합(working set)을 추정해 그만큼의 프레임을 보장하고, 보장할 수 없으면 일부 프로세스를 통째로 내리는 것이다. 페이지 폴트 빈도(PFF, Page Fault Frequency)를 상한과 하한 사이로 유지하도록 프레임을 조절하는 방식도 같은 목적의 실용적 기법이다.

면접에서 이렇게 물어본다

• 페이지 폴트가 발생했을 때 운영체제가 처리하는 과정을 순서대로 설명해 보라.
• LRU가 OPT의 근사가 되는 근거인 지역성 원리를 설명해 보라.
• 벨라디의 모순이 무엇이고 어떤 알고리즘에서 왜 발생하는가.
• 정확한 LRU 대신 클럭 알고리즘을 쓰는 이유와 그 동작 방식을 설명해 보라.
• 스래싱의 원인과 작업 집합 모델이 이를 어떻게 막는지 말해 보라.