[CS] 페이징 기법

Sundae·2023년 11월 27일

운영체제

목록 보기

13/15

페이징 기법

연속 메모리 할당 방식을 사용하면 외부 단편화라는 문제점이 발생한다.

하지만 이를 해결하는 방법이 있는데 바로 가상 메모리(virtual memory) 기술을 사용하는 것이다.
가상 메모리는 실행하기 위한 프로그램을 일부만 메모리에 적재하여 실행할 수 있게하며, 가상 메모리 관리 기법에는 페이징과 세그멘테이션이 있다. 현대 대부분의 운영체제는 페이징 기법을 사용한다.

연속 메모리 할당 방식에서 외부 단편화가 생긴 이유는 각기 다른 크기의 프로세스가 연속적으로 할당되었기 때문에 결국에는 아래의 이미지처럼 외부 단편화가 발생한다.

그렇다면 만약 크기가 제각각인 프로세스를 일정한 단위로 자르고, 메모리에 불연속적으로 할당할 수 있으면 어떨까?

아래의 이미지와같이 프로세스들을 10MB 단위의 일정한 크기로 자르고 불연속적으로 적재할 수 있다면 외부 단편화는 발생하지 않을 것이다.

이를 페이징(paging)이라고한다.

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

페이징에서의 스와핑

메모리를 효율적으로 사용하기 위해선 스와핑을 적절히 사용하여야한다. 페이징을 사용할 때도 스와핑이 가능한데, 이때는 프로세스 전체가 스왑 되는 것이 아닌 페이지 단위로 스왑 아웃/인 된다. 이를 각각 페이지 아웃(page out), 페이지 인(page in)라고 부른다.

이는 프로세스를 실행하기 위해서 프로세스 전체가 메모리에 적재될 필요가 없다는 말과 똑같다. 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 필요하지 않은 페이지들은 보조기억장치에 둘 수 있다. 이와 같은 페이징 방식을 통해 물리 메모리보다 더 큰 프로세스를 실행할 수 있다.

페이지 테이블

페이징을 사용하여 외부 단편화 문제 해결과 물리 메모리 크기보다 더 큰 프로세스를 실행할 수 있는 방안이 생겼다. 그런데, 중요한 문제가 한 가지 남아있다.

프로세스를 이루는 페이지가 어느 프레임에 적재되어 있는지 CPU가 알 수 없다. 프로세스가 메모리에 불연속적으로 배치되면 CPU 입장에서는 명령어가 실행될 때 다음, 또 그 다음 프레임에 접근하기가 어려워진다.

그래서 이를 해결하기 위해 페이지 테이블을 사용한다. 페이지 테이블에선 물리 주소에 프레임이 불연속적으로 배치되더라도 논리 주소에는 연속적으로 배치한다. 그리고 페이지 테이블은 배치한 페이지 번호와 프레임 번호를 짝지어 준다.

글로만 보면 알 수 없으니 이미지로 이해해보자.

프로세스마다 각자의 프로세스 테이블이 있다. 아래 이미지의 페이지 테이블은 프로세스 A의 페이지 테이블이다.

CPU는 테이블을 보고 0번 페이지는 3번 프레임에, 1번 페이지는 5번 프레임에 할당되어있다는 것을 알 수 있다. 결론적으로, CPU는 물리 주소상에서 분산되어 저장되어 있는 프로세스를 연속적으로 배치되어있는 논리 주소를 통해 쉽게 접근할 수 있다.

내부 단편화

페이징은 외부 단편화 문제를 해결하지만, 내부 단편화(internal fragmentation)라는 문제를 야기할 수 있다.

페이징은 프로세스의 논리 주소 공간을 일정한 크기로 자른다고 했다. 하지만, 모든 프로세스의 크기가 페이지의 배수는 아니다. 딱 맞게 잘리지 않는다는 뜻이다. 만약 페이지 크기를 10KB로 설정했는데, 프로세스의 크기가 108KB라면 어떨까? 이 경우에 마지막 페이지는 2KB만큼의 크기가 남는다. 이를 내부 단편화라고 한다.

그렇다면, 페이지 크기를 매우 작게 설정하면 되지 않을까? 하나의 페이지의 크기를 줄인다면 그만큼 내부 단편화의 크기는 작아지니 말이다. 하지만 이 방법은 문제가 될 수 있다. 하나의 페이지 크기를 작게 설정하면 페이지 테이블이 차지하는 공간이 비대해질 수 있기 때문이다.

그렇기에 내부 단편화를 방지하면서 너무 크지 않은 페이지 테이블이 만들어지도록 페이지 크기를 적당히 조정하는 것이 중요하다.

페이지 테이블 베이스 레지스터 - PTBR

프로세스마다 각자 프로세스 테이블을 갖고 있으며, 페이지 테이블들은 메모리에 적재되어 있다. 그리고 CPU 내의 페이지 테이블 베이스 레지스터(PTBR; Page Table Base Register)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있다.

프로세스 A가 실행될 때 PTBR은 프로세스 A의 페이지 테이블을 가리키며 프로세스 B가 실행될 때도 마찬가지로 PTBR은 프로세스 B의 페이지 테이블을 가리킨다. 그리고 접근한 페이지 테이블을 통해 페이지가 적재된 프레임을 알 수 있다. 이러한 프로세스들의 페이지 테이블 정보들은 각 프로세스의 PCB에 기록되며, 문맥 교환이 일어날 때 다른 레지스터와 마찬가지로 함께 변경된다.

접근 단계가 늘어나는 문제 해결 - TLB

위와 같은 식으로 페이지 테이블을 메모리에 적재해두면 문제가 하나 있다. 메모리 접근 단계가 한 단계가 더 늘어난다는 점이다. 테이블에 접근하기 위한 단계 한 번, 프레임에 접근하기 위한 단계 한 번, 총 두 번의 메모리 접근이 필요하다.

이와 같은 문제를 해결하기 위해 CPU 곁에 TLB(Translation Lookaside Buffer)라는 캐시 메모리를 둔다. 우리가 사용하는 컴퓨터의 CPU 옆에는 TLB가 있으며, TLB는 페이지 테이블의 캐시이기 때문에 테이블의 일부 내용을 저장한다. 그리고 주로 최근에 사용된 페이지 위주로 가져와 저장한다.

CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 TLB 히트(TLB hit)라고 한다. 이 경우에는 메모리 접근에 걸리는 단계 수는 한 단계이다. 하지만, 반대로 페이지 번호가 TLB에 없을 경우 어쩔 수 없이 두 단계가 걸린다. 이를 TLB 미스(TLB miss)라고 한다.

페이징의 주소 변환

하나의 페이지 또는 프레임은 여러 주소를 포함하고 있다. 만약 특정 주소에 접근하려면 아래와 같은 두 가지 정보가 필요하다.

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

페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호와 변위(offset)로 이루어져 있다. 만약 CPU가 32비트 주소를 내보냈다면 이 중 N비트는 페이지 번호이며 (32-N)비트는 변위이다.

페이지 번호는 말 그대로 페이지 번호이며, 변위는 접근하려는 주소의 프레임 시작 위치로부터 얼만큼 떨어져 있는지 알기 위한 정보이다.
다시말해, 논리 주소<페이지 번호, 변위>는 물리 주소 <프레임 번호, 변위>로 변환된다.

예시로 다시 이해해보자.

위 이미지에서 만약 CPU가 5번 페이지, 변위 2라는 논리 주소 <5, 2>에 접근하고 싶다고 한다면 CPU가 접근하게 될 물리 주소는 어디일까?

페이지 테이블에서 5번 페이지는 현재 1번 프레임에 있으며 변위 2에 접근하게 된다. 변위는 접근하려는 주소의 프레임 시작 위치로부터 얼만큼 떨어져 있는지 알기 위한 정보라고 했다. 1번 프레임은 8번지부터 시작하므로 즉, CPU가 접근하게 될 물리 주소는 10번지이다.

페이지 테이블 엔트리

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

페이지 테이블 엔트리에는 페이지 번호, 프레임 번호 외에도 다른 중요한 정보들이 있다. 대표적으로 유효 비트, 보호 비트, 참조 비트, 수정 비트가 있다.

1. 유효 비트(valid bit)

유효 비트(valid bit)는 현재 해당 페이지에 접근 가능한지를 알려준다. 만약, 현재 페이지가 메모리에 적재되어 있다면 유효 비트가 1, 메모리에 적재되어있지 않고 보조기억장치에 있다면 유효 비트가 0이 된다.

만약 CPU가 유효 비트가 0인 페이지로 접근하려고 할 때 페이지 폴트(page fault)라는 예외가 발생한다.

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

2. 보호 비트(protection bit)

보호 비트(protection bit)는 페이지 보호를 위해 존재하는 비트이다. 보호 비트를 통해 해당 페이지가 읽고 쓰기가 가능한 페이지인지, 읽기만 가능한 페이지인지를 나타낼 수 있다. 보호 비트가 0일 경우 해당 페이지는 읽기만 가능한 페이지임을 나타내고, 1일 경우 읽고 쓰기가 모두 가능한 페이지임을 나타낸다. 만약 읽기 전용 페이지에 쓰기를 시도하면 운영체제가 이를 막아준다.

보호 비트는 위 이미지처럼 세 개의 비트로 좀 더 복잡하게 구현할 수 있다.

읽기(Read)인 r, 쓰기(Write)인 w, 실행(eXecute)를 나타내는 x. 이와 같은 조합으로 읽기, 쓰기, 실행하기 권한의 조합을 표현할 수 있다.
예를 들어, 보호 비트가 100으로 설정된 페이지일 경우 해당 페이지는 읽기만 가능하며, 보호 비트가 111로 설정된 페이지는 읽기, 쓰기, 실행이 모두 가능하다.

3. 참조 비트(reference bit)

참조 비트(reference bit)는 CPU가 해당 페이지에 접근한 적이 있는지 여부를 나타낸다. CPU가 읽거나 쓴 페이지는 참조 비트가 1로 설정되고, 적재 이후 한 번도 읽거나 쓴 적이 없다면 0으로 유지된다.

4. 수정 비트(modified bit)

수정 비트(modified bit)는 해당 페이지에 데이터를 쓴 적이 있는지 수정 여부를 알려준다. 더티 비트(dirty bit)라고도 부른다. 이 비트가 1이면 변경된 적이 있는 페이지이며, 0이라면 변경된 적이 없는 페이지임을 나타낸다. (접근한 적 없거나 읽기만 했던 페이지)

수정 비트는 왜 있는걸까? 언뜻 봤을 때 참조 비트와 수정 비트는 크게 하는 역할이 달라보이지 않는다.

수정 비트는 페이지가 메모리에서 사라지는 시점에 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지 판단하기 위해 존재한다.

보조기억장치에는 메모리에 적재되어 있는 해당 페이지의 내용을 그대로 갖고 있다.

만약, CPU가 페이지에 쓰기 작업(수정)을 한 후, 페이지를 스왑 아웃한다고 가정해보자. 메모리에 적재되어 있던 페이지와 보조기억장치의 페이지는 같은 내용(값)을 갖고있을까? 메모리에 적재되어있던 페이지는 CPU가 쓰기 작업을 했기 때문에 보조기억장치에 저장되어있는 페이지와는 다른 내용을 갖고 있을 것이다.

결론은, 만약 CPU가 스왑 아웃 되는 페이지에 대해서 쓰기 작업을 하지 않았을 경우, 아무런 추가 작업 없이 보조기억장치에 저장되어 있는 페이지에 덮어쓰기만 하면 된다. 하지만 쓰기 작업을 했던 페이지가 스왑 아웃 되는 경우엔 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야한다.

페이징의 이점 - 쓰기 시 복사(copy on write)

페이징이 제공하는 이점은 외부 단편화 문제를 해결한다는 점 외에도 다양하다.

대표적인 예시로 쓰기 시 복사(copy on write)가 있다.

프로세스를 fork하여 동일한 프로세스 두 개가 복제되면 모든 자원이 복제되어 메모리에 적재된다.
이 말은, 위 이미지처럼 프로세스가 복제될 때 부모 프로세스의 메모리 영역이 그대로 자식 프로세스로서 다른 영역에 복제된다는 말과 같다. 이 복사 작업은 프로세스 생성 시간을 늦출 뿐만 아니라 불필요한 메모리 낭비를 야기한다.

반면 쓰기 시 복사는 자식 프로세스가 생성되면 우선 메모리 영역을 복제하는 것이 아닌 부모 프로세스와 동일한 프레임을 가리킨다. 그리고 나서, 부모 프로세스 혹은 자식 프로세스에 쓰기 작업이 발생하면 그 순간 해당 페이지가 별도의 공간으로 복제된다. 이를 쓰기 시 복사라고 한다. 쓰기 시 복사를 사용하면 프로세스 생성 시간을 줄이는 것은 물론 메모리 공간 절약도 가능하다.