Demand Paging
실제로 필요할 때 page 를 메모리에 올리는 것으로 다음과 같은 장점이 있습니다.
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
Demand Paging 또한 Valid/Invalid bit 을 사용합니다.
여기서 Invalid bit 은 여러가지 의미를 나타냅니다.
- 프로세스가 사용하지 않는 주소 영역
- 페이지가 물리 메모리에 없는 경우(backing storage 에 있는 경우)
이 경우 page fault 가 났다고 표현합니다.
Page fault
Page fault 가 발생하면, trap 이 발생되어 운영체제에게 CPU 제어권이 넘어가게 됩니다.
그러면 운영체제는 다음과 같은 순서로, 디스크에서 메모리로 페이지를 올리는 작업을 하게 됩니다.
Page fault 가 발생하면 벌어지는 일
- 정상적인 접근인지 확인
- 사용하는 메모리 범위를 초과하는 요청
- 접근하면 안되는 주소로의 접근 등
=> 프로세스 중단
- 디스크에서 비어있는
frame을 가져온다- 디스크가 가득찬 상태이면, 뺏어옴(replace)
- 페이지를 disk 에서 memory 로 읽어옴
- Disk I/O 가 끝나기 전까지는 프로세스는 CPU 를 선점당한 상태(Blocked)
- I/O 가 끝나면, page table entry 를 기록함(Valid bit = "valid" 로 설정)
- Ready Queue 에 프로세스를 삽입
- 프로세스가 다시 CPU 넘겨받아 컨텍스트 스위칭을 하며, 이전 상태를 로드
- 이전에 중단되었던 명령을 수행
Page fault rate
Page fault rate 0 ≦ p ≦ 1.0
if p == 0 , no page fault
if p == 1 , every reference is a fault
Effective access time
= (1 - p) x memory access time
+ p(OS & HW page fault overhead)
+ [swap page out if needed]
+ swap page in
+ OS & HW restart overhead일반적으로 Page fault rate 이 0.09 근처라고 합니다.
즉, 대부분의 경우에는 Page table 에서 원하는 물리 주소로 변환할 수 있다는 것 입니다.
아래쪽의 식은 fault 가 발생하는 경우의 오버헤드를 계산한 식 입니다.
이를 간단히 요약하면, 위에서 살펴본 Page fault 가 발생하면 벌어지는 일 모두가 오버헤드라는 것 입니다.
그래서 이 Page fault rate 을 0에 가깝게 유지하는게 중요하다고 합니다.
Page replacement
Frame 이 없는 경우에는 사용되지 않을 page 를 쫒아내어, 해당 page 의 frame 을 사용합니다.
알고리즘에 따라 동일한 페이지가 여러 번 메모리에서 쫒겨나고 들어올 수 있습니다.
Replacement Algorithm
Replacement Algorithm 은 Page fault rate 을 최소화 하는것이 목표입니다.
이 알고리즘을 평가할 때는, 주어진 page reference string 에 대해 page fault 를 내는 비율을 측정합니다.
# reference string 예시
1,2,3,4,1,2,5,1,2,3,4,5 ...Optimal Algorithm
미래에 참조될 페이지를 안다고 가정하고, 가장 먼 미래에 참조될 페이지(당장은 사용하지 않을 페이지)를 제거하는 방식입니다.
위 그림은 4개의 frame 이 있다고 가정한 경우의 예제 입니다.
처음 1, 2, 3, 4 는 메모리에 올라와 있지 않아서, page fault 가 발생했습니다.
그리고 그 다음 1, 2 는 fault 가 나지 않았고, 5 는 다시 fault 가 발생했는데요.
여기서 가장 나중에 참조될 번호인 4 번 자리에 replace 된 것을 확인하실 수 있습니다.
이 알고리즘은 사실 실제로 사용할 수 있는 알고리즘은 아닙니다.
왜냐하면, 미래에 어떤 페이지가 어떤 순서로 참조될지는 아무도 모르기 때문입니다.
그래서 이 알고리즘은, 다른 알고리즘의 성능을 측정하는 기준이 됩니다.(upper bound)
FIFO Algorithm
First-in First-out 방식으로 오래된 page 를 제거하는 알고리즘 입니다.
이 알고리즘은 단순하지만, 특이한 현상이 있습니다.
이는 page 수를 늘려주면, page fault rate 가 오히려 상승하는 경우의 예시인데요.
이를 FIFO Anomaly(Belady's Anomaly) 라고 합니다.
LRU Algorithm
그래서 가장 많이 사용하는 알고리즘은, Least Recently Used Algorithm 입니다.
캐싱 알고리즘으로도 자주 사용되는 이 알고리즘은, 가장 오래전에 참조된 것을 지우는 방식입니다.
LFU Algorithm
Least Frequentyl Used Algorithm 은 가장 적게 참조된 페이지를 지우는 방식입니다.
이 알고리즘은 다음과 같은 장단점이 있습니다.
- 장점
- LRU 와는 다르게 시간을 두고 관찰하는 방식이기 때문에, page 의 인기도를 좀 더 정확히 측정 가능
- 단점
- 참조 시점의 최근성을 반영하지 못함
- LRU 보다 구현이 복잡함
LRU & LRF 예제
LRU 는 참조 횟수는 고려하지 않고, 가장 오래전에 참조된 Page 1 을 삭제합니다.
LRU 는 참조 횟수를 고려하여, 가장 적게 참조된 Page 4를 삭제합니다.
하지만, 가장 최근에 참조된 페이지를 지우는 단점이 있습니다.
LRU & LRF 구현
- LRU
- 구현 형태 : Double LinkedList 형태
- 시간 복잡도 : O(1)
- LFU
- 구현 형태 : 이진트리의 Heap 형태
- 시간 복잡도 : O(log n)
다양한 캐싱 환경
캐싱이란 한정된 공간에 요청된 데이터를 저장해놓았다가, 다음 요청시 캐시에 저장된 데이터를 반환하는 방법 입니다.
paging system 뿐만 아니라 다른 환경에서도 사용됩니다.
- cache memory :
CPU Cache와Memory의 속도차 완화 - buffer caching :
Memory와File System의 속도차 완화 - web caching :
Remote Web server와Client사이 거리로 인한 지연시간 완화
캐시는 빠른 응답속도를 위해 사용하기 때문에, 운영 시간 제약이 존재합니다.
일반적으로 buffer caching, web caching 의 경우 O(1) ~ O(log n) 정도 까지 허용한다고 합니다.
그러나 Paging system 에서는 LRU, LFU 를 사용할 수 없습니다.
사용할 수 없는 이유는, 위 알고리즘 같은 경우는 특정 항목이 참조된 시점, 횟수를 알아야 합니다.
그래서 운영체제는 프로세스가, 어떤 페이지를 언제 몇번 참조했는지 알아야 하는데요.
하지만, page fault 가 발생하지 않으면 프로세스는 운영체제 개입 없이 MMU 를 통해서 바로 주소 변환을 합니다.
위에서 알아본 바로는 page fault rate 는 약 0.09 정도로 가끔 일어나는 일 입니다.
그래서 운영체제가 모든 참조 활동에 대해 추적할 수 없기 떄문에 LRU, LFU 와 같은 알고리즘을 사용할 수 없습니다.
Clock Algorithm
LRU, LFU 를 사용할 수 없는 Paging system 에서는 그래서 LRU 를 근사시킨 Clock Algorithm 을 사용합니다.
이 알고리즘은 최근에 사용한 page 는 1, 사용하지 않았으면 0 으로 비트값을 세팅하고 하나씩 확인하다가0 인 페이지를 만나면 쫒아내게 됩니다.
이 알고리즘은 Circular linked list 로 구현할 수 있습니다.
여기서 modified bit 은 쓰기 작업 요청이 들어왔는지에 대한 bit 입니다.
이 bit 는 1 이라도, reference bit 이 0 이면 쫒겨날 수 있습니다.
다만, 쫒겨나기 전 쓰기 작업을 수행합니다.
Page Frame Allocation
프로세스가 명령을 수행할 때, 여러 페이지를 동시에 참조합니다.
이 명령어는 로직에 따라 수행을 위해 최소 할당되어야 하는 frame 의 수가 있습니다.
그래서 각 프로세스에 얼마만큼의 page frame 을 할당할 것인가가 Page Frame Allocation 의 주요 관심사 입니다.
Allocation Scheme
- Equal allocation : 모든 프로세스에게 똑같은 개수를 할당
- Proportional allocation : 프로세스 메모리 크기에 비례하여 할당
- Priority allocation : 프로세스의 우선순위에 따라 다르게 할닽
Global vs Local Replacement
Global Replacement
Replace 가 필요한 경우, 다른 프로세스에 할당된 frame 도 뺏어올 수 있습니다.
FIFO, LRU, LFU 등을 global replacement 알고리즘으로 사용하는 경우에 해당합니다.
Local Replacement
자신에게 할당된 Frame 내에서만 replace 를 수행합니다.
FIFO, LRU, LFU 등의 알고리즘을 process 별로 수행하는 경우에 해당합니다.
Thrasing Diagram
여러개의 process 를 실행할 경우 어느정도 지점까지는 CPU 사용률이 상승합니다.
그러나 그 지점을 지나게되면 CPU 사용율은 뚝 떨어지게 되는데, 이를 Thrasing 이 일어났다고 표현합니다.
Thrasing 은 page fault 가 발생하는 빈도수가 너무 높고 이 때문에 발생하는 오버헤드 때문에 CPU 사용률이 줄어드는 현상입니다.
이때 악순환이 일어날 수 있는데요.
OS 가 CPU 저조한 CPU 사용률을 보고, 더 많은 프로그램을 메모리에 올리게 됩니다.
그러면 각 프로세스는 더 작은 메모리를 갖게되고, 메모리에 있는 페이지보다 디스크에 있는 페이지가 많아집니다.
그러면 page fault 가 발생하는 빈도수가 더 상승하게 되고 CPU 사용률은 상승할 수 없게 됩니다.
Working-set Model
Locality of reference
프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다
-> 프로세스는 한번 참조한 곳을 다시 참조할 확률이 높다는 말
그래서 이 집중적으로 참조되는 page 의 집합을 locality set 이라고 합니다.
Working-set Model
이 모델은 프로세스가 일정 시간동안 원활하게 작업을 수행하기 위한 page 들의 집합을 Working-set 이라고 정의합니다.
Locality 에 기반한 것으로, 이 모델은 Working-set 모두 올라와있는 경우에만 작업을 수행하도록 합니다.
만약 일부라도 없으면, Frame 을 반납하고 swap out(Suspend) 됩니다.
이는 Thrasing 을 방지하기 위한 방법으로, OS 로 인한 프로세스 증가 악순환을 방지할 수 있습니다.
Working-set Algorithm
Working-set Algorithm 과거의 page reference 를 참조합니다.
Window 안에있는(특정 시간 동안) page 들의 집합을 Working-set 으로 정의합니다.
WS(t1) 의 경우, t1 시간 동안 사용한 {1,2,4,6,7} 을 Working-set 으로 정의했습니다.
5개의 페이지가 필요한데 만약 3개의 자리밖에 없다면, 아예 이 프로세스는 suspend 됩니다.
이런 방식으로 Thrasing 을 방지하는 알고리즘 입니다.
PFF Schema
Page-Fault Frequency 는 page fault rate 의 상한선, 하한선을 두고 그 사이를 유지시키는 방법입니다.
- page fault rate 이 상한선 이상
- frame 을 더 할당하여, rate 감소시킴
- page fault rate 이 하한선 이하
- 할당된 frame 수를 줄임
Page size 결정
Page size 에 따라 시스템은 어떤 영향을 받는지를 아래에서 알아보겠습니다.
- page size 감소
- 장점
- 내부 조각 감소
- 필요한 정보만 메모리에 올라와서 효율적으로 활용 가능
- 단점
- page table 크기 증가
- Locality of reference 에 의해 page fault rate 가 증가할 수 있음
- 장점
일반적으로 가장 많이 사용하는 page size 는 4kb 라고 합니다.
하지만, 저장장치의 발달에 따라 더 큰 page size 를 사용하는 추세로 바뀌고 있다고 합니다.