住房与建设部网站 2018 128号,沈阳网 沈阳网站,可以看网站的浏览器,王福滨哈尔滨建设目录
2.4.1 进程同步的基本概念
1. 两种形式的制约关系
2. 临界资源#xff08;critical resource#xff09;
3. 生产者-消费者问题
4. 临界区#xff08;critical section#xff09;
5. 同步机制应遵循的规则
2.4.2 硬件同步机制
1. 关中断
2. Test-and-Set …目录
2.4.1 进程同步的基本概念
1. 两种形式的制约关系
2. 临界资源critical resource
3. 生产者-消费者问题
4. 临界区critical section
5. 同步机制应遵循的规则
2.4.2 硬件同步机制
1. 关中断
2. Test-and-Set 指令
3. Swap 指令
4. 小结 进程的异步性必然导致若干进程对系统资源进行无序争夺从而导致系统混乱。为保证多个进程能有条不紊地运行在多道程序系统中必须引入进程同步机制。
进程同步进制的主要任务是使并发执行的诸进程之间能有效地共享资源和相互合作从而使程序的执行具有可再现性。 2.4.1 进程同步的基本概念
1. 两种形式的制约关系
1间接相互制约关系。由于共享系统资源。
2直接相互制约关系。由于进程之间的相互合作。 2. 临界资源critical resource
一次仅允许一个进程访问的资源为临界资源 。 3. 生产者-消费者问题
1问题描述
有一群生产者进程在生产产品并将这些产品提供给消费者进程去消费。为使生产者进程与消费者进程能并发执行在两者之间设置了一个具有 n 个缓冲区的缓冲池生产者进程将其所生产的产品放入一个缓冲区中消费者进程可从一个缓冲区中取走产品去消费。 2解决方法
变量定义如下
int in 0; //数组单元输入指针
int out 0; //数组单元输出指针
int count 0; //记录缓冲池产品数
item buffer[n]; //具有n个缓冲区的缓冲池
缓冲池是被组织成循环缓冲的。 在生产者进程中使用一个局部变量 nextp用于暂时存放每次刚刚生产出来的产品而在消费者进程中则使用一个局部变量 nextc用于存放每次要消费的产品。
生产者 void producer() {while(1) {//produce an item in nextpwhile(count n); //缓冲池已满do no-opbuffer[in] nextp; //放入产品in (in 1) % n; //指向下一个数组单元count count 1; //缓冲池产品数加一}
}
消费者 void consumer() {while(1) {while(count 0); //缓冲池已空do no-opnextc buffer[out]; //取出产品out (out 1) % n; //指向下一个数组单元count count - 1; //缓冲池产品数减一//consume the item in nextc}
} 3存在问题
虽然上面的生产者程序和消费者程序在分别看时都是正确的而且两者在顺序执行时其结果也会是正确的但若并发执行时就会出现差错问题就在于这两个进程共享变量 count 。
假设 count 初值为 5 。生产者对它做加 1 操作消费者对它做减 1 操作这两个操作在用机器语言实现时分别可用以下形式描述。
reg1 count; |reg2 count;
reg1 reg1 1; |reg2 reg2 - 1;
count reg1; |count reg2;祖传计组图。 实际执行时由于时间片完可能导致两段程序中各语句穿插执行。
reg1 count; (reg15)
reg1 reg1 1; (reg16)
reg2 count; (reg25)
reg2 reg2 - 1; (reg24)
count reg1; (count6)
count reg2; (count4)
倘若再将两段程序中各语句交叉执行的顺序改变将可看到其它答案。这表明程序的执行已经失去了再现性。为了预防产生这种错误解决此问题的关键是把变量 count 作为临界资源处理亦即令生产者进程和消费者进程互斥地访问变量 count 。 4. 临界区critical section
把在每个进程中访问临界资源的那段代码称为临界区。
把一个访问临界资源的循环进程描述如下
while(true) {进入区检查有无进程进入。临界区进程访问临界资源。退出区将访问标志复位。剩余区其它部分的代码。
} 5. 同步机制应遵循的规则
1空闲让进
当无进程处于临界区时应允许一个请求进入临界区的进程立即进入自己的临界区。
2忙则等待
当已有进程进入临界区时其它试图进入临界区的进程必须等待。
3有限等待
对要求访问临界资源的进程应保证在有限时间内能进入自己的临界区以免陷入 “死等” 状态。
4让权等待
当进程不能进入自己的临界区时应立即释放处理机以免进程陷入 “忙等” 状态。 2.4.2 硬件同步机制
利用计算机硬件指令来解决临界区问题。对临界区管理时将标志看作一把 “锁” 。
初始时锁是打开的。进入临界区前进程必须先进行 “锁测试” 。“锁开” 则进入“锁关” 则等待。“锁开” 进入时应立即将其锁上以防止其它进程进入。“锁测试” 和关锁操作必须是连续的原子操作。
计算机硬件提供了三大指令关中断、Test-and-Set 指令、Swap 指令。 1. 关中断
原理在进入锁测试之前关闭中断直到完成锁测试并上锁之后才能打开中断。这样进程在临界区执行期间计算机系统不响应中断从而不会引发调度。
缺点
滥用关中断权利可能导致严重后果与系统安全相关的中断无法被响应关中断时间过长会影响系统效率不适用于多 CPU 系统这个关了还有那个2. Test-and-Set 指令
TS 指令的一般性描述如下
boolean TS(boolean * lock) {boolean old;old * lock;* lock true;return old;
}
利用 TS 指令实现互斥的循环进程结构可描述如下
do {//...while TS(lock); //entry section//... //critical sectionlock false; //exit section//... //remainder section
} while(true);
do ... while ... 记得最后的分号。
在进入区若恒有 lock true则代表临界区已上锁其它试图进入临界区的进程必须等待。 3. Swap 指令
Swap 指令在 8086/8088 中又称为 XCHG 指令用于交换两个字的内容。
Swap 指令的一般性描述如下
void swap(boolean * a, boolean * b) {boolean temp;temp * a;* a * b;* b temp;
}
为每个临界资源设置一个全局的 boolean 变量 lock其初值为 false代表没有上锁。再设置一个局部的 boolean 变量 key 。利用 Swap 指令实现互斥的循环进程结构可描述如下
do {key true;do { //entry sectionswap(lock, key);} while(key ! false);//... //critical sectionlock false; //exit section//... //remainder section
} while(true);
由于 lock 的初值为 false因此第一个进入临界区的进程内循环一次即退出循环。此时lock 值为 true其它试图进入临界区的进程将一直在内循环中循环。直到第一个进入临界区的进程执行到退出区lock 值被设置为 false 。 4. 小结
利用上述硬件指令能有效地实现进程互斥但当临界资源忙碌时其它访问进程必须不断地进行测试处于一种 “忙等” 状态不符合 “让权等待” 原则造成处理机时间的浪费同时也很难将它们用于解决复杂的进程同步问题。
