RK0

This blog presents a conceptual overview of inter-task communication based on Signals, along with (some of) the services that correspond to them in RK0. Consider uniprocessor environments. Refer to the RK0 Docbook for full details and usage snippets.

Task States

For our purposes, a task, as a concurrency unit, can assume three states:

• RUNNING – it is active and occupies the CPU performing useful work.
• READY – it is able to be dispatched, if the scheduler logic decides so.
• SLEEPING – a condition must be satisfied so it switches to the READY state. This condition is generalised as an Event.

Synchronisation or Coordination

The simplest form of synchronisation is that Process A cannot proceed after point L1 before Process B reaches point L2.

To achieve that, when reaching point L1, Process A waits for a wake signal from Process B. This is a unilateral synchronisation. One task waits, and another signals—Task B is just “waving” to Task A. Hadn’t Task B signalled, Task A would be stuck, but B would proceed.

Note that if sleep or wake are operations that do not register they have happened, Task A needs to be sleeping before a wake is issued. So, either Task A is always faster than B, or it can afford to lose wake signals and wait for Task B to eventually reach point L2 again.

A bilateral synchronisation would be depicted as (using pend and post the name for the operations sleep and wake, respectively):

This could be described as ‘Task A can only proceed after point L1 when Task B reaches point L2, and Task B can only proceed after point L2 when Task A reaches point L1.’ It is often referred to as a ‘rendezvous‘ because now both stop by to “shake hands.”

The operation nomenclature varies across mechanisms and operating systems.

For uniprocessor systems, it is seldom desirable, as the task holding the lock will be periodically interrupted by the one trying to acquire the lock.

Blocking and Spin-locking

When a task is ‘waiting’ for a signal, it can be either running in a tight loop (spinning) or suspended (blocked). In multi-processor kernels, due to true parallelism, when context switching is not possible (or desirable) and/or the lock is brief, spinning can be a better option than suspending the task.

For uniprocessor environments, it is hardly the case that spinning can be more efficient than suspending a task.

INTER-TASK COORDINATION/SYNCHRONISATION MECHANISMS

In this section, we generalise mechanisms for inter-task coordination and point to the RK0 implementations.

A task reacts to an event. As mentioned, an event can be registered or not – more often than not, it is. When an event is registered, a task will react to it either when waiting for it to happen or by checking if it has happened.

Task Event Flags

Each task might have a 32-bit storage in its control block, allowing it to specify up to 32 different events by assigning 1 event/bit. A task checks/waits for a combination of events, whose meaning is implicit. Besides the combination of events, the operation get() operation also establishes if either ANY (OR logic) or ALL of the required bits (AND logic) will make the waiting condition true. A task can either suspend until the condition is met (for a bounded time or forever) or return immediately with the result.

When another task issues a set() whose result satisfies the waiting condition, if the task was pending, it switches to READY. A set operation is an OR of the current event flags with a bit string passed by the setter task.

Upon returning from a check which condition was met, all required positions are cleared on the Task’s Event Register.

Semaphores

The Counting Semaphore is the canonical semaphore: events accumulate on a counter every time they are signalled. Likewise, the counter is decreased every time an event is consumed.

PEND(S): if S > 0 then S := S-1, else the task is suspended until S > 0. 

POST(S): if there are tasks waiting, then one of them is resumed; else S := S+1.` 

A pend operation issued on a semaphore whose counter is 0 means the task ‘has not found’ what it is looking for and goes to sleep, enqueued in the semaphore waiting queue. A post on a semaphore whose value is 0 either wakes a sleeping task or increases the counter. Counting Semaphores are normally used as ‘credit trackers’ – a task pends on a semaphores before grabbing a resource from a pool, and signal upon releasing it, for instance,

A Binary Semaphore is a specialisation that counts up to 1. It suits when the number of occurrences of an event is meaningless – knowing it has occurred is enough. Binary Semaphores are also commonly used for mutual exclusion (as a one-token entry region), although not always appropriate.

LOCKS AND CRITICAL SECTIONS

Non-shareable resources, whether peripherals or data in memory, can be protected from simultaneous access by preventing tasks from concurrently executing the program pieces through which access is made. These program pieces are called critical sections.

Mutex Semaphores (Locks)

Another semaphore specialisation is a Mutex. A mutex can be described as a binary semaphore with ownership and is the ideal mechanism for critical sections. Before entering a critical section, a task locks a mutex. If successful, this task becomes the owner. Only the owner can unlock the mutex. A task trying to acquire an already locked mutex will be blocked and enqueued into the mutex’s waiting queue.

RK0 implements Mutexes with Fully Transitive Priority Inheritance

Conditional Critical Sections

It was mentioned that some mechanisms might not convey a state indicating whether an event has occurred (unlike Semaphores or Event Registers). In these cases, a task will be triggered by an event only if it is already waiting for it. Otherwise, that occurrence is lost.

In RK0, this mechanism is called the Sleep Queue: a priority-based waiting queue. They can be useful on their own, but are often more effective as building blocks for higher-level synchronisation mechanisms.

The Condition Variable Model is a known pattern, arguably, synonymous with Monitors. Monitors are ADTs – data+interface. Unlike semaphores, which can have their state changed by any task within their scope, to operate a Monitor, a task first needs to acquire it, and only a single task can be active within a monitor at any given time. When a task enters the monitor, it becomes active and can check whether a condition (a predicate) is true or false. If it is false, it unlocks the mutex and suspends itself – all within an atomic operation. Now, other tasks can enter the Monitor. Eventually, an active task will signal the sleep queue associated to that condition, indicating the condition is true. Now it switches from SLEEPING to READY, and when the scheduler decides, its execution is resumed inside the monitor.

The last sentence is a bit of a simplification. The good practice is that the task will check for the condition after locking the mutex – even if it was signalled that the condition is true – this is the so-called Mesa semantics (or signal-and-continue), as explained in detail in the Docbook.

Monitor structure 
{
  SLEEP_QUEUE condition;
  MUTEX lock; 
}
// general procedure:
acquire monitor lock;
while (!condition) /* predicate is false */
{
             /* atomically sleep+release lock */
              disable preemption
              sleep(condition)
              release monitor lock
              enable preemption
              /* when signalled wake up here */
              acquire monitor lock
} 
/* condition satisfied, lock acquired */
doWork(); 
wake(condition);
release monitor lock;
return;