index.md (4386B)
1 +++ 2 title = 'Scheduling' 3 +++ 4 # Scheduling 5  6 if more processes ready than CPUs available: 7 8 - scheduler decides which process to run next 9 - algorithm used by scheduler is called scheduling algorithm 10 11 when to schedule? 12 13 - process exits 14 - process blocks on IO or semaphore 15 - when new process is created 16 - when IO interrupt occurs 17 - when clock interrupt occurs 18 19 scheduling #goals 20 21 - different goals for batch, interactive, or real time systems 22 - for all systems: 23 - fairness: giving each process a fair share of CPU 24 - policy reinforcement: carrying out stated policy 25 - balance: keeping all parts of system busy 26 - throughput: maximise jobs per hour 27 - turaround time: minimise time between submission and termination 28 - CPU utilisation: keepin CPU busy *all the time* 29 30 Batch scheduling algorithms: 31 32 - First-Come First-Served (FIFO) 33 - process jobs in order of arrival 34 - non-preemptive 35 - single process Q: 36 - new jobs or blocking processes are added to end of Q 37 - can lead to "convoy effect" if only few CPU bound and many IO bound processes 38 - Shortest job first: 39 - pick job with the shortest run time 40 - provably optimal: lowest turnaround time 41 - of course, runtimes have to be known in advance 42 - may lead to starvation, if a lot of short-lived processes arrive then a long run-time process will never run 43 - highest-response-ratio-next -- improved version of shortestjob first 44 45 Interactive scheduling: 46 47 - response time -- respond to requests quickly 48 - proportionality -- meet users' expectations 49 - algorithms: 50 - round robin scheduling: 51 - preemptive algorithm 52 - each process gets a time slice (quantum) 53 - if process is still running at end of quantum, it gets preemted & goes to end of ready Q 54 - how big should that quantum be? depends on the implementation (lol when does it not depend) 55 - of course, you don't want most of the time to be context switching 56 - priority scheduling 57 - similar to round robin, but several ready Qs 58 -  59 - next process is picked from Q with highest priority 60 - static vs dynamic 61 - static priority: there is a single unchanging priority. often used as base priority level. 62 - dynamic priority: OS cleverly decides which processes should have higher priorities (e.g. if IO bound, should have higher priority than CPU bound) 63 - but can lead to priority inversion (e.g. Pathfinder). solutions: 64 - priority ceiling protocol: mutex gets priority assigned of the highest priority process that might lock the mutext 65 - priority inheritance protocol: high priority process blocks because low priority process hold mutex -> low priority process 'inherits' priority of blocked process 66 - random boosting: ready processes holding mutexes are temporarily (and randomly) boosted in priorities 67 - how to minimise response time for each priority Q? shortest process next: 68 - use shortest job first and try to best predict next running time 69 - form weighted average of previous running times of processes 70 - guaranteed scheduling 71 - N processes running -> each process gets 1/Nth of CPU time (aka fair-share) 72 - calc how much CPU time process might have gotten (time since process creation divided by N) 73 - measure actual consumed CPU time 74 - form ratio (e.g. 0.5 means process running for half the time it was entitled to) 75 - pick process with smallest ratio to run next 76 - lottery scheduling 77 - processes get lottery tickets 78 - whenever scheduling decision has to be made, OS chooses winning ticket randomly 79 - processes can have multiple tickets & priorities 80 - tickets can be traded between processes 81 82 real time systems 83 84 - main concerns: 85 - meeting deadlines - avoid using data 86 - predictability - avoid quality degradation in multimedia systems 87 - soft real time vs hard real time (cannot miss any deadlines) 88 - can consist of periodic and aperiodic tasks 89 - schedules can be static (schedules are known in advance) or dynamic (make scheduling decisions during execution) 90 - system with periodic tasks is schedulable when we can meet the deadlines 91 92 