가상 메모리 관리

DanChu 🌟·2022년 8월 19일

요구 페이징, Demand Paging

프로그램 실행 시 운영체제는 프로세스를 구성하느 모듈을 전부 메모리에 올리지 않는다. 대신 필요한 모듈만 메모리에 올려 실행하고 나머지 모듈은 필요하다고 판단될 때(프로세스가 요청할 때) 메모리로 불러온다. 이렇게 사용자가 요구할 때 해당 페이지를 메모리로 가져오는 것을 요구 페이징 demand paging 이라고 한다.

참고로, 프로세스를 구성하는 모든 페이지를 메모리에 올리는 것을 순수한 스와핑 swapping 이라 하고, 사용자가 요구할 때 메모리에 올리는 것을 게으른 스와퍼 lazy swapper 라고 한다.

Page Fault

가상 메모리의 크기는 물리 메모리와 스왑 영역을 합친 것인데, 가상 메모리 시스템에서 사용자의 프로세스는 물리 메모리와 스왑 영역 중 한 곳에 있다. 이때 페이지가 물리 메모리와 스왑 영역 중 어디에 있는지를 표시하기 위해 페이지 테이블을 만들어 관리하고, 이는 유효 비트를 사용한다. 0 일때는 페이지가 메모리에 있어서 주소 필드에 물리 메모리의 프레임으로 번호가 저장되며, 1일때는 스왑영역에 있어서 주소 필드에 스왑 영역 내 페이지 주소가 저장된다.

이렇게 페이지 테이블에서 유효 비트를 1을 가진 스왑 영역에 있는 페이지들이 요청되었을 때 페이지 부재 page fault 가 일어난다고 한다. 페이지 부재 page fault가 일어나면 프로세스가 해당 페이지를 사용할 수 있도록 스왑 영역에서 물리 메모리로 옮겨야 한다.

Victim Page

위의 페이지 부재 page fault 상황에서 스왑 영역에 있는 요청된 페이지는 메모리의 빈 영역에 올리고 페이지 테이블은 갱신(업데이트)된다. 이때, 메모리에 빈 프레임이 없는 경우에는 메모리에 있는 프레임 중 하나르 스왑 영역으로 내보낸 후 해당 페이지를 가져올 수 있다. 어떤 페이지를 스왑 영역으로 내보낼지 결정하는 알고리즘을 페이지 교체 알고리즘 page replacement algorithm 이라 하며, 페이지 교체 알고리즘에 의해 스왑 여역으로 보내지는(스왑 아웃 되는) 페이지를 대상 페이지 victim page 라 한다.

페이지 교체 알고리즘

FIFO, first-in first-out

가장 먼저 메모리에 올라온 페이지 순서대로 먼저 내보내는 알고리즘이다. 들어온 시간을 저장하거나 올라온 순서를 큐를 이용해 저장할 수 있고, 구현은 간단하나 성능이 좋지 않다. Belady's Anomaly 현상이 발생할 수 있다

Belady's Anomaly

프레임의 개수가 많아져도 페이지 부재 page fault가 줄어들지 않고 늘어나는 현상을 말한다. 직관적으로 생각한다면 프레임 개수와 페이지 부재 횟수는 반비례 해야할 것 같지만, FIFO 알고리즘에선 그렇지 않을 수 있다.

OPT, optimal

앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 알고리즘이다. 프로세스가 앞으로 사용할 페이지를 미리 알아야 하기때문에 실제로 구현하기는 거의 불가능하다. 따라서 실제로 사용하기보단 연구 목적을 위해 사용된다.
모든 페이지 교체 알고리즘 중 페이지 부재 page fault 발생이 가장 적으며, Belady's Anomaly 현상이 발생하지 않는다.

LRU, Least Recently Used

가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘으로 (시간 지역성 temporal locality 고려), 최적 알고리즘과 비슷한 효과를 낼 수 있다. 페이지마다 카운터를 두고 사용된 시간을 알 수 있는 부분을 저장한다. 큐로 구현 가능하며, 성능이 좋은편이고 많은 운영체제가 채택하는 알고리즘이다. 하지만 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야 하므로 막대한 오버헤드가 발생할 수 있고, 카운터나 큐, 스택과 같은 별도의 하드웨어가 필요하다.

LFU, Least Frequently Used

LFU 알고리즘은 참조횟수가 가장 적은 페이지를 교체하는 알고리즘이다. 교체 대상이 여러 개라면 가장 오랫동안 사용하지 않는 페이지를 교체한다. LRU는 직전 참조된 시점만을 반영하지만, LFU는 참조횟수를 통해 장기적 시간규모에서의 참조성향을 고려할 수 있다.
단점으로는 가장 최근에 불러온 페이지가 교체될 수 있으며, 구현이 복잡하고 막대한 오버헤드가 발생할 수 있다.

MFU, Most Frequently Used

LFU와 반대로 참조 횟수가 가장 많은 페이지를 교체하는 알고리즘이다. 가장 많이 사용되었기 때문에 앞으로는 사용되지 않을 것이라 가정하는 알고리즘.

NUR, Not Used Recently (= NRU, Not Recently Used)

클럭 알고리즘이라고도 하며, LRU, LFU 페이지 교체 알고리즘과 성능이 거의 비슷하면서도 하드웨어적 자원을 통해 불필요한 공간 낭비를 해결한(오버헤드를 줄인) 알고리즘이다.
LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정하지만, LRU와 달리 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다.

클럭 알고리즘은 참조 비트 reference bit 를 순차적으로 조사하며 동작한다.

1. 프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅
2. 알고리즘이 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나간다
3. 참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체

페이지가 참조되어 1이 되고, 한 바퀴 도는 동안 사용되지 않으면 다시 0이되고 다시 한 바퀴를 도는 동안 사용되지 않는 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정하는 알고리즘이다. 동일 그룹 내에서는 무작위로 선택되며, 실제 구현시 각 페이지마다 참조 비트 reference bit 와 변형 비트 modified bit, birty bit 가 사용된다. 두 비트 사이에서는 참조 비트가 변형비트보다 우선순위가 높다.

클럭 알고리즘은 시계 바늘이 한 바퀴 도는 동안 걸리는 시간만큼 페이지를 메모리에 유지시켜 페이지 부재율을 줄이도록 설계되었다. 때문에 클럭 알고리즘을 2차 기회 알고리즘 이라 부르기도 한다.