Transcript Processes and Threads

Operating Systems Review
Processes, Threads, Race
Conditions & Deadlocks
1
What is a process?
A process is
1. a program in execution.
2. an abstraction of a running program.
3. a data structure that includes everything
needed to manage a running program.
2
What is a thread?
A thread is a lightweight process.
3
Process Hierarchies
A process may create sub-processes, called a
“child” process. The process that creates a child
process is called the “parent” process.
4
Process / Thread States
• Possible process states
– running
– blocked
– ready
• Transitions between states shown
5
Implementation of Processes (1)
Fields of a process table entry
6
Threads
The Thread Model (1)
(a) Three processes each with one thread
(b) One process with three threads
7
The Thread Model (2)
• Items shared by all threads in a process
• Items private to each thread
8
The Thread Model (3)
Each thread has its own stack
9
Thread Usage (1)
A word processor with three threads
10
Thread Usage (2)
A multithreaded Web server
11
Implementing Threads in User Space
A user-level threads package
12
Implementing Threads in the Kernel
A threads package managed by the kernel
13
Hybrid Implementations
Multiplexing user-level threads onto kernellevel threads
14
Interprocess Communication
Race Conditions
A Race Condition may occur when
Two or more processes want to access a shared resource at
same time and the result depends upon who runs when.
15
Two Atomic Functions (Semaphores)
down(s)
{ if (s > 0)
s--;
else
go to sleep;
}
up(s)
{ if (1 or more processes
waiting for s)
pick_one_and_wake_it_up;
else
s++;
}
These semaphore functions were proposed by E.W. Dijkstra in 1965.
Def’n: An atomic action is an action that is guaranteed to be indivisible –
that is, it cannot be interrupted until completed.
16
Monitors (1)
Example of a monitor
17
Monitors (2)
• Outline of producer-consumer problem with monitors
– only one monitor procedure active at one time
– buffer has N slots
18
Monitors (3)
Solution to producer-consumer problem in Java (part 1)
19
Monitors (4)
Static class our_monitor {
private int buffer[] = new int[N];
private int count = 0, lo = 0, hi = 0;
// this is a monitor
// counters and indices
public synchronized void insert(int val) {
if (count == N) go_to_sleep();
buffer[hi] = val;
hi = (hi + 1) % N;
count = count + 1;
if (count == 1) notify();
}
//
//
//
//
//
if the buffer is full, go to sleep
insert an item into the buffer
slot to place next item in
one more item in the buffer now
if consumer was sleeping, wake it up.
public synchronized int remove() {
int val;
if (count == 0) go_to_sleep();
val = buffer[lo];
lo = (lo + 1) % N;
count = count – 1;
if (count == N-1) notify();
return val;
}
//
//
//
//
//
if the buffer is empty, go to sleep
fetch an item from the buffer
slot to fetch next item from
one less item in the buffer
if producer was sleeping, wake it up.
private void go_to_sleep() {
try{wait();} catch(InterruptedExecption exc) {};
}
}
Solution to producer-consumer problem in Java (part 2)
20
Message Passing
The producer-consumer problem with N messages
21
Barriers
• Use of a barrier
– processes approaching a barrier
– all processes but one blocked at barrier
– last process arrives, all are let through
22
Introduction to Deadlocks
• Formal definition :
A set of processes is deadlocked if each process in the set is
waiting for an event that only another process in the set can cause
• Usually the event is release of a currently held resource
• None of the processes can …
– run
– release resources
– be awakened
23
Four Conditions for Deadlock
Mutual exclusion condition
1.
•
each resource assigned to 1 process or is available
Hold and wait condition
2.
•
process holding resources can request additional
No preemption condition
3.
•
previously granted resources cannot forcibly taken away
Circular wait condition
4.
•
•
must be a circular chain of 2 or more processes
each is waiting for resource held by next member of the
chain
Coffman, E.G., Elphick, M.J. and
Shoshani, A.
24
Deadlock Modeling (1)
• Modeled with directed graphs
– resource R assigned to process A
– process B is requesting/waiting for resource S
– process C and D are in deadlock over resources T and U
Holt, R.C.
25
Detection with One Resource of Each
Type
• Note the resource ownership and requests
• A cycle can be found within the graph, denoting
deadlock
26
Strategies for dealing with Deadlocks
just ignore the problem altogether
detection and recovery
dynamic avoidance
1.
2.
3.
careful resource allocation
•
4.
prevention
•
negating one of the four necessary conditions
27
The Ostrich Algorithm
• Pretend there is no problem
• Reasonable if
– deadlocks occur very rarely
– cost of prevention is high
• UNIX and Windows take this approach
• It is a trade off between
– convenience
– correctness
28
Recovery from Deadlock
• Recovery through killing processes
–
–
–
–
crudest but simplest way to break a deadlock
kill one of the processes in the deadlock cycle
the other processes get its resources
choose process that can be rerun from the beginning
29
30
Deadlock Prevention
Summary of approaches to deadlock prevention
31