페이지 교체 알고리즘

페이지 교체 알고리즘

- 페이지 부재가 발생 했을때 필요한 페이지를 주 기억 장치에 적재 할 때 사용하는 기법이다.

 

대표적인 페이지 교체 알고리즘

1. FIFO(First In First Out)

- 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체하는 기법

 

1,2,3,2,4,1 (할당된 페이지 프레임 수는 3이고, 처음에는 모든 프레임이 비어 있다.)

선입선출 알고리즘을 사용할 경우 페이지 부재 횟수는?

 

 

1번을 제외하고 모든 부재가 발생 했기 때문에 부재 횟수는 5입니다.

먼저 프레임 3개를 체우면 123이 됩니다. 4번째에서 2를 채울려고 했지만 2는 이미 123 에 있기 때문에  부재가 발생하지 않았습니다. 5번째 4를 채울려고 했고 123에는 4가 없었기에 가장 오래된 1을 빼고 4로 채웁니다.(423)

6번째 1을 채울려고 했으며 423에는 1이 없기 때문에  가장 오래된 2를 빼고 1을 채워넣으면 413이 됩니다.

 

2. LRU(Least Recently Used)

- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체하는 기법

 

1,2,3,2,4,1 (할당된 페이지 프레임 수는 3이고, 처음에는 모든 프레임이 비어 있다.)

선입선출 알고리즘을 사용할 경우 페이지 부재 횟수는?

 

 

1번을 제외하고 모든 부재가 발생 했기 때문에 부재 횟수는 5입니다.

먼저 프레임 3개를 체우면 123이 됩니다. 4번째에서 2를 채울려고 했지만 2는 이미 123 에 있기 때문에  부재가 발생하지 않았습니다. 5번째 4를 채울려고 했고 123에는 4가 없었기에 가장 오래된 1을 빼고 4로 채웁니다.(423)

6번째 1을 채울려고 했으며 423에는 1이 없기 때문에 최근에 가장 오랫동안 사용하지 않은  3을 빼고 1을 채워넣으면 421이 됩니다.

 

3. LFU(Least Frequently Used)

- 사용 빈도가 가장 적은 페이지를 교체하는 기법

 

4. NUR(Not Used Recently)

- LRU와 비슷한 방식

- 최근에 사용하지 않은 페이지 교체

- 최근 사용여부를 확인하기 위해 각 페이지마다 참조비트 & 변형비트를 사용

- 참조비트 : 페이지가 호출되었을 때는 1, 호출되지 않았을 때는 0

- 변형비트 : 페이지 내용이 변형되었을 때는 1, 변경되지 않았을 때는 0