Transcript Chapter 7 Deadlocks

Chapter 7
Deadlocks
Deadlock
• A state of indefinite waiting of a process
• May occur when processes are competing for
resources or when attempting to interact with
one another.
• Processes that are executing concurrently in a
multiprogramming environment may often
reach a state of starvation or deadlock.
• Resources are not shared
2
Deadlock will occur when, four condition’s below becomes
true.
Mutual exclusion - Each resource is either currently
allocated to exactly one process or it is available. (Two
processes cannot simultaneously control the same resource or be in their
critical section).
Hold and Wait - processes currently holding resources can
request new resources.
No preemption - Once a
process holds a resource, it
cannot be taken away by
another process or the kernel.
Circular wait - Each process is
waiting to obtain a resource
which is held by another
process.
Resource Allocation and Deadlock
• System consists of resources
• Resource types R1, R2, . . ., Rm
CPU cycles, memory space, I/O devices
• Each process utilizes a resource as follows:
1. Request a number of resource instances. If the
resources requested are not available, then
process must wait
2. Acquire resource(s), the OS allocates resources
3. Use the resource(s) for a finite interval.
4. Release the resource(s).
4
Resource Allocation Graph with a Cycle
Two types of nodes
represent a set of processes
and resources
P = {P1, P2, …, Pn}, the
set consisting of all the
processes in the system
R = {R1, R2, …, Rm}, the
set consisting of all
resource types in the
system
Suspended
Processes that are either
requesting or acquiring
resources
Suspended
Two types of edges
request edge – directed edge
From Pi  to Rj
assignment edge – directed
edge From Rj to  Pi
5
Suspended
Deadlock Problem
• A set of blocked (suspended) processes
• Each process holding one or more resources
• Processes waiting to acquire one or more
resources held by other processes
6
Multiple Resource Allocation
Problem
• Several processes may compete for multiple
resources
• If the allocation of multiple resources to
processes is not done with proper
synchronization, deadlock might occur
• This waiting state is much more involved than
starvation
7
Deadlock – General Definition
• A set of processes is in a deadlock state when
every processes in the set is waiting for an
event that can only be caused by another
process in the set.
• The events of interest are:
– allocations of resources
– release of resources
• The resources are: CPU cycles, memory spaces,
files, I/O devices in the computer system.
8
Disadvantage Of Deadlock
• Deadlocked processes can never complete
execution because they are waiting indefinitely
• System resources are tied up because they are
held by deadlocked processes.
• Deadlocks are undesirable because they
normally slow down a system
9
Directed Edges
• A request edge (Pi, Rj) from process Pi to
resource Rj. Thus, Pi is waiting for an instance of
resource type Rj.
• An assignment edge (Rj, Pi) from resource Rj to
process Pi. It indicates that an instance of Rj has
been allocated to process Pi.
10
A Resource Allocation Graph
These conditions are necessary but not sufficient
for deadlock to occur. His means that even if the
four conditions are present, deadlock may not
actually occur. The present of process conditions
implies that there is potential for deadlock.
P1 is waiting request
from R2
P1 has acquired an instance
of resource type R1;
So P1 holds a unit of
resources R1.
11
P2 is waiting request
from R3
P2 has acquired an instance
of resource type R2;
So P1 holds a unit of
resources R1.
Another Resource Allocation Graph
• P3 requesting resource R1 and there are two instances of
resources R1 and assume one instance is immediately allocated
to P3, since the system has two instances of resources R1.
• Now, P2 is also requesting an instance of resources R1, and P2
must wait for availability of resource R1.
• The following cycle can be identified in the graph that there is
no deadlock.
12
Solution to Deadlock
There are several ways to address the problem of
deadlock in an operating system. (Just ignore it and hope it
doesn't happen)
• Detection and recovery - if it happens, take action
• Dynamic avoidance by careful resource allocation.
• Check to see if a resource can be granted, and if
granting it will cause deadlock, don't grant it.
• Prevention - change the rules
Dining Philosophers
• Illustrates processes that are competing for exclusive
access to more than one resource, such as tape drives
or I/O devices.
• A monastery’s dining table
– Circular table
– Five plates
– Five forks (critical)
– Plate of noodles at center of table (endless supply)
– Philosophers can only reach forks adjacent to their
plate (left and right forks)
14
Life of a Philosopher
1.
2.
3.
4.
5.
6.
7.
8.
15
Spends some time thinking
Gets hungry
Sits at the table
Attempts to get the left fork
Attempts to get the right fork
Starts eating, this activity takes a finite time
Releases the left and right forks
Returns to the initial state (thinking)
Dining philosopher: example of
Deadlock problem
When all philosopher are hungry, they will sit down at
the same time.
1. At this point every
philosopher will pick up
the fork on the left side
and reach out for the fork
on the right, which not
available.
2. The four condition for
deadlock are now met
and deadlock occurs.
16
Dining Table
Two basic activates carried out by every philosopher:
Thinking and eating.
3. When a philosopher wants to eat,
he/she attempts to pick up the two
forks that are on either side of him/her
and starts to eat.
1. After eating, the philosopher puts
down (releases) the two forks and
rerun to thinking.
1. The resources are Forks that is
necessary for eating and only
resources in the unit.
2. The other units are not
relevance (Plates, table, chairs,
center bowl of food, etc.)
17
Why Synchronize?
• When a philosopher is hungry
–obtains 2 forks (1 at a time)
–Proceeds to eat
• When a philosopher has satisfied hunger
returns both forks and goes back to think
• Problem: There are 5 competing philosopher
processes
• Using semaphores as before, is not sufficient for
solving the problem
18
Dining Philosophers 1st Attempt
• Suppose all philosophers want to eat at the
same time
• Each one will pick up the left fork first then block
trying to pickup the right fork
• All processes will now block indefinitely deadlock
19
Dining Philosophers 2nd Attempt
• After taking the left fork, if the right fork is not
available, philosopher puts back the left fork and waits
for a while.
• Problem: Suppose all philosophers want to eat at the
same time:
– Each will pick up the left fork first and then try to pick up the
right fork.
– The right fork is not available, so all philosophers put back left
forks and wait.
– After some time, philosophers pick up the left fork and try
again - the cycle repeats.
20
Dining Philosophers 3rd Attempt
• Use a mutex semaphore to make eating mutually
exclusive.
• A philosopher is guaranteed to get both forks in this
case.
• Problem: Only one philosopher can be eating at any
given time.
21
4th Attempt to a Solution
• A philosopher’s neighbors are defined by macros
LEFT & RIGHT.
• A philosopher may move only into eating state if
neither neighbor is eating.
• Use an array, state, to keep track of whether a
philosopher is eating, thinking or hungry (trying
to acquire forks).
• Use an array of semaphores, one per philosopher,
so hungry philosophers can block if the needed
forks are busy.
22
Informal Solution to Deadlock
Dinning Philosophers
• Deadlock will not occur when the Philosophers
do not sit at the table at the same time,
therefore, if the Philosophers start thinking
before eating deadlock will not always occur.
• Because time interval to think is randomly
generated so that the Philosophers will not
normally start to eat at the same time and
deadlock will not always occur.
23
Methods For Dealing With
Deadlocks
• Deadlock prevention:
– disallow the existence of one of the four
necessary conditions for deadlocks to occur.
• Deadlock avoidance:
– for each resources request which can be satisfied,
determine whether the request should be delayed
in order to avoid a possible deadlock in the future.
• Deadlock detection and recovery:
– detect the existence of deadlock; if it has
occurred, take actions to remove it.
24
Deadlock avoidance
• When detected a deadlock had occurred and
tried to fix the problem after the fact.
• Another solution is to avoid deadlock by only
granting resources if granting them cannot
result in a deadlock situation later.
• The text describes the bankers algorithm but
then points out that it is essentially impossible
to implement because of this assumption.
25
Deadlock Prevention (1)
Non-existence of hold and wait.
• Allocation only if all resources requested are
available
• Allocation of resources only when there is no
previous allocation.
• Low resource utilization
• Starvation possible
26
Deadlock Prevention (2)
• Non-existence of circular wait.
Impose a linear ordering of resource types.
Processes must request resources in an
increasing order of enumeration.
27
Disallow Circular Wait
• Impose a total ordering of all resource types, R =
{R1, R2, …, Rm}.
• Define a one to one function, F: R  N
• Require that each process requests resources in an
increasing order of enumeration.
• Process P can request resources of type Ri, then
resources of type Rj, only if:
F( Rj) > F( Ri)
28
General Cycle
• A technique for disallowing
(Preventing) the circular wait
condition is to assign a total
ordering to al the resource
types in the system.
• Each resource type can be
assigned a unique integer
number, or an index
number.
29
Dining Philosophers
• Each Philosopher object will repeatedly execute
its sequence of activities until the simulation
period ends. The following sequence will be
carried out by a Philosophers:
1. Check if the index value of the left fork is less then
the index value of the right fork, then carry out the
Step 2, other wise, carry out the Step 3, then Step 2.
2. Attempt to acquire the left fork
3. Attempt to acquire the right fork
4. Each for a time interval of eatPeriod time units.
5. Think or a time interval of thinklPeriod time
units.
30
Dining-Philosophers Problem
Every philosopher needs two forks (or forks)
and these must be accessed in a mutual
exclusive manner
// Shared data
Semaphore fork[] = new Semaphore[5];
31
Output Listing of a Simulation Run
Project: Dining Philosophers - Deadlock
Run at: Sat Oct 01 17:15:39 EDT 2006 by jgarrido on Windows XP
----------------------------------------------------Input Parameters
Simulation Period: 740
Activity Stop: 400
Mean Think Time: 17.5
Mean Eat Time: 12.75
Project: Dining Philosophers - Deadlock
Run at: Sat Oct 01 17:15:40 EDT 2005
Start Simulation
Time 0000.000 Philosopher0 starts
Time 0000.000 Philosopher1 starts
Time 0000.000 Philosopher2 starts
Time 0000.000 Philosopher3 starts
Time 0000.000 Philosopher4 starts
32
Informal definition of Safe State
• Banker’s algorithm
• A state is safe if the system can allocate
resources to each process (up to its
maximum) in some order and still avoid a
deadlock
• A system is in a safe state only if there exits a
safe sequence of allocations
33
Unsafe State
• If a system is in an unsafe state, then some
sequence of requests may lead “unavoidably” to
a deadlock (i.e., the deadlock cannot be avoided
by delaying the requests from the processes).
• An unsafe state is not necessarily a deadlock state
and does not necessarily lead to deadlock state.
34
Banker’s Algorithm
• There exist multiple instances of each resource
type
• Each process must a priori claim maximum use of
resources
• When a process requests a resource, it may have
to wait
• When a process gets all its resources, it must
return them in a finite period of time.
35
Banker’s Algorithm (2)
When a request for resources is made by process Pi:
• If Requesti < Needi then goto step 2. Otherwise there is an error since Pi has
exceeded it maximum claim
• If Requesti < available then goto step3, otherwise Pi must wait
• The OS pretends to have allocated the requested resources to Pi by modifying
the state as follows:
AVAILABLE := AVAILABLE - Request
Allocationi := Allocationi + Request ti
Need = Need – Request
• If the resulting state is safe, Pi is allocated the resources. However, if the new
state is unsafe, then Pi must wait and the state is restored
36
Example of Banker’s Algorithm
5 processes P0 through P4; 3 resource types
A (10 instances), B (5 instances), and C (7 instances)
Snapshot at time T0:
P0
P1
P2
P3
P4
Allocation
ABC
010
200
302
211
002
Max
ABC
753
322
902
222
433
Available
ABC
332
Need
ABC
743
122
600
011
431
Example (Cont.)
• The content of the matrix Need is
defined to be Max – Allocation
P0
P1
P2
P3
P4
Need
ABC
743
122
600
011
431
Safe Sequence
< P1, P3, P4, P0, P2 >
Available
3 3 2
P0
can not be completed since is greater than available time
P1 [1] Allocated
P2
P1(2+0+0)+(3+3+2)=5 3 2
can not be completed since is greater than available time
P3 [3] Allocated
P1(2+1+1)+(5+3+2)=7 4 3
P4 [4] Allocated
P1(0+0+2)+(7+4+3)=7 4 5
P0 [0] Allocated
P1(0+1+0)+(7+4+5)=7 5 5
P2 [2] Allocated
P1(3+0+2)+(7+5+5)=10 5 7
https://www.youtube.com/watch?v=5WMxEnWNmho
Example: P1 Request (1,0,2)
• Check that Request  Available (that is, (1,0,2)  (3,3,2)  true
Allocation Need Available
ABC
ABC ABC
P0
010
743
230
P1
302
020
P2
302
600
P3
211
011
P4
002
431
• Executing safety algorithm shows that sequence
< P1, P3, P4, P0, P2> satisfies safety requirement
• Can request for (3,3,0) by P4 be granted?
• Can request for (0,2,0) by P0 be granted?
Example-4 of Banker’s Algorithm
Suppose P1 requests (1,0,2). The OS needs to
check if (1,0,2) < (3,3,2), which is true. The OS then
pretends to grant this request, and determine if the
new state is a safe state.
The sequence <P1, P3, P4, P0, P2> is a safe sequence.
Can request for (3,3,0) by P4 be granted?
Can request for (0,2,0) by P0 be granted?
40
Deadlock Detection
• Allow system to enter deadlock state
• Run detection algorithm
• Recovery Scheme
41
Detection and Recovery
A detection and recovery scheme
requires overhead that includes:
• Maintaining information and running the
detection algorithm
• The potential losses inherent in recovering
from deadlock
42
Deadlock Detection
A detection algorithm is invoked periodically to
determine whether a deadlock has occurred.
• A system has a deadlock if and only if it is
impossible to satisfy the resource requests of
some processes
• Formally, a system is in a deadlock-free state if
three exists a deadlock-free sequence for the
current resource allocation state.
43
System Recovery
•
•
•
•
44
Abort all deadlocked processes
Abort processes one at a time
Preempt resources one at a time
Rollback
Recovery: Process Termination
• Abort all deadlocked processes.
• Abort one process at a time until the deadlock cycle is
eliminated.
• In which order should processes be aborted?
– Priority of the process.
– How long process has computed, and how much longer to
completion.
– Resources the process has used.
– Resources process needs to complete.
– How many processes will need to be terminated.
– Is process interactive or batch?
45
Chapter 8
File
Management
Purpose of File Management
• The purpose of file management is to identify
the concepts of file management and how to
use it effectively.
• Data should be organized in some convenient
and efficient manner. In particular, users
should be able to:
– Put data into files
– Find and use files that have previously been
created
47
File System
• Set of OS Services that provides Files and
Directories for user applications.
• File management, as you have no doubt
guessed, involves a lot more than simply
moving files around from one place to another
on the computer and changing names.
• The operating system also automates other
complicated activities that are indispensable
to managing files and information on the
computer.
48
Files
• A file is simply a sequence of bytes that have been stored in
some device (storage) on the computer
While the procedures for managing files differ from operating
system to operating system, many of the concepts and
commands behind the procedures are the same. These
essential commands are examined below.
• Creating Files/Folders
• File naming
• Save As
• Copy, Paste, etc.
• Searching
• Viewing Options
49
Permanent (non-volatile) Storage
Devices
•
•
•
•
50
Disk Drives
Flash Memory (Memory stick)
CDs and DVDs
Magnetic tape drives
File Attributes
•
•
•
•
•
•
•
Name - Symbolic (Human-readable) name of the file
Type - Executable file, print file, etc.
Location - Where file is on disk
Size – How much stored in the file?
Protection - Who can read, write file, etc.
Time, date - When file was created, modified, accessed
Permission – Who is allowed to use this file?
51
Folders
• An important attribute of folders is the Name
• Typically, a folder may contain Files and other
Folders (commonly called sub-folders or subdirectories)
• This results in a Tree Structure of Folder and
Files.
52
Folder/Directory Tree Structure
The pathname of a file
specifies the sequence
of folders users must
traverse to travel down
the tree to the file.
The pathname for file
B2 is abc/def/B2
(absolute path of the file).
53
Pathnames
• This pathname actually describes the
absolute path of the file, which is the sequence
of folders one must travel from the root of the
tree to the desired file.
• A relative path describes the sequence of
Folders one must traverse starting at some
intermediate place on the absolute path.
• The Absolute path provides a unique
identification for a file. Two different files can
have the same filename as long as the resulting
pathnames are unique.
54
Link in Directory Tree Structure
In modern OS, there are
mechanism that allow a file
to appear to be in different
part of the tree structure
than where it actually
resides. This called a
Shortcut on Windows and
a Symbolic Link on
55
Unix/Linux.
Access Methods
• An access method describes the manner and
mechanisms by which a process accesses the
data in a file.
• There are two common access methods:
– Sequential
– Random (or Direct)
56
File Operations
When a process needs to use a file, there are a
number of operations it can perform:
• Open – This allows the OS to carry out the directory traversal only
once at the time that the file is opened.
• Close – When an application is done using a file, it should close it.
• Read – allows to read some data from specific file into the
memory space of the process.
• Write – is opposite of a read operation, it write some of data to a
file from the memory space of the process.
57
File Open
The open request will cache the directory entry in
main memory so that the OS can quickly access
that data anytime it is needed in the future.
The open request will return a file handle.
58
Close File
• Makes file no longer accessible from application
– Deletes the Handle created by Open
59
Sequential Access
• If the process has opened a file for sequential
access, the File Management subsystem will
keep track of the current file position for
reading and writing.
• To carry this out, the system will maintain a
file pointer that will be the position of the
next read or write.
60
File Pointer
The value of the file pointer will be initialized during
Open to one of two possible values
– Normally, this value will be set to 0 to start the reading or
writing at the beginning of the file.
– If the file is being opened to append data to the file, the File
Position pointer will be set to the current size of the file.
– After each read or write, the File Position Pointer will be
incremented by the amount of data that was read or written.
61
Stream
• A Stream is the flow of data bytes, one byte
after another, into the process (for reading) and
out of the process (for writing).
• This concept applies to Sequential Access and
was originally invented for network I/O, but
several modern programming environments
(e.g. Java, C#) have also incorporated it.
62
I/O Redirection
• Standard Input can come from a file
– app.exe < def.txt
• Standard Output can go to a file
– App.exe > def.txt
• Standard Output from one application can be
Standard Input for another
– App1.exe | app2.exe
Called a Pipe
63
Pipe
• A Pipe is a connection that is dynamically
established between two processes.
• When a process reads data, the data will come from
another process rather than a file. Thus, a pipe has a
process at one end that is writing to the pipe and
another process reading data at the other end of the
pipe.
• It is often the situation that one process will produce
output that another process needs for input.
• Rather than having the first process write to a file and
the second process read that file, we can save time by
having each process communicate via a pipe.
64
Directory Functions
•
•
•
•
•
•
65
Search for a file
Create a file
Delete a file
List a directory
Rename a file
Traverse the file system
Contiguous Allocation
When an application wishes to read or write data,
the file management system much determine where
the data actually is on the disk. Figure below shows
the address calculation with contiguous allocation.
Read/Write Disk Address Calculation
66
Windows FAT Tables
• FAT16 (File Allocation Table)
– MS-Dos, Windows 95
– Max 2GB space for a FileSystem
– Generally bad disk fragmentation
• FAT32
– Windows 98
– Supported by Windows 2000, XP, 2003
– FAT32 provides the following enhancements over previous
implementations of the FAT file system: FAT32 supports
drives up to 2 terabytes in size.
– Microsoft Windows 2000 only supports FAT32 partitions up
to a size of 32 GB.
http://support2.microsoft.com/kb/154997
67
Windows FAT Table
68
Windows NTFS File System
The Microsoft New Technology File System
(NTFS) was created as part of the Windows NT
development effort to create a reliable system that
could be used as server by businesses. Windows
NT, 2000, XP, 2003 Server and etc.
69
Unix File System
70
Windows FAT Table
FAT
Directory
Entry
Cluster 1
Free
Cluster
Cluster 2
Free List
Cluster 3
Free
Cluster
71
Virtual File System
On any given computer, there will likely be multiple
file system. There will also, be multiple device types
and possibly multiple disk partitions, each with a
different file system.
72
Windows: Map Network Drive
73