혼자 공부하는 컴퓨터구조 + 운영체제: 5. 가상 메모리

 

14. 가상 메모리

 

 

메모리 연속 할당

 

스와핑(swapping)

실행이 완료되었거나, 사용한지 너무 오래되어 현재 실행 중이지 않은 프로세스들은 메모리에서 보조기억장치로 옮겨 적재한다. 이것을 스와핑이라고 한다.

 

 

• 스왑 아웃: 메모리에서 보조기억장치로 나가는 것
• 스왑 인: 보조기억장치에서 메모리로 적재되는 것
• 스왑 영역: 보조기억장치 내 스와핑을 위한 일부 영역

 

메모리 할당

메모리 할당 방식에는 3가지가 있다.

 

 

• 최초 적합: 적재할 프로세스보다 큰 공간이 탐색되면 그 공간에 우선 배치하는 방식
• 최적 적합: 빈 공간을 모두 검색한 후, 적재할 프로세스보다 크되 가장 작은 공간에 배치하는 방식
• 최악 적합: 빈 공간을 모두 검색한 후, 가장 큰 공간에 적재할 프로세스를 배치하는 방식

 

 

외부 단편화

연속적으로 메모리를 할당하면 반드시 외부 단편화의 문제가 생긴다. 아래 그림에서 B는 50MB, D는 20MB를 차지하고, C는 30MB의 빈공간이라고 가정해보자. B가 스왑아웃 후, D가 스왑인 되면 초록색의 30MB 영역과 20MB인 C 영역이 남아서 메모리상 총 남은 공간의 합은 50MB이나, 실제 한 번에 사용할 수 있는 공간은 30MB가 된다. 이를 해결하기 위해 메모리 조각 모음이라고도 불리는 압축(compression) 방식을 적용할 수 있다. 그러나 프로세스들을 중단하고 메모리에 있는 내용을 옮겨야 하므로 오버헤드를 발생시킨다. 사실 압축에 대한 최적의 방법을 결정하기도 어렵다.

 

 

 

- 리눅스나 macOS에서 터미널상 free 또는 top 명령어를 치면 메모리의 상태, 스왑 영역의 크기 등을 볼 수 있다고 한다. 스왑 영역의 크기는 사용자가 직접 지정할수도 있다.

 

 

 

 

페이징

 

프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 자르고, 메모리의 논리 주소 공간을 페이지와 동일한 크기의 프레임이라는 단위로 자른 뒤 페이지를 프레임에 적재하는 방식이다. 이렇게 잘게 쪼개어 페이지 단위로 스왑인, 스왑 아웃을 해준다. 페이징 시스템에서는 이것을 각각 페이지인, 페이지 아웃이라고 부른다.

 

 

어떤 프로세스를 페이지 단위로 자른다는 것은 해당 프로세스를 실행하는데 모든 페이지가 필요하지는 않다는 것을 의미한다. 이렇게 하면 외부 단편화 문제를 해결할 수 있을 뿐만 아니라 수시로 페이지인, 아웃을 하면서 실제 물리 메모리 공간보다 더 큰 프로세스를 실행할 수도 있게 된다.

 

내부 단편화

메모리를 프레임 단위로 자르면, 내부 단편화가 발생할 수 있다. 256kb의 프로세스를 100kb의 프레임에 담는다면, 맨 마지막 프레임에는 56kb가 담긴다. 마지막 프레임에는 44kb의 공간이 비어있는 내부 단편화가 발생할 수 있다. 이를 막기 위해 프레임을 너무 잘게 쪼개면 페이지와 메모리의 주소 표시량이 늘어나기 때문에 좋지 않다. 따라서 내부 단편화를 막으면서도 적절한 주소 공간이 만들어지도록 페이지와 프레임의 크기를 적정 크기로 나눠줘야한다.

 

 

- 쓰기 시 복사(copy on write)

페이징을 하면 외부 단편화를 방지할 수 있을 뿐만 아니라 쓰기 시 복사가 가능해진다. 원래대로라면 부모 프로세스를 fork하면서 자식 프로세스를 만드는 경우, 프로세스간 자원 공유를 막기 위해서 메모리 공간에 적재된 부모 프로세스의 데이터들을 모두 복사하여 자식 프로세스에 할당해야한다. 그러나 페이징이 되어있는 경우, 일단 부모 프로세스의 메모리 공간인 프레임들을 자식 프로세스도 똑같이 가리키도록 하면 된다. 이렇게 하면 프로세스의 생성 시간이 줄어들고 불필요한 데이터가 메모리에 적재되지 않는다. 혹시라도 이 페이징된 데이터 중, 쓰기가 발생하면 그때서야 CPU는 해당 페이지를 복사하면 된다.

 

 

페이지 테이블

메모리에 페이지들이 비연속적으로 할당되었기 때문에 프로세스의 페이지가 순차적으로 실행될 수 없다는 문제가 생긴다. 이를 해결하기 위한 방법이 페이지 테이블을 사용하는 것이다.

 

페이지 테이블은 프로세스별 논리주소와 메모리의 물리주소간 매핑테이블이라고 생각하면 된다. 메모리에는 프로세스의 페이지들이 순차적으로 배치되어 있지 않더라도, CPU는 프로세스의 논리주소를 순차적으로 실행하면 된다.

 

 

각 프로세스마다 페이지 테이블을 갖고 있다. 그리고 이 페이지 테이블들은 메모리에 적재되어 있으며, CPU 내의 페이지 테이블 베이스 레지스터(PTBR, Page Table Base Register) 에 각 프로세스의 페이지 테이블이 적재된 메모리 주소가 저장된다. 즉 CPU는 PTBR을 참고하여 실행 중인 프로세스의 페이지 테이블 주소를 알아내고, 메모리에 적재된 프로세스의 데이터들을 순차적으로 읽어낸다.

 

 

TLB(Translation Lookaside Buffer)

CPU에서 메모리내의 페이지 테이블에 접근하고, 이를 기반으로 다시 메모리 내 실제 프로세스의 데이터가 있는 곳에 접근하면 두 번 접근이 이루어지기 때문에 속도가 느리다. 이를 해결하기 위해 CPU 코어의 MMU(Memory Management Unit)에 TLB라는 페이지 테이블의 캐시 데이터를 보관한다. 

 

참조 지역성에 근거하여 페이지 테이블을 보관하는데, 실제 CPU가 요청하는 논리 주소에 대해 프로세스 테이블이 TLB내에 있으면 TLB hit, 없으면 TLB miss 라고 한다. 

 

 

페이지 주소

 

페이지의 주소는 다음 2가지 정보로 이루어진다.

• 페이지 번호(page number): 접근하고자하는 페이지 또는 프레임의 번호
• 변위(offset): 메모리 주소가 페이지 또는 프레임의 시작 위치에서 떨어진 정도

32비트 짜리 주소고, 페이지 번호가 N 비트라면 변위는 32 - N 비트만큼을 차지하며 문자열로 구성된다.

 

이렇게 구성된 주소를 통해 아래 그림과 같은 방식으로 CPU가 메모리에 접근한다.

 

 

 

 

페이지 테이블 엔트리와 여러 비트들

페이지 테이블의 각 행을 페이지 테이블 엔트리라고 부른다. 엔트리를 구성하는 각 열은 앞서 살펴본 페이지 번호, 프레임 번호뿐 아니라 훨씬 더 많은 정보들이 포함되어있다. 그중 전공서에서 주로 살펴보는 여러 비트 정보들에 대해 정리하였다.

• 유효 비트(valid bit): 해당 페이지에 접근 가능한지 여부를 표시. 페이지 테이블에 표기되어 있더라도 스와핑 등에 의해 현재 페이지가 메모리에 있지 않고 보조기억장치에 있는 경우 유효비트를 0으로 표기한다.
• 보호 비트(protection bit): 해당 페이지가 읽기/쓰기 모두 가능하다면 1, 읽기만 가능하면 0으로 표기한다. 보호비트로 r, w, x 3개를 두어 각각 읽기, 쓰기, 실행 가능 여부를 표시하는 방식도 사용한다.
• 참조 비트(reference bit): CPU가 페이지에 접근한 적이 있는지를 나타낸다.
• 수정 비트(modified bit, dirty bit): 1이면 변경한 적이 있는 페이지, 0이면 변경한 적이 없는 페이지로 나타낸다. 만약 CPU가 해당 페이지의 내용을 수정한 경우, 수정 비트를 참조하여 해당 페이지를 보조 기억 장치로 스왑 아웃할 때 변경된 값을 보조 기억 장치에 업데이트하는 작업을 추가로 해준다.

 

- 페이지 폴트(page fault) 

유효비트가 0인 페이지에 CPU가 접근 시, 페이지 폴트를 일으키고 기존 작업 내역을 백업한다. 이후 원하는 페이지를 메모리에 적재, 유효비트를 1로 변경한 뒤 다시 작업을 실행한다.

 

- 계층적 페이징(hierarchical paging)

전체 페이지 테이블이 메모리에 올라가있는 것은 부담이므로, 페이지 테이블을 계층적으로 여러 개 두고 참조가 필요한 부분만 메모리에 두는 방식이 계층적 페이징이다. 기존 주소값을 '페이지 번호 + 변위'로 나타냈는데, 계층적 페이징에서는 페이지 번호 부분이 각 계층에서의 페이지 번호로 분할되어 표현된다. 페이지 폴트가 발생했을 경우 여러 번 참조가 필요할 수 있으므로 무조건 계층이 많을수록 좋은 것은 아니다.

 

 

페이지 교체와 프레임 할당

 

요구 페이징(demand paging)

프로세스를 실행하는데 필요한 모든 페이지를 처음부터 메모리에 전부 적재하는 것이 아니라, 해당 페이지가 필요한 순간에서야 해당 페이지를 적재하는 것을 요구 페이징이라고 한다. 웹 프레임워크들에서는 lazy loading 개념이라고 보면 된다.

 

요구 페이징은 CPU가 페이지를 요구하고, 없으면 페이지 폴트 발생 후 페이지를 메모리에 적재한 뒤 유효 비트값을 1로 변경하는 방식을 사용한다. 페이지 폴트가 발생하면 성능에 좋지 않으므로 무조건 메모리의 프레임에 프로세스의 모든 페이지들을 싣는 것이 유리하겠지만, 메모리 용량의 한계로 요구 페이징 방식을 적용하는 것은 필연적이다.

 

페이지 교체 알고리즘

메모리에 페이지를 실을 공간이 더 이상 없으면 페이지 교체(스왑 아웃/인)가 필요할 것이다. 이때 최적의 알고리즘을 적용하기 위해 알아야할 페이지 참조열(page reference string)이라는 개념이 있다.

 

1 1 2 2 3 3 4 4 4 5 1

순으로 페이지 참조가 일어난다면, 연속된 페이지 참조에서는 페이지 폴트가 발생하지 않으므로 연속된 참조 부분은 제외하여 페이지 참조열을 표현한다.

1 2 3 4 5 1

 

이때 적용되는 여러 알고리즘의 일부를 요약하면 다음과 같다.

• FIFO(First In First Out) 페이지 교체 알고리즘: 먼저 들어온 페이지부터 나가게 하는 것. 즉 가장 오래된 페이지를 내보내는 방식인데, 해당 페이지가 많이 참조되고 있을 수도 있으므로 무조건 가장 들어온지 오래된 페이지를 나가게하는 것은 좋지 않다.
• 2차 기회(Second Chance) 페이지 교체 알고리즘: FIFO를 기본으로 하되, 해당 페이지의 참조 비트가 1이라면 참조가 최근에 됐었던 페이지라는 의미이므로, 해당 페이지를 페이지아웃 하지 않고 최후순위로 적재 위치를 변경한다. 그러면서 참조 비트를 0으로 만들어 기회를 한 번 더 준다.
• 최적(Optimal) 페이지 교체 알고리즘: 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘이다. 아래 그림에서 페이지 참조열 전체를 참조했을 때, 교체가 필요한 순간 이후 가장 오랫동안 사용하지 않을 페이지를 일단 보조기억장치로 내보내는 방식이다. 이렇게 하면 페이지 폴트가 가장 적게 발생한다. 그러나 앞으로의 사용 빈도를 판단하는 것은 매우 어려운 일이다. 사실상 해당 알고리즘은 한정된 페이지, 프레임 개수 내에서 이론적으로 최소한의 페이지 폴트가 발생하는 경우의 수로 상정하고 다른 알고리즘들의 상대적인 성능을 평가하는데 이용된다.
• LRU(Least Recently Used) 페이지 교체 알고리즘: 각 시점에서 과거 페이지 조회 이력을 기준으로 가장 오랫동안 사용하지 않은 페이지를 교체하는 알고리즘이다.

 

 

 

스래싱(thrashing)

CPU 이용률과 멀티프로그래밍의 정도(degree of multiprogramming, 동시에 실행되는 프로세스의 수)의 관계를 그래프로 그려보면 대략적으로 아래와 같다.

 

 

여기서 프레임 개수에 비해 프로세스의 수가 많아지면 그만큼 많은 페이지 폴트가 발생한다. 특정 한계치를 넘어서면 CPU가 프로세스를 처리하는 시간 대비 페이지 폴트로 인한 CPU 부하가 커져서 성능이 급격히 떨어지는 순간이 오는데, 그것을 스래싱이라고 한다. 메모리 대비 CPU의 성능만 좋은 경우 여러 프로세스를 실행하다가 스래싱이 발생할 수 있다.

 

 

프레임 할당

페이지 폴트를 막기 위해 페이지 교체 알고리즘도 중요하지만, 어떤 프로세스에 얼마의 프레임을 할당할 것인가도 중요하다. 10개의 프레임이 필요한 프로세스에 10개 프레임을 할당하면 전혀 문제가 없지만, 자원의 한계로 5개만 할당한 경우 어떤 순간 필요한 프레임(페이지)가 6개가 되어버리면 페이지 폴트가 발생할 수 있기 때문이다. 따라서 프레임 할당 방식이 중요하다.

 

• 균등 할당(equal allocation): 모든 프로세스에 (가용 프레임 수) / (요청 프로세스 수) 만큼 균등하게 프레임을 할당한다.
• 비례 할당(proportional allocation): 프로세스의 크기에 비례하여 프레임을 할당한다. 그러나 큰 프로세스라도 실제 실행 시 많은 프레임을 필요로 하지 않을 수 있기 때문에 최적의 방식이 아니다.
• 동적 할당 방식- 작업 집합 모델: 특정 시간동안 어떤 프로세스가 참조한 페이지 수(작업 집합(working set))를 기반으로 각 프로세스에 할당할 프레임 수를 결정한다.
• 동적 할당 방식- 페이지 폴트 기반: 어떤 프로세스에 일어나는 페이지 폴트 수가 많으면 많은 프레임을 할당한다.