[OS]페이지 교체 알고리즘

📚페이지 교체 알고리즘

페이징 기법에서 모든 페이지 프레임이 사용되고 있을 때 메모리에 새로 적재되어야 할 페이지가 있다면 적절한 교체 대상 페이지 프레임을 선택하여 새로운 페이지를 적재해야 한다.

최적의 성과를 얻기 위해 페이지 프레임에 있는 페이지 중 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 선택하면 된다. 이것을 최적화 원칙이라고 하는데 이론적으로는 최적이지만 실제 프로세스가 어떻게 진행될지 미래를 예측할 수 없어서 구현이 불가능하다. 따라서 페이지 교체 알고리즘은 대체로 좋은 결론이면서 시간 및 공간의 오버헤드가 적은 방법을 선택하는 것이 좋다.

효율적인 동작을 위해 교체가 일어나지 않게 할 필요가 있는 페이지들도 있는데 예를 들어 페이징을 위한 커널 코드 영역, 커널에 속하지 못한 보조기억장치 드라이버 등이 있다.

📄FIFO 페이지 교체

FIFO(First-In First-Out) 페이지 교체 알고리즘은 메모리 내에 가장 오래 있었던 페이지를 교체 대상으로 선택하여 교체한다. 가장 먼저 들어온 페이지가 가장 오래 머물렀던 페이지 이기 때문에 FIFO 페이지 교체 알고리즘은 큐를 이용한다.

메모리에 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성이 높다. 그런데 FIFO 페이지 교체 알고리즘은 메모리에 가장 오래 있엇던 페이지를 교체시킴으로써 가장 많이 쓰이는 페이지를 교체시킬 가능성이 있다는 문제가 있다.

FIFO 페이지 교체 알고리즘은 Belady 이상현상이라는 단점도 가지고 있다. 프로세스에 더 많은 수의 페이지를 할당할 경우 오히려 페이지 부재가 더 많이 발생할 수 있는 현상을 Belady 이상현상이라고 한다.

📄LRU 페이지 교체

LRU(Least Recently Used) 페이지 교체 알고리즘은 메모리 내에서 가장 오랫동안 사용되지 않은 페이지를 교체 대상으로 선택하여 교체한다다. 이 기법은 국부성 휴리스틱에 의존하는 것인데 국부성이란 프로세스는 기억장치 내의 정보를 균일하게 액세스하는 것이 아니라 어느 한순간에 특정 부분을 집중적으로 참조한다는 것이다.

• 시간국부성: 처음에 참조된 기억장소가 가까운 미래에도 계속 참조된 가능성이 높다.
• 공간국부성: 하나의 기억장소가 참조되면 그 근처의 기억장소가 계속 참조되는 경향이 있다.

LRU 페이지 교체 알고리즘은 두 가지 방식으로 구현 가능하다.

1. 참조시간 이용
   각 페이지가 참조될 때마다 시각을 테이블에 기록한다. 교체가 필요한 경우 참조시간이 가장 오래된 페이지가 교체 대상으로 선택된다.

2. 리스트 이용
   메모리에 적재된 페이지 번호를 저장하는 리스트를 이용하여 페이지를 액세스하면 해당 페이지 번호를 리스트의 선두에 옮긴다. 이렇게 되면 참조시간이 가장 오래된 페이지가 리스트의 끝에 오게 된다. 따라서 페이지 교체가 필요한 경우 리스트의 끝에 있는 페이지가 교체 대상으로 선택된다.

LRU 기법은 Belady 이상현상이 발생하지 않고 최적화 원칙에 근사한 선택을 할 수 있다. 하지만 LRU는 매번 시간을 기록하거나 오래된 참조시간을 찾고 리스트를 유지하는 등 오버헤드가 크다는 단점이 있다.

📄LFU 페이지 교체

LFU(Least Frequently Used) 페이지 교체 알고리즘은 메모리 내에서 참조된 횟수가 가장 적은 페이지를 교체 대상으로 선택하여 교체한다.

LFU도 매번 참조 횟수를 증가시키고 가장 적은 참조 회수를 찾아야해서 오버헤드가 크다는 단점이 있다.

📄2차 기회 페이지 교체

2차 기회(second chance) 페이지 교체 알고리즘은 참조비트가 0이면서 메모리 내에 가장 오래 있었던 페이지를 교체 대상으로 선택하여 교체한다. 이 기법은 FIFO 페이지 교체를 보완한 기법이다.

2차 기회는 자주 참조되는 페이지가 교체되지 않고 메모리에 남아 있을 수 있게 한 차례 더 기회를 준다는 의미이다. 참조 비트는 페이지 프레임에 있는 페이지마다 부여된 값이고, 이것은 페이지가 계속 메모리에 있는 상태에서 추가로 해당 페이지가 참조되면 참조비트가 1이 된다.

참조할 페이지가 메모리에 존재하지 않고 페이지 프레임에 빈자리가 있다면 페이지를 페이지 프레임에 적재하고 큐에 추가한다. 그리고 참조 비트는 0으로 설정한다. 참조할 페이지가 메모리에 존재하지 않고 페이지 프레임이 가득 찼다면 페이지 교체 대상을 선택해야 한다.

2차 기회 페이지 교체 알고리즘에서 페이지 교체 대상을 선택하는 과정은 다음과 같습니다.

1. 큐의 선두 항목을 꺼내 참조 비트를 조사한다.
2. 참조 비트가 1이면 0으로 바꿔 큐의 뒤에 추가하고 1단계로 돌아간다.
3. 참조 비트가 0이면 그 페이지를 교체 대상으로 선택한다.

참조할 페이지의 참조 비트가 1이고 해당 페이지가 이미 메모리에 존재한다면 큐의 위치는 변화시키지 않고 해당 페이지의 참조 비트를 1로 다시 설정한다.

• 클럭 페이지 교체 알고리즘
  2차 기회 페이지 교체에서 변형된 큐로 페이지를 관리하는 기법이다.

📚프로세스별 페이지 집합관리

프로세스가 사용할 수 있는 페이지 프레임의 개수는 컴퓨터 시스템의 성능에 영향을 준다. 따라서 이 개수를 제한할 필요가 있다.

페이지 프레임 개수가 늘어나면 메모리에 적재될 수 있는 프로세스의 수는 줄어들지만 프로세스별 페이지 부재가 덜 발생할 수 있다.

반면에 페이지 프레임 개수가 줄어들면 메모리에 적재될 프로세스의 수는 늘어나고 시스템 처리량이 많아질 수 있다. 대신 프로세스별 페이지 부재가 자주 발생할 수 있다.

📄워킹 세트 알고리즘

워킹 세트(working set)는 한 프로세스가 최근에 참조한 페이지의 집합으로 페이지 부재비율을 감소시키기 위해 제안된 알고리즘이다. 프로세스의 워킹 세트 \(W(t, \delta)\)는 시각 t에 t를 포함한 직전 \(\delta\)시간 동안 참조한 페이지의 집합을 의미한다.

\(W(t, \delta)\)는 시각 \(t - \delta + 1\)부터 시각 \(t\)까지 참조한 페이지의 집합이다.

프로세스의 워킹 세트는 메모리 내에서 유지되어야하는데 그렇지 않은 경우 쓰래싱(thrashing)이 유발된다. 쓰래싱은 페이지 부재가 비정상적으로 많이 발생하여 프로세스 처리보다 페이지 교체 처리에 많은 시간을 소비하는 문제이다.

워킹 세트 알고리즘은 프로세스의 워킹 세트를 메모리에 유지시키는 것을 원칙으로 한다. 프로세스마다 워킹 세트의 크기에 맞게 페이지 프레임 개수를 조절한다.

📄PFF 알고리즘

PFF(Page Fault Frequency) 알고리즘은 페이지 부재 빈도를 이용하여 프로세스별 페이지 집합의 크기를 변화시키는 알고리즘이다.

페이지 부재 빈도는 페이지 부재가 얼마나 자주 일어나는지 나타내는 것으로 페이지 부재가 발생하면 직전 페이지 부재 이후로 경과된 시간의 역수로 정한다.

PFF 알고리즘은 페이지 부재 빈도의 상한과 하한을 정해두고 페이지 부재 빈도가 상한보다 높으면 페이지 프레임의 개수를 1 증가시키고, 하한보다 낮으면 페이지를 모두 제거하고 페이지 프레임 개수도 줄인다.