가상 메모리

---

1. 스와핑

• 스와핑은 메모리에서 사용되지 않는 일부 프로세스를 보조기억장치(하드디스크)로 내보내고, 실행할 프로세스를 메모리로 들여보내는 메모리 관리 기법이다.

• 이때 프로세스들이 쫓겨나는 보조기억장치의 영역을 스왑 영역이라고 한다.

• 실행되지 않는 프로세스가 스왑 영역으로 옮겨지는 것을 스왑 아웃이라고 한다.

• 반대로 스왑 영역에 있던 프로세스를 다시 메모리로 옮겨오는 것을 스왑 인이라고 한다.

• 스왑 아웃되었던 프로세스가 다시 스왑 인될 때는 기존의 물리 주소와는 다른 주소에 적재될 수 있다.

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

• 이처럼 프로세스 A, B, C, D의 크기를 합하면 메모리 크기보다 크지만, 스와핑을 통해 4개의 프로세스를 동시에 실행할 수 있다.

2. 연속적 메모리 할당

• 프로세스를 메모리의 빈 공간에 연속적으로 할당하는 방법에는 최초 적합, 최적 적합, 최악 적합 3가지 방법이 있다.

• 만약 메모리를 고정된 파티션(길이)로 분할할 경우 필요한 용량보다 더 큰 메모리를 받으면 메모리가 낭비되는 내부 단편화가 발생한다.

• 메모리를 프로세스의 크기와 같은 파티션으로 동적으로 분할하여도 외부 단편화가 발생한다.

2.1. 최초 적합

• 최초 적합은 운영체제가 메모리 내의 빈 공간을 순차적으로 탐색하다가 적재할 수 있는 공간을 발견하는 즉시 그 공간에 프로세스를 배치하는 방식이다.

• 최초 적합 방식은 메모리 검색을 최소화하여 빠른 할당이 가능하다.

2.2. 최적 적합

• 최적 적합은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 작은 공간에 프로세스를 배치하는 방식이다.

• 메모리의 낭비가 적지만, 메모리를 전부 탐색해야하기 때문에 시간이 오래걸린다.

2.3. 최악 적합

• 최적 적합은 운영체제가 빈 공간을 모두 검색해 본 후, 프로세스가 적재될 수 있는 공간 중 가장 큰 공간에 프로세스를 배치하는 방식이다.

• 메모리 낭비도 크고, 메모리를 전부 탐색해야하기 때문에 시간도 오래 걸린다.

2.4. 외부 단편화

• 프로세스들이 메모리에 연속적으로 할당되는 환경에서 프로세스들이 실행되고, 종료되기를 반복하다보면 메모리 사이에 빈 공간들이 생긴다.

• 빈 공간들이 프로세스를 할당하기 어려울 만큼 작은 메모리 공간이라면 다른 메모리를 적재하기 어렵고, 이는 메모리 낭비로 이어진다.

• 외부 단편화를 해결할 수 있는 대표적인 방안으로 메모리를 압축하는 방법이 있다. (메모리 조각 모음)

• 압축을 통해 여기저기 흩어져 있는 빈 공간들을 하나의 큰 빈공간으로 만들 수 있다.

• 다만 압축을 수행하기 위해서는 시스템이 하던 일을 중지해야하고, 메모리에 있는 내용을 옯기는 작업에는 많은 오버헤드가 발생한다.

• 이러한 단점을 해결하고자 가상 메모리 기법과 페이징 기법을 사용한다.

3. 가상 메모리

• 가상 메모리는 실행하고자 하는 프로그램을 일부만 메모리에 적재하여 실제 물리 메모리의 크기보다 더 큰 프로세스를 실행할 수 있게 하는 기술이다.

• 가상 메모리 관리 기법에는 크게 페이징과 세그멘테이션이 있다.

• 세그멘테이션 기법은 가상 메모리를 서로 크기가 다른 논리적 단위의 세그먼트로 분할한 후, 메모리를 할당하여 실제 메모리 주소로 변환하는 방식으로 각 세그먼트가 연속적인 공간에 저장된다. 세그멘테이션 기법은 프로세스가 연속적인 공간에 저장되기 때문에 외부 단편화 문제는 여전히 발생한다.

페이징 기법을 통해 물리 메모리보다 큰 프로세스를 실행할 수 있을 뿐만 아니라 외부 단편화 문제도 해결할 수 있다.

3.1. MMU (Memory Management Unit)

• CPU는 MMU에 존재하는 논리 주소를 통해 메모리에 존재하는 물리 주소에 접근한다.

• MMU는 대부분 CPU 내부에 존재하며, 페이지 테이블을 캐시한 TLB를 참조하여 CPU에서 요구하는 메모리의 물리 주소에 접근한다.

3.2. 페이징

• 페이징은 메모리의 물리 주소 공간을 프레임(페이지와 동일한 크기의 일정한 단위) 단위로 자르고, 프로세스의 논리 주소 공간을 페이지(일정한 단위)로 자른 뒤 각 페이지를 프레임에 할당하는 가상 메모리 관리 기법이다.

• 페이징을 사용하면 페이지 단위로 스와핑을 할 수 있다.

• 페이징 시스템에서의 스왑 아웃은 페이지 아웃, 스왑 인은 페이지 인이라고 부린다.

• 프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있다.

3.3. 페이지 테이블

• 프로세스가 메모리에 페이지 단위로 불연속적으로 배치되어 있다면 CPU는 프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 알아야만 한다.

• 이를 위해 페이징 시스템은 프로세스의 물리 주소가 불연속적으로 배치되었더라도, CPU가 찾을 수 있는 논리 주소에는 연속적으로 배치되도록 페이지 테이블을 사용한다.

• 페이지 테이블의 페이지 번호를 이용해 페이지가 적재된 프레임을 찾을 수 있다.

• 프로세스마다 각자의 페이지 테이블을 가지고 있고, 각 페이지 테이블은 메모리에 적재되어 있다.

• 페이지 테이블의 주소는 PCB에 기록된다.

• 문맥 교환 시에 PCB에서 현재 실행할 프로세스의 페이지 테이블 주소를 읽어와 CPU 내의 페이지 테이블 베이스 레지스터(PTBR)에 저장하여 PTBR이 해당 프로세스의 페이지 테이블을 가리킨다.

• 하지만 이렇게 페이지 테이블을 메모리에 두면 페이지 테이블 접근과 프레임 접근, 이렇게 2번의 메모리 접근이 필요하기 때문에 메모리 접근 시간 또한 2배로 늘어난다.

• 메모리 접근 시간이 2배로 늘어나는 문제를 해결하기 위해 TLB라는 페이지 테이블 캐시 메모리를 사용한다.

• CPU에서 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우를 TLB 히트라고 한다. 이 경우 메모리 접근이 불필요하다.

• CPU에서 발생한 논리 주소에 대한 페이지 번호가 TLB에 없는 경우를 TLB 미스라고 한다. 이 경우 어쩔 수 없이 페이지가 적재된 프레임을 알기 위해 메모리 접근이 필요하다.

3.4. 페이징에서의 주소 변환

• 하나의 페이지 혹은 프레임은 여러 주소를 포괄하고 있다.

• 논리 주소는 기본적으로 페이지 번호(page number)와 변위(offset)으로 이루어져 있다.

  • ex)
    CPU 32비트라면 N 비트는 페이지 번호, 32-N비트는 변위

• 페이지 번호: 접근하고자 하는 페이지 번호, 이를 통해 페이지에 해당하는 프레임의 물리 주소를 알 수 있다.

• 변위: 접근하려는 주소가 프레임의 시작 주소로부터 얼마나 떨어져 있는지 알기 위한 정보

• 논리주소<페이지 번호, 변위>을 물리주소<프레임 번호, 변위>로 변환

3.5. 페이지 테이블 엔트리

• 페이지 테이블의 각각의 행들을 페이지 테이블 엔트리라고 한다.

• 페이지 테이블 엔트리에는 유효 비트, 보호비트, 참조비트, 수정비트 정보가 담겨있다.

3.5.1. 유효 비트

• 해당 페이지 접근 가능 여부에 대한 정보

• 현재 페이지가 메모리에 적재되어 있다면 1, 그렇지 않고 보조기억장치의 스왑영역에 있다면 0

• CPU가 유효비트가 0인 페이지에 접근하려고 할 경우 페이지 폴트(page fault) 예외 발생

• 페이지 폴트 처리 과정
  1. CPU는 기존의 작업 내역을 백업

  2. 페이지 폴트 처리 루틴 실행
  3. 페이지 처리 루틴에 의해 원하는 페이지를 메모리에 적재한 뒤 유효비트 1로 변경
  4. CPU가 해당 페이지에 접근 가능

3.5.2. 보호 비트

• 보호 비트를 통해 해당 페이지에 접근할 권한을 제한하여 페이지를 보호
  

3.5.3. 참조 비트

• 해당 페이지가 메모리에 적재된 이후 CPU가 접근한 적이 있는지 여부

• 적재 이후 CPU가 접근한 적이 있다면 1, 없다면 0으로 유지

3.5.4. 수정 비트

• 해당 페이지가 메모리에 적재된 이후 데이터가 수정된 적이 있는지 여부

• 더티 비트(dirty bit)라고도 한다.

• 페이지가 수정된 적이 있다면 1, 없다면 0

• 수정 비트가 필요한 이유: 페이지가 메모리에서 사라질 때(페이지 아웃) 보조기억장치에 쓰기 작업을 수행할지 판단하기 위함

3.6. 페이징 이점 - 쓰기 시 복사

• 외부 단편화 문제 해결 이외에도 페이징은 프로세스 간 페이지를 공유할 수 있다는 점에서 다양한 이점들을 제공한다.

• 대표적으로 쓰기 시 복사라는 이점을 제공한다.

• 프로세스 간에는 기본적으로 자원을 공유하지 않는다. 하지만 fork를 통해 부모 프로세스의 복사본이 자식 프로세스로 만들어지는 경우에는 부모 프로세스와 자식 프로세스가 동일한 프레임을 가리킨다.

• 하지만 부모와 자식 프로세스 둘 중 하나가 페이지에 쓰기 작업을 수행하는 순간 해당 페이지가 별도의 공간으로 복제되어 고유한 페이지가 할당된 프레임을 가리킨다. 이것을 쓰기 시 복사라고 한다.

• 쓰기 시 복사를 통해 프로세스 생성 시간을 줄일 수 있고, 메모리 공간도 절약할 수 있다.

3.7. 계층적 페이징

• 계층적 페이징은 페이지 테이블을 페이징하여 여러 단계의 페이지를 두는 방식이다.

• 페이지 테이블도 메모리에 적재되므로 모든 페이지 테이블 엔트리를 메모리에 두는 것은 큰 메모리 낭비이다.

• 그래서 페이지 테이블을 계층적으로 구성하여 필요한 경우에만 메모리에 적재할 수 있다.

4. 페이지 교체

• 가상 메모리를 통해 물리 메모리보다 큰 프로세스를 실행할 수 있다고 해도 운영체제는 프로세스들이 한정된 메모리를 효율적으로 이용할 수 있도록 기존에 메모리에 적재된 불필요한 페이지를 보조기억장치로 보내고, 프로세스들에 적절한 수의 프레임을 할당하여 페이지를 할당할 수 있어야 한다.

• 이를 위해서는 요구 페이징, 페이지 교체 알고리즘, 프레임 할당에 대해서 알고 있어야 한다.

4.1. 요구 페이징

• 페이지가 필요할 때에만 메모리에 적재하는 기법

• 요구 페이징의 기본 메커니즘

  1. CPU가 특정 페이지에 접근하는 명령어 실행
  2. 해당 페이지가 메모리에 적재된 경우(유효비트가 1인 경우) CPU는 페이지가 적재된 프레임에 접근
  3. 해당 페이지에 메모리가 없는 경우(유효 비트가 0인 경우) 페이지 폴트 발생
  4. 페이지 폴트 처리 루틴에 따라 페이지를 메모리에 적재하고 유효 비트를 1로 설정
  5. 위를 반복

• 아무런 페이지도 메모리에 적재되지 않은 상태로 실행되는 요구 페이징을 순수 요구 페이징이라고 한다.

• 요구 페이징 시스템이 안정적으로 작동하기 위해서는 페이지 교체와 프레임 할당이 필요하다.

4.2. 페이지 교체 알고리즘

• 페이지 교체 알고리즘의 목적은 페이지 폴트를 가장 적게 일으키기 위함이다.

• 페이지 교체 알고리즘을 이해하기 위해서는 페이지 폴트 횟수가 중요한데 이는 페이지 참조열을 통해 알 수 있다.

※페이지 참조열: CPU가 참조하는 페이지들 중 연속된 페이지를 생략한 페이지열
ex) 2 2 2 3 5 3 3 7 -> 2 3 5 3 7

4.2.1. FIFO 페이지 교체 알고리즘

• 메모리에 적재된 순서대로 교체하는 알고리즘

• 프로그램의 실행 빈도나 패턴을 고려하지 못함

4.2.2. 최적 페이지 교체 알고리즘

• 앞으로의 사용 빈도가 가장 낮은 페이지를 교체하는 알고리즘

• 현실적으로 불가능 (앞으로 사용하지 않을 페이지를 예측하는게 어려움)

4.2.3. LRU(Least Recently Used) 페이지 교체 알고리즘

• 가장 오랫동안 사용되지 않은 페이지를 교체하는 알고리즘

• 많은 파생 알고리즘 존재

4.3. 스래싱

• 빈번한 페이지 교체로 인해 CPU 사용률이 낮아지는 문제(성능 저하)를 스래싱이라고 한다.

4.4. 프레임 할당

• 스래싱의 발생을 예방하기 위해서는 프로세스들에 적절한 수의 프레임을 할당해 주어야 한다.

4.4.1. 정적 할당

• 프로세스의 크기와 물리 메모리의 크기만 고려하여 프레임을 할당하는 정적 할당 방식에는 균등 할당과 비례 할당이 있다.

• 프로세스의 크기와 실제로 실행할 때 필요한 프레임이 다를 수도 있다.

• 균등 할당: 모든 프로세스에 동일한 프레임을 배분

• 비례 할당: 프로세스 크기에 따라 프레임을 배분

4.4.2. 동적 할당

• 프로세스의 실행에 따라 할당할 프로세스를 결정하는 방식

• 동적 할당은 작업 집합 모델 혹은 페이지 폴트율에 따라 프레임을 할당한다.

• 작업 집합 모델 기반: 실행 중인 프로세스가 일정 시간 동안 참조한 페이지의 집합을 기반으로 프레임을 할당

• 페이지 폴트율 기반: 페이지 폴트율의 상항선과 하한선을 기준으로 해당 범위 내에서만 프레임을 할당
  • 페이지 폴트율이 너무 높으면 프레임을 더 할당해 준다.
  • 페이지 폴트율이 너무 낮으면 프레임을 회수한다.