Transcript ex1.01

Operating Systems : Coursework 1
Coursework 1 : Semaphore Implementation
Task : To write a package of functions or methods which implement P and V
semaphore operations and to emulate their behaviour in an emulated multi-tasking
environment.
Background
• Semaphores are to be identified by a string of characters e.g. “mutex”.
• Processes are to be identified by an ID number within some range e.g. 0-255.
Specifications
The following functions should be implemented :
create_semaphore (string semaphore);
P (string semaphore, int process);
V (string semaphore);
present_status ();
In this emulation, no run queue or process scheduling is required. Instead of
branching to a dispatcher, messages are printed out monitoring the effect of the operation
just performed.
The P operation tests the value of the semaphore. If it is free, the process is allocated
the semaphore and a message to this effect is printed out. If the semaphore is not free,
the process must be queued in some appropriate data structure and a message printed
out to that effect.
The V operation also tests the semaphore. If there are any processes queued waiting
for it, the next one is notionally dispatched and a message is printed out saying this
process now has the semaphore.
For example, the function calls :
create_semaphore (“mutex”);
P(“mutex”, 1);
P(“mutex”, 2);
V(“mutex”);
V(“mutex”);
should produce output of the form semaphore “mutex” created
P(“mutex”, 1) : “mutex” allocated to process 1
P(“mutex”, 2) : process 2 queued on “mutex”
V(“mutex”) : “mutex” released by process 1
“mutex” allocated to process 2
V(“mutex”) : “mutex” released by process 2
“mutex” free
1
Operating Systems : Coursework 1
The present_status function should print out the current status of all the semaphore
queues. For example, after the calls :
P (“fred”, 1);
P(“jim”, 1);
P(“fred”, 2);
P(“fred”, 3);
the status printed should be something like :
“fred” : allocated to process 1
awaited by process 2
awaited by process 3
“jim” : allocated to process 1
This function should also detect deadlocks. For example, after :
P (“mike”, 1);
P(“roland”, 2);
P(“roland”, 1);
P(“mike”, 2);
the status printed out should be :
“mike” : allocated to process 1
awaited by process 2
“roland” : allocated to process 2
awaited by process 1
deadlock detected : processes 1, 2
Notes
• Semaphores should initially be free
• In practice, any one process cannot be queued awaiting more than one semaphore. A
test should be incorporated to preclude this arising by mistake in the emulation
requested.
• Multiple disjoint deadlock cycles, each of any length, should be detected.
• First-Come-First-Served order of queuing for semaphores should be preserved.
• Any implementation language desired may be used.
• Efficiency may be taken into account when grading submissions.
Hand-in
1. An annotated listing of your program
2. Representative tests and the resulting output
Deadline : 5pm, Friday 16th November, to the ITO.
2