페이징 교체 알고리즘

1. 가상 메모리

- 프로그램이 CPU에서 실행되려면 실행에 필요한 부분이 메모리에 올라와 있어야 한다. 또한 여러 프로그램이 동시에 수행되는 환경에서는 한정된 메모리 공간을 여러 프로그램이 조금씩 나누어서 사용하는데 운영체제가 적절히 프로세스에게 메모리를 할당해주어야 한다.

- 운영체제는 CPU에서 당장 수행해야 하는 부분만 디스크에 올리고 나머지는 디스크의 swap 영역으로 놓았다가 다시 필요해지면 기존에 메모리에 있었던 부분과 교체하는 방식을 사용

- 이처럼 메모리의 연장 공간으로 디스크의 swap영역을 사용하게 된다면 물리적 메모리 크기에 대한 제약을 고려할 필요가 없어짐 -> 가상 메모리는 물리 메모리 크기의 한계를 극복하기 위해 나온 기술이며, 프로세스 전체가 메모리 내에 올라오지 않더라도 실행이 가능하도록 하는 기법

2. 요구 페이징

- 프로세스의 주소공간을 메모리로 적재하는 방법

- 프로그램 실행 시 프로세스를 구성하는 모든 페이지를 한꺼번에 메모리에 올리는 것이 아니라 당장 사용될 페이지만을 올리는 방식. 특정 페이지에 대해 CPU의 요청이 들어온 후에 해당 페이지를 메모리에 적재

- 특정 프로세스를 구성하는 페이지 중, 어떤 페이지가 메모리에 존재하고 어떤 페이지가 메모리에 존재하지 않는지를 구별이 필요 -> 요구페이징에선 "valid-invalid bit(유효-무효 비트)"를 사용하여 각 페이지가 메모리에 존재하는지를 표시

* "valid-invalid bit(유효-무효 비트)"

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

2. 페이지 부재(page fault)

- CPU가 접근하려는 페이지가 메모리에 없는 경우. (즉, 페이지 테이블의 valid bit값이 0인 경우)

- 페이지 부재 발생 시 페이지를 디스크에서 읽어와야 하는데 이 과정에서 막대한 overhead가 발생한다. 따라서 요구 페이징 기법은 페이지 부재 발생률이 성능에 큰 영향을 끼친다.

페이지 부재 시 동작 과정

= page fault가 발생했을 때 처리하는 과정은 다음과 같습니다.

1. ( 찾으려는 페이지가 TBL에 없는 경우) 찾으려는 페이지가 메모리에 있는지 Page Table에서 valid bit를 확인한다.
2. valid bit가 0이라면 MMU(Memory Management Unit)가 페이지 부재 트랩을 발생시킨다. 이 때 CPU의 제어권이 커널 모드(kernel mode)로 전환되고, 운영체제의 페이지 부재 처리 루틴(page fault handler)이 호출되어 페이지 부재를 처리하게 된다.

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

-> 이처럼 이미 메모리에 있는 페이지 중 하나를 다시 backing store에 보내는 것을 page-out, 새로운 페이지를 메모리에 올리는 것을 (page-in)이라고 하며, 만약 비어 있는 프레임이 없다면 페이지 교체 알고리즘을 통해 물리적 메모리에 있는 프레임 하나를 스왑 영역으로 쫓아내 비어 있는 프레임을 만든 후 적재한다.

- 디스크 스왑 영역에 있던 페이지를 물리 메모리에 적재하기 위해서는 시간이 많이 소요되므로, 해당 프로세스는 CPU 제어권을 뺏기고 현재까지 수행되던 CPU 레지스터 상태 및 프로그램 카운터 값을 프로세스 제어 블록(PCB)에 저장해 둔다. 다시 CPU 를 할당받았을 때 PCB 정보를 바탕으로 정확히 같은 상태에서 다음 명령을 수행한다.

5. 페이지 테이블에서 해당 페이지의 유호-무효 비트를 유효비트로 설정하고 프로세스를 준비큐로 이동시킨다.
6. 다시 CPU를 할당 받았을 때 PCB에 있던 값을 복원시켜 중단되었던 명령을 수행한다.

3. 페이지 교체

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

- 희생양 페이지( Victim Page)

- 희생양 페이지는 보통 메모리에 올라가 있는 페이지 중 CPU에 수정(modify)되지 않는 페이지를 고르는 것이 효율적이다. 수정되지 않은 페이지는 page-out이 될 때 backing store에 쓰기(write) 연산을 할 필요가 없기 때문이다. (backing store는 읽는 시간도 느리지만, 거기에 더해 쓰기 작업까지 한다면 더욱 비효율적일 것이다.)

- 해당 페이지가 수정되었는지 안되었는지를 판단하기 위해, 페이지 테이블에 modified bit(=dirty 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과 동일

1. OPT(Optimal) - 앞으로 가장 오랫동안 사용되지 않을 페이지 교체

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

2. FIFO(First in First out) - 가장 먼저 들어온 페이지를 교체

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

3. LRU(Least Recently Used) - 가장 오랫동안 사용하지 않은 페이지를 교체

FIFO의 이상현상이 발생하지 않음
메모리 페이지의 참조 성향 중 시간 지역성(temporal locality) : 근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 높음" 을 고려한 알고리즘 => "가장 오랫동안 사용하지 않았던 데이터라면 앞으로도 사용할 확률이 적을 것이다."
사용된 시간을 알수있는 부분을 저장하여 가장 오랫동안 참조되지 않는 데이터를 제거. 마지막 참조 시점이 가장 오래된 페이지를 교체
페이지마다 카운터가 필요하며, 큐로도 구현가능. 사용한 데이터를 큐에서 제거하여 맨 위로다시 올리고, 프레임이 모자랄 경우 맨 아래에 있는 데이터를 삭제
단점: 프로세스가 주기억장치에 접근할때마다 참조된 페이지 시간을 기록해야 하므로 막대한 오버헤드가 발생
카운터나 큐, 스택과 같은 별도의 하드웨어가 필요

* 카운터 : 각 페이지별로 존재하는 논리적인 시계(Logical Clock)로, 해당 페이지가 사용될때마다 0으로 클리어 시킨 후 시간을 증가시켜 시간이 가장 오래된 페이지를 교체

4. LFU(Least Frequently Used) - 참조 횟수가 가장 낮은 페이지를 교체

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

LRU는 1번 페이지가 가장 오래전에 사용되었기 때문에 1번을 내쫓는다. 1번 페이지는 마지막 참조시점이 다른 페이지들에 비해 오래되기는 했지만 참조 횟수가 가장 많았지만 LRU알고리즘은 이러한 사실을 인지하지 못한다.

반면 LFU는 가장 참조 횟수가 적었던 4번 페이지를 내쫓는다. 그러나 4번 페이지는 가장 최근에 참조된 페이지로 지금부터 많이 사용되기 시작할 페이지일 수 있지만, LFU는 이러한 사실을 인지하지 못한다.

5. MFU(Most Frequently used) - 참조 횟수가 가장 많은 페이지 교체

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

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

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

7. SCR(Second Chance Replacement) : 2차 기회 페이지 교체

- 가장 오랫동안 주기억장치에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하기 위한 것으로,

FIFO 기법의 단점을 보완하는 기법

- 큐의 상단에서 꺼낸 대상의 참조 비트를 검사하여 0이면 교체 대상으로 선택하고, 1이면 0으로 바꿔 큐의 뒤에 삽입
- 만약 모든 페이지의 참조 비트가 세팅되어 있다면 큐의 첫번째 요소였던 페이지가 두번 검사될 것이고, 해당 페이지가 내쫓아짐

8. Clock : 클럭 알고리즘

- 2차 기회 페이지 교체를 원형 큐를 이용하여 구현한 것

- LRU 알고리즘과 LFU 알고리즘과는 달리 하드웨어적인 지원을 통해 동작한다.(전자는 페이지의 참조 시각 및 참조 횟수를 sw적으로 유지 및 비교해야 했음)

- 페이지 프레임의 참조 비트를 조사해서 참조비트가 1인 페이지는 0으로 바꾼 후 지나가고, 0인 페이지를 찾으면 그 페이지와 교체한다.

* 교체 방법

스레싱

- 프로세스의 처리 시간보다 페이지 교체에 드는 시간이 더 많아져 CPU이용률이 떨어지는 현상

- 다중프로그래밍정도가 높아지면 어느정도 까지는 CPU이용률이 오르지만, 한계치를 넘으면 스레싱이 발생하고 CPU이용률이 급감한다.

스레싱이 발생 -> 운영체제는 메모리에 적재된 프로세스의 수(MPD)가 적다고 판단 -> 메모리에 더 많은 프로세스 적재
-> 각 프로세스에 할당되는 메모리의 양이 급격히 감소 -> 페이지 부재 빈도수 증가 -> 무한 루프…
스레싱 발생을 방지하기 위해 MPD를 조절하는 알고리즘이 필요하다)

다중프로그래밍정도: 메모리에 동시에 올라가 있는 프로세스의 수

해결책

다중프로그래밍정도를 적정 수준으로 유지한다.
페이지 부재 빈도를 조절한다
working set을 유지한다
일부 프로세스를 중단한다

스레싱 발생을 방지하기 위해 MPD를 조절하는 알고리즘이 필요하다

MPD 조절 알고리즘

워킹셋 알고리즘
- 프로세스는는 일정 시간 동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다. 이렇게 집중적으로 참조되는 페이지들의 집합을 지역성 집합이라고 한다
- 이러한 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘을 워킹셋 알고리즘이라 한다
- 워킹셋을 구성하는 페이지들이 한꺼번에 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리를 할당한다. 그렇지 않을 경우에는 프로세스에게 할당된 페이지 프레임들을 모두 반납시킨 후 그 프로세스의 주소 공간 전체를 디스크로 스왑 아웃 시킨다
- 워킹셋 윈도의 크기를 효과적으로 결정하는 것이 워킹셋 알고리즘의 핵심

페이지 부재 빈도 알고리즘
- 프로세스의 페이지 부재율을 주기적으로 조사하고 이 값에 근거해 각 프로세스에 할당할 메모리량을 동적으로 조절한다
- 어떤 프로세스의 페이지 부재율이 시스템에서 정해놓은 상한값을 넘게되면 이 프로세스에 할당된 프레임의 수가 부족하다는 것을 의미하므로 이 프로세스에게 프레임을 추가로 더 할당한다. 이 때, 추가로 할당할 빈 프레임이 없다면 일부 프로세스를 스왑 아웃시켜 메모리에 올라와 있는 프로세스의 수를 조절한다.
- 이런 방식으로 메모리 내에 존재하는 모든 프로세스에 필요한 프레임을 다 할당한 후에도 프레임이 남는 경우 스왑 아웃되었던 프로세스에게 프레임을 할당함으로써 MPD를 높인다.