· wait-and-signal synchronization,
· multiple-task wait-and-signal synchronization,
· credit-tracking synchronization,
· single shared-resource-access synchronization,
· recursive shared-resource-access synchronization, and
· multiple shared-resource-access synchronization.
Note that, for the sake of simplicity, not all uses of semaphores are listed here. Also, later chapters of this book contain more advanced discussions on the different ways that mutex semaphores can handle priority inversion.
6.4.1 Wait-and-Signal Synchronization
Two tasks can communicate for the purpose of synchronization without exchanging data. For example, a binary semaphore can be used between two tasks to coordinate the transfer of execution control, as shown in Figure 6.5.
Figure 6.5: Wait-and-signal synchronization between two tasks.
In this situation, the binary semaphore is initially unavailable (value of 0). tWaitTask has higher priority and runs first. The task makes a request to acquire the semaphore but is blocked because the semaphore is unavailable. This step gives the lower priority tSignalTask a chance to run; at some point, tSignalTask releases the binary semaphore and unblocks tWaitTask. The pseudo code for this scenario is shown in Listing 6.1.
Listing 6.1: Pseudo code for wait-and-signal synchronization
tWaitTask () {
:
Acquire binary semaphore token
:
}
tSignalTask () {
:
Release binary semaphore token
:
}
Because tWaitTask's priority is higher than tSignalTask's priority, as soon as the semaphore is released, tWaitTask preempts tSignalTask and starts to execute.
6.4.2 Multiple-Task Wait-and-Signal Synchronization
When coordinating the synchronization of more than two tasks, use the flush operation on the task-waiting list of a binary semaphore, as shown in Figure 6.6.
Figure 6.6: Wait-and-signal synchronization between multiple tasks.
As in the previous case, the binary semaphore is initially unavailable (value of 0). The higher priority tWaitTasks 1, 2, and 3 all do some processing; when they are done, they try to acquire the unavailable semaphore and, as a result, block. This action gives tSignalTask a chance to complete its processing and execute a flush command on the semaphore, effectively unblocking the three tWaitTasks, as shown in Listing 6.2. Note that similar code is used for tWaitTask 1, 2, and 3.
Listing 6.2: Pseudo code for wait-and-signal synchronization.
tWaitTask () {
:
Do some processing specific to task
Acquire binary semaphore token
:
}
tSignalTask () {
:
Do some processing Flush binary semaphore's task-waiting list
:
}
Because the tWaitTasks' priorities are higher than tSignalTask's priority, as soon as the semaphore is released, one of the higher priority tWaitTasks preempts tSignalTask and starts to execute.
Note that in the wait-and-signal synchronization shown in Figure 6.6 the value of the binary semaphore after the flush operation is implementation dependent. Therefore, the return value of the acquire operation must be properly checked to see if either a return-from-flush or an error condition has occurred.
6.4.3 Credit-Tracking Synchronization
Sometimes the rate at which the signaling task executes is higher than that of the signaled task. In this case, a mechanism is needed to count each signaling occurrence. The counting semaphore provides just this facility. With a counting semaphore, the signaling task can continue to execute and increment a count at its own pace, while the wait task, when unblocked, executes at its own pace, as shown in Figure 6.7.
Figure 6.7: Credit-tracking synchronization between two tasks.
Again, the counting semaphore's count is initially 0, making it unavailable. The lower priority tWaitTask tries to acquire this semaphore but blocks until tSignalTask makes the semaphore available by performing a release on it. Even then, tWaitTask will waits in the ready state until the higher priority tSignalTask eventually relinquishes the CPU by making a blocking call or delaying itself, as shown in Listing 6.3.
Listing 6.3: Pseudo code for credit-tracking synchronization.
tWaitTask () {
:
Acquire counting semaphore token
:
}
tSignalTask () {
:
Release counting semaphore token
:
}
