操作系统第2章

《操作系统第2章》由会员分享，可在线阅读，更多相关《操作系统第2章（154页珍藏版）》请在金锄头文库上搜索。

1、第 2 章 处理机管理 2.1 处理机管理概述 2.2 进程 2.3 进程控制 2.4 进程同步与互 斥 2.5 进程通信 2.6 进程调度 2.7 进程死锁 2.8 线程的基本概 念 2.1 处理机管理概述在计算机的各种硬件资源中，处理机是最重要的资源，也是最紧俏的资源。 2.1.1 处理机管理的功能处理机管理的主要任务是对处理机进行分配，对进程的控制和管理。处理机管理的主要功能有进程控制、进程同步、进程通信和进程调度和进程死锁。2.1.2 前趋图前趋图是一个有向无循环图。图中的每个结点可用 于表示一条语句、一个程序段等；结点间的有向边表示 在两个结点之间存在的前趋关系。前趋 ，后继 ，初始

2、结点 ，终止结点 图2-1 具有6个结点的前趋图P 2P 3P 4P 5P 6P 12.1.3 程序的顺序执行及其特征若一个计算由若干操作组成，而这些操作必须按照 某种先后次序执行，这类计算过程就是程序的顺序执行 ，由这些操作构成的程序称为顺序程序。比如，有如下 程序：它的执行顺序是：ICP输入计算打印如果有2个程序需要执行，则执行顺序为： 程序顺序执行时的特征： （1）执行的顺序性严格按照程序所规定的顺序执行。只有前一段执行结束，后一 段程序才能开始。 （2）环境的封闭性在单道程序环境下，程序一旦开始执行，其计算结果不受外界 因素影响。程序在运行时独占所有资源，资源的状态只有本程序能 够改变

3、它。 （3）计算过程的可再现性只要程序执行的环境和初始条件相同，程序无论重复执行多少 次，按何种方式执行，都将获得相同的结果。（与时间无关性）I1C1P1I2C2P2图2-2 程序顺序执行时的前趋图2.1.4 程序的并发执行在引入了操作系统后，程序可以并发执行。对于上 例程序的执行情况如下: I1I2I3I4C1C2C3C4P1P2P3P4图2-3 程序并发执行时的前趋图（1）程序并发执行时的特征 间断性表现为“执行暂停执行执行”的间断性活动规律 。 失去封闭性封闭性是指程序独占资源，程序在执行时，不会受 到其它程序的影响。现在程序不再独占资源，而是多个 程序共享资源，因此封闭性也不复存在。

4、不可再现性由于程序执行时失去了封闭性，也将导致失去可再 现性，既使并发程序执行的环境和初始条件相同，程序 的多次或以不同方式的执行，也可能获得不相同的结果 。程序的执行将与时间有关。（2）进程并发执行的判断方法判断程序能否并发执行的方法有2种：Bernstein（巴斯滕）条件和前趋图。 Bernstein条件（时间无关性条件）即不同运算（或程序）的读集与写集的交集和写集与写集的交集的并集为空集时，这几个运算（或程序）可以并发执行。运算的读集是指在运算执行期间引用的所有变量的集合，运算的写集是指在运算执行期间要改变的所有变量的集合。如：运算w=x+y，其读集是x,y，其写集是w。 例2-2 有四

5、条语句，哪些语句可以并发地执行？s1：a=x+y;s2：b=z+1;s3：c=a-b;s4：d=c+1;分析：4个语句的读集与写集分别是：读集：R(s1)=x,y, R(s2)=z, R(s3)=a,b, R(s4)=c写集：W(s1)=a, W(s2)=b, W(s3)=c, W(s4)=d由Bernstein条件可知s1与s2可以并发执行。 利用前趋图画出程序执行的前趋图，根据该程序或运算在前趋 图中的位置关系，可以判断其能否并发执行。即在程序 或运算的先后顺序上，只有前后相邻的程序或运算不能 并发执行，其余程序和运算都可以并发执行。 例2-3 已知一个求值公式(A2+3B)/(B+5A)

6、，若A、B已赋值 ，试画出该公式求值过程的前趋图，并判断哪些求值过 程可以并发执行。 分析：把公式(A2+3B)/(B+5A)按运算顺序分解，可以产生 如下运算步骤：s1s6，如图2-4（a）所示；根据分解 的运算顺序画出它的前趋图，如图2-4（b）所示。 能够并发执行的运算是：s1与s2、 s1与s3、 s2与s3、s1与s5、s2与s5、 s3与s4、s4与s5，其余的运算不能并发执行。s1s2s3s4s5s6x1=a*ax2=3*bx3=5*ax4=x1+x2x5=b+x3x6=x4/x5运算顺序前趋图2.2 进程（process）2.2.1 进程的定义和特征 1进程的定义进程是一个可并

7、发执行的具有独立功能的程序关于某个数 据集合的一次执行过程，也是操作系统进行资源分配和保护的 基本单位。操作系统中为什么要引入进程呢？ （1）刻画系统的动态性程序是一个静态的概念，它无法描述程序的执行过程这样 一个动态的过程。 （2）正确描述程序的执行状态 在多道程序环境下，程序与计算（程序的执行）不再一一 对应。2进程的特征动态性、并发性、独立性、异步性、结构性（1）动态性 进程是程序在数据集合上的一次执行过程，它由创建 而产生，因调度而执行，因得不到资源而暂停，因撤销而 消亡。 （2）并发性并发性是指多个同在主存中的进程，能在一段时间内同时运行、交替使用处理器的情况。并发性是进程也是 操作

8、系统的重要特征。（3）独立性独立性是指进程是一个能独立运行、独立分配资源和独立接受调度的基本单位。凡是未建立进程的程序都不能 参加运行。 （4）异步性指系统中的进程按各自独立的、不可预知的速度向前推进。 （5）结构性 进程由三部分组成 ：程序块、数据块和进程控制块。2.2.2 进程的状态和转换 1进程的三种状态 （1）就绪状态当进程分配到除处理器（CPU）以外的所有必要资 源后，只要再获得处理器就可以立即执行，这时进程的 状态称为就绪状态。 （2）执行状态处于就绪状态的进程一旦获得了处理器，就可以运 行，进程状态也就处于执行状态。 （3）阻塞状态（等待状态）正在执行的进程因为发生某些事件（如请

9、求输入/输 出、申请额外空间等）而暂停运行，这种受阻暂停的状 态称为阻塞状态，也称为等待状态。 三种状态之间的转换如图所示。 进程调度I/O请求阻塞就绪执行时间片完I/O完成2.进程的五种状态 （1）新状态当一个新进程刚刚建立，还未将其放入就绪队列时 的状态，称为新状态。 （2）终止状态当一个进程已经正常结束或异常结束，操作系统已 将其从系统队列中移出，但尚未撤消，这时称为终止状 态。终止新状态进程调度I/O请 求阻塞就绪执行时间片完I/O完成3进程的挂起状态（静止状态）（1）进程挂起的原因当内存中的所有进程都处于阻塞状态时（因为I/O活动比计算速度慢得多，所以这种情况很可能出现），就 可以通

10、过“交换”（swapping）的方法将阻塞进程换出到 磁盘的“挂起队列”（suspendqueue），这时进程就处于挂起状态。然后取出挂起队列中的另一个进程，或者接受一个新进程的请求，将其纳入内存运行。通常比较倾向于调 入一个以前被挂起的进程，给它提供服务，而不是增加 系统中的负载总数。 （2）挂起状态的转换挂起状态又称为静止状态，一个就绪进程被挂起， 变为静止就绪状态；阻塞状态进程被挂起，称为静止阻 塞。处于静止状态的进程保存在磁盘上，它只有被对换 到主存才能被调度执行。2.3 进程控制 进程控制的主要任务是：创建进程、阻塞进程、唤醒进程和撤销进程。 2.3.1 进程控制块PCB （Proc

11、ess Control Block） 1进程控制块的作用进程控制块是进程实体的重要组成部分，是操作系统中最重要的记录型数据，在PCB中记录了操作系统所需要的、用于描述进程情况及控制进程运行所需要的全部信息。2进程控制块的内容（1）进程标识信息进程标识符用于唯一地标识一个进程，它分为： 外部标识符：由用户（其它进程）使用，由字符串组 成。 内部标识符：由系统使用，由数字组成的进程号。（2）进程调度信息进程调度信息是关于进程调度和进程状态的信息。 进程优先权。 进程调度所需的其它信息。如等待时间、已执行时间 等。 进程状态。 阻塞事件。（3）现场信息任何一个进程在让出处理机时必须把此时的处理机现场

12、信息保存到进程控制块中，当该进程重新恢复运行时应恢复处理机现场。 通用寄存器。 指令计数器。 程序状态字（PSW）。 用户栈指针。作业： 尽可能详细地介绍中断（包括中断的概念、中断处理过程等）（4）进程管理信息（进程控制信息） 程序和数据的地址。所在的主存和外存的地址。 进程同步和通信机制。信号量和消息队列指针等。 资源清单。列出了进程所需的和已分配到的资源。 链接指针。下一个进程的PCB的首地址。 3进程控制块的组织方式（1）链接方式把具有相同状态的PCB，用其中的链接指针链接成队列。 就绪队列、 阻塞队列、空闲队列执行指针就绪队列指针阻塞队列指针空闲队列指针PCB2PCB3PCB4PCB5

13、PCB6PCB7PCB16307011（2）索引方式 系统按照进程的状态建立索引表。例如就绪索引表、阻塞索引表等，并把各个索引表在主存的首地址记录在 主存中的专用单元里，也可以称为表指针。 比较以上两种方式的特点，链接方式是插入和删除操作很方便，查找速度慢；索引方式查找速度快，但因为索引表是线性的，因此插入和删除操作麻烦。因为进程的主要操作就是插入和删除，因此，链接方式使用更多一些。4进程控制原语原语是指具有特定功能的不可被中断的过程。它是一些系统功能模块，主要用于实现操作系统的一些专门 控制操作。用于进程控制的原语有：创建原语、撤销原语、阻塞原语、唤醒原语（1）创建原语用于为一个进程分配工作

14、区和建立PCB，置该进程 为就绪状态。 （2）撤销原语用于一个进程工作完后，收回它的工作区和PCB。（3）阻塞原语用于进程在运行过程中发生等待事件时，把进程 的状态改为等待状态。 （4）唤醒原语用于当进程等待的事件结束时，把进程的状态改 为就绪状态。2.3.2 进程的创建与撤销1进程的创建（1）引起创建进程的事件 提交一个批处理作业 在终端上一个交互式作业登录 操作系统创建一个服务进程 用户进程提出某种请求，系统将专门创建一个进程来提供用户所需要的服务。如用户进程要求打印，操作系统将为之创建一个打印进程。 存在的进程创建新的进程（子进程）（2）进程的创建过程 在主进程表中增加一项（数字进程号）

15、，并从空闲PCB队列中申请一个空PCB。 为新进程的程序、数据和用户堆栈分配相应的主存空间，并为其分配所需资源。 初始化PCB中的相应信息，如标识信息、处理器信息、进程控制信息等。 把进程加入就绪队列或直接将进程投入运行。 2进程的撤销（1）引起进程撤销的事件 进程正常结束。即程序执行到最后一条指令后。如C语言函数的最 后一条指令return，执行之后，结束该函数。 在进程运行期间，由于出现某些错误和故障而使得进 程被迫中止。如越界错误、非法指令错、超时故障、运行超时、 等待超时、算术运算错、I/O故障等。 进程应外界的请求而中止运行。如操作员或操作系统要求、发生死锁、父进程干预 或结束。（2

16、）进程撤销的过程 根据撤销进程标识号，从相应队列中找到它的PCB。 若该进程处于执行状态，则立即终止该进程的执行，并转去执行进程调度程序，再调入一个进程执行。 若该进程有子进程，还要将其子进程终止，以防止它们成为不可控制的进程。 将该进程所占用的资源回收，归还给其父进程或操作系统。逐级归还。 撤销进程出队，将它的PCB放入空闲队列。 2.3.3 进程的阻塞与唤醒1. 阻塞与唤醒阻塞：进程让出处理器，去等待一个事件。如：等待资源、等待I/O完成、等待一个事件发生。当阻塞发生时，进程自己调用阻塞原语阻塞自己，所以阻塞是进程的自主行为。唤醒：等待事件结束，处于阻塞状态的进程进入就绪状态。2进程阻塞的过程 停