Parallel Programming in C for the Transputer
© D. Thiébaut, 1995

EXERCISES

7-2	Write the complete code for InManager and OutManager using the second rule of deadlock free code. Test your program by simulating several hundred concurrent enqueue and dequeue operations.

 

The reason is that if we had removed the semaphores and encapsulated the code of the InManager and OutManager between a pair of ProcToHigh() and ProcToLow() calls, we could still have had an interleave problem, because the ChanIn and ChanOut operations are blocking, and we couldn't have prevented one task to start before the other one had switched back to low-priority. This leads us to Rule 7 for implementing deadlock free accesses to shared resources.

Rule 7	When the access to the shared structure does not involve any communication primitives that are blocking, then the use of semaphores can be replaced be the creation of section run in high-priority mode. If, however, communication primitives are an integral part of the access to the shared resource, then semaphores must be employed.

7-6 Semaphores and Locks

For a lock to work properly, it must exhibit three essential properties: safety, fairness, and being live.

Safety

For example, assume that two tasks, T1 and T2, use a safe lock to access a counter count, following the algorithm below:

S1 lock(count)
S2 localcounter <-- count
S3 count <-- count+1
S4 unlock(count)

Fairness

Being live

Semaphores are safe, fair and live locks, with two operations SemP and SemV controlling their locking and unlocking, respectively. The transputer does not support semaphores in hardware, and the SemP and SemV operations are only provided as facilities by Logical Systems. Although the exact details of their implementation is proprietary and protected, we can safely make several assumptions about how the three properties have been implemented.

First the SemP operation must test the status of the Semaphore variable, and if it is in the unlock state, it must lock it, and associate the successful result of the test to that task. Because the transputer does not support such Test-and-Set operations, LS C must use high priority to prevent interleaving of these actions among several tasks.

Second, if a task attempts to lock a semaphore and finds it locked, it should not be allowed to continue and should stop until it can be granted the locked resource. Blocking the task or forcing it to reschedule is a simple solution in this case. Because the lock must be fair, a separate queue of the tasks that are waiting on the same resource is required. This queue should contain only tasks that have tried to lock that resource, and should be maintained in a first-come-first-serve basis to implement fairness and liveliness. Therefore each semaphore is associated with a queue of inactive tasks that are waiting to access the shared resource.

The SemV operation is performed when the task that had gain control of the shared resource is releasing its priviledged access. If other tasks had tried the lock during the critical section, then one of them must be selected and given the control of the lock. Since we assume that a queue is keeping track of them, then a dequeue operation is performed and the task put back on the list of active tasks.

EXERCISES

7-4

Sketch out a pseudo code description of the internal operations of SemP and SemV. In particular, explore some of the ways that can be used for SemP, which is a function called by a task, to block that task and enqueue it in a separate queue. In particular, address the following points. How can SemP "block" the task that just called it? Describe a possible data structure for the queue associated with each semaphore. What should each element of the queue contain? Assuming that some application is using only one semaphore and multiple tasks, show a block diagram representing the transputer queues containing the active and inactive tasks, and the queue associated with the semaphore. Are these queues three separate entities? .

 

7-5

Implement your own rudimentary semaphore facility, with two functions, MySemP and MySemV, for locking the semaphores, and for releasing them. In this scheme, a semaphore will simply be a collection of two integers acting as the tickets used at some grocery stores. You may have encountered this system at your supermarket. You arrive at the deli counter and find a dispenser of tickets, each one printed with a number larger than that of the previous ticket by one. You grab a ticket and wait for the clerk to call out your number. Upon finishing serving the current client, the clerk calls out the next number in sequence. Just as with the deli system where you keep checking your number against that of the currently served client, your semaphore system will keep tasks waiting on the semaphore circulating in the round-robin queue of active tasks, and allowing them to check their numbers from time to time. Identify the role of the two integers. Give an algorithmic description of the MySemP and MySemV operations, and specify how they control the two integers. How do you avoid tasks waiting on a semaphore from wasting too much processing power? Show that your system implements a locking of semaphores that is safe, live, and fair. Implement your system in LS C and test it. Verify that it works!

 

7-7 Deadlocks in Communication

• Two (or more) tasks are supposed to exchange information between each other, but because of a programming error, the tasks are unsynchronized and both try to ChanOut at the same time, or to ChanIn at the same time.

• Several tasks are supposed to exchange information between each other over channels, and this time they are well synchronized, so that a ChanOut is always matched by a ChanIn. However, the unexpected fill-to-capacity of one buffer disables a ChanIn/ChanOut communication exchange, forcing a chain reaction where other buffers fill-up, and eventually the system is deadlock with full buffers everywhere, and no possibility of emptying them.

• A group of n tasks must exchange information between them, in such a way that Task1 is waiting on Task2 for a message, while Task2 is waiting on Task3, and so on, until we find that Taskn is waiting on Task1.

For the first case explored above, the error is often a programmer's mistake and can be detected with the help of a debugger (the tasks will be both shown as blocked on a ChanIn or ChanOut operation), or by a sophisticated deadlock detection scheme.

The second and third cases are related to each other, in the sense that the failure in both cases is created by the fact that all the tasks create a cycle of requests, and that they lock each other in a system that is closed, so that no single task can exit the deadlock condition until the others in the cycle do.

This cycle formation is the major source of deadlocks in communication, and we will see that several solutions are available for preventing them.

Deadlock condition

First, let's define what we mean by cycles. To return to Example 1 at the beginning of the chapter, we can represent the computation/communication structure of the program as a graph, where the tasks become the nodes of a graph, and their interdependency introduced by the ChanIn/ChanOut primitives become the arcs linking the nodes. This graph is often referred to as a wait-for graph [FEIT91], since it shows the relationship between tasks waiting on one another. Figure 7-6 shows this graph for the Compute/Relay pair.