IT/OS

운영체제 5차 정리 - Virtual Memory

김효랑이 2018. 10. 30. 14:52
728x90
반응형

 호야의 블로그 

[OS] 운영체제 5차 정리

저번 메모리 관리에 이어 가상 메모리에 관한 정리를 하도록 하겠습니다.


Virtual Memory

*Background of Virtual Memory

  - 프로그램이 실행되려면 메인 메모리에 프로그램이 탑재되어야 하는데, 그 크기가 클 경우는 문제가 될 수 있다. 

  - 소스 코드의 전체의 루틴 중에 실행되어 사용되는 코드는 많지 않으므로, 전체 중에 일부만 탑재시키는 목적으로 가상 메모리를 사용한다.

  - Memory Management에서의 목적과 같이 Degree of multiprogramming을 높여주는 것이 목적이지만 Memory Management의 Overlay나 Dynamic Loading, Linking과 다른 것은 Logical address space의 대부분이 탑재되는 것이 아닌 대부분이 탑재되지 않으며 사용되는 부분만 탑재되어 물리적 주소공간을 절약할 수 있게 된다.

  - 각 process는 logical address space가 Virtual address space로 되며 이는 무한대의 공간을 가질 수 있다. 

  - 실행에서는 Logical address space(virtual address space)와 Physical address space가 분리되어있어야 하며, 이는 Execution time binding이 필요하다.

  - 프로그램이 Physical memory보다 클 경우도 탑재할 수 있으며 프로그램의 메모리를 분리하여 논리 공간과 물리 공간의 사용되는 부분만 탑재해서 사용하므로 Paging과 Segmentation이 사용될 수 있다. 

  - 메모리를 분리해서 관리하므로 공유메모리 구현이 가능하며 파일 공유가 쉽다.

  - 구현이 어려우며 잘못 사용한다면 성능이 저하될 수 있는 것이 단점이다.

  - 전체를 탑재하지 않아서 프로세스 생성에 효율적이며, 더 많은 프로그램이 동시에 돌아갈 수 있고, 프로세스를 load 혹은 swap 할 때, 더욱 적은 I/O로 가능하다.

  -  Virtual Memory는 OS가 제공하는 기능으로 Process의 어느 부분이 탑재되었는지, 언제 Process의 부분을 가져올 것인지, 어디에 탑재시킬 것인지, 언제 빼내 올 것인지를 정해야 한다.

  - OS가 언제 부분을 가져올지에 대해서 Page에 대해서 한다면 Demand Paging, Segmentation 기반으로 한다면 Demand Segmentation이라 한다.

  - 각 부분을 Main Memory로 가져오는 것을 Swap-in, 빼내는 것을 Swap-out이라 하며, 이 Swapping은 Medium-term Scheduler의 Swapping과는 다른 것으로 각 단위, 부분에 대한 것이다.


* Virtual Address Space

  - Logical address의 구조와 같으며, Stack과 Heap은 고정 크기가 아니며 함수호출을 하면 Stack이 늘어나서 점차 아래쪽으로 확장하고, Heap은 동적으로 메모리를 할당하여 점차 위쪽으로 확장한다.

  - Heap과 Stack 사이도 가상 주소 공간의 일부이지만 heap 또는 stack이 확장되어야만 실제 물리 페이지를 요구하게 된다.

  - 공백을 포함하는 Virtual address Space를 Sparse address Space라 한다.

  - Sparse address Space는 stack이나 heap이 확장될 때 사용되거나, 프로그램 실행 중 동적으로 라이브러리를 링크할 필요가 있을 때 사용된다.

  - Sparse hole에 shared library 공간을 주어서 메모리 공유를 할 수 있다.

  - 프로세스가 fork 할 때, 빠른 프로세스의 생성을 위해 일부 페이지가 공유될 수 있다. (code section)


*Demand Paging

  - OS가 VM을 관리할 때, Page 단위로 관리하며, Page 단위로 Swapping을 하게 될 텐데, 언제 Page를 Swap 할지를 결정하는 방법의 하나가 Demand Paging이다.

  - Lazy Swapper를 사용하여 Page 요구가 있을 때 해당 페이지를 backing-store에서 메모리에 Swap-in 한다.

  - 이때, Swapper는 프로세스 전체에 대해서 Swapping하는 개념과 비슷하고, Lazy Swapper는 Pager의 개념으로 개별 페이지들이 Swapping되는 것으로 이해한다.

  - Demand Paging을 사용하면 불필요한 I/O를 줄일 수 있고, 프로세스마다 필요한 물리 메모리를 줄일 수 있으며, 반응이 빨라지고, 더 많은 프로세스를 돌릴 수 있다.

  - Demand Paging이 아닌 Pre-fetching의 방식도 있으며 필요한 페이지를 예측하여 메모리에 올려놓는 방법으로 예측이 맞으면 Lazy Swapper보다 I/O를 줄일 수 있지만, 예측이 쉽지 않고, 예측이 실패하면 더 많은 대가를 치러야 해서 잘 사용되지 않는다.

  - Demand Paging을 위하여 Process의 Page 중에 메인 메모리에 탑재되었는지 아닌지를 알기 위해 Valid-Invalid bit를 사용하며, Page Table의 Page가 Invalid bit인 `i`를 나타내면 Page Fault가 발생했다고 한다.


*Page Fault

  - Process가 Page table에서 Legal address를 참조했으며, Page가 Main Memory에 탑재되지 않았을 경우를 나타낸다.

  - illegal Address를 참조했을 경우 OS는 Process를 abort() 하며 단순히 메모리에 없을 때 발생한다.

  - 프로세스가 시작할 때 1개도 메모리를 탑재시키지 않고 실행시키는 것을 Pure Demand Paging이라 한다.

  - Locality of reference 때문에, 프로세스가 실행되면 될수록 Page fault는 감소한다.

  - OS가 table에서 Invalid bit임을 확인하고 Page Fault가 발생하면 Empty Frame을 가져오고 Page를 Frame에 Swap-in 하며, Page Table을 Valid bit으로 바꾸고, Page fault가 일어나게 된 명령어를 다시 실행시킨다.

  - Page table과 swap space, Instruction restart를 위해서 Hardware인 MMU chip이 필요하다.

  - 한 번도 불리지 않은 Page는 Page Fault interrupt가 반드시 발생하고, 이때의 Page fault는 특별히 Cold fault라고 한다.

  - Cold fault는 프로세스가 시작하는 초기 단계에서 집중적으로 발생하며, Replacement 정책으로 Page fault를 줄일 수 있는 반면에 Cold fault는 줄일 수 없다.

  - Steps in Handling a Page Fault


7 Step in Handling a Page Fault

      1: Invalid bit임을 알아서 OS에게 Trap이 발생함을 알린다.

      2: Context Switch가 발생하며 Process의 정보를 PCB에 저장한다.

      3: Vectored Interrupt 형식으로 Interrupt를 발생시킨 device가 data bus에 interrupt vector를 실어서 보내는데 이 Interrupt vector를 받아서 Page Fault Interrupt임을 확인한다.

      4: 해당 Page의 참조가 illegal 했다면 abort 시키고, Legal 했다면 Backing store에서 Page를 찾는다.

      5: Free Frame을 확보하며 없으면 Replacement 정책으로 Swap 할 Frame을 고른다.

      6: Backing Store에서 Frame에 쓰이기 위해 Backing store, disk가 읽힐 때까지 Device Queue에서 기다린다.

      7: 해당 Device를 찾을 때까지 걸리는 Seeking time이 걸리게 된다.

      8: 찾은 후에 Free frame으로 Page를 가져온다 (Swap-in)

      9: 위의 기다리는 시간 동안 CPU에게 다른 프로세스를 할당한다. 원래의 프로세스는 waiting state에 있다.

      10: Swap-in이 끝나게 되면 Disk controller가 Interrupt를 발생시킨다.

      11: Interrupt가 발생하여 CPU에서 돌고 있던 다른 프로세스의 정보가 PCB에 저장되는 Context switch가 일어난다.

      12: 어떤 Interrupt인지를 확인하며, Disk로부터 발생하였음을 확인한다.

      13: OS에 의해서 Page Table의 수정이 일어난다.

      14: 원래의 프로세스가 다시 CPU의 할당을 받기 위해 잠시 기다린다.

      15: 원래 프로세스의 정보가 담긴 PCB를 가져오는 Context switch가 일어난다. 

      16: 처음에 Interrupt가 걸린 Instruction을 재시작한다. 


*Copy-on-Write

  - Copy-on-Write는 Process의 fork에서 사용되는 것인데, Parent Process가 fork 하여 Child Process를 만들게 되면 Parent Process의 Page들을 Child Process에게 복사해주게 되는데, 이때, 대부분의 Child Process는 exec system call을 사용하여 새로운 메모리 공간을 만들게 되므로, 이 복사해주는 작업이 필요 없게 된다.

  - Copy-on-Write는 Parent Process가 fork 하여 생긴 Child Process의 page를 공유하다가 Child가 Page에 write를 하면 해당 페이지만을 Copy 하는 것을 의미한다.

  - Process 생성에 효율적인 방법이다.

  - OS는 zero-fill-on-demand 기법으로 페이지를 관리하며 빈 페이지 집합인 Pool은 할당되기 전에 zero로 초기화되어 있어야 한다.


*Page Replacement

  - OS가 Free Frame을 관리하게 되는데, Kernel과 I/O 버퍼용 frame을 미리 확보해놓게 되고, 특히 I/O 버퍼는 상당히 큰 크기를 가지고 있다.

  - Process가 Page를 Swap-in 해야 할 경우에 Free frame이 없을 때도 있고 이때, Free frame을 기다리는 것은 너무 느리므로, Page Replacement를 해준다.

  - Swap-out 당하는 Page를 Victim이라 하며, Page fault rate를 최소화할 수 있는 Victim을 선택해야 한다.

  - Free Frame이 없는 경우 Victim Page를 내보내고 요청된 Page를 가져오는 2번의 메모리 접근이 필요하고 EAT이 증가하게 되는데, modify bit를 사용하여 이러한 Overhead를 감소시킬 수 있다.

  - Modify(Dirty) Bit를 사용하여 확인되면 내용이 원래 디스크 상의 페이지 내용과 다르다는 것을 알 수 있고 현재의 내용을 디스크에 기록하게 된다. Swap out 시에 이 bit를 확인하고 Disk에 기록하며, set이 안 돼 있으면 단순히 버린다. 이 기법은 읽기 전용 페이지에도 적용된다.

  - Basic Page Replacement


Page Replacement

1. 디스크에서 요구한 페이지의 위치를 확인한다.

2. 빈 프레임을 찾는다

  - 빈 프레임이 발견되면 빈 프레임을 사용한다.

  - 빈 프레임이 발견되지 않으면 Victim을 선정하기 위하여 Page Replacement 알고리즘을 사용한다.

  - Modify bit이 Set 되어있다면 Victim을 디스크에 기록하고, Page와 Frame Table을 수정한다.

3. 요구된 페이지를 읽고 Page와 Frame Table을 수정한다.

4. 사용자 프로세스를 다시 시작한다.

*Page and Frame Replacement Algorithm

  - Page Replacement Algorithm을 결정할 때, 각 프로세스에 할당되는 Frame의 개수에 따라 Page Fault는 다를 수밖에 없다.

  - Frame-allocation algorithm을 결정해야 하며 일반적으로 다음과 같이 Frame 수가 증가할수록, Page Fault가 감소하게 된다.


Graph of Page Faults vs The number of Frames

* First-In-First-Out(FIFO) Algorithm

  - 가장 간단한 Page Replacement Algorithm

  - 각 Page가 메모리 안으로 들어온 시간을 이용하며, 가장 오래된 페이지를 Victim으로 정한다.

  - Page가 들어온 시간을 이용하기 위해서는 FIFO Queue에 의해서 Page를 관리함으로써 구현할 수 있다.

  - Belady`s Anomaly : 할당되는 프레임의 수가 증가함에 따라 Page Fault가 증가할 수 있는 현상을 말한다. Belady`s Anomaly가 발생하는 이유는 Algorithm이 Stack property를 가지고 있지 않기 때문이다.

  - FIFO Algorithm은 Belady`s Anomaly가 발생하여, 다음과 같은 그래프를 보이게 된다.


* Optimal Algorithm

  - 앞으로 가장 오랫동안 사용되지 않을 페이지를 Victim으로 Replace 하는 알고리즘

  - Belady`s Anomaly가 발견되지 않으며 Stack Property를 가지고 있다.

  - 하지만 미래의 어떤 Page가 Reference 될지 모르기 때문에, 구현 불가능한 알고리즘으로 다른 알고리즘과 비교하기 위하여 사용된다.


* Least Recently Used(LRU) Algorithm

  - 사용된 지 가장 오래된 Page를 Replace 하는 알고리즘

  - Page가 언제 사용되었는지에 대한 시간 정보를 알고 있어야 하고, 이를 구현하는 방법으로는 Counter와 Stack이 있다.

  - Belady`s Anomaly는 없으나 하드웨어 지원이 필요하다.

  - Counter Implementation 

      : 모든 page는 Counter를 가지고 있으며, Page가 참조될 때마다, Counter에 Clock 값을 복사한다.

      : Page의 Counter 중 가장 작은 값을 가지는 Page가 Replace 된다.

      : 가장 작은 Counter를 찾기 위한 시간과 Page Table이 변경될 때마다 시간 값을 관리해야 하므로 Overhead가 존재한다.

  - Stack Implementation

      : Stack 구조를 사용하여 참조된 Page를 관리하며, Page가 참조될 때마다, 스택에서 제거되어 Top에 두어진다.

      : Bottom에 존재하는 Page가 가장 사용이 오래된 Page이므로 Victim으로 대체된다.

      : 중간에 존재하는 Page도 Top으로 갈 수 있으므로 구현을 쉽게 하기 위해서 Double Linked List로 Stack이 구현된다.

      : Bottom의 Page가 무조건 Victim이므로 Victim을 찾는 시간이 없다.

      : Page를 참조할 때마다 Stack의 위치이동이 일어나므로 Overhead가 존재한다.


* LRU Approximation Algorithm

  - LRU 구현에는 Hardware의 지원이 있어야 하고, 이를 완벽히 지원할 수 있는 하드웨어를 사용하지 않는다.

  - LRU를 위한 Hardware 대신에 Reference bit를 사용하여 LRU에 근사하는 여러 알고리즘이 사용된다.

  - Reference bit는 0으로 초기화되고, Page가 참조되면 1로 되며, 주기적으로 초기화된다.

  - Reference bit를 1개의 bit로 사용하면 정보가 부족할 수 있어서 여러 개의 bit를 Reference bit로 사용한다.

  - Reference bit는 Page의 사용순서까지는 아니지만 어떠한 Page가 특정 시점까지 사용되었고 어떠한 Page는 특정 시점까지 사용되지 않았는지 알 수 있다.

  - Additional Reference Bit Algorithm

      : 각 Page에 여러 bit를 할당하여 사용한다.

      : Shift register를 사용하여 Page 참조마다 모든 Page의 Reference bit를 Shift 한다.

      : 가장 작은 값을 가지는 Page가 Replacement의 대상이 된다.


 - Second Chance Algorithm

      : Reference bit이 1이면 0으로 바꾸어서 넘어가고 0이면 해당 Page를 Victim으로 결정한다.

      : Page가 참조되면 Reference bit가 1이 되므로 Replace 할 Page를 찾을 때는 Page를 거쳐 가며 확인하면서 Reference bit을 0으로 만들어 기회를 준다는 의미로 이름이 지어졌다.

      : 시계 방향으로 탐색하며 원형의 구조를 생각할 수 있어서 Clock Algorithm이라고도 한다.

      : FIFO Replacement Algorithm을 기반으로 하며, 원형 큐를 이용하여 구현된다.

      : 모든 Page의 Reference bit가 1이면 이 알고리즘은 FIFO와 같아진다.


Second Chance Algorithm

 - Enhanced Second Chance Algorithm

      : Reference bit와 Modify bit를 둘 다 사용하는 알고리즘

      : 입/출력 횟수를 줄이기 위해 변경된 페이지에 우선순위를 준다.

      : 교체될 페이지를 찾기까지 여러 번의 순환 큐를 검사할 수 있다.

      : Modify bit가 Set 되어 있다면 Replace 할 때에 Hard disk에 쓰기 하는 데에 부담이 있다.

      : 두 bit 모두 0일 때가 Replace 되기에 좋은 Page이며, Reference bit이 Modify bit보다 Replace가 되지 않을 우선순위가 높다.


* Counting Algorithm

  - 몇 번 참조되었는지 값을 가지고 있는 Counter를 가지고 있으며 2가지 방법으로 나누어진다.

  - Least Frequently Used(LFU)

      : Counter의 수가 가장 작은 Page를 대체하는 방법

      : 활발히 사용되는 Page는 Counter의 값이 클 것이고, 이를 이용하는 방법

      : 하지만 초기에 많이 사용되고 나중에는 사용되지 않는 식의 일이 발생한다면 문제가 된다

      : 일반화시키면 집중적으로 사용된다면 사용되지 않더라고 이 방식으로는 메모리에 머무르게 된다.

      : 이를 해결하기 위해 일정 시간마다 Counter bit를 1씩 shift 시켜서 지수 적으로 영향을 감소시킨다.

  - Most Frequently Used(MFU)

      : Counter의 수가 가장 큰 Page를 대체하는 방법

      : 작은 Counter의 수를 가진 Page는 가장 최근에 참조된 Page 것으로 해석한다.

      : 값이 큰 Counter를 가진 Page는 나중에 들어왔기 때문에 Counter가 클 것으로 해석한다.

      : Locality of reference를 배경으로 한 해석을 기반으로 한다.


* Allocation for Frames

  - 메모리는 크게 OS를 위한 부분과 사용자를 위한 부분으로 나눌 수 있으며, 프로세스는 사용자를 위한 부분의 메모리에 탑재되어 사용된다.

  - 가상 메모리 기법을 이용하여 프로세스의 일부 메모리만을 탑재하며 실행시킬 수 있게 되지만, 다중 프로그래밍 환경에서는 여러 개의 프로세스가 메모리에 존재하게 되고, 이에 따라 몇 개의 Frame을 프로세스에 할당하여 다중 프로그래밍을 구현할 것인지 정해야 한다.

  - 프로세스에 할당할 최소 Frame의 수는 Instruction Set Architecture에 의해서 결정되는데, 명령어가 실행 도중에 Page Fault 현상이 일어나게 되면 해당 명령이 다시 시작해야 되므로, 하나의 명령어가 참조할 수 있는 모든 페이지를 수용할 수 있는 충분한 Frame이 존재해야 한다.

  - 프로세스에 할당할 수 있는 최대 Frame 수는 할당 가능한 실제 메모리의 양으로 정의된다.

  - 최소 Frame 할당과 최대 Frame 할당 사이에서 적당한 Frame 할당을 해야 한다.

  - 이러한 Frame 할당 방법에는 Fixed Allocation과 Priority Allocation이 있다.


* Fixed Allocation

  - Equal Allocation  

      : 프로세스의 사이즈를 고려하지 않으며 Frame 수와 프로세스의 수를 가지고 할당

      : 100개의 Frame이 있고 5개의 Process가 있으면, 20개씩 할당한다.

  - Proportional Allocation

      : 프로세스의 사이즈를 고려하여 비례적으로 Frame을 나누어 할당


Proportional Allocation

* Priority Allocation

  -  Frame에 우선순위를 부여하며, Page Replacement가 일어날 때, 낮은 우선순위를 가진 Frame을 Victim으로 설정하여 대체한다.


* Global Allocation

  - 다중 프로그래밍 환경에서 여러 프로세스가 메모리에 상주할 때, 한 프로세스는 모든 Frame에 대해서 Replacement를 해줄 수 있다.

  - 다른 프로세스에 할당된 Frame을 가져올 수 있으며, 한 프로세스에 할당되는 Frame 수는 바뀔 수 있다.

  - 프로세스 실행 시간이 매우 다양하게 바뀔 수 있으며 Throughput이 좋아질 수 있다.

  - 어떤 Frame을 가져올지 모름으로 프로세스가 자신의 Page Fault Rate를 조절할 수 없다.


  * Local Allocation

  - 각각의 프로세스는 자신에게 할당된 Frame 안에서 Replacement를 한다.

  - 잘 사용되지 않는 Frame이 있다면 낭비의 문제가 있을 수 있다.


*Thrashing

  - Degree of multiprogramming을 높이기 위해서 프로세스마다 할당해줄 Frame을 줄일 수 있다.

  - 프로세스가 실제 사용하는 Frame 수 만큼 프레임을 갖지 못하게 되면 Page Fault가 계속해서 일어나게 되고, CPU Utilization은 프로세스의 page가 계속 교체돼서 I/O 작업이 계속 일어나게 돼서 줄어들게 된다.

  - 다중 프로그래밍의 정도를 높이기 위해 Frame의 개수를 줄이다가 CPU 활용도가 줄어들게 되는 현상을 Thrashing이라 한다.

  - 어떤 프로세스가 프로세스 수행에 보내는 시간보다 페이지 교환에 보내는 시간이 더 크면 Thrashing이라고 할 수 있다.

  - Thrashing을 해결하기 위해서는 프로세스에 필요한 만큼의 Frame을 할당하는 것이다.

  - Thrashing에 대한 대책으로 Working-Set Model이 사용된다.


* Working-Set Model

  - 가능한 한 최대의 다중 프로그래밍의 정도를 유지하면서 Thrashing을 막기 위해 사용한다.

  - Locality를 개념으로 만들어진 것으로, 프로세스가 많이 참조하는 Page들의 집합을 메모리 공간에 계속 상주하게 하여, 빈번한 Page Replacement를 줄이는 방법이다.

  - Locality

      : Locality는 집중적으로 사용되고 있는 Page의 집합이라 할 수 있다.

      : 실행 중인 프로세스는 Page 중에 일부를 선호하여 지역적인 부분만을 참조하게 되고 이를 Locality 라 한다.

      : 기본적인 Page는 중첩돼서 사용되며, 소수의 Page만 Replacement 되는 프로세스의 특성에 의해서 나온 개념이다.

      : Thrashing은 Locality에 사용되는 메모리보다 주어진 메모리가 작아서 발생하는 것으로 볼 수 있고, 이에 따라 충분한 Frame을 주어야 한다.

  - 프로세스의 Working-Set Model을 구성하기 위해, 작업설정의 크기를 알아야 하고, 이는 Working-Set Window를 이용한다.

  - Working-Set Window는 프로세스의 Locality에 근사한 값으로 정해지는 것이 좋으며, 특정 시점부터 과거에 참조한 페이지를 보고 미래를 예측하기 위해서 사용한다.

  - Working-Set Window가 크면 여러 개의 Locality를 1개의 Locality로 간주할 수 있다.

  - Working-Set Window가 작으면 1개의 Locality도 포함하지 못할 수 있다.

  - WSS를 프로세스의 Working-Set이라 할 때, 모든 프로세스의 WSS의 합을 D라 하며 전체 요구 Frame과 같다.

  - D가 할당 가능한 Frame의 수 m보다 크게 되면 Thrashing이 발생하게 된다.

  - D가 m보다 크면 프로세스 중 하나는 suspend 되며 이는 Medium-term scheduler가 해준다.

  - 프로세스가 수행되는 동안의 Working-Set은 계속해서 변화한다.

  - OS는 각 프로세스의 Working-Set을 감시하며 각 프로세스에 Working-Set 크기에 맞는 충분한 Frame을 할당하고, Frame이 남을 때는 다른 프로세스도 탑재시키며 다중 프로그래밍의 정도를 증가시키고, 이때 D가 m보다 크게 되면 잠시 중지시킬 프로세스를 선정해서 Page를 회수한다.


Working ets and Page Fault Rates

  - Working Set이 설정됨에 따라 초반에는 Page Fault Rate가 높은 것을 볼 수 있지만, 시간이 지나면 Locality에 의해서 Page Fault Rate가 줄어든 것을 볼 수 있다.


* Page Fault Frequency

  - Working-Set model은 Overhead가 많이 발생하여 이와는 다른 방식으로 사용하며 Working-Set model보다 직접적인 접근 방식이다.

  - Thrashing을 막기 위해서 Page Fault Rate를 사용한다.

  - 허용할 수 있는 Page Fault Rate 구간을 설정해서 높으면 Frame을 할당받아야 하고, 낮으면 Frame을 잃어도 되는 식으로 구현한다.

  - 프로세스가 새로운 지역성으로 이동하는 과도기에는 제대로 작동하지 않을 수 있는 문제가 있다.



728x90
반응형