OS Chapter 7
2015-11-01 13:31:34 0 举报AI智能生成
登录查看完整内容
为你推荐
查看更多
操作系统第七章主要探讨了进程和线程的管理。在计算机科学中，进程是正在执行的程序的实例，而线程则是进程中的一个独立执行路径。本章详细介绍了如何创建、调度和终止进程和线程，以及如何进行进程间通信。此外，还讨论了并发编程中的同步和互斥问题，包括死锁、饥饿和优先级反转等现象。为了解决这些问题，引入了各种同步原语，如信号量、互斥锁和条件变量。最后，本章还介绍了一些高级进程和线程管理技术，如线程池、协程和用户级线程。通过学习这一章，读者将掌握进程和线程的基本概念和管理方法，为进一步深入学习操作系统打下坚实的基础。
作者其他创作
大纲/内容
OS Chapter 7 Deadlocks
The Deadlock Problem
A set of blocked processes each holding a resource and waiting to acquire a resource held by another process in the set
Example\u00A0System has 2 disk drivesP1 and P2 each hold one disk drive and each needs another one
Bridge Crossing Example
System Model
Each resource type Ri has Wi instances
Each process utilizes a resource as follows:
request : the process requests the resource
use: the process can operate on the resource
release: the process releases the resource
Deadlock Characterization
Deadlock can arise if four conditions hold simultaneously.
Mutual exclusion: \u00A0only one process at a time can use a resource
Hold and wait: \u00A0a process holding at least one resource is waiting to acquire additional resources held by other processes
Resource-Allocation Graph
A set of vertices V and a set of edges E.
request edge – directed edge Pi - Rj
assignment edge – directed edge Rj - Pi
Basic Facts
If graph contains no cycles = no deadlock
Methods for Handling Deadlocks
Ensure that the system will never enter a deadlock state提供一个protocol
Allow the system to enter a deadlock state and then recover
Deadlock Prevention
Restrain the ways request can be made
Mutual Exclusion – not required for sharable resources; must hold for nonsharable resources
Deadlock Avoidance
Requires that the system has some additional a priori information available
Simplest and most useful model requires that each process declare the maximum number of resources of each type that it may need
The deadlock-avoidance algorithm dynamically examines the resource-allocation state to ensure that there can never be a circular-wait condition
Safe State
If a system is in safe state = no deadlocks
If a system is in unsafe state =\u00A0possibility of deadlock
Avoidance =\u00A0ensure that a system will never enter an unsafe state.
Avoidance algorithms
Single instance of a resource typeUse a resource-allocation graph
Multiple instances of a resource type\u00A0Use the banker’s algorithm
Resource-Allocation Graph Scheme
Claim edge Pi - Rj indicated that process Pj may request resource Rj; represented by a dashed line
Claim edge converts to request edge when a process requests a resource
Request edge converted to an assignment edge when the \u00A0resource is allocated to the process
Resources must be claimed a priori in the system
Resource-Allocation Graph Algorithm
Suppose that process Pi requests a resource Rj
The request can be granted only if converting the request edge to an assignment edge does not result in the formation of a cycle in the resource allocation graph
Banker’s Algorithm
Multiple instances\u000BEach process must a priori claim maximum use\u000BWhen a process requests a resource it may have to wait \u00A0\u000BWhen a process gets all its resources it must return them in a finite amount of time
Safety Algorithm
Resource-Request Algorithm for Process Pi
Example of Banker’s Algorithm
Deadlock Detection\u00A0
Allow system to enter deadlock state \u000BDetection algorithm\u000BRecovery scheme
Single Instance of Each Resource Type
Maintain wait-for graphNodes are processesPi - Pj \u00A0 if Pi is waiting for Pj
Several Instances of a Resource Type
Detection Algorithm
Work = Work + Allocationi\u000BFinish[i] = true \u00A0\u000B\u00A0 \u00A0\u00A0go to step 2
Algorithm requires an order of O(m x n2)operations to detect whether the system is in deadlocked state
Example of Detection Algorithm
P2 requests an additional instance of type C\u00A0 \u00A0 \u00A0Request\u00A0 \u00A0 \u00A0 \u00A0 A B C\t\t P0 \u00A0 \u00A00 0 0\t\t P1 \u00A0 \u00A02 0 2\t\t P2 \u00A0 \u00A00 0 1\t\t P3 \u00A0 \u00A01 0 0\u00A0\t\t P4 \u00A0 \u00A00 0 2
Recovery from Deadlock\u00A0
Recovery from Deadlock: \u00A0\u000BProcess Termination
Abort all deadlocked processes
Abort one process at a time until the deadlock cycle is eliminated
In which order should we choose to abort?
Recovery from Deadlock: \u000BResource Preemption
Selecting a victim – minimize cost 选择牺牲者
0 条评论
回复 删除
下一页
