가상 메모리 관리 Variable allocation 관리 방법

안녕하세요 저번에는 Fixed allocation 방법에 대해서 page를 분류하고 메모리를 좀 더 효율적으로 사용하는 방법에 대해서 알아보았는데요  page로 딱 나누었기 때문에 누구에게는 몇 개의 칸만 누구에게는 적게 이렇게 나눠 줬으면 됐었는데 사실 프로세스가 가변적으로 즉 프로세스를 나눈 크기가 페이지마다 크기가 다르다면 어떻게 나눠야 좋은 방법일까요?

 

오늘은 각 page들이 크기에 따르게 분할되고 Page 프레임이 한 프로세스에게 딱 공간을 주는 것이 아니라 필요할 때마다 할당해주고 메모리의 크기에 대해서 변할 때 알아보려고 합니다.

 

 

1 .Working set (ws) algorithm

working set 알고리즘은 특정한 일정 시간 동안 참조되었던 페이지들을 중복되지 않게 가지고 있는 SET 알고리즘입니다 

특정 시점 windowsize라고 하는데요 만약 특정 시간을 10초라고 잡았을 때에  프로세스가 시작한 지 약 1초가 지났다고 가정을 하면 1- 10 하여 -9 초부터 1 초까지 의 참조된 페이지들을 set이라고 가지고 있는 것입니다 말로 설명하면 조금 어려운데요 조금 더 쉽게 설명하여 보겠습니다

현재시간을 t라고 하고 세모를 우리가 정한 특정 시간이라고 가정을 하겠습니다 , 그러면 현재 시간에서 세모를 빼면 그 사이를 window size라고 합니다 한글 번역하면 창문 크기인데 저도 정확한 뜻은 잘 모르겠지만 볼 수 있다 해서 window 로한것 같아요

이렇게 window size 현재시간부터 특정하게 정해놓은 시간까지의  사용해놓은 페이지들의 집합들을 Working set이라고 합니다   ( 시간이 변하면 별할수록 window size 안에 가지고 있는 page 들은 계속 바뀐다는 것을 꼭 인지해야 합니다 )

 

window size 가 늘어나면 늘어날수록 WS 가 점점 늘어나다가 일정 시점이 되면 완만해지는 것을 알 수 있는데요 왜 이렇게 될까요? 다들 지역성이라고 하지만 제 생각에는 한 프로세스가 사용할 수 있는 page 수가 딱 정해지 있지 않지만 평균 내외에서 크게 달라지지 않을 것 같아서 그런 것 같습니다 정확한 정답은 없지만 한 번쯤 생각해보시면 좋을 것 같습니다 단점은 페이지 폴트가 없더라도 windowsize에 들어가지 못하면 page를 빼고 넣어야 하는 단점이 있습니다 

 

2. Page Fault Frequency (pff) algorithm

위에 설명한 방법은 오버 해드가 엄청 클 것 같습니다 만약 3이라는 window size 가 가지고 있다고 해보겠습니다 한 프로세스가 처음에 1초부터 3초까지  1, 2 , 3번이라는 프로세스를 사용하였습니다 그 후 그페이지 다음에  3~ 6초까지 2번 이라는 페이지만을 사용했다고 가정해보겠습니다 그후 6~9 초에는 1  , 3번을 사용했다면   다시 올려하는 지역성은 좋지만 계속하지 않아도 되는 i/o 를 작업하면 오버헤드가 엄청 큽니다 그래서 PFF라는 알고리즘 이나 왔습니다 

PFF 알고리즘은 특정 시간에 페이지 폴트가 나오면 그떄 메모리 i/o 작업을 해주자 라는것에서 나온알고리즘입니다 즉위에처럼 수시로 window size 를 정하여 매 시간마다 고침해주는것이 아니라 특정시간에 페이지 폴트가 나오면 메모리를 교체해주고 그렇지 않으면 메모리를 교체해주지 말자라는  라는 것에서 나온 알고리즘입니다 

 

t라는 Threshold value 즉 사용자가 직접 작성하는 paramter 값을 둔 후에 만약  페이 폴트 첫 발생한 시점에 시간이 내 가정한 t 값보다 작다면  ws에 넣고 그렇지 않으면 넣지 않는 것입니다  설명은 어렵지만 밑에 사진과 함께 설명하겠습니다

자 이렇게 t 값은 2 초로 지정했다고 가정하겠습니다 그 후 time이 0 인곳에서 1인곳까지의 t 값은 1- 0으로 1입니다 그러면 t값이 더 크다는것을 알 수 있습니다 time 이 0 인곳에는 0 , 3 , 4밖에 없었지만 다시한번 WS 에 적재 해두는것을 알수있습니다 자이제 time 1 인곳에서 4 인 곳까지 3 이라는 값이 나왔습니다 t 보다 < 3 이 더큰 값이 나왔습니다 그러자  1 ~ 4 까지 참조되었던 1 , 2 , 3 만 WS 에 적재 된다는것을 알수있습니다 

 

이렇게 page 폴트가 일어날떄마다 ws 에있는 것을 바꿔주는 알고리즘입니다 매번 새로고침을 하지 않기 때문에 오버헤드가 적다는 것을 알 수 있습니다 

 

3 . Variable MIN (VMIN) algorithm 

마지막 최적화 알고리즘인데요 가상 메모리에서 min이라고 나오는것은 그냥 실현이 불가능하다고 생각하시면 됩니다 왜냐 하면 프로세스가 어떤 페이지를 사용할지 예측을 os 가해야하는데요 그렇기에 실현이 불가능합니다 즉 내가 게임을 할떄마다 무슨챔피언을 할지 어느방향으로 움직일지 어떤 입력값이 들어올지 다예측한다는 말인데요 사실상 불가능한 알고리즘 입니다 가상메모리 최적화 성능향상 하는 부문에 MIN 이라면 실현이 그냥 불가능 합니다 하지만 왜 알아야 하냐 하면 우리가 만든 알고리즘을 테스트할 때 많이 사용하는 알고리즘입니다