[운영체제] 9. Paging (and Beyond Physical Memory)

Paging

주소 공간을 고정된 크기의 page 단위로 물리 메모리의 frame에 불연속적으로 매핑하는 방식이다. Segmentation의 경우 다중 프로세스간 공유와 보호라는 장점이 있지만, 외부 단편화가 발생한다. 하지만, paging은 외부단편화가 없고 하드웨어 지원이 간단하다. 그리고 이후에 학습할 demand paging을 하기에도 쉽다. Paging의 주소 변환은 page table을 이용한다.

Page table은 각 page가 물리 메모리의 어느 frame에 위치하는지 나타낸다. 또한, Page table은 각 프로세스 당 하나씩 존재한다.

 

Paging에서의 주소 변환

예를들어, 가상메모리는 총 64B의 크기이며 page의 크기는 16B이다. 그리고 물리 메모리는 총 128B이며 frame의 크기는 page와 같은 16B이라고 가정해보자. 따라서, 주소공간을 표현하기 위한 비트는 6비트이며, 주소 공간에는 4개의 page가 존재하므로 이를 구별하기 위해 2개의 비트를 사용한다.

물리 주소 = VPN X Page size + Offset

가상주소 4, 44, 21을 각각 변환해보면

4= 00 0100(2). VPN=3, offset=4이다. 따라서, 3x16+4=52가 물리주소이다.

44= 10 1100(2). VPN=5, offset=12이다. 따라서, 5x16+12=92가 물리주소이다.

21= 01 0101(2). VPN=7. offset=5이다. 따라서, 7x16+5=117이 물리주소이다.

 

Page table management

Page table을 프로세스마다 생성되어  PCB에 존재한다. 그리고 PCB은 메모리의 커널 영역에 존재한다.

Page table이 PCB에 존재하여 메모리에 존해하는 이유는 page table의 크기가 너무 크기 때문이다. 예를들어, 32bit-CPU, 4KB의 page size를 가정하는 경우, offset은 12bit이며 VPN은 20bit이다. 따라서, page table 내부에는 2의 20제곱 개의 Page table entry가 존재한다. PTE는 보통 4B이므로 page table은 결국 4MB임을 의미한다. 만약 여기서 프로세스 100개가 수행된다면... 왜 메모리에 있어야 하는지 알 수 있을 것이다.

 

Page table의 메모리에 존재하여 생기는 이슈

• 가상주소의 물리주소 변환을 위해 page table을 위한 메모리 접근이 추가된다. (2번의 메모리 접근) → TLB로 해결
• Page table의 크기가 메모리에 존재하지만 여전히 크다. → Multi-level page table or Inverted page table로 해결

PTE(Page table entry): page table에 존재하여 page가 물리 메모리의 어느 frame에 위치하는지 알 수 있다. 이외에도 추가적인 비트를 통해 다른 정보도 포함한다.

• P(Present bit) : 해당 페이지가 물리 메모리에 존재하는지 확인 가능.
• R/W (Read/Write bit) : 해당 페이지 read/write가 가능한지 여부
• U/S (User/Supervisor bit): 유저, 커널모드 중 어느 모드에서 접근 가능한지
• A (Access bit): replacement를 위해 활용
• D (Dirty bit): 페이지가 수정되었는지 확인 가능 → Delayed write과 관련
• Valid bit: 페이지가 합법적인지 확인 가능

Present bit와 valid bit의 차이점

• Present bit는 해당 페이지가 물리메모리에 존재하는지 존재 여부를 알려주는 비트이다. 존재하지 않을 경우에 접근 시 page fault가 발생한다. 합법적인 접근이며 없는 page를 메모리에 올리고 다시 접근한다.
• Valid bit는 해당 페이지가 합법적인지 알려주는 비트이다. 0일 때 접근할 경우 합법적이지 않은 접근이어서 segmentation fault로 인해 프로그램이 죽게된다.

TLB(Translation Lookaside Buffer)

TLB는 MMU의 한 부분이며, 최근에 사용한 page와 frame의 쌍을 저장하는 캐시 공간이다. 마치 주소 변환을 위한 캐시라고 생각하면 편하다. 예를들어, page 3번이 frame 7번에 있었다면, <3,7>이라는 쌍을 저장한다. 이후에 3번 page를 접근하면 page table의 접근, 즉 메모리의 접근이 없어진다. (TLB는 앞서 말한듯 MMU의 일부로 MMU는 CPU에 존재하여 접근이 매우 빠르다.)

 

예제. TLB의 성능

int a[10]; //4B X 10
int sum=0;
for(i=0; i<10; i++)
	sum+=a[i];

Page size는 16B로 위처럼 배열 중 4개의 아이템을 담을 수 있는 공간이다.

1. a[0]의 접근 → TLB miss로 두번의 메모리 접근
2. a[1],a[2]의 접근 → TLB hit
3. a[3],a[7]의 접근 → TLB miss로 두번의 메모리 접근
4. a[4],[5],[6],[8],[9]의 접근 → TLB hit

위를 통해, TLB hit rate = 70%임을 확인할 수 있다. 하지만, 실제로는 page 크기가 훨씬 크기에 거의 99%에 육박한다. 따라서, 거의 대부분의 경우에 메모리는 한번만 접근한다.

 

문맥교환에서의 TLB 관리

TLB는 현재 동작 중인 프로세스에만 유효하다. 예를들어, 프로세스1에서 <10,100>, 프로세스2에서 <10,170>이다.(<page number, frame number>). 이때, 프로세스1이 동작중에 가상주소 10번을 접근하다 프로세스 2로 문맥교환이 발생하여 프로세스2의 가상수조 10번을 접근하려 한다면 아래 Case 1처럼 둘다 VPN 10에 대한 유효한 비트가 1일 경우 문제가 발생할 것이다.

 이를 처리하기 위해 대표적으로 두가지 방법이 사용된다.

1. Case2: 문맥교환 전에 모든 valid bit를 0으로 바꾼뒤, 해당하는 PTE의 valid bit를 1로 바꾼다.
2. Case3: ASID(Address space IDentifier)를 사용하여 구분하는 방식으로,  flush 작업을 없애 case2에 비해 더 효율적이다.

---

Smaller Page Tables

위에서 다룬 문제중 첫번째 문제인 메모리를 두번 접근하는 문제는 TLB로 해결했다. 이번에는 Page table의 크기가 너무 큰 문제를 해결하기 위한 해결책을 소개한다.

 

Page table을 줄이는 해결책

1. Bigger pages
2. Hybrid approach: segmenation + paging
3. Multi-level page table
4. Inverted page table

 

 

1. Bigger pages

가장 단순한 방법으로 page의 크기를 크게 한다. 이렇게하면, 물리메모리의 frame이 적어지고 결국 매핑을 위한 PTE가 줄어들어 page table의 크기가 작아진다. 장점으로는 간단하며 TLB 히트율이 좋다. 단점으로는 내부 단편화가 심하며 로딩 시간이 길다.

 

2. Hybrid approach: segmenation + paging

Segment의 limit register 정보로 page table의 크기를 줄일 수 있다. 간단한 예로, 16KB의 주소공간과 1KB의 page 크기를 갖는 시스템이 있다고 하자. 그리고 현재 4개의 page를 사용 중이며 12개의 page는 사용하지 않는다. 사용 중인 4개의 page 들은 개별적으로 frame에 배치되어있다. 이때, 앞서 말한듯 12개의 page가 비유효하고 이러한 낭비되는 공간을 줄이기 위해 각 segment 단위 별로 limit를 써주어 유효한 PTE만 존재하게 된다.

(Code: base=0, limit=1K → 1PTE / Heap: base=4K, limit=5K → 1PTE / Stack: base=14K, limit=16K → 2PTE)

 

3. Multi-level Page Table

기존의 선형적인 page table 대신 구조적인 multi-level 구조를 사용한다. 가장 상위 계층에 page directory가 존재한다. page directroy의 실제 할당 되지 않은 많은 수의 page table을 valid bit를 이용하여 줄인다. 기존의 주소 변환 방식에서 VPN 중 일부는 page directroy를 검사하며  나머지는 page table을 검사한다.

 

실제 얼마나 많은 공간이 절약되는지 확인해보자. 예를들어 16KB의 주소공간과 page는 64B의 크기를 갖는다면 256개의 PTE가 존재한다. 그리고 실제 사용하는 page는 6개라고 가정하자. 한 page에 존재하는 PTE는 64/4=16개이며, 이는 즉 256개의 PTE를 담기 위해 16개의 page(frame)이 필요함을 의미한다. 즉, page table은 16 frame이 필요한 셈이다. 하지만, multi-level page table을 사용할 경우 directory를 위해 1개의 frame과 page table을 위해 2개의 frame을 사용하여 총 3개의 frame만 필요하다.

Multi-level Page Table의 주소 변환 방법

위의 예시와 같은 시스템의 경우 가상 주소를 표현하기 위한 bit는 14bit이며, 페이지 크기는 64B이기 때문에 offset은 6bit이다. 그리고 VPN은 디렉토리와 Page table을 위한 용도로 나뉘는데, 1개의 프레임에 16개의 PTE가 존재하기 때문에 4bit를 사용한다. 그리고 디렉토리의 PTE 또한 16개이기 때문에 4bit를 사용한다.

아래의 변환을 수행해보자

100 = 00 0000 0110 0100(2). Directory:0->100/PT:1->23/offset:100100=36. 따라서, 23*64B+36

300 = 00 0001 0010 1100(2). Directory:0->100/PT:4->80/offset:101100=44. 따라서, 80*64B+44

200 = 00 0000 1100 1000(2). Directory:0->100/PT:3->Invalid

1030 = 00 0100 0000 0110(2). Directory:1->Invalid

 

계층이 더 많아질 수록 디렉토리가 많아지는 방식이다.

 

4. Inverted Page tables

기존의 경우, page를 frame으로 매핑하여 page table은 프로세스당 한개씩 존재했다. 하지만, inverted page table을 사용할 경우 frame을 page로 매핑하여 page table은 시스템에 단 한개만 존해하게 된다.

 

---

Swap

디스크에 존재하는 한 공간의 이름이다. 시스템을 수행 중에 메모리의 공간이 부족해지면 사용하지 않는 page나 프로세스드를 디스크의 swap공간으로 내리게 된다. 이러한 기법으로 사용자에게 가상의 큰 주소 공간을 갖고 있는 것과 같은 환상을 제공한다. (실제 학습한 내용으로는 상태 전이도에 의해 프로세스 전체가 suspend 된다고 배웠지만, page 단위로 suspend하는게 일반적이다.)

Demand paging(demand loading)

Page는 어느 frame에 매핑된다는 정보만 존재하고 실제 page는 swap공간에 존재한다. 그리고 실제 수행중에 page fault가 발생하면 그때 lazy manner로 page를 메모리로 올린다.

 

Cache Management

위처럼 메모리에 공간이 부족할 경우 어떤 page를 suspend할 지 결정하여야 한다. 이러한 결정은 hit ratio가 극대화 하는 방향으로 관리되어야 한다.

 

대표적인 정책

1. Optimal replacement policy(MIN)
2. FIFO(First In First Out)
3. Random
4. LRU(Least Recently Used)

교체 정책 비교를 위해 사용될 workload. Reference string: 01201303121, cache size: 3 frames

 

1. Optimal replacement policy(MIN)

가장 미래에 접근하리라 예상되는 page를 내리는 방식이다. 가장 이상적인 교체 정책이지만 실제 구현하기가 굉장히 어렵다.

Hit ratio=6/11=54.5%

2. FIFO(First In First Out)

도착한지 가장 오래된 page를 내리는 기법이다. 간단하지만 지역성을 고려하지 않아 성능이 좋지않다. 그리고 Belady's anomaly가 발생한다.

hit ratio=4/11=36.4%

Belady's anomaly란, 원래 어떠한 변화를 주면 더 긍정적인 결과를 나아야 정상이지만 그렇지 않은 경우를 뜻하는 용어이다. FIFO의 경우 frame 크기를 증가시키면 되려 성능이 나빠진다.

3. Random

무작위로 page를 내린다. 간단하지만 FIFO와 마찬가지로 지역성을 고려하지 않았으며 예측이 불가능하다.

hit ratio=5/11=45.4%

4. LRU(Least Recently Used)

가장 과거에 사용되었던 page를 내리는 방식이다. 장점으로는 지역성(temporal locality)을 고려하여 히트율이 어느 정도 보장되지만 단점으로는 loop에서는 성능이 좋지 않다. (비슷한 정책으로는 LFU(Least Frequently Used)가 존재한다.)

---

Thrashing

시스템이 할 일을 제대로 못하고 page in-out만 반복하는 현상. 물리메모리의 공간이 크기 않아서 발생하는 문제이다. 프로그램을 수행할수록 성능이 좋아지다가 특정 시점을 기준으로 CPU 성능이 폭락한다. (무수한 page fault로 인한 I/O 작업의 증가로 인해 발생)

 

이는 working set으로 해결하게 된다. working set은 한 프로세스가 원할히 수행되기 위한 최소 page 수이다. 모든 working set의 합은 모든 프로세스를 원할히 수행하는 최소 page 수이며, 이는 원할히 수행하기 위한 최소 물리 메모리의 크기를 의미한다. 

D: 총 working set의 합. m: 시스템에서 이용가능한 page의 수

• D>m: 일부 프로세스를 suspend 한다.
• D<m: 다른 프로세스를 시작할 수 있다.