《电子科技大学《计算机操作系统》第2章-并发与进程-调度ppt课件.pptx》由会员分享，可在线阅读，更多相关《电子科技大学《计算机操作系统》第2章-并发与进程-调度ppt课件.pptx（73页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多计算机操作系统电子电子科技科技大学大学计算机科学与工程学院计算机科学与工程学院李李玉军玉军寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多主要内容主要内容调度scheduling死锁deadlock同步synchronization进程process寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5 进程调度进程调度如果有多个进程（线程）竞争
2、CPU，那么就需要选择下一个要运行的进程（线程）。在操作系统中完成这部分工作的程序称为调度程序（scheduler），该程序使用的算法称为调度算法（scheduling algorithm）。进程的调度算法对系统的整体性能和用户体验影响很大。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式调度的生活实例寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式
3、目标防止进程长期不能获得调度而饥饿尽量提高处理机的利用率提高系统吞吐量尽量减少进程的响应时间原则满足用户需求满足系统需求寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式基本概念响应时间周转时间截止时间系统吞吐量寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式响应时间 从用户通过键盘提交一个请求开始，直至系统首次产生响应为止的时间。响应时间的构成 输入
4、传送时间处理时间响应传送时间寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式周转时间 从作业被提交给系统开始，到作业完成为止的这段时间间隔，也称为作业周转时间。周转时间的构成 驻外存等待调度时间驻内存等待调度时间执行时间阻塞时间需累计需累计寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式平均周转时间：多个作业周转时间的平均值 带权周转时间：作业的周转
5、时间与系统为它提供的服务时间之比平均带权周转时间：多个作业带权周转时间的平均值 寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式截至时间 某任务必须开始执行的最迟时间，或必须完成的最迟时间。系统吞吐量 在单位时间内，系统所完成的作业数。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式面向用户的原则响应时间周转时间截止时间面向系统的原则吞吐量利用率公平
6、性优先级寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式面向用户的原则响应时间快 尽可能使绝大多数用户的请求能在响应时间内完成，常用于评价分时系统的性能。平均周转时间短 常用于评价批处理系统的性能，涉及长程调度、中程调度和短程调度。满足截至时间 常用于评价实时系统的性能。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式面向系统的原则系统吞吐量大 常用
7、于评价批处理系统的性能。处理器利用率高大、中型多用户系统较看重处理器的利用率单用户微机或某些实时系统不看重处理器的利用率 各类资源的平衡使用 使系统中的各种资源都尽量处于忙碌状态。公平性 对所有进程公平，不偏袒任何进程。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式面向系统的原则（续）优先权：优先权高的进程应优先调度接纳接纳调度调度处理机处理机完成完成等待事件等待事件事件发生事件发生阻塞队列阻塞队列就绪队列就绪队列0就绪队列就绪队列1就绪队列就绪队列n被剥夺被剥夺寒假来
8、临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式面向系统的原则（续）优先权（续）几乎所有操作系统的调度算法都可考虑优先权原则。仅考虑优先权会导致进程饥饿，即某些低优先权进程长时间得不到调度。可以考虑动态优先权，将进程排队的等待时间等因素纳入优先权的计算。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式调度类型 非剥夺方式剥夺方式长程调度中程调度短程调度I/
9、O调度寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.1 调度的目标、原则和方式调度的目标、原则和方式非剥夺（抢占）方式执行进程只有在执行完毕，或因申请I/O阻塞自己时，才中断其执行，释放处理机。不利于“即时性”要求较高的分时和实时系统，主要用于批处理系统。剥夺（抢占）方式在新进程到来时，或某个具有较高优先权的被阻塞进程插入就绪队列时，或在基于时间片调度的系统中，时间片用完而中断当前进程的执行，调度新的进程执行。会产生较多的中断，主要用于实时性要求较高的实时系统及性能要求较高的批处理系统和分时系统。寒假来临，不少的高中
10、毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.2 调度的类型调度的类型长程调度（高级调度、作业调度）用于决定把外存上处于后备队列中的作业调入内存，并为它们创建进程、分配必要的资源，然后，再将新创建的进程排在就绪队列（就绪/挂起）上，等待短程（中程）调度。交互用户交互用户交互用户交互用户处理机处理机处理机处理机完成完成完成完成就绪队列就绪队列就绪队列就绪队列就绪就绪就绪就绪/挂起队列挂起队列挂起队列挂起队列后备队列后备队列后备队列后备队列长程调度长程调度寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是
11、，目前社会上寒假招工的陷阱很多2.5.2 调度的类型调度的类型长程调度需要考虑两个问题选择多少个作业进入内存，为之创建进程？取决于多道程序的度多道程序的度，即允许同时在内存中运行的进程数。选择哪些作业 取决于长程调度算法长程调度算法寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.2 调度的类型调度的类型短程调度（进程调度、低级调度）决定就绪队列中的哪个进程应获得处理器运行频率最高现代操作系统几乎都具有短程调度功能中程调度（中级调度）对换功能的一部份，用以提高内存的利用率和系统的吞吐量。内存紧张时，选择一个进程换出到外存
12、（换出）。内存充裕时，从外存选择一个挂起状态的进程调度到内存（换入）。只有支持进程挂起的操作系统才具有中程调度功能。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.2 调度的类型调度的类型同时具有三级调度的调度队列模型 中程调度中程调度中程调度中程调度长长长长程程程程 调调调调度度度度短程调度短程调度短程调度短程调度处理机处理机处理机处理机完成完成完成完成就绪队列就绪队列就绪队列就绪队列就绪就绪就绪就绪/挂起队列挂起队列挂起队列挂起队列阻塞阻塞阻塞阻塞/挂起队列挂起队列挂起队列挂起队列阻塞队列阻塞队列阻塞队列阻塞队列时
13、间片用完时间片用完时间片用完时间片用完事件等待事件等待事件等待事件等待事件发生事件发生事件发生事件发生寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3 进程调度算法进程调度算法调度算法根据系统的资源分配策略所规定的资源分配算法对于不同的系统目标，通常采用不同的调度算法常见的调度算法先来先服务短作业优先时间片轮转基于优先级剩余时间最短优先响应比高者优先反馈寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.1 先来先服务（先来先服务（FCFS）
14、算法：First-Come-First-Served 选择最先进入就绪队列的进程投入执行，即进程按照请求CPU的顺序使用CPU。评价属于非抢占调度方式对长进程（作业）有利，不利于短进程（作业）有利于CPU繁忙型的进程，而不利于I/O繁忙型的进程不能直接用于分时系统通常与其它调度算法混合使用平均周转时间长寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.1 先来先服务（先来先服务（FCFS）示例 计算P1、P2、P3和P4的周转时间、平均周转时间、带权周转时间和平均带权周转时间。进程名程名 产生生时间服服务时间优先先级
15、时间片片P10221P2161P3214P4353寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.1 先来先服务（先来先服务（FCFS）246810121416t进程名程名产生生时间服服务时间优先先级时间片片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P4寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.2 短进程（作业）优先短进程（作业）优先（SPF/SJF）算法:Shortest Job/Process
16、First,SJF/SPF 短进程或短作业优先调度，前提为执行时间预知。评价非抢占调度方式该算法对长作业不利，可能导致长进程饥饿。有利于短进程，减小了平均周转时间。缺少剥夺机制，不适用于分时系统或事务处理环境。由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会估计不准运行时间，致使该算法不一定能真正做到短作业优先调度。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.2 短进程（作业）优先短进程（作业）优先（SPF/SJF）246810121416t进程名程名产生生时间服服务时间优先先级时间
17、片片P10221P2161P3214P4353P1P3P4P2P1 P2P3 P4寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.3 时间片轮转调度算法（时间片轮转调度算法（RR）算法：Round Robin 每个进程被分配一个时间片，如果在时间片结束时该进程还在运行，则剥夺其CPU并分配给另一个进程，被剥夺CPU的进程则插入到就绪队列末尾，等待下次调度；如果该进程在时间片内阻塞或结束，则立即切换CPU。典型应用系统示例分时联机系统基于时间片轮转调度基于时间片轮转调度主机主机终端终端1终端终端2终端终端n终端终端1
18、 1服务进程服务进程终端终端2服务进程服务进程终端终端n服务进程服务进程寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.3 时间片轮转调度算法（时间片轮转调度算法（RR）评价属于抢占调度方式对短的、计算型进程有利对I/O型作业（进程）不利常用于分时系统或事务处理系统时间片的设置与系统性能、响应时间密切相关 时间片设得太短会导致过多进程切换，降低CPU效率；反之，设得太长又可能引起对短的交互请求的响应时间变长。在分时系统中，时间片大小的确定应综合考虑最大用户数目、响应时间、系统效率等多种因素。寒假来临，不少的高中毕业
19、生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多246810121416t进程名程名产生生时间服服务时间优先先级时间片片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P42.5.3.3 时间片轮转调度算法（时间片轮转调度算法（RR）寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多246810121416t进程名程名产生生时间服服务时间优先先级时间片片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P42.5.3.3 时间片轮转调度
20、算法（时间片轮转调度算法（RR）寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.4 基于优先级的调度算法基于优先级的调度算法算法 每个进程被赋予一个优先级（权），允许优先级（权）最高的可运行进程先运行。优先级的类型静态优先级动态优先级寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.4 基于优先级的调度算法基于优先级的调度算法静态优先级(static)优先数在进程创建时分配，生存期内不变。确定依据进程类型（重要性、紧迫性）进程对资源的需求
21、均衡系统资源使用用户需求评价简单，开销小适合批处理进程寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.4 基于优先级的调度算法基于优先级的调度算法静态优先级的问题 若一直存在高优先级的就绪进程，则低优先级的进程可能会饿死(无穷阻塞）。解决方法 进程的优先级随着时间或执行历史而变化老化策略(aging)。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多动态优先级 在创建进程时所赋予的优先级可随进程的推进或随其等待时间的增加而改变，以便获得更好的调度性
22、能。调整时机时钟中断进程切换进程终止2.5.3.4 基于优先级的调度算法基于优先级的调度算法寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多基于优先级调度算法的分类 2.5.3.4 基于优先级的调度算法基于优先级的调度算法进程主动释放处理器进程主动释放处理器处理器可被剥夺处理器可被剥夺非抢占式优先级算法抢占式优先级调度算法寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多246810121416t进程名程名产生生时间服服务时间优先先级时间片片P10221P216
23、1P3214P4353P1P2P3P4P1 P2P3 P42.5.3.4 基于优先级的调度算法基于优先级的调度算法1.1.非抢占式调度方式非抢占式调度方式2.2.优先级数越小，优先级越高优先级数越小，优先级越高寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多246810121416t进程名程名产生生时间服服务时间优先先级时间片片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P42.5.3.4 基于优先级的调度算法基于优先级的调度算法1.1.抢占式调度方式抢占式调度方式2.2.优先级数越小，优先级越高
24、优先级数越小，优先级越高寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.5 剩余时间最短者优先算法剩余时间最短者优先算法算法:Shortest Remaining Time,SRT在SJF的基础上增加了剥夺机制调度程序总是选择预期剩余时间最短的进程 当一个新进程加入就绪队列时，它可能比当前运行的进程具有更短的剩余时间。只要新进程就绪，调度程序就可能抢占当前正在运行的进程。优点既不像FCFS那样偏爱长进程，也不像RR算法那样会产生额外的中断，从而减少了开销。周转时间方面，SRT比SJF性能要好，短作业可以立即被选择执
25、行。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.5 剩余时间最短者优先算法剩余时间最短者优先算法问题需要估计预计的服务时间存在进程饥饿现象必须记录进程的已服务时间寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多246810121416t进程名程名产生生时间服服务时间优先先级时间片片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P42.5.3.5 剩余时间最短者优先算法剩余时间最短者优先算法寒假来临，不少的高中毕业生和
26、大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.6 响应比高者优先响应比高者优先算法:Highest Response Ratio Next 当前进程执行完毕或需要阻塞时，选择响应比最高的进程投入执行。评价实质上是一种动态优先权调度算法是FCFS和SJF的结合，既照顾了短作业，又考虑了作业到达的先后次序，不会使长作业长期得不到服务。利用该算法时，每次调度之前，都须先做响应比的计算，会增加系统开销，且难以准确计算。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多24681012
27、1416t进程名程名产生生时间服服务时间优先先级时间片片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P42.5.3.6 响应比高者优先响应比高者优先寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.7 反馈调度法反馈调度法短进程优先、剩余时间最短者优先以及响应比高者优先调度算法采用了“奖励短进程”的思想。虽然性能较好，但均基于进程的预期执行时间未来。反馈调度法则采用了“惩罚长进程”的思想。根据进程执行历史，调度基于抢占原则（按时间片）并采用动态优先级机制，可以获得较好的性能。寒假来临，不
28、少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.7 反馈调度法反馈调度法算法：MultilevelQueues，采用多级队列区别对待的方法“惩罚长进程”多个独立的、优先级不同的就绪队列各队列区别对待，即优先调度优先级高的队列进程执行过程中可降级，即在整个生命周期内可能位于不同队列。该算法有多个变种 主要区别在于抢占机制不同寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.7 反馈调度法反馈调度法寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备
29、过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.7 反馈调度法反馈调度法基于时间片轮转的反馈调度算法1.设置多个就绪队列，每个队列赋予不同优先级，第一队列优先级最高，依次递减；各个队列中进程执行的时间片也不相同，优先级越高的队列中，每个进程的时间片就越小。2.新进程进入时，首先放入第一个队列尾，按FCFS原则排队，如果在一个时间片内完成则退出，否则将该进程调入第二队列，依次类推。3.仅当第一队列空闲时，调度程序才调度第二队列中的进程，依次类推。如果CPU正在执行第i队列中某进程时有新进程进入较高的队列（第1(i-1)中的任何一个队列），则新进程抢占当前运行进程，并将当前
30、运行进程放回到第i队列末尾。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.7 反馈调度法反馈调度法基于时间片轮转的反馈调度算法示意图就绪就绪队列队列0 0就绪就绪队列队列1 1就绪就绪队列队列2 2就绪队列就绪队列n n至至CPU至至CPU至至CPU至至CPUS1S2S3Sn新进程新进程时间片:S1S2S3寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.3.7 反馈调度法反馈调度法评价：多级反馈队列调度算法具有较好的性能，能较好地满足各种
31、类型用户的需要。终端型作业用户 能在第一队列所规定的时间片内完成，可使终端型作业用户都感到满意。对短作业用户有利 能在前几个队列所规定的时间片内完成。长批处理作业用户 对于长作业，它将依次在第1，2,，n个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多246810121416t进程名程名产生生时间服服务时间优先先级时间片片P10221P2161P3214P4353P1P2P3P4P1 P2P3 P42.5.3.7 反馈调度法反馈调度法q=2i寒假来临，不少的
32、高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时系统 系统能够及时（即时）响应外部事件的请求，在规定的时间内完成对该事件的处理，并控制所有实时任务协调一致地运行。对于实时系统而言，系统的正确性不仅取决于对于实时系统而言，系统的正确性不仅取决于计算的计算的逻辑结果逻辑结果，而且还依赖于产生结果的，而且还依赖于产生结果的时间时间。实时控制系统实时信息处理系统寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时
33、系统与实时任务调度实时系统与实时任务调度实时系统的基本要求可确定性Determinism可响应性Responsiveness用户控制User control可靠性Reliability失效弱化Fail-soft寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时任务 具有及时性要求的、常常被重复执行的特定进程，在实时系统中习惯称为任务。截止时间开始截止时间 任务在某时间以前，必须开始执行。完成截止时间 任务在某时间以前必须完成。寒假来临，不少的高中毕业生和大学在校生都选择
34、去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时任务的分类实时任务截至时间硬实时任务软实时任务周期性周期性实时任务非周期性实时任务寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时系统处理能力限制 假定系统中有m个周期性的硬实时任务，它们的处理时间为Ci，周期为Pi，则在单处理机情况下，必须满足下面的限制条件：寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒
35、假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时系统通常具备快速切换机制 对外部中断的快速响应能力 要求系统具有快速硬件中断机构，禁止中断的时间间隔尽量短，以免耽误时机。快速的任务分派能力 应使系统中的每个运行功能单位适当的小，以减少任务切换的时间开销。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时调度的目标 使硬实时任务在其规定的截止时间内完成（或开始），同时尽可能使软实时任务也能在规定的截止时间内完成（或开始）。
36、实时调度的必要信息就绪时间开始截止时间和完成截止时间处理时间资源需求优先级子任务结构寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时调度算法非抢占式时间片轮转非抢占优先级抢占式剥夺点抢占立即抢占寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时调度算法基于时间片的轮转调度算法实时进程按时间片轮转的方式执行响应时间一般为秒级广泛用于分时系统及一般
37、实时处理系统寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时调度算法基于优先级的非剥夺调度算法实时进程按优先级、非抢占方式执行响应时间一般在数百毫秒至数秒范围多用于多道批处理系统及不太严格的实时系统寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时调度算法基于优先级的剥夺点剥夺调度算法实时进程按优先级、抢占方式执行响应时间一般在几毫秒至几十毫秒
38、用于一般实时系统寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时调度算法立即剥夺调度算法实时进程按优先级、抢占方式执行响应时间为微秒至毫秒级可用于苛刻的实时系统寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度优先级反转（优先级倒置、优先级逆转、优先级翻转）是一种不希望发生的任务调度状态。在该种状态下，一个高优先级任务间接被一个低优先级任务所抢先(
39、preempted)，使得两个任务的相对优先级被倒置。可发生于任何基于优先级的可抢占的调度方案中。已在火星探路者中发生。寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时调度算法最早截止时间优先调度算法Earliest Deadline First，EDF根据任务的截止时间来确定任务的优先级截止时间越早，优先级越高可以是抢占式或非抢占式寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统
40、与实时任务调度实时系统与实时任务调度EDF实例1342134212 34t开始截止时间任务到达任务执行EDF算法用于非抢占调度方式寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时调度算法最低松弛度度优先调度算法Least Laxity First,LLF任务松弛度计算公式 任务的松弛度=完成截至时间 剩余执行时间 当前时间 例：若A进程需在200ms时完成，本身运行需要100ms，当前时刻是10ms，则A的松弛度:2001001090系统按任务松弛度的高低进行调度主要
41、用于可抢占调度方式寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度LLF实例 在一个实时系统中，有两个周期性实时任务A和B A：周期：20ms，执行时间：10ms；B：周期：50ms，执行时间：25ms；下图为A、B的截止时间 A1A2A3A4A5A6A7A8B1B2B3020406080100120140160t寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与
42、实时任务调度LLF实例（续）A1(10)A2(0)A3(10)t01020304050607080B1(15)B1(5)B2(20)t1t2t3t4t5t6t7t8B1(25)A2(未到未到)B1(15)A3(5)B2(未到未到)A4(未到未到)B2(20)A4(0)寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多50A3(5)2.5.4 实时系统与实时任务调度实时系统与实时任务调度LLF实例（续）A1(10)A2(10)A3(10)t010203040607080B1(15)B1(5)B2(20)t1t2t3t5t6t7t9
43、t10B1(25)B1(15)B2(25)A4(10)B2(20)B2(10)B1(5)t4t8寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多2.5.4 实时系统与实时任务调度实时系统与实时任务调度实时调度算法速度单调调度算法Rate Monotonic Scheduling,RMS任务周期 一个任务到达至下一任务到达之间的时间范围任务速度 周期（以秒计）的倒数，以赫兹为单位优先级的确定 优先级函数是任务速度的单调递增的函数系统按任务优先级的高低进行调度寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意
44、义的寒假。但是，目前社会上寒假招工的陷阱很多作业与作业与Project作业3 1.进程A、B、C、D和E到达时间、服务时间如下表所示，试计算分别采用FCFS、RR(q=1)、RR(q=4)、SPN、SRT、HRRN、FB(q=1)、FB(q=2i-1)调度算法时，进程A、B、C、D和E的周转时间、带权周转时间，以及平均周转时间、平均带权周转时间，并对结果进行简要分析。进程程到达到达时间服服务时间A03B26C44D65E82寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多作业与作业与Project作业3（续）2.高响应比优先调
45、度算法的主要优点是什么？3.为什么说多级反馈队列调度算法能较好地各种用户需求？Projecct 3 模拟实现短进程优先调度算法（SPF）和时间片轮转调度算法（RR），要求如下：1.进程通过定义一个进程控制块数据结构（PCB）来表示；2.每个进程需要赋予进程ID、进程到达时间、进程需要运行的总时间等属性；3.在RR中，以1为时间片单位。提交信箱：提交信箱：os_leeyj163os_leeyj163文件名命名格式：文件名命名格式：作业作业3_Project3_3_Project3_姓名姓名_ _学号学号.doc.doc寒假来临，不少的高中毕业生和大学在校生都选择去打工。准备过一个充实而有意义的寒假。但是，目前社会上寒假招工的陷阱很多谢谢你的阅读v知识就是财富v丰富你的人生