This blog presents a conceptual overview of inter-task communication based on Signals and their corresponding services within RK0. Consider uniprocessor environments. Refer to the RK0 Docbook for 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.
Task A:.. L1: wait(proceed).. | Task B:.. L2: signal(proceed).. |
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.
A bilateral synchronisation would be depicted as:
Task A:... . | Task B:.. L2: signal(proceed).. |
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.”
Busy wait (or spin-locking)
The most simple form of coordination is to coordinate tasks using busy waits, which are task polls: they actively wait for the presence of an event, consuming CPU time while waiting – it acquires CPU just to check for the condition – it is ‘spinning’.
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.
On multi-processor kernels, due to true parallelism, when context switching is not possible (or desirable) and the locking is brief, spinning can provide a better response than putting the waiting CPU to sleep.
Blocking
For uniprocessor environments, it is more efficient to block a task that waits for a signal.
Every blocking kernel call in RK0 can be bounded to a maximum waiting time.
INTER-TASK COORDINATION/SYNCHRONISATION MECHANISMS
In this section, we generalise mechanisms for inter-task coordination and point to the RK0 implementations.
Direct Signals (Task Notification)
Each task might have a 32-bit number associated with its control block, so it can register a combination of up to 32 events by assigning 1 event/bit. A notifier task will set one or more bits on a task’s event register. A task can check if a combination of events has happened by inspecting its event register. A combination of required events that were satisfied is consumed; that is, bits are cleared. If no condition is satisfied, the task (optionally) goes to sleep to be waken when the event(s) are present.
Semaphores
A Semaphore is an ‘event counter’, meaning that events accumulate up an arbitrary maximum positive number (there are different implementations, but in RK0 semaphores have unsigned counters, meaning they cannot be less than 0).
A Semaphore can be understood as a ‘credit tracker’ because its counter often represents the count of a resource, say, the number of empty or full slots on a buffer. Tasks will post (signal) and pend (wait) on semaphores to notify and check/wait for an event, respectively.
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.
A Binary Semaphore is a specialisation that counts up to 1. It suits when the number of occurrences of an event is not relevant to the handler. Binary Semaphores are also commonly used for mutual exclusion (as a one-token entry region), although not always appropriate.
Mutex Semaphores (Locks)
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.
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 Priority Inheritance
Monitors
In RK0, Monitors are implemented using the Condition Variable Model, an association of locks and sleep queues that are manipulated attomicaly over a exposed interface. The idea is to guarantee a single tak can manipulate a program region, to access (and allow others to) a shared resource, free of race conditions.
Thus, a Sleep Queue+Mutex composition can handled by helper methods:
kCondVarWait(&sleepq, &mutex, timeout)kCondVarSignal(&sleepq)kCondVarBroadcast(&sleepq)
These helpers follow the Pthreads Condition Variables semantics, which in turn are aligned with Mesa Monitors.
/* mesa monitor pseudo code */
procedureX:
lock(); /* entry queue */
/*-shared data representing a state
*/
STATE sharedData;
/* each sleep queue is associated to a condition*/
SLEEPQ cond1, cond2, ... conN;
/*-entered the monitor-*/
while(a condition is false)
{
/* unlock monitor and sleep for condition, atomically */
/* now other task can enter */
atomic(unlock, sleep(condition));
/*-when waking, lock monitor -*/
lock();
}
/*- proceed, monitor is locked -*/
/* still active, feeling good */
doStuff(sharedData);
/* manipulating sharedData led to condK to be true */
/* signal a task waiting for condK */
signal(condK);
unlock();
/*-unlock and leave-*/
Refer to the RK0 docbook to see how to handle Condition Variables.
All these mechanisms ensure precedence and coordinate actions but do not exchange data. Combining both can be achieved with Message-Passing mechanisms, which will be covered in another blog. Meanwhile, you can gather detailed information about Message Passing on the RK0 Docbook.
RK0 
/* comment here */