반응형
페이지 교체 알고리즘
운영체제는 주기억장치보다 더 큰 용량의 프로그램을 실행하기 위해 프로그램의 일부만 주기억장치에 적재하여 사용한다. 이를 가상메모리 기법이라 한다.
페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시(페이지 부재) 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법을 페이지 교체 알고리즘이라고 한다.
쉽게 말하면, 페이지 폴트가 발생했을때 페이지를 교체하는 방법이다.
※ 페이지란?
페이징 기법에서 일정한 크기를 가진 블록을 페이지(page)라고 한다.
페이징 기법은 컴퓨터가 RAM에서 사용하기 위해 2차 기억 장치로부터 데이터를 저장하고 검색하는 메모리 관리 기법이다. 이때 가상기억장치를 모두 같은 크기의 블록으로 만들어 운영한다고 생각하면 된다.
* 프레임: 물리 메모리를 일정한 크기로 나눈 블록
* 페이지: 가상 메모리를 일정한 크기로 나눈 블록
페이지 교체 알고리즘 종류
♣ FIFO(First In First Out)
- 가장 먼저 들어와서 가장 오래 있었던 페이지를 교체
- 구현이 간단하나 성능이 그리 좋지 못함
- 페이지가 올라온 순서를 큐에 저장하는 방식
- 활발하게 사용 중인 페이지를 계속해서 교체한다면 페이지 부재율이 높아지고 실행속도 저하 위험 존재
♣ LRU(Least Recently Used)
- 최근에 가장 오랫동안 사용하지 않은 페이지를 교체
- 최적 알고리즘과 비슷한 효과를 낼 수 있음
- 성능이 좋은 알고리즘으로 많은 운영체제(OS)에서 채택되는 알고리즘
♣ LFU(Least Frequently Used)
- 사용 빈도가 가장 적은 페이지를 교체
- 가장 최근에 불러온 페이지가 교체될 수 있으며, 구현이 복잡한 편이고 막대한 오버헤드가 발생할 수 있음
- 잘 사용되는 알고리즘은 아님
♣ MFU(Most Frequently Used)
- 참조 횟수가 가장 많은 페이지 교체
- 구현에 많은 비용이 듦
- 잘 사용되는 알고리즘은 아님
♣ OPT(Optimal)
- 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체
- 페이지 부재 가장 적음 (가장 이상적인)
- 실제로 구현하기 거의 불가능한 알고리즘으로 연구 목적을 위해 사용
(프로세스가 앞으로 사용할 페이지를 미리 알아야 되기 때문)
♣ NUR(Not Used Recently)
- 최근에 사용하지 않은 페이지를 교체
- 교체되는 페이지가 참조되는 시점이 가장 오래된 것이라고 보장하지는 못함
- 최근의 사용 여부를 확인하기 위해서 각 페이지마다 두 개의 비트, 참조 비트와 변형 비트가 사용됨
- 적은 오버헤드로 적절한 성능을 낾
* 참조 비트 : 페이지가 호출되지 않았을 때는 0, 호출되었을 때는 1로 저장
* 변형 비트 : 페이지 내용이 변경되지 않았을 때는 0, 변경되었을 때는 1로 지정
♣ SCR
- 가장 오랫동안 주기억장치에 있었던 페이지 중, 자주 사용되는 페이지 교체를 방지하는 기법
- FIFO 단점 보완
[참고 자료]
728x90
'정보처리기사 실기(개정 후) > 0장. 기타개념정리' 카테고리의 다른 글
| [개념정리] 코딩 표준 - 변수 명명법(Casing) (0) | 2023.03.13 |
|---|
댓글