Operating System - Ch10. Virtual memory

본 글은 Operating System Concepts 10판을 기준으로 작성되었습니다...!

 

 

이번 챕터에서는 Virtual memory에 대해서 알아보자.

Virtual memory의 기본 개념은 Secondary Storage와 Physical memory 간의 "Swap", 그리고 이론상 무한한 양의 메모리를 사용할 수 있도록 하는 것이다.

아출발

---

 

Virtual memory and Physical memory, 제일 오른쪽은 disk임.

 

이 그림을 통해 알 수 있듯이, virtual memory를 잘 사용하면 physical memory의 크기보다 훨씬 큰 양의 메모리를 사용할 수 있다. 이것이 가능한 이유는 바로 디스크의 일부분을 메모리로 생각하고 사용하기 때문이다. 

 

Physical memory에 Free frame이 더이상 없어 새로운 프로세스가 왔을 때 곤란해진다. 이 때 disk를 메모리처럼 사용해서새로운 프로세스가 필요로 하는 만큼의 메모리 확보를 위해 이미 할당된  frame의 페이지를 디스크로 옮겨준다. 그렇게 생기는 free frame을 새로 들어오는 프로세스에게 매핑해준다. 이를 demand paging이라고 한다.

 

그렇다면, Physical memory에 올려져있지도 않는 프로세스는 어떻게 동작할 수 있는가? CPU에서 프로그램 실행을 위해 메모리 영역 참조를 할 때 page table을 살펴보면 대응되는 프레임을 찾을 수가 없을 것이다. 이때 빠르게 physical memory에 disk에 옮겨놓았던 페이지를 다시 옮겨주고 그 프레임에 있던 페이지는 다시 디스크로 옮겨 넣는 방식으로 동작한다. 실제로 프로세스가 실행이 되면 처음에 logical address만 할당이 된다. 

 

 " CPU의 요청이 있을 때만 physical memory에 올리는 기법 " = Demand paging

  

 

Demand Paging

상술한 내용 때문에 demand paging을 page-level swapping이라고 한다. 

 

프로세스가 시작될 때는 physical memory에 아무것도 올리지 않고, 프로세스가 동작하면서 필요한 부분의 페이지를 메모리로 올려 사용하는것이 핵심 개념이다.

 

Physical memory가 꽉 찼을 때, 디스크에서 페이지를 불러오려면 physical memory에 올라가 있는 페이지를 디스크로 옮겨줘야 하는 경우가 생기는데, 이 때 안 쓰이는 페이지가 디스크로 옮겨지는 과정을 swap이라고 한다. 왜 이게 잘 작동하지?

 

Locality 때문이다. 챕터9에서 Temporal locality와 Spatial locality에 대해 알아봤는데, Demand paging에서는 둘 다 적용되고, 성능도 좋다.

 

챕터 09에서 살펴봤듯이, Page table에는 메모리 보호를 위해 frame number와 valid-invalid bit 정보가 들어있다. Invalid 한 상태인 페이지에 접근하는 경우를 Protection fault라고 한다.

 

근데, Demand paging기법에서는 프로세스가 시작될 때 테이블의 모든 페이지를 invalid로 만들어두고 시작한다. 따라서 참조될 수 있는 영역인데도 invalid한 영역인 경우가 발생한다. (page-fault) 이 경우, 실제로 참조되지 못하는 메모리 (protection-fault) or page-fault인 경우로 나눌 수 있다. 

페이지 테이블을 봤는데 페이지가 invalid한 상태라면, CPU입장에서는 아무것도 할 수 없다. 따라서 이 때의 관리는 운영체제가 진행한다.

 

Page Fault

Page Fault는 페이지 테이블 안에 invalid로 설정되있는 페이지에 참조하려는 경우를 말한다.

 

Steps of Page Fault

1. 특정 메모리 영역을 참조하려고 할 때 MMU가 페이지 테이블에 특정 페이지를 참조한다.

2. 페이지가 invalid 상태에 있어 CPU가 trap을 건다.

3. 운영체제가 interrupt 신호를 받고, backing store (디스크에 존재하는 페이지)를 읽고,

4. free frame에 할당한다.

5. 페이지 테이블을 이에 맞게 업데이트한다.

6. valid로 된 페이지를 참조해서 메모리를 정상적으로 참조한다.

 

만약 3, 4 단계에서 free frame이 존재하지 않는다면, 안 쓰는 페이지를 디스크에 넣고 그 공간에 디스크에 저장되있던 페이지를 넣는데, 이를 page replacement라고 한다.

 

Page replacement

상술했듯 physical memory에 free frame이 없을 때 page fault가 발생하면 page replacement가 발생한다.

어떤 페이지를 디스크에 넣고 빈 프레임에 페이지를 넣는데, 어떤 페이지를 디스크로 보낼 것인가를 정하는 것을

page replacement 알고리즘이라고 한다.

 

쓸 예정이 없거나, 과거에 잘 안썼거나 등을 알고리즘을 통해 판별하고, 잘 안쓰겠다 싶은 페이지를 디스크에 보내는데, 이 때 판단 근거로 쓰이는 것이 바로 Locality이다. 이전에 사용했었다면 앞으로 다시 사용할 가능성이 높고, 이전에 계속 사용되지 않았다면 앞으로도 사용되지 않을 확률이 크다.

 

- Belady's proof: 가장 오랫동안 사용되지 않은 페이지를 디스크에 보내자.

victim이 바로 디스크에 보내질 희생양 페이지.

 

Page Replacement Algorithms

자주 쓰지 않는 페이지를 교체하는 것, 가장 작은 page-fault rate가 알고리즘의 목표.

 

 

프로세스에게 할당된 프레임 수가 많을수록, page-fault는 적게 발생한다. 

 

- FIFO: 제일 공평한 알고리즘. 다만 성능이 좋지 않다. 그래서 FIFO는 사용하지 않는다.

- LRU (Least Recently Used): 최근에 가장 사용되지 않은 페이지를 디스크로 보내는 알고리즘이고, 가장 Optimal한 알고리즘이다.

 

LRU의 구현

- Timestamp를 구현한다. 사용된 시간대의 시간 정보를 가지고 있다. 이를 이용해서 가장 오래전에 사용된 페이지를 디스크로 보낸다는 개념이다. 페이지를 참조할 때마다 timestamp를 관리해주어야 한다. 따라서 오버헤드가 아주 크다. 

 

- Stack을 구현한다. 가장 최근에 사용된 페이지가 스택의 top에 위치하도록 한다. 스택의 크기와 스택 유지에 대해서 오버헤드가 크다.

 

- Approximation: timestamp을 표현하기 위한 bit수(4~8)를 1bit까지 줄인다. 이를 위해 등장한 알고리즘이 LRU Approximation Algorithms이다.

 

LRU Approximation Algorithms

- Reference bit: 처음에는 0으로 설정해두고, 페이지가 참조가 되면 1이 된다. 그리고 이를 주기적으로 0으로 다시 바꾼다.  timestamp를 1bit로 표현하는 개념이다. Reference bit가 0인 페이지중 랜덤으로 하나 골라서 디스크로 보낸다. 이 때 문제는, 처음부터 reference bit가 0이었던 페이지인지 1이었던 것이 0이 된 것인지 구별이 불가능하다는 문제점이 있다. 이를 해결하기 위해 등장한 것이 Second chance이다. 

 

- Second Chance (LRU clock): victim으로 선정될 페이지를 미리 골라놓고, 만약 골랐던 페이지가 참조됐다면 reference bit를 0으로 바꾸고 다음 페이지를 선정한다. 만약 다음 페이지로 reference bit가 1이면 또 0으로 만들고 다음 페이지를 고른다. 고른 페이지의 reference bit가 0이라면 그 때 replacement를 수행한다. 사실 이것도 오버헤드가 커서 사용하지 않는다.

 

NRU (Not Recently Used) or enhanced second chance ★

Reference bit (R)와 Modify bit(M), 총 두 개의 비트를 사용한다.

 

NRU

  NRU 알고리즘에서는 Modify 비트와 Reference 비트를 통해 총 네 가지 상태를 표현한다. 현재 가장 많이 사용되고 있는 알고리즘이다.

 

  LRU에서 r을 모두 0으로 설정해준 것처럼 r과 m 모두 0으로 설정해놓는다. write될 때는 r과 m 모두 1로 변경한다. Read가 될 때는 r은 1, m은 0으로 변경한다. 그림을 보면, m이 1로 변했을 때, 즉 modify가 된 경우에는 다시 modify되기 전으로 돌아가지 않는다. Class 0가 먼저 희생양으로 지목받고, 그 다음으로 1, 2, 3 순서로 희생양으로 지목된다.

 

  

LFU (Least Frequently Used)

NRU가 사용된지 가장 오래된 페이지를 선별하는 알고리즘이었다면, LFU는 가장 적게 참조된 페이지를 선별하는 알고리즘이다. 사용 횟수를 세기 위해 counter가 필요하고, 하나씩 올리면서 증가하는 오버헤드를 줄이기 위해 counter를 비트로 표현하게 된다. 결국 counter가 reference bit의 형태가 되면서 approximate LRU랑 똑같아진다.

 

Allocation algorithms

Physical memory의 프레임을 어떻게 할당해줄것인가에 대한 알고리즘들.

 

- Equal allocation: 모든 프로세스에게 공평하게 프레임을 할당해주기.

- Proportional allocation: 더 큰 프로세스에게 더 많은 프레임을 할당해주기.

- Priority-based allocation: 프로세스의 우선순위에 따라 프레임을 할당해주기.

 

현재 운영체제에서는 proportional allocation을 주류로 쓰고 priority 개념과 함께 사용한다.

 

Thrashing

CPU utilization이 최대에 달하기도 전에, 뚝 떨어지는 것을 thrashing이라고 한다.

Thrashing이 발생하는 이유는, 프로세스 수가 많아지면서 physical memory보다 훨씬 많은 양의 메모리를 필요로 하고, 이 때 계속해서 page fault가 계속 발생하고 replacement가 계속 일어난다. (이는 현재 수행중인 프로세스의 locality 사이즈의 합이 메모리 사이즈보다 크다는 것을 의미한다.) replacement는 I/O이기 때문에 느리고, I/O수행중에는 CPU가 놀게 되면서 CPU utilization이 뚝 떨어지는 현상이 발생하는 것이다.