14. 가상 메모리
지금까지는 메모리 내에 프로세스들이 연속적으로 배치되는 상황을 가정했다. 즉, 아래 그림과 같이 프로세스 A 는 A 의 크기만큼 메모리 주소를 할당받아 연속적으로 배치되고, 프로세스 B 는 프로세스 A 이후에 또 B 의 크기만큼 연속적인 메모리 주소를 할당받아 배치되는 식으로 말이다.
이렇게 프로세스에 연속적인 메모리 공간을 할당하는 방식은 "연속 메모리 할당" 방식이라고 한다. 이번 절에서는 이와 같이 프로세스들을 메모리에 연속적으로 할당할 때 무엇을 고려해야 하는지, 그리고 어떤 잠재적인 문제가 있는지 확인해보자.
1. 연속 메모리 할당
1.1 스와핑
메모리에 적재된 프로세스들 중에는 현재 실행되지 않을 프로세스가 있을 수 있다. 입출력 작업의 요구로 대기 상태가 된 프로세스라던지, 오랫동안 사용되지 않은 프로세스가 이런 프로세스에 속한다.
이러한 프로세스들을 임시로 보조기억장치 일부 영역으로 쫒아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식을 "스와핑(swapping)" 이라고 한다.
이때 프로세스들이 쫓겨나는 보조기억장치의 일부 영역을 "스왑 영역(swap space)" 이라고 한다. 그리고 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것을 "스왑 아웃(swap out)", 반대로 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것을 "스왑 인(swap in)" 이라고 한다. 스왑 아웃 되었던 프로세스가 다시 스왑 인될 때는 스왑 아웃되기 전의 물리주소와는 다른 주소에 적재될 수 있다.
스와핑을 사용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있다.
크기를 넘어가는 프로세스는 보조기억장치에 잠시 스왑 아웃해두면 된다.
1.2 메모리 할당
프로세스는 메모리 내의 빈 공간에 적재되어야 한다. 메모리 내에 빈 공간이 여러 개 있다면 프로세스를 어디에 배치해야 할까? 비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식은 대표적으로 최초 적합, 최적 적합, 최악 적합의 세가지 방식이 있다.
최초 적합
"최초 적합(first fit)" 은 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식이다.
검색을 최소화할 수 있고 결과적으로 빠른 할당이 가능하다.
최적 적합
"최적 적합(bset fit)" 은 운영체제가 빈 공간을 모두 검색해본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식이다.
최악 적합
"최악 적합(worst fit)"은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식이다.
1.3 외부 단편화
프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 언뜻 들으면 당연하게 느껴질 수 있지만, 사실 이는 메모리를 효율적으로 사용하는 방식이 아니다. 왜냐하면 연속 메모리 할당은 "외부 단편화(external fragmentation)" 라는 문제를 내포하고 있기 때문이다.
아무런 프로세스도 적재되지 않은 상태의 메모리 전체를 생각해보면 커널 영역에 운영체제 프로세스가 적재되어 있고 유저 영역에는 어떠한 프로세스도 적재되어 있지 않다.
이제 유저 영역에 하나둘씩 프로세스(A,B,C,D 프로세스)들이 적재되었고, 중간 프로세스(B,D 프로세스)가 작업을 마무리해 메모리 중간에 빈 공간이 생겼다고 생각해보자.
그 이후에 정리된 프로세스들의 크기만한 프로세스를 할당하려고 하면 할 수 있을까? 정답은 못한다! (파편화가 되어있어 메모리가 연속적이지 않기 때문이다!)
이러한 메모리 내 연속적이지 않은 빈공간이 생기는 현상을 외부 단편화라고 한다. (실제로는 메모리 단편화는 성능에 큰 문제가 될 수 있기 때문에 해당 문제는 꼭 해결해야만 한다!)
외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리 "압축(compaction)" 하는 방법이 있다. 메모리 조각 모음이라고 부른다.
다만 압축 방식은 여러 단점이 있다. 작은 빈 공간들을 하나로 모으는 동안 시스템은 하던 일을 중지해야 하고(Java 의 STW ), 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며, 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하면서 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵다.
이에 외부 단편화를 없앨 수 있는 또 다른 해결 방안이 등장했는데, 이것이 오늘까지도 사용되는 가상 메모리 기법, 그 중에서도 페이징 기법이다.
2. 페이징을 통한 가상 메모리 관리
프로세스 메모리에 연속적으로 할당하는 방식은 두 가지 문제를 내포하고 있다.
한 가지는 앞선 절에서 다루었던 외부 단편화이고,
또 하나는 물리 메모리보다 큰 프로세스를 실행할 수 없다는 점이다.
"가상 메모리(virtual memory)" 는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술이다.
이를 가능케 하는 가상 메모리 관리 기법에는 크게 "페이징" 과 "세그멘테이션"이 있지만, 이 책에서는 현대 대부분의 운영체제가 사용하는 페이징 기법을 다룬다.
2.1 페이징이란
연속 메모리 할당 방식에서 외부 단편화가 생긴 근본적인 이유는 각기 다른 크기의 프로세스가 연속적으로 할당되었기 때문이다.
만일 메모리와 프로세스를 일정한 단위로 자르고, 이를 메모리에 불연속적으로 할당할 수 있다면 외부 단편화는 발생하지 않는다.이것이 "페이징(paging)" 이다.
페이징은 프로세스의 논리 주소를 "페이지" 라는 일정한 단위로 자르고,
물리 주소 공간을 "프레임" 이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤
페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.
페이징에서의 스와핑
프로세스 단위의 스왑 인, 스왑 아웃이 아닌 페이지 단위의 스왑 인(페이지 인), 스왑 아웃(페이지 아웃)
메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 스왑 아웃
실행에 필요한 페이지들은 메모리로 스왑 인
이는 다르게 말하면 한 프로세스를 실행하기 위해서 프로세스 전체가 메모리에 적재될 필요가 없다는 말과 같다. 달리 말해서 통해서 메모리보다 더 큰 프로세스를 실행할 수 있다.
2.2 페이지 테이블
그런데 여기서 문제가 발생한다.
프로세스가 불연속적으로 배치되어 있다면 CPU 입장에서는 이를 순차적으로 실행할 수 없다. 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU 가 모두 알고 있기란 어렵기 때문이다.
즉, 프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 '다음에 실행할 명령어 위치' 를 찾기 어려워진다.
이를 해결하기 위해서 페이지 시스템은 프로세스가 비록 물리 주소(실제 메모리 내의 주소인)에 불연속적으로 배치되더라도 논리 주소(CPU가 바라보는 주소인) 에는 연속적으로 배치되도록 "페이지 테이블(page table)" 을 이용한다.
페이지 테이블을 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표이다. CPU 로 하여금 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있도록 한다.
위와 같은 방식으로 비록 물리 주소상에서는 프로세스들이 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보일 수 있다.
프로세스마다 각자의 페이지 테이블을 가지고 있고, 각 프로세스의 페이지 테이블들은 메모리에 적재되어 있다.
물리적으로는 분산되어 저장되어 있더라도, CPU 입장에서는 바라본 논리 주소는 연속적으로 본인다.
CPU 는 그저 논리 주소를 순차적으로 실행하면 될 뿐이다.
그리고 CPU 내의 "페이지 테이블 베이스 레지스터(PTBR : page table base register)" 는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다.
그런데 이렇게 페이지 테이블을 메모리에 두면 문제가 있다. 메모리 접근 시간이 두배로 늘어나기 때문이다!
이와 같은 문제를 해결하기 위해 CPU 곁에 "TLB(translation lookaside buffer)" 라는 페이지 테이블의 캐시 메모리를 둔다. TLB 는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장한다.
CPU 가 발생한 논리 주소에 대한 페이지 번호가 TLB 에 있을 경우 이를 "TLB히트" 라고 한다. 이 경우에는 페이지가 적재된 프레임을 알기 위해 메모리에 접근할 필요는 없고, TLB 캐시에 접근하기 때문에, 결론적으로 메모리 접근은 1번만 이루어진다!
하지만 만일 페이지 번호가 TLB 에 없다면 어쩔 수 없이 메모리 내의 테이블에 접근할 수 밖에 없다. 이를 "TLB 미스" 라고 한다. 이 경우 결론적으로 메모리 접근은 2번 이루어진다..
2.3 페이징에서의 주소 변환
하나의 페이지 또는 프레임은 여러 주소를 포괄하고 있다. 그렇기에 특정 주소에 접근하려면 아래와 같은 두 가지 정보가 필요하다.
어떤 페이지 혹은 프레임에 접근하고 싶은지
접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지?
그렇기에 페이징 시스템에서는 모든 논리 주소가 기본적으로 "페이지 번호(page number)" 와 "변위(offset)" 으로 이루어져 있다.
가령 CPU 가 32비트 주소를 내보냈다면 이 중 N 비트는 페이지 번호, 32-N 비트는 변위, 이런식으로 이루어진다.
페이지 번호는 말 그대로 접근하고자 하는 페이지 번호이다. 페이지 테이블에서 해당 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되었는지 알 수 있다. 변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어졌 있는지를 알기 위한 정보이다.
즉, 논리 주소(페이지 번호, 변위) 는 페이지 테이블을 통해 물리 주소(프레임 번호, 변위) 로 변환된다.
2.4 페이지 테이블 엔트리
페이지 테이블을 조금 자세히 들여다보자. 페이지 테이블의 각 엔트리, 다시 말해 페이지 테이블의 각각의 행들을 "페이지 테이블 엔트리(PTE : page table entry)" 라고 한다.
지금까지는 페이지 테이블 엔트리에 담기는 정보로 페이지 번호, 프레임 번호만을 설명했지만, 실은 페이지 테이블 엔트리에는 이외에도 중요한 정보(유효 비트, 보호 비트, 참조 비트, 수정 비트)가 있다.
각각의 설명은 패스..
3. 페이지 교체와 프레임 할당
가상 메모리를 통해 작은 물리 메모리보다 큰 프로세스도 실행할 수 있다고는 하지만, 그럼에도 불구하고 여전히 물리 메모리의 크기는 한정되어 있다.
운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용할 수 있도록
기존에 메모리에 적재된 불필요한 페이지를 선별하여 보조기억장치고 내보낼 수 있어야 하고,
프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있도록 해야한다.
3.1 요구 페이징
프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만 메모리에 적재하는 방법은 "요구 페이징(demand paging)" 이라고 한다.
요구 페이징의 기본적인 양상은 다음과 같다.
CPU 가 특정 페이지에 접근하는 명령어를 실행한다.
해당 페이지가 현재 메모리에 있을 경우 CPU 페이지가 적재된 프레임에 접근한다.
해당 페이지가 현재 메모리에 없을 경우 페이지 폴트가 발생한다.
페이지 폴트 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
이 과정을 반복한다.
위와 같은 요구 페이징 시스템이 안정적으로 작동하기 위해서 필연적으로 다음 2가지를 해결해야 한다.
페이지 교체
프레임 할당
먼저 페이지 교체에 대해서 살펴보자. 요구 페이징 기법으로 페이지들을 적재하다 보면 언젠가는 메모리가 가득 차게 된다. 이때는 당장 실행에 필요한 페이지를 적재하기 위해서 메모리에 적재된 페이지를 보조기억장치로 내보내야 한다.
메모리에 가득찬 페이지 중 어떤 페이지를 보조기억장치로 내보내야 할까? 이를 결정하는 알고리즘이 페이지 교체 알고리즘이라고 한다.
3.2 페이지 교체 알고리즘
좋은 페이지 교체 알고리즘의 기준은 "페이지 폴트가 가장 적게 일으키는 알고리즘"을 좋은 알고리즘으로 평가한다.
페이지 폴트가 일어나면 보조기억장치로부터 필요한 페이지를 가져와야 하기 때문에 메모리에 적재된 페이지를 가져오는 것보다 느려지기 때문이다.
페이지 폴트가 자주 일어나는 것을 다른말로 하면, "보조기억장치로 내쫓을 페이지를 잘못 골랐다." 라는 의미가 된다. 이는 당연히 컴퓨터 성능을 저해하는 나쁜 알고리즘일 것이다.
그렇기에 페이지 교체 알고리즘을 제대로 이해하려면 "페이지 폴트 횟수" 알 수 있어야 한다. 그리고 페이지 폴트 횟수는 "페이지 참조열(page reference string)" 을 통해 알 수 있다.
페이지 참조열 : CPU 가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열을 의미한다.
연속된 페이지를 생략하는 이유는 중복된 페이지를 참조하는 행위는 페이지 폴트를 발생시키지 않기 때문이다.
페이지 교체 알고리즘을 평가할 때 관심있게 고려할 것은 오직 페이지 폴트의 발생 횟수이기 때문에 어차피 페이지 폴트가 일어나지 않을 연속된 페이지에 대한 참조는 고려하지 않는 것이다.
3.2.1 FIFO 페이지 교체 알고리즘
"FIFO 페이지 교체 알고리즘" 은 가장 단순한 방법으로, 이름 그대로 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식이다.
FIFO 페이지 교체 알고리즘은 아이디어와 구현은 단순하지만, 마냥 좋은 것은 아니다.
프로그램 실행 초기에 적재된 페이지 속에는 프로그램 실행 초기에 잠깐 실행되다가 이후에 사용되지 않을 페이지도 있겠지만, 프로그램 실행 내내 사용될 내용을 포함할 수도 있다.
이런 페이지는 메모리에 먼저 적재되었다고 해서 내쫓아서는 안된다.
3.2.2 최적 페이지 교체 알고리즘
"최적 페이지 교체 알고리즘"은 CPU 에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘이다.
잘 생각해보면 메모리에 오랫동안 남아야 할 페이지는 자주 사용될 페이지고,
반대로 메모리에 없어도 될 페이지는 오랫동안 사용되지 않을 페이지인데,
오랜 기간 메모리에 있었던 페이지라고 해서 보조기억장치로 내쫓는 것은 비합리적이라고 볼 수 있다.
따라서 보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지이므로, 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘을 페이지 교체 알고리즘으로 삼는 것이 가장 합리적이다.
최적 페이지 교체 알고리즘은 이름 그대로 가장 낮은 페이지 폴트율을 보장하는 알고리즘이다.
다만, 최적 페이지 교체 알고리즘은 실제 구현이 어렵다. 오랫동안 사용되지 않을 페이지를 예측하기란 매우 어렵다. (이는 현실적으로 불가능에 가깝다..)
따라서 최적 페이지 교체 알고리즘은 운영체제에서 사용하기 보다는, 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용된다.
3.2.3 LRU 페이지 교체 알고리즘
최적 페이지 교체 알고리즘은 조금 변형한 방식으로 "LRU 페이지 교체 알고리즘"이 있다.
LRU 페이지 교체 알고리즘은 '최근에 사용하지 않은 페이지는 앞으로도 사용하지 않을 것' 이라는 전재가 있다.
최적 페이지 교체 알고리즘 : 가장 오래 사용되지 않을 페이지 교체
LRU 페이지 교체 알고리즘 : 가장 오래 사용되지 않은 페이지 교체
페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용 시간이 적었던 페이지를 교체한다.
이 외에도 페이지 교체 알고리즘의 종류는 매우 다양하다. (페이지 교체는 왜 하고, 무엇이 좋은 페이지 교체 알고리즘인지 기준을 세우는 것을 목표로 하자!)
3.3 스레싱과 프레임 할당
페이지 폴트가 자주 발생하는 이유는 나쁜 페이지 교체 알고리즘만 있는 것은 아니다. 프로세스가 사용할 수 있는 프레임의 수가 적어도 페이지 폴트는 자주 발생한다. 반대로 페이지가 사용할 수 있는 프레임의 수가 늘어난다면 페이지 폴트가 줄어든다.
이처럼 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 "스레싱(thrashing)" 이라고 한다.
이를 기반으로 생각해볼 때 아무리 CPU 성능이 뛰어나도 동시에 실행되는 프로세스를 수용할 물리 메모리가 너무 작다면 전체 컴퓨터의 성능이 안 좋아지는 이유는 이러한 이유 때문이다.
스레싱이 발생한 이유는 각 프로세스가 필요로 하는 최소한의 프레임 수가(메모리) 보장되지 않았기 때문이다.
각 프로세스가 필요로 하는 최소한의 프레임 수를(메모리) 파악하고 프로세스들에게 적절한 프레임을 할당해주어야 한다.
우선 가장 간단한 형태의 프레임 할당을 알아보자. 모든 프로세스에 균등하게 프레임을 제공하는 방식이다. 이를 "균등 할당"이라고 한다.
하지만 짐작할 수 있다시피 그리 권장하는 방법은 아니다. 실행되는 프레임의 크기는 각기 다른데, 프로세스마다 동일하게 프레임을 할당하는 방식은 비합리적이다.
때문에, 프로세스 크기가 크면 프레임을 많이 할당하고 적으면 적게 할당하는 방식이 있는데, 이를 "비례 할당" 이라고 한다.
비례 할당도 완벽한 방식은 아니다. 크기에 비례해서 할당하더라도 막상 모든 프레임이 필요하지 않을 수 있다.
결국 실행해봐야 필요한 프레임을 알 수 있다!
프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 "작업 집합 모델" 을 사용하는 방식과 "페이지 폴트 빈도" 를 사용하는 방식이 있다.
말이 어렵지 사실은 단순하다.
3.3.1 작업 집합 모델
작업 집합 모델 프레임 할당은
'프로세스가 일정 기간 동안 참조한 페이지 집합'을 기억하여 빈번한 페이지 교체를 막는다.
스레싱이 발생하는 이유는 빈번한 페이지 교체 때문
그렇다면 CPU 가 특정 시간 동안 주로 참조한 페이지 개수만큼만 프레임을 할당하면 된다.
작업 집합을 기억하여 빈번한 페이지 교체를 방지하는 방식
실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 "작업 집합"이라고 한다.
3.3.2 페이지 폴트 빈도 프레임 할당 (G1GC 랑 비슷한데?)
이는 아래 두개의 가정에 의해 생겨난 아이디어이다.
페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 가지고 있다.
만약 페이지 폴트율이 상한선보다 더 높아지면 그 프로세스는 너무 적은 프레임을 가지고 있다고 볼 수 있다. 이 경우 프레임을 더 할당해주면 된다.
반대로 페이지 폴트율이 하한선보다 더 낮아지면 그 프로세스는 너무 많은 프레임을 가지고 있다고 볼 수 있다. 이때는 프레임을 회수한다.
Last updated