2024. 6. 2. 10:44ㆍCS/Operating System
피지컬한 메모리가 결국은 페이지 단위로 동작하고, 메모리가 부족하면 디스크로 내려보내게 될 것인데 어떤 프레임을 내려 보낼 것인가에 대한 얘기이다.
Page Replacement
- page fault가 발생했을 때 OS는 디스크에서 faulted page를 load 해서 메모리에 할당해줘야 한다.
- 그런데 운영체제가 메모리에 빈 프레임을 유지하기 위해서 어떤 페이지를 evict 시켜야 한다.
- eviction은 정해진 page replacement 알고리즘대로 동작하게 된다.
Evicting the best page
- replacement 알고리즘의 목적은 fault rate를 감소시키는 것이다.
- 가장 좋은 선택은 가장 오랫동안 사용되지 않을 페이지를 evict 하는 게 가장 좋다.
벨라디의 증명
- 가장 오랫동안 쓰이지 않을 메모리를 빼는 게 page fault가 가장 적게 일어난다고 벨라디가 수학적으로 증명했다.
- 가장 오랫동안 쓰이지 않을 페이지를 내리는 게 page fault를 가장 줄일 수 있고, 디스크에 접근하는 횟수를 줄일 수 있으므로 시스템 성능을 가장 올릴 수 있지만 어떤 페이지가 가장 오래 쓰이지 않을지 알 수 없다. 즉, 미래를 예측해야 한다.
- 벨라디의 증명의 유용한 점은 yardstick으로 사용할 수 있다는 것이다. 새로 짠 알고리즘이 벨라디와 비교해서 괜찮다면 사용해도 좋은 것이다.
FIFO
- 아주 심플하고 명확하다. 가장 먼저 들어온 페이지를 가장 먼저 내보내는 방식이다.
- FIFO가 좋을 것으로 보이는 이유는, 가장 먼저 들어온 만큼 가장 많이 사용되어서 앞으로 많이 쓰이지 않을 것이라고 생각될 수 있기 때문이다.
- 반대의 케이스도 충분히 가능하다.
- 밸라디 Anomaly(모순)이 생긴다. 당연히 피지컬한 메모리가 적은 게 page fault가 더 적어야 하는데 FIFO를 사용하면 메모리가 많아질수록 page fault가 더 많이 일어나는 모순된 케이스가 존재한다.
FIFO Example
frame 수는 3과 4이고 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5 순서로 액세스가 일어났을 때 page fault는 몇 번 일어날까?
벨라디의 모순은 항상 생기지는 않는다.
LRU(Least Recently Used)
- LRU는 reference information을 사용한다.
- 과거에 가장 오랫동안 사용되지 않은 페이지는 미래에도 사용되지 않는다고 locality를 사용한 예측 방법이다.
- replacement에서 과거에 가장 오랫동안 사용되지 않은 페이지를 evict 한다.
- LRU를 사용하면 좋긴 한데 과거의 기록을 계속 가지고 있어야 한다는 단점이 있다. 따라서 완벽하게 구현하기가 상당히 어렵다.
- 구현 사항은 다음과 같다.
- Counter : timestamp가 필요하다.
- Stack
LRU Example
- 페이지 테이블에 들어있는 R비트를 사용한다.
- counter-base approach
- 각 페이지마다 counter를 유지한다.
- 일정한 간격마다 모든 페이지에 대해 R bit가 0이면 counter를 증가시킨다. R이 1이면 counter를 0으로 초기화한다.
- 카운터는 그 인터벌의 수를 가지고 있다.
- 가장 큰 카운터를 가지는 페이지가 최근에 가장 적게 쓰인 페이지이다.
- 어떤 아키텍처는 R bit를 가지지 않는다.
- valid bit를 사용해서 r bit를 시뮬레이션할 수 있다.
- LRU를 완벽하게 구현하려면 계속 스캔해야 한다는 큰 오버헤드가 존재한다.
Second Chance
- LRU를 완벽하게 구현하면 계속 스캔해야 해서 오버헤드가 굉장히 크다는 점에서 고안되었다. 꽤나 오버헤드를 줄이면서 LRU와 유사하게 동작한다.
- 최근에 액세스 된 페이지에게 second chance를 주는 FIFO이다.
- big circle(clock) 안에서 모든 피지컬한 페이지 프레임을 순회한다.
- 동작 과정은 다음과 같다.
- 계속 스캔하면서 R bit을 체크하고 한 바퀴를 다 돈다.
- 한 clock 스캔이 끝났는데 R bit가 0이라면 eviction 1이라면 R bit를 0으로 만든다.
- R bit가 1일 때 0으로 만든다는 것은 한 번 살려주는 것, 즉 Second Chance를 주는 것이다.
- Second Chance를 줬는데도 여전히 0이라면 evict 한다.
- 마나 빨리 스캔할 것인지가 중요하다.
- count를 내부에 가지고 있거나 스캔할 필요는 없다.
- 여기서 말하는 스캔은 뭔가를 찾기 위해 스캔을 실행하 것이다. 여기서는 가볍게 백그라운드로 스캔 계속 돌리는 느낌이다.
- 쓸만하긴 하지만 시곗바늘을 돌리는걸 어떤 속도로 돌릴지 그런 것도 문제가 된다. 또, Second chance에 따라 빠진 페이지가 앞으로 오래 사용되지 않는다는 보장은 없다.
실제 리눅스에서는 큐를 둔다. 큐 두 개를 사용해서 잘 사용되지 않는 페이지를 inactive list에 넣어서 해당 큐의 페이지를 evict 하는 방식을 사용한다.
또 더 최근에는 MGLRU 방식으로 돌린다. 리스트를 세대별로 두고 LRU 하는 방식이다.
NRU (Not Recently Used)
second chance에서 조금 더 향상된 버전이다.
- LRU에서는 R bit을 보고 최신성을 생각했다면 NRU에서는 R, M을 보고 판단한다.
- 알고리즘은 다음과 같다.
- 최근에 액세스 되지 않은 페이지를 구분하기 위해 주기적으로 돌면서 R bit을 0으로 만든다.
- R, M bit에 따라 클래스를 지정하고, lowest numbered nonempty class에서 랜덤 하게 혹은 FIFO로 페이지를 삭제한다.
- 한 클락동안 참조되지 않았는데, 수정된 page를 유지하는 게 clean page보다 낫다고 판단한다.
- 처음에 cold page fault가 나서 메모리에 들어오면 R 0, M 0이다.
- 그리고 read가 일어나면 R 1, M 0이 된다.
- 여기서 다시 인터럽트(하드웨어에서 쏘는 인터럽트가 아닌 R 초기화)가 일어나서 다시 0 0이 될 수도 있다.
- R 1에서 write가 일어나면 R 1, M 1이 된다.
- 그리고 인터럽트가 돌아서 R 0, M 1이 될 수 있다.
- 총 4가지 상태가 될 수 있는 것이다. M이 1에서 0이 되는 일은 페이지가 완전히 빠졌다가 다시 들어올 때까지는 존재하지 않는다.
- 왜 dirty보다 clean을 빼는 게 더 나을까? 수정을 했다는 것은 값을 업데이트했다는 것이고, 뭔가 더 써먹으려고 수정했을 확률이 높기도 하고 더 중요한 건 디스크에 내리는 오버헤드가 적다. clean page는 디스크에 내용이 그대로 똑같이 있어서 페이지 테이블에서 프레임으로 할당 해제만 해도 된다.
- 하지만 dirty page는 할당을 해제하면서 디스크에 써주는 작업까지 해야 하므로 오버헤드가 더 크다.
- 장점은 이해하기도 쉽고 구현하기도 좀 더 쉬워 보인다. 최선은 아니지만 LRU보다는 조금 더 좋아 보인다.
LFU (Least frequently used)
Counting 기반의 page replacement이다.
- 각 페이지마다 소프트웨어 카운터가 있다.
- 각 clock마다, 각 페이지마다 R bit가 counter에 추가된다.
- 카운터는 각 페이지가 일정 주기마다 얼마나 자주 참조되었는지를 나타낸다.
LFU
- locality에 의해서 많이 참조되지 않은, 가장 적게 엑세스 된 페이지를 빼게 된다.
MFU
- 가장 많이 참조된 페이지를 빼는 것이다.
- 근거 1)
카운터가 적은 페이지는 이제 사용하려고 막 들어온 페이지이다. - 근거 2)
페이지는 프로세스의 초기 단계에 많이 사용되다가 나중에는 사용되지 않는다.
LFU와 MFU에 대해 공부하기 전에 결국 각 페이지가 얼마나 참조되었는지 알아야 한다.
따라서 Aging(counting) 기법이 필요하다. CPU 스케쥴링의 aging과는 다른 기법이다.
알고리즘이 어떻게 동작하는지 알아보자.
- 각 페이지의 R bit를 보고 counter 가장 왼쪽에 추가한다.
- 0~5번 페이지의 R bit을 봤더니 1 0 1 0 1 1이 되었으면 그걸 counter에 추가하는 것이다.
- 다음 클락에서 counter에 shift right를 수행한다.
어느 순간에 딱 봤을 때 어떤 페이지를 빼야 하냐면 1의 개수가 가장 적은 페이지를 빼면 된다.
- 액세스가 일어나면 1을 적기 때문에 1의 개수가 가장 적은 페이지가 최근에 참조된 횟수가 가장 적은 페이지이기 때문이다.
- 만약 어느 시점에 카운터의 값이 00100000이라면 내가 설정한 주기 안에서 액세스가 한 번 일어났다는 뜻이다.
카운터를 비트로 사용하는 이유는 8bit를 사용해서 카운팅 할 수 있기 때문이다. 그냥 숫자로 해서 +시키면 bit를 더 많이 사용해야 하고 하드웨어의 구현이 8bit가 더 편하다.
Allocation of Frames
Page Replacement와 전혀 다른 문제를 살펴보자면, 프로세스 A는 4개의 페이지, 프로세스 B는 6개의 페이지를 사용하고 있다.
이게 타당한가? 가 문제가 된다.
프로세스 A, B를 두고 다르게 프레임 수 제한을 걸었다면 그 타당성을 의심해봐야 한다. 각 프로세스별로 생각해 봤을 때 프레임을 얼마나 할당하는지를 생각해 보자.
멀티프로그래밍 환경에서 프로세스들은 메모리를 가지고 경쟁하게 된다. OS는 프레임을 누구에게 얼마나 할당할지를 고민해야 한다. 만약 B가 메모리를 더 요구해서 A의 메모리를 뺐어서 줘야 한다면 두 가지 방식을 생각할 수 있다.
Fixed space algorithms
- 모든 프로세스는 몇 개 이상의 프레임은 사용할 수 없다고 제한을 정해놓는 것이다. 참고로 페이지 4K와는 전혀 다른 얘기이다.
- Local replacement라고도 얘기하고, 만약 메모리가 부족하면 해당 프로세스가 사용하던 메모리 안에서 LRU를 돌리던가 해서 알아서 메모리를 확보하는 것이다.
Variable space algorithms
- 특별히 limit을 정해놓지 않고 모든 프로세스를 통틀어서 replacement 알고리즘을 적용시켜서 뺐어서라도 확보해 주는 것이다.
- Global replacement라고 얘기하고, 리눅스에서 실제 사용한다.
- 전체적인 성능에서 Variable space가 더 효율적이지만 Fairness가 깨지는 문제가 생길 수 있다. 따라서 대부분의 운영체제는 전체적인 성능은 fairness보다 중요하게 생각해서 variable space 알고리즘을 사용한다.
- 클라우드에서는 돈을 낸 만큼 CPU, 메모리를 사용하는 것이라 이렇게 하면 문제가 생길 수 있다.