Chapter4-4

 

가상 메모리 관리(페이지 교체 알고리즘)

 

페이지 교체 알고리즘

-      해당 페이지를 빼고 다른 패이지를 넣기 위한 방법

-      메모리에 모든 페이지를 다 올리지 못하기 때문에 사용

-      프로세스당 할당된 페이지 수가 정해져 있는 상황

 

알고리즘 종류

-      FIFO

-      Optimal(최적)

-      LRU

-      2차기회

-      LFU

 

FIFO ( First - In - First - Out )

-      8 ->8,1 -> 812 -> 312 ***

-      먼저 메모리를 차지하고 있는 페이지를 내보내고 해당 자리에 다음에 들어오는 페이지를 할당한다.

-      Page Fault (페이지 부재)

• 할당된 페이지 안에 접근할 페이지가 없는 경우

-      FIFO의 모순

• 할당된 페이지 수가 많아지면 PageFault(페이지부재)가 많이 일어나지 않는 것처럼 보이지만 사실상 그렇지 않다.
• 무조건 들어온 순서가 가장 오래된 것이 나가는 것 이기 때문
• 다음에 들어올 것이 사용 할 것이라도 다시 내보낸다.

 

Optimal

-      가장 많이 사용되지 않을 페이지를 교체

 

LRU ( Least Recentlyu Used ) - 가장 먼저 사용된 페이지를 내보냄

-      페이지 부재가 일어난 곳부터 계산

-      스택 사용

• 접근을 할 때 마다 스택에서 해당 페이지 번호를 가장 위로 올린다.
• 페이지 부재가 일어난 경우 가장 밑에 있는 페이지를 빼고 가장 위에 페이지를 쌓는다.

-      시간 사용

• 접근이 될 때 마다 해당 페이지에 시간을 더해준다.
• 패이지 부재가 일어난 경우 가장 시간이 적은 페이지를 빼고 해당 위치에 가장 높은 시간을 부여한다.

 

2차 기회 ( Second Chance ) - 구현상 가장 좋은 방법

-      처음에 페이지가 할당되면 비트를 사용해서 0을 부여한다.

-      다음에 참조가 되면 0에서 1로 변경한다.

-      원형 Queue의 형태

-      한 번도 참조가 되는 경우가 없으면 FIFO와 같은 형식으로 변경

-      기회가 지난 후에는 비트를 0으로 변경시킨다.

-      페이지가 자주 참조되는 페이지는 참조비트를 1로 해주고 그 다음에는 다시 0으로 변경한다.

 

LFU ( Least Frequently Used ) - 가장 덜 자주 사용된 페이지를 내보냄

-      사용할 때 마다 카운트를 함

-      가장 적게 카운트 된 페이지를 내보냄