[운영체제] 페이징 교체 알고리즘

cs-study에서 스터디를 진행하고 있습니다.

가상 메모리

• 프로그램이 CPU에서 실행되려면 실행에 필요한 부분이 메모리에 올라와 있어야 한다. 또한, 여러 프로그램이 동시에 수행되는 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어서 사용하는데, 이를 위해 운영 체제가 적절히 프로세스에 메모리를 할당해야 한다.
• 운영체제는 CPU에서 당장 수행해야 하는 부분만 디스크에 올리고, 나머지는 디스크의 swap 영역으로 놓았다가 다시 필요해지면 기존에 메모리에 있었던 부분과 교체하는 방식을 사용한다.
• 이처럼 메모리의 연장 공간으로 디스크의 swap 영역을 사용하게 된다면 물리적 메모리 크기에 대한 제약을 고려할 필요가 없어진다.

 

→ 가상 메모리는 물리 메모리 크기의 한계를 극복하기 위해 나온 기술이며, 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법을 말한다.

 

요구 페이징 (Demand Paging)

• 프로세스의 주소 공간을 메모리로 적재하는 기법이다.
• 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라, 당장 사용될 페이지만 올리는 방식이다. 특정 페이지에 대해 CPU의 요청이 들어온 후에 해당 페이지를 메모리에 적재한다.
• 특정 프로세스를 구성하는 페이지 중, 어떤 페이지가 메모리에 존재하고 어떤 페이지가 메모리에 존재하지 않는 지를 구별해야 한다. 요구 페이징에서는 valid-invalid bit (유효-무효 비트)를 사용하여 각 페이지가 메모리에 존재하는지 표시한다.

 

 

• 프로세스가 실행되기 전에는 모든 페이지의 유효-무효 비트가 무효 값으로 초기화되어 있지만, 특정 페이지가 참조되어 메모리에 적재되는 경우 해당 페이지의 유효-무효 비트는 유효 값으로 바뀌게 된다. 그리고 해당 페이지가 디스크의 스왑 영역으로 쫓겨날 때는 무효 값으로 다시 바뀌게 된다.
• CPU가 참조하려는 페이지가 현재 메모리에 올라와 있지 않아서 유효-무효 비트가 무효로 세팅되어 있는 경우를 페이지 부재라고 한다.

 

페이지 부재 (Page Fault)

• CPU가 접근하려는 페이지가 메모리에 없는 상황이다. 즉, 페이지 테이블의 유효-무효 비트가 0인 상태이다.
• 페이지 부재 발생 시 페이지를 디스크에서 읽어봐야 하는데 이 과정에서 막대한 오버헤드가 발생한다. 따라서 요구 페이징 기법은 페이지 부재 발생률이 성능에 큰 영향을 끼친다.

 

페이지 부재 시 동작 과정

 

1.  찾으려는 페이지가 TLB (페이지 테이블의 캐시)에 없는 경우, 해당 페이지가 메모리에 있는지 페이지 테이블에서 유효-무효 비트를 확인한다.

 

2. 유효-무효 비트가 0이라면 MMU (Memory Management Unit)가 페이지 부재 트랩을 발생시킨다. 이때 CPU의 제어권이 커널 모드로 전환되고, 운영체제의 페이지 부재 처리 루틴이 호출되어 페이지 부재를 처리하게 된다.

 

3 & 4.  페이지 부재 처리 실행

• 운영체제는 해당 페이지에 대한 접근이 문제가 없는지 확인한다. 사용되지 않은 주소 영역에 속한 페이지를 접근하려 했거나, 해당 페이지가 접근 위반일 경우에는 해당 프로세스를 종료한다. (접근 위반의 예시: 읽기 전용 페이지에 대해 쓰기 접근을 시도하려는 경우)
• 해당 페이지에 대한 접근이 허용 가능하다면, 물리적 메모리에서 비어 있는 프레임을 할당 받아 그 공간에 페이지를 읽어 온다. 만약 비어 있는 프레임이 없다면 기존 메모리에 올라와 있는 페이지 중 하나를 디스크의 스왑 영역으로 쫓아낸다.

→ 이처럼 이미 메모리에 있는 페이지 중 하나를 다시 backing store (swap device라는 하드웨어의 일부분인데 디스크라고 생각해도 무방하며, 페이지를 임시로 보관하는 장소이다.)에 보내는 것을 page-out, 새로운 페이지를 메모리에 올리는 것을 page-in이라고 한다. 만약 비어 있는 프레임이 없다면 페이지 교체 알고리즘을 통해 물리적 메모리에 있는 프레임 하나를 스왑 영역으로 쫓아내 비어 있는 프레임을 만든 후 적재한다. 이때, 디스크 스왑 영역에 있던 페이지를 물리 메모리에 적재하기 위해서는 시간이 많이 걸리므로, 해당 프로세스는 CPU 제어권을 빼앗기고 현재까지 수행되면 CPU 레지스터 상태 및 프로그램 카운터 값을 PCB에 저장해 준다.

 

5. 페이지 테이블에서 해당 페이지의 유효-무효 비트를 유효 비트로 설정하고, 프로세스를 Ready-Queue로 이동시킨다.

 

6. 다시 CPU를 할당 받았을 때, PCB에 있던 값을 복원하여 중단되었던 명령을 수행한다.

 

페이지 교체 (Page Replacement)

• 페이지 부재가 발생하면 요청된 페이지를 디스크에서 메모리로 읽어와야하는데, 물리적 메모리에 빈 프레임이 존재하지 않을 수 있다.
• 이러한 경우, 메모리에 올라와 있는 페이지 중 하나를 디스크로 쫓아내 메모리에 빈 공간을 확보하여 새로운 페이지를 메모리에 올려야 한다.
• 이러한 과정을 페이지 교체라고 부르며, page-out이 된 페이지를 희생양 페이지 (victim page)라고 한다.

 

희생양 페이지 (Victim Page)

• 희생양 페이지는 보통 메모리에 올라가 있는 페이지 중 CPU에 수정되지 않는 페이지를 고르는 것이 효율적이다. 수정되지 않은 페이지는 page-out이 될 때 backing store에 쓰기 연산을 할 필요가 없기 때문이다.
• 해당 페이지가 수정되었는지 판단하기 위해, 페이지 테이블에 modified bit (=ditry bit)를 추가하여 이를 검사한다. 해당 페이지가 수정되었다면 이 비트를 1로 두고, 수정되지 않으면 0으로 둔다. 이를 이용해서 victim page는 최대한 수정되지 않은 페이지를 선택한다.

 

 

• 위 예시에서 수정되지 않은 페이지는 0, 2, 3번으로 총 3개의 페이지가 존재하는데 이 중에서 하나의 페이지를 선택해서 교체해야 할 것이다.
• 페이지 교체를 할 때 어떠한 프레임에 있는 페이지를 쫓아낼 것인지 결정하는 알고리즘을 페이지 교체 알고리즘이라고 하며, 페이지 부재율을 최소화하는 것이 페이지 교체 알고리즘의 목표이다.

 

페이지 교체 알고리즘 (Page Replacement Algorithm)

페이지 교체 알고리즘의 종류

• OPT - Optimal: 앞으로 가장 오랫동안 사용되지 않을 페이지 교체
• FIFO - First In First Out: 가장 먼저 들어온 페이지를 교체
• LRU - Least Recently Used: 가장 오랫동안 사용되지 않은 페이지를 교체
• LFU - Least Frequently Used: 참조 횟수가 가장 적은 페이지 교체
• MFU - Most Frequently Used: 참조 횟수가 가장 많은 페이지 교체
• NUR - Not Used Recently: 최근에 사용하지 않은 페이지 교체
• SCR - Second Chance Replacement: FIFO에서 한 번 더 기회를 주고 교체
• 클럭 알고리즘: SCR과 동일

 

OPT (Optimal)

 

• 빌레디의 최적 알고리즘으로 MIN, OPT 등으로 불린다.
• 가장 이상적이다.
• 프로세스가 앞으로 사용할 페이지를 미리 알아야 하므로 실제 시스템에서 온라인으로 사용할 수는 없는 오프라인 알고리즘이다.
• 어떠한 알고리즘보다도 가장 적은 페이지 부재율을 보장하므로 다른 알고리즘 성능에 대한 상한성을 제공한다.

 

FIFO (First in First out)

 

• 페이지에 가장 먼저 올라온 페이지를 교체한다.
• 들어온 시간을 저장하거나 올라온 순서를 큐에 저장하고, 페이지 부재 시 메모리에 가장 먼저 올라온 페이지를 먼저 교체하는 방식이다.
• 보통 프레임의 수가 많아질수록 페이지 결함의 횟수는 감소할 것이라 생각할 수 있지만, 물리적 공간이 늘어났음에도 성능이 더 나빠지는 경우도 발생할 수 있다. 이러한 상황을 FIFO의 이상 현상, Belady's Anomaly (FIFO anomaly)라고 한다.

 

 

LRU (Least Recently Used)

 

• FIFO의 이상 현상이 발생하지 않는다.
• 메모리 페이지의 참조 성향 중 시간 지역성을 고려한 알고리즘이다. (시간 지역성: 최근에 참조된 페이지가 가장 가까운 미래에 다시 참조될 가능성이 높음.)
• 사용된 시간을 알 수 있는 부분을 저장하여 가장 오랫동안 참조되지 않은 데이터를 제거한다.
• 페이지마다 카운터가 필요하며 큐로 구현이 가능하다. 사용한 데이터를 큐에서 제거하여 맨 위로 다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터를 삭제한다. (카운터: 각 페이지 별로 존재하는 논리적인 시계로, 해당 페이지가 사용될 때마다 0으로 초기화한 후 시간을 증가한다.)
• 프로세스가 주기억장치에 접근할 때마다 참조된 페이지 시간을 기록해야하므로 막대한 오버헤드가 발생할 수 있다.

 

LFU (Least Frequently Used)

• 페이지의 참조 횟수로 교체할 페이지를 결정한다. (물리적 메모리 내에 존재하는 페이지 중 과거에 참조 횟수가 가장 적었던 페이지를 쫓아내고 그 자리에 새로 참조될 페이지를 적재한다.)
• 만약 최저 참조 횟수를 가진 페이지가 여러 개면 임의로 하나를 선정해 쫓아내는데, 성능 향상을 위해 그들 중 상대적으로 더 오래 전에 참조된 페이지를 쫓아내도록 구현하는 것이 효율적이다.
• LRU는 직접 참조된 시점만을 반영하지만, LFU는 참조 횟수를 통해 장기적 시간 규모에서의 참조 성향을 고려할 수 있다.
• 가장 최근에 불러온 페이지가 교체될 수 있으며, 이에 따른 오버헤드가 발생할 수 있다.

 

 

• LRU는 1번 페이지가 가장 오래 전에 사용되었기 때문에 1번 페이지를 내쫓는다. 1번 페이지는 마지막 참조 시점이 다른 페이지에 비해 오래되기는 했지만 참조 횟수가 많았다는 사실을 LRU가 알지 못한다.
• 반면 LFU는 가장 참조 횟수가 적었던 4번 페이지를 내쫓는다. 그러나 4번 페이지는 가장 최근에 참조된 페이지로, 지금부터 많이 사용되기 시작할 수 있지만 LFU는 이러한 사실을 알지 못한다.

 

MFU (Most Frequently Used)

• 가장 많이 사용된 페이지가 앞으로는 사용되지 않을 것이라는 가정에 의한 알고리즘이다.

 

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

 

• LRU 근사 알고리즘으로, LRU처럼 오랫동안 참조하지 않은 페이지 중 하나를 선택하지만 가장 오래된 페이지라는 보장은 없다.
• 각 페이지마다 참조 비트와 변형 비트가 사용된다.
  • 참조 비트: 페이지가 참조되지 않았을 때 0, 호출되었을 때 1. (모든 참조 비트는 주기적으로 0으로 변경)
  • 변형 비트: 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때 1
• 어떤 고정된 시간 간격이 있어서 그 시간 간격이 지나면 주기적으로 모든 페이지의 참조 비트를 초기화한다. 페이지를 교체하려 할 때에는 페이지를 다음과 같이 4가지의 클래스로 나누고, 가장 낮은 클래스의 랜덤한 페이지를 선택하여 제거한다.
  • Class 0: 참조되지 않음, 수정되지 않음.
  • Class 1: 참조되지 않음, 수정됨.
  • Class 2: 참조됨, 수정되지 않음.
  • Class 3: 참조됨, 수정됨.

 

SCR (Second Chance Replacement)

• 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로, FIFO 기법의 단점을 보완하는 기법이다.
• 큐의 상단에서 꺼낸 대상의 참조 비트를 검사하여 0이면 교체 대상으로 선택하고, 1이면 0으로 바꿔 큐의 뒤에 삽입한다.
• 만약 모든 페이지의 참조 비트가 세팅되어 있다면, 큐의 첫 번째 요소였던 페이지가 두 번 검사될 것이고, 해당 페이지를 내쫓는다.

 

Clock: 클럭 알고리즘

 

• SCR을 원형 큐를 이용하여 구현한 것이다.
• LRU 알고리즘, LFU 알고리즘과는 달리 하드웨어적인 자원을 통해 동작한다. (해당 알고리즘은 참조 시각 및 참조 횟수를 소프트웨어적으로 유지 및 비교해야 한다.)
• 페이지 프레임의 참조 비트를 조사해서 참조 비트가 1인 페이지는 0으로 바꾼 후 지나가고, 0인 페이지를 찾으면 그 페이지와 교체한다.