저번에 설명했듯이 외부 단편화(External Fragmentation)로 인한 메모리 낭비가 사용 불가 수준으로 심하기 때문에 그에 대한 해결 방안으로 압축(Compaction)이 있지만 이로 인한 오버헤드와 비효율적이기 때문에 사용하기 어렵습니다.
그 뒤로 등장한 것이 바로 페이징(Paging)이라는 것입니다. 페이징이라는 것은 프로세스를 일정 크기로 나눠서 외부 단편화를 해결하려는 목적을 가지고 있습니다.
페이징은 프로세스의 논리 주소 공간을 페이지(Page)라는 일정한 단위로 자르고, 메모리 물리 주소 공간을 프레임(Frame)이라는 페이지와 동일한 크기의 일정한 단위로 자른 뒤 페이지를 프레임에 할당하는 기법입니다.
페이징을 사용하는 시스템에서는 프로세스 전체가 Swap Out/In 되는 것이 아닌 페이지 단위로 Swap Out/In됩니다.
즉, 메모리에 적재될 필요가 없는 페이지들은 보조기억장치로 Swap Out되고, 실행에 필요한 페이지들은 메모리로 Swap In됩니다.
그래서 페이징 시스템에서는 Swap Out은 페이지 아웃(Page Out), Swap In은 페이지 인(Page In)이라고 부릅니다.
프로세스를 이루는 페이지 중 실행에 필요한 일부 페이지만을 메모리에 적재하고, 당장 실행에 필요하지 않은 페이지들은 보조기억장치에 남겨둘 수 있기 때문에 물리 메모리보다 큰 프로세스를 실행할 수 있습니다.
페이지 테이블
여기서 고려해야 할 문제가 있습니다.
프로세스가 메모리에 불연속적으로 배치되어 있다면?
CPU 입장에서는 다음에 실행할 명령어 위치를 찾기가 어렵습니다.
그래서 물리 주소에 불연속적으로 배치되더라도 페이징 시스템은 CPU가 바라보는 주소인 논리 주소에는 연속적으로 배치되도록 페이지 테이블(Page Table)을 이용합니다.
페이지 테이블은 CPU로 하여금 페이지 번호만 보고 해당 페이지가 적재된 프레임을 찾을 수 있게 합니다. 즉, 페이지 테이블은 현재 어떤 페이지가 어떤 프레임에 할당되었는지를 알려줍니다.
프로세스들이 메모리에 분산되어 저장되어 있더라도 CPU 입장에서는 논리 주소가 연속적으로 배치되어 있기 때문에 CPU는 논리 주소를 순차적으로 실행하면 됩니다.
페이징은 외부 단편화 문제를 해결할 수 있지만 내부 단편화(Internal Fragmentation)라는 문제를 일으킬 수 있습니다.
🔎 내부 단편화(Internal Fragmentation)?
모든 프로세스가 페이지 크기에 딱 맞게 분할되는 것이 아니기 때문에 작업에 필요한 메모리 공간보다 많은 공간을 할당받음으로써 발생하는 내부의 사용 불가능한 공간이 발생할 수 있습니다. 그렇다고 하나의 페이지 크기를 너무 작게 설정하면 그만큼 페이지 테이블의 크기도 커지기 때문에 페이지 테이블이 차지하는 공간이 낭비됩니다.
프로세스마다 각자 테이블들을 가지고 있고, 각 페이지 테이블들은 메모리에 적재되어 있습니다. 그리고 CPU 내의 페이지 테이블 베이스 레지스터(Page Table Base Register)는 각 프로세스의 페이지 테이블이 적재된 주소를 가리키고 있습니다.
하지만 페이지 테이블을 메모리에 두게 되면, 메모리에 있는 페이지 테이블을 보기 위해 한 번, 프레임에 접근하기 위해 한 번, 이렇게 총 두 번의 메모리 접근이 필요하기 때문에 문제가 있습니다.
이를 해결하기 위해 CPU 곁에(MMU 내에) TLB(Translation Lookaside Buffer)라는 페이지 테이블의 캐시 메모리를 둡니다.
페이지 테이블의 캐시이기 때문에 페이지 테이블의 일부 내용을 저장합니다. 참조 지역성에 근거해 주로 최근에 사용된 페이지 위주로 가져와 저장합니다.
캐시 히트/미스와 마찬가지로, CPU가 발생한 논리 주소에 대한 페이지 번호가 TLB에 있을 경우 TLB 히트라고 하며, TLB에 없을 경우 TLB 미스라고 합니다.
페이징에서의 주소 변환
페이징 기법을 사용하기 위해서는 여러 개로 흩어진 페이지에 CPU가 접근하기 위해서 페이지 테이블을 통해서 주소를 변환해야 합니다.
페이징 시스템에서는 모든 논리 주소가 기본적으로 페이지 번호(Page Number)와 변위(Offset)로 이루어져 있습니다.
페이지 번호는 접근하고자 하는 페이지 번호입니다. 페이지 테이블 인덱스 값이라고 볼 수 있습니다.
변위는 접근하려는 주소가 프레임의 시작 번지로부터 얼만큼 떨어져 있는지를 알기 위한 정보입니다.
즉, 논리 주소(페이지 번호, 변위)는 페이지 테이블을 통해 물리 주소(프레임 번호, 변위)로 변환됩니다.
아래의 예제를 통해 확인해 보겠습니다.
- Page size = 4 bytes
- Page Table: 5 6 1 2
- 논리주소 13 번지는 물리주소 몇 번지?
문제에서 요구한 대로 CPU가 13번지에 접근하려고 합니다.
여기서 페이지 테이블의 정보를 읽기 위해 논리 주소를 페이지 번호(p)와 변위(d)로 나눠야 합니다.
변위는 페이지 크기에 따라 다릅니다. 현재 문제에서 페이지 크기는 4 byte입니다. 이는 2^2이므로 d=2 입니다. 그러면 페이지 번호는 변위를 제외한 크기가 됩니다. 이제 페이지 번호와 변위를 계산해 보겠습니다.
논리 주소는 13이며 2진수로 나타내면 1101입니다.
변위는 2이므로 2진수 뒤에서 2칸이 변위이고, 변위를 제외한 나머지 2칸은 페이지 번호입니다.
13 = 1101(2)
p = 11(2)
d = 01(2)페이지 번호의 값을 10진수로 나타내면 3이며, 페이지 테이블의 인덱스는 3이 됩니다. 페이지 번호 3에 해당하는 값은 위 예제에서 2가 됩니다. 그러면 물리주소를 구성하는 f의 값은 2가 됩니다.
f = 10(2)
d = 01(2)
물리주소 = 1001결과적으로 물리주소는 이진수로 1001이 됩니다. 10진수로 9번지가 됩니다.
페이지 테이블 엔트리
페이지 테이블의 각각의 행들을 페이지 테이블 엔트리(Page Table Entry)라고 합니다.
사실 페이지 테이블 엔트리에는 페이지 번호, 프레임 번호외에도 유효 비트, 보호 비트, 참조 비트, 수정 비트 정보들이 존재합니다.
⚡ 유효 비트
현재 페이지가 메모리에 적재되어 있는지 아니면 보조기억장치에 있는지를 알려주는 비트로 현재 해당 페이지에 접근 가능한지 여부를 알려줍니다.
즉, 페이지가 메모리에 적재되어 있다면 유효 비트가 1, 아니면 0이 됩니다.
만약, 유효 비트가 0인 메모리에 적재되어 있지 않은 페이지로 접근하려고 하면 페이지 폴트(Page Fault)라는 예외가 발생합니다.
⚡ 보호 비트
페이지 보호 기능을 위해 존재하는 비트입니다.
0일 경우, 읽기만 가능한 페이지임을 나타내고, 1일 경우 읽고 쓰기가 모두 가능한 페이지임을 나타내는 것입니다.
읽기 전용 페이지에 쓰기를 시도하면 운영체제가 이를 막아줍니다.
이 보호 비트를 3개의 비트로 복잡하게 구현할 수 있습니다.
rwx로 각각 읽기(Read), 쓰기(Write), 실행(eXecute)을 나타냅니다.
예를 들어, 보호 비트가 111로 설정된 페이지는 읽기, 쓰기, 실행이 모두 가능합니다.
⚡ 참조 비트
CPU가 이 페이지에 접근한 적이 있는지 여부를 나타냅니다.
CPU가 읽거나 쓴 페이지는 비트가 1이며, 적재 이후 한 번도 읽거나 쓴적이 없는 페이지는 0으로 유지됩니다.
⚡ 수정 비트
해당 페이지에 데이터를 쓴 적이 있는지 없는지 수정 여부를 알려줍니다.
더티 비트(Dirty Bit)라고도 부릅니다.
이 비트가 1이면 변경된 적이 있는 페이지, 0이면 변경된 적이 없는 페이지임을 나타냅니다.
이 수정 비트가 존재하는 이유는 페이지가 메모리에서 사라질 때 보조기억장치에 쓰기 작업을 해야 하는지, 할 필요가 없는지를 판단하기 위해 존재합니다.
한 번도 수정된 적이 없는 페이지가 보조기억장치로 Out될 때, 아무런 추가 작업 없이 새로 적재된 페이지로 덮어쓰기만 하면 되지만, 수정 비트가 1이면 보조기억장치에 저장된 페이지의 내용과 메모리에 저장된 페이지의 내용이 서로 다른 값을 갖게 됩니다. 그러면 변경된 값을 보조기억장치에 기록하는 작업이 추가되어야 하기 때문에 수정 비트를 두는 것입니다.
이상으로 페이징에 대해서 간단히 알아봤습니다.
참고
- KOCW - 운영체제, 양희재 교수님
- 혼자 공부하는 컴퓨터구조 + 운영체제
