[ 혼자 공부하는 컴퓨터구조 + 운영체제 ] Chapter14. 가상 메모리
14-1. 연속 메모리 할당
연속 메모리 할당: 프로세스에 연속적인 메모리 공간을 할당하는 방식
(1) 스와핑
스와핑(swapping): 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치로 내보내고 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법
스왑 영역(swap space): 프로세스들이 쫓겨나는 보조기억장치의 일부 영역
스왑 아웃(swap-out): 현재 실행되지 않는 프로세스가 메모리에서 스왑 영역으로 옮겨지는 것
스왑 인(swap-in): 스왑 영역에 있던 프로세스가 다시 메모리로 옮겨오는 것
스와핑을 이용하면 프로세스들이 요구하는 메모리 주소 공간의 크기가 실제 메모리 크기보다 큰 경우에도 프로세스들을 동시 실행할 수 있다.
(2) 메모리 할당
비어 있는 메모리 공간에 프로세스를 연속적으로 할당하는 방식은 대표적으로 최초 적합, 최적 적합, 최악 적합이 있다.
최초 적합(first fit)
: 운영체제가 메모리 내의 빈 공간을 순서대로 검색하다가 적재할 수 있는 공간을 발견하면 그 공간에 프로세스를 배치하는 방식
- 검색을 최소화할 수 있고 결과적으로 빠른 할당이 가능하다.
최적 적합(best fit)
: 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식
최악 적합(worst fit)
: 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식
(3) 외부 단편화
연속 메모리 할당은 외부 단편화라는 문제를 내포하고 있다.
프로세스들이 실행되고 종료되기를 반복하며 메모리 사이 사이에 빈 공간들이 생기는데, 위 그림과 같은 상황에서 빈 공간의 총합은 50MB일지라도 어느 빈 공간에도 50MB 크기의 프로세스가 적재될 수 없다.
외부 단편화(external fragmentation): 프로세스를 할당하기 어려울 만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상
외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축하는 방법이 있다.
압축(compaction): 메모리 내에 저장된 프로세스를 적당히 재배치시켜 여기저기 흩어져 있는 작은 빈 공간들을 하나의 큰 빈 공간으로 만드는 방법
다만 압축 방식은 작은 빈 공간들을 하나로 모으는 동안 시스테은 하던 일을 중지해야 하고, 메모리에 있는 내용을 옮기는 작업은 많은 오버헤드를 야기하며, 어떤 프로세스를 어떻게 움직여야 오버헤드를 최소화하며 압축할 수 있는지에 대한 명확한 방법을 결정하기 어렵다.
14-2. 페이징을 통한 가상 메모리 관리
프로세스를 메모리에 연속적으로 할당하는 방식은 외부 단편화 문제와, 물리 메모리보다 큰 프로세스를 실행할 수 없다는 문제를 가지고 있다.
가상 메모리(virtual memory): 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술
가상 메모리 관리 기법에는 크게 페이징과 세그멘테이션이 있지만, 현재 대부분의 운영체제는 페이징 기법을 사용한다.
(1) 페이징이란
연속 메모리 할당 방식에서 외부 단편화가 생긴 근본적인 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문이다.
페이징(paging): 프로세스의 논리 주소 공간을 페이지(page)라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임(frame)이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법
페이징을 사용하는 시스템에서는 프로세스 전체가 스왑 아웃/스왑 인되는 것이 아닌 페이지 단위로 스왑 아웃/스왑 인된다.
페이징 시스템에서의 스왑 아웃은 페이지 아웃(page out), 스왑 인은 페이지 인(page in)이라고 부르기도 한다.
한 프로세스를 실행하기 위해 프로세스 전체가 메모리에 적재될 필요가 없기 때문에, 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않는 페이지들은 보조기억장치에 남겨둘 수 있는 것이다.
(2) 페이지 테이블
프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서 '다음에 실행할 명령어 위치'를 찾기가 어려워진다.
이를 해결하기 위해 페이징 시스템은 프로세스가 비록 (실제 메모리 주소인) 물리 주소에 불연속적으로 배치되더라도 (CPU가 바라보는 주소인) 논리 주소에는 연속적으로 배치되도록 페이지 테이블을 이용한다.
페이지 테이블(page table): 페이지 번호와 프레임 번호를 짝지어 주는 일종의 이정표로, 현재 어떤 페이지가 어떤 프레임에 할당되었는지를 알려준다.
물리 주소 상에서는 프로세스들이 분산되어 저장되어 있더라도 CPU 입장에서 바라본 논리 주소는 연속적으로 보일 수 있기 때문에, CPU는 논리 주소를 그저 순차적으로 실행하면 된다.
※ 내부 단편화(internal fragmentation)
모든 프로세스 크기가 페이지의 배수는 아니기 때문에, 페이지 크기에 딱 맞게 잘리는 것은 아니다. 가령 페이지 크기가 10KB인데, 프로세스으 크기가 108KB인 경우 마지막 페이지는 2KB만큼의 크기가 남게 되는데, 이러한 메모리 낭비를 내부 단편화라고 한다.
페이지 테이블 베이스 레지스터(PTBR): 각 프로세스의 페이지 테이블이 적재된 주소를 가리킨다.
페이지 테이블을 메모리에 두면 메모리에 있는 페이지 테이블을 보기 위해 한 번, 그렇게 알게 된 프레임에 접근하기 위해 한 번 접근해야 하기 때문에 메모리 접근 시간이 두 배로 늘어난다는 문제가 있다.
이와 같은 문제를 해결하기 위해 CPU 곁에 TLB를 둔다.
TLB(Translation Lookaside Buffer): 페이지 테이블의 캐시 메모리로, 페이지 테이블의 일부를 저장
TLB 히트: CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우
TLB 미스: 페이지 번호가 TLB에 없어 페이지가 적재된 프레임을 알기 위해 메모리 내의 페이지 테이블에 접근해야 하는 경우
(3) 페이징에서의 주소 변환
하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있는데, 특정 주소에 접근하려면 다음과 같은 두 가지 정보가 필요하다.
1. 어떤 페이지 혹은 프레임에 접근하고 싶은지
2. 접근하려는 주소가 그 페이지 혹은 프레임으로부터 얼마나 떨어져 있는지
페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호와 변위로 이루어져 있다.
페이지 번호(page number): 접근하고자 하는 페이지 번호로, 해당 페이지 번호를 찾으면 페이지가 어떤 프레임에 할당되었는지를 알 수 있다.
변위(offset): 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지
(4) 페이지 테이블 엔트리
페이지 테이블 엔트리(PTE): 페이지 테이블의 각각의 행
페이지 테이블 엔트리에는 페이지 번호, 프레임 번호 이외에도 유효 비트, 보호 비트, 참조 비트, 수정 비트 등 중요한 정보들이 있다.
유효 비트(valid bit)
: 현재 해당 페이지에 접근 가능한지 여부를 알려주는 비트
현재 페이지가 메모리에 적재되어 있는지 아니면 보조기억장치에 있는지를 알려준다.
페이지 폴트(page fault): CPU가 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하면 발생하는 예외
CPU가 페이지 폴트를 처리하는 과정은 하드웨어 인터럽트를 처리하는 과정과 유사하다.
1. CPU는 기존의 작업 내역을 백업
2. 페이지 폴트 처리 루틴을 실행
3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경
4. 페이지 폴트를 처리했다면 CPU는 해당 페이지에 접근할 수 있게 됨
보호 비트(protection bit)
: 페이지에 접근할 권한을 제한하여 페이지를 보호하는 비트
해당 페이지가 읽고 쓰기가 모두 가능한 페이지인지, 혹은 읽기만 가능한 페이지인지를 나타낼 수 있다.
- 0 → 읽기만 가능한 페이지, 1 → 읽고 쓰기가 모두 가능한 페이지
- r, w, x의 조합으로 읽기, 쓰기, 실행하기 권한을 나타낼 수도 있다.
참조 비트(reference bit)
: CPU가 이 페이지에 접근한 적이 있는지 여부를 나타내는 비트
수정 비트(modified bit) = 더티 비트(dirty bit)
: 해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려주는 비트
수정 비트는 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위해 존재한다.
CPU가 쓰기 작업을 수행한 페이지(수정 비트가 1인 페이지)의 경우 보조기억장치에 저장된 페이지의 내용과 메모리에 저장된 페이지의 내용은 서로 다른 값을 갖기 때문에, 스왑 아웃될 경우 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 한다.
※ 쓰기 시 복사
fork → 부모 프로세스의 메모리 영역이 다른 영역에 자식 프로세스로서 복제되고, 각 프로세스의 페이지 테이블은 자신의 고유한 페이지가 할당된 프레임을 가리킨다. 이는 프로세스 생성 시간을 늦출 뿐만 아니라 불필요한 메모리 낭비를 야기한다.
쓰기 시 복사 → 부모 프로세스와 동일한 자식 프로세스가 생성되면 자식 프로세스로 하여금 부모 프로세스와 동일한 프레임을 가리킨다. 부모 프로세스 혹은 자식 프로세스 둘 중 하나가 페이지에 쓰기 작업을 했을 때 해당 페이지가 별도의 공간으로 복사된다. 이를 통해 프로세스 생성 시간을 줄이며 메모리 공간 절약이 가능하다.
※ 계층적 페이징(= 다단계 페이지 테이블 기법)
: 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식
프로세스의 크기가 커지면 프로세스 테이블의 크기도 커지기 때문에 모든 페이지 테이블 엔트리를 메모리에 두는 것은 메모리 낭비이다. 페이지 테이블을 계층적으로 구성하면 페이지 테이블 중 몇 개는 보조기억장치에 있어도 무방하며, 추후 해당 페이지 테이블을 참조해야 할 때 메모리에 적재하면 된다.
1. 바깥 페이지 번호를 통해 페이지 테이블의 페이지 찾기
2. 페이지 테이블의 페이지를 통해 프레임 번호를 찾고 변위를 더함으로서 물리 주소 얻기
14-3. 페이지 교체와 프레임 할당
(1) 요구 페이징
요구 페이징(demand paging): 프로세스를 메모리에 적재할 때 처음부터 모든 페이지를 적재하지 않고 필요한 페이지만을 메모리에 적재하는 기법
1. CPU가 특정 페이지에 접근하는 명령어를 실행
2. 해당 페이지가 현재 메모리에 있을 경우(유효 비트가 1일 경우) CPU는 페이지가 적재된 프레임에 접근
3. 해당 페이지가 현재 메모리에 없을 경우(유효 비트가 0일 경우) 페이지 폴트 발생
4. 페이지 폴트 처리 루틴은 해당 페이지를 메모리로 적재하고 유효 비트를 1로 설정
5. 다시 1.을 수행
순수 요구 페이징(pure demanding paging): 아무런 페이지도 메모리에 적재하지 않은 채 무작정 실행부터 하는 기법
요구 페이징 시스템이 안정적으로 작동하려면 페이지 교체와 프레임 할당을 해결해야 한다.
(2) 페이지 교체 알고리즘
페이지 교체 알고리즘: 실행에 필요한 페이지를 적재하기 위해 보조기억장치로 내보낼 페이지를 결정하는 방법
일반적으로 페이지 폴트를 가장 적게 일으키는 알고리즘을 좋은 알고리즘으로 평가한다.
페이지 참조열(page reference string): CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
FIFO 페이지 교체 알고리즘
: 메모리에 가장 먼저 올라온 페이지부터 내쫓는 방식
아이디어와 구현이 간단하지만, 프로그램 실행 초기에 적재된 페이지 속에 프로그램 실행 내내 사용될 내용을 포함하고 있을 수도 있기 때문에 먼저 적재되었다고 해서 내쫓아서는 안 된다.
※ 2차 기회 페이지 교체 알고리즘
: FIFO 페이지 교체 알고리즘의 부작용을 어느 정도 개선한 변형 알고리즘
기본적으로 메모리에서 가장 오래 머물렀던 페이지를 대상으로 내보낼 페이지를 선별하나, 만일 페이지의 참조 비트가 1일 경우 당장 내쫓지 않고 참조 비트를 0으로 만든 뒤 최근에 적재된 페이지로 간주한다.
최적 페이지 교체 알고리즘
: CPU에 의해 참조되는 횟수를 고려하는 페이지 교체 알고리즘
보조기억장치로 내보내야 할 페이지는 앞으로 사용 빈도가 가장 낮은 페이지이므로, 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하며, 가장 낮은 페이지 폴트율을 보장한다.
다만 앞으로 오랫동안 사용되지 않을 페이지를 예측해야 하는데, 이는 현실적으로 불가능에 가깝기 때문에 실제 구현이 어렵다.
따라서 운영체제에서 사용하기보다는, 주로 다른 페이지 교체 알고리즘의 이론상 성능을 평가하기 위한 목적으로 사용된다.
LRU 페이지 알고리즘
: 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘
최근에 사용되지 않은 페이지는 앞으로도 사용되지 않을 것이라는 아이디어를 토대로 만들어진 알고리즘이다.
(3) 스래싱과 프레임 할당
스래싱(thrashing): 프로세스가 실제 실행되는 시간보다 페이징에 더 많은 시간을 소요하여 성능이 저해되는 문제
스래싱을 그래프로 표현하면 다음과 같다.
CPU 이용률: CPU가 얼마나 쉴 새 없이 일을 하고 있는지
멀티프로그래밍의 정도: 메모리에서 동시에 실행되는 프로세스의 수
스래싱이 발생하는 근본적인 원인은 각 프로세스가 필요로 하는 최소한의 프레임 수가 보장되지 않았기 때문이다.
운영체제는 각 프로세스들이 무리 없이 실행하기 위한 최소한의 프레임 수를 파악하고 프로세스들에 적절한 수만큼 프레임을 할당해 줄 수 있어야 한다.
균등 할당(equal allocation): 모든 프로세스에 균등하게 프레임을 배분하는 방식
프로세스들의 크기는 각기 다르기 때문에, 동일한 프레임 개수를 할당하는 것은 비합리적이다.
비례 할당(proportional allocation): 프로세스의 크기에 따라 프레임을 배분하는 방식
프로세스의 크기가 클지라도 막상 실행해보니 많은 프레임을 필요로 하지 않는 경우도 있다. 즉, 하나의 프로세스가 실제로 얼마나 많은 프레임이 필요한지는 결국 실행해 봐야 아는 경우가 많다.
※ 균등 할당과 비례 할당 방식은 프로세스의 실행 과정을 고려하지 않고 단순히 프로세스의 크기와 물리 메모리의 크기만 고려한 방식이라는 점에서 정적 할당 방식이라고도 한다.
작업 집합 모델(working set model): 프로세스가 일정 기간 동안 참조한 페이지 집합(작업 집합)을 기억하여 빈번한 페이지 교체를 방지
CPU가 특정 시간 동안 주로 참조한 페이지 개수, 즉 작업 집합의 크기만큼만 프레임을 할당한다.
페이지 폴트 빈도(PFF) 기반 프레임 할당: 페이지 폴트율에 상한선과 하한선을 정하고, 그 내부 범위 안에서만 프레임을 할당하는 방식
이는 다음의 두 개의 가정에서 생겨난 아이디어이다.
1. 페이지 폴트율이 너무 높으면 그 프로세스는 너무 적은 프레임을 갖고 있다.
2. 페이지 폴트율이 너무 낮으면 그 프로세스가 너무 많은 프레임을 갖고 있다.
한 프로세스에 할당된 프레임 수와 페이지 폴트 비율은 반비례 관계를 보인다.
페이지 폴트율이 상한선보다 더 높아지면 프레임을 더 할당해 주고, 하한선보다 더 낮아지면 다른 프로세스에 할당하기 위해 프레임을 회수한다.
※ 작업 집합 모델과 페이지 폴트 빈도 방식은 프로세스의 실행을 보고 할당할 프레임 수를 결정한다는 점에서 동적 할당 방식이라고도 한다.