操作系统第三章 处理器调度20160930.ppt

1、调度是指系统将计算机资源分配给进程。在单一程序环境中，只有一个进程存在，计算机的所有资源都被一个进程所垄断，因此不存在资源竞争问题。在多通道程序环境中，多个进程同时运行，进程间存在资源竞争，尤其是处理器资源的竞争，影响系统性能。处理器调度是指在多道程序设计环境中为每个进程分配处理器。在处理器调度中，合理的调度算法可以提高处理器的处理能力和系统性能，满足用户的需求。第3章处理器调度和死锁，2/136，第3章处理器调度和死锁，3.1处理器调度的基本概念，3.2调度算法，3.3实时调度，3.4多处理器系统中的调度，3.5死锁的原因和必要条件，3.6防止死锁的方法，3.7死锁的检测和释放，3.1处理器

2、调度的层次，在内存中的并发进程之间，构成了竞争使用处理器的关系。低级调度将处理器分配给进程。低级调度受内存中用户作业数量的影响。处理器调度不仅是一个低级调度问题，还与内存中可容纳的用户作业数量有关。为了减轻内存负担，外部内存被用作内存的补充，进程可以在外部内存和内存之间进行交换。将切换到外部存储器的进程转移到存储器中是中间调度，它也影响存储器中进程的调度，并且处理器调度与中间调度相关。3.1处理器调度分为三级：高级调度、中级调度和低级调度。进程调度是处理器调度的核心。用户作业将从提交到系统时开始经历高级调度、中间调度和低级调度，直到它们在运行后退出系统。3.1.1高级调度、1作业和作业分类作业

3、由一组统一管理和操作的流程组成，这是一项相对独立的作业，用户需要计算机系统来完成。作业可以是编译和链接后的用户程序，也可以是由各种命令组成的脚本。根据要处理的作业类型，作业可以分为计算作业和输入/输出作业。在操作系统中，需要中央处理器处理的作业称为计算作业；输入输出操作称为输入输出操作。在正常情况下，操作系统管理会区别对待这两种作业：基于输入输出的作业需要更多的时间等待输入输出过程，执行速度较慢；基于计算的作业等待输入/输出过程所需的时间更少，执行速度更快。3.1.1高级调度，作业也可以根据不同的提交方式分为批量作业和终端作业。在多道程序设计环境中，用户的批处理作业被提交到系统的磁盘上，并以批

4、处理备份队列的形式组织起来，这就是批处理作业。批处理作业需要作业调度来将备份队列中的作业调度到内存中，然后才能执行。对于终端型作业用户，通过终端登录系统，直接将作业存入内存。终端作业可以在没有作业调度的情况下执行。3.1.1高级调度(续)，作业调度根据操作系统预先指定的作业调度策略，从磁盘上的作业备份队列中选择作业并将其转移到内存中，为作业分配所需的资源，并建立与作业对应的进程。作业运行准备完成后，作业调度开始作业运行。作业运行后，作业调度返回并释放作业占用的资源，并结束作业。作业调度也称为高级调度或远程调度。作业调度模型如图3.1所示。3.1.1高级调度(续)，作业和流程之间有着密切的关系：

5、一个作业可以由一个流程组成，并在一个流程下运行；它也可以由多个进程组成，并在多个进程下运行。作业是计算机处理任务的实体，而过程是计算机处理任务的执行者。没有作业，这个过程就没有任何意义；没有流程，作业无法完成。一个作业中创建和运行的进程数量由作业所有者根据需要决定。系统可以接受的作业数量取决于系统的资源，尤其是处理器和内存资源。一个系统可以接受的作业数称为系统的多通道度，也称为系统的多通道度。3.1.1高级调度(续)，当内存中运行的作业过多时，会影响系统的服务质量和程序的正常执行。为了保证用户进入系统的顺利操作，操作系统会限制系统的多通道程度。当多声道度达到极限时，在另一个操作完成后，只能进入

6、一个操作。3.1.1高级调度(续)，作业调度中操作系统需要完成的工作：确定作业的数据结构。操作系统为进入系统的每个作业分配一个类似于过程控制块的作业控制块。作业控制块包括作业名称、作业需求信息、作业资源使用信息、作业控制模式、作业类型、作业优先级和作业状态。作业控制块是作业的标志，存在于作业的全过程。只有当操作完成或退出系统时，作业控制块才会被撤销。操作系统根据作业控制块中的信息调度和管理作业。作业名称由用户提供，系统将其写入作业控制块。3.1.1高级调度(续)，作业对资源的需求信息包括由用户提供的估计作业执行时间、最新作业完成时间、作业所需的内存量、作业所需的输入输出设备的类型和数量、作业所

7、需的文件量和输出量。作业的资源使用信息包括作业进入系统的时间、作业开始执行的时间、作业已经执行的时间、作业在存储器中的地址以及分配给作业的输入/输出设备的数量，这些信息由操作系统写入。作业控制方法分为在线和离线，指示作业是在线还是离线。作业类型分为中央处理器忙作业和输入输出忙作业，或批处理输入作业和终端作业。3.1.1高级调度(续)，作业优先级反映作业操作的紧急程度，可由用户指定或由系统根据作业类型、作业对资源的需求、作业所需的运行时间和当前系统条件动态指定。作业状态是指作业的当前状态，可分为提交状态、备份状态、运行状态和完成状态。作业运行时，首先释放作业占用的所有资源，然后作业调度程序调用内

8、存管理器回收作业的作业控制块空间，从而取消作业。确定作业的调度算法。操作系统调度器需要在调度作业之前确定作业调度算法，然后根据确定的作业调度算法从磁盘作业备份队列中选择作业进入内存。3.1.1高级调度(续)，为作业分配资源。作业运行需要各种资源，包括硬件资源和软件资源。硬件资源包括内存、处理器和各种输入输出设备。软件资源有各种共享变量。作业的资源分配策略主要考虑作业中包含的流程所需的资源。一般来说，资源是根据流程要求分配的。在资源分配中，有必要避免进程间资源竞争造成的死锁。回收运营资源。作业完成后，作业调度器不仅要输出相关的作业信息，还要恢复作业占用的所有资源，取消与作业相关的进程和作业控制块

9、。3.1.1高级调度(续)，在作业调度工作中，大部分工作是由作业调度器完成的。但是，内存和输入/输出设备的分配和释放不是由作业调度程序完成的，而是由内存管理和设备管理程序完成的。作业调度器只将作业的内存需求和设备需求转移到相应的内存管理程序和设备管理程序，完成内存和设备的分配和恢复。3.1.1高级调度(续)，3作业状态为了更好地描述作业，作业可以分为不同的状态。作业状态包括：提交状态、备份状态、执行状态和完成状态。提交状态：用户将作业提交给操作系统，等待程序和数据输入到磁盘。备份状态：系统接收输入的用户作业，并将其放在计算机磁盘上。作业以备份队列的形式组织在磁盘上，等待作业调度程序将作业调度到

10、内存中。在执行状态：中，作业被分派到内存，为作业分配资源，并为其创建相应的进程，该进程获得CPU并开始运行。3.1.1高级调度(续)，完成状态：从作业的第一个进程完成开始，直到作业的所有进程都完成，释放作业占用的资源并退出系统的整个进程。运行状态及其转换如图3.2所示。图3.2作业状态及其转换，3.1.1高级调度(续)，作业状态的划分比过程状态的划分更粗糙，过程是所有作业状态的阶段体现。作业调度将作业从备份状态更改为内存执行状态。作业执行状态包括与作业相对应的流程的就绪、运行和阻塞状态。在分时操作系统和实时操作系统中，最终用户的作业被直接发送到内存，而不需要作业调度。操作系统需要完成的功能是决

11、定是否可以为作业创建一个进程。分时操作系统和实时操作系统也支持批处理作业，并且可以在批处理作业存在时完成作业调度。3.1.2中间调度，也称为中程调度，是一种使用外部内存来补充内存以提高内存利用率和平衡系统负载的措施。在多进程环境中，内存中有许多进程，其中一些可能需要暂停，这些进程暂时不参与处理器的竞争。为了充分利用内存资源，系统将使用进程交换方法将进程交换到外部内存中，并释放这些进程占用的内存空间，以便内存可以接受新的进程或使内存中的进程更快地前进。当换出到外部存储器的进程的暂停时间到期时，这些进程需要换出到存储器。中间调度是确定在换出内存的过程中哪些进程需要进入内存。3.1.2中间调度，当进

12、程需要在内存中交换，内存资源不足时，系统需要选择内存中的进程来交换出内存，并为进入内存的进程放弃内存空间。中间调度根据内存中可容纳的进程数量来平衡系统负载，并在一定时间内起到平滑和调整系统负载的作用。低级调度低级调度，也称为进程调度和短程调度，根据特定的调度算法从内存中的就绪进程队列中选择进程，并将处理器分配给这些进程。进程调度发生在内存中的就绪进程中，从内存中的就绪进程到处理器中的执行过程非常短，这称为短程调度。中间调度位于高级调度和低级调度之间，称为中程调度。中间调度主要用于内存管理，尤其是虚拟内存管理。3.1.3低级调度，作业调度的过程位于外部存储器和计算机存储器之间，并且需要最长的过程

13、。因此，作业调度被称为远程调度。与作业调度和中间调度相比，流程调度的频率最高，作业调度的频率最低。3.1.3低级调度。处理器调度的三级模型如图3.3所示。3.1.3低级调度，3.1.3低级调度(续)，进程调度的2个主要原因(1)处理器执行的进程完成任务且处理器空闲；(2)处理器执行的进程转为阻塞状态，此时处理器处于空闲状态；(3)处理器执行的进程被其他进程抢占；(4)由处理器执行的进程被暂停。3.1.3低级调度(续)，3进程调度中的基本机制(1)队列。为了快速有效地找到就绪队列中的每个进程，进程就绪队列应该以某种方式排列成一个或多个队列。(2)调度程序。(3)语境转换机制。上下文切换机制是指在

14、操作系统的调度器的执行下，切换处理器并实现进程上下文切换的过程。3.1.3低级调度(续)，4流程切换的实现需要流程上下文切换、流程状态、流程等待时间等信息的改变。新旧流程切换如图3.4所示。过程切换过程描述？3.1.3低级调度(续)，进程切换需要完成以下任务：保存和恢复处理器信息。处理器中的寄存器存储当前正在执行的进程的相关数据和状态。当进程被切换时，进程的这些信息必须保存在进程控制块中，以便当处理器再次执行进程时，进程的断点信息可以从进程控制块复制回处理器寄存器，以确保处理器可以从进程的最后一个断点继续向前移动。处理器中的寄存器信息被写入旧进程的进程控制块，新进程的进程控制块信息被复制到处理

15、器的寄存器中。3.1.3低级调度(续)，更新过程控制块中的过程状态、过程到达时间、过程等待时间、过程优先级变化等信息，并将过程控制块移动到相应的过程队列。交换进程的状态从执行变为就绪或阻塞，其进程控制块也插入就绪队列或阻塞队列。类似地，分配给处理器的进程的状态从就绪变为执行，并且进程控制块从就绪队列中移除。更新内存管理数据结构，维护流程的代码和数据段。3.1.3低级调度(续)，5非抢占式调度和抢占式调度在进程调度中非抢占式调度是一种常见的调度方法。在非抢占式调度中，将处理器分配给某个进程后，该进程不会自动放弃该处理器，直到该进程结束或被阻塞。非抢先调度有什么问题？如果正在执行的进程碰巧正在执行

16、一个没有资源的无限循环，则正在执行的进程不会放弃处理器，所有就绪的进程将永久等待，系统将进入相持状态。解决方案？此时，如果系统能够有规律地自行实施进程中断，这种僵局是可以避免的。3.1.3低级调度(续)，强制进程中断的调度模式是抢占调度模式，也称为剥夺调度模式，这意味着当一个进程在处理器中运行时，操作系统可以从该进程中剥夺已经分配给该进程的处理器，并根据指定的抢占原则将其分配给其他进程。只有当系统允许抢占调度并满足抢占条件时，系统才能采用抢占调度模式。满足抢占条件的进程可以抢占当前正在执行该进程的处理器。被抢占的进程状态从执行状态变为就绪状态，其进程控制块进入进程就绪队列。3.1.3低级调度(

17、续)。图3.5显示了抢占的进程状态。3.1.3低级调度(续)，抢占条件也称为抢占原则，可概括如下：分时系统中的时间片，当一个进程的运行时间片到期时，该进程将被抢占，处理器将被分配给其他准备好的进程。分时操作系统采用基于时间片的抢占调度方法，如UNIX操作系统和Linux操作系统。优先级当就绪队列中有一个进程的优先级高于处理器上当前运行的进程时，系统将从当前进程中剥夺处理器，优先级较高的进程将获得处理器。基于优先级的进程抢占调度被许多操作系统采用，尤其是实时操作系统。在UNIX操作系统中，当用户模式进程在完成系统调用后从核心模式返回到用户模式继续运行时，处理器可能会被在核心模式下执行的其他进程抢占。3.1.3低级调度(续)，短进程当就绪队列中的进程的执行时间短于处理器上当前运行的进程的执行时间时，当前进程被抢占，系统将处理器分配给较短的进程。先占，3.1.3低级调度(续)，抢占导致的问题：增加系统开销进程间不一致的数据共享当进程间存在数据共享时，如果一个进程在数据更新完成前被抢占，获取处理器的进程只需再次读取该共享数据，此时读取的数据可能不一致。因此，操作系统必须采取一定的措施