ch5处理机调度PPT课件.ppt

作业： ? 在单道批处理系统中，有下列三个作业，采用 FCFS 、 SJF 、 SRT 和 HRRN 调度算法进行调度， 哪一种算法调度性能好？为什么？（单位以十进 制计） 提交时间 1 10.00 2 10.1 0 3 10.25 运行时间 开始时间 完成时间 周转时间 带权周转时间 2.00 1.00 0.25 作业 平均周转时间 平均带权周转时间 91 作业： ? 在单道批处理系统中，有下列三个作业，采用 FCFS 、 SJF 、 SRT 和 HRRN 调度算法进行调度， 哪一种算法调度性能好？为什么？（单位以十进 制计） 提交时间 1 10.00 2 10.1 0 3 10.25 运行时间 开始时间 完成时间 周转时间 带权周转时间 2.00 1.00 0.25 作业 平均周转时间 平均带权周转时间 91 作业： ? 在单道批处理系统中，有下列三个作业，采用 FCFS 、 SJF 、 SRT 和 HRRN 调度算法进行调度， 哪一种算法调度性能好？为什么？（单位以十进 制计） 提交时间 1 10.00 2 10.1 0 3 10.25 运行时间 开始时间 完成时间 周转时间 带权周转时间 2.00 1.00 0.25 作业 平均周转时间 平均带权周转时间 91 ? 为了解决进程对处理机的分配问题，在有的多出理机系 统中采用了局部就绪对列的方法限制进程的转移。 ? 局部就绪队列：就是把处于就绪状态的进程分成不同的 组，并使每一组进程和一个处理机对应起来。这样，每 个处理机只执行以其对应就绪对列中的进程。各个就绪 队列中的进程不会发生横向转移。这种方法减少了调度 程序的开销。但是，处理机的使用率却因此下降。例如： 系统中某个局部就绪对列中因等待进程较多而使得对应 的处理机十分繁忙，而另外的处理机则因就绪对列为空 而处于空闲状态。 64 多处理机系统的调度目标是：以最高的可靠性， 使用最少的处理机在最短的时间内完成最多的可 以并行完成的进程。 65 ? （ 2 ）多处理机的调度评价 ? 多处理机的调度有两种评价模型： ? 确定性模型 ? 随机性模性 ? 确定性模型：进程调度执性之前，估计出这些被调度进 程所须要的执行时间，以及这些进程之间的相互关系。 ? 调度程序的目的：是根据给定的执行时间和相互关系， 确定出一个最佳的执行顺序。 ? 因此，确定性模型只用来确定给定进程的执行顺序，而 随机性模性则常被用来研究动态调度技术 。 66 调度策略 1. 线程调度 使用了线程这个概念之后，执行的概念就与进程 分开了。一个应用程序可用一系列线程的形式完 成，它们之间相互配合，并在相同的地址空间同 时运行。在多处理机上调度线程和处理机分配时， 较多使用以下四种方法：负载共享、群调度 、 专用处理机分配 、动态调度 。 67 ? 调度策略 2. 负载共享 线程并不分配给某一特定的处理机。系统中有 一个全局就绪队列，每个处理机空闲时就从该队 列中选择一个线程。这里的负载共享要与负载平 衡相区别。负载共享是最简单的方法，它直接继 承了单处理机系统的许多好处。 68 ? 调度策略 负载共享的优点：对处理机平均分配负载；不需 要集中调度者；对就绪队列可按单处理机所采用 的各种方式加以组织，其调度算法也可沿用单处 理机所用的算法。 负载共享的缺点：集中队列占据了部分内存，对 它的访问要求互斥。因此，在许多处理机同时都 要工作时，就会成为瓶颈； 被抢占进程不可能 再在同一台处理机上运行；如果所有进程都被放 入一个公共线程池，那么同一程序的所有线程不 可能同时获得处理机。 69 ? ? 调度策略 3. 群调度 相关联的线程集被一个处理机集一对一调用。群 调度用于组成一个进程的多个线程的同时调度。 群调度对于中粒度和细粒度的并行应用是必要的。 它提高了紧耦合进程并发执行的效率，减少了调 度耗费 。群调度的使用产生了对处理机分配的 需求。研究表明，群调度策略的某些形式在总体 上要比负载共享要好。 70 ? 调度策略 4. 专用处理机分配 ? 与自我调度相对应，其调度是隐式的，在程序执 行期间，每个程序都被分配与其线程数相等的处 理机，程序结束时，将所有的处理机归还，以便 其他程序使用。专用处理机分配和群调度在调度 时都涉及到处理机分配。多处理机系统上的处理 机分配类似于单处理机系统上的请求调页式内存 分配。