[OS] 9. Virtual Memory - Paging system

Non continuous allocation (Virtual storage methods)

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

 

Paging system

• 프로그램을 같은 크기의 블록으로 분할(Pages)
• Page: 프로그램의 분할된 Block
• Page frame: 페이지와 같은 크기로 잘려진 메모리 상의 공간

연속해서 올라가 있는 것이 아닌 (non-continouns allocation)

Paging system 특징

• 논리적 분할이 아님 (크기에 따른 분할)
• Segmentation에 비해 Page 공유(sharing) 및 보호(Protection)과정이 복잡함
• Segmentation에 비해서 Simple and Efficient (같은 크기로 잘랐기 때문에)
• No external fragmentation (Internal fragmentation 발생 가능 (메모리에 해당 프로그램의 크기만큼 사용하기 때문에))

Paging system in Windows

Paging System 에서 Address Mapping

• Block 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)

(residence bit: 메모리에 올라가 있는지 확인, page frame num: 어디에 올라가 있는지 알려줌

secondary storage address :프로세스에 대한 모든 페이지는 swap device에 저장되어있다.

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 (페이지를 읽는데 실패함)), swap device에서 해당 page를 메모리로 적재 PMT를 갱신한 후 3-2 단계 수행
   2. Residence bit=1인 경우, 해당 entry에서 page frame번호 p'를 확인
4. p'와 가상 주소의 변위 d를 사용하여 실제 주소 r형성 (r=p' * pageSize +d)
5. 실제 주소 r로 주기억 장치에 접근

(page fault: context wsitching 발생(I/O)-> Overhead)

문제점

• 원하는 데이터에 접근할 때 커널상에 존재하는 메모리에 접근 후 메인 메모리에 접근하게 되는데 메모리를 두번 접근한다. => 필요횟수보다 메모리 접근 횟수가 2배 => 성능저하
• 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)에 적재 - Associative high speed memory(PMT를 탐색하기 위한 전용 하드웨어)
• PMT를 병렬 탐색
• Low overhead, high speed

• PMT를 TLB에 넣는다.
• 이후에 p라는 페이지를 요청하면 page number(p)를 PMT에서 병렬로 동시에 탐색해서 결과를 한번에 내보낸다.
• TLB에서 해결되기 때문에 메모리 접근횟수도 줄어든다. (오버헤드도 적어짐)
• address apping을 빨리하게 된다.
• Expensive hardware (큰 PMT를 다루기 어려움)

 

Hybrid direct/associative mapping

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

 

1. 프로세스의 PMT가 TLB에 적재되어 있는지 확인
2. TLB에 적재되어 있는경우 (Associative Mapping 사용)
   • residence bit를 검사하고 page frame번호 확인
3. TLB치에 적재되어 있지 않은 경우
   • Direct Mapping으로 page frame 번호 확인
   • 해당 PMT entry를 TLB에 적재함

 

Address mapping

• Virtual address: v = (p,d)
• Address mapping
• Address mapping mechanism
  
  • Direct mapping (직접 사상)
  • Associative mapping (연관 사상)
  • Hybrid direct/associative mapping
• Memory management
• Page sharing protection

 

Memory management

Page와 같은 크기로 미리 분할 하여 관리/사용

• Page frame으로 미리 잘라놓는다. (page를 담는 틀)
• FPM기법과(Fixexd partition multiprogramming) 유사

Frame table (관리하기 위한 data structure)

• Page frame당 하나의 entry를 가짐
• 구성
  • Allocated(할당됬는지)/available field(사용할 수 있는지)
  • PID field
  • Link field: For free list(사용가능한 fp들을 연결)
  • AV: Free list header(free list의 시작점)

 

Page sharing

함수X를 프로그램 A,B,C가 사용한다면 메모리에 각 프로그램이 사용하는 함수 X를 올려둘 것이다

이렇게 하면 중복된 메모리 낭비를 유발한다. 

그렇다면 공유된 함수X를 메모리 상에 올리고 프로그램 A,B,C가 공유해서 사용하면 효율적일 것이다

=> paging sharing의 개념 (이 개념이 가능한 이유는 non-continuous allocation이기 때문이다)

(contiuous allocation이였다면 부분 부분 잘라서 공유할 수 없을 것이다)

 

공유가능 page

• Procedure pages (Pure code (reenter code)
• Data page(데이터 영역도 공유)
  
  • Read only data (읽기만 할 수 있는 형태)
  • Read write data (읽기, 쓰기 가능한 형태 => 여러명이 사용하면 mutual exclusion문제가 발생할 것)
    • 병행성(concurrency) 제어 기법 관리하에 사용

 

Editor 프로그램을 3명이서 사용하는경우 - Page sharing (example)

• 한글 에디터를 ed1,ed2,ed3 페이지는 모든 프로세서가 공유할 것이다. 각자 메모리 상에 올릴 수 있지만
• 하나만 메모리에 올려두고 모두가 공유해서 사용하면 될 것이다.
• 실제로 작성하는 문서(데이터)들만 서로 다른 곳에 기록을 해 두면 훨씬 메모리를 효율적으로 사용할 수 있다.
• => 기본적인 paging sharing의 개념

 

Data page sharing

data를 공유할 때 page map table 관점에서 생각한다면 두개의 프로세스가 자기만의 PMT를 가지고 있지만

page frame number를 같은 것을 사용하여 같은 영역을 접근하는 효과를 나타낼 수 있다.

 

Procedure page sharing (solution)

마찬가지로 같은 페이지 frame number를 적음으로써 같은 프로시저 페이지를 공유할 수 있다.

 

((X, d)는 메모리상에 x프로세스가 시작하는 지점부터 d까지 할당된 범위를 나타냄)

branch입장에서 k1에서 d만큼 떨어진 것, k2에서 d만큼 떨어진 것 둘다 같은 page frame을 나타냄

 

그런데 branch에 (k1,d),(k2,d) 서로 다른 페이지 번호를 지칭하고 있다

Branch(k1,d)로 적혀있었으면 PMT for 1에서는 문제가 없는데

PMT for 2에서 문제가 발생한다. Branch(k1,d)를 PMT for 2에서 본다면 엉뚱한 곳에 가서 데이터를 읽을 것이다.

 

서로 지칭하는 이름이 다름으로써 프로시저를 공유했을 때 이러한 문제가 발생할 수 있다.

이런 문제를 해결하려면? 부르는 이름을 통일 시킬까?

 

프로세스들이 공유하는 페이지에 대한 정보를 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활용으로 해결 가능 (하드웨어 비용 증가)

프로그램의 논리적 구조 고려하지 않음 을 해결한 기법 => Segmentatiuon System

 

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---