이제야 가상메모리에 대해 다룬다. 전 시간에 배운 dynamic memory management나 dynamic memory allowcation은 하드웨어가 처리해줬다. 이젠 운영체제가 메모리 관리를 어떻게 하는지 알아보겠다.
가상메모리는 physical memory(물리적 메모리)의 한계를 극복하고자 만들어졌다.
실제 메모리 주소가 아닌 가상의 메모리 주소를 주고, 이를 활용하는 기법이다.
지금까지 설명한 두 방식(page, segmentation)이 대표적인 가상메모리 방식 2가지다.
이름 그대로 시스템이 요구하는 페이지만 물리 메모리에 올리는 것이다
이는 큰 장점들이 있는데.
Demand paging은 기존의 paging과 작동방식이 몇가지만 다른데.
backing store에서 페이지를 꺼내 메모리에 올려야하는데, 공간이 없으면 다른 페이지를 backing store로 내려야 한다. 이를 결정하는것이 OS이고, 역시나 효율적인 알고리즘이 존재한다. 요구사항은 다음과 같다.
이를 충족하는 알고리즘은 다양하다. 우리는 개중 제일 좋은 알고리즘을 알아보자
미래에 불러올 paging을 모두 알고있으면, 제일 나중에 참조되는 page를 쫓아내면 된다!
하지만 현실의 시스템은 이럴수 없다. 미래에 뭘 참조할지 연산하는건 큰 낭비다...
그래도 이 알고리즘을 기준으로 성능을 비교하면, 훌륭한 비교수단이 된다
-Online algorithm : 입력이 차례대로 주어지는 알고리즘
-Offline algorithm : 입력 전체가 주어져야 작동하는 알고리즘
따라서 Optimal Algorithm은 Offline Algorithm이다!
자료구조 Queue의 알고리즘과 똑같다. 어디서 보지 않았는가?
cpu 스케줄링에도 FIFO가 있었다!(FCFS).
이 알고리즘은, 메모리 frame이 늘어날수록 성능이 저하된다.
가장 오랫동안 참조되지 않은 page를 쫓아낸다.
아래 그림을 보면 1이라고 착각 할 수 있는데, 5를 참조한 시점 이전에 1과 2는 참조가 되었고 3이 제일 예전에 참조된 것이다. 따라서 3을 쫓아내고 5를 불러온다.
참조가 제일 적게된 페이지를 쫓아낸다. 참조 횟수를 저장할 카운트가 필요하다. 따라서 위의 LRU보단 구현이 살짝 복잡하다.
LRU
LFU
이미 메모리에 올라와있을땐, 운영체제가 알 수 있는 방법이 없다.
하드웨어적으로 주소변환을 끝마치고 올린것이기 때문이다.
=> LRU나 LFU는 Virtual memory에선 불가능함...
다행히 paging기법에 적용할 수 있는 알고리즘이 있다. LRU와 유사함.
-**reference bit(하드웨어)가 0인것을 찾을때까지 포인터를 이동
demand paging기법은 프로세스를 page단위로 쪼개 메모리에 적재한다. 모든 page를 적재하진 않는다.
이때 프로세스에 page를 얼마만큼 할당해줄건지 결정해야만 한다. 나름의 우선순위가 있다.
가령 for문같이 반복문을 돌때 필요한 page는 다 할당해주면, page fault가 낮아진다. 이는 성능향상으로 직결된다.
아래는 페이지 프레임 할당 기준 3가지다.
프로세스에게서 자원을 뺏는 preemptive(선점형)처럼 page frame할당도 다른 프로세스에 할당된 frame을 빼았는 방식이 존재한다. = Global
비 선점형(약간 다르긴하다)은 Local. 자기 자신의 frame내에서 할당-해제한다.
메모리에 페이지가 너무 적게 올라가있어, page fault가 너무 자주 발생하는 경우를 Thrashing이라 한다.
이럴때 운영체제가 재밌는 행동을 하는데...
이를 예방하려면 메모리에 적제된 프로세스의 개수를 조절하거나, 프로그램이 어느정도의 메모리를 확보하게 해줘야 한다. 아래는 기본적인 해결방법들이다
여기서 설명하는 Locality of reference는 캐시에서 사용하는 개념과 일치한다.
두 종류의 지역성이 있는데.
for
문에서 i
는 짧은시간동안 수많은 참조가 이루어짐Array
를 연속적으로 탐색하는 것.이 지역성을 기반으로 참조되는 page들의 집합을 locality set이라 한다.
또한, 지역성을 기반으로 프로세스가 일정시간 원할하게 수행되기 위해 메모리에 한번에 적재되어야 하는 page들의 집합을 Working Set 이라한다
이 WorkingSet이 메모리에 올라오지 못하면, frame을 모두 반납후 swap-out 상태가 된다
떼쓰는 녀석한테 떡하나 더 준다.
프로세스의 page fault가 높으면, page를 더 준다.
단, 남아있는 공간이 없으면, page fault높은 녀석은 swap-out시킨다.
징징이 컷!
page size가 작으면, 당연히 table도 커진다. 이는 공간의 낭비. 따라서 메모리 크기가 커지면, page의 크기도 키워야 한다.