Virtual Memory(non-continuous allocation)

Virtual Storage(Memory)

• Non-continuous allocation

• (참고: continuous aloocation은 연속된 메모리 공간에 프로세스를 올리는 것)

• 사용자 프로그램을 여러 개의 block으로 분할한다.

• 실행 시, 필요한 block들만 메모리에 적재한다.

  • 나머지 block들은 swap device에 존재함.(swap device를 디스크로 이해하면 됨)

• 기법들

  • paging system
  • Segmentation system
  • Hybrid paging/segmentation system

Address Mapping

• memory allocation을 하면 Address Mapping이 필연적으로 따라온다.

continuous allocation

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

Non-continuous allocation

• Virtual address(가상 주소) = relative address

  • logical address (논리 주소)
  • 연속된 메모리 할당을 가정한 주소(프로그래머가 프로그램 어디서부터 어디까지 자를지 고민하지 않고 통으로 짜도 됨)

• Real address(실제 주소) = absolute(physical)

  • 실제 메모리에 적재된 주소

• virtual memory에서 Address mapping이라는 말은 virtual address를 real address로 바꿔주는 것을 의미한다.
  

Block Mapping(adress mapping 기법)

• 사용자 프로그램을 block 단위로 분할/관리
  • 각 block에 대한 address mapping 정보 유지
    

Block map table(BMT)

• Address mapping 정보 관리
  • Kernel 공간에 프로세스마다 하나의 MBT를 가짐
• block number: 블록 번호
• residence bit: 메모리에 올라갔는지 여부(0/1, 1이면 올라가있는 상태)
• real address: 실제 물리 주소
  

Block mapping 순서

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

Paging system

• 프로그램을 같은 크기의 블록으로 분할하는데, paging system에서는 이 블록을 page라고 부른다.

Terminologies

• Page
  • 프로그램의 분할된 block
• Page frame
  • 메모리의 분할 영역
  • Page와 같은 크기로 분할
    

특징

• 논리적 분할이 아니다.
• 크기에 따른 분할이다.
• page 공유 및 보호 과정이 Segmentation에 비해 복잡하다.
• 예를 들자면 segmentation은 함수 단위로 관리해서, 관리가 쉬운데, paging system은 크기 단위로 자르기 때문에 관리가 복잡함
• Simple, Efficient (Segmentation과 비교했을 때)
• No external fragmentation
• Internal fragmentation 발생 가능
  

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

PMT(Page Map Table)

• page number: 페이지 번호
• residence bit: 메모리 적재 여부(0/1)
• secondary storage address: 모든 페이지는 swap device에 저장됨. swap device 어디에 저장됐는지에 대한 정보
• page frame number: 메모리 어디에 올라갔는지에 대한 정보
  

Address Mapping - Direct mapping

• Block mapping과 유사
• 가정
  • PMT를 커널 안에 저장
  • PMT entry size = entrySize(PMT row 하나를 EntrySize라 지칭하겠다.)
  • Page size = pageSize

Direct mapping 기본 flow

1. 해당 프로세스의 PMT가 저장되어 있는 주소 b에 접근
2. 해당 PMT에서 page p에 대한 entry 찾음
   - p의 entry 위치 = b + p * entrySize
3. 찾아진 entry의 존재 비트 검사
   
   3-1. Residence bit = 0 인 경우(page fault), swap device에서 해당 page를 메모리로 적재. PMT를 갱신한 후 3-2단계 수행
   
   3-2. Residence bit = 1인 경우, 해당 entry page frame 번호 p'를 확인
4. p'와 가상 주소의 변위 d를 사용하여 실제 주소 r 형성
   
   r = p' * pageSize + d
5. 실제 주소 r로 주기억장치에 접근

Direct mapping 정리

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

Address Mapping - Associative mapping

• TLB(Translation Look-aside Buffer)에 PMT 적재
  • Associative high-speed memory
• PMT를 병렬 탐색
• Low overhead, high speed
• Expensive hardware
  • 큰 PMT를 다루기 어렵다.
    

Address Mapping - Hybrid Direct/Associative Mapping

• 두 기법 혼합
  • HW 비용 줄이고, Associative mapping 장점 활용
• 작은 TLB 사용
  • PMT: 메모리(커널 공간)에 저장
  • TLB: PMT중 일부 entry들을 적재
    • 최근에 사용된 page들에 대한 entry 저장
  • Locality(지역성) 활용
    • 프로그램의 수행과정에서 한 번 접근한 영역을 다시 접근(temporal locality)또는 인접 영역을 다시 접근(spatial locality)할 가능성이 높음

Hybrid방법 순서

• 프로세스의 PMT가 TLB에 적재되어 있는지 확인
  
  (1) TLB에 적재되어 있는 경우 -> residence bit을 검사하고 page frame번호 확인
  
  (2) TLB에 적재되어 있지 않은 경우 -> direct mapping으로 page frame번호 확인 후 해당 PMT entry를 TLB에 적재함.
  

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의 시작점)

Frame Table

• PID: 누가 가져갔느냐
• AV: 가장 처음으로 비어있는 entry 지칭
• link: 내 다음에 누가 비어있는지 기록(빈 entry에 대한 linked list를 만듬)

Page Sharing

• 여러 프로세스가 특정 page를 공유 가능
  • Non-continous allocation이므로 가능

공유 가능 page

• Procedure(function) pages
  • Pure code(reenter code)를 담고 있는 page
• Data page
  • Read-only data
  • Read-write data
    • ME 발생 가능성 -> 병행성(concurrency)제어 기법 관리하에서만 가능

Example

• Editor 프로그램을 3명이 사용하는 경우
  
• 사용하는 데이터만 따로 저장됨

Data page sharing

• 같은 page frame number를 참조하면 됨

Procedure page sharing

• P1
  • k1: Branch(k1, d)
• P2
  • k2: Branch(k2, d)

=> 같은 메모리 주소임에도 불구하고 Branch(k1, d), Branch(k2, d)로 각각 부르는 주소가 달라짐. P2에서 주황 메모리 위치를 기대하여 Branch(K1, d)를 참조하면 완전히 다른 곳을 참조하게 됨

Problem

• 모두 같은 주소지만 부르는 주소가 달라져 다른 프로세스에서 엉뚱한 곳으로 갈 수 있음

Solution

• 프로세스들이 shared page에 대한 정보를 PMT의 같은 entry에 저장하도록 함(부르는 이름 통일)

Page Protection

• 여러 프로세스가 page를 공유할 때(공유: 보안문제 발생 가능)
  • Protection bit 사용

• 공유되는 페이지에 대한 접근 권한을 적어둠

Summary

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

Segmentation System

1. 개요

• 프로그램을 논리적 block으로 분할(segment)
  • block의 크기가 다름
  • 예) stack, heap, main procedure, shared lib, Etc.

2. 특징

• 메모리를 미리 분할 하지 않음
  • VPM과 유사
• Segment sharing/protection이 용이함
• Address mapping 및 메모리 관리의 overhead가 큼
• No internal fragmentation
  • External fragmentation 발생 가능
    

3. Address mapping

• Virtual address:v = (s, d)
  • s: segment number
  • d: displacement in a segment
• Segment Map Table(SMT)
• Address mapping mechanism
  • Paging system과 유사
    
• secondary storage address: swap device에 저장된 주소
• protection bits: 읽기, 쓰기, 실행, 수정 권한 내역
  

3-1. address mapping(direct mapping) 순서

• 1 프로세스의 SMT가 저장되어 있는 주소 b에 접근
• 2 SMT에서 segment s의 entry 찾음
  • s의 entry 위치 = b + s * entrySize
• 3 찾아진 Entry에 대해 다음 단계들을 순차적으로 실행
  • (1) 존재 비트가 0인 경우(segment fault), swapt device로부터 해당 segment를 메모리로 적재, SMT를 갱신
  • (2) 변위(d)가 segment길이보다 큰 경우(d > ls), segment overflow exception처리 모듈을 호출
  • (3) 허가되지 않은 연산일 경우 (protection bit field 검사), segment protection exception처리 모듈을 호출
• 4 실제 주소 r 계산 (r = as + d)
• 5 r로 메모리에 접근

4. Memory management

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

5. Segment sharing/protection

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

6. Segmentation System - Summary

• 프로그램을 논리 단위로 분할(sgement)
• 메모리를 동적으로 분할
• no internal fragmentation
• Segment sharing/protection 요이
• Paging system 대비 관리 overhead가 큼
• 필요한 segment만 메모리에 적재
  • 메모리 효율적 활용
• segment mapping overhead
  • 메모리 공간 및 추가적인 메모리 접근이 필요
  • 전용 HW 활용으로 해결 가능

7. Paging vs Segmentation

Hybrid paging/segmentation system

1. 개요

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

2. 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과 유사

2-1 SMT

2-2 PMT

2-3 address mapping table 구조

2-4 Direct address mapping

- 메모리 접근 3번 하는 단점이 있다. - 이 단점을 TLB써서 극복하기도 한다.

3. Summary

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