《操作系统 进程同步知识分享》由会员分享，可在线阅读，更多相关《操作系统 进程同步知识分享（108页珍藏版）》请在金锄头文库上搜索。
1、操作系统,第三讲 进程同步,一、进程之间的关系,2,第一节进程同步的基本概念,相互合作关系（直接相互制约） （ICP） 资源共享关系 （间接相互制约） （I1 I2 I3）,第3章进程的同步与通信,I：输入进程C：计算进程P：输出进程,二、临界资源,第一节进程同步的基本概念,1、举例: 银行存款问题(count是共用变量，即共享资源，临界资源),第3章进程的同步与通信,P1：count += 300; P2：count -= 200; count = 初值+100,P1：LD R1, count; P2：LD R2, count; P2: SUB R2, 200; P2: LD count,
2、R2; P1: ADD R1, 300; P1: LD count, R1; count = 初值 + 300,LD R, count ADD R, 300 LD count, R,P1：LD R1, count; P2：LD R2, count; P1: ADD R1, 300; P1: LD count, R1; P2: SUB R2, 200; P2: LD count, R2; count = 初值 - 200,二、临界资源,5,第一节进程同步的基本概念,3、临界资源使用方法 对临界资源的使用采用互斥方式 互斥：一个进程使用完之后，另一个进程才能使用,第3章进程的同步与通信,三、临界区
3、,6,第一节进程同步的基本概念,1、临界区 进程中访问临界资源的代码段 2、同类临界区 涉及同一临界资源的不同进程中的临界区,第3章进程的同步与通信,三、临界区,7,第一节进程同步的基本概念,3、进入区 临界区前检查临界资源使用情况的代码段 4、退出区 临界区后面恢复临界资源访问标志的代码段,第3章进程的同步与通信,三、临界区,8,第一节进程同步的基本概念,5、临界资源使用的同步准则 空闲让进：（提高效率） 忙则等待：（解决互斥） 有限等待：等待进入临界区的要求应在一有限时间满足（以免死等） 让权等待：放弃占用CPU（以免忙等）,第3章进程的同步与通信,三、临界区,第一节进程同步的基本概念,6
4、、临界资源的状态判断与设置 例1：flag=true代表有进程正在使用R flag初值为false,第3章进程的同步与通信,Pi: repeat while flag do no_op flag := true; 临界区代码 flag := false; : Until false;,出现“同时进入”问题 不符合“忙则等待”准则,Pj: repeat while flag do no_op flag := true; 临界区代码 flag := false; : Until false;,三、临界区,10,第一节进程同步的基本概念,6、临界资源的状态判断与设置 对临界资源状态（是否正在使用）必
5、须判断与设置同时进行 即判断与状态设置（状态改变）为原子操作，否则，会出现问题,第3章进程的同步与通信,一、信号量,11,第二节信号量机制,1、信号量（Semaphore） 信号量是一种特殊的变量（S） 除初始化外，对信号量变量（S）的操作只能由两个标准的原子操作（不可中断）实现 wait(S):等待操作（也叫P操作） signal(S):发信号操作（也叫V操作）,第3章进程的同步与通信,二、信号量机制,12,第二节信号量机制,信号量变量是由一个整型数和一个阻塞等待进程链表构成的记录型数据结构 type semaphore = record value: integer; L: list of
6、 process; end;,第3章进程的同步与通信,所有对同一个信号量进行操作且进入等待状态的进程，都自动进入阻塞等待（让权等待）状态，并将其挂在该信号量阻塞等待队列L中,二、信号量机制,第二节信号量机制,1、P原子操作（wait）,第3章进程的同步与通信,procedure wait(s); var s: semaphore; begin s.value := s.value 1; if s.value 0 then block(s.L); end;,二、信号量机制,第二节信号量机制,2、V原子操作（signal）,第3章进程的同步与通信,procedure signal(s); var
7、s: semaphore; begin s.value := s.value + 1; if s.value = 0 then wakeup(s.L); end;,二、信号量机制,第二节信号量机制,3、利用信号量实现进程互斥同步 银行存款问题 count是共用变量(即共享资源)，采用mutex互斥信号量实现互斥访问,第3章进程的同步与通信,15,var mutex: semaphore := 1; /定义变量,procedure P1; /增加存款进程 begin wait(mutex); count += 300; signal(mutex); end;,procedure P2; /减少存
8、款进程 begin wait(mutex); count -= 200; signal(mutex); end;,二、信号量机制,16,第二节信号量机制,4、利用信号量实现较复杂的进程同步 S1 S7分别为进程P1P7的执行部分，它们的执行顺序如右图所示,第3章进程的同步与通信,var a, b, c, d, e, f, g, h: semaphore := 0, 0, 0, 0, 0, 0, 0, 0; P1: begin S1; signal(a); signal(b); end; P2: begin wait(a); S2; signal(c); end; P3: begin wait(
9、b); S3; signal(d); end; P4: begin wait(c); S4; signal(e); signal(f); end; P5: begin wait(e); S5; signal(g); end; P6: begin wait(f); wait(d); S6; signal(h); P7: begin wait(g); wait(h); S7; end;,二、信号量机制,17,第二节信号量机制,5、信号量机制的特性 wait(s)操作和signal(s)操作必须成对出现(可以不在同一进程中) 缺少wait(s)不能保证资源互斥使用 缺少signal(s)将可能使资源
10、永远得不到释放 不存在“忙等”问题,第3章进程的同步与通信,一、生产者消费者问题,第三节经典进程同步问题,1、生产者消费者问题描述 有一群生产者进程在生产消息，并将此消息提供给消费者进程去消费 生产者进程（多个），产品存放缓冲区（n个），消费者进程（多个）,第3章进程的同步与通信,缓冲区是临界资源,一、生产者消费者问题,第三节经典进程同步问题,2、生产者消费者问题举例 数据输入进程（生产者）与计算进程（消费者） 数据计算进程（生产者）与数据输出（如打印）进程（消费者）,第3章进程的同步与通信,一、生产者消费者问题,第三节经典进程同步问题,3、生产者消费者关系 公用信号量mutex：初值为1，实
11、现临界资源（缓冲区）互斥使用。(如果缓冲区只有一个缓冲块，可以只用这一个信号量) 生产者私用信号量empty：初值为n，指示空缓冲块数目 消费者私用信号量full：初值为0，指示满缓冲块数目 整型量in, out：初值均为0，in指示首空缓冲块序号，out指示首满缓冲块序号,第3章进程的同步与通信,20,一、生产者消费者问题,第三节经典进程同步问题,4、采用信号量的生产者-消费者进程描述,第3章进程的同步与通信,21,var mutex, empty, full: semaphore := 1, n, 0 buffer: array0, , n-1 of item; 定义变量 in, out:
12、 integer: =0, 0;,procedure producer; 生产者进程 begin repeat 生产一个产品nextp; wait(empty); wait(mutex); buffer(in) : = nextp; in := (in + 1) mod n; signal(mutex); signal(full); until false; end;,procedure consumer; 消费者进程 begin repeat wait(full); wait(mutex); nextc := buffer(out); out := (out + 1) mod n; sign
13、al(mutex); signal(empty); 消费一个产品nextc; until false; end;,一、生产者消费者问题,第三节经典进程同步问题,5、采用信号量应注意的问题 公用（互斥）信号量（mutex）和私用信号量（empty, full）都必须成对出现 在进入临界区之前，先对私用信号量（empty, full）进行wait操作，再对公用信号量进行wait操作（不能颠倒，否则易于造成“死锁”）,第3章进程的同步与通信,22,二、阅览室管理问题,第三节经典进程同步问题,1、阅览室管理问题描述 阅览室有一批座位，可以坐下若干同学自习；有一张唯一的登记表，记录空座位数目 某一同学入
14、室时，查看登记表；如果空座位数目0，则座位数减一，并进入阅览室坐下自习；否则，在阅览室门口等待 当从阅览室中出来时,使登记表中空座位数加1,第3章进程的同步与通信,二、阅览室管理问题,第三节经典进程同步问题,2、阅览室管理问题举例 阅览室中有50个座位（即最多可坐下50位同学自习），只有一张登记表，欲进入阅览室的同学须先在登记表上登记，然后进入阅览室自习；出门时注销登记。,第3章进程的同步与通信,登记表是临界资源,二、阅览室管理问题,第三节经典进程同步问题,3、进入与出门关系 互斥公用信号量mutex：初值为1，实现临界资源（登记表）互斥使用。 空座位信号量seat：初值为50，指示空座位数目
15、,第3章进程的同步与通信,25,二、阅览室管理问题,第三节经典进程同步问题,4、采用信号量的阅览室管理进程描述,第3章进程的同步与通信,26,var mutex, seat: semaphore := 1, 50 /定义变量,procedure roomin; /进门进程 begin wait(seat); wait(mutex); 登记，同学进入阅览室; signal(mutex); : end;,procedure roomout; /出门进程 begin wait(mutex); 撤消登记，同学走出阅览室.; signal(mutex); signal(seat); : end;,三、读
16、者写者问题,第三节经典进程同步问题,1、读者写者问题描述 指多个只读进程（reader）可以同时访问共享对象，而改写进程（writer）必须与其它进程（包括reader, writer）互斥地访问共享对象的同步问题,第3章进程的同步与通信,27,三、读者写者问题,第三节经典进程同步问题,2、读者写者问题举例 数据库数据的读（读者）操作、写（写者）操作 民航订票：查询订票信息（读者）操作，售票人员售出机票（写者）操作,第3章进程的同步与通信,28,三、读者写者问题,第三节经典进程同步问题,3、读者写者关系 互斥信号量wmutex：初值为1，实现临界资源（文件）互斥使用。 读者数目：readcount，初值为0，表示正在读的进程数目 如果readcount=0，读者进程必须执行wait(wmutex)操作
