Demand Paging
Demand Paging
- 실제로 필요할 때 page를 physical memory에 올리는 방법
- I/O 감소, Memory 사용량 감소, 빠른 응답 시간, 더 많은 process 수용
- Valid / Invalid bit 사용
- Invalid = 페이지가 물리적 메모리에 없는 경우, 처음에는 모든 page entry가 Invalid로 초기화
Page Fault
Page Fault
- Invalid page를 접근하면 MMU가 interrupt 발생시킴
- Kernel mode로 들어가서 page fault handler가 invoke 됨
Page Fault 처리 순서
- if invalid reference: abort process
- Get an empty page frame (없는 경우 replace = 기존에 존재하는 page를 backing store로 쫓아냄)
- 해당 페이지를 disk(backing store)에서 memory로 읽어온다.
3-1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함 (block)
3-2. Disk read가 끝나면 page table entry에 기록, valid/invalid bit = 'valid'
3-3. ready queue에 process를 다시 삽입 -> dispatch later - 추후 이 프로세스가 CPU를 잡고 다시 running
- 아까 중단되었던 Instruction 재개
Performance of Demand Paging
Page Fault Rate 0 <= p <= 1.0
- if p == 0 : no page fault (ex. memory가 매우 커서 page가 모두 올라와 있을 때)
- if p == 1, every reference is a fault (처음 시작할때)
Effective Access Time
- (1-p) * memory access + p (OS & HW page fault overhead) + [swap page out if needed] + swap page in + OS & HW restart overhead
Page Replacement Algorithm
Free Frame이 없는 경우 -> Page Replacement
- 어떤 frame을 빼앗아올지 결정해야 함 -> Replacement Alogorithm 사용
- page-fault rate을 최소화하는 것이 목표
Optimal Algorithm
Belady's optimal algorithm, MIN, OPT
- 가장 먼 미래에 참조되는 Page 를 replace
- 미래의 참조를 어떻게 아는가? -> offline algorithm (online 컴퓨터에서 적용 못함)
- 다른 알고리즘의 성능에 대한 upper bound 제공
FIFO (First In First Out)
FIFO: 먼저 들어온 것을 먼저 내쫓음
- 메모리가 증가할 수록 page fault가 증가함
LRU (Least Recently Used) & LFU (Least Frequently Used)
LRU: 가장 오래 전에 참조된 것을 지움
LFU: 참조 횟수가 가장 적은 객체를 지움
- 최저 참조 횟수를 가진 page가 여러 개 있는 경우
- 임의로 선정
- 성능 향상을 위해 LRU와 결합해서 가장 오래 전에 참조된 page를 지우게 구현 가능
- LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영가능
- 참조 시점의 최근성 반영하지 못하고 LRU보다 구현이 복잡하다는 단점
LRU와 LFU 알고리즘의 구현
- LRU: Linked List로 구현: O(1) complexity
- LFU: tree구조로 구현 (heap): O(log n) complexity
- Linked list로 구현하면 O(n) complexity
Clock Algorithm
Caching
- paging system 처럼 한정된 빠른 저장 공간을 가지고 계속적으로 요청되는 새로운 객체를 저장 공간에 읽어들였다가 후속 요청 시 직접 서비스하는 방식
- 저장 공간 = cache
- paging system, cache memory, buffer caching, Web caching ...
캐쉬 운영의 시간 제약
- Replacement Algorithm에서 삭제할 객체를 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
- Buffer caching이나 Web caching의 경우 O(1) ~ O(log n)정도까지 허용
- Paging system의 경우: 페이지 요청이 매우 비번하여 O(1)인 LRU 알고리즘도 부담 👉 Clock Alogorithm
Clock Algorithm (= Second chance algorithm, NUR(Not Used Recently), NRU(Not Recently Used))
- LRU의 근사 알고리즘
- 동작 방식
- Reference bit을 사용해서 교체 대상 페이지 선정 (circular list)
- reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
- 포인터가 이동하는 중에 reference bit 1은 모두 0으로 바꿈 (first chance)
- Reference bit가 0인 것을 찾으면 그 페이지를 교체
- 한 바퀴 되돌아와서도 (=second chance) 0이면 그때에는 replace 당함
- 자주 사용되는 페이지라면 second chance가 올 때 reference bit = 1일 것이다.
- 개선 방법
- reference bit와 modified bit(dirty bit)을 함께 사용
- refernce bit = 1 : 최근에 참조된 페이지
- modified bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지) -> 추후 메모리에서 쫓아내기 전에 디스크에 먼저 써주어야 함
Page Frame의 Allocatioin
Allocation problem: 각 process에 얼마만큼의 page frame을 할당할 것인가?
- 명령어 수행을 위해 최소한 할당되어야 하는 frame 수가 있음
- Loop를 구성하는 page 들은 한 번에 allocate되는 것이 유리함: 아니면 매 loop마다 page fault 발생할 것이므로
Allocation Scheme
- Equal allocation: 모든 프로세스에 똑같은 개수 할당
- Proportional allocation: 프로세스 크기에 비례하여 할당
- Priority allocation: 프로세스의 priority에 따라 다르게 할당
Global vs Local Replacement
Global Replacement
- Replace 시 다른 process에 할당된 frame을 빼앗아올 수 있음 (메모리 전체를 대상으로 함)
- Process 별 할당량을 조절하는 또 다른 방법
- Working set, PFF 알고리즘 사용
Local Replacement
- 자신에게 할당된 frame 내에서만 replacement
Thrashing
Thrashing
- 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당받지 못한 경우 발생
- Page fault rate 매우 높아짐 -> CPU utilization 낮아짐 -> OS는 MPD (Multiprogramming degree)를 높여야 한다고 판단하고 또 다른 프로세스가 시스템에 추가됨 -> 프로세스 당 할당된 frame 수 더욱 감소 -> 프로세스는 page 의 swap in/out으로 매우 바쁨 -> 대부분의 시간에 CPU는 한가함 -> low throughput
Working-Set Algorithm
Locality of reference (참조의 지역성)
- 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다.
- Locality set = 집중적으로 참조되는 해당 page들의 집합
Working-Set Model
- Working Set: Locality에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번해 메모리에 올라와 있어야 하는 page들의 집합
- Working Set Model에서는 프로세스의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out (suspend)
- Thrashing을 방지하고 MPD(Multiprogramming degree)를 결정
Working-Set Algorithm
- 프로세스들의 working set size 합이 page frame 수보다 큰 경우
- 일부 프로세스를 swap out시켜 남은 process의 working set을 우선적으로 충족 (MPD를 줄임)
- Working set을 다 할당하고도 page frame이 남는 경우
- Swap out 되었던 프로세스에게 working set 할당 (MPD를 키움)
- Working set을 제대로 탐지하기 위해서는 window size를 잘 결정해야 함
- window size 너무 작으면 locality set을 모두 수용하지 못할 우려, 너무 크면 여러 규모의 Locality set 수용
PFF (Page-Fault Frequency) Schema
PFF
- page-fault rate의 상한값과 하한값을 두고 상한값을 넘으면 frame을 더 할당하고 하한값 이하이면 할당 frame 수를 줄인다.
- 빈 frame이 없으면 일부 프로세스를 swap out
Page Size의 결정
Page size를 감소시키면
- 페이지 수, 페이지 테이블 크기 증가
- Internal fragmentation 감소
- Disk transfer 효율성 감소
- 필요한 정보만 메모리에 올라와 메모리 이용이 효율적 <-> Locality의 활용 측면에서는 좋지 않음
👉 요즘 트렌드: Larger page size
'CS > 운영체제' 카테고리의 다른 글
| 10. File System Implementation (1) | 2023.12.19 |
|---|---|
| 09. File System (1) | 2023.12.03 |
| 07. Memory Management (0) | 2023.11.25 |
| 06. Deadlocks (1) | 2023.11.21 |
| 05. Process Synchronization (0) | 2023.11.13 |
