#23. 가상 메모리(Virtual Memory)

유효 접근 시간

- Effective Access Time

  * p: probability of a page fault = page fault rate

  * T(ef) = (1 - p)T(m) + pT(p)

(여기서 사실 Tm + Tb로 페이지 테이블을 읽는데 걸리는 시간도 계산해야 하지만, 그 시간은 굉장히 작기 때문에 무시하고 계산했음 : T(m) 메모리 읽는데 걸리는 시간 T(p) 페이지 결함(부재)가 걸려서 처리되는 시간

전기신호를 통해 Page fault발생 시 CPU에 인터럽트 발생 -> OS내부 ISR 실행 -> 하드디스크에서 해당 페이지를 메모리로 로드 바로 이 하드디스크에서 해당 페이지를 찾는데(read) 걸리는 시간이 오래 걸린다.)

 

- 예제

  * T(m) = 200nsec (DRAM)

  * T(p) = 8 msec (seek time + rotational delay + transfer time) 

(HardDisk에서 찾는 시간 : seek time, HardDisk에서 header가 해당 페이지까지 오는데 도는 시간 : rotational delay, 해당 페이지를 찾아서 읽는데 걸리는 시간 : transfer time, seek time이 가장 오래 걸림)

  * T(ef) = (1 - p)200nsec + p8,000,000nsec = 200 + 7,999,800p (nsec)

  * p = 1 / 1,000 => T(ef) = 8.2usec (40배 느림)

(page fault발생 시 실제 메모리에서 찾는 시간 + 하드디스크에서 찾는 시간 때문에 40배 느려짐,

이걸 해결할 수 있는 방법중에 하나가 보조기억장치를 하드디스크가 아닌 플레시 메모리같은걸 쓰는 법도 있다. seek time이 거의 없으므로~)

  * p = 1 / 399.990 => T(ef) = 220nsec (10% 느림)

(실제 P가 굉장히 낮다.)

 

 

지역성의 원리

- Locality of reference

  * 메모리 접근은 시간적, 공간적 지역성을 가진다.

  * 실제 페이지 부재 확률은 매우 낮다

 

- 다른 방법

  * HDD는 접근 시간이 너무 길다 -> swap device로 부적합

  * SSD 또는 느린 저가 DRAM 사용

 

 

페이지 교체 (Page Replacement)

- Demand Paging

  * 요구되어지는 페이지만 backing store에서 가져온다.

  * 프로그램 실행 계속에 따라 요구 페이지가 늘어나고,

  * 언젠가는 메모리가 가득 차게 된다.

 

- Memory full

  * 메모리가 가득 차면 추가로 페이지를 가져오기 위해

  * 어떤 페이지는 backing store로 몰아내고 (page-out)

  * 그 빈 공간으로 페이지를 가져온다. (page-in)

  * 용어: victim page

(메모리에 로드된 페이지를 backing store로 몰아낼 때 반드시 하드디스크에 기록해야 할까? 할수도 않할수도 있다. 이왕이면 않해도 되는 상황에서는 않하는게 좋다. 즉, 메모리 프레임에 올라온 페이지가 변경이 되었다면 victim으로 선택했을 때 해당 페이지의 상태를 backing store에 기록해줘야 한다. 따라서 페이지 테이블에는 modify에 해당하는 비트를 두고, modify 비트가 1이면 backing store에 페이지 상태를 저장해 준다.

보통 victim을 선택할 때 modify되지 않는 페이지를 선택하는게 좋지 않겠는가? 그래야 IO시간을 절약 할 수 있으니까(기록 안해두 됨))

 

- 어느 페이지를 몰아낼 것인가?

  * I/O 시간절약을 위해

  * 기왕이면 modify 되지 않은 페이지를 victim으로 선택

  * 방법 : modified bit (= dirty bit)

 

- 여러 페이지 중에서 무엇을 victim으로?

  * random (성능이 지멋대로일것임)

  * First-In First-Out (FIFO)

  * 그외

  * 용어 : page replacement algorithms 

 

- Page reference string (페이지 참조 열)

  * CPU가 내는 주소: 100 101 102 432 612 103 104 611 612

  * Page size = 100바이트라면

  * 페이지 번호 = 1 1 1 4 6 1 1 6 6 

  * Page reference string = 1 4 6 1 6

(CPU가 해당 순서로 주소를 read한다고 했을 때, Paging을 하므로 Page Number가 중요하다.

Page Number로 100, 101, 102번지 = 1이다. 단지 각각 offset이 0, 1, 2이다. Page 단위가 100Byte이므로..

만약 Page Number가 1인 페이지를 읽는데 Page Fault가 일어나면 Demand Paging이 일어나서 그다음 Page Number가 1인 페이지를 읽을 때는 더이상 Page Fault가 일어나지 않을 것이다.

따라서 Page Reference String을 보면 1 4 6 1 6인 이유는 모든 페이지에 Page Fault가 일어난다고 했을 때, 연속으로 동일한 페이지를 요구할 경우 Page Fault가 일어나지 않을 것이다. 즉, skip을 한다는 것.

이것을 보고 Page reference string이라고 한다.)

 

- Page Replacement Algorithms

  * FIFO (First-In First-Out)

  * OPT (Optimal)

  * LRU (Least-Recently-Used)