9-1. Virtual Memory (Non-continous allocation)_Paging system

Non-continuous allocation

사용자 프로그램을 여러 개의 block으로 분할하여 할당하는 것을 말하며 실행시마다 필요한 block들만 메모리제 적재하고 나머지는 Swap device에 존재하게 하는 가상 메모리가 이를 따른다.

 

메모리 할당 기법으로는 Paiging, Segmentation, Hybrid Paging/segmentation 이 있다

 

Virtual address(가상주소)/relative address는 논리 수조로 연속된 메모리 할당을 가정한 주소이다.

Real address(실제주소)/physical(absolute address 는 실제 메모리에 적재된 주소로 연속되지 않을 수 있다.

 

* Address mapping은 가상 주소를 실제 주소로 바꾸어 주는것이다.

 

Block Mapping 

사용자 프로그램을 block 단위로 분할 /관리하는 것으로서 각 block에 대한 address mapping 정보를 유진 한다.

구성은 다음과 같다.

virtual adreess V = (b, d) 

가상 주소 V는 b(block number)와 d(displacement(offset)로 구성되어있다.

b는 블록의 시작점을 가리키고 d는 그 시작점으로부터 원하는 가상 죽소가 얼마나 떨어져 있는지를 가리키는 offset정보를 담고 있다.

 

프로세스마다 커널 안에 BMT(block map table)를 가지고 Address mapping정보를 관리한다.

 BMT 를 이용한 block mapping 

1. 프로세스의 BMT접근
2. BMT에서 block b에 대한 항목(entry)을 찾음
3. Residence bit 검사 
   0(없다면?)-> swap device에서 해당 블록을 메모리로 가져와 BMT업데이트  후 재검사.
   1(있다면?) -> BMT에서 b에 대한 real address 값(a) 확인
4. 실제 주소 계산(a+d)
5. 4를 이용하여 메모리 접근

Paging system

page : 프로그램의 분할된 block

page frame: 페이지와 같은 크기로 분할된 메모리의 분할 영역

페이징 시스템 특징

• 논리적 분할이 아닌 크기에 따른 분할(Windows page size = 4KB)
  segmentation 대비하여 page공유 및 보호 과정이 복잡
• segmentation 대비 간단하고 효율적이다.
• 외부 단편화가 존재하지 않는다. 단 내부 단편화는 발생 가능

페이징 시스템은 왜 배울까?

사용자가 실제 이렇게 사용한다. 

 

Paging system Address Mapping

블록 맵핑과 흡사하다.

Virtual address : V = (p, d)로 

p는 page number d는 offset을 나타낸다.

주소 매핑을 위해 PMT(Page Map Table)을 사용한다.

 

주소 매핑을 하는 기술로는 

Direct mapping과 Associateve mapping, Hybrid direct/associative mapping 기술이 있다.

 

Direct mapping

블록 맵핑과 유사하다.

1. 해당 프로세스의 PMT가 저장되어있는 주소 b에 접근
2. 해당 PMT에서 Page p에 대한 entry 찾음
3. 찾아진 entry의 존재 비트를 검사
   존재하지 않는다면? -> page fault ->swap device에서 해당 page를 메모리로 적재 후 갱신
   존재한다면? 해당 entry에서 page frame 번호를 확인
   
4. page frame 번호와 가상 주소의 offset(d)를 사용하여 실제 주소 r형성
5. 실제 주소 r로  mainmemory 접근

page fault는 context switching을 발생시켜 overhead를 일으키므로 줄여야 한다.

 

디렉트 맵핑의 문제점

• 원하는 데이터 접근을 위해 메모리 접근 횟수가 2배(성능 저하)가 된다.
• PMT를 위한 별도의 메모리 공간이 필요하다

해결방안.
Associative mappint(TLB)

PMT 위한 전용 기억장치 공간(dedicated register or cache) 사용

등

 

Associative Mapping

TLB(translation Look-aside Buffer)에 PMT를 적재하여 높은 메모리 속도를 가진다. PMT를 위한 작은 H/W로 생각할 수 있다.

PMT탐색 시 병렬로 탐색해 overhead가 적고 높은 속도를 가지지만 비싸다.

비싼 만큼 용량을 키우기 어려워 큰 PMT를 다루기가 어렵다.

Hybrid direct/associative mapping

두 기법을 혼합하여

PMT 중 최근 사용된 page들 즉 Locality를 활용하여 부합하는 entry만 TLB에 적재하여 HW 비용은 줄이고  Associative mapping의 장점을 활용한 방법이다.

 

프로세스의 PMT가 TLB에 적재되었는지를 먼저 확인, 있다면 Associated mapping을 하고

없을 경우 direct mapping기법을 활용하여 page frame 번호를 확인하고 해당 PMT entry를 TLB에 업데이트한다.

Hybrid direct/associative mapping

Memory management

메모리는 Page와 같은 크기로 미리 분할(page frame) 하여 이들을 Frame table의 형태로 관리한다.

각 page frame당 하나의 entry를 가지며 Allocated/available field, PID field, Link Field, AV로 구성되어있다.

AV는 프레임 테이블에서 비어있는 위치를 가리키는 포인터이며 링크는 그다음 빈 공간을 연결한다.

 

Page Sharing

Non-continuous allocation 이므로 page공유가 가능하다. 예를 들어 여러 프로세스에서 공통으로 사용하는 func가 있다면 각 프로세스마다. 똑같은 func을 메모리에 올리는 것이 아닌 func페이지를 하나만 올려두고 여러 프로세스가 공유할 수 있다.

 

공유 가능한 page

• procedure page(function)
  > pure code
• Data page
  > 읽기만 가능한 데이터 이거나, 병행성 제어 기법 관리하에 있는 읽기 쓰기 가 가능한 데이터 

 

문제점 1 : procedure 페이지를 공유하는데 프로세스들이 각 PMT에 공유되는 페이지에 대해 다른 entry를 저장할 경우 원하는 프러시저를 사용 못하는 프로세스가 발생할 수 있다.

 

해결책 >각 프로세스가 공유하는 프러시저에 대해서는 PMT에 같은  entry에 저장하도록 함으로써 해결 가능하다.

 

 

문제점 2 : 여러 프로세스가 page를 공유하므로 보안 문제가 발생한다. 

해결책 > protection bit를 사용하여 해결한다.

페이징 시스템 요약

장점

프로그램을 고정된 크기의 block으로 분할하고 메모리를 block에 맞는 size로 분할하므로 외부다 편화 문제가 없고

메모리 통합/압축 등의 작업이 불필요하다.

또한 필요한 page만 page frame에 적재하여 사용하기 때문에 메모리의 효율적 활용이 가능하다.

 

단점

프로그램을 고정된 크기로 분할할 뿐 논리적 구조는 고려하지 않는다. 따라서 Page sharing/protection이 복잡하다.

PMT활용을 위한 별도의 메모리 공간 및 메모리 접근 시 2번의 접근이 발생하여 이를 TLB라는 전용 HW로 극복하지만 하드웨어 비용이 증가하는 단점이 있다.