Chapter 10. Virtual Memory Management

01

Outline

---

① Demand Paging

② Page Replacement

③ Thrashing

④ Allocating Kernel Memory

 

 

① Demand Paging

---

● 가상메모리

프로세스 전체가 메모리 내에 올라오지 않더라도 실행 가능

사용자 프로그램이 physical memory보다 커져도 됨

 

● Demand paging

page가 필요할때만 메모리에 load

swapper : 전체 프로세스 조작

pager    : 개별 페이지 조작 (lazy swapper)

 

lazy swapper

-> 필요없는 page는 절대 swap 안됨

 

요청한 page가 physical memory에 없으면

disk에서 해당 page를 읽어서 load

 

● valid/invalid bit

page가 메모리에 있는지 없는지 확인

 

● Page fault

메모리에 없는 page를 요청하면 빈 frame 찾아서 해당 page를 memory에 load

 

Trap 형태로 처리. 해당 page가 invalid 상태

1)    Invalid 상태가 잘못된 참조 때문인지, 메모리에 없기 때문인지 확인하기 위해서 another table lookup

2)    빈 frame 확보

3)    해당 page를 빈 frame에 swap in (해당 process를 waiting state로 전환. Disk 접근하기 때문)

4)    page table 갱신

5)    Validation bit를 valid로 바꿈

6)    Page fault가 발생한 지점부터 instruction 재수행

 

● Pure paging

참조되기 전까지 절대 swap-in 안되므로 시작할 때는 page 없음

page fault 유발

 

● Locality of Reference

1. spatial: 특정 page 집중적으로 참조

2. temporal: 특정 시간에 일부 page만 참조

 

● EAT (Effective Access Time)

if p = 0, page faults 발생 안함

if p = 1, 모든 참조가 page fault

EAT = p*(page fault overhead) + (1-p)*(memory access)

 

② Page Replacement

---

page fault 발생했는데 빈 frame 없으면 교체해야 함

 

● 빈 프레임 있을 때

1. 디스크에서 필요한 page 위치 찾기

2. 빈 frame 찾기

3. 빈 frame에 page 삽입

4. 프로세스 재시작

 

● 빈 프레임 없을 때

1. 변경할 page swap out

2. bit를 valid에서 invalid로 변경

3. 요청한 page swap in 

4. page table에 추가, bit를 valid로 변경

 

1. FIFO

-> 순서대로 수행

-> Belady's Anomaly: frame이 많을수록 page fault가 많이 발생하는 기현상

 

2. Optimal

-> 가장 오래동안 사용되지 않을 페이지 교체

-> 예측 불가, 실용성 (x)

-> 다른 알고리즘의 효율성 비교, 평가용

 

3. LRU

-> 사용한 지 가장 오래된 페이지 교체

  1) Counter implementation: page 참조될 때마다 counter에 시간기록

  2) Stack implementation: page 참조되면 top으로 이동시킴

 

4. LRU-approximation 

-> LRU의 구현 복잡도를 낮추지만 유사한 성능

-> reference bit 사용

    -> 0으로 초기화, 참조되면 1로 변경

    -> 0이면 교체대상

 

  1) Additional Reference Bit Algorithm

    -> 각 페이지에 8 bit씩 할당

    -> 매 시간마다 bit를 오른쪽으로 shift

 

  2) Second chance (clock) Algorithm

    -> reference bit가 0인 page를 만날 때까지 1을 0으로 변경

    -> reference bit가 0이면 swap out

    -> swap in 하고 reference bit를 1로 변경

    -> clock hand (포인터) 다음 칸으로 이동

 

5. Enhanced Second Chance Algorithm

reference bit와 modify bit 사용

6. Couter-Based Algorithm (잘 안쓰임)

각 page마다 reference 횟수 기록

  1) LFU

    -> 참조횟수 작은 page 교체

    -> 활발하게 사용되는 page는 큰 참조횟수 갖게 될 것

    -> 초기에만 집중적으로 사용되고 이후에 사용 안될 경우 문제 발생

 

  2) MFU

    -> 참조횟수 큰 page 교체

③ Thrashing

---

프로세스가 충분한 frame을 할당받지 못해서 page fault 매우 높아짐

-> CPU utilization 감소

 

Low CPU utilization을 해결하기 위해 multiprogramming의 정도를 높임

-> swap in/out은 disk access이므로 waiting 상태로 전환, CPU가 놀고 있다고 판단

-> 다른 프로세스가 추가됨

-> 과도한 paging 작업 유발

 

● Thrashing 예방 (Working set model 사용)

-> frame을 필요한 만큼만 제공

-> 어떻게 각 프로세스가 필요로 하는 최소한의 프레임 수를 알 수 있는가? "Locality Model"

 

Locality Model

-> 프로세스가 실행될 때 항상 특정 지역에서만 메모리를 집중적으로 참조

 

프로세스는 demand paging에 의해 전체 메모리가 활성화되는 것이 아니라, 일부 set of pages만 활성화된다.

활성화된 set of pages를 locality라고 하는데, 프로세스는 하나의 locality에서 다른 locality로 이동하게 된다.

Locality의 합이 전체 메모리 크기보다 클 경우 thrashing이 발생한다.

 

● Working Set Model

n번 만큼의 page reference 관찰

  -> if n 작음 : 전체 locality 포함 못함

  -> if n 큼    : 여러 개의 locality 과도하게 포함됨

  -> if n 무한 : 전체 프로그램 포함

 

WSSi (Working set of Process Pi): 최근 n번 동안 참조된 page의 총 개수

∑WSSi (total demand for frames) > physical memory size 이면 thrashing 발생

 

④ Allocating Kernel Memory

---

kernel memory는 user memory와는 다르게 취급

user mode process에 할당하는 page list와는 다른 별도의 메모리 풀에서 할당 받음

 

이유

1. 커널은 다양한 크기의 자료구조를 위해 메모리를 할당 받음

2. 일부 커널 메모리는 연속적이어야 함

 

● 커널 프로세스에 할당되는 메모리 관리

1. Buddy system

2. Slab Allocator

 

● Buddy system

물리적으로 인접한 페이지로 구성된 고정 크기 세그먼트에서 메모리 할당

1. 할당

012

2. 병합 (Coaleascing)

01

 

● Slab

하나 또는 그 이상의 연속적인 메모리 공간을 slab이라고 한다.

이 slab을 kernel object마다 미리 할당한다.

Cache는 하나 또는 그 이상의 slab으로 구성된다.

Slab을 미리 할당하기 때문에 fast memory request가 가능하다.

 

예를 들어, 7kb의 semaphore를 할당하기 위해서 8kb의 page가 필요하므로

모든 semaphore마다 1kb씩 공간이 낭비되는데,

slab allocation을 사용할 경우 연속적인 page로 할당해놓고

semaphore 크기에 딱 맞춰서 할당하기 때문에

internal fragmentation을 방지할 수 있다.