07. vm

  • Haram Lee
  • 2026-04-14
  • studies / 26-1 / operating-systems

Virtual Memory

이 단원이 하려는 말

  1. 핵심 아이디어
    • 이 단원은 physical memory를 프로세스에 직접 보여 주지 말고, 그 위에 한 단계 추상화된 virtual address를 두자는 이야기다.
    • 즉 프로그램은 virtual address를 사용하고, 실제 하드웨어는 physical address를 사용하며, 둘 사이를 address translation mechanism이 연결한다.
    • 슬라이드가 이걸 level of indirection이라고 부른다.
  2. 왜 필요한가
    • 여러 프로세스를 메모리에 함께 올려 두고 번갈아 실행하면 utilization은 좋아지지만, 한 프로세스의 잘못된 memory access가 다른 프로세스나 OS를 침범할 수 있다.
    • 그래서 memory 쪽에서도 protection이 필요하고, virtual memory는 그 protection을 위한 핵심 추상화다.

Address Translation

  1. 주소 변환이란
    • 프로그램은 virtual address를 기준으로 instruction fetch와 data access를 한다.
    • 하지만 실제 physical memory는 다른 위치에 있을 수 있으므로, 실행 중에 virtual address를 physical address로 바꿔야 한다.
    • 이 변환을 수행하는 것이 address translation이다.
  2. 슬라이드 예시
    • 슬라이드에서는 ebx에 15KB 주소가 들어 있다고 가정하고, 다음 instruction들을 예시로 든다.
    • 128 : movl 0x0(%ebx), %eax
    • 132 : addl $0x03, %eax
    • 135 : movl %eax, 0x0(%ebx)
    • 첫 번째 instruction은 15KB 위치에서 값을 읽고, 두 번째는 register 연산만 하고, 세 번째는 다시 15KB 위치에 값을 쓴다.
    • 즉 instruction fetch도 주소를 쓰고, data load/store도 주소를 쓴다는 점을 보여 주는 예시다.

Relocation

  1. 문제의식
    • OS는 프로세스를 physical memory의 0번지에만 둘 수 없다.
    • 어떤 프로세스는 16KB 근처, 어떤 프로세스는 48KB 근처에 놓고 싶을 수도 있다.
    • 그러면 프로그램이 생각하는 주소와 실제 physical 주소를 다르게 연결해야 하는데, 이게 relocation 문제다.
  2. 의미
    • 프로그램 입장에서는 여전히 자기 코드, 데이터, heap, stack이 한 주소 공간 안에 있는 것처럼 보인다.
    • 하지만 OS는 그 전체를 physical memory 어디에든 배치할 수 있어야 한다.

Static Relocation

  1. 개념
    • static relocation은 소프트웨어 방식 relocation이다.
    • 프로그램을 메모리에 올리기 전에 코드 안의 주소들을 전부 rewrite한다.
    • 예를 들어 원래 0x0200을 참조하던 instruction을, 프로그램을 0x1000에 놓으면 0x1200을 참조하도록 바꾸고, 0x5000에 놓으면 0x5200을 참조하도록 바꾸는 식이다.
  2. 장점
    • 별도의 하드웨어 지원이 필요 없다.
  3. 단점
    • protection이 없다.
    • 프로세스가 OS나 다른 프로세스의 memory region을 망가뜨릴 수 있다.
    • privacy도 없다. 즉 임의의 memory address를 읽을 수 있다.
    • 한 번 배치한 뒤에는 주소 공간을 다시 움직이기 어렵다.
    • external fragmentation 때문에 새 프로세스를 배치하지 못할 수도 있다.

Dynamic Relocation

  1. 개념
    • static relocation 대신, 하드웨어가 실행 중에 주소를 바꿔 주는 방식이다.
    • 슬라이드에서는 이를 hardware-based relocation이라고 설명한다.
    • MMU가 모든 memory reference마다 address translation을 수행한다.
    • virtual address가 유효하지 않으면 MMU가 exception을 발생시킨다.
    • OS는 현재 프로세스의 유효 주소 공간 정보를 MMU에 넘겨 준다.
  2. 이후 등장하는 구현들
    • Base
    • Base and Bounds
    • Segmentation
    • Paging
    • 이 단원에서는 특히 base, base and bounds, segmentation까지의 흐름을 이해하는 게 핵심이다.

Design Points to Consider

  1. 설계할 때 봐야 할 것
    • memory protection을 어떻게 줄 것인가
    • 구현이 쉬운가, 어떤 하드웨어가 필요한가
    • fragmentation이 어떻게 생기는가
    • sharing unit이 무엇인가
    • 더 나아가 on-demand allocation을 지원할 수 있는가
    • 즉 이 단원은 단순히 “주소 바꾸는 법”만이 아니라, protection, efficiency, sharing을 함께 보려는 단원이다.

Fixed Partitions

  1. 기본 아이디어
    • physical memory를 크기가 고정된 partition들로 나눈다.
    • 각 프로세스는 partition 하나에 들어간다.
    • partition 개수는 동시에 올릴 수 있는 프로세스 수를 뜻한다.
  2. 주소 변환
    • 필요한 하드웨어는 base register 하나다.
    • physical address는 다음처럼 계산한다.
PA = VA + Base
  • context switch가 일어나면 OS가 새 프로세스의 base 값을 register에 넣는다.
  1. 슬라이드 예시
  • 슬라이드 그림에서는 virtual address가 0x0362, base register가 0x2000일 때 실제 physical address가 0x2362가 된다.
  • 즉 프로세스는 자기 주소 공간 안에서 0x0362를 썼지만, 실제 physical memory에서는 partition 시작점이 더해진 주소로 접근한다.
  1. 장점
    • 구현이 쉽다.
    • context switch가 빠르다.
  2. 단점
    • internal fragmentation이 생긴다.
    • partition 안에서 남는 unused area가 낭비된다.
    • partition size가 고정이라서, 작은 프로세스에는 낭비가 많고 큰 프로세스에는 부족할 수 있다.

Fragmentation

  1. 정의
    • fragmentation은 “free memory가 있지만 유용하게 할당할 수 없는 상태”를 말한다.
  2. 왜 생기나
    • free hole이 너무 작고 흩어져 있거나,
    • 할당 규칙 때문에 그 free space를 쓸 수 없기 때문이다.
  3. 종류
    • Internal fragmentation
      • 할당된 덩어리 내부에 남는 낭비 공간
    • External fragmentation
      • free 공간 총합은 충분해도 contiguous한 큰 공간이 없는 상태
    • 슬라이드 그림에서는 “No contiguous space!”라는 말로 external fragmentation을 보여 준다.

Base and Bounds

  1. 개념

    • fixed partition보다 더 유연한 contiguous allocation 방식이다.
    • physical memory를 variable-sized partition처럼 사용한다.
    • 각 프로세스에 대해
      • base register
      • bounds register
        를 둔다.

  2. 동작 방식

    • virtual address가 bounds보다 작으면 합법적 접근이다.
    • 그 경우 physical address는 다음처럼 계산한다.
PA = VA + Base
  • 반대로 bounds를 넘으면 protection fault를 낸다.
  1. 슬라이드 예시
  • 슬라이드 그림에서는
  • base = 0x3200
  • bounds = 0x1000
  • VA = 0x0362
    일 때 허용되고, 결과 physical address는 0x3562가 된다.
  • 하지만 VA = 0x2200 같은 값은 bounds를 넘으므로 protection fault다.
  1. 하드웨어 요구사항
    • base register + bound register가 필요하다.
    • 여기서 bounds register의 역할은 protection이다.
  2. 장점
    • 구현이 단순하고 저렴하다.
    • fixed partition보다 internal fragmentation이 적다.
  3. 단점
    • 각 프로세스는 여전히 physical memory에서 contiguous하게 배치되어야 한다.
    • 그래서 external fragmentation이 생긴다.
    • holes가 scattered되면 큰 프로세스를 넣기 어렵다.
    • partial sharing이 어렵다. 즉 주소 공간의 일부만 공유하기가 힘들다.

OS Issues

  1. 프로세스 시작 시
    • OS는 새 address space를 넣을 room을 찾아야 한다.
    • 이를 위해 free list를 관리한다.
    • free list는 physical memory에서 사용되지 않는 구간들의 목록이다.
    • 새 프로세스를 시작할 때 OS는 이 free list를 뒤져 충분한 contiguous 공간을 찾는다.
  2. 프로세스 종료 시
    • OS는 그 프로세스가 차지하던 memory를 free list에 다시 넣어야 한다.
    • 즉 reclaiming memory가 필요하다.
  3. context switch 시
    • OS는 현재 프로세스의 base/bounds 값을 PCB에 저장하고,
    • 다음 프로세스의 base/bounds 값을 복원해야 한다.
    • 즉 memory management 정보도 context switch의 일부다.

Compaction

  1. 왜 필요하냐
    • base and bounds는 external fragmentation이 생긴다.
    • free hole이 흩어져 있으면, 총 free memory는 충분해도 큰 프로세스를 위한 contiguous 공간을 만들 수 없다.
  2. 무엇을 하나
    • compaction은 physical memory 안에 흩어진 segment나 partition을 다시 모아서, 빈 공간을 한데 모으는 작업이다.
  3. 왜 비싸냐
    • running process를 멈춰야 한다.
    • 데이터를 복사해야 한다.
    • segment register 값도 바꿔야 한다.
    • 슬라이드도 Compaction is costly라고 직접 강조한다.

Segmentation

  1. 핵심 아이디어
    • 주소 공간을 code, data, heap, stack 같은 논리적 segment로 나눈다.
    • 즉 base and bounds를 프로세스 전체 하나에 적용하는 대신, segment별로 따로 적용하는 방식이다.
  2. virtual address 형태
    • segmentation에서는 virtual address를 다음처럼 본다.
\langle segment\#, offset \rangle
  • 즉 일부 비트는 segment 번호, 나머지는 그 segment 안의 offset을 뜻한다.
  1. 왜 base and bounds보다 낫나
  • code, heap, stack을 하나의 큰 contiguous region으로 강제로 묶을 필요가 없다.
  • 각 segment를 physical memory에 따로 배치할 수 있다.
  • 각 segment는 독립적으로 grow/shrink할 수 있다.
  • protection도 segment별로 따로 줄 수 있다.

Segmentation Example

  1. 슬라이드 segment table 예시
    • 슬라이드는 프로세스별 segment register 또는 segment table 예시를 보여 준다.
    • 예를 들면
      • Code: base 0x8000, bounds 0x0800, grows down, protection RO-X, valid 1
      • Data: base 0x8800, bounds 0x0400, grows down, protection RW, valid 1
      • Heap: base 0x9000, bounds 0x0800, grows down, protection RW, valid 1
      • Stack: base 0x7000, bounds 0x0800, grows up, protection RW, valid 1
    • 즉 segment마다 base, bounds, grows direction, protection, valid bit를 따로 가진다.
  2. 의미
    • code는 read-only + execute로 두고,
    • data/heap/stack은 read-write로 둘 수 있다.
    • stack은 다른 segment와 grow 방향이 다를 수도 있다.
    • 이게 segmentation의 큰 장점이다.

Segmentation: Addressing

  1. Explicit approach
    • virtual address의 일부 비트를 segment number로 쓰고, 나머지를 offset으로 쓰는 방식이다.
    • 즉 주소 자체에 “이건 어느 segment냐”가 직접 들어 있다.
  2. Implicit approach
    • segment를 주소 값이 아니라 memory reference의 종류로 결정하는 방식이다.
    • 예를 들어
      • PC 기반 addressing이면 code segment
      • SP나 BP 기반 addressing이면 stack segment
    • 슬라이드는 이런 implicit 방식도 설명한다.

Support for Sharing

  1. 왜 sharing이 필요한가
    • 같은 code를 여러 process가 함께 쓸 수 있으면 memory를 아낄 수 있다.
    • 대표적인 예가 shared libraries 같은 code sharing이다.
  2. 어떻게 하나
    • 서로 다른 process의 segment table에 같은 translation을 넣으면 된다.
    • 즉 두 프로세스의 code segment가 같은 physical segment를 가리키도록 할 수 있다.
  3. 조건
    • 공유되는 segment는 protection bit가 동일해야 한다.
    • 그래서 하드웨어가 read, write, execute permission을 segment별로 표현할 수 있어야 한다.

Segmentation: Pros

  1. 장점
    • sparse allocation이 가능하다.
      • stack과 heap이 독립적으로 자랄 수 있다.
    • 보호가 쉽다.
      • valid bit
      • segment별 protection bit
      • 예: code는 read-only, system segment는 kernel-mode-only
    • base and bounds보다 sharing이 낫다.
      • code/data를 segment level에서 공유할 수 있다.
    • 각 segment별로 dynamic relocation을 지원한다.

Segmentation: Cons

  1. 단점
    • 각 segment는 physical memory에 contiguously 할당되어야 한다.
    • 그래서 external fragmentation이 생긴다.
    • 큰 segment를 위한 충분한 contiguous physical memory가 없을 수도 있다.
    • segment table이 커진다.
      • main memory 공간이 더 필요하다.
      • 속도를 위해 hardware cache가 필요할 수도 있다.
    • heap segment 중간 객체들이 free될 때 internal fragmentation도 생길 수 있다.

마지막 정리

  1. 이 단원의 흐름
    • address translation이 왜 필요한지 이해한다.
    • static relocation은 단순하지만 protection이 없어서 한계가 있다.
    • 그래서 MMU를 이용한 dynamic relocation으로 간다.
    • 가장 단순한 방식이 fixed partition이고,
    • 그다음이 base and bounds,
    • 그다음이 segmentation이다.
    • segmentation은 protection과 sharing을 훨씬 잘 지원하지만, 여전히 external fragmentation 문제를 완전히 없애지는 못한다.
  2. 다음 단원과 연결
    • segmentation까지 오면 logical structure와 protection은 좋아진다.
    • 하지만 contiguous allocation 때문에 external fragmentation가 계속 문제다.
    • 그래서 다음 단원에서 paging이 등장한다.
    • paging은 주소 공간과 physical memory를 fixed-sized page/frame으로 잘라서 이 문제를 해결하려는 방식이다.
Discussion