操作系统_处理器调度20160930

《操作系统_处理器调度20160930》由会员分享，可在线阅读，更多相关《操作系统_处理器调度20160930（275页珍藏版）》请在金锄头文库上搜索。

1、l 调度是系统将计算机资源分配给进程。 l 在单道程序环境下，只有一个进程存在，计算机 的所有资源由一个进程独占，没有资源竞争问题 。 l 在多道程序环境下，多个进程并发运行，各进程 之间存在资源的相互竞争，特别是对处理器资源 的竞争，从而影响到系统性能。 l 处理器调度指在多道程序环境下将处理器分配给 各进程。在处理器调度中，合理的调度算法能够 提高处理器的处理能力和系统性能，满足用户需 求。第第3 3章章 处理机调度与死锁处理机调度与死锁2/136第第3 3章章 处理机调度与死锁处理机调度与死锁3.1 处理机调度的基本概念3.2 调度算法3.3 实时调度3.4 多处理机系统中的调度3.5

2、产生死锁的原因和必要条件3.6 预防死锁的方法3.7 死锁的检测和解除3.1 处理器调度的层次l 在内存中并发的进程之间构成的是一种竞争使用 处理器的关系。 l 低级调度将处理器分配给进程。 l 低级调度受到内存中用户作业数的影响，处理器 调度不只是低级调度问题，还与内存中能够接纳 用户作业的个数有关，与作业调度有关，作业调 度为高级调度。 l 为了减轻内存的负担，外存作为内存的补充，进 程可以在外存与内存之间对换。对换到外存的进 程调入内存为中级调度，中级调度也会影响内存 中进程的调度，处理器调度与中级调度有关。 3.1 处理器调度的层次l 处理器调度划分为3个层次：高级调度、中级调度 和低

3、级调度。进程调度是处理器调度的核心。 l 用户作业从提交给系统开始，直到运行结束退出 系统为止，将经历高级调度、中级调度和低级调 度。3.1.1 高级调度1作业及作业分类作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作。 l 作业可以是完成了编译、链接之后的一个用户程序，也可以是用各种命令构成的一个脚本。 l 根据需要处理工作的类型，作业分为计算型作业和I/O型作业。 l 在操作系统中，将需要CPU处理为主的作业称为计算型作业；将以I/O过程为主的作业称为I/O型作业。 l 一般情况下，操作系统管理会对这两种作业进行区别对待：I/O为主的作业，由于等待I/O

4、过程需要更多的时间，执行更慢；计算型为主的作业等待I/O过程需要的时间更短，执行更快。 3.1.1 高级调度l 作业也可以按照提交方式不同分为批处理作业和 终端型作业。 l 在多道程序环境下，用户的批处理作业被提交到 系统的磁盘上，以批处理后备队列的形式进行组 织，这样的作业为批处理作业。 l 批处理作业需要作业调度将后备队列上的作业调 度到内存才能执行。 l 对终端型作业用户通过终端登录到系统，直接将 作业置于内存中。终端型作业不需要作业调度便 能执行。3.1.1 高级调度（续）l作业调度按照操作系统预先规定的作业调度策略，从磁盘 的作业后备队列中选择作业调入内存，为作业分配所需要的 资源并

5、建立与作业相对应的进程。l当作业运行的准备工作完成后，作业调度启动作业运行。 在作业运行结束后，作业调度归还并释放作业占用的资源， 结束作业。l作业调度也称为高级调度或长程调度。l作业调度模型如图3.1所示。图3.1 作业调度模型提交作业后备队列 用户作业进程就绪队列 处理器进程阻塞队列高级调度终端交互用户3.1.1 高级调度（续）l作业与进程之间存在着紧密的关系：一个作业可能由一个进程组成，运行在一个进程下； 也可能由多个进程组成，运行在多个进程下。作业是 计算机处理任务的实体，进程是计算机处理任务的执 行体。没有作业，进程无事可做；没有进程，作业不 能完成。一个作业中创建多少个进程，有多少

6、个进程 运行由作业的拥有者根据需要决定。l一个系统能够接纳作业的个数由系统的资源决定，特 别是处理器和内存资源。l一个系统能够接纳作业的个数称为系统的多道度，也 称为系统的多道程序度。3.1.1 高级调度（续）l当内存中运行的作业太多时，会影响到系统的服 务质量，影响到程序的正常执行。操作系统为了 保证进入系统的用户作业能够顺利运行，会限制 系统的多道度。当多道度达到限值时，只有完成 一个作业后另一个作业才能进入。3.1.1 高级调度（续）作业调度中操作系统需要完成的工作： l 确定作业的数据结构。操作系统为每个进入系统的作业分配一个与进程控制块（PCB）类似的作业控制块（JCB），作业控制块

7、中包括：作业的名称、作业对资源的需求信息、作业的资源使用信息、作业的控制方式、作业类型、作业优先级和作业状态。作业控制块是作业的标志，存在于作业的整个过程中，只有作业完成或退出系统时，作业控制块才被撤销。操作系统根据作业控制块中的信息对作业进行调度和管理。作业名称由用户提供，系统将其写到作业控制块中。3.1.1 高级调度（续）作业对资源的需求信息包括估计作业执行时 间、作业最迟完成时间、作业要求的内存量、作 业要求输入输出设备的类型和台数、作业要求的 文件量和输出量，这些信息由用户提供。作业的资源使用信息包括作业进入系统时间 、作业开始执行时间、作业已经执行时间、作业 在内存中的地址、作业被分

8、配的输入输出设备台 号，这些信息由操作系统写入。作业的控制方式分为联机和脱机两种，表示 该作业是联机操作还是脱机操作。作业类型分为CPU繁忙型作业和I/O繁忙型作 业，或批处理输入作业和终端作业。3.1.1 高级调度（续）作业优先级反映作业运行的紧急程度，可由用户指定，也可由系统根据作业类型、作业对资源的需求、作业要求的运行时间和系统当前状况动态指定。作业状态指作业当前所处的状态，可分为提交状态、后备状态、运行状态及完成状态。当作业运行结束时，首先释放作业所占用的全部资源，再由作业调度程序调用存储器管理程序收回该作业的作业控制块空间，从而撤销作业。 l 确定作业的调度算法。操作系统调度程序在调

9、度作业前需要确定作业的调度算法，然后再按照确定的作业调度算法从磁盘的作业后备队列中选择作业进入内存。3.1.1 高级调度（续）l 为作业分配资源。作业运行需要各种资源，包括硬件资源和软件 资源。硬件资源有内存、处理器和各种输入输出设 备。软件资源有各种共享变量等。作业的资源分配 策略主要考虑的是作业所包含的进程所需要的资源 ，在一般情况下，资源按照进程需求进行分配。资 源分配中需要避免由进程之间的资源竞争而造成的 死锁等现象。 l 回收作业资源。作业完成后，作业调度程序除了要输出相关的 作业信息之外，还要回收作业所占用的全部资源， 撤销与作业相关的进程和作业控制块。3.1.1 高级调度（续）在

10、作业调度工作中，大多数工作由作业的调度 程序完成。但是，内存和输入输出设备的分配和释 放不是由作业调度程序完成，而是由存储器管理和 设备管理程序完成的。作业调度程序只是将作业对内存的要求和对设 备的要求转交给相应的内存管理程序和设备管理程 序，由内存管理程序和设备管理程序完成内存和设 备的分配与回收。3.1.1 高级调度（续）3作业的状态为了更好地描述作业，可以将作业分为不同的状 态。作业的状态包括：提交状态、后备状态、执行状 态和完成状态。l 提交状态:用户将作业提交给操作系统，等待输入 程序和数据到磁盘。l 后备状态:系统接收输入的用户作业，并将其放入 计算机磁盘。作业在磁盘上以后备队列形

11、式进行组织 ，等待作业调度程序将作业调度到内存。l 执行状态:作业被调度到内存，为作业分配资源并 为其创建与之对应的进程，进程获得CPU，开始运行 。3.1.1 高级调度（续）l 完成状态:从作业的第一个进程完成开始，直到作 业所有的进程完成，释放作业所占用的资源，退出系 统的整个进程。作业状态及其转换如图3.2所示。执行状态就绪运行阻塞后备状态提交状态完成状态图3.2 作业状态及其转换3.1.1 高级调度（续）l 作业状态的划分比进程状态的划分更粗，进程是 作业全部状态中的一个阶段体现。 l 作业调度将作业从后备状态转换到内存执行状态 。作业执行状态包含作业所对应进程的就绪、运 行和阻塞状态

12、。 l 在分时操作系统和实时操作系统中，终端用户的 作业直接送入到内存，不需要作业调度。操作系 统需要完成的功能是决定是否能够为作业创建进 程。 l 分时操作系统和实时操作系统也支持批处理作业 ，在批处理作业存在时，也能够完成作业调度。3.1.2 中级调度l 中级调度又称为中程调度，是为了提高内存利用 率和平衡系统负载而采取的一种利用外存补充内 存的措施。 l 在多进程环境下，内存中的多个进程，其中有些 进程可能需要挂起，这些进程暂时不参与对处理 器的竞争。为了充分利用内存资源，系统会采用 进程对换的方法将进程换出到外存，将这些进程 占用的内存空间释放，让内存能够接纳新的进程 或使得内存中的进

13、程能够更快推进。当被换出到 外存中的进程挂起时间到时，又需要将这些进程 换入到内存。中级调度是在换出内存的进程中确 定需要进入内存的进程。3.1.2 中级调度l 当进程需要换入内存，而内存资源不充足时，则 系统需要选择内存中的进程换出外存，让出内存 空间给进入内存的进程。 l 中级调度根据内存中能够接纳的进程数来平衡系 统负载，起到在一定时间内平滑和调整系统负载 的作用。1低级调度低级调度又称为进程调度、短程调度，是按照一 定的调度算法从内存的就绪进程队列中选择进程， 为进程分配处理器。l 进程调度发生在内存中的就绪进程，被调度的进 程从内存就绪到处理器中执行的过程，该过程很短 ，被称为短程调

14、度。l中级调度位于高级调度与低级调度之间，被称为中 程调度。中级调度主要用于内存管理，特别是虚拟 存储器管理。 3.1.3 低级调度l 作业调度发生进程位于外存与进入计算机内存之 间，经过的过程最长，因此，作业调度被称为长程 调度。l 进程调度与作业调度和中级调度比较，进程调度 发生的频率最高，作业调度发生的频率最低。3.1.3 低级调度处理器调度的三级模型如图3.3所示。3.1.3 低级调度图3.3 处理器三级调度模型进程挂起就绪队列进程阻塞队列进程挂起阻塞队列进程就绪队列完成中级调度低级调度处理器高级调度作业后备队列交互式用户提交用户作业3.1.3 低级调度（续）2引起进程调度的主要原因

15、（1）处理器执行的进程完成任务，处理器空闲；（2）处理器执行的进程转入阻塞状态，此时处理 器空闲；（3）处理器执行的进程被其它进程抢占；（4）处理器执行的进程被挂起。3.1.3 低级调度（续）3进程调度中的基本机制 （1）排队器。为使进程调度时能够快速有效地找到就 绪队列中的每个进程，首先应该按照一定的方式将 进程就绪队列排成一个或多个队列。 （2）分派程序。分派程序将根据进程调度策略将所选 中的进程从就绪队列中移出，然后进行进程上下文 的切换，并将处理器分配给进程。 （3）上下文切换机制。上下文切换机制是指在操作系 统分派程序的执行下完成处理器的切换过程，实现 进程上下文切换3.1.3 低级

16、调度（续）4进程切换的实现进程切换需要完成进程上下文切换，进程状态、进程等 待时间等信息的改变。新、老进程切换如图3.4所示。老进程新进程CPU图3.4 进程调度中的进程切换 进程切换过程描述？3.1.3 低级调度（续）进程切换需要完成以下工作：l保存并恢复处理器信息。处理器中的寄存器保存了当前正在执行进程的相 关数据和状态，在进程被切换时，必须将进程的 这些信息保存到进程控制块中，以便进程被处理 器再次执行时，能够将进程的断点信息从进程控 制块拷贝回处理器寄存器中，保证处理器能够从 进程的上次断点开始继续向前推进。处理器中寄存器信息写到老进程的进程控制块中 ，新进程的进程控制块信息被拷贝到处理器的寄 存器中。3.1.3 低级调度（续）l 更新进程控制块中的进程状态、进程达到时间、进 程等待时间、进程优先级变化等信息，并将进程控 制块移到相应的进程队列。被切换的进程状态从执行改为就绪或阻塞，其进程控 制块也被插入就绪队列或阻塞队列。同样，被分配 处理器的进程，其状态从就绪改为执行，进程控