운영체제 (8) - Virtual Memory

2024년 1학기 운영체제 수업을 듣고 정리한 내용입니다. 수업 교재는 운영체제 - 내부구조 및 설계원리 8 판입니다.

Virtual memory

가상 메모리는 RAM과 하드디스크를 모두 메모리로 사용하는 것이다. 메인 메모리는 RAM으로, 서브 메모리는 하드디스크로 사용한다.

Execution of a program in virtual memory

가상 메모리에서는 모든 페이지/세그먼트들을 메모리에 올리지 않고 일부 페이지/세그먼트만 메모리에 올린다. 메모리에 올라간 페이지/세그먼트들을 Resident set이라고 부른다.

메모리에 올라간 페이지/세그먼트들 속 프로세스가 프로그램을 실행할 때, 특정 페이지/세그먼트를 찾는 경우가 있다. 하지만 메인 메모리에 페이지가 없고 서브 메모리에 존재하는 경우에는 Page Fault가 발생한다. 이 때 Interrupt가 발생하고 그 프로세스는 Blocked된다. Page Fault Interrupt가 발생하면 하드디스크에서 페이지를 메모리로 불러오는 작업을 하게 되고 작업이 완료되면 다시 프로세스는 Ready 상태가 된다.

Thrashing / Locality

페이지를 읽어올 때에는 기존에 메모리에 올라가있는 페이지를 버리고 새로운 페이지를 읽어온다. 그러나 프로그램이 실행되는 시간보다 페이지를 읽어오는 시간이 더 많은 경우 Thrashing이 발생한다고 한다. 하지만 프로그램이 실행될 때 지역성의 원리에 의해 실행중인 위치의 주변을 참조하는 경우가 많으므로 Thrashing은 잘 발생하지 않는다고 한다.

Paging

가상 메모리 시스템에서 페이징 시스템 또한 페이지 테이블을 갖는다. 페이지 테이블에는 다음과 같은 데이터가 저장된다.

• 페이지가 위치한 프레임 번호
• 페이지가 메모리에 있는지의 여부 비트 (Present)
• 메인 메모리로 올라온 후에 수정되었는지 여부 비트 (Modified)
• 그 외 컨트롤 비트들

프로세스의 PCB나 스택이 변경되었을 경우 값을 살려야 하므로 Modified비트가 필요하다.

페이징 시스템에서는 가상 주소를 사용하는데, 가상 주소에는 페이지 테이블에서의 인덱스와 오프셋으로 이루어져 있다.

Address Transition

가상주소에 있는 인덱스를 페이지 테이블 베이스 포인터(PTBR)에 더해 엔트리를 찾고, 엔트리 속 프레임 번호와 오프셋을 더해 실제 페이지가 담겨있는 프레임에 접근한다. PTBR은 PCB에 저장되어 있고, 프로세스가 실행될 때 CPU에 올라오게 된다.

Hierarchical Page Table

페이지 테이블이 매우 커져서 한 프레임 크기보다 크다면, 불가피하게 여러 프레임에 걸칠 수밖에 없다. 그럴 경우에는 가상 주소속 페이지 테이블 인덱스로 접근할 수 없기 때문에 여러 페이지 테이블에 접근할 수 있는 루트 페이지 테이블이 필요하다.

만약 메모리의 크기가 4GB이고, 한 프레임의 크기가 4KB인 시스템에서 페이지 테이블을 만들다보니 4MB의 크기가 되어버렸다고 하자. 페이지 테이블이 프레임 크기를 벗어나버렸으므로, 가상 주소속 페이지 인덱스 값으로 페이지 테이블의 모든 엔트리에 접근할 수 없다.

계산 방법

계층 페이지 테이블을 계산하기 위해 기본적으로 주어지는 값은 이렇다.

• 프로그램의 최대 크기
• 페이지의 크기
• 페이지 테이블의 한 엔트리의 크기

먼저 메모리에 올라갈 데이터를 페이지의 크기로 나눈다. 프로그램 크기가 4GB이므로 4GB/4KB로 나눈다.

$$
2^{32} / 2^{12}=2^{20}
$$

얻은 결과값은 프로그램 속 페이지의 최대 개수이다. 이 값에 엔트리 크기를 곱하면 페이지 테이블의 크기가 된다. 엔트리의 크기가 4바이트라고 하면,

$$
2^{20} * 2^2 = 2^{22}
$$

$2^{22}$가 페이지 테이블의 크기가 된다. 이제 생각해봐야 할 것은 이 값이 페이지의 크기보다 큰가 살펴보는 것이다. 당연히 $2^{12}$보다 크므로 앞서 했던 작업을 반복한다.

메모리에 올라갈 데이터(앞서 구한 페이지 테이블의 크기인 $2^{22}$)를 페이지의 크기로 나눈다.

$$
2^{22}/2^{12}=2^{10}
$$

그리고 이 값에 엔트리 크기를 곱한다.

$$
2^{10}*2^2 = 2^{12}
$$

이 결과가 페이지 크기와 같거나 작으므로 루트 페이지 테이블을 얻게 되었다.

앞서 계산했듯이 루트 페이지 테이블의 크기는 $2^{12}$이므로 루트 페이지 테이블의 엔트리 수는 $2^{10}$이다(10비트). 그리고 페이지의 크기가 $2^{12}$였으므로 이를 엔트리 크기로 나눈 $2^{10}$이 루트 페이지로 접근한 하위 페이지 테이블의 인덱스 비트(10비트)가 된다. 페이지의 크기가 $2^{12}$이므로 오프셋은 12비트가 된다.

따라서 가상 주소는 10비트(루트 페이지 테이블 인덱스 비트) + 10비트(하위 페이지 테이블 인덱스 비트) + 12비트(오프셋 비트)로 구성된다. 앞서 PTBR값을 통해 페이지 테이블 엔트리에 접근했다면 이제는 PTBR값이 루트 페이지 테이블의 시작 주소가 된다.

가상 주소는 루트 페이지 테이블값에 루트 페이지 테이블 인덱스 비트를 더해 하위 페이지 테이블의 시작 주소를 찾고, 그 주소 값에 하위 페이지 테이블 인덱스 비트를 통해 프레임 번호를 찾게 된다. 그 값에 오프셋을 더해 실제 프레임 속 명령어의 위치를 찾게 된다.

Inverted Page Table

페이지 테이블이 굉장히 커서 위와 같이 복잡한 과정이 생기므로 모든 페이지를 기억하는 페이지 테이블을 만들지 말고, 그냥 메모리에 올라온 프레임을 기억하는 페이지 테이블 하나만 만들어 낭비를 줄이는 Inverted Page Table이 등장했다. 엔트리에 저장되는 정보는 다음과 같다.

• 페이지 번호
• 프로세스 식별자
• 컨트롤 비트
• 체인 포인터(같은 해시 결과를 갖는 엔트리끼리 번호로 연결한 것)

페이지 번호가 곧바로 엔트리와 매핑되기 때문에 적절한 변환함수가 필요하다. 즉, Inverted Page Table은 해시 테이블이다. 해시 테이블에서 해시 함수의 결과가 같은 경우 해시 충돌이므로 같은 해시값을 같는 엔트리는 체인 포인터를 사용해서 충돌을 피한다.

가상 주소속 페이지 번호를 해시화하여 Inverted Page Table에 접근한다. 해시 충돌이 없다면 Chain에 NULL이 저장되어 있으므로 곧바로 프레임 번호와 오프셋을 조합하여 메모리에 접근하게 된다. 해시 충돌이 일어났다면 Chain에 다음 엔트리 번호가 저장되어 있을것이고 Chain이 NULL이 될 때까지 엔트리를 이동하여 프레임 번호를 알아내게 된다.

Translation Lookaside Buffer(TLB)

페이지 테이블을 사용하여 메모리에 접근하는 것은 결국 테이블에 접근하는 것과, 테이블을 통해 알아낸 메모리의 주소로 접근하는 것, 액세스가 총 두 번 일어나게 된다. 메모리에 액세스 하는 것은 오래 걸리는 작업이므로, 실제 메모리에 접근하는 것은 어쩔 수 없지만 테이블에 접근하는 것은 캐시를 사용할 수 있다. 최근에 접근한 페이지 테이블 엔트리를 기억하는 캐시가 Translation Lookaside Buffer(TLB)다.

가상 주소를 사용할 때 페이지 테이블에 곧바로 접근하지 않고 먼저 TLB에 접근다. 최근에 접근한 페이지 테이블 엔트리가 TLB에 있다면 hit하게 되므로 바로 프레임번호를 얻게 되어 메모리에 접근하게 된다. miss하였다면 어쩔 수 없이 페이지 테이블에 접근하게 된다. 여기서 원하는 페이지를 못찾게 되었다면 Page Fault가 일어나고 하드디스크에 접근해 페이지를 읽어오게 된다.

Segmentation

세그먼트 시스템에서도 세그먼트 테이블이 존재한다. 세그먼트 테이블 엔트리에는 다음과 같은 값이 저장된다.

• 세그먼트가 메인 메모리에 존재하는지 여부 비트(Present)
• 메인 메모리로 올라오고나서 값이 바뀌었는지 여부 비트(Modified)
• 세그먼트의 길이(Length)
• 세그먼트의 시작 주소(Base)
• 그 외 컨트롤 비트

가상 주소에는 세그먼트 테이블 엔트리와 오프셋값이 들어있다.

세그먼트 역시 세그먼트 테이블 포인터(STBR)가 존재한다. STBR과 가상 주소속 세그먼트 테이블 인덱스값을 더해 엔트리를 얻고, 엔트리 속 Base값과 오프셋 값을 더해 메모리에 접근하게 된다. 이 때 Length값과 Offset값을 비교하여 잘못된 메모리 접근을 막는 Protection도 일어난다.

Combined Paging and Segmentation

세그먼트는 정해진 크기가 아니기 때문에 external fragmentation이 일어날 수 있으므로 비효율적이다. 따라서 페이지 시스템과 혼합하여 사용한다. 먼저 의미있는 단위로(세그먼트로) 나누되 세그먼트를 페이지 단위로 나눈다.

이렇게 세그먼트를 페이지로 나누게 되면 한 페이지에 프로그램 코드만 있거나 데이터만 있으므로 공유 및 Protection이 쉬워진다.

혼합된 방식을 사용하기 때문에 세그먼트 테이블과 페이지 테이블이 공존한다. 가상 주소의 구조가 바뀌었는데, 세그먼트 테이블 인덱스와 페이지 테이블 인덱스 그리고 오프셋이 들어가는 구조로 변경되었다.

세그먼트 테이블 엔트리는 컨트롤 비트, Length 그리고 Base값이 있고 Present와 Modified는 사라졌다. 실제로 메모리에 올라오는 것은 페이지이므로, 필요하지 않기 때문이다.

먼저 세그먼트 테이블 인덱스와 STBR을 합쳐 엔트리를 찾는데 엔트리에는 페이지 테이블의 시작 주소(Base)가 담겨있다. 그리고 Length값을 얻게 되는데 페이지 테이블의 길이를 의미한다. 페이지 테이블의 시작 주소와 가상 주소의 페이지 테이블 인덱스를 조합하여 프레임 번호를 얻고, 오프셋을 조합하여 메모리에 접근하게 된다.

Fetch Policy

페이지를 메모리로 불러올 때 인접한 페이지를 한 번에 불러올지, 아니면 필요한 페이지만 불러올지 결정하는 정책이다. 필요한 페이지만 불러오는 방식을 Demand Paging, 인접한 페이지를 불러오는 것이 Pre-paging인데, 지역성의 원리에 의해 최근에 참조한 페이지를 다시 참조할 가능성이 높아 Demand paging 방식을 사용하는 것이 효율적이라는 결론이 내려졌다.

Replacement Policy

하지만 페이지를 읽어오기 위해서는 기존에 메모리에 있던 페이지를 버려야 한다. 버릴 페이지가 나중에 참조될지 안될지 모르기 때문에 어떻게 버리느냐에 따라 Page Fault를 줄일 수 있으므로 성능에 중요한 영향을 끼치게 된다.

Optimal

여러 방법을 비교하기 위해 최적의 방법을 알고 있다고 가정한 후 다른 방법과 수치적으로 비교해본다. 최적의 방법은 앞으로 오랫동안 사용하지 않을 페이지를 알고 있는 채로 페이지 교체를 진행하는 방법이다.

142351342543341순으로 페이지를 읽는다고 하자.

최초의 1,4,2에서는 Page Fault가 발생하지만, 비교를 할 때 세어볼 필요는 없으므로 건너뛴다. 다음으로 3을 불러오는데, 1,4,2중 앞으로 제일 늦게 읽어올 페이지는 2이므로(순서를 알고 있으므로 351342이니까 2가 제일 늦게 읽힌다) 2를 버리고 3을 불러온다. 다음으로 4를 읽는데, 1,4,3중 제일 늦게 읽어올 페이지는 4이므로(5134니까) 4를 버리고 5를 불러온다. 이렇게 계속 제일 늦게 불러올 페이지를 확인하고 그 페이지와 읽어올 페이지를 교환하면 위 사진처럼 결과가 나타난다. 총 Page Fault는 6번 발생한 모습이다.

Least Recently Used(LRU)

당연하게 미래에 어떤 페이지를 쓰게될 지 모르기 때문에 과거에 어떻게 썼었는지 확인하는 방법이다. 현재 메모리에 올라와 있는 페이지중 가장 늦게 읽었던 페이지를 버린다. 지역성에 의해서 최근에 읽었던 페이지는 계속 읽힐 것이라고 믿는 것이다. 그러려면 언제 읽었는지를 기억할 시간값을 추가로 저장해야하므로 오버헤드가 생기지만 optimal한 방법과 비슷한 성능을 낸다.

1,4,2를 읽어온 후 3을 읽는데, 메모리에 올라와 있는 페이지중에 제일 늦게 읽은 페이지는 1이다. 1을 버리고 3을 불러온다. 다음으로 5를 불러와야 하는데 3,4,2중에 제일 늦게 읽은 페이지는 4다. 4를 버리고 5를 불러온다. 이런 방식으로 진행하면 총 Page Fault는 8번이다.

First-in First-out(FIFO)

LRU는 시간값을 저장한 뒤 전체 탐색을 해야하므로 오버헤드가 크다. 따라서 간단한 규칙인 FIFO를 사용해서 먼저 읽은 페이지를 먼저 버리는 방법이다.

1,4,2를 읽고 3을 불러올 때 제일 먼저들어온 페이지는 1이다. 1을 버리고 3을 불러온다. 다음으로 5를 불러올 때 3,4,2중 제일 먼저 들어온 페이지는 4다. 4를 버리고 5를 불러온다.

예제에서는 중간 즈음에 5134순으로 읽는 부분이 LRU와 다르게 진행된다. 4를 읽어야 하는데, 3,5,1중에 제일 먼저 들어온 페이지는 3이다. 따라서 3을 버리고 4를 읽는다. 이런 식으로 진행하면 총 Page Fault는 9번이다.

성능은 LRU보다 좋지 않지만 규칙이 간단하므로 오버헤드가 거의 없다.

특별한 점은 페이지 프레임 수가 많아질수록 Page Fault가 많이 발생하는 이상한 현상이 발생한다는 것이다.

Clock

메모리에 올라오고 나서 사용되었는지 기억할 1비트를 추가한다. used비트라고 부르며 이 비트값이 0인 페이지를 교체하는 기법이다. 굉장히 오버헤드가 작지만 성능은 준수하다.

숫자 옆에 별표 표시는 페이지가 메모리로 올라오고 나서 읽었음을 나타내는 used비트를 뜻한다. Clock기법은 커서가 존재하여 페이지를 메모리로 불러와야 할 때 used가 0인 페이지를 찾는 역할을 한다. 그리고 페이지를 불러올 때 커서 위치에 불러오도록 한다.

먼저 1을 메모리로 불러오고 나서는 커서가 다음칸으로 이동한다. 메모리로 불러온 페이지는 used값이 0이지만, 불러온 페이지를 곧바로 사용하기 때문에 used값이 항상 1로 초기화 된다. 똑같이 4를 불러오고 나서 다음칸으로 커서가 이동한다. 2를 불러오고 나서 다시 커서가 1번으로 이동한다. 다음으로 3을 불러와야 하는데, 이 때 used비트가 0인 페이지를 찾는다. 1은 used값이 1이기 때문에 건너뛰는데, 이 때 used를 0으로 만들어 두고 이동한다. 똑같이 2와 4를 모두 탐색했지만 비트값이 1이어서 값을 0으로 바꾸고 건너뛴다. 다시 1부터 탐색하는데 아까 used값을 0으로 만들어 두었기 때문에 1을 버리고 3을 불러온다. 그 결과로 [3*, 4, 2]가 되었다.

다음으로 5를 불러와야하는데 커서가 4에 있다. 4는 used값이 0이기 때문에 4를 버리고 5를 불러온다. 그런 다음 커서가 다음 칸으로 이동한다. 결과는 [3*, 5*, 2]가 된다.

1을 불러오고 나서 다시 3을 불러온다. 1을 불러온 뒤에는 메모리 상태가 [3*, 5*, 1*]인데, 메모리에 3이 있다. 이 상태에서는 이미 메모리에 원하는 페이지가 있기 때문에 커서는 움직이지 않고 used를 1로 바꾸게 된다.

총 Page Fault는 9번 발생했지만 오버헤드가 굉장히 적기 때문에 속도가 빠르다.

통계적으로는 LRU가 가장 성능이 좋고 FIFO가 가장 나쁘다고 한다. Clock기법은 프레임 수가 많아질 경우 LRU와 비슷한 성능을 내게 되는 모습이다.

Resident Set Size

Resident set은 프로세스를 실행할 때 메모리에 있는 페이지의 집합을 말한다. 각 프로세스마다 페이지 수를 바꾸는 방법은 여러 가지가 있다.

Fixed Allocation-Local Scope

Fixed~는 프로세스에게 고정된 페이지 수를 할당하는 방법이다. Local scope는 페이지를 불러와야 할 때 자신의 것을 버리고 불러오는 방법이다. 만약 페이지 수가 적게 할당되었다면 많은 Page Fault가 일어나게 된다. 반대로 페이지 수가 크게 할당되었다면 실행시키는 프로그램의 수가 적어지게 된다.

Variable Allocation-Global Scope

Variable~은 프로세스에게 유동적인 페이지 수를 할당하는 방법이다. 실행중에 페이지 수가 계속 변하기 때문에 이 방법이 적절하다.

Global scope는 프로세스가 페이지를 필요로 할 때 자신의 Resident set을 늘려 페이지를 불러온다. 만약 공간이 부족하다면 다른 프로세스의 페이지를 버리고 그 자리에 자신의 페이지를 올리는 방법이다. 버릴 페이지를 탐색하기 위해 모든 프로세스를 탐색해야하므로 LRU를 사용할 수 없고 Clock기법을 사용한다.

Variable Allocation-Local Scope

프로그램 타입이나 다른 기준에 따라서 Resident set의 크기가 정해진다. Page Fault가 발생하면 Local scope이므로 자신의 것을 버리게 된다. 그러나 Page Fault가 점점 많이 발생한다면 자신의 Resident set을 늘린다. 그러다가 점점 Page Fault 발생 빈도가 낮아진다면 Resident set의 크기를 줄이게 된다. 자신의 것만 탐색하기 때문에 LRU를 적용할 수 있다.

UNIX

UNIX는 두 가지의 메모리 관리 방법을 사용한다. 유저 프로세스에게는 페이징 시스템 기반의 가상 메모리를, 커널에게는 변형된 Buddy 시스템을 사용한다.

UNIX에서 페이지를 교체할 때에는 Clock기법을 사용하는데 커서가 두 개인 알고리즘을 사용한다. 한 커서는 used비트를 1에서 0으로 바꾸는 역할을 하고, 다른 커서는 used비트가 0인 페이지를 탐색하는 역할을 갖는다. 이렇게 하는 이유는 교체 시기 전까지 미리 탐색을 해두므로 교체해야할 때 빠르게 교체할 수 있다. 대신 탐색용 커서가 비트를 바꾸는 커서를 앞지르지 않도록 속도 조절을 적절히 해야한다.

Windows

윈도우 역시 페이징 시스템 기반의 가상 메모리를 사용한다. 윈도우는 Variable allocation-Local scope를 사용한다. 메모리가 여유롭다면 페이지 프레임 수를 늘리고, 메모리가 부족하다면 페이지 프레임 수를 줄여서 공간을 만든다. 이 때 버릴 페이지는 LRU를 사용한다.