OS_10_2_Memory Management

1. Paging

1) paging

• physical memory를 frame이라고 부르는 고정 사이즈의 block으로 나누는 것이다. (size is power of 2, between 512 bytes and 8192 bytes)
  • logical memory를 같은 사이즈의 block(page)로 나누는 것이다.
  • 모든 free frame들을 추적해야 한다.
    • n pages 크기의 Program을 구동하기 위해서는 n free frame을 찾아야하고 program을 load해야한다.
• Page-to-frame mapping
  • OS와 HW는 page-to-fram mapping 정보를 유지해야한다.
  • 이것은 많은 relocation register들을 요구한다.
  • 그래서 Page table이 좋은 해결책이다.

2) Page Table and Address Translation

• 각 process의 page table은 main memory에서 유지되어야 한다.
  • Two register가 page table에 접근하기 위해 사용된다.
  • Page-table base register (PTBR)
    • page table의 시작 주소를 가리킨다.
    • page table의 위치를 찾는데 사용됨.
  • Page-table length register (PRLR)
    • page table의 크기를 나타낸다.
• CPU가 생성한 주소는 다음과 같이 나뉜다.
  • Page number (p) - page table의 index로 사용된다. 해당 page number는 physical memory의 각 frame의 base address를 포함하고 있다.
  • Page offset (d) - bass address와 결합되어 memory unit으로 전송되는 physical memory의 주소를 정의한다.

3) Logical Address and Page Table

• Logical address format
  • page number와 page offset의 길이가 page size에 따라 결정된다.
  • 예를들어 32-bit system에서 page size가 4 KB인 경우, page number는 20 bit고 page offset은 12 bit이다.

page table

p → 20 bit, d → 12 bit

• 즉, page table에서 p bit만큼 이동하여 f를 찾은 후, page offset과 결합하여 physical memory를 결정한다.

example

4) Two Memory Accesses

• 각 process의 page table은 main memory에 올라와 있다.
• 현대 시스템의 page table은 매우 크다.
  • One milion entries
  • fast registers를 사용하는 것이 불가능함.
• 모든 data/instruction 접근은 두번의 메모리 접근을 필요로 한다.
  • One for the page table and one for the data/instruction

5) Translation Look-Aside Buffer

• two memory access problem은 다음과 같은 방법으로 해결 가능
  • 특수하고 작은 hardware cache를 사용하여 해결 가능
    • ‘associative memory’ or ‘translation look-asside buffers (TLBs)
• TLB는 special and small hardware cache
  • Associative memory - parallel search
  • 만약 A’가 associative register 안에 있다면, 해당 주소의 frame number를 가져올 수 있다.
  • 그렇지 않은 경우, frame number를 메모리에 있는 page table에서 가져와야한다.

6) Effective Memory-Access Time

• Hit ratio : H
  • TLB에서 page number를 찾은 비율
• TLB search time : T
• Memory access time : M
• Effective Access Time
  • H(T+M) + (1-H)(T+M+M)
  • e.g.
    • H = 80%, T = 20 nanosec, M = 100 nanosec,
    • 0.8 (20+100) + 0.2 (20 + 100 + 100) = 140

7) Memory Protection

• Memory protection은 갹 프레임에 protection bit를 연관 시켜서 구현 될 수 있다.
• Valid-invalid bit는 각 page table에 첨부된다.
  • ‘valid’는 해당 페이지가 유효하며 메모리에 있다는 것을 나타낸다.
  • ‘invalid’는 해당 페이지가 유효하지 않거나 메모리에 없다는 것을 나타낸다.

page table은 각 process마다 정의가 된다.

8) Memory Sharing

• shared memory가 필요한 이유
  • Reentrant code(재진입 코드)는 process간에 공유 될 수 있다.
    • 재진입 코드란 여러 프로세스가 동시에 접근해도 안전하게 실행 될 수 있는 코드
    • ex) text editors, compilers, window systems
  • 두 개 이상의 프로세스가 같은 코드를 실행 할 수 있다.
• Page sharing for shared memory
  • physical memory에 shared page의 한 개 복사본만이 유지 된다.
  • share page의 entry는 여러 page table에 존재한다.

page table을 조작하여 process간의 memory sharing을 표현 가능

9) Page Table Structure

a) Hierarchical Paging

• 현대의 시스템은 매우 큰 Logical address space를 지원함. (2^32 to 2^64)

• Page table이 극도로 커지게 됨.

  • 만약 page size가 4KB(2^12)라면, page table은 100만개의 entry로 구성 될 수 있다. (2^20)
  • 만약 각 entry size가 4 Byte라면, page table 하나만으로도 4MB의 공간이 필요하다.
    • page table은 연속적인 메모리 공간을 필요로한다.
    • 우리는 이렇게 큰 page table을 하나의 page에 할당할 수 없다. 그래서 특별하고 연속된 메모리 영역을 유지하여야한다.
    • 64-bit machine인 경우 page table은 엄청나게 커질 수 있다.

• Hierarchical paging

  • page table을 여러 개의 작은 page table로 분할하여 사용하는 것.

• logical address (on 32-bit machine with 4 KB page size)는 해당처럼 나누어 진다:

  • page number 20 bits
  • page offset 12 bits

• page table이 page되어야 하기에, page number가 또 나누어 진다.

  • 10-bit page number
  • 10-bit page offset

• Address translation
  • Pi는 outer page table의 index를 나타내고, p2는 outer page table에서의 offset을 나타낸다.

example

b) Hashed Page Tables

• 32bit 이상의 주소 공간에서 일반적으로 사용됨.
• virtual page number는 page table에 hashing 된다.
  • page table은 같은 위치로 hasing되는 요소들의 chain을 포함하고 있다.
• virtual page number는 이 chain에서 일치 여부를 검사하기 위해 비교된다.
  • 만약 Match가 발견 된다면, 해당하는 물리적 프레임이 추출된다.

c) Inverted Page Tables

• 실제 메모리의 페이지마다 one entry를 가진다.
  • 오직 하나의 page table이 system에서 사용된다..
  • eg.) 64-bit UltraSPARC and PowerPC
• page의 각 항목이 실제 메모리 위치에 저장된 페이지의 가상 주소와, 해당 페이지를 소유한 프로세스에 대한 정보로 구성된다.
• 각 page table을 저장하는 데 필요한 메모리를 줄이지만, page reference가 발생할 때, table을 검색하는 데 필요한 시간을 증가시킨다.

2. Segmentation

1) Segmentation

• 사용자 관점에서 메모리를 지원하는 메모리 관리 체계
  • Segments는 의미론적으로 정의된 프로그램 부분
  • segment는 다음 중 하나를 포함한다.
    • code, data, stack, symbol table,…
• Protection and sharing
  • Memory는 segment 단위로 보호 된다.
    • 하드웨어 에서는 잘못된 메모리 참조가 발생하면 자동으로 검사 된다.
    • 또한, Segment는 두 개의 다른 프로세스의 segment table이 동일한 물리적 위치를 가리킴으로써 공유될 수 있다.

example

2) Segmentation Architecture

• Logical address는 two tuple로 구성된다.
  • <segment-number, offset>
• Segment table
  • segment table은 이러한 두 차원의 물리적 주소를 매핑한다.
• Each table entry has
  • base - segment가 메모리에 위치한 시작 물리적 주소를 가지고 있다.
  • limit - segment의 길이를 규정한다.

example

3) Segmentation with Paging - MULTICS

• MULTICS system은 external fragmentation과 lengthy search time을 segment를 paging함으로 써 해결했다.
• 해당 해결책은 순수 segmentation과 다른 점이 있다.
  • 세그먼트 테이블 엔트리는 세그먼트의 기점 주소(base address)가 아닌 이 세그먼트에 대한 페이지 테이블(page table)의 기점 주소를 포함합니다.
  • page segment를 단편화 시킴?

intel address translation, 하위호환 유지를 위해서 복잡해짐