CS - 운영체제(10) 가상메모리

가상메모리는 physical memory(물리적 메모리)의 한계를 극복하고자 만들어졌다.
실제 메모리 주소가 아닌 가상의 메모리 주소를 주고, 이를 활용하는 기법이다.
지금까지 설명한 두 방식(page, segmentation)이 대표적인 가상메모리 방식 2가지다.

Demand Paging(요구 페이징)

이름 그대로 시스템이 요구하는 페이지만 물리 메모리에 올리는 것이다
이는 큰 장점들이 있는데.

입출력 양의 감소
메모리 사용량 감소
빠른 응답 시간(전체를 올리면 더 빠르지만, I/O양이 감소해 메모리 직접 엑셋스가 많아 빠름)
더 많은 사용자 수용
이 있다.

Demand paging은 기존의 paging과 작동방식이 몇가지만 다른데.

엔트리를 전부 invaild하게 표시
요청이오면 그제서야 메모리에 올리고 valid
요청한 엔트리가 없어서 메모리에 올릴땐, backingStore(보조기억장치)에서 꺼내와야한다. 입출력이기에, OS에 요청. 이는 곧 trap(소프트웨어적 예외)f처리를 말함
=> 이걸 page fault라고 표현.

page-replacement

backing store에서 페이지를 꺼내 메모리에 올려야하는데, 공간이 없으면 다른 페이지를 backing store로 내려야 한다. 이를 결정하는것이 OS이고, 역시나 효율적인 알고리즘이 존재한다. 요구사항은 다음과 같다.

page fault rate가 최소가 되어야함(보조기억장치 왔다갔따 시간 너무 오래걸림)
바로 사용할 page는 내리면 안된다
동일한 페이지가 올라왔다 내려왔다 가능해야함

이를 충족하는 알고리즘은 다양하다. 우리는 개중 제일 좋은 알고리즘을 알아보자

Optimal Alogorithm

미래에 불러올 paging을 모두 알고있으면, 제일 나중에 참조되는 page를 쫓아내면 된다!
하지만 현실의 시스템은 이럴수 없다. 미래에 뭘 참조할지 연산하는건 큰 낭비다...
그래도 이 알고리즘을 기준으로 성능을 비교하면, 훌륭한 비교수단이 된다

-Online algorithm : 입력이 차례대로 주어지는 알고리즘
-Offline algorithm : 입력 전체가 주어져야 작동하는 알고리즘

따라서 Optimal Algorithm은 Offline Algorithm이다!

FIFO(First-in-First-out)

자료구조 Queue의 알고리즘과 똑같다. 어디서 보지 않았는가?
cpu 스케줄링에도 FIFO가 있었다!(FCFS).
이 알고리즘은, 메모리 frame이 늘어날수록 성능이 저하된다.

LRU(Least Recently Used)

가장 오랫동안 참조되지 않은 page를 쫓아낸다.
아래 그림을 보면 1이라고 착각 할 수 있는데, 5를 참조한 시점 이전에 1과 2는 참조가 되었고 3이 제일 예전에 참조된 것이다. 따라서 3을 쫓아내고 5를 불러온다.

LFU(Least Freqeuncy Used)

참조가 제일 적게된 페이지를 쫓아낸다. 참조 횟수를 저장할 카운트가 필요하다. 따라서 위의 LRU보단 구현이 살짝 복잡하다.

LRU와 LFU 구현방식

LRU

LRU는 참조되는 순서로 LinkedLIst에 추가하면 된다.
제거할땐 head를 제거하면 끝
따라서 시간복잡도는 상수 O(1)이다.

LFU

LFU는 참조 횟수라는 값을 가져야 한다.
따라서 LinkedList가 아닌, min-heap을 사용하면 된다(당연한소리다)
시간복잡도는 heap의 탐색 시간인 O(log n)이다.

Paging System에서 LRU,LFU

이미 메모리에 올라와있을땐, 운영체제가 알 수 있는 방법이 없다.
하드웨어적으로 주소변환을 끝마치고 올린것이기 때문이다.
=> LRU나 LFU는 Virtual memory에선 불가능함...

Clock Algorithm

다행히 paging기법에 적용할 수 있는 알고리즘이 있다. LRU와 유사함.
-**reference bit(하드웨어)가 0인것을 찾을때까지 포인터를 이동

이동하면서 reference bit을 0으로 만듬.
0인걸 찾으면, 그 페이지를 backing store로 보냄
modified bit(쓰기, 하드웨어)가 1이면, backingstore에도 복사해줘야함. 가능하면 쫓아내지 않는다.

Page frame Allocation

demand paging기법은 프로세스를 page단위로 쪼개 메모리에 적재한다. 모든 page를 적재하진 않는다.
이때 프로세스에 page를 얼마만큼 할당해줄건지 결정해야만 한다. 나름의 우선순위가 있다.

가령 for문같이 반복문을 돌때 필요한 page는 다 할당해주면, page fault가 낮아진다. 이는 성능향상으로 직결된다.

아래는 페이지 프레임 할당 기준 3가지다.

eqaul allocation : 모든 프로세스에 똑같이 할당(비추)
proprtioanl allocation : 프로세스 크기 비례 할당(나름 합리적이라 볼수있음)
priority allocation : 우선순위 할당(starvation이 발생하진 않나?)

Global vs Local replacement

프로세스에게서 자원을 뺏는 preemptive(선점형)처럼 page frame할당도 다른 프로세스에 할당된 frame을 빼았는 방식이 존재한다. = Global

비 선점형(약간 다르긴하다)은 Local. 자기 자신의 frame내에서 할당-해제한다.

Thrashing

메모리에 페이지가 너무 적게 올라가있어, page fault가 너무 자주 발생하는 경우를 Thrashing이라 한다.

이럴때 운영체제가 재밌는 행동을 하는데...

이는 CPU 이용율을 떨어뜨린다 = I/O에 자주 인터럽트 됨
운영체제가 봤을때 CPU사용률이 저조 = 또다론 프로세스가 시스템에 추가된다
할당된 frame수는 더 감소하고, 프로세스의 page들은 더욱 swap이 빈번하게 일어난다
omg!

이를 예방하려면 메모리에 적제된 프로세스의 개수를 조절하거나, 프로그램이 어느정도의 메모리를 확보하게 해줘야 한다. 아래는 기본적인 해결방법들이다

Working-set Model

여기서 설명하는 Locality of reference는 캐시에서 사용하는 개념과 일치한다.
두 종류의 지역성이 있는데.

time locality : 시간 지역성. 최근에 접근한 데이터면 다시 접근가능성.
예를들어 for문에서 i는 짧은시간동안 수많은 참조가 이루어짐
space locality : 공간 지역성. 최근의 접근한 데이터 근처 접근가능성.
예를들어 Array를 연속적으로 탐색하는 것.

이 지역성을 기반으로 참조되는 page들의 집합을 locality set이라 한다.
또한, 지역성을 기반으로 프로세스가 일정시간 원할하게 수행되기 위해 메모리에 한번에 적재되어야 하는 page들의 집합을 Working Set 이라한다

이 WorkingSet이 메모리에 올라오지 못하면, frame을 모두 반납후 swap-out 상태가 된다