Recall that Shortest Remaining Time First (SRTF) is a variant of Shortest Job Fi
ID: 3856351 • Letter: R
Question
Recall that Shortest Remaining Time First (SRTF) is a variant of Shortest Job First (SJF) with preemption added in. Consider the following three processes
for the CPU. The scheduler uses SRTF. The scheduler re-evaluates which process to run only upon the arrival of a new process into the
scheduling queue, or the completion of a process. The table shows the arrival time of each process.
Process
Arrival Time
Execution Time
P1
T0
5 ms
P2
T0 + 2 ms
4 ms
P3
T0 + 3 ms
1 ms
The scheduling starts at time T0.
Fill up the blank cell/cells in the table below with the appropriate time information.
(a) At time T0: (2 points)
Process
Remaining Time
P1
P2
Not Arrived Yet
P3
Not Arrived Yet
(b) At time T0 + 2 ms : (Process P2 arrives) (4 points)
Process
Remaining Time
P1
P2
P3
Not Arrived Yet
(c) At time T0 + 3 ms: (Process P3 arrives) (4 points)
Process
Remaining Time
P1
P2
P3
(d) Fill in the table below with the process that is executing on the processor during each time slot (the first slot has been filled up with Process P1). (10 points)
Interval T0 +
0 ms
1 ms
2 ms
3 ms
4 ms
5 ms
6 ms
7 ms
8 ms
9 ms
10 ms
11 ms
12 ms
Running Process
P1
Process
Arrival Time
Execution Time
P1
T0
5 ms
P2
T0 + 2 ms
4 ms
P3
T0 + 3 ms
1 ms
Explanation / Answer
Under what circumstances do page faults occur? Describe the actions taken by the operating system when a page fault occurs. Answer: A page fault occurs when an access to a page that has not been brought into main memory takes place. The operating system verifies the memory access, aborting the program if it is invalid. If it is valid, a free frame is located and I/O is requested to read the needed page into the free frame. Upon completion of I/O, the process table and page table are updated and the instruction is restarted. 9.2 Assume that you have a page-reference string for a process with m frames (initially all empty). The page-reference string has length p; n distinct page numbers occur in it. Answer these questions for any page-replacement algorithms: a. What is a lower bound on the number of page faults? b. What is an upper bound on the number of page faults? Answer: a. n b. p 9.3 Consider the page table shown in Figure 9.30 for a system with 12-bit virtual and physical addresses and with 256-byte pages. The list of free page frames is D, E, F (that is, D is at the head of the list, E is second, and F is last). Convert the following virtual addresses to their equivalent physical addresses in hexadecimal. All numbers are given in hexadecimal. (A dash for a page frame indicates that the page is not in memory.) • 9EF • 111 29 30 Chapter 9 Virtual Memory • 700 • 0FF Answer: • 9E F - 0E F • 111 - 211 • 700 - D00 • 0F F - EFF 9.4 Consider the following page-replacement algorithms. Rank these algorithms on a five-point scale from “bad” to “perfect” according to their page-fault rate. Separate those algorithms that suffer from Belady’s anomaly from those that do not. a. LRU replacement b. FIFO replacement c. Optimal replacement d. Second-chance replacement Answer: Rank Algorithm Suffer from Belady’s anomaly 1 Optimal no 2 LRU no 3 Second-chance yes 4 FIFO yes 9.5 Discuss the hardware support required to support demand paging. Answer: For every memory-access op
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.