[운영체제] 9. 가상 메모리 : Caching 기법, Clock Algorithm, Thrashing (Virtual Memory 2)

 지난 포스팅에서 가상 메모리 시스템에서 사용되는 Replacement 알고리즘에 대해 알아보았습니다.

 

 이번 포스팅에서는 Replacement 알고리즘이 가상 메모리가 아닌 다양한 Caching 환경(cache memory, buffer caching, Web caching 등)에서 쓰이는 것을 살펴보겠습니다.

 

다양한 Caching 환경

 Caching이란 한정된 빠른 공간(Cache)에 요청된 데이터를 저장해 두었다가, 다음에 똑같은 요청이 왔을 때 느린 저장 장치까지 가지 않고 Cache로부터 직접 서비스하는 방식입니다.

 

 다양한 Caching 환경들을 살펴보겠습니다.

 

 (1) Paging System

 지난 포스팅까지 살펴본 개념입니다. Paging System에서는 한정된 빠른 공간이 메인 메모리이고, 느린 저장 장치가 Backing Store입니다. 그래서 가능한 물리적 메모리에서 서비스를 하고, 메모리에 올라와 있지 않는 경우(Page Fault 발생 시)에만 Backing Store에서 읽어옵니다.

 

 (2) Cache Memory

 CPU가 메모리에 접근할 때, 메모리에 직접 접근하는 것이 아닌 CPU와 Main Memory 사이에 Cache memory를 두는 것입니다. 

Cache memory는 좀 더 빠른 계층으로, CPU가 Main memory에 접근하기 전, Cache memory를 확인해 요청된 내용이 있는지 살피고, 없는 경우에만 Main memory에 요청하게 됩니다. Cache memory 중 주소 변환을 위한 특유의 Cache memory는 TLB라고 부릅니다. 

 

(3) Buffer Caching

Buffer caching은 File System에 대한 Read/Write 요청을 메모리에서 빠르게 서비스하는 방식입니다.

 

Buffer caching과 File System에 대해서는 다음 포스팅에서 좀 더 자세히 알아보겠지만, Buffer cahing에서 빠른 공간은 물리적 메모리이고 느린 공간은 File System이라면, Paging System에서는 각각 물리적 메모리 Backing Store(Disk Swap Area)로 두 가지 시스템에서 유사한 매체를 둡니다.

 

(4) Web Caching

 사용자가 웹 브라우저를 사용할 때, 웹 페이지를 요청하면 웹 서버에서 그 페이지를 가져와 웹 브라우저에 표시를 하게 됩니다. 이전에 이미 요청한 URL을 나중에 또 요청하게 될 때, 이미 읽어왔던 웹 페이지를 저장해놓았다가 화면에 보여주는 방식입니다.

 

 Cache Memory와 Buffer Caching은 단일 시스템에서 저장 매체 간의 속도 차이로 Caching을 하는 것이고, 이와 다르게 Web Caching은 다른 컴퓨터에서 읽어오며 시간이 걸리는 것으로 다른 시스템 간에 시간을 줄이는 것입니다. 

 

 

 

캐시 운영의 시간 제약

 Replacement Algorithm에서 삭제할 항목을 결정하는 일에 지나치게 많은 시간이 걸리게 되면, 실제 시스템에서 사용할 수 없기 때문에 시간 제약 조건이 있습니다. Cache 안에 n개가 있는데, 어떤 것을 쫓아내기 위해 모든 것을 스캔하는 것은 시간 복잡도가 O(n)으로 오버헤드가 크게 발생하게 됩니다.

 

 Buffer Caching이나 Web Caching와 같은 대부분의 Caching 환경에서는 시간 복잡도가 O(1)에서 O(log n) 정도까지만 허용됩니다. 지난 포스팅에서의 LRU, LFU에서도 이 시간 복잡도를 만족한 것을 볼 수 있었습니다.

 

 하지만, 시간 복잡도만 만족한다고 될 것은 아니고, 지난 포스팅에서는 언급하지 않았지만 Paging 시스템에서는 큰 제약 조건들이 있습니다.

 

 

실제 Paging System에서 LRU, LFU 사용이 가능한가?

 결론부터 말씀드리면 Paging System에서 LFU(Lowest Frequency Used)와 LRU(Least Recently Used) 알고리즘은 일반적으로 는 잘 사용되지 않습니다.

 

 LFU 알고리즘은 페이지 교체 시 가장 적게 참조된 페이지를 선택하여 교체합니다. 그러나 이 알고리즘을 적용하기 위해서는 각 페이지의 참조 횟수를 추적해야 합니다. 그러나 실제로는 이러한 추적이 매우 복잡하고 비효율적입니다. 각 페이지에 대한 참조 횟수를 추적하는 것은 추가적인 메모리와 연산 비용 등 오버 헤드가 크기 때문에 현실적으로는 구현이 어렵습니다.

 

 LRU 알고리즘은 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식으로 동작합니다. 이 알고리즘은 페이지의 참조 순서를 추적하여 가장 오래 전에 참조된 페이지를 선택합니다. 그러나 이를 구현하기 위해서는 각 페이지에 대한 액세스 시간을 추적해야 합니다. 그래서 마찬가지로 오버헤드가 크기 때문에, 실제 시스템에서는 구현이 어렵습니다.

 

 

 그래서 대부분의 실제 시스템에서는 보다 간단하고 효율적인 알고리즘인 FIFO(First-In-First-Out)나 Clock(Second Chance) 알고리즘을 사용합니다. 위 두 가지 알고리즘은 비교적 적은 오버헤드로 효율적인 페이지 교체를 가능하게 합니다. FIFO에 대해서는 지난 포스팅에 알아보았습니다. Clock 알고리즘에 대해 알아보겠습니다. 

 

 

Clock Algorithm

 Clock 알고리즘은 최근에 사용되지 않은 페이지를 쫓아내는 방식으로 동작합니다. Second chance , NUR(Not Used Recently) 등 여러 명칭으로 불립니다.

(출처 : https://core.ewha.ac.kr/publicview/C0101020140513133424380501?vmode=f)

 

그림에서 각각의 사각형은 물리적 메모리에 있는 Page입니다. 그리고 각 페이지는 Reference Bit을 가지고 있습니다. 이 Reference Bit은 페이지가 CPU에 의해 참조될 때 1로 설정됩니다. 이 역할은 운영체제가 아니라 하드웨어가 수행합니다. 

 

 Page Fault가 발생하여 페이지를 교체해야 할 때, 운영체제는 하드웨어가 세팅해놓은 Reference Bit을 확인합니다. 포인터가 페이지들을 순환하면서 Reference Bit을 확인합니다. 만약 Reference Bit가 1이라면, 최근에 참조된 페이지입니다. 따라서 Reference Bit이 1인 페이지를 만나기 전까지 확인합니다. 만약 한 바퀴를 돌았는데도 Reference Bit이 0이면, 그때에는 해당 페이지를 교체합니다. 

 

  Reference Bit외에도 Modified Bit이 함께 사용됩니다. Modified Bit은 페이지가 쓰기 작업(Write)으로 변경되었는지를 나타냅니다. Modified Bit이 0이면 해당 페이지는 Backing store에서 물리적 메모리에 올라온 이후로 변경된 적이 없는 페이지입니다. 이러한 페이지를 내쫓을 때는 Backing Store에 이미 동일한 값을 가지고 있는 것이므로 그냥 메모리에서 내쫓으면 됩니다. 그리고 가능하면 Modified Bit이 0인 것을 우선으로 쫓아내면 조금 더 좋은 효율을 기대할 수 있습니다.

 

 Modified Bit이 1이면 해당 페이지는 최근에 변경된 적이 있으므로, 교체하기 전에 Backing Store에 변경된 내용을 반영해야 합니다.

 

 

 

 

 

Thrashing

프로그램에 메모리가 너무 적게 할당되어 Page Fault가 자주 발생하는 경우를 Thrashing이라고 부릅니다.

 

(출처 : Operating System Concepts   - Abraham Silberschatz)

 x축은 메모리에 동시에 올라가 있는 프로그램의 수이고, y축은 CPU 이용률입니다.

 

 프로그램이 늘어날 수록 어느 정도까진 CPU 이용률이 높아지지만 어느 순간부터는 비례하지 않습니다.

 

 예를 들어 설명하자면, 만약 메모리에 프로그램이 하나만 올라가 있다면 CPU 이용률이 매우 낮습니다. 왜냐하면 프로그램이 실행될 때 메모리만 사용하는 것이 아닌 I/O 작업을 하러 가는 경우에 CPU는 낭비되기 때문입니다. 

 

 만약 프로그램이 두 개 이상일 때는 프로그램 하나가 I/O작업을 하러 가더라도, 다른 프로그램이 CPU 제어권을 잡아서 일을 할 수 있습니다. 이런 이유로 특정 지점까지는 계속 CPU 이용률이 올라갑니다.

 

 그러다가 특정 지점에서는 CPU 이용률이 뚝 떨어지는데, 이 시점이 Thrashing이 발생한 순간입니다. 

 

 메모리에 동시에 올라가 있는 프로그램의 수가 많다는 것은, 각 프로그램이 갖고 있는 메모리의 용량이 작다는 뜻입니다. 프로세스에게 Page가 너무 적게 할당되면 CPU가 한 번 Instruction을 실행할 때, 그 페이지가 메모리에 없기 때문에 I/O 작업을 해야 합니다. 이때 CPU 제어권이 다른 프로그램에게 넘어가고, 그 프로그램을 실행하려는데 또 요청한 페이지가 메모리에 올라가 있지 않으면 I/O 작업을 다시 해야 합니다.

 

 이런 식으로 Page Fault가 많이 발생해 CPU 이용률이 낮아집니다. 그런데 운영체제는 CPU 이용률이 낮으면 프로그램이 메모리에 충분히 없다고 판단을 하기 때문에 계속해서 프로그램을 메모리에 올리게 됩니다. 프로그램을 올릴수록 메모리 용량이 작아지고 Page Fault는 빈번하게 발생하게 됩니다. 이러면 어떤 프로세스가 CPU를 잡든 거의 무조건 Page Fault가 발생하게 됩니다.

 

 이렇게 되면 페이지를 교체하는 작업에만 시간을 허비하고, 실제 CPU는 할 일이 없는 상황이 되어버립니다. 

 

 

이러한 현상을 막기 위해 각 프로그램이 어느 정도 메모리를 확보할 수 있도록 동시에 메모리에 올라가 있는 프로그램의 수를 조절해주어야 합니다. 이를 위한 알고리즘이 Working Set알고리즘과 PFF(Page-Fault Frequency) 알고리즘입니다.

 

 

다음 포스팅에서 이 알고리즘에 대해 알아보겠습니다. 

 

 

 

 

 

 

참고자료

[KOCW 이화여대 반효경 교수님 - Virtual Memory2]

https://core.ewha.ac.kr/publicview/C0101020140513133424380501?vmode=f

반효경 [운영체제] 23. Virtual Memory 2

 

[ Operating System Concepts - Abraham Silberschatz ]

https://www.yes24.com/Product/Goods/89496122

운영체제 - 예스24