《计算机操作系统 第四章》由会员分享，可在线阅读，更多相关《计算机操作系统 第四章（49页珍藏版）》请在金锄头文库上搜索。
1、操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM第4章 并发与互斥 基本概念 互斥：软件方法 硬件方法 信号量机制 管程 死 锁 主 要 内 容1操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM4.1 基本概念4.1.1 临界资源和临界区临界资源（Critical Resources）：一种一次只能为一个进程服务的资 源。临界区（Critical Section）：进程中访问临界资源的程序。每个使用 该资源的进程都要包含
2、一个临界区。操作系统在管理可控制资源分配与使用方面，应当 保证进程对临界资源的访问满足以下3点：l 互斥访问要求。l 不致于产生“死锁”。 l 不能有“饥饿”进程。2操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM4.1.2 互斥管理准则 空闲让进：当没有进程在临界区时，任何需要进 入临界区的进程都允许立即进入。 忙则等待：在共享同一对象的所有进程中，一次 只能有一个进程进入临界区。其它要求进入临界 区的进程只能等待。 有限等待：任何一个进程经有限时间等待后都能 进入临界区，不允许出现进程死锁或饥饿的情况
3、发生。 让权等待：当一个进程不能进入临界区时要立即 阻塞自己，释放处理机让其它进程使用，避免“ 忙等”。 3操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM4.2 互斥：软件方法 第一次尝试 算法中设计了一个变量turn保存允许进入临界区的进程编 号（初值为1，表示进程1可以首先进入）。当一个进程要求进 入临界区时，先检查turn的值。若turn保存的不是自己的进程编 号就进行循环等待；否则进入临界区。访问完成后退出临界区 ，再将turn设置为对方的进程编号。 第二次尝试算法中定义了一个标志数组flag。当
4、flagi=true，表 示进程i正在临界区。初始时Flag的各分量值皆为false，表 示尚无进程进入。当一个进程要求进入临界区时，先检查是否 有进程已进入。若有进程进入，就循环等待；否则，设置自己 的标志为真，立即进入。访问完成后再将自己的标志设为假。4.2.1 Dekker方法4操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM算法如下： Process P (1) Process P (2) Begin begin While (Flag2) do skip; While (Flag1) do ski
5、p; Flag1 = true; Flag2 = true; Critical section; Critical section; Flag1 = false; Flag2 = false; end. end.5操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM第三次尝试 在第二次尝试的基础上，将其中的两个语句顺序交换， 形成了新的算法如下： Process P (1) Process P (2)Begin begin Flag1 = true; Flag2 = true;While (Flag2) do
6、skip;While (Flag1) do skip;Critical section; Critical section;Flag1 = false; Flag2 = false; end. end.6操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM 第四次尝试 这是一个“礼让为先”的算法，每个进程设置好自 己的flag标志，表明希望进入临界区。但也准备重置flag， 以表示谦让。算法如下： Process P (1) Process P (2) Begin begin Flag1 = true; Fla
7、g2 = true; While (Flag2) do While (Flag1) do flag1=false; flag2=false; flag1=true; flag2=true; Critical section; Critical section; Flag1 = false; Flag2 = false; end. end.7操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM正确的算法 为了避免过度互斥礼让的问题，Dekker使用第一种尝试中的轮盘 变量turn，表示哪个进程有权进入临界区。让它
8、在两个进程的活动中规 定一个强制性的顺序。算法如下： Process P (1) Process P (2) Begin begin Flag1 = true; Flag2 = true; While (Flag2) do While (Flag1) do if (turn=2) if (turn=1) flag1=false;flag2=false; while (turn=2) do skip; while (turn=1) do skip;flag1=true; flag2=true; Critical section; Critical section; turn=2; turn=1;
9、 Flag1 = false; Flag2 = false; end. end.8操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM4.2.2 Peterson算法变量turn用来保存进程的编号，当turn=i，表示进程i有权进入临界 区。数组flag表示哪个进程进入了临界区，Flagi=true，表示进程i已进 入。初始时，标志数组flag的各元素值皆为false，表示无进程进入临界 区。变量turn可以不设初始值。下面是该算法的主要部分： Process P (1) Process P (2) Begin
10、 begin Flag1 = true; Flag2 = true; turn=2; turn=1; While (Flag2turn=2) While (Flag1 turn=1) do skip; do skip; Critical section; Critical section; Flag1 = false; Flag2 = false; end. end 9操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM4.3 硬件方法4.3.1 交换指令将两个指定位置上的数据进行交换，是该指令实现的操 作。微
11、型机PC上对应的指令格式是XCHG op1，op2，用于交 换两个操作对象的值（其中，opi是操作对象）。交换指令的功能可描述为下面的过程：Procedure XCHG(op1,op2) Begin Boolean temp; temp = op1; op1 = op2; op2 = temp; End 10操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM4.3.2 测试与设置指令该指令将状态测试和状态设置集于一条指令中，形 成一个原子操作。也就是说，两个操作的执行不受中断信 号的干扰。下面将指令格式定义为
12、TS（），功能是，读出 一个指定变量的值，同时将一个新值置入。对于逻辑变量，比如lock，TS（）的测试和设置的功 能可描述为下面的函数：Function TS(lock) Begin TS = Lock; Lock = true; End 11操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM下面的例子中定义的全局变量是 mutex，初始值为false表示无人进入。利用TS指令实现的互斥机制描述如下。Procedure Process (i)BeginWhile (TS（mutex）) do skip; / 循环等待Critical section;mutex = false;End.12操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统二十一世纪计算机本科教育OPERATING SYSTERM4.4 信号量机制著名的计算机学者Dijkstra通过长期的操作系
