가상 메모리 관리 기법
Demand Paging
✨ 실제로 필요할 때 page 를 메모리에 올리는 것
- I/O 양의 감소
- Memory 사용량 감소
- 빠른 응답 시간
- 더 많은 사용자 수용
✨ Valid / Invalid bit의 사용
- Invalid 의 의미
✓ 사용되지 않는 주소 영역인 경우
✓ 페이지가 물리적 메모리에 없는 경우 - 처음에는 모든 page entry가 invalid로 초기화
- address translation 시에 bit가 invalid bit이 set되어 있으면
⇒"page fault" 오류 발생.
Page Fault
- invalid page를 접근하면 MMU가 trap을 발생시킴 (page fault trap)
- Kernel mode로 들어가서 page fault handler가 invoke됨
- 다음과 같은 순서로 page fault를 처리한다.
- Invalid reference? (eg. bad address, protection violation) => abort process.
- Get an empty page frame. (없으면 뺏어온다: replace)
- 해당 페이지를 disk에서 memory로 읽어온다.
3-1. disk I/O가 끝나기까지 이 프로세스는 CPU를 preempt 당함(block)
3-2. Disk read가 끝나면 page tables entry 기록, valid/invalid bit = "valid"
3-3. ready queue에 process룰 insert → dispatch later- 이 프로세스가 CPU를 잡고 다시 running
- 아까 중단되었던 instruction을 재개
step in handling page fault
성능 계산
Page fault Rate = 0 ≤ p ≤ 1.0 으로 가정
(p = 0이면 no page fault , p = 1이면 매 참조마다 page fault. 보통은 p가 매우 작은 편이다)
Effective Access Time =
(1-p) × memory access
+p(OS & HW page fault overhead
+ [swap page out if needed] /* Free frame이 없는 경우*/
+ swap page in
+ OS&HW restart overhead)Free frame이 없는 경우
-
Page replacement
✓ 어떤 frame을 빼앗아올지 결정해야 함.
✓ 곧바로 사용되지 않을 page를 쫓아내는 것이 좋음
✓ 동일한 페이지가 여러 번 메모리에서 쫓겨났다가 다시 들어올 수 있음 -
Replacement Algorithm
✓ page-fault rate 을 최소화하는 것이 목표
✓ 알고리즘의 평가
주어진 page reference string에 대해 page fault를 얼마나 내는지 조사
✓ reference string의 예
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5.
Page Replacement Algorithm
1. Optimal Algorithm(OPT)
-
Optimal Algorithm은 가장 먼 미래에 참조되는 page를 대체하는 방법이다. 이 방법은 항상 최적의 결과를 갖는다.
-
미래의 참조를 모두 알고 있어야 하므로 실제 시스템에 사용 불가능하고, 다른 알고리즘의 성능에 대한 upper bound를 제공하는 역할을 한다.
(Belady's optimal algorithm, OPT, MIN 등으로 불린다.) -
미래의 참조를 어떻게 아는가? Offline algorithm(미래의 참조를 모두 알고있다는 가정)
"4 frames example"
🏴 빨간색은 page fault가 발생한 경우이고, 분홍색은 frame에 이미 존재해서 page fault가 발생하지 않은 경우이다. OPT는 항상 최적이므로 위와 같은 reference string이 주어진 경우 6번 미만의 page fault가 발생하는 방법은 존재하지 않는다.
📌 다음부터 나올 알고리즘은 Online Algorithml 미래를 모른다. 사용가능한 알고리즘
2. FIFO (First in First Out) Algorithm
- 먼저 들어온 것을 먼저 내쫓음
- 어떤 page는 항상 필요할 수 있는데, 그런 경우에도 replace를 시킨다는 단점이 있다.
- FIFO Anomaly (Belady's anomaly)
✓ frame이 늘어나도 page fault가 감소하지 않고 오히려 늘어나는 경우가 존재하는 현상.
3. LRU (Least Recently Used) Algorithm
-
가장 오래 전에 참조된 것을 지움
4. LFU (Least Frequently Used) Algorithm
-
참조 횟수(reference count)가 가장 적은 페이지를 지움
✓ 최저 참조 횟수인 page가 여럿 있는 경우- LFU 알고리즘 자체에서는 여러 page 중 임의로 선정한다
- 성능 향상을 위해 가장 오래 전에 참조된 page를 지우게 구현할 수도 있다
-
장단점
✓ LRU처럼 직전 참조 시점만 보는 것이 아니라 장기적인 시간 규모를 보기 때문에 page의 인기도를 좀 더 정확히 반영할 수 있음
✓ 참조 시점의 최근성을 반영하지 못함
✓ LRU보다 구현이 복잡함
LRU와 LFU의 알고리즘 예제
LRU와 LFU 알고리즘의 구현
- LRU는 Linked List 형태. 참조가 되면 바로 끝으로 내려가고, 빠져야 될때는 가장 위에 있는 것을 빼기만 하면 됨.
- LFU는 Heap을 이용해 구현. 이진 트리로 구성되어 맨 위에는 참조 회수가 가장 적은 페이지를 놓음. 직계 자식들과 비교를 해서 내려 갈 수 있는 곳까지 찾음.
다양한 caching 환경
✨ caching 기법
- 한정된 빠른 공간(캐쉬)에 요청된 데이터를 저장해 두었다가 후속 요청시 캐쉬로부터 직접 서비스하는 방식
- paging system 외에도 cache memory, buffer caching, Web caching등 다양한 분야에서 사용
✨ 캐쉬 운영의 시간 제약
-
교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없음
-
Buffer caching이나 Web caching의 경우
✓ O(1)에서 O(log n) 정도까지 허용 -
Paging system인 경우
✓ page fault인 경우에만 OS가 관여함
✓ 페이지가 이미 메모리에 존재하는 경우 참조시각 등의 정보를 OS가 알 수 없음
✓ O(1)인 LRU의 list 조작조차 불가능
Paging System에서 LRU, LFU는 사용할 수 없다. 주소변환은 운영체제가 아니라 하드웨어에서 바로 변환해서 사용자 프로그램이 사용하고, 운영체제는 이때 전혀 관여하는 것이 없기때문에 LRU와 LFU에 이용할 정보가 없다. page fault가 날때만 운영체제는 알게 됨.
Clock Algorithm
✨ Clock algorithm
- LRU의 근사(approximation) 알고리즘
- 여러 명칭으로 불림
✓ Second chance algorithm
✓ NUR (Not Used Recently) NRU (Not Recently Used) - 최근에 참조되었는지 여부를 나타내는 Reference bit이라는 정보를 사용해서 교체 대상 페이지 선정 (circular list)
- reference bit가 0인 것을 찾을 때까지 포인터를 하나씩 앞으로 이동
- 포인터 이동하는 중에 reference bit 1은 모두 0으로 바꿈
- Reference bit이 0인 것을 찾으면 그 페이지를 교체
- 한 바퀴 되돌아와서도(=second chance) 0이면 그때에는 replace 당함
- 한 바퀴 돌아 왔을때 다시 bit가 1이라면 그만큼 자주 사용되는 페이지라는 의미
✨ Clock algorithm의 개선
- reference bit (access bit)과 modified bit (dirty bit)을 함께 사용
- reference bit = 1 : 최근에 참조된 페이지
- modified bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지)
읽기만 발생했다면 reference bit = 1,
쓰기가 발생했다면? reference bit 과 modified bit 모두 1
앞의 알고리즘들은 Process를 고려하지 않음.
Page Frame의 Allocation(할당)
✨ Allocation problem: 각 process에 얼마만큼의 page frame을 할당할 것인가?
✨ Allocation의 필요성
- 메모리 참조 명령어 수행시 명령어, 데이터 등 여러 페이지 동시 참조
✓ 명령어 수행을 위해 최소한 할당되어야 하는 frame의 수가 있음 - Loop를 구성하는 page들은 한꺼번에 allocate 되는 것이 유리함
✓ 최소한의 allocation이 없으면 매 loop 마다 page fault
✨ Allocation Scheme(할당 계획)
- Equal allocation : 모든 프로세스에 똑같은 갯수 할당
- Proportional allocation : 프로세스 크기에 비례하여 할당
- Priority allocation : 프로세스의 priority에 따라 다르게 할당
프로세스가 page fault를 발생시켰을 때 대체될 frame의 그룹에 따라 Global Replacement와 Local Replacement로 나뉜다
Global vs Location
✨ Global replacement
- Replace 시 다른 process에 할당된 frame을 빼앗아 올 수 있다(전체 메모리)
- 각 Process별 할당량이 알아서 조절 됨
- FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당
- Working set, PFF 알고리즘 사용
- 일반적으로 더 좋은 처리량을 가지므로 가장 흔하게 사용되는 방법
✨ Local replacement
- 자신에게 할당된 frame 내에서만 replacement(프로그램에 할당된 메모리)
- FIFO, LRU, LFU 등의 알고리즘을 process 별로 운영시
- 쉬고 있는 메모리를 사용할 수 없기 때문에 비교적 비효율적이다.
Thrasing
- 프로세스의 원활한 수행에 필요한 최소한의 page frame 수를 할당 받지 못한 경우 발생
- Page fault rate이 매우 높아짐에따라 CPU utilization이 낮아짐
- OS는 CPU가 쉬고있으므로, MPD (Multiprogramming degree)를 높여야 한다고 판단
- 또 다른 프로세스가 시스템에 추가됨 (higher MPD)
- 프로세스 당 할당된 frame의 수가 더욱 감소
- 프로세스는 page의 swap in / swap out으로 매우 바쁨(대부분이 I/O 처리)
- 대부분의 시간에 CPU는 한가함
- low throughput
🏴 악순환
degree of multiprogramming - 메모리에 올라가있는 프로그램 개수
CPU Utilization - CPU가 놀지않고 일한 비율
메모리에 너무 많은 프로그램을 올려놓아서 뚝 떨어지는 상황
"thrashing이 일어났다"Thrashing Prevention
Locality of reference
- 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다
- 집중적으로 참조되는 해당 page들의 집합을 locality set이라 함
1. Working-Set Model
-
Locality에 기반하여 프로세스가 일정 시간 동안 원활하게 수행되기 위해
한꺼번에 메모리에 올라와 있어야 하는 page들의 집합을 Working Set이라 정의함 -
Working Set 모델에서는 process의 working set 전체가 메모리에 올라와 있어야 수행되고 그렇지 않을 경우 모든 frame을 반납한 후 swap out(suspend)
-
Thrashing을 방지함
-
Multiprogramming degree를 결정함
Working-Set Algorithm
- Working set은 Working set window라는 고정된 page 참조 시간(횟수)로 구한다.
- window size가 △인 경우
시각t 에서의 working set WS(tᵢ)
Time interval [tᵢ-ㅿ, tᵢ] 사이에 참조된 서로 다른 페이지들의 집합
Working set에 속한 page는 메모리에 유지, 속하지 않은 것은 버림
(즉, 참조된 후 △ 시간 동안 해당 page를 메모리에 유지한 후 버림)
2. PFF (Page-Fault Frequency) Scheme
-
page-fault rate의 상한값과 하한값을 둔다
✓ Page fault rate이 upper bound(상한값)을 넘으면 frame을 더 할당한다
✓ Page fault rate이 lower bound(하한값) 이하이면 할당 frame 수를 줄인다 -
빈 frame이 없으면 일부 프로세스를 swap out
메모리가 많으면 Page-Fault 비율이 줄어들고, 적으면 늘어난다는 뜻. 다만 일정이상의 메모리가 간다면 효율이 매우 낮아진다.
Page Size 결정
✨ Page size를 감소시키면
- 페이지 수 증가
- 페이지 테이블 크기 증가
- Internal fragmentation 감소
- Disk transfer의 효율성 감소
✓ Seek/rotation vs transfer - 필요한 정보만 메모리에 올라와 메모리 이용이 효율적
✓ Locality의 활용 측면에서는 좋지 않음
✨ Trend
- Larger page size
