운영체제 10강 :: 페이지 교체 알고리즘, 프로세스 집합

운영체제에서 기억하고 싶은 내용

 

 

페이지 교체 알고리즘

페이징 기법이라고 부르는듯 하다

새로 페이지를 적재해야 하는데, 모든 페이지 프레임이 사용되고 있네?

그럼 페이지 프레임에서 교체할 대상을 결정해야 하지

그 때 사용되는 기법이다

FIFO, LRU, LFU, 2차 기회 페이지 교체 등이 있다

 

 

최적화의 원칙

교체 대상 선택 방법으로 완벽한 방법이 있다

가장 오랫동안 사용되지 않을 페이지를 선택하는 방법이다

하지만 이론적으론 완벽하지만, 미래를 예측할 수 없어 실현이 불가능하다고 한다

 

 

교체 제외 페이지

교체를 하지 말아야 페이지들도 있다

어차피 필요한 영역은 교체하지 않는게 효율적일 것

 

• 페이징을 위한 커널 코드 영역
• 보조기억장치 드라이버 영역
• 입출력장치를 위한 데이터 버퍼 영역
• ... 등

 

 

FIFO(First In First Out)

가장 간단한 방법으로 큐를 사용하는 알고리즘이 있다

메모리 내에서 가장 오래 있었던 페이지를 교체하는 것

 

단점

가장 많이 쓰는 페이지를 교체 해버릴 수 있다

 

Belady의 이상현상

페이지 프레임을 늘리면 부재 횟수가 줄어들길 기대하지만,

타이밍이 안맞아 오히려 부재 횟수가 늘어나느 이상현상이 생길 수 있다

 

 

LRU(Least Recently Used)

국부성(Locality) 휴리스틱을 기반으로 한 방법이 있다

메모리 내에 가장 오랫동안 사용되지 않은 페이지를 교체하는 것

 

참조 시각을 이용한 구현

각 페이지가 참조 될 때 시각을 테이블에 기록하고,

참조 시각이 가장 오래된 페이지를 선택해서 교체한다

 

리스트를 이용한 구현

위의 방법과 유사한 방법 같다

페이지가 참조될 때 리스트의 선두로 옮기고,

교체가 필요할 때 리스트 마지막에 있는 페이지를 교체한다

 

위의 두 방법은 Belady의 이상현상이 없고,

대부분의 경우 최적화의 원칙에 유사하다

 

단점

국부성이 맞지 않는 상황이 존재할 수 있다

오버헤드도 많이 필요하다

 

 

LFU(Least Frequently Used)

메모리 내에 참조된 횟수가 가장 적은 페이지를 교체한다

 

단점

가장 최근에 옮겨진 페이지는 참조된 횟수가 없어 교체될 가능성이 높다

그리고 초반에 많이 사용됐지만 사용 안되는 페이지는 살아남을 가능성이 높다

막대한 오버헤드도 문제

 

 

2차 기회 페이지 교체

가장 괜찮은 방법이라는 두 번째 기회를 주는 방법

큐에 페이지와 참조 비트를 짝지어서 구현한다

참조 비트가 0이면서, 가장 오래 있었던 페이지를 교체

 

2차 기회를 주는 방법

• 처음 메모리에 적재되면 참조 비트는 0이다
• 적재된 상태에서 추가로 참조되면 참조 비트를 1로 만든다
• 교체를 해야할 때 해당 페이지의 참조 비트가 1이면 한번 더 기회를 준다
• 어떻게? 참조 비트를 0으로 바꾸고 큐의 마지막에 다시 넣어준다(2차 기회)

 

변형된 원형 큐로도 구현 가능

시계 방향으로 움직여서 Clock 페이지 교체 알고리즘이라고도 부른다네

포인터는 마지막 추가된 페이지 다음 위치를 가르킨다

 

 

프로세스별 페이지 집합 관리

페이지 프레임의 개수만큼 메모리에 집합이 있다

집합의 크기가 작을수록 시스템 처리량이 증대되지만, 부재는 자주 발생하고, 성능이 저하될 수 있다

반면 크기가 크면 페이지 부재는 감소하지만, 메모리에 적재될 수 있는 프로세스는 줄어든다

페이지 프레임 개수 관리를 잘하는 것도 중요하겠네?

그래서 알고리즘이 있다

 

 

페이지 프레임 개수 알고리즘

워킹세트 알고리즘, PFF 알고리즘

 

 

워킹세트(Working set)

페이지 부재 비율 감소시키기 위해 Denning이 제안 모델이 있다

 

원칙

프로세스의 워킹 세트를 메모리에 유지한다

메모리에 유지하지 않으면 쓰레싱이 발생할 수 있다

 

쓰레싱(Thrashing)
페이지 부재가 비정상적으로 많이 발생
프로세스 처리보다 페이지 교체 처리에 많은 시간을 소비해서 시스템 처리량이 급감하는 현상

 

프로세스마다 워킹 세트 크기에 맞게 페이지 프레임 개수 조절 가능하다

 

문제점

기본적으로 국부성을 이요하기 때문에, 과거를 통한 미래 예측이 정확하지 않다

워킹 세트 정확히 알아내고 업데이트 하는 것이 현실적으로 어렵다

 

 

PFF(Page Falut Frequency) 알고리즘

페이지 부재 빈도를 이용해서 프로세스별 페이지 집합 크기를 변화시킨다

 

방법

PFF 상한과 하한을 지정

상한보다 높으면 프레임 개수를 1 증가시키고,

하한보다 낮으면 그 사이 참조되지 않은 페이지 모두 제거한다

 

장점

워킹 세트 알고리즘 만큼 페이지 집합이 자주 바뀌지 않는다