Mumbai University > COMPS > Sem 5 > Operating System

Marks: 10 M

Year: May 2015

• Consider a system consisting of n processes P0, P1, ..., Pn.
• Each process has a segment of code, called a critical section, in which the process may be changing common variables, updating a table, writing a file, and so on. It is section of code that requires access to shared resources.
• An important fact regarding this system is that when a process A is executing in its critical section, no other process except A is allowed to execute in its critical section.
• However many processes may have a critical section code and all of them needs to be executed. So, The Critical Section Problem deals with creating a set of protocols so as to help the process cooperate.
• The code –body shown below depicts how and where the Critical Section code is implemented.

• Entry Condition: Process requests for permission to enter the critical section
• Critical section: A portion of code within a process that needs access to shared resources and that must not be executed while another process is in its critical section.
• Exit Condition: Every critical section must end with an exit condition which alerts the system regarding the exit.

A solution to a critical section problem must satisfy three conditions;

a) Mutual Exclusion: If a process A is executing in its critical section, then no other processes must execute in its critical section.

b) Progress: If no process is currently in its critical section, then only those process which are currently not in its remainder section can participate in deciding who will enter the Critical section next.

c) Bounded waiting: There exists a bound with regards to the number of times other process can enter its critical section between when a process has requested for critical section and when that request is granted

The various solutions to it are:

a) Petersons solution

Peterson’s solution is restricted to two processes that alternate execution between their critical sections and remainder sections. The processes are named P0 and P1. The Petersons solutions asks both the processes to share two data items

The algorithm for Peterson solution is:

b) Hardware based

Many modern computer systems provide a special hardware instruction that allows us either to test and modify the content of a word or to swap the contents of two words atomically—that is, as one uninterruptible unit. It is implemented using either of the two instructions:

test_and_set( ): this instruction can be executed atomically. Therefore if two such instructions are executed simultaneously on a different PC, then it will be executed in some arbitrary order

compare_and_swap( ): it also operates atomically as a single uninterruptible unit. It operates on three operands unlike test_and_set and also returns the original value of the variable value

c) Mutex lock

The hardware locks are generally inaccessible to application programmers; instead of it we use software tools-the simplest being mutex. It is short form for mutual exclusion. We use mutex lock to protect critical regions and thus avoid race conditions.

Every process will have to acquire a lock before entering the Critical section (using acquire ( ) function) and release the lock when exiting (using the release ( ) function) . Calls to the two functions mentioned above must be done atomically which is done by the hardware methods described in method (b) above.

d) Semaphores

Semaphores are similar to the mutex lock except that they are much robust and can provide sophisticated ways for the process to synchronize their activities. A semaphore S is an integer variable and can only be accessed and modified by two functions wait( ) and signal( ). It can be initialized to a non-negative value. The wait operation decrements the semaphore value while the signal operation increments the semaphore value