LFU와 LRU알고리즘이란?

#정보처리기사 #개발자의도구들 #LFU #LRU #페이지교체알고리즘

24년도 1회차 정보처리기사 필기 시험대비 공부를 진행하였습니다.

\* 본글은 PC버전에 최적화 되어있습니다.

​

**\\ **공부방법론은 가장 첫글에 있습니다. 참고하실 분들은 참고하세요! \\ - 개발자의도구들

\\ 정보처리기사 전체 총 정리는 여기 있습니다!! \\

​

4과목, 프로그래밍 언어 활용

view

페이지 교체 알고리즘

페이지의 부재(page Fault)시 가상기억장치에 필요한 페이지를 메모리에 적재해야합니다.

​

이때 메모리의 모든 페이지 프레임이 사용중이라면, 무엇을 뺄지를 결정하는 알고리즘입니다.

---

OPT(OPtimal replacement)

​

최적교체로 불리는 OPT는 실현 불가능한 기법입니다. 앞으로 가장 적게 사용될 페이지를 고려해서 빼는 알고리즘인데요.

​

실제 우리가 미래를 알수 없듯이, 컴퓨터도 미래를 알수는 없어요. 그래서 불가능한 알고리즘이지만, 가장 이상적인 알고리즘이 되겠습니다.

​

​

1 2 3 4 / 8 / 9 / 7 / 8 4 4 1 1 1 순서

13번의 교체중 fault 수 4(초기) + 1 +1 + 1 = 7

---

FIFO

First In First Out 기법으로 queue를 사용한 교체기법입니다. 가장 먼저 들어온 페이지가 제일 먼저 교체됩니다.

​

간단하고 프로그래밍하기에는 쉽지만, 참조되는 페이지가 자주 비슷하다면, 비효율적인 알고리즘이 될수 있겠습니다.

​

1 2 3 4 / 8 / 9 / 7 / 8 4 4 /1 1 1 순서

13번의 교체중 fault 4 + 1 + 1 + 1 + 1 = 8

---

LRU

Least Recently Used의 약자로 가장 오랫동안 사용되지 않는 페이지를 교체하는 기법입니다. 즉 가장 안쓴거를 바꾼다는 말이되겠습니다.

​

참조되는 페이지가 자주 겹친다면, 매우 효율적인 알고리즘이 될 수 있겠습니다.

​

1 2 3 4 / 8 / 9 / 7 / 8 4 4 /1 1 1 순서

13번의 교체중 Fault 8번

---

LFU

Least Frequntly Used의 약자로 LRU와 약간은 비슷합니다. 가장 사용이 적은 페이지를 교체하는 기법으로, 가장 오래 사용되지 않는 기법과는 결이 다르겠습니다.

​

역시나 참조되는 페이지가 자주 겹칠때 사용하면 효율적이겠습니다.

​

1 2 3 4 / 8 / 9 / 7 / 8 4 4 /1 1 1 순서

13번 중에 Fault 8번

---

SCR

가장 오랫동안 메모리에 있던 페이지 중 자주 사용되는 페이지의 교체를 방지하는 기법입니다.

​

2차 기회를 준다고해서 Second Change Replacement라는 이름이 붙었습니다.

​

---

NUR

Not Used Recently의 약자로 이름만 들으면 LRU와 매우 비슷합니다. 역시나 이름에 걸맞게 작동원리도 비슷한데 최근에 사용되지 않는 페이지를 교체합니다.

​

최근에 사용되지 않는 페이지는 향후에도 사용되지 않을 가능성이 높다는 것을 전제로 하여 LRU에서 나타나는 시간적인 오버헤드를 줄 일 수 있다고합니다.

​

페이지 사용 여부확인을 위해 참조비트와, 변형 비트를 사용합니다.

​

​