페이지 교체 알고리즘

JoyJuhee·2022년 10월 18일
0

운영체제

목록 보기
10/10
post-thumbnail

메모리는 한정되어 있기 때문에 스와핑이 많이 일어난다. 스와핑은 많이 일어나지 않도록 설계되어야 하며, 이는 페이지 교체 알고리즘을 기반으로 스와핑이 일어난다.

1. 오프라인 알고리즘(offline algorithm)

: 먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 알고리즘으로 가장 좋은 방법이다.
(미래에 많이 안쓸것 같은 페이지랑 현재 페이지를 바꾸는 것.)
👉 그러나, 미래의 프로세스를 알 수 없다. 그래서, 사용할 수 없는 알고리즘이지만 다른 알고리즘과의 성능 비교에 대한 기준을 제공한다.

2. FIFO(First In First Out)

: 가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법

3. LRU(Least Recently Used)

: 참조가 가장 오래된 페이지를 바꾼다. '오래된'것을 파악하기 위해 각 페이지마다 계수기, 스택을 두어야 하는 문제점.

4. NUR(Not Used Recently)

: clock 알고리즘이라고 하며 먼저 0과 1을 가진 비트를 둔다. 1은 최근에 참조되었고, 0은 참조되지 않음을 의미한다. 시계 방향으로 돌면서 0을 찾고 0을 찾은 순간 해당 프로세스를 교체하고, 해당 부분을 1로 바꾸는 알고리즘

3. LFU(Least Frequently Used)

: 가장 참조 횟수가 적은 페이지를 교체한다. 즉, 많이 사용하지 않은 것을 교체한다.


출처 : 면접을 위한 CS전공지식 노트 (책/강의)

0개의 댓글