open-courses
Search…
公开课笔记
CMU 15-445/645 Database Systems
Relational Data Model
Advanced SQL
Database Storage
Buffer Pools
Hash Tables
Tree Indexes
Index Concurrency Control
Query Processing
Sorting&Aggregations
Join Algorithms
Query Optimization
Parallel Execution
Embedded Database Logic
Concurrency Control Theory
Two Phase Locking
Timestamp Ordering Concurrency Control
Multi-Version Concurrency Control
Logging Schemes
Database Recovery
Introduction to Distributed Databases
Distributed OLTP Databases
Distributed OLAP Databases
UCB - CS162
OS intro
Introduction to the Process
Processes, Fork, I/O, Files
I/O Continued, Sockets, Networking
Concurrency: Processes & Threads
Cooperating Threads, Synchronization
Semaphores, Condition Variables, Readers/Writers
Scheduling
Resource Contention & Deadlock
Address Translation, Caching
File System (18,19,20)
Distributed Systems, Networking, TCP/IP, RPC (21,22)
Distributed Storage, Key-Value Stores, Security (23)
Security & Cloud Computing (24)
Topic: Ensuring Data Reaches Disk
MIT - 6.006
Sequence and Set Interface
Data Structure for Dynamic Sequence Interface
Computation Complexity
Algorithms and Computation
Structure Of Computation
Graph & Search
Tree & Search
Weighted Shortest Paths
String Matching, Karp-Rabin
Priority Queue Interface & Implementation
Dictionary Problem & Implementation
Sorting
Dynamic Programming
Backtracking
Self-Balancing Tree
MIT - 6.824
2PC & 3PC
Introduction and MapReduce
RPC and Threads
Primary/Backup Replication
Lab: Primary/Backup Key/Value Service
Google File System (GFS)
Raft
Lab: Raft - Leader Election
Lab: Raft - Log Replication
Stanford-CS107
原始数据类型及相互转化
指鹿为马
泛型函数
泛型栈
运行时内存结构
从 C 到汇编
函数的活动记录
C 与 C++ 代码生成
编译的预处理过程
编译的链接过程
函数的活动记录续、并发
从顺序到并发和并行
信号量与多线程 1
信号量与多线程 2
复杂多线程问题
函数式编程 - Scheme 1
函数式编程 - Scheme 2
函数式编程 - Scheme 3
函数式编程 - Scheme 4
函数式编程 - Scheme 5
Python 基础
MIT - 6.001 - SICP
什么是程序
程序抽象
替代模型
时间/空间复杂度
数据抽象
高阶函数
Symbol
数据驱动编程与防御式编程
数据抽象中的效率与可读性
数据修改
环境模型
面向对象-消息传递
面向对象 - Scheme 实现
构建 Scheme 解释器
Eval-Apply Loop
Normal Order (Lazy) Evaluation
通用机
寄存器机器
子程序、栈与递归
在寄存器机器中执行
内存管理
MIT - 6.046
Randomized Algorithms
Skip Lists
System Design
Twitter
Cache Consistency & Coherence
DDIA 笔记
Replication
Transactions
The Trouble with Distributed Systems
Consistency & Consensus
Papers We Love
Consistent Hashing and Random Trees (1997)
Dynamic Hash Tables (1988)
LFU Implementation With O(1) Complexity (2010)
Time, Clocks, and the Ordering of Events in a Distributed System (1978)
Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
Release It 笔记
Anti-patterns & Patterns in Microservice Architecture
Database Design
Log Structured Merge (LSM) Tree & Usages in KV Stores
Prometheus
Powered By
GitBook
Resource Contention & Deadlock
简介
Resources
计算机为 Processes/Threads 提供执行所需的各种资源,包括 CPU time、disk space、memory、socket 等资源。从 OS 控制角度上看,它们可以分为:
Preemptable:可以被 OS 随时剥夺,如 CPU time
Non-preemptable:只能由 Process/Thread 主动释放的资源,如 disk space、virtual address space 以及 mutex 等
从资源共享角度上看,它们可以分为:
Exclusive Access:如打印机
Sharable:如 read-only files
因此 OS 的重要职责之一,就是管理好这些资源。
Starvation vs. Deadlock
Starvation 指的是 process/thread 一直无法获得 CPU 资源;Deadlock 指的是多个 processes/threads 之间形成了资源等待环,如下图所示:
Thread A 占有 Res1,等待 Res2 被释放
Thread B 占有 Res2,等待 Res1 被释放
Deadlock 会导致多个 threads 出现 Starvation,但反之不亦然,因为 Starvation 有可能结束,而 Deadlock 无法在没有外部干预的前提下自动解决。
Deadlock
Conditions for Deadlock
先观察 4 个 Deadlock 的案例
Example1: Thread A & B
可以观察到:
Deadlock 的出现与否并不确定,在特定情况下才会出现。
Deadlock 出现的场景存在多个独占资源
Example2: Bridge Crossing Example
在本例中,每段路都可以被看作是独占资源,每辆车在进入每段路之前,都必须获取它的使用权。当经过只有一个车道的桥时,两边的车必须同时获取桥左右两段道路的使用权,若两辆车分别获取左段和右段的使用权,则会出现 Deadlock。通常的解决方式时一辆车后退到桥外,让另一辆车先通过,或者上桥之前有交警协助管理,一次只能通过一个方向的车。此外,如果总是只让一个方向的车先通过,则会出现 Starvation。
Example3: Train Example
如图所示,当每辆火车都想向右转时,就可能出现 Deadlock。A 等待 B 离开当前铁轨,B 等待 C 离开当前铁轨,C 等待 D 离开当前铁轨,D 等待 A 离开当前铁轨,四者的需求形成等待环。
Example4: Dining Lawyers Problem
即哲学家就餐问题,有 5 名哲学家围坐在饭桌上,每个人餐盘左边和右边分别有 1 根筷子,每名哲学家需要拿到左右两边的筷子后,才能够吃饭。如果 5 名哲学家都拿起了左边的筷子,等待右边的筷子,就会出现 Deadlock。解决的思路有两种:
在 Deadlock 出现后解决
在 Deadlock 出现前预防
Four Requirements for Deadlock
以上的例子展现出 Deadlock 出现的 4 个先决条件:
Mutual Exclusion:资源独占
Hold and Wait:每个 thread 持有某个资源,同时等待其它资源被释放
No Preemption:资源只能被 thread 主动释放,无法直接剥夺
Circular Wait:存在等待环
Resource Allocation Graph
System Model
每个系统由一组 threads、resources 以及它们之间的关系构成:
A set of Threads:
T
1
T_1
T
1
、
T
2
T_2
T
2
、...、
T
n
T_n
T
n
Resource types:
R
1
R_1
R
1
、
R
2
R_2
R
2
、...、
R
m
R_m
R
m
每个 resource type
R
i
R_i
R
i
有
W
i
W_i
W
i
个实例
每个 thread 与 resource 实例的关系可能有 Request、Use、Release
Resource-Allocation Graph
Graph 由节点 V 与边 E 构成:
V 分成两种类型:T 和 R
E 也可以分成两种:
Request Edge:
T
1
→
R
j
T_1 \rightarrow R_j
T
1
→
R
j
Assignment Edge:
R
j
→
T
i
R_j \rightarrow T_i
R
j
→
T
i
Graph Examples
Deal With Deadlock
Deadlock Detection Algorithm
当每种资源只有一个实例时,直接检查 Resource-Allocation Graph 中是否有环存在即可;当每种资源有多个实例时,则可以通过模拟的方式来实现:
[
Avail
]
=
[
FreeResource
]
Add all nodes to UNFINISHED
do
{
done
=
true
Foreach node in UNFINISHED
{
if
([
Request_node
]
<=
[
Avail
])
{
remove node from UNIFINISHED
[
Avail
]
=
[
Avail
]
+
[
Alloc_node
]
done
=
false
}
}
}
until
(
done
)
当检测到 Deadlock 存在时:
终止 thread,强迫它放弃资源,如
Bridge:上帝从桥上选中一辆车丢到河中即可
Dining Lawyer:枪毙一个律师
但这种做法并不通用,直接杀死 thread 可能导致系统处于不一致的状态
剥夺 thread 占有的资源,但这有时候不符合语义
回滚 thread 的操作
...
Techniques for Preventing Deadlock
无限资源
无共享资源
不允许等待,直接拒绝,thread 只能重试
让所有 threads 一次性把需要的资源都获取
让所有 threads 按统一的顺序获取资源
Banker's Algorithm for Preventing Deadlock
核心思想:thread 启动前声明最大的资源需求量,若当前资源允许,则允许 thread 继续运行,保证整个系统永远处于安全状态。
小结
由于计算机拥有的资源有限,我们不得不通过虚拟化技术来让不同的 processes/threads 共享、复用资源,这也是 OS 要解决的核心问题:
Multiplex CPU:Scheduling, Fix/Prevent Deadlock
Multiplex Memory:Address Translation
Multiplex Disk and Devices:File System, ...
明确每个话题存在的意义,能帮助我们更好地构建操作系统知识体系。
参考
slides
UCB - CS162 - Previous
Scheduling
Next - UCB - CS162
Address Translation, Caching
Last modified
3yr ago
Copy link
Outline
简介
Resources
Starvation vs. Deadlock
Deadlock
Conditions for Deadlock
Resource Allocation Graph
Deal With Deadlock
小结
参考