Virtual Memory

이번시간에는 가상 메모리 챕터에서 페이지 프레임의 할당과 스레싱 그리고 이를 해결하기 위한 알고리즘들에 대해서 알아보도록 하겠습니다. 

Allocation of Frames

  프로세스가 정상적으로 작동하기 위해서는 적어도 일정 수준 이상의 페이지 프레임(메모리 공간)을 각 프로세스에게 할당 해야한다.(Each process needs a minimum numer of pages)

  프로세스 여러개가 동시에 수행되는 상황에서 각 프로세스에 얼마만큼의 메모리 공간(페이지 프레임)을 할당할 것인지 정해야한다. OS는 시스템의 성능 향상을 위해 효율적으로 메모리 공간을 프로세스에게 할당할 필요가 있다. 이때, 할당 알고리즘이 활용되는데 첫번째가 모든 프로세스에게 페이지 프레임을 균등하게 할당하는 균등할당, 프로세스의 크기에 비례해서 페이지 프레임을 할당하는 비례할당, 그리고 마지막으로 프로세스의 우선순위에 따라 페이지 프레임을 할당하는 우선순위 할당 방식이 있다. 

Local Replacement and Global Replacement

교체할 페이지를 선정할 때, 교체 대상이될 프레임의 범위를 어떻게 정할지에 따라 교체 방법을 전역교체와 지역교체로 구분할 수 있다. 전역교체 방법은 모든 페이지 프레임이 교체 대상이 될 수 있다. 이에 반해 지역 교체 방법은 현재 수행 중인 프로세스에게 할당된 프레임 내에서만 교체 대상을 선정할 수 있는 방법이다. 

Thrashing

앞서 모든 프로세스는 일정 수준 이상의 페이지 프레임을 할당 받아야 한다고 했다. 그래야 정상적으로 작동하기 때문이다. 하지만 일정 수준 이상의 페이지 프레임을 할당 받지 못하는 경우 시스템 상에 큰 문제가 발생 할 수 있다. 만약 CPU로부터 집중적으로 참조되는 페이지들이(page는 process를 구성하는 단위) 일정 수준 이상의 페이지 프레임을 할당 받지 못해 물리 메모리에 적재되지 못하게 되면 페이지 부재율(page fault rate)이 크게 상승해 CPU 이용률(CPU utilization)이 현저하게 떨어질 수 있다. 이를 스레싱이라 한다.

 

1. 운영체제는 CPU 이용률(CPU utilization)이 낮을 경우 물리 메모리에 올라와 있는 프로세스의 수가 적기 때문이라고 판단.
2. 준비 큐에 프로세스가 단 하나라도 있으면 CPU는 그 프로세스를 실행하므로 쉬지 않고 일하게 된다. 그런데 CPU이용률이 낮다는 것은 준비큐가 비어있는 경우가 발생한다는 뜻이다. 즉, 이는 메모리에 올라와 있는 프로세스의 수가 너무 적어 이들 프로세스가 모두 I/O 작업을 함으로써 준비 큐가 비는 경우가 발생한다는 뜻이다.
3. 따라서 CPU 이용률이 적게 되면 운영체제는 메모리에 올라가는 프로세스의 수를 늘리게 된다. 메모리에 동시에 올라와 있는 프로세스의 수를 다중 프로그래밍 정도(the degree of multiprogramming)라고 하는데, OS는 CPU이용률이 낮을 경우 다중 프로그래밍의 정도를 높이게 된다. 
4. 그런데, 다중프로그래밍의 정도를 지나치게 높이면 각 프로세스에게 할당된 메모리의 양이 지나치게 감소하게 된다. 그렇게 되면 각 프로세스는 그들이 원활하게 수행되기 위해 필요한 최소한의 페이지 프레임도 할당받지 못하는 상태가 되어 페이지 부재가 빈번하게 발생하게 된다. 
5. 이렇게 페이지 부재가 발생하면 디스크 I/O 작업을 수반하므로 context switching을 통해 다른 프로세스에게 CPU를 양도하게 된다. 이때, 이양받은 다른 프로세스 역시 할당 받은 페이지 프레임이 지나치게 적으면 페이지 부재가 발생할 수 밖에 없다. 그러면 또 다시 다른 프로세스에게 CPU가 이양되고 같은 상황이 반복되게 된다. 이런 상황을 스레싱이라 한다.

 

워킹셋(Working-Set) 알고리즘

  스레싱이 발생하지 않도록 하면서 CPU 이용률을 최대한으로 높일 수 있도록 다중프로그래밍의 정도를 조절하는 것이 중요하다. 이를 위한 방법이 워킹셋 알고리즘 방법과 페이지 부재 빈도 알고리즘 방법이 있다. 다시 말해, 이 방법들은 다중프로그래밍의 정도를 조절하여 CPU의 이용률을 최대한으로 높이는 동시에 스레싱이 발생하지 않도록 하는 방법이다

 

• Wokring-set Model: 프로세스는 일정 시간동안 특정 주소 영역을 집중적으로 참조하는 경향이 있다. 이렇게 집중적으로 참조되는 페이지들의 집합을 지역성 집합(locality set)이라 한다. 워킹셋 알고리즘은 이런 지역성 집합이 메모리에 동시에 올라갈 수 있도록 보장하는 메모리 관리 알고리즘.  워킹셋 알고리즘에서는 프로세스가 일정 시간 동안 원활히 수행되기 위해 한꺼번에 메모리에 올라와 있어야하는 페이지들의 집합을 워킹셋 집합이라고 정의하고, 프로세스의 워킹셋을 구성하는 페이지들이 모두 메모리에 올라갈 수 있는 경우에만 그 프로세스에게 메모리 공간을 할당한다. 만약 이를 충족하지 못하는 경우 프로세스에게 할당된 페이지 프레임들을 모두 반납하고 그 프로세스의 주소공간 전체를 디스크로 스왑 아웃시킨다.
• 따라서 워킹셋 알고리즘은 이와같은 방식으로 다중프로그래밍의 정도를 조절하고 스레싱을 방지한다. 워킹셋 알고리즘은 메모리에 올라와 있는 프로세스들의 워킹셋 크기의 합이 프레임의 수보다 클 경우 일부 프로세스를 스왑 아웃시켜서 남은 프로세스의 워킹셋이 메모리에 모두 올라가는 것을 보장 한다. 이는 MPD(Multi-Programming Degree)를 줄이는 효과가 있다. 반면에 프로세스들의 워킹셋을 모두 할당한 후에도 프레임이 남을 경우, 스왑 아웃되었던 프로세스를 다시 메모리에 올려서 워킹셋을 할당함으로써 MPD를 증가 시킨다. 이처럼 워킹셋 알고리즘은 CPU 이용률을 높게 유지하면서 MPD를 조절하여 스레싱을 방지한다. 

페이지 부재 빈도 알고리즘

• Page-Fault Frequency Allocation: 페이지 부재 빈도 알고리즘은 프로세스의 페이지 부재율을 주기적으로 관리하면서 각 프로세스에게 할당할 메모리의 양을 동적으로 조절한다. 어떤 프로세스의 페이지 부재율이 시스템에서 미리 정해놓은 상한값을 넘게 되면 이 프로세스에게 할당된 프레임의 수가 부족하다고 판단하여 프레임을 추가로 할당한다. 만약 추가로 할당할 빈 프레임이 없다면 메모리에 올라와 있는 일부 프로세스를 스왑 아웃시켜 올라가 있는 프로세스의 수를 조절한다. 반대로 시스템에서 설정한 하한값을 넘으면 이 프로세스에게 할당된 프레임의 수가 많다고 판단하여 할당된 프레임의 수를 줄인다. 이런식으로 MPD를 조절하면서 CPU 이용률을 높이면서 스레싱을 방지할 수 있다.