[ Demand Paging ]
물리적 메모리 주소 변환은 운영체제가 관여하지 않는다. 하지만 Virtual Memory 기법은 전적으로 운영체제가 관여를 하고 있다.
Demand Paging이라는 것은 Page 요청이 있으면 그 페이지를 메모리에 올리겠다는 것이다.
프로그램이 실행될 때, 그 프로세스를 구성하는 주소 공간을 한꺼번에 물리적 메모리에 올리는 게 아니라 요청이 있을 때 메모리에 올려놓는다.
이렇게 되면 I/O 양이 상당히 줄어들고 그만큼 물리적 메모리를 사용하는 양이 감소된다.
좋은 소프트웨어일수록 방어적으로 코드를 짜기 때문에 이상한 사용자가 이상한 짓을 하더라도 문제가 생기지 않도록 하는 것이 좋다.
즉 프로그램을 구성하는 주소 공간에서 빈번히 사용되는 부분은 제한적이므로 사용이 되지 않는 Page를 물리적 메모리에 올리면 메모리가 낭비된다.
요청이 있는 Page만 물리적 메모리에 올려놓게 되면 멀티프로그래밍 환경에서 더 많은 프로그램을 올릴 수 있다.
또한, 더 빠른 응답 시간을 얻을 수 있다. 실제 환경에서는 한정된 메모리 공간에 여러 프로그램들이 동시에 실행이 된다.
메모리가 한정되어 있기 때문에 빈번하게 사용되는 Page를 메모리에 올려놓기 위해서 Demand Paging 기법을 사용하는 게 좋다.
한정된 공간을 더 효율적으로 사용하므로 Disk I/O가 더 줄어들고 메모리에서 서비스하는 비율이 높기 때문에 응답 시간이 더 좋아진다.
✓ 실제로 필요할 때 Page를 메모리에 올리는 것
- I/O 양의 감소, Memory 사용량 감소, 빠른 응답 시간, 더 많은 사용자 수용
✓ Valid/Invalid Bit 사용
- Invalid : 사용되지 않는 주소 영역인 경우, 페이지가 물리적 메모리에 없는 경우
- 처음에는 모든 Page Entry가 Invalid로 초기화
- Address Translation 시에 Invalid Bit이 Set되어 있으면 "Page Fault"
● Memory에 없는 Page의 Page Table
논리 메모리는 하나의 프로그램을 구성하는 여러 개의 페이지들로 구성이 되어있으며 한쪽에는 Backing Store (Swap Area)가 있다.
당장 필요한 부분은 Demand Paing에 의해서 물리적 메모리에 올라가 있고 그렇지 않은 Page들은 Swap Area에 내려간다.
Page Table에는 페이지에 대한 주소 변환 정보와 Valid/Invalid의 정보가 담겨있다.
프로그램을 최초로 실행시키면 Valid/Invalid Bit는 모두 Invalid로 표시되며, 요청이 와서 메모리에 올라가는 페이지는 Valid로 바뀐다.
이 프로그램을 구성하는 A부터 F까지의 Page가 있다.
G와 H 번째 페이지는 사용되지 않는 Page이지만 주소 공간에서 주소 영역을 지원해 주기 때문에 Page Table에는 7번까지 Entry가 만들어진다.
Page Table에서 valid라고 표시되어 있는 0, 2, 5번 Page가 물리적 메모리 4, 6, 9번의 주소에 할당되며
Invalid라고 표시되어 있는 1, 3, 4번 Page는 물리적 메모리에 올라와 있지 않고 디스크에 내려가 있다.
예를 들어, CPU가 1번 Page를 주소 변환을 하려고 했는데 Invalid 이면, 메모리에 올라가 있지 않는 상태이므로 Page Fault가 발생한다.
그러면 그 페이지를 디스크에서 메모리로 올리는 I/O 작업을 하기 위해 CPU 제어권은 운영체제에게 넘어간다.
운영체제에는 Page Fault에 대한 인터럽트 처리 루틴을 통해 Fault 난 Page를 메모리에 올려야 한다.
운영체제는 먼저 잘못된 요청인지 아닌지 확인한 후, 주소가 잘못되어 있거나 접근 권한이 없을 때에는 Abort 시킨다.
정상적인 요청이라면 해당 페이지를 Disk에서 Memory로 올려줘야 하는데, 메모리가 꽉 차있다면 메모리에서 Page를 하나 쫓아내서 빈 메모리 공간을 얻는다.
그런 다음 Disk에서 읽어온 Page를 해당 메모리 주소에 올려놓는다.
Page Fault가 나면 운영체제는 Disk Controller에게 Fault 난 Page를 읽어오라고 요청한다.
그런데 디스크에서 메모리로 올리는 작업은 매우 느린 작업이기 때문에 디스크 I/O를 하게 되면 이 프로세스가 CPU를 갖고 있어 봐야 CPU가 낭비가 된다.
그래서 Disk Read 요청 후에 CPU를 뺏겨 Blocked 상태가 되고, 당장 실행할 수 있는 Ready 상태의 프로세스에게 CPU 제어권을 넘겨준다.
Disk Read가 끝나면 Page Table에 Page Frame 번호와 Valid를 표시해 놓는다.
그 후, Page Fault가 났던 프로세스가 CPU를 다시 잡고 메모리 주소 변환을 하게 되면 Page Fault가 나지 않고 MMU에 의해 주소 변환이 된다.
✓ Page Fault
- Invalid Page를 접근하면 MMU가 trap을 발생시킨다. (Page Fault Trap)
- Kernel Mode로 들어가서 Page Fault Handler가 Invoke 된다.
- Page Fault 처리 순서
- Invalid Reference ? (eg. Bad address, Protection Violation) → Abort Process
- Get an Empty Page Frame (없으면 뺏어온다. Replace)
- 해당 페이지를 Disk에서 Memory로 읽어온다.
- Disk I/O가 끝나기까지 이 프로세스는 CPU를 Preempt 당한다. (block)
- Disk Read가 끝나면 Page Table Entry 기록한다. Valid/Invalid Bit = "valid"
- Ready Queue에 Process를 Insert → Dispatch Later
- 이 프로세스가 CPU를 잡고 다시 Running 상태로 간다.
- 아까 중단되었던 Instruction을 재개한다.
● Steps in Handling a Page Fault
아래 그림은 Memory Reference를 요청했는데 메모리에 올라와 있지 않는 상태다.
그래서 Trap이 걸려 CPU 제어권이 운영체제에게 넘어가고 운영체제는 Backing Store에 있는 Page를 물리적 메모리로 가져온다.
비어있는 물리적 메모리 Frame이 있다면 메모리에 바로 올려놓고 비어있는 Frame이 없으면 메모리에 올라가 있는 Page 중 하나를 쫓아내고 거기다 올려논다.
올려놓는 작업이 끝났으면 Page Table Entry에 해당 페이지 Frame 번호를 올려놓고 Invalid를 Valid로 바꿔놓는다.
그 후, 나중에 CPU를 얻어 주소 변환을 하게 되면 Valid로 표시되어 있기 때문에 주소 변환을 정상적으로 하게 된다.
이렇게 되면 해당하는 물리적 메모리의 Page Frame에 접근할 수 있게 되는 것이다.
● Performance of Demand Paging
디스크에 접근하는 작업은 시간이 오래 걸리는 작업이기 때문에 Page Fault가 얼마나 나느냐에 따라서 메모리에 접근하는 시간이 크게 달라진다.
Page Fault 비율을 0에서 1로 볼 수 있는데, Page Fault 비율이 0이면 Page Fault가 나지 않고 메모리에서 다 참조가 되는 경우를 의미한다.
Page Fault Rate이 1이면 메모리에 참조할 때마다 항상 Page Fault가 일어난다는 의미이다.
실제로 Page Fault가 얼마나 일어나는지 시스템에서 조사를 해보면 1에 가까운 수로 나온다고 한다.
즉, 대부분의 경우에는 Page Fault가 일어나지 않고 메모리로부터 직접 주소 변환을 하며, Page Fault가 나서 Disk의 접근을 필요로 하는 경우는 많지 않다.
대부분의 경우에는 Page Fault가 나지 않지만 한 번 나면 많은 시간을 사용해야 한다.
Page Fault까지 감안해서 메모리에 접근하는 시간은 아래와 같다.
- (1-p)* memory access + p
- 1-p : Page Fault가 발생하지 않는 비율로 메모리에 접근하는 시간만 소요된다.
- p : Page Fault가 발생하는 비율이다. CPU 제어권이 운영체제로 넘어가서 하드웨어적으로 Page Fault를 처리하는 Overhead가 발생한다.
- 메모리에 빈 공간이 없으면 Page 하나를 쫓아내고 그 위치에 Disk에서 읽어온 Page를 올려 놓는다.
- 그 후, OS가 Page Table에 Valid를 표시하고 나중에 CPU를 다시 얻으면 Restart를 하는 과정에 있기 때문에 Overhead가 굉장히 크다.
✓ page fault rate 0 <= p <= 1.0
- if p=0 no page faults
- if p=1, every reference is a fault
✓ effective access time
- (1-p)* memory access + p (OS & HW page fault overhead + [swap page out if needed] + swap page in + OS & HW page restart overhead)
