20. 페이징과 스와핑: Chapter 9. Main Memory (Part 2)

9.3 페이징

• 지금까지 논의된 메모리 관리는 프로세스의 물리 주소 공간이 연속적이어야 했음
• 페이징
  • 프로세스의 물리 주소 공간이 연속적이지 않아도 되는 메모리 관리 기법
  • 연속 메모리 할당의 문제를 해결
    1. 외부 단편화 문제 해결
    2. 단편화된 된 메모리의 압축의 필요성 문제 해결

 

기본 방법

• 물리 메모리는 프레임frame이라고 불리는 같은 크기 블록으로 나누어짐
• 논리 메모리는 페이지page라고 불리는 같은 크기 블록으로 나누어짐
• 이를 통해 논리 주소 공간은 물리 주소 공간으로부터 완전히 분리되었고, 이 때문에  물리 메모리의 크기가 2^64 바이트보다 적게 장착된 시스템에서도 프로세스는 64비트로 이루어진 논리 주소 공간을 사용할 수 있음

• 논리 주소 공간은 페이지 번호 p과 페이지 오프셋 d 두 개의 부분으로 분리됨
• 페이지 번호: 프로세스의 페이지 테이블을 액세스 할 때 사용됨
• 페이지 오프셋: 참조되는 프레임 안에서의 위치
• 페이지 테이블: 물리 메모리의 각 프레임의 시작 주소를 저장하고 있음
• 따라서 프레임의 시작 주소와 페이지 오프셋이 결합하여 물리 메모리 주소가 됨

• CPU에 의해 생성된 논리 주소를 물리 주소로 변환하기 위한 MMU의 작업 단계
  1. 페이지 번호 p를 추출하여 페이지 테이블의 인덱스로 사용함
  2. 페이지 테이블에서 해당 프레임 번호 f를 추출함
  3. 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꿈
  4. 프레임 번호 f와 페이지 오프셋 d을 물리 주소로 구성함

• 프레임과 크기와 마찬가지로 페이지 크기는 하드웨어에 의해 정해짐
• 페이지 크기는 2의 거듭 제곱으로 일반적으로 컴퓨터 아키텍처에 따라 페이지당 4KB ~ 1GB 사이가 됨
• 논리 주소 공간의 크기가 2^m이고 페이지의 크기가 2^n 바이트일 경우 논리 주소의 상위 m-n 는 페이지 번호를 저장하고 하위 n비트는 페이지 오프셋을 지정함

• 위 그림은 논리 주소 에서 n=2, m = 4 이고 물리 메모리의 크기가 32B일 경우의 메모리 상황을 나타냄
  • 논리 주소 공간의 크기: 2^4 = 16 -> 16B
  • 페이지 크기: 2^2 = 4 -> 4B
• 예시
  • ex1) 논리 주소 0: 5*4 + 0 = 20
  • ex2) 논리 주소 3: 5*4 + 3 = 23
  • ex2) 논리 주소 4: 6*4 + 4 = 28

• 위 그림은 실행되기 위한 새 프로세스스 도착했을 때 메모리를 할당하기 전(a)과 할당 후(b)의 메모리 상황을 나타냄
• 한 프로세스가 실행되기 위해 도착하면 그 프로세스의 크기가 페이지 몇 개분에 해당하는지를 조사함
• 즉 프로세스가 n 페이지를 요구하면 메모리에서 이용할 수 있는 프레임이 n개가 있어야 함
• n개의 프레임을 사용할 수 있다면 이 프레임들은 이 프로세스에 할당함
• 그리고 프로세스의 처음 페이지가 할당된 프레임 중 하나에 적재되고 그 프레임 번호가 페이지 테이블에 기록됨
• 그다음 페이지는 또 다른 프레임에 적재되고 또 그 프레임 번호가 페이지 테이블에 기록되며 이 과정이 반복됨

 

 

하드웨어 지원

• CPU 스케줄러가 실행할 프로세스를 선택하면 사용자 레지스터를 다시 적재하고 저장된 페이지 테이블로부터 적절한 하드웨어 페이지 테이블 값을 다시 적재해야 함
• 대부분의 컴퓨터는 페이지 테이블을 메인 메모리에 저장하고 페이지 테이블 기준 레지스터PTBR로 하여금 페이지 테이블을 가리키도록 함
• 다른 페이지 테이블을 사용하려면 단지 이 레지스터만을 변화시키면 되고, 따라서 문맥 교환 시간을 줄일 수 있음

 

 

Translation Look-Aside Buffer, TLB

• 메인 메모리에 페이지 테이블을 저장하면 문맥 교환 속도가 빨라지지만, 메모리 액세스 시간이 느려질 수 있음
• 1) 페이지 테이블 항목과 2) 실제 데이터 에 접근하기 위한 2번의 연산이 필요하기 때문임
• TLB: 위 문제를 해결하기 위해 사용되는 특수한 소형 하드웨어 캐시
• TLB의 각 항목은 키와 값의 두 부분으로 이루어져 구성됨
• 페이지 번호가 같은 것이 발견(TLB hit)되면 그에 대응하는 프레임 번호를 알려줌 
• 페이지 번호가 TLB에 없으면(TLB miss) 위 그림에 따라 페이지 테이블에 따른 메모리 참조가 이루어져야 함
• 실질 메모리 접근 시간 
  
  • 적중률hit ration: 접근하려는 메모리의 페이지 번호가 TLB에서 발견되는 비율
  • ex)  적중률이 80%이고 메인 메모리에 접근하는 시간이 10ms이라고 할 때 실질 메모리 접근 시간
    • => 0.80 * 10 + 0.20 * 20(10ns(페이지 테이블에 접근하여 프레임 번호를 얻는 시간) + 10ns(원하는 데이터를 메모리에서 읽는 시간)) = 12 nanoseconds
  • ex)  적중률이 90%이고 메인 메모리에 접근하는 시간이 10ms이라고 할 때 실질 메모리 접근 시간
    • => 0.99 * 10 + 0.01 * 20 = 10.01 nanoseconds

 

 

보호 protection

• 페이지 테이블의 각 엔트리에는 유효valid/무효invalid 라는 하나의 비트가 있음
• 이 비트가 유효로 설정되면 관련된 페이지가 프로세스의 합법적인 페이짐을 나타냄
• 이 피트가 무효로 설정되면 관련된 페이지는 프로세스의 논리 주소 공간에 속하지 않는다는 것을 나타냄
• 위 그림에서 페이지 0, 1, 2, 3, 4, 5 주소는 페이지 테이블을 토해서 정상적으로 매핑됨
• 그러나 페이지 6,7에 매핑하려고 시도하면 비트가 무효로 설정된 것을 발생하여 트랩을 발생시킴

 

 

공유 페이지 Shared Pages

• 페이징의 장점은 공통의 코드(C 라이브러리 등)을 공유할 수 있는 것임
• 재진입 코드( 다중사용자 시스템 내에서 공유될 목적으로 작성된 코드 ex) 읽기 전용 코드)는 실행 중에 절대 변경되지 않으며, 따라서 위 그림과 같이 두개 이상의 프로세스가 동일한 코드를 동시에 실행할 수 있음

 

 

9.4 페이지 테이블의 구조

• 많은 현대 컴퓨터는 매우 큰 주소 공간을 가지며 이러한 환경에서는 페이지 테이블도 상당히 커짐
• 이러한 경우에 페이지 테이블을 구성하는 3가지 방법이 있음
  1. 계층적 페이징
  2. 해시 페이징
  3. 테이블 및 역 페이지 테이블

 

 

계층적 페이징

• 2단계 페이징 기법: 페이지 테이블 자체가 다시 페이징 되게 하는 것

 

 

해시 페이지 테이블

• 주소 공간이 32비트보다 커지면 가상 주소 공간을 해시로 사용하는 해시 페이지 테이블을 많이 사용함
• 가상 주소공간으로부터 페이지 번호가 오면 그것을 해싱함
• 그것으로 해시 페이지 테이블에서 연결 리스트를 따라가며 첫번째 원소와 가장 페이지 번호를 비교함
• 일치하면 그에 대응하는 페이지 프레임 번호를 가져와 물리 주소를 얻음
• 일치되지 않으면 연결 리스트의 그 다음 원소로 똑같은 일을 반복함

 

 

역 페이지 테이블

• 역페이지 테이블에서는 메모리 프레임마다 한 항목씩을 할당함
• 각 항목은 그 프레임에 올라와 있는 페이지 주소, 그리고 그 페이지를 소유하고 있는 프로세스 ID를 표시함
• 이렇게 되면 시스템에는 단 하나의 페이지 테이블만이 존재하게 되고, 테이블 내 각 항목은 메모리 한 프레임씩을 가리키게됨

 

 

9.5 스와핑

• 모든 프로세스의 물리 주소 공간 크기의 총합이 시스템의 실제 물리 메모리 크기보다 큰 경우에도 스와핑을 이용하면 동시에 실행하는 것이 가능함
• 다중 프로그래밍의 정도를 증가시킴

 

 

기본 스와핑

• 표준 스와핑에는 메인 메모리와 백업 저장장치(보조 저장장치) 간에 전체 프로세스를 이동함
• 프로세스 또는 일부가 백업 저장장치로 스왑될 때 프로세스와 관련된 자료구조는 백업 저장장치에 기록되어야 함

 

 

페이징에서의 스와핑

• 프로세스 전체를 스왑하는 것이 아니라 적은 수의 페이지만 스왑함
• 스와핑은 일반적으로 표준 스와핑을 말하며, 페이징은 페이징에서의 스와핑을 의미함
• 페이지-아웃 연산은 페이지를 메모리에서 백업 저장장치로 이동시킴
• 페이지-인 연산은 백업 저장장치에서 메모리로 페이지를 이동시킴