Scheduling.html (7086B)
1 <?xml version="1.0" encoding="UTF-8"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3 <html><head><link rel="stylesheet" href="sitewide.css"><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/><meta name="exporter-version" content="Evernote Mac 7.6 (457297)"/><meta name="altitude" content="-1.633376002311707"/><meta name="author" content="Alex Balgavy"/><meta name="created" content="2018-12-03 16:08:06 +0000"/><meta name="latitude" content="52.33331298828125"/><meta name="longitude" content="4.866615317820796"/><meta name="source" content="desktop.mac"/><meta name="updated" content="2018-12-03 16:08:37 +0000"/><title>Scheduling</title></head><body><div><img src="Scheduling.resources/09C0D52D-0C2A-4E90-BF83-3EA6ACFC8CAC.png" height="309" width="460"/><br/></div><div style="margin-top: 1em;margin-bottom: 1em;-en-paragraph:true;"><span style="-en-paragraph:true;">if more processes ready than CPUs available:</span></div><ul><li><div>scheduler decides which process to run next</div></li><li><div>algorithm used by scheduler is called scheduling algorithm</div></li></ul><div style="margin-top: 1em;margin-bottom: 1em;-en-paragraph:true;"><span style="-en-paragraph:true;">when to schedule?</span></div><ul><li><div>process exits</div></li><li><div>process blocks on IO or semaphore</div></li><li><div>when new process is created</div></li><li><div>when IO interrupt occurs</div></li><li><div>when clock interrupt occurs</div></li></ul><div style="margin-top: 1em;margin-bottom: 1em;-en-paragraph:true;"><span style="-en-paragraph:true;">scheduling #goals</span></div><ul><li><div>different goals for batch, interactive, or real time systems</div></li><li><div>for all systems: 4 </div></li><ul><li><div>fairness: giving each process a fair share of CPU</div></li><li><div>policy reinforcement: carrying out stated policy</div></li><li><div>balance: keeping all parts of system busy</div></li><li><div>throughput: maximise jobs per hour</div></li><li><div>turaround time: minimise time between submission and termination</div></li><li><div>CPU utilisation: keepin CPU busy <span style="font-style: italic;">all the time</span></div></li></ul></ul><div style="margin-top: 1em;margin-bottom: 1em;-en-paragraph:true;"><span style="-en-paragraph:true;">Batch scheduling algorithms:</span></div><ul><li><div>First-Come First-Served (FIFO) 5 </div></li><ul><li><div>process jobs in order of arrival</div></li><li><div>non-preemptive</div></li><li><div>single process Q: 6 </div></li><ul><li><div>new jobs or blocking processes are added to end of Q</div></li></ul><li><div>can lead to "convoy effect" if only few CPU bound and many IO bound processes</div></li></ul><li><div>Shortest job first: 7 </div></li><ul><li><div>pick job with the shortest run time</div></li><li><div>provably optimal: lowest turnaround time</div></li><li><div>of course, runtimes have to be known in advance</div></li><li><div>may lead to starvation, if a lot of short-lived processes arrive then a long run-time process will never run</div></li><li><div>highest-response-ratio-next -- improved version of shortestjob first</div></li></ul></ul><div style="margin-top: 1em;margin-bottom: 1em;-en-paragraph:true;"><span style="-en-paragraph:true;">Interactive scheduling:</span></div><ul><li><div>response time -- respond to requests quickly</div></li><li><div>proportionality -- meet users' expectations</div></li><li><div>algorithms: 8 </div></li><ul><li><div>round robin scheduling: 9 </div></li><ul><li><div>preemptive algorithm</div></li><li><div>each process gets a time slice (quantum)</div></li><li><div>if process is still running at end of quantum, it gets preemted & goes to end of ready Q</div></li><li><div>how big should that quantum be? depends on the implementation (lol when does it not depend) 10 </div></li><ul><li><div>of course, you don't want most of the time to be context switching</div></li></ul></ul><li><div>priority scheduling 11 </div></li><ul><li><div>similar to round robin, but several ready Qs</div></li><li><div><img src="Scheduling.resources/643D34DE-D587-463D-86B8-F9A35F934198.png" height="168" width="407"/></div></li><li><div>next process is picked from Q with highest priority</div></li><li><div>static vs dynamic 12 </div></li><ul><li><div>static priority: there is a single unchanging priority. often used as base priority level.</div></li><li><div>dynamic priority: OS cleverly decides which processes should have higher priorities (e.g. if IO bound, should have higher priority than CPU bound)</div></li></ul><li><div>but can lead to priority inversion (e.g. Pathfinder). solutions: 13 </div></li><ul><li><div>priority ceiling protocol: mutex gets priority assigned of the highest priority process that might lock the mutext</div></li><li><div>priority inheritance protocol: high priority process blocks because low priority process hold mutex -> low priority process 'inherits' priority of blocked process</div></li><li><div>random boosting: ready processes holding mutexes are temporarily (and randomly) boosted in priorities</div></li></ul><li><div>how to minimise response time for each priority Q? shortest process next: 14 </div></li><ul><li><div>use shortest job first and try to best predict next running time</div></li><li><div>form weighted average of previous running times of processes</div></li></ul></ul><li><div>guaranteed scheduling 15 </div></li><ul><li><div>N processes running -> each process gets 1/Nth of CPU time (aka fair-share)</div></li><li><div>calc how much CPU time process might have gotten (time since process creation divided by N)</div></li><li><div>measure actual consumed CPU time</div></li><li><div>form ratio (e.g. 0.5 means process running for half the time it was entitled to)</div></li><li><div>pick process with smallest ratio to run next</div></li></ul><li><div>lottery scheduling</div></li><ul><li><div>processes get lottery tickets</div></li><li><div>whenever scheduling decision has to be made, OS chooses winning ticket randomly</div></li><li><div>processes can have multiple tickets & priorities</div></li><li><div>tickets can be traded between processes</div></li></ul></ul></ul><div style="margin-top: 1em;margin-bottom: 1em;-en-paragraph:true;"><span style="-en-paragraph:true;">real time systems</span></div><ul><li><div>main concerns: 16 </div></li><ul><li><div>meeting deadlines - avoid using data</div></li><li><div>predictability - avoid quality degradation in multimedia systems</div></li></ul><li><div>soft real time vs hard real time (cannot miss any deadlines)</div></li><li><div>can consist of periodic and aperiodic tasks</div></li><li><div>schedules can be static (schedules are known in advance) or dynamic (make scheduling decisions during execution)</div></li><li><div>system with periodic tasks is schedulable when we can meet the deadlines</div></li></ul><div style="margin-left: 40px;"><img src="Scheduling.resources/AC15C36D-9C69-4389-B190-480FA7BACF45.png" height="455" width="984"/><br/></div><div><br/></div></body></html>