多个相关进程在执行次序上的协调。
制约关系:直接制约。
如图所示:一个进程在执行操作的时候,另一个进程必须等待,体现在次序上的等待和协调,并不争夺临界资源。
多个进程因为争夺临界资源二相互排斥执行的过程称为进程的互斥。
制约关系:间接制约。
思路:
设置一个共享变量 W (锁) , 初值为 0。当一个进程想进入其临界区 (进程中涉及临界资源的程序段) 时, 它首
先测试这把锁: 如果锁的值为 0, 则进程将其置为 1 并进入临界区。若锁已经为 1, 则进程等待直到其变成 0。
实现:
加锁原语:LOCK(W) :L: if W=1 then goto L else W=1;
解锁原语:UNLOCK(W):W=0;
信号量:
☻说明:
表示资源的实体——是一个与队列有关的整型变量。
☻类型:
公用信号量:用于进程间的互斥,初始值通常为 1.
私有信号量:用于进程间的同步,初始值通常为 0 或 N .
☻P 操作 (Wait 操作):
proberen——检查。意味着请求分配一个单位资源。
- S = S - 1
- if (S < 0) {
- //调用进程被阻塞,进入S的等待队列
- }
☻V 操作 (Signal 操作):
荷兰语 "verhogen"——"增量" 之意, 意味着释放 / 增加一个单位资源。
- S = S + 1;
- if (S <= 0) {
- //从S的等待队列中唤醒一个进程使其进入就绪状态
- }
☻使用 PV 实现互斥
☻使用 PV 实现进程同步
描述: 生产者和消费者共享 n 个缓冲区, 生产者生产产品放入缓冲区, 消费者从缓冲区中取产品消费。请写出能够正确反映它们逻辑关系的代码
行为分析:
生产者:生产产品,放置产品 (有空缓冲区)。
消费者:取出产品 (有产品),消费产品。
行为关系:
生产者之间: 互斥 (放置产品)
消费者之间: 互斥 (取出产品)
生产者与消费者之间:互斥 (放 / 取产品) 同步 (放置——取出)
信号量设置:
semaphore mutex =1;// 互斥
semaphore empty=n;// 空闲数量
semaphore full=0;// 产品数量
伪代码:
- semaphore mutex = 1 //互斥
- semaphore empty = n //缓冲区空闲数
- semaphore full = 0 //产品数量
- 生产者:
- while (1) {
- product; //生产
- p(empty);
- p(mutex);
- add to buffer; //放置产品
- v(mutex);
- v(full)
- }消费者:
- while (1) {
- p(full);
- p(mutex);
- get from buffer; //取出产品
- v(mutex);
- v(empty) conseume; //消耗
- }
描述:一个数据对象 (文件、记录) 可以为多个并发进程共享。其中有的进程只需要读其中的内容, 我们称为 "读者"; 有的进程负责更新 (读写) 其中内容, 我们称为 "写者"。
规定:""可以同时读取共享数据对象;"" 不能和其它任何进程同时访问共享数据对象。
行为分析:
Ø 读进程的行为:
Ø 写进程的行为:排他性的使用资源。
Ø 确定同步与互斥关系:
读者 - 读者: 互斥访问 readnum
读者 - 写者: 互斥访问 Data
写者 - 写者: 互斥访问 Data
Ø 确定临界资源:
Data,readnum
信号量设置:
int readnum=0;
semaphore mutex=1;// 公用信号量,用于 readnum 的互斥。
semaphore write=1;// 公用信号量,用于 Data 访问的互斥。
伪代码:
- int readnum = 0; //计数,用于记录读者的数目
- semaphore mutex = 1; //公用信号量,用于readnum互斥
- semaphore write = 1; //公用信号量,用于Data访问的互斥,
- 读者:p(mutex) //对readnum互斥
- readnum++;
- if (readnum == 1) P(write) //申请使用data资源
- V(mutext) //释放readnum
- reading;
- p(mutex) //对readnum互斥
- readnum--;
- if (readnum == 0) V(write) //释放data资源
- V(mutext) //释放readnum
- 写者:
- //P(mutex)
- P(write) //write本身已经互斥
- writing;
- v(wirte)
- //V(mutex)
描述:理发店有一位理发师和一把理发椅。如果没有顾客, 则理发师在理发椅上睡觉; 当有顾客到达时, 如理发师在睡觉则唤醒他理发, 如果理发师正忙着理发, 则坐在椅上等待。编写程序实现理发师和顾客行为的正确描述。
行为分析:
Ø 理发师行为: 睡觉、理发。没有顾客睡觉,有顾客理发。
Ø 顾客行为: 理发或等待。
Ø 相互作用:
理发师与顾客之间: 同步
顾客与顾客之间:无
信号量设置:
semaphore customers=0; //customers 表示等候理发的顾客数量
semaphore barbers=0; //barbars 表示等候顾客的理发师数量
伪代码:
- semaphore customers = 0; //customers表示等候理发的顾客数量
- semaphore barbers = 0; //barbars表示等候顾客的理发师数量
- 理发师代码:
- while (1) {
- p(customers) //检查是否有顾客
- v(barbers) //告诉顾客有发型师
- Cut_hair();
- }顾客代码:V(customers) p(barbers);
- Get_hair();
这里主要体现了进程的同步。如有疑问,请看信号量介绍的同步实现。
增加条件:理发店有 n 把椅子, 顾客到达时如果理发师空闲则理发, 如果理发师忙, 则看椅子上是否还有空位置, 有空位置等待, 没有空位置就离开。
伪代码:
- semaphore customers = 0; //customers表示等候理发的顾客数量
- semaphore barbers = 0; //barbars表示等候顾客的理发师数量
- int waiting = 0; //等待人数
- semaphore mutex = 1; //用于waiting的互斥
- 理发师进程:
- while (1) {
- p(customers) //检查是否有顾客
- P(mutex);
- waiting = waiting - 1;
- v(mutex);
- v(barbers) Cut_hair();
- }顾客进程:P(mutex) //占空椅子的操作是互斥的,即一个一个占
- if (waiting //如果座位未满
- {
- waiting = waiting + 1;
- V(mutex);
- V(customers);
- P(barbers); //检测是否有理发师
- Get_haircut();
- } else {
- V(mutex); //表示座位已经满了
- }
1.P、V 操作 (对同一信号量) 总是成对出现的; 互斥操作时他们处于同一进程中; 同步操作时他们处于不同进程中。
2. 信号量初始值的设置和 P、V 操作的位置及次序是关键, 要十分小心的设置, 一定要保持正确的逻辑关系和较高的执行效率。
来源: http://www.cnblogs.com/MrSaver/p/6147437.html