[운영체제] 물리 메모리 해제와 할당의 동작 원리

목차

 

1. 물리 메모리 해제

1.1 LRU, LFU, FIFO 알고리즘

1.2 Clock 알고리즘

2. 물리 메모리 할당

2.1 Thrashing

2.2 working-set 알고리즘

2.3 pff 알고리즘

 

프로세스를 할당 할 때, 물리 메모리가 가득차 있으면, 특정 프로세스의 물리 메모리를 해제하고, 할당하려는 프로세스의 정보를 하드 디스크에서 읽어와 물리 메모리에 할당하게 된다.  그렇다면 물리 메모리는 어떤 기준으로 해제하는지 동작 원리에 대해 알아보자.

 

 

물리 메모리 해제

1. LRU, LFU, FIFO

 

1) LRU(Least Recently Used Algorithm)

가장 오랫동안 참조되지 않은 페이지를 교체하는 방법이다. 

2) LFU(Least Fequently Used Algorithm)

가장 적게 된 참조된 페이지를 교체하는 방법이다.

3) FIFO(First In First Out)

가장 먼저 물리 메모리에 할당되었던 페이지를 교체하는 방법이다. 

 

이렇게 단순하게 설명한 이유는 실제로 이 방식들은 페이지에서 물리 메모리를 해제하는데 사용될 수 없기 때문이다.

 

이 알고리즘들은 페이지에서 물리 메모리를 해제하는데 사용될 수 없다.

가상 메모리와 물리 메모리의 참조는 OS가 아닌 MMU 하드웨어가 한다. 따라서 OS는  page default가 일어난 후에만 CPU를 할당받는다. 어떤 페이지가 몇번 참조되었는지, 어느 순서로 참조되어있는지를 알기 위해선 OS가 연산을 해야하지만, MMU하드웨어에서 매핑 참조가 일어나므로 OS는 알 수가 없다. 따라서 이 방식들은 물리 메모리를 해제하는데 사용할 수 없다. 위의 알고리즘들을 사용할 수 없으므로, 물리 메모리를 해제하기 위해 Clock 알고리즘을 사용한다. 

 

 

2. Clock 알고리즘

 

Clock 알고리즘

 

 

앞서, 매핑은 MMU라는 하드웨어가 한다고하였는데, MMU는 페이지를 참조할 때마다 page table의 reference bit를 1로 설정해준다.  이후 page default가 발생했을 때, OS가 page table의 reference bit을 시계방향으로 돌면서, 1이면 0으로 바꾸고, 0인 페이지는 물리 메모리에서 해제하게 된다. 

 

이렇게 되면, page default가 발생할 동안 참조되었던 메모리는 해제되지 않고, 참조되지 않았던 메모리는 해제되게 된다.  이런 점에서 LRU와 유사한 알고리즘이다.  

 

 

물리 메모리 할당

1. Thrashing

Thrashing

 

일반적으로 프로그램을 많이 할당하면 CPU 사용률이 올라가게 된다. 그런데 어느 한계에 다다르면, CPU 사용률이 떨어지게 되는데 이를 Thrashing 이라고 한다.

 

1) 발생 이유

프로세스가 너무 많으면, 물리 메모리는 용량이 한정되어 있으므로, 각 프로세스의 page는 물리메모리에 할당할 파이가 적어지게 된다. 그러면 프로세스의 원활한 수행에 필요한 최소한의 page frame을 할당받지 못하게 되고 page default가 매우 자주 발생하게 된다. 어떤 프로세스가 CPU를 잡아도 계속 page default가 나서 디스크에 메모리를 받으러 I/O를 하게 되므로 CPU utilization은 매우 낮아지는 것이다. 그런데 여기에 추가로 OS는 CPU utilization이 너무 낮으니까 할당된 프로세스가 적은 줄알고 프로세스를 더욱 할당하게 된다. 

 

이러한 문제를 해결하기 위해 working set 알고리즘과 pff 알고리즘이 있다.

 

2. working set 알고리즘

working set

 

 

1) 개념

working set

프로세스가 특정 시점에 자주 참조하는 page들의 집합

최근 일정시간 동안 참조된 page들의 집합

window는 일정한 간격이지만, 시간은 계속 변화하므로 그때마다 working set은 다르다.

 

window

특정 시간의 범위 

 

2) 동작

프로세스 A가 window 시간동안 1 1 3 2 5의 페이지를 참조했다고 하면, working set은 1 2 3 5가 된다. working set에 포함된 페이지는 물리메모리에 할당하고, 나머지는 버려버린다.  이 알고리즘은 참조된 이후 window시간 동안만 page를 메모리에 유지한 후 버리는 것과 같다.

 

 

3. PFF 알고리즘

PFF 알고리즘

 

page default에 상한과 하한을 둬서 주황색 부분처럼 상한을 넘으면 프로세스에 frame을 더 할당하고, 하한값 이하이면

할당 frame 수를 줄이게 된다. 만약 빈 frame이 없으면 일부 프로세스를 swap  out 한다.

 

 

 

 

 

 

 

본 포스팅은 kowc 이화여대 반효경 교수님 운영체제 강의를 바탕으로 작성하였습니다.