进程管理经典培训讲义(编辑修改稿)

进程管理经典培训讲义(编辑修改稿)内容摘要：

„„ 图 8 进程家族结构图 在操作系统中，某些被进程调用的操作，例如队列操作、对信号灯的操作、检查启动外设操作等，一旦开始执行，就不能被中断，否则就会出现操作错误，造成系统混乱。 所以，这些操作可以用原语来实现。 原语是操作系统核心（不是由进程而是由一组程序模块所组成）的一个组成部分，并且常驻内存，通常在管态下执行。 原语一旦开始执行，就要连续执行完，中间不允许中断。 1. 创建进程原语 通过创建原语完成创建一个新进程的功能。 由于进程的存在是以其进程控制块为标志的，因此，创建一个 新进程的主要任务是为进程建立一个进程控制块 PCB，将调用者提供的进程 0 进程 1 进程 2 进程 3 进程 n 进程 5 进程 6 进程 4 中国最大的管理资源中心 39 有关信息填入该 PCB 中，并把该进程控制块插入到就绪队列中。 所以，创建一个新进程的过程是：首先申请 PCB空间，根据建立的进程名字查找 PCB表，若找到了则非正常终止 (即已有同名进程 )，否则，申请分配一块 PCB 空间；其次，为新进程分配资源，若进程的程序或数据不在内存中，则应将它们从外存调入分配的内存中；然后把有关信息 (如进程名字、信号量和状态位等 )分别填入 PCB 的相应栏目中；最后把 PCB 插入到就绪队列中。 能够导致创建进程的事件主要有：用户登录、作 业调度、提供服务和应用请求。 前三种由系统内核直接调用创建原语创建新进程，后一种由用户调用操作系统提供的系统调用完成创建任务，如 Linux中的 fork( )系统调用。 撤销进程原语 进程完成了其“历史使命”之后，应当退出系统而消亡，系统及时收回它占有的全部资源以便其它进程使用，这是通过撤销原语完成的。 撤销原语的实现过程是：根据提供的欲被撤销进程的名字，在 PCB 链中查找对应的 PCB，若找不到要撤销的进程的名字或该进程尚未停止，则转入异常终止处理程序，否则从 PCB 链中撤销该进程及其所有子孙进程 (因为仅撤销该进程 可能导致其子进程与进程家族隔离开来，而成为难以控制的进程 )；检查此进程是否有等待读取的消息，有则释放所有缓冲区，最后释放该进程的工作空间和 PCB 空间，以及其它资源。 撤销原语撤销的是标志进程存在的进程控制块 PCB，而不是进程的程序段。 这是因为一个程序段可能是几个进程的一部分，即可能有多个进程共享该程序段。 3. 阻塞进程原语 一个正在运行的进程，因为未满足其所申请的资源而会被迫处于阻塞状态，等待所需事件的发生，进程的这种状态变化就是通过进程本身调用阻塞原语实现的。 其实现过程是：首先中断 CPU，停止进程运行， 将 CPU 的现行状态存放到 PCB 的 CPU 状态保护区中，然后将该进程置阻塞状态，并把它插入到等待队列中。 然后系统执行调度程序，将 CPU分配给另一个就绪的进程。 4. 唤醒进程原语 当某进程所需要的资源出现时，由释放资源的进程调用唤醒原语，唤醒等待该资源的进程。 唤醒原语的基本功能是：把除了 CPU之外的一切资源都得到满足的进程置成就绪状态。 执行时，首先找到被唤醒进程的 内部标识 ，让该进程脱离阻塞队列，将现行状态改变为就绪状态，然后插入就绪队列等待调度运行。 3 进程互斥与同步 并发执行的多个进程，是在异步环境下运行的 ，每个进程都以各自独立的、不可预知的速度向前推进。 但是，有时相互合作的进程需要在某些确定的点上协调它们的工作，以各自的执行结果为对方的执行条件，从而限制各进程的执行速度，产生直接制约关系。 如：计算 中国最大的管理资源中心 40 进程和打印进程，打印进程必须等待计算进程得出计算结果后，才能进行打印输出；而计算进程必须等待打印进程将上一次计算的结果打印输出后，才能进行下一次计算，否则就会造成混乱。 另外，还有一些进程由于共享某一公有资源，而这类资源对于不同的进程必须交叉使用，如打印机，当一个进程正在使用时，另一个进程必须等待，这就产生间接制约关 系。 我们把在异步环境下并发执行的进程，因直接制约而需要相互等待、相互合作，以达到各进程按相互协调的速度执行的过程称为进程间的同步。 把因间接制约而导致交替执行的过程称为进程间的互斥。 临界资源与临界区 系统中同时存在有许多进程，它们共享各种资源，然而有许多资源在某一时刻只能允许一个进程使用。 例如打印机、磁带机等硬件设备和变量、队列等数据结构，如果有多个进程同时去使用这类资源就会造成混乱。 因此必须保护这些资源，避免两个或多个进程同时访问这类资源。 我们把某段时间内只能允许一个进程使用的资源称为临界资源。 几个进程若共享同一临界资源，它们必须以互相排斥的方式使用这个临界资源，即当一个进程正在使用某个临界资源且尚未使用完毕时，其它进程必须延迟对该资源的操作，当使用该资源的进程释放该资源时，其它进程才可使用该资源，任何进程不能从中插进去使用这个临界资源，否则将会造成信息混乱和操作出错。 我们把访问临界资源的代码段称为临界区。 以 A、 B 两个进程共享一个公用变量 V 为例：如果 A 进程的 CS1 段程序向变量 V写入数据值，而 B进程的 CS2段程序从 V中取数据值，那么当 A进程正在给 V变量赋值操作时，B 进程就不能去使用 V变量。 系统只能 让它们按次序交替使用，而不能同时使用，即只有进程 A执行完 CS1 程序段释放了 V之后，才允许 B 进程执行 CS2 程序段来使用 V，我们把公用变量 V 称为临界资源，把 CS1 和 CS2 这种必须互斥执行的程序段称为相对于临界资源 V的临界区。 由于对临界资源的使用必须互斥进行，所以进程在进入临界区时，首先判断是否有其它进程在使用该临界资源，如果有，则该进程必须等待，如果没有，该进程才能进入临界区，执行临界区代码，同时，关闭临界区，以防其它进程进入。 当进程用完临界资源时，要开放临界区，以便其它进程进入。 因此，使用临界资源的代码结构 为： 进入区 临界区 退出区 有了临界资源和临界区的概念，进程间的互斥可以描述为禁止两个或两个以上的进程同时进入访问同一临界资源的临界区。 互斥工具 进程互斥可以用若干种方式实现，下面介绍两种方式：硬件方式和软件方式。 1. 硬件方式 ① 中断禁用 为保证多个并发进程互斥使用临界资源，只需保证一个进程在执行临界区代码时不被中 中国最大的管理资源中心 41 断即可，这个能力可以通过系统内核为启用和禁用中断定义的原语提供。 进程可以通过下面的方法实现互斥。 while(1) { 禁止中断 临界区 启用中断 其余部分 } 由于临界区不能被中断，故可保证互斥。 但该方法代价太高，因为 CPU被限制于只能交替执行程序，执行效率明显降低。 ② 专用的机器指令 CPU 的设计者提供了一些硬件指令，用于保证几个动作的原子性。 这几个动作在一个指令周期中执行，不会受到其它指令的干扰。 如 testset指令和 exchange指令。 testset指令定义如下： boolean testset(int i) { if(i==0) { i=1。 return true。 } else return false。 } 该指令测试它的参数 i的值。 如果 i为 0，则用 1取代并返回 true，这可以表示临界资源未被使用时，进程占用临界资源；如果 i为 1， i值不变，返回 false，这可以表示临界资源已被使用时，进程不能再占用临界资源。 由于整个 testset函数自动整体执行，就是说它不服从于任何中断，故可实现进程互斥。 用 testset指令实现互斥举例： const int n = / * 进程数 * / int bolt。 void P(int i) { while ( 1 ) { while (!testset (bolt)) /*什么也不做 */。 临界区 中国最大的管理资源中心 42 bolt =0。 /* 其余部分 */ } } void main( ) { bolt = 0。 parbegin (P⑴ , P⑵ „ , P(n))。 } 每个进程都在循环检测 bolt变量，当 bolt为 0时，进程进入临界区；否则进程一直循环检测。 exchange指令定义如下： void exchange(int register, int memory) { int temp。 temp=memory。 memory=register。 register=temp。 } 该指令交换一个寄存器和一个存储器单元的内容。 在执行该指令的过程中，任何其它指令对该存储器单元的访问均被阻止。 用 exchange指令实现互斥举例： const int n = / * 进程数 * / int bolt。 void P(int i) { int keyi。 while ( 1 ) { keyi = 1。 while (keyi != 0) exchange (keyi, bolt)。 临界区 exchange (keyi, bolt)。 /* 其余部分 */ } } void main( ) { 中国最大的管理资源中心 43 bolt = 0。 parbegin(P⑴ , P⑵ .... ,P(n))。 } 共享变量 bolt 被初始化为 0，每个进程都使用一个局部变量 keyi 且初始化为 1，惟一可以进入临界区的进程是发现 bolt 等于 0的那个进程，它把 bolt 置为 1，排斥所有其它进程进入临界区。 进程离开临界区时，它把 bolt重置为 0，允许另一个进程进入临界区。 机器指令方法的特点： ① 优点：  适用于在单 CPU或共享主存的多 CPU上的任何数目的进程。  非常简单且易于证明。  可用于支持多个临界区。 ② 缺点：  使用了忙等待。 因此，当一个进程正在等待进入一个临界区时，它会继续消耗 CPU时间。  可能发生饿死现象。 当一个进程离开一个临界区并且有多个进程正在等待时，选择哪一个等待进程是随意的，因此，某些进程可能无限地被拒绝进入。  可能发生死锁现象。 考虑单 CPU 中的下列情况：进程 Pl 执行专门指令并进入临界区，然后 P1 被中断并把 CPU 给具有更高优先级的 P2。 如果 P2试图使用与 P1 相同的资源，由于互斥机制，它将被拒绝访问。 因此，它会进入忙等待循环。 但是，由于 P1比 P2的优先级低，它将永远不会被调度执行。 软件方式 Dekker算法 : boolean flag [2]。 int turn。 void P0( ) { while (true) { flag [0] = true。 while (flag[1]) if(turn==l) { flag[0] = false。 while ( turn == 1) /* 什么也不做 */ flag [0] = true。 } 临。