操作系统进程互斥与同步-互斥

1、间接的相互制约关系间接的相互制约关系 资源共享（竞争资资源共享（竞争资源系统）源系统）直接的相互制约关系直接的相互制约关系 公共变量（进程协公共变量（进程协作）作）34例例1 1：x x代表某航班机座号，代表某航班机座号，p p1 1和和p p2 2两个售票进两个售票进程，售票工作是对变量程，售票工作是对变量x x加加1 1。这两个进程在一。这两个进程在一个处理机个处理机C C上并发执行，分别具有内部寄存器上并发执行，分别具有内部寄存器r r1 1和和r r2 2。 35例例2：两个进程共享一个变量：两个进程共享一个变量x 两个进程共享一个变量两个进程共享一个变量x时，两种可能的执行次序：时，

2、两种可能的执行次序：A： p1： r1 := x；r1:= r1+1； x := r1 ； p2： r2:= x；r2 := r2+1； x := r2 ；设设x的初值为的初值为10，两种情况下的执行结果：，两种情况下的执行结果： 情况情况A： x = 10+2 情况情况B： x = 10+1 B： p1： r1 := x； r1:= r1+1； x := r1 ； p2： r2:= x；r2 := r2+1； x := r2 ；36 一次仅允许一个进程使用的资源称为一次仅允许一个进程使用的资源称为临界资源临界资源。 硬件：如输入机、打印机、磁带机等硬件：如输入机、打印机、磁带机等 软件：如公

3、用变量、数据、表格、队列等软件：如公用变量、数据、表格、队列等l每个进程中访问临界资源的那段程序称为每个进程中访问临界资源的那段程序称为临界区临界区。 x := x+1; csa 进程进程A进程进程B x := x+1; csb 37在操作系统中，当某一进程正在访问某一存储区域时，在操作系统中，当某一进程正在访问某一存储区域时，就不允许其他进程来读出或者修改存储区的内容，否则，就不允许其他进程来读出或者修改存储区的内容，否则，就会发生后果无法估计的错误。进程间的这种相互制约就会发生后果无法估计的错误。进程间的这种相互制约关系称为互斥。关系称为互斥。 x := x+1; csa 进程进程A进程进

4、程B x := x+1; csb 由共享公有资源而造成的对并发进程执行由共享公有资源而造成的对并发进程执行速度的速度的间接制约间接制约。受间接制约的类中各程序段在执行顺序上受间接制约的类中各程序段在执行顺序上是是任意任意的。的。间接制约的几个进程是互斥关系间接制约的几个进程是互斥关系38 并发进程在一些关键点上可能需要互相等待与互通消息，并发进程在一些关键点上可能需要互相等待与互通消息， 这种相互制约的等待与互通消息称为进程同步。这种相互制约的等待与互通消息称为进程同步。 病员就诊病员就诊 看病活动：看病活动： 要病人去要病人去化验；化验； 等等化验结果；化验结果； 继续诊病；继续诊病；化验活

5、动：化验活动： 需要进行化验需要进行化验 ? 进行进行化验；化验； 开出化验结果；开出化验结果； 39共享缓冲区的计算进程与打印进程的同步共享缓冲区的计算进程与打印进程的同步 计算进程计算进程 cp和打印进程和打印进程 iop公用一个单缓冲公用一个单缓冲 缓冲区缓冲区bufiop cp1040用变量用变量w w代表某种资源的状态，代表某种资源的状态，w w称为称为“锁锁” ” 。 检测检测w的值的值 (是是0还是还是1)；如果如果w的值为的值为1，继续检测；，继续检测；如果如果w的值为的值为0，将锁位置，将锁位置1 (表示占用资源表示占用资源)，进入临，进入临界区执行。界区执行。 (此为上锁操

6、作此为上锁操作)临界资源使用完毕，将锁位置临界资源使用完毕，将锁位置0。 (此为开锁操作此为开锁操作) 42算法算法 lock 输入：锁变量输入：锁变量w 输出：无输出：无 test： if (w为为1) * 测试锁位的值测试锁位的值* goto test； else w=1； *上锁上锁* 不断的测不断的测试锁的状试锁的状态，耗费态，耗费CPUCPU时间时间开锁原语开锁原语算法算法 unlock 输入：锁变量输入：锁变量w 输出：无输出：无 w=0；*开锁开锁* 43信号灯是一个确定的二元组信号灯是一个确定的二元组(s，q)，s是一是一个具有非负初值的整型变量，个具有非负初值的整型变量，q是

7、一个初始是一个初始状态为空的队列。操作系统利用信号灯的状态为空的队列。操作系统利用信号灯的状态对并发进程和共享资源进行控制和管状态对并发进程和共享资源进行控制和管理。理。信号灯是整型变量。信号灯是整型变量。 变量值变量值 0 0 时，表示绿灯，进程执行；时，表示绿灯，进程执行； 变量值变量值 0 0 时，表示红灯，进程停止执时，表示红灯，进程停止执行。行。注意：创建信号灯时，应准确说明信号灯注意：创建信号灯时，应准确说明信号灯 s 的意义和初值的意义和初值 (这个这个初值初值 绝不能为负值绝不能为负值)。44P 操作的定义操作的定义 对信号灯对信号灯s的的 p操作记为操作记为 p(s)。p(s

8、)是一是一个不可分割的原语操作，即取信号灯值个不可分割的原语操作，即取信号灯值减减1，若相减结果为负，则调用，若相减结果为负，则调用p(s)的进的进程被阻，并插入到该信号灯的等待队列程被阻，并插入到该信号灯的等待队列中，否则可以继续执行。中，否则可以继续执行。P 操作的实现操作的实现 入入 口口 S-1 S S0 ?转进程调度转进程调度返回返回 入信号灯等待队列入信号灯等待队列 置置“等待状态等待状态”00 0 045V V 操作的定义操作的定义对信号灯对信号灯s s的的 v v操作记为操作记为 v(s)v(s)。v(s)v(s)是是一个不可分割的原语操作，即取信号灯一个不可分割的原语操作，即

9、取信号灯值加值加1 1，若相加结果大于零，进程继续执，若相加结果大于零，进程继续执行，否则，要帮助唤醒在信号灯等待队行，否则，要帮助唤醒在信号灯等待队列上的一个进程。列上的一个进程。V 操作的实现操作的实现 入入 口口 S+ +1 S 从信号灯的等待队列中取出首元素从信号灯的等待队列中取出首元素 入就绪队列入就绪队列 置置“就绪状态就绪状态” 返回返回 S0 ?0 046上锁原语上锁原语进入临界区进入临界区csa 进程进程 pa开锁原语开锁原语上锁原语上锁原语进入临界区进入临界区csb 进程进程 pb开锁原语开锁原语47 程序程序 task1 main( ) int w=1； * 互斥锁互斥锁

10、 * cobegin pa( )； pb( )； coend 47pa( ) lock(w)； csa ； unlock(w)； pb( ) lock(w)； csb ； unlock(w)； 48 设：设：mutex为互斥信号灯，初值为为互斥信号灯，初值为1。p(mutex)进入临界区进入临界区csa 进程进程 pa v(mutex)p(mutex)进入临界区进入临界区csb 进程进程 pb v(mutex)49程序程序 task2 main( ) int mutex=1； * 互斥信号灯互斥信号灯 * cobegin pa( )； pb( )； coend pa( ) pb( ) p(mu

11、tex)； p(mutex)； csa ； csb ； v(mutex)； v(mutex)； 两个并发进程，一个共享资源，互斥信号灯的值两个并发进程，一个共享资源，互斥信号灯的值仅取仅取1 1、0 0和和1 1三个值。三个值。mutex=1 mutex=1 表示没有进程进入临界区；表示没有进程进入临界区；mutex=0 mutex=0 表示有一个进程进入临界区；表示有一个进程进入临界区；mutex=mutex=1 1 表示一个进程进入临界区，表示一个进程进入临界区， 另一另一个进程等待进入。个进程等待进入。50互斥举例互斥举例1x代表某航班机座号，代表某航班机座号，pa和和pb两个售票两个售票进程，售票工作是对变量进程，售票工作是对变量x加加1