2.4Semaphores

To further enhance the usage of CPU time and to reduce the time for task switching, we will make use of yet another powerful data structure of preemptive multitasking: semaphores. These semaphores allow changing the state of our tasks.

In our current model, the two tasks are permanently running and thus consuming precious CPU capacity. For this purpose, we introduce two new variables in the TCB: State and NextWaiting. For now, State is initially set to the value RUN, and NextWaiting is set to 0. If required, State may be set to the value BLKD (that is, blocked). So if we refer to the task as being RUN or BLOCKED, that means that the State variable has the corresponding value. As a result, we obtain the TCB and the state machine shown in Figure 2.11. The state machine will be extended later.

FIGURE 2.11 Task State Machine

Next, we slightly modify our task switching ISR so that it ignores tasks that are not in state RUN:

•Reset the interrupt, if required

•Store the internal CPU registers into the TCB to which CurrentTask is pointing

•Repeat

Replace CurrentTask by NextTask pointer of the TCB to which CurrentTask is pointing

until the state of CurrentTask is RUN

•Restore the internal CPU registers from the TCB to which CurrentTask is pointing now

•Return from ISR

There is an important invariant: Whenever a task examines the variable State, it will find this variable set to RUN . State may have any value at any time; but if

State is not set to RUN, then this task is not active at that time, and thus the task cannot find itself in another state.

This invariant does not yet have any impact on our model, since our tasks are permanently in state RUN. Clearly, if no task were in state RUN, the above ISR would loop forever. It will be the semaphores that control the state changes of a task; that is, switch between RUN and BLKD.

A semaphore represents the number of abstract resources: if resources are available, the semaphore counts the number of resources. If no resources are available, the semaphore counts the number of tasks that are waiting for resources. The latter situation can also be expressed as the “number of resources missing”. If there are resources missing, then the TCBs of the tasks waiting for these resources are appended to a linked list of TCBs of waiting tasks, where the head of the list is part of the semaphore.

The semaphore consists of two variables: a counter and a pointer to a TCB. The TCB pointer NextWaiting is only valid if the counter is less than 0; otherwise, it is invalid and set to 0 for clarity. The pointer represents the state of the semaphore as shown in Table 2.3.

TABLE 2.3 Semaphore States

When a semaphore is created, the counter is initialized with the number N > 0 of resources initially available, and the NextWaiting pointer is set to 0. Then tasks may request a resource by calling a function P(), or the tasks may release a resource by calling a function V(). The names P and V have been established by Dijkstra, who invented the semaphores concept. In C++, a semaphore is best represented as an instance of a class Semaphore, while P() and V() are public member functions of that class.

The algorithm for the P() member function is as follows:

Append CurrentTask at the end of the waiting chain

DeSchedule()

The P() function examines Counter in order to verify if there are any resources available. If so, the number of resources is simply decremented and execution proceeds. Otherwise, the number of waiting tasks is increased (which again causes the counter to be decreased, since -Counter is increased), the task is blocked and appended to the waiting chain, and finally DeSchedule() is called to make the blocking effective. Obviously, Counter is decremented in any case. So decrementing the counter can be placed outside the conditional part, thereby changing the comparison from > 0 to > 0. By inverting the condition from > 0 to < 0 and by exchanging the If part (which is empty now) and the Else part, we get the following equivalent algorithm:

•Decrement Counter

•If Counter < 0

Set State of CurrentTask to BLKD

Append CurrentTask at the end of the waiting chain

DeSchedule()

The V() member function has the following algorithm:

Set State of first waiting task to RUN

Remove first waiting task from the head of the waiting chain

The V() function examines Counter. If V() finds that Counter is > 0, which means there are no tasks waiting, then it just increments Counter, indicating there is one more resource available. If V() finds that Counter is < 0, there are tasks waiting. The number of waiting tasks is decremented by incrementing the counter, the first task in the waiting chain is then unblocked by setting its state back to RUN, and the task is removed from the waiting chain. The task that is being activated had issued a P() operation before and continues execution just after the DeSchedule() call it made in the P() function. Figure 2.12 shows a

sequence of P() function calls performed by a task T0, and V() function calls performed by another task or ISR on the same semaphore.

Count = 2

Count = 1

Count = 0

Count = -1

T0 RUN

T0 BLKD

V P P P V V P P V

FIGURE 2.12 P() and V() Function Calls

A semaphore is very similar to a bank account. There are no restrictions to pay money into your account (V()) whenever you like. In contrast, you can withdraw money (P()) only if you have deposited it before. If there is no money left, you have to wait until somebody is kind enough to fill the account again. If you try to cheat the bank by trying to withdraw money from an empty account (P() when Counter = 0), you go to jail (get blocked) until there is enough money again. Unfortunately, if you are in jail, there is no way for yourself to fix the problem by depositing money, since in jail you can’t do anything at all.

As for the bank account, there are huge differences between the P() and V() functions, see Table 2.3.

TABLE 2.4 P() and V() properties

Semaphores used some common initial values which have specific semantics, as shown in Table 2.3.

TABLE 2.5 Typical Initial Counter Values