4.2实现互斥的方法
Dekker算法
1965年的荷兰数学家T.J.Dekker
避免“无原则”的礼让
规定各程序进入临界区的顺序
全局数组变量flag表示进入临界区的“意愿”
全局变量turn解决进入顺序
算法的问题
逻辑复杂
正确性难证明
存在轮流问题
存在忙等待
Peterson算法
1981年数学家G.L.Peterson
简单出色（不存在轮流问题）
flag和turn含义与Dekker相同
先设turn=别人，只有“flag[别人]”和“turn=别人”同时为真时才循环等待
硬件实现方法
中断禁用
中断禁用（关中断）原理
单CPU体系结构
如果进程访问临界资源时（执行临界区的代码）不被中断，就能保证互斥的访问
途径
使用关/开中断指令
x86的开/关指令为STI/CLI
限制了处理器交替执行各程序的能力，不能用于多核处理器结构
专用指令
适用范围
单处理器或共享主存多核处理器结构
对统一存储单元的访问是互斥的
软件算法第二种尝试失败的原因：检测flag[1]和置位flag[0]在一个指令周期完成不会出错
TestSet指令（TS）
定义（逻辑）————比较并交换指令的bool特例
原子指令
指令功能
测试内存变量var1某一位的值：
0：设置标志寄存器的zf标志置位(1)，而且var1这位变1
1：设置标志寄存器的zf标志复位(0)，而且var1这位变1
解决方案
利用TestSet实现锁机制
锁机制自旋锁
内核自用的一种互斥机制
一个锁变量（其实是一个二进制位）lockbit
加锁操作lock
解锁操作unlock
exchange指令
定义：交换一个寄存器和内存单元的内容
原子操作
x86 CPU的对应指令为XCHG
指令功能：根据寄存器reg1与内存单元var1的值对换，并根据结果设置标志寄存器的z标志。
利用xchg实现锁机制
互斥方法
设置锁变量lockvar，初值为0
临界区前，lock
临界区后，unlock
机器指令方法的优缺点
优点
适用于单处理器或共享多核处理器系统，进程数量随意
简单且易于证明
可以使用多个变量支持多个临界区
缺点
忙等待/自旋等待
可能饥饿
可能死锁
常用并发机制
4.3信号量
信号量机制
荷兰计算机科学家 E. W. Dijkstra提出 (1965)，解决并发进程问题的第一个重要进展，需操作系统支持
两个或多个进程可以通过传递信号进行合作，从而可以迫使进程在指定位置暂停，直到它接收到特定信号
信号量机制可以满足任何复杂的合作要求
信号量值用来表示可用资源数目（非负整数）
信号量机制的组成
操作系统提供的用于线程并发控制的特殊数据结构
含有一个非负整数变量和三个专门操作
初始化：通常将信号量的值初始化为非负整数（=可用资源数）
P操作/semWait操作/Down操作
信号量值减1
若信号量的值变成负数，则请求执行P操作的进程被阻塞
V操作/semSignal操作/Up操作
信号量值加1
如果信号量的值不是正数（其绝对值=现在被阻塞的进程数[等待队列长度]），则使一个因执行P操作阻塞的进程接触阻塞（唤醒）
除此之外，无其他检查和修改信号量值的操作
信号量和P、V原语的描述
二元信号量
信号量的值只能是0或者1
和一般信号量具有相同的表达能力
因count不能小于0，需要其他方法判断等待队列是否为空
二元信号量的操作和原语描述
信号量的实际含义
信号量s（s.count)的初值
系统中某些资源的数目，应该≥0
进程执行P（s）/semWait（s）操作
申请一个单位的资源（s.count--）
若s.count < 0，资源已经分配完毕，进程被系统阻塞在s的队列上----让权等待
进程执行V（s）/semSignal（s）操作
释放一个单位资源（s.count++）
若s.count≤0，则唤醒一个等待进程
s.count
≥0：可用的资源数/可以执行P（s）而不会阻塞的进程数
<0：|s.count|为在队列中等待的进程数
信号量的实现
基本要求：保证P和V操作的原子性，实现信号量操作的互斥
软件方案：Dekker算法、Peterson算法
硬件支持方案：可以采用TS指令、关中断
信号量的TestSet指令实现
信号量的关中断实现
信号量的优缺点
优点：简单，表达能力强，用P、V操作可解决多种类型的同步、互斥问题
缺点：不够安全、P、V操作使用不当可能产生死锁，遇到复杂的同步问题时实现复杂
信号量机制的应用
实现互斥
进程同步
生产者-消费者问题
读者-写者问题
其他
4.3.1用信号量实现互斥/同步
实现互斥
n个进程访问同一个共享资源
设置信号量s，初始化为1
每个进程进入临界区之前执行P操作
进程离开临界区时执行V操作
保证最多只有一个进程在临界区，从而实现共享资源的互斥访问
实现同步
进程的同步
系统中一些进程需要相互合作共同完成一项任务：一个进程运行到某一点时需要另一伙伴进程提供消息
未获得消息之前，该进程属于阻塞状态，获得消息后被唤醒进入阻塞态
用信号量解决同步关系的方案
两个进程P1、P2，分别有操作a和b，a先于b执行
设置信号量s，初始化0或具体资源限制值
进程P1的操作a后执行V操作
进程P2的操作b前执行P操作
每执行一次操作a后，才可以执行b操作，从而实现进程同步
用信号量实现进程同步（例）
三个进程并发运行，合作完成数据输入、计算和打印输出工作
进程Pi将输入的数据写入缓冲区B1
进程Pc读出B1中的数据，完成计算，把结果写入缓冲区B2
进程Pp读出B2中的结果，打印输出
同步要求：（读出数据后缓冲区为空）
先写后读（不能读空缓冲区）
未读完不能写（不能写非空缓冲区）
四个信号量empty1、full1、empty1、full2，初始值分别为1、0、1、0（两个缓冲区都为空）
4.3.2生产者/消费者问题
若干进程通过有限的共享缓冲区交换数据
一组“生产者”进程不断写入
另一组“消费者”进程不断读出
共享缓冲区 无限/共有N个
任何时刻只能有一个进程可对共享缓冲区进行操作
有限缓冲区的生产者/消费者问题
对象
被阻塞事件
解除阻塞事件
生产者
插入满缓冲区
消费者移出一项
消费者
从空缓冲区中移出
生产者插入一项
解决方案