Google Answers Logo
View Question
Q: Operating System ( No Answer,   0 Comments )
Subject: Operating System
Category: Computers > Operating Systems
Asked by: bear28-ga
List Price: $15.00
Posted: 26 May 2006 10:07 PDT
Expires: 26 May 2006 15:48 PDT
Question ID: 732630
1. We cannot assume any particular order when a process or thread is 
released from a semaphore. The following sample code ATTEMPTS to 
implement a FIFO semaphore so that the waiting processes will be released 
in a first-in-first-out order. In the sample code, a FIFO semaphore
consists of an integer counter that is used to simulate a semaphore?s
counter, and a semaphore queue which is used to enforce the
order. The two corresponding procedures are FIFO_Wait(..) and FIFO_Signal().
To guarantee atomic execution of these two procedures, a semaphore
Mutex is used with an initial value 1. FIFO_Wait() uses Mutex to lock
the procedure and checks the semaphore counter. Then, FIFO_Wait()
releases the procedure and it is all set. If Counter is zero, then the
caller must be queued. To this end, a semaphore X with initial value 0
is allocated, and added to the end of a semaphore queue. Then,
FIFO_Wait() releases the procedure, and lets the
caller wait on X. On the other hand, FIFO_Signal() first locks the
procedure, and checks if the semaphore queue is empty. If the queue is
empty, the counter is increased by one, unlocks the procedure, and
returns. However, if there is a waiting process in the queue, the head
of the queue is removed and signaled so that the only waiting process
on that semaphore can continue. Then, this semaphore node is freed and
the procedure is unlocked. Finally, the
initialization procedure FIFO_Init(), not shown below, sets the
counter to an initial value and the queue to empty.
Semaphore Mutex = 1;
int Counter;
FIFO_Wait(...) FIFO_Signal(...)
Wait(Mutex); Wait(Mutex);
if (Counter > 0) { if (queue is empty) {
Counter--; Counter++;
Signal(Mutex); Signal(Mutex);
else { /* must wait here */ else { /* someone is waiting */
allocate a semaphore node, X=0; remove the head X;
add X to the end of queue; Signal(X);
Signal(Mutex); free X;
Wait(X); Signal(Mutex);
Discuss the correctness of this solution. If you think it correctly
implements a first-in-first-out semaphore, provide a convincing
argument to justify your claim. Otherwise, discuss why it is wrong
using a logic execution sequence.
There is no answer at this time.

There are no comments at this time.

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  

Google Home - Answers FAQ - Terms of Service - Privacy Policy