[혼자 공부하는 컴퓨터 구조 + 운영체제] 14강 가상메모리

연속 메모리 할당

프로세스 A는 A의 크기만큼 메모리 주소를 할당받아 연속적으로 배치되고, 프로세스 B는 프로세스 A이후에 B의 크기만큼 연속적인 메모리 주소를 할당받아 배치되는 방식을 연속 메모리 할당이라고 한다. 이 방식을 구현할 때 무엇을 고려해야 하고, 어떤 잠재적인 문제가 있는지 알아본다.

스와핑

메모리에 적재된 프로세스들 중에선 현재 실행되지 않는 프로세스가 있을 수 있다. 대기중인 프로세스나 오랫동안 사용되지 않은 프로세스가 그렇다. 스와핑은 이러한 프로세스들을 임시로 보조기억장치 일부 영역으로 쫓아내고, 그렇게 해서 생긴 메모리상의 빈 공간에 또 다른 프로세스를 적재하여 실행하는 방식이다.

• 스왑 영역 : 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
• 스왑 아웃 : 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
• 스왑 인 : 스왑 아웃되었던 프로세스가 다시 메모리로 옮겨오는 것

스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리보다 큰 경우에도 프로세스를 동시에 실행할 수 있다.

메모리 할당

프로세스는 메모리 내에 빈 공간에 적재되어야 한다. 메모리 내에 빈 공간이 여러 개 있다면 프로세스를 어떻게 배치해야 할까? 프로세스를 연속적으로 할당하는 방식을 알아보자.

다음과 같은 상황에서 20MB의 크기를 갖는 프로세스를 저장해야한다면 어떻게 해야 할까?

• 최초 적합
  • 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식이다. 빈 공간 A → B → C 순서로 검색했다면, 빈 공간 A에 적재된다.
  • 프로세스가 적재될 수 있는 공간을 발견하는 즉시 메모리를 할당하는 방식으로 검색을 최소화할 수 있어 빠른 할당이 가능하다.
• 최적 적합
  • 운영체제가 빈 공간을 모두 검색해 본 후, 적재할 수 있는 공간중 가장 작은 공간에 프로세스를 배치한다. 예시에서는 빈 공간C가 여기에 해당한다.
• 최악 적합
  • 운영체제가 빈 공간을 모두 검색해본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치한다. 예시에서는 빈 공간 B가 여기에 해당한다.

외부 단편화

프로세스를 메모리에 연속적으로 배치하는 연속 메모리 할당은 당연하게 느껴질 수 있지만, 이는 효율적인 메모리 사용 방법이 아니다. 왜냐하면 외부 단편화라는 문제를 내포하고 있기 때문이다.

프로세스가 추가되고 제거되면서 크고 작은 빈 공간이 생기게 되는데, 빈 공간보다 큰 프로세스는 적재할 수 없다. 따라서 프로세스를 적재하는 게 시간이 오래 걸리게 되며, 이렇게 메모리 낭비로 이어지는 현상을 외부 단편화라고 한다.

외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축하는 방법이 있다. 압축은 작은 빈 공간을 하나로 모아서 하나의 큰 빈 공간으로 만드는 방법이다. 다만 여러 단점이 있는데, 작은 공간을 모으는 과정에서 하던 일을 중지해야 하며, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하고, 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하여 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵다. 이에 외부 단편화를 없앨 수 있는 또 다른 해결 방안이 등장했는데, 이 것이 가상 메모리 기법과 페이징 기법이다.

페이징을 통한 가상 메모리 관리

프로세스를 연속적으로 할당하면 외부 단편화와 물리 메모리보다 큰 프로세스를 실행할 수 없다는 문제가 있다. 프로세스를 반드시 연속적으로 할당해야 한다면 메모리보다 큰 프로그램은 적재할 수 없다.

가상메모리는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있는 기술이다. 이를 가능케 하는 가상 메모리 관리 기법에는 크게 페이징과 세그멘테이션이 있지만, 현대 대부분 운영체제가 페이징을 사용하므로 페이징만 다뤄본다.

페이징이란

페이징은 메모리와 프로세스를 일정 단위로 자르고, 이를 메모리에 불연속적으로 할당할 수 있도록 하는 것이다. 페이징은 논리 주소 공간을 페이지라는 일정 단위로 자르고, 메모리 물리 주소 공간을 프레임이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.

페이징은 스와핑을 사용할 수 있다. 다만 프로세스 전체가 아닌 페이지 단위로 스왑 아웃/스왑 인을 할 수 있다. 페이징 시스템에서의 스왑 아웃은 페이지 아웃, 스왑 인은 페이지 인이라고 부르기도 한다.

이는 한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없다는 말과 같다. 따라서 실행에 필요한 일부 페이지만 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨두면서 물리 메모리보다 더 큰 프로세스를 실행할 수 있다.

페이지 테이블

프로세스가 메모리에 불연속적으로 배치되어 있다면 CPU 입장에서는 이를 순차적으로 실행할 수 없다. 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 모두 알기 어렵기 때문인데, 이를 해결하기 위해 페이지 테이블을 사용한다.

페이지 테이블은 페이지 번호와 프레임 번호의 짝 정보를 가지고 있는 테이블로, 이를 통해 어떤 페이지가 어떤 프레임에 할당되어 있는지 알 수 있다.

이 방식으로 물리 주소상에서는 프로세스들이 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보이게 된다. 따라서 CPU는 논리 주소를 그저 순차적으로 실행하면 된다.

내부 단편화
페이징은 외부 단편화 문제를 해결할 수 있지만, 내부 단편화라는 문제를 야기할 수 있다. 페이징은 프로세스의 논리 주소 공간을 페이지라는 단위로 자르는데, 모든 프로세스가 페이지 크기에 딱 맞게 잘리는 것은 아니다.
가령 페이지의 크기가 10KB라고 할 때, 프로세스의 크기가 108KB라면 마지막 한 페이지는 2KB만큼의 크기가 남는다. 이 것을 내부 단편화라고 한다.
프로세스마다 각자의 프로세스 테이블을 가지고 있으며, 각 프로세스의 페이지 테이블은 메모리에 적재되어 있다. 그리고 CPU 내의 페이지 테이블 베이스 레지스터(PTBR; Page Table base Register)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다.
예를 들어 프로세스 A가 실행될 때 PTBR은 프로세스 A의 페이지 테이블을 가리키고, 프로세스 B가 실행될 때 PTBR은 프로세스 B의 페이지 테이블을 가리킨다. 따라서 CPU는 PTBR을 통해서 현재 실행 중인 프로세스를 처리하면 된다.
다만 이렇게 되면 CPU가 페이지 테이블에 접근한 뒤에 프레임에 접근하게 되므로 메모리 접근 시간이 두 배로 늘어나게 되는데, 이는 CPU 곁에(일반적으로 MMU 내에) TLB(Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리를 둠으로써 해결한다.
TLB는 페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장한다. 참조 지역성에 근거해 최근에 사용된 페이지 위주로 가져와 저장한다. CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 이를 TLB 히트라고 하고, 페이지 번호가 TLB에 없을 경우를 TLB 미스라고 한다.

 

페이징에서의 주소 변환

하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있다. 그렇기에 특정 주소가 접근하려면 두 가지 정보가 필요하다.

• 어떤 페이지 혹은 프레임에 접근하고 싶은지
• 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지

그렇기 때문에 페이징 시스템에는 모든 논리 주소가 기본적으로 페이지 번호와 변위로 이루어져 있다.

• 페이지 번호 : 접근하려는 페이지의 번호로, 페이지 테이블에서 해당 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되어 있는지 알 수 있다.
• 변위 : 접근하려는 주소가 프레임의 시작 번지로부터 얼마만큼 떨어져 있는지를 알기 위한 정보

논리 주소 <페이지 번호, 변위>는 페이지 테이블을 통해 물리 주소 <프레임 번호, 변위>로 변환된다.

페이지 테이블 엔트리

페이지 테이블의 각 엔트리, 즉 페이지 테이블의 각각의 행들을 페이지 테이블 엔트리(PTE; Page Table Entry)라고 한다.

페이지 엔트리에는 페이지 번호와 프레임 번호 외에 중요한 정보가 있는데, 대표적인 것이 유효 비트, 보호 비트, 참조 비트, 수정 비트이다.

• 유효 비트
  • 해당 페이지에 접근이 가능한지 여부이다. 현재 페이지가 메모리에 적재되어 있는지, 보조기억장치에 있는지를 알려준다. 만약 유효 비트가 0인 페이지에 접근하려고 하면 페이지 폴트라는 예외가 발생한다.
  • 페이지 폴트가 발생하면 다음과 같은 과정을 처리한다.
    CPU는 기존의 작업 내역을 백업한다. → 페이지 폴트 처리 루틴을 실행한다. → 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경한다. → 페이지 폴트를 처리했다면 CPU는 해당 페이지에 접근할 수 있게 된다.
• 보호 비트
  • 페이지 보호 기능을 위해 존재한다. 비트가 0이면 읽기만 가능한 페이지임을 나타내고, 1일 경우 읽고 쓰기가 모두 가능한 페이지임을 나타낸다. 이를 통해 읽기 전용 페이지에 쓰기를 시도하면 운영체제가 이를 막아준다.
  • 보호 비트는 세 개의 비트로 조금 더 복잡하게 구현할 수 있다. 각각 읽기(r), 쓰기(w), 실행(x)의 조합으로 구성하면 읽기, 쓰기 실행 권한을 설정할 수 있다.
• 참조 비트
  • CPU가 페이지에 접근한 적이 있는지 여부를 나타낸다. 적재 이후 CPU가 읽거나 쓴 페이지는 참조 비트가 1로 세팅되고, 한 번도 읽거나 쓴 적이 없다면 0으로 유지된다.
• 수정 비트
  • 페이지의 수정 여부를 알려준다. 더티 비트라고도 불리며, 이 비트가 1이면 변경된 적이 있는 페이지이고, 0이면 변경된 적이 없는 페이지이다.
  • 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위해 존재한다. 수정된 적 없는 페이지가 스왑 아웃되면, 새로 적재할 페이지로 덮어쓰면 된다(이미 보조기억장치에 저장된 내용과 같으므로). 하지만 수정되었다면, 변경된 내용을 보조기억장치에 기록해야 한다.

Q : 페이지 인이 발생하면 보조기억장치에 저장된 페이지 정보는 삭제되는가?
A : 일반적으로 즉시 지우지거나 없애진 않는다. 페이지를 다시 메모리로 내보내야 할 때 재사용할 수 있고, 읽기 전용 페이지의 경우(코드 영역 등)에는 굳이 제거할 필요가 없기 때문이다.

쓰기 시 복사

페이징 기법이 제공하는 이점은 외부 단편화 문제를 해결한 것 외에도 다양한데, 대표적인 것이 쓰기 시 복사이다.

멀티 프로세스를 설명하면서 ‘프로세스를 fork 하여 동일한 프로세스 두 개가 복제되면 코드 및 데이터 영역을 비롯한 모든 자원이 복제되어 메모리에 적재된다’라고 했다. 이때 ‘프로세스 간에는 기본적으로 자원을 공유하지 않는다’라는 프로세스의 전통적인 개념에 입각하면 새롭게 생성된 자식 프로세스는 새로운 메모리 공간에 생성된다. 하지만 복사 작업은 오버헤드가 존재하며, 불필요한 메모리 낭비를 야기한다.

반면 쓰기 시 복사에서는 부모 프로세스와 동일한 자식 프로세스가 생성되면, 새롭게 메모리에 적재하지 않고 자식 프로세스 페이지 테이블이 부모와 동일한 페이지를 가리키도록 한다. 만일 부모 프로세스와 자식 프로세스가 읽기만 수행한다면 이 상태를 지속하다가 두 프로세스중 하나가 페이지에 쓰기 작업을 수행하면, 그 순간 페이지가 복제된다. 이 것이 쓰기 시 복사이며, 메모리 낭비와 복제 시간을 줄였다는 이점을 챙긴 기능이다.

계층적 페이징

페이지 테이블의 크기는 생각보다 작지 않다. 프로세스의 크기가 커지면 자연히 테이블도 커지기 때문에 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 메모리 낭비이다. 이에 등장한 것이 계층적 페이징이다.

계층적 페이징은 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식이다. 프로세스의 페이지 테이블을 여러 개의 페이지로 자르고, 바깥쪽에 페이지 테이블을 하나 더 두어 잘린 페이지 테이블의 페이지를 가리키게 한다.

계층 적 페이징을 사용하는 경우 CPU가 발생하는 논리 주소도 달라진다. 페이지 번호가 바깥 페이지 번호와 안쪽 페이지 번호로 나뉘게 된다.

• 바깥 페이지 번호 : CPU와 근접한 곳에 위치한 페이지 테이블 엔트리의 번호
• 안쪽 페이지 번호 : 페이지 테이블의 페이지 번호

이러한 논리 주소를 토대로 주소 변환은 다음과 같이 이루어진다.

1. 바깥 페이지 번호를 통해 페이지 테이블의 페이지 찾기
2. 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로써 물리 주소 얻기

계층적 페이징은 페이지 폴트가 발생했을 때 메모리 참조 횟수가 많아지므로 계층이 많다고 해서 반드시 좋다고 볼 수 없다.

페이지 교체와 프레임 할당

운영체제는 메모리에 적재된 불필요한 페이지를 선별하여 보조기억장치로 내보낼 수 있어야 하고, 프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있게 해야 한다. 운영체제가 어떻게 이러한 기능을 수행하는지 알아보자.

요구 페이징

프로세스를 메모리에 적재할 때 모두가 아닌, 필요한 페이지만을 메모리에 적재하는 기법을 요구 페이징이라고 한다. 즉, 실행에 요구되는 페이지만 적재하는 기법이다.

요구 페이징의 기본적인 양상

1. CPU가 특정 페이지에 접근하려는 명령어를 실행한다.
2. 해당 페이지가 현재 메모리에 있을경우 CPU는 페이지가 적재된 프레임에 접근한다.
3. 해당 페이지가 현재 메모리에 없을 경우 페이지 폴트가 발생한다.
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정한다.
5. 다시 1번을 수행한다.

아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행할 수 있으며, 이 경우 첫 명령어를 실행하는 순간부터 페이지 폴트가 계속 발생하지만, 서서히 빈도가 떨어진다. 이를 순수 요구 페이징 기법이라고 한다.

요구 페이징이 안정적으로 작동하려면 페이지 교체와 프레임 할당이 해결되어야 한다.

요그 페이징 기법으로 페이지를 적재하다보면 언젠간 메모리가 가득 차게 된다. 따라서 일부 페이지를 보조기억장치로 내보내야한다. 이때 어떤 페이지를 내보낼지 결정하는 것이 페이지 교체 알고리즘이다.

페이지 교체 알고리즘

좋은 페이지 교체 알고리즘은 페이지 폴트를 적게 일으키는 알고리즘이다. 페이지 폴트가 발생하면 보조기억장치에서 가져와야 하므로 매우 느리기 때문이다.

페이지 교체 알고리즘을 이해하려면 페이지 폴트 횟수를 알아야한다. 페이지 폴트 횟수는 페이지 참조열을 통해 알 수 있다. 페이지 참조열은 CPU가 참조하는 페이지 중 연속된 페이지를 생략한 페이지 열을 의미한다. 연속된 페이지를 생략하는 이유는, 중복된 페이지를 참조하는 행위는 페이지 폴트를 일으키지 않기 때문이다.

가령 ‘2 2 2 3 5 5 5 3 3 7’순서로 페이지에 접근했다면, 페이지 참조열은 ‘2 3 5 3 7’이다.

• FIFO 페이지 교체 알고리즘
  • 가장 단순한 알고리즘으로, 가장 먼저 올라온 페이지부터 내쫓는 방식이다.
  • 아이디어와 구현이 간단하지만, 마냥 좋은 것은 아니다. 프로그램 실행 초기에 적재된 페이지에 프로그램 실행 내내 사용될 내용을 포함할수도 있기 때문이다.
• 최적 페이지 교체 알고리즘
  • CPU에 의해 참조되는 횟수를 고려하는 페이지 참조 알고리즘이다. 오랫동안 사용되지 않을 페이지는 메모리에 없어도 될 페이지이므로, 앞으로 사용 빈도가 가장 낮은 페이지를 교체한다.
  • 이는 가장 낮은 페이지 폴트율을 보장하지만 구현하기 매우 어렵다. 앞으로 오랫동안 사용되지 않을 페이지를 예측하는 것이 현실적으로 불가능에 가깝기 때문이다. 따라서 최적 페이지 교체 알고리즘은 운영체제에서 사용하기보단, 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용된다.
• LRU 페이지 교체 알고리즘
  • 최적 페이지 교체 알고리즘과 비슷한 알고리즘은 만들 수 있는데, 가장 오랫동안 사용되지 ‘않은’ 페이지를 교체하는 알고리즘이 그렇다. 이것이 LRU 페이지 교체 알고리즘으로, 페이지마다 마지막으로 사용한 시간을 토대로 최근에 가장 사용이 적었던 페이지를 교체한다.

스래싱과 프레임 할당

페이지 폴트가 자주 발생하는 또 다른 이유로는 프로세스가 사용할 수 있는 프레임 수가 적은 것이다. 프레임의 수가 부족하면 CPU는 페이지 폴트가 자주 발생할 수 밖에 없는데, 이처럼 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제를 스래싱이라고 한다.

메모리에 동시에 실행되는 프로세스의 수를 멀티프로그래밍의 정도(degree of multiprogramming)라고 한다. 멀티프로그래밍의 정도가 높다면 그만큼 많은 프로세스가 동시에 실행중이라고 이해하면 된다.

스래싱이 CPU 이용률에 끼치는 영향

이 그래프는 멀티프로그래밍의 정도가 높을수록 CPU 이용률이 그만큼 증가하지 않음을 나타낸다. 멀티프로그래밍의 정도가 어느 정도 증가하면 CPU 이용률이 높아지지만, 필요 이상으로 늘리면 스래싱이 발생하면서 성능이 저하된다. CPU의 성능이 아무리 뛰어나도 메모리가 너무 작다면 컴퓨터의 성능이 안좋아지는 이유가 이것이다.

스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다. 그렇기에 운영체제는 각 프로세스들이 무리없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해줄 수 있어야 한다.

가장 단순한 형태의 프레임 할당 방식부터 알아보자.

• 균등 할당
  • 세 개의 프로세스에 총 300개의 프레임을 할당할 수 있다면, 각 프로세스에 100개의 프로세스를 할당하는 방식이다.
  • 하지만 이는 프로세스들의 크기가 각기 다르기 때문에 권장할만한 방법은 아니다.
• 비례 할당
  • 프로세스의 크기가 크면 프레임을 많이 할당하고 프로세스 크기가 작으면 프레임을 적게 나눠주는 방식이다.
  • 하지만 프로세스의 크기가 크더라도 막상 실행해보니 많은 프레임을 필요로 하지 않는 경우도 있다. 반대로 프로세스의 크기가 작아도 실행해보니 많은 프레임을 필요로 하는 경우도 있다. 결국 실행해봐야 아는 경우가 많다.

프로세스를 실행하는 과정에서 배분할 프레임을 결정하는 방식에는 크게 작업 집합 모델을 사용하는 방식과 페이지 폴트 빈도를 사용하는 방식이 있다.

• 작업 집합 모델
  • 프로세스가 일정 기간동안 참조한 페이지 집합을 기억하여 빈번한 페이지 교체를 방지하는 방식이다. 이는 참조 지역성의 원리를 근거로 한다.
  • 실행 중인 프로세스가 일정 시간동안 참조한 페이지의 집합을 작업 집합이라고 한다. CPU가 과거에 주로 참조한 페이지를 작업 집합에 포함한다면 운영체제는 작업 집합의 크기만큼만 프레임을 할당해주면 된다.
• 페이지 폴트 빈도
  • 이 방식은 ‘페이지 폴트율이 너무 높으면 그 프로세스는 적은 프레임을 갖고 있다’, ‘페이지 폴트율이 너무 낮으면 그 프로세스는 많은 프레임을 갖고 있다’라는 가정에서 생겨난 아이디어이다.
  • 이는 상한선과 하한선을 가정하고 상한선보다 높아지면 프레임을 더 할당해주고, 하한선보다 낮아지면 프레임을 회수하는 방식이다.