Ethelcofie’s How To Articles

September 15, 2008

Program for simulation of mutual exclusion with the use of semaphores

Program for simulation of mutual exclusion with the use of semaphores

PROBLEM DESCRIPTION

In operating systems the problem of mutual exclusion is very often encountered because of multiple processes that access, modify certain shared resources such as data structures .The operating system need to ensure that these shared data structures are not accessed and modified by multiple processes at the same time causing incorrect results for the processes involved. One of the solutions to the problem of mutual exclusion is to use semaphores which as defined by http://encyclopedia.thefreedictionary.com as a protected variable (or abstract data type) and constitutes the classic method for restricting access to shared resources (e.g. storage) in a multiprogramming environment.

Semaphores have two basic functions, P():checks if critical section is filled then blocks or allows process as appropriate() function: checks when a process leaves critical section and removes it from semaphore queue.

The semaphores are used to implement these rules: to at most one process uses the shared data structure at a time (critical section) and all processes get their turn with the shared resource

PROGRAM DESCRIPTION

This java program simulates the use mutual exclusion using semaphores. The program involves four processes named process 1,2,3,4 who are competing for critical sections A,B,C,D,E,F,G. with a semaphore A for critical section A,sem Z for B,semC for B,sem D for section E, ,sem F for section F and lastly sem G for section G .

The simulation program implements mutual exclusion by implementing these three rules:

1. At most one process may execute in the critical section a time i.e. all processes that request a critical section that is occupied are denied request and are to wait.

2. Request to enter and exit a critical section is eventually succeed: All processes that have made a request for a critical section may be denied a request initially but after a wait will get into the critical section when it is available.

3. Critical section request are prioritized on First come first served basis

HOW PROGRAM WORKS

The program simulates a random request by any number of the processes for any of critical sections and implements the management of these process request using mutual exclusion rules stated above.

The program works by creating four processes, then creating 7 semaphores along corresponding to the 7 critical sections. The implements a P function whose primary task is to check when a process makes critical section request using the counter variable whether or not the critical section is occupied if it is it blocks the process until critical section is vacant else removing process from process queue and adding it to the semaphore queue

The program also implements the V function whose primary duty is to check for a process leaving a critical section decrease counter value flagging the critical section as vacant .This is implemented after a process sends a message of leaving the process

ALGORITHM

Create Processes

Create all 7 critical sections

Create corresponding semaphores for each critical section

If for a process request for a critical section

Then

Check if semaphore counter >0

Refuse permission to enter section for process and request process to hold till critical section if available

Add process to semaphore queue

If semaphore counter =0

Then

Grant permission to enter the critical section

Remove process from semaphore queue

If process sends an acknowledgement to leave the critical section

Then

Decrease semaphore counter

DRAWING OF A SCENARIO OF THE MUTUAL EXCLUSION SIMULATION PROGRAM

DRAWING OF A SCENARIO OF THE MUTUAL EXCLUSION

DRAWING OF A SCENARIO OF THE MUTUAL EXCLUSION

SCREEN SHOT OF MUTUAL EXCLUSION INVOLVING FOUR PROCESSES AND 7 CRITICAL SECTIONS AND THEIR METAPHORS

Advertisements

Leave a Comment »

No comments yet.

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Create a free website or blog at WordPress.com.

%d bloggers like this: