[운영체제] 페이징 교체

메인 메모리에 빈 프레임이 없을 때 어떻게 해야할까?

1 ) 페이지 폴트 발생시킨 알고리즘 종료

2 ) swap out

3 ) 교체

---

[페이지 교체 과정]

1 ) 보조저장장치에서 필요한 페이지의 위치를 알아낸다.

2 ) 빈 페이지 프레임을 찾는다.

• 비어 있는 프레임이 있다면 사용한다.
• 비어 있는 프레임이 없다면 희생 프레임을 선정한다. (페이지 교체 알고리즘 이용)
• 희생될 페이지를 보조저장장치에 기록하고, 관련 테이블을 수정한다.

3 ) 빼앗은 프레임에 새 페이지를 읽어오고 테이블을 수정한다.

4 ) 페이지 폴트가 발생한 지점에서부터 프로세스를 계속한다.

페이지 교체 과정(왼) / 페이지 교체 필요성(오)

 

[페이지 교체 장점]

1 ) 메모리 과할당 방지

2) 페이지 교체가 논리 메모리와 물리 메모리 분리를 완성시킴.

---

[페이지와 프레임 교체 알고리즘]

페이지 교체에 필요한 두 가지 알고리즘이 있다.

1 ) 프레임 할당 알고리즘 : 메인 메모리의 프레임을 얼마나 할당한건지 결정.

 

2 ) 페이지 교체 알고리즘 : 페이지 교체가 필요할 때 어떤 페이지를 교체할 지 결정.

 -> 같은 페이지는 페이지 폴트를 일으키지 않는다. -> 하나의 번호로 표시함.

 -> 성능은 참조열로부터 페이지 폴트 발생 횟수를 계산하여 평가.

프레임과 페이지 폴트는 반비례 관계

 

---

[페이지 교체 알고리즘]

1 ) FIFO Algorithm : 큐를 이용하여 가장 오래된 키를 교체하는 방식

 -> Belady모순이 발생 ( 프레임과 페이지 폴트의 반비례 관계가 깨지는 곳이 존재)

FIFO 페이지 교체

 

2 ) 최적 알고리즘 : 가장 오래 사용되지 않을 프로세스를 밀어내는 방법

 -> But 미래의 사용을 정확히 알 수 없기 때문에 구현이 불가

 -> 성능 비교용으로 사용됨.

최적 알고리즘

 

3 ) LRU 페이지 교체

 가정 : 과거와 미래가 비슷한 활동을 보일것임.

LRU 구현

 구현 : 페이지 테이블에 마지막 접근 시간을 기록함

1. 계수기(counters) 구현 방법 : 각 페이지에 cnt열을 두고 cpu 클락을 복사하는 방법 (서칭 필요)
2. 스택 구현 : 스택의 요소들을 모두 움직여야 하는 문제가 있음 (속도 느림)
3. 연결리스트 구현 : 구현이 어려움. 

 

         LRU와  OPT는 스택 알고리즘 (Belady 모순 발생x)

 

4 ) LRU 근사 알고리즘 : LRU과 비슷하지만 비용이 낮은 알고리즘

  1. 참조 비트

       -> 각 페이지에 참조 비트를 두고 0으로 초기화 함. 

       -> 페이지가 참조 되면 1로 변경

       -> 페이지 교체가 필요하면 참조 비트가 0인 비트와 교체

 

  2. 2차기회 알고리즘 

       -> 페이지 교체가 필요할 때 참조 비트가 0인 것과 교체

       -> 만약 참조 비트가 1이라면 참조 비트를 0으로 바꾸고 넘어감.

2차 기회 알고리즘

 3. 2차기회 알고리즘 개선

     -> 참조비트와 수정 비트를 같이 둠.

     -> (0, 0) -> (0, 1) -> (1, 0) -> (1, 1) 순으로 교체.

 

 

5 ) 카운팅(계수기반) 알고리즘

   -> Lease Frequently Used(LFU) Algorithm : 참조 횟수 가장 작은 페이지와 교체

   -> Most Frequently Used(MFU) Algorithm : 참조 횟수 가장 많은 페이지와 교체

 

6 ) 페이지-버퍼링 알고리즘

1. 시스템들이 가용 프레임 여러 개를 풀로 가지고 있다가 페이지 폴트가 발생하면 예전과 마찬가지로 교체될 페이지를 찾지만, 교체될 페이지의 내용을 디스크에 기록하기 전에 가용 프레임에 새로운 페이지를 먼저 읽어 들이는 방법이다. -> 프로세스가 가능한 한 빨리 시작할 수 있도록 해준다
2. 변경된 페이지 리스트를 유지하는 방법 : 페이징 장치가 아무런 일도 없게 되면 그때마다 변경된 페이지들을 차례로 보조저장장치에 쓴 후에, 페이지의 변경 비트를 0으로 되돌려 놓는다. 
3. 가용 프레임 풀은 유지하지만 그 풀 속 각 프레임의 원래 임자 페이지가 누구였었는지 기억해 놓는 방법 

 

7 ) 응용과 페이지 교체

 -> 응용에 따라서 페이지 접근 방법이 다를 수 있음

 -> 따라서 Raw Disk Mode를 제공함으로써 자기 응용에 맞는 버퍼링, 페이징 알고리즘을 작성할 수 있도록함.