#20. 페이징(Paging)

주소 변환(Address Translation)

- 예제

  * Page size = 4bytes

  * Page Table: 5 6 1 2

  * 논리주소 13번지는 물리주소 몇 번지?

Page Number	Frame Number
0	5
1	6
2	1
3	2

13 = 1101(2)

d(displacement) = 01(2) = 1

p(page number) = 11(2) = 3, frame number = 2 = 10(2)

Page Size = 4bytes 이므로,  d는 하위 2비트이다.

logical address => physical address 변환

1101(2) => 1001(2) = 9

답 : 9번지

 

- 예제

  * Page Size = 1KB

  * Page Table = 1 2 5 4 8 3 0 6

  * 논리주소 3000번지는 물리주소 몇 번지?

Page Number	Frame Number
0	1
1	2
2	5
3	4
4	8
5	3
6	0
7	6

3000  = 1011_1011_1000(2)

Page Size = 1KB 이므로, d는 하위 10비트이다. 

d(displacement) = 11_1011_1000(2) = 1976

p(page number) = 10(2) = 2, frame number = 5 = 101(2)

logical address => physical address 변환

11_1011_1000(2) -> 1_0111_1011_1000(2) = 6072

답 : 6072번지

 

* 물리주소 0x1A53 번지는 논리주소 몇 번지?

0x1A53 = 1_1010_0101_0011(2)

d(displacement) = 10_0101_0011(2) = 595

p(frame number) = 110(2) = 6, page number = 7

physical address => logical address 변환

10_0101_0011(2) = 595번지

답 : 595번지 = 0x253

 

 

내부단편화, 페이지 테이블

- 내부 단편화 (Internal Fragmentation)

  * 프로세스 크기가 페이지 크기의 배수가 아니라면,

  * 마지막 페이지는 한 프레임을 다 채울 수 없다.

  * 남은 공간 = 메모리 낭비

- 페이지 테이블 만들기

  * CPU 레지스터로

  * 메모리로

  * TLB (Translation Look-aside Buffer) 로

  * 테이블 엔트리 개수 vs 변환 속도

  * 연습: TLB 사용 시 유효 메모리 접근 시간(Effective Memory Access Time)

    Tm = 100ns, Tb = 20ns, hit ratio = 80%

 

CPU 레지스터로 페이지 테이블을 만들면 주소변환이 빠르겠지만, CPU 레지스터의 크기가 그렇게 크기 않기 때문에 페이지 갯수에 한계가 있다. 

메모리로 페이지 테이블을 만들면 주소변환은 상대적으로 느릴 수 있지만, 페이지 테이블 크기에 거의 한계가 없다.(주소 변환이 느릴 수 밖에 없는 이유는, 페이지 테이블을 read하려면 메모리에 접근 해야 한다, 그리고 실제 해당 물리 주소에 접근하려고 또 메모리에 접근해야 하므로 2번 접근해야 한다.)

CPU 레지스터에로 페이지 테이블을 만들기에는 한계가 명확하니, 메모리로 만들어야 하는데, 메모리는 접근이 느리기 때문에 이를 해결하기 위한 캐쉬 메모리에 쓰이는 SRAM을 활용한다.

메인 메모리는 DRAM으로 만듬.

 

별도의 SRAM 칩으로 페이지 테이블을 만든다. 이를 TLB라고 한다. CPU 레지스터보다는 페이지 갯수가 많을 거고, 메모리 보다는 변환 속도가 빠를것이다.

 

TLB사용 시 유효 메모리 접근 시간(메모리에서 어떤 내용을 읽어오는데 걸리는 유효한 시간)을 계산해보자.

Tm = 100ns, Tb = 20ns라고 한다면 (Tm 은 메모리 접근 시간, Tb는 버퍼 접근 시간)

ex) CPU가 어떤 주소를 read한다고 한다면, 페이지 테이블에는 페이지 번호와 프레임 번호가 매핑되어 있다고 하자.

CPU가 페이지 테이블(버퍼)에 접근하는데 걸리는 시간을 Tb라고 하고, 페이지 테이블로부터 실제 메모리 주소를 얻어온 후 해당 물리주소에 접근하는데 걸리는 시간을 Tm 이라고 한다.

 

EMAT = hit x (Tb + Tm) + (1 - hit) x (Tb + Tm + Tm)

1 - hit(hit 되지 않을 확률) : cpu가 어떤 논리주소를 읽으려고 하는데 그 주소가 페이지 테이블에 없다. 이유는 페이지 테이블은 메모리에서 일부만 들고오기 때문에, 이걸 miss됬다 라고 하는데, miss될 확률을 의미한다.

 

hit할 확률 x (페이지 테이블 접근 시간 + 얻어온 물리주소로 메모리 접근 시간) + miss 확률 x (페이지 테이블 접근 시간 + (페이지 테이블에 매핑되는 부분이 없음) 메모리 접근하여 다시 얻어오는 시간 + 얻어온 물리주소로 메모리 접근 시간)

 

hit ratio = 0.8 이라면

0.8 x (100 + 20) + (1 - 0.8) x (100 + 20 + 100) = 140ns

Tm = 실제 메모리를 읽는데 걸리는 시간이 100ns인데 지금 페이징을 이용하였을 때 걸리는 평균 시간이 140ns이다. 

40ns만큼 느려졌지만, 그럼에도 불구하고 외부 단편화를 해소하는데 감수한 것.

너무 실망하지 않아도 되는게 실제 현실에서는 사실 hit ratio가 0.95이상이다.