[운영체제] Page Fault를 줄이기 위한 운영체제의 노력

Paging System의 메모리 관리에서 운영체제는 Page Fault를 줄이는 것이 중요합니다.

Paging System (feat. Demand Paging)

Paging System이란 어떠한 프로그램(프로세스)를 메모리에 올릴 때, 일정 크기의 Page로 나눠서 올리는 것입니다. 그리고 대부분은 Demand paging을 사용하는데, 이는 실제로 필요할 때 필요한 만큼의 Page만 메모리에 올리는 것을 의미합니다.

이렇게 함으로써 얻는 이점은 I/O 감소, 메모리 사용량 감소, 빠른 응답시간, 더 많은 사용자 수용입니다.

이런 방법을 사용하기 위해, 논리주소와 실제 메모리 주소를 mapping시켜놓은 page table에서 'Valid / Invalid bit'를 사용합니다. 이는 해당 페이지가 메모리에 올라와있으면 1, 그렇지 않으면 0으로 표기합니다.

Page Fault란?

Paging System에서 어떤 논리 주소의 값을 읽어오는 과정에서 물리 메모리에 올라와있지 않는 경우, Backing Store(=Swap Area)에서 읽어오는 것을 의미합니다. Page Table에서 'Vaild / Invalid bit'이 0인 것을 참조하는 경우 발생합니다. Backing Store에 접근하는 것은 CPU가 직접 읽지 않고 I/O작업을 수행하는 것입니다. 메모리에 비에 속도가 몇 백 배 느린 저장장소이기 때문에 이를 줄이는 것이 전체적인 효율을 좌우합니다.

 

Page Fault를 줄이기 위해서 Page Replacement를 효율적으로 수행해야 합니다.

Page Fault의 과정

1. invalid page에 접근하면 MMU(Memory management unit, 논리주소를 물리주소로 바꾸는 하드웨어)가 trap(page fault)를 발생

2. Kernel mode로 들어가서 page fault handler가 invoke 됨.

3. valid한 요청인지 확인함. 아니라면 abort proces

4. 비어있는 페이지를 가져옴. 없으면 뺏어옴(-> Page Replacement)

5. disk에서 memory의 해당 페이지에 읽어옴. 그동안 해당 프로세는 block 됨.

6. valid / invalid bit을 1로 바꿈.

7. ready queue에 process를 insert

8. cpu가 다시 해당 프로세를 잡고 이어서 작업을 수행

 

위의 과정 중에서 Page Replacement는 운영체제가 수행하며, 효율적으로 수행해야 합니다. 여기서 효율적이라 함은 쫓아낸 page가 최대한 오랜 기간 동안 다시 참조되지 않아야 하는 것을 의미합니다.

 

Clock Algorithm

사실 미래에 어떤 페이지가 참조될지 정확히 알아낼 수 있는 방법은 없고, 과거의 history를 보고 유추하는 방법을 사용합니다. 이 방법에는 크게 두 가지가 있는데요. 하나는 LRU(Least Recently Used, 가장 오래전에 참조된 것을 지움)과 다른 하나는 LFU(Leat Frequently Used, 참조 횟수가 가장 적은 것을 지움)입니다.

 

그런데 위의 방법을 수행하는 데에는 하나의 큰 제약사항이 있습니다. 바로 각 페이지가 언제 참조됐고, 몇 번 참조됐는지 알아내는 것이 매우 어렵다는 것입니다. 왜냐하면 주소변환을 하여 메모리에서 읽어오는 일은 MMU와 CPU가 하드웨어적으로 하는 일이지, 운영체제는 오직 Page Fault가 발생했을 때만 개입하기 때문입니다.

 

이런 문제를 해결하기 위해서 하드웨어의 도움을 받아 reference bit와 modifed bit을 추가적으로 사용합니다. 이것은 page table에 valid / invalid bit과 함께 사용되며, MMU가 관리합니다. MMU가 해당 페이지 프레임을 참조하면 reference bit을 1로 바꾸고, 수정(Write)하는 작업을 수행하면 modified bit을 1로 바꿉니다.

 

위의 두 bit을 사용하여 Clock 알고리즘을 수행할 수 있습니다. 우선 각 페이지 프레임의 reference bit을  circular list로 구현합니다. 그리고 page fault가 발생했을 때, 포인터를 이동하며 reference bit 이 1이면 0으로 바꾸고, 0을 만나면 해당 페이지를 쫓아냅니다. 이를 다시 말하면, referece bit이 1이라는 것은 포인터가 한 바퀴 도는 동안 최소 한번 이상 참조됐다는 것을 의미하며, 0이라는 것은 한 번도 참조되지 않았다는 것을 의미합니다.

 

이 방법을 활용해서 정확히 언제 각 페이지 프레임들이 참조되었는지 알 수 없더라도 LRU와 근사한 결과를 도출할 수 있습니다.

 

추가적으로 modified bit이 1이라는 것은 쓰는 작업이 들어갔으므로 이 페이지를 쫓아내기 전에 backing store에 수정된 값을 다시 써야 하고 이는 시간이 오래 걸리는 작업입니다. 따라서 되도록 modified bit이 0인 것을 우선적으로 쫓아내면 조금 더 성능을 개선할 수 있습니다.

Page Fault를 줄이기 위해서 Page Allocation를 효율적으로 수행해야 합니다.

각 프로세스가 최소한의 page를 할당받지 못하면 Thrasing이 발생하여 Page Fault가 늘어납니다.

한 번에 하나의 프로세스만 실행된다면 CPU utilization이 떨어집니다. 왜냐하면 해당 프로세스가 I/O 작업을 하러 떠나면 CPU는 놀아야하기 때문이죠. 따라서, 동시에 실행되는 프로세스를 늘릴 수로 CPU utilization이 증가합니다. 하지만, 어느 시점부터는 CPU utilization이 뚝 떨어지는데, 이 현상이 Thrashing입니다.

 

한번에 여러 프로세스를 실행시키면, 각 프로세스마다 할당되는 페이지 프레임은 줄어들고, 어느 시점에서는 자주 호출되는 Page도 메모리에 올릴 수 없게 되어 항상 Page Fault가 발생하게 됩니다. 그러면 모든 프로세스가 연속적으로 Page Fault를 발생하게 되고 I/O를 해야 하기 때문에, CPU가 놀게 되는 것입니다.

 

따라서, 운영체제는 각 프로세스가 원활한 수행에 필요한 최소한의 page frame 수를 할당받을 수 있도록 해야 합니다. 

 

Working-Set Algorithm

어떤 프로세스가 집중적으로 참조하는 모든 프로세스의 집합을 locality set이라하며, Working-Set에서는 working set이라고 부릅니다. 다. 이 working set을 모두 메모리에 올려야 프로세스를 수행하고, 모두 올릴 만큼의 page frame이 부족하면 모두 할당받았던 page frame을 모두 반납하고 swap out(suspend)하는 것이 Working-Set Algorithm입니다. 여기서 working set은 특정시점과 window size 만큼 전 사이에 참조된 모든 페이지입니다. 달리 말하면, 참조된 후 window size만큼은 무조건 메모리에 유지하고 이후에 버리는 방법을 사용합니다. 

 

 PFF(Page-Fault Frequency) Scheme

이 방법은 한 프로세스의 page fault rate의 상한선과 하한선을 정해놓고, 이 사이를 맞춰나가는 것입니다. 하한선 보다 낮으면 할당 frame 수를 줄이고, 상한선 보다 높으면 frame을 더 할당합니다. 이 방법도 frame을 더 할당할 때 빈 frame이 없으면 해당 프로세스를 swap out 합니다.

 

추가적으로 위 두 방법은 replace시 다른 프로세스에 할당된 frame을 뺏어올 수 있으며 이를 global replacement라고 합니다. 반대로, 자신에게 할당된 frame만 뺏어오는 방법을 local replacement라고 하며, FIFO, LRU, LFU 등의 알고리즘을 process별로 운영시 사용합니다.