![[페이지 교체 알고리즘] - Least Recently Used Algorithm(LRU)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FqOdjk%2FbtrkAuIesdJ%2F8emO43wzpiJKOkLfJvFqrK%2Fimg.png)
# 페이지 교체 알고리즘 (Paging Algorithm)
- 페이징(Paging)
: 프로세스가 사용하는 메모리 공간을 잘게 나눠 비연속적으로 실제 메모리에 할당하는 메모리 관리 기법입니다. 다시 말해, 하나의 프로세스가 사용하는 메모리 공간이 연속적이어야 한다는 제약을 없애 외부 단편화가 발생하지 않게 하는 메모리 관리 기법입니다. - 프레임(Frame)
: 물리적 메모리(물리 메모리)를 일정한 크기로 나눈 블록 - 페이지(Page)
: 논리적 메모리(가상 메모리)를 일정한 크기로 나눈 블록 - 페이지 테이블(Page Table)
: 하나의 프로세스는 하나의 테이블 페이지를 가지며, 프로세스의 페이지 정보를 저장하고 있습니다. - 페이지 부재(Page Fault)
: 페이지 테이블 변환 과정에서 매핑 데이터를 찾지 못하고 물리 메모리 공간이 부족해져 Page-Out이 발생하면 운영체제는 페이지 부재를 발생시킵니다. - 페이지 교체 알고리즘(Paging Algorithm)
: 페이지 부재(Page Fault)가 발생했을 때, 모든 Page Frame이 사용중이라면 어떤 Page Frame을 선택하여 교체할 것인지를 결정하는 알고리즘
즉 페이지 교체 알고리즘이란,
프로세스가 특정 페이지를 요구할 때 페이징 시스템이 해당 페이지를 물리 메모리에 로딩하는데 이때 메모리에 필요한 페이지가 없을 경우에 하드 디스크에서 페이지를 찾아 빈 프레임에 로딩합니다. 이것이 페이지 부재라는 것입니다. 이때 모든 페이지 프레임이 사용 중이여서 하드 디스크에서 찾은 페이지를 올릴 빈 프레임이 없는 경우에 어떤 페이지 프레임을 선택하여 하드 디스크에서 찾은 페이지와 교체할지 결정하는 알고리즘이 페이지 교체 알고리즘입니다.
페이지 교체 알고리즘에는 대표적으로 다음과 같은 종류의 알고리즘이 있습니다
- FIFO(First In First Out)
: 페이지가 주기억장치에 가장 먼저 들어온 페이지를 교체하는 기법으로 각 페이지가 주기억장치에 들어올 때마다 타임스탬프를 찍어 기억하거나 페이지가 올라온 순서를 큐에 저장하는 방식입니다. 하지만 가장 오래 있었던 페이지는 앞으로 계속 사용될 가능성이 있기에 사용중인 페이지를 계속해서 교체하게 되어 페이지 부재의 발생이 빈번해진다는 단점이 있습니다. - OPT(Optimal Page Replacement)
: 주기억장치에서 앞으로 가장 오랫동안 사용되지 않을 페이지를 교체하는 기법으로 프로세스가 앞으로 사용할 페이지를 미리 알수 있는 경우에 사용합니다. 하지만 실제 상황에서는 프로세스가 앞으로 사용할 페이지를 미리 알 수 없기 때문에 알고리즘 구현이 불가능합니다. - LFU(Least Frequently Used)
: 참조 횟수가 가장 적은 페이지를 교체하는 기법입니다. 참조 횟수를 기준으로 두고 있기 때문에 참조될 가능성이 많아도 횟수가 적어 자주 교체가 발생하거나, 초기에 여러번 참조해 이후에 참조하지 않는데에도 메모리에 그대로 남아있는 경우가 발생합니다. - MFU(Most Frequently Used)
: 참조 횟수가 가장 많은 페이지를 교체하는 기법입니다. LFU와 반대되는 개념입니다. 참조 횟수가 적은 페이지가 최근에 사용된 것이기 때문에 가장 많은 페이지를 교체하는 기법입니다. 이 기법은 반대로 자주 참조되는 페이지를 자주 교체할 수 있습니다. - LRU(Least Recently Used)
: 가장 오래 사용되지 않은 페이지를 교체하는 기법입니다. OPT 기법과 가장 비슷한 효과를 내는 방법으로 많은 운영체제가 채택하는 알고리즘입니다.
# LRU(Least Recently Used) 알고리즘
- 동작 설명
주기억 장치의 크기 : 4
참조되는 페이지 번호 순서대로 :
1 2 3 1 4 3 5 6
1) 페이지 1이 주기억 장치에 있는지 확인 → 없음 : 주기억 장치에 1 저장
인덱스 번호 0 1 2 3 배열 값 1
2) 페이지 2가 주기억 장치에 있는지 확인 → 없음 : 모든 배열 값을 한칸씩 뒤로 민 후에 주기억 장치에 2 저장
- 모든 배열 값을 한칸씩 뒤로 밀기
인덱스 번호 0 1 2 3 배열 값 1
- 주기억 장치에 2 저장
인덱스 번호 0 1 2 3 배열 값 2 1
3) 페이지 3이 주기억 장치에 있는지 확인 → 없음 : 모든 배열값을 한칸씩 뒤로 민 후에 주기억 장치에 3 저장
- 모든 배열 값을 한칸씩 뒤로 밀기
인덱스 번호 0 1 2 3 배열 값 2 1
- 주기억 장치에 2 저장
인덱스 번호 0 1 2 3 배열 값 3 2 1
4) 페이지 1가 주기억 장치에 있는지 확인 → 있음 : 인덱스 0번부터 2-1번까지만 한칸씩 뒤로 민 후 페이지 1 저장
- 인덱스 0번부터 2-1번(페이지 1의 인덱스 번호 - 1)까지 한칸씩 뒤로 밀기
인덱스 번호 0 1 2 3 배열 값 3 2
- 주기억 장치에 1 저장
인덱스 번호 0 1 2 3 배열 값 1 3 2
5) 페이지 4가 주기억 장치에 있는지 확인 → 없음 : 모든 배열값을 한칸씩 뒤로 민 후에 주기억 장치에 4 저장
- 모든 배열 값을 한칸씩 뒤로 밀기
인덱스 번호 0 1 2 3 배열 값 1 3 2
- 주기억 장치에 1 저장
인덱스 번호 0 1 2 3 배열 값 4 1 3 2
6) 페이지 3이 주기억 장치에 있는지 확인 → 있음 : 인덱스 0번부터 2-1번까지만 한칸씩 뒤로 민 후 페이지 1 저장
- 인덱스 0번부터 2-1번(페이지 3의 인덱스 번호 - 1)까지 한칸씩 뒤로 밀기
인덱스 번호 0 1 2 3 배열 값 4 1 2
- 주기억 장치에 1 저장
인덱스 번호 0 1 2 3 배열 값 3 4 1 2
7) 페이지 5가 주기억 장치에 있는지 확인 → 없음 : 모든 배열값을 한칸씩 뒤로 민 후에 주기억 장치에 5 저장
- 모든 배열 값을 한칸씩 뒤로 밀기
인덱스 번호 0 1 2 3 배열 값 3 4 1
- 주기억 장치에 1 저장
인덱스 번호 0 1 2 3 배열 값 5 3 4 1
8) 페이지 6이 주기억 장치에 있는지 확인 → 없음 : 모든 배열값을 한칸씩 뒤로 민 후에 주기억 장치에 6 저장
- 모든 배열 값을 한칸씩 뒤로 밀기
인덱스 번호 0 1 2 3 배열 값 5 3 4
- 주기억 장치에 1 저장
인덱스 번호 0 1 2 3 배열 값 6 5 3 4
최종 배열 값
인덱스 번호 0 1 2 3 배열 값 6 5 3 4 - 코드 설명
public class LRU {
// size : 주기억장치 사이즈
// n : 입력된 페이지 수
// arr : 페이지 번호 배열
public int[] solution(int size, int n, int[] arr) {
int[] answer = new int[size]; // 주기억장치
for(int x: arr) {
int pos = -1;
for(int i=0; i<size; i++) {
if(x == answer[i])
pos = i; // 주기억장치에 페이지 존재하는지 여부 확인
}
if(pos==-1) { // 주기억장치에 페이지가 존재하지 않는 경우
for(int i=size-1; i>=1; i--) {
answer[i] = answer[i-1]; // 모든 페이지를 한 칸씩 뒤로 이동
}
} else { // 주기억장치에 페이지가 존재하는 경우
for(int i=pos; i>=1; i--) {
answer[i] = answer[i-1]; // 인덱스 0부터 해당 인덱스까지 한 칸씩 뒤로 이동
}
}
}
return answer;
}
}