[운영체제] 페이지 대치 알고리즘 비교 (선입선출, 최적페이지, 최근최소사용, LRU 근접)

소개글

"[운영체제] 페이지 대치 알고리즘 비교 (선입선출, 최적페이지, 최근최소사용, LRU 근접)"에 대한 내용입니다.

목차

① 선입선출 대치 알고리즘
② 최적 페이지 대치 알고리즘
③ 최근최소사용 알고리즘
④ LRU 근접 알고리즘

본문내용

가장 간단한 방식의 페이지 대치 알고리즘으로서 가장 오래 주 기억 장소에 있던 페이지를 대치하는 방식이다. 운영체제에서는 현재 메모리의 모든 페이지 목록을 보유한다. 또 메모리에는 가장 오래 저장된 목록의 헤드 페이지와 가장 최근에 도착한 꼬리 페이지를 가지고 있다. 페이지 폴트 시 오래된 헤드의 페이지가 제거되고, 새로운 페이지가 목록 끝에 추가된다. 이렇게 페이지는 선입선출 큐에 의해 관리되는데, 이 큐의 크기는 사용 가능한 메모리 프레임의 수다. 그러나 이런 선입 선출 대치 알고리즘은 자주 참조해야만 하는 페이지를 단순히 먼저 적재되었다는 이유만으로 삭제해 버릴 가능성이 다분하기 때문에 단순한 형태의 선입 선출 대치알고리즘은 별로 사용되지 않는다.

<중 략>

위 그림에서와 같이 페이지 부재가 일어날 때마다 어떤 페이지가 3개의 프레임 속에 있는가를 보여준다. 그림에서 보여주듯이 모두 15개의 페이지 부재가 있다.

선입 선출 페이지 대치 알고리즘은 이해가 쉽고, 프로그램 작성에 용이하지만 성능이 항상 좋지 않다는 치명적인 단점이 있다. 위 그림과 보면 프레임을 더 많이 할당했는데도 불구하고 페이지 부재가 더 많이 일어나는 현상이 발생하는 단점을 갖는다. 그리고 이러한 현상을 발견한 사람이 벨레디이며, 그래서 이를 벨레디의 변이 현상이라고 부른다.

페이지 프레임 수가 증가했을 때 페이지의 부재가 줄다가 다시 부재가 늘고, 그 이후는 계속해서 비슷하므로, 적정한 프레임 수를 찾는 것도 매우 어려운 일 중 하나이다.

참고 자료

[윤경호, 1997][페이징 시스템에서 페이지 교체 알고리즘에 관한 연구][목포대학교 대학원]
[구리락차, 2014][안드로이드 기반의 페이징 기법 시뮬레이터의 설계 및 구현 : FIFO, LRU, Optimal 페이지 교체 알고리즘][한성대학교 대학원]
[최준원, 2014][플래쉬 메모리 저장장치를 위한 향상된 LRU 버퍼 캐쉬 교환 알고리즘에 대한 연구][연세대학교 공학대학원]