[운영체제] 9. 가상 메모리 : Working Set, PFF 알고리즘 (Virtual Memory 2)

1. Working-Set

 프로그램이 메모리에서 원활하게 실행되기 위해서는 어느 정도의 Page Frame을 확보해야 합니다. 그리고 프로그램은 특정 시간에는 특정 메모리 위치만 집중적으로 참조하는 특징이 있습니다. 예를 들어 for문이 실행되고 있는 동안에는 그 루프를 구성하는 페이지만 집중적으로 참조됩니다. 이렇게 집중적으로 참조되는 해당 page 들의 집합을 Locality set이라고 합니다.

 

 이것을 Working-Set 알고리즘에서는 working-set이라고 부릅니다. 정리하자면 Locality에 기반해서, 프로세스가 일정 시간 동안 원활하게 수행되기 위해 한꺼번에 메모리에 올라와있어야 하는 page의 집합을 working-set이라고 합니다. 이렇게 어느 정도 page를 보장해 주어 프로그램이 원활하게 실행이 되도록 합니다.

 

 하지만 너무 많은 프로그램들이 메모리에 올라가있으면 Working-set을 보장할 수 없는 상태가 됩니다. 예를 들어 Working set이 페이지 5개로 되어있는데, 할당할 수 있는 페이지가 3개라고 가정해 보겠습니다. 이럴 경우에는 페이지 3개가 아닌 5개가 필요하기 때문에 모든 페이지를 반납하며 페이지를 5개 줄 때까지 받질 않습니다. Working set이 한꺼번에 메모리에 올라가는 게 보장이 되지 않으면 전체를 다 반납하고 프로세스가 디스크로 Swap out 됩니다. 이런 상태가 되면 프로그램은 Suspended 상태가 됩니다.

 

 

 

Working-Set Algorithm

 Working set은 미리 알 수 없기 때문에, 과거를 통해 추정을 합니다. 동시에 메모리에 올리면 좋은 페이지들을 미리 알고 올릴 수 있다면 좋겠지만 그것을 모르기 때문입니다. 과거 델타 시간 동안 참조된 페이지들을 working set으로 간주해서 그 시간 동안 참조된 페이지들은 내쫓지 않고 메모리에 유지합니다. 이 델타 시간을 Window라고 합니다.

 

Working-set model (출처 : Operating System Concepts   - Abraham Silberschatz)

 만약 현재 시점을 t1이라고 한다면 window 사이즈(그림에서는 10)만큼 메모리에 올려놓습니다. 과거에 참조한 10개의 페이지를 확인 후 서로 다른 페이지들{1,2,5,6,7}을 나열합니다. t1에서는 이 5개의 페이지가 프로그램의 working set입니다.

 

 이 프로그램에게 다섯 개의 page frame을 줄 수 있다면 해당 페이지를 메모리에 올리고, 메모리 공간이 부족해 5개 페이지를 다 주지 못하면 모두 디스크로 Swap out 시키고 suspend 상태로 바꿉니다.

 

 working set은 그때그때마다 바뀌는데, 그림에서 t2 시점에서의 working set는 {3,4}의 두 개의 페이지입니다. 참조된 페이지를 델타 시간동안 유지하다가 버리게 됩니다. working set이 보장되지 않을 경우엔 Swap out 시켜 메모리에 남아있는 프로그램만이라고 Working set을 보장받게 해 줍니다. 나중에 메모리에 여유가 생겨 working set이 전부 보장되면, 이 프로그램을 메모리에 올려놓게 됩니다.

 

 이렇게 working set 알고리즘은 Multiprogramming Degree를 조절하고 Thrashing을 방지하게 됩니다.

 

 

 

 

 

2. PFF(Page-Fault Frequency)

PFF 알고리즘도 Multiprogramming Degree를 조절하며 Thrashing을 방지하는 알고리즘입니다. 하지만 working set처럼 working set을 추정하는 것이 아닌 직접 Page fault rate를 보는 방법입니다. 

 

 만약 특정 프로그램이 Page fault 를 많이 내고 있으면, 이 프로그램의 working set이 메모리에 보장되어있지 않은 상태라고 판단해 더 많은 page를 내어줍니다.

Page-fault frequency (출처 : Operating System Concepts   - Abraham Silberschatz)

 

 위 그래프처럼, 보통은 프로그램에 할당된 메모리의 크기가 커지면 Page Fault 발생 비율이 줄어들게 됩니다. 프로그램 상황에 따라 곡선의 기울기는 다를 수 있지만, 어떤 프로그램의 Page Fault Rate이 일정 수준 이상으로 발생한다고 하면, Working set 보장이 안된다고 판단하여 Page 수를 늘립니다. 그렇게 Page Fault Rate을 줄여줍니다. 반대로 Page Fault Rate이 너무 적으면 그런 프로그램으로부터는 page 수를 줄여 적정한 선을 맞추어줍니다.

 

 만약 어떤 프로그램이 Page Fault Rate이 빈번한데, 그 프로그램에 더 할당해 줄 메모리가 없다면 그 프로그램을 통째로 Swap out 시키게 됩니다. 그래서 메모리에 남아있는 프로그램만이라도 Page Fault Rate이 일정 수준으로 유지시키며 Thrashing을 방지합니다.

 

 

 

 

 

Page size의 결정

 page size는 어떻게 결정되어야하는지에 대해 간단히 살펴보겠습니다. 

 

 Paging 시스템에서는 동일한 크기의 Page 단위로 물리적 메모리 frame을 자르고, 가상 메모리의 프로그램을 구성하는 주소 공간도 page로 자르게 됩니다. 그리고 보통 page size는 4KB로 사용하고 있습니다.

 

 하지만 메모리 주소체계가 32비트에서 64비트로 바뀌고 메모리 크기도 점점 커지고 있기 때문에, page size가 너무 작으면 page table이 너무 커지며 낭비가 될 수 있습니다. 그래서 메모리 크기가 커지면서 page size도 크게 잡아야 할 필요성이 생겼습니다. 최근에는 Larger page size를 사용하는 메모리 시스템도 등장하고 있습니다. 

 

 

 

페이지 사이즈에 따른 파급 효과를 살펴보겠습니다.

 

 

 만약 Page size를 줄이면 페이지 수가 증가하고 페이지 테이블 크기가 증가하게 됩니다. 이렇게 되면 페이지 테이블을 관리하는 데 필요한 추가적인 오버헤드가 발생하고, 메모리 공간이 낭비될 수 있습니다.

 

 대신 메모리의 주소 공간이 더 세분화되어, 작은 조각들이 메모리에 쉽게 할당될 수 있습니다. 이렇게 되면 내부 조각이 발생할 가능성을 줄여 메모리 공간의 낭비를 최소화할 수 있습니다

 

 그리고 페이지 사이즈가 작을수록 필요한 정보만을 메모리에 올리고 저장할 수 있어 메모리 이용을 효율적으로 할 수 있습니다. 페이지 크기가 크면 페이지 중 아주 작은 부분만 필요해도 페이지 전체를 올려야하는 문제가 있었는데 이런 경우가 줄어드는 것입니다. 

 

 

 반면에 Page size가 커지면 페이지 테이블의 크기가 줄어들어 메모리 공간을 절약할 수 있지만, 이로 인해 내부 조각 문제가 발생할 수 있습니다. 큰 페이지 사이즈에서는 작은 조각의 데이터도 전체 페이지를 할당해야 해서 내부 조각 문제와 메모리 낭비가 크게 발생할 수 있습니다.

 

 또, locality 측면에서는 좋지 않을 수 있습니다. 작은 페이지 사이즈에서는 데이터가 메모리에 분산되어 있어서 메모리 참조 패턴에 따른 locality를 유지하기 쉽지만, 큰 페이지 사이즈에서는 한 번에 많은 양의 데이터를 메모리로 가져오기 때문에 locality를 유지하기 어려울 수 있습니다.

 

 디스크 전송의 효율성도 낮아질 수 있습니다. 작은 페이지 사이즈에서는 디스크로부터 데이터를 읽을 때 Seek 및 Rotation이 적게 발생하고 전송량이 적어서 효율적이지만, 큰 페이지 사이즈에서는 이런 효율성이 감소됩니다. 

 

 

 

 

참고자료

[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