Demand Paging
🔔 Concept
프로세스의 이미지를 "같은 크기"의 블록으로 분할한다.
실행 프로그램 로딩 시, "당장 필요한 페이지"만 로딩한다.
실행 도중 "필요한 페이지들만" 추가적으로 로딩을 한다. 즉, Page Fault가 발생하면 로딩한다.
따라서 프로세스가 실행하는 동안 한번도 접근하지 않는, 메모리에 한번도 로딩되지 않는 페이지가 있을 수도 있다.
✅ Page(페이지)
Secondary Storage에서 n개의 같은 크기의 페이지로 분할되어 있다.
✅ Page Frame(프레임)
메인 메모리는 m개의 프레임으로 분할되어 있다.
일부 페이지는 메인 메모리의 프레임에 할당되어 있다.
✅ Pager(페이저)
참조가 필요한 특정 페이지를 메모리를 가져오거나 필요 없는 페이지를 메모리 밖으로 밀어내는, 페이지 단위의 swap을 하는 커널의 코드(커널의 모듈)이다.
✅ Swapper(스와퍼)
프로세스 이미지 통째로 가져오거나, 통째로 밀어내는 커널의 모듈(커널의 코드)이다.
페이저와 차이점은 페이지 단위, 스와퍼는 프로세스 단위이다.
🔔 Paging System의 특징
1) 프로세스 이미지를 논리적으로 분할하지 않는다.
일률적으로 크기 단위로 잘라낸다. 4KB라면 모두 각각 4KB로 한다. (스택, 힙 등 섞일 수 있다)
2) 따라서 단순하고 효율적이다.
3) 대부분의 운영체제에서 사용된다.
(다만 Paging과 Segmentation을 섞은 하이브리드로 사용된다)
4) 특정 페이지의 Sharing과 Protection이 복잡하다.
📌 Address Mapping
Virtual Address v = (b,d)
예를 들어 Virtual Address가 32bit일 때, 페이지 하나의 크기가 4KB(2의 12승)라고 가정해 보자.
Virtual Address는 32Bit이지만 12bit만 displacement로 사용되고, 나머지 20bit는 page number로 사용된다.
🔔 Demand Paging의 3가지 Address Mapping 메커니즘
n개의 페이지 중 0, 1, k번 페이지만 메모리에 들어가 있다.
각각 메모리의 2번, 4번, h번 페이지 프레임에 들어가 있다.
각각의 페이지에 대해 Secondary Storage Address가 있다. 즉 해당 페이지를 찾기 위해서 보조기억장치의 어느 주소에 접근하면 되는지 나와 있다.
2번 페이지에 접근하려 하는데 residence bit = 0이므로 page fault 발생 -> Secondary Storage Address를 찾고 접근하여 읽어온다.
1) Direct Mapping
일반 Block Mapping과 동일
PMT(Page Mapping Table)이 메인 메모리의 커널 스페이스 안에 존재한다. 해당 프로세스의 PCB 안에 PMT가 존재한다.
(1) cpu에서 프로세스 Pa가 실행중이다. Pa가 virtual address (p, d)를 generation했다.
(2) Pa의 pcb에서 PMT를 찾는다.
(3) p번 페이지의 resident bit 을 검사하고 1이면 page frame number(p')을 찾는다.
(4) p' * pageSize + d 가 REAL address가 된다.
(5) 만약 resident bit = 0이면 page fault가 발생한다. 해당 page를 swap device로부터 memory로 load해오기 위해 context switching이 발생한다.
❗ 문제 ❗
(1) PMT가 Memory에 있다는 문제
Pa가 실행하면서 real address를 찾기 위해 PMT에 접근하기 위해 Memory에 한번 더 접근해야 한다는 단점이 존재한다. 즉 원래는 한번 접근해도 되는 일을 두번 접근하게 된다.
메모리 접근횟수가 2배가 되는 것은 성능을 저하시키고, 프로그램 실행시간을 느리게 한다.
(2) PMT 테이블의 크기
PMT 테이블의 크기가 매우 클 경우 메모리 커널 공간 안에 넣기 어려울 수 있다.
Solution 👇
(1) Associative Mapping (Translation Look-aisde Buffer)
(2) PMT를 dedicated Register나 캐시 메모리에 저장
2) Associative Mapping (Translation Look-aisde Buffer)
Translation Look-aisde Buffer 라는 특수한 버퍼를 이용한다. 연관 기억장치이며, Key값을 기반으로 Parellel search를 하는 것이다.
Page Map Table을 TLB 안에 저장해두고 TLB의 테이블을 Parellel search하겠다는 방법이다.
탐색 속도가 매우 빠르며 오버헤드가 적다.
하드웨어의 비용이 비싸진다.
(1) cpu에서 프로세스 Pa가 실행중이다. Pa가 virtual address (p, d)를 generation했다.
(2) TLB의 PMT에서 page number p를 parallel search로 빠르게 찾는다.
(3) p번 페이지의 resident bit 을 검사하고 1이면 page frame number(p')을 찾는다.
(4) p' * pageSize + d 가 REAL address가 된다.
(5) 만약 resident bit = 0이면 page fault가 발생한다. 해당 page를 swap device로부터 memory로 load해오기 위해 context switching이 발생한다.
PMT에서 p'를 찾는 시간이 매우 빠르기 때문에 Direct Mapping보다 성능이 훨씬 좋다.
3) Hybrid Direct/Associative Mapping
PMT의 사이즈가 큰데 이를 모두 수용하는 TLB Mapping은 매우 비싼 단점이 있다
작은 용량의 TLB만 사용하고, 전체 PMT는 커널 공간에 넣어둔다. PMT에서 자주 사용되는 페이지에 대한 PMT Entries만 뽑아서 TLB에 저장한다.
따라서 가격은 줄어들고, TLB Mapping의 장점을 가져갈 수 있다.
(1) cpu에서 프로세스 Pa가 실행중이다. Pa가 virtual address (p, d)를 generation했다.
(2) TLB의 PMT에서 page number p를 parallel search로 빠르게 찾는다.
(3-1) 만약 p가 있다면(hit⭕), p번 페이지의 resident bit 을 검사하고 1이면 page frame number(p')을 찾는다.
(4) p' * pageSize + d 가 REAL address가 된다.
(5) 만약 resident bit = 0이면 page fault가 발생한다. 해당 page를 swap device로부터 memory로 load해오기 위해 context switching이 발생한다.
(3-2) 만약 p가 없다면(miss❌), 주기억장치로 가서 메모리의 FULL PMT에서 p를 찾는다. p번 페이지의 resident bit 을 검사하고 1이면 page frame number(p')을 찾는다.
(4) p' * pageSize + d 가 REAL address가 된다.
(5) 만약 resident bit = 0이면 page fault가 발생한다. 해당 page를 swap device로부터 memory로 load해오기 위해 context switching이 발생한다.
대부분의 경우 자주 사용되는 것을 TLB에 잘 넣어둔다면 TLB HIT 확률이 80-90%이기 때문에 성능이 좋다.
그리고 자주 사용되기 때문에 TLB에 있는 페이지는 대부분 Residence Bit이 1이다. 반면 TLB가 아닌 FULL PMT에 있는 페이지는 대부분 Residence Bit이 0이다.
🔔 Effective Memory Access Time
