페이징1 포스팅에 이어서!
가상 메모리를 통해 큰 프로세스도 실행할 수 있다고는 하지만,
물리 메모리의 크기는 한정되어 있기 때문에
보조기억장치로 보낼 페이지를 선별할 수 있어야 하고,
각 프로세스에게 적당한 양의 프레임을 분배할 수 있어야 함.
요구 페이징 - demand paging
- 프로세스를 메모리에 적재할 때, 모든 페이지가 아닌 필요한 페이지만을 메모리에 적재
- 즉 실행에 요구되는 페이지만을 적재
demaing paging의 문제점
- 필요한 페이지를 적재하기 위해, 어떤 페이지는 보조기억장치로 보내야 함. 어떤 페이지를 보내야 할까?
- 프로세스에게 몇 개의 프레임을 할당해야 적절할까?
페이지 교체 알고리즘
- 메모리에 적재된 페이지 중 보조기억장치로 swap out할 페이지를 결정하는 방법
- 일반적으로 page fault를 가장 적게 일으키는 알고리즘이 좋은 알고리즘
- page fault: 현재 메모리에 적재되어 있지 않은 페이지에 접근할 시 발생하는 예외
그렇다면 page fault 횟수는 어떻게 알 수 있을까?
→ 페이지 참조열을 통해 (page reference string)
페이지 참조열 page reference string
- CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
- 연속된 페이지를 참조할 때는 page fault가 일어나지 않으므로 고려하지 않아도 되므로.
- ex. CPU가 참조하는 페이지가 [2, 2, 2, 3, 5, 5, 5, 3, 3, 7] 이면 페이지 참조열은 [2, 3, 5, 3, 7]
다음으로 페이지 교체 알고리즘을 한번 알아보자.
FIFO(First-In First-Out) 페이지 교체 알고리즘
- 말 그대로 가장 먼저 메모리에 적재된 페이지를 보조기억장치로 먼저 내보내는 알고리즘
- 단점: 가장 먼저 들어온 페이지가 프로그램 실행 내내 사용되어야 할 수도………
최적(Optimal) 페이지 교체 알고리즘
- CPU의 페이지 참조 횟수를 고려하여 페이지를 교체하는 알고리즘
- 앞으로 사용 빈도가 낮은 페이지를 교체
- 가장 낮은 page fault 발생 횟수를 보장
- 단점: 구현이 어렵다. 앞으로 오랫동안 사용되지 않을 페이지를 어떻게 예측할 것인가?
LRU 페이지 교체 알고리즘
- Least Recently Used Page - LRU
- 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘 < 이건 당연히 페이지 참조열을 살펴 보면 쉽게 알 수 있는 정보
프레임 할당
- 프로세스가 사용할 수 있는 프레임 수가 적어도 page fault가 자주 발생
- 이는 프로세스를 실행해야 할 시간에 페이지 교체를 실시하여 CPU 성능 저해
- 이러한 문제를 thrashing이라고 함.
https://www.prepbytes.com/blog/operating-system/thrashing-in-os/
y축: CPU utilization - CPU 이용률
x축: degree of multiprogramming - 멀티프로그래밍의 정도, 동시에 실행되는 프로세스 수
해당 그림은 동시에 실행되는 프로세스 수가 많다고 해서 CPU 이용률이 비례해서 증가하는 것이 아님을 나타냄.
동시에 실행되는 프로세스를 필요 이상으로 늘림
→ 각 프로세스들이 사용할 수 있는 프레임 수가 적어짐
→ page fault 빈번하게 발생
→ CPU 이용률 떨어짐
따라서 운영체제는 각 프로세스들이 실행하기 위한 최소한의 프레임 수를 알고 적절하게 프레임을 할당해야 한다.
프레임 할당 방식
- 정적 할당 방식
- 균등 할당 equal allocation
- 비례 할당 proprtional allocation
- 동적 할당 방식
-
작업 집합 모델 working set model 사용
-
페이지 폴트 빈도 Page Fault Frequency(PFF) 사용
-
정적 할당 방식
- 균등 할당
- 모든 프로세스에게 균등하게 프레임 할당
- 비합리적
- 비례 할당
-
프로세스 크기에 비례하여 프레임 할당
-
프로세스가 정작 실행하는 데 필요한 프레임은 크기에 비례하지 않을 수 있음
-
동적 할당 방식
- working set model
- 프로세스가 일정 기간 동안 참조한 페이지의 집합을 기억하여 빈번한 페이지 교체 방지
- 참조한 페이지의 집합을 working set, 작업 집합이라 부름
- 참조 지역성의 원리 기반, 프로세스는 특정 시간에 몇 개의 페이지를 집중적으로 참조
- working set의 크기만큼만 프레임 할당
- 프로세스가 일정 기간 동안 참조한 페이지의 집합을 기억하여 빈번한 페이지 교체 방지
- Page Fault Frequency / PFF
- page fault율이 너무 높다 → 프로세스는 너무 적은 프레임을 가지고 있다.
- page fault율이 너무 낮다 → 프로세스는 너무 많은 프레임을 가지고 있다.
- 이 2개의 아이디어를 활용하여, page fault율의 상한선과 하한선을 정하여 해당 범위 안의 프레임 수를 할당하는 것
https://www.studytonight.com/operating-system/thrashing-in-operating-system
Reference
혼자 공부하는 운영체제
