操作系统英文课件：ch2 Processes and Threads c

1、1Processes and ThreadsChapter 22.1Processes2.2Threads2.3Inter-process communication2.4Classical IPC problems2.5Scheduling2Content of this lectureWhy Scheduling?When to Schedule?Basic Scheduling AlgorithmBatch systemsFirst-Come First-ServedShortest job firstInteractive systemsRound-robinPriority sche

2、dulingMulti Queue & Multi-level FeedbackGuaranteed Scheduling, Lottery Scheduling, and Fair Sharing SchedulingSummary3SchedulingDeciding 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 SchedulerP

3、roc1: 20 time unitsProc2: 4 time unitsProc3: 2 time unitsPreemptive vs.non-preemptiveReady queueProc 1Proc 2Proc 3Proc 10Proc 11Proc 12Blocked queueCPUScheduler5Preemptive抢占式 vs. Non-preemptiveNon-preemptive scheduling:The running process keeps the CPU until it voluntarily gives up the CPU process e

4、xitsswitches to blocked state1and 4 only (no 3)Disadvantage?Preemptive scheduling:The running process can be interrupted and must release the CPU (can be forced to give up CPU)Preemptive principles?RunningTerminatedReadyBlocked1436CPU SchedulingProblem to solve When (scheduling opportunity) when to

5、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 CPU-bound processan I/O bound process82. When to sch

6、edule?A new process is createdThe running process exitsThe running process is blocked I/O interrupt (some processes will be ready)Clock interrupt (every 10 milliseconds)93. Scheduling AlgorithmFair (nobody cries)Priority (lady first)Efficiency (make best use of equipment)Encourage good behavior (goo

7、d boy/girl)Support heavy loads (degrade gracefully完全降低)Adapt to different environments (interactive, real-time)Properties of a GOOD Scheduling Algorithm:10Performance CriteriaFairness Efficiency: keep resources as busy as possible Policy Enforcement seeing that stated policy is carried outThroughput

8、: number of processes that completes in unit time Turnaround Time (also called elapse time)amount of time to execute a particular process from the time its entered Waiting Time amount of time process has been waiting in ready queue Response Time amount of time from when a request was first submitted

9、 until first response is produced. Proportionality meet users expectation Meeting Deadlines: avoid losing data Predictability11Different Systems, Different FocusesFor allFairness, policy enforcement, resource balanceBatch SystemsMax throughput, min turnaround time, max CPU utilization Interactive Sy

10、stemsMin Response time, best proportionality Real-Time Systemspredictability, meeting deadlines 12Single Processor Scheduling AlgorithmsBatch systemsFirst Come First Serve (FCFS)Shortest Job FirstInteractive SystemsRound RobinPriority SchedulingMulti Queue & Multi-level FeedbackGuaranteed Scheduling

11、Lottery SchedulingFair Sharing Scheduling13(1) First Come First Served (FCFS)Also called FIFO. Process that requests the CPU FIRST is allocated the CPU FIRST. Non-preemptiveUsed in Batch Systems Implementation: FIFO queuesA new process enters the tail of the queueThe scheduler selects from the head

12、of the queue. Performance Metric度量标准: Average Waiting Time. Given 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 waitin

13、g time: (0+24+27)/3 = 1715Suppose that the processes arrive in the order P2 , P3 , P1 The Gantt chart for the schedule is:Waiting time for P1 = 7; P2 = 0; P3 = 3Average waiting time: (7 + 0 + 3)/3 = 3.3Much better than previous case.Convoy effect: short process behind long processFCFS Example (cont.

14、)0P1 (24)37P2 (3)P3 (4)16Problems with FCFSNon-preemptiveNot optimal AWT (Average Waiting Time)Cannot 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?Consider n-1 jobs in syst

15、em that are I/O bound and 1 job that is CPU bound. I/O bound jobs pass quickly through the ready queue and suspend themselves waiting for I/O. CPU bound job arrives at head of queue and executes until complete. I/O bound jobs rejoin ready queue and wait for CPU bound job to complete. I/O devices idl

16、e until CPU bound job completes. When CPU bound job complete, other processes rush to wait on I/O again. CPU becomes idle. 18(2) Shortest Job First (SJF)Schedule the job with the shortest elapse time firstScheduling in Batch Systems Two types:Non-preemptivePreemptiveRequirement: the elapse time need

17、s to know in advanceOptimal 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 ti

18、me 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+

19、21)/4 = 10.25(comparing to 7)06P4 (3)P1 (6)14P3 (7)21P2 (8)2421SJF is not always optimalIs SJF optimal if all the jobs are not available simultaneously?ProcessDurationOrderArrival TimeP11010P2222010P1 (10)P1 waiting time: 0P2 waiting time: 8The average waiting time (AWT): (0+8)/2 = 4P2 (2)2 (p2 arri

20、ves)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 SJFAlso called Shortest Remaining Time Fir

21、stSchedule the job with the shortest remaining time required to completeRequirement: 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!0

22、122 P1 (8)P2 (2)4P1 (2)25A Problem with SJFStarvationIn some condition, a job is waiting for everExample: SJFProcess A with elapse time of 1 hour arrives at time 0But ever 1 minute from time 0, a short process with elapse time of 2 minutes arriveResult of SJF: A never gets to run26Interactive Schedu

23、ling AlgorithmsUsually preemptiveTime is sliced切开 into quantum (time intervals)Scheduling decision is also made at the beginning of each quantumPerformance CriteriaMin Response Timebest proportionality Representative有代表性的 algorithms:Round-robinPriority-basedMulti Queue & Multi-level FeedbackGuarante

24、ed SchedulingLottery SchedulingFair Sharing Scheduling27(3) Round-robin轮转调度 One of the oldest, simplest, most commonly used scheduling algorithmSelect process/thread from ready queue in a round-robin fashion (take turns)Problem: Do not consider priority Context switch overhead28Round-robin: ExampleP

25、rocessDurationOrderArrival TimeP1310P2420P33300Suppose time quantum is: 1 unit, P1, P2 & P3 never blockP1P2P310P1P2P3P1P2P3P2P1 waiting time: 4P2 waiting time: 6P3 waiting time: 6 The average waiting time (AWT): (4+6+6)/3 = 5.3329Time Quantum时间段Time slice too largeFCFS behavior Poor response timeTim

26、e slice too smallToo many context switches (overheads) Inefficient CPU utilizationHeuristic: 70-80% of jobs block within time-slice Typical time-slice 10 to 100 ms 30(4) Priority SchedulingEach job is assigned a priority. FCFS within each priority level. Select highest priority job over lower ones.R

27、ational合理的: higher priority jobs are more mission-criticalExample: display a video film in real time vs. send emailProblems:May not give the best AWTindefinite无限的 blocking or starving a process 31Set PriorityTwo approachesStatic (for system with well known and regular application behaviors)Dynamic (

28、otherwise)Priority 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

29、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 SchedulingHybrid between priority and round-robinProcesses assigned to one queue permanently Scheduling between queue

30、s Fixed Priorities % CPU spent on queue Example System processes (highest priority)Interactive programs (Round Robin)Background Processes (FCFS)Student Processes 36Multi-Queue Scheduling: Example20%50%30%37Real Life AnalogyTasks (to-do list) for poor BobClass 1 priority (highest): tasks given by his

31、 bossFinish the project (50%)Class 2 priority: tasks for his wifeBuy a valentine present (30%)Class 3 priority (lowest): Bobs tasksWatch TV (20%)38(6)A Variation: Multi-level Feedback AlgorithmMulti-Level Queue with priorities Processes move between queues Each queue represents jobs with similar CPU

32、 usageJobs in a given queue are executed with a given time-slice Rational:Once an I/O process completes an I/O request, it should have higher CPU priority.39 Multi-level Feedback Algorithm (Details)Example (CTSS): Queuei has time-slice t 2i If a job in Queuei doesnt block by end of time-slice, it is

33、 moved to Queuei+1Lowest priority Queue is FCFS40Multi-level Feedback Algorithm: Example41Review: Scheduling AlgorithmsBatch systemsFirst come first serve Shortest job firstInteractive systemsRound-robinPriority schedulingMulti-Queue & Multi-level feedback42(7) Guaranteed Scheduling (QoS)Make real p

34、romises to the users about performance and then live up to them.Example:with n processes running, the scheduler makes sure that each one gets 1/n of the CPU cycles.Scheduling:compute the ratio of actual CPU time consumed to CPU time entitledSelect the one with the lowest ratio43(8) Lottery Schedulin

35、gMore commonly usedProbability机率-based:Give processes lottery tickets. At scheduling time, a lottery ticket is chosen at random, and the process holding that ticket gets that resource. Give more tickets for higher priority processesAdvantages:SimpleHighly responsiveCan support cooperation between processesEasy to support p