[운영체제] Chapter 9. Main Memory

경희대학교 허선영 교수님의 운영체제 수업을 기반으로 정리한 글입니다.

 

Chapter Objectives

• 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 addresses generated 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 the first hole that is big enough
    • searching을 처음부터 시작 -> size에 맞는 hole이 발견되면 탐색 중지
  • Best-fit: allocate the smallest hole that is big enough
    • unsorted -> 전수탐색 수행
    • smallest leftover hole
  • Worst-fit: allocate the largest 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)

1. page number p를 이용 -> page table의 index로 사용
2. page table에서 관련된 frame number를 추출
3. 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
  • Page-table Length Register(PTLR): page table의 size
• In the scheme, 모든 데이터 or 명령어 접근 -> 두 번의 memory 접근이 필요
  • page table 접근 + data & instruction 접근

- Translation Look-Aside Buffer

• Translation Look-Aside Buffer(TLB): special fast-lookup hardware cache
  
  • associative memory로도 불림
  • 일반적으로 small -> 64 ~ 1024 entries
  • shared by process
• TLB miss -> value가 TLB로 loaded -> 다음 시도에서 빠른 접근
  • 교체 정책은 따로 설정해야 함
• some TLB -> Address-Space IDentifiers(ASIDs)을 각 tlb entry마다 가짐
  • 각 process를 구분 -> process address space protection
  • ASID가 제공되지 않는 경우 -> context switch 시에 TLB는 flush되어야 함

 

3. Memory Protection

• Protection bit for each frame -> read-only or read-write access를 구분
  
  • also add more bits execute-only, ...
• Valid-invalid bit - page table의 eache entry에 위치
  • valid: process의 logical address space에 존재
  • invalid: process의 logical address space에 존재 X
• Page-Table Length Register(PTLR) -> valid length
• Any violations result -> trap to the kernel

-> 6, 7번 page number는 logical address space에 존재하지 않음

 

Sturucture of the Page Table

• 32-bit logical address space as on modern computers
  
  • page size of 4KB -> 2^12
  • page 개수 -> 2^32 / 2^12 = 2^20
  • each entry -> 4bytes 차지
  • each process -> 4MB 차지
• main memory에 contiguous하게 할당하고 싶지 않은 경우

• Most common techniques for structuring the page table
  • Hierarchical Paging
  • Hashed Page Tables
  • Inverted Page Tables

1. Hierarchical Paging

• logical address space를 multiple page tables로 분할

- Two-Level Paging

• logical address(32-bit machine with 4K page size) 
  • page number 20 bits
  • page offset 12 bits
  • 기존 2^20의 entry 개수 -> 2^10 + 2^10개로 줄일 수 있음
  • page table의 크기는 줄지만, table의 개수가 늘어남 -> memory 참조 회수가 늘어남

 

2. Hased Page Table

• Virtual page number -> hashed into a page table
• page number에 hash function을 적용한 값을 바탕으로 hash table의 entry 참조
• hash function을 적용한 값이 동일한 entry에 대해서는 충돌(collision) 발생 -> 이를 해결하기 위해 Linked List 사용

-> 처음부터 하나씩 page number를 비교하면서, 동일한 값을 찾을 때까지 linked list를 탐색

• hash table과 linked list를 사용 -> page 개수 만큼 entry가 필요하지 않음 -> size를 줄일 수 있음
• 만약 linked list의 size가 5 -> 기존 page table보다 5배 만큼 크기를 줄일 수 있음

 

3. Inverted Page Table

• 한 프로세스 당 하나의 page table을 가짐 -> 사용하지 않는 page가 많아도, page의 최대 개수 만큼 page table entry를 가지고 있어야 함 -> 이런 문제를 해결하는 것이 Inverted Page Table
• Inverted Page Table: 가능한 모든 logical pages가 아닌, 가능한 모든 physical frames을 tracking
• 모든 process -> 하나의 page table 참조
• page table의 entry 개수 = physical memory의 frame 개수
• page table의 크기는 감소하지만, pid와 page number를 이용하여 비교연산을 page table에 진행 -> O(n)의 시간복잡도 소요

 

Swapping

• process는 memory에서 backing store에서 잠깐 옮겨지고, 이후 다시 가져와서 실행을 이어나갈 수 잉ㅆ음 -> Swapping
• processes가 차지하는 physical memory space가 실제 physical memory를 초과할 수 있음

 

1. Standard Swapping

• Standard swapping: entire processes 단위로 swapping을 수행
  
  • context switch time can the be very high
• Modified versions of swapping -> process의 page 단위로 swapping

 

2. Swapping with Paging

---

참고자료

• https://itstory1592.tistory.com/103

[운영체제] Page table의 3가지 구조 - Hierarchical, Hashed, Inverted Page table