운영체제 4차 정리 - Memory Management (2)

 호야의 블로그 

[OS] 운영체제 4차 정리

저번 메모리 관리 정리에 이어 이번에 메모리 관리 마무리 정리를 하도록 하겠습니다.

Memory Management (2)

Non-Contiguous Allocation

* Page

  - 물리적 주소공간을 고정된 사이즈의 Block으로 나눈 것을 Frame이라 한다.

  - 논리적 주소공간을 고정된 사이즈의 Block으로 나눈 것을 Page라 한다.

  - 1개의 프로그램을 실행시키기 위한 n개의 Page는 n개의 Frame이 필요하다.

  - 논리적 주소공간을 물리적 주소공간으로 번역하기 위해 Page Table이 필요하다.

  - External Fragmentation을 없앨 수 있으며, 프로세스에 할당되는 주소공간이 연속적일 필요가 없다.

  - Internal Fragmentation이 생기는데, 1byte를 위해서 Page가 할당되는 것이 Worst case이다.

  - Logical Address는 연속적이며, Page Table을 통하여 Physical Address는 연속적이지 않아도 된다.

  - Logical Address Space와 Page size에 따라 Page Table entire entry가 결정되고 결정하는 방법은 단순히 나누는 것으로 결정할 수 있다. 이때 Page Size는 그대로 Offset으로 Frame에서 정확한 메모리를 접근할 때 사용된다.

  - Page number(p)를 Page table entry number이고 Page offset(d)은 Page size보다 작은 값을 가지게 된다.

  - Page Table은 연속된 주소공간이며 Logical address의 번역을 위해 사용된다.

  - Logical Address는 Page number와 Page offset으로 구성되며, Page number에 해당하는 Page Table에는 Frame number가 있고, 해당 Frame의 Page offset에 해당하는 메모리 주소가 Logical address에서 번역된 Physical address이다.

  - Page size는 2^n byte를 사용한다.

  - Process는 Logical address만 보기 때문에 연속된 address를 사용하는 것으로 느끼지만, 실제 Physical memory는 분할되어 있고 이를 관리하는 게 메모리 관리이다.

  - Page Table Base Register(PTBR)는 Page Table의 시작주소 레지스터이다.

  - Page Table Limit Register(PTLR)는 Page Table의 Size를 가지는 레지스터이다.

  - Page Table은 Logical address를 가지므로 프로세스당 1개씩 존재한다.

  - Free Frame List는 System에 1개 존재한다.

  - Page Table을 사용한다는 것은 Execution Time Binding의 Dynamic Binding을 하는 것으로 MMU가 사용이 되는 것이다.

  - Page Table의 size가 커서 RAM에 저장되며, 실제 MMU에는 Associative memory인 Translation Look-Aside Buffer(TLB cache)가 있다.

  - TLB cache에는 Address-Space Identifiers(ASIDs)가 있는데, 이는 Process에 속한 Page Table의 id를 의미하며 프로세스마다 따로 사용이 되어야 하기 때문에 프로세스를 구분하고 주소공간을 보호하기 위해 사용한다.

  - ASID를 사용하지 않으면 TLB를 사용할 때마다 Flush를 해야 해서 메모리 접근이 더 필요하므로 좋지 않다.

  - TLB cache는 64 ~ 1,024개의 entry를 가지며 작은 용량을 차지한다.

  - TLB cache 안에 정보 비교할 수 있는 것이 들어 있어서 매칭을 보고 있으면 "TLB hit"가 돼서 바로 Physical address로 찾아갈 수 있고, 없으면 "TLB miss"가 돼서 Page Table에서 값을 찾아서 TLB에 위치시키며 주소를 찾아가게 된다.

  - TLB hit이면 Page Table을 찾아가지 않기 때문에 메모리 접근 시간이 한번 난 것과 비슷하게 보인다.

  - TLB는 RAM이 아닌 Associative memory이므로 address line decoding이 필요하지 않다.

  - TLB가 꽉 찼을 경우 다른 것으로 대체할 수 있는 Replacement 정책을 잘 고려해야 한다.

  - TLB에서 계속 사용하게 되는 주소는 묶어놓을 수 있다.

* Paging Hardware with TLB

  - Effective Access Time(EAT)

      : a는 Hit Ratio, e는 TLB 접근 시간을 의미한다.

      : 위 식은 hit 할 때 메모리 접근 1번에 TLB 접근 시간과 miss일 때 Physical memory, Page Table memory 접근 2번에 TLB 접근 시간을 의미한다.

      : a = 80%, e = 20ns, 메모리 엑세스에 100ns가 주어지면 EAT = 0.8*120 + 0.2*220 = 140ns

      : a = 98%, e= 20ns 메모리 접근 140ns가 주어지면 EAT = 0.98*160+0.02*300 = 162.8ns

  - Memory Protection

      : Page Table은 연속적인 메모리 공간으로 각 프로세스마다 다르고, 다른 프로세스가 참조하지 못하도록 Protection이 필요하다.

      : Valid-Invalid bit는 Page가 Read only 또는 Read/Write 별로 정의되어 있는 것을 구분시켜주는 것으로 만약 읽기 전용에 Frame에 쓰기를 시도한다면 OS가 Trap으로 프로세스를 죽이게 된다.

      : 보호를 위해 PTLR을 사용해서 illegal address를 참조하지 않도록 하는 방법도 있다.

* Shared Page

  - Page 단위로 공유를 할 수 있으며 Read Only Page의 reentrant code가 공유되면 좋다.

  - Multi Thread의 메모리 공유와 비슷하게 Stack을 제외한 것을 공유할 수 있다.

  - 단순히 메모리 공유로 IPC를 할 수 있는 것이 장점이다.

  - 공유되는 Page는 같은 Frame을 공유해야 하므로 이를 번역하는 Page Table에서 혼동되면 안 되기 때문에 아무 데나 존재하면 안 된다.

  - Private Code, Data는 공유되는 것이 아니므로 아무 곳에나 존재해도 된다.

Shared page

* Page Table Structure

  - Page Table의 크기가 크고 연속적으로 메모리를 차지하고 있으므로 Page Table의 구조에 대해 생각을 해볼 수 있었고, Hierarchical Paging, Hashed Paging, Inverted Paging이 있다.

  - Hierarchical Paging

      : Page Table을 계층 구조로 만든다.

      : Page Table을 Paging 한다.

      : Logical Address는 Page table 개수만큼의 number와 offset으로 구성된다.

* Two-Level Page-Table Scheme

      : Page size가 4KB이고 1 word가 32bit일 때, Logical Address는 10/10/12로 나타낼 수 있으며,

Page table entry당 4byte일 경우 Original Page Table은 4MB이고 Two-Level Paging을 하고 Inner Page Table Entry를 1K로 둔다면, Outer Page Table Entry는 1K 개수가 되고, Inner Page Table 4KB가 1K 개가 있어서 4MB를 만족하고, Outer Page Table을 위한 4KB가 추가로 필요하게 된다.

      : 이렇게 Logical address를 차례로 찾아가기 때문에 Forward-mapped Page Table이라고도 한다.

      : Hierarchical Paging의 Level이 많아질수록 메모리 접근 시간이 증가하기 때문에 좋지 않다.

  - Hashed Page Table

      : Page Table entry가 32bit보다 더 큰 수로 표현돼야 할 겨우 이 방법을 고려한다.

      : Hierarchical Paging을 해도 Outer Page entry 수가 너무 많아서 Page entry 자체를 줄일 수 있는 Hash function을 사용하여 Table 구조를 만들었다.

      : Original Page Table은 찾는 시간은 걸리지 않아서 O(1)의 Time Complexity를 가졌고, Direct Method로 Hashing 한다면 Original Page Table과 같이 O(1)의 Time Complexity를 가진다.

      : Hashing 되어 같은 Key 값을 가지게 되는 것을 Synonym이라 하며, 같은 주소를 참조하는 Key가 여러 개 있다면 이는 Collision이 발생했다고 하고, Collision resolution으로는 Chaining을 사용한다.

      : Chaining을 함에 따라 Linked list의 size에 따라 Time Complexity는 O(1) ~ O(n)를 가지게 된다.

* Hashed Page Table

  - Inverted Page Table

      : Page Table 하나하나의 사이즈 자체가 너무 커서 모든 프로세스가 하나의 Page Table을 공유하는 방법을 생각했다.

      : Page Table을 저장하기 위한 메모리는 줄지만, Table을 찾는 데에 PID를 사용하여 시간이 더 걸리게 된다.

      : 메모리의 실제 Frame마다 하나의 Entry를 가진다.

Non-Contiguous Allocation

* Segmentation

  - 기억장치의 사용자 관점을 지원하는 메모리 관리 기법

  - Logical Address Space는 main program, procedure, function, local variable, global variable, common block, stack, symbol table, arrays로 구성되어 있으며 각각은 segment에 해당한다.

  - 각 Segment는 연관된 기능을 수행하는 하나의 모듈 프로그램으로 생각한다.

  - 각 Segment의 크기가 다르므로 Multiple Partition으로 메모리를 할당하며 이에 따라 External Fragmentation이 발생할 수 있다. (6/28 수정)

  - Logical Address는 Segment number(s)와 offset(d)으로 구성되며 Segment Table은 각 Segment의 Limit와 Base를 가지고 있다.

  - Segment Table Base Register(STBR)는 Segment Table의 시작 주소를 나타내며, Logical address의 segment number(s)와 합쳐져서 Segment Table의 실제 주소를 참조할 수 있다.

  - Segment Table Limit Register(STLR)는 Segment Table의 전체 size를 나타내며, Logical address의 segment number(s)와 비교하여 s가 작아야 legal address를 참조하는 것으로 판단할 수 있고 이는 프로그램에 사용되는 세그먼트 수를 지적하는 것과 같다.

* Segmentation Hardware

  - Segmentation은 Multiple Partition(Variable Size Partition)을 사용하고 이 중에서 First-fit, Best-fit을 사용한다.

  - Relocation Address를 사용하고 Dynamic Execution Binding을 한다.

  - Segment Sharing은 Sharing의 기본 단위가 segment이므로 Segment Table에서 같은 메모리를 참조하도록 limit과 Base로 주소를 정해주면 공유된다.

  - Page와 비슷하게 Protection은 Valid-Invalid bit로 가능하며 Read/Write/Execute에 대한 정보를 가지고 있다.

  - Variable Size Partition은 Execution Time Binding이 아니어도 되지만 Segmentation에서는 Execution Time Binding이어야 한다.

후기 및 정리

운영체제 메모리 관리 정리를 마무리 하겠습니다. 다음 글에서는 가상 메모리에 관한 글을 올리겠습니다.

OS 8번째 글: 2018/10/30 - [IT/OS] - [OS] 운영체제 5차 정리 - Virtual Memory

OS 7번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 3차 정리 - Memory Management (2)

OS 6번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 3차 정리 - Memory Management (1)

OS 5번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 2차 정리 - 데드락(Deadlock)

OS 4번째 글: 2018/10/26 - [IT/OS] - [OS] 운영체제 1차 정리 - Scheduling

OS 3번째 글: 2018/10/24 - [IT/OS] - [OS] CPU 스케줄러

OS 2번째 글: 2018/10/24 - [IT/OS] - [OS] 진짜 간단히 정리한 프로세스 개념

OS 1번째 글: 2018/10/18 - [IT/OS] - [OS] 운영체제에 대해서

조금의 도움이 되셨다면 로그인 없이도 가능한 댓글과

왼쪽 아래 ♥공감 버튼을 꾹 눌러주세요!