Embedding concurrency means multi-threading or multi-tasking, which is basically implemented using systems like Linux or RTOS. In RTOS, task scheduling mainly includes preemptive and time-slicing scheduling, and the specific differences will not be detailed here. This chapter contains some terms related to concurrency, such as concurrency, criticality, resources, deadlocks, etc. It is best to read books on RTOS systems in detail.

Disclaimer: This article is based on the book “Design Patterns for Embedded Systems in C”. It mainly serves as a note, adding a bit of personal understanding, to share and discuss with everyone.

1. Design Patterns for Concurrency and Resource Management

There are a total of 8 patterns. The first two, cyclic execution pattern and static priority pattern, provide two different methods for scheduling tasks or threads. The next three patterns, critical section pattern, guarded call pattern, and queue pattern, aim to solve the problem of serial access to resources in a multi-tasking environment. The rendezvous pattern discusses how multiple tasks synchronize in different ways. The last two patterns focus on preventing deadlock issues. I hope the patterns below can inspire you.

1.1 Cyclic Execution Pattern

The cyclic pattern features a very simple way to call multiple tasks, allowing all tasks equal opportunities to run, but it cannot respond timely to urgent events. It is generally used in resource-constrained systems, avoiding the overhead of RTOS and not requiring complex task scheduling. Simplicity is its greatest advantage.

1.1.1 Pattern Structure

CyclicExecutive has a controlLoop() function that can repeatedly call the run operation of each task. It also needs to wait for the task to finish before calling the next task.

1.1.2 Roles

1.1.2.1 Abstract Task (AbstractCEThread)

Provides an interface for threads by declaring the run() function. It is used for the task function that is executed cyclically.

1.1.2.2 Cyclic Control (CyclicExecutive)

This class is used to cyclically execute each task. It also has a global stack and static data needed by the tasks themselves. A variant of the pattern is time-triggered cyclic execution, in which CyclicExecutive sets the CycleTimer to start each cycle. This variant allows each function to be executed in the cycle class.

1.1.2.3 Cyclic Timer (CycleTimer)

The diagram shows a timer with ‘0, 1’, which is optional. When the timer expires, it can call an interrupt or return TRUE to the hasElapsed() function. CyclicExecutive will call start() to start timing for the next cycle.

1.1.2.4 Concrete Task Implementation (ConcreteCEThread)

Each ConcreteCEThread has its own run() function for specific task implementation.

1.1.3 Effects

As mentioned earlier, the advantage of this pattern lies in its simplicity. On one hand, it is difficult to cause scheduling errors, and on the other hand, it responds insufficiently to urgent events, making it only suitable for devices with limited memory. Another downside is that communication between tasks needs to be considered; for example, if one task needs data from another task, the data can only be stored in global memory or shared resources. We should avoid defining too many global variables, as it may lead to management difficulties and memory wastage.

1.1.4 Implementation

The implementation of this pattern is very simple. In most cases, cyclic execution may only be called in the main() function of the application.

1.2 Static Priority Pattern

Most real-time operating systems are based on the static priority pattern. So, to use this pattern, you can directly port an RTOS system. The complexity and completeness of this pattern cannot be compared to that of an RTOS system; however, reading this can help you understand task scheduling in RTOS, as it is based on this framework. The static priority pattern can assign priorities to tasks, allowing better responses to high-priority timing.

1.2.1 Pattern Structure

Except for the three classes in the lower right corner, AbstraceStaticThread, SharedResource, and ConcreteStaticThread, the others are generally implemented by RTOS.

1.2.2 Roles

1.2.2.1 Abstract Thread (AbstraceStaticThread)

This is an abstract class that provides the run() function for the scheduler to run.

1.2.2.2 Concrete Thread (ConcreteStaticThread)

The ConcreteThread implements the run() function as a specific implementation of AbstraceStaticThread.

1.2.2.3 Mutex

It is a mutex semaphore class used for serial access to SharedResource. When a task calls the lock() function of the mutex, other tasks attempting to lock the same mutex will be blocked until the mutex is unlocked or times out.

1.2.2.4 Queue (PriorityQueue)

PriorityQueue sorts pointers to StaticTaskControlBlock based on priority, meaning that the queue stores the queue order of each thread. Generally, in RTOS, there are multiple queues, such as ready queues and blocked queues, and the scheduler will take the first one from the ready queue for execution.

1.2.2.5 Resource (SharedResource)

This resource may be shared among one or more threads, and it is necessary to ensure the normality of the resource, which will be explained in the following patterns regarding resource sharing issues.

1.2.2.6 Stack

Each AbstraceStaticThread has a stack for return addresses and passing parameters.

1.2.2.7 Scheduler (StaticPriorityScheduler)

The simplest rule: always run the highest priority ready thread. In RTOS, task creation, task switching, etc., all need to go through the scheduler. After task creation is successful, the task will be added to the ready list according to its priority, and tasks that are suspended will be added to the suspended list. The system has a tick clock interrupt or other means to switch tasks; a common method to find the next running task is to take it from the ready list. Another method is hardware-based, using the hardware instructions provided by the processor, which requires hardware support.

1.2.3 Effects

The static priority pattern can provide timely responses to events, optimize CPU usage for large programs, and avoid the waste of single-threaded CPU usage while waiting. With the support of RTOS, inter-thread communication is also well guaranteed, using mailboxes and semaphore mechanisms, which avoids excessive global variables.

1.2.4 Implementation

The best way is to directly port a mature RTOS system to implement it. Using this pattern requires a design in the early development phase regarding memory allocation, priority allocation, etc., and requires planning before program development; otherwise, various problems may arise later. The complexity is higher than that of single-threading, so you need to have a deep understanding to master the application of RTOS systems. However, don’t be afraid; RTOS is still a medium-sized system, and you can study the source code when you have time, as RTOS’s use of pointers and data structures is very mature and efficient.

1.3 Critical Section Pattern

The critical section pattern is the simplest way to coordinate tasks. It directly prohibits task switching, allowing safe access to resources only within the critical section, and then exiting the critical section.

1.3.1 Pattern Structure

The pattern structure is very simple; resources are accessed only after entering the critical section. The scheduler does not participate in the opening and closing of the critical section, only providing services to prohibit and restart task switching. If the scheduling system does not provide it, the critical section can be managed at the hardware level by directly using C’s asm to enable and disable interrupt handling.

1.3.2 Roles

1.3.2.1 Critical Section (CRShaaredResource)

This element is used to prohibit task switching to prevent simultaneous access to resources. In this example, the protected resource is the Value attribute, and related services must use the critical section for protection; the setValue() and getValue() functions must be independently implemented within the critical section.

1.3.2.2 Task Collection (TaskWithSharedResource)

This element represents all tasks that want to access shared resources. These tasks do not know the method of protecting resources, as it is encapsulated within the shared resource.

1.3.3 Effects

The characteristic of this pattern is to prohibit the switching of scheduled tasks, and more strictly, to prohibit all interrupts. Note that once the element exits the critical section, task switching will resume, and using the critical section will inevitably affect the timing of other tasks, so try to keep the critical section time short.

1.3.4 Implementation

Most RTOS systems directly provide functions that can be called.

1.4 Guarded Call Pattern

The guarded call pattern provides a locking mechanism for serial access, preventing calls from other threads to resources once locked. In RTOS systems, this is simply referred to as a semaphore. Using this pattern may lead to priority inversion or deadlock issues.

1.4.1 Pattern Structure

In this pattern, multiple PreemptiveTasks access GuardedResource through their functions. When a thread calls a semaphore that is already locked, the scheduling service will add that thread to the blocked queue, waiting for that semaphore to be released or to time out before unblocking. The scheduling service must implement the lock() function as a critical section to prevent potential race conditions.

1.4.2 Roles

1.4.2.1 Shared Resource (GuardedResource)

This class uses a mutex semaphore for mutually exclusive access. Before accessing the resource, the lock() function associated with the Semaphore is executed. If the Semaphore is in an unlocked state, it becomes locked; if it is in a locked state, the Semaphore will block this task by resetting the signal.

1.4.2.2 Task (PreemptiveTask)

The task that accesses the shared resource.

1.4.2.3 Mutex Semaphore (Semaphore)

It serially accesses GuardedResource. The lock() function is called before accessing the resource, and the release() function is called after accessing the resource to release the semaphore.

1.4.3 Effects

This pattern provides timely access to resources while simultaneously preventing multiple accesses that could lead to data corruption and system errors. If the resource is not locked, access to the resource will not be delayed.

1.4.4 Implementation

By using the semaphore functions provided by RTOS. Generally, interfaces for creating semaphores, destroying semaphores, locking, and unlocking will be provided.

1.5 Queue Pattern

The queue pattern is a common implementation of asynchronous communication between tasks. It provides a way for communication between tasks. The sender places messages into the queue, and after a period, the receiver retrieves messages from the queue. It can also achieve serial access to shared resources by queuing access messages and processing them later, thus avoiding simultaneous access to shared resources.

1.5.1 Pattern Structure

QUEUE_SIZE declaration determines the maximum number of elements the queue can hold. It must be large enough to handle the worst-case scenario, but not too large to avoid wasting memory.

1.5.2 Roles

1.5.2.1 Message

It can be anything, from simple data values to detailed data structures for sending messages.

1.5.2.2 Message Queue (MessageQueue)

MessageQueue is the storage for exchanging information between QTasks. It provides the getNextIndex() function to compute the next valid index value. The insert() function inserts a Message at the head position and updates the head index. The remove() function can be used to delete the oldest message. iFull() and isEmpty() are used to check if the queue is full or empty.

1.5.2.3 Mutex Semaphore (Mutex)

It is a mutex semaphore, similar to that described in the static priority pattern.

1.5.2.4 Task (QTask)

QTask is the client of the MessageQueue, either calling insert() to insert new messages or calling remove() to access the oldest data.

1.5.3 Effects

The queue pattern is very useful when data is passed between tasks. The mutex can ensure that the queue itself is not damaged due to simultaneous access. Compared to the guarded call pattern, the queue pattern does not receive data as timely.

1.5.4 Implementation

The simplest implementation of a queue is an array of message elements. It has simple advantages but also lacks flexibility and has fixed space occupancy issues. More commonly, linked lists are used to implement queues. MessageQueue can also add multiple buffers, one queue for each priority, thus implementing priority strategies, or based on message priority, inserting elements into the queue. In complex systems, predicting the optimal queue size is not feasible; if using an array to implement the queue, there may be issues of exceeding capacity. In such cases, an additional buffer queue can be used as temporary storage.

1.6 Rendezvous Pattern

Tasks must synchronize in different ways. Synchronization may occur due to shared single resources or waiting for signals, etc. Both queue patterns and guarded call patterns can achieve this. But what if the conditions required for synchronization are more complex? The rendezvous pattern solves this problem. Only when all tasks meet the synchronization conditions can they continue running.

1.6.1 Pattern Structure

At least 2 threads need to synchronize, each having a unique Rendezvous.

1.6.2 Roles

1.6.2.1 Aggregation (Rendezvous)

Used to manage synchronization. It has two methods: the reset() function resets the synchronization criteria to the initial condition. The synchronize() function is called when a task wants to synchronize. If the criteria are not met, the task is blocked. This can usually be implemented using observer patterns or guarded call patterns.

1.6.2.2 Counting Semaphore (Semaphore)

This is usually a counting semaphore, with interface functions for creating, destroying, locking, and releasing standard locks. It is used to store the current number of tasks that meet the synchronization conditions. When it equals the preset value, the synchronization condition is met.

1.6.2.3 Thread (SynchronizingThread)

Represents each thread using Rendezvous for synchronization.

1.6.3 Effects

In this pattern, two or more tasks can only continue running or call back functions when they simultaneously meet a certain condition.

1.6.4 Implementation

This pattern can be implemented using the previous observer pattern or guarded call pattern. If using the observer pattern, tasks must register the address of the function, which will be called when the synchronization condition is met. If using the guarded call pattern, each Rendezvous object has a unique semaphore; when tasks want to synchronize, they call the synchronize() function to inform the Rendezvous. When the Rendezvous meets the synchronization condition, it releases the semaphore, and the tasks are subsequently released to run according to the usual scheduling strategy.

1.7 Simultaneous Locking Pattern

First, ignoring errors caused by the software itself, deadlocks require satisfying four conditions:

1. Mutually exclusive resources.

2. Some resources are already locked when requesting other resources.

3. Resource locking is allowed to be interrupted.

4. There is a circular wait condition.

Deadlocks can be avoided by breaking any one of these four conditions. The critical section pattern breaks conditions 1 and 3. The queue pattern avoids the occurrence of condition 1.

The simultaneous locking pattern avoids deadlocks by breaking condition 2. The pattern works in an all-or-nothing manner. Either all required resources are locked at once, or none are locked. Simply put, when a thread needs a certain resource, it can only proceed if it successfully locks all resources together, thus avoiding a deadlock caused by two threads requesting each other’s resources.

1.7.1 Pattern Structure

Generally speaking, MultimasteredResource is part of a collection of different resources managed by a number of ResourceMasters, each managing such a collection.

1.7.2 Roles

1.7.2.1 Resource Management (MultimateredResource)

This element is managed by multiple ResourceMasters, and it has its own mutex semaphore to avoid simultaneous lock requests. Using QueryMutex must be done through the tryLock() function to determine whether all attempts to lock will succeed or fail through ResourceMasters.

1.7.2.2 Mutex (QueryMutex)

This is a normal mutex semaphore, unlike the previous one; it provides a tryLock() function. This function serves the same purpose as the lock() function, which is to lock, but the tryLock() function will return an error code if the lock fails instead of blocking the current thread.

1.7.2.3 Client (ResourceClient)

This element is a client that wants to access all resource collections at once to avoid deadlocks. It directly accesses MultimateredResource until it successfully receives locks on ResourceMasters. After using the resources, it releases them.

1.7.2.4 Control Lock (ResourceMaster)

ResourceMaster controls the locks of the entire resource collection.

1.7.3 Effects

The simultaneous locking pattern prevents deadlocks by eliminating necessary condition 2, by locking all required resources at once or none at all. However, this may increase the delay in executing other tasks and may occur even without actual resource conflicts. This situation is more evident when resources are more numerous and widespread. Furthermore, the pattern does not solve the priority inversion problem; in fact, it may exacerbate it.

1.7.4 Implementation

It is necessary to ensure that the tryLock() function is successfully locked on MultimasteredResource before attempting to do so.

1.8 Ordered Locking

Ordered locking is another method to ensure that deadlocks do not occur, this time by preventing condition 4 from happening. By sorting resources and requiring clients to always lock resources in that specified order, it becomes impossible to form a circular wait condition.

1.8.1 Pattern Structure

1.8.2 Roles

1.8.2.1 Lock (Mutex)

As with the above pattern, it provides two basic functions: lock() and release().

1.8.2.2 Resource Management (OrderedResource)

This is the core of the pattern. It has a resourceID property, which is a unique ID associated with each resource, and is associated with ResourceList. The locking rule executed by this class is always: if the resource’s resourceID is greater than the maximum resourceID of any locked resource, the resource can only be locked. The ResourceClient must first call the lockDyadic() function and then add to the resource list. After completing operations on the resource, the releaseDyadic() function is called. The book refers to this access as dyadic; unlike dyadic, unary access is done internally, locking, using the resource, and unlocking. Dyadic access can remain locked until the resource is used up and then released.

1.8.2.3 Client (ResourceClient)

Represents the collection of elements that want to call OrderedResource services. Clients do not need to know anything about the resourceID itself.

1.8.2.4 Resource List (ResourceList)

In this element, if the passed resourceID is greater than the maximum of the locked resources, addLock() returns success; otherwise, it returns failure.

1.8.2.5 Used Resources (ResourceReference)

This is just an array of resourceIDs included in the ordered list. Simply saving a maximum value is not enough because many resources may be locked at any time.

1.8.3 Effects

The pattern eliminates deadlocks by ensuring that all clients lock resources in the same order. This pattern requires analysis and planning of resource ordering during design. For example, if there are two threads that need resources A, B, and C, if thread 1 locks in the order A, B, C, while thread 2 locks in the order C, B, A, a deadlock may occur. Therefore, this pattern is designed to ensure that resources are locked in the specified sequence.

1.8.4 Implementation

The pattern’s implementation requires adding an extra resourceID to each OrderedResource and ensuring that each OrderedResource’s resourceID is greater than any currently locked resourceID in the logic of ResourceList. Additionally, the list of already locked resourceIDs must be maintained so that when an OrderedResource is released, other resources can be appropriately locked.

The most common implementation of ResourceList is an array of integers representing the order of locking.