가상메모리 #2 - Virtual Storage Methods(Paging system)

Virtual Storage Methods

• Paging system

• Segmentation system
• Hybrid paging/segmentation system

---

Paging System

• 프로그램을 같은 크기의 블록으로 분할 (Pages)
• Terminologies
  • Page
    • 프로그램의 분할된 block
  • Page frame
    • 메모리의 분할 영역
    • 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)
• Address mapping
  • PMT(Page Map Table) 사용
• Address mapping mechanism
  • Direct mapping (직접 사상) : block mapping과 거의유사
  • Associative mapping (연관 사상)
    • TLB(Translation Look-aside Buffer)
  • Hybrid direct/associative mapping

 

Page Map Table (PMT)

• page number : 페이지 번호
• residence bit : 메모리에 적재 유무
• page frame number : page frame번호 ( 메모리 어느 위치에 적재 되어 있는지 )
• secondary storage address : 프로세스가 swap device 어디에 저장되어 있는지

 

Direct mapping

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

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

문제점

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

 

Associative Mapping

• TLB(Translation Look-aside Buffer)에 PMT 적재
  • Associative high-speed memory
  • (PMT를 적재하는 전용 하드웨어라고 생각할 수 있다)
• PMT를 병렬 탐색
• Low overhead, high speed
• Expensive hardware
  • 큰 PMT를 다루기가 어려움

• 다른 과정 없이 page number(p)만으로 TLB안에 저장되어있는 PMT를 병렬로 검색한다.
• 메모리에 접근하지 않기 때문에 빠르고 오버헤드가 적다.

 

Hybrid Direct/Associative Mapping

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

 

• 프로세스의 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

• page frame number : page frame 번호
• allocated : 할당 유무
• PID : 프로세스 id
• AV : 빈공간을 찾기 위한 포인터 ( 가장 처음으로 비어있는 entry 지칭 )
• link : 다음에 빈 entry에 저장 ( linked list로 생각 )
• 할당이 되고나면 AV는 link에 저장된 entry 로 이동

 

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명이 사용하는 경우

• ed1, ed2, ed3는 프로그램 코드 이므로 모두 사용한다.
• 메모리에 한번만 올려 공유해서 사용한다.

 

Data page sharing

Procedure Page Sharing (Problem)

• 같은 위치에 있지만 다른 page number를 가진다 (k1, k2)

 

Procedure Page Sharing (Solution)

• 프로세스들이 shared page에 대한 정보를 PMT의 같은 entry에 저장하도록 함

 

 

Page Protection

• 여러 프로세스가 page를 공유 할 때, 보안문제 발생 가능성
• Protection bit 사용하여 권한 관리

Paging System 

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

 

---

강의

www.youtube.com/watch?v=mTFYeZwPj0s&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=28

www.youtube.com/watch?v=B_QLTChsi04&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=29