가상 메모리와 페이징

운영체제의 가장 핵심적인 역할은 프로세스 관리와 메모리 관리이다.

OS는 가상 메모리를 활용해서 메모리 관리를 어떻게 할까?

스와핑

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

 

가상 메모리는 모든 데이터를 주 기억장치에 올리지 않고 필요한 부분만 올린다. 그리고 남은 것들은 보조기억장치에 존재하게 되며 필요할 때마다 보조기억장치에서 주기억장치로 옮겨서 사용한다.

 

예를 들어 입출력 작업의 요구로 대기 상태가 된 프로세스, 오랫동안 사용하지 않은 프로세스는 임시로 보조기억장치 일부 영역으로 옮겨진다. 이렇게 되면 주기억장치에 빈 공간이 생기고 이 공간에 새로운 프로세스를 담아 실행할 수 있다. 이런 방식을 스와핑이라고 한다.

실행할 프로세스가 메모리로 이동하는 것을 스왑 인이라고 하고, 사용되지 않는 프로세스가 스왑 영역으로 들어오는 것을 스왑 아웃이라고 한다.

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

 

swapping

 

메모리 할당

그렇다면 메모리의 빈 공간에 프로세스를 어떻게 연속적으로 할당할 수 있을까?

여기에는 최초 적합, 최적 적합, 최악 적합이라는 세 가지 방식이 있다.

 

위의 그림과 같이 메모리에 프로세스가 적재되어있고 적재할 프로세스를 빈 공간에 적재하려고 한다.

용어 그대로 직관적인 접근을 하면 된다.

최초 적합은 제일 먼저 발견한 빈 공간에 프로세스를 적재하는 것이다. 따라서 빈공간 A에 적재한다.

최적 적합은 프로세스가 적재될 수 있는 공간 중에 가장 작은 공간에 적재하는 것이다. 따라서 빈공간 C에 적재한다.

최악 적합은 반대로 가장 큰 공간에 적재하는 것이다. 따라서 빈공간 B에 적재한다.

 

하지만 위의 방법들은 외부 단편화라는 문제를 야기할 수 있다.

외부 단편화를 예시로 살펴보자.

 

그림처럼 사용자 영역에 프로세스를 적재하고 P2, P4가 종료되어 빈 공간이 생겼다.

모든 빈공간을 합치면 50MB 만큼의 크기가 남지만 50MB의 프로세스를 적재할 수는 없다.

이처럼 프로세스를 할당하기 어려울만큼 작은 메모리 공간들로 인해 메모리가 낭비되는 현상을 외부 단편화라고 한다.

 

메모리에 프로세스가 몇 개 없을 때는 외부 단편화가 큰 문제가 되는지 의심이 될 수 있다. 하지만 메모리의 용량도 커지고 적재되는 프로세스가 많아지면 외부 단편화로 인한 메모리 낭비는 커지게 되므로 반드시 해결해야하는 문제이다.

압축을 통해서 흩어져있는 빈 공간을 하나의 큰 공간으로 만들 수 있다. 하지만 압축을 하는 동안 시스템이 중지되야하고, 메모리에 있는 내용을 옮기면서 많은 오버헤드가 야기될 수 있다. 따라서 다른 해결방안이 등장했는데 바로 페이징 기법이다. 

---

페이징

물리 메모리의 크기보다 큰 프로세스는 실행할 수 없기 때문에 일부 프로세스만 메모리에 적재하여 물리 메모리보다 큰 프로세스를 실행할 수 있는 기술이 가상 메모리라고 했다. 그 과정에서는 위에서 설명한 스와핑 기법이 들어가게 된다.

하지만 외부 단편화라는 문제점이 있었다. 이를 해결하고자 가상 메모리 관리 기법에 페이징이라는 기술이 제시되었다.

 

먼저 외부 단편화가 왜 발생했는지 원인을 알아야한다.

외부 단편화가 생긴 이유는 각기 다른 크기의 프로세스가 메모리에 연속적으로 할당되었기 때문이다.

그렇다면 반대로 메모리와 프로세스를 일정한 크기로 자르고, 메모리에 불연속적으로 할당한다면 외부 단편화는 발생하지 않는다. 이것이 바로 페이징이다.

 

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

 

이 때, 물리 주소에 페이지가 불연속적으로 배치되어있는 것을 알 수 있다.

외부 단편화는 해결할 수 있지만 CPU 입장에서는 다음에 어떤 명령어를 실행해야할 지 골치가 아플 것이다.

그렇기 때문에 페이지 테이블을 이용해서 물리 주소에서는 불연속적으로 배치가 되어있어도 논리 주소에는 연속적으로 배치가 되도록 한다. 페이지 테이블은 페이지와 프레임 번호를 짝지어주는 역할이다. 따라서 CPU 입장에서는 페이지 테이블에 적혀있는 페이지 번호만 확인하면 실제 물리 주소의 몇 번 프레임에 적재되어있는지 순차적으로 파악할 수 있다.

 

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

그리고 CPU 내의 페이지 테이블 베이스 레지스터(PTBR)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다.

 

하지만 페이지 테이블을 메모리에 두면 메모리 접근 시간이 두 배로 늘어난다는 단점이 있다.

그렇기 때문에 페이지 테이블의 캐시 메모리인 TLB(Translation Lookaside Buffer)를 사용한다.

CPU가 논리 주소에 대한 페이지 번호가 TLB에 있다면 TLB hit이고 이 때는 직접 메모리에 접근할 필요가 없다.

하지만 TLB에 페이지 번호가 없다면 직접 메모리에 접근해야한다. 이것을 TLB miss라고 한다.

 

페이징 기법은 외부 단편화를 해결한다는 것 말고 프로세스 간에 페이지를 공유할 수 있다는 점에서 이점이 존재한다.
프로세스 간에 페이지를 공유하는 사례로는 copy on write가 있다.

왼쪽 그림처럼 읽기 작업만 수행하는 경우에는 부모 프로세스의 메모리 공간을 복사하지 않고도 동일한 코드 및 데이터 영역을 가리킬 수 있다. 
다르게 표현하면 포인터를 새로 만들어 부모 프로세스와 동일한 메모리 주소를 가리키게 하는 것이다.

오른쪽 그림처럼 부모 프로세스와 자식 프로세스 중 하나가 하나의 페이지에 쓰기 작업을 수행하면 해당 페이지가 별도의 공간으로 복제된다. 만약 자식 프로세스에서 쓰기 작업을 수행하면 부모 프로세스를 기반으로 쓰기 작업에 필요한 만큼의 메모리 영역을 복사한다. 부모 프로세스 전체 메모리 영역을 복사하는 것이 아니기에 자식 프로세스 생성에 있어 수행시간을 단축시킨다.

copy on write

 

---

페이징에서의 주소 변환

CPU가 프로세스 A의 페이지 2에서 10만큼 떨어진 주소에 접근하고 싶어한다.

단순하게 생각해보면 페이지 2에 해당하는 프레임을 페이지 테이블에서 찾고 그 물리주소에서 10만큼 떨어진 곳을 찾아주면 된다.

이 과정을 컴퓨터가 수행하려면 어떻게 해야할까?

 

페이징 시스템에서 모든 논리 주소는 페이지 번호와 변위로 이루어져있다.

그리고 논리 주소의 페이지 번호와 변위는 페이지 테이블을 통해 물리 주소의 프레임 번호와 변위로 변환된다.

여기서 주의할 점은 변위 값은 논리 주소나 물리 주소나 똑같다. 왜냐하면 페이지의 크기와 프레임의 크기는 같기 때문이다.

 

예를 들어 CPU가 논리주소 <5, 2>에 접근하고 싶어한다. CPU가 접근하게 될 물리 주소는 어디일까?

논리주소 <5, 2> 는 5번 페이지, 변위 2라는 의미이다. 따라서 5번 페이지에 해당하는 프레임을 페이지 테이블에서 찾고 시작 주소에서 2만큼 떨어진 곳이 CPU가 접근하게 될 물리 주소이다.

---

페이지 테이블 엔트리

지금까지 페이지 테이블에는 페이지 넘버와 프레임 넘버만을 설명했지만 이외에도 중요한 정보들이 들어있다.

 

유효 비트

유효 비트는 현재 해당 페이지에 접근 가능한지 여부를 알려준다. 페이지가 메모리에 적재되어 있다면 유효 비트가 1이고 페이지가 메모리에 적재되어 있지 않고 스왑 영역에 있다면 유효 비트가 0이 된다.

 

만약 CPU가 유효 비트가 0인 페이지에 접근하려고 하면 페이지 폴트라는 인터럽트가 발생한다.

페이지 폴트는 다음의 과정을 거쳐서 처리된다.

1. CPU는 기존의 작업 내역을 백업한다.
2. 페이지 폴트 처리 루틴을 실행한다.
3. 페이지 처리 루틴은 원하는 페이지를 메모리로 가져온 뒤 유효 비트를 1로 변경한다.
4. 페이지 폴트를 처리했다면 CPU는 이제 해당 페이지에 접근할 수 있다.

보호 비트

프로세스를 이루는 요소 중 코드 영역은 readonly이다. 즉, 읽기 전용 영역이다. 이러한 읽기 전용 영역을 보호하기 위해서 보호 비트가 사용된다. 보호 비트가 1이면 읽고 쓰기가 가능하고, 0이면 읽기만 가능한 페이지임을 나타낸다.

 

보호 비트를 조금 더 세부적으로 read, write, execute의 조합으로 표현하기도 한다.

예를 들어 보호 비트가 110이면 read가 1, write가 1, execute가 0이다. 즉, 읽고 쓰기는 가능하지만 실행은 불가능하다는 의미이다.

참조 비트

참조 비트는 CPU가 해당 페이지에 접근한 적이 있는지 여부를 나타낸다. CPU가 접근한 적이 있다면 1, 없다면 0이다.

수정 비트

더티 비트라고도 부르며 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이지이다.

 

왜 수정 비트가 필요할까?

왼쪽 그림과 같이 CPU가 페이지의 값을 변경하지 않은 경우 스왑 아웃될 때 보조기억장치에 저장된 값과 변함이 없기 때문에 그대로 덮어쓰면 된다. 하지만 오른쪽 그림처럼 CPU가 페이지의 값을 변경했다면 스왑 아웃될 때 보조기억장치에 저장된 값에 변경이 필요하다. 이 작업이 필요한지 불필요한지 판단하기 위해서 수정 비트가 필요하다.

계층적 페이징

계층적 페이지는 프로세스 하나당 하나의 페이지 테이블을 사용하던 것을 여러 개로 나누어 사용하는 방식이다.

모든 페이지 테이블 엔트리를 메모리에 적재하는 것은 큰 메모리 낭비이기 때문에 모든 페이지 테이블 엔트리를 항상 메모리에 유지하지 않을 수 있는 방법이다.

 

아래 그림에서는 2-level page table을 기준으로 한다.

논리 주소의 형태는 p1은 바깥 페이지 번호를 의미하고 p2는 안쪽 페이지 번호를 의미한다.

이러한 형태의 논리 주소를 바탕으로 물리 주소를 얻기 위해서는 p1을 통해 페이지 테이블의 페이지 즉, 안쪽 페이지를 찾고 안쪽 페이지를 통해 프레임 번호를 찾은 후 변위를 더해서 물리 주소를 얻을 수 있다.

 

하지만 계층이 늘어날수록 페이지 폴트가 발생했을 때 메모리 참조 횟수가 많아지므로 계층이 많다고 무조건 좋은 것은 아니다.

계층적 페이징