文档介绍：会计学
1
专业综合操作系统练****题
2
（三）同步与互斥
第1页/共49页
3
1. 进程同步的基本概念
多道程序系统中，进程之间有两种形式的制约关系：
（1）间接相互制约：源于资源共享
（2）直接相互制约：源于进程合作
进程同步：主要源于进程合作
是进程之间的直接制约关系
进程互斥：主要源于进程共享
是进程之间的间接制约关系
第2页/共49页
4
临界资源：一次只允许一个进程使用的资源。
如：打印机，公共变量
临界区：在每个进程中，访问临界资源的那段程序。
同步机制遵循的准则：
空闲让进，忙则等待，有限等待，让权等待
当临界区空闲时，进程可以立即进入，以便有效利用临界资源
当已有进程进入临界区时，其它进程必须等待，以保证互斥
对要求进入的进程，应在有限的时间内使之进入，以避免“死等”
对于等待的进程，它必须立即释放处理机，以避免进程忙等
第3页/共49页
5
2. 实现临界区互斥的基本方法
进程互斥的硬件方法
（1）检测和设置（TS）指令
（2）swap指令（或exchange） 交换两个字（字节）的内容
用软件实现的同步互斥机制
在进入区设置和检查一些标志
（1）算法一：单标志法
（2）算法二：双标志法先检查
（3）算法三：双标志法后检查
（4）算法四：Peterson算法
第4页/共49页
6
【例1】（错误解法）
（turn是int型的变量，初始化为i或j）
算法一能够保证同一时刻只有一个进程在临界区中，但是却要求进程Pi和进程Pj轮流地访问临界区，若进程Pi不打算进入临界区，那么进程Pj在进入过一次临界区后就再也不能进入。所以不满足空闲让进和有限等待的两个准则。
第5页/共49页
7
【例2】（错误解法）
（flag[2]是bool型的数组，两个元素初始化为false）
算法二消除了算法一中需要两个进程轮流访问临界区的错误，但却存在两个进程都进不了临界区的可能性，仍然不能满足空闲让进和有限等待。
第6页/共49页
8
【例3】算法三（正确解法，又称为Dekker算法）
（turn是int型的变量，初始化为i或j；flag[2]是bool型的数组，两个元素初始化为false）
Dekker算法结合了算法一和算法二，实现了空闲让进和忙则等待。基本上Dekker算法是个正确的算法，能够正常工作。
第7页/共49页
9
【例4】算法四（正确解法，又称为Peterson算法）
（turn是int型的变量，初始化为i或j；flag[2]是bool型的数组，两个元素初始化为false）
Peterson算法与Dekker算法类似，实现了空闲让进、忙则等待和有限等待。相比而言，Dekker算法比较复杂，证明起来也比较困难，而Peterson算法较简洁。
第8页/共49页
10
【例11】 （2010年联考第27题）
进程P0和P1的共享变量定义及其初值为：
boolean falg[2];
int turn=0;
falg[0]=FALSE; falg[1]=FALSE;
若进程P0和P1访问临界资源的类C伪代码实现如下：
void P0() //进程P0
{while(TRUE){
flag[0]= TRUE; turn=1;
while(flag[1]&&turn==1);
临界区;
flag[0]=FALSE;
｝｝
void P1() //进程P1
{while(TRUE){
flag[1]= TRUE; turn=0;
while(flag[0]&&turn==0);
临界区;
flag[1]=FALSE;
｝｝
则并发执行进程P0和P1时产生的情形是
A. 不能保证进程互斥进入临界区、会出现“饥饿”现象
B. 不能保证进程互斥进入临界区、不会出现“饥饿”现象
C. 能保证进程互斥进入临界区、会出现“饥饿”现象
D. 能保证进程互斥进入临界区、不会出现“饥饿”现象
0
0
0
0
0
0
0
0
第9页/共49页