Transcript Introduction to Object Technology

Concurrency:
Mutual Exclusion, Synchronization,
Deadlock, and Starvation
in
Representative Operating Systems
1
Concurrency
•
•
•
•
•
Mutual exclusion
Semaphores
Monitors
Message passing
Deadlock
– Deadlock prevention
– Deadlock avoidance
– Deadlock detection
• Starvation
CS-550: Concurrency in Representative Operating Systems
2
UNIX Concurrency Mechanisms
• Mechanisms for interprocess communication and
synchronization:
–
–
–
–
–
Pipes
Messages
Shared memory
Semaphores
Signals
• Pipes, messages, and shared memory are used to
communicate between processes, semaphores
and signals to trigger actions by other processes
CS-550: Concurrency in Representative Operating Systems
3
UNIX Concurrency Mechanisms (cont.)
• Pipes
– Major contribution to the development of OSs
– Circular buffer allowing two processes to communicate using a producerconsumer model
– FIFO queue, written by one process and read by another
– Pipe created with fixed number of bytes
– Write
• If room available, executed immediately
• Else, process is blocked
– Read
• If requested number of bytes available, executed immediately
• Else, process blocked
– Mutual exclusion enforced by the OS: one process at a time can access pipe
– Pipe types:
• Named: shared by unrelated processes
• Unnamed: shared by related processes
CS-550: Concurrency in Representative Operating Systems
4
UNIX Concurrency Mechanisms (cont.)
• Messages
– Block of text with accompanying type
– Operation
• System calls: msgsnd and msgrcv
• Each process has message queue – mailbox
• Message sender specifies type of message
• Message receiver can retrieve messages by type or FIFO
– Synchronization
• Message sender suspended if tries to send to a full queue
• Message receiver suspended if tries to read from an empty
queue
• Message receiver not suspended if attempts to read a
message of certain type and no message present
CS-550: Concurrency in Representative Operating Systems
5
UNIX Concurrency Mechanisms (cont.)
• Shared memory
– Fastest method of interprocess communication in UNIX
– Common block of virtual memory shared by several processes
– Operation: same read/write operations as the rest of the virtual
memory
– Protection: per-process, read-only or read-write
– Synchronization must be provided by processes using shared
memory
CS-550: Concurrency in Representative Operating Systems
6
UNIX Concurrency Mechanisms (cont.)
• Semaphores
– Generalization of the semaphore concept
– Kernel implements semaphore operations atomically: no other
process can access the semaphore until all operations are done
– Semaphore elements
• Current value of semaphore
• Process ID of last process to operate on the semaphore
• Number of processes waiting for the semaphore value to be greater
than current value
• Number of processes waiting for the semaphore value to be zero
– Each semaphore has associated queues of processes waiting on
that semaphore
– Semaphores created in sets of one or more semaphores
CS-550: Concurrency in Representative Operating Systems
7
UNIX Concurrency Mechanisms (cont.)
• Signals
– Software mechanism to inform a process of the occurrence of
an asynchronous event
– A signal can be send process-to-process or internal to kernel
– Operation:
• Signal is delivered by updating a field in the process table of the
destination process
• Signal is processed after process wakes up to run or when it returns
from a system call
• Process responds to signal by performing a default action, executing a
signal handler function, or ignoring the signal
– Signals have no priorities and no queuing
• Signals that occur at the same time are given to process one at a time,
without implied ordering
• Signals of a given type cannot be queued: single bit for each type
CS-550: Concurrency in Representative Operating Systems
8
Solaris Thread Synchronization Primitives
• Solaris implements four thread synchronization primitives, in
addition to the concurrency mechanisms of UNIX SVR4 (in the
kernel for kernel threads and in the threads library for user-level
threads
–
–
–
–
Mutual exclusion (mutex) locks
Semaphores
Multiple readers, single writer (reader/writer) locks
Condition variables
• Operation
– Thread executes a primitive and creates a synchronization object (data
structure with requested parameters)
– Synchronization operations: enter (acquire, lock) and release (unlock)
– It is the thread’s responsibility to use synchronization primitives properly:
there is no mechanism in the kernel or the threads library to enforce mutual
exclusion or to prevent deadlock
– All synchronization primitives require a hardware instruction that can test
and set an object in one atomic operation
CS-550: Concurrency in Representative Operating Systems
9
Solaris Thread Synchronization Primitives
CS-550: Concurrency in Representative Operating Systems
10
Solaris Thread Synchronization Primitives
CS-550: Concurrency in Representative Operating Systems
11
Solaris Thread Synchronization Primitives (cont.)
•Mutual exclusion lock
–Principle: prevents more than one thread to proceed in a critical
section
–Primitives:
•mutex-enter(): Acquires the lock, potentially blocking
•Thread attempts to acquire a mutex lock
•If lock already set by another thread, blocking action depends on
type-specific information stored in the mutex object (spin lock or go
on queue of threads sleeping on this lock)
•Mutex-exit(): Releases the lock, potentially unblocking a waiter
•Mutex_tryenter(): Acquires the lock if it is not already held
•Programmer uses a busy-wait for user-level threads, which avoids
blocking the entire process because one thread is blocked
CS-550: Concurrency in Representative Operating Systems
12
Solaris Thread Synchronization Primitives (cont.)
•Semaphores
–Classic counting semaphores, with following primitives
•sema_p () Decrements semaphore, potentially blocking thread
•sema_v () Increments semaphore, potentially unblocking waiting thread
•Sema_tryp () Decrements semaphore if blocking not required (permits
busy waiting)
CS-550: Concurrency in Representative Operating Systems
13
Solaris Thread Synchronization Primitives (cont.)
•Readers/Writer Lock
–Operation
•Either multiple simultaneous read-only threads have access to the
protected object (status read lock), or
•Single write-only thread has access to object for writing, excluding all
readers (status write lock)
–Primitives
•rw_enter ()
Attempts to acquire lock as reader or writer
•rw_exit ()
Releases a lock as reader or writer
•rw_tryenter ()
Acquire the lock if blocking is not required
•rw_downgrade () An acquired write lock is converted to a read lock. If
waiting writer, it waits until lock is released. If no
waiting writer, pending readers are awaken
•rw_tryupgrade () Attempts to convert a reader lock into a writer lock
CS-550: Concurrency in Representative Operating Systems
14
Solaris Thread Synchronization Primitives (cont.)
• Condition variables
– Objective: implement a monitor using a condition variable and a mutex
lock
– The condition variable is used to wait until a particular condition is true
– Primitives
• cv_wait ( )
Blocks until the condition is signaled; must release associated
mutex before blocking and reacquire it before returning
• cv_signal ( )
Wakes up one of the threads blocked in cv_wait ( )
• cv_broadcast ( ) Wakes up all the threads blocked in cv_wait ( )
CS-550: Concurrency in Representative Operating Systems
15
Windows 2000 Concurrency Mechanisms
• Synchronization of threads is based on the object architecture
• The Executive implements synchronization using the
synchronization objects
– The following object types have specific uses, but can be used for
synchronization as well
•
•
•
•
Process
Thread
File
Console input
– The following object types are exclusively designed for synchronization
•
•
•
•
•
File change notification
Mutex
Semaphore
Event
Waitable timer
CS-550: Concurrency in Representative Operating Systems
16
Windows 2000 Concurrency Mechanisms (cont)
• Operation
– Each synchronization object instance can be in one of two
states: signaled or unsignaled
– When a thread issues a wait request to the Executive, it uses
the handle of the synchronization object
• If object is in unsignaled state, thread is suspended
• When object enters the signaled state, Executive releases the thread
(and all thread objects waiting on that synchronization object)
• Objects used exclusively for synchronization
– File change notification
• A notification of any file system changes
• Signaled when change occurs in the file system that matches filter
criteria of this object
• When signaled, one waiting thread is released
CS-550: Concurrency in Representative Operating Systems
17
Windows 2000 Concurrency Mechanisms (cont)
• Objects used exclusively for synchronization (cont.)
– Mutex
• Used to enforce mutually exclusive access to a resource, allowing only
one thread at a time to gain access (binary semaphore). Can be used to
synchronize threads running on different processes. Used for the Win32
and OS/2 environments.
• Signaled when owning thread or other thread releases mutex
• When signaled, only one waiting thread is released
– Semaphore
• Counter that regulates the number of threads that can use a resource
• Signaled when semaphore count drops to zero
• When signaled, all waiting threads are released.
CS-550: Concurrency in Representative Operating Systems
18
Windows 2000 Concurrency Mechanisms (cont)
• Objects used exclusively for synchronization (cont.)
– Event
• An announcement that a system event has occurred
• Signaled when thread sets event
• When signaled, all waiting threads are released
– Waiting Timer
• Counter that records the passage of time
• Signaled when set time arrives or time interval expires
• When signaled, all waiting threads are released
CS-550: Concurrency in Representative Operating Systems
19