Operating System Unit 4

Que:-1    Explain the terms : Race Condition, Critical Section and Starvation.

Ans:-    

Race Condition

A race condition is a situation that may occur inside a critical section. This happens when the result of multiple thread execution in critical section differs according to the order in which the threads execute.

Race conditions in critical sections can be avoided if the critical section is treated as an atomic instruction. Also, proper thread synchronization using locks or atomic variables can prevent race conditions.

Critical Section

The critical section in a code segment where the shared variables can be accessed. Atomic action is required in a critical section i.e. only one process can execute in its critical section at a time. All the other processes have to wait to execute in their critical sections.

Starvation is a condition where a process does not get the resources it needs for a long time because the resources are being allocated to other processes.

It generally occurs in a Priority based scheduling System.

Que:-2    What do you mean by mutual exclusion? Explain Peterson’s solution for mutual exclusion problem.

Ans:-    

Mutual exclusion[edit]

P0 and P1 can never be in the critical section at the same time. If P0 is in its critical section, then flag[0] is true. In addition, either flag[1] is false (meaning that P1 has left its critical section), or turn is 0 (meaning that P1 is just now trying to enter the critical section, but graciously waiting), or P1 is at label P1_gate (trying to enter its critical section, after setting flag[1] to true but before setting turn to 0 and busy waiting). So if both processes are in their critical sections, then we conclude that the state must satisfy flag[0] and flag[1] and turn = 0 and turn = 1. No state can satisfy both turn = 0 and turn = 1, so there can be no state where both processes are in their critical sections. (This recounts an argument that is made rigorous in.

Peterson's algorithm (or Peterson's solution) is a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated by Gary L. Peterson in 1981.^[1] While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two.

The algorithm

The algorithm uses two variables: flag and turn. A flag[n] value of true indicates that the process n wants to enter the critical section. Entrance to the critical section is granted for process P0 if P1 does not want to enter its critical section or if P1 has given priority to P0 by setting turn to 0.

Que:-3    What is Semaphore? Give the implementation of Readers-Writers Problem using Semaphore.

Ans:-

Semaphores can be used to restrict access to the database under certain conditions. In this example, semaphores are used to prevent any writing processes from changing information in the database while other processes are reading from the database.

semaphore mutex = 1;                 // Controls access to the reader count
semaphore db = 1;                    // Controls access to the database
int reader_count;                    // The number of reading processes accessing the data

Reader()
{
  while (TRUE) {                     // loop forever
     down(&mutex);                          // gain access to reader_count
     reader_count = reader_count + 1;       // increment the reader_count
     if (reader_count == 1)
         down(&db);                         // if this is the first process to read the database,
                                            // a down on db is executed to prevent access to the 
                                            // database by a writing process
     up(&mutex);                            // allow other processes to access reader_count
     read_db();                             // read the database
     down(&mutex);                          // gain access to reader_count
     reader_count = reader_count - 1;       // decrement reader_count
     if (reader_count == 0)
         up(&db);                           // if there are no more processes reading from the 
                                            // database, allow writing process to access the data
     up(&mutex);                            // allow other processes to access reader_countuse_data();
                                            // use the data read from the database (non-critical)
}

Writer()
{
  while (TRUE) {                     // loop forever
     create_data();                         // create data to enter into database (non-critical)
     down(&db);                             // gain access to the database
     write_db();                            // write information to the database
     up(&db);                               // release exclusive access to the database
}

Que:-4   What is Monitor? Write Solution to Dining-Philosopher problem using monitor.

Ans:-

Monitor-based Solution to Dining Philosophers
We illustrate monitor concepts by presenting a deadlock-free solution to the dining-philosophers problem. Monitor is used to control access to state variables and condition variables. It only tells when to enter and exit the segment. This solution imposes the restriction that a philosopher may pick up her chopsticks only if both of them are available.
To code this solution, we need to distinguish among three states in which we may find a philosopher. For this purpose, we introduce the following data structure:
THINKING – When philosopher doesn’t want to gain access to either fork.
HUNGRY – When philosopher wants to enter the critical section.
EATING – When philosopher has got both the forks, i.e., he has entered the section.