[운영 체제와 정보기술의 원리] 8장. 가상메모리

0. Virtual Memory

프로그램이 실행되려면 실행에 “당장” 필요한 부분이 memory에 적재되어 있어야 한다.

현대 time-sharing 시스템에서는 여러개의 process들이 메모리를 함께 사용하므로, OS는 “어떤 process에게 어느정도의 memory를 할당할지“를 결정해야 한다.

OS는 보통 하나의 process에 메모리를 몰빵해서 주기보다는 몇몇 process들에게 집중적으로 할당하고, 시간이 흐르면 이들로부터 메모리를 회수해서 또 다른 process들에게 주는 방식으로 동작한다.

Process의 빠른 실행을 위해 process마다 “최소한” 확보해야하는 memory의 크기가 존재하기 떄문이다.

프로그램이 실행되기 위해 그 process의 address space의 전체가 메모리에 적재되어야 있어야 되는것은 아니다. OS는 당장 필요한 부분만을 메모리에 적재하고, 그렇지 않은 부분은 disk의 swap area에 내려놓고, 다시 필요하면 메모리에 있는 부분들과 교체한다.

이런 방식을 채택함으로써 프로그램 입장에서 “physical memory의 크기에 대한 제약“에서 자유로워진다.
또한, 프로그램 입장에서 physical memory를 생각할 필요 없이 자기 자신만의 독자적인 memory를 사용하는것을 가정할 수 있는데, 이러한 공간을 virtual memory이라고 부른다.
- 즉, virtual memory는 process 각각 마다 0부터 시작하는 address space를 가지게 된다. 이들 중 일부는 메모리에 적재되고, 나머지는 swap area에 존재한다.

Virtual Memory 기법

Demand Paging (요구 페이징)
- 대부분의 경우에 이 방식을 사용한다.
Demand Segmentation (요구 세그먼테이션)
- 하나의 segment를 여러개의 page로 나누는 paged segmentation 방법에서 사용한다.
- 즉, 세부적인 구현에서는 demand paging만 사용된다고 할 수 있다.

2. Demand Paging (요구 페이징)

Demand Paging: 프로그램 실행 시, process를 구성하는 모든 page를 한꺼번에 메모리에 올리는게 아니라, 당장 사용될 page만을 올리는 방식을 말한다.

Demand paging에서는 특정 page에 대해 CPU의 요청이 들어온 후에야, 해당 page를 메모리에 적재한다.
이런 기법의 장점
1. Memory 사용량이 감소한다 (필요한 부분만 적재하기 때문)
2. I/O overhead가 줄어든다 (process 전체를 메모리에 올리는데 소요되는 I/O overhead 줄어든다)
3. Response time이 단축된다 (사용되지 않을 주소 영역에 대한 I/O 불필요)
4. 시스템에 더 많은 process를 수용할 수 있다.
5. 프로그램이 physical memory의 용량 제약에서 벗어난다 (일부 page만을 적재하여 physical memory보다 큰 프로그램도 실행가능)

Virtual memory기법에서는 process가 실행되는 동안 일부 page만 메모리에 있고 나머지는 swap area에 있다. 이런 시스템 특성상, 특정 process의 페이지들중에서 “어떤 page가 메모리에 존재하고, 어떤 page가 메모리에 존재하지 않는지”를 구별하기 위해서 valid-invaild bit (유효-무효 비트)를 표시한다.

process의 모든 page에 대해 존재하므로, page table의 각 entry에 저장된다.
Process가 실행되기 전에는 invalid로 초기화되고, 특정 page가 참조되어 memory에 적재되면 valid로 바뀐다.
Memory -> Swap area로 쫓겨날때는 다시 invalid가 된다.
Invalid인 경우
1. Page가 현재 memory에 없는 경우
2. 그 page가 속한 address space를 process가 사용하지 않는 경우
Page fault (페이지 부재)
- CPU가 참조하려는 page가 현재 memory에 올라와있지 않아, invalid bit로 세팅되어 있는 경우

Demand Paging의 page fault 처리

CPU가 invalid page에 접근하면

Address translation을 담당하는 하드웨어인 MMU가 page fault trap을 발생시킨다.
CPU 제어권이 kernel mode로 바뀌고, OS의 page fault handler (페이지 부재 처리루틴)이 호출되어 다음 그림과 같이 처리한다

Page fault 처리 과정
1. CPU가 page N을 참조한다
2. Page table에서 page N이 invalid 상태를 확인한다
3. Page fault trap이 발생한다
4. Disk에서 부재 page를 empty frame으로 적재하고, page table을 업데이트한다.

즉, 부재 상태의 page를 memory에 적재하기에 앞서 OS는 해당 page에 대한 접근이 적법한지를 체크한다.

다음 두 경우에 해당하면 process를 종료시킨다.

사용되지 않는 address space에 속한 page에 접근
해당 page에 대한 접근 권한 위반 (protection violation)
- Read-only인 page에 write 시도한 경우

해당 page에 대한 접근이 적법하다고 판명이 나면,

Physical memory에서 free frame을 할당받아, 그 공간에 해당 page를 읽어온다
만약 free frame이 없다면, 기존의 메모리에 있는 페이지 중 하나를 swap area로 쫓아낸다 (swap out)

한편, 요청된 page를 disk -> memory로 적재하기까지는 오랜 시간이 소요된다
Page fault를 발생시킨 process는 CPU를 빼앗기고 blocked state가 되며, 현재까지 수행하던 register 및 PC 값등을 PCB에 저장한다. Disk I/O가 완료되어 interrupt가 발생하면 page table에서 해당 page의 valid-invalid bit를 valid로 세팅하고 다시 process를 blocked state에서 ready queue로 이동시킨다. 그러면 PCB에 저장되어 있던 context를 복원시켜 이전에 중단되었던 명령을 재개한다.

Demand Paging의 성능

Demand paging의 성능에 가장 큰 영향을 미치는것은 page fault의 발생 빈도이다.

Page fault가 일어나면 요청된 page를 Disk -> Memory로 읽어오는 막대한 overhead 발생.

Effective Access Time (유효 접근시간)

  (1 - P) * memory access time
  + P * (
  page fault 처리 overhead +
  메모리에 empty frame이 없는 경우 swap-out overhead +
  요청된 page의 swap-in overhead +
  process 재시작 overhead
  )

p: page fault rate [0, 1]

Page fault가 일어나면 다음과 같은 overhead가 발생한다

Memory에 올라와 있는 page 중 하나를 swap out시킨 후, 요청된 page를 memory로 swap-in 시킨다.
다 읽어왔으면 interrupt를 통해 프로세스를 ready-queue에 넣어준다

이러한 과정에는 disk I/O와 각종 overhead가 일어나서 시간이 오래걸린다. 따라서, effective access time이 줄어들수록 demand paging의 성능은 향상된다.

2. Page Replacement (페이지 교체)

Page fault가 발생하면, 요청된 page를 disk에서 memory로 읽어와야 하는데, 이때 physical memory에 empty frame이 없을 수도 있다.

Page Replacement
- Memory에 올라와있는 page중 하나를 swap out 시키는 작업
Page Replacement Algorithm
- 어떠한 frame에 있는 page를 쫓아낼 것인지 결정하는 교체 알고리즘
- Goal: page fault rate을 최소화
- 미래에 참조될 가능성이 적은 page를 쫓아내자!
Page Reference String (페이지 참조열)
- 참조되는 page number을 시간 순서대로 나열한 값들
- ex) 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
- 해당 page가 memory에 올라와있으면 hit이고 아니면 miss라고 한다.

1. Belady’s Optimal Algorithm (최적 페이지 교체)

Belady’s Optimal Algorithm
- 가장 먼 미래에 참조될 page를 쫓아낸다
- 어떤 순서로 참조될지 미리 알고있어야 하므로 실제로 사용될수는 없다.
- 유용한 경우: 알고리즘의 성능에 대한 상한선을 제공한다

2. FIFO Algorithm

FIFO Algorithm
- Physical memory에 가장 먼저 올라온 page를 쫓아낸다
- Page의 향후 참조 가능성을 고려하지 않기 때문에 비효율적인 상황이 발생할 수 있다 (가장 먼저 온 page가 참조가 엄청 많이 될 수도 있기때문)

위의 그림은 FIFO의 문제점을 보여준다.

Memory frame이 3개일때 9번의 page fault가 일어났다.
Memory frame이 4개일때 10번의 page fault가 일어났다.

위와 같이 memory를 증가시켰음에도 불구하고 page fault가 오히려 증가했다. 이와 같은 현상을 FIFO anomaly라고 부른다.

3. LRU Algorithm

LRU (Least Recently Used)
- 가장 오래전에 reference된 page를 쫓아낸다. (aka 마지막 참조 시점이 가장 오래된 page)
- Temporal Locality: 최근에 참조된 page가 가까운 미래에 다시 참조될 가능성이 높은 성질.

4. LFU Algorithm

LFU (Least Frequently Used)
- 과거에 reference count가 가장 적었던 page를 쫓아낸다
- 최저 reference count가 같은 page가 여러개 있을 경우에는 임의로 하나를 선정한다
  - 혹은 상대적으로 더 오래전에 참조된 page를 쫓아내면 성능향상을 할 수 있다.
LFU는 reference count를 하는 방법에 따라 Incache LFU와 Perfect LFU로 나눌 수 있다.
- Incache LFU
  - Memory에 올라온 후부터 참조 횟수를 카운트. 쫓겨났다가 다시 들어온경우는 0으로 초기화
- Perfect LFU
  - Memory에 올라온 여부와 상관없이 과거 total reference count를 계산
  - 장점: Page ref count를 정확히 반영할수 있다
  - 단점: Memory에서 쫓겨난 page의 ref count까지 모두 보관하고 있어야 하므로 overhead가 더 크다

LFU 알고리즘은 LRU 보다 오랜 시간 동안의 참조 기록을 반영할수 있다는 장점이 있다.

LFU는 ref count를 통해 장기적인 시간 규모에서의 참조 성향을 반영.
LRU는 직전에 참조된 시점만을 반영.
LFU 단점
- 시간에 따른 page ref count를 반영하지 못한다
  - ex) 1, 1, 1, 1, 2, 2, 3, 3, 2, 4, 5 page ref string이 있다고 가정해보자. 현재 page 5를 참조하려고 한다.
  - 누굴 쫓아낼까? -> Page 4를 쫓아낸다. Ref count가 1이기 때문.
  - 하지만, page 4는 이제 막 인기를 얻기 시작한 page 일수도 있다.
- LRU보다 구현이 복잡하다.

5. Clock Algorithm

LRU와 LFU의 문제점

페이지의 참조 시각과 참조 횟수를 계속 software단에서 유지해야 되니까 overhead가 발생한다.
Clock Algorithm
- Hardware 지원을 통해 알고리즘 운영 overhead를 줄인다.
- LRU를 근사한 알고리즘으로, NUR (Not Used Recently) 또는 NRU (Not Recently Used) 알고리즘으로도 불린다.
- Clock algorithm은 오랫동안 참조되지 않은 page중 하나를 교체한다
- 교체되는 page의 시점이 가장 오래되었다는 것을 보장하지는 못한다 (그래서 LRU 근사)
- Hardware 지원으로 동작하기때문에 LRU에 비해 훨 빠르다
- 대부분의 시스템에서 Clock 방식을 채택한다

Clock Algorithm의 동작

교체할 page를 선정하기 위해 page frame들의 reference bit를 순차적으로 조사한다.
Reference bit는 각 frame마다 하나씩 존재하며, 그 frame내의 page가 참조될때 하드웨어에 의해 1로 세팅된다.
위의 그림처럼 시곗바늘처럼 순차적으로 돌면서 현재 가리키는 page reference bit가 1인 경우, 0으로 바꾼 후 넘어가고 만약 현재 가리키는 bit가 0인 경우에는 그 page를 교체한다
- 참조비트는 페이지가 참조될때 자동으로 1로 세팅되기 때문에, 시곗바늘이 한 바퀴 돌아오는 동안에 다시 참조되지 않을 경우에는 그 페이지가 교체되는 것이다.
  - 시곗바늘이 한바퀴 돌아왔을때 여전히 0이라면 그 시간동안 한번도 참조되지 않았단 뜻이기 때문이다.
  - 자주 사용되는 page라면 그 시간안에 다시 1로 세팅될것이다 -> 최근에 참조가 일어나지 않은 페이지를 교체하는 알고리즘이라 할 수 있다.
Second chance algorithm이라고도 부른다.

3. Page Frame의 할당

여러개의 process가 동시에 수행되는 상황에서는, 각 process에 얼마만큼의 memory space을 할당할지 결정 해야한다.

Process마다 page frame을 균등하게 할당하는것도 방법이지만, 시스템 성능향상을 위해서 더 효율적인 memory 할당방식이 필요하다.

대표적인 할당 알고리즘 3가지를 살펴보자.

Allocation Algorithm (할당 알고리즘)
- Equal Allocation (균등할당)
  - 모든 process에게 page frame을 균등하게 나눠주는 방식
- Proportional Allocation (비례할당)
  - Process 크기에 비례해 page frame을 할당하는 방식
- Priority Allocation (우선순위 할당)
  - Process의 priority에 따라 page frame을 다르게 할당하는 방식
  - 당장 CPU에서 실행될 process에 더 많은 page frame을 할당한다.

한편 위의 할당 알고리즘만으로는 page reference 특성을 반영하지 못할수도 있다.

현재 수행 중인 process 수가 지나치게 많을 경우
- Process당 할당되는 memory양이 과도하게 적어질수 있다.
- CPU에서 명령을 실행할때는 보통 여러 page를 동시에 참조한다 (code, stack, data 영역)
- 따라서 process를 정상적으로 돌리려면 어느정도의 page frame은 할당해줘야 한다
반복문이 실행중인 경우
- 반복문을 실행중인 process의 경우, 반복문을 구성하는 page들을 전부 올리는 편이 좋다.
- 그렇지 않으면 cycle을 돌때마다 page fault가 발생할것이고 성능이 현저히 떨어질것이다.
Process에게 필요한 memory양은 시간에 따라 다를 수 있다.

4. Global Replacement and Local Replacement (전역교체와 지역교체)

Page fault시 교체할 page를 선정할때, 교체 대상이 될 frame의 범위를 어떻게 정할지에 따라 다음과 같이 구분할 수 있다.

Global Replacement (전역교체)
- Process 상관없이 모든 page frame이 교체대상이 될 수 있다
- 전체 memory를 각 process가 공유해서 사용하고, replacement algorithm에 의해 할당되는 memory 양이 가변적으로 변하는 방법이다.
  - Ex) LRU 알고리즘으로 global replacement를 한다면, physical memory 전체에 올라와있는 녀석들 중 가장 오래전에 reference된 page를 교체한다. 그 page가 어떤 process 소속인지는 상관안한다.
- 이는 process별 frame 할당량을 조절하는 또 다른 방법이 될 수 있다
  - 전체 시스템 차원에서 더 자주 reference되는 page가 올라가기 때문에, process의 frame 할당량이 스스로 조절될수 있는것이다.
  - 전체 page frame을 대상으로 LRU, LFU, Clock 혹은 곧 살펴볼 Working-set, PPF 알고리즘도 global replacement 알고리즘으로 사용될 수 있다.
Local Replacement (지역교체)
- 현재 수행중인 process에게 할당된 frame 내에서만 교체 대상을 선정할 수 있다
- Process마다 page frame을 미리 할당하는것을 전제로 한다
- LRU, LFU 등을 process별로 독자적으로 사용할 때 해당된다