Question

Explain the main disadvantage of scheduling with preemption. (b) Describe and explain an example. (c) Is the Five Philosophers Problem a synchronization problem? Explain.

Answer 1

a) Explain the main disadvantage of scheduling with preemption.

Preemptive Scheduling is a CPU scheduling technique that works by dividing time slots of CPU to a given process. When the burst time of the process is greater than CPU cycle, it is placed back into the ready queue and will execute in the next chance. This scheduling is used when the process switch to ready state.

Main Disadvantage of Preemptive Scheduling

Takes a higher time by the scheduler to suspend the running task, switch the context, and dispatch the new incoming task. The process which has low priority needs to wait for a longer time if some high priority processes arrive continuously.

In this given figure you can see how the preemptive scheduling done the work of the particular process.

b) Is the Five Philosophers Problem a synchronization problem? Explain.

Yes, the five philosophers problem is a synchronization problem because a solution of the Dining Philosophers Problem (DPP) is to use a semaphore to represent a chopstick. A chopstick can be picked up by executing a wait operation on the semaphore and released by executing a signal semaphore.

The structure of the chopstick is -

semaphore chopstick [5];

Initially the elements of the chopstick are initialized to 1 as the chopsticks are on the table and not picked up by a philosopher.

The structure of a random philosopher i is given -

do {
   wait( chopstick[i] );
   wait( chopstick[ (i+1) % 5] );
   . .
   . EATING THE RICE
   .
   signal( chopstick[i] );
   signal( chopstick[ (i+1) % 5] );
   .
   . THINKING
   .
} while(1);

In the above structure, first wait operation is performed on chopstick[i] and chopstick[ (i+1) % 5]. This means that the philosopher i has picked up the chopsticks on his sides. Then the eating function is performed.

After that, signal operation is performed on chopstick[i] and chopstick[ (i+1) % 5]. This means that the philosopher i has eaten and put down the chopsticks on his sides. Then the philosopher goes back to thinking.

Difficulty in the Solution -

The above solution makes sure that no two neighboring philosophers can eat at the same time. But this solution can lead to a deadlock. This may happen if all the philosophers pick their left chopstick simultaneously. Then none of them can eat and deadlock occurs.

Some of the ways to avoid deadlock are as follows −

There should be at most four philosophers on the table.

An even philosopher should pick the right chopstick and then the left chopstick while an odd philosopher should pick the left chopstick and then the right chopstick.

A philosopher should only be allowed to pick their chopstick if both are available at the same time.