OS_10_1_Memory Management

1. Introduction

• CPU scheduling은 process들이 CPU를 공유하는 것을 허용한다.
  • CPU utilization과 반응 속도를 개선시킴
• To realize this
  • 메모리에 여러개의 process를 가지고 있어야함
    • multitasking의 전제조건
  • 이는 메모리 관리에 복잡한 문제를 초래한다.
• Memory management는 OS에서 가장 복잡한 부분중 하나
  • 메모리 관리는 여러 다른 목적을 가지고 있다.
• memory management의 일반적인 목적
  • 각 프로세스에 단일 연속적이고 보호된 메모리 공간을 제공하여 다른 프로세스 간의 메모리 공유를 용이하게 하고 유연한 메모리 관리를 가능하게 한다.
    • PC가 계속해서 증가하면서 instruction을 찾기 때문에
  • 물리적으로 사용 가능한 memory space보다 각 프로세스에 더 큰 독립된 메모리 공간을 제공한다.
    • 물리 메모리가 1GB일지라도 각 프로세스가 4GB 메모리 공간을 사용 가능
• Tricks used by OS
  • 주소 변환을 통한 연속적이지 않은 물리 메모리 할당
    • Paging or segmentation
    • 각 프로세스가 보는 주소를 실제 주소와 구별한다.
  • 요구에 따른 memory 할당 (demand paging)

2. Memory Allocation and Fragmentation

1) Memory Allocation and Address Binding

• Address binding
  • 모든 instruction들과 data들을 메모리 주소들에 할당한다.
• Three phases of address binding
  • Compile time
    • 메모리 위치를 미리 알 수 있는 경우
    • absolute code를 생성할 수 있다. 하지만, starting location이 변하면 반드시 recompile해야한다.
  • Load time
    • memory location이 compile time에 알 수 없는 경우 compiler는 relocatable code를 만들 수 있다.
  • Execution time
    • process가 execution동안 한 메모리 segment에서 다른 메모리로 이동 할 수 있을 때, Binding이 run time까지 지연된다.

2) Contiguous Memory Allocation

• CPU는 contiguous memory를 필요로 한다.
  • 프로세스가 도착하면, 충분한 크기의 공간을 가진 “hole”에서 메모리가 할당된다.
    • hole은 사용가능한 메모리 block으로 메모리 전체에 여러 크기의 hole이 흩어져 있다.
  • OS는 다음과 같은 정보를 유지한다.
    • allocated partitions
    • free partitions(hole)

3) Fragmentation Problem

• 2가지 type의 fragmentation
  • External Fragmention → free 공간
    • 요청을 만족하기에 충분한 공간이 있지만, 연속적이지 않은 경우
  • Internal Fragmentation
    • 할당된 메모리가 실제 요청된 메모리보다 약간 큰 경우
    • 메모리는 고정된 크기의 block 또는 Partition으로 할당되며, 할당된 블록이 프로세스가 실제로 필요로 하는 메모리보다 조금 더 많은 경우
    • 이는 partition 내부에 있는 사용되지 않는 메모리로, 낭비되는 메모리 공간이다.

4) Illustration

조각조각 흩어져 있어서 free공간을 사용 할 수 없다. (External Fragmentation)

5) Contiguous Memory Allocation Algorithms

• 요청된 크기 n을 free holes들의 list에서 어떻게 충족할 수 있는가?
• Three algorithms
  • First-fit : 충분히 큰 첫 번째 공간을 할당한다
    • 속도는 빠름
  • Best-fit : 만족하는 것 중에 가장 작은 공간에 할당한다.
    • 크기별로 정렬되어 있지 않다면, entire list를 탐색 해야 한다.
    • 가장 작은 잔여공간을 남기므로 저장 공간 활용도가 높음.
  • Worst-fit : 가장 큰 공간을 할당한다.
    • 이 또한, entire list를 탐색해야한다.
    • 가장 큰 잔여 공간을 남기므로 공간 활용도는 낮아짐.
• First-fit and best-fit은 worst-fit 보다, 저장 공간 활용도와 속도의 측면에서 우수함.

6) Solutions to Fragmentation

• external fragmentation을 compaction을 통해서 줄인다.
  • compaction은 메모리의 내용을 재 배치하여 모든 빈 메모리를 하나의 큰 block으로 만드는 것을 뜻한다.
  • compaction은 재배치가 dynamic하고, execution time에서만 가능하다.
• 다른 해결책
  • address translation을 통해서 비연속적인 메모리 할당

3. Address Translation

1) Key Idea for Noncontiguous Allocation: Address Translation

• 프로그램들은 logical(virtual) 주소를 사용하며 OS/HW는 이 주소를 physical(real) 주소로 변환한다.
• address translation의 이점
  • 비연속적인 메모리 할당을 가능하게 한다.
    • 메모리 할당에 대해서 유연성을 제공함.
  • 메모리 보호와 공유에 대해서 효율적인 구현을 가능하게 한다.

2) Logical vs. Physical Address Space

• logical 주소 공간과 별도의 physical 주소 공간이 바인딩 되는 개념은 올바른 메모리 관리에 중요하다.
• Logical(virtual) address
  • CPU에 의해서 생긴다.
• Physical address
  • memory unit에서 보여지는 주소

3) Memory-Management Unit (MMU)

• MMU
  • virtual address를 physical address로 mappingg하는 하드웨어 장치
• The user program
  • virtual address를 다룬다.
  • user program은 physical address를 볼 수 없다.

a) Dynamic Relocation Using a Relocation Register

b) Dynamic Relocation Using a Relocation Register

c) Noncontiguous Memory Allocation with Address Translation

• Segmentation
  • 메모리를 segment 단위로 할당하는 방식
  • Process memory = code segment + data segment + stack segment + …
    • 각 segment는 다른 크기를 가진다.
• Paging
  • 메모리를 페이지 단위로 할당하는 방식
  • Process memory = page + page + page…
    • Page는 동일한 고정된 크기를 가진다.

segmentation

Paging

• 항상 요청하는 메모리가 page단위 이기 때문에 External fragmentation이 없다.