9.3. Paging(페이징)
프로세스의 물리 주소 공간을 불연속적 (non-contiguous)으로 관리가능
외부 단편화 문제를 해결가능 & Hole 압축 불필요
9.3.1. Basic Method(기본 방법)
- 프레임(frame) : 물리 메모리를 같은 크기 블록으로 나눈 것
- 페이지(page) : 논리 메모리를 같은 크기의 블록으로 나눈 것
메모리 연속 할당은 논리 메모리에 있는 프로그램 하나를 통째로 물리 메모리에 적재한다.
But, 페이징 기법은 논리 주소 공간과 물리 주소 공간이 완벽하게 분리된다.
페이지 번호 (p) & 오프셋 (d) : "p 페이지에 있는 d번째 메모리에 할당해 줘"
- 페이지 번호는 페이지 테이블을 접근할 때 사용된다.
- 페이지 오프셋은 페이지 테이블에서 반환 된 물리 주소의 프레임에서 참조할 위치가 된다.
프로세스마다 페이지의 개수가 다르기 때문에 페이지 테이블 (page table)을 통해 관리해 주어야 한다.
CPU에 의해 생성된 논리 주소를 물리 주소로 변환하는 과정
- 페이지 번호 p를 추출해 페이지 테이블의 index로 사용한다.
- 페이지 테이블에서 해당 프레임 번호 f를 추출한다.
- 논리 주소의 페이지 번호 p를 프레임 번호 f로 바꾼다.
페이지 크기(page size)
- 프레임 크기와 마찬가지로 하드웨어에 의해 정해진다.
- 크기는 2의 거듭 제곱, 4KB ~ 1GB 사이의 크기를 가진다.
- 논리 주소 공간의 크기가 2^m이고, 페이지 크기자 2^n바이트인 경우
- 논리 주소 상위 m - n 비트는 페이지 번호(page number)
- 논리 주소 하위 n비트는 페이지 오프셋(page offset)을 지정한다.
4바이트 크기의 페이지를 가진 32바이트 물리 메모리 에서의 페이징 예시이다.
논리 주소 공간의 크기가 16(2^4)바이트이다.
페이지의 크기가 4(2^2)바이트 이므로 4개( 2^(4-2) )의 페이지 번호가 생성된다.
→ 그림을 보면 페이지의 크기와 페이지 오프셋의 크기가 같은 것을 알 수 있다.
프레임 테이블
O/S 는 어떤 프레임이 할당되어 있고, 어떤 프레임이 사용 가능한지, 총 프레임은 몇개나 되는지 등 여러 정보를 알고 있어야 한다.
이러한 정보는 운영체제에서 단 하나의 자료구조로 관리 되며 프레임 테이블이라고 한다.
프레임 테이블은 각 프레임당 하나의 항목을 가지고 있으며, 프레임이 비었는지 할당되었는지, 누가 할당 했는지에 대한 정보를 가지고 있다.
9.3.2. Hardware Support(하드웨어 지원)
페이지 테이블에 대한 포인터는 각 프로세스의 PCB에 다른 레지스터 값과 함께 저장된다.
cpu 스케줄러가 실행할 프로세스를 선택하면 컨텍스트 스위치를 위해 페이지 테이블을 다시 로드해야 한다.
9.3.2.1. Translation Look-Aside Buffer(TLB)
PTBR(page-table base register) - 페이지 테이블 기준 레지스터
페이지 테이블을 메모리에 저장하고 페이지 테이블 기준 레지스터가 페이지 테이블을 가리키도록 한다.
- Context Switch가 빠르다. But, 메모리 액세스 시간이 느려진다.
- 두번의 메모리 액세스가 필요하다.
- 페이지 번호를 기준으로 PTBR의 오프셋 값을 이용해 페이지 테이블의 항목을 찾는다.
- 실제 주소 생성 후 원하는 메모리 위치에 액세스
Translation Look-AsideBuffer(TLB) 이용하여 문제 해결
CPU에서 페이지 테이블에 바로 접근하지말고 TLB (translation look-aside buffer)를 거친다.
TLB는 캐시 메모리이기 때문에 빠른 속도로 메모리에 접근할 수 있다.
"TLB hit"가 발생한 경우 빠르게 물리 주소로 변환할 수 있고, "TLB miss"가 발생한 경우 페이지 테이블에서 실제 값을 찾아 물리 주소로 변환할 수 있다.
Effective Memory-Access Time(실질 메모리 접근 시간)
- TLB hit: 찾고자 하는 페이지 번호가 TLB에 있는 경우
- TLB miss: 페이지 번호가 TLB에 없는 경우
- hit ratio: 페이지 번호가 TLB에서 발견되는 비율
- if) hit ratio : 80% -> EAT = 0.80×10+0.20×20 = 12 ns (TLB miss : hit의 2배만큼 시간이 걸림)
- if) hit ratio : 80% -> EAT = 0.80×10+0.20×20 = 12 ns (TLB miss : hit의 2배만큼 시간이 걸림)
9.3.3. Protection(보호)
페이징 환경에서 메모리 보호는 각 페이지에 붙어있는 보호 비트(protection bit)에 의해 구현된다.
유효-무효 비트 (valid-invalid bit)라는 하나의 비트가 페이지 테이블의 각 엔트리에 추가된다.
- 유효 (valid) 해당 페이지가 프로세스의 논리 주소 공간에 포함되어 있다. 합법 (legal)한 페이지
- 무효 (invalid) 해당 페이지가 프로세스의 논리 주소 공간에 포함되어있지 않다. 불법(illegal)한 페이지 → 불법 주소가 들어오면 유효-무효 비트를 통해 트랩을 건다.
9.3.4. Shared Pages(공유 페이지)
페이징의 장점은 공통의 코드를 공유할 수 있다는 점이다.
(멀티 프로그래밍 환경에서 중요하게 고려해야 할 점이다.)
libc 라이브러리를 고려하자. 만약 각 프로세스에 libc 사본을 적재한다면?
libc 크기 : 2MB, 40개의 프로세스가 있다면 80MB 메모리가 필요하다.
하지만 코드가 재진입 코드(Reentrant code)인 경우 프로세스간 공유가 가능하다.
- Reentrant code : 실행 중에 절대 바뀌지 않는 코드
라이브러리의 페이지 테이블 엔트리가 모든 프로세스에서 동일하다.
물리적 주소에는 라이브러리가 하나만 적재 되어있지만, 모든 프로세스가 동일한 라이브러리를 사용한다.
→ 라이브러리를 물리 주소로 복사하지 않고 논리 주소로 복사한 것이다.
(읽기 전용이므로 동기화 문제, Deadlock문제는 발생하지 않는다.)
9.4. 페이지 테이블의 구조
현대 컴퓨터가 매우 큰 주소 공간을 가진다. 따라서 페이지 테이블도 상당히 커진다.
9.4.1. Hierarchical Paging(계층적 페이징)
2단계 페이징 기법
- 페이지 테이블 자체가 다시 페이징 되게 한다.
20bit의 페이지 번호와 12비트 offset이 존재하는 메모리가 있다고 하자.
페이지 번호를 다시 나누면 10비트 짜리 페이지 번호와 10비트 짜리 페이지 오프셋으로 나누어진다.
p1은 바깥 페이지 테이블의 인덱스이며, p2는 안쪽 페이지 테이블의 페이지 내 오프셋이다.
문제점
하지만, 64비트 환경에서는 적절하지 않은 기법이다.
(p1 : 32, p2 : 10, p3 : 10, d : 12)
2번째 바깥 페이지 테이블인 p1을 페이징 해야하므로 4단계 페이징 기법을 사용해야한다.
너무 많은 메모리 접근을 필요로 한다.
9.4.2. Hashed Page Tables(해시 페이지 테이블)
주소 공간이 32비트보다 커지면 가상 주소를 해시로 사용하는 해시 페이지 테이블을 많이 이용한다. → 해시는 O(1)의 시간복잡도를 가진다.
9.4.3. Inverted Page Table(역 페이지 테이블)
프로세스의 주소를 통해 페이지 테이블에 접근하는 방식을 역으로 적용한다.
pid (process identifier)를 추가하여 해당 pid의 페이지를 역으로 저장한다.
9.5. Swapping(스와핑)
스와핑을 통해 물리 주소 공간의 크기보다 훨씬 큰 프로세스를 문제 없이 실행할 수 있다.
9.5.1. Standard Swapping(기본 스와핑)
메인 메모리와 백업 저장장치 간에 전체 프로세스를 이동한다.
실제 물리 메모리보다 더 많은 프로세스를 수용할 수 있도록 물리 메모리가 초과 할당될 수 있다.
- 비활성 프로세스는 Swap Out을 통해 백업 저장장치로 이동하고,
- 활성 프로세스는 Swap In을 통해 다시 메인 메모리에 적재된다.
9.5.2. Swapping with Paging(페이징에서의 스와핑)
프로세스 전체를 이동하는데 엄청난 시간이 걸리는 단점이 있다.
따라서, 프로세스 전체가 아닌 프로세스 페이지를 스왑한다.
물리 메모리를 초과 할당할 수 있지만 프로세스 전체를 스왑하는 비용이 발생하지 않는다.
최근에는 페이징이라는 말이 페이징을 통한 스와핑을 의미하고
swap in, swap out대신 page in, page out이라는 용어를 사용한다.
참고 :
Silberschatz et al. 『Operating System Concepts』. WILEY, 2020.
