Ch08. 가상 메모리의 기초_02)페이징 기법(1)

페이징 기법의 구현

페이징 기법

• 고정 분할 방식을 이용한 가상 메모리 관리 기법
• 물리 주소 공간을 같은 크기로 나누어 사용
• 가상 주소는 프로세스 입장에서 바라본 메모리 공간으로 항상 0번지부터 시작
• 페이지와 프레임
  • 가상 주소의 분할된 각 영역을 페이지라고 하며 번호를 매겨 관리
  • 물리 메모리의 각 영역은 가상 주소의 페이지와 구분하기 위해 프레임이라고 함(프레임도 페이지처럼 번호를 매겨 관리)
  • 페이지와 프레임의 크기는 같기 때문에 페이지는 어떤 프레임에도 배치될 수 있음
  • 어떤 페이지가 어떤 프레임에 있는지에 대한 연결(매핑) 정보는 페이지 테이블에 담겨 있음
  • 페이지 테이블에 invalid는 해당 페이지가 스왑 영역에 있다는 의미

페이징 기법의 구현

---

페이징 기법의 주소 변환

프로세스가 30번지의 내용을 읽으려고 할 때 주소 변환 과정

• 페이징 기법에서 가상주소가 물리주소로 변환되는 과정, 그림[8-6]
• 가상주소와 물리주소를 같은 10B로 나눔, 따라서 한 페이지 또는 한 프레임은 총 10개의 주소를 가짐

① 가상 주소 30번지가 어느 페이지에 있는지 찾음 (30번지는 페이지 3의 0번째 위치에 있음: VA=<3, 0>)

② 페이지 테이블의 페이지 3으로 가서 해당 페이지가 프레임 1에 있다는 것을 알아냄

③ 최종적으로 물리 메모리 프레임 1의 0번째 위치에 접근 (이 주소가 가상 주소 30번지의 물리 주소)

페이징 기법의 주소 변환

프로세스가 가상 주소 18번지에 값을 저장하려고 할 때 주소 변환 과정

① 가상 주소 18번지가 어느 페이지에 있는지 찾음 (18번지는 페이지 1의 8번째 위치에 있음: VA=<1 ,8>)

② 페이지 테이블의 페이지 1로 가서 해당 페이지가 프레임 3에 있다는 것을 알아냄

③ 프로세스가 저장하려는 값을 프레임 3의 8번 위치에 저장

정형화된 주소 변환

• 페이징 기법에서는 가상 주소를 VA=<P, D>로 표현
  • VA : 가상 주소^{virtual address}
  • P : 페이지^page
  • D : 페이지의 처음 위치에서 해당 주소까지의 거리^distance
• 페이징 기법에서의 주소 변환은 가상 주소 VA=<P, D>를 물리 주소 PA=<F, D>로 변환하는 것
  • PA : 물리 메모리의 주소를 가리키는 용어로 물리 주소 또는 실제 주소
  • F : 프레임^frame
  • D : 프레임의 처음 위치에서 해당 주소까지의 거리^distance

페이징 기법의 주소 변환 과정

• VA=<P, D> → PA=<F, D>
• 페이지 테이블을 사용하여 P는 F로 바꾸고 D는 변경 없이 그대로 씀
• D를 변경하지 않는 이유는 페이지와 프레임의 크기를 똑같이 나누었기 때문

페이징 기법의 정형화된 주소 변환

페이지의 크기가 다양할 경우 가상 주소를 <P, D>로 변환하는 공식

가상 주소를 <P, D>로 변환하는 공식

• 한 페이지의 크기가 10B인 가상 메모리 시스템에서 가상 주소 32번지
  • P=3(32/10의 몫)
  • D=2(32/10의 나머지)
• 한 페이지의 크기가 512B인 시스템에서 가상 주소 2049번지
  • P=4(2049/512의 몫)
  • D=1(2049/512의 나머지)

16bit CPU의 컴퓨터에서 한 페이지의 크기가 2¹⁰B일 때 페이징 시스템

• 한 프로세스가 사용할 수 있는 가상 메모리의 크기는 2¹⁶(65,536)B
• 사용자는 0번지부터 65535(2¹⁶-1)번지까지 가상 주소 공간을 사용 가능
• 가상 주소로 사용할 수 있는 16bit 중 6bit는 페이지 번호로, 10bit는 페이지의 처음 위치에서 해당 주소까지의 거리
• 이것은 시스템의 페이지가 0~63 번까지, 페이지 하나가 0~1023 번까지 구성되어 있다는 의미임

16bit 가상 주소의 예

• 전체 페이지의 수는 2⁶, 즉 64개이고 페이지 0번부터 63번까지 존재
• 물리 주소도 가상 주소와 같이 1,024B로 나뉨
• 프레임은 0부터 31까지만 있다고 가정
• 페이지 테이블은 페이지 테이블 엔트리가 0~63으로 총 64개 (페이지 테이블의 크기는 물리 주소의 크기가 아니라 프로세스의 크기에 비례)

16bit CPU의 페이징 시스템

프로세스가 980번지에 저장된 데이터를 요청했을 때 동적 주소 변환

• 가상 주소 980번지의 페이지 P, 거리 D를 구함
  • P=0(980/1024의 몫), D=980(980/1024의 나머지) → VA=<0, 980>
• 페이지 테이블로 가서 페이지 0이 프레임 2에 저장되어 있다는 것을 확인
• 물리 메모리의 프레임 2 시작 지점으로부터 980번지 떨어진 곳에 접근하여 데이터를 가져옴

16bit CPU의 페이징 시스템

---

페이지 테이블 관리

다수의 프로세스가 있는 페이징 시스템

• 페이지 테이블 관리가 복잡한 이유 : 시스템에 여러 개의 프로세스가 존재하고 프로세스마다 페이지 테이블이 하나씩 존재함.
• 프로세스마다 페이지 테이블이 존재함. 프로세스의 수가 많아지면 페이지 테이블의 크기가 커지고, 이에 따라 프로세스가 실제로 사용할 수 있는 메모리 영역이 줄어듦
• 페이지 테이블 크기를 적정하게 유지하는 것은 페이지 테이블 관리의 핵심
• 페이지 테이블은 메모리 관리자가 자주 사용하는 자료구조이므로 물리메모리 영역 중 운영체제 영역의 일부분에 모아 놓음

다수의 프로세스가 있는 페이징 시스템

물리 메모리 내 페이지 테이블의 구조

• 페이지 테이블의 수가 증가하거나 페이지 테이블 크기가 커지면 운영체제 영역이 커지는 만큼 사용자 영역이 작아짐
• 각 페이지 테이블의 시작 주소는 페이지 테이블 기준 레지스터^{Page Table Base Register, PTBR}에 보관

물리 메모리 페이지 테이블의 구조

• 물리 메모리의 크기가 작을 때는 프로세스만 스왑 영역으로 옮겨지는 것이 아니라 페이지 테이블의 일부도 스왑 영역으로 옮겨짐
• 페이지 테이블에 빠르게 접근하기 위해 레지스터가 존재함
• 각 프로세스가 메모리에 접근하려고 할 때 메모리 관리자는 페이지 테이블의 위치를 신속하게 파악해야 함
• 그래서 각 페이지 테이블의 시작 주소를 페이지 테이블 기준 레지스터에 보관함
• 페이지 테이블 기준 레지스터는 각 프로세스의 프로세스 제어블록에 저장되는 데이터로, 물리메모리 내에 페이지 테이블의 시작주소를 가지고 있음

---

페이지 테이블 매핑 방식

• 컴퓨터 시스템 내에 다수의 프로세스가 존재하고, 각 프로세스는 하나의 페이지 테이블을 가지며, 페이지 테이블은 운영체제 영역에 있음
• 따라서 페이지 테이블의 크기가 너무 커지면 프로세스가 실제로 사용할 수 있는 영역이 작아짐
• 사용할 수 있는 물리 메모리 영역이 적을 경우 프로세스만 스왑 영역으로 옮겨지는 것이 아니고, 페이지 테이블의 일부분도 스왑 영역으로 이동함
• 페이지 테이블을 전체를 메모리에서 관리하느냐, 일부를 스왑 영역에서 관리하느냐에 따라 가상 주소를 물리주소로 변환하는 방법이 달라지므로 페이지 테이블이 위치하는 곳에 따른 다양한 페이지 테이블 매핑 방식이 존재함

직접 매핑^{direct mapping}

• 페이지 테이블 전체가 물리 메모리의 운영체제 영역에 존재하는 방식
• 별다른 부가 작업 없이 바로 주소 변환이 가능하기 때문에 직접 매핑이라고 부름

연관 매핑^{associative mapping}

• 페이지 테이블 전체를 스왑 영역에서 관리하는 방식
• 물리 메모리의 여유 공간이 작을 때 사용하는 방식
• 모든 페이지 테이블을 저장장치의 스왑 영역에 저장하고 그 중 일부만 물리 메모리에 가져옴
• 일부 내용만 무작위로 가져오기 때문에 페이지 번호와 프레임 번호 둘 다 필요
• 주소 변환 시 물리 메모리 내의 페이지 테이블을 다 검색해야 하며 만약 원하는 프레임 번호를 얻지 못하면 스왑 영역에 있는 페이지 테이블 검색
• 검색 실패 시 스왑 영역에서 다시 찾아야 하므로 시간을 낭비하게 됨

집합 - 연관 매핑^{set-associative mapping}

• 연관 매핑에서는 물리 메모리에 있는 데이터가 무작위로 올라오기 때문에 원하는 프레임 번호를 얻기 위해 모든 테이블을 검색해야 하는 문제 존재
• 집합-연관 매핑은 디렉토리 매핑이라고도 부름
• 집합-연관 매핑에서는 페이지 테이블을 일정한 집합으로 자르고, 자른 덩어리 단위로 물리 메모리에 가져옴
• 페이지 테이블을 n개씩 자르고 이를 관리하는 페이지 테이블을 하나 더 생성
• 새로 생성한 집합 테이블에는 일정하게 자른 페이지 테이블이 물리 메모리에 있는지, 스왑 영역에 있는지에 대한 위치 정보를 표시
• 연관 매핑과 비교했을 때 집합 테이블을 통해 원하는 페이지 테이블 엔트리가 스왑 영역에 있는지, 물리 메모리에 있는지 간단히 파악할 수 있음
• 연관매핑과 집합 집합-연관 매핑은 캐쉬에서 사용하는 방식임

역매핑^{invert mapping}

• 물리 메모리의 프레임 번호를 기준으로 테이블을 구성
• 물리 메모리의 프레임에 어떤 프로세스의 어떤 페이지가 올라와 있는지 표시
• 프로세스 수와 상관없이 테이블이 하나만 존재하므로 테이블의 크기가 매우 작음 (장점)
• 프로세스가 가상 메모리에 접근할 때 프로세스 아이디(PID)와 페이지 번호를 모두 찾아야 하는 단점이 있음 (속도가 아주 느림)

직접 매핑 방식의 구조

• 페이지 테이블 전체가 물리 메모리에 저장되기 때문에 가상 주소 VA=<P, D>를 물리 주소 PA=<F, D>로 변환하려면 페이지 테이블의 P번째 위치(PTE P)에서 원하는 프레임 값을 얻을 수 있음
• 페이지 테이블의 시작 주소는 페이지 테이블 기준 레지스터가 가지고 있으므로 물리 메모리상 페이지 테이블의 P번째 주소가 시작 주소로부터 P번째 위치에 존재

직접 매핑

연관 매핑 방식의 구조

• 메모리에 접근하기 위해 먼저 변환 색인 버퍼(Translation Look-ahead Buffer, TLB)를 찾음 (TLB 또는 연관 래지스터라고 부름)
  • TLB 히트 : 원하는 페이지 번호가 변환 색인 버퍼에 있는 경우로, 곧바로 물리 주소로 변환
  • TLB 미스 : 원하는 페이지 번호가 변환 색인 버퍼에 없는 경우로, 스왑 영역에 저장된 직접 매핑 테이블을 사용하여 프레임 번호로 변환
• 전체 페이지 테이블을 물리 메모리에 보관하지 않아 메모리를 절약할 수 있음
• TLB 미스가 빈번하게 발생할 경우 시스템의 성능이 떨어지는 단점 존재
• 변환 색인 버퍼는 페이지 테이블의 일부를 무작위로 가지고 있기 때문에 모든 변환 색인 버퍼를 검색한 후에야 원하는 페이지가 메모리에 없다는 것을 알 수 있음

연관 매핑

집합-연관 매핑 방식

• 연관 매핑에서는 모든 변환 색인 버퍼를 검색한 후 TLB 미스 발생을 확인함으로써 시스템의 성능이 저하되는 단점을 개선한 방법이 집합-연관 매핑 방법
• 컴퓨터 사용 시 파일이 많으면 디렉터리를 사용해 일정한 묶음으로 만듦
• 집합-연관 매핑은 관련 있는 테이블을 묶음으로 모아 놓은 형태
• 페이지 테이블을 같은 크기의 여러 묶음으로 나누고, 각 묶음의 시작 주소를 가진 디렉터리 테이블을 새로 만들어 관리
• 전체 페이지 테이블은 스왑 영역에 있으며, 일부 테이블은 묶음 단위로 메모리로 옮김
• 해당 묶음이 현재 메모리에 있는지, 스왑 영역에 있는지를 표시하는 디렉터리 테이블을 새로 만듦
• 디렉터리 테이블을 살펴보면 원하는 테이블 묶음이 어디에 있는지 알 수 있으므로 전체 테이블을 찾아보지 않아도 TLB 미스를 바로 알 수 있음

집합-연관 매핑 방식의 가상 구조

• 페이지 테이블이 일정 크기의 묶음으로 나뉘기 때문에 가상 주소를 VA=<P, D>가 아니라 VA=<P1, P2, D>로 바꾸어 표시
  • P1 : 디렉터리 테이블에서의 위치 정보 (디렉터리 테이블 번호)
  • P2 : 묶음 내에서의 위치 정보 (묶음 테이블 번호)
• 페이지 테이블을 10개씩 한 묶음으로 나눌 경우 0~9번 테이블은 0번 디렉터리에, 10~19번 테이블은 1번 디렉터리에 속함
  • 가상 주소 32번지 : <0, 3, 2>로 변환
  • 가상 주소 127번지 : <1, 2, 7>로 변환
• 페이지 주소를 세분화함, 페이지 번호 3은 0과 3, 페이지번호 12는 1과 2로, 페이지 번호 178은 17과 8로 나눔
• 여기서 P1은 P2 테이블 묶음이 메모리에 있는지, 스왑 영역에 있는지에 대한 위치 정보를 나타냄
• 이러한 특징 때문에 집합-연관 매핑을 멀티페이지 매핑이라고도 함.

집합-연관 매핑 방식의 구조

• 디렉터리 페이지 테이블의 시작 주소는 페이지 테이블 기준 레지스터가 가지고 있음
• 프로세스가 특정 주소를 요구하면 VA=<P1, P2, D>로 변환되고, P1을 이용하여 디렉터리 테이블에서 주소를 찾음
• 만약 I(invalid)라고 표시되어 있으면 TLB 미스가 발생한 것
• 원하는 테이블이 물리 메모리에 있으면 묶음 테이블의 시작 주소가 명시되어 있음

집합-연관 매핑

• [그림 8-15]에서 묶음 테이블 시작 주소 b, 그러므로 P2를 이용해 묶음 테이블에서 원하는 프레임 번호를 얻음
• 집합-연관 매핑은 직접 매핑과 연관 매핑의 장점을 합한 방법으로, 크기가 큰 페이지 테이블을 같은 크기의 묶음으로 나누어 효율적 관리 가능
• 연관 매핑의 경우 변환 색인 버퍼에 여러 테이블이 섞여있기 때문에 주소 변환을 위해 모든 테이블을 검색함
• 집합-연관 매핑에서는 디렉터리 테이블을 이용해 묶음 테이블의 위치를 바로 확인 가능
• 연관 매핑은 TLB 미스가 발생할 경우 변환 색인 버퍼 전체를 검색하는데 시간을 낭비하지만, 집합-연관 매핑은 이러한 시간이 소모되지 않음
• 직접 매핑과 달리 일부 페이지 테이블만 메모리에서 관리해 물리메모리를 절약함

역매핑

• 물리 메모리의 프레임 번호를 기준으로 테이블 작성

역매핑

역매핑 방식의 구조

• 테이블이 <프레임 번호, 프로세스 아이디, 페이지 번호>로 구성
• 페이지 테이블의 행 수는 실제 프레임의 수와 같음
• 프로세스의 수와 상관없이 항상 일정 크기의 페이지 테이블을 유지하여 테이블의 크기가 매우 작음
• 주소 변환 시 메모리 관리자는 주소 변환을 해야 하는 프로세스의 아이디와 페이지 번호가 물리 메모리에 있는지 역매핑 테이블에서 검색
• 현재 테이블에 원하는 데이터가 없으면 스왑 영역에서 가져옴
• 페이지 테이블을 다 검사한 후에야 저장장치에 접근하기 때문에 검색 시간을 낭비하는 단점이 있음

역매핑 테이블의 구성