logical & physical address의 차이점과 translating addresses에서 memory management unit(MMU)의 역할에 대해 설명
memory 할당의 first-, best-, worst-fit strategies를 적용
internal and external fragmentation를 구별
translation look-aside buffer(TLB)를 포함한 paging system에서 logical addresses를 physical addresses로 변환
hierarchical paging, hashed paging, and inverted page tables를 설명
Background
1. Basic Hardware
modern computer system -> Memory는 operation의 중심에 위치
Memory -> large array of bytes로 구성
program은 disk에서 memory로 brought, process 위에 위치
Main memory & registers -> 오직 해당 storage에만 CPU가 직접적으로 접근 가능
Register access -> done in one CPU clock(or less)
Main Memory access -> take many cycles, causing a memory stall(hyper threading을 통해서 T1 -> T2로 thread 전환으로 손실 최소화)
Cache -> CPU와 Main memory 사이에 위치
hardware에 의해 관리, os의 개입 X
2. Logical vs Physical Address Space
Logical vs Physical Address
Logical address: CPU에 의해 생성, virtual address라고도 불림
Physical address: memory unit의 시점에서 보는 address, memory-address register에 로드되는 주소
Binding addresses
Logical addresses = Physical addresses: in compile-time and load-time address binding
Logical addresses != Physical addresses: in execution-time address binding
Logical address space: set of all logical addressesgenerated by a program
Physical address space:logical addresses에 매칭되는 physical addresses의 모든 set
- Memory Management Unit(MMU)
run-time mapping from logical addresses to physical addresses -> MMU라는 hardware device에 의해 수행
- Simple Memory Management Scheme
Generalization of the base-register scheme
base register -> called relocation register (offset 역할)
relocation register에 위치한 value -> logical address에 더해져서 physical address로 변환
user program은 logical addresses만을 다룸 -> real physical addresses를 보지 않음
Contiguous Memory Allocation
Main Memory는 OS와 user processes 모두 support 해야 함 -> 자원은 한정돼있기 때문에, 효율적으로 사용해야 함
Contiguous allocation -> is one method
Main memory -> two partitions로 나뉨
Resident operating system: in low memory with interrupt vector
User processes: in high memory in single contiguous section of memory
High memory vs Low memory - High memory: logical address가 존재하는 메모리 공간 - Low memory: logical address를 갖고 있지 않은 메모리 공간 low memory에 대해서는 가상 주소를 물리 주소로 변환하는 매핑이 이미 존재 high memory에 대하여는 별도의 매핑을 해야만 접근 가능 https://hyeyoo.com/95
1. Memory Protection
Relocation registers는 user processes를 다른 processes로부터 지킴과 동시에, os의 code와 data를 변경하는것을 막을 때 사용됨
Base register: physical address의 smallest one 주소를 포함
Limit register: logical addresses의 범위(크기)를 포함
2. Memory Allocation
Variable Partition Scheme: each partition이 각각 process 하나를 소유
Hole: block of available memory; memory에 흩어진 사용 가능한 공간
파티션이 요청한 크기에 맞춰 동적으로 공간 할당 -> 시간이 지나면서 holes가 생김
- Dynamic Storage Allocation Problem
free holes의 목록 -> size n을 요구하는 request가 주어졌을 때, 이를 어떤 방식으로 만족시킬지
First-fit: allocate thefirst holethat is big enough
searching을 처음부터 시작 -> size에 맞는 hole이 발견되면 탐색 중지
Best-fit: allocate the smallest hole that is big enough
unsorted -> 전수탐색 수행
smallest leftover hole
Worst-fit: allocate thelargest hole
전수탐색
largest leftover hole
first-fit & best-fit이 worst-fit 방식보다 속도 & 저장 공간 활용성 측면에서 효율적
but, worst-fit을 사용하는 것이 더 나을 때도 있음? -> largest hole을 선택하면, 이에 따라 발생하는 hole의 크기도 커져서, 후에 사용가능성이 높아짐
3. Fragmentation
External Fragmentation: request가 요구하는 size를 만족하는 공간이 total memory space에 존재하나, 그 공간이 contiguous하지 않을 때 발생
Internal Fragmentation:
18464 bytes의 hole이 존재할 때, 18462 bytes의 크기 요청 -> 바로 할당 시에 2bytes의 크기가 남음
이를 관리하는 비용이 대체로 비효율 -> physical memory를 fixed sized blocks로 나누고, memory 공간을 block size에 따라 할당
이때, memory에 할당된 크기가 requested memory의 크기보다 매우 클 때, internal fragmentation 발생
compaction: processes를 이동시켜 hole의 크기를 키움 -> one solution of External Fragmentation
모든 free memory가 하나의 large block이 되도록 shuffle
relocation이 dynamic & execution time에 수행돼야 가능
simplest algorithm: 모든 프로세스를 end of memory로 이동 -> 너무 오래 걸림
Another possible solution: logical address space가 noncontiguous하도록 허용 -> memory 공간이 available한 physical memory를 process에 할당 -> Paging
Paging
physical address space of a process can be noncontiguous -> avoids external fragmentation(still have interanl)
1. Basic Method
physical memory -> devide memory into fixed-sized blocks called frames
logical memory -> devide memory into blocks of same size called pages
process execution: pages -> available memory의 frames로 loaded
program of size N pages -> N free frames
logical to physical addresses -> need page table
logical address는 다음으로 나눠짐
Page number: page table에서의 index
Page offset: base address와 합쳐져서 -> 정확한 physical address를 정의
- Steps to translate a logical address to a physical address (by MMU)
page number p를 이용 -> page table의 index로 사용
page table에서 관련된 frame number를 추출
page number p -> frame number f로 변경
- Paging Example
6-bit logical address: n = 2, m = 6
page size: 4
2. Hardware Support
Page table은 main memory에 유지 -> kernel memory
Page-table Base Register(PTBR): page table의 address
