[운영체제] 가상 메모리

1. 물리 주소와 논리 주소

CPU와 프로세스는 메모리의 하드웨어 상 실제 주소인 물리 주소가 아니라 프로세스마다 부여되는 0번지부터 시작되는 주소 체계인 논리 주소를 이용한다. 실제로 정보가 저장되어 있는 하드웨어 상의 메모리와 상호작용을 하기 위해서는 논리 주소와 물리 주소간의 변환이 이루어져야 한다.

메모리 관리 장치(Memory Management Unit / MMU)는 CPU와 메모리 사이에 위치하며, CPU가 이해하는 논리 주소를 메모리가 이해하는 물리 주소로 변환하는 역할을 한다.

 

그렇다면 왜 굳이 CPU는 논리 주소 체계를 이용하는 걸까 ? 

메모리에 적재되어있는 정보들이 시시각각 변하기 때문에 물리 주소를 이용하는 경우, 메모리의 정보가 바뀔 때마다 변경된 부분을 추적해서 기억해야 한다. 이는 곧 CPU의 할 일이 될 것이다. 하지만, 논리 주소를 이용하는 경우 사용하지 않는 다음 주소를 할당하기만 하면 되므로 CPU의 과부하를 방지할 수 있다.

 

---

 

2. 스와핑과 연속 메모리 할당

2-1. 스와핑

스와핑
: 입출력 작업을 요구하며 대기 상태가 되었거나, 오랫동안 사용되지 않은 프로세스를 스왑 영역으로 옮겨 메모리 상의 공간을 확보하는 작업 

스왑 영역
: 보조기억장치의 일부 영역

스왑 아웃
: 스왑 영역으로 옮겨지는 것

스왑 인
: 스왑 영역에서 메모리로 옮겨오는 것

 

2-2. 연속 메모리 할당

메모리 내에 프로세스들이 연속적으로 배치되는 상황을 가정해보자. 

 

프로세스 A                  프로세스 A

프로세스 B       →             X

프로세스 C                 프로세스 C

 

프로세스 A,B,C 순으로 메모리가 할당된 후 프로세스 B가 종료된 경우 빈 공간이 생긴다. 만약 새로운 프로세스의 크기가 프로세스 B보다 큰 경우 프로세스 C 다음의 공간으로 할당해야 하는 상황이 발생한다.

이를 외부 단편화(external fragmentation)라고 하며, 곧 메모리 낭비로 이어진다.

 

---

 

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

3-1. 가상메모리

가상 메모리
: 실행하고자 하는 프로그램의 일부만 메모리에 적재해, 실제 메모리보다 더 큰 프로세스를 실행할 수 있도록 만드는 메모리 기법. 보조기억장치의 일부를 메모리처럼 사용하기도 한다. 

가상 주소 공간
: 가상 메모리 기법으로 생성된 논리 주소 공간

대표적인 가상 메모리 관리 기법에는 페이징과 세그멘테이션이 존재한다.

 

3-2. 페이징

페이징
: 프로세스의 논리 주소 공간을 페이지라는 일정한 단위로 나누고, 물리 주소 공간을 페이지와 동일한 크기의 프레임이라는 일정한 단위로 나눈 뒤 페이지를 프레임에 할당하는 가상 메모리 관리 기법  
페이지는 물리 메모리 내에 불연속적으로 배치될 수 있다.

페이지 아웃
: 페이징 시스템에서의 스왑 아웃

페이지 인
: 페이징 시스템에서의 스왑 인

페이지 테이블
: 프로세스의 페이지와 실제로 적재된 프레임을 짝지어주는 정보.
페이지 번호와 프레임 번호가 대응되어 있다.

페이지 엔트리
: 페이지 테이블을 구성하고 있는 각각의 행을 의미.
페이지 번호, 프레임 번호, 유효 비트, 보호 비트, 참조 비트, 수정 비트 등이 있다.

내부 단편화(Internal Fragmentation)
: 페이지 하나의 크기보다 작은 크기로 발생하는 메모리 낭비


페이지 테이블 베이스 레지스터 (PRBR)
: 특정 프로세스의 페이지 테이블이 적재된 메모리 상의 위치를 가리키는 레지스터이다.
프로세스마다 가지는 정보이므로 각 PCB에 기록되며, 다른 프로세스로의 문맥 교환이 발생할 때 변경된다.

페이지 엔트리 정보

유효 비트
: 해당 페이지에 접근이 가능한지 여부
페이지가 메모리에 적재되어 있다면 1, 보조기억장치에 적재되어있다면 0 이다.
유효 비트가 0인 페이지에 접근하는 경우 페이지 폴트 예외가 발생하고, 해당 페이지를 메모리로 가져온 후 유효 비트를 1로 변경하는 과정이 이루어진다.

보호 비트
: 페이지 보호 기능을 위해 존재하는 비트
rwx의 조합으로 페이지에 접근할 권한을 제한한다. 111로 설정된 페이지는 읽기, 쓰기, 실행이 모두 가능하다.

참조 비트
: CPU가 해당 페이지에 접근한 적이 있는지의 여부
CPU가 읽거나 쓴 페이지는 1, 읽거나 쓴 적이 없는 페이지는 0으로 유지된다.

수정 비트(더티 비트)
: 해당 페이지에 데이터를 쓴 적이 있는지의 여부
변경된 적이 있다면 1, 변경된 적이 없는 즉 읽기만 했던 페이지의 경우 0으로 유지된다.
페이지를 메모리에서 삭제해야 할 때 수정 비트가 1일 경우 보조기억장치에 대한 쓰기 작업이 필요하지만, 0일 경우 페이지를 메모리에서 삭제하기만 해도 된다.

 

모든 프로세스의 페이지 테이블을 메모리에 두는 것은 메모리 접근 횟수가 많아지고, 메모리 용량을 많이 차지하기 때문에 비효율적이다.

 

메모리 접근 횟수의 관점에서 보면, 모든 프로세스의 페이지 테이블이 메모리에 적재되어 있을 경우 CPU는 페이지 테이블에 접근하기 위해 한 번, 실제 프레임에 접근하기 위해 한 번, 이렇게 총 두 번 메모리에 접근해야 한다. 이를 해결하기 위해 TLB(Translation Look-aside Buffer)라는 페이지 테이블의 캐시 메모리가 사용된다. TLB는 MMU내에 위치하며 참조 지역성의 원리에 근거해 자주 사용할 법한 페이지 위주로 페이지 테이블의 일부 내용을 저장한다.

CPU가 접근하려는 논리 주소의 페이지 번호가 TLB에 있을 경우, TLB는 CPU에게 해당 페이지 번호가 적재된 프레임 번호를 알려주고, 이를 TLB 히트라고 한다. 이 경우 메모리에 한 번만 접근하면 된다.

반대로 페이지 번호가 TLB에 없는 경우 페이지가 적재된 프레임의 번호를 알기 위해 메모리 내의 페이지 테이블에 접근을 해야 하고, 이를 TLB 미스라고 한다. 

TLB

 

 

메모리 용량의 관점에서 보면, 프로세스의 크기가 커지면 페이지 테이블의 크기도 커지기 때문에 프로세스를 이루는 모든 페이지 테이블 엔트리를 메모리에 두는 것은 메모리 낭비이다.

계층적 페이징(hierarchical paging / multilevel page table) 방식으로 페이지 테이블을 페이징하여 CPU와 가까이 위치한 바깥 쪽에 Outer 페이지 테이블을 둬서 메모리 공간을 절약할 수 있다.

계층적 페이징

 

페이징 주소 체계

하나의 페이지 내에는 여러 주소가 포함되어 있기 때문에 페이징 시스템의 논리 주소는 기본적으로 <페이지 번호, 변위>와 같은 형태로 이루어져 있다. 페이지 번호는 몇 번째 페이지 번호에 접근할지를 나타내고, 변위는 접근하려는 주소가 페이지(프레임) 시작 번지로부터 얼마나 떨어져 있는지를 나타낸다. 

<페이지 번호, 변위> 는 <프레임 번호, 변위>로 변환되는 셈이다.

페이징 주소 체계 예시

CPU가 논리 주소 <2,2>에 접근을 한다면 실제로 22번지 물리 주소에 접근을 하는 것이다.

 

페이지 교체 알고리즘

요구 페이징
: 메모리에 처음부터 모든 페이지를 적재하지 않고, 메모리에 필요한 페이지만을 적재하는 기법

1. CPU가 특정 페이지에 접근하는 명령어를 실행한다.
2-1. 해당 페이지의 유효 비트가 1일 경우 CPU는 페이지가 적재된 프레임에 접근한다.
2-2. 해당 페이지의 유효비트가 0일 경우 페이지 폴트가 발생한다.
2-2-1. 페이지 폴트 처리 루틴을 통해 해당 페이지를 메모리로 적재한 후, 유효 비트를 1로 설정한다.
2-2-2. 다시 1의 과정을 수행한다.

(유효 비트를 1로 설정한 후 프레임에 접근하는 과정이 이루어지는 것이 아님. CPU가 페이지에 접근하는 명령어를 다시 실행해야함)

순수 요구 페이징
: 아무런 페이지도 메모리에 적재되지 않은 채 프로세스를 실행하는 경우

 

요구 페이징을 통해 페이지들을 메모리에 적재하다 보면 메모리가 가득 찰 것이다. 추가적으로 메모리를 적재해야 하는 상황에서는 페이지 아웃을 해야 하며, 페이지 아웃을 할 페이지를 선택하는 방법을 페이지 교체 알고리즘이라고 한다. 

페이지 교체 알고리즘 종류

1. FIFO 페이지 교체 알고리즘
: 메모리에 가장 먼저 적재된 페이지부터 스왑 아웃하는 알고리즘
- 참조되고 있는 페이지를 스왑 아웃할 우려가 존재

2. 최적 페이지 교체 알고리즘 (Optimal)
: 사용 빈도가 낮을 것이라고 예상되는 페이지를 스왑 아웃하는 알고리즘
- 가장 낮은 페이지 폴트율을 보장하는 알고리즘
- 가장 적제 사용할 페이지를 예측하기 어렵기 때문에 구현이 어려운 알고리즘

3. LRU 페이지 교체 알고리즘 (Least Recently Used)
: 가장 적게 사용한 페이지를 스왑 아웃하는 알고리즘
- 보편적으로 사용하는 페이지 교체 알고리즘

4. MFU 페이지 교체 알고리즘 (Most Frequently Used)
: 가장 많이 사용한 페이지를 스왑 아웃하는 알고리즘
- 가장 많이 사용된 페이지가 앞으로 사용되지 않은 것이라 가정
 

스래싱(thrashing)
: 프로세스가 실행되는 시간보다 페이지 교체에 더 많은 시간을 소요하여 성능 저하가 발생하는 문제

 

페이지 폴트 종류

메이저 페이지 폴트(Major page fault)
: CPU가 접근하려는 페이지가 물리 메모리에 없을 때 발생하는 페이지 폴트
- 요청한 페이지가 페이지 아웃되어 보조기억장치의 가상 메모리에 저장되어 있는 경우
- Disk I/O를 발생

마이너 페이지 폴트(Minor page fault)
: CPU가 요청한 페이지가 물리 메모리에는 존재하지만, 페이지 테이블 상에는 반영되지 않은 경우에 발생하는 페이지 폴트
- 메이저 페이지 폴트에 비해 악영향이 적다.
- 어느 스레드가 특정 페이지를 사용하고 있을 때, 해당 프로세스의 다른 스레드가 동일한 페이지를 요청하는 경우 발생한다. MMU는 해당 스레드에서 용청한 페이지가 이미 사용 중인 페이지를 가리키도록 하면 해결할 수 있다.
- Disk I/O 발생하지 않음

 

---

 

4. 세그멘테이션

세그멘테이션
: 프로세스를 일정한 크기의 페이지 단위가 아닌 가변적인 크기의 세그먼트(segment) 단위로 분할하는 방식

세그먼트의 크기가 일정하지 않기 때문에 외부 단편화가 발생할 수 있다.

 

---

 

정리

CPU가 프로세스를 실행하는 과정을 정리해보자.

 

- 프로세스별 논리 주소 공간이 마련되어있고, 프로세스별 페이지 테이블을 가지고 있다. 때문에 논리 주소는 중복될 수 있지만 물리 주소는 고유하다.

 

1. CPU는 실행할 프로세스의 가상 주소를 MMU에게 변환을 요청한다

2. MMU는 변환 결과가 TLB에 존재하는지 확인한다.

2-1. TLB에 존재하는 경우 물리 주소 공간에 바로 접근한다.

2-2. TLB에 존재하지 않는 경우 PTBR을 사용하여 프로세스의 페이지 테이블 위치를 확인하고, MMU가 페이지 테이블을 검색한다.

3. 페이지 테이블에서 해당 가상 주소에 대응하는 물리 주소를 찾는다.

4. 찾은 물리 주소 공간에 접근한다.