Virtual Storage(Memory)

개념

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

Address Mapping

Continuous allocation

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

Non-countinuous allocation

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

  • Logical address(논리주소)
  • 연속된 메모리 할당을 가정한 주소

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

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

• Address mapping : Virtual address -> Real address

Virtual memory methods

Block Mapping

Block Mapping 순서

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

Paging System

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

특징

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

Address Mapping

• Virtual address: v=(p,d)
  • p : page number
  • d : displacement(offset)
• PMT(Page Map Table) 사용
• Address mapping mechanism
  • Direct mapping
  • Associate mapping(TLB, Translation Look-aside Buffer)
  • Hybrid direct/associate mapping
    

BMT 와 유사하다. secondary storage address는 page 가 swap device 어디에 저장되어 있는지를 나타냄

1) Direct Mapping

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

Paging system의 direct mapping 순서

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

page fault 상태에서는 process 가 running 에서 asleep/block 상태가 되기 때문에 overhead가 큼

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

2) Associative Mapping

• TLB(Translation Look-aside Buffer)에 PMT 적재
  • Associative high-speed memory
• PMT를 병렬 탐색
• Low overhead, high speed
• Expensive hardware (큰 PMT를 다루기가 어려움, size 12bits/4096 entries)

하드웨어의 도움을 통해 병렬적으로 PMT에서 빠르게 page number 탐색할 수 있음

3) Hybrid Direct/Associative Mapping

• 두 기법을 혼합하여 사용

• 작은 크기의 TLB 사용

  • PMT : 메모리(커널)에 저장
  • TLB : PMT 중 일부 entry들을 적재(최근에 사용된 page들에 대한 entry 저장)
  • Locality(지역성) 활용

• 프로세스의 PMT가 TLB에 적재되어 있는지를 확인
  1) TLB에 적재되어 있는 경우, Associative mapping 활용
  2) TLB에 적재되어 있지 않은 경우, Direct mapping 활용
  -> 해당 PMT entry를 TLB에 적재함

Memory Management

• Page와 같은 크기로 분할하여 관리/사용
  • Page frame
  • FPM(Fixed Partition Multiprogramming) 기법과 유사
• Frame table
  • Page frame 당 하나의 entry

• 구성
  • Allocated/available field
  • PID(Process ID) 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 Protection

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

Segmentaion system

프로그램을 논리적 block으로 분할(segment)

• Block의 크기가 서로 다를 수 있음
• ex) stack, heap, main procedure, 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 length: 각각의 segment 크기
• protection bits(R/W/X/A) : 각 segment에 대한 process의 권한

Hybrid paging/segmentation system

• Paging 과 Segmentation의 장점 결합

• 프로그램 분할

  1. 논리 단위의 segment로 분할
  2. 각 segment를 고정된 크기의 page들로 분할

• Page 단위로 메모리에 적재

Address mapping

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

segment는 메모리에 직접 올라가지 않고, page가 올라가므로 residece bit 는 없음. 대신에 PMT address 존재