페이지 교체 알고리즘Hit & Miss페이징 기법 (Paging)종류FIFO 알고리즘 (First-in First out)OPT 알고리즘 (Optimal)LRU 알고리즘 (Least-Recently-Used)
페이지 교체 알고리즘
페이징 기법으로 메모리를 관리하는 운영체제에서, 페이지 부재가 발생 하여 새로운 페이지를 할당하기 위해 현재 할당된 페이지 중 어느 것과 교체할지를 결정하는 방법이다. 이 알고리즘이 사용되는 시기는 페이지 부재가 발생해 새로운 페이지를 적재 해야하나 페이지를 적재할 공간이 없어 이미 적재되어 있는 페이지 중 교체할 페이지를 정할 때 사용된다. 빈 페이지가 없는 상황에서 메모리에 적재된 페이지와 적재할 페이지를 교체함으로 페이지 부재 문제를 해결할 수 있다. 단점으로는 TimeStamping에 의한 overhead가 존재한다는 점이다
Hit & Miss
만약 CPU가 어떤 일을 처리할 때 필요한 메모리(데이터)가 페이지에 저장되 있다면 그 것을 cache hit이라고 한다. 만약 저장되어 있지 않다면 이 것을 cache miss 라고 한다.
페이징 기법 (Paging)
컴퓨터가 메인 메모리에서 사용하기 위해 2차 기억 장치로부터 데이터를 저장하고 검색하는 메모리 관리 기법이다. 즉 가상기억장치를 모두 같은 크기의 블록으로 편성하여 운용하는 기법이다. 이때의 일정한 크기를 가진 블록을 페이지(page)라고 한다. 주소공간을 페이지 단위로 나누고 실제기억공간은 페이지 크기와 같은 프레임으로 나누어 사용한다.
종류
FIFO 알고리즘 (First-in First out)
주 기억장치에 적재될 때마다 순서를 기억해서 가장 먼저 들어온 페이지가 후에 들어오는 페이지와 교체 하는 기법이다.
- 총 8번의 부재가 일어남
OPT 알고리즘 (Optimal)
페이지 부재가 발생했을 경우 각 페이지 호출순서에 따라 사용하지 않을 페이지를 교체하는 기법이다.
- 총 7번의 부재가 일어남
LRU 알고리즘 (Least-Recently-Used)
캐시(Cache)에서 메로리를 다루기 위한 알고리즘으로써, 페이지 부재가 발생했을 경우 최근 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘이다.
- 총 7번의 부재가 일어남