Chapter 9. Memory Management Strategies

Outline

---

① Overview

② Background

③ Swapping

④ Contiguous Memory Allocation

⑤ Paging

⑥ Structure of the Page Table

⑦ Segmentation

 

① Overview

---

● 기법

1. Contiguous allocation

2. Paging

3. Segmentation

 

● 해야할 작업

1. address translation

2. memory protection

 

프로세스들의 address space의 합이 physical memory보다 클 수 있음

디스크 접근 시간 >> 메모리 접근시간

  -> 메모리 hit ratio 높여야 함

② Background

---

● Basic hardware

base 레지스터, limit 레지스터

-> 합법적인 logical address space 정의

-> 프로세스 바꿀 때마다 base, limit 레지스터 업데이트

 

MMU (Memory Management Unit)

virtual address를 physical address로 변환하는 hardware device

 

1. register

2. TLB (Translation Lookaside Buffer)

모든 logical address에 relocation register의 값을 더함

346 (logical) + 14000 (relocation) = 14346 (physical)

 

● Address Binding

프로그램을 디스크에서 메모리로 올릴 때, 메모리의 어느 위치로 이동시킬 것인가?

Binding 되는 시점

1. compile time

-> 시작주소 바뀌면 컴파일 다시 해야함

 

2. load time

-> 메모리에 다시 로딩되면 주소 바뀜

 

3. execution time

-> runtime binding

-> binding을 실행 시점까지 지연시킴

-> MMU 도움 필요

 

Compile, load time -> logical == physical

Execution time       -> logical != physical

 

● Logical Address

Logical Address

-> CPU에 의해 생성된 주소

 

Physical Address

-> 실제 메모리 주소

 

● Process address space

● Dynamic loading, linking, shared library

Dynamic loading

-> 각 루틴은 호출되기 전까지 load되지 않음

-> 코드 많지만 자주 호출 안되는 경우 효과적

-> OS 지원 필요없음, library에서 제공됨

 

Dynamic linking

-> Linking을 execution time 직전까지 지연시킴.

-> stub이라고 하는 코드에 어떻게 memory-resident library routine을 적절히 위치시킬 지에 대한 정보를 저장.

-> stub은 해당 라이브러리의 주소로 대체되어 해당 routine을 수행함.

-> linking하고자 하는 routine의 주소는 다른 address space에 저장되므로, 다른 프로세서의 메모리에 접근하기 위해서는 operating system의 도움이 필요함.

 

Shared library

-> 각각의 프로그램에 library를 포함시키지 않으므로 메모리를 효율적으로 사용 가능.

-> Library가 업데이트 될 경우 static library는 linking을 다시 해야 하는데 shared library는 library만 업데이트 하면 됨

 

③ Swapping

---

프로세스가 일시적으로 메모리 밖으로 나감.

계속 수행하기 위해 다시 메모리 안으로 들어옴

swap in, out 시간 오래 걸림

④ Contiguous Memory Allocation

---

프로세스를 연속적으로 할당

● 레지스터

1. Relocation registers

-> base address

 

2. Limit registers

-> process 크기

 

● 연산

1. Address translation

-> offset (logical address) + base address

 

2. Memory protection

-> logical address < limit register

 

● Dynamic storage allocation

1. First fit: 제일 첫 번째 남은 공간

2. Best fit: 제일 작은 남은 공간

3. Worst fit:제일 큰 남은 공간

 

● Fragmentation

1. External fragmentation

  -> contiguous allocation에서 주로 발생.

  -> ∑(홀 크기)는 프로세스 크기 보다 크지만, 각각의 홀 크기는 process 보다 작아서 process 할당 불가

  -> Compaction을 해서 빈 hole들을 합쳐서 process 크기 보다 큰 hole을 만들면 해결 가능.

 

2. Internal fragmentation

  -> paging에서 주로 발생.

  -> Process를 할당하고 남은 공간이 절대 사용되지 않음.

  -> 메모리 할당 단위 때문에 발생함. 

 

⑤ Paging

---

-> Process가 연속적일 필요가 없으므로(non-contiguous) 하나의 process가 분산되어서 저장될 수 있음. 

-> physical memory를 고정된 크기의 block 으로 나눔 (frame)

-> logical memory를 같은 크기의 block으로 나눔 (page)

-> frame 크기 == page 크기

-> 내부 단편화 (O), 외부 단편화 (X)

1. page num 찾기

-> logical address를 page size로 나누기

 

2. page table 탐색

-> frame num 찾기

 

3. physical address 계산

-> frame num + page size (시작 주소) + offset

 

● paging 기본 방법

page number

-> page table 인덱스

 

page offset

-> page 시작 지점에서 얼마나 떨어져 있는가?

 

ex. logical address space = 2^m, page size = 2^n 일 때

상위 m-n비트 -> page num

하위 n비트      -> offset

● page number 찾기

 

● Address translation

 

page size를 줄이면 내부 단편화 감소하지만

page table entry 관리하는 overhead 증가 (trade-off)

page size 보통 4KB 또는 8KB

 

● Frame table

-> 각 프레임 당 하나의 항목을 가짐

-> 해당 프레임이 할당됐는지 아닌지에 대한 정보 저장

 

● 하드웨어 지원

1. 레지스터

  1) PTBR (Page Table Base Register): page table의 위치 가리킴

  2) PTLR (Page Table Length Register): page table의 크기 저장

  -> 메모리 접근 두 번 해야함 (page table 찾기, 실제 데이터 접근)

 

2. TLB (Translation Look-aside Buffer)

  -> 레지스터에서 메모리 접근 두 번 해야하는 문제 해결

  -> page table의 일부를 저장 (캐시 역할)

  -> TLB에서 주소 찾으면 메모리 접근 안함, 못찾으면 메모리 접근 수행

 

※ ASID (Address-space Identifier)

  -> 프로세스마다 다른 페이지 테이블을 가지므로, 전역에 있는 TLB는 전체 프로세스에 대한 캐시를 다뤄야 함.

  -> 전역에 있는 TLB 는 테이블에는 단순히 페이지 넘버뿐 아니라, 프로세스 아이디도 가지고 있어야 함. (ASID)

  -> context switch 할 때 page table을 교체할 필요 없음

 

● Associative memory

-> parallel search

 

● TLB가 장착된 페이징 하드웨어

 

 

● Memory Protection

-> page table에 valid/invalid bit 추가

 

1. valid    : page가 process의 logical address space에 있고 유효한 상태

2. invalid : page가 process의 logical address space에 속하지 않음

 

valid bit이지만 process 영역이 아닐 수도 있으므로 PTLR 확인 필요

⑥ Structure of the Page Table

---

1. Hierarchical Paging

2. Hashed Page Tables

3. Inverted Page Tables

 

● Hierarchical paging

-> 32비트 논리 주소 공간에서 페이지 크기가 4KB (2^12)일 경우 페이지 테이블은 2^20개의 entry를 가진다.

-> 각 entry가 4B일 때 각 프로세스는 4MB (4 * 2^20)의 page table을 가진다. 따라서 page를 여러 개로 나눈다.

 

1) Two-level page table

논리 주소 공간을 3개로 나눈다.

일반 page table의 경우 32비트 논리 주소 공간을 20비트 page number와 12비트 offset으로 나누는데,

 

two-level page table은 상위 20비트를 다시 10비트씩 나눠서

상위 10비트는 첫번째 레벨 page table의 인덱스를,

하위 10비트는 두번째 레벨 page table의 인덱스를 가리킨다.

 

두번째 레벨 page table에서는 frame number를 가리킨다.

Page table이 두개이므로 메모리 공간이 더 필요할 것으로 보이지만,

대부분 invalid bit가 가리키고 있는 2-level page table은 메모리에 저장되지 않으므로 메모리 공간을 적게 사용한다.

두 개의 page table을 탐색해야 하므로 lookup time이 증가한다.

 

2) Three-level page table

논리 주소 공간을 4개로 나눈다.

64비트 논리 주소 공간의 경우, two-level page table을 사용하면

논리 주소 공간이 각각 42비트, 10비트, 12비트로 나눠진다.

상위 42비트는 여전히 크므로 이를 각각 32비트, 10비트로 나눈다.

결과적으로 64비트의 논리 주소 공간은 32비트, 10비트, 10비트, 12비트로 나눠진다.

Page table의 개수가 3개이므로 lookup time이 증가한다.

 

● Hashed Page Table

페이지 테이블을 사용하지 않고, 해쉬 태이블 사용

 

● Inverted page table

Page table을 frame number, page number, pid로 구성한다.

동일한 page number이지만 서로 다른 frame number에 할당될 수 있으므로 이를 구분하기 위해서 pid를 추가한다.

보통의 page table의 경우 각각의 프로세스가 별도의 page table을 가지고 있으므로

page table을 유지하는데 많은 메모리가 필요한데,

 

inverted page table은 system-wide하게 단 하나의 page table을 가진다.

Page table은 frame index로 정렬한다.

원하는 pid를 찾기 위해서 전체 테이블을 search해야하는 단점이 있다.

⑦ Segmentation

---

Contiguous allocation

-> 연속적으로 저장되는 단위 = 전체 프로세스

 

Segmentation

-> 연속적으로 저장되는 단위 = segment

 

프로그램을 segment 단위(function, stack, code 영역 등)로 나눈다. (Segment는 contiguous하게 저장함.)

프로그래머가 인지하는 메모리의 모습을 실제 물리 메모리의 모습으로 변환하는 메모리 기법

세그먼트의 길이는 다양하며, 각 세그먼트의 길이는 프로그램 목적에 따라 자동적으로 결정

 

 

1. Address translation

base                : segment의 시작지점

limit                : segment의 길이

logical address   : <segment num, offset>

physical address : base + offset

 

2. Memory protection

offset과 segment table의 limit을 비교.

offset이 limit보다 크면 protection 위배

 

Segment-table base register(STBR): segment table이 저장된 메모리 상의 주소 저장

Segment-table length register(STLR): segment table의 개수 저장