操 作 系 统
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
二十一世纪计算机本科教育
• 第四次尝试
这是一个“礼让为先”的算法，每个进程设置好自 己的flag标志，表明希望进入临界区。但也准备重置flag， 以表示谦让。算法如下： Process P (1) Process P (2) Begin begin …… …… Flag[1] = true; Flag[2] = true; While (Flag[2]) do While (Flag[1]) do {flag[1]=false; {flag[2]=false; flag[1]=true}; flag[2]=true}; Critical section; Critical section; Flag[1] = false; Flag[2] = false; …… …… end. end.
操 作 系 统
4
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
5
二十一世纪计算机本科教育
算法如下： Process P (1) Begin …… While (Flag[2]) do skip; Flag[1] = true; Critical section; Flag[1] = false; …… end.
•第三次尝试 第三次尝试
在第二次尝试的基础上，将其中的两个语句顺序交换，形 成了新的算法如下： Process P (1) Process P (2) Begin begin …… …… Flag[1] = true; Flag[2] = true; While (Flag[2]) do skip; While (Flag[1]) do skip; Critical section; Critical section; Flag[1] = false; Flag[2] = false; …… …… end. end.
Procedure XCHG(op1,op2) Begin Boolean temp; temp = op1; op1 = op2; op2 = temp; End
操 作 系 统
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
二十一世纪计算机本科教育
4.3.2 测试与设置指令
该指令将状态测试和状态设置集于一条指令中，形成 一个原子操作。也就是说，两个操作的执行不受中断信号 的干扰。下面将指令格式定义为TS（），功能是，读出一 个指定变量的值，同时将一个新值置入。 对于逻辑变量，比如lock，TS（）的测试和设置的功 能可描述为下面的函数： Function TS(lock) Begin TS = Lock; Lock = true; End 操 作 系 统
二十一世纪计算机本科教育
4.4.2 记录型信号量
操 作 系 统
16
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
操 作 系 统
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
二十一世纪计算机本科教育
4.2
– 第一次尝试
互斥： 互斥：软件方法
Dekker方法 4.2.1 Dekker方法
算法中设计了一个变量turn保存允许进入临界区的进程编号 （初值为1，表示进程1可以首先进入）。当一个进程要求进入临 界区时，先检查turn的值。若turn保存的不是自己的进程编号就 进行循环等待；否则进入临界区。访问完成后退出临界区，再将 turn设置为对方的进程编号。
11
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
Procedure Process (i) Begin …… While (TS（mutex）) do skip; Critical section; mutex = false; …… End.
二十一世纪计算机本科教育
下面的例子中定义的全局变量是 mutex，初始值为false表示无人进入。 false表示无人进入 mutex，初始值为false表示无人进入。 利用TS指令实现的互斥机制描述如下。 TS指令实现的互斥机制描述如下 利用TS指令实现的互斥机制描述如下。
操 作 系 统
7
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
二十一世纪计算机本科教育
正确的算法
为了避免过度互斥礼让的问题，Dekker使用第一种尝试中的轮盘 变量turn，表示哪个进程有权进入临界区。让它在两个进程的活动中规 定一个强制性的顺序。算法如下： Process P (1) Process P (2) Begin begin …… …… Flag[1] = true; Flag[2] = true; While (Flag[2]) do While (Flag[1]) do if (turn=2) if (turn=1) {flag[1]=false; {flag[2]=false; while (turn=2) do skip; while (turn=1) do skip; flag[1]=true}; flag[2]=true}; Critical section; Critical section; turn=2; turn=1; Flag[1] = false; Flag[2] = false; …… …… end. end.
4.1
基本概念
4.1.1 临界资源和临界区
临界资源（Critical Resources）：一种一次只能为一个进程服务的资源。 临界资源 临界区（Critical Section）：进程中访问临界资源的程序。每个使用该 临界区 资源的进程都要包含一个临界区。
操作系统在管理可控制资源分配与使用方面，应当保 证进程对临界资源的访问满足以下3点： 操 互斥访问要求。 作 不致于产生“死锁”。 系 不能有“饥饿”进程。 统
Process P (2) begin …… While (Flag[1]) do skip; Flag[2] = true; Critical section; Flag[2] = false; …… end.
操 作 系 统
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
6
二十一世纪计算机本科教育
– 第二次尝试
算法中定义了一个标志数组flag[]。当flag[i]=true，表示 进程i正在临界区。初始时Flag[]的各分量值皆为false，表示尚 无进程进入。当一个进程要求进入临界区时，先检查是否有进程 已进入。若有进程进入，就循环等待；否则，设置自己的标志为 真，立即进入。访问完成后再将自己的标志设为假。
13
操 作 系 统 操 作 系 统 操 • 作 系 统 操 作 系 统
14
二十一世纪计算机本科教育
4.4.1 整型信号量
• 整型信号量是Dijkstra最初提出的一种信号量，被定 义为整型变量。其取值范围是[0，1]。其值等于1是放 行状态（也称作“绿灯”），等于0为阻止状态（也称 作“红灯”）。 整型信号量机制中的P、V操作是两个小巧玲珑的过程。 它们是操作系统中提供的两个原语，其代码如图所示。 操 作 系 统
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
3
二十一世纪计算机本科教育
4.1.2 互斥管理准则
– 空闲让进：当没有进程在临界区时，任何需要进 空闲让进： 入临界区的进程都允许立即进入。 – 忙则等待：在共享同一对象的所有进程中，一次 忙则等待： 只能有一个进程进入临界区。其它要求进入临界 区的进程只能等待。 – 有限等待：任何一个进程经有限时间等待后都能 有限等待： 进入临界区，不允许出现进程死锁或饥饿的情况 发生。 – 让权等待：当一个进程不能进入临界区时要立即 让权等待： 阻塞自己，释放处理机让其它进程使用，避免 “忙等”。
操 作 系 统
8
操 作 统 操 作 系 统 操 作 系 统 操 作 系 统
二十一世纪计算机本科教育
系 4.2.2
Peterson算法 Peterson算法
变量turn用来保存进程的编号，当turn=i，表示进程i有权进入临界 区。数组flag表示哪个进程进入了临界区，Flag[i]=true，表示进程i已进 入。初始时，标志数组flag的各元素值皆为false，表示无进程进入临界 区。变量turn可以不设初始值。下面是该算法的主要部分：
// 循环等待
操 作 系 统
12
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
二十一世纪计算机本科教育
4.4
信号量机制
著名的计算机学者Dijkstra通过长期的操作系统研究与 设计，于1965年提出了一种同步机制——信号量机制。该 机制由一个称为信号量（Semaphore，也译为“信号灯”） 的特殊变量和两个被命名为P、V操作的原语组成。在广泛 的应用中，该机制得到了迅速发展。 这一机制的基本原理是，为每个临界资源设置一个信 号量，负责在多个进程之间转发互斥信息。当一个进程需 要互斥使用某个临界资源时，可通过对信号量的P操作， 了解该资源的空闲情况。当它使用完该临界资源后，又可 操 通过对相关信号量的V操作，让其它需要该资源的进程感 作 知到它的离去。 系 若一个资源被视为临界资源，就应当为它定义一个独 统 立的信号量，对进程访问起“放行”和“阻止”作用，就 像交通管理中每个路口设置的交通灯一样。
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
二十一世纪计算机本科教育
第4章 并发与互斥
主要内容
• • • • • • 基本概念 互斥：软件方法 硬件方法 信号量机制 管程 死 锁
操 作 系 统
1
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统
2
二十一世纪计算机本科教育
15
操 作 系 统 操 作 系 统 操 作 系 统 操 作 系 统