[OS] Memory Management

Background

- 프로그램은 실행을 위해 디스크에서 메모리로 적재되어야 함
- 메인 메모리와 레지스터들이 CPU가 접근할 수 있는 유일한 저장소임
- 레지스터에 접근하는 것은 1 CPU clock cycle 이하로 소요됨
- 메인 메모리에 접근하는 것은 수많은 cycle들을 소요할 수 있음
- Cache 접근은 메인 메모리에 접근하는 것과 CPU 레지스터에 접근하는 것 사이만큼의 시간이 소요됨
- 올바른 작동을 보장하기 위해 메모리 보안이 필요함

Memory Address Binding

Memory Address

• Symbolic Address: 코드 단에서 설정하는 address (ex. a = 10)
• Virtual(Logical) Address: 프로그램이 이상적으로 사용하는 주소 체계
• Physical Address: 실제 메모리의 주소. base와 limit register의 쌍이 physical address space를 정의함

  

Memory-Management Unit (MMU)

• Logical Address -> Physical Address 로 변환하는 과정을 address binding이라고 함
• Address binding은 프로그램이 컴파일될 때 수행되며, 3가지로 분류됨
  1. Compile time binding: logical memory가 physical memory 그대로 올라감. 시작 location이 바뀌면 코드를 recompile 해야함
  2. Load time binding: 각각의 symbol에 대해서 loader가 절대 주소를 할당함. 컴파일러는 상대적 주소들을 가진 relocatable code를 구현함
  3. Execution time binding: process 실행중에 physical memory내 주소가 변할 수 있을 때 사용. 이를 위해 MMU같은 하드웨어의 support가 필요함
• Address binding을 수행하는 하드웨어 디바이스를 MMU라고 함
• 구성
  1. Relocation register: 가장 작은 physical address의 값을 가짐
  2. Limit register: logical addresses의 범위 값을 가짐

---

Contiguous Allocation 연속 할당

Swapping

• Process는 상황에 따라 메모리에서 swapped out되서 디스크에 저장되거나 다시 디스크에서 swapped in 되서 메모리에 저장되는 경우가 있음
• Swap에는 큰 디스크 전송시간이 필요하기 때문에 현재는 메모리 공간이 부족할 때 Swapping 기법이 사용됨

Contiguous Allocation

• 메모리가 할당되는 순서대로 프로세스가 physical memory에 차곡차곡 할당됨
• 아직 할당 안되고 사용가능한 부분을 Hole이라고 함
• Dynamic Storage-Allocation Problem
  • Size n의 Hole을 어떻게 할당할까?
  • First-fit: 프로세스가 들어갈 수 있을 정도 사이즈의 Hole 중 가장 처음 만나는 Hole에 할당
  • Best-fit: 프로세스가 들어갈 수 있을 정도 사이즈의 Hole 중 가장 작은 Hole에 할당. 모든 list를 다 찾아봐야한다는 문제가 있음
  • Worst-fit: 가장 큰 Hole에 할당. 모든 list를 다 찾아봐야하고 또다른 Hole을 만들어내게 됨
• 할당은 했는데 안쓰고 남은 공간을 Frament라고 함
  • External fragmentation (외부 단편화): 메모리 공간 중 사용하지 못하게 되는 일부분
  • Internal fragmentation (내부 단편화): 프로세스가 사용하는 메모리 공간에 포함된 남는 부분
  • Compaction (압축): 외부 단편화 해소를 위해 프로세스들을 쭉 밀어서 남는 공간을 확보하는 방법

---

Non-contiguous Allocation 불연속 할당 - 1) Paging

Paging

• process의 logical memory를 동일한 사이즈의 페이지 단위로 physical memory에 할당하는 방식
• Basic Method
  • Physical memory를 Frame이라고 불리는 fixed-sized blocks로 나눔 (사이즈는 2의 제곱. 512 bytes < < 8MB)
  • Logical memory를 page라고 불리는 blocks of same size로 나눔
  • 사이즈 n pages의 프로그램을 실행시키고 싶으면 n개의 free frames를 찾아서 프로그램을 load함
  • Page table을 만들어서 logical -> physical 주소로 변환함
  • Internal fragmentation은 있을 수 있지만 external framentation은 없음
• Address Translation Schema: CPU에 의해 생성되는 address는 Page number(p, page table의 index)와 Page offset(d, base address와 합쳐 physical memory address를 정의함)로 나뉜다.

  

  logical address space 2^m, page size 2^n

• Address Translation Architecture

  

  

Page Table

• Logical Address를 Physical Address로 변환하는 과정에서 사용됨
• 모든 프로그램마다 page table이 있음
• Page table은 메인 메모리에 있음
• Page-table base register (PTBR): 페이지 테이블의 위치를 저장하는 레지스터
• Page-table length register (PTLR): 페이지 테이블의 길이를 저장하는 레지스터
• 모든 메모리 접근은 2번의 메모리 접근 횟수가 요구됨 -> page table 접근, 데이터 접근
• 이를 빠르게 하기 위해 Translation Look-aside Buffer (TLB)와 Associative memory가 사용됨

Associative Memory & TLB

• TLB에서는 Page Number와 Frame Number를 저장하고 이렇게 한 세트를 record라고 함
• TLB는 일종의 캐시라고 생각하면 됨
• TLB에서는 associative memory를 사용하는데 비싼 대신에 더 빠름
• TLB를 이용한 (p, d)의 address translation 과정
  1.  Associative Memory에서 Page table의 일부를 가져옴
  2. 만약 p가 그 안에 있다면 frame number를 꺼내옴
  3. 없다면 메인 메모리의 page table에서 frame number를 가져옴 (TLB miss)
  4. TLB는 context switching time에 flushed 됨

Memory Protection

• 각 frame마다 protection bit을 추가함으로써 memory protection을 구현할 수 있음
• Valid-invalid bit: 유효한지 표현

---

Structure of the Page Table

Hierarchical Paging

• Two-level Page-table Schema
  • Page table 자체를 page로 구성해 하드 디스크에 저장하고 잇다가 필요시 메모리로 로드
  • 비유하자면, 10000개의 서류를 보관할 때, 표(table)에 서류 10000개에 대한 모든 정보를 가지고 있는게 아니라 10개로 나눠서 한 테이블에 1000개의 정보를 저장하는 방식

Hashed Page Tables

• Virtual page number가 page table에 hashed됨
• 문제점: 충돌이 발생할 수 있음 -> 전체 영역에 대해서 uniform하고 random하게 분포시켜주면 됨

Inverted Page Tables

• 기존 페이지 테이블의 문제점: 모든 프로세스마다 logical address에 대응하는 모든 page에 대해 page table entry가 존재
• Inverted Page Table: 한 개의 page table만 존재. Page table entry에는 physical memory의 page frame이 담고 있는 내용을 표시. 프로세스 수행시 테이블 전체를 탐색해야 하는 단점이 있지만 associative register로 병렬 탐색 가능

---

Non-contiguous Allocation 불연속 할당 - 2) Segmentation

Segmentation

• 불연속 할당의 한 방법으로 physical memory에 의미 단위로 나누어 올리는 기법
• 의미 단위로 쪼개서 segment table이 가볍고, sharing과 protection에 있어 paging보다 효과적
• 하지만 메모리 공간 사용의 측면에서 sement의 크기가 동일하지 않아 문제점들이 있음 (external fragment 발생)
• Logical Address Structure
  • Segment-number
  • Offset
• Sement Table
  • 2차원의 Logical address를 Physical Address로 매핑시키는데 사용
  • 테이블 요소
    • Base: 각각의 segment가 메모리 상에서 어디에 있는지
    • Limit: segment의 사이즈
  • Segment-table base register (STBR): 메모리에서 segment table의 위치를 가리킴
  • Segment-table length register (STLR): 프로그램에서 사용되는 segment의 개수를 나타냄

---

Segmentation with Paging - MULTICS

• MULTICS 시스템은 segment를 paging해서 external fragmentation 문제를 해결함
• Virtual address 구조
  • Segment number s
  • Page number p
  • Displacement d