阻塞在信 号量lock

对于同步，“一类资源”配一信号量s，初
始值为可用资源数量

如：s表示缓冲区的空闲状态；

问题描述

有一组生产者生产数据，放在缓冲区（同步）

设一信号量empty, 初始值为缓冲区大小

有一组消费者取数据，每次取一项（同步）

设一信号量full，初始值为0

任何时候只有一个主体可以访问缓冲区（互斥）

消费者 consumer: while (true) { semWait(full); semWait(s); w = b[out]; semSignal(s); semSignal(empty); out++; /* consume item w */ }
e=e-1 s=s-1 n=n+1
n=n-1 e=e+1

并发是指两个或多个事件在同一时间间隔内发生。在多道 程序环境下， 并发性是指在一段时间内宏观上有多个程序 在同时运行，但在单处理机系统中，每一时刻却仅能有一
道程序执行，故微观上这些程序只能是分时地交替执行。

并行是指两个或者多个事件在同一时刻发生。
多处理机系统中，可以并发执行的程序便可被分配到多个

传递消息时，进程间未共享资源，则不需互斥，
但可能会死锁或饥饿，通信成为临界资源

必须强制实施互斥：一次只允许一个进程进入临界区 一个在非临界区停止的进程不能干涉其他进程 有限等待：决不允许出现需要访问临界区的进程被无限
延迟的情况，即不会死锁或饥饿

有空让进： 临界区空闲时，请求进程可进 对相关进程的执行速度和处理器的数目没有任何要求和 限制 一个进程驻留在临界区中的时间必须是有限的
处理机上，实现并行执行。

并发的相关问题

进程间的通信
资源共享与竞争
多个进程活动的同步

分配给进程的处理器时间

并发出现的环境

多应用程序：共享处理器时间
结构化应用程序：设计成一组并发进程
操作系统结构：上一点用于操作系统

临界资源：一次仅允许一个进程使用的共享资源； 如：打印机、变量、数组


方法

软件方法：由并发执行的进程担负这个责任
机器指令：减少开销，但不通用
在操作系统或程序设计语言中提供支持

中断禁用

单处理器中并发进程不能重叠只能交替 一个进程一直运行到调用系统服务或被中断 保证互斥只需保证一个进程不被中断

缺点

长时间关中断效率明显降低
不能用于多处理器结构中
实现互斥和同步

竞争关系

进程间相互不知对方存在 竞争：CPU、设备、内存等 影响：进程的结果与其他进程无关；会影响状态； 可能引发的问题：互斥

死锁 饥饿

互斥产生的额外控制问题

死锁

进程之间互有对方必需的资源而不释放 例：R1 P2，R2 P1

饥饿

两个进程轮流访问临界资源，其他进程被无限地拒 绝访问资源，处于饥饿状态

用于同步：s>=0

s>=0, 可用资源的个数
s<0， |s|个进程等待资源

信号量的三个操作

2、semWait(s) 进程请求分配一个资源，操作使信号 量减1，若为负，进程阻塞，否则继续执行

3、semSignal(s)进程释放一个资源，操作使信号量加 1，若小于或等于0，则阻塞的进程被解除阻塞
也称P(s)操作，wait(s) 也称V(s)操作，signal(s)

信号量的三个操作

1、一个信号量s可以初始化成非负数

用于互斥：s=1, 取值 －(n－1)～1；

s=1时，有一个临界资源可用，一个进程可进入临界区 s=0时，临界资源已分配， 正有进程在临界区内 s<0时，|s|个进程等待进入临界区

专用机器指令

用于保证访问的原子性 1、比较和交换指令（compare and swap)、2、Exchange指令

机器指令方法的特点

适用于在单处理器或共享内存的多处理器上的任何数目的进程 非常简单且易于证明
可用于支持多个临界区，可以用自己的变量定义

缺点

忙等待：进程等待进入临界区，仍会继续消耗CPU 时间 可能饥饿：当需要选择等待进程进入时，某些可能被无限拒绝 可能死锁：低优先级的进程占有高优先级的进程所需资源

读者优先（重点掌握）

读者优先: 只要有读者，写者就得等待 写进程访问共享数据区，其他写进程和读进程就都
不能访问它

没有读进程在读，第一个试图读的进程需要等待， 至少已经有一个读进程在读时，其他读进程无需等 待

写者优先（不作详解 ）

只要有写者声明要写，不再允许新读者进入，只待 旧读者读完即可。

两人拣围棋问题：P1拣白子，P2 拣黑子（先），
两人交替进行，一次进允许一人拣
解：w: 可拣白子，w=0；b：可拣黑子，b=1

桌上一空盘，可向其中放一水果。爸爸可放一苹果或一桔
子，儿子只吃桔子，女儿只吃苹果。如何实现爸爸、儿子、 女儿三个进程的同步。 解：设信号量S：表示盘子，S=1；So：桔子数，So=0； Sa：苹果数，Sa=0
OS难对资源进行最优化分配-----死锁
难以定位程序设计错误

一个简单例子
void echo() ---多道程序设计系统中的共享函数
{
chin = getchar(); 全局共享变量
chout = chin;
putchar(chout);
}
P1 ——chin=getchar() 中断 P2——chin= getchar()

临界区：进程访问临界资源的那段程序代码；
互斥：当一个进程在临界区访问临界资源时，其他进程不能进
入临界区。 同步：合作的并发进程需要按先后次序执行

死锁：多个进程等待其他进程的资源，形成循环等待链；
饥饿：一个进程呈可执行状态，被调度器忽视而不能调度执行。

并发的困难

共享全局资源，引发数据安全问题

1972年图灵奖，“ 结构化程序设计之父”

不要求忙等的同步互斥工具
一个信号量表示一个资源或一个同步条件
当资源不可用时，进程将等待，直到释放资源
的另一个进程发来信号时才唤醒 由若干个机器指令构
成的完成某种特定功 能的一段程序，具有 不可分割性

两个原语访问

semWait(s) semSignal(s)
ห้องสมุดไป่ตู้

共享合作关系

进程间接知道彼此的存在 进程间通过共享某些资源（如：变量、文件）进行 合作，但不确切知道对方

多个进程可以同时读一个数据项，但是必须互斥写 操作

多个进程读写共享数据时，必须保持数据一致性

通信合作关系

进程直接知道对方的存在
进程间通过发送消息和接受消息来进行通信，
实现同步和协调各种活动；
需要一个特殊变量（整数型）：称为信号量

荷兰 计算机科学家

1 提出“goto有害论”; 2 提出信号量和PV原语(1965); 3 解决了“哲学家聚餐”问题; 4 最短路径算法(SPF)和银行家算法的创造者;


5 第一个Algol 60编译器的设计者和实现者;
6 THE操作系统的设计者和开发者;

P1优先级低，进入临界区中断；P2优先级高，抢占CPU，需要访问同一临界资
源，等待；P1 无法再次得到CPU ，资源无法释放，进入死锁。

解决并发进程问题基本原理：

两个或多个进程可以通过简单的信号进行合作，
一个进程可以被迫在某一位置停止，直到它接到
一个特定的信号

复杂的合作需求都可以通过适当的信号结构完成

设一信号量s，初始值为1

缓冲区满，生产者不能再加数据；缓冲区空，消费 者不能再取数据

生产者 producer:

while (true) {
/* 生产数据*/
b[in] = v;
in++; }
消费者 consumer: while (true) { while (in <= out) /*do nothing */; w = b[out]; out++; /* consume item w */ }

例：
n=5， 共享变量；
①②③：输出6，n=0 ②③①：输出5，n=1
②①③：输出5，n=0
×

OS必须能够跟踪不同的进程，依靠PCB OS必须为每个活跃的进程分配和释放各种资源

处理器时间
存储器
文件 I/O设备

OS必须保护每个进程的数据和物理资源 进程的功能和输出结果必须与执行速度无关

putchar(chout);


解决办法：控制访问该变量的代码

规定一次仅允许一个进程进入echo，并只在
echo运行结束后，才对另一个进程可用

如何实施？

竞争条件：发生在多个进程或者线程读写数据时， 最终结果依赖于多个进程的指令执行顺序
P1: …… ① L1: n++ ……. Go to L1; P2: …… ② L2: printf(n); ③ n=0; ……. Go to L2;