[운영체제] 18. Paging

18장의 핵심 질문 : 페이지를 사용하여 어떻게 메모리를 가상화할 수 있을까?

 

🔹 흐름 정리

우리는 메모리 공간 관리를 위해 세그멘테이션 기법을 도입하였다. 세그멘테이션에서는 세그멘트 단위(예, 코드, 힙, 스택)로 주소 공간을 나눴기 때문에 다양한 크기의 덩어리로 구분해주어야 했는데, 이로 인해 외부 단편화(external fragmentation)문제가 발생했다. 외부 단편화 문제는 공간이 할당되는 것을 점점 더 어렵게 했다. 그래서 나온 새로운 방식이 페이징(paging)이다. 우리는 이번 글에서 페이징 기법에 대해 알아볼 것이다.

---

🔹 페이징(paging)이란?

세그멘테이션에서 발생한 외부 단편화의 근본적인 원인은 공간을 다양한 크기의 덩어리로 분할한다는 것에 있다. 그래서 페이징은 공간을 동일한 크기의 조각으로 분할한다. 이러한 동일한 크기의 단위를 페이지(page)라고 한다. 물리 메모리에서는 가상 메모리의 페이지에 상응하는 페이지 프레임(page frame)을 가진다. 하나의 페이지 프레임은 하나의 페이지와 짝지어진다. 

그러면 페이징 기법으로 어떻게 주소 변환을 하는건지 예를 들어 살펴보자.
가상 주소 공간은 총 64 바이트이고, 4개의 16 바이트짜리 페이지로 이루어져있다고 가정하자. 64는 $2^{6}$이므로 가상 주소를 표현하기 위해서는 6비트가 필요하다.
물리 메모리는 128 바이트라고 가정하자. 128은 $2^{7}$이므로 가상 주소로 표현하려면 7비트가 필요하다.

movl 21, %eax

가상 주소 21번지에 해당하는 데이터를 eax 레지스터에 탑재하고자 한다. 21을 2진수로 변환하면 010101 이다. 이 가상주소를 페이지 번호(Virtual Page Number, VPN)와 오프셋으로 나눈다. 가상 주소공간의 페이지는 4개이므로 페이지번호로는 2비트를 사용하고 나머지 4비트를 오프셋 비트로 사용한다. 오프셋은 페이지 내에서 우리가 원하는 바이트의 위치를 나타낸다.
그래서 21, 즉 010101 은 가상페이지 01의 0101번째 바이트라는 것을 의미한다.

가상 주소에 대해 알았으니 이제 물리 주소로 변환해보자. 가상 페이지 번호 VPN를 페이지 테이블의 인덱스로 사용하여 가상 페이지 01이 이 어느 물리 프레임에 저장되어 있는지 찾을 수 있다. 여기서는 물리 프레임 번호(Physical Frame Number, PFN) 7번으로 가정하자. 따라서 가상 페이지 번호(VPN) 01은 물리 프레임 번호(PFN) 111(7)로 변환된다. 오프셋은 동일하기 때문에 변환할 필요가 없다. 오프셋이 동일한 이유는 가상 주소의 페이지와 물리 주소의 페이지 프레임은 상응되기 때문이다.
따라서 따라서 가상 주소 010101(십진수 21)는 물리주소 1110101(십진수 117)로 변환된다. 아래 그림은 이 과정들을 시각화해서 보여주고 있다.

주소 변환 과정을 큰 그림으로 살펴보았는데, 주소 변환 과정에서 참조한 페이지 테이블에 대해서는 설명하지 않았다. 이에 대해 알아보자. 

---

🔹 페이지 테이블

▶ 페이지 테이블은 어디에 있는가?

세그멘테이션 기법을 사용할 때 필요했던 세그멘트 테이블이나 베이스-바운드 쌍에 비해 페이지 테이블은 매우 커질 수 있다. 앞서 보았던 128비트의 물리 메모리야 3비트로 페이지를 표현할 수 있었지만, 이는 설명을 위해 사용한 아주 작은 메모리이기 때문에 비현실적이다. 4KB 크기의 페이지를 가지는 32비트 주소 공간이라고 해보자. 4KB짜리 페이지를 위해서는 12비트가 필요하므로(4KB =$2^{2} * 10^{3} \doteq 2^{2} * 2^{10} = 2^{12}$) 오프셋으로 12비트를 사용한다. 남은 20비트로 VPN을 표현할 것이다. 20비트로 VPN을 표현한다는 것은 $2^{20}$ 약 100만 개의 페이지 수가 있다는 것을 의미한다. 페이지마다 페이지 테이블 항목(page table entry, PTE) 4바이트를 사용한다고 하면, 페이지 테이블의 크기는 총 4MB이다. ($2^{2} * 2^{20}$ = 4MB) 얼마 안되는 것 같아 보일 수도 있지만 4MB는 하나의 프로세스를 위한 페이지 테이블을 위한 공간이다. 프로세스 100개가 실행 중이라면 운영체제는 주소 변환을 위해 연속된 400MB의 메모리가 필요하다. 이러면 메모리 가상화의 목표 중 하나인 효율성(Efficiency)에 어긋난다.

그래서 현재 실행 중인 프로세스의 페이지 테이블을 저장할 수 있는 회로는 MMU 안에 두지 않는다. 대신 각 프로세스의 페이지 테이블을 운영체제를 위한 물리 메모리 페이지에 저장한다.

---

▶ 페이지 테이블에는 뭐가 있는가?

페이지 테이블 항목(Page Table Entry, PTE)에 있는 비트들에 대해 몇 가지 알아보자.

• Valid bit
  - 주소 공간에서 할당되지 않아 미사용되고 있는 페이지를 표현
  - 미사용 중인 페이지들에게 물리 프레임을 할당할 필요를 없앰 -> 대량의 메모리를 절약
• protection bit
  - 페이지가 읽을 수 있는지, 쓸 수 있는지, 또는 실행될 수 있는지를 표시
  - protection bit가 허용하지 않는 방식으로 페이지에 접근하려고 하면 운영체제에 트랩을 생성
• Present bit
  - 이 페이지가 물리 메모리에 있는지, 혹은 디스크에 있는지 가리킴
  (나중에 더 자세히 배움)
• dirty bit
  - 메모리에 반입된 후 페이지가 변경되었는지 여부를 나타냄
• reference bit(accessed bit)
  - 때때로 페이지가 접근되었는지를 추적하기 위해 사용
  (나중에 더 자세히 배움)

---

🔹 페이징(paging)이 어떻게 기존 문제들을 해결?

페이징은 이전 방식에 비해 많은 장점을 가지고 있다. 유연성 과 단순함 이다.
먼저 페이징은 고정된 단위의 페이지를 사용하기 때문에 프로세스의 주소 공간 사용 방식과는 상관없이 효율적으로 주소 공간 개념을 지원할 수 있다. 예를 들면 힙과 스택이 어느 방향으로 커지는지, 어떻게 사용되는지에 대한 고려를 해주지 않아도 된다는 것이다.
또한 페이징은 빈

 

🔹 페이징의 문제점 : 너무 느림!

페이지 테이블의 크기가 메모리 상에서 매우 크게 증가하면 이로 인해 처리 속도가 저하될 수 있다. 

 

🔹 메모리 트레이스

페이징을 통해 발생하는 메모리 접근에 대해 알아보자.

프로그램이 실행되면, 각 명령어의 반입 시에 메모리가 두 번 참조된다. (명령어의 위치를 파악하기 위해 페이지 테이블 접근 한 번, 페이지 테이블의 정보를 가지고 해당 페이지로 가서 명령어 자체에 한 번) 게다가 mov 명령어는 메모리 참조를 한 번 하기 때문에 이를 위해 페이지 테이블 접근 한 번(배열의 가상 주소 -> 물리 주소 변환), 배열 자체 접근하기 위한 메모리 참조까지 총 4번의 메모리 접근이 발생한다.

위 코드로 예를 들어보자. 위 코드를 어셈블리 코드로 바꾸면 아래와 같다.

위 코드의 1번 라인을 수행한다고 해보자. 먼저 가상 주소 0x1024가 어느 페이지에 위치했는지를 알기 위해 페이지 테이블에 접근한다. 페이지 정보를 가지고 해당 페이지로 가서 명령어를 읽는다. 그런데 movl 명령어이다. %edi 레지스터가 담고 있는 배열의 주소를 알기 위해서는 페이지 테이블에 또 접근해야 하고, 배열이 위치한 페이지를 알았다면 이제 배열 자체에 접근하기 위해 다시 메모리를 접근해야 한다. 이렇게 총 4번의 메모리 접근이 이루어진다.

메모리를 참조하는 과정들을 아래와 같이 시각화 할 수 있다.

딱 봐도 메모리 접근이 너무 많다. 이렇게 되면 컴퓨터가 매우 느려질 수 있는 문제점이 발생한다. 다음 글에서는 이런 문제점들을 모두 해결해 현실적으로 페이징 기법을 사용할 수 있게 도와주는 하드웨어, TLB에 대해 알아볼 것이다.