[OS] Operating System - 페이징과 스와핑

Paging

 

Paging, 페이징은 운영체제에서 메모리를 관리하는 기법이다. 운영체제는 메모리를 관리하기 위해 메모리를 같은 크기의 블록으로 나눠서 관리를 하는데 이때 나눠진 블록이 바로 페이지이다. 페이지를 사용하면 연속 메모리 할당의 두 가지 문제점을 해결할 수 있다. 외부 단편화 문제와 연관된 요소들의 압축 문제를 해결할 수 있다. 또한 운영체제와 하드웨어 간의 협력을 통해 성능을 향상할 수 있다.

---

페이징에 대한 기본적인 방법은 다음과 같다. 

• 물리 메모리의 분할 : 물리 메모리를 고정 크기의 블록으로 나눈다. 이때의 블록은 프레임(frame)이라고 한다
• 논리 메모리의 분할 : 프로세스의 논리 메모리고 같은 크기의 블록으로 나눈다. 해당 블록을 페이지(page)라고 한다

이를 통해 논리적 주소 공간은 물리적 주소 공간과 나눠지게 되는 방식이 페이징의 핵심이 된다. 이때 모든 주소는 CPU에 의해 생성이 되며 두 개의 부분으로 나눠서 생성이 된다. 

Page

• Page number (페이지 번호)
  • 논리 주소의 상위 비트를 차지하며, 페이지 테이블에서 해당 페이지가 메모리에 저장된 위치를 나타낸다
  • 페이지 테이블은 각 페이지가 어떤 프레임(물리 메모리 블록)에 저장되어 있는지를 매핑하는 정보를 저장한다
  • 페이지 번호는 2^n 형태로 표현되며, n은 페이지 크기(바이트)를 나타낸다. 
    • ex : 페이지의 크기 = 4kb = 4096 (바이트) = 2^12, 이때의 페이지 번호는 12
• Page offset (오프셋)
  • 논리 주소의 하위 비트를 차지하며, 페이지 내에서 특정 데이터의 위치를 나타낸다
  • 페이지 크기만큼의 메모리 공간을 0부터 시작하는 주소로 생각해보자. 이때의 오프셋은 각각 해당되는 주소를 의미한다
    • ex :  페이지 크기가 4kb이면 오프셋은 0에서 4095까지의 값을 가질 수 있다

 

페이지 테이블(page tabel)

 

그럼 페이지 테이블(page table)은 무엇일까? 페이지 테이블은 페이징 시스템에서 논리 주소를 물리 주소로 변환하는 데 사용되는 데이터 구조이다. 페이징 시스템은 메모리를 같은 블록(페이지)으로 나누고, 페이지 테이블은 각 페이지가 메모리에 저장된 위치를 기록한다. 페이지 테이블의 구성은 다음과 같다.

 

• 페이지 엔트리 : 페이지 테이블은 각 페이지마다 하나의 엔트리를 가지고 있다.  
  • 프레임 번호 : 페이지가 저장된 프레임 번호
  • 접근 권한 : 페이지에 대한 접근 권한(읽기, 쓰기, 실행)
  • 유효 비트 : 페이지가 유효한지 여부를 나타내는 비트
  • 변경 비트 : 페이지 내용이 변경되었는지 여부를 나타내는 비트

이러한 요소로 구성된 페이지 테이블은 운영체제에서 관리가 되며, 논리 주소 변환, 메모리 관리, 페이지 접근 보호의 기능을 가지고 있다.

 

논리 주소 변환은 다음과 같은 과정을 통해 이루어진다.

paging hardware

 

1. CPU에서 만들어진 논리 주소를 접근한다. 이때 논리 주소에 접근해서 상위 비트를 추출한다. 그리고 해당 페이지의 번호(p)를 얻는다
2. 페이지 테이블에서 프레임 번호 추출
   1. 페이지 번호를 페이지 테이블의 인덱스로 사용하여 해당 페이지가 저장된 프레임 번호(f)를 찾는다
   2. 페이지 테이블을 통해 페이지 번호(논리) -> 프레임 번호(물리)로 매핑할 수 있게 된다.
3. 페이지 테이블에서 획득한 프레임 번호를 통해 기존 논리 주소에서 상위 비트인 페이지 번호를 프레임 번호로 대체한다.
4. 오프셋 추가
   1. 논리 주소의 하위 비트는 페이지 내에서 데이터의 위치를 나타내는 오프셋이다
   2. 대체된 주소를 통해 최종 물리 주소를 계산하면 된다.

---

 이러한 페이지에 대해 페이지와 프레임 크기는 모두 하드웨어에 의해 정의된다. 하드웨어를 통해 정의가 되므로 CPU와 메모리 하드웨어 간의 호환성이 보장이 된다. 일반적으로 크기는 2의 n승으로 이루어지며, 시스템 아키텍처와 요구 사항에 따라 결정된다. 또한 2^n승의 방법은 주소 변환 계산을 간소화하여, 나눗셈 연산 대신에 비트 연산자를 통한 이동이 가능하게 한다. 그리고 페이지의 경계가 물리 메모리 블록 경계와 일관되게 사용할 수 있다.

 

페이지와 하드웨어

 

이러한 페이지에 관한 작업이 발생할 때 하드웨어에서는 이러한 페이지에 관련된 작업이 잘 이루어지도록 서포트를 한다.

 

1. 프로세스 전환 시 페이지 테이블 재로드
   1. CPU 스케줄러가 실행할 프로세스를 선택하면 시스템은 해당 프로세스의 페이지 테이블을 메모리에 다시 로드한다.
   2. 각각의 프로세스는 다른 논리 주소 공간을 사용한다. 그렇기에 각 프로세스에는 각각의 페이지 테이블이 존재한다.
2. PCB 내 페이지 테이블 포인터 저장
   1. 각 프로세스 제어 블록 (PCB)에는 해당 프로세스의 페이지 테이블 위치를 가리키는 포인터를 저장한다
   2. CPU 스케줄러는 새로운 프로세스 실행 시 PCB에서 저장된 페이지 테이블 포인터를 사용하여 빠르게 페이지 테이블을 메모리에 로드시킨다

이를 통해 페이지 테이블 간의 전환 속도가 향상되어서 프로세스 간 전환 시 지연시간이 감소된다. 또한 PCB에 각각의 페이지 테이블 정보를 저장하면서 별도의 레지스터를 사용하지 않는데 이를 통해 메모리를 절약할 수 있게 된다.

 

PTBR - Page-Table Base Register

 

 시스템 메모리 내 페이지 테이블의 시작 주소를 저장하는 하드웨어가 존재한다. 해당 하드웨어는 바로 PTBR(Page-Table Base Register)이며 페이징 시스템에서의 중요한 하드웨어 레지스터이다. 프로세스가 논리 주소를 사용하여 메모리에 접근하면 CPU는 PTBR의 값을 통해 페이지 테이블에 위치한 해당 논리 주소에 대한 페이지 번호를 맵핑하는 엔트리를 찾는다.

 

 이를 통해 빠른 문맥교환이 가능해진다는 장점이 있지만 메모리에 접근하는 시간을 느려진다는 단점이 존재한다. 논리 주소를 물리 주소로 변환하는 과정에서 두 번의 메모리 접근이 필요한데, 처음에는 페이지 테이블 엔트리를 조회하기 위해 사용되고, 다음에는 실제 데이터를 가져오기 위해 사용이 된다. 이러한 과정으로 인해 메모리 접근의 결과를 얻기 위한 시간이 늘어난다.

 

PTBR, PCB 페이지 테이블 포인터의 차이

 

 앞에서 페이지 테이블 정보를 저장하면서 레지스터를 사용하지 않는다고 하였지만 바로 PTBR이 나와서 찾아본 것이다. 결론적으로 PTBR은 각 프로세스의 페이지 테이블 정보를 저장하는 것이 아닌 시스템 전체의 페이지 테이블 위치를 저장하는 레지스터이다.

 

TLB - Translation Look-aside Buffer

 

TLB

 가상 주소를 물리 주소로 변환하는 과정을 빠르게 하기 위해 사용되는 캐시 메모리이다. CPU에서는 논리적 주소를 사용하여 메모리에 접근하지만 실제 메모리는 물리적 주소로 구성이 되어있다. 그렇기에 이러한 과정에서 사용되는 것이 Page table이다. 다만 여러 개의 프로세스와 페이지 테이블 중에 자주 사용되는 프로세스-페이지 테이블이 존재한다. 이러한 페이지 테이블과 관련이 된 항목을 저장하여 논리적, 물리적 주소의 변환과정의 시간을 줄여주는 것이 바로 TLB이다. 

 

동작 방식은 다음과 같다

1. CPU는 논리 주소를 통해 메모리에 접근한다
2. TLB에서 해당 가상 주소에 대한 항목을 검색한다
3. TLB에 항목이 존재하는 경우 (TLB Hit):
   1. TLB에서 페이지 테이블 엔트리(PTE)를 추출
      1. PTE는 논리적 주소를 물리 주소로 변환하는 데 사용
   2. CPU는 변환된 물리 주소를 통해 메모리에 접근
4. TLB에 항목이 없는 경우 (TLB Miss):
   1. 페이지 테이블에서 해당 논리 주소에 대한 PTE를 찾는다
   2. PTE는 TLB에 추가된다
   3. CPU는 PTE를 사용하여 논리 주소를 물리 주소로 변환한다
   4. CPU는 물리 주소를 사용하여 메모리에 접근한다.

결국 중요한 점은 TLB에 존재하는 항목이 얼마나 자주 사용되느냐가 관건이다. 그렇기에 이를 통해 장단점이 나눠진다

• 장점
  • 논리 주소를 물리 주소로 변환하는 속도가 향상된다
  • 페이지 테이블 접근 횟수를 줄여 메모리 접근 속도를 향상한다
  • CPU의 성능을 향상한다
• 단점
  • 용량에 한계가 있기에 모든 페이지 항목을 저장할 수는 없다
  • TLB Miss가 발생 시 성능 저하가 발생한다

결국 장, 단점을 보면 TLB HIt와 Miss의 처리율에 따라 달라지게 된다. 그렇기에 얼마나 hit를 했는지 판별하는 hit ratio가 중요한 척도가 된다. hit ratio는 해당 메모리에서 특정 데이터를 찾는 성공 비율을 의미한다. 

 

각 비율에 따라 달라지는 성능

 

 

Memory Protection with Paging, 페이징을 통한 메모리 보호

 

 페이징의 기능 중에는 성능을 위한 기능 말고 메모리 보호를 위한 기능도 존재한다. 해당 메모리 보호는 프레임(frame)마다 연결된 보호 비트를 통해 구현이 된다. 이는 유효/무효 비트(valid - invalid bit)라고 부른다. 해당 비트들은 각 페이지 테이블 항목에 같이 존재한다. 그리고 논리 주소 공간에 해당 페이지가 존재하는지 판별해 주는 역할이다.

 

valid - invalid bit

 

• 유효(valid) : 해당 페이지는 프로세스의 논리 주소 공간에 존재한다는 것을 의미 (legal)
• 무효 (invalid) : 해당 페이지는 논리 주소 공간 밖에 있다는 것을 의미 (illegal)

이때 무효로 정해져 있으면 현재 접근하려는 주소는 불법적인 것이기에 시스템에서 트랩을 발생한다. 그렇기에 접근 불가의 영역이다.

이러한 방법을 통해 간단하게 접근 가능/불가능의 영역을 판단하고 사용할 수 있게 되며, 불가능한 영역의 접근 시 트랩의 발생등을 통해 시스템의 안정성이 향상된다. 

 

Shared Pages

 

일반적으로 각 프로세스는 고유한 라이브러리의 사본을 주소공간에 로드한다. 다만 이때 라이브러리가 여러 프로세스에서 동시에 사용가능하고 final 한 변경 불가의 코드(리엔트런트 코드- reentrant code)라면 해당 라이브러리는 여러 프로세스에서 공유해서 사용이 가능하다. 

 

이러한 사용을 공유 페이지 (shared pages)라고 한다

sharing of standard c library in a paging environment

공유 페이지는 여러 프로세스가 동일한 코드를 공유하기에 메모리 사용량을 줄인다는 점에서 메모리 절약이 가능하다. 또한 별도의 사본 라이브러리를 프로세스마다 로딩할 필요가 없기에 로딩시간이 단축이 된다. 다만 해당 공유페이지에서 사용하는 것들은 무조건 수정이 불가능한 그런 코드여야 한다. 그렇지 않으면 사용하는 사용하는 코드들이 달라지기에 데이터 무결성 등에 관한 문제가 발생할 수 있다.

 

Structure of the Page Table

 

 작은 크기의 페이지 테이블이라는 문제없지만, 페이지 테이블을 사용할 때 대용량 논리 주소 공간을 사용하면 용량의 문제가 생길 수 있다. 그렇기에 페이지 테이블에 관한 구조를 사용해서 해당 문제를 줄이고자 하였다. 각 구조는 계층형, 해시, 역전의 구조가 존재한다.

 

 

계층형 구조 (Hirearchial Paging)

 

• 계층형
  • 다단계 페이지 테이블 구조를 사용하여 논리 주소를 여러 레벨로 분리한다
  • 각 레벨 테이블은 다음 테이블의 시작 주소를 가리키고 마지막 테이블은 메모리 주소를 가리키는 실제 물리적 주소를 가리킨다
  • 페이지 검색 과정이 다단계로 진행되기에 속도가 떨어질 수 있다.

해시 구조 (Hashed) / 역전 구조 (Inverted)

 

• 해시
  • 해시 함수를 사요하여 논리 주소를 해시 테이블 인덱스로 변환한다
  • 해시 테이블은 페이지 테이블 엔트리(PTE)를 저장한다
  • 빠른 검색 속도를 제공하지만 해시 충돌 가능성이 존재한다
• 역전
  • 이전과는 다르게 물리 프레임 주소를 기반으로 페이지 테이블을 구성한다
  • 각 프레임이 연결된 모든 논리 페이지 주소 목록을 저장한다
  • 메모리 관리 단순화에 효과적이지만 논리 주소를 물리 주소로 변환하는데 더 많은 시간이 걸린다

 

Swapping, 스와핑

 

 스와핑은 멀티프로그래밍 환경에서 실행할 수 있는 프로세스의 수를 늘리기 위해 사용하는 기술이다. 이를 통해 시스템이 실제로 가지고 있는 물리 메모리보다 전체 프로세스의 총 가상 주소 공간이 더 커질 수 있게 해주는 메모리 관리 기술이다.

swapping

 프로세스의 코드와 데이터를 실행하기 위해서는 해당 사항들이 메모리에 존재해야 한다. 다만 즉시 필요하지 않은 프로세스 또는 프로세스의 일부를 메모리에 대기시키는 것은 메모리의 낭비가 예상이 된다. 그렇기에 그런 부분들은 일시적으로 하드 디스크와 같은 보조 저장 장치에 옮겨놨다가 필요할 때 다시 메모리로 불러와 사용하는 것이다.

 

 그렇기에 스와핑을 통하면 기존 주어진 메모리보다 더 많은 프로세스를 실행할 수 있기에 성능의 효율이 증가되며, 사용하지 않는 프로세스는 메모리에서 제거해서 효율이 증가하고, 기존 중요한 프로세스는 메모리에 계속 유지를 시킬 수 있기에 해당 프로세스는 계속해서 빠른 응답이 가능하다는 장점이 존재한다.

 

 다만 장점만 존재하는 기술은 없기에 단점 또한 존재한다. 하드 디스크의 경우 메모리 계층 구조상 메모리보다 lv이 낮기에 메모리보다 용량은 많지만 읽기/쓰기 속도는 느리다는 단점이 존재한다. 그렇기에 스와핑을 사용 시 성능의 저하가 발생한다. 또한 스와핑을 사용하는 경우 프로세스의 교환이 기존 문맥 교환보다 느리다는 단점이 있기에 실행이 중단되는 상황도 발생하며, 이밖에도 추가적인 하드웨어를 요구할 수도 있다.

 

스와핑과 페이징의 비교

 

Swapping과 Paging

 

기존의 경우 프로세스의 프로세스의 단위로 페이징을 실행하였다. 대신 위의 Swapping과 Paging을 합쳐서 사용하면 더 효율적으로 메모리 관리를 할 수 있게 된다.

Swapping with Paging

 

프로세스 단위로 스와핑을 하는 것이 아닌 페이지 단위로 스와핑을 수행하면 기존 메모리에 저장할 수 있는 용량을 넘기면서도 효율적으로 메모리 관리가 가능해진다. 전체 프로세스 대신 페이지 단위로만 스와핑을 실행하기에 시스템이 더 자세하게 메모리를 관리할 수 있게 된다. 또한 페이지 단위로 스와핑을 진행하면 프로세스를 교체하는 것보다 더 작은 단위로 움직이기에 빠른 처리가 가능해진다. 그리고 마지막으로 필요하지 않은 페이지만 보조저장장치로 이동시키기에 메모리에는 중요 및 사용하는 페이지만 존재한다. 이를 통해 메모리 절약이 가능해진다.

• page out
  • 페이지를 메모리에서 보조 저장 장치로 이동하는 작업
• page in
  • 페이지를 보조 저장 장치에서 메모리로 이동하는 작업