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

上传人:鲁** 文档编号:585127475 上传时间:2024-09-01 格式:PPT 页数:49 大小:636KB
返回 下载 相关 举报
操作系统英文课件:ch2 Processes and Threads c_第1页
第1页 / 共49页
操作系统英文课件:ch2 Processes and Threads c_第2页
第2页 / 共49页
操作系统英文课件:ch2 Processes and Threads c_第3页
第3页 / 共49页
操作系统英文课件:ch2 Processes and Threads c_第4页
第4页 / 共49页
操作系统英文课件:ch2 Processes and Threads c_第5页
第5页 / 共49页
点击查看更多>>
资源描述

《操作系统英文课件:ch2 Processes and Threads c》由会员分享,可在线阅读,更多相关《操作系统英文课件:ch2 Processes and Threads c(49页珍藏版)》请在金锄头文库上搜索。

1、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-robinvPriori

2、ty 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

3、 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 t

4、he 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 opp

5、ortunity) 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

6、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 equipmen

7、t)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 st

8、ated 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

9、 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 turnar

10、ound 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

11、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

12、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: 0

13、P2 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

14、 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 Devi

15、ce 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 rejoi

16、n 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 S

17、ystems 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 waiti

18、ng 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 waitin

19、g 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 tim

20、e: 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 Tim

21、eP11020P2212P1 (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

22、: 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

23、 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 vRepresen

24、tative有代表性的 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

25、(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

26、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 j

27、ob 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 proce

28、ss 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: ExampleProcess

29、DurationPriorityArrival 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 Schedu

30、lingvHybrid 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 Schedulin

31、g: 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 Feedba

32、ck 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 Feedba

33、ck 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 firstv

34、Interactive 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.vSchedu

35、ling: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 get

36、s 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 (fr

37、om 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 Rea

38、l-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 v

39、50-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

展开阅读全文
相关资源
正为您匹配相似的精品文档
相关搜索

最新文档


当前位置:首页 > 高等教育 > 研究生课件

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号