Memory Management
Logical vs Physical
- Logical Address == virtual address
- 프로세스마다 독립적으로 가지는 주소 공간
- CPU가 보는 주소
- Physical Address : 메모리에 실제 올라가는 위치
Symbolic (사용자가 보는) ---컴파일---> Logical (숫자 주소) ---?---> Physical (물리적 공간에 올라가기 위함)
주소 바인딩 Address Binding
- Compile time binding
- 컴파일 시
- 시작 위치 변경시 재 컴파일
- 절대 코드 생성, 논리 이자 물리적 주소 Absolute Code
- 꼭 0번지부터
- Load time binding
- 실행 시작시 비어있는 곳으로 할당
- 재배치 가능 코드를 생성한 경우 재배치 가능
- CPU 요청시 주소변환하여 물리적 주소 찾아 반환
- Execution time binding (Run time binding)
- 실행 중
- 수행 시작 후에도 위치 옮길 수 있음
- CPU가 주소 참조시 매번 점검
- 하드웨어적인 지원 필요 : MMU, base and limit registers
MMU Memory-Management Unit
logical address를 physical address로 매핑해주는 H/W 장치
프로세스가 생성해내는 모든 주소값에 대해 base register의 값을 더한다.
사용자 프로세스, 즉 CPU는 logical만 다루면 된다. mmu에게 요청만 하여 메모리 접근하면 된다.
- Dynamic Relocation
Relocation regsiter(base)(: 접근할 수 있는 물리적 메모리 주소의 최소값)과
limit register(: 논리적 주소의 범위)을 사용하여 physical 변환
논리 + relocation register -> 물리 주소 시작 위치
limit register : 악의적인 요청인지 확인 -> Trap -> OS에 Abort함
용어
Dynamic Loading
프로세스를 static하게 미리 다 올리는 것이 아니라 루틴이 불려질 때 메모리에 load
memory utilization 향상
가끔씩 사용되는 많은 양의 코드에 유용. (방어적인 루틴, 오류 처리 루틴)
OS의 라이브러리를 이용하여 개발자가 직접 만듦. OS가 직접적으로 참여하진 않음.
Overlays
프로세스 중 실제 필요한 정보만을 올림
프로세스 크기가 메모리보다 클 때 유용
OS 지원없이 사용자가 구현. 초창기 수작업으로 프로그래머가 구현 (Manual Overlay) -> 어려움
Swapping
프로세스를 일시적으로 통째로 메모리에서 backing store로 쫓아냄
- Backing store == Swap area -> 디스크(큰 저장 공간)
- Swap in : Compile time 혹은 load time binding에서 원래 메모리 위치로 돌아감 -> 그래서 run-time binding이 돼야 한다.
- Swap out: swapper 중기 스케줄러에 의해 쫓겨날 프로세스 선정 (priority순으로)
- Swap time: 대부분 transfer time. swap되는 양에 달려있음
Dynamic Linking
linking을 실행 시간까지 미루는 기법
- Static
- 라이브러리가 이미 파일 코드에 포함됨
- 실행 파일 크기 커짐
- 동일한 라이브러리를 각 프로세스가 메모리에 올리므로 메모리 낭비
- Dynamic -> Shared Library(dll, shared object)
- 라이브러리가 코드 실행시 link됨
- 라이브러리 파일을 찾을 수 있는 stub 포인터. 현 프로그램의 주소 공산을 사용하지 않기에
- OS의 도움 필요
Allocation of Physical Memory
메모리는 OS 상주 영역과 사용자 프로세스 영역, 두 영역으로 이루어져 있음
종류
- Contiguous Allocation : 연속 할당
각각의 프로세스가 메모리 연속 공간에 적재되도록 함
종류
- fixed partition allocation : 고정 분할. 융통성 X, 내부 & 외부 조각 발생
- variable partition allocation : 가변 분할, 외부 조각 발생
- Noncontiguous Allocation : 불연속 할당
종류
- Paging : 메모리를 같은 크기의 페이지로 자름. 페이지 단위로 움직임
- Segmentation: 주소 공간을 의미 있는 단위로 자름.
- Paged Segmentation: 혼합
Contiguous Allocation
- 고정 분할 방식
- 미리 파티션으로 나눠둠
- 분할 크기가 같을 수도, 다를 수도 있다.
- 분할 당 하나의 프로그램 적재
- 융통성 X
- load 되는 프로그램 수가 고정됨
- 최대 수행 가능 프로그램 크기 제한
- 내부 조각 (올리는 프로그램이 공간보다 작아 남는 공간 발생)과 외부 조각(파티션이 너무 작아 사용이 안된 부분이 있음) 발생
- 가변 분할 방식
- 프로그램의 크기 고려 할당
- 분할의 크기, 개수가 동적으로 변함
- 외부 조각 (파티션이 너무 작아 올라갈 프로그램이 없어 낭비) 발생
Hole
- 가용 메모리 공간
- 여러 hole들이 메모리 여러 곳에 흩어져있음
- 프로세스 도착시 수용가능한 hole 할당
<How to hole 할당?>
Dynamic Storage-Allocation Problem
: 가변 분할 방식에서 size n인 요청을 만족하는 hole 찾기 문제
- Fist-fit : 최초로 찾아지는
- Best-fit : 다 살펴본 뒤 크기가 가장 잘 맞는 것 찾기 (모두 탐색 필요)
- Worst-fit : 가장 큰 hole 할당 (모두 탐색 필요), 시간,공간 이용률 측면에서 가장 비효율적
Compaction
외부 조각 문제를 해결하는 방법
- 사용중인 메모리를 한 곳으로 몰고, hole도 다른 쪽으로 몰아 큰 block 만들기
- 비용이 많이 듦
- 실행 시간에 동적으로 재배치 가능한 경우에만 가능한 방법
Noncontiguous Allocation
Paging
- virtual memory를 동일한 사이즈의 Page단위로 나눔
- 불연속적으로 메모리 저장됨
- 일부는 backing storage에, 일부는 physical memory에 저장된다.
Basic method
- physical을 동일한 크기의 frame으로 나눔
- logical를 동일한 크기의 page로 나눔 (frame과 크기 동일)
- page table을 이용하여 logical to physical
- 외부 조각은 발생 X, 내부 조각은 발생 가능성이 있다.
Page table
page는 주로 4Kb로 logical memory는 100만개로 나뉜다.
그 만큼 page table의 entry가 필요하게 되는 데 용량이 커 메모리에 저장하게 된다.
CPU는 [ p | d ]
를 통해 page table에 접근하여 p번째 entry를 찾아 frame 번호를 얻어 [ f | d ]
로 physical 주소로 변환한다.
구현
- Page table 은 main memory에 상주
- Registers 2개
- PTBR (Page-table base register) : page table 시작 위치를 가리킴
- PTLR (Page-table length register) : table 크기를 보관한다.
- 메모리 접근 연산에 2번의 메모리 접근 필요 -> 비용 낭비
page table 접근 1번, data/instruction 접근 1번
- 속도 향상을 위해 associative register 혹은 cache인 TLB(translation look-aside buffer)을 이용
TLB (paging h/w)
TLB에 빈번히 참조되는 것을 미리 올려둔다.
- 별도의 H/W cache이다.
- process 마다 존재
- Page 번호와 frame번호가 저장돼있어야 함 (쌍으로)
- 전체 검색이 필요
- 먼저 TLB를 전체 탐색 후
- hit(찾는 것이 있다면) : 바로 physical 접근 (메모리 접근 1번)
- miss(찾는 것이 없다면) : page table에 가서 변환 (메모리 접근 2번)
Two-Level Page Table
32비트 주소 체계 -> 2^32 4GB의 주소 공간
page size : 4K -> page table entry 1M개 필요 (entry가 4B라면 4M page table 필요)
이 공간을 일부분만 사용하여 page table이 심하게 낭비 됨
-> page table을 또 하나의 page로 구성 : 사용하지 않는 주소 공간에 대해서 outer에서 null로 두고, inner은 대응하는 것이 없음.(낭비 줄임)
logical address
p1 | p2 | d
10 | 10 | 12
* p1은 outer의 index이고(page number), p2는 outer의 page에서 displacement(page offset)
- d
page 하나당 4KB : 2^12B -> 12 bit 필요
- p2
entry 하나당 4B : 1K = 2^10 -> 10 bit 필요
*64비트 체계라면?
메모리 접근을 n번해야해서 오버헤드일지도 모르지만 TLB를 사용하여 시간 단축
Memory Protection
entry마다 bit를 둔다.
-
Protection bit
page에 대한 접근 권한 표시. 연산에 대한 권한 (read/write/read-only)
-
Valid / Invalid Bit in a Page Table
page table은 프로그램이 가지는 메모리 공간 만큼 필요하고, 사용되지 않더라도 생성되야 함
그래서 Valid (공간 사용) / Invalid (공간 사용 X)로 bit에 표시
- invalid : 프로세스가 그 주소 부분을 사용하지 않을 경우/ 메모리에 있지 않고 swap area에 있을 경우
Inverted Page Table
공간 오버헤드가 큰 것을 해결
- Page frame 당 page table에 하나의 entry를 둔 것. 하나만 있음 (system-wide)
- page table entry는 물리 메모리의 page frame을 담고 있음. p-id | logical address
- 테이블 전체 탐색 필요 -> associative register 사용 (병렬적으로 동시 검색)
CPU -> [ pid | p | d ]
로 페이지 테이블에서 찾기 -> f번째에 해당 process logical address를 찾음 -> [ f | d ]
로 변환된 physical address 나옴
=> 몇번째 entry인지가 중요함
Shared Page
data를 제외하고 공유 가능한 코드. 즉, 재사용 가능한 코드. Re-entrant Code (Pure Code)
[조건]
1. read-only (다른 코드에 의한 영향이 X)
2. 동일한 logical address에 위치해야함.
Segmentation
구조
- logical address :
[ segment-number | offset ]
- Segmentation table
[ base | limit ]
- base : 물리적 위치 시작 주소
- limit : segment 길이
- Registers 2개
- STBR (Segment-table base register) : table 시작 위치
- STLR (Segment-table length register) : table 길이. segment entry 개수
-> s is legal if s<STLR : 아니라면 Trap!
- CPU ->
[ S | d ]
->
- segment table의 s번째 확인
[limit | base]
->
- 와중에 1.
s true if s<STLR
2. d<limit
(세그먼트는 의미단위라 길이가 다 달라 확인 필요) check!
- base +d 가 physical address
장점
1. Protection : 세그먼트 별로 bit 있음
2. Sharing
=> 의미 단위이기에 효과적이다. (반면, paging은 의미단위가 아니라서 권한 부여시 맞지 않는 부분 발생)
- paging보다 개수가 적다. (Table로 인한 낭비가 적음)
단점
Allocation
- first-fit/best-fit 등을 이용하게 되고
- 외부 조각 발생 (반면, paging은 발생하지 않음)
Sharing of Segments
공유가능한 코드에 대해 같은 세그먼트를 이용.
data 같은 private segment는 다 따로 둠.
Segmentation with Paging (Paged Segmentation)
segment table entry는 segment의 base 가 아니라 segment를 구성하는 page table의 base를 갖고 있음
1. CPU-> [ s | d ]
세그먼트 번호 | offset
2. segment table에서 page table 시작 주소 찾기 [ segment length | page table base ]
페이지 단위로 올라가게 됨
3. page table base + d 하여 [ p | d' ]
페이지 번호 | 페이지 offset을 찾는다.
4. 해당 세그먼트를 위한 페이지 테이블에서 p entry를 찾아 physical로 변환 [ f | d' ]
5. 메모리에 페이지 별로 올라감 (물리 메모리는 페이지 단위로 이용하는 것)
=> 각 기법의 장점을 이용할 수 있다.
이 주제에서 주소 변환시 OS역할은? 없다
다 H/W가 한다. OS가 하면 CPU가 정신 없을 것이다.