[운영체제] 3장. Memory 관리

해당 게시물은 조진성 교수님의 '운영체제' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 목차 - 3장. Memory 관리

3-1. Main Memory
3-2. Virtual Memory

---

📌 3-1. Main Memory

* Memory Management
- To provide a convenient abstraction for programming
- To allocate scarce memory resources among competing processes to maximaize performance with minimal overhead
- To provide isolation between processes

 

* Memory Management Keypoints
1. 프로세스 내부에서 사용하는 logical address와 physical address를 분리해서 이것들을 어떻게 맵핑할 것인지 잘 관리해주는 것
2. physical address, RAM의 크기보다 큰 무한대의 virtual address가 있도록 지원해주는 것

- 프로그램을 돌리기에 RAM의 공간이 부족할 때 secondary storage(hdd, ssd)의 일부를 physical memory로 대신해서 동작하게끔 한다.

- 운영체제가 logical address 메모리가 무한한 것처럼 서비스를 제공한다.

* Binding of Instructions and Data to Memory
- Compile time : 컴파일 시점에서 메모리 주소를 결정하면 특정 주소에서 실행해야되기 때문에 일반적인 운영체제에서는 사용할 수 없다.
- Load time : 프로세스를 메모리에 올릴 때(로딩할 때) 실제 주소로 변환해서 메모리에 로딩하면 되지만 바꿀 메모리 주소가 너무 많아서 시간이 너무 오래걸린다.
- Execution time : 실제 메모리의 주소는 명령어를 실행할 때 계산한다.

* Virtual Memory Management
- virtual(logical) address space <-> physical address space
- MMU : virtual address를 physical address로 translation, mapping 시킨다. CPU가 명령어를 실행할 때 logical address(프로그램 내부) -> MMU -> physical address(실제 RAM 주소) -> physical memory

* Logical (Virtual) Address Space
- 프로그램이 어디서 실행되든지 logical address는 항상 똑같다.

* Contiguous Allocation
- logically contiguous한 address를 physically contiguous하게 배치하는 방법
- 성능이 가장 좋다.
- Address translation : Physical address = logical address + relocation register
- Memory protection : 참조할 수 있는 제일 큰 address(Limit register)를 저장한 후 비교한다. (trap: address error)

* Multiple-partition Allocation
- 새로운 프로세스가 생성 됐을 때 어떤 Hole에 배치할 것인가
- First-fit / Best-fit / Worst-fit

* Fragmentation
- External Fragmentation : 사용되지않는 작은 공간이 쌓인 것
- Internal Fragmentation : Allocated memory may be slightly larger than requested memory.
- Reduce external fragmentation by compaction : compaction을 사용해서 문제를 해결할 수 있지만 I/O overhead가 너무 크다.

* Paging
- Logically contiguous but physically not contiguous
- page와 frame으로 나눈다.
- 마지막 page에 internal fragmentation이 생긴다.
- page mapping이 복잡하다. (table로 관리해야 한다.)

* Address Translation
- logical address (p: page 번호 / d: offset 위치)
- physical address (f: frame 번호 / d: offset 위치)
- page table: page->frame. 프로세스마다 필요하다.
- free-frame list의 frame에 page를 mapping한다.

* Implementation of Page Table
- page table은 main memory에 구성되어 있어서 memory access 성능이 두 배로 나빠진다.
- 이를 해결하기 위해서 자주 사용되는 page table 정보만 cache 메모리에 넣는다. = TLB(Translation Look-aside Buffer)
- TLB : MMU 안에 존재하는 cache 메모리. p->f로 translation
- TLB miss 1% / TLB hit 99%

* Associative Memory
- page number에 매칭되는 frame number가 나오는 특별한 메모리
- (== CAM / Content Addressable Memory)

* TLB
- Temporal locality(이전 데이터) vs Spatial locality(근처 데이터)
- locality : program 크기의 20%정도(for, while 루프)만 프로그램 실행시간의 대부분을 차지한다.
- Handling TLB misses : MMU에서 hardware적으로 처리한다.
- Managing TLBs

* Effective Access Time
- EAT = 2 + ε - α
- Associative Lookup : ε time unit (작은 overhead)
- hit ratio : α (99%)

* Memory Protection
- page table에 valid-invalid bit를 둬서 invalid임을 확인한다. (falt: address error)

* Page Table Entries (PTEs)
- v(1), R(1), M(1), Prot(2), FrameNumber(20)
- V : Valid bit
- R : Reference bit
- M : Modify bit
- Prot : Protection bits (Read/Write/Execute, etc.)

* Page Table Structure
- Page table의 크기를 줄이자. invalid 메모리까지 가지고 있을 필요가 없다.
- dynamically extensible하도록 page table을 만들자.
- Hierarchical paging : 현재 사용중인 기법
- Hashed page table
- Inverted page table

* Hierarchical Page Table
- Outer page table -> Page table -> Memory
- 프로세스의 메모리 크기가 작으면 page table의 크기도 작아지게 만들기 위해서 사용한다.

* Hashed Page Table
- overhead가 너무 커서 사용하지 않는다.

* Inverted Page Table
- frame number로 table을 만든다.
- process의 정보를 일일이 찾아야 하기 때문에 사용하지 않는다.

* Shared Pages Example
- DLL, Shared Library를 메모리에 하나만 올려놓고 physical memory에 맵핑한다.
- paging 기법이 DLL, Shared Library를 구현할 때 용이하게 구현된다.

* Segmentation
- paging과는 다르게 의미있는 단위로 자르자.
- code segment, data segment, stack segment, extra segment(heap)
- logical address (s: segment 번호 / d: offset 위치)
- segment table (limit: 용량 / base: physical address)
- segment 내에서는 contiguous allocation을 한다.
- 따라서 external fragmentation이 또 발생한다.

* Paging vs Segmentation
- Hybrid approaches : Paged Segments. 먼저 의미있는 단위로 segmentation을 진행하고 각 segment내부에서 paging을 진행한다.

---

📌 3-2. Virtual Memory

* Demand Paging

- 초기에는 page table이 모두 invalid고 필요한 시점에 paging을 적용한다.
- A paging system with (page-level) swapping
- swapping : page 단위로 secondary storage <-> main memory
- Locality in a Memory-Reference Pattern
- Valid-Invalid Bit in Demand Paging
- v : 참조할 수 있고 physical memory에 있다.
- i : 참조할 수 없거나 physical memory에 없다. secondary storage에 있다. Protection fault or Page fault

* Page Fault
- 참조할 수 있지만 invalid로 표시 되어있을 때 발생시킨다. = memory가 secondary storage에 있다.
- Steps in Handling a Page Fault
1. reference (load M -> page table)
2. trap (page table -> OS)
3. page is on backing store (OS -> secondary storage)
4. bring in missing page (secondary storage -> physical memory)
5. reset page table (page table)
6. restart instruction (load M)

* Memory Reference
- 1(99%): MMU -> TLB -> TLB hit -> Memory
- 2(1%):
1. CPU -> TLB -> TLB miss -> Page Table(vaild) -> PTE
2. CPU -> TLB -> TLB miss -> Page Table(invalid) -> Page Fault or Protection Fault

* Copy-on-Write

- 이걸로 더 성능을 높였다.
- fork() 이후 두 프로세스가 같은 physical memory를 가리키지만 write memory하게 되면 새로운 physical memory를 참조한다.

* Page Replacement Algorithm
- page fault가 발생해서 free frame에 memory를 올리려고 하는데 frame이 꽉찼을 때 하나를 골라서 secondary storage로 내리는 알고리즘
- 오랫동안 사용되지 않은 memory를 고른다. temporal locality를 활용한다. victim 선정.
- 목표 : lowest page-fault rate
- page faults vs number of frames

* FIFO

- Belady's anomaly - frame을 늘렸는데 page fault가 늘어나는 비정상적인 상황이다. 어리석은 알고리즘으로써 사용하지 않는다.

* Optimal Algorithm

- 이 알고리즘보다 더 좋은 성능을 갖는 알고리즘은 없다. 미래에 어떤 것이 올지 알고 있는 알고리즘.(비현실적이다.)

* Least Recently Used (LRU) Algorithm

- 과거를 보고 미래를 예측한다. 가장 오래전에 사용된 page를 찾는다. temporal locality를 통해 생각해낸 알고리즘이다. optimal 성능에 근접하다.

* Implementation of LRU Algorithm

- 현재 시간을 기록하는 time stamp. reference bit를 사용해 0 또는 1을 저장해서 0인 page를 내린다. timestamp 관리의 overhead가 크다.- Timestamp implementation
- Stack implementation
- Approximation
- Reference bit : 최근에 참조된적 있냐 없냐

* Second chance (LRU Clock)

- 포인터가 clock 방향으로 돌아가면서 victim을 선정한다.

* Not Recently Used (NRU) Algorithm

- R(reference), M(modify) bits. 현재 CPU가 사용하는 방법이다. page replacecment algorithm. LRU, LFU는 overhead가 커서 NRU를 사용한다.

* Least Frequuently Used (LFU) Algorithm

- 참조된 횟수에 기반한 방법이다. optimal 성능에 근접하다. counter 관리의 overhead가 크다.
- LRU나 LFU나 overhead가 크기때문에 bit 크기를 줄이면 NRU하고 똑같이 되어버린다.

* Allocation of Frames
- free frame을 process에게 어떻게 할당할 것인가
- Allocation algorithm
- Equal allocation
- Proportional allocation
- Priority-based allocation
- Page replacement
- Global replacement
- Local replacement
- Page-Fault Frequency Scheme
- page fault rate가 많이 나는 쪽, frame이 부족한 쪽에게 frame 여유가 있는 프로세스에서 빼서 넘겨준다.

* Thrashing
- page fault가 너무 많이나서 swapping만 하고 있는 상황. disk I/O
- memory에 비해 process의 수가 많다.
- 해결방안
1. memory를 더 늘린다.
2. process의 수를 줄인다.

* Working-Set Model
- working-set : 해당 process가 최근 시간 안에 사용된 page들의 집합
- working-set size가 작을수록 locality가 우수하다.
- working-set size = total demand frames가 memory보다 크면 Thrashing이 발생한다.

* Other Considerations
- Prepaging
- Spatial locality
- Page size selection
- Fragmentation : internal fragmentation 측면에서 page size가 작은게 좋다.
- Page table size : page table size 측면에서 page size가 큰게 좋다.
- I/O overhead : page size가 큰게 좋다.
- Locality : page size가 큰게 좋다.
- 결론 : page size = 4KB
- TLB Reach
- TLB가 커버하는 메모리의 크기
- Page size가 클수록 좋다.
- Program structure : 좋은 코드를 많이 봐야한다.
- 2차원 배열 for문의 행 열의 순서에 따라서 page fault의 수가 늘기도 줄기도 한다.
- I/O Interlock : Pages must somtimes be locked into memory
- DMA (Direct Memory Access) : CPU가 메모리를 사용하지 않는 시간을 틈타서 I/O 장치가 직접 메모리에 쓰게끔 하는 방법. = virtual memory를 쓰지 않는다.

---