Page Replacement
페이지 폴트가 나면 운영체제는 디스크에서 메모리의 프레임으로 폴트가 난 페이지를 로드한다. 때때로, 어떤 프로세스들이 메모리 프레임을 모두 사용하고 있을 수도 있다. 이때, 운영체제는 페이지를 교체해야 되는데, 몇가지 페이지 교체 알고리즘이 있다.
페이지 폴트 알고리즘은 페이지 폴트 수가 적을 수록 좋은 알고리즘이다.
Belady's 알고리즘(Optiaml Page Replacement)
미래에 가장 오랜 시간 접근되지 않을 페이지를 교체하는 알고리즘으로, 모든 알고리즘 중에 가장 최적의 알고리즘이다. 다만, 미래를 예측하는게 불가능하기 때문에 구현할 수 없고, 다른 알고리즘에 대한 상한선(upper bound)를 제공한다. 따라서 어떤 알고리즘의 성능이 Belady's 알고리즘과 유사하다 하면 매우 좋은 알고리즘으로 평가할 수 있다.
FIFO
큐를 이용한 선입선출 방식으로, 가장 먼저 들어온 페이지를 먼저 교체하는 알고리즘이다. 오래전에 들어왔으니, 충분이 access 되었고, 이제 access 되지 않을 것이라 생각하고 동작하는 알고리즘으로, 프로그램이 꼭 이렇게 동작하지 않으니, 좋은 알고리즘이 아니다. 또한, 프레임 수를 늘렸는데, 오히려 page fault가 늘어나는 Belady's anomaly가 발생한다.
LRU
temporal locality를 이용해 가장 오래전에 access된 페이지(참조 시점이 가장 오래된 페이지)를 교체하는 알고리즘이다. counter와 stack을 이용해 구현한다.
counter 이용
PTE에서 Reference Bit(R)를 확인하고 R=0이면 counter를 1 증가시키고 R=1이면 counter를 0으로 초기화한다. 페이지 교체가 일어나게 되면, counter값이 가장 큰 페이지를 교체한다.
stack 이용
Second Chance
페이지 프레임을 원으로 정렬하고 시계바늘이 한바퀴 돌고 돌아왔을 때, R=1이면 0으로 세팅하고 지나가고 R=0이면 페이지 교체를 한다. 최근에 참조되지 않은 페이지를 교체 대상으로 삼는다는 점에서 LRU와 비슷하지만 그 페이지의 참조 시점이 가장 오래되었다는 것은 보장하지 못하기 때문에 LRU보다 알고리즘적으로는 성능이 좋지 않지만, 하드웨어적인 자원으로 동작하기 때문에 LRU보다 훨씬 빠르고 효율적이다.
NRU
Reference Bit, Modify Bit을 R,M 순으로 두고 비트를 세팅하여 00,01,10,11 중 숫자가 가장 낮은 숫자를 빼는 알고리즘이다. 예를들어 ????????????모르겠다
~
LFU
Counting Based page replacement 알고리즘이다. 1 clock당 software counter에 각각의 R비트를 shift right 하여 R비트를 저장한다. 특정 시점에 페이지 교체가 일어나야 한다면, 1의 수를 보고 얼마나 access 되었는지 판단할 수 있다.
- LFU(Least Frequently Used) : 가장 참조 횟수 적은 페이지 교체
- MFU(Most Frequently Used) : 가장 참조 횟수 많은 페이지 교체
예제에서 (e) 시점에서 페이지 교체가 일어날 때, LFU에 의하면 3번 페이지가 교체되어야 하고, MFU에 의하면 0번 페이지가 교체되어야 한다.
Allocation Of Frames
경쟁 관계에 있는 프로세스 중 어떤 프로세스를 메모리에 적재해야 하는가?(프레임을 어떻게 할당해야 하는가?)
- Fixed space algorithm : 모든 프로세스에 대해 프레임 수를 고정해서 할당한다. 더 필요하다고 더 할당하지 않고 페이지 교체를 통해 메모리 부족 문제를 해결하도록 한다. 웹 서버처럼 다중 사용자가 함께 쓰는 환경에 적합하다.
Local replacement - some process may do well, others suffer(어떤 프로세스는 잘되고 어떤 프로세스는 잘 안될 수 있음)- Variable space algorithm : 프로세스 당 사용할 수 있는 프레임 수를 제한하지 않고, 동적으로 변할 수 있게 한다. 개인 컴퓨터에서 노래 들으면서 크롬 켜고 코딩 하듯이 혼자 여러개 쓰는 환경에 적합하다.
Global Replacement - one process can ruin it for the rest(다른 프로세스 망칠 수 있음)
페이지 교체 방법
전역교체와 지역교체가 있다.
- 전역교체는 모든 페이지 프레임이 교체 대상이 되는 것을 의미한다. 전역교체 방법은 프로세스가 메모리를 미리 할당받지 않고 전체 메모리를 각 프로세스가 공유하면서 사용하고 교체에 따가 메모리 양이 가변적으로 변하는 것을 의미한다. 만약에 LRU를 이용해 전역교체를 한다면, 메모리에 올라와있는 전체 페이지들 중 가장 오래전에 참조된 페이지를 교체한다. 그 페이지가 어떤 프로세스의 페이지인지는 중요하지 않다. 즉, 다른 프로세스의 페이지를 빼앗아올 수 있는 것이다.
- 지역교체는 현재 수행중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법으로, 프로세스마다 페이지 프레임을 미리 할당받고, 해당 프로세스 내에서만 페이지 교체가 일어난다.
Thrashing
멀티프로그래밍 환경에서 동시에 수행되는 프로그램이 많아 CPU가 페이지 폴트를 수행하느라 다른 작업에 사용되지 못하는 것을 뜻한다. 프로세스마다 메모리 프레임 수를 적절하게 배분하는 것이 중요하다.
- 이를 해결하기 위한 방법
- Write out all pages of a process : 한 프로세스를 멈추고 디크스로 쫒아내기
- Buy more memory : 메모리 늘리기
운영체제가 Thrashing 해결하는 방법
- working set model
- PFF
Working Set Model
지역성을 기반으로 가장 많이 쓰이는 페이지 집합을 메모리 공간에 계속 상주 시켜 스레싱을 줄이는 방법
- Working Set : 프로세스가 일정 시간동안 원활히 수행되기 위해 메모리에 한꺼번에 올라가야 하는 페이지들의 집합
- working Set Size(WSS) : locality가 낮아지면 다양한 페이지가 참조되는 것이기 때문에 WSS가 커진다.
워킹셋이 한꺼번에 메모리에 올라갈 수 있는 경우에만 프로세스에 메모리를 할당한다. 그렇지 않을 경우 프로세스에 할당된 페이지를 모두 반납하고 프로세스 전체를 디스크 스왑영역으로 내린다. 직관적으로, Working Set은 메모리에 있는 것이 좋다. Working Set에 따라서 멀티프로그래밍의 정도를 계산할 수 있다. WSS를 파라미터로 넘기면 프로세스끼리 어떤 프로세스의 프레임을 빼앗아올지 판단할 수 있다. WSS가 여전히 메모리에 맞는다면 프로세스가 시작할 수 있도록 허용한다.
Working Set page replacement
PTE에 Time of last use 필드를 만들고 주기적으로 클럭이 돌면서 R비트를 0으로 초기화한다. 해당 페이지가 참조되면 R을 1로 세팅하고 R이 1이면 Time of last use를 current time으로 세팅한다. 만약 R이 0이면 current time에서 Time of last use를 빼서 t보다 크면 해당 페이지를 쫒아낸다.
위의 예제에서는 Time of last use가 1213인 페이지를 교체하면 된다.
PFF(Page Fault Frequency)
어떤 프로세스의 페이지 폴트율이 시스템에서 정한 상한값을 넘기면 이 프로세스에 프레임을 더 할당하는 방법이다. 만약 빈 프레임이 없으면, 페이지 폴트율이 하한값 이하로 떨어진 프로세스의 프레임 수를 줄인다. 모든 프로세스에 필요한 프레임을 다 할당하였는데, 프레임이 남는 경우, 스왑 아웃되었던 프로세스에게 프레임을 할당한다.
