Classical Problem Synchronization

Classical Problems of Synchronization

Dinning Philosopher Problem

• Dinning philosophers problem is one of classical process synchronization problem. Here five philosophers are seated around a circular table. They spend their lives in thinking and eating. Five plates with five forks are kept on the circular table.

• While philosophers think, they ignore the eating and do not require fork. When a philosopher decides to eat, then he/she must obtain a two fork, one from left side fork and another from right side fork. Philosophers can pick up only a single fork at one time.

After consuming a food, the philosophers replace the fork and resumes thinking. A philosophers to the left or right of a ow dinning philosopher cannot eat while the dinning philosophers is eating, since forks are a shared resource.

Fig. 2.14.1 shows seating arrangement of five philosophers.

Consider the following code :

void dinning_Philosopher( )

while (true)

{

thinking ( );

eating ( );

}

void eating ()

{

takeleftfork();

takerightfork( );

eatfood(delay);

putrighttfork( );

putleftfork( );

• Here philosophers operates asynchronously and concurrently, it is possible for each philosophers to enter into eating mode. The procedure takeleftfork( ) waits until the specified fork is available and then seizes it. This is not possible because of the following reasons.

• Each philosopher will hold exactly one fork, and no forks will remain available on the table. The philosophers will all deadlock.

• To solve this problem, write some extra code in takerightfork () procedure. User can specify the philosophers to put down the left fork if that philosophers cannot obtain the right fork.

Problem analysis :

• Shared resource: Here each fork is shared by two philosophers so we called it is a shared resource.

• Race condition: we do not want a philosopher to pick up a fork that has already been picked up by his neighbor. This is a race condition.

• Solution: we consider each fork as a shared item and protected by a mutex lock. Before eating, each philosopher first lock left fork and then right fork. If philosopher acquires both locks successful, then philosophers have two locks (two fork) so he can eat a food. After finishes easting, this philosopher releases both fork, and thinks.

Some other alternatives :

1. Pick up the left fork, if the right fork is not available for a given time, put the left fork down, wait and try again. Even if each philosopher waits a different random time, an unlucky philosopher may starve.

2. Require all philosophers to acquire a binary semaphore before picking up any forks. This guarantees that no philosopher starves but limits parallelism dramatically.

• Because we need to lock and unlock a chopstick, each chopstick is associated with a mutex lock. Since we have five philosophers who think and eat simultaneously, we need to create five threads, one for each philosopher. Since each philosopher must have access to the two mutex locks that are associated with its left and right to chopsticks, these mutex locks are global variables.

Reader-Writer Problem

• When two types of processes need to access a shared resource such as a file or database. They called these processes reader and writers.

• For example in railway reservation system, readers are those who want train ar schedule information. They are called reader because readers do not change the content of the database. Many readers may access the database at once. There is sb no need to enforce mutual exclusion among readers.

• The writers are those who making reservations on a particular train. Writer can 19 modify the database, so it must have exclusive access. When writer is active, no or other readers or writers may be active. Therefore, it must enforce mutual exclusion

• Reader writer problem is similar to one which a file is to be shared among a set of processes. If a process want only to read the file, then it may share the file with any other process that also wants to read the file. If the writer wants to append the file, then no other process should have access to the file when the writer has access to i

• If reader having higher priority than the writer, then there will be starvation with writers. For writer having higher priority than reader then starvation with readers.

The Producer Consumer Problem

• Producer - consumer problem is example classic problems of synchronization. Producer process produce data item that consumer process consumes later.

• Buffer is used between producer and consumer. Buffer size may be fixed or variable. The producer portion of the application generates data and stores it in a buffer, and the consumer reads data from. the buffer. Fig. 2.14.3 shows producer-consumer problem.

• Producer-consumer is also called bounded buffer problem. There exist several producers and consumers.

The producer-consumer problem shows the need for synchronization in systems where many processes share a resource. In the problem, two processes share a fixed-size buffer. One process produces data items and deposits it in the buffer, while the other process consumes data items from the buffer.

• The producer cannot deposit its data if the buffer is full. Similarly, a consumer cannot retrieve any data if the buffer is empty. If the buffer is not full, a producer can deposit its data. The consumer should be allowed to retrieve a data item if buffer contains.

• The consumer retrieves a data item, so the data from buffer start decreasing. When buffer becomes empty, the producer should be allowed to deposit its data.

• Problem arises when the buffer is full and producer wants to add a new data item. Solution to this problem is that producer goes to sleep until consumer removes data item from the buffer. Similar condition exists with the consumer. Consumer wants to consume data item from the buffer, but buffer is empty then consumer go to sleep. It wakeup when producer add some data items into the buffer.

• In order to synchronize these processes, both procedure and consumer are blocked on some condition. The producer is blocked when the buffer is full, and the consumer is blocked when the buffer is empty.

• Example of procedure consumer problem:

1. Printing word file: When user gives the print command for printing file, a word processor spools data to a buffer and that data are subsequently consumed by the printer as it prints the document. Printer stops printing when buffer is empty.

2. A compiler may produce assembly code, which is consumed by an assembler. Speed of the procedure and consumer is different. The producer process is faster than the consumer process. Suppose the CPU is producer and line printer is consumer, then CPU can generate data much faster than a line printer.To solve this above problem, buffer is used in between procedure and consumer. (Buffer capacity is fixed (bounded) or variable (unbounded). Fig. 2.14.4 shows the buffer states between producer-consumer problem. Buffer is in any of the following states:

1. Full buffer

2. Empty buffer

3. Partially empty buffer

• A solution to the producer-consumer problem satisfy the following conditions:

1. When buffer is full, producer must wait. Producer do not produce data item.

2. When buffer is empty, consumer must wait.

3. Mutual exclusion is required for accessing the buffer.

• Producer-consumer problem is solved by using semaphore, mutex and monitor. Mutual exclusion must be enforced on the buffer itself.

• Each data item produce by producer to the shared buffer must be consumed exactly once by the consumer. Data item must be consumed in the same order (First in First Out Order) in which it is out into the buffer.

• If there is no synchronization between producer and consumer then data can be lost if the producer add new data item into the buffer before the consumer consumes the previous data item.

• We use variable counter to keep track of the number of data items in the buffer.

Solution to single producer and single consumer is given below:

1. Code for producer

producer (void)

{

int item;

while (TRUE)

{

produce item(&item);

produce if (counter == N)

sleep();

enter item(item);

counter counter + 1;

if (counter == 1)

wakeup(consumer);

}

}

2. Code for consumer process

consumer(void)

{

int item;

while (TRUE) 

{

if (count == 0) sleep();

remove_item(&item); 

counter counter - 1;

if (count == N-1)

wakeup(producer); 

consume_item(item);

}

}

• Initially we assume that the buffer is empty. Consumer read the counter and context switch occurs. The producer process produce data item and increments the counter by one. After incrementing the counter, it sends a wakeup signal to the consumer. Here one more context switching occurs and consumer process runs.

• Solution to producer consumer problem by using binary semaphore : 

void main()

{

count = 0;

int i;

binarysemaphore s = 1;

int producer ()

{

While (true)

{

produce_data_item( );

semwaitB(s);

append();

count count + 1;

if (count == 1)

semSignalB(delay);

semSignalB(s);

int consumer ()

{

int P;

semWaitB(delay);

while (true)

{

semWaitB(s);

consume();

count count - 1;

p = count; semSignalB(s); consumedata();

if (p == 0) semWaitB(delay);

of bewollsei

University Question

1. Consider a situation where we have a file shared between many people.

If one of the people tries editing the file, no other person should be reading or writing at the same time, otherwise changes will not be visible to him/her. However if some person is reading the file, then others may read it at the same time.

a) What kind of situation is this?

b) Consider the following problem parameters to solve this situation. 

Problem parameters:

1) One set of data is shared among a number of processes. 

2) Once a writer is ready, it performs it write. Only one writer: may write t write at a time.

3) If a process is writing no other process can read it. 

4) If at least one reader is reading, no other process can read it. 

5) Readers may not write and only read.

AU: Dec.-17, Marks 11

Ans. It is reader and writer problem. Here we consider reader having higher priority than writer. Reader should not wait if the share is currently opened for reading.

• To implement this problem three variables are used; readcount, mutex and wrt. 

Semaphore function: wait() and signal()

semophore mutex, wrt;

int readcount;

• For writer process:

1. Writer requests the entry to critical section.

2. If allowed i.e. wait() gives a true value, it enters and performs the write. If not allowed, it keeps on waiting.

3. It exits the critical section.

do {

// writer requests for critical section

wait(wrt);

// performs the write and leaves the critical section

signal(wrt);

} while(true);

•For reader process:

1. Reader requests the entry to critical section.

2.If allowed: It increments the count of number of readers inside the critical section. If this reader is the first reader entering, it locks the wrt semaphore to restrict the entry of writers if any reader is inside.

• It then, signals mutex as any other reader is allowed to enter while others are already reading.

• After performing reading, it exits the critical section. When exiting, it checks if no more reader is inside, it signals the semaphore "wrt" as now, writer can enter the critical section.

3. If not allowed, it keeps on waiting.

do {

// Reader wants to enter the critical section

wait(mutex);

// The number of readers has now increased by 1

readcount = readcount + 1;

// there is atleast one reader in the critical section, this ensure no writer

can enter if there is even one reader

// thus we give preference to readers here

HSM if (readcnt==1)

// other r neaders can enter while this current reader is inside

// the critical section

signal(mutex);

// current reader performs reading here

wait(mutex); // a reader wants to leave

readcount = readcount -1;

// that is, no reader is left in the critical section,

if (readcount == 0)

signal(wrt);

// writers can enter

signal(mutex); // reader leaves

} while(true);

Semaphore 'wrt' is queued on both readers and writers in a manner such that preference is given to readers if writers are also there. Thus, no reader is waiting simply because a writer has requested to enter the critical section.