第3章 处理器管理

  1. 多道程序设计。
    1. 什么是多道程序设计。
      1. 让多个计算问题同时装入一个计算机系统的主存储器并行执行,这种程序设计技术称为多道程序设计,这种计算机系统称为多道程序设计系统,或简称多道系统。
      2. 采用多道程序设计技术应注意以下三方面的问题。
        1. 存储保护。应采用存储保护的方法保证各道程序互不侵犯。
        2. 程序浮动。程序可以随机地从主存储器的一个区域移动到另一个区域,程序被移动后,仍丝毫不影响它的执行。这种技术称为程序浮动。
        3. 资源的分配和调度。
    2. 为什么要采用多道程序设计。
      1. 程序的顺序执行。一个计算问题往往要依照一定的顺序执行,执行的顺序是由编制的程序确定的。不能使多台设备同时忙碌。
      2. 程序的并行执行。现代计算的硬件都具有处理器与外围设备并行工作的能力。程序的并行执行发挥了处理器与外围设备并行工作的能力,使处理器的效率有所提高。但是由于处理器的执行速度远远高于外围设备的传输速度,所以还是会使处理器处于空闲状态。为进一步提高效率,可以考虑同时接纳两道或两道以上的计算问题。
      3. 多道并行执行。对于具有处理器与外设并行处理能力的计算机系统来说,采用多道程序设计技术后,能提高整个系统的效率。具体表现为:
        1. 提高了处理器的利用率。缩短了空闲时间。
        2. 充分利用外围设备资源。
        3. 发挥了处理器与外围设备以及外围设备之间的并行工作能力。
    3. 采用多道程序设计应注意的问题。
      1. 可能延长程序执行时间。在并行执行时,一道题的执行可能受到另一道题的制约。对每一道题来说,从开始执行到完成所需的时间有时会比单独执行所需的时间长。
      2. 并行工作道数与系统效率不成正比。并行的道数要根据系统配置的资源和用户对资源的要求而定。
  2. 进程概述。为了能正确反映程序执行时的活动规律和状态变化,我们要引进一个新概念——进程。
    1. 进程的定义。
      1. 可把程序看做具有独立功能的一组指令或一组语句的集合,或者说是指出处理器执行操作的步骤。
      2. 程序的执行必须依赖于一个实体——数据集。
      3. 把一个程序在一个数据集上的一次执行称为一个进程(Process)。
      4. 程序是静态的文本,进程是动态的过程。进程包括程序和程序处理的对象(数据集),进程实现了程序的功能。
      5. 静止的可以运输货物的火车可以看做是程序,载着货物正在行驶中的火车即列车,可以看做是进程。列车中的货物可以看做是数据集。
    2. 为什么要引入进程。
      1. 提高资源的利用率。
        1. 操作系统把一个计算问题中每个可独立执行的程序模块的一次执行看做一个进程。例如输入进程、处理进程、打印进程。
        2. 通过进程的同步可使这些进程正确合作,从而使处理器与外围设备以及各种外围设备之间有效地并行工作,提高资源的利用率。
      2. 正确描述程序的执行情况。
        1. 在多道程序设计的系统中,往往要同时处理多个用户的计算问题。从程序的角度已无法正确描述程序执行时的状态。
        2. 把完成操作系统功能的进程称为系统进程,完成用户功能的进程称为用户进程。
    3. 进程的属性。进程有如下一些基本属性。
      1. 进程的动态性。进程是动态的,它包含数据和运行在数据集上的程序。
      2. 多个不同的进程可以包含相同的程序。
        1. 一个程序运行在不同的数据集上就构成不同的进程,能得到不同的结果。
        2. 一个能被多个用户同时调用的程序在执行中,自身不能改变。
        3. 我们把一个能被多个用户同时调用的程序称为可再入的程序。
      3. 进程可以并发执行。同时执行的进程是轮流占用处理器的,把它们称为是并发执行的。
      4. 进程有三种基本状态。
        1. 等待态。等待某一事件,也称为阻塞态。
        2. 就绪态。等待系统分配处理器以便运行。
        3. 运行态。正在占用处理器运行。
        4. 进程状态变化的若干情况。
          1. 运行态→等待态。等待某一事件。
          2. 等待太→就绪态。等待的事件发生。一个结束等待的进程必须先转换成就绪态,当分配到处理器后才能运行。
          3. 运行态→就绪态。落选。占用处理器的时间用完或有更高优先级的进程要运行。
          4. 就绪态→运行态。选中。
      5. 根据上述四个基本属性可概括出进程具有如下三个特征:
        1. 动态性。进程是程序的一次执行过程,在执行过程中进程状态不断发生变化。
        2. 并发性。若干进程是可同时执行的,它们轮流占用处理器交替运行。
        3. 异步性。进程的执行速度取决于自身与外界原因以及能占用处理器的时间,因此以不可知的速度向前推进。
  3. 进程队列。
    1. 进程控制块。
      1. 为了标识进程,记录各个进程执行时的情况,操作系统在创建进程时为每一个进程设置一个进程控制块。英文名称是Process Control Block,缩写为PCB。
      2. 一般情况下,进程控制块应包含四类信息。
        1. 标识信息。每个进程都有唯一的标识符,可以用字符或编号表示。
        2. 说明信息。说明本进程的情况。如进程状态、进程程序存放位置、进程数据存放位置等。
        3. 现场信息。当进程让出处理器时,把各种现场信息保留下来。以便稍后继续执行。如通用寄存器内容、控制寄存器内容、程序状态字寄存器内容。
        4. 管理信息。是对进程进行管理和调度的信息。例如进程优先级、队列指针等。
    2. 进程的创建和撤销。
      1. 进程的创建。
        1. 当系统为一个程序分配了一个工作区(存放程序处理的数据集)和建立了一个进程控制块后就创建了一个进程。
        2. 一个刚刚被创建的进程,它的初始状态为就绪态。
      2. 进程的撤销。
        1. 当一个进程完成了特定的任务后,系统就收回这个进程所占的工作区和取消该进程的进程控制块,就撤销了该进程。
      3. 操作系统中往往设计一些能完成特定功能且不可中断的过程。我们把这些不可中断的过程称为原语。用于控制进程的原语有:
        1. 创建原语。
        2. 撤销原语。
        3. 阻塞原语。进行运行过程中发生等待事件时,把进程状态改为等待态。
        4. 唤醒原语。当进程等待的事件发生时,把进程状态改为就绪态。
    3. 进程队列的链接。
      1. 为了便于管理,经常把相同状态的进程链接在一起,称为进程队列。于是就有了就绪队列、等待队列。
      2. 进程队列可以用进程控制块的链接来形成。链接的方式有两种:单向链接和双向链接。
      3. 系统中负责进程入队和出队的工作称为队列管理。
  4. UNIX系统中的进程。
    1. UNIX进程的特点。
      1. 通常,操作系统把进程分成系统进程和用户进程,分别执行操作系统程序和用户程序。
      2. 但是,UNIX却不是这样划分进程的。UNIX不区分系统进程和用户进程,UNIX中的进程既可执行操作系统程序又可执行用户程序,按照需要进行切换。
      3. UNIX中的进程在执行用户程序时应在用户态执行,执行操作系统程序时应在核心态执行。
    2. UNIX进程的组成。UNIX中的每一个进程由三部分组成:进程控制块、正文段和数据段。
      1. 进程控制块。
        1. 为节省进程控制块所占用的主存空间,UNIX把每个进程控制块分成两部分:进程基本控制块和进程扩充控制块。
        2. 进程基本控制块常驻在主存储器中。它记录了进行进程调度时必须使用的一些信息。在UNIX中,把进程基本控制块中的数据结构称为proc结构。
        3. 进程扩充控制块非常驻在主存储器中。通常把进程扩充控制块存放在磁盘上被称为“对换区”的存储区域中。在UNIX中,把进程扩充控制块中的数据结构成为user结构。
        4. 进程基本控制块。
          1. UNIX设置了一张进程表。每个进程占据其中一个表项,作为其进程基本控制块。结构省略。
          2. 可以把proc结构中的信息分成以下几类:
            1. 标识信息。包括用户标识和进程标识。
            2. 有关进程非常驻主存部分的信息。
            3. 有关进程调度的信息。
            4. 其他信息。这是用于管理和控制的信息。
        5. 进程扩充控制块。
          1. 每个进程都有一个进程扩充控制块。结构省略。
          2. 进程扩充控制块中的信息大致可分为如下几类:标识、现场保护、主存管理、文件读写、系统调用,以及进程控制和管理等。
      2. 正文段。
        1. 在UNIX中把可供多个进程共享的程序称为进程的正文段。
        2. 正文段是可再入的程序,它由不可被修改的程序和常数组成。
        3. 为了管理可共享的正文段,UNIX设置了一张正文表text[]。表项的结构省略。
      3. 数据段。
        1. 进程的数据段包括进程执行时的非共享程序和程序执行时用到的数据。
          1. UNIX把进程的数据段分成三个部分:用户栈区、用户数据区和系统工作区。
          2. 系统工作区又由核心栈和user区两部分组成。
    3. UNIX进程的状态。
      1. 运行状态。进程正占用处理器运行。当进程执行用户程序时在用户态运行;当发生中断事件或请求系统调用时就要执行系统程序,因而转入核心态运行;当系统程序完成工作后,进程又返回用户程序,故再回到用户态运行。
      2. 就绪状态。如果处于就绪状态的进程在磁盘的对换区中,则必须先由“交换进程”(称为0进程)把它换入主存储器,然后才能调度它去运行。
      3. 睡眠状态。进程为等待某事件而让出处理器便进入睡眠状态。
      4. 创建状态。UNIX用系统调用fork创建进程。在创建过程中,处于变迁阶段的状态称为创建状态,创建状态是进程的初始状态,最终它会称为就绪状态。
      5. 僵死状态。这是进程消亡前的暂时状态。
    4. UNIX进程的创建和终止。
      1. UNIX的进程树。
        1. 当计算机系统被启动后,首先把UNIX的核心程序装入内存。
        2. 核心程序在做完自身的初始化工作后,建立系统的第一个进程。在UNIX系统中,把这个进程称为0号进程。0号进程始终在核心态运行。它的功能是进行进程调度和让进程在主存和磁盘上进程交换。故也把0号进程成为交换进程。
        3. 由0号进程再创建一个被称为初始化进程的1号进程。1号进程在用户态运行。每当有终端用户请求注册时,1号进程就为该用户创建一个login进程。
        4. 若用户注册成功,则login进程就为该用户再创建一个shell进程。
        5. 每个shell进程等待用户输入命令。shell进程执行shell命令解释程序,对接收到的命令进程分析,分析后再创建一个进程去执行该命令。
        6. 执行命令的进程可根据需要再继续创建进程。一条命令执行完后,又返回到shell进程等待下一条命令。
        7. UNIX系统中的进程构成了一个树形结构的进程簇。UNIX把被创建的进程称为创建者的子进程,创建者就是子进程的父进程。
      2. 进程的创建。
        1. 在UNIX系统中,除0号进程和1号进程外,其他进程总是通过系统调用fork来创建新进程,形成父子关系。
        2. fork的主要工作。略。
      3. 进程的终止。
        1. UNIX为每个用户创建的第一个进程是shell进程。
        2. 父进程是用系统调用wait等待其子进程终止的。
        3. 当命令处理结束时,子进程是用系统调用exit请求终止自己,并释放父进程的。
        4. 一个进程终止后,其父进程的善后工作主要是释放子进程的proc和user,以及把子进程所用的时间累加到父进程中。
    5. UNIX进程的换进换出。
      1. 在UNIX中经常要发生进程在主存与磁盘之间的转换,我们把这项工作称为进程的换进换出。
      2. 在UNIX中,进程的换进换出工作是由0号进程(交换进程)来做的。它执行sched程序来完成换进换出的工作。
      3. sched的工作流程。略。
      4. 标识runout和runin是交换进程的睡眠标识。
      5. UNIX规定,一个进程被换出前必须至少在主存驻留2s。同样,一个在磁盘对换区的进程要换进时也必须至少在对换区驻留2s。
    6. UNIX进程的睡眠与唤醒。
      1. 进程的睡眠。
        1. 一般来说,进程总是在执行一个系统调用时被确定是否应睡眠。
        2. 在确定一个进程需要睡眠时,便调用sleep程序让进程进入睡眠状态,且将其链入睡眠队列。还必须判断是否有runin标识,在进行后续操作。
      2. 进程的唤醒。
        1. 系统通过调用wakeup程序来唤醒等待相应事件的进程。
        2. wakeup程序根据发生的事件找到那些因等待事件而睡眠的进程。
        3. 如果在磁盘对换区中有进程被唤醒,则还要判断是否有runout标志。
  5. 中断技术。
    1. 中断和中断类型。
      1. 一个进程占有处理器运行时,由于自身或外界的原因使运行被打断,让操作系统处理所出现的事件,到适当的时候再上被打断的进程继续运行。我们称这个进程在运行中被中断了,引起中断的事件称为中断源,对出现的事件进程处理的程序称为中断处理程序。
      2. 从中断事件的性质来说,可以分成以下两大类。
        1. 强迫性中断事件。这类事件不是正在运行的进程所期待的,而是由于外部的请求或某些意外事故而迫使正在运行的进程被打断。强迫性中断事件大致有以下几种:
          1. 硬件故障中断。例如电源电压超出规定范围,主存储器读写时发生校验错等。
          2. 程序性中断事件。例如使用了非法操作码,地址越界等。
          3. 外部事件中断。例如用户从终端上输入了一条命令,设备的定时时钟的时间已到等。
          4. 输入/输出中断事件。例如外围设备在执行信息传输操作时出现故障。
        2. 自愿性中断事件。
          1. 这是正在运行的进程所期望的中断事件,是正在运行的进程执行一条“访管指令”请求系统调用为其服务所引起的中断。
          2. 我们经常把自愿性中断称为访管中断。
    2. 中断响应。
        1. 通常,处理器每执行完一条指令后,硬件的中断装置立即检查有无中断事件发生。若有中断事件发生,则暂停现行进程的执行,让操作系统的中断处理程序占用处理器。这一过程称为中断响应。
        2. 中断字寄存器。
          1. 它是记录强迫性中断事件的寄存器。
          2. 对每一种强迫性中断事件都可设置一个中断字寄存器,分别对应硬件故障中断、程序性中断以及外部中断。
        3. 程序状态字和程序状态字寄存器。
          1. 程序状态字(Program Status Word,缩写为PSW)是用来控制指令执行顺序并且保留和指示与程序有关的系统状态。一般来说,程序状态字包含如下三部分内容。
            1. 程序基本状态。
              1. 指令地址——指出下一条指令的存放地址。
              2. 条件码——指出指令执行结果的特征。
              3. 目态/管态。
              4. 等待/计算。
            2. 中断码。保存程序执行时当前发生的中断事件。
            3. 中断屏蔽位。指出程序执行中发生中断事件时,要不要响应出现的中断事件。
          2. 在计算机系统中,对每个处理器设置一个用来存放当前运行进程的PSW的寄存器,该寄存器称为程序状态字寄存器。
        4. 中断响应。
          1. 为了说明中断响应过程,必须区分三种PSW。
            1. 当前正在占用处理器的进程的PSW,称为当前PSW。
            2. 中断处理程序的PSW称为新PSW。新PSW中存放着中断处理程序的入口地址。
            3. 保护好的被中断进程的PSW称为旧PSW。
          2. 中断装置通过交换PSW完成中断响应,使被中断的进程让出处理器,且使处理按照中断处理程序的新PSW控制执行。
          3. 当中断处理程序占用了处理器时,它只要从保护好的旧PSW中取出中断码,分析发生的具体事件,就可对中断事件进行处理。
    3. 中断事件的处理。中断处理程序的主要工作有如下几个方面:
      1. 保护被中断进程的现场信息。
      2. 分析中断原因。
      3. 处理发生的中断事件。各类中断事件的处理原则:略。
    4. 中断优先级和中断屏蔽。
      1. 在计算机系统中,每一个瞬间可能有几个中断事件同时发生。
      2. 一般来说,终端装置是按预定的顺序响应同时出现的中断事件。这个预定的顺序称为中断优先级。
      3. 中断优先级是按中断事件的重要性和紧迫程度来确定的,是在硬件设计时固定的。
      4. 我们希望在一个中断处理程序没有结束之前,不要再响应其他的中断事件,或只响应比当前级别高的中断事件。为此,计算机系统采用中断屏蔽技术。
      5. 利用程序状态字PSW中的中断屏蔽位来指出要不要响应出现的中断事件。
  6. UNIX系统的中断技术。
    1. 中断事件和异常情况。
      1. 在UNIX中把可能出现的事件分成两大类:中断事件和异常情况。
      2. 如果出现的事件和正在运行的进程无关,则把这些事件称为中断事件。例如I/O中断事件、时钟中断事件、电源故障中断事件等。
      3. 如果出现的事件与正在运行的进程有关,则把这些事件称为异常情况。异常情况都是在执行指令时捕捉到的,例如执行到一条trap指令或地址错、地址越界等。
    2. 处理器状态字。
      1. UNIX用一个由32位组成的字作为处理器状态字(记为ps),可以把它看做UNIX中的PSW。
      2. 处理器状态字ps的结构:略。
      3. 我们把操作系统设置的中断称为软中断。
      4. 每个进程都有自己的ps,当进程运行时就把它的ps送入处理器状态字寄存器中。
    3. 中断处理。
      1. 中断响应。
        1. 在UNIX中,不同的事件由不同的处理程序来处理。为此,系统设置了一张处理程序入口表。每个表项的内容有发生的事件、处理程序的入口地址、处理程序的处理器状态字等。
        2. UNIX把存放指令地址的寄存器称为程序计数寄存器。处理器总是按该寄存器指示的地址(指令地址,UNIX把它记为pc)去取指令。
        3. 中断响应过程与中断屏蔽:略。
      2. 中断处理过程。
        1. 对中断事件和异常情况处理过程的不同:略。
        2. 当硬件响应中断后,UNIX处理程序的工作可分为现场保护、分析处理、恢复现场三个阶段。
  7. 处理器调度。
    1. 处理器的两级调度。
      1. 我们把在批处理操纵系统控制下的作业称为批处理作业。
      2. 在操作系统中,我们把磁盘上用来存放作业信息的专用区域称为输入井,把在输入井中等待处理的作业称为后备作业。
      3. 我们把从输入井中选取后备作业装入主存储器中的工作称为作业调度。
      4. 作业调度的必要条件:系统现有的尚未分配的资源可以满足被选作业的资源要求。
      5. 若有多个进程被装入主存储器,则就创建了多个主存储器。这些进程的初始状态都是“就绪态”。
      6. 我们把从就绪状态的进程中选取一个进程,让它占用处理器的工作称为进程调度。
      7. 作业调度与进程调度相互配合能实现多道作业的并行执行。
      8. 我们把在分时操作系统控制下的作业称为终端作业。
    2. 批处理作业的调度算法。
      1. 在设计调度算法时,可考虑如下原则:
        1. 公平性——对用户公平,不能无故或无限制的拖延一个作业的执行。
        2. 平衡资源使用——尽可能是系统资源都处于忙碌。
        3. 极大的流量——在单位时间内为尽可能多的作业服务,保证计算机系统的吞吐能力。
      2. 假定作业i进入输入井的时间为Si。若它被选中执行,得到计算结果的时间为Ei,那么它的周转时间就定义为Ti=Ei-Si。
      3. 从系统的角度来说,希望进入输入井的作业的平均周转时间尽可能的小。
      4. 周转时间和平均周转时间与选用的调度算法有关。常用的作业调度算法有:
        1. 先来先服务算法。
          1. 注意,只有满足必要条件的作业才可能被选中。
          2. 先来先服务算法具有一定的公平性,容易实现。
          3. 可能由于时间长的作业被先选中,使计算时间短的作业长时间的等待,从而也增加了平均周转时间,降低了系统的吞吐率。
        2. 计算时间短的作业优先算法。
          1. 这种算法能降低作业的平均周转时间,从而提高系统的吞吐能力。
          2. 实际上,我们可以证明采用计算时间短的作业优先算法,能使平均周转时间最小。
          3. 采用该算法需要注意两个问题:
            1. 该算法是以用户估计的计算时间为准。
            2. 会使进入输入井早但要求计算时间长的作业等待很长时间。
        3. 响应比高者优选算法。
          1. 响应比高者优先算法综合考虑等待时间和计算时间,我们把响应比定义为:响应比=等待时间/计算时间。
          2. 采用响应比高者优先算法进行调度时,必须先计算出输入井中资源能得到满足的所有作业的响应比,然后从中选择响应比最高者优先装入主存储器。
        4. 优先级调度算法。
          1. 为每个作业确定一个优先级,资源能满足且优先级高的作业被优先选取。
          2. 确定作业的优先级。
            1. 一种方法是用户自己来提出作业的优先级。
            2. 另一种方法是操作系统根据作业的缓急程度、作业估算的计算时间、作业的类型、资源申请情况等因素综合考虑。分析这些因素在实现系统设计目标中的影响,决定因数的比例,总和得出作业的优先级。
        5. 均衡调度算法。尽可能地使得使用不同资源的作业同时执行。
    3. 进程调度算法。
      1. 我们把一个进程让出处理器由另一个进程占用处理器的过程称为进程切换。
      2. 进程的切换是由进程状态的变化引起的。在下列情况下均会引起进程的切换:
        1. 一个进程从运行状态变成等待状态。
        2. 一个进程从运行状态变成就绪状态。
        3. 一个进程从等待状态编程就绪状态。
        4. 一个进程完成工作后被撤销。
      3. 常用的进程调度算法有以下几种。
        1. 先来先服务调度算法。
          1. 这种调度算法是按照进程进入就绪队列的先后次序来选择可占用处理器的进程。
          2. 一旦一个进程占用了处理器,它就一直运行下去,直到该进程完成工作而结束或者因等待某事件而不能运行才让出处理器。
          3. 可能会使进程等待分配处理器的平均时间较长。
        2. 最高优先级调度算法。
          1. 对每一个进程给出一个优先级,进程调度总是让当时具有最高优先级的进程先使用处理器。
          2. 对一个高优先级的进程占用处理器后,又可分两种方式来对待它。
            1. 第一种方式是非抢占式的。占有了处理器就一直运行下去。
            2. 第二种方式是可抢占式的。严格保证任何时刻总是让具有最高优先级的进程在处理器上运行。
          3. 这种抢占式的优先级调度算法在实时系统中很有用。
          4. 如何为进程确定优先级:略。
        3. 时间片轮转调度算法。
          1. 时间片是允许进程一次占用处理器的最长时间。
          2. 时间片轮转调度算法规定进程一次连续占用处理器的时间不能超过预定的时间片。
          3. 在分时操作系统中,经常采用时间片轮转调度算法。
          4. 时间片的值应根据进程要求系统给出应答的时间和进入系统的进程数来决定。
          5. 可对每个进程规定相同或不同的时间片。
        4. 分级调度算法。这种调度算法是,由系统设置多个就绪队列。具体调度原则略。
    4. UNIX系统的进程调度算法。UNIX的进程调度采用了动态优先数调度算法。
      1. 优先数和优先权。
        1. UNIX中每个进程都有一个优先数,进程的优先数随进程的执行情况而变化。
        2. 优先数越小则优先权越高。进程调度总是让优先权高的进程先占用处理器,占用处理器的进程每次可使用一个规定的时间片。
      2. 进程的优先权。UNIX确定进程优先权的原则如下:
        1. 进入核心态运行的进程的优先权高于在用户态运行的进程的优先权。
        2. 一个进程因用完了一个时间片而被剥夺处理器时,应降低该进程的优先权,以使其他进程有机会使用处理器。
        3. 对进入睡眠的进程,系统将按照它们等待事件的轻重缓急程度赋予它们不同的优先权。
        4. 应相应降低累计使用处理器时间较长的进程的优先权,以减少这些进程使用处理器的机会。
      3. 进程的优先数。根据确定进程优先权的原则,UNIX采用两种方法来确定进程的优先数:设置法和计算法。
      4. 进程调度程序switch。
        1. 在UNIX系统中,进程调度工作由switch程序来完成。
        2. 在下列情况下就要启动switch程序重新启动选择一个进程占用处理器。
          1. 进程完成了预定的工作而终止;
          2. 进程因等待某些事件而进入睡眠状态;
          3. 进程用完了一个规定的时间片;
          4. 发现有比现行进程更高优先权的进程;
          5. 对捕获到的异常情况处理结束后。
        3. 进程调度程序switch的主要任务是:在主存就绪的进程中,选取一个优先数最小的进程;为被选中的进程恢复现场信息。

发表评论

电子邮件地址不会被公开。 必填项已用*标注