Description
The following code was proposed (by David Seidman CS-350 class of S’04) as the rendezvous code for N processes using N semaphores:
signal(semaphore[i]);
for(j = 0; j < N; j++) {
wait(semaphore[j]);
signal(semaphore[j]);
}
[[Rendezvous Code Here]]]
Prove that the above code will work. What should be the initialization of semaphore[i]?
When presented with the above code, another student suggested that a better solution is the one below.
signal(semaphore[i]);
for(j = 0; j < N; j++) {
wait(semaphore[j]);
signal(semaphore[j]);
}
[[Rendezvous Code Here]]]
wait(semaphore[i]);
Could a process ever block as a result of executing the last instruction in the above code? If yes, give an example, if not, then explain why not.
Why do you think the last instruction in the above code is included?
Laundromat Brawl. The local laundromat has just entered the computer age. As each customer enters, he or she puts coins into slots at one of two stations and types in the number of washing machines he/she will need. The stations are connected to a central computer that automatically assigns available machines and outputs tokens that identify the machines to be used. The customer puts laundry into the machines and inserts each token into the machine indicated on the token. When a machine finishes its cycle, it informs the computer that it is available again. The computer maintains a boolean array available[M] to represent if corresponding machines are available (M is a constant indicating how many machines there are in the laundromat), and a semaphore nfree that indicates how many machines are available. The pseudo code to allocate and release machines is as follows. The available array is initialized to all true, and nfree is initialized to M.
int allocate() /* Returns index of available machine */
{
wait(nfree); /* Wait until a machine is available */
for (int i=0; i < M; i++)
if (available[i]) {
available[i] = FALSE;
return i;
}
}
void return(int machine) /* Make machine available again */
{
available[machine] = TRUE;
signal(nfree);
}
It seems that if two people make requests at the two stations at the same time, they will occasionally be assigned the same machine. This has resulted in several brawls in the laundromat, and you have been called in by the owner to fix the problem. Assume that one thread handles each customer station. Explain how the same washing machine can be assigned to two different customers.
Modify the pseudo code above to eliminate the problem. You need not implement this in Java, but feel free to do so if you wish.
Critical Section with Priorities: A set of processes share a critical section of code, which is to be accessed in a mutually exclusive fashion. Each process is assigned a priority according to its ID — the lower the ID, the higher the priority, so P1 is higher priority than P2. If two or more processes need to access the critical section, then the one with “higher priority” enters the critical section next. The following is a sketch of the solution for this problem using semaphores.
We keep a vector V[] of booleans. V[i] is “True” if Pi needs to use the critical section.
We use a vector of binary semaphores B[] to block processes from entering their critical section: B[i] will be the semaphore blocking process Pi.
A special scheduler process SCHED is used whenever a blocked process needs to be awakened to use the critical section.
SCHED is blocked by waiting on a special semaphore S.
When a process Pi needs to enter the critical section, it sets V[i] to “True”, signals the semaphore S and then waits on the semaphore B[i].
Whenever SCHED is unblocked, it selects the process Pi (if any) with the smallest index i for which V[i] is “True”. Process Pi is then awakened by signaling B[i]. SCHED goes back to sleep by blocking on semaphore S.
When a process Pi leaves the critical section, it signals S.
Answer the questions below:
Implement the operation of the above sketched system in Java [here is a primer on using semaphores in Java]. Clearly explain the various data structures you use and initializations thereof.
Show your Java code in action. Assume that there are five processes P0, P1, P2, … P5 with P0 being the highest priority, P1 being the next, etc. Each process requests the critical section for a total of five times (say in a loop from 1 to 5). Process Pi should print “Pi is requesting CS” before proceeding with the step described in (e) above. It should print “Pi is in the CS” whenever it is in the critical section. And, it should print “Pi is exiting the CS” when it gets to the step described in (g). Your code needs fixing if you get a printout indicating that two processes Pi and Pj (where i<j) are requesting the CS and Pj gets to the CS before Pi (even if Pj requested it before Pi).
Explain how you could use the above template to design a protocol for a set of processes to access the CS according to some arbitrary metric — e.g., using EDF based on a deadline imposed on the process, or by accounting for the number of times a process was allowed to enter the CS, and giving priority to the process that has used the CS the least so far in its lifetime, etc.
The use of a single directional servo camera is to be synchronized among a set of concurrent client processes (threads). Using servo controls, it is possible to make the camera point to any one of 8 different discrete angles to take a snapshot. Since it takes a significant amount of time for the camera to change its angle (compared to the time it takes it to take the picture), it was determined that a good way to synchronize the various client processes’ exclusive use of the camera is to use one of the various schedulers for stateful resources, namely, the FSCAN scheduler.
The proposed solution works as follows:
Each client thread will execute in a loop, in which the thread would (1) sleep for a random period of time, (2) requests a snapshot at some camera angle (e.g., selected uniformly at random), (3) blocks until the camera takes that snapshot, and (4) go back to (1).
The camera is controlled by a single thread that executes in a continuous loop, in which the thread would (1) block until a request from a client thread is issued, (2) selects the next request to service according to the FSCAN scheduling strategy, (3) after some delay proportional to the angle it has to move, it signals the client thread(s) for which the snapshot was taken, and (4) go back to (1).
In the above solution, since it may be the case that multiple client threads might be blocked waiting for snapshots from the same angle, the camera thread should signal all threads that requested that angle since one snapshot would satisfy all of them.
Write a Java code that implements the above sketched solution. Your code should produce printouts every time a client makes a request and every time the camera serves a snapshot to one or more clients (indicating the client id and the angle of the snapshot requested/served). Use your code for enough time and with enough client threads and number of iterations to convince yourself (and the graders) that FSCAN is followed correctly.