8. Memory Management(1)

Background

• 프로그램은 디스크에서 메모리로 불러온 후, 프로세스 내에 위치해야 실행될 수 있음
• main memory와 register만이 CPU가 직접 접근 가능한 저장 장치임
• register 접근은 CPU clock cycle 1회 (또는 그 이하)
• main memory 접근은 여러 cycle이 소요될 수 있음
• cache는 main memory와 CPU register 사이에 위치
• 올바른 동작을 보장하기 위해 메모리 보호가 필요함

Multistep Processing of a User Program

사용자 프로그램은 메모리에서 실행되기 전까지 여러 단계를 거침

source program
↓ (compiler 또는 assembler)
object module
↓ (linker 또는 linkage editor)
executable module
↓ (loader)
memory image
↓
실행

Process in Memory: Address Space

    max
  +--------+
  | stack  |
  +--------+
  |  heap  |
  +--------+
  |  data  |
  +--------+
  |  text  |
  +--------+
    0

Binding of Instructions and Data to Memory

Compile time binding

• 이 시점에 각 symbol의 절대 주소가 결정되어야 함
• 절대 주소를 포함한 absolute code가 생성됨
• 시작 위치가 바뀌면 코드를 다시 컴파일해야 함

Load time binding

• loader가 각 symbol에 대한 절대 주소를 할당
• compiler는 상대 주소를 포함한 relocatable code를 생성함

Execution time binding

• 실행 중일 때, 프로세스가 메모리 내 위치를 변경할 경우 사용됨
• CPU가 주소를 생성할 때마다 주소 변환(address mapping)이 필요
• 하드웨어 지원 필요 (예: base and limit register, MMU)

Address Mapping Table

          CPU
    논리적 주소 (logical)    →    물리적 주소 (physical)
    ---------------------      -------------------------
        0번지                    →     500번지
      500번지                    →   20000번지

CPU가 제시한 주소 = 논리 메모리 내 주소
실제 메모리에서의 위치 = 물리 메모리 내 주소
예: 논리 주소 500 → 물리 주소 20500

Base and Limit Registers

• 물리 주소 공간은 base register와 limit register의 쌍으로 정의됨

  0           ┐
              │  operating system
  256000      │
  300040      │  process            ← base
  409240      │
  880000      │  process
 1024000      ┘                     ← limit

Logical vs. Physical Address Space

• 논리 주소 공간(logical address space) 개념은 물리 주소 공간(physical address space)과 분리되어 있으며, 이는 적절한 메모리 관리의 핵심임

• Logical address

  • CPU에 의해 생성됨
  • virtual address라고도 불림

• Physical address

  • 메모리 장치에 의해 인식되는 주소

• 논리 주소와 물리 주소는 컴파일 시간과 적재 시간 바인딩에서는 동일함

• 실행 시간 바인딩에서는 서로 다름

Memory-Management Unit (MMU)

• MMU (Memory-Management Unit)

  • 논리 주소를 물리 주소로 변환해주는 하드웨어 장치

• MMU 방식

  • relocation register의 값을 CPU에서 전달된 모든 주소에 더한 후 메모리에 보냄

  [ CPU ]
     │
     ▼
  ┌─────────────┐
  │ logical addr│ →────┐
  │     = 346   │      │
  └─────────────┘      ▼
                ┌────────────────┐
                │ relocation reg │ = 14000
                └────────────────┘
                          │
                          ▼
                  ┌──────────────┐
                  │ physical addr│ = 14346
                  └──────────────┘
                          │
                          ▼
                      [ memory ]

• 사용자 프로그램은 논리 주소만 다루며, 물리 주소는 직접 접근하지 않음

Swapping necessitates dynamic relocation

• Swapping

  • 프로세스는 일시적으로 메모리에서 backing store로 스왑됨
  • 이후 다시 메모리로 복귀됨

• Backing store

  • 모든 사용자 메모리 이미지를 저장할 수 있을 만큼 큰 고속 디스크
  • 사용자들이 직접 접근할 수 있어야 함

• 스왑에서 가장 큰 비중을 차지하는 것은 전송 시간

  • 총 전송 시간은 스왑되는 메모리 양에 비례함

Contiguous Allocation

• 주기억장치는 일반적으로 두 파티션으로 나뉨:

  • Resident OS: interrupt vector가 있는 low memory에 위치
  • User process는 high memory에 위치

• 사용자 프로세스를 보호하기 위해:

  • Relocation register: 가장 작은 물리 주소 값을 가짐
  • Limit register: 논리 주소 범위를 가짐
    • 각 논리 주소는 limit register로 경계 설정됨

  ┌────────────┐
  │     OS     │ ← low memory
  └────────────┘
  ┌────────────┐
  │ user proc. │ ← high memory
  └────────────┘

Hardware Support for Relocation and Limit Registers

• 하드웨어는 relocation과 limit register를 사용하여 주소를 변환함

  [ CPU ]
     │
     ▼
 ┌────────────┐
 │ logical addr│
 └────┬───────┘
      ▼
  ┌──────────────┐
  │ limit register│
  └────┬─────────┘
       ▼ (비교)
   logical < limit ?
       │
     ┌─┴────────────┐
     │   yes        │────────────┐
     └──────────────┘            ▼
                            ┌──────────────┐
                            │ relocation   │
                            │   register   │
                            └────┬─────────┘
                                 ▼
                            [ + ] (합산)
                                 ▼
                        ┌──────────────┐
                        │ physical addr│
                        └────┬─────────┘
                             ▼
                          [ memory ]

       no
       │
       ▼
  trap: addressing error

Contiguous Allocation (Cont.)

• Hole: 사용 가능한 메모리 블록
  • 다양한 크기의 hole(빈 공간)은 메모리 전반에 흩어져 있음
  • 프로세스가 도착하면, 해당 요청을 수용할 수 있는 크기의 hole에서 메모리가 할당됨
• 운영체제는 다음 정보를 유지함:
  • a) 할당된 공간
  • b) 빈 공간 (hole)

Dynamic Storage-Allocation Problem

• 요청 크기 n을 충족시키기 위해 hole 리스트에서 어떻게 할당할 것인가

• First-fit

  • 충분히 큰 첫 번째 hole에 할당

• Best-fit

  • 충분히 큰 가장 작은 hole에 할당
  • 전체 리스트를 탐색해야 함 (정렬된 경우 예외)
  • 많은 작은 leftover hole을 생성함

• Worst-fit

  • 가장 큰 hole에 할당
  • 역시 전체 리스트를 탐색해야 함
  • 가장 큰 leftover hole을 생성

저장 공간 활용 측면에서 First-fit 및 Best-fit이 Worst-fit보다 더 효율적임

Fragmentation

• External fragmentation

  • 전체 메모리 공간은 요청을 만족할 수 있을 만큼 있지만, 연속적이지 않음

• Internal fragmentation

  • 할당된 메모리는 실제 요청보다 약간 클 수 있음 → 이 크기 차이가 internal fragmentation (파티션 내부 메모리이나 사용되지 않음)

• 외부 단편화를 줄이는 방법: compaction

  • 메모리 내 내용을 섞어 모든 빈 공간을 하나의 큰 블록으로 만듦
  • 단, relocation이 동적으로 가능하고 실행 시간에 수행될 경우에만 compaction 가능

Paging

• Paging

  • 주소 공간을 비연속적으로 만들 수 있게 하는 스킴

• 기본 방식

  • 물리 메모리를 고정 크기 블록(frame) 으로 나눔
    (크기는 2의 제곱수, 512B ~ 8MB)
  • 논리 메모리를 같은 크기의 블록(page) 으로 나눔
  • 모든 frame의 상태를 추적
  • 프로그램 실행 시, n개의 페이지에 대해 n개의 빈 frame과 page table이 필요
  • 페이지 테이블을 통해 논리 주소를 물리 주소로 변환
  • 내부 단편화는 있으나 외부 단편화는 없음

Paging

  max
   │
   ▼
 ┌────────────┐
 │   stack    │
 ├────────────┤
 │    ...     │   ← pages
 ├────────────┤
 │   heap     │
 ├────────────┤
 │   data     │
 ├────────────┤
 │   text     │
 └────────────┘
Process Address Space

         │
         ▼
┌──┬──┬──┬──┬──┬──┬──┐
│  │  │  │  │  │  │  │  ← (page) frames
└──┴──┴──┴──┴──┴──┴──┘
   Physical Memory

Address Translation Scheme in Paging

• CPU가 생성하는 주소는 다음 두 부분으로 나뉨:

  • Page number (p)
    → 페이지 테이블에서 물리 메모리의 각 페이지에 해당하는 base address를 찾는 인덱스로 사용됨

  • Page offset (d)
    → base address에 더해 실제 메모리 접근 주소를 결정

주소 구조:

  page number   page offset
  ┌───────┬────────────────┐
  │   p   │       d        │
  └───────┴────────────────┘
     (m-n)비트       n비트

- 논리 주소 공간이 $2^m$일 때, 페이지 크기가 $2^n$이면

Address Translation Architecture

CPU
 ↓
┌─────────────┐
│ logical addr│
└────┬────────┘
     ↓
┌─────────────┐
│ Page Table  │
└────┬────────┘
     ↓
┌──────────────┐
│ physical addr│
└──────────────┘
              ↓
     Physical Memory

Paging Example

• Page Number = 2 / 4 = 0

• Offset = 2 % 4 = 2

• Logical address (m): 4비트

• Page number (m-n): 2비트

• Offset (n): 2비트

• 4바이트 페이지 → n = 2비트

Free Frames

• (a) 할당 전

free-frame list: 18 3 14 9 6 ...
new process: page 0, page 1

• (b) 할당 후

free-frame list: 13 8 10 ...
new process:
  page 0 → frame 14
  page 1 → frame 9

Implementation of Page Table

• 페이지 테이블은 주기억장치에 저장됨

  • Page-table base register (PTBR): 페이지 테이블을 가리킴
  • Page-table length register (PTLR): 테이블의 크기를 나타냄

• 문제점: 메모리 접근마다 두 번의 접근이 필요함

  • 하나는 페이지 테이블, 다른 하나는 데이터/명령어 접근

• 해결책: TLB(Translation Look-aside Buffer) 또는 Associative memory 사용

  • 일반적으로, TLB는 컨텍스트 전환 시 플러시됨 (이전 항목 제거)
  • 일부 TLB는 ASID(Address-Space Identifiers)를 저장하여 플러시를 피함
    → 각 프로세스의 주소 공간 보호 지원

Associative Memory (TLB)

• 두 가지 종류의 메모리:

  1. 일반 메모리 (예: DRAM)
     • 주소를 주면 데이터를 반환
  2. 연관 메모리 (Associative memory)
     • 데이터 일부를 주면 전체 레코드를 반환 (ex: 전화번호부)
     • 병렬 탐색 없이는 느림, 구현 비용이 큼

• Associative Memory (TLB): 병렬 탐색
  → 페이지 테이블의 일부만 TLB에 저장됨

• 주소 변환 과정 (p, d)

  • 페이지 번호 p를 TLB에서 먼저 찾음
    • 존재하면 해당 frame 반환
    • 없으면 페이지 테이블에서 frame 번호 검색

Paging Hardware with TLB

           logical address
                ↓
               ┌───┐
               │ p │────┐
               └───┘    │
                        ↓
                     ┌──────┐
               ┌────▶│ TLB  │────┐
               │     └──────┘    ↓
               │            ┌────────────┐
               │            │ Page Table │
               │            └────────────┘
               ↓                    ↓
             ┌────┐             ┌──────┐
             │  d │────────────▶│ + d  │
             └────┘             └──────┘
                                ↓
                         Physical Memory

Effective Access Time

• 연관 메모리(associative memory) 탐색 시간 = α time unit

• 메모리 접근 시간 = β

• Hit ratio = ε (연관 메모리에서 찾은 비율)

• 유효 접근 시간 (EAT: Effective Access Time)

<히트 시> + <미스 시>
EAT = (α + β) * ε + (α + 2β) * (1 − ε)
    = α + (2 − ε)β

Memory Protection

• 메모리 보호는 각 frame에 보호 비트(protection bit)를 연결하여 구현
• Valid-invalid 비트: 페이지 테이블의 각 항목에 포함
  • "valid": 해당 페이지가 유효 (사용 가능한 page)
    • 프로세스의 논리 주소 공간에 포함됨
  • "invalid": 접근이 허용되지 않음 (해당 주소는 불법)

Valid (v) or Invalid (i) Bit in a Page Table

• 페이지 크기 = 2KB
• 주소 범위: 0 ~ 10468만 사용
• 총 6개 페이지만 사용됨 (10469 / 2048 = 약 6)
• 페이지 테이블에서는 6개의 항목만 유효
• PTLR(Page Table Length Register)을 사용하여 valid-invalid bit 대신 유효성을 검사할 수 있음

logical address → 00000
                → frame number
                → valid-invalid bit

페이지 테이블:
page 0 → valid
page 1 → valid
...
page 4 → valid
page 5 → valid
page 6 이상 → invalid

Shared Pages

• Shared code

  • 읽기 전용 (read-only, 재진입 가능) 코드
  • 여러 프로세스가 공유 (예: 텍스트 편집기, 컴파일러, 윈도우 시스템)
  • 공유 코드는 논리 주소 공간의 동일한 위치에 있어야 함
    • 공유 코드에서의 자기 참조가 가능하도록 하기 위함

• Private code and data

  • 각 프로세스는 개별 복사본을 유지
  • 해당 코드는 논리 주소 공간 내 임의의 위치에 존재할 수 있음

Shared Pages Example

• 에디터는 3개의 페이지로 구성 (ed1, ed2, ed3)
• ed1~ed3는 공유 코드
• 나머지 데이터 페이지는 프로세스 별로 분리됨

process P1:
  page table → ed1
              ed2
              ed3
              data1
              data2

process P2:
  page table → ed1
              ed2
              ed3
              data3

process P3:
  page table → ed1
              ed2
              ed3
              ...

MemoryManagement-1 교수님 강의 내용 요약

Address Binding

• 모든 instruction과 함수 이름은 주소를 가짐
• CPU는 instruction을 fetch 및 실행하며 주소 정보를 필요로 함
• 주소를 결정하는 주체는 compiler

Binding 종류

• Execution Time Binding에서는 주소를 실시간으로 변환
• 이 작업을 빠르게 하기 위해 MMU (Memory Management Unit) 사용

MMU의 역할

• Logical Address + Base Address = Physical Address
• 덧셈 연산만으로 처리됨 (오버헤드 낮음)
• Protection: limit register를 사용하여 접근 범위 제한

메모리 단편화 문제와 Paging 도입

문제: External Fragmentation

• 연속 할당 방식에서는 빈 공간이 파편화되어 사용 불가
• compaction은 성능 비용 큼 → 비현실적

해결: Paging

• Address space와 memory를 동일한 크기(page, frame)로 분할
• page를 빈 frame 아무 곳에나 할당
• Internal Fragmentation: 마지막 page에서만 낭비 발생 → 무시할 수 있는 수준

주소 변환 방식

• Logical Address = Page Number + Offset
• 변환: page number → frame number (via page table), offset 그대로 유지
• 주소 변환시 paging table 사용 (process마다 하나씩 존재)

비트 분할을 통한 효율적 주소 변환

• Page size = 2^n 일 때
  • 하위 n비트 → offset
  • 상위 비트 → page number
• 나눗셈 불필요, bit 분할로 연산 가능

TLB (Translation Lookaside Buffer)

TLB란?

• 페이지 테이블 중 일부를 cache에 저장
• Associative Memory 사용
• TLB hit 시: 빠른 주소 변환 가능 (1 memory access)
• TLB miss 시: page table 접근 필요 (2 memory access)

Context-Switch와 TLB

• 프로세스 전환 시 TLB는 invalidate되어야 함
• 초기에는 miss 발생하지만 locality 덕분에 금방 hit 증가

Effective Access Time 계산

• hit ratio: ( \epsilon \ )
• TLB hit: ( \alpha \ ) (access time)
• Memory access: ( \beta \ )
• EAT = ( \epsilon (\alpha + \beta) + (1 - \epsilon)(\alpha + 2\beta) )

TLB의 장점

• Locality 덕분에 hit ratio 매우 높음 (ex: 1023/1024)
• 성능 향상에 매우 효과적

Protection

• Valid / Invalid bit 사용
• 접근 가능한 범위만 valid로 설정

Shared Paging

공유의 필요성

• text section 등은 read-only이므로 공유 가능
• 서로 다른 process라도 같은 frame을 가리키게 설정 가능
• 메모리 절약 효과 큼

Paging의 공유 구조

• process별로 독립된 page table 유지
• text section의 entry만 동일 frame 번호를 가리킴

결론

• Paging은 효율적인 메모리 관리를 가능케 하는 핵심 기법
• Overhead((\alpha))는 존재하지만, 메모리 효율과 공유 구조로 인해 이를 상쇄함
• TLB, 비트 분할, shared paging 등으로 성능 최적화 가능