e=e-1 s=s-1 n=n+1
n=n-1 e=e+1

生产者 producer: while (true) { /* 生产v*/ semWait(empty); semWait(s); b[in] = v; semSigal(s); semSigal(full); in++; }

消费者 consumer: while (true) { semWait(full); semWait(s); w = b[out]; semSigal(s); semSigal(empty); out++; /* 消费w */ }
需要一个特殊变量（整数型）：称为信号量

荷兰 计算机科学家

1 提出“goto有害论”; 2 提出信号量和PV原语(1965); 3 解决了“哲学家聚餐”问题; 4 最短路径算法(SPF)和银行家算法的创造者; 5 第一个Algol 60编译器的设计者和实现者; 6 THE操作系统的设计者和开发者;
死锁

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

饥饿

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

共享合作关系

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

多个进程可以同时读一个数据项，但是必须互斥写 操作
P2: …… ② L2: printf(n); ③ n=0; ……. Go to L2;

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

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

处理器时间


存储器


机器指令方法的特点

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

缺点

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

当进程对一个信号量加1后，另一个进程会被唤醒， 两个进程继续并发运行

在向信号量发出信号后，不需要知道是否有另一
个进程正在等待，被解除阻塞的进程数量或者没
有或者是1
信号量的值：资源个数
因信号量阻塞的进程队列
申请分配资源
当前进程放入队列s.queue 阻塞此进程
释放资源
从s.queue中移除该进程P 把进程P插入到就绪队列

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



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

并发的困难

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

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

缓冲区满，生产者不能再加数据；缓冲区空，消费 者不能再取数据
生产者/消费者问题的无限缓冲区：in 〉out

生产者 producer:

while (true) {
/* 生产数据*/
b[in] = v;
in++; }
消费者 consumer: while (true) { while (in <= out) /*do nothing */; w = b[out]; out++; /* consume item w */ }
处理机上，实现并行执行。

并发的相关问题

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

分配给进程的处理器时间

并发出现的环境

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

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

semWait和semSignal必须成对出现

互斥时，位于同一进程，临界区的前后 同步时，交错出现于两个合作进程内

多个semWait的次序不能颠倒，否则可能导致死锁； 用于同步的semWait应出现在用于互斥的semWait 之前

多个semSignal的次序可以任意

在进程对信号量减1之前无法提前知道该信号量是

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

通信合作关系

进程直接知道对方的存在
进程间通过发送消息和接受消息来进行通信，
实现同步和协调各种活动；

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

必须强制实施互斥：一次只允许一个进程进入临界区 一个在非临界区停止的进程不能干涉其他进程 有限等待：决不允许出现需要访问临界区的进程被无限

putchar(chout);


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

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

如何实施？

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

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

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

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


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

问题：按照什么顺序从等待队列移出？

先进先出（FIFO）：阻塞最久的进程最先从队
列释放

强信号量：采用FIFO 策略的信号量

保证不会导致饥饿

弱信号量：没有规定移出顺序的（略）

对每一个临界资
源设一个信号量
s表示，初始化 为1；

每个进程进入临 界区之前执行
semWait(s),退出
临界区之后执行 semSignal(s);

信号量为实施互斥和进程间合作提供了强大灵 活的工具，但存难点

semWait和semSignal操作可能分布在整个程序中， 很难看出整体效果

因此提出管程（Monitor），一个程序设计语言结 构，可以锁定任何对象，提供与信号量相同的功能，
更易于控制

使用信号的管程

定义：管程由一个或多个过程、一个初始化序列和 局部数据组成的软件模块
文件 I/O设备

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

竞争关系

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

死锁 饥饿

互斥产生的额外控制问题

OS难对资源进行最优化分配-----死锁
难以定位程序设计错误

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

缓冲区是有限的---循环存储器
(b)

生产者 producer: while (true) { /* 生产数据*/ semWait(empty); semWait(s); b[in] = v; semSigal(s); semSigal(full); in++; }

消费者 consumer: while (true) { semWait(full); semWait(s); w = b[out]; semSigal(s); semSigal(empty); out++; /* consume item w */ }
chout = chin;
putchar(chout); P1恢复 chout = chin; putchar(chout);
Process P1

Process P2

chin = getchar();

chin = getchar();
chout = chin;

chout = chin; putchar(chout);
阻塞在信 号量lock

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

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

问题描述

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

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

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

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