[OS] 페이지 교체 알고리즘(Page replace algorithm)

페이지 교체 (page replace)

• 페이지 교체는 요청된 페이지가 메모리 프레임에 없고, 페이지를 로딩할 빈 메모리 프레임도 없는 경우, 현재 사용중인 프레임들 중에서 하나를 선택하여 비우고 이곳에 요청된 페이지를 로딩하는 과정이다.
• 비우기로 선택된 프레임을 희생 프레임(victim frame)이라고 부르고, 그곳에 저장되어 있다가 쫓겨나는 페이지를 희생 페이지(victim page)라고 부른다.
• 희생 페이지가 수정된 페이지(modified / dirty page)라면 하드 디스크에 스왑-아웃된다.
• 목표: 현재 작업 집합에 포함되지 않거나 가까운 미래에 참조되지 않을 페이지를 희생 페이지로 선택하여 페이지 폴트의 횟수를 줄이는 데에 있다.

 

최적 교체 알고리즘 (OTP)

• 가장 최적의 페이지 즉, 미래에 사용될 가능성이 가장 낮은 페이지, 다른 말로 작업 집합에서 가장 멀어진 페이지를 희생 페이지로 선택한다.
• 교체가 이루어지는 현재 시점에서 미래에 각 페이지들이 언제 참조되는지 알아내고, 이에 따라 가장 먼 미래에 사용될 페이지를 희생 페이지로 선택한다.

 

FIFO 알고리즘

• 메모리 프레임에 존재하는 페이지 중 가장 오래된 페이지를 희생 페이지로 선택한다.
• 오래 전에 로딩된 페이지들은 작업 집합에서 벗어나 앞으로 참조될 가능성이 낮을 것이라는 판단으로 만들어진 알고리즘이다.

 

LRU 알고리즘

• 참조의 지역성을 이용한다.
• 메모리 프레임에 있는 페이지 중 가장 오랫동안 참조되지 않았던 페이지를 희생 페이지로 선택한다.
• 최근에 참조된 페이지가 가까운 미래에 다시 참조될 가능성이 매우 높고, 반대로 오랫동안 사용되지 않았다면 앞으로도 사용될 가능성이 매우 낮다는 참조의 지역성 원리에 근거를 두고 있다.
• 가장 오랫동안 사용되지 않았던 페이지를 선택함으로써 이미 작업 집합에서 많이 벗어났을 확률이 높은 페이지를 선택하는 것이다.

 

 

참고

운영체제(Operating system), 황기태 지음