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

调度是系统将计算机资源分配给进程。在单道程序环境下，只有一个进程存在，计算机的所有资源由一个进程独占，没有资源竞争问题。在多道程序环境下，多个进程并发运行，各进程之间存在资源的相互竞争，特别是对处理器资源的竞争，从而影响到系统性能。处理器调度指在多道程序环境下将处理器分配给各进程。在处理器调度中，合理的调度算法能够提高处理器的处理能力和系统性能，满足用户需求。第3章处理机调度与死锁2/136第3章处理机调度与死锁3.1处理机调度的基本概念3.2调度算法3.3实时调度3.4多处理机系统中的调度3.5产生死锁的原因和必要条件3.6预防死锁的方法3.7死锁的检测和解除3.1处理器调度的层次在内存中并发的进程之间构成的是一种竞争使用处理器的关系。低级调度将处理器分配给进程。低级调度受到内存中用户作业数的影响，处理器调度不只是低级调度问题，还与内存中能够接纳用户作业的个数有关，与作业调度有关，作业调度为高级调度。为了减轻内存的负担，外存作为内存的补充，进程可以在外存与内存之间对换。对换到外存的进程调入内存为中级调度，中级调度也会影响内存中进程的调度，处理器调度与中级调度有关。3.1处理器调度的层次处理器调度划分为3个层次：高级调度、中级调度和低级调度。进程调度是处理器调度的核心。用户作业从提交给系统开始，直到运行结束退出系统为止，将经历高级调度、中级调度和低级调度。3.1.1高级调度1．作业及作业分类作业由一组统一管理和操作的进程集合构成，是用户要求计算机系统完成的一项相对独立的工作。作业可以是完成了编译、链接之后的一个用户程序，也可以是用各种命令构成的一个脚本。根据需要处理工作的类型，作业分为计算型作业和I/O型作业。在操作系统中，将需要CPU处理为主的作业称为计算型作业；将以I/O过程为主的作业称为I/O型作业。一般情况下，操作系统管理会对这两种作业进行区别对待：I/O为主的作业，由于等待I/O过程需要更多的时间，执行更慢；计算型为主的作业等待I/O过程需要的时间更短，执行更快。3.1.1高级调度作业也可以按照提交方式不同分为批处理作业和终端型作业。在多道程序环境下，用户的批处理作业被提交到系统的磁盘上，以批处理后备队列的形式进行组织，这样的作业为批处理作业。批处理作业需要作业调度将后备队列上的作业调度到内存才能执行。对终端型作业用户通过终端登录到系统，直接将作业置于内存中。终端型作业不需要作业调度便能执行。3.1.1高级调度（续）作业调度按照操作系统预先规定的作业调度策略，从磁盘的作业后备队列中选择作业调入内存，为作业分配所需要的资源并建立与作业相对应的进程。当作业运行的准备工作完成后，作业调度启动作业运行。在作业运行结束后，作业调度归还并释放作业占用的资源，结束作业。作业调度也称为高级调度或长程调度。作业调度模型如图3.1所示。图3.1作业调度模型提交作业后备队列用户作业进程就绪队列处理器进程阻塞队列高级调度终端交互用户3.1.1高级调度（续）作业与进程之间存在着紧密的关系：一个作业可能由一个进程组成，运行在一个进程下；也可能由多个进程组成，运行在多个进程下。作业是计算机处理任务的实体，进程是计算机处理任务的执行体。没有作业，进程无事可做；没有进程，作业不能完成。一个作业中创建多少个进程，有多少个进程运行由作业的拥有者根据需要决定。一个系统能够接纳作业的个数由系统的资源决定，特别是处理器和内存资源。一个系统能够接纳作业的个数称为系统的多道度，也称为系统的多道程序度。3.1.1高级调度（续）当内存中运行的作业太多时，会影响到系统的服务质量，影响到程序的正常执行。操作系统为了保证进入系统的用户作业能够顺利运行，会限制系统的多道度。当多道度达到限值时，只有完成一个作业后另一个作业才能进入。3.1.1高级调度（续）作业调度中操作系统需要完成的工作：确定作业的数据结构。操作系统为每个进入系统的作业分配一个与进程控制块（PCB）类似的作业控制块（JCB），作业控制块中包括：作业的名称、作业对资源的需求信息、作业的资源使用信息、作业的控制方式、作业类型、作业优先级和作业状态。作业控制块是作业的标志，存在于作业的整个过程中，只有作业完成或退出系统时，作业控制块才被撤销。操作系统根据作业控制块中的信息对作业进行调度和管理。作业名称由用户提供，系统将其写到作业控制块中。3.1.1高级调度（续）作业对资源的需求信息包括估计作业执行时间、作业最迟完成时间、作业要求的内存量、作业要求输入输出设备的类型和台数、作业要求的文件量和输出量，这些信息由用户提供。作业的资源使用信息包括作业进入系统时间、作业开始执行时间、作业已经执行时间、作业在内存中的地址、作业被分配的输入输出设备台号，这些信息由操作系统写入。作业的控制方式分为联机和脱机两种，表示该作业是联机操作还是脱机操作。作业类型分为CPU繁忙型作业和I/O繁忙型作业，或批处理输入作业和终端作业。3.1.1高级调度（续）作业优先级反映作业运行的紧急程度，可由用户指定，也可由系统根据作业类型、作业对资源的需求、作业要求的运行时间和系统当前状况动态指定。作业状态指作业当前所处的状态，可分为提交状态、后备状态、运行状态及完成状态。当作业运行结束时，首先释放作业所占用的全部资源，再由作业调度程序调用存储器管理程序收回该作业的作业控制块空间，从而撤销作业。确定作业的调度算法。操作系统调度程序在调度作业前需要确定作业的调度算法，然后再按照确定的作业调度算法从磁盘的作业后备队列中选择作业进入内存。3.1.1高级调度（续）为作业分配资源。作业运行需要各种资源，包括硬件资源和软件资源。硬件资源有内存、处理器和各种输入输出设备。软件资源有各种共享变量等。作业的资源分配策略主要考虑的是作业所包含的进程所需要的资源，在一般情况下，资源按照进程需求进行分配。资源分配中需要避免由进程之间的资源竞争而造成的死锁等现象。回收作业资源。作业完成后，作业调度程序除了要输出相关的作业信息之外，还要回收作业所占用的全部资源，撤销与作业相关的进程和作业控制块。3.1.1高级调度（续）在作业调度工作中，大多数工作由作业的调度程序完成。但是，内存和输入输出设备的分配和释放不是由作业调度程序完成，而是由存储器管理和设备管理程序完成的。作业调度程序只是将作业对内存的要求和对设备的要求转交给相应的内存管理程序和设备管理程序，由内存管理程序和设备管理程序完成内存和设备的分配与回收。3.1.1高级调度（续）3．作业的状态为了更好地描述作业，可以将作业分为不同的状态。作业的状态包括：提交状态、后备状态、执行状态和完成状态。提交状态:用户将作业提交给操作系统，等待输入程序和数据到磁盘。后备状态:系统接收输入的用户作业，并将其放入计算机磁盘。作业在磁盘上以后备队列形式进行组织，等待作业调度程序将作业调度到内存。执行状态:作业被调度到内存，为作业分配资源并为其创建与之对应的进程，进程获得CPU，开始运行。3.1.1高级调度（续）完成状态:从作业的第一个进程完成开始，直到作业所有的进程完成，释放作业所占用的资源，退出系统的整个进程。作业状态及其转换如图3.2所示。执行状态就绪运行阻塞后备状态提交状态完成状态图3.2作业状态及其转换3.1.1高级调度（续）作业状态的划分比进程状态的划分更粗，进程是作业全部状态中的一个阶段体现。作业调度将作业从后备状态转换到内存执行状态。作业执行状态包含作业所对应进程的就绪、运行和阻塞状态。在分时操作系统和实时操作系统中，终端用户的作业直接送入到内存，不需要作业调度。操作系统需要完成的功能是决定是否能够为作业创建进程。分时操作系统和实时操作系统也支持批处理作业，在批处理作业存在时，也能够完成作业调度。3.1.2中级调度中级调度又称为中程调度，是为了提高内存利用率和平衡系统负载而采取的一种利用外存补充内存的措施。在多进程环境下，内存中的多个进程，其中有些进程可能需要挂起，这些进程暂时不参与对处理器的竞争。为了充分利用内存资源，系统会采用进程对换的方法将进程换出到外存，将这些进程占用的内存空间释放，让内存能够接纳新的进程或使得内存中的进程能够更快推进。当被换出到外存中的进程挂起时间到时，又需要将这些进程换入到内存。中级调度是在换出内存的进程中确定需要进入内存的进程。3.1.2中级调度当进程需要换入内存，而内存资源不充足时，则系统需要选择内存中的进程换出外存，让出内存空间给进入内存的进程。中级调度根据内存中能够接纳的进程数来平衡系统负载，起到在一定时间内平滑和调整系统负载的作用。1．低级调度低级调度又称为进程调度、短程调度，是按照一定的调度算法从内存的就绪进程队列中选择进程，为进程分配处理器。进程调度发生在内存中的就绪进程，被调度的进程从内存就绪到处理器中执行的过程，该过程很短，被称为短程调度。中级调度位于高级调度与低级调度之间，被称为中程调度。中级调度主要用于内存管理，特别是虚拟存储器管理。3.1.3低级调度作业调度发生进程位于外存与进入计算机内存之间，经过的过程最长，因此，作业调度被称为长程调度。进程调度与作业调度和中级调度比较，进程调度发生的频率最高，作业调度发生的频率最低。3.1.3低级调度处理器调度的三级模型如图3.3所示。3.1.3低级调度图3.3处理器三级调度模型进程挂起就绪队列进程阻塞队列进程挂起阻塞队列进程就绪队列完成中级调度低级调度处理器高级调度作业后备队列交互式用户提交用户作业3.1.3低级调度（续）2．引起进程调度的主要原因（1）处理器执行的进程完成任务，处理器空闲；（2）处理器执行的进程转入阻塞状态，此时处理器空闲；（3）处理器执行的进程被其它进程抢占；（4）处理器执行的进程被挂起。3.1.3低级调度（续）3．进程调度中的基本机制（1）排队器。为使进程调度时能够快速有效地找到就绪队列中的每个进程，首先应该按照一定的方式将进程就绪队列排成一个或多个队列。（2）分派程序。分派程序将根据进程调度策略将所选中的进程从就绪队列中移出，然后进行进程上下文的切换，并将处理器分配给进程。（3）上下文切换机制。上下文切换机制是指在操作系统分派程序的执行下完成处理器的切换过程，实现进程上下文切换3.1.3低级调度（续）4．进程切换的实现进程切换需要完成进程上下文切换，进程状态、进程等待时间等信息的改变。新、老进程切换如图3.4所示。老进程新进程CPU图3.4进程调度中的进程切换进程切换过程描述？3.1.3低级调度（续）进程切换需要完成以下工作：保存并恢复处理器信息。处理器中的寄存器保存了当前正在执行进程的相关数据和状态，在进程被切换时，必须将进程的这些信息保存到进程控制块中，以便进程被处理器再次执行时，能够将进程的断点信息从进程控制块拷贝回处理器寄存器中，保证处理器能够从进程的上次断点开始继续向前推进。处理器中寄存器信息写到老进程的进程控制块中，新进程的进程控制块信息被拷贝到处理器的寄存器中。3.1.3低级调度（续）更新进程控制块中的进程状态、进程达到时间、进程等待时间、进程优先级变化等信息，并将进程控制块移到相应的进程队列。被切换的进程状态从执行改为就绪或阻塞，其进程控制块也被插入就绪队列或阻塞队列。同样，被分配处理器的进程，其状态从就绪改为执行，进程控制块从就绪队列中移出。更新存储器管理数据结构，维护进程的代码段和数据段。3.1.3低级调度（续）5．进程调度中的非抢占（nonpreemptive）调度和抢占（preemptive）调度非抢占式调度是一种通常的调度方式，在非抢占调度中，处理器分配给进程后，一直到进程结束或进程阻塞，进程才自动放弃处理器。非抢占调度存在什么问题？若执行进程正好在执行一个没有资源的无限循环，则执行进程不会放弃处理器，所有的就绪进程会永久等待，系统进入了一种僵持的状态。解决方法?如果此时系统能够自身定期强制执行进程中断，则可以避免这种僵持状态。3.1.3低级调度（续）强制执行进程中断的调度方