[운영체제] 8. Memory Management

Logical vs Physical Address

1) Logical Address(virtual address)

- 프로세스마다 독립적으로 가지는 가상의 주소 공간 (CPU가 보는 주소)

- 각 프로세스마다 0번지부터 시작

 

2) Physical Address

- 메모리에 실제 올라가는 위치

 

* 주소 바인딩

- 특정 시스템의 Logical Addr를 Physical Addr로 매핑하는 것

(Symbolic addr(변수/함수로 호출) -> Logical addr -> Physical addr)

 

주소 바인딩(Address binding)

주소 변환이 이루어지는 시기에 따라 분류

1) Compile time binding

- 컴파일 시 주소 변환(Logical addr을 그대로 사용) -> 비효율적이기 때문에 요즘은 사용하지 않음

- 절대 코드 : 메모리에 올라갈 위치를 바꾸고 싶으면 컴파일 다시 해야 함

2) Load time binding

- 실행 시작 시 주소 변환

- 재배치 가능 코드

3) Execution time binding(Runtime binding)

- 프로그램 시작 중에도 주소 변환 가능

- 재배치 가능 코드

- CPU가 주소를 참조할 때마다 binding을 점검해야 함 -> HW적인 지원이 필요

 

MMU(Memory-Management Unit)

2개의 register를 이용해 logical addr -> physical addr로 주소 변환을 제공하는 하드웨어 유닛

1) relocation register(base register) : 접근할 수 있는 물리적 메모리 주소의 최솟값

-> (base register + 시작 위치)를 통해 실제 physical memory의 주소 제공

2) limit register : 악성 프로그램의 공격을 막기 위해 논리적 주소의 범위를 체크

 

Terminologies

1) Dynamic Loading

프로세스의 루틴이 호출될 때에 메모리에 load하는 것

- 가끔씩 사용되는 많은 양의 코드의 경우 유용(오류 처리 루틴)

- memory utilization의 향상

- 운영체제의 특별한 지원 없이 개발자가 프로그램 자체에서 구현 가능(OS는 라이브러리를 통해 구현 가능)

cf) 운영체제의 paging 기법

 

2) Dynamic Linking

Linking을 실행 시간execution time까지 미루는 기법

- Static LInking : 라이브러리가 프로그램의 실행 파일 코드에 포함됨

- Dynamic Linking : 라이브러리 호출 시 stub을 통해 Link함 (shared-ilbrary/dml 파일)

 

3) Overlays(manual overlay)

메모리에 프로세스의 부분 중 실제 필요한 정보만을 올리는 것

- 프로세스의 크기가 메모리보다 클 때 유용

- 운영체제의 특별한 지원 없이 개발자가 프로그래머 자체에서 구현(초창기 -> 복잡하다)

 

4) Swapping

- Swapping : 프로세스를 일시적으로 메모리에서 backing store로 쫓아내는 것

- Backing store(swap area) : 디스크

- Swap In/Swap out : 중기 스케줄러 swapper에 의해 선정

--- priority-based CPU scheduiing algorithm

--- execition time binding이 지원되면 더 효율적으로 사용 가능

--- swap time은 대부분 transfer time에 비례(swap되는 양에 비례하는 시간)

 

Allocation of Physical Memory

* 메모리 영역의 구분

1) OS 상주 영역 : 낮은 주소 영역

2) 사용자 프로세스 영역 : 높은 주소 영역

 

* 사용자 프로세스 영역의 할당 방법

1) Contiguous allocation : 각각의 프로세스가 메모리의 연속적인 공간에 적재되도록 하는 것

- Fixed partition allocation(고정 분할 방식)

- Variable partition allocation(가변 분할 방식)

2) Noncontiguous allocation : 하나의 프로세스가 메모리의 여러 영역에 분산되어 올라갈 수 있음

- Paging

- Segmentation

- Paged segmentation

 

1. Contiguous Allocation 

- Fixed partition allocation(고정 분할 방식) : internal/external fragmentation 발생

- Variable partition allocation(가변 분할 방식) : external framentation 발생

 

- external fragment (프로그램 크기 > 분할의 크기) : 프로그램이 올라갈 수 없는 작은 분할 통째

- internal fragment (프로그램 크기 < 분할의 크기) : 하나의 분할 내부에서 남는 메모리 조각

 

 

중간중간에 Hole(가용 메모리 공간)이 생기게 된다

 

* Dynamic-Storage-Allocation-Problem

가변 분할 방식에서 size n인 요청을 만족하는 가장 적절한 hole을 찾는 문제

 

1) ✅first-fit : size n 이상 중 최초로 찾아지는 hole에 할당 (low overhead)

2) ✅best-fit : size n 이상 중 가장 작은 hole에 할당 (good for future)

- 많은 수의 아주 작은 hole이 생성

3) worst-fit : 가장 큰 hole에 할당

- 상대적으로 아주 큰 hole들이 생성

 

* Compaction

external fragment를 해결하기 위한 한 방법

사용 중인 메모리 영역을 한 군데로 몰고, hole을 다른 한 곳으로 몰아 큰 block을 만드는 방법

- 매우 비용이 많이 드는 방법

- execution time binding이 지원되어야만 가능

 

2. Noncontiguous Allocation 

1) Paging

: 프로그램의 virtual addr를 동일한 사이즈의 page 단위로 잘라서 올림

- page table을 통해 logical addr(page) -> physical addr(frame)로 변환

 

(+) hole 생성 등 신경쓰지 않아도 됨

(-) 복잡한 주소 변환, internal addr 발생 가능

page 내에서의 offset 부분은 영향 없다(상대위치)

* Implementation of Page Table

- Page-table base resigster(PTBR) : page table의 시작 위치를 가리킴

- Page-table length register(PTLR) : table 크기를 보관(limit)

 

- page table은 main memory에 상주

-> 모든 메모리 접근 연산에는 2번의 memory access 필요 : page table 1번, 실제 data/instruction 접근 1번

-> 속도 향상을 위해 associative register, 즉 TLB라는 캐시를 사용

 

* Associative Register(TLB)

- page table 중 일부만 존재

- 모든 TLB를 살펴봐야 하기 때문에 parallel search가 가능

- 프로세스마다 TLB의 정보가 다르기 때문에 context switch 때 flush해야 한다

 

* Effective Access time

 

* Two-Level Page Table

address space가 매우 크지만 대부분의 프로그램은 주소 공간 중 지극히 일부만 사용하므로 많은 공간이 낭비됨

-> 2-level의 경우 낭비되는 공간의 entry가 NULL로 처리되어 주소 공간 줄인다(안쪽 page table 사용 X)

 

* inner page table의 크기는 page 한 개와 같다

- page(4KB=2^12B)

- entry(4B) : 1K(2^10B)개

 

* logical address(32-bit machine with 4K page size)

- page offset : 12 bit (2^12B 구분)

- page number : 20 bit

--- page number 10 bit (2^10B 구분)

--- page offset 10 bit

 

- P1 : outer page table index (10 bit)

- P2 : inner page table index (10 bit)

- D : page offset (12 bit)

 

* Memory Protection

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

1) protection bit : page에 대한 접근 권한 - 주로 연산 권한(read/write/read-only)

- code : read-only

- data/stack : read, write

2) valid/Invalid bit

- valid : 해당 주소의 frame에 그 프로세스를 구성하는 유효한 내용이 있는 경우

- invalid : 페이지가 사용되지 않거나 메모리에 올라오지 않고 swap area에 있는 경우

 

* Inverted page table

시스템 내부에 page table을 하나 두고, entry를 page frame(physical memory)의 개수만큼 둠

- pid : process id

- p : entry #(physical frame #)

- d : offset

 

(+) page table 용량을 줄일 수 있음

(-) large overhead -> associative register를 두어 parallel하게 검색하도록 한다

 

* Shared Pages

1) Shared code (re-entrant code/pure code)

read-only로 하여 프로세스 간에 하나의 code만 physical space에 올림

shared code는 모든 프로세스의 logical addr space에서 동일한 위치에 있어야 한다

2) Private code

각 프로세스들은 독자적으로 메모리에 올림

 

2) Segment

: 프로그램의 주소 공간을 의미 있는 크기(code/data/stack)로 잘라서 올림

- 크기가 균일하지는 않음 -> hole 문제 발생

 

Logical Address

segment-number, offset으로 구성

1) segment table

- base : starting physical address of the segment 

- limit : length of the segment

2) segment-table base register(STBR) : 물리적 메모리에서의 segment table의 위치

3) segment-table length register(STLR) : 프로그램이 사용하는 segment의 개수

=> limit & STLR로 두 번 검증

4) Protection

5) Sharing : shared segment / same segment number

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

6) Allocation : first fit / best fit -> external fragmentation 발생

=> segment의 길이가 동일하지 않기 때문에 가변 분할 방식에서의 문제점이 동일하게 발생

 

3) Paged segmentation

segment가 여러 개의 page로 구성되어 있음

- segment-table entry가 segment를 구성하는 page table의 base address를 가지고 있음

- segment가 의미 단위의 일을 처리 / page가 내부 일을 처리

- 크기가 동일한 page로 구성되어 있기 때문에 allocation 문제가 발생하지 않음