CPU가 program을 수행하기 위해서는 Memory에서 instruction과 data를 불러와야한다. 그러나 CPU가 직접적으로 접근할 수 있는 대상은 Main memory와 register만 가능하고, Main memory로의 접근은 속도가 매우 느리기 때문에 Cache라는 새로운 저장 공간을 사용하여 빠르게 data에 접근을 한다. 이를 위해서는 Memory management가 필요한데, 자기 자신의 address space만을 접근하도록 memory protection이 필요하고 어떤 대상을 cache에 올려놓을지, 어떻게 하면 memory를 효과적으로 사용하는지 등에 대해 OS가 관리를 해줘야 한다.

Binding of Instructions

: Memory 상의 정확한 physical address를 변수의 주소로 mapping 시키는 일련의 과정

Compile time binding

• Logical address = Physical address (각각의 변수들의 절대 주소를 이 때 알 수 있다)
• Multitasking/Multiprogramming 이 안됨
• 만약 compile된 program을 다른 OS에서 실행할 경우 User-process의 시작 지점이 다르기 때문에 해당 OS에서 다시 compile해야 하기 때문에 flexibility가 떨어진다. (시작 위치가 정해져 있기 때문)

Load time binding

: program을 memory에 탑재할 때 이 process의 address space가 몇 번지부터 시작인지 정함
(시작 지점 + 상대적인 offset = 실제 주소)

• Loader가 각각의 symbol에 절대 주소를 할당해준다
• Compiler는 process의 address space가 0번지부터 시작한다고 가정하는 상대 주소를 포함한 relocatable code를 생성한다.
• Multitasking 가능 (여러 process가 올라가더라도 각각의 process의 시작 위치를 알기만 하면 되기 때문)

Execution time binding

• Process가 execution 동안 memory에서 위치를 변경할 때 사용
• CPU가 주소를 생성할 때마다 address mapping table에 의한 binding이 필요하다
• Hardware support가 필요함 (e.g., base / limit register, MMU)

주요 개념

Address mapping table
: logical address를 physical address로 바꿔주는 자료구조로, instruction, data를 접근할 때마다 참조하기 때문에 매우 빨라야하는데 주소 변환 과정은 느리기 때문에 속도를 빠르게 하기 위해 hardware의 support가 필요하다

MMU (Memory-Management Unit)
: Address mapping table을 참조해 주소 변환을 진행하는 과정에서 느린 주소 변환 과정을 보조하기 위해 설계된 hardware로 logical address를 physical address로 mapping시킨다.

Base and Limit Register
: base, limit register 쌍은 physical address space를 정의한다.
base register의 경우 시작 지점을 의미하고 limit register의 경우 process가 차지하는 영역 즉, 길이를 의미한다.

Contiguous allocation
:Process의 address space가 memory 상에서 연속적으로 저장되어 있다고 가정하는 개념으로 이 가정에서만 physical address = base register + logical address이 성립한다.

• Main memory의 구조를 보면 다음과 같다.
  
  이 Relocation과 Limit register의 경우 다음과 같은 방법으로 mapping을 support 해준다.
  
  먼저 logical address를 MMU에 주는데 이 때 limit register가 범위 내에 있는지를 확인해서 protection을 해준다. (범위를 벗어나면 다른 주소공간을 참조하게 되기 때문) 그 뒤, relocation register의 값을 불러와서 offset 만큼 이동한 뒤 이를 physical memory로 변환하게 된다.

그러나 Contiguous allocation의 경우 치명적인? 단점이 존재하는데, 그 원인은 process의 크기가 다양하다는 점에 있다. Memory는 한정적이고 process의 크기는 다 다르기 때문에 process 사이에 빈공간이 존재하게 되는데 이를 Hole이라고 하고 Hole의 크기도 매우 다양해지게 되는데, 최악의 경우 Hole들의 크기가 작아서 process가 memory에 올라가지 못하게 되는 경우도 존재하게 된다.
이를 최대한 해결해서 Memory utilization을 높이기 위한 방법이 다음에 나올 Dynamic Storage-Allocation Problem이다.

Dynamic Storage-Allocation Problem

: 어떻게 free hole들의 list를 관리할지에 대한 방법

First-fit

• 가장 먼저 발견한 hole이 충분히 크면 그 hole에 할당한다.

Best-fit

• 충분히 큰 hole들 중 가장 작은 hole에 할당한다. 즉, 충분히 크기가 큰 hole들 중 process와 크기가 가장 비슷한 hole에 할당한다.
• 크기를 비교해야 하기 때문에 전체 list에 대한 탐색이 필요하다.
• 충분히 큰 hole들 중 가장 작은 hole들에게 할당하기 때문에 충분히 크지 않은 hole들이 할당되지 못한 채 남아있게 된다.

Worst-fit

• 무조건 제일 큰 hole에 할당한다.
• 가장 큰 hole을 찾기 위한 탐색 과정 필요
• Process의 크기보다 훨씬 더 큰 hole을 찾아서 할당하기 때문에 할당한 hole 내부에도 충분히 다른 process가 들어갈 수 있는 공간이 생긴다

$\Rightarrow$ Storage utilization관점에서는 Worst-fit보다는 First-fit과 Best-fit이 더 좋다

Fragmentation

: Dynamic Storage-Allocation Problem의 경우 Best-fit에서 크기가 매우 작은 hole들이 남거나 Worst-fit에서 처럼 hole에 할당하고도 내부에 공간이 남는 경우 들을 일컬어 "Fragmentation"이라고 한다.

• External fragmentation
  : 실제로 할당이 되지 않아 빈 공간으로 남아있는 부분
• Internal fragmentation
• 할당은 되었는데 process가 사용을 하지 않는 공간
  ex) 1000 byte process에게 1024($2^{10}$) byte 할당 = 24 byte : internal fragmentation
  이 문제의 경우 Compaction으로 해결할 수 있다. Compaction은 memory를 한 쪽으로 밀어서 빈공간들을 합쳐 fragmentation을 크게 만든 뒤 그 공간에 process를 할당하는 방법이다. 그러나, 이 방법은 이론 상으로는 좋은 방법이 될 수 있지만, memory를 미는 과정이 overhead가 매우 크기 때문에 compaction을 하는 것보다 근원적으로 external fragmentation을 만들지 않도록 하는 방법이 선호된다.

Paging

: 레고 블럭처럼 memory 공간에 address space를 끼워 넣는 할당 방법이다. 이 방법으로 contiguous했던 address space가 noncontiguous해진다. Address space가 contiguous할 경우 시작 주소 (Base register)만으로도 physical address를 알 수 있는데, noncontiguous해지게 되면 각각의 page가 memory의 어느 frame에 들어가 있는지를 알아야하기 때문에 그러한 정보를 담고 있는 자료구조가 필요하다. 이 때의 자료구조가 Page table이다.

Method

• Physical memory를 frames라고 불리는 고정된 크기의 block으로 나눈다 (보통 2로 나눠떨어지는 수)
• Logical memory를 pages불리는 같은 크기의 block으로 나눈다
• 모든 free frame들을 추적한다
• size=n인 page들의 program을 실행하기 위해서는 n개의 free frame들을 찾아서 program을 load 해야 한다.
• Logical address를 physical address로 변환하기 위한 page table을 setting한다.
• External fragmentation은 생기지 않지만, Internal fragmentation은 생긴다.

Address Translation

• CPU에 의해 생성된 주소는 Page number와 offset으로 나뉜다.
  
  
  아까의 그림과 달라진 부분은 logical address를 physical address로 변환하는 과정에 page table이 관여해 주소를 mapping 시켜준다는 점이다.

Free Frames

새로운 process를 free frame에 할당하는 과정을 그림으로 나타내면 위와 같다.

Implementation

• Page table은 main memory에 존재하고, 두 개의 register로 관리된다.

1. PTBR (Page-table base register)
   : page table의 위치를 저장하고 있는 register
2. PTLR (Page-table length register)
   : page table의 size를 저장하고 있는 register

Problem

: 모든 memory 접근이 두 번의 access를 요구한다. (Page table lookup + data/instruction load)

Solution

: Cache와 MMU와 같이 Hardware support로 해결한다. 여기서의 hardware는 TLB (Translation Look-aside Buffer) 또는 Associative memory가 사용된다.

• 일반적으로 TLB는 context switching이 일어나게 되면 flush된다.
• 몇몇 TLB들은 ASIDs(Address Space IDentifiers)를 각각의 TLB entry에 저장해서 TLB flush를 회피한다.
• Cache 처럼 locality에 근거해서 TLB에 올린다.

TLB

EAT (Effective Access Time)

: CPU가 Memory에 접근해서 원하는 Instruction/ Data를 가져오는데까지 걸리는 평균 시간

• Associative lookup = $\alpha$
• Memory access time = $\beta$
• Hit ratio = $\epsilon$
  EAT

  $\text{EAT} = (\alpha + \beta)\epsilon + (\alpha + 2\beta)(1-\epsilon) = \alpha + (2-\epsilon)\beta$

  1. TLB hit
     : TLB lookup + 주소변환 뒤 data를 가져오는 시간
     = $\alpha+\beta$
  2. TLB miss
     : TLB lookup + page table lookup + 주소변환 뒤 data를 가져오는 시간
     = $\alpha+2\beta$

이를 단순히 memory에 접근하는 시간인 $\beta$와 비교했을 때 Paging 기법의 성능이 얼마나 느려지는지를 확인하기 위한 지표이며, EAT를 $\alpha+\beta$에 최대한 가깝게 만들어야 한다.

Page table

Problem

: Program은 매우 큰 address space를 갖기 때문에 32bit 운영체제와 4KB page size (m=32, n=12)에서는 $2^{20}$개의 logical page들은 갖고 있고 각각의 page는 4byte이기 때문에 $4*2^{20}=2^{22}$byte 즉 4MB가 page table의 크기가 된다. 이걸 저장하기 위해서는 1K (2^{10})개의 page frame이 각각의 process마다 필요한데, 이는 너무 큰 공간을 차지하게 된다.

Solution

따라서 각각의 page table을 disk에 저장을 하고 필요한 page만 on demand로 올리는 방식을 채택하게 되었다. 이를 위해서는 흩어져 있는 page table의 frame들이 어디 있는지를 알려주는 자료구조가 필요하기 때문에 page table의 page table이 필요하다. 따라서 Two lebel page table이라는 개념이 등장하게 되었다.

Two level page table을 적용하게 될 경우 logical address는 다음과 같이 나뉜다.

기존의 logical address의 경우 page number 20-bit와 offset 12-bit로 나뉘었었는데 two-level의 경우 20-bit를 한 번 더 나누어서 10-bit에 바깥 page table의 index를 저장하고 나머지 10-bit에 안쪽 page table의 page를 저장하는 형태로 구성되어 있다.

주소 mapping 과정을 그림으로 나타내면 다음과 같다.

Multilevel Paging and Performance

EAT로 설명을 하면,

• TLB 접근 시간 : 20ns
• Memory 접근 시간 : 100ns
• TLB Hit ratio : 98%
• Level : 4

$\text{EAT}=0.98*120 + 0.02*520 = 128\text{ns}$

• 120 = TLB Hit (TLB access + data load)
• 520 = TLB Miss (TLB lookup + Memory access * 4 level + data load)

그럼에도 불구하고, 64bit OS의 경우 6-level이 필요하데 되는 이는 부적절할 뿐만 아니라 전부 다 사용하는 것도 아니기 때문에 다른 구조가 필요하다.

Hashed Page Table

32bit보다 큰 address space를 위한 page table로 hash 함수를 사용한 Hashed Page Table이 있다.

• Virtual page number가 page table에 hash되어 주소 변환을 한다.
  
  Hash 함수의 가장 대표적인 문제로 Collision이 있고 이는 Chaining이나 linear probing등의 기법으로 해결을 한다. 만약 collision이 발생할 경우 $O(1)$의 시간복잡도를 갖는 hash 함수가 $O(n)$까지 늘어날 수 있기 때문에 chaining 기법으로 collision을 대처해야 하고 chaining을 쓰더라도 chaing을 탐색하는 과정이 $O(n)$이 걸릴 수 있기 때문에 chain의 길이를 최대한 짧게 하는 것이 좋다고 한다.

Inverted Page Table

Problem

: Page table의 경우 각각의 process마다 할당되어 있는데, page table size는 page의 개수에 비례하고 하나의 logical page 당 page table entry 하나가 대응되는데, 실제로는 적은 수의 page만 필요하기 때문에 낭비가 심하다.

Solution

: Logical page 당 하나의 page table entry 대신 physical page 당 하나의 page table entry로 하면 loss가 줄어들 것이다.

• One system-wide page table
  • 필요한 entry의 개수 = #frames
  • 모든 process가 page table을 공유
  

Segmentation

: Program은 다양한 길이의 segment의 집합체이다. 예를 들어, program을 구성하는 segment으로 main program, 사용되는 함수, symbol table, subroutine 등을 들을 수 있다.

Architecture

• Logical address structure

  <segment-number, offset>

• Segment table
  : 2차원의 logical address를 physical address들에 mapping한다.

  • 각각의 entry는 page table과 동일하게 base register와 limit register를 갖고 있다.

• STBR (Segment-table base register)
  : Memory 상에서 segment table의 위치를 저장

• STLR (Segment-table length register)
  : program에 의해 사용되는 segment의 개수를 저장
  
  

• Protection
  :Valid/Invalid bit와 R/W/X bit가 각각의 entry와 연계되어 있다.
  이 중 R/W/X bit는 Read/Write/Execute를 의미하는데 "의미 단위"로 분할 했기 때문에 detail한 access control이 가능하다는 점이 장점이다. 예를 들어, code section의 경우 read-only이기 때문에 이 부분의 R bit로 write 작업을 하지 못하도록 할 수 있다.

• Sharing
  : 방금 말했듯이 code section의 경우 protection bit에 의해 보호가 되기 때문에 segment level에서는 code를 공유 가능하다.
  

• Allocation
  : Segment는 process 처럼 길이가 다양하기 때문에 dynamic storage-allocation problem이 memory 할당에 생긴다.

• 동일한 frame size만큼 memory를 할당한 뒤 frame에 page를 끼워 넣는 방식인 paging 기법과 반대로 fragmentation은 fragment size 만큼 memory를 할당하기 때문에 External fragmentation이 생기지만, internal fragmentation은 생기지 않는다.

그러나 전에 말했듯이 external fragmentation은 만들지 않는 것이 좋기 때문에 fragmentation에 external fragmentation이 발생하지 않도록 설계된 paging 기법이 결합되게 되었다.

Segmentation with Paging

$\Rightarrow$ Memory는 frame 단위로 분할, logical address space는 segment 단위로 분할한 뒤 각각의 segment를 page 단위로 분할한다.

기존의 segmentation과 달리 Virtual address에 segment의 base register 대신 해당 segment에 대한 page table의 base 주소가 들어가게 된다.


이렇게 Memory management기법, 그 중에서도 Paging 기법 위주로 살펴보았다. Paging 기법의 경우 다음 posting인 Virtual memory에서도 중요한 개념으로 쓰이기 때문에 잘 알아두어야 한다고 한다.