1. The
Bounded-Buffer Problem
- This
is a generalization of the producer-consumer problem wherein access is
controlled to a shared group of buffers of a limited size.
- In
this solution, the two counting semaphores "full" and
"empty" keep track of the current number of full and empty
buffers respectively ( and initialized to 0 and N respectively. ) The
binary semaphore mutex controls access to the critical section. The
producer and consumer processes are nearly identical - One can think of
the producer as producing full buffers, and the consumer producing empty
buffers.
2. The
Readers-Writers Problem
- In
the readers-writers problem there are some processes ( termed readers )
who only read the shared data, and never change it, and there are other
processes ( termed writers ) who may change the data in addition to or
instead of reading it. There is no limit to how many readers can access
the data simultaneously, but when a writer accesses the data, it needs
exclusive access.
- There
are several variations to the readers-writers problem, most centered
around relative priorities of readers versus writers.
- The first readers-writers
problem gives priority to readers. In this problem, if a reader wants
access to the data, and there is not already a writer accessing it, then
access is granted to the reader. A solution to this problem can lead to
starvation of the writers, as there could always be more readers coming
along to access the data. ( A steady stream of readers will jump ahead of
waiting writers as long as there is currently already another reader
accessing the data, because the writer is forced to wait until the data
is idle, which may never happen if there are enough readers. )
- The second readers-writers
problem gives priority to the writers. In this problem, when a writer
wants access to the data it jumps to the head of the queue - All waiting
readers are blocked, and the writer gets access to the data as soon as it
becomes available. In this solution the readers may be starved by a
steady stream of writers.
- The
following code is an example of the first readers-writers problem, and
involves an important counter and two binary semaphores:
- readcount is used by
the reader processes, to count the number of readers currently accessing
the data.
- mutex is a semaphore
used only by the readers for controlled access to readcount.
- rw_mutex is a
semaphore used to block and release the writers. The first reader to
access the data will set this lock and the last reader to exit will
release it; The remaining readers do not touch rw_mutex. ( Eighth
edition called this variable wrt. )
Note
that the first reader to come along will block on rw_mutex if there
is currently a writer accessing the data, and that all following readers will
only block on mutex for their turn to increment readcount.
3. The
Dining-Philosophers Problem
- The
dining philosophers problem is a classic synchronization problem involving
the allocation of limited resources amongst a group of processes in a
deadlock-free and starvation-free manner:
- Consider five philosophers
sitting around a table, in which there are five chopsticks evenly
distributed and an endless bowl of rice in the center, as shown in the
diagram below. ( There is exactly one chopstick between each pair of
dining philosophers. )
- These philosophers spend
their lives alternating between two activities: eating and thinking.
- When it is time for a
philosopher to eat, it must first acquire two chopsticks - one from their
left and one from their right.
- When a philosopher thinks,
it puts down both chopsticks in their original locations.
- One
possible solution, as shown in the following code section, is to use a set
of five semaphores ( chopsticks[ 5 ] ), and to have each hungry
philosopher first wait on their left chopstick ( chopsticks[ i ] ), and
then wait on their right chopstick ( chopsticks[ ( i + 1 ) % 5 ] )
- But
suppose that all five philosophers get hungry at the same time, and each
starts by picking up their left chopstick. They then look for their right
chopstick, but because it is unavailable, they wait for it, forever, and
eventually all the philosophers starve due to the resulting deadlock.
Some
potential solutions to the problem include:
- Only
allow four philosophers to dine at the same time. ( Limited simultaneous
processes. )
- Allow
philosophers to pick up chopsticks only when both are available, in a
critical section. ( All or nothing allocation of critical resources. )
- Use
an asymmetric solution, in which odd philosophers pick up their left
chopstick first and even philosophers pick up their right chopstick first.
( Will this solution always work? What if there are an even number of
philosophers? )
No comments:
Post a Comment