Transcript Unit 3

Operating Systems
Operating Systems
Unit 3:
– Concurrent execution
• mutual exclusion
– Concurrent programming
• semaphore
• monitor
Concurrent execution
• System has more than one
thread/process
• either independent or in cooperation:
– mostly independent
– occasionally need to communicate or
synchronize
COP 5994 - Operating Systems
2
Communication/synchronizati
on
• Threads may access resource
simultaneously
– resource can be put in inconsistent state
• Context switch can occur at anytime, such as
before a thread finishes modifying value
• Solution: mutual exclusion
– idea: serialized access
– Only one thread allowed access at one time
– Others must wait until resource is available
• Must be managed such that wait time not
unreasonable
COP 5994 - Operating Systems
3
Critical section
• a Section of code
– where shared resource is modified
– only one thread can be in its critical section
– avoid infinite loops and blocking inside
• Provides mutual exclusion
• Rest of code is safe to run concurrently
COP 5994 - Operating Systems
4
Mutual Exclusion properties


Mutual Exclusion
If process is executing in its critical section, then no
other processes can be executing in their critical
sections
Progress
If no process is executing in its critical section and there
exist some processes that wish to enter their critical
section, then the selection of the processes that will
enter the critical section next cannot be postponed
indefinitely



Assume that each process executes at a nonzero speed
No assumption concerning relative speed of the n processes
Bounded Waiting
A limit must exist on the number of times that other
processes are allowed to enter their critical sections
after a process has made a request to enter its critical
section
COP 5994 - Operating Systems
5
Mutual exclusion algorithm
• General structure of process Pi (vs. Pj)
do {
entry protocol
critical section
exit protocol
remainder section
} while (true);
COP 5994 - Operating Systems
6
Dekker’s Algorithm
• Idea: processes share common
variables to synchronize their actions:
int turn;
– denotes which process is favored to enter
its critical section
boolean flag[2];
– denotes whether process is ready to enter
its critical section
COP 5994 - Operating Systems
7
Dekker’s Algorithm: Process
Pi
do {
flag[i] = true;
while (flag[j]) {
if (turn == j) {
flag[i] = false;
while ( turn == j ) ;
flag[i] = true;
}
}
critical section
turn = j;
flag[i] = false;
remainder section
} while(true);
COP 5994 - Operating Systems
8
Dekker’s Algorithm
• Guarantees mutual exclusion for 2
processes
• Uses notion of favored thread to resolve
conflict over which thread should execute
first
• Each thread temporarily yields to other
thread
• Favored status alternates between
threads
COP 5994 - Operating Systems
9
Peterson’s Algorithm
• Less complicated than Dekker’s
Algorithm
– Still uses busy waiting, favored threads
– Requires fewer steps to perform mutual
exclusion primitives
– Easier to demonstrate its correctness
COP 5994 - Operating Systems
10
Peterson’s Algorithm: Process
Pi
do {
flag[i] = true;
turn = j;
while (flag[j] and turn == j)
;
critical section
flag[i] = false;
remainder section
} while (true);
COP 5994 - Operating Systems
11
Lamport’s Bakery Algorithm
• N-Thread Mutual Exclusion
– Creates a queue of waiting threads by
distributing numbered “tickets”
– Each thread executes when its ticket’s
number is the lowest of all threads
– Unlike Dekker’s and Peterson’s Algorithms,
the Bakery Algorithm works in
multiprocessor systems and for n threads
– Relatively simple to understand due to its
real-world analog
COP 5994 - Operating Systems
12
Bakery Algorithm
Critical section for n processes:
• Before entering its critical section
process receives a number
• Holder of the smallest number enters critical
section
• If processes Pi and Pj receive the same
number,
process with lower process id is served first
• The numbering scheme always generates
numbers in increasing order of enumeration;
i.e.,COP1,2,3,3,3,3,4,5...
5994 - Operating Systems
13
Bakery Algorithm
• Shared data
boolean choosing[n];
int number[n];
Data structures are initialized to false and 0
respectively
COP 5994 - Operating Systems
14
Bakery Algorithm
do {
choosing[i] = true;
number[i] = max(number[0], number[1], …, number [n –
1])+1;
choosing[i] = false;
for (j = 0; j < n; j++) {
while (choosing[j]) ;
while ((number[j] != 0) && (number[j],j) <
number[i],i)) ;
}
critical section
number[i] = 0;
remainder section
} while (true);
COP 5994 - Operating Systems
15
Mutual Exclusion via Hardware
• Disabling interrupts
• Special instructions
– test and set
– swap
COP 5994 - Operating Systems
16
Disabling Interrupts
• mask interrupts while in critical section
– current thread cannot be preempted
• could result in deadlock
– e.g.: thread does I/O block in critical section
• works only on uniprocessor systems
• used rarely
COP 5994 - Operating Systems
17
Test-and-Set Instruction
boolean testAndSet(var)
• returns the value of var and sets var to
true
• atomic instruction
• simplifies mutual exclusion algorithm
• algorithm must use instruction correctly
COP 5994 - Operating Systems
18
Mutual exclusion algorithm
do {
while (testAndSet(lock)) ;
critical section
lock = false;
remainder section
} while (true);
COP 5994 - Operating Systems
19
Swap Instruction
swap(a, b)
• exchanges the values of a and b
atomically
• Similar in functionality to test-and-set
– more common
COP 5994 - Operating Systems
20
Mutual exclusion algorithm
do {
myTurn = true;
do {
swap(lock, myTurn);
} while (myTurn) ;
critical section
lock = false;
remainder section
} while (true);
COP 5994 - Operating Systems
21
Semaphore
• Software construct to enforce mutual
exclusion
• Contains a protected variable:
– accessed via wait and signal commands
P
V
• binary semaphore: 0 or one
• counting semaphore
COP 5994 - Operating Systems
22
Binary Semaphores
• only one thread allowed in critical section
– Wait operation: P
• If no other thread in critical section:
– thread enters critical section
– Decrement protected variable (to 0 in this case)
• Otherwise place in waiting queue
– Signal operation: V
• Indicate that thread has left its critical section
• Increment protected variable (from 0 to 1)
• A waiting thread (if there is one) may now enter
COP 5994 - Operating Systems
23
Mutual exclusion algorithm
do {
P(lock) ;
critical section
V(lock);
remainder section
} while (true);
COP 5994 - Operating Systems
24
Synchronization with Semaphores
• Semaphores can be used to notify other
threads that events have occurred
– Producer-consumer relationship:
• Producer enters its critical section to produce
value
• Consumer is blocked until producer finishes
• Consumer enters its critical section to read value
• Producer cannot update value until it is
consumed
– Semaphores offer a clear, easy-toimplement solution to this problem
COP 5994 - Operating Systems
25
Counting Semaphores
• Initialized with values greater than one
• Can be used to control access to a pool
of identical resources
– Decrement the semaphore’s counter when
taking resource from pool
– Increment the semaphore’s counter when
returning it to pool
– If no resources are available, thread is
blocked until a resource becomes available
COP 5994 - Operating Systems
26
Implementing Semaphores
• Application level
– typically implemented by busy waiting
– inefficient
• Kernel implementations
• block waiting threads via locks
• disable interrupts via masks
– must avoid poor performance and deadlock
– hard to implement on multiprocessor
systems
COP 5994 - Operating Systems
27
Linux Synchronization Tools
• to protect kernel data structures:
– spin lock
• reader/writer lock
• seqlock
– kernel semaphore
• general thread synchronization
– System V Semaphores
COP 5994 - Operating Systems
28
Linux Kernel Spin Locks
• Protects critical sections on SMP
systems
– Once acquired, all subsequent requests to
the spin lock cause busy waiting (spinning)
until the lock is released
• Unnecessary in uniprocessor systems
– code removed for speed
COP 5994 - Operating Systems
29
Linux Kernel Reader/Writer Locks
• optimize concurrency for read/write of kernel
data
– Allow multiple kernel control paths to hold a read
lock, but permit only one kernel control path to hold
a write lock with no concurrent readers
– A kernel control path that holds a read lock on a
critical section must release its read lock and
acquire a write lock if it wishes to modify data
– An attempt to acquire a write lock succeeds only if
there are no other readers or writers concurrently
executing inside their critical sections.
COP 5994 - Operating Systems
30
Linux Kernel Seqlocks
• Seqlocks
– Allow writers to access data immediately
without waiting for readers to release the
lock
– Combines spinlock with a sequence counter
– Requires readers to detect if a writer has
modified the value of the data protected by
the seqlock by examining the value of the
seqlock’s sequence counter
– Appropriate for interrupt handling
COP 5994 - Operating Systems
31
Linux Kernel Semaphores
• Counting semaphores
– before entering critical section, must call function
down
• If the value of the counter is greater than 0, decrement the
counter, allow the process to execute.
• If the value of the counter is less than or equal to 0, down
decrements the counter, and the process is added to the
wait queue and enters the sleeping state.
– Reduces the overhead due to busy waiting
– when a process exits its critical section, must call
function up
• If the value of the counter is greater than or equal to 0,
increments counter
• If the value of the counter is less than 0, up increments the
counter, and a process from the wait queue is awakened to
execute its critical section
COP 5994 - Operating Systems
32
Linux System V Semaphores
• accessible via the system call interface
• Semaphore arrays
– Protect a group of related resources
– Before a process can access resources
protected by a semaphore array, the kernel
requires that there be sufficient available
resources to satisfy the process’s request
– Otherwise, kernel blocks requesting process
until resources become available
COP 5994 - Operating Systems
33
Windows XP Synchronization Tools
• Dispatcher objects
– states: signaled vs. unsignaled
– operation: wait
• specify maximum waiting time
– variations
• Event, Mutex, Semaphore, Waitable timer
COP 5994 - Operating Systems
34
Windows XP kernel synchronization
• Spin lock
• Queued spin lock
– Guarantees FIFO ordering of requests
• Fast mutex
– Like a mutex, but more efficient
– Cannot specify maximum wait time
– Reacquisition by owning thread causes deadlock
• Executive resource lock
– One lock holder in exclusive mode
– Many lock holders in shared mode
COP 5994 - Operating Systems
35
Windows XP: Other synchronization
tools
• Critical section object
– Like mutex, but only for threads of same
process
– Faster than mutex, no maximum wait time
• Timer-queue timer
– Waitable timer objects combined with thread
pool
• Interlocked variable access
– Atomic operations on variables
• Interlocked singly-linked lists
COP 5994 - Operating Systems
– Atomic
insertion and deletion
36
Monitor
• Programming language construct
– Contains data and procedures needed to
access shared resource
• resource accessible only within the monitor
• Supports:
– mutual exclusion
– synchronization
• Dijkstra, Brinch-Hansen, Hoare
COP 5994 - Operating Systems
37
Monitor: mutual exclusion
• Entry to monitor is controlled
• Resource access using monitor:
– thread must call monitor entry routine
– only one thread is allowed into monitor
– other threads must wait
COP 5994 - Operating Systems
38
Monitor: mutual exclusion
• Resource release using monitor:
– Monitor entry routine alerts one waiting
thread to acquire resource and enter monitor
– Higher priority given to waiting threads than
ones newly arrived
• Avoids indefinite postponement
COP 5994 - Operating Systems
39
Monitor: synchronization
• Special monitor variable: condition
variable
• every condition variable has associated
queue
• operations:
– wait(condVar)
thread is suspended
– signal(condVar)
suspended thread may resume
COP 5994 - Operating Systems
40
Monitor: condition variables
• Before a thread can reenter the monitor,
the thread calling signal must first exit
monitor
– Signal-and-exit monitor
• Requires thread to exit the monitor immediately
upon signaling
COP 5994 - Operating Systems
41
Monitor: condition variables
• Signal-and-continue monitor
– Allows thread inside monitor to signal that
the monitor will soon become available
– Still maintain lock on the monitor until thread
exits monitor
– Thread can exit monitor by waiting on a
condition variable or by completing
execution of code protected by monitor
COP 5994 - Operating Systems
42
Dining Philosophers Example
monitor dp {
enum {thinking, hungry, eating} state[5];
condition self[5];
void pickup(int i)
// following slides
void putdown(int i)
// following slides
void test(int i)
// following slides
void init() {
for (int i = 0; i < 5; i++)
state[i] = thinking;
}
}
COP 5994 - Operating Systems
43
Dining Philosophers
void pickup(int i) {
state[i] = hungry;
test(i);
if (state[i] != eating)
self[i].wait();
}
COP 5994 - Operating Systems
44
Dining Philosophers
void putdown(int i) {
state[i] = thinking;
// test left and right neighbors
test((i+4) % 5);
test((i+1) % 5);
}
COP 5994 - Operating Systems
45
Dining Philosophers
void test(int i) {
if ( (state[(i + 4) % 5] != eating) &&
(state[i] == hungry) &&
(state[(i + 1) % 5] != eating)) {
state[i] = eating;
self[i].signal();
}
}
COP 5994 - Operating Systems
46
Java Monitors
• enables thread mutual exclusion and
synchronization
• Signal-and-continue monitors
– Allow a thread to signal that the monitor will
soon become available
– Maintain a lock on monitor until thread exits
monitor
• method keyword synchronized
COP 5994 - Operating Systems
47
Java Monitors
• wait method
– releases lock on monitor,
thread is placed in wait set
– condition variable is “this” object
– when thread reenters monitor, reason for
waiting may not be met
• notify and notifyAll
– signal waiting thread(s)
COP 5994 - Operating Systems
48
Agenda for next week:
• Homework:
– implement Dining Philosophers with Java monitor
• Chapter 7
– Deadlock
• Chapter 8
– Processor scheduling
• Read ahead !
COP 5994 - Operating Systems
49