All
페이지 교체 알고리즘
기본개념
•
페이징 기법에서는 모든 페이지 프레임이 사용 중일 때 새로운 페이지를 적재하기 위해 교체 대상을 선택해야 함
•
목표:
◦
앞으로 가장 오래 사용하지 않을 페이지를 교체하는 것 (이론적 최적)
◦
현실적으로 미래를 예측할 수 없기 때문에 좋은 근사 방법을 선택해야 함
교체 제외 페이지
•
페이징을 위한 커널 코드 영역
•
보조기억장치 드라이버 영역
•
시간을 맞춰 동작해야 하는 코드 영역
•
입출력장치를 위한 데이터 버퍼 영역 등
FIFO(First-In First-Out)
•
메모리에서 가장 오래 있었던 페이지 교체
•
큐 이용
[Page1] → [Page2] → [Page3] → [Page4]
(Front) (Rear)
Plain Text
복사
•
새 페이지가 필요하면 Front(제일 오래된) 페이지 교체
단점
•
자주 사용하는 페이지도 오래됐으면 교체될 수 있음
•
Belady의 이상현상: 프레임 수를 늘려도 페이지 폴트가 줄지 않고 늘어날 수 있음
LRU(Leat Recently Used)
•
메모리에서 가장 오랫동안 사용되지 않은 페이지 교체
•
Locality(지역성) 휴리스틱에 기반함
•
참조시각 또는 리스트 이용
참조시각을 이용한 구현
•
각 페이지 참조 시 마다 현재 시간 저장
•
교체 시 가장 오래된 시각을 가진 페이지 교체
•
리스트를 이용한 구현
•
참조될 때마다 리스트 맨 앞에 이동
•
교체할 때 리스트 끝에 있는 페이지 교체
•
장점
•
Belady 이상현상 발생하지 않음
•
최적화에 근접하는 선택 가능
단점
•
지역성이 맞지 않는 상황도 존재
•
막대한 오버헤드:
◦
매 참조 시 마다 리스트 수정/시각 기록 필요
◦
하드웨어 지원 없이 구현하면 매우 비효율적
LFU(Leat Frequently Used)
•
메모리에서 참조 횟수가 가장 적은 페이지 교체
•
참조횟수 이용
•
단점
•
최근에 들어온 페이지가 참조 횟수가 적어 바로 교체될 수 있음
•
예전에 많이 참조됐지만 지금은 거의 안 쓰는 페이지가 오래 살아남음
•
막대한 오버헤드: 참조 횟수 관리 부담
2차 기회 페이지 교체
•
참조 비트가 0이면서 메모리에 가장 오래 있었던 페이지 교체
•
FIFO 큐와 참조 비트 이용
•
참조 비트로 최근 참조 여부 체크
◦
각 페이지가 메모리에 적재될 때는 참조 비트 0
◦
적재된 상태에서 추가로 참조되면 참조 비트 1
1. 참조할 페이지가 메모리에 없는 경우
•
빈 페이지 프레임이 있으면
◦
페이지 적재
◦
큐에 추가
◦
참조 비트 0
•
빈 페이지 프레임이 없으면
◦
큐의 Front page 꺼내 참조 비트 확인
◦
참조 비트 1이면
▪
참조 비트를 0으로 리셋
▪
페이지를 큐 뒤로 이동
▪
다시 다음 Front 페이지를 검사
◦
참조 비트 0이면
▪
해당 페이지를 교체
▪
새 페이지를 적재하고 큐 뒤에 추가
▪
참조 비트 0 설정
2. 참조할 페이지가 메모리에 있는 경우
•
큐 위치 변화 없이 참조 비트만 1로 설정
[Page 요청 발생]
↓
[메모리에 있는가?]
↓
[YES] [NO]
참조 비트 = 1 ↓
(큐 변화 없음) 빈 프레임 있는가?
↓
[YES] [NO]
새 페이지 적재 큐 Front 검사
참조 비트 = 0 참조비트 1 → 0으로 변경 후 뒤로
참조비트 0 → 교체 후 적재
Plain Text
복사
클럭 페이지 교체
•
원형 큐 + 포인터 이용 (시계바늘처럼 동작)
•
포인터는 마지막에 추가된 페이지의 다음 위치를 가리킴
•
새 페이지 필요 시:
◦
포인터가 가리키는 페이지의 참조 비트 확인
▪
참조 비트 0이면 → 교체
▪
참조 비트 1이면 → 0으로 리셋하고 포인터 이동
•
빈 페이지가 있으면 그냥 삽입
프로세스별 페이지 집합 관리
•
운영체제에서 각 프로세스는 실행되기 위해 일정량의 메모리 페이지를 필요로 함
•
프로세스마다 일정 개수의 페이지 프레임을 메모리에 유지되는 페이지 집합
•
페이지 집합 크기 작을수록 시스템 처리량 증가, 페이지 폴트 증가
•
페이지 집합 크기 클수록 페이지 폴트 감소, 실행 가능한 프로세스 수 감소
적절한 페이지 집합 크기 관리는 운영체제 성능 최적화에 핵심
워킹세트(Working set) 알고리즘
•
Denning이 제안한 페이지 폴트 비율 감소 모델
•
워킹 세트 W(t, Δ) = 시각 t에서 직전 Δ시간 동안 참조된 모든 페이지 집합
•
짧은 시간(Δ시간) 동안 프로세스가 참조한 페이지 집합을 메모리에 항상 올려두자는 아이디어
◦
시간 지역성 때문, 방금 쓴 것을 또 쓸 가능성 높음
원칙
•
워킹 세트를 메모리에 유지하는 원칙
•
워킹 세트 미유지 시 계속 디스크로부터 페이지를 가져오는 상황(=쓰래싱) 발생
문제점
•
Δ시간 동안의 참조 이력을 전부 추적해야 함
•
엄청난 시간/공간 오버헤드 발생
•
구현이 너무 복잡해서 현실에서 그대로 적용하기 어렵다
PFF 알고리즘 (Paga Fault Frequency)
•
페이지 폴트 빈도를 이용해 프로세스별 페이지 집합 크기를 변화시키는 기법
•
워킹 세트를 직접 계산하지 않고 PFF를 이용해 워킹 세트 크기를 추정해서 관리
PFF
•
얼마나 자주 페이지 교체가 발생하는지 나타내는 척도
•
페이지 폴트 발생 직후 부터 다음 페이지 폴트 발생할때까지 시간을 T 로 뒀을때 이의 역수(1/T)
◦
T가 작으면 (폴트 금방 발생) → PFF 값이 커짐, 메모리 부족하다는 뜻
◦
T가 크면(폴트 없이 오래 실행) → PFF 값이 작아짐, 여유롭게 실행되고 있다는 뜻
•
상한과 하한 기준 설정
◦
PFF > 상한 (잦은 페이지 폴트) → 페이지 프레임 1개 추가
◦
PFF < 하한 (페이지 폴트가 너무 적음) → 참조되지 않은 페이지 제거
•
PFF 알고리즘을 통해 동적으로 페이지 집합 크기를 조정하여, 시스템 메모리 사용을 최적화하고 쓰래싱을 방지함