Transcript Chapter 6并发：死锁和饥饿

Operating
Systems:
Internals
and Design
Principles
Chapter 6
并发：死锁和饥饿
Seventh Edition
By William Stallings
Operating Systems:
Internals and Design Principles
当两列火车在路口相遇时，二者都应该完全停下来，除非对方已离
开，否则不可以开动。
—A TREASURY OF RAILROAD FOLKLORE,
B. A. Botkin and Alvin F. Harlow
6.1 死锁

一组相互竞争系统资源或进行通信的进程间
的“永久”阻塞。

当一组进程中的每个进程都在等待某个事
件，而只有在这组进程中的其他被阻塞的进
程才能触发这个事件，这组进程发生死锁。

永久的

没有有效的解决方法
潜在的死锁
I need quad
C and B
I need quad
D and A
I need quad
B and C
I need quad
A and B
真正的死锁
HALT until
D is free
HALT until
A is free
HALT until
C is free
HALT until
B is free
联合进程图
可重用
• 能被一个进程安全使用，并且不会
由于使用而耗尽
• processors, I/O channels, main
and secondary memory, devices,
and data structures such as files,
databases, and semaphores
可消耗
• one that can be created
(produced) and destroyed
(consumed)
• interrupts, signals, messages,
and information
• in I/O buffers
可重用资源死锁示例
可重用资源死锁示例2:
Memory Request

可用内存空间200Kbytes，有两个进程:
P1
...
...
Request 80 Kbytes;
Request 70 Kbytes;
Request 60 Kbytes;
Request 80 Kbytes;
...

P2
...
当两个进程第二次请求内存时，发生死锁
可消耗资源Deadlock

考虑一对进程，进程双方都要尝试从对方接收消息，然后向对方发送
消息

如果使用阻塞接受，则发生死锁
方法
资源分配策略
死锁
一次性请求所有资源
的
检
预防
保守的；预提交资
源
抢占
资源排序
测、
预防
不同方案
避免
处于检测和预防之
操作以发现至少一条安全路
间
行
和
避免
检测
非常自由，只要可
能，就允许
周期性调用以调试死锁
资源分配图
Resource Allocation Graphs
Resource Allocation Graphs
死锁的条件
互斥
占有且等待
• 一次只有
一个进程
可以使用
一个资源
• 一个进程
等待其他
资源时，
继续占有
已经分配
的资源
不可抢占
循环等待
• 不能强行
抢占进程
已占有的
资源
• 存在一个
封闭的进
程链，每
个进程至
少占有此
链中下一
个进程所
需的一个
资源
6.2 死锁预防
死锁的处理

处理死锁一般有三个方法：
预防死锁 Prevent Deadlock
• 采取一个策略防止死锁条件的任何一个发生
避免死锁 Avoid Deadlock
• 基于当前的资源分配状态做动态选择
检测死锁 Detect Deadlock
• 检测死锁的存在并从死锁中恢复出来

设计一种系统来排除发生死锁的可能性。两种方法：
 间接
 防止前三个必要条件的任何一个的发生
 直接
 防止循环等待的发生
互斥
Mutual
Exclusion
如果对一个资源需
要进行互斥方法，
那么此作系统必须
支持互斥。
占有且等待
Hold and Wait
要求进程一次性请求
所有需要的资源，并
阻塞这个进程，直到
所有请求都同时满足

不可抢占
 如果已占有某个资源的进程进一步申请资源时被拒绝时，进
程必须释放它原先分配的资源，如有必要，可再次申请这个
资源和其他的资源。
 一个进程请求被另一个进程占有的资源时，OS可以抢占另一
个进程，要求其释放资源。

循环等待
 定义一个对资源类型的线性顺序
6.3 死锁避免

动态决策，是否进行当前的资源分配取决于该分配过程会不
会引起死锁

要求知道将来的进程资源请求情况
Deadlock
Avoidance
资源分配拒绝
• 如果进程新增加的资
源会导致死锁，则不
允许此分配
进程初始化拒绝
• 如果一个进程的资
源请求会导致死锁，
则不允许启动次进
程

n个进程和m个不同类资源的系统

Resource = 𝑹 = 𝑹𝟏, 𝑹𝟐, … , 𝑹𝒎

Available = 𝑽 = (𝑽𝟏, 𝑽𝟐, … , 𝑽𝒎)


Claim = 𝐂 =
𝑪𝟏𝟏 𝑪𝟏𝟐 …𝑪𝟏𝒎
𝑪𝟐𝟏 𝑪𝟐𝟐
…𝑪𝟐𝒎
…
…
𝑪𝒏𝟏 𝑪𝒏𝟐…𝑪𝒏𝒎
Allocation = 𝐀 =
𝑨𝟏𝟏 𝑨𝟏𝟐 … 𝑨𝟏𝒎
𝑨𝟐𝟏 𝑨𝟐𝟐
… 𝑨𝟐𝒎
…
…
𝑨𝒏𝟏 𝑨𝒏𝟐 … 𝑨𝒏𝒎
𝑵
𝒊=𝟏 𝑨𝒊𝒋

𝐑 𝐣 = 𝑽𝒋 +

𝑪𝒊𝒋 ≤ 𝑹𝒊

𝐀𝐢𝐣 ≤ 𝑪𝒊𝒋

死锁避免策略：如果一个新进程的资源需求会导致死锁，拒绝进
程Pn+1，仅当
𝑵
𝑹𝒋 ≥ 𝑪 𝒏
𝒋
+𝟏
+
𝑪𝒊𝒋
𝒊=𝟏

又称为银行家算法（banker’s algorithm）

State ——系统的状态是当前给进程分配的资源情况，包含两个向
量Resource和Available及两个矩阵Claim和Allocation

Safe state——安全状态是指至少有一个资源分配序列不会导致死
锁

Unsafe state
安全状态的确定

四个进程和三类资源的系统

资源被分给四个进程，这是安全状态吗？
资源总量
分配后的可
用资源
P3 运行结束后
因此，这是一个安全状
态
死锁避免逻辑

不需要死锁预防中的抢占和回滚进程

比死锁预防的限制少

必须实现声明每个进程请求的最大资源

所讨论的进程必须是无关的，也就是说，它们执行
的顺序必须没有任何同步请求的限制

分配的资源数目必须是固定的

在占有资源时，进程不能退出
6.4 死锁检测
死锁处理策略
死锁预防策略非常保守
• 通过限制访问资源和在进程上强加约束来
解决死锁问题
死锁检测策略完全相反
• 不限制资源访问或约束进程行为
死锁检测算法
 死锁的检查可以非常频繁地在每次资源请求时发生，也可以更
少些，取决于死锁发生的可能性
优点:
 可尽早检测死锁
 算法相对简单
 缺点
 频繁检查会消耗相对多的处理器时间
死锁检测算法
定义请求矩阵Q，Qij表示进程i请求j类型
资源的数量。算法主要是标记没有死锁
进程的过程，最初，所有进程未标记。
1.
2.
3.
4.
标记Allocation中一行全为0的矩阵
初始化临时向量W，令W等于Available向量
查找下标i，使进程i当前未标记且Q的第i行小于等于W，
即对所有的1 ≤ 𝑘 ≤ 𝑚, 𝑄𝑖𝑗 ≤ 𝑊𝑘，如果找不到这样的
行，终止算法
如果找到，标记进程i，并把Allocation矩阵中的相应行加
到W中，即对所有1 ≤ 𝑘 ≤ 𝑚, 令𝑊𝑘 = Wk + Aik，返回步骤
3
R1 R2 R3 R4 R5
R1 R2 R3 R4 R5
P1
0
1
0
0
1
P1
1
0
1
1
0
P2
0
0
1
0
1
P2
1
1
0
0
0
P3
0
0
0
0
1
P3
0
0
0
1
0
P4
1
0
1
0
1
P4
0
0
0
0
0
Request matrix Q
Allocation matrix A
R1
R2
R3
R4
R5
2
1
1
2
1
Resource vector
R1
R2
R3
R4
R5
0
0
0
0
1
Available vector
 算法不保证防止死锁，是否死锁取决于
将来同意请求的顺序，只能确定当前是
否存在死锁
死锁恢复

取消所有死锁进程。

把每个死锁进程回滚到前面定义的某些检查点（checkpoint），
并重启所有进程。

连续取消死锁进程，直到不再存在死锁。

连续抢占资源直到不再存在死锁。
死 结
锁
方
法
总
6.6 哲学家就餐问题
Dining Philosophers Problem
•No two
philosophers can
use the same fork at
the same time
(mutual exclusion)
•No philosopher
must starve to death
(avoid deadlock and
starvation)
Cont.
A Second Solution . . .
使用管程
Monitor解
决
6.7 UNIX的并发机制
UNIX Concurrency Mechanisms

UNIX 提供了一系列用来进程间通信和同步的机制:
Pipes
Messages
Semaphores
Shared
memory
Signals
管道Pipes

是一个环形缓冲区，允许两个进程以生产者/消
费者模型通信
 first-in-first-out queue, written by one
process and read by another
Two types:
• Named
• Unnamed
Messages

消息是一段有类型的文本

UNIX 为参与消息传递的进程提供了msgsnd 和msgrcv system
calls

每个进程都有与之相关联的消息队列，其功能类似于邮箱
Shared Memory

最快的进程间通信方式

是虚拟内存中多个进程共享的一个公共内存块

每个进程有一个Read-only或Write-only权限

互斥约束不是shared-memory机制的一部分， 必须
由使用共享内存的进程提供

是 semWait and semSignal 原语的推广

一个进程操作一个信号量未完成时，其他进程不允许访问信号量

增量和减量可以大于1
与信号量相关的是阻塞在该信号量上的进程队列

包含以下元素
•
•
•
•
信号量的当前值
最后一个操作信号量进程的process
等待信号量的值比当前值大的进程个数
等待信号量的值变为0的进程个数

以集合的形式创建，semctl一次可同时设置集合中
的所有信号量，每次操作的实际功能由sem_op参
数的值决定
sem_op的可能值
• >0，增加信号量值，唤醒等待进程
• =0，检查信号量值，如=0，继续；否则增加等待信号
量变0的进程数，该进程阻塞
• <0，绝对值小于或等于信号量的值，信号量
+=sem_op，如结果=0，唤醒那些等待该事件的进程
• <0，绝对值大信号量的值，阻塞在信号量增加的事件
上

是一种软件机制，用来通知进程异步事件的发生
 类似于硬件中断，但没有优先级。内核平等对待所有信号。

信号的传递是通过更新要接收信号的进程的进程表的某个字段来实现

进程收到信号后可做如下回应:
 执行缺省操作


executing a signal-handler function
ignoring the signal
UNIX
Signals
V alu e
Nam e
D escrip tion
01
S IG H U P
阻塞；当内核认为进程在做无用工作时发给进程
02
S IG IN T
Interrupt
03
S IG Q U IT
Q uit; 由 用 户 发 送 ， 用 来 引 发 进 程 停 止 并 产 生 信 息 转 储
04
S IG IL L
非法指令
05
S IG T R A P
跟 踪 捕 捉 （ T race trap ） 触 发 用 于 进 程 跟 踪 代 码 的 执 行
06
S IG IO T
IO T instruction
07
S IG E M T
E M T instruction
08
S IG F P E
F loating -point ex ception
09
S IG K IL L
杀 死 K ill; term inate process
10
S IG B U S
B us error
11
S IG S E G V
段 错 误 S egm entation violation; process attem pts to
access location outside its virtual address space
12
S IG S Y S
参 数 错 误 system call
13
S IG P IP E
W rite on a pipe that has no readers attach ed to it
14
S IG A L R M
A larm clock; 一 个 进 程 希 望 在 一 段 时 间 后 收 到 信 号 时
产生
15
S IG T E R M
软 件 终 止 S oftw are term ination
16
S IG U S R 1
U ser-d efined signal 1
17
S IG U S R 2
U ser-d efined signal 2
18
S IG C H L D
子 进 程 死 D eath of a child
19
S IG P W R
电 源 故 障 P ow er failure
Linux Kernel
Concurrency Mechanism

Includes all the mechanisms found in UNIX plus:
Spinlocks
Barriers
Semaphores
Atomic
Operations
Atomic Operations

Atomic operations execute without interruption and
without interference

Simplest of the approaches to kernel synchronization

Two types:
Integer
Operations
Bitmap
Operations
operate on an
integer variable
operate on one of
a sequence of bits
at an arbitrary
memory location
indicated by a
pointer variable
typically used to
implement
counters
Linux
Atomic
Operations
Spinlocks

Most common technique for protecting a critical section in Linux

Can only be acquired by one thread at a time
 any other thread will keep trying (spinning) until it can acquire the
lock

Built on an integer location in memory that is checked by each thread
before it enters its critical section

Effective in situations where the wait time for acquiring a lock is expected
to be very short
Disadvantage:
 locked-out threads continue to execute in a busy-waiting mode

Semaphores
User level:
 Linux provides a semaphore interface corresponding to that in UNIX
SVR4
 Internally:
 implemented as functions within the kernel and are more efficient than
user-visable semaphores
 Three types of kernel semaphores:
 binary semaphores
 counting semaphores
 reader-writer semaphores

Linux
Semaphores
Barriers

enforce the order in which instructions are executed
Table 6.6
Linux Memory Barrier Operations
Synchronization Primitives
Mutual
exclusion
(mutex)
locks
Condition
variables
Semaphores
In addition to the
concurrency
mechanisms of
UNIX SVR4,
Solaris supports
four thread
synchronization
primitives:
Readers/w
riter locks
Solaris
Data
Structures

Used to ensure only one thread at a time can access the resource
protected by the mutex

The thread that locks the mutex must be the one that unlocks it

A thread attempts to acquire a mutex lock by executing the
mutex_enter primitive

Default blocking policy is a spinlock

An interrupt-based blocking mechanism is optional
Semaphores
Solaris provides classic counting
semaphores with the following primitives:
• sema_p() Decrements the semaphore,
potentially blocking the thread
• sema_v() Increments the semaphore,
potentially unblocking a waiting thread
• sema_tryp() Decrements the
semaphore if blocking is not required
Readers/Writer Locks
 Allows
multiple threads to have simultaneous
read-only access to an object protected by the lock
 Allows
a single thread to access the object for
writing at one time, while excluding all readers
 when lock is acquired for writing it takes on the status of
write lock
 if one or more readers have acquired the lock its status is read
lock
A condition variable
is used to wait until
a particular
condition is true
Condition variables
must be used in
conjunction with a
mutex lock
Windows 7 Concurrency
Mechanisms

Windows provides synchronization among threads as part of the object
architecture
Most important methods are:
•
•
•
•
•
executive dispatcher objects
user mode critical sections
slim reader-writer locks
condition variables
lock-free operations
Wait Functions
Allow a
thread to
block its
own
execution
Do not
return
until the
specified
criteria
have been
met
The type
of wait
function
determines
the set of
criteria
used
Table 6.7
Windows
Synchronization
Objects

Similar mechanism to mutex except that critical sections can be
used only by the threads of a single process

If the system is a multiprocessor, the code will attempt to acquire a
spin-lock
 as a last resort, if the spinlock cannot be acquired, a dispatcher
object is used to block the thread so that the kernel can dispatch
another thread onto the processor
Slim Read-Writer Locks

Windows Vista added a user mode reader-writer

The reader-writer lock enters the kernel to block only after
attempting to use a spin-lock

It is slim in the sense that it normally only requires allocation of a
single pointer-sized piece of memory
 Windows
also has condition variables
 The
process must declare and initialize a
CONDITION_VARIABLE
 Used
with either critical sections or SRW locks
 Used as follows:
1. acquire exclusive lock
2. while (predicate()==FALSE)SleepConditionVariable()
3. perform the protected operation
4. release the lock
Lock-free Synchronization

Windows also relies heavily on interlocked operations for
synchronization
 interlocked operations use hardware facilities to guarantee that
memory locations can be read, modified, and written in a single
atomic operation
“Lock-free”
• synchronizing without taking a software lock
• a thread can never be switched away from a
processor while still holding a lock

Deadlock:



一组进程竞争系统资源或互相通信被阻塞的现象
死锁是永久的，直到OS采取措施
涉及到可重用资源和可消耗



Consumable = destroyed when acquired by a process
Reusable = not depleted/destroyed by use
死锁的处理：
 prevention – guarantees that deadlock will not
occur
 detection – OS checks for deadlock and takes
action
 avoidance – analyzes each new resource request