10. Virtual Memory (1)

Virtual Memory는 Physical Memory의 공간 사용 효율을 높이기 위해 만들어진 기술이다.

지금까지 살펴본 memory management는 virtual memory가 없다는 가정 하에 전개가 되었다.

 

Virtual Memory

폰노에만 머신에 따르면 프로세스의 모든 address space가 메모리에 올라와야 프로그램이 수행될 수 있다고 했다.
=> 이론적으로는 그렇다.

그러나 CPU 입장에서는 자기가 현재 수행해야 할 Instruction과 Instruction이 접근해야 할 Data만 사용하므로 얘네만 메모리에 올라와 있으면 실질적으로 프로그램 수행에 아무런 문제가 없다.

이제부터 이론과 실제는 다르다.

실제로 CPU가 접근하는 Instruction과 데이터만 메모리에 올리자.
당장 필요하지 않은 부분은 메모리에 올라오지 않으므로 메모리를 효율적으로 사용할 수 있다.
또한 프로세스 관점으로 보면 전체 address space 중 일부만 메모리에 올라와 있으므로 더 많은 프로세스가 메모리에 올라와 수행될 수 있으므로 동시에 더 많은 프로세스가 수행될 수 있다.

그런데 이렇게 되면 프로세스의 모든 address space는 메모리에 올라와 있어야 한다는 철학이 깨져버린다.

이 철학을 유지하면서도 실질적으로 일부만 올라오게 해서 효율성을 높이는 방법은 없을까??

CPU한테는 이 프로세스의 모든 address space가 다 올라온 것처럼 속인다.
그리고는 뒤에서 OS가 CPU가 접근하는 부분은 다 메모리에 올라와 있을 수 있도록 바쁘게 일을 한다.
=> OS는 일부만 올라온 걸 알지만 CPU와 프로세스는 모든 address space가 다 올라온 것으로 알고 있다.

그렇다면 CPU가 접근하려는 데이터가 실제 메모리에 올라와 있지 않을 때만 잘 처리해주면 문제없이 수행될 수 있다.
=> page를 교체하는 방식으로 해결

즉, logical address space와 physical address space가 분리가 된다.
=> CPU가 알고 있는 건 logical address space, OS가 알고 있는 건 physical address space.

 

이렇게 하면 좋은 점 중 하나는 프로세스는 실제 주소는 모르고 logical address만 알고 있기 때문에 OS는 프로세스들이 physical address space를 공유하도록 할 수 있다.
그럼에도 프로세스들은 개별적으로 logical address space를 갖고 있기 때문에 독립적인 공간을 갖고 있다고 생각한다.

이러한 특정이 가져다주는 추가적인 이점도 있다.

프로세스가 만들어지려면 fork를 해야 하는데, 자식 프로세스는 부모 프로세스의 address space를 그대로 복사한다고 했다.
virtual memory 개념이 없을 때는 실제로 독립적인 physical address 공간을 만들어서 address space를 복사해줬다.

그런데 virtual mermoy 개념이 도입되면, 자식 프로세스는 logical address space만 독립적으로 제공하고 실제로는 부모의 address space가 저장된 physical memory를 공유하도록 만들 수 있다.
=> 메모리를 효율적으로 사용할 수 있다.
=> 또한 메모리 복사가 필요가 없으므로 빠르게 새로운 프로세스를 하나 만들 수 있다.

자식 또는 부모 프로세스가 메모리 공간에 접근해서 값을 바꾸려고 하면 그때는 어쩔 수 없이 실제로 물리적 공간을 별도로 제공해야 한다.

 

Demand paging

지금 메모리에 올라와 있지 않은 부분을 CPU가 갑자기 접근하게 될 때 어떻게 할 것인지를 해결해야 한다.

이것만 해결하면 프로세스는 큰 문제없이 수행될 수 있다.

우리는 paging 기법을 사용한다는 가정 하에 virtual memory를 배울 것이다.

프로세스의 전체 address space 중 일부 페이지는 실제 physical memory에 올라와 있을 것이고 일부 페이지는 올라와 있지 않을 것이다.
그런데 CPU가 올라와 있지 않은 페이지에 접근하려고 하면 OS는 재빠르게 해당페이지를 메모리에 올려주어야 한다.

그래서 페이지 단위로 메모리에 올리고 내리는 기술이 필요하다.
지금까지 배운 메모리와 디스크 사이의 Swap은 프로세스 단위로 발생했었는데, 이제는 페이지 단위로 해주면 된다.

또한 실제로 접근되는 페이지만 메모리에 올라오게 될 것이므로, Suspend된 프로세스의 페이지들은 굳이 디스크로 내리지 않아도 자연스럽게 메모리에서 밀려날 것이다.

 

Virtual memory larger than Physical memory

Virtual memory를 사용했을 때의 효과 :

실제 프로세스의 logical address space의 크기가 DRAM의 크기보다 큰 경우에도 프로세스가 수행될 수 있도록 해준다.

프로세스가 동적 할당을 많이 해서 점점 커지다 보면 실제 DRAM의 크기보다 커질 수도 있다.
=> 그러면 프로세스는 동작을 할 수 없게 되는데, virtual memory를 사용하면 현재 사용중인 페이지만 실제 메모리에 올리면 되므로 그 경우에도 정상적으로 수행될 수 있다.

 

Demand paging

페이지에 접근하려 할 때만 메모리에 올리게 되면 얻을 수 있는 장점이 몇 가지 있다.

접근되는 페이지만 I/O를 통해 메모리에 올라가게 되므로 I/O의 양이 줄어들고, 메모리 공간을 효율적으로 사용할 수 있다.

반응성은 왜 좋아질까?

CPU가 실제로 접근을 해야지 메모리에 올리기 때문에 처음 프로세스가 만들어질 때는 메모리에 아무런 페이지도 올리지 않는다.

그렇기 때문에 프로세스가 실행되면 별도의 준비 과정 없이 바로 수행을 시작할 수 있다.

 

실제로 페이지가 올라와 있는지를 구분하기 위해서 valid, invalid bit을 사용한다.

또한 이 페이지에 대한 접근이 합법적인 접근인지 합법적이지 않은 접근인지를 나타내는 용도로도 사용된다.

 

Swap을 수행하는 애를 Swapper라고 부르는데, 그 중에서도 page 단위로 swap을 하는 Swapper를 Pager라고 부르기도 한다.

페이지 테이블은 모든 페이지에 대해 엔트리가 만들어져 있지만, 모든 페이지가 메모리에 올라와 있는 것이 아니므로 엔트리마다 표시된 valid-invalid bit의 역할이 한 층 더 중요해진다.

페이지 테이블의 엔트리가 invalid로 표시되어 있는 경우는 3가지로 나눠서 생각할 수 있다.

1. illegal

CPU가 발생시킨 logical address가 프로세스의 사이즈보다 큰 경우엔 완전히 잘못된 주소를 접근하는 것이다.

예를 들어 어 프로세스의 address space는 10개의 페이지로 구성되어 있는데, 11번째 페이지에 접근하려는 경우엔 잘못된 접근이다.

페이지 테이블이 프로세스의 사이즈에 딱 맞춰서 만들어지는 것이 아니기 때문에 사용되지 않는 엔트리가 발생할 수 있다.
=> 이 엔트리는 invalid로 표시를 해야 한다.

 

2. not in memory

실제 CPU가 접근을 할 때만 페이지가 메모리에 올라오기 때문에 모든 페이지가 메모리에 올라와 있는 것이 아니라고 했다. 디스크에는 저장되어 있지만 실제로 메모리에 올라와 있지 않은 페이지라면 invalid라고 표시를 해야 한다.

 

3. obsolete

메모리에도 올라와 있고, 합법적인 메모리 주소 접인데도 invalid라고 표현되어 있는 경우도 있다.

메모리에 올라와 있는 페이지의 데이터가 다른 누군가에 의해 업데이트가 된 경우, 이 페이지에 담겨 있는 내용은 과거의 데이터가 되어 버린다.

이때는 최신 데이터를 다시 읽어와서 메모리에 올려야 한다.

 

실제로 그 페이지에 접근하려고 할 때 페이지가 메모리에 올라오므로, 처음 프로세스가 만들어지면 메모리에는 어떠한 페이지도 올라와 있지 않다.
=> 페이지 테이블의 모든 엔트리가 invalid에서 시작한다.

그리고 CPU가 메모리에 접근하기 위해서 logical address를 발생시키게 되면, 페이징 기법에 의해 MMU는 그 페이지가 실제로 몇 번 frame에 저장되어 있는지 찾기 위해 페이지 테이블을 look up을 하게 되는데 해당 엔트리가 invalid로 표시되어 있으면 페이지를 메모리에 올려주어야 한다.

그때는 page fault를 호출한다.
=> 커널 코드의 page fault handler가 디스크에서 페이지를 메모리에 올리는 과정을 처리해준다.

 

만약 CPU가 0번 페이지의 데이터에 접근을 하려고 한다면, MMU는 페이지 테이블에서 0번 페이지에 해당하는 엔트리를 찾을 것이고 valid로 표시되어 있기 때문에 실제 frame의 시작주소를 찾아서 물리 주소를 CPU에게 전달할 수 있다.

하지만 CPU가 1번 페이지의 데이터에 접근을 시도하면, MMU는 똑같이 페이지 테이블을 look up해서 1번 페이지에 해당하는 엔트리를 찾을 것이고 invalid로 표시가 되어 있다. 그렇다면 메모리에 올라와 있지 않은 페이지라는 뜻이므로 Page fault를 호출한다. 

 

Page Fault

OS는 어떠한 과정을 거쳐서 페이지 폴트를 처리할까?

 

페이지 폴트가 발생했다는 것은 MMU가 접근한 페이지 테이블의 엔트리가 invalid로 표시되어 있었다는 것이다.

먼저 invalid라고 표시되어 있는 이유가 illegal reference인지를 판단한다.
만약 잘못된 주소에 대한 접근이라면 이 프로세스는 이상 동작을 하고 있다는 뜻이므로 abort를 시켜버린다.

제대로된 영역에 접근을 하는데 invalid라면 메모리에 올라와 있지 않은 페이지거나, update가 발생해서 과거의 데이터가 되어버린 페이지거나 둘 중 하나다.
=> 이 두 경우는 모두 디스크에서 페이지를 읽어와야 하는 경우이다.

 

이제 페이지를 실제로 메모리에 올릴 것인데, 그럼 먼저 메모리 빈 frame을 찾아야 한다.
=> 빈 frame이 존재하면 거기에 올리면 끝이다.

그런데 모든 frame이 가득 찬 상황이라면 이미 올라온 페이지 중에 하나를 쫒아내고 빈 공간을 확보해야 한다.
=> Replace

빈 공간이 확보되면 디스크에서 페이지를 읽어와서 메모리에 올린다.

 

디스크 I/O가 끝나고 나면( 페이지를 메모리에 올리고 나면 ) valid/invalid bit를 valid로 바꾸고 페이지가 저장된 frame의 시작 주소를 페이지 테이블의 엔트리에 기록한다.

그리고 나서는 디스크 I/O가 발생해서 wait 상태가 된 프로세스를 ready 상태로 바꾸고 ready queue에 편입시킨다.

 

page fault가 발생해서 wait 상태가 되었던 프로세스가 다시 ready가 되어 CPU를 받게 되면 trap이 끝나게 되고, 접근하려던 데이터가 이제는 메모리에 올라와 있으므로 원래 수행하려던 코드를 정상적으로 수행할 수 있게 된다.

Page fault가 발생하고, 처리되는 과정을 간략하게 나타낸 그림이다.

 

Difficulties in actual HW design

위에서 살펴본 page fault를 처리하는 과정을 실제로 구현하는 것은 매우 어렵다.

명령어를 fetch하는 과정이나 operand(피연산자)를 fetch하는 과정에서 페이지 폴트가 발생하는 것은 비교적 간단하게 처리를 할 수 있다.

그러나 Worst Case를 살펴보자.

Instruction이 update하려는 destination이 여러 곳일 때 문제가 발생한다.

Destination address가 10 byte에 copy를 해야 한다. 그런데 5 byte는 하나의 페이지 끝 부분에 들어가 있고, 나머지 5 byte는 두 번째 페이지 첫 부분에 들어 있다면?

즉, 카피해야 할 대상이 2개의 페이지에 걸쳐서 있다면?
일단 이 instruction을 가져오는 데 성공했고, source address로부터 데이터를 읽어오는 것도 성공을 했다.
그리고 destination address의 첫 번째 페이지를 읽어오는 데에도 성공했다, 그럼 첫 번째 페이지에는 source 데이터가 copy가 되겠지,
그런데 두 번째 페이지는 메모리에 올라와 있지 않은 페이지라면, 두 번째 페이지에는 copy를 할 수가 없다.

=> page fault가 발생하게 된다. 명령 수행 도중에 page fault가 발생한 것이다.
그럼 이 프로세스는 I/O를 발생시키고 wait 상태로 가야 한다.

페이지 폴트가 처리되고 다시 돌아오면 이 프로세스는 명령어를 fetch하는 것부터 다시 시작해야 한다.
그런데 첫 번째 페이지는 이미 카피가 끝나버린 상태이다.
이 프로세스가 다시 CPU를 잡아서 완전히 copy를 마칠 때까지는 데이터 무결성이 깨진 상태가 되어버리는 것이다.

명령이 수행되던 도중에 페이지 폴트가 발생하는 경우에는 다시 수행하기 전으로 되돌리고 페이지 폴트를 처리해야 한다.

그런데 그게 되려면 카피가 발생하기 전에 데이터를 미리 백업해둬야 한다.
이러한 문제들로 인해 페이지 폴트를 단순게 처리할 수는 없다.
=> 여기부터는 OS를 전공으로 하게 되면 이런 것들을 어떻게 처리할까 심도있게 배우게 된다.

일단은 페이지 폴트를 처리하는 것이 엄청 어려운 일이구나 정도만 알고 넘어가자.

 

Performance of Demand Paging

Demad Paging 기법을 사용했을 때의 성능은 어떻게 될까?

[Swap page out if nedded] 라고 표기된 이유는? 비어 있는 frame이 없으면 기존에 올라와 있는 페이지중 하나를 쫓아내야 한다고 했다. 이때 쫓겨나는 페이지는 다시 디스크에 써야할 수도 있고 쓰지 않아도 될 수도 있다.

메모리의 페이지와 하드 디스크의 페이지의 내용이 일치하면, 즉 데이터의 update가 발생하지 않았으면 굳이 swap out을 해줄 필요가 없다.

메모리에 접근하는 시간은 200ns이고, 페이지 폴트가 발생했을 때 처리하는 시간은 8ms가 걸린다고 하자.

페이지 폴트가 발생하면 디스크 I/O가 발생하므로 당연히 시간이 오래 걸릴 것이다.

이때 페이지 폴트가 CPU가 메모리에 1000번 접근할 때마다 1번씩 발생한다고 하면, p = 0.001이 된다.

그때의 EAT는 8.2 μs로 그냥 메모리에 접근했을 때보다 무려 40배나 느려진다.

이 정도면 사용을 하면 안 되는 게 아닌가??

 

Pure demand paging :

CPU가 접근할 때만 Swap이 발생해서 페이지가 메모리에 올라오기 때문에 초기에는 메모리에 아무런 페이지도 올라와 있지 않다.

Locality of reference :

한 번 가지고 온 데이터에 대해서 자주 접근하게 되면 페이지 폴트 한 번으로 많은 메모리 접근을 커버할 수 있게 된다.

실제로 locality가 매우 강하기 때문에 페이지 폴트로 인한 성능 저하가 그렇게 심하지 않기 때문에 virtual memory를 사용할 수 있게 되는 것이다.

따라서 인기 있는 페이지를 쫒아내지 않는 것이 성능에 중요한 영향을 미친다.

=> 시스템이 locality를 이용할 수 있게 해주는 것이 중요하다.

=> 페이지 교체 알고리즘이 locality 보호를 위해 중요하다.

 

페이지 폴트가 발생했을 때, 디스크에서 페이지를 읽어서 메모리에 올려야 하는데 메모리에 공간이 없다면 기존의 페이지 중 하나를 밀어내야 한다고 했다.

이것을 Page replacement(페이지 교체)라고 하고, 밀려나는 페이지를 victim page라고 한다.

메모리에 올라온 이후에 해당 페이지에서 수정이 발생했는지를 확인해야 한다.
=> 수정이 발생하지 않았으면 굳이 swap out을 해줄 필요가 없다.
=> 수정이 발생했다면 dirty bit를 1로 표시하고, dirty bit가 1인 페이지는 디스크에 다시 써줘야 한다(swap out).

 

victim page를 선정할 때, Locality를 최대한 활용할 수 있도록 선정하는 것이 중요하다.

 

Page-Replacement Algorithms

Victim page를 선정하기 위한 알고리즘을 살펴볼 것이다.

해당 알고리즘의 성능을 측정하기 위해서, CPU가 접근하는 페이지 번호를 정해놓고 이 순서대로 접근했을 때 어떤 알고리즘이 페이지 폴트가 가장 적게 발생하는지 시뮬레이션 한다.

시뮬레이션에 들어가기 전에, 하나 생각해보자.

메모리 공간이 커지면 페이지 폴트가 덜 발생한다는 것은 상식적으로 생각해 볼 수 있다.

 

1. First In First Out (FIFO) Algorithm

페이지 교체도 어떤 순서로 페이지를 쫓아낼지를 정하는 것이므로 스케줄링으로 생각할 수 있다.

스케줄링 정책에서 항상 고려되는 방식 중 하나가 FIFO 알고리즘이라고 했다.

victim page를 선정할 때, 가장 오래 전에 메모리에 올라온 페이지를 victim으로 선정한다.

메모리에 3개의 페이지 frame이 존재한다고 했을 때, 9번의 페이지 폴트가 발생한다.

그런데 공간을 늘려서 4개의 페이지 frame이 존재한다고 하면, 10번의 페이지 폴트가 발생한다.

 

상식에서 벗어나는 현상이다.

=> Belady's Anomaly (Belady의 이상현상)

FIFO는 좋은 Replacement Algorithm이 될 수 없다.

 

2. Optimal Algorithm

FIFO 방식에서 볼 수 있었듯이 차후에 접근될 페이지가 victim으로 선정되면 페이지 폴트가 발생하게 된다.

그러면 가까운 시간에 접근될 페이지는 victim으로 선정하지 말자는 알고리즘
=> 이렇게 하려면 미래에 접근될 페이지를 미리 알아야 하는데 신이 아닌 이상 사실상 불가능하다.

그래도 알 수 있다고 가정하고 이런 알고리즘을 최적의 알고리즘으로 설정하자.
=> 이 알고리즘과 최대한 가까운 성능을 보이는 알고리즘이 좋은 알고리즘일 것이다.

페이지 폴트가 발생한 시점에서 차후에 가장 나중에 접근될 페이지를 victim으로 선정한다.

 

이렇게 했을 때는 페이지 폴트가 6번 발생한다.

 

3. Least Recently Used Algorithm

미래를 예측하기 위한 가장 좋은 정보는 과거의 정보라고 했다.

Locality에 의해 과거에 자주 접근된 데이터는 미래에도 자주 접근될 것이다.

따라서 최근에 접근된 페이지는 앞으로도 접근될 가능성이 높을 것이다.
=> 최근에 가장 오래 전에 접근이 된 페이지를 victim으로 선정한다.

과거의 접근 행태를 보고 미래에 접근될 데이터를 예측.

optimal은 미래를 내다봤다면, LRU는 과거를 본다.

 

LRU 알고리즘은 컴퓨터를 배우는 사람이라면 모두가 알고있어야 할 만큼 시스템에서 많이 사용되는 알고리즘이다.

그런데 LRU 알고리즘을 구현한다고 했을 때 발생하는 문제가 있다.

 

LRU 알고리즘을 OS에 구현하려면, 일단 메모리에 올라온 각각의 페이지가 최근에 언제 접근되었는지 timestamp가 다 찍혀 있어야 한다.
각 페이지에 대한 timestamp 정보들이 별도로 관리가 되어야 한다.

OS에서 페이지 배열 정보를 갖고 있는 자료 구조가 있다.
=> 바로 페이지 테이블이다.

페이지 테이블에는 모든 페이지에 대한 매핑 정보가 저장되어 있다.

페이지 테이블에 column 하나를 추가해서 최근에 접근된 시간을 기록한다면, 모든 페이지들이 언제 접근되었는지 기록할 수 있다. 

그런데 페이지 테이블에 기록하는 space 오버헤드는 그렇다고 치고, victim을 선정해야 할 때 페이지 테이블에서 각 페이지의 timestamp를 보고 min 값을 찾아야 한다. => O(N)이 소요된다.
time 오버헤드가 너무 크다는 문제가 있다.

페이지 폴트가 나면 페이지 폴트 핸들러는 O(N)에 걸쳐 가장 오래 전에 접근된 페이지를 찾아야 한다.

그럼 LRU를 사용하지 못하는 건가?
LRU와 비슷하지만 타임 오버헤드는 확 줄어드는 알고리즘이 없을까?
=> LRU approximation algorithm

 

그 전에 LRU 구현의 방식을 조금 변경해서 오버헤드를 줄일 수 있는지 살펴보자.

Counter implementation

timestamp를 찍기 위해서는 타이머라는 device에서 시간 값을 받아와야 하는데, 타이머도 장치이므로 I/O가 발생해야 한다.
물론 디스크 접근처럼 오래 걸리는 I/O는 아니지만 그래도 I/O니까 시간이 조금은 걸린다.
굳이 정확한 시간을 받아와서 기록할 필요가 있을까??

CPU count라는 변수를 갖고 있고, CPU가 메모리에 접근할 때마다 Count값을 1 증가시킨다.

=> 즉, CPU가 메모리에 접근한 횟수가 CPU count가 된다.

CPU가 메모리에 접근할 때, 해당 페이지에 Count 값을 기록한다.
이 Count 값이 가장 작은 페이지가 가장 오래 전에 접근된 페이지가 된다.

그런데 그렇다고 하더라도 여전히 victim을 찾기 위해 O(N)의 시간이 소요된다는 문제는 해결되지 않는다.

 

Stack implementation

페이지들을 double linked list로 구현해서 가장 최근에 접근된 페이지를 스택의 가장 위로 올린다.

이렇게 하려면 모든 페이지들은 prev와 next 포인터를 갖고 있어야 하기 때문에 double linked list이다.

페이지 폴트가 발생한 시점에서 Stack의 제일 아래에 있는 페이지가 가장 접근된지 오래된 페이지가 된다.

O(1)만에 victim을 선정할 수 있다.

하지만 이 Stack을 유지하기 위한 오버헤드가 발생하게 된다.

7을 접근했을 때, 7을 top으로 올리기 위한 오버헤드가 발생한다.

7을 위로 올리기 위해서는 6번 포인터에 접근을 해서 포인터 값을 바꿔야 한다.
=> 즉, 6번의 메모리 접근이 발생하게 된다.
이 Stack을 유지하기 위해 메모리 접근마다 메모리에 접근해야 하는 오버헤드가 발생한다.

victim 선정 오버헤드를 줄이기 위해 자료구조를 유지하는 오버헤드가 매우 커진다.

 

Search를 위한 overhead와 자료 구조 유지를 위한 오버헤드는 하나를 줄이면 하나가 커지는 관계다.

LRU를 사용하려면 어쩔 수 없이 오버헤드가 발생하게 된다.
오버헤드를 줄이려면 LRU 성능을 조금 포기할 수 밖에 없겠다.

 

LRU Approximation Algorithms

Reference bit

페이지마다 이 페이지가 참조가 됐으면 1, 참조가 안 됐으면 0으로 표시한다.
처음에 이 페이지가 올라오면 0으로 설정되고, 나중에 이 페이지가 다시 한 번 참조되면 1로 바뀐다.
이 값은 주기적으로 0으로 다시 reset을 해준다.

victim을 선정할 때 reference bit이 0인 애들을 victim으로 선정하겠다.

그리고 Search할 때 bit가 0인 애들 중 아무거나 하나를 찾으면 되므로, Search 오버헤드가 많이 줄어든다.

그런데 victim을 선정해야 하는 시점에 0인 애들이 꽤 많이 있을텐데, 그 중에 누가 더 오래 전에 참조됐는지는 구분이 안 된다.
=> 이건 너무 심하게 간략화한 것 같다.

 

Additional Reference Bits Algorithm

Reference bit 1비트 외에 추가적인 Reference bit를 사용한다.

주기적으로 0으로 reset하지 말고, 현재 Reference bit를 Most Significant Bit(MSB)에 적고 shift right 한다.

=> 즉, 과거의 접근 정보를 저장하는 것이다.

8개의 추가적인 비트가 과거에 대한 정보가 되는 것이다.

 

그런데 이 방식을 사용하기 위해서는 비트를 더 많이 사용해야 하므로 space 오버헤드가 발생하고, LRU 알고리즘과 똑같이 모든 페이지의 Additional Reference bit를 확인해서 victim을 선정해야 하므로 time 오버헤드도 발생하게 된다.
=> 이것도 사용하기가 좀 그렇다.

 

Clock algorithm

각 페이지는 1bit의 Reference bit를 갖고, 페이지들은 Circular queue에 관리된다.

다음 번에 victim으로 선정될 페이지를 가리키는 포인터가 있다.
=> 이 포인터가 가리키는 페이지를 victim으로 선정한다.

이 포인터가 가리키는 페이지의 reference bit가 0이면 그냥 얘를 victim으로 선정한다.

이 포인터가 가리키는 페이지의 reference bit가 1이면 최근에 참조가 되었다는 뜻이므로 이 페이지를 victim으로 선정하지 않고 reference bit를 0으로 바꾼다. 그런 다음 포인터를 한 칸 옮겨서 다음 페이지를 가리키게 한다.
=> reference bit가 0인 애를 만날 때까지 포인터를 전진

Reference bit algorithm과의 차이는 reference bit algorithm에서는 0들 사이에서 누가 더 오래됐는지를 구분할 수 없다는 것이다.
그런데 여기서는 도는 순서가 정해져 있기 때문에 방금 전에 0으로 바꾼 비트와 아까 전에 0으로 바꾼 비트는 순서 상의 차이로 구분할 수 있다는 뜻이다.

 

0으로 바꾸고 한 바퀴를 돌고 다시 왔을 때 여전히 0이면, 한 바퀴를 돌 동안 접근이 되지 않았다는 뜻이므로 그때는 victim으로 선정한다.

앞서 말했듯이, 0인 bit 사이에도 더 오래 전에 참조가 되었던 페이지를 구분할 수 있게 된다.

다시 돌아왔을 때 더 먼저 만난 0이 더 오래 전에 0으로 바뀐 bit일 것이다.
=> 얘가 victim으로 선정되어야 한다.

 

Second change(clock) page-replacement algorithm은 성능이 좋으면서도 space overhead와 time overhead가 그렇게 크지 않은 좋은 알고리즘이다.

Counting Algorithms

지금까지는 접근 시점을 기준으로 가장 오래 전에 접근된 페이지를 victim으로 선정했다.

접근 시점도 중요하지만 접근 빈도도 중요한 요소가 될 수 있다.

예를 들어 어떤 페이지는 바로 직전에 한 번 접근이 되었고, 다른 페이지는 엄청 많이 접근이 되었는데 방금 전에는 접근이 되지 않았다.

LRU 알고리즘을 사용하면 많이 접근된 페이지가 방금 전에 접근되지 않았다는 이유로 가차없이 victim으로 선정이 된다.

 

LFU (Least Frequently Used) Algorithm

최근 접근 횟수가 가장 적은 페이지를 victim으로 선정하는 방식

 

MFU (Most Frequently Used) Algorithm

최근에 가장 자주 접근된 페이지를 victim으로 선정하자는 방식

 

말도 안 되는 소리처럼 보일 수 있지만, 나름의 철학이 있다.

접근 빈도가 낮은 페이지는 최근에 메모리에 올라와서 그럴 수 있다는 아이디어
=> 앞으로 자주 접근될 가능성이 있다.

접근 빈도가 높았던 페이지는 오래 전에 올라와서 충분히 접근이 되었으므로 앞으로는 접근 빈도가 낮을 수도 있기 때문에 victim으로 선정한다.

 

시스템의 목적에 따라, 어떤 어플리케이션을 돌리는 시스템인지에 따라 LFU가 좋은 경우도 있고 MFU가 좋은 경우도 있다. => 어떤 알고리즘이 좋다고 단정지어 얘기할 수 없다.

대신 일반적으로는 어떤 것이 더 좋은지를 따져봤을 때 LRU 알고리즘이 가장 좋더라.

 

※ 본 내용은 한양대학교 강수용 교수님의 강의를 기반으로 작성되었습니다.