가상 메모리 관리

문딤·2022년 8월 19일

요구 페이징

필요한 프로그램만 메모리에 적재하는 방법.

프로세스의 이미지를 backing store에 저장한다.
backing store는 swap device로 하드웨어의 부분인데 페이지를 임시로 보관하는 공간이다.
프로세스는 페이지의 조합이기 때문에 필요한 페이지만 메모리에 올린다.

lazy swapper : 그 페이지가 필요하지 않는 한 메모리에 적재 되지 않는다.

⭕ 요구 페이징의 장점

필요한 페이지만 메모리에 적재하기 때문에 메모리 사용량이 감소한다.

프로세스 전체를 메모리에 올리는데 소요되는 입출력 오버헤드가 감소한다.

사용되지 않는 주소 영역에 대한 입출력이 줄어 응답시간이 줄어든다.

시스템이 더 많은 프로세스를 수용할 수 있게 해준다.

물리적 메모리의 제약을 벗어날 수 있다.

페이지 부재(page fault)

메모리에 페이지가 존재하는지 구별하기 위해 유효-무표비트(vaild_ invalid bit)를 두어 각 페이지가 존재하는지 표시한다.

이때 페이지가 메모리에 적재되지 않아 유효-무효 비트에 무효로 세팅되어 있는 경우를 페이지 부재가 일어났다고 한다.

◻ 페이징 부재 해소

운영체제가 해당 페이지에 대한 접근하기 위해 주소가 유효한지 확인합니다.

범위를 벗어나는 영역에 속한 페이지 접근이나 접근 권한 위반을 할 경우 프로세스를 종료시킵니다.

접근이 가능한 경우 물리적 메모리에 비어 있는 프레임을 할당받습니다.

비어 있는 프레임이 없다면 기존에 메모리에 올라와 있는 페이지 중 하나를 디스크로 내보냅니다. (스왑 아웃)

디스크로부터 메모리 적재는 오랜 시간이 걸립니다. 따라서 페이지 부재가 발생한 프로세스는 CPU를 반납하고 PCB에 현재상태를 저장 후 봉쇄 상태가 됩니다.

디스크 입출력이 완료되어 인터럽트가 발생하면, 해당 페이지의 유효-무효 비트를 유효로 수정합니다.

봉쇄되었던 프로세스를 준비 큐로 이동시킵니다.

CPU를 할당 받고 PCB로부터 저장한 값을 복원시켜 중단되었던 명령부터 실행을 이어갑니다.

Victim Page

페이지의 교체를 위해 특정 페이지를 몰아내는 page-out으로 victim - page를 만들어내야한다.

THEN

어떤 페이지를 희생양으로 만들지 선정하는데, 만약 페이지를 backing store로 몰아낼 때 페이지에 명령에 수정이 일어나지 않았으면 우리는 page-out 과정에서 수정을 할 필요가 없다. 하지만 명령에서 수정이 일어났다면 하드디스크에 저장하기 위해 수정하는 작업이 필요하다.

◻ 수정이 필요하지 않으면 몰아내는(page-out)과정만 필요하다.
◻ ++ 수정이 필요하다면 수정하는데 추가로 시간이 들어간다.

두 가지 경우에는 page-out 과정에서 발생하는 시간이 다르다.

따라서 시간을 절약하기 위해서 victim page로 수정되지 않은 페이지를 victim으로 선택하는 경우가 많다.

페이지 교체 알고리즘

FIFO(선입선출, 큐)

메모리에 먼저 올라온 페이지를 먼저 내보낸다는 알고리즘이다. 따라서 victim page의 대상은 가장 먼저 메모리에 올라온 페이지가 되는 것이다.

그러면 프레임의 수가 커질수록 페이지 결함은 어떻게 되겠는가?
FIFO의 알고리즘은 프레임의 수가 적을수록 페이지 결함이 더 많이 일어나게 된다.
계속 교체를 해주어야하기 때문이다. 하지만 프레임의 수가 많아질수록 페이지 결함의 횟수는 감소하게 된다.

💨 Belady’s Anomaly

OPT(Optimal)

가장 사용하지 않을 페이지를 가장 우선적으로 내려 보내는 알고리즘이다.

사용하지 않을 페이지를 우선적으로 보내므로 앞의 FIFO에 비해서 페이지 결함이 일어날 횟수가 많이 감소하는 것을 알 수 있다. 하지만 Optimal의 경우 앞으로도 사용이 잘 되지 않을 것이라는 보장이 없으므로 미래를 알 수 없는 조건에 의해 실질적으로 수행하기에는 큰 어려움이 있다고 할 수 있다.

LRU(Least-Recently-Used)

최근에 사용하지 않은 페이지를 가장 먼저 내려 보내는 알고리즘이다.

최근에 사용되지 않으면 나중에도 사용되지 않을 것이라는 아이디어로부터 온 것이다. OPT의 경우에는 미래에 대한 예측이지만 LRU의 경우에는 과거를 보고 판단하므로 실질적으로 사용 가능한 알고리즘이라고 할 수 있다.
비록 OPT 보단 페이지 결함이 더 일어날 수 있지만 실제로 사용할 수 있는 알고리즘 중에서는 좋은 방법 중 하나라고 할 수 있다.

LFU(Least Frequently Used Algorithm)

과거에 참조 횟수가 가장 적은 페이지를 교체 시킬 페이지로 결정하는 알고리즘.

Incache-LFU: 메모리에 적재될 때부터 페이지의 횟수를 카운트 하는 방식
Perfect-LFU: 메모리 적재 여부와 상관 없이 페이지의 과거 총 참조 횟수를 카운트 하는 방식

ex)

◻ 11번째로 5번을 참조 하려고 하면 페이지 폴트가 발생한다. 이 때 LRU 알고리즘은 1번 페이지 프레임을 교체하게 된다. 이에 반해 LFU 알고리즘은 참조 횟수가 가장 적은 4번 페이지 프레임을 교체하게 된다.

◻ 1번 페이지가 오랫동안 쓰이지 않았지만 LFU 알고리즘은 참조 횟수가 가장 적은 4번 페이지를 교체 했다. 그러나 앞으로 4번 페이지가 계속 사용되는 페이지 일 수도 있을것이다. 이처럼, LFU는 최신 흐름을 잘 반영하지 못할 수도 있다.

클럭 알고리즘 (NRU or NUR)

LRU처럼 가장 최근에 참조되지 않은 페이지를 대상으로 선정한다는 점에서 LRU와 근사하지만 교체되는 페이지의 참조 시점이 가장 오래되었다는 것을 보장하지는 않는다.

클럭 알고리즘은 참조 비트(reference bit)를 순차적으로 조사하며 동작한다.

프레임 내의 페이지가 참조될 때 하드웨어에 의해 1로 자동 세팅된다.

클럭 알고리즘은 한 바퀴 돌며 참조되지 않은 페이지의 참조 비트 값을 0으로 바꾼 후 지나간다.

참조 비트가 0인 페이지를 방문하면 해당 페이지를 교체한다.

페이지가 참조되어 1이 되고 , 한 바퀴 도는 동안 사용되지 않으면 0

💨 다시 한 바퀴 돌았을 때 사용되지 않는 페이지는 참조되지 않았으므로 교체 대상 페이지로 선정된다.

스레싱과 프레임 할당(정적, 동적)

CPU의 이용률과 프로세스의 수의 관계는 ❓

CPU이용률이 높을수록 효율이 좋다.
프로세스의 갯수가 증가할수록 CPU의 이용률은 증가한다.

💨 왜냐하면 프로세스의 수가 많아지면 적절하게 프로세스에 CPU를 할당할 수 있게 되고 이로 인해 CPU는 항상 일을 할 수 있게 된다.

BUT

앞에서 배운 요구 페이지 기법을 사용하게 되면 일정 범위 이상의 페이지가 메인 메모리에 올라오게 되면 CPU의 이용률이 감소하게 된다.
왜냐하면 페이지가 메인 메모리에서 가득 차 있게 되면 page-in/out을 통해 페이지 결함으로 CPU가 동작을 못 하는 시간이 늘어나기 때문이다.

스레싱

CPU 이용률이 떨어지는 일정범위를 넘는 부분을 '스레싱'이라 한다.

THEN

프로세스 당 충분한 수의 메모리를 할당한다는 것
=> 적절한 프레임을 할당한다는 것이다.

프레임 할당

정적 할당은 프로세스의 크기를 알기 때문에 이를 통해 프레임을 할당하는 방식이다.

균등 할당의 경우 각 프로세스 당 동일한 프레임을 할당하는 것이다.
비례 할당은 프로세스의 크기에 따라 비례적으로 나누는 방식이다.

하지만 프로세스마다 주요 사용하는 페이지가 다르다.
따라서 원래 프로세스의 크기와는 다르게 적용이 될 수도 있다.

💨 이를 고려하여 프레임을 할당하는 방식이 동적 할당이다.

동적할당 방식

Working set model 방식은 시간에 따라 주로 참조하는 페이지를 계산하여 이 값을 통해 프레임을 할당하는 것이다.

◻ CPU가 주소를 낼 때 시간을 측정하여 어떤 번지의 주소를 참조하는지를 측정한다.
조사한 주소를 Locality라고 한다. 각각의 시간에 Locality를 포함할 수 있는 프레임을 할당해주면 적절하게 메모리와 CPU를 사용할 수 있을 것이다.
그러나 이런 것은 동작을 한 후에 할 수 있는 것이지 미래를 알 수는 없다.

◻ 따라서 미래를 예측하는 방식을 사용하는데 그것이 Working set이다.
Working set은 과거에 어떤 페이지가 사용되어 왔는지를 가지고 있는 데이터이다.
최근 얼마까지의 시간을 기준으로 할 것인가에 대한 값이 Working set window이다.

Page-Fault Frequency(PFF)는 말 그대로 Page fault인 페이지 결함의 발생 비율을 측정하여 프레임을 할당하는 방식이다.