[운영체제] 16. 페이지 교체 알고리즘

지난 글에서 프로세스를 메모리에 올리는 다양한 방법을 고민하면서, Virtual Memory 방식에 대해 정리하였다.

하나의 프로그램 전체를 메모리에 올린 뒤 그때그때 실행할 프로그램을 교체하는 방식이 스와핑이었다면, 하나의 프로그램을 모두 메모리에 올리기에는 프로그램 용량이 너무 커서 다 못 올리는 경우 가상 메모리를 사용하여 프로그램이 사용하는 전체 메모리를 가상 공간에 표현하고, 가상 공간과 실제 메모리를 '페이지' 라는 단위로 매핑하여 그때 그때 필요한 가상 공간 영역을 실제 메모리에 올리는 방법을 사용했다.

 

이때 가상 공간 상 페이지 번호(virtual page number, VPN)와 실제 메모리 공간 속 페이지 (page frame number) 를 매핑하기 위해 페이지 테이블을 두었는데, 이 페이지 테이블을 MMU 라는 메모리 관리 하드웨어 유닛에 넣자니 매번 전체 테이블을 로딩하는 비용 문제로 메모리에 두고, 대신 MMU에는 TLB 라는 페이지 테이블에 대한 일종의 캐시를 두는 방식을 취했다.

 

페이지 테이블을 통해 현재 접근하려는 가상 주소를 실제 메모리상 주소로 변환하여 접근하게 되는데, 가상 주소 공간의 크기가 메모리 공간보다 크기 때문에 모든 virtual page 가 page frame 과 매핑된 것이 아니라, virtual page 와 page frame의 매핑에 실패하는, page fault 가 발생할 수 있었다.

 

page fault가 발생하면 트랩이 발생하고, OS가 나서서 참조할 페이지를 디스크로부터 읽어온 뒤, 메모리에 로딩하고 페이지 테이블에 해당 정보를 새롭게 저장하도록 교체한다. 그리고 트랩이 발생한 명령어를 다시 실행해서 가상 주소와 실제 주소 간 변환을 마무리 하고 명령어를 실행시킨다.

 

---

 

이번 글에서는 page fault가 발생했을 때, 어떤 기준을 가지고 페이지를 교체하는지 다양한 알고리즘들을 정리해본다.

 

먼저 페이지 폴트가 발생하면, 기존 페이지 중 하나는 새로 들어올 페이지를 위해서 삭제되어야 한다.

이때 삭제되는 페이지는 삭제되기 전에 수정 사항을 반드시 디스크에 저장해야 한다.

또한 자주 사용되는 페이지를 제거하는 것은 좋지 않다. 자주 사용되는 페이지를 페이지 테이블에서 제거하면 페이지 폴트가 금방 다시 발생할 것이기 때문이다.

 

Optimal Page Replacement Algorithm

실제로 사용가능한 알고리즘은 아니고, 이상적인 알고리즘이다.

따라서 실제로 사용 가능한 알고리즘의 성능을 평가하는 기준으로 사용되는 알고리즘이라고 보면 된다.

 

만약 페이지 테이블에 있는 모든 페이지에 대해 나중에 언제 reference 될 지 알 수 있다고 해보자.

그러면 최적의 페이지 교체 알고리즘은 가장 나중에 언급될 페이지를 내보내는 것이 최적일 것이다.

 

그래서 먼저 프로세스를 한 번 돌려보고, 프로세스가 명령어를 수행하면서 페이지에 접근하는 것들을 다 로깅한다.

그리고 같은 프로세스를 두 번째 실행할 때, 로깅해둔 기록을 보고 page fault 발생 시 제일 먼 미래에 참조될 페이지를 내보낸다.

 

이 방법은 실제로 사용을 하기는 힘들다.

프로세스를 한번 실행할 때 한번 돌려보고 또 실행하는 것도 이상할 뿐더러, 프로세스마다 사용자 입력에 따라 다르게 동작하는 것이 일반적이므로, 모든 사용자의 입력 경우의 수에 따라 로깅을 하는 것도 쉽지 않다.

 

그래서 이 알고리즘은 벤치마킹의 용도라고 보면 된다.

 

 

Not Recently Used (NRU)

(중요해요~)

이 페이지 교체 알고리즘은 메모리 관리에 있어서 매우 중요한 알고리즘이다.

기본적인 동작 방식은 이름 그대로 최근에 참조되지 않은 페이지를 내보내도록 동작한다.

그렇다면 구체적으로 어떻게 이를 알아낼 수 있을까?

 

먼저 페이지 테이블에 저장된 엔트리에는 virtual page number, page frame number 외에도 여러가지 부가 정보를 나타내는 비트들이 들어있었다.

그 중 R bit (Reference bit) 는 이 페이지가 read / write 등이 발생해서 참조된 적이 있으면 1로 세팅되고,

M bit (Modified bit) 는  이 페이지에 write가 발생한 적이 있으면 1로 세팅된다.

 

이 알고리즘은 주기적으로 페이지 테이블에 있는 모든 R 비트를 초기화한다.

(M비트는 초기화 할 수 없다. 초기화 하려면 수정된 내용을 디스크에 써야 할 것이다.)

 

그리고 페이지 테이블에 있는 엔트리를 다음 4가지 종류로 구분한다.

 

1. R = 0, M = 0

수정되지도 않고, R비트 초기화 이후 접근된 적도 없다.

 

2. R = 0, M = 1

수정된 적이 있고, R비트 초기화 이후 접근된 적은 없다.

 

3. R = 1, M = 0

수정된 적이 없으나, R비트 초기화 이후 접근된 적이 있다.

 

4. R = 1, M = 1

수정된 적이 있고, R비트 초기화 이후 접근된 적도 있다.

 

이 중에서 당연히 1순위로 내보낼 페이지는 1번 종류 페이지이다.

그 다음으로는 2번, 접근한 적은 있지만 수정된 적은 없는 페이지들 중 랜덤하게 선택해서 내보낸다.

2번도 없다면 3번, 3번도 없다면 4번을 내보낸다.

 

수정된 것을 내보내면 디스크에 반영해야 하다보니 비용이 들테니 2, 3 에 대한 순서가 조금 헷갈릴 수 있겠지만,

주기적으로 R 을 초기화 하고 있는데, R이 세팅되지 않았다면 자주 접근하지 않을 것으로 보고 수정된 내용을 지금 반영해둔다고 생각하면 납득이 되기도 한다.

(clock tick 마다 R비트가 초기화 될 때, clock tick 동안 읽은 적 없는 수정된 페이지를 내보내는 것이, 읽은 적 있는 clean page를 내보내는 것보다 낫다.)

 

 

First In First Out (FIFO)

페이지 테이블에 먼저 들어온 페이지가 먼저 나간다.

그러면 큐가 필요할텐데, 큐를 구현할 때는 연결 리스트를 사용해서 구현한다.

페이지가 메모리에 들어오면, 그 순서를 저장하고, page fault가 발생하면 연결 리스트의 맨 앞에있는, 제일 오래된 페이지를 교체한다.

 

하지만 만약 헤드에 존재하는 페이지가 자주 참조되는 페이지라면 이 페이지를 내보냈을 때 page fault가 금방 발생할테니 좋지 않다는 단점이 존재한다.

따라서 이 문제를 해결하기 위해 또 한번의 기회를 주는 알고리즘이 등장했다.

 

Second Chance

 

Second Chance 방식도 FIFO와 비슷하게 먼저 로딩된 페이지가 헤드에 존재한다.

위 그림에서는 각 페이지 상단의 숫자가 로딩된 시각을 나타낸다.

 

기존의 FIFO 방식에서는 page fault가 발생했다면 단순히 헤드에 존재하는 페이지를 내보내지만, Second Chance 방식에서는 페이지를 내보내기 전에 R bit를 체크하고, R bit 가 0이라면 내보내고 (이때 M 비트가 활성화 됐다면 디스크에 페이지 내용을 쓴 다음 내보낸다.)

 

R bit가 1 이라면, 내보내기 한번 참조된 적이 있으니 바로 내보내지 않고 R 비트를 초기화한 뒤 큐의 맨 뒤에 붙여서 새로 들어온 페이지로 취급하며, 이때 시간 정보는 0에서 20으로 갱신된다.

아직 페이지를 내보낸 것이 없으므로 이제 다시 헤드를 보면서 페이지를 체크하고, 만약 R 비트가 활성화 되지 않았다면 해당 페이지를 내보낸다. 만약 기존에 모든 페이지가 1이었다면 한바퀴를 돌았을 때 맨 처음 R비트를 초기화해서 맨 뒤에 붙였던 페이지를 만나게 되므로 이 페이지를 내보내게 된다.

 

하지만 이 방법도 페이지를 바로 내보내지 않고, 비트를 체크해서 리스트 뒤에 붙이는 과정을 반복하므로 추가적인 오버헤드가 발생한다는 단점이 존재한다.

 

 

The Clock Page

 

그래서 위에서 발생한 문제를 해결하기 위해 새로운 교체 알고리즘으로 The Clock Page 방식의 알고리즘이 등장했다.

이 방식은 Circular List 로 구성한 뒤, 가장 오래된 페이지를 가리키고 있다가, 페이지 폴트가 발생한 경우 가장 오래된 페이지의 R bit를 확인해서 0이면 내보내고, 1이면 R 비트를  0으로 초기화한 뒤, 헤드를 시계방향으로 이동시킨다. 그러면 기존의 페이지는 자연스럽게 꼬리에 붙는 효과가 생긴다.

 

 

Least Recently Used (LRU)

이름 그대로 가장 최근에 사용되지 않은 것 = 가장 옛날에 사용된 페이지부터 교체하는 알고리즘이다.

이 알고리즘에는 가장 최근에 사용된 페이지는 금방 또 사용된다는 전제가 깔려있다.

 

이제 LRU를 구현하는 여러가지 방법을 살펴보자.

 

1. 연결 리스트를 사용하여 자주 사용된 페이지는 앞 header에 두고, 가장 덜 사용되는 페이지를 뒤 쪽에 배치한다.

그리고 메모리에 접근할 때마다 연결리스트에 저장되는 데이터를 업데이트한다.

 

2. 카운터를 사용한다.

각 페이지 테이블 엔트리에 '카운터' 필드를 두고, 시스템 전체에서 카운터 값을 C에 저장한다.

메모리를 참조할 때마다 C 값을 1 증가시키고, 이때의 C 값을 현재 참조한 페이지 테이블 엔트리의 '카운터' 필드에 저장한다.

만약 페이지 폴트가 발생하면, 테이블 엔트리를 모두 살펴보면서 제일 작은 '카운터' 값을 가진 페이지 엔트리를 교체한다.

 

3. 하드웨어적으로 구성된 2차원 배열을 사용한다.

 

 

0 ~ 3 까지 4개의 페이지가 있고, 참조 순서는 0 1 2 3 2 1 0 3 2 3 이라고 해보자.

 

(a) 처음에 매트릭스는 모두 0으로 초기화 되어있다가, 0번 페이지가 참조되면 0번 row를 모두 1로 세팅한 뒤, 0번 col을 초기화한다.

그러면 위와 같이 0을 제외한 나머지 값이 1로 세팅된다.

 

(b) 1번 페이지가 참조되면 1번 row를 모두 1로 세팅한 뒤, 1번 col을 초기화 한다.

 

(c) 2번 페이지가 참조되면 2번 row를 모두 1로 세팅한 뒤, 2번 col을 초기화 한다.

 

(d) 3번 페이지가 참조되면 3번 row를 모두 1로 세팅한 뒤, 3번 col을 초기화 한다.

 

(e) 2번 페이지가 참조되면 2번 row를 모두 1로 세팅한 뒤, 2번 col을 초기화 한다.

 

....

 

이런 과정을 (j) 까지 반복하고, (j) 이후에 페이지 폴트가 발생했다고 해보자.

 

페이지 폴트가 발생하면 각각의 row에 저장된 값을 바이너리 값으로 보고 제일 작은 바이너리 값을 갖는 페이지를 교체한다.

(j) 에서 보면 1번 페이지는 0000 = 0 이므로 제일 작아서 1번 페이지가 교체된다.

 

이 방법은 페이지 참조를 하는 순간 자신의 row의 모든 필드를 1로 세팅하므로 자신의 값이 제일 커지게 된다.

그리고 자신의 col을 모두 0으로 초기화하므로, 다른 페이지들의 값을 감소시키는 효과가 있다.

따라서 제일 오랫동안 참조되지 않은 페이지는 다른 페이지들에 의해 계속 감소되었을 것이므로 제일 작은 값을 가질 것이다.

 

Not Frequently Used (NFU)

LRU를 소프트웨어적인 방법으로 구현하여, 실제 LRU와 완전히 동일하진 않지만, 거의 근사하는 효과를 보는 방법이다.

이름에서 알 수 있듯, '제일 오랫동안 사용되지 않은 것' 을 내보내는 것이 아니라, "제일" 인지는 모르겠지만 일단 자주 사용되지 않았다면 제일 오랫동안 사용되지 않았을 가능성이 높은 것으로 보고 교체한다.

 

이 방법은 각 페이지의 참조 횟수를 보고 참조 횟수가 제일 작은 페이지를 교체한다.

(위에서 본 카운터 방식이랑 비슷한 것 같은데 차이가 뭘까?)

 

먼저, 각각의 페이지마다 소프트웨어적으로 0으로 초기화된 카운터 값을 둔다.

Clock 인터럽트가 발생할 때마다 페이지 테이블을 스캔하고, R 비트의 값을 카운터에 더한다.

참조된 적이 있다면 카운터 값이 증가할 것이다.

 

R 비트의 값은 주기적으로 초기화되기 때문에, 자주 사용되는 페이지는 그럼에도 불구하고 거의 R비트의 값이 1이라 카운터의 값이 매우 클 것이다. 반면 자주 사용되지 않는 페이지는 R비트의 값이 작을 것이다.

이런 페이지부터 페이지 폴트가 발생하면 교체하게 된다.

 

이 방법의 단점은 시간이 지날 때마다 프로세스에서 자주 사용하는 페이지가 변할 수 있음에도 과거에 자주 사용했었던 페이지들이 방출이 되지 않는 문제가 있다.

프로세스 실행 초반에 자주 사용했던 페이지들이 카운터 값을 쌓아둔 바람에, 실행 중반에 자주 사용하는 페이지들이 우선순위가 밀려 계속 교체되는 것이다.

(그렇다면 더 긴 주기를 두고 카운터 값을 주기적으로 초기화면 어떨까?)

 

 

Aging

LRU를 소프트웨어적인 방법으로 흉내내는 또 다른 기법은 에이징 기법을 사용하는 것이다.

 

(d) 의 2번 페이지는 001 이 아니라 0001 이다. (오타)

 

위 그림과 같이 6개 페이지가 있다고 해보자. 이때 각 페이지의 R비트를 하나의 배열에 모아서 저장한다.

상단의 배열이 R비트 배열이고, 하단의 숫자는 0으로 초기화된 카운터 값이다.

 

(a) clock tick 0이 되었을 때, 그 순간의 R비트가 101011 이라고 해보자.

그러면 페이지 0, 2, 4, 5 는 참조가 되었다는 뜻이므로 해당 페이지들의 카운터의 제일 왼쪽 비트 값을 1로 세팅한다.

(a) 그림에서 제일 왼쪽 비트를 세로로 읽으면 101011 임을 알 수 있다.

 

(b) clock tick 1이 되었을 때, R비트가 초기화 되고 다시 세팅된 R비트가 110010 이라고 해보자.

기존의 각 페이지 세팅값을 오른쪽으로 한칸 shift 하고 110010 을 각 페이지에 세팅한다.

 

...

 

그리고 페이지 폴트가 발생하면 이 카운터가 값이 제일 작은 페이지가 제거된다.

제일 최근에 참조되었다면 왼쪽에 있는 bit 가 1로 활성화 되었을 것이므로 숫자로 변환하면 큰 값을 갖게 되고,

최근에 참조되지 않았다면, 작은 값을 갖게되어 최근에 참조되지 않은 페이지가 방출된다.

 

이 방법은 실제 LRU와 다른 점이 있다.

먼저 실제 LRU와 다르게 clock tick 사이에서 발생한 참조 순서는 따지지 않는 점이 다르다.

실제 LRU라면 (e) 에서 3과 5를 비교할 때 앞 3비트가 001로 같았다면 이 1에 대해서 누가 먼저 1로 세팅되었는지를 따져서 방출할 페이지를 결정하지만, 에이징 방법을 사용하면 그 뒤의 추가적인 비트 (과거의 참조 값) 를 확인해서 방출하므로 다르다.

(가장 오랫동안 사용되지 않은 페이지를 방출하는 건데, 001 로 같다고 보고, 그 이전에서 또 가장 오랫동안 사용되지 않은 기간을 한번 더 비교하는 셈이다.)

또한 카운터의 비트수에 제한이 있어서 정확한 카운팅을 할 수 없다는 한계가 있다. (카운팅 값이 충분히 동률이 발생할 수 있으나, 과거의 값을 참조할 수 없다.)

 

 

Working Set

페이지를 한번에 로딩하는게 아니라 필요할 때 로딩하는 Demand Paging 기법이다.

이 기법이 등장한 배경은 참조 지역성 (locality of reference) 과 관련이 있다.

프로세스는 어떤 실행 단계에 있든지 모든 페이지들 중에서 상대적으로 적은 일부 페이지들만 참조한다는 것이다.

 

따라서 처음에 페이지들을 미리 로딩해두는게 아니라 어차피 상대적으로 일부 페이지들만 참조할 것이고, 이건 프로세스를 실행하다보면 자연스럽게 참조할 것이니 처음에는 페이지 폴트를 일부러 유발시켜서 자주 사용할 페이지들을 로딩하도록 한다.

 

즉, 프로세스가 실행되면 처음에는 메모리에 아무런 페이지를 갖고 있지 않다가 CPU가 명령어를 실행하면서 페이지 폴트가 발생하면 그때 메모리에 페이지를 로딩하게 된다. (그래도 텍스트 세그먼트는 미리 로딩하지 않을까? 아예 로딩을 안하나?)

시간이 지나면 프로세스는 필요로하는 페이지 대부분을 메모리에 로딩해두면서 점점 안정화되고, 페이지 폴트 발생 횟수가 상대적으로 줄어든다.

 

이제 이와 관련된 Working Set 페이지 교체 알고리즘을 정리하기 전에, 용어를 몇 가지 정리하자.

 

- Working Set

프로세스가 현재 사용하고 있는 페이지들의 집합을 의마한다. (중요해요~)

 

- Thrashing

나의 프로그램이 몇 개 명령어 밖에 실행을 안했는데도 계속 페이지 폴트가 발생하는 상황을 말한다.

Thrashing은 사용 가능한 메모리 공간이 필요한 working set 크기에 비해서 너무 작을 때 발생한다.

 

- Working set model (Prepaging)

많은 페이징 시스템은 각 프로세스의 워킹 셋을 미리 추적해서, 프로세스를 실행하기 전에 워킹 셋을 메모리에 넣어둔다.

이때 워킹 셋은 당연히 시간이 지남에 따라 변화할 수 있다.

(수업 중에서는 프로세스가 실행됨에 따라 변할 수 있다는 느낌으로 설명하셨다.)

 

 

 

워킹셋은 w(k, t) 와 같이 함수로 표현할 수 있다.

이때 k 는 가장 최근에 메모리를 참조한 페이지의 개수, t 는 시간이다.

 

만약 페이지를 7 8 7 6 5 8 1 3 순으로 참조한다고 하면 (현재 3을 불러온 상황으로 제일 최신)

k = 2 일 때는 working set 에 (1, 3)

k = 3 일 때는 working set 에 (8, 1, 3)

k = 5 일 때는 working set 에 (6, 5, 8, 1, 3) 과 같이 저장한다.

k = 7 일 때는 working set 에 (8, 7, 6, 5, 8, 1, 3) 이 저장되는데 이때 중복은 고려하지 않으므로 k = 6과 동일한 6개의 페이지가 저장된다.

 

따라서 k 값이 증가함에 따라 처음에는 점점 working set 에 들어가는 페이지 개수가 증가하다가 어느 순간부터는 중복 페이지가 생기면서 점점 증가하는 속도가 감소하여 위와 같은 그래프를 그리게 된다.

 

이제 working set 을 이용한 페이지 교체 알고리즘을 정리해보자.

 

 

먼저 페이지 테이블이 위와 같이 구성되어 있다고 해보자.

하나의 칸에는 기존의 페이지 테이블 엔트리 정보가 들어있고, 그 바로 아래 칸에는 이 엔트리에 대해서 마지막으로 사용한 시간과 현재 tick에서 reference 되었는지를 나타내는 R bit 가 저장된다. 

(이렇게 2줄이 모여서 하나의 페이지에 대한 정보를 나타낸다. 또한 R 비트는 tick이 지나면 초기화 될 것이라는 것도 유추할 수 있다.)

 

현재까지 CPU를 사용한 시간들의 합인 Current Virtual Time 이 2204 이고, 이 시점에서 페이지 폴트가 발생했다고 하면,

워킹셋 알고리즘은 먼저 페이지 테이블을 스캔을 하면서 R비트를 체크한다.

 

만약 R = 1 이라면, 이 페이지는 현재 워킹 셋에 들어있다고 보고, time of last use 값을 current virtual time 으로 덮어쓴다.

만약 R = 0 이라면, age 를 계산한다.

age는 current virtual time - time of last use 의 값으로, 마지막으로 사용된 후, 현재 current virtual time 까지 얼마나 시간이 지났는지를 보는 것이다. 만약 이 값이 사전에 정해둔 τ 보다 크다면 오랫동안 사용하지 않은 것이므로 이 페이지를 워킹 셋에 없는 것으로 보고 교체한다. 이 값이 τ 이하라면, 비록 R = 0 이지만 비교적 최근에 쓴 것으로 보고 그대로 놔두되, 만약 모든 페이지가 이 조건에 해당한다면 이 중에서 하나를 빼기는 해야하므로, time of last use가 제일 작은 페이지를 기억해둔다.

 

즉 워킹셋 집합을 τ 라는 시간 동안에 사용한 페이지들의 집합 정도로 근사해서 생각하고, 워킹셋에 없는 페이지를 우선적으로 빼되, 워킹 셋에 모두 들어있다면, 그 중에서 제일 오래된 페이지를 뺀다고 생각할 수 있다.

만약 모든 페이지의 R 비트가 1이라서 current virutual time 으로 세팅된 것으로 여겨지면 그때는 랜덤하게 하나의 페이지를 내보낸다.

(랜덤하게 할 지 다른 기준을 적용할 지는 역시 알고리즘마다 차이가 있을 수 있다. 예를 들면 단순하게 랜덤으로 쫓아도 되지만, 이 중에서 M bit 가 0인 clean 페이지를 골라서 내쫒으면 비용이 덜 들 것이다.)

 

 

WSClock

(생략 하셨다)