CS计算机代考程序代写 data structure algorithm cache Operating Systems CMPSC 473

Operating Systems CMPSC 473
Page Replacement Lectures 16, 17: March 18, 23, 2021 Instructor: Bhuvan Urgaonkar

Administrative
• IwelcomefeedbackonExam1
– E.g.,finalwillbemostlysimilarbutwillbeopen-notes
• Project 2 and Exam 1 grades should be out by next Tuesday
– Will have completed 45% of your overall grades • Project 1: 15; Project 2: 20; Exam 1: 10
– Will show you a histogram to help you gauge how you are doing

Administrative
– Asimulatorforamulti-taskingcomputerwithvirtualmemoryusinga round-robin CPU scheduler
– You are to implement MMU, TLB, DRAM, multi-level page tables, swap device, page replacement policies (LRU and Clock) – 60%
– You are to carry out specified performance evaluation – 40%
– TAs will post a short video overviewing the codebase they have prepared
– No checkpoints this time; deadline April 8th
• Project 3 will be out later today (?)

Selected problems from Exam 1

Quiz 16.1
• CalculateaveragecompletiontimefortwoprocessesA and B arriving at t=0 and t=1, respectively. Quantum length is 1. A’s duration is 10, B’s duration is 2. They never trap and the only interrupt that arrives is the timer interrupt. Assume the following scheduling policies:
– FIFO – SJF
– SRPT – RR
– Lottery (equal weights)

Quiz 16.2
• Calculatethroughput(inprocessing/sec)forasystem with two processes A and B arriving at t=0 and t=1, respectively. Quantum length is 1. A’s duration is 10, B’s duration is 2. They never trap and the only interrupt that arrives is the timer interrupt. Assume the following scheduling policies:
– FIFO – SJF
– SRPT
– RR
– Lottery (equal weights)

Quiz 16.3
• Calculatethroughput(inprocessing/sec)forasystem with two processes A and B arriving at t=0 and t=1, respectively. Quantum length is 1. A’s duration is 10, B’s duration is 2. They never trap and the only interrupt that arrives is the timer interrupt. Assume context switching requires 0.01 units of time. Assume the following scheduling policies:
– FIFO – SJF
– SRPT – RR
– Lottery (equal weights)

Quiz 16.4
• Consider the SRPT scheduling policy. What data structure would you choose for implementing the ready/running and blocked
queues of processes. Keep in mind that the following updates need to be handled efficiently:
– Arrivalofanewprocess
– Departureofaprocess
– Occurrenceofatrap
– Occurrenceofaninterrupt
– Selectionofnextprocesstorun
• RepeatthisforFIFO,SJF,RR,Lottery

Unsorted linked list of PCBs
Sorted linked list of PCBs
Balanced tree (heap)
Arrival
O(1)
O(n)
O(lg n)
Departure
O(1)
O(1)
O(1)
Trap
O(1)
O(1)
O(1)
Interrupt
O(n)
O(n)
O(lg n)
Scheduler
O(n)
O(1)
O(lg n)
Error in recorded video: This should be O(log n) not O(1)

• Covered so far:
Paging-based VMM
– Cooperation between MMU, TLB, page tables, swap device • Handlingofpagefaults
– Designofpagetables
• Remaining concerns:
– When to bring a page into DRAM?
• Proactive:pre-fetching
• Reactive/lazy: “demand paging”
– Which pages to keep and which to evict?
– When to write “dirty” pages back to swap?
• Proactive vs. lazy
Our focus

Page Replacement Algorithms
• Objectivewewillworkwith:Minimizepagefaultrate
• Evaluate algorithm by running it on a particular string of memory references (reference string) and computing the number of page faults on that string
• Inallourexamples,thereferencestringis
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5

Graph of Page Faults Versus The Number of Frames

First-In-First-Out (FIFO) Algorithm
• Referencestring:1,2,3,4,1,2,5,1,2,3,4,5
• 3 frames (3 pages can be in memory at a time per process)
11
2 33
45
2 1 3 9 page faults
24
Error in recorded video: This should have been a hit (H)

First-In-First-Out (FIFO) Algorithm
• Referencestring:1,2,3,4,1,2,5,1,2,3,4,5
• 3 frames (3 pages can be in memory at a time per process)
1
2
3
1 2
3
1 2
45 1 3
24
54 1 5 2
9 page faults
1
2
3
4
• 4 frames
3 43
• Belady’s Anomaly: more frames cause more page faults!!!
10 page faults

FIFO example: on your own

FIFO Illustrating Belady’s Anomaly

03/23 – Administrative
• Grades out for Project 2 are out, delayed for Exam 1
– Incaseofconcernswithyourgrades,emailONLYtherelevantTAs
– Exam 1: Avik, Vijay, Avimita
– Project 2: Raj, Rubaba, Ranjitha
• AIconcernsforProject2
– Unprofessional
– Unfairtoothers
• Inflated grades for cheatersL
• Has already caused delays in Exam 1 grading, Project 3 video, pending details of evaluation
• Project 3:
– Video coming out on Wednesday 03/24
– # members allowed per team increased to 3

03/23 – Administrative
• GradesforProject2

Optimal Algorithm
• Replace page that will not be used for longest period of time • 4framesexample
1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5
1
2
3
4
• Whatisthedifficulty?
4
5
6 page faults

How can we approximate optimal?
• Recall temporal locality
• Corollary: A page that has not been used for a long time will likely not be used for a long time
• Heuristic called “Least Recently Used” (LRU)
– Evict the page that has not been accessed for the longest time

Locality In A Memory-Reference Pattern

LRU Example
• Referencestring: 1,2,3,4,1,2,5,1,2,3,4,5
1
2
5
3
1
2
4
3
1
2
3
4
5
2
4
3
1
2
5
4

Stack Algorithms
• A class of page replacement algorithms for which the set of pages in DRAM with n frames is always a subset of the set of pages in DRAM with n+1 frames
• Belady’s anomaly iff not a stack algorithm
• Both OPT and LRU are stack algorithms
• FFT: Prove these – Not on syllabus

LRU Implementation
• Need a data structure to maintain page access times (“timestamps”)
– These timestamps could be embedded in the page table entries
• Two operations
– Update timestamp upon reference (hit or miss)
– Choose page with lowest timestamp when need to evict (miss and DRAM full)

LRU Algorithm (Cont.)
• Which data structure to use? Let n denote # pages in DRAM
Unsorted linked list
Sorted linked list
Priority queue
Hash table
Access
Insert w/o eviction
Replace (Evict then insert)

LRU Algorithm (Cont.)
• Which data structure to use? Let n denote # pages in DRAM
Unsorted linked list
Sorted linked list
Priority queue
Hash table
Access
O(n)
O(n)
O(log n)
O(1)
Insert w/o eviction
O(1)
O(1)
O(log n)
O(1)
Replace (Evict then insert)
O(n)
O(1)
O(log n)
O(n)

Cost of Maintaining Exact LRU
• Unfortunately, even hash tables are likely to be too expensive
– On every reference (load/store): • Compute hash of page address
• Update time stamp
• Can we do better?

LRU Approximation Algorithms: Hardware Support
• Associate with each page a single bit called the “reference bit”
– Set to 1 whenever a page is referenced
• Reference bits cleared periodically at a coarse timescale
– E.g., in response to some timer interrupts

LRU Approximation: The Clock Algorithm (“Second Chance”)
• Keepframesincircle
• Uponreference,bitsetto1
• Onpagefault,OS:
– Checksreferencebitof
next frame
– Ifbit=0,replacepage,
set bit to 1
– Ifbit=1,setbitto0,
advance pointer to next frame
Fernando Corbato, passwords, MULTICS,Turing award

• Keepframesincircle
• Uponreference,bitsetto1
• Onpagefault,OS:
– Checksreferencebitof
next frame
– Ifbit=0,replacepage,
set bit to 1
– Ifbit=1,setbitto0,
advance pointer to next frame
The Clock Algorithm
B 1
A 1
C 1
D 1
A, B, C, D, B, A, E, F, C, G

Variants
• Preferentiallyevictpageswithref=0,dirty=0
• Least Frequently Used (LFU)
• FFT: sometimes better page replacement algorithms are MRU or MFU – when?

Fairness concerns and/or effects of high multi-programming

Working Set Model
• Idea, history
• Co-design of CPU scheduler and page replacement
Peter Denning

Interlude: the “big” ideas so far (and to come)
• Exploit locality
– Caches everywhere!
• “Nofreelunch”
– Space-timetradeoffs
• Softwarevs.hardwareimplementationimplications
– Whenever possible, implement common work in h/w and leave specialized work to OS
• Use simple heuristics to “learn” workload properties and/or adapt to uncertainty
– Optimizeforthecommoncase
• Avoid context switching when possible

Quiz 17.1
• How many page faults would the following reference string experience with OPT?

Quiz 17.2
• How many page faults would the following reference string experience with LRU?

Quiz 17.3
• Consider a demand-paging system with the following time-measured utilizations: CPU util = 20%, Paging disk (swap device) = 97.7%, Other I/O devices = 5%. For each of the following, say whether it will (or is likely to) improve CPU utilization. Explain your answer.
– InstallafasterCPU
– Install a bigger swap device
– Increasethedegreeofmulti-programming
– Decreasethedegreeofmulti-programming
– Install more main memory
– Install a faster hard disk (on which the swapping device resides)
– Increase the page size

Refs vs. LRU Qlength
• An interesting and useful data structure
# memory references
0 P-1 V-1
LRU queue position

•
Quiz 17.4
Q5: Consider a system with the following #memory refs vs. LRU queue position curve
1000
0
1000
If the following two computers cost the same, which would you buy 1. CPU = 2GHz, RAM = 400pages
2. CPU = 1GHz, RAM = 500pages
Assume memory access time of 100 cycles and swap access time of 100,000 cycles. Ignore memory needed to store page tables, ignore the TLB.

Related Posts