[운영체제] Virtual Memory - FIFO, LRU, LFU

이전에 봤던 논리 주소의 메모리 변환은

운영체제가 관리하지 않고 하드웨어가 관리했는데, 

 

Virtual Memory 변환은 운영체제가 관리하고있다.

 

 

요청이 있을때 그 페이지를 메모리에 올리는것

프로그램이 실행될때 그 구성되는 주소 공간에 페이지를 전부 메모리에 올리는게 아니라

Demand Paging 기법을 사용한다.

 

 

페이징 마다 valid- invalid bit 이 있다

invalid 는 물리적인 메모리(physical memory) 에 없고 디스크에만 있는 상황

CPU 가 invalid-bit 에 접근을 하면 "page fault" 현상 발생

-> cpu 가 운영체제로 넘어가게 된다. 홀드된 페이지를 메모리에 올리게 된다.

 

 

 

진행 순서

1. 잘못된 요청을 아닌지? 확인 한다. 주소가 잘못되었는지 등

2. 빈 페이지 프레임을 획득해야되고, 빈 곳이 없다면 하나 쫒아낸다.

3. 디스크에서 메모리로 가져온다

   1.  CPU 를 뺏고 block 상태로 둔다.

   2. I/O 작업이 끝나면 페이지 테이블 엔트리에 valid 로 표시

   3. 나중에 프로세스가 다시 CPU를 얻게되면 CPU 가 해당 페이지에 접근가능하게 된다.

 

page fault 과정 이미지

빈 페이지 가 없던 경우를 알아보자

빈페이지가 없을땐 뭔가를 쫒아내야한다.

쫒아내는걸 Page replcaement 라 고 한다.

 - 곧바로 사용되지 않을 page 를 쫒아낸다.

 

이렇게 page replacement 를 하는 알고리즘들이있다.

page fault rate 이 낮게 나오게 하는게 목표

 

알고리즘 종류들 

 

어떤 알고리즘이 가장 좋을까

가장 page fault 가 적은 알고리즘

이론상으로 가장 먼 미래에 참조되는 page 를 replace 하는 기법

실제 시스템에선 사용할수없다. 미래를 알 수 없으니

다만, 알고리즘의 비교 척도로 사용된다.

 

어떻게 사용되느냐?

가장 먼 미래에 참조되는 page 를 replace 한다.

 

이제 이 밑에서부터 실제 시스템에서 사용가능한 알고리즘들

 

먼저 들어온 것을 내쫒는 FIFO 알고리즘

FIFO Anomaly

이 FIFO 의 특이한 성질은

기본적으로 메모리 크기를 3page 에서 4page 로 늘리면 성능이 좋아져야하는데

성능이 나빠지는 경우가 생길 수 있다.

 

메모리 관리에서 가장 많이 쓰이는 알고리즘

가장 오래전에 사용된 걸 쫒아낸다.

재사용이 된 건 쫒아내는 우선순위가 바뀐다.

 

가장 덜 빈번하게 사용된걸 쫒아낸다.

LRU 는 가장 오래전에 요청한 걸 쫒아낸다.  많은 참조가 일어났었다는건 확인하지 않는다.

LFU 는 참조 횟수로 보기때문에 가장 참조가 적은 4번을 쫒아낸다. 문제점은 이제 막 참조가 시작된애를 쫒아내게 된다.

 

 

 

LRU 알고리즘은 참조 순서에 따라 줄을 세운다. Linked List로 시간 순서대로 관리한다.

참조가 일어나면 가장 아래로 옮기고 쫒아낼때는 가장 위에걸 쫒아낸다.

O(1) 복잡도를 가지게 된다.

 

 

LFU 도 한줄로 줄세워서 구현할수가 없다.

LRU는 그냥 제일 아래로 보내면 되는데, LFU 는 참조 횟수가 1이 늘어도 다른것들과 비교해서 위치를 정해야한다.

 

O(n) 복잡도를 가진다.

 

 

그래서 LFU 는 힙 알고리즘을 이용해서 구현하게 되고 ,이걸 이용하면 O(log n) 의 알고리즘을 갖게 된다.