第三章进程管理5(同步和互斥2)

计算机操作系统大学本科课件

经典的进程同步问题发送进程和接收进程的同步问题 利用信号量可以解决合作进程之间的同 步。 设进程Pa,Pb Pa,Pb通过缓冲区队列传送数 例：设进程Pa,Pb通过缓冲区队列传送数 据 1

Pa

BUF1

BUF2

.….

BUFn

Pb

计算机操作系统大学本科课件

发送和接送过程满足的条件是： 发送和接送过程满足的条件是 1)在Pa至少送一块数据入一个缓冲区之 1)在Pa至少送一块数据入一个缓冲区之 ,Pb不可能从缓冲区中取出数据 前,Pb不可能从缓冲区中取出数据 2)Pa往缓冲队列发送数据时 往缓冲队列发送数据时, 2)Pa往缓冲队列发送数据时,至少有一个 缓冲区是空的; 缓冲区是空的; 3)由Pa发送的数据块在缓冲队列中按先 3)由Pa发送的数据块在缓冲队列中按先 进先出(FIFO)方式排列. (FIFO)方式排列 进先出(FIFO)方式排列. 描述发送过程deposit (data)和接受过 描述发送过程deposit (data)和接受过 程remove (data) .

Pa

BUF1

BUF2

.….

BUFn

Pb

计算机操作系统大学本科课件

1)Bufempty 进程Pa的私用信号量, 1)Bufempty————进程Pa的私用信号量, Bufempty 进程Pa的私用信号量 进程Pb的私用信号量; Buffull ————进程Pb的私用信号量; 进程Pb的私用信号量 2)Bufempty的初始值为n(n 为缓冲队列的缓冲区 2)Bufempty的初始值为n(n 的初始值为 个数),Buffull的初始值为0; ),Buffull的初始值为 个数),Buffull的初始值为0; 发送过程Deposit(data),接送过程Remove(data), Deposit(data),接送过程Remove(data),这 发送过程Deposit(data),接送过程Remove(data),这 两个过程必须同步，因为,因为过程deposit(data) deposit(data)的 两个过程必须同步，因为,因为过程deposit(data)的 执行结果是过程remove(data)的执行条件, remove(data)的执行条件 执行结果是过程remove(data)的执行条件,而当缓冲 队列全部装满数据时,remove(data)的执行结果又是 队列全部装满数据时,remove(data)的执行结果又是 ,remove(data) deposit(data)的执行条件 的执行条件。 deposit(data)的执行条件。

Pa

BUF1

BUF2

.….

BUFn

Pb

计算机操作系统大学本科课件

发送过程deposit (data)和接受过程 和接受过程remove 发送过程deposit (data)和接受过程remove (data)Pa:deposit(data) begin local x P(Bufempty) 按FIFO方式选择一个 方式选择一个 空缓冲Buf(x); 空缓冲 Buf(x)<--data Buf(x)置满标记 置满标记 V(Buffull) end Pb:remove(data) begin local x P(Buffull) 按FIFO方式选择一个 方式选择一个 装满数据的缓冲Buf(x) 装满数据的缓冲 data<--Buf(x) Buf(x)置空标记 置空标记 V(Bufempty) end

计算机操作系统大学本科课件

Dijkstra把同步问题抽象成一种生产者和消 Dijkstra把同步问题抽象成一种生产者和消 费者关系， 费者关系，计算机系统中的许多问题都可以被归 结为生产者和消费者关系，例如， 结为生产者和消费者关系，例如，生产者可以是 计算进程，消费者是打印进程， 计算进程，消费者是打印进程，

输入时输入进程 是生产者，计算进程是消费者。 是生产者，计算进程是消费者。我们可以通过一 个缓冲区把生产者和消费者联系起来P1 P2 P3 . Pn. C1 C2

1

2

3

… …. … … n

C3 .

Cn

计算机操作系统大学本科课件

经典的进程同步问题Proceducer2 生 产 者 - 消 费 者 的 同 步 问 题 (The ProceducerConsumer Problem) 举例： 举例： 一个生产者 一个消费者

产品

仓库 生产者把产品生产出来，送入仓库。 生产者把产品生产出来，送入仓库。给 消费者发信号，消费者得到信号后， 消费者发信号，消费者得到信号后，到仓库 取产品，取走产品后给生产者发信号…… 取产品，取走产品后给生产者发信号

计算机操作系统大学本科课件

生产者-消费者问题是相互合作进程关 系的一种抽象 输入——计算——打印生产者 消费者 生产者 消费者 系统中使用资源的进程——消费者 系统中释放资源同类资源的进程——生产者

一个生产者

产品仓库

一个消费者

计算机操作系统大学本科课件

要解决进程的同步问题要满足的条件 1 想接收数据时，有界缓冲区中至少有一个单元是满的 想接收数据时， 2 生产者想发送数据时，有界缓冲区中至少有一个单元是空的 生产者想发送数据时， 同步问题 由于缓冲区是临界资源，所以生产者和消费者之间必须互斥的 访问临界资源

用信号量解题的关键步骤： 信号量的设置； 给信号量赋初值(常用的 互斥和同步信号量值的大小); P、V操作安排的 位置(其中，P的顺序不能颠倒，V的顺序任意)

计算机操作系统大学本科课件

设：公用信号量 mutex 表示缓冲区的个数 初值为1 (消费者)私用信号量 full 表示有界缓冲区中非空单元数 初值为0 (生产者)私用信号量 avail 表示有界缓冲区中空的单元数 初值为n deposit(data): begin P(avail) 检查缓冲区中是否有空单元 执行后n-1 P(mutex) 检查缓冲区是否可用 执行后 mutex=0 送数据入缓冲区 V(full) 执行后，非空单元数加1 0+1=1 V(mutex) 释放缓冲区中的资源 end Remove(data): begin 检查缓冲区是否有数据 P(full) P(mutex) 访问缓冲区 取缓冲区中某单元数据 V(avail) 取走数据以后，有界缓冲区的空单元个数加1 V(mutex) 释放缓冲区 end

计算机操作系统大学本科课件

次序

deposit(data): begin P(avail)P(mutex)

送数据入缓冲区 V(full)V(mutex)

endRemove(data): begin P(full) 次序 P(mutex) 取缓冲区中某单元数据 V(avail) V(mutex) end

公用信号量,互斥时使用的信 公用信号量, 号量(二元信号量): ):它仅允 号量(二元信号量):它仅允 许取值为“ 许取值为“0”与“1”,用 作互斥。 作互斥。它联系着一组共行进 初值为1 程，初值为1,每个进程均可 对之施加P、V操作。 对之施加P、V操作。 P、V操作 私用信号量：一般信号量(资 私用信号量：一般信号

量( 源信号量): ):它联系着一组共 源信号量):它联系着一组共 行进程，但其初值为0 行进程，但其初值为0,或为 某个正整数n,表示资源的数 某个正整数n,表示资源的数 n, 主要用于进程同步。 目，主要用于进程同步。只允 许拥有它的进程对之施加 进程对之施加P 许拥有它的进程对之施加P操 作，对V操作没有限制 操作没有限制

(消费者)私用信号量 full 表示有界 缓冲区中非空单元数 初值为0 表示有界 缓冲区中空的单元数 初值为n(生产者)私用信号量 avail

计算机操作系统大学本科课件

几个经典的进程同步问题生产者—消费者问题 哲学家进餐问题 读者—写者问题 图书馆阅览室问题 理发师问题 吃水果问题 司机—售票员问题 过河问题

计算机操作系统大学本科课件

生产者—消费者问题一个最著名的进程同步问题 问题描述：一组生产者向一组消费者提 供消息，它们共享一个有界缓冲池，生 产者存入消息，消费者从中取得消息。

计算机操作系统大学本科课件

哲学家进餐问题哲学家进餐问题是典型的同步问题，是由Dijkstra提出并解 决的。 问题描述5个哲学家，他们的生活方式是交替的思考和进餐。 哲学 …… 此处隐藏：3683字，全部文档内容请下载后查看。喜欢就下载吧 ……