1Processes and ThreadsChapter 22.1Processes2.2Threads2.3Inter-process communication2.4Classical IPC problems2.5Scheduling2Content of this lecturevWhy Scheduling?vWhen to Schedule?vBasic Scheduling AlgorithmBatch systemsvFirst-Come First-ServedvShortest job firstInteractive systemsvRound-robinvPriority schedulingvMulti Queue & Multi-level FeedbackvGuaranteed Scheduling, Lottery Scheduling, and Fair Sharing SchedulingvSummary3SchedulingvDeciding which process/thread should occupy the resource (CPU) to run next.(CPU (horsepower)Process 1Process 2Process 3I want to ride itWhose turn is it?4Process SchedulervProc1: 20 time unitsvProc2: 4 time unitsvProc3: 2 time unitsvPreemptive vs.non-preemptiveReady queueProc 1Proc 2Proc 3Proc 10Proc 11Proc 12Blocked queueCPUScheduler5Preemptive抢占式 vs. Non-preemptivevNon-preemptive scheduling:The running process keeps the CPU until it voluntarily gives up the CPU process exitsswitches to blocked state1and 4 only (no 3)Disadvantage?vPreemptive scheduling:The running process can be interrupted and must release the CPU (can be forced to give up CPU)Preemptive principles?RunningTerminatedReadyBlocked1436CPU SchedulingvProblem to solve When (scheduling opportunity) when to allocate CPU to process?What (scheduling algorithm) what is the principle of allocation?How (context - switch上下文切换) How to allocate CPU? scheduling- process? 71. Scheduling(Process Behavior)Bursts of CPU usage alternate轮流 with periods of I/O waita)a CPU-bound processb)an I/O bound process82. When to schedule?vA new process is createdvThe running process exitsvThe running process is blocked vI/O interrupt (some processes will be ready)vClock interrupt (every 10 milliseconds)93. Scheduling AlgorithmvFair (nobody cries)vPriority (lady first)vEfficiency (make best use of equipment)vEncourage good behavior (good boy/girl)vSupport heavy loads (degrade gracefully完全降低)vAdapt to different environments (interactive, real-time)Properties of a GOOD Scheduling Algorithm:10Performance CriteriavFairness vEfficiency: keep resources as busy as possible vPolicy Enforcement seeing that stated policy is carried outvThroughput: number of processes that completes in unit time vTurnaround Time (also called elapse time)amount of time to execute a particular process from the time its entered vWaiting Time amount of time process has been waiting in ready queue vResponse Time amount of time from when a request was first submitted until first response is produced. vProportionality meet users expectation vMeeting Deadlines: avoid losing data vPredictability11Different Systems, Different FocusesvFor allFairness, policy enforcement, resource balancevBatch SystemsMax throughput, min turnaround time, max CPU utilization vInteractive SystemsMin Response time, best proportionality vReal-Time Systemspredictability, meeting deadlines 12Single Processor Scheduling AlgorithmsvBatch systemsFirst Come First Serve (FCFS)Shortest Job FirstvInteractive SystemsRound RobinPriority SchedulingMulti Queue & Multi-level FeedbackGuaranteed SchedulingLottery SchedulingFair Sharing Scheduling13(1) First Come First Served (FCFS)vAlso called FIFO. Process that requests the CPU FIRST is allocated the CPU FIRST. vNon-preemptivevUsed in Batch Systems vImplementation: FIFO queuesA new process enters the tail of the queueThe scheduler selects from the head of the queue. vPerformance Metric度量标准: Average Waiting Time. vGiven Parameters: Burst Time (in ms), Arrival Time and Order 14FCFS ExampleProcessDurationOrderArrival TimeP12410P2320P3430The final schedule:0P1 (24)2427P2 (3) P3 (4)P1 waiting time: 0P2 waiting time: 24P3 waiting time: 27The average waiting time: (0+24+27)/3 = 1715Suppose that the processes arrive in the order P2 , P3 , P1 vThe Gantt chart for the schedule is:vWaiting time for P1 = 7; P2 = 0; P3 = 3vAverage waiting time: (7 + 0 + 3)/3 = 3.3vMuch better than previous case.vConvoy effect: short process behind long processFCFS Example (cont.)0P1 (24)37P2 (3) P3 (4)16Problems with FCFSvNon-preemptivevNot optimal AWT (Average Waiting Time)vCannot utilize resources in parallel:Assume 1 process CPU bounded and many I/O bounded processes result: Convoy effect, low CPU and I/O Device utilization Why?17Why Convoy Effects?vConsider n-1 jobs in system that are I/O bound and 1 job that is CPU bound. vI/O bound jobs pass quickly through the ready queue and suspend themselves waiting for I/O. vCPU bound job arrives at head of queue and executes until complete. vI/O bound jobs rejoin ready queue and wait for CPU bound job to complete. vI/O devices idle until CPU bound job completes. vWhen CPU bound job complete, other processes rush to wait on I/O again. vCPU becomes idle. 18(2) Shortest Job First (SJF)vSchedule the job with the shortest elapse time firstvScheduling in Batch Systems vTwo types:Non-preemptivePreemptivevRequirement: the elapse time needs to know in advancevOptimal if all the jobs are available simultaneously (provable) Gives the best possible AWT (average waiting time)19Non-preemptive SJF: ExampleProcessDurationOrderArrival TimeP1620P2840P3730P4310P4 waiting time: 0P1 waiting time: 3P3 waiting time: 9P2 waiting time: 16The total time is: 24The average waiting time (AWT): (0+3+9+16)/4 = 703P4 (3)P1 (6)9P3 (7)16P2 (8)2420Comparing to FCFSProcessDurationOrderArrival TimeP1610P2820P3730P4340P1 waiting time: 0P2 waiting time: 6P3 waiting time: 14P4 waiting time: 21The total time is the same.The average waiting time (AWT): (0+6+14+21)/4 = 10.25(comparing to 7)06P4 (3)P1 (6)14P3 (7)21P2 (8)2421SJF is not always optimalvIs SJF optimal if all the jobs are not available simultaneously?Process Duration Order Arrival TimeP11010P2222010P1 (10)P1 waiting time: 0P2 waiting time: 8The average waiting time (AWT): (0+8)/2 = 4P2 (2)2 (p2 arrives)1222What if the scheduler waits for 2 time units? (Do it yourself)P1 waiting time: 4P2 waiting time: 0The average waiting time (AWT): (0+4)/2 = 2However: waste 2 time units of CPU0142 ProcessDurationOrderArrival TimeP11020P2212P1 (10)P2 (2)423Preemptive SJFvAlso called Shortest Remaining Time FirstSchedule the job with the shortest remaining time required to completevRequirement: the elapse time needs to be known in advance24Preemptive SJF: Same ExampleProcessDurationOrderArrival TimeP11010P2222P1 waiting time: 4-2 =2P2 waiting time: 0The average waiting time (AWT): (0+2)/2 = 1No CPU waste!0122 P1 (8)P2 (2)4P1 (2)25A Problem with SJFvStarvationIn some condition, a job is waiting for everExample: SJFvProcess A with elapse time of 1 hour arrives at time 0vBut ever 1 minute from time 0, a short process with elapse time of 2 minutes arrivevResult of SJF: A never gets to run26Interactive Scheduling AlgorithmsvUsually preemptiveTime is sliced切开 into quantum (time intervals)Scheduling decision is also made at the beginning of each quantumvPerformance CriteriaMin Response Timebest proportionality vRepresentative有代表性的 algorithms:Round-robinPriority-basedMulti Queue & Multi-level FeedbackGuaranteed SchedulingLottery SchedulingFair Sharing Scheduling27(3) Round-robin轮转调度 vOne of the oldest, simplest, most commonly used scheduling algorithmvSelect process/thread from ready queue in a round-robin fashion (take turns)Problem: Do not consider priority Context switch overhead28Round-robin: ExampleProcessDurationOrderArrival TimeP1310P2420P33300Suppose time quantum is: 1 unit, P1, P2 & P3 never blockP1 P2 P310P1 P2 P3 P1 P2 P3 P2P1 waiting time: 4P2 waiting time: 6P3 waiting time: 6 The average waiting time (AWT): (4+6+6)/3 = 5.3329Time Quantum时间段vTime slice too largeFCFS behavior Poor response timevTime slice too smallToo many context switches (overheads) Inefficient CPU utilizationvHeuristic: 70-80% of jobs block within time-slice vTypical time-slice 10 to 100 ms 30(4) Priority SchedulingvEach job is assigned a priority. vFCFS within each priority level. vSelect highest priority job over lower ones.vRational合理的: higher priority jobs are more mission-criticalExample: display a video film in real time vs. send emailvProblems:May not give the best AWTindefinite无限的 blocking or starving a process 31Set PriorityvTwo approachesStatic (for system with well known and regular application behaviors)Dynamic (otherwise)vPriority may be based on: Cost to userImportance of userProcess typeRequirement to resource Aging Percentage of CPU time used in last X hours.32Priority Scheduling: ExampleProcessDurationPriorityArrival TimeP1640P2810P3730P432008P4 (3)P1 (6)11P3 (7)18P2 waiting time: 0P4 waiting time: 8P3 waiting time: 11P1 waiting time: 18The average waiting time (AWT): (0+8+11+18)/4 = 9.25(worse than SJF:7)P2 (8)2433Priority in Unix34Be “nice” in UnixNobody wants to35(5) Multi-Queue SchedulingvHybrid between priority and round-robinvProcesses assigned to one queue permanently vScheduling between queues Fixed Priorities % CPU spent on queue vExample System processes (highest priority)Interactive programs (Round Robin)Background Processes (FCFS)Student Processes 36Multi-Queue Scheduling: Example20%50%30%37Real Life AnalogyvTasks (to-do list) for poor BobClass 1 priority (highest): tasks given by his bossvFinish the project (50%)Class 2 priority: tasks for his wifevBuy a valentine present (30%)Class 3 priority (lowest): Bobs tasksvWatch TV (20%)38(6)A Variation: Multi-level Feedback AlgorithmvMulti-Level Queue with priorities vProcesses move between queues vEach queue represents jobs with similar CPU usagevJobs in a given queue are executed with a given time-slice vRational:Once an I/O process completes an I/O request, it should have higher CPU priority.39 Multi-level Feedback Algorithm (Details)vExample (CTSS): Queuei has time-slice t 2i If a job in Queuei doesnt block by end of time-slice, it is moved to Queuei+1Lowest priority Queue is FCFS40Multi-level Feedback Algorithm: Example41Review: Scheduling AlgorithmsvBatch systemsFirst come first serve Shortest job firstvInteractive systemsRound-robinPriority schedulingMulti-Queue & Multi-level feedback42(7) Guaranteed Scheduling (QoS)vMake real promises to the users about performance and then live up to them.vExample:with n processes running, the scheduler makes sure that each one gets 1/n of the CPU cycles.vScheduling:compute the ratio of actual CPU time consumed to CPU time entitledSelect the one with the lowest ratio43(8) Lottery SchedulingvMore commonly usedvProbability机率-based:Give processes lottery tickets. At scheduling time, a lottery ticket is chosen at random, and the process holding that ticket gets that resource. vGive more tickets for higher priority processesvAdvantages:SimpleHighly responsiveCan support cooperation between processesEasy to support priority and proportion requirement44(9) Fair-Share SchedulingvIs Round-robin fair?Yes, it is (from process point of view)No, it may be not (from user point view)vUser-based fair share schedulingEach user gets fair sharevExample:Alice has 4 processes: A1, A2, A3, A4Bob has 1 process: B1Then A1, A2, A3, A4 are entitled only to 50% CPU, while B1 alone is entitled to 50%Possible scheduling sequence: A1,B1,A2,B1,A3,B1,A4,B1,45Scheduling in Real-Time SystemsvThe scheduler makes real promises to the user in terms of deadlines or CPU utilization.vSchedulable real-time systemGivenvm periodic周期的 eventsvevent i occurs within period Pi and requires Ci secondsThen the load can only be handled if46User-level Thread SchedulingPossible Scheduling v50-msec process quantumvrun 5 msec/CPU burst47Kernel-level Thread SchedulingPossible scheduling v50-msec process quantumvthreads run 5 msec/CPU burst48SummaryvWhat is schedulingvScheduling objectivesvCPU SchedulingvFCFSvShortest job first (SJF)vPriorityvRound-robinvMulti-QueuevMulti-level Feedback lScheduling algorithmsGuaranteed SchedulingLottery SchedulingFair Sharing SchedulinglScheduling forReal-time systemsThreads49Homeworkv37、38、45、46、47、51