[오퍼레이팅 시스템] Virtual Memory Management

Virtual Memory Management

 

[ Demand Paging ]

  : Page가 필요할 때만 실제 Memory에 적재하는 방식. (Lazy Swapper와 함께 사용)

  : Page Fault가 발생하였을 때 필요한 Page를 Physical Memory에 적재.

     → 해당 Page에 대응하는 Frame을 Page에 할당.

  : I/O 양을 줄일 수 있고, Physical Memory의 사용량을 감소.

  : 응답 시간이 빨라짐.

 

  · Valid / Invalid Bits

    : Memory에 Page가 올라와있지 않는 경우 Invalid, 올라와있는 경우 Valid Bit로 선택.

    : 처음에는 모든 Entry가 Invalid로 초기화되어있음.

    : Address Translation 시에 Invalid Bit가 Set 되어있다면 Page Fault 발생.

  · Page Fault 처리

     1) Reference 영역을 확인해 Invalid Reference인 경우 Process를 Abort 시킨다.

     2) Empty Frame을 받는다.

     3) Frame을 Page에 할당.

     4) Table을 업데이트한다.

     5) Invalid Bit를 Valid Bit로 바꾼다.

     6) 명령을 재수행한다.

  · Demand Paging의 효율 → Page Fault의 빈도수에 따라 달라짐.

    

[ Page Replacement ]

  : Page Fault를 최소화하기 위해 Victim Frame을 선택하는 과정.

 

  · LRU(Least Recently Used) Algorithm

    : 최근에 가장 적게 사용된 Frame을 Victim으로 선택하는 방법.

    : Page Table에 논리적 시간인 Counter를 붙여 사용하거나 Stack을 사용해 가장 적게 사용된 Frame을 찾는다.

       ( 이때 사용되는 Stack은 실제 Stack 자료구조를 사용하는 것이 아니며, 쌓아 올린다는 의미의 Stack이고 LIFO를 따르지 않는다. )

    : 어떤 주소를 참조했을 때 그 주소가 다시 참조될 확률이 높다는 Temporal Locality를 활용한 알고리즘.

  · LRU-approximation Algorithm

    : LRU와 유사하면서 Overhead를 줄인 Algorithm.

    : Hardware의 도움을 받아 Reference Bit와 Modify Bit를 Page마다 추가.

       → Reference Bit : 참조할 때마다 변경되는 Bit.

       → Modify Bit : 수정할 때마다 변경되는 Bit.

       → 해당 Bit를 추가함으로써 Page 전체를 검색하지 않고도 비교적 최근에 사용되지 않거나 변경되지 않은 페이지를 선택할 수 있도록 함.

            ( 페이지 전체 탐색을 완전히 방지하는 것은 아님 )

      ◆ Solution Algorithm

            1) Additional-reference-bits Algorithm

                : Reference Bit를 여러 비트로 늘리고, 시간이 지날수록 Right Shift를 하며 참조된 경우 가장 왼쪽 Bit를 1로 바꾸는 방식.

                : 해당 Bit-Stream끼리 비교하여 Victim을 지정.

Additional-reference-bits Algorithm

            2) Second Chance Algorithm (Clock Algorithm)

                : Bit를 늘리지 않고 LRU-approximation을 구성하려 노력한 알고리즘.

                : Clock-Hand라는 포인터를 가지고 Victim에 멈춰있는 상태. → 처음 만난 Reference Bit가 0인 Page.

                : Reference Bit가 1인 것은 0으로 전환하고 넘어가고, 0인 것은 Victim으로 삼음.

                : Reference Bit가 1인 것을 한 번 넘어간다고 하여 Second Chance.

            3) Enhanced Second Chance Algorithm

                : Reference Bit와 Modify Bit를 쌍으로 두고 이에 따른 Class를 나누어 Victim을 선택.

                  ▶ Class 1 : (0, 0) 최근에 참조되지도, 변경되지도 않은 경우로, 교체하기 가장 좋은 Page.

                  ▶ Class 2 : (0, 1) 최근에 참조되지는 않았지만 변경된 경우로, Disk에 저장해야 하기 때문에 교체에 적당하지 않은 Page.

                  ▶ Class 3 : (1, 0) 최근에 변경되지는 않았지만 참조된 경우로, 다시 사용될 확률이 높은 Page.

                  ▶ Class 4 : (1, 1) 최근에 참조되었고 변경도 된 경우로, 다시 사용될 가능성이 높으며 교체하려면 Disk에 기록이 필요한 Page.

  · Counter-Based Algorithm

    - LFU(Least Frequently Used) : 참조 횟수가 가장 작은 Page를 교체하는 Algorithm.

    - MFU(Most Frequently Used) : 참조 횟수가 가장 많은 Page를 교체하는 Algorithm.

 

[ Thrashing ]

  : Page Fault가 지속적으로 발생해 I/O만 기다리고 수행을 할 수 없는 상태.

  : 총 Memory를 늘리거나 Process를 줄이는 방법으로 해결.

Thrashing

  · Working-Set Model

    : Temporal Locality에 의거해 최근에 참조한 Page를 중심으로 Working Set을 형성하여 Memory와 Process를 조절.

    : Thrashing이 발생하지 않도록 Σ (locality size) ≤ (Total Physical Memory)가 되도록 조절.

    : Process마다 Working Set과 Number of Working Set를 설정하여 이를 조절.

 

[ Allocating Kernel Memory ]

  : Kernel은 Memory Access를 효율적으로 하기 위해 Contiguous한 Memory 할당을 선호해 별도의 방법 사용.

  · Buddy System

    : 2의 지수승으로 Page를 할당하는 방식이며, Contiguous하게 할당한다.

    : 연산으로 병합(Coalescing)과 분할(Splitting)을 사용한다.

    : 고정된 크기의 Buddy를 할당하므로 Internal Fragmentation이 발생할 수 있다.

  · Slab Allocator

    : Data Structure에 따른 다양한 크기의 Slab 객체를 미리 생성해 요청이 있을 때 바로 할당하는 형태로 이루어짐.

    : 크기가 다양하므로 Internal Fragmentation을 줄일 수 있고, 할당 속도가 매우 빠름.

       ◆ Slab States

            1) Full : Slab이 모두 할당되어 새로운 객체를 할당할 수 없는 상태.

            2) Partial : Slab의 일부만 할당된 상태. 새로운 객체를 할당할 수 있는 상태.

            3) Empty : Slab이 하나도 할당되어 있지 않은 상태.

Slab States