mutex互斥信号灯.ppt

（四）进程互斥 一、进程互斥的概念 1. 临界资源 例1：两个进程A、B共享一台打印机 若不加以控制，两个进程的输出结果可能交织在一起，很难区分。 例2：两个进程共享一个变量x 设： x代表某航班已卖出的机座数，初值为0。p1和p2为两个售票进程，功能是对共享变量x的值加1。 这两个进程在一个处理机C上并发执行，分别具有内部寄存器r1和r2。 两进程并发执行的两种可能次序: 序列A 序列B p1: r1 := x ; p1: r1 := x ; r1 := r1 + 1 ; p2: r2 := x; x := r1 ; r2 := r2 + 1 ; P2: r2 := x ; x := r2 ; r2 := r2 + 1 ; p1: r1 := r1 + 1 ; x := r2 ; x := r1 ; 特点：当两个进程公用一个变量时，它们必须顺序的访问，一个进程对公用变量操作完毕后，另一个进程才能去访问和修改这一变量。 （1）什么是临界资源 我们把一次（一段时间内）仅允许一个进程使用的资源称为临界资源。 许多物理设备，如输入机、打印机、磁带机等都具有这种性质。 软件资源，如公用变量、数据、表格、队列等也都具有这一特点。 （2）什么是临界区 每个进程中访问临界资源的那段程序段称为临界区（临界段）。 （3）什么是互斥 在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约的关系称为互斥。 例如：进程A正在执行CSa段时，进程B就不能进入CSb段执行。 进程A 进程B … … x = 0 CSb x = x + 1 CSa … … x = x + 1 … 操作系统如何保证进程的互斥呢？ （1）保证进入 当有若干个进程欲进入临界区时，应在有限的时间内使其进入； （2）排它性 每次至多有一个进程处于临界区； （3）有限性 进程在临界区内仅逗留有限的时间。 ?这些原则如何实现呢？ 二. 锁和上锁、开锁操作 1. 什么是锁 用变量w代表某种资源的状态，w称为“锁” 2. 进程使用临界资源的操作 3. 上锁原语和开锁原语 （1）上锁原语 算法 lock 输入：锁变量w 输出：无 { test ： if (w为1) goto test ;/* 测试锁位的值 */ else w = 1 ; /* 上锁 */ } 改进的算法 4. 用上锁原语和开锁原语实现进程互斥 三. 信号灯和P、V操作 什么是信号灯 信号灯是整型变量。 a ≥ 0时，表示绿灯，进程可继续执行。 a 0时，表示红灯，进程停止执行。 信号灯是一个确定的二元组（s，q），s是一个具有非负初值的整型变量，q是一个初始状态为空的队列。操作系统利用信号灯的值对并发进程和共享资源进行控制和管理。 注意：创建信号灯时，应准确说明信号灯s的意义和初值（这个初值绝不能为负值）。 2. P、V操作 信号灯的值只能由P、V操作来改变。 （1）P操作 P操作定义 对信号灯s的P操作记为P（s）。 P（s）是一个不可分割的原语操作，即取信号灯值减1，若相减结果为负，则调用P（s）的进程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。 （2） V操作 V操作定义 对信号灯s的V操作记为V（s）。 V（s）是一个不可分割的原语操作，即取信号灯值加1，若相加结果大于零，进程继续执行， 否则，要帮助唤醒在信号灯等待队列上的一个进程。 3. 用信号灯的P、V操作实现进程互斥 设：mutex为互斥信号灯，初值为1。 （1）框图描述 （2）程序描述 Main( ) { int mutex = 1; /*互斥信号灯*/ cobegin Pa（）； Pb（）； coend } 用两个进程共享打印机的例子 （3）信号灯可能的取值 假设有N个并发进程共用一台打印机，设互斥信号灯mutex的初值为1，则： mutex的取值范围为多少？信号灯的值分别代表什么含义？ （3）信号灯可能的取值 诸N个并发进程，互斥信号灯mutex的初值为1时，则： mutex的取值为：1～-(N-1). 其含义为： 1 ：表示有进程进入临界区。有一个资源，无进程等待； 0 ：表示有1个进程进入临界区。无资源，无进程等待； -i