Virtual Memory

https://core.ewha.ac.kr/publicview/C0101020140509151648408460?vmode=f

반효경 [운영체제] 22. Virtual Memory 1

 

가상 메모리에 대해 배워 보자.

가상 메모리는 OS가 관여한다.

 

Demand Paging

요청이 있으면 페이징, 즉 페이지를 메모리에 올린다는 뜻이다. 

프로그램이 실행될 때 모든 페이지를 메모리에 올리지 않는다. 디맨드 페이징 기법을 사용한다.

프로그램 내에서 빈번히 사용되는 페이지는 지극히 제한적이다.

좋은 SW일수록 방어적으로 SW를 설계한다. 방어적인 코드, 즉 예외처리와 같은 코드가 많다. 

방어적인 코드들은 많이 사용되지 않는다.

 

장점

- 디맨드 페이징을 쓰면 필요한 것만 메모리에 올리기 때문에 IO의 양이 많이 감소한다. 

- 멀티프로그래밍 환경에서 더 많은 사용자가 메모리에 올라갈 수 있다

- 빠른 응답 시간 : system wide하게 전체적으로 생각하는 관점에서의 응답 시간 

- 메모리 사용량 감소 

 

Valid/InValid bit 의 사용 

맨 오른쪽이 swap area 또는 backing store이다.

물리적 메모리에 올라가 있는 0,2,5번 페이지는 페이지 테이블의 valid-invalid bit이 valid이다. 의미있는 주소변환 정보를 갖고 있다. 

나머지 페이지들은 backing store에 내려가 있어서 invalid 이다.

그 외에도 이 프로그램이 사용하지 않는 페이지 엔트리인 경우 invalid 이다. 

위 프로그램은 A~F까지의 페이지로 구성된다. G,H는 사용되지 않는다. 

하지만 주소공간에서 지원하는 만큼은 페이지 엔트리를 만들어야 해서 만든 것이다. 

 

즉 주소변환을 통해 물리적인 프레임을얻을 수 있어야한 valid이다. 

 

CPU가 논리주소를 통해 메모리 몇번지를 보겠다고 하면 먼저 주소변환을 한다. 

그런데 1페이지는 메모리에 페이지가 없으니까 일단 메모리에 먼저 올려야 한다. 디스크에서 메모리에 올리는 것이므로 이것은 IO 작업이다. 

요청한 페이지가 메모리에 없는 경우를 page fault가 났다고 한다. 

page fault가 나면 CPU는 자동적으로 OS에게 넘어간다. 이것을 page fault trap이라고 한다. 일종의 SW 인터럽트다.

OS가 fault난 페이지를 메모리에 올리는 작업이 필요하다.

 

Page Fault

page fault 처리 루틴

 

invalid 페이지를 접근하면 MMU(주소변환을 해주는 HW)가 page fault trap을 발생시킨다.

커널 모드로 들어가서 page fault handler를 실행한다. 

1. 잘못된 요청인지 확인한다 (bad address, protection violation) => abort

2. 빈 페이지 프레임을 획득한다. 없으면 페이지를 쫓아낸다. 

3. 페이지를 디스크에서 메모리로 읽어온다.

- disk IO가 끝날때까지 이 프로세스는 CPU를 preempt 당한다. block 상태가 된다. 

- disk read가 끝나면 페이지 테이블 엔트리를 기록한다. invalid 에서 valid로 바꾼다. 

- ready queue에 프로세스를 삽입한다. 

4. 프로세스가 CPU를 잡고 running

5. 중단된 instruction 재개 

 

page fault 가 발생하는 비율에 따라 demand paging의 성능이 결정된다. 

메모리 접근하는 시간을 page fault까지 감안해서 계산해보자.

p가 page fault가 나는 비율이다. 

(1-p)*메모리 접근 시간 : page fault가 안났으니까 메모리 접근만 하면 된다. 

p*(OS로 cpu가 넘어가고, HW적으로 page fault를 처리하고, 페이지 프레임이 꽉 찼으면 swap out하고, swap in하고, CPU를 다시 얻으면 restart하는 시간)

 

Page replacement

빈 페이지 프레임이 없는 경우 페이지를 쫓아내는 것이다. 

OS가 하는 일으로, 어떤 페이지를 쫓아낼지 결정한다. 

여기에 사용되는 알고리즘을 replacement algorithm이라 한다. 

이 알고리즘은 가능하면 page fault가 나지 않고 메모리에서 바로 처리 가능하도록 해야 한다. 

쫓아낸 페이지가 다시 참조가 되거나 하면 안좋다. 즉 가급적 page fault rate이 낮아지도록 해야 한다. 

reference string은 페이지가 참조되는 순서를 나타낸 것이다. 예를 들면 1,2,3,4,1,2,5,1,2,3,4,5 와 같다. 

 

즉 page replacement 는 쫓아낼 victim을 골라서 swap out 시키는 것이다. 

페이지가 메모리로 올라온 이후에 write가 발생해서 메모리가 변경되었다면?

swap out만 하는것이 아니라 변경된 내용을 backing store에 써줘야 한다. 

쫓겨난 페이지는 invalid로, swap in한 페이지는 valid로 바꿔준다. 

운영체제가 하는 일이다. 

 

Optimal Algorithm

최적의 알고리즘이다. 단 reference string을 다 안다는 가정하에 가능하다. 따라서 실제로 사용될 수는 없다. 

그래서 Offline Optimal Algorithm이라 부른다.

가장 먼 미래에 참조되는 페이지를 쫓아내는 방식이다. 

4page frame 예시

빨간색이 page fault가 난 것이다. 처음에는 메모리가 비어 있으니까 처음 올리는 페이지들은 page fault가 난다.

연보라색이 페이지 폴트가 나지 않고 메모리에서 참조한 것이다.

5번을 참조할 때 보면 페이지 프레임이 꽉 차서 5번을 swap in 하기 위해 4번을 swap out한다. 왜냐하면 4번이 가장 먼 미래에 참조되기 때문이다. 

결과적으로 총 6번의 page fault가 발생한다. 

이것은 최적 알고리즘이므로 어떤 알고리즘을 써도 페이지 폴트를 6번보다 적게 낼 수는 없다. 

 

이 알고리즘은 결국 실제 시스템에서 사용하지는 못한다.

다른 알고리즘의 성능에 대한 upper bound를 제공하는 데 의미가 있다. 

아무리 좋은 알고리즘을 만들어도 이거보다 성능이 좋을 수 없다는 것이다. 

다른 이름으로는 Belady's optimal algorithm, MIN, OPT 등이 있다.

 

이제부터 미래를 모르는 상황, 즉 실제 상황에서 사용 가능한 알고리즘에 대해 배워보자.

FIFO 

삐뽀 알고리즘

First In First Out으로 메모리에 먼저 들어온 페이지를 쫓아내는 방식이다. 

이 알고리즘은 특이한 성질이 있다. 메모리 크기를 늘려주면 일반적으로 성능이 늘어난다.

삐뽀는 메모리 크기를 늘려줬는데 성능이 저하되는 현상이 발생할 때도 있다.

이것을 삐뽀 Anomaly라 한다. (또는 Belady's Anomaly

LRU 

LRU 알고리즘

실제로 가장 많이 사용하는 알고리즘이다. Least Recently Used

가장 오래 전에 참조된 페이지를 지운다. 

중간에 5가 swap in 될때를 보면 그 시점 기준 가장 오래 전에 사용된 페이지인 3번을 swap out 시켰다.

 

삐뽀는 먼저 들어오면 무조건 먼저 쫓겨난다. 먼저 들어왔어도 계속 사용될 수 있는건데.. 

그래서 엘알유는 가장 오래 전에 사용된 페이지를 쫓아낸다.

 

미래를 모르면 과거를 보자. 최근에 참조된 페이지가 가까운 미래에 참조될 확률이 높다고 보는 것이다.

LFU

Least Frequently Used로 가장 덜 빈번하게 사용된 페이지를 쫓아낸다. 

즉 참조 횟수가 제일 적은 페이지를 메모리에서 쫓아내는 것이다. 

 

참조 횟수가 제일 적은 페이지가 여러개 있다면??

- LFU 알고리즘 자체에서는 임의로 선정한다.

- 성능 향상을 위해서는 참조 횟수가 동률인 페이지 중에서 가장 오래전에 참조된 페이지를 쫓아낼 수도 있다.

 

장단점

- LRU처럼 직전 참조 시점만 보는게 아니라 페이지의 인기도를 더 정확히 반영할 수 있다.

- 참조 시점의 최근성을 반영하지 못함 

- LRU보다 구현이 복잡함 

 

예제를 통해 장단점을 알아보자

LRU의 경우 1번을 쫓아낸다. 왜냐하면 가장 참조 오래 전에 참조되었기 때문이다.

하지만 1페이지는 참조 횟수가 가장 많다. LRU는 이걸 고려하지 못하는게 단점이다. 

 

LFU 알고리즘은 4번을 쫓아낸다. 가장 적게 참조되었기 때문이다.

하지만 4페이지는 가장 최근에 참조되었다. LFU는 이걸 고려하지 못한다. 

 

LRU와 LFU의 구현 

구현은 어떻게 할까? 알아보자.

 

 

LRU

LRU는 가장 오래 전에 참조된 페이지부터 링크드리스트 형태로 나열한다. 

새로 참조한 페이지는 가장 아래쪽으로 이동시킨다 

쫓아낼 때는 제일 위에서 쫓아내면 된다. 

리스트 형태로 구현하면 O(1)의 시간복잡도를 갖는다. 즉 쫓아내기 위해 비교가 필요없다. 

만약 페이지마다 참조된 시간을 기록해놓는다면 쫓아내기 위해 다 비교해야 하므로 O(n)의 시간복잡도가 걸린다.

 

LFU

비슷하게 가장 참조횟수가 적은 페이지가 맨 위에 있고, 밑으로 갈수록 참조 횟수가 적어지도록 나열할 수 있다. 

새로운 참조가 발생하면 아래 페이지들이랑 비교하면서 어디까지 내려갈 수 있는지 확인해야 한다.

따라 O(n)의 시간복잡도를 갖는다. 그래서 비효율적이라 이렇게 구현 안한다. 대신 Heap을 사용한다.

힙을쓰면된다

부모가 자식보다 참조횟수가 적은 형태의 힙을 구성한다. 

자식이랑만 비교하면 되어서 O(logn)의 시간복잡도를 갖는다.

왜냐하면 노드가 n개이면 이진트리의 높이는 logn이 되기 때문이다.

쫓아낼 때는 root를 쫓아내고 힙을 재구성하면 된다. 

 

다양한 캐싱 환경 

캐싱 기법 

- 한정된 빠른 공간인 캐시에 요청된 데이터를 저장해 두었다가 후속 요청시 캐시로부터 직접 서비스하는 방식 

- 페이징 시스템 외에도 캐시 메모리, 버퍼 캐싱, 웹 캐싱 등 다양한 분야에서 사용한다. 

캐시 운영의 시간 제약 

- 교체 알고리즘에 삭제할 항목을 결정하는 데 시간이 적게 걸려야 함 

- 버퍼 캐싱, 웹 캐싱은 O(1),O(logn) 정도까지 허용 

 

페이징 시스템에서 LRU, LFU를 사용할 수 있을까?

LRU, LFU를 쓰려면 OS가 물리 메모리에 올라가 있는 페이지 중 가장 전에 참조된, 또는 가장 적게 참조된 페이지를 알아야 하는데 알 수 없다. 

왜냐하면 CPU가 요청한 페이지가 이미 물리 메모리에 올라가 있는 경우에는 OS에게 CPU가 넘어가지 않는다. 

따라서 메모리에 이미 있던 페이지에 관해서는 OS가 알 수가 없다.

페이지 폴트가 나면 CPU 제어권이 OS에게 넘어온다. 디스크에 있던 페이지가 메모리로 swap in 되는 시간은 알 수 있다. 

따라서 페이지 폴트가 발생하는 경우에만 페이지의 정보만 알 수 있어서 페이징 시스템에서 LRU, LFU를 사용할 수 없다.

 

Clock Algorithm

그렇다면 페이징 시스템에서는 무슨 알고리즘을 써야 할까 ? 바로 클락 알고리즘이다.

LRU의 근사 알고리즘이다. Second chance algorithm, NUR, NRU와 같은 이름으로 불린다. 

 

하드웨어가 조작하는 비트가 있다. 하드웨어가 조작하므로 페이지 폴트가 아닌 상황에도 조작 가능하다. 

reference bit : 최근에 참조된 페이지면 1

modified bit(dirty bit) : 최근에 변경된 페이지면 1 (IO를 동반하는 페이지)

 

페이지 폴트가 발생하면 OS는 레퍼런스 비트를 보고 페이지가 최근에 참조되었는지 확인해서 victim을 결정한다.

이때, 1인 페이지를 찾으면 0으로 값을 바꾸고 다음 페이지를 본다. 

그래서 레퍼런스 비트가 최근에 참조되었는지 확인할 수 있는 정보인 것이다. 

레퍼런스 비트가 0이면 시계바늘이 한바퀴 돌 동안 참조되지 않은 페이지라는 뜻이다. 

LRU와 같은 효과까지는 아니지만 비슷한 정도까지는 가능하다. 

페이징 시스템에서 일반적으로 사용하는 알고리즘이다. 

 

모디파이드 비트는 왜 필요할까? 

페이지를 스왑-아웃 할때 모디파이드 비트가 0이면 단순히 쫓아내기만 하면 된다. 

모디파이드 비트가 1이면 배킹 스토어에 쫓아낼 때 수정된 내용을 반영해야 한다. 

수정 여부를 알아야 하기 때문에 모디파이드 비트를 사용하는 것이다. 

 

클락 알고리즘을 개선할 수 있다.

모디파이드 비트가 1인 페이지를 쫓아내면 배킹 스토어에 쓰는 작업까지 해야 한다. 

따라서 모디파이드 비트가 0인 페이지를 우선적으로 쫓아내면 시간을 절약할 수 있다. 

 

페이지 프레임의 할당 

각 프로세스에 얼만큼의 페이지 프레임을 할당할 것인가? 

지금까지 배운 방법들을 생각해보면 페이지가 어떤 프로세스의 페이지인지 신경쓰지 않고 조건에 따라 swap out 시켰다.

하지만 프로세스를 원활하게 실행하기 위해서는 프로세스의 몇몇 페이지들이 메모리에 올라가 있어야 한다.

예를 들어 loop 같은 경우 한번에 페이지가 할당되는 것이 유리하다. 왜냐하면 매 루프 마다 요청이 있기 때문이다.

즉 프로세스에게 적어도 몇개의 페이지 프레임을 줘야 페이지 폴트가 잘 발생하지 않는 페이지 개수가 존재한다. 

프로그램 별로 페이지 할당을 해주지 않으면  특정 프로그램이 페이지 프레임을 장악해버리는 문제도 발생할 수 있다. 

 

Allocation Scheme

- Equal allocation : 모든 프로세스의 동일한 개수 할당 

- Proportional allocation : 프로세스 크기에 비례하여 할당 

- Priority allocation : 프로세스의 priority에 따라 다르게 할당 

 

Global vs local replacement

글로벌 

- 삐뽀, LRU, LFU등의 알고리즘을 global replacement로 사용할 수 있다

- 즉 알아서 프로세스 별 페이지 프레임 수가 조절된다.

- working set, pff 알고리즘 사용

즉, 다른 프로세스의 페이지를 쫓아낼 수 있다. 

 

로컬 

- 자신에게 할당된 프레임 내에서만 replacement 한다 

- 삐뽀, LRU, LFU 알고리즘을 프로세스 별로 운영한다 

자신한테 할당된 페이지만 쫓아낼 수 있다. 

 

Thrashing

프로그램에게 최소 메모리도 할당되지 않으면 페이지 폴트가 자주 발생한다. 

x축은 메모리에 동시에 올라간 프로세스의 개수이다. y축은 cpu 이용률이다.

프로세스 수가 적을때는, 프로세스가 CPU만 사용하는 것이 아니고 IO도 하고 다른 일도 한다. 

그 때 CPU가 놀기 때문에 이용률이 낮다. 

따라서 멀티프로그래밍 디그리를 올릴수록 CPU 사용률도 증가한다.

 

하지만 스래싱이 발생하면 CPU 사용률이 감소한다. 

왜냐하면 프로세스 당 할당받은 메모리가 너무 적어지게 된다. 

그래서 프로세스가 CPU를 잡아도 페이지를 참조하려고 하면 메모리에 없다. IO를 해서 swap in 해야한다. 

즉 페이지 폴트가 빈번히 발생해서 CPU 이용률이 낮아진다. CPU가 할 일이 없어진다. 

하지만 OS 입장에서는 CPU 이용률이 낮으니까 프로세스 수를 늘린다. (MPD를 높인다)

 

즉 어떤 프로세스가 CPU를 잡아도 높은 확률로 페이지 폴트가 발생하고, 프로세스는 swap in/out을 하고,

CPU는 한가한 상태가 Trashing 상태이다. 

 

트래싱을 막기 위해서는 MPD를 조절해줘야 한다. 

 

Working set model

MPD를 조절해서 프로세스가 최소한의 메모리를 가질 수 있게 하는 것이 워킹 셋 모델이다. 

 

Locality of reference 

- 프로세스는 특정 시간 동안 일정 장소만을 집중적으로 참조한다. 

- 집중적으로 참조되는 해당 페이지들의 집합을 locality set이라 한다. 

예를 들어 for loop가 실행되는 동안 루프를 구성하는 페이지가 집중적으로 참조된다. 

 

Working-Set Model 

워킹 셋 알고리즘에서는 로컬리티 셋을 워킹 셋이라고 부른다. 

워킹 셋이 적어도 메모리에 한꺼번에 올라와 있도록 보장해줘야 페이지 폴트가 잘 발생하지 않는다.

 

워킹 셋 모델에서는 프로세스의 워킹 셋을 메모리에 다 올릴 수 있는 게 아니라면 모든 페이지를 반납하고 swap out 된다. (suspend)

 

MPD를 조절해서 트래싱을 방지한다. 

 

Working Set algorithm

워킹 셋은 미리 알 수 없다. 과거를 통해 워킹 셋을 추정한다. 

과거 델타시간동안 참조된 페이지들을 워킹 셋으로 간주한다. 

델타시간을 window라고 부른다. 

델타 = 10인 상황에서 WS(t1)는 t1 시점부터 과거 10번째 까지 참조된 페이지들이다. 

WS에 해당되는 페이지는 메모리에 유지하고 속하지 않은 것은 버린다. 

다른 말로 표현하면, 참조된 페이지를 델타시간동안 유지하고 버리는 것이다.

 

프로세스의 워킹 셋이 페이지 프레임 수보다 크면 일부 프로세스를 스왑 아웃시켜서 남아있는 프로세스라도 워킹 셋을 보장해준다. (MPD를 줄인다)

워킹셋을 다 할당하고도 페이지 프레임이 남으면 스왑 아웃 되었던 프로세스에게 워킹 셋을 할당한다(MPD를 키운다)

 

Page Fault Frequency Scheme

이 방법도 MPD를 조절하며 트래슁을 방지하는 알고리즘이다. 

워킹셋처럼 워킹 셋을 추정하는 것이 아니라, 직접 페이지 폴트를 본다. 

현 시점에 시스템에서 페이지 폴트가 얼마나 나는지 보고, 특정 프로그램이 페이지 폴트를 얼마나 내는지 본다. 

페이지 폴트를 많이 일으키는 프로그램은 워킹 셋을 보장받지 못한다고 판단해 페이지를 더 할당해준다. 

페이지 프레임을 더 할당받으면 페이지 폴트 비율이 감소한다. 정도는 프로그램마다 다르다. 

 

페이지 폴트를 많이 일으키는 기준이 upper bound이고 이 비율보다 많이 일으키면 워킹 셋을 보장받지 못한다고 판단해 페이지 프레임 수를 늘려준다. 

페이지 폴트가 lower bound보다 발생하지 않는 프로그램은 페이지 프레임을 불필요하게 많이 할당받았다고 판단한다.

이런 프로세스로부터 페이지 프레임을 빼앗는다. 

 

PFF에서도 어떤 프로세스의 페이지 프레임을 늘려줘야 하는데 여분이 없다면

일부 프로세스들을 swap out 시켜서 남아있는 프로세스들이라도 워킹 셋을 만족하도록 한다. 

 

페이지 사이즈 결정 

주소가 32bit->64bit으로 변화함에 따라 페이지 사이즈도 키워줄 필요가 있다. 

 

페이지 사이즈가 감소하면 

- 페이지 수 증가 

- 페이지 테이블 크기 증가 (엔트리 수 증가, 필요로 하는 메모리 증가)

- 페이지 안에서 사용이 안되는 내부 조각 감소 

- 필요한 정보만 메모리에 올라와서 메모리 이용이 효율적 

- disk transfer 효율성 감소 . seek 할때 시간이 오래 걸리기 때문에 가능하면 한번의 seek에 큰 페이지를 가져오는 것이 효율적

 

최근 트렌드는 페이지 크기를 키우고 있다.