운영체제 - Virtual Memory (가상 메모리)

Virtual Memory (1/5) - Non-continuous allocation

★ Virtual Storage (Memory)

• Non-continuous allocation
• 사용자 프로그램을 여러 개의 block으로 분할
• 실행 시, 필요한 block들만 메모리에 적재
  • 나머지 block들은 swap device(disk)에 존재
• 기법들
  • Paging system
  • Segmentation system
  • Hybrid paging/segmentation system

★ Address Mapping

• Continuous allocation
  • Relative address (상대 주소)
    • 프로그램의 시작 주소를 0으로 가정한 주소
  • Relocation (재배치)
    • 메모리 할당 후, 할당된 주소(allocation address)에 따라 상대 주소들을 조정하는 작업

• Non-continuous allocation
  • Virtual address (가상주소) = relative address
    • Logical address (논리주소)
    • 연속된 메모리 할당을 가정한 주소
  • Real address (실제주소) = absolute (physical)
    • 실제 메모리에 적재된 주소
  • Address mapping
    • Virtual address → real address

• 사용자/프로세스는 실행 프로그램 전체가 메모리에 연속적으로 적재되었다고 가정하고 실행할 수 있음

★ Block Mapping

• 사용자 프로그램을 block 단위로 분할/관리
  • 각 block에 대한 address mapping 정보 유지
• Virtual address : v = (b, d)
  • b = block number
  • d = displacement(offset) in a block
• Block map table (BMT)
  • Address mapping 정보 관리
    • Kernel 공간에 프로세스마다 하나의 BMT를 가짐

 

1. 프로세스의 BMT에 접근
2. BMT에서 block b에 대한 항목(entry)를 찾음
3. Residence bit 검사
   1. Residence bit = 0 경우,
   swap device에서 해당 블록을 메모리로 가져 옴 BMT 업데이트 후 3-2 단계 수행
   1. Residence bit = 1 경우,
   BMT에서 b에 대한 real address 값 a 확인
4. 실제 주소 r 계산 (r = a + d)
5. r을 이용하여 메모리에 접근

Virtual Memory (2/5) - Paging system (part 1)

★ Paging system

• 프로그램을 같은 크기의 블록으로 분할 (Pages)
• Terminologies
  • Page
    • 프로그램의 분할된 block
  • Page frame
    • 메모리의 분할 영역
    • Page와 같은 크기로 분할

• 특징
  • 논리적 분할이 아님 (크기에 따른 분할)
    • Page 공유(sharing) 및 보호(protection) 과정이 복잡함
      • Segmentation 대비
    • Simple and Efficient
      • Segmentation 대비
    • No external fragmentation
      • Internal fragmentation 발생 가능

★ Paging System (in Windows)

 

★ Address Mapping

• Virtual address : v = (p, d)
  • p : page number
  • d : displacement(offset)
• Address mapping
  • PMT(Page Map Table) 사용
• Address mapping mechanism
  • Direct mapping (직접 사상)
  • Associative mapping (연관 사상)
    • TLB(Translation Look-aside Buffer)
  • Hybrid direct/associative mapping
• Page Map Table (PMT)

• Direct mapping
  • Block mapping 방법과 유사
  • 가정
    • PMT를 커널 안에 저장
    • PMT entry size = entrySize
    • Page size = pageSize

• 문제점
  • 메모리 접근 횟수가 2배
    • 성능 저하 (performance degradation)
  • PMT를 위한 메모리 공간 필요
• 해결방안
  • Associative mapping (TLB)
  • PMT를 위한 전용 기억장치(공간) 사용
    • Dedicated register or cache memory
  • Hierachical paging
  • Hashed page table
  • Inverted page table

★ Associate Mapping

• TLB(Translation Look-aside Buffer)에 PMT 적재
  • Associative high-speed memory
• PMT를 병렬 탐색
• Low overhead, high speed

 

★ Hybrid Direct / Associative Mapping

• 두 기법을 혼합하여 사용
  • HW 비용은 줄이고, Associative mapping의 장점 활용
• 작은 크기의 TLB 사용
  • PMT : 메모리(커널 공간)에 저장
  • TLB : PMT 중 일부 entry들을 적재
    • 최근에 사용된 page들에 대한 entry 저장
  • Locality (지역성) 활용
    • 프로그램의 수행과정에서 한 번 접근한 영역을 다시 접근(temporal locality) 또는 인접 영역을 다시 접근(spatial locality)할 가능성이 높음
      
      
• 프로세스의 PMT가 TLB에 적재되어 있는지 확인
  1. TLB에 적재되어 있는 경우,
  • residence bit를 검사하고 page frame 번호 확인
  1. TLB에 적재되어 있지 않은 경우,
  • Direct mapping으로 page frame 번호 확인
  • 해당 PMT entry를 TLB에 적재함

 

Virtual Memory (3/5) - Paging system (part 2)

★ Memory Management

• Page와 같은 크기로 미리 분할하여 관리/사용
  • Page frame
  • FPM 기법과 유사ㅋ
• Frame table
  • Page frame당 하나의 entry
  • 구성
    • Allocated/available field
    • PID field
    • Link field : For free list (사용가능한 fp들을 연결)
    • AV : Free list header (free list의 시작점)

★ Page Sharing

• 여러 프로세스가 특정 page를 공유 가능
  • Non-continuous allocation!
• 공유 가능 page
  • Procedure pages
    • Pure code (reenter code)
  • Data page
    • Read-only data
    • Read-write data
      • 병행성(concurrency) 제어 기법 관리하에서만 가능

★ Page Sharing (Example)

• Editor 프로그램을 3명이 사용하는 경우

• Data page sharing

 

• Procedure Page Sharing (Problem)

• Procedure Page Sharing (Solution)
  • 프로세스들이 shared page에 대한 정보를 PMT의 같은 entry(이름 같게)에 저장하도록 함

 

★ Page Protection

• 여러 프로세스가 page를 공유할 때,
  • Protection bit 사용

 

★ Paging System - Summary

• 프로그램을 고정한 크기의 block으로 분할 (page) / 메모리를 block size로 미리 분할 (page frame)
  • 외부 단편화 문제 없음
  • 메모리 통합/압축 불필요
  • 프로그램의 논리적 구조 고려하지 않음
    • Page sharing/protection이 복잡
• 필요한 page만 page frame에 적재하여 사용
  • 메모리의 효율적 활용
• Page mapping overhead
  • 메모리 공간 및 추가적인 메모리 접근이 필요
  • 전용 HW 활용으로 해결 가능
    • 하드웨어 비용 증가

Virtual Memory (4/5) - Segmentation System

★ Segmentation system

• 프로그램을 논리적 block으로 분할 (segment)
  • Block의 크기가 서로 다를 수 있음
  • 예) stack, heap, main procedure, shared lib, Etc.
• 특징
  • 메모리를 미리 분할 하지 않음
    • VPM과 유사
  • Segment sharing/protection이 용이 함
  • Address mapping 및 메모리 관리의 overhead가 큼
  • No internal fragmentation
    • External fragmentation 발생 가능

• Address mapping
  • Virtual address: v = (s, d)
    • s : segment number
    • d : displacement in a segment
  • Segment Map Table (SMT)
  • Address mapping mechanism
    • Paging system과 유사
• Segment Map Table (SMT)

• Address mapping (direct mapping)

• Memory management
  • VPM과 유사
    • Segment 적재 시, 크기에 맞추어 분할 후 적재

• Segment sharing / protection
  • 논리적으로 분할되어 있어, 공유 및 보호가 용이함

 

★ Segmentation System - Summary

• 프로그램을 논리 단위로 분할 (segment) / 메모리를 동적으로 분할
  • 내부 단편화 문제 없음
  • Segment sharing/protection이 용이함
  • Paging system 대비 관리 overhead가 큼
• 필요한 segment만 메모리에 적재하여 사용
  • 메모리의 효율적 활용
• Segment mapping overhead (Paging 시스템과 유사)
  • 메모리 공간 및 추가적인 메모리 접근이 필요
  • 전용 HW 활용으로 해결 가능

★ Paging vs Segmentation

• Paging System
  • Simple
  • Low overhead
  • No logical concept for partitioning
  • Complex page sharing mechanism
• Segmentation System
  • High management overhead
  • Logical concept for partitioning
  • Simple and easy sharing mechanism

Virtual Memory (4/5) - Segmentation System

★ Hybrid paging/segmentation system

• Paging과 Segmentation의 장점 결합
• 프로그램 분할
  • 논리 단위의 segment로 분할
  • 각 segment를 고정된 크기의 page들로 분할
• Page 단위로 메모리에 적재

• Address mapping
  • Virtual address : v = (s, p, d)
    • s : segment number
    • p : page number
    • d : offset in a page
  • SMT와 PMT 모두 사용
    • 각 프로세스 마다 하나의 SMT
    • 각 segment마다 하나의 PMT
  • Address mapping
    • Direct, associated 등
  • 메모리 관리
    • FPM과 유사
• SMT in hybrid mechanism

• PMT for a segment k in hybrid mechanism

• Address mapping tables

• Direct (address) mapping

 

★ Hybrid Paging/Segmentation

• Summary
  • 논리적 분할(segment)와 고정 크기 분할(page)을 결합
    • page sharing/protection이 쉬움
    • 메모리 할당/관리 overhead가 작음
    • No external fragmentation
  • 전체 테이블의 수 증가
    • 메모리 소모가 큼
    • Address mapping 과정이 복잡
  • Direct mapping의 경우, 메모리 접근이 3배
    • 성능이 저하될 수 있음