20. 페이지 교체

가상 메모리를 사용하면 최대크기는 하드디스크의 크기 만큼 으로 CPU를 속이는 것이 가능하다.

 

 

유효 접근 시간

 

: CPU가 어떤 주소를 낼 때 운이 좋다면 해당 페이지가 메모리에 있기에 페이지 테이블을 거쳐서 빠르게 읽을 수 있지만

 

어떤 내용은 메인 메모리에 없을 것이고 Interrupt후 OS 인터럽트 루틴으로 점프 후 디스크에 있는 내용을 메모리

 

에 다시 올리고 valid bit 와 프레임 번호 설정등 많을 일을 거쳐야 한다. 따라서 CPU가 어떤 주소를 내면 어떤 주소는 빨

 

리 읽혀질 것이고 어떤 주소는 느리게 읽혀질 것이다. 그렇다면 평균 적으로는 얼마일까? ( = 유효 접근 시간 )

 

 

P : page fault rate = 페이지 부재가 일어날 확률 

 

유효 접근 시간 : (1 - P)*Tm  + P * Tp

 

즉 (페이지 부재가 일어나지 않을 확률 * 메모리에서 읽어오는 시간) + (페이지부재 확률 * 페이지 부재시 일어나는 시간)

 

Tp의 주요 시간은 하드디스크에서 페이지를 가져오기 위해 읽는 시간이다.

 

 

하드디스크의 구조 :

 

원판에 자성물질이 발라져있고 코일을 위에 둬서 ( 디스크 헤더) 코일에 전기를 흐르면 n극 s극을 흐르며

 

값을 저장한다. 읽을 적에는 원판이 빠른 시간으로 회전하면 n극 s극을 지나면서 코일에 전기를 유도. 이 유도를 통해서

 

내용을 읽어낸다.

 

 

seek time : 헤더를 움직여서 안쪽으로 넣어야한다. 우리가 원하는 트랙으로 옮기는 것

 

rotational delay : 헤더를 옮겨도 쭉 돌려서 헤더 밑까지 옮겨야 한다.

 

transfer time : 해당되는 내용이 읽혀진다.

 

제일 시간이 오래 걸리는 곳은 seek time 이 되겠다.

 

 

이렇게 Page fault 가 일어나면 시간이 너무 오래 걸리기 때문에 최대한 부재가 일어나지 않도록 해야 한다.

 

아니면 하드디스크를  플래쉬 메모리 등으로 두어서 seek time을 없애는 방법도 있겠다.

 

 

 

현실적으로는 어떨까?

 

Locality of reference

- 여기서의 reference는 Cpu가 참조하는 주소를 말한다. CPu가 참조하는 주소는 지역에 모여져 있다는 뜻이다.

우리가 캐쉬 메모리를 쓰는 이유와 같다.  메모리 접근은 시간적, 공간적으로 지역성을 가진다.

 

시간적인 지역성은 CPu가 메모리의 한 부분을 읽었다면 그 후에도 그 부분을 읽는다는 뜻. 반복문이 많기 때문이다.

페이지 fault가 일어나서 한번 메모리로 가져오면 반복해도 fault는 일어나지 않을 것

 

공간적인 지역성은 지금 1000번지를 읽었다면 다음은 1000번지 부근을 읽을 것이다. 컴퓨터 명령 길이는 4byte 라 본다면 1004 1008등 그 인접한 구역을 읽기 때문이다.

 

따라서 page fault가 일어날 적에 그 주소만 들고 오는게 아니라 그 인근에 것을 모두 블록 단위로 가져온다면

처음에 page fault가 일어나도 블록 단위로 가져왔기에 그 이후로 page fault가 매우 줄어들 것 ( 추후에 )

 

이렇게 P값은 일반적으로 낮지만 한번 page fault에 소요되는 시간은 길기에 HDD대신 SSD등을 쓸 수도 있겠다.

 

 

 

페이지 교체 ( Page ReplaceMent )

Demand Paging 이란 메인 메모리에 다 올리는 것이 아닌 필요한 부분만 올리는 것이라 하였다. 처음에는 메인 메모리

 

가 비어있지만 필요에 따라 페이지 단위로 프로세스들이 올라오게 되고 언젠가는 메모리가 꽉 차게 될 것이다. 이 경

 

우를 생각해보자.  

어느 한놈을 쫒아내서 backing store로 몰아내야 빈자리가 생기고 필요한 프로세스를 넣을 수 있을 것이다.

 

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

 

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

 

 

victim page :빈 자리를 위해 쫓아낸 페이지

 

 

그렇다면 어떤 페이지를 몰아 낼 것인가?

 

메인 메모리에 올라있는 내용은 CPu가 읽는 경우도 있지만 쓰는 경우도 있다. 하드디스크로 보낼 때는 기록을 해야할까?

 

읽기만 했다면 원래 하드디스크에 있는 한 프로세스의 페이지를 올린 것이니 기록하지 않아도 되지만 CPu에서 실행되다

 

가 메모리에 내용이 바뀌었다면 backing store 로 보낼 때 write를 해야 한다. 따라서 기왕이면 write를 안하는 즉

 

modified 가 안된 페이지를 내리는게 좋겠다.

 

따라서 modified가 됐는지 안됐는지 알 수 있도록 페이지 테이블에 한 비트를 더 달아주자.

 

 

즉 modified가 0이라면 CPu가 읽었는데 바꾸진 않았다는 뜻이된다. 그렇기 때문에 modified가 안됬다는 뜻

 

Modified bit가 1이라면 victim page 가 되었을때 하드 디스크에 적어주어야 한다.

 

 

 

아까 말햇듯 기왕이면 i/o 시간을 절약하기 위해 ( 쓰는 시간 ) modify 되지 않은 페이지를 victim 으로 선택하자

 

 

이제 modified 안된 page 중에 어느 것을 선택해야 할까?

 

 

1. Random 으로 선택

 

2. FIFO  ( First-in First-out) 비어있는 메인 메모리에 p1의 첫 페이지가 올라 왔을 것이다. 이 페이지를 내리는 것

 

3.  OPT ( Optimal )

 

4. LRU ( Least-Recentlty-Used)

 

용어 :

 

Page reference String : 페이지 참조 열

 

예를 들어 CPU가 내는 주소가 100 101 102 432 612 103 104 611 612번지 순서로 읽는다. Paging 을 생각해보면

 

100번지를 내었을때 그 주소는 결국 F와 D로 나뉘어 지고 해당 페이지가 메모리에 몇번지 있는가 로 나타

 

내기 때문에 바이트 주소가 중요한 것이 아니라 페이지 단위가 중요하다. 

 

Page size가 100 바이트라면 (프레임 역시 100 바이트 단위 )

 

100번지의 프레임 번호는 1 , 101 도 d가 1이지 프레임 번호는 1 그리고 432번지는 4 612번지는 6이 될것이다.

 

따라서 페이지 번호  (프레임 번호) = 1 1 1 4 6 1 1 6 6

 

1번째 페이지를 읽는데 fault가 일어나면 메모리로 해당 페이지를 가져왔을 것.

 

이제 연속되어지는 번호들은 fault가 일어나지 않으므로 1 4 6 1 6으로 나타낼 수 있다.

 

이어지는 숫자를 스킵하고 넘어가는 것을 Page refrence string = 1 4 6 1 6 이라고 한다.