[운영체제] 8. Memory Management (2)

kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다.

1. Noncontiguous allocation

1) Paging

• Paging
  • Process의 virtual memory(logical memory)를 동일한 사이즈의 page로 나눔
  • Virtual memory의 내용이 page 단위로 noncontigous하게 저장됨
  • 일부는 backing store(hdd, ssd)에, 일부는 physical memory에 저장 -> swapping
• Basic method
  • Physical memory를 동일한 크기의 frame으로 나눔
  • Logical memory를 동일 크기의 page로 나눔(frame과 같은 크기)
  • 모든 가용 frame들을 관리 (프레임들이 사용 중인지, 아닌지 관리)
  • Page table을 사용하며 logical address를 physical address로 변환
  • External fragmentation 발생 안함 (frame와 page가 같은 크기이므로)
  • Internal fragmentation 발생 가능 (제일 마지막 조각 하나 정도 발생 가능함)

 Address Translation Scheme

CPU는 다음 두 가지로 구성된 virtual address를 사용

- Page number (p): page table의 index, 해당 index에는 그 페이지의 물리적 정보 상의 base address가 저장됨

- Page offset (d): base address와 더해져서 physical address가 구해짐 

 

 

• Implementation of Page Table
  • Page table은 main memory에 상주함
  • Page-table base register (PTBR)가 page table을 가리킴
  • Page-table length register (PTLR)가 테이블 크기를 보관
  • 모든 메모리 접근 연산에는 2번의 memory access가 필요 -> page table 접근 + 실제 data/instruction 접근
  • 속도향상을 위해 associative register 혹은 translation look-aside buffer(TLB)라 불리는 고속의 lookup hardware cache 사용
• Associative Register
  • Associative registers (TLB): parallel search가 가능. TLB에는 page table의 일부만 존재함
  • Address translation
    • page table 중 일부가 associative register에 보관되어 있음
    • TLB hit: 만약 해당 page #가 associative register에 있는 경우 곧바로 frame #를 얻음
    • TLB loss: 그렇지 않은 경우 main memory에 있는 page table로부터 frame #를 얻음
    • TLB는 context switch 때 flush (remove old entries)

 

 

Effective Access Time

- Associative register lookup time = a

- memory cycle time = 1

- Hit ratio = b

EAT = <hit> + <miss> = b*(1+a) + (1-b)*(2+a) = 2+a-b

<hit>의 경우 TLB lookup 시간 a와 실제 data/instruction 접근 시간 1 소요

<miss>의 경우 TLB lookup 시간 a와 page table 접근 시간 1, 실제 data/instruction 접근 시간 1 소요

Two-Level Page Table

기존 Paging 방식의 Problem

32bit address 사용시 2^32 B = 4GB 의 주소 공간 (2^10 -> K, 2^20 -> M, 2^30 -> G)

Page entry가 4K 시 1M개의 page table entry 필요. (12bit로 offset 표현)

32bit 주소 체계를 사용하므로 각 page entry가 4B(32bit). 프로세스 당 4MB(4B*1M)의 page table 필요. (2^20 * 2^2)  

그러나 대부분의 프로그램은 4G의 주소 공간 중 지극히 일부분만 사용하므로 page table 공간이 심하게 낭비됨. (index로 page table에 접근하기 때문에 안쓰는 주소공간이라고 빼먹을 수 없음)

 

-> page table 자체를 page로 구성

-> 사용되지 않는 주소 공간에 대한 outer page table의 엔트리 값은 NULL (대응되는 inner page table이 없음)

 

 

Two-level paging example

- logical address (on 32-bit machine with 4K page size)의 구성

4K = 2^12. 12 bit -> page offset

32 - 12 = 20 bit -> page number

- page table 자체가 page로 구성되기 때문에 page number는 다음과 같이 나뉜다. (각 page table entry가 4B)

page size 4K, entry 크기 4B -> 4B*1K = 4K 이므로 entry가 1K개 존재 가능. 2^10, 10 bit로 inner page table offset 표현 가능

10 bit -> page number

10 bit -> page offset 

 

2단계 페이징

 

Multilevel Paging and Performance

• Address space가 더 커지면 다단계 페이지 테이블 필요
• 각 단계의 페이지 테이블이 메모리에 존재하므로 logical address의 physical address 변환에 더 많은 메모리 접근 필요
• 캐쉬 메모리를 통해 메모리 접근 시간을 줄일 수 있음
• 4단계 페이지 테이블을 사용하는 경우
  • 메모리 접근시간 100ns, 캐쉬 메모리 접근 시간 20ns, 캐쉬 hit ratio 98%
    • effective memory access time = 0.98*(100+20) + 0.02*(100*5+20) = 128ns
    • cache miss 인 경우, 페이지 테이블 접근 4번, 실제 data/instruction 접근 1번으로 총 5번의 메모리 접근이 요구됨

Memory Protection

page table의 각 entry 마다 아래의 bit를 둔다.

• Protection bit
  • page에 대한 접근 권한 (read/write/read-only)
  • 일반적으로 read/write - data, stack, read-only - code
• Valid-invalid bit
  • valid는 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있음을 뜻함 (접근 허용)
  • invalid는 해당 주소의 frame에 유효한 내용이 없음을 뜻함 (접근 불허)
  • invalid - 프로세스가 그 주소부분을 사용하지 않는 경우, 해당 페이지가 메모리에 올라와 있지 않고 swap area에 있는 경우

 

 

Inverted Page Table

• Page table이 매우 큰 이유
  • 모든 process 별로 그 logical address에 대응하는 모든 page에 대해 page table entry가 존재
  • 대응하는 page가 메모리에 있든 아니든 간에 page table에는 entry로 존재
• Inverted page table
  • Page frame 하나 당 page table에 하나의 entry를 둔 것 (system-wide)
  • 각 page table entry는 각각이 물리적 메모리의 page frame이 담고 있는 내용 표시 (process-id, process의 logical address). page table과 physical memory가 1:1 대응됨.
  • 단점
    • 테이블 전체를 탐색해야 함 -> assosicative register(TLB) 사용(expensive..), parallel search

 

Inverted page table architecture

 

Shared Page

• Shared code
  • Re-entrant code (=pure code)
  • read-only로 하여 프로세스 간에 하나의 code만 메모리에 올림 (eg. text editors, compilers, window systems)
  • Shared code는 모든 프로세스의 logical address space에서 동일한 위치에 있어야 함
• Private code and data
  • 각 프로세스들은 독자적으로 메모리에 올림
  • Private data는 logical address space의 아무 곳에 와도 무방

 

Shared pages

2) Segmentation

프로그램은 의미 단위인 여러 개의 segment로 구성

• 적게는 프로그램을 구성하는 함수 하나하나를 세그먼트로 정의
• 크게는 프로그램 전체를 하나의 세그먼트로 정의 가능
• 일반적으로는 code, data, stack 부분이 하나씩의 세그먼트로 정의됨
•  segment는 다음과 같은 logical unit들
  • main(), function, global variables, stack, symbol table, arrays

Segmentation Architecture

Logical address는 다음의 두 가지로 구성. <segment number, offset>

• Segment table
  • base - starting physical address of the segment
  • limit - length of the segment
• Segment-table base register (STBR) - 물리적 메모리에서 segment table의 위치
• Segment-table length register (STLR) - 프로그램이 사용하는 segment의 수. segment number s < STLR 이어야 유효함.
• Protection
  • 각 세그먼트 별로 protection bit가 있음
    • valid bit = 0 -> illegal segment
    • read/wrtie/execution 권한 bit
• Sharing
  • shared segment
  • same segment number
• Allocation
  • first fit / best fit
  • external fragmentation 발생 
  • segment의 길이가 동일하지 않기 때문에 가변 분할 방식에서와 동일한 문제점들이 발생

※ Paging과의 차이점

page는 길이가 모두 같았지만(offset 크기가 결정이 됨) segment는 다르기 때문에 segment 크기에 따른 offset 크기 결정이 필요함.

frame 역시 같은 크기로 나뉘어져 있어 몇 번 frame으로 가라는 매칭이 가능했지만 segmentation은 정확한 byte 단위 주소로 알려줘야 함.

segment는 의미 단위이기 때문에 공유와 보안에 있어 paging보다 훨씬 효과적임.

 

3) Segmentationwith Paging

pure segmentation 과의 차이점: segment-table entry가 segment의 base address를 가지고 있는 것이 아니라 segment를 구성하는 page table의 base address를 가지고 있음

장점) segmentation 내부를 page로 나누면 fragmentation 문제를 줄일 수 있다.

단점) logic이 복잡해서 버그 가능성이 증가한다.