[운영체제] CH9. Virtual Memory(3)

* 다양한 캐싱 환경

캐싱 기법이란 한정된 빠른 공간(=Cache)에 요청된 데이터를 저장해 두었다가 후속 요청 시 캐시로부터 직접 서비스하는 방식이다.

paging system 외에도 cache memory, buffer caching, web caching 등 다양한 분야에서 사용된다.

 

캐시 운영의 시간 제약

교체 알고리즘에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리는 경우 실제 시스템에서 사용할 수 없다.

대부분의 캐싱 환경에서는 O(1) ~ O(log n) 정도까지 허용한다.

 

 

그렇다면, Paging System에서 LRU, LFU와 같은 알고리즘을 사용할 수 있을까?

운영체제는 page table entry의 값이 valid인 경우에 주소 변환을 통해서 메모리에 접근한다.

하지만 invalid인 경우에는 trap(page fault)이 발생하게 되고, 이 때 운영체제가 CPU를 잡게 된다(Kernel mode).

그렇기 때문에 운영체제가 CPU를 잡은 시점에서 가장 오래 전에 참조된 페이지, 참조 횟수가 가장 적은 페이지에 대한 정보가 없다.

그래서 Clock Algorithm 이란 알고리즘을 사용한다.

 

Clock Algorithm

LRU의 근사(approximation) 알고리즘 이다.

Second chance Algorithm, NUR(Not Used Recently), NRU(Not Recently Used) 라고도 불린다.

자료구조로 Circular list를 사용하기 때문에 시계와 비슷하다고 해서 clock algorithm이란 이름이 붙었다.

 

Reference bit를 사용해서 교체 대상 페이지를 선정한다.

reference bit는 OS에 의해 초기에 0으로 초기화되고, 해당 페이지가 참조되었을 때 하드웨어에 의해 1로 변경된다.

 

해당 페이지가 참조되면 그 페이지의 reference bit을 1로 set해줌으로써 참조가 되었다는 것을 표시해준다. 이는 운영체제가 아닌 하드웨어가 담당하는 일이다.

운영체제가 victim을 찾을 때, reference bit를 참고한다.

reference bit가 1이면 0으로 바꾸고 다음을 조사한다. -> 한 번 더 기회를 주는 것

reference bit가 0이라는 것은 운영체제가 모든 페이지를 탐색하는 동안 한 번도 그 페이지가 참조되지 않았다는 의미이다. 그렇기 때문에 reference bit가 0인 페이지를 victim으로 선정한다.

 

Clock Algorithm의 개선

modified bit(= dirty bit)을 함께 사용하는 방법이다.

modified bit은 해당 페이지가 수정이 되었는지를 표시하는 비트이다.

• 0: 메모리에 올라온 후 수정되지 않은 페이지를 의미한다. 이미 backing store의 값과 동일하기 때문에 backing store에 새로 쓸 필요 없이 물리적 메모리에서 쫓아내는 작업만 수행한다.

• 1: 메모리에 올라온 이후 한 번 이상 내용을 수정한 페이지이다. backing store에 수정사항을 반영하고 메모리에서 쫓아낸다.

따라서 reference bit의 값이 0이고 modified bit의 값이 0인 것과 1인 것 두가지가 존재할 경우에는 0인 페이지를 victim으로 선정하는 것이 좋다.

결과적으로,

• reference bit = 1 : 최근에 참조된 페이지
• modified bit = 1 : 최근에 변경된 페이지 (I/O를 동반하는 페이지)

라고 할 수 있다.

 

따라서 (R, M) 이 있을 때, (1, 1) -> (1, 0) -> (0, 1) -> (0, 0) 순으로 victim으로 정하기 좋다.

 

Page Frame의 Allocation

이때까지의 페이지 교체 알고리즘은 어떤 프로세스에 해당하는 페이지인지 고려하지 않고 victim을 선정했다.

실제로는 프로그램이 원할히 실행되려면 일련의 페이지들이 같이 메모리에 적재되어야 더 효율적이다.

Allocation problem: 각 프로세스에 얼마만큼의 페이지 프레임을 할당할 것인가?

Allocation의 필요성

메모리 참조 명령어 수행 시 명령어, 데이터 등 여러 페이지를 동시에 참조하는 경우가 있다. 즉, 프로그램마다 할당되어야 하는 페이지의 수가 있는 것이다.

또한, loop를 구성하는 페이지들은 한꺼번에 allocate 되는 것이 유리하다. 최소한의 allocation이 없으면 매 loop마다 page fault가 발생하기 때문이다.

이러한 이유로 적절한 Allocation이 필요하다.

Allocation Scheme

• Equal allocation: 모든 프로세스에 똑같은 개수 할당
• Proportional allocation: 프로세스 크기에 비례하여 할당
• Priority allocation: 프로세스의 우선 순위에 따라 다르게 할당

 

Global vs. Local Replacement

Global replacement

replace 시 다른 프로세스에 할당된 프레임을 빼앗아 올 수 있다.

프로세스별 할당량을 조절하는 또 다른 방법이다.

FIFO, LRU, LFU 등의 알고리즘을 global replacement로 사용시에 해당한다.

 

Local replacement

자신(프로세스)에게 할당된 프레임 내에서만 replacement가 일어난다.

FIFO, LRU, LFU 등의 알고리즘을 프로세스 별로 운영시에 해당한다.

 

Thrashing

Thrashing이란 프로세스의 원활한 수행에 필요한 최소한의 페이지 프레임 수를 할당받지 못한 경우를 말한다.

실행중인 프로그램의 개수가 많아질수록,

전체적으로 Page fault rate가 높아지고 CPU utilization이 낮아진다.

CPU utilization이 낮아지면 운영체제는 MPD(MultiProgramming Degree)를 높여야 한다고 판단하게 된다.

그럼 또 다른 프로세스가 시스템에 추가되고, 프로세스 당 할당된 프레임의 수는 더욱 감소한다.

프로세스는 페이지의 swap in/swap out으로 매우 바빠지고, CPU utilization은 점점 나빠진다.

결과적으로 Low Throughput을 야기시킨다.

 

Thrashing을 방지하기 위해 Working-St Model, PFF Algorithm이 존재한다.

 

Working-Set Model

프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다. 이를 레퍼런스의 locality라고 한다.

집중적으로 참조되는 해당 페이지들의 집합을 locality set이라고 한다.

e.g) loop를 구성하는 페이지

 

Locality에 기반하여 프로세스가 일정 시간동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와 있어야 하는 페이지들의 집합을 Working Set 이라고 정의한다.

Working-Set Model에서는 프로세스의 working-set 전체가 메모리에 올라와 있어야 수행되고, 그렇지 않을 경우 모든 프레임을 반납한 후 swap out(suspend state)시킨다.

이는 Thrashing을 방지할 수 있고, Multiprogramming degree를 결정한다.

 

그럼 Working-Set은 어떻게 결정할까?

미래에 어떤 페이지들이 메모리에 올라가있는 것이 좋은지는 알 수 없다. 따라서 마찬가지로 과거의 정보를 통해 결정한다.

Working set window(dt)를 통해 알아낼 수 있다.

 

e.g) window의 크기가 10인 경우

첫번째 window의 경우, {1,2,5,6,7} 총 다섯 개의 페이지가 이 프로그램의 Working-set이다. 이 프로그램에게 다섯 개의 페이지를 할당할 수 있으면 이를 올리고, 그렇지 않으면 모두 swap out시키고 이 프로그램을 suspend 상태로 변경한다.

 

Page-Fault Frequency(PFF) Scheme

Working-Set Model과 마찬가지로 Multiprogramming degree를 조절하면서 Thrashing을 방지하는 방법이다.

page-fault rate의 상한값과 하한값을 둔다.

• page-fault rate가 상한값을 넘으면 프레임을 더 할당한다.
• page-fault rate가 하한값 이하면 할당 프레임 수를 줄인다.

빈 프레임이 없으면 일부 프로세스를 swap out 시킨다.

 

 

 

 

 

본 포스팅은 이화여대 반효경 교수님의 강의와 경북대 탁병철 교수님의 강의를 토대로 작성한 글입니다.