Qing Li - Real-Time Concepts for Embedded Systems

· ceiling priority protocol-ensures that the priority level of the task that acquires the mutex is automatically set to the highest priority of all possible tasks that might request that mutex when it is first acquired until it is released.

When the mutex is released, the priority of the task is lowered to its original value.

Chapter 16 discusses priority inversion and both the priority inheritance and ceiling priority protocols in more detail. For now, remember that a mutex supports ownership, recursive locking, task deletion safety, and priority inversion avoidance protocols; binary and counting semaphores do not.

Typical operations that developers might want to perform with the semaphores in an application include:

· creating and deleting semaphores,

· acquiring and releasing semaphores,

· clearing a semaphore’s task-waiting list, and

· getting semaphore information.

Each operation is discussed next.

Table 6.1 identifies the operations used to create and delete semaphores.

Table 6.1: Semaphore creation and deletion operations.

Several things must be considered, however, when creating and deleting semaphores. If a kernel supports different types of semaphores, different calls might be used for creating binary, counting, and mutex semaphores, as follows:

· binary- specify the initial semaphore state and the task-waiting order.

· counting- specify the initial semaphore count and the task-waiting order.

· mutex- specify the task-waiting order and enable task deletion safety, recursion, and priority-inversion avoidance protocols, if supported.

Semaphores can be deleted from within any task by specifying their IDs and making semaphore-deletion calls. Deleting a semaphore is not the same as releasing it. When a semaphore is deleted, blocked tasks in its task-waiting list are unblocked and moved either to the ready state or to the running state (if the unblocked task has the highest priority). Any tasks, however, that try to acquire the deleted semaphore return with an error because the semaphore no longer exists.

Additionally, do not delete a semaphore while it is in use (e.g., acquired). This action might result in data corruption or other serious problems if the semaphore is protecting a shared resource or a critical section of code.

Table 6.2 identifies the operations used to acquire or release semaphores.

Table 6.2: Semaphore acquire and release operations.

The operations for acquiring and releasing a semaphore might have different names, depending on the kernel: for example, take and give, sm_p and sm_v, pend and post, and lock and unlock. Regardless of the name, they all effectively acquire and release semaphores.

Tasks typically make a request to acquire a semaphore in one of the following ways:

· Wait forever- task remains blocked until it is able to acquire a semaphore.

· Wait with a timeout- task remains blocked until it is able to acquire a semaphore or until a set interval of time, called the timeout interval, passes. At this point, the task is removed from the semaphore’s task-waiting list and put in either the ready state or the running state.

· Do not wait- task makes a request to acquire a semaphore token, but, if one is not available, the task does not block.

Note that ISRs can also release binary and counting semaphores. Note that most kernels do not support ISRs locking and unlocking mutexes, as it is not meaningful to do so from an ISR. It is also not meaningful to acquire either binary or counting semaphores inside an ISR.

Any task can release a binary or counting semaphore; however, a mutex can only be released (unlocked) by the task that first acquired (locked) it. Note that incorrectly releasing a binary or counting semaphore can result in losing mutually exclusive access to a shared resource or in an I/O device malfunction.

For example, a task can gain access to a shared data structure by acquiring an associated semaphore. If a second task accidentally releases that semaphore, this step can potentially free a third task waiting for that same semaphore, allowing that third task to also gain access to the same data structure. Having multiple tasks trying to modify the same data structure at the same time results in corrupted data.

To clear all tasks waiting on a semaphore task-waiting list, some kernels support a flush operation, as shown in Table 6.3.

Table 6.3: Semaphore unblock operations.

The flush operation is useful for broadcast signaling to a group of tasks. For example, a developer might design multiple tasks to complete certain activities first and then block while trying to acquire a common semaphore that is made unavailable. After the last task finishes doing what it needs to, the task can execute a semaphore flush operation on the common semaphore. This operation frees all tasks waiting in the semaphore’s task waiting list. The synchronization scenario just described is also called thread rendezvous, when multiple tasks’ executions need to meet at some point in time to synchronize execution control.

At some point in the application design, developers need to obtain semaphore information to perform monitoring or debugging. In these cases, use the operations shown in Table 6.4.

Table 6.4: Semaphore information operations.

These operations are relatively straightforward but should be used judiciously, as the semaphore information might be dynamic at the time it is requested.

Semaphores are useful either for synchronizing execution of multiple tasks or for coordinating access to a shared resource. The following examples and general discussions illustrate using different types of semaphores to address common synchronization design requirements effectively, as listed:

· 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.

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.