《第3章调度与死锁》.ppt

第3章 处理机调度与死锁 在多道程序环境下，进程数目往往多于处理机数目。要求系统能按某种算法，动态地将处理机分配给就绪队列中的一个进程，使之执行。 现代OS的运行性能，如吞吐量、作业平均周转时间、响应的及时性等，在很大程度上取决于调度，因而，调度策略成了OS的一个关键问题。 3.1 处理机调度的基本概念 3.1.1 高级、中级和低级调度 1. 高级调度 又称作业调度或长期调度（long-term scheduling)。 作业：（用户）利用计算机进行一次运行所需工作的集合。要完成一个工作，用户必须先提交一个作业。如一个作业可能由多个程序构成。 在PC机或普通工作站和服务器上几乎没有作业的概念 在巨型机和大型服务器上，主机的速度高且造价高，要保证其利用率和效率，用专门的作业控制软件作为前端机向主机提交作业的唯一入口。 用户以批文件将作业提交到前端机是用户启动程序的主要方式。 2. 低级调度 也称进程调度或短期调度。用于决定就绪队列中哪个进程获得处理机，之后派发程序（dispatcher）将处理机分配给该进程。 进程调度可采用下面两种方式 1）非抢先式调度（Non-preemptive Mode) 在下面的情况执行处理机调度： （1）正在执行的进程正常结束或由于某种错误而终止运行； （2）执行中的进程提出I/O请求，在等待I/O完成前，进程阻塞，转进程调度； （3）在进程通讯中，执行中的进程执行了某种原语操作，如P操作、阻塞原语和唤醒原语时，都可能引起进程调度。 2）抢先式调度（preemptive mode) 在下面的情况执行处理机调度： (1) 在分时系统中，按照时间片轮转，分给进程的时间片用完时； (2) 按照优先级调度，有更高优先级进程变为就绪时； (3) 短作业优先原则 3. 中级调度 为提高效率，加快进程运行，调节系统的负荷，提高吞吐量。 有时需要在选择内存中阻塞或就绪的进程暂时放到外存（一般是硬盘），即所谓的挂起。当这些进程又具备了运行条件、且内存又稍有空闲时，中级调度把外存上的就绪进程调入内存，放入就绪队列。这种内外存的数据交换称为对换。 中级调度解决： 在阻塞或就绪的进程中选择哪个（些）进程挂起 在条件允许下，在外存挂起的进程集合中如何选择进程激活并调回内存。 外存 对换 作业输入 spooling 输入程序 spooling 作业调度 就绪 阻塞 就绪 运行 完成 阻塞 后备 作业输出 4. 三种调度之间的关系如图 低级调度 中级调度 3.1.2 调度队列模型 1.仅有进程调度的调度队列模型 特点：单就绪、单阻塞队列 2. 具有高级和低级的调度队列模型 特点 ：1)具有进程调度、作业调度 2)根据阻塞原因设置了多个阻塞队列 3.同时具有三级调度的调度队列模型 选择哪种模型应根据系统的规模及目标制定 3.1.3 选择调度方式和算法的若干准则 我们可从不同的角度来判断处理机调度算法的性能，如用户的角度、处理机的角度和算法实现的角度。实际的处理机调度算法选择是一个综合的判断结果。 1. 面向用户的准则 (1) 周转时间短 批处理系统的重要指标。 作业从提交到完成（得到结果）所经历的时间为周转时间。 包括：在外存后备队列中等待，CPU上执行，就绪队列和阻塞队列中等待，结果输出等待。 平均周转时间T和平均带权周转时间（带权周转时间W是 T(周转)/ (CPU执行)） 平均周转时间: 带权周转时间 (2) 响应时间快 分时系统的重要指标。用户输入一个请求（如击键）到系统给出首次响应（如屏幕显示）的时间。 包括：从终端的键盘输入的一个请求信息传送到处理机的时间；处理机对请求的处理时间；处理结果送到终端显示器的时间。 (3) 截止时间的保证 实时系统的重要指标。 开始截止时间和完成截止时间 (4) 优先级准则 可以使关键任务达到更好的指标。 公平性：不因作业或进程本身的特性而使上述指标过分恶化。如长作业等待很长时间。 2. 面向系统的调度性能准则 (1)系统吞吐量高 批处理系统的重要指标。 吞吐量指单位时间内所完成的作业数，跟作业本身特性和调度算法都有关系。 (2)处理机利用率高 大中型主机多用户系统性能指标，系统价格昂贵。PC一般不考虑这个指标。 (3)各种资源的均衡利用 大中型主机多用户系统性能指标。如CPU繁忙的作业和I/O繁忙（指次数多，每次时间短）的作业搭配。对PC及实时系统该指标并不重要。 3. 调度算法本身的调度性能准则 易于实现 执行开销比 3.2 调度算法 OS中调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。有的调度算法适用于作业调度，有的算法适用于进程调度，有的两者都适应。 3.2.1 先