操作系统 第3章 调度与死锁.ppt

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