版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
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輪轉(zhuǎn)調(diào)度 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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 蘇教版三下教育課件
- 醫(yī)院消毒供應(yīng)室試題
- 蘇少版小學(xué)美術(shù)一年級下冊全冊教案
- DB11-T 2017-2022 射頻電磁輻射車載巡測技術(shù)規(guī)范
- DB11-T 2059-2022 生態(tài)產(chǎn)品總值核算技術(shù)規(guī)范
- 倉儲物流中心改造合同模板
- 關(guān)于合同法中代位權(quán)制度的理解與適用
- 國際展覽中心土方開挖合同
- 衛(wèi)生間翻新包工裝修合同
- 動物園裝修材料供應(yīng)協(xié)議
- 《字體設(shè)計基礎(chǔ)》課件
- 大腸埃希菌敗血癥護理查房課件
- 2024年高端醫(yī)療服務(wù)行業(yè)市場研究報告
- 工程造價咨詢服務(wù)方案(技術(shù)方案)
- 五年級上冊語文第12課《古詩三首》同步練習(xí)(含答案)
- NDJ-8S數(shù)字旋轉(zhuǎn)粘度計
- GB 17565-2022防盜安全門通用技術(shù)條件
- 一+《展示國家工程++了解工匠貢獻》(教學(xué)課件)-【中職專用】高二語文精講課堂(高教版2023·職業(yè)模塊)
- 傳統(tǒng)文化中的管理智慧分答案
- 學(xué)生視力情況統(tǒng)計表
- 《我國糧食安全問題》課件
評論
0/150
提交評論