페이징 기법 : 모든 페이지 프레임이 사용 되고 있을때 새로 적재되어야 할 페이지를 위해 적절한 교체 대상을 결정
교체 대상 선택 방법
- 최적화의 원칙
- 가장 오랫동안 사용되지 않을 페이지를 선택한다.
- 이론적으로 최적이나, 미래를 예측할 수 없어 실현 불가능하다.
- 선택을 위한 기본정책
- 대체로 좋은 결론을 내리면서, 선택을 위한 시간 및 공간 오버헤드가 적은 방법
- 교체 제외 페이지
- 페이징을 위한 커널 코드 영역
- 보조기억장치 드라이브 영역
- 시간을 맞춰 동작해야 하는 코드 영역
- 입출력장치를 위한 데이터 버퍼 영역
페이지 교체 알고리즘
1. FIFO 페이지 교체
FIFO(First in First Out) 선입 선출
메모리 내에 가장 오래 있었던 페이지를 선택하여 교체
단점
- 가장 많이 쓰이는 페이지를 교체시킬 가능성이 있음
- Belady의 이상현상 : 프로세스에 더 많은 수의 페이지 프레임을 할당하면 오히려 페이지 부재가 더 많이 발생할 수 있음.
변경 방식
있으면 안들어가고 없으면 큐에 넣어서 밀어넣는다.
안에 있는 상태에서 똑같은게 나왔다가 넣어주는것은 아니다.
LRU 페이지 교체
Least Recently Used : 가장 오랫동안 사용되지 않은 페이지를 선택하여 교체한다.
- 국부성 휴리스틱에 기반한다. 참조시각 또는 리스트를 사용해 구현한다.
참조시각 : 각 페이지가 참조될 때마다 그때의 시각을 테이블에 기록하고, 교체가 필요한 경우 참조시각이 가장 오래된 페이지를 선택하여 교체한다.
리스트를 이용한 구현은 각 페이지가 참조될 때마다 리스트의 선두로 옮긴다.
교체가 필요한 경우 리스트의 끝에 있는 페이지를 선택하여 교체한다.
장점 :
- Belady의 이상현상이 발생하지 않는다.
- 많은 경우 최적화 원칙에 근사한 선택 가능하다
단점 :
- 국부성이 맞지 않는 상황도 존재한다.
- 막대한 오버헤드
3. LFU 페이지 교체
Least Frequently Used : 메모리 내에서 참조된 횟수가 가장 적은 페이지를 선택하여 교체
단점
- 가장 최근에 메모리로 옮겨진 페이지가 교체될 가능성이 높다.
- 초기에 많이 사용하고 더 이상 사용되지 않는 페이지는 교체 가능성 낮음
- 막대한 오버헤드
프로세스별 페이지 집합관리
- 프로세스마다 사용할 수 있는 페이지 프레임의 개수만큼 메모리에 유지되는 페이지 집합이다.
- 집합의 크기가 작을 수록 시스템 처리량은 늘어난다.
- 각 프로세스별 페이지 부재는 자주 발생하여 성능이 떨어진다.
- 반대로 되면 페이지 부재는 감소하지만, 메모리의 적재되는 프로세스는 줄어든다.
각 프로세스가 사용할 수 있는 페이지 프레임 개수 관리하는 알고리즘
1. 워킹 세트 알고리즘
2. PFF알고리즘
워킹 세트 알고리즘
W(t, $)
시각t 에 t를 포함한 직전 $ 시간 동안 참조한 페이지 집합
ex ) W(t,$) = W(4,3) = {A,C}
2 ~ 4 부터 들어간 참조한 페이지의 집합이다.
- 프로세스가 수행됨에 따라 워킹세트, 워킹세트의 크기가 변할 수 있다.
- 메모리에 유지하지 않으면 쓰래싱 유발가능하다.
쓰래싱 : 페이지 부재가 비정상적으로 많이 발생하여, 프로세스 처리보다 페이지 교체처리에 많은 시간을 소비하여 시스템의 처리량이 급감하는 현상
문제점
- 과거 통해 미래 예측 정확하지 않음
- 정확히 알아내고 계속 업데이트 하는것이 비현실적
- 최적값 알기 어렵고, 변화 할 수 있음
PFF 알고리즘 : 페이지 부재 빈도(PFF) 를 이용하여 프로세스별 페이지 집합의 크기를 변화시키는 기법
Page Fault Frequency
- 페이지 교체가 얼마나 자주 교체 하는지 나타내는 척도
- 페이지 부재가 발생하면 직전 페이지 부재 이후로 경과된 시간의 역수
즉 페이지 교체가 자주 일어나면 메모리를 더 주고, 자주 일어나지 않으면 메모리를 뺏는다.
특정 프로세스에 대해 프레임 할당을 많이 해줄수록 페이지 결함이 적게 일어날것이다.
이와 반대로 프레임 할당이 적으면 페이지 결함이 많이 일어나게 될 것이다. 그래서 PFF라는 방식은 페이지 결함에 대한 특정 상한선을 초과한 프로세스에는 더 많은 프레임을 할당하여 페이지 결함을 줄이고 페이지 결함이 거의 없는 하한선 이하의 프로세스에는 프레임을 회수하여 적절하게 페이지 결함이 일어나지 않게 조절을 하게 된다.
요약하면
PFF가 상한 보다 높으면 페이지 프레임 개수 1증가 시키고
하한보다 낮으면 그 사이에 참조되지 않았던 페이지를 모두 제거
장점 : 프로세스별 페이지 집합이 자주 바뀌지 않는다.
댓글