Operating Systems CMPSC 473
Project 3
April 1, 2021 – Lecture 20 Instructor: Bhuvan Urgaonkar
Interlude: Simulation
• Basicsofdiscrete-eventsimulation
• Discussion of Project 3 codebase and some tips
• Somereductionoftasks,deadlineextension(and implications for Project 4)
Simulation: what and why?
• Twofundamentalwaysofevaluatingasystem
• Build it! (or a smaller version of it called a “prototype”)
• Model it
• Modeling a system
• Analytical model
• Simulation
• Key pros and cons:
• Time (and generally $) investment: Prototype > Simulation > Analytical model
• Expertise: Analytical model > Prototype > Simulation
• Accuracy: Prototype > Simulation > Analytical model
• In practice, used iteratively and, sometimes, in combination with each other
Discrete-event simulation
• The system being described can be modeled as a state machine whose state changes in response of “events” at discrete time units
• Key concepts:
• Simulated time – should correctly reflect when events of importance occur over time
• State:allthevariableswithinyourprogramthatmimicsomeaspectofthe operation of your system or measure some aspect of its performance
• Events: external vs. internal
Discrete-event simulation
• Implementingthesimulatorconsistsofensuringthatalleventsare considered and handled correctly
• Each event has:
• An arrival time
• An occurrence time
• Otherpropertiesthatdescribehowitwillaffectthestate
• Handlingofaneventcanhavethefollowingeffects:
• Changeinthestateofthesystem
• Creationofmoreeventsinthefuture
• Update/removalofsomependingevents
• Updating of the simulated time
• Our simulator is simpler that the above general case
Canonical Simulator
Initialize state s and eventQ; t=0;
while (1) {
add events arising at time=t to eventQ e = pop (eventQ);
t = e.occurence_time;
simulate (e);
// change s
// add/update eventQ
if termination condition break; }
Initialize state s and eventQ; t=0;
while (1) {
e = pop (eventQ);
t = e.occurence_time; simulate (e);
// change s
// add to eventQ // update t
if termination condition break; }
Mapping to our codebase: simulate()
init() line 4-53
init() line 6
simulate() line 269-272 (Add first event into eventQ) simulate() line 277
readPage() line 115
readPage() line 116
• nextMem -> nextInstruction
• readPage -> simulateInstruction
simulate() line 285-304, 323-324 simulate() line 344-352
simulate() line 359-441 simulate() line 384, 395, 409, 439
• processSimulate -> simulateNextRun
• diskToMemory -> simulatePFHandling
Other Notes:
Page fault – > create disk interrupt event line 179-185
Line 307 -> servicing of disk interrupt and if needed, page replacement – if (simPause == 0) {…} Line 128-132 -> detection of page fault / tlb miss
Line 335 -> argument to schedulingRR() is not needed
If nothing to run at this time Add next event e to eventQ; t = e.occurrence_time;
•
Updates to Project 3 scope, deadline, OHs
Reduced scope
• No need to implement or evaluate OPT page replacement • Implementing and evaluating CLOCK optional
• if you implement it, you will get 10% extra credits Additional time
• New deadline will be April 15
Additional office hours between now and deadline:
• Instructor: Thursdays 1:30-3:30 pm, Fridays: 3-5 pm
• TAs (Rubaba, Avimita, Vijay) will send an announcement re. any additional OHs they might be able to offer
• •