[Chapter 9. 가상 메모리] 페이지 대치 알고리즘 (LRU 근사), 사전 대치와 사전 적재

* 본 글은 '운영체제(Operating System: Concepts) 9th edition'의 내용과 2021학년도 1학기에 수강한 '운영체제' 과목 강의 내용을 함께 정리하여 작성하였습니다.

 

LRU 근사(LRU-Approximation) 페이지 교체

---

LRU 페이지 교체는 가장 오랜 기간 동안 사용되지 않은 페이지를 선택하여 대치하는 알고리즘이다.

 

교체할 페이지를 선택하기 위해서는 페이지가 '참조된 시간'에 대한 정보를 이용해야 하는데,

이 시간 정보들을 관리하기 위해서는 계수기, 클럭의 시간 값이나 스택을 활용해야 한다.

 

하지만 계수기 값과 스택을 갱신하는 일은 메모리 참조 때마다 수행되어야 하기 때문에

메모리 접근 성능이 거의 10배 느려지게 되며, 모든 사용자 프로세스의 수행 속도를 그만큼 저하시키게 된다.

 

 

따라서 계수기, 클럭, 스택을 활용하는 대신

하드웨어의 다양한 지원을 통해 LRU 알고리즘과 근사하게 구현을 한 페이지 교체 알고리즘들이 존재한다.

 

• 부가적 참조 비트 알고리즘
• 2차 기회 알고리즘
• 개선된 2차 기회 알고리즘

 

하드웨어 지원이 없는 경우에는 LRU나 근사 알고리즘을 사용하기보다는 FIFO 등 다른 알고리즘을 사용한다.

하지만 많은 시스템들은 참조 비트(reference bit)의 형태로 LRU 근사 알고리즘을 지원하고 있다.

 

참조 비트 (reference bit)

페이지 테이블에 각 항목마다 참조 비트를 추가한다.

 

처음에 모든 참조 비트는 운영체제에 의해 0으로 설정된다.

페이지 참조가 일어날 때마다(페이지 내의 어떤 바이트라도 읽거나 쓸 때) 참조된 각 페이지의 참조 비트는 하드웨어에 의해 1로 설정된다.

 

약간의 시간이 지나면 페이지의 사용 순서는 모르지만

해당 기간동안 어떤 페이지가 사용되었는지 여부를 판별함으로써 부분적 순서 정보 추출이 가능하다.

 

이 부분 정보가 LRU 근사 알고리즘의 기본이 된다.

 

부가적 참조 비트 알고리즘 (Additional-Reference Bits Algorithm)

각 페이지마다 참조 바이트(8 bit) 하나씩을 마련해주어

일정한 간격마다 참조 비트들을 기록하는 것을 통해 선후 관계 정보를 얻을 수 있다.

 

타이머 인터럽트(timer interrupt)로 일정 시간 간격마다 (ex. 매 100밀리 초마다)

1. 참조 바이트를 우측으로 1 bit shift

2. 참조 비트를 맨 왼쪽 최상위 비트(MSB)에 복사

 

 

이렇게 하면 참조 바이트가 최근의 8회 인터럽트 기간 동안 페이지의 사용 기록을 담고 있게 된다.

 

값이 00000000이라면 해당 페이지를 8번의 구간 동안 한 번도 사용하지 않았다는 것을 뜻하고,

값이 11111111이라면 각 구간마다 최소한 한번 이상 사용되었다는 것을 뜻한다.

 

값이 11000100인 페이지는 01110111인 페이지보다 더 최근에 사용되었음을 알 수 있다.

따라서 참조 바이트 값이 가장 작은 페이지가 참조된지 가장 오래된 것이기 때문에 해당 페이지를 선택하여 교체하는 것이다.

 

이 방법은 8회 이전의 참조 상황은 비교할 수 없다는 한계가 존재한다.

 

2차 기회 알고리즘 (Second-Chance Algorithm)

2차 기회 알고리즘은 참조 비트만 제공될 경우에 사용하며, FIFO 대치 알고리즘이 기본이 된다.

 

페이지 순서대로 참조 비트 검사를 진행하는데

1. 만약 해당 참조 비트가 0이면 해당 프레임의 페이지를 교체한다.

2. 만약 해당 참조 비트가 1이면 0으로 변경하여 다시 한번 기회를 부여, 다음 FIFO 페이지로 넘어간다.

 

 

참조 비트가 1에서 0으로 변경된 페이지는 다른 모든 페이지들이 교체되거나 기회를 받을 때까지 교체되지 않는다.

따라서 참조 비트가 계속 설정되어 있을 정도로 자주 사용되는 페이지는 전혀 교체되지 않을 것이다.

 

개선된 2차 기회 알고리즘 (Enhanced Second-Chance Algorithm)

위의 2차 기회 알고리즘에 변경 비트를 추가하여 만들어진 더 강력한 알고리즘이다.

 

참조 비트(reference bit)와 변경 비트(modify bit, dirty bit)의 조합을 통해서 다음 4가지의 등급이 생성된다.

 

1. (0, 0) : 참조되지도 않고 변경되지도 않은 경우

→ 교체하기 가장 좋은 페이지이다.

 

2. (0, 1) : 참조되지 않았지만, 변경은 된 경우

→ 해당 페이지를 뺏어오려면 디스크에 내용을 기록해야 한다. (write-back)

 

3. (1, 0) : 참조되었으나 변경은 되지 않은 경우

→ 해당 페이지는 곧 다시 사용될 가능성이 높다.

 

4. (1, 1) : 참조되었고 변경도 된 경우

→ 곧 다시 사용될 확률이 가장 높으며, 해당 페이지를 뺏으려면 디스크에 내용 기록도 해야 한다.

 

프레임을 할당받은 어느 페이지든 위의 4개 등급 중 하나에 속하게 되며,

가장 낮은 등급을 가지면서 처음 만난 페이지가 희생될 페이지로 선택된다.

 

교체될 페이지를 찾기까지 순환 큐를 여러 번 검사해야 할 수도 있다.

 

사전 대치와 사전 적재

---

페이지 부재의 발생은 많은 오버헤드를 일으킨다.

 

페이지 부재 발생 시 페이지 부재 트랩에 의해 처리가 이루어지고, 이후에 해당 프로세스를 다시 실행시키려면 스케줄링이 실행되어야 한다.

만약 페이지 대치까지 수행되어야 하는 상황이라면 여기서 더 많은 시간이 소요된다.

 

 

이를 해결하기 위해서는 페이지 대치 알고리즘을 사전에 실행시키는 방법이 있다.

항상 빈 프레임을 가지고 있다면 페이지 부재 발생 시 페이지 대치 알고리즘까지 수행해야 하는 것을 미리 방지할 수 있게 된다.

 

미리 선정된 희생자를 디스크로 내보내는 출력 작업(write-back)은 CPU와 병행할 수 있기 때문에 더 효과적이다.

* 현재 입출력에 사용되는 페이지는 대치되지 말아야 하는 조건 필요

 

 

더 나아가, 페이지 부재 발생 시점에 페이지를 적재하는 방법이 아닌, 미리 여러 페이지를 한번에 적재해놓는 방법도 존재한다.

이는 페이지 참조에 대한 예측이 필요하지만 다양한 정보를 활용하는 것을 통해 구현 가능하다.

 

ex. 서브루틴(함수), 행렬이 참조되는 경우 연관 페이지 모두를 적재하는 방법

→ 컴파일러에 의해 필요 정보가 제공될 수 있음