[OS] 가상 메모리할당 - Paging System

가상 메모리 (Virtual Storage)

• Non-continuous allocation (비연속 할당)
• 사용자 프로그램을 여러 개의 block으로 분할
• 실행 시, 필요한 block들만 메모리에 적재하고 나머지는 swap device에 존재

기법

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

Address Mapping

Virtual address를 Real address로 변환하는 과정

Virtual address(Logical address) : 연속된 메모리 할당을 가정한 주소
Real address : 실제 메모리에 적재된 주소

-> 사용자/프로세스는 실행 프로그램 전체가 메모리에 연속적으로 적재되었다고 가정하고 실행한다.

Block Mapping

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

Virtual address : v = (b, d)

• b : block number
• d = displacement(offset) in a blcok
  
  

Block map table (BMT)

• Address mapping 정보를 관리한다.
• Kernel 공간에 프로세스마다 하나의 BMT를 가짐
  
  residence bit : 해당 블록이 메모리에 적재되었는지 여부를 나타낸다 (0/1)

Block Mapping 과정

1. 프로세스의 BMT에 접근
2. BMT에서 block b에 대한 항목(entry)를 찾음
3. Residence bit 검사 (0 -> swap device에서 메로리로 가져옴
   1 -> b에 대한 real address 값 a 확인)
4. 실제 주소 r 계산 (r = a + d)
5. r을 이용해 메모리에 접근
   

Paging System

프로그램을 같은 크기의 블록으로 분할 (단위 : Pages)

• Page : 프로그램의 분할된 block
• Page Frame : 메모리의 분할 영역, Page와 같은 크기로 분할한다.

특징

• 논리적 분할이 아닌 크기에 따른 분할이다.
• Page sharing, Protection 과정이 복잡하다.
• Simple and Efficient
• No External Fragmentation (Internal Fragmentation 가능)
  왜 외부 단편화가 발생하지 않나? 궁금하다면

Address Mapping 과정

Virtual address : v = (p, d)
PMT( Page Map Table ) 사용

Direct Mapping 과정

1. PMT가 저장되어 있는 주소 b에 접근
2. 해당 PMT에서 page p에 대한 entry 탐색 ( p의 entry 위치 = b + p * entrySize)
3. 찾아진 entry의 Residence bit 검사
4. p'과 가상 주소의 변위 d를 사용하여 실제 주소 r 형성 ( r = p' * pageSize + d)
5. 실제 주소 r로 주기억장치에 접근
   

단점

• p로 접근한 뒤 다시 한번 p'으로 접근해 메모리 접근 횟수가 2배이다.
• PMT를 위한 메모리 공간이 필요하다.

해결 방안

• Associative Mapping (TLB)
• PMT를 위한 전용 기억장치 사용 -> H/W의 힘을 빌린다.

Associatvie Mapping

TLB(Translation Look-aside Buffer)에 PMT 적재

• Associative high-speed memory

PMT를 병렬 탐색할 수 있어 빠르다.
Low Overhead, high Speed 지만, Cashe Memory 형태라 가격이 비싸다.
-> 연산을 하지 않고 병렬로 빠르게 찾음

이 두개의 장점만을 사용하기 위해 Hybrid Direct/Associative Mapping 방법을 사용한다.

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

Page Sharing

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

공유 가능 Page

• procedure pages (like function)
• Data page
  • Read-only data
  • Read-write data : 병행성 제어 기법 (세마포, 모니터 등) 관리하에서만 가능

Main Memory에 한개만 띄우고 공유해서 사용 가능하다.
주의 ! 주소가 다르기 때문에 function에서 다른 function을 호출하는 경우 엉뚱한 곳으로 이동할 수 있다.

• 권한을 관리하기 위해 Protection bit를 사용한다. (VRWE와 같은 권한을 관리하는 bit)
  

Segmentation system과 Hybrid/segmentation system은 다음 시간에 정리하도록 하겠다.

---

Reference

운영체제:그림으로 배우는 구조와 원리 - 한빛 아카데미