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

Memory Management Strategies

 

[ Address Translation ]

  : Physical Address를 Virtual Address로 변화시키는 과정으로, Runtime에 이루어짐.

  : Memory 접근 시마다 이루어진다.

 

[ Memory Protection ]

  : 허가되지 않은 메모리 주소에 접근하는 것을 방지하는 데 사용.

  : 접근 시 Exception을 발생시킨다.

 

[ MMU(Memory Management Unit) ]

  : Physical Memory에서 Virtual Memory로의 변환에 도움을 주는 장치.

  · Register : 주소 변환에 필요한 연속적인 메모리의 시작 주소 또는 크기에 대한 값을 저장하기 위해 사용.

  · TLB(Translation Look-a-side Buffer) : Virtual Memory와 Physical Memory와의 매핑 정보를 저장하기 위해 사용.

 

[ Memory Management Strategies ]

  · Contiguous Allocation : Process를 연속된 Memory에 저장하는 방법.

    - Address Translation : Offset을 통해 시작 주소로부터 얼마나 떨어져있는지를 통해 가상 주소 변환.

    - Protection : Virtual Address와 Limit Register를 비교하는 방식으로 접근 가능한 메모리인지 판단.

    - MMU

       1) Relocation Register : Process의 Physical Memory의 시작 위치를 저장.

       2) Limit Register : Process의 Size를 저장.

    - Issue

       1) Allocation Issue : 어느 위치에 할당할지에 대한 이슈.

          ▶ First-Fit : 크기 조건이 맞는 가장 먼저 등장하는 Hole에 할당.

          ▶ Best-Fit : 크기가 가장 유사한 Hole에 할당.

          ▶ Worst-Fit : 크기가 가장 큰 Hole에 할당.

       2) External Fragmentation

           : Memory를 연속적으로 할당하기 때문에, 공간이 있음에도 연속되지 않아 할당하지 못하는 문제.

  · Paging : Physical Memory와 Virtual Memory를 고정된 크기의 블록으로 매핑시키는 방식.

                 → Page는 Page Number와 Page Offset을 연결한 Bit-Stream으로 이루어짐.

                 → Physical Address = Physical Frame Number * Page Size + Offset

                 → 32bit 주소에서 4KB의 크기를 가진 Page의 주소는 4KB = 4096Bytes = 2¹²Bytes이므로 Offset : 12bits, Number : 20bits가 된다.

    - Address Translation : Page Table을 이용해 주소 변환.

    - Protection : Page Table의 Valid / Invalid Bit를 확인하거나 PTLR, PTBR을 확인해 적절한 위치를 참조하는지 판단.

    - MMU

       1) TLB

           : Page Table을 TLB에 저장하고 가져다 씀.

           : TLB Hit율이 높아야 효율성 증가. 보통 99% 이상이 되도록 설계.

           ◆ Analysis

              1) TLB 탐색 : ε시간, 확률 α.

              2) Page Table Look-up : Hit하지 않은 경우 테이블 검색. 1 microsecond.

              3) Hit한 경우 1 microsecond.

              → Effective Access Time : α(1 + ε) + (1 - α)(2 + ε) = 2 + ε - α. TLB가 없다면 항상 2이므로 Hit하지 못해도 효율적.

       2) PTBR(Page Table Base Register)  : Page Table의 시작 위치를 저장한 Register.

       3) PTLR(Page Table Length Register) : Page Table의 크기를 저장한 Register.

    - Issue : Page Table Size를 적절하게 지정하는 것이 가장 큰 이슈. (Inner Fragmentation도 있지만 큰 이슈가 아님)

       1) Hierarchical Page Table

           : 하나의 페이지 안에 여러 개의 페이지 테이블을 넣은 계층적 페이지 테이블을 의미한다.

           : Two-Level Page Table과 같은 경우 P1은 Outer Table의 Index, P2는 Inner Table의 Index를 표시한다.

           : 사용하지 않는 Table 정보는 보관하지 않음으로써 메모리를 절약.

           : 두 번 Look-up 해야 하는 문제가 있지만 TLB로 이 부분을 해소시킬 수 있다.

Two-level Page Table

       2) Hashed Page Table

           : Page Table을 Hash Table로 구성하는 방법으로, Table의 크기에 상관 없이 상수시간에 찾을 수 있다는 장점을 가짐.

           : Hash Table은 Collison 문제를 가지고 있어 Algorithm이 필요하게 되는데, 이 알고리즘을 적용함에 있어 효율성이 떨어진다.

       3) Inverted Page Table

           : Frame - Page 매핑 관계를 Page - Frame 매핑 관계로 전환하여 하나의 테이블만 보관하도록 함.

           : 테이블 전체를 탐색해야한다는 단점이 있어 실제로는 사용되지 않는다.

  · Segmentation : Paging과 유사하나, 논리적 단위인 Segment를 사용하고 가변적인 길이를 할당할 수 있다.

    - Address Translation : Segment Table을 이용해 주소 변환.

    - Protection : Table의 Permission을 확인하거나 STBR, STLR을 확인해 적절한 위치를 참조하는지 판단. 

    - MMU 

       1) TLB : Segment Table 정보를 TLB에 저장하여 가져다 씀.

       2) STBR(Segment Table Base Register) : Segment Table의 시작 주소를 저장.

       3) STLR(Segment Table Length Register) : Segment Table의 크기를 저장.

    - Issue : 길이를 가변적으로 사용하므로 External Fragmentation이 발생.