Data structures and linked lists in GeMRTOS is a very efficient mechanism to deal with events during runtime. In this video, it is shown the basic principles of data structure in GeMRTOS.
GeMRTOS is a Generic, eMbedded, Multiprocessor Real-Time Operating System. It is based on control blocks and a code structure that makes it flexible and adaptable for modern embedded real-time applications.
GeMRTOS categorizes events into three types:
- Timed events: these events occur when the system time reaches a specified time,
- External events: these events are generated by peripheral devices and are usually associated with interrupt service routines, and
- Internal events: these events occur when certain conditions are met during runtime. Internal events include system exceptions and internal signals.
The GeMRTOS controller handles timed events and external events, and generates the corresponding processor interrupt requests.
The GeMRTOS controller handles timed events and external events, and generates the corresponding processor interrupt requests.
GeMRTOS control blocks #
The overall system state is stored in control blocks that are highly linked among them. Events change the system status and consequently the information in the control blocks and the connections among them change accordingly.
The following control blocks are defined natively by GeMRTOS:
- Kernel control block (GS_KCB), which centralizes the information of the operating system.
- Task control block (GS_TCB), which contains the runtime information of a system task.
- Event control block (GS_ECB), which is created for each possible event during runtime
- Scheduling list control block (GS_LCB), which is used for the GeMRTOS hybrid partition scheduling.
- Processor control block (GS_RCB): which is used to keep track of the status of each one of the system processors.
- Resource control block (G_RCB): which is responsible for implementing each one of the various system resources such as semaphores or message queues during runtime.
- Signal control block (GS_SCB): which is used to define the internal exceptions.
All of these control blocks are highly linked in order to maintain the status of the systems during runtime. Each one of the control blocks contains different fields to support the different linked list to which it can be linked.
Data structures and linked lists in GeMRTOS #
The GeMRTOS holds the system information in control blocks linked among them in order to preserve the system consistency during runtime. Several linked list structures are established among control blocks. Figure 1 shows the components of a linked list in GeMRTOS:
- root block: this is the root block of the list containing the first element pointer field that points to the first element of the linked list. The root block may be a different data structure from the rest of the blocks of the linked list. An empty list has only the root block, with a NULL value, and
- list element: this is a block of the nodes of the linked list. Each list element contains a next element pointer field to the next element and may contain a previous element pointer field to the previous element.
Figure 1.
The list elements may be sorted according to certain criteria stored in a sorting value field of the list element.
Event time linked list (ECBTL) #
The event time linked list (ECBTL) supports timed events. The Occurrence Time field (ECBValue) of each event control block is used to sort them in the ECBTL list. The GeMRTOS controller implements system time internally removing the need for a timer interrupt. The GeMRTOS controller compares the current system time to the closest occurrence time event (the ECBValue of the first element in the ECBTL list).
If the system time is greater than or equal to the occurrence time (ECBValue) of the first event control block in the ECBTL list, the GeMRTOS controllers generates a processor interrupt. Timed interrupts are thus supported by inserting an event control block into the event time list (ECBTL). The interrupt service routine will handle the event based on its type. Various types can be defined including: periodic task releases, task deadlines, and timeouts, among others.
Resources linked lists (RCBs) #
The resource control blocks help with resource management Two main lists are defined by the resource control blocks:
- The resource waiting event list (RCBWEL), in which event control blocks are sorted based on the priority of the requesting task. Request events can be associated, depending on the type of resource, with semaphore requests, message senders or data producers, among others, and
- The resource granted event list (RCBGEL), in which the events associated with semaphore grants, message receivers, or data consumers, depending on the type of the resource, are linked.
It is possible to create as many resource control blocks as needed. The type of the resource (semaphore, message queue, etc.) defines the actions to be executed each time an event occurs.
Scheduling linked lists #
The scheduling list control blocks (LCBs) are used to manage task and subsystems scheduling. The scheduling list control block defines two main linked lists:
- The task ready list (TCBRDYL), which sorts task control blocks based on the ready priority assigned to each task, and
- The task running list (TCBRUNL), which sorts the task control blocks based on the execution priority assigned to each task.
Task preemption occurs if the lowest execution priority is lower than the highest ready priority. There may be as many scheduling list control blocks as the designer sees fit. Task control blocks (TCBs) associated with tasks that are neither ready nor running are linked to the task waiting list depending on the status of the tasks and events. Task control blocks are linked to their associated event control blocks, for example, a periodic running task may grant a resource and such a resource may have a time out.
GeMRTOS modifies the linked lists according the event that occur during runtime. Consequently, the behavior of the system is easily determined according to how the system status is change for each event. GeMRTOS callbacks allow to extend it to new runtime behaviors and types of tasks, resources, signals and scheduling strategies.
