CENG 302
OPERATING SYSTEMS
Dr. Mansur Alp TOÇOĞLU
In this chapter,
• Classic Synchronization Problems and Solutions
• Producer/Consumer
• Reader/Writer
• Dining Philosopher
topics will be discussed.
2
THREE CLASSICAL
SYNCHRONIZATION PROBLEMS
• Three classical synchronization problems will be
studied.
1. The Producer-Consumer Problem
2. The Readers–Writers Problem
3. The Dining-Philosophers Problem
3
PRODUCER-CONSUMER PROBLEM
• Producer and consumer are created as processes.
• There are 3 important restrictions here:
• Only one process can access the buffer at a time (mutual exclusion).
For this purpose, mutex or binary semaphore will be used.
• If the Buffer is empty, the consumer waits for the producer to enter
data into the Buffer. The producer and consumer will use the
semaphore named empty for synchronization purposes.
• If the Buffer is full, the producer waits for the consumer to receive
data from the Buffer. The producer and the consumer will use the
full named semaphore for synchronization purposes.
4
PRODUCER-CONSUMER PROBLEM
(CONTINUES…)
# define N 100 / * Number of elements in the buffer*/
# define TRUE 1
typedef int semaphore; / * Semaphores are defined as an int type */
semaphore mutex = 1; / * mutually exclusive of the critical section */
semaphore empty = N; / * Number of empty slots in the buffer */
semaphore full = 0; / * Number of occupied slots in the buffer*/
producer()
{
int item; / * local variable */
while (TRUE) {
produce_item(&item);
wait(empty); / * If the Buffer is full, wait, otherwise reduce by 1*/
wait(mutex); / * Ask permission to enter the critical section*/
enter_item(item); / * Enter data into Buffer (Critical Section) */
signal(mutex); / * Indicate that you have left the Critical Section */
signal(full); / * Wake up any consumer waiting*/
/ * Increase the number of full slot by 1*/
}
}
consumer(){
int item; / * local variable */
while (TRUE) { / * If the Buffer is empty, wait, otherwise reduce the
wait(full); number of full spaces by 1 */
wait(mutex); / * Ask permission to enter the critical section */
remove_item(&item); / * Get data from Buffer (Critical section) */
signal(mutex); / * Indicate that you have left the Critical Section */
signal(empty); / * If there is a waiting producer, wake it up */
consume_item(item);
}
} 5
PRODUCER-CONSUMER PROBLEM
(CONTINUES…)
Semaphores: mutex, empty, full;
mutex = 1; /* for mutual exclusion*/
empty = N; /* number empty buf entries */
full = 0; /* number full buf entries */
Producer Consumer
do { do {
... wait(full);
// produce an item in nextp wait(mutex);
... ...
wait(empty); // remove item to nextc
wait(mutex); ...
... signal(mutex);
// add nextp to buffer signal(empty);
... ...
signal(mutex); // consume item in nextc
signal(full); ...
} while (true); } while (true);
6
PRODUCER-CONSUMER PROBLEM
SOLUTION IN C
Global Tanımlar
7
PRODUCER-CONSUMER PROBLEM
SOLUTION IN C ( C O N T I N U E S … )
main()
8
PRODUCER-CONSUMER PROBLEM
SOLUTION IN C ( C O N T I N U E S … )
Producer
9
PRODUCER-CONSUMER PROBLEM
SOLUTION IN C ( C O N T I N U E S … )
Consumer
10
READERS-WRITERS PROBLEM
• Suppose a database is shared by multiple processes.
• While some processes only want to read data,
• Others will want to manipulate the data.
(Readers and Writers)
• There is no problem if two processes want to
read at the same time, but a problem may
occur if a writer accesses the data at the same time
with a reader or a writer process.
• This synchronization problem is called
Readers/Writers.
11
READERS-WRITERS PROBLEM
(CONTINUES…)
Writer Process
12
READERS-WRITERS PROBLEM
(CONTINUES…)
Reader Process
do
{
wait(mutex) :The reader waits on the mutex, only
protecting the read counter
read_count++: Number of processes wanting to read
if (read_count==1) :If first reader process
wait(rw_mutex); :1 reader is waiting
signal(mutex)
......
//do the reading
.......
wait(mutex) : n-1 reader is waiting on mutex
read_count--: 1 reader finished reading
if (read_count==0 ) :If the last reader
signal(rw_mutex)
signal(mutex)
}while (true);
13
READERS-WRITERS PROBLEM
SOLUTION IN C
Global Definitions
14
READERS-WRITERS PROBLEM
SOLUTION IN C
main()
15
READERS-WRITERS PROBLEM
SOLUTION IN C
Writer Process
16
READERS-WRITERS PROBLEM
SOLUTION IN C
Reader Process
17
THE DINING-PHILOSOPHERS
PROBLEM
• There are 5 philosophers. Their work is to think and eat rice.
• There are 5 chairs, 5 plates and 5 chopsticks.
• A philosopher can eat with 2 chopsticks.
• Philosophers are not influenced by each other while thinking.
18
THE DINING-PHILOSOPHERS
PROBLEM ( C O N T I N U E S … )
• When eating, a philosopher uses his neighbor’s chopstick. Meanwhile, his
neighbor has to think.
• Having seized the two chopsticks, the philosopher eats his food without taking
a break, leaves the chopsticks and continues to think.
• Each chopstick is represented by a semaphore and given a value of 1.
• A philosopher takes over the chopstick, that is, the semaphore, by executing the wait
operation on the chopstick.
• Likewise, a philosopher releases the chopsticks with the signal operation.
• If they all take the left side chopsticks in their left hand at the same time, they will
all starve forever. For solution :
• A maximum of n-1 philosophers can be allowed to sit at the table at a time
• A philosopher starts eating only by checking whether both chopsticks are empty. If
they are empty, philosopher may be allowed. This operation should be done in critical
section. int sem_getvalue(sem_t *sem, int *valp);
• Asymmetric solution –Odd numbered philosophers first left chopsticks, then right
ones may be allowed. For even numbered philosophers, first the right and then the left
chopsticks may be allowed.
• A philosopher can be made to pick up the chopstick on his right first.
19
THE DINING-PHILOSOPHERS
PROBLEM ( C O N T I N U E S … )
Pseudocode….
20
THE DINING-PHILOSOPHERS
SOLUTION IN C
Global Definitions
21
THE DINING-PHILOSOPHERS
SOLUTION IN C
THE DINING-PHILOSOPHERS
SOLUTION IN C
REFERENCES
• Textbook:
• Operating System Concepts, Ninth Edition, Abraham
Silberschatz, Peter Bear Galvin, Greg Gagne
24
