What is a lower bound on the number of page faults?
모든 페이지 번호가 sequence에서 연달아 순차적으로(11..122..2..)등장한다고 가정하면, 서로 다른 페이지 개수인 n이 최소 page fault 발생 횟수이다.
What is an upper bound on the number of page faults?
최악의 경우 모든 페이지 요청에 대한 page fault가 발생하며, 횟수는 p이다.
CPU가 요청한 페이지는 아래와 같이 분류된다. 오래 걸리는 경우일수록 아래에 위치한다. 하위 경우는 상위 경우를 상속하며, 상위 경우의 실행 시간에 해당 경우의 사건에 의한 시간이 가산된다. 괄호 안은 발생 확률을 의미한다.
access time = rotation latency + (data size / transfer rate) = 10000 + 1000 = 11000 μs
3000 회전 / 60 s = 50 회전 / s ⇒ 원하는 sector 찾는데 평균적으로 반 바퀴 회전한다고 가정하면 rotational latency = 1/50 * 1/2 = 0.01 s = 10000 μs
transfer rate = 1 word / 1 μs = 1000 word / 1000μs ⇒ 1 page 옮기는데 1000 μs 걸림
instruction time (μs) = 0.99 * 1 + 0.008 * 2 + 0.001 * 11002 + 0.001 * 22002 = 34.01 μs
12-bit virtual and physical addresses and 256-byte pages.
word size가 1byte라고 가정하면, page 내의 word 개수는 2^8이고 address의 offset은 8비트이다.
그렇다면 address 앞의 4비트가 page 및 frame 번호를 의미한다.
문제에 주어진 4개의 virtual address에 대한 CPU의 요청이 들어왔다고 하자.
free frame list = [D, E, F]이고, pop 연산은 앞의 원소부터 제거한다.