페이지 교체 알고리즘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번의 부재가 일어남