[OS] Virtual Memory

✔️ 가상 메모리 ( Virtual Memory )

◾️ 가상 메모리란 RAM을 관리하는 방법이다. 각 프로세스(프로그램)에 실제 물리적 메모리 주소가 아닌 가상의 메모리 주소를 주는 방식을 말한다. 

◾️ 가상 메모리는 크게 나누어 Paging 방식과 Segment 방식이 있다.

◾️ 대부분의 시스템은 Paging 기법을 사용한다. 

◾️ 가상 메모리는 운영체제가 관리한다. 

◾️ 논리적 메모리 주소를 물리적 메모리 주소로 변환하는 것은 하드웨어가 한다.

◾️ 이 챕터에서는 Paging 기법을 사용하는 것으로 가정한다. 

✔️ Demand Paging 

 

◾️ Demand Paging이란 Page 요청이 있을 때, Page를 메모리에 올리는 것을 말한다.

◾️ 프로세스(프로그램)이 실행될 때 해당 프로세스를 구성하는 논리적 주소 공간에 해당하는 모든 Page를 전부 물리적 메로리에 적재하지 않는다. 즉, 요청 받은 Page만 물리적 메모리에 적재한다.

◾️ 프로그램을 구성하는 Page중 실제로 빈번히 사용되는 Page는 제한적이다. 자주 사용되지 않은 예외처리 코드를 가지고 있는 Page를 물리적 메모리에 올려두는 것은 비효율적이다.

 

 

◾️ 맨 오른쪽 원기둥 모양은 하드 디스크(backing store)를 나타낸다. 

◾️ 위 그림을 보면 0번, 2번, 5번 Page는 물리적 메모리에 위치하고 나머지 Page는 하드 디스크에 있다. 즉, 현재 필요한 Page만 물리적 메모리에 적재 되어있다.

◾️ 하드 디스크를 보면 프로그램에는 5번 Page까지만 존재한다. 6번, 7번 Page는 사용되지 않는다. 따라서 Page table에서 6번, 7번 Page는 invaild 상태이다. 현재 사용되지 않는 1번, 3번, 4번 Page도 invaild 상태임을 볼 수 있다.

◾️ Page table의 Entry는 해당 시스템 주소공간 체계의 Max 크기만큼 만들어지는데 위 그림 시스템에서는 Page를 7개까지 만들 수 있나보다.

◾️ 만약 CPU가 1번 'B' Page에 대해서 주소 변환을 요청했더니 물리적 메모리에 해당 Page가 적재되어 있지 않을 수 있다. 이러한 상황을 Page Fault라고 한다. Page Falut가 발생하면 하드 디스크에서 요청받은 Page를 가져와야한다. 이는 I/O 작업이고, 이 때 OS가 개입하여 커널 모드에서 해당 Page를 물리적 메모리에 적재한다.  

 

◾️ Page Falut 처리과정

1. 잘못된 Page 접근인지 확인한다. 잘못된 접근이라면, 해당 프로세스를 abort 시킨다. 
2. 물리적 메모리에 존재하는 빈 Page Frame을 얻어낸다. (만약 빈 Page Frame이 없으면, 메모리에서 Page 하나를 쫓아낸다. 쫓아내는 기준은 알고리즘에 의해 결정된다. 잠시후 살펴볼 예정.)
3. 빈 Page Frame을 얻었스면 하드 디스크에서 요청 받은 Page를 찾아 물리적 메모리에 올린다. (이는 I/O 작업이다. 참고로 I/O 작업은 매우 느리다. 하드 디스크는 메모리에 비해 수십만~수백만배 느리다.)
4. CPU는 커널모드에서 유저모드로 돌아와 메모리 주소변환을 MMU에 의해 정상적으로 수행한다. 

 

◾️ 그림으로 보는 Page Falut 처리과정

1. 메모리 레퍼런스(논리적 주소)를 Page Table을 이용하여 주소변환을 하려고 했더니 in-vaild 상태이다. 즉, Page가 물리적 메모리에 적재 되어있지 않는 상황이다.
2. 따라서 trap이 발생하여 CPU는 운영체제한테 넘어간다. (커널모드 전환)
3. OS는 하드 디스크에 있는 Page를 찾아서,
4. 물리적 메모리의 빈 Page Frame에 적재한다.
5. 그리고 해당 Page Frame 번호를 Page에 해당하는 Entry에 기록하고 vaild 상태로 만든다.
6. 이제 다시 CPU는 프로세스를 잡고 instruction을 수행한다.  

◾️ Page Fault가 발생했을 때 하드 디스크에 접근하여 Page를 가져오는 것은 매우 오래걸리는 작업이다.

◾️ Page Fault 발생 횟수(rate)에 따라 메모리 접근 시간이 크게 좌우된다. 

◾️ 실제로 Page Fault rate는 0.0X 정도이다. 즉 대부분의 경우에서 Page Fault는 발생하지 않는다.

메모리 접근 시간 : (Page Fault가 안나는 비율 * 메모리 접근 시간) + (Page Fault가 나는 비율 * (다양한 오버헤드)) 

 

◾️ Page Replacement란 Page를 물리적 메모리에서 하드로 쫓아내는 것이다.

◾️ Page Fault가 발생하여 하드에 있는 Page를 메모리에 적재 하려고할 때 비어있는 Page Frame이 없는 상황에서 어떤 Page를 하드로 내쫓아 공간을 확보할지 결정 해야한다. (Replace Algorithm을 통해 결정한다.)

◾️ Replacement 알고리즘은 Page Fault rate가 0에 가깝도록 하는 것이 목표다.

◾️ Reference String이란 Page가 참조 되는 순서를 나타낸다. 

 

◾️ 위 그림의 victim은 하드로 쫓아낼 Page이다. 그림으로 과정을 알아보자

1. vicitim Page를 하드로 swap out 한다.
2. Page Table에서 victim Page Entry에 대해서 in-vaild로 바꾼다. (현재 메모리에 없음을 표시)
3. 하드에서 새로운 Page를 메모리에 적재한다.
4. 새롭게 적게된 Page에 대한 Page Table Entry를 vaild로 바꾼다. (현재 메모리에 있음을 표시)

◾️ Page를 메모리에서 쫓아낼 때 만약 그 Page에 대해 wirte 작업이 이루어졌으면, 그 내용을 하드에 있는 Page에 반영해야한다. 만약 wirte 작업 등 Page에 대한 변경 작업이 없었으면 그냥 메모리에서 지우기만 하면 된다. 

 

Page Replacement 알고리즘 1

 

◾️ Optimal한 알고리즘이다. 즉 가장 좋은 알고리즘이다.

◾️ 미래에 참조될 Page 목록을 미리가지고 있다. 그 목록을 보고 가장 먼 미래에 참조되는 Page를 메모리에서 내쫓는다.

◾️ 미래에 어떤 Page가 요청될지 미리 알고 있어야 한다. 따라서 실제 시스템에서는 사용이 불가능하다. 

Optimal 알고리즘은 실제 시스템에서 사용 가능한 다른 Page Replacement에 대한 upper bound를 제공한다. 

◾️ 위 그림에서 5번 Page가 메모리에 적재될 때, 해당 시점에서 가장 미래에 참조되는 4번 Page를 내쫓는 것을 볼 수 있다.

◾️ 빨간색 : Page Fault가 발생한 경우

◾️ 연보라 : Page Fault가 발생하지 않고 메모리에서 바로 참조되는 경우 

Page Replacement 알고리즘 2

◾️ 먼저 메모리에 적재된 Page를 먼저 내쫓는 방식이다. (FIFO)

◾️ 이 알고리즘을 사용하면 기이한 현상이 발생한다. 메모리의 크기를 늘려줬을 때 성능이 나빠진다. 위 그림에서 확인할 수 있다. 이러한 현상을 FIFO Anomaly라고 한다. 

Page Replacement 알고리즘 

 

◾️ LRU 알고리즘은 가장 오래전에 사용된 Page를 쫓아낸다.

◾️ 가장 먼저 들어왔지만 가장 최근에 사용된 Page가 있다면 내쫓지 않는다.

◾️ 5번 Page가 참조될 때를 보자 3번 Page가 내쫓아진다. 해당 시점에서 3번 Page가 가장 오래전에 참조 됐음을 Refernce String을 통해 알 수 있다. 

◾️ 실제 시스템에서는 미래에 대한 Page 참조 목록을 알 수 없기 때문에 과거 기록을 사용한다. 

Page Replacement 알고리즘 3

 

◾️ LFU는 가장 덜 빈번하게 사용된 Page를 쫓아낸다. 

 

◾️ LRU 알고리즘의 문제점 : LRU는 마지막 참조 시점만 확인한다. 1번 Page는 가장 먼저 참조 되었지만 4번이나 참조되었다. 즉 4개의 Page들 중에서 참조 횟수가 가장 높음에도 불구하고 내쫓는 문제가 있다.

◾️ LFU 알고리즘의 문제점 : LFU 알고리즘은 현재 시각을 기준으로 가장 적은 참조횟수를 가지고 있는 Page 4를 내쫓는다. 하지만 4번 Page가 이후에 여러번 참조된다면, 4번 Page를 내쫓는 것은 좋은 선택이 아니다. 

 

LRU 알고리즘의 구현

◾️ LRU는 메모리 내의 Page들을 참조 시간 순서대로 Linked List로 나열해서 관리한다.

◾️ 그림에서 위쪽으로 갈 수록 오래전에 참조된 Page이고, 아래쪽으로 갈 수록 최근에 참조된 Page이다.

◾️ LRU 알고리즘은 가장 오래전에 참도된 Page를 내쫓는 알고리즘이다. 즉, Linked List의 가장 위쪽에 있는 원소를 쫓아내면 된다. ( O(1) 시간이 걸린다. )

◾️ 만약 어떤 Page가 새롭게 메모리에 적재되거나 또는 원래 적재되어 있던 Page가 다시 참조되면, 해당 Page를 Linked List에서 가장 아래쪽으로 이동시킨다.

 

LFU 알고리즘의 구현

◾️ LFU도 Linked List로 Page들을 관리하는 방법이 있다.

◾️ 그림에서 위쪽으로 갈수록 참조 횟수가 적은 Page이고, 아래쪽으로 갈수록 참조 횟수가 많은 Page이다.

◾️ LFU 알고리즘은 가장 적게 참조된 Page를 내쫓는 알고리즘이다. 즉, 가장 위쪽에 있는 원소를 쫓아내면 된다. 

◾️ 하지만 어떤 Page가 새롭게 메모리에 적재되거나 또는 원래 적재되어 있던 Page가 다시 참조되면, 해당 Page를 Linked List의 적절한 위치에 배치해야한다. 참조횟수로 줄세우기를 하기 때문에 최악의 경우 적절한 위치를 찾기 위해 모두 비교해야한다. ( O(n) 시간이 걸린다. ) 

◾️ LFU 알고리즘을 min heap으로 구현하면 O(logN) 시간으로 구현할 수 있다. 

 

 

 

 

◾️ Paging은 일종의 캐슁 기법이다. 메모리에 Page를 캐슁하는 것이다.
◾️ Paging뿐만 아니라 Buffer caching, Web caching 등이 있다. 

 

 

◾️ CPU는 프로세스 A를 running 하고있다.

◾️ CPU는 프로세스 A의 논리적 메모리 주소를 물리적 사용하여 CPU 클럭마다 명령어를 하나씩 읽어와서 실행한다.

◾️ CPU는 매 클럭마다 프레스 A의 명령어를 하나씩 읽어오고, 해당 명령어에 대한 논리적 주소를 물리적 주소로 변환하하여 명령어를 실행한다.

◾️ 논리적 주소를 물리적 주소로 변환했을때 해당 Page가 이미 메모리에 올라와있다면 바로 가져온다. 이때는 OS 개입이 없다. MMU와 같은 하드웨어에 의한 주소변환이 이루어질 뿐이다.

◾️ 해당 Page가 올라와있지 않다면, Page Fault가 발생하고 하드 디스크 접근이 필요하다. 즉 I/IO 작업이 발생하고 이때  OS가 개입한다. OS는 하드에 있는 Page를 물리적 메모리에 적재하고, 그 과정에서 Replacement가 필요하면 수행한다. 

 

◾️ LRU : OS는 과연 어떤 Page가 가장 오래전에 참조 됐는지 알 수 있을까? -> 알 수 없음!

◾️ LFU : OS는 과연 어떤 Page가 가장 적게 참조 됐는지 알 수 있을까? -> 알 수 없음!

◾️ 만약 요청된 Page가 물리적 메모리에 이미 적재되어있다면(cahe hit) 단지 MMU등의 하드웨어에 의한 주소변환이 이루어진다. 즉, OS는 해당 Page의 참조여부를 알 수 없다. LRU 또는 LFU 알고리즘은 OS가 주관하는 것이다. 그런데 캐슁된 Page의 참조 기록은 OS가 알아차릴 수 없는 것이다. 즉, OS는 Page 참조에 대해 반쪽짜리 정보만 얻을 수 있다. 

◾️ 따라서 실제 시스템에서는 LRU, LFU를 사용할 수 없다. LRU, LFU는 buffer, web caching에서 사용될 수 있다.

 

 

◾️ Clock 알고리즘은 LRU의 근사 알고리즘이다. 가장 최근에 사용되지 않은 Page를 쫓아내는 방식이다. (NUR or NRU)

 

◾️ 위 그림의 각 사각형은 Page Frame을 나타낸다.

◾️ 각 Page는 refernce bit가 있다. 이미 메모리에 적재된(캐슁된) 어떤 Page가 참조되면 하드웨어적으로 주소 변환이 일어난다. 이때 reference bit을 1로 만들어줘서 Page가 참조되었음을 표시한다. OS는 하드웨어가 만든 reference bit 정보를 참조하여 Page 참조 정보를 얻는다. 

◾️ referece bit는 해당 Page가 최근에 참조됐다는 것을 의미한다. 

◾️ OS는 원형 리스트로 된 Page 목록을 시계방향으로 돈다. 돌면서 referece bit가 1인 Page들을 0으로 바꾼다.

◾️ reference bit가 0이라면, 이는 시계 바늘이 한 반퀴 도는 동안 해당 Page에 대한 참조가 없었다는 의미다.

◾️ reference bit가 1이라면, 이는 시계 바늘이 한 반퀴 도는 동안 해당 Page가 적어도 1번은 참조가 있었다는 의미다.

◾️ 시계 바늘을 돌며, reference bit가 0인 Page를 메모리에서 내쫓는다. LRU는 가장 오래전에 사용된 Page를 내쫓는 방법이고, Clock 알고리즘은 가장 최근에 사용되지 않는 Page를 내쫓는 방법이다. 따라서 Clock 알고리즘은 LRU를 근사한다. 

 

modified bit

◾️ 어떤 Page에 대해 write 작업이 이루어졌다면, 해당 내용은 하드의 Page에 반영되어야한다. 

◾️ write 작업이 이루어진다면, 하드웨어는 해당 Page에 대한 modified bit을 1로 만들어주어 하드에 있는 Page에 변경 내용을 반영해야한다는 것을 표시한다. 

 

 

◾️ 메모리에는 여러 프로그램의 Page들이 적재되어있다. 

◾️ Page Fault를 줄이기 위해서는 프로세스가 필요한 일련의 Page들이 같이 적재 되어야 한다.

◾️ Code 영역과 Date 영역이 같이 메모리에 적재되어야 Page Fault가 덜난다. 

◾️ 예를들어 3개의 Page로 구성되는 for문 로직이 있다고 해보자. 이때 3개의 Page가 메모리에 모두 적재 되어있어야 Page Fault가 적게 발생한다. (for문이 10000번 반복될 경우 매번 Page Fault가 발생하면 효율적이지 못할 것이다.)

◾️ 프로그램 별로 Page 할당수를 정해놓지 않으면 특정 프로그램이 메모리를 장악할 수 있다. 따라서 프로그램마다 Page 할당수를 정한다. 이를 Allocation이라고 한다. 

 

 

◾️ 프로세스당 Page 할당수를 정하지 않더라도 LRU, LFU 알고리즘을 사용하면 알아서 적절히 할당되는 효과가 있다.

◾️ 어떤 프로그램이  메모리 공간을 많이 필요로 한다면 그 시점에서 해당 프로그램의 Page는 메모리에 많이 올라갈 것이고 다른 프로그램의 Page는 쫓겨난다. 즉, 굳이 미리 Page 할당수를 정해놓지 않더라도 자연적으로 알아서 할당량이 조절될 수 있다. 

 

◾️ 프로그램의 Page 할당수가 너무 적다면, Page Fault가 자주 발생한다. 

◾️ Thrashing이란 Page Fault가 지나치게 많이 발생하는 현상을 말한다. 

 

◾️ x축은 메모리에 동시에 올라가 있는 프로그램의 개수다.

◾️ y축은 cpu 이용률이다. 

◾️ 프로그램이 1개만 메모리에 올라가있으면, I/O 대기동안 cpu는 idle 상태이다. 

◾️ 만약 여러 프로그램이 메모리에 올라가있으면, I/O 대기동안 cpu는 다른 프로세스를 running 한다. 즉, cpu 이용률이 높다.

◾️ 아주 많은 프로그램이 메모리에 올라간다면, 프로그램당 할당되는 메모리 공간 (Page 할당수)이 적고 각 프로세스는 Page Fault를 많이 발생시킨다. 즉 I/O 대기가 많이 발생하여 cpu는 idle 상태를 자주격는다. OS는 이런 현상을 cpu가 노논다고 판단하여 프로그램을 더 running 시키려고 메모리에 올린다. 상황을 악화되고 Thrashing을 겪는다.  

◾️ 이러한 Thrashing을 막기 위해서는 multiprogramming degree를 조절해야한다. (working set, pff 알고리즘 사용)

 

◾️ 참조의 지역성 : 예를들어 for문이 실행되면, for문을 구성하는 Page는 자주 사용된다.

◾️ 특정 시간동안 집중적으로 참조되는 Page 집합을 locality set 또는 working set이라고 한다. 

◾️ working set을 메모리에 무도 올려줘야 Page Fault 발생을 줄일 수 있다.

◾️ 만약 메모리에 많은 프로그램이 올아와있어서 working set을 못 올린다면, 현재 할당 받은 Page를 모두 반납하고 해당 프로세스는 하드로 swap out된다. 

◾️ 즉, working set을 한 번에 메모리에 올리는 것이 보장이 안될 때 해당 프로세스에 할당된 메모리를 통째로 뺐는다.

 

◾️ 특정 시간동안 집중적으로 참조되는 Page 집합인 working set은 미리 알아낼 수가 없다.

◾️ 그저 과거의 기록을 통해 working set을 추정할 수는 있다. 

◾️ 과거 델타 시간동안 참조되었던 Page를 working set이라고 정의한다. 윈도우를 이동함에 따라 working set은 계속 변하는 것을 볼 수 있다.

 

◾️ working set이 메모리에 한 번에 올라가지 못한다면 해당 프로세스는 swap out 되고 나머지 프로그램들이 working set을 보장 받도록한다. 따라서 Thrashing을 막을 수 있다. 

 

 

◾️ PFF는 프로세스에 대한 Page Fault rate를 통해 Page Frame 할당수를 조절하는 알고리즘이다.

◾️ 만약 특정 프로그램이 Page Fault를 많이 낸다면, working set이 보장되지 않는 상태이므로 해당 프로그램에 대한 Page Frame 할당수를 늘린다.

◾️ Page Fault를 너무 안내는 프로세스에 대해서는 Page Frame 할당수를 조금 줄여서 일정 수준의 Page Fault를 유지하게 한다. 

 

◾️ 물리적 메모리의 크기가 커지면 그에 따라 Page 크기도 늘려줄 필요가 있다. 최근에는 Page 크기를 늘리는게 추세다.