[OS] 8. 페이지 교체 알고리즘 (Page Replacement Algorithm)

페이지 교체 알고리즘 (Page Replacement Algorithm) : 페이지 폴트 시 교체할 페이지 선택

페이지 폴트 시 교체할 페이지를 선택할 때, 교체한 페이지가 다시 필요해져 페이지 폴트가 발생하는 비율을 줄여야 한다. 따라서 자주 사용되지 않을 페이지를 선택해야 하며, 제거할 페이지 중 최고의 페이지는 가장 긴 시간 동안 접근하지 않을 페이지이다.

최적 페이지 교체 알고리즘

운영체제가 모든 페이지 참조를 수집했다고 가정하면, 각 페이지들이 몇 개의 명령어 뒤에 처음으로 참조되는지 알 수 있다. 그 중 가장 많은 명령어 뒤에 참조되는 페이지를 교체하는 알고리즘이다. 페이지 폴트가 발생했을 때, 운영체제가 각 페이지들이 어느 시점에 참조되는지 알 수는 없지만, 프로세스를 처음 돌린 뒤에 수집된 정보를 바탕으로 사용 가능하다.

NRU 페이지 교체 알고리즘

가상 메모리를 지원할 때, 각 페이지마다 운영체제가 페이지 사용 정보를 수집하기 위해 두 개의 상태 비트를 유지한다. R(Reference) 비트는 페이지가 참조될 때마다 설정되고(read/write), M(Modify) 비트는 페이지가 수정될 때마다 설정된다(clean/dirty). 최근에 참조되지 않은 페이지를 참조된 페이지와 구별하기 위해 주기적으로(clock tick마다) R 비트를 0으로 초기화한다. 페이지를 4개의 클래스로 분류하여 페이지 폴트가 발생했을 때 낮은 클래스에 있는 페이지 중 하나를 랜덤으로 교체한다.

1. 클래스 0 : R = 0, M = 0
2. 클래스 1 : R = 0, M = 1
3. 클래스 2 : R = 1, M = 0
4. 클래스 3 : R = 1, M = 1

가장 최근에 참조되지 않은, 변경된 페이지의 교체가 집중적으로 참조된, 변경되지 않은 페이지의 교체보다 좋다.

FIFO 페이지 교체 알고리즘

메모리에 가장 먼저 로드된 페이지를 교체하는 알고리즘이다. 메모리에 페이지들이 들어온 순서대로 링크드 리스트를 정렬하고, 페이지 폴트가 발생하면 맨 앞에 들어온 것을 교체한다.

벨레이디의 모순(Belady’s anomaly)은 페이지 프레임이 늘어나면, 페이지 폴트의 개수가 오히려 늘어나는 경우를 말한다.

Second-Chance 페이지 교체 알고리즘

메모리에 가장 먼저 로드된 페이지의 R을 검사한 후 교체하는 알고리즘이다. 메모리에 페이지들이 들어온 순서대로 링크드 리스트를 정렬하고, 페이지 폴트가 발생하면 가장 오래된 페이지의 R을 검사한다. R이 0이면 이 페이지는 최근에 사용되지 않은 페이지이므로 교체해도 된다. R이 1이면 이 페이지를 맨 뒤로 옮기고, R을 0으로 초기화한 후 적재 시간을 현재 시간으로 갱신하고 다시 검사한다.

Clock 페이지 교체 알고리즘

시계 모양 원형 리스트를 구성하고, 화살표가 가리킨 페이지의 R을 검사하는 알고리즘이다. 메모리에 페이지들이 들어온 순서대로 원형 리스트를 정렬하고, 페이지 폴트가 발생하면 화살표가 가리키는 페이지의 R을 검사한다. R이 0이면 최근에 사용되지 않은 페이지이므로 새로운 페이지를 삽입하고 화살표를 다음 페이지로 이동시킨다. R이 1이면 이 페이지의 R을 0으로 초기화하고 그 다음 페이지를 검사한다.

LRU 페이지 교체 알고리즘

LRU(Page Replacement Algorithm)는 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘이다. 메모리에 페이지들이 들어온 순서대로 링크드 리스트를 정렬하여 가장 최근에 사용된 것을 리스트의 맨 앞에, 가장 오래된 것을 리스트의 맨 뒤에 배치한다. 페이지 폴트가 발생하면, 가장 맨 뒤에 있는 페이지를 추출하여 교체한다. 그러나 모든 메모리 참조마다 리스트를 갱신해야 하며, 이는 리스트에서 페이지를 탐색하고 삭제 및 이동하는 작업이 오래 걸릴 수 있다.

LRU의 하드웨어 구현 1: 64bit 카운터

카운터가 명령을 실행할 때마다 C값을 1씩 증가시키고, 각 페이지 테이블 엔트리는 카운터 값을 저장할 수 있는 공간을 가진다. 메모리가 참조될 때마다 참조된 메모리를 담고 있는 페이지를 가리키는 페이지 테이블 엔트리에 C값을 저장한다. 페이지 폴트가 발생하면, 모든 페이지 테이블 엔트리의 C값을 조사하여 가장 적은 값을 갖는 페이지를 교체한다.

LRU의 하드웨어 구현 2: N*N bit로 구성된 행렬

N개의 페이지 프레임을 N*N bit로 구성된 행렬로 표현한다. 행렬의 모든 값의 초기값은 0이다. 페이지 프레임 k가 참조되면, LRU 하드웨어는 행렬에서 k번째 행의 모든 비트를 1로 설정하고, k번째 열의 모든 비트를 0으로 설정한다. 행의 이진 값이 가장 작은 행에 대응되는 페이지 프레임이 가장 과거에 참조된 것이다.

페이지가 0, 1, 2, 3, 2, 1, 0, 3, 2, 3 순으로 참조되었다고 가정하자. 일단 1행을 모두 1로, 0열을 0으로 초기화한다. 이후 1행을 모두 1로, 1열을 모두 0으로 초기화한다. 페이지 폴트가 발생하면, 행 값이 제일 낮은 프레임을 교체한다. 만약 그림 j에서 페이지 폴트가 발생했으면, 2행이 가장 낮으므로 프레임 2를 교체한다.

LRU의 소프트웨어 구현 1: NFU (Not Frequently Used)

각 페이지마다 각 페이지들이 얼마나 자주 참조되었는지를 알려줄 소프트웨어 카운터를 유지한다. 카운터의 초기값은 0이다. 클록 인터럽트가 발생할 때마다 운영체제는 메모리의 모든 페이지를 검사하여 R의 값을 소프트웨어 카운터에 더한다. 페이지 폴트가 발생하면, 가장 적은 카운터 값을 갖는 페이지가 교체된다. 그러나 NFU에는 잊어버리는 기능이 부재되어 있다. 예를 들어, 다중 패스 컴파일러의 경우 패스 1에서 자주 참조된 페이지들은 높은 카운터 값을 가지며, 이는 패스 2에서도 유지된다. 만약 패스 1이 그 이후 다른 패스들보다 더 긴 실행 시간을 가지거나 패스 1에서 더 많은 참조가 일어난다면, 패스 1에서 실행된 페이지들은 그 이후 패스에서 사용되는 페이지들에 비해 더 큰 카운터 값을 가진다. 따라서 패스 1에 사용되던 페이지 대신 현재 패스에 사용하는 유용한 페이지들을 교체하게 된다.

LRU의 소프트웨어 구현 2: 에이징 (Aging)

NFU를 기반으로 다음 사항을 변경한다. 첫째, R를 더하기 전에 오른쪽으로 1비트 시프트한다. 둘째, R는 오른쪽 비트가 아닌 왼쪽 최상위 비트에 추가된다.

시간 순서를 구별할 정보를 기록하여 LRU는 오직 하나의 비트로 참조 여부만 기록하기 때문에 페이지 3, 5 중 어떤 페이지가 더 먼저 참조되었는지 모른다. 그러나 에이징은 시간 순서를 구별할 정보를 기록하여 2번의 클록 틱 전에 1번 더 참조된 페이지 5 대신 3을 교체한다. 또한 에이징은 과거에 대한 정보를 제한한다. NFU는 과거에 대한 모든 정보를 기억하지 못해 10번째 전에 참조되었는지, 100번째 전에 참조되었는지 알 수 없다. 하지만 에이징은 최대 N번 전에 정보를 기록할 N비트만이 존재하여 과거에 대한 정보를 제한한다.

워킹 세트 알고리즘

스레싱(Thrashing)은 멀티 프로그래밍의 정도가 높아 페이지 폴트가 계속 발생해 페이지 교체 시간이 길어지는 현상이다. 이는 여러 프로세스로 인해 프로세스가 충분한 페이지를 가지지 못하는 경우 발생한다. 멀티 프로그래밍의 정도가 높을수록 어느 순간부터 CPU 점유율이 하락하게 된다. 프로세스는 스와핑하느라 바쁜데, CPU는 아무것도 하지 않는 상황이 발생하는 것이다.

Demand Paging은 실제로 필요할 때 (요청이 있으면) 그 페이지를 메모리에 올리는 방식이다. 프로세스가 시작될 때 메모리에는 어떤 페이지도 존재하지 않으며, CPU가 첫 명령어를 fetch하면 페이지 폴트를 통해 운영체제가 해당 페이지를 로드한다. 프로세스는 참조의 지역성(Locality of Reference)을 가지며, 이는 작은 페이지만을 집중적으로 참조하는 경향을 의미한다. Locality Set은 집중적으로 참조되는 해당 페이지의 집합을 말한다.

워킹 세트(Working Set) W(K, T)는 프로세스가 현재 사용하고 있는 페이지의 집합을 의미한다. 워킹 세트의 Locality Set은 프로세스가 일정 시간 원활히 수행되기 위해 한 번에 올라와야 하는 페이지들의 집합이다. 워킹 세트를 시간 T에 대해, 가장 최근에 횟수 K번 발생한 메모리 참조에 의해 사용된 페이지의 집합으로 정의할 수 있다. 이는 뒤의 페이지가 앞의 페이지를 포함하기 때문에 K를 늘리수록 커지다가, 가상 페이지의 개수가 한정되어 한 곳에 수렴하게 된다.

워킹 세트 모델(Working Set Model)은 다음과 같은 특징을 가진다:

• PrePaging: 각 프로세스의 워킹 세트를 추적하다가, 프로세스가 실행되기 전 그 프로세스의 워킹 세트를 미리 로드한다.
• 주기적인 인터럽트가 R을 일정 시간마다 초기화한다.
• 페이지 폴트가 발생하면, 페이지 테이블을 스캔해서 쫓아낼 페이지를 탐색한다.
• 해당 프로세스의 워킹 세트 전체를 한꺼번에 메모리에 올라갈 수 있는 경우에만 메모리에 할당하며, 그렇지 않을 경우 모든 페이지 프레임들을 반납시키고 디스크로 swap-out하여 스레싱을 방지한다.

워킹 세트 윈도우(Working Set Window)는 올라올 워킹 세트를 결정하며, 워킹 세트 윈도우의 크기는 T로 설정된다. 페이지가 참조된 시점부터 T 시간 동안 메모리에 유지하고, 그 시점이 지나면 메모리에서 지운다. 메모리에 있는 프로세스들의 워킹 세트 크기의 합이 페이지 프레임의 수보다 클 경우 일부 프로세스를 swap-out하여 남은 프로세스의 워킹 세트가 메모리에 모두 올라가도록 한다. 워킹 세트를 모두 할당한 후에도 페이지 프레임이 남으면, swap-out된 프로세스를 메모리에 올려 워킹 세트를 재할당한다.

현재 가상 시간(Current Virtual Time)은 프로세스가 시작된 후에 CPU를 실제 사용한 시간을 의미한다. 페이지의 현재 가상 시간이 2204일 때 페이지 폴트가 발생하면, 페이지 테이블을 모두 스캔하면서 R을 체크한다.

• R = 1인 경우, 마지막으로 페이지를 사용한 시간을 현재 가상 시간으로 바꾼다.
• R = 0인 경우, age = (현재 가상 시간 - 마지막으로 페이지를 사용한 시간)와 T를 비교한다.
  • age > T인 경우, 워킹 세트에 그 페이지가 포함되어 있지 않으므로 그 페이지를 지우고 계속 스캔한다.
  • age <= T인 경우, 가장 큰 age를 만드는 페이지를 기억하고 계속 스캔한다.
• 마지막까지 스캔했을 때 모든 엔트리가 age <= T이면, 가장 큰 age를 만드는 페이지를 지운다.
• 모든 엔트리가 R = 1인 경우, 한 페이지를 랜덤으로 지운다.

세그멘테이션 (Segmentation)

세그멘테이션은 하나의 가상 주소를 제공하는 페이징과 달리, 여러 개의 가상 주소를 제공한다. 프로세스를 논리적 내용을 기반으로 나누어서 메모리에 배치한다. 세그멘테이션 기법에서의 프로세스는 세그먼트(segment)의 집합으로 구성되며, 각 세그먼트는 자기만의 선형적인 주소 공간을 가진다. 페이징 기법에서는 주소 공간이 서로 충돌할 수 있지만, 세그멘테이션에서는 동적으로 테이블이 변화한다.

세그먼트 테이블의 각 엔트리의 논리 주소는 <segment-number, offset>으로 구성된다. 페이징과 달리, 세그먼트의 크기는 일정하지 않기 때문에 테이블에 limit 정보가 추가로 담겨 있다. 만약 세그먼트의 범위를 초과하는 주소가 들어온다면, 인터럽트가 발생해 프로세스가 강제로 종료된다.

논리 주소 (2, 100)은 물리 주소 4400번지로 변환되나, 논리 주소 (1, 500)은 인터럽트로 인해 프로세스가 강제로 종료된다.

세그멘테이션의 장점은 보호와 공유이다. 세그멘테이션도 페이징처럼 r, w, x 비트를 테이블에 추가하는데, 프로세스를 논리적으로 나누어 비트 설정이 간단하다. 세그멘테이션은 정확히 code 영역만 나누기에 다른 영역을 포함할 확률이 높은 페이징보다 더 효율적이다.

하지만 세그멘테이션은 외부 단편화 문제를 해결하지 못해, 현재는 페이징 기법을 대부분 사용한다. 외부 단편화는 메모리 할당을 처음 시작할 때 크기가 서로 다른 프로세스로 인해 다양한 크기의 홀이 발생하는 문제이다. 세그먼트를 논리적인 단위로 나눈 세그멘테이션 역시 외부 단편화로 인해 메모리 낭비가 크다.

세그멘테이션을 페이징으로 변환한 방식은 펜티엄(Pentium)에서 사용되었다. cs, ds, ss를 각각의 세그먼트가 아닌 하나의 주소 공간으로 통일해서 사용한다. 그러므로 cs, ds, ss는 다 같은 셀렉터 값을 가진다. 세그먼트와 페이지가 동시에 존재하기 때문에 주소 변환도 2번 이루어진다. CPU의 세그먼트 테이블에서 주소 변환이 먼저 이루어지고, 그 다음 페이지 테이블에서 주소 변환이 이루어진다.