This is a document I found online, where the author’s goal is to design a simple embedded operating system that implements a basic task scheduler. As the author mentioned, although it cannot be called an operating system, it embodies the essence of a small embedded operating system. This serves as excellent learning material for us, providing a glimpse into the nature of operating systems, which I am sharing today.
Multitasking Mechanism
In fact, in a single CPU scenario, there is no real multitasking mechanism; only different tasks take turns using the CPU, so it is essentially still single-tasking. However, due to the CPU’s very fast execution speed, combined with frequent and rapid task switching, we perceive that many tasks seem to be running simultaneously. This is what is referred to as multitasking mechanism.
The characteristic of real-time systems is that the delay is predictable, allowing a response to certain signals within a specified time (usually at the millisecond level).
Task States
Tasks have the following characteristics: a task cannot run at any time, and a running task cannot guarantee that it will occupy the CPU until it finishes. Generally, there are states such as ready, running, and suspended.
-
Running State: A task in the running state is one that is currently using the CPU. At any moment, there can only be one running task.
-
Ready State: A task in the ready state is runnable and waiting for a task to release the CPU.
-
Suspended State: A state where certain conditions are not met, preventing the task from running.
How to Transition to Ready State
INT32U OSRdyTbl; /* Ready Task Table */
The above defines a 32-bit variable, where each bit represents a task, with 0 indicating a suspended state and 1 indicating a ready state. It records the readiness status of each task, referred to as the ready table. OSRdyTbl is defined as a 32-bit variable, corresponding to 32 tasks. Of course, if defined as 64 bits, it can support up to 64 tasks. Thus, two macros can be defined to change the task’s state to ready or suspended.
/* Register a ready task in the ready table */
#define OSSetPrioRdy(prio) { OSRdyTbl |= 0x01<<prio;} // Set the corresponding bit to 1
/* Remove a task from the ready table */
#define OSDelPrioRdy(prio) { OSRdyTbl &= ~(0x01<<prio); }// Clear the corresponding bit
Tasks are independent of each other and do not call each other. All tasks are logically equal. Since tasks cannot see each other, information transfer among them cannot be done face-to-face. This necessitates various communication mechanisms such as semaphores, message mailboxes, queues, etc.
What is Preemptive Scheduling?
The concept of scheduling simply means that the system selects an appropriate task to execute among multiple tasks. How does the system know when to execute which task? A unique priority level can be assigned to each task, and when multiple tasks are ready at the same time, the one with the higher priority is executed first. At the same time, the task’s priority also serves as its unique identifier. The code operates based on this identifier.
所谓 preemptive scheduling 是指：once a higher-priority task appears in the ready state, it immediately deprives the current task of its running rights, allocating the CPU to the higher-priority task. This way, the CPU always executes the task with the highest priority that is in a ready condition.
Time Management in Multitasking Systems
Like humans, multitasking systems also need a “heartbeat” to maintain normal operation, and this heartbeat is called clock ticks, typically generated by a timer that produces fixed-period interrupts.
The OSTimeDly function is based on clock ticks for delays (in the clock’s interrupt service function, it decrements the delay tick count for each delayed task. If it finds that a task’s delay tick count reaches zero, it changes its state from suspended to ready.). This function’s functionality is simple: it first suspends the current task, sets its delay tick count, then performs a task switch, and after the specified clock ticks arrive, it restores the current task to a ready state.
Tasks must yield the CPU’s usage rights through OSTimeDly or OSTaskSuspend (delaying or waiting for events) to allow lower-priority tasks a chance to run.
How to Implement Multitasking?
With only one CPU, how can multiple independent programs run at the same time? To achieve multitasking, the condition is that each task is independent of each other. How can a person be independent and have private property? Tasks are the same; if a task has its own CPU, stack, program code, and data storage area, then this task is an independent task. (The CPU is obtained through multitasking mechanisms, while the others need to be allocated by you.)
TIPS:
If a task is running a public function (like printf) and is preempted by another higher-priority task, when this higher-priority task also calls the same public function, it is very likely to corrupt the original task’s data. This is because two tasks may share a set of data. To prevent this situation, two measures are commonly adopted: reentrant design and mutual exclusion calls.
In a reentrant function, all variables are local variables, and local variables are temporarily allocated space during the call. Therefore, when different tasks call this function at different times, the storage space allocated for the same local variable does not interfere with each other (in the task’s private stack). Additionally, if a reentrant function calls other functions, those called functions must also be reentrant.
Methods for achieving mutual (exclusive) access relate to interrupts, disabling scheduling, mutual exclusion semaphores, counting semaphores, etc.
How a Task Can Own Its Program Code
Regarding how to implement multitasking, first is the program code; each task’s program code is like a function, similar to the bare-metal program of 51, where each task is a large loop. Then there is the data storage area; since global variables are shared by the system and tasks, they are not private to the task, so this data storage area refers to the task’s private variables. How can they become private?
Local variables too. The compiler stores local variables on the stack, so it’s easy; as long as the task has a private stack, it suffices.
TIPS:
Critical resources are shared resources that only one task is allowed to use at a time. The segment of a program that accesses critical resources in each task is called the critical section.
In a multitasking system, to ensure the reliability and integrity of data, shared resources must be accessed mutually (exclusively), so global variables (except read-only ones) cannot be accessed simultaneously by multiple tasks, meaning that when one task is accessing, it cannot be interrupted by other tasks. Shared resources are a type of critical resource.
How a Task Can Own Its Stack and Data Storage Area
The private stack serves to store local variables and function parameters. It is a linear space, so a static array can be requested, pointing the stack pointer SP to the first element of the stack array (increasing stack) or the last element (decreasing stack). This creates an artificial stack. Each task also needs a variable to record its stack pointer, stored in the Task Control Block (TCB).
What is a Task Control Block?
Each task in the system has a task control block that records the execution environment of the task. This task control block is relatively simple, containing only the task’s stack pointer and delay tick count. The task control block is the task’s ID card. It connects the task’s program with its data, and by finding it, all of the task’s resources can be obtained.
How a Task Can Own Its CPU
Finally, let’s look at how tasks “own” their CPU. With only one CPU, all tasks share it and take turns using it. How can this be achieved? First, let’s look at the interrupt process. When an interrupt occurs, the CPU saves the current program’s running address, registers, and other scene data (generally saved on the stack) and then jumps to execute the interrupt service program.
After completion, the previously saved data is loaded back into the CPU, returning to the original program for execution. This achieves the interleaved execution of two different programs.
Doesn’t this idea allow for multitasking? By mimicking the interrupt process, task switching can be achieved. During task switching, the current task’s scene data is saved in its task stack, and the data of the task to be run is loaded from its task stack into the CPU, changing the CPU’s PC, SP, and registers, etc. It can be said that task switching is the switching of the task's running environment.
The task’s running environment is stored in the task stack, meaning that the key to task switching is to assign the task’s private stack pointer to the processor’s stack pointer SP.
Create a task. It receives three parameters: the task’s entry address, the start address of the task stack, and the task’s priority. After calling this function, the system initializes the task stack based on the user-provided parameters and saves the stack pointer in the task control block, marking the task as ready in the ready task table. Finally, it returns, and a task is successfully created.
When a task is about to run, it obtains its stack pointer (stored in the task control block) to load these registers from the stack into the corresponding positions in the CPU.
How to Implement Preemptive Scheduling?
Priority-based preemptive scheduling means that once the highest priority task is in the ready state, it immediately preempts the running low-priority task’s CPU resources. To ensure that the CPU always executes the highest priority task that is in the ready condition, after each task state change, the system checks if the currently running task is the highest priority task among the ready tasks; otherwise, a task switch occurs.
When does the task state change? There are two situations:
1. A high-priority task actively requests to suspend itself to yield the processor for some resource or delay, allowing a low-priority task in the ready state to execute. This scheduling is called task-level switching. For example, when a task executes OSTimeDly() or OSTaskSuspend() to suspend itself, it falls under this category.
2. A high-priority task, due to the arrival of clock ticks or after the completion of interrupt handling, causes the kernel to discover that a higher-priority task has execution conditions (such as the timeout of a delayed clock), and it directly switches to execute the higher-priority task after the interrupt. This scheduling is also known as interrupt-level switching.
Suspending/Resuming Tasks
-
Suspending a Task
By using OSTaskSuspend(), a task can be actively suspended. OSTaskSuspend() will remove the task from the ready task table and finally restart the system scheduling. This function can suspend the task itself or other tasks.
2. Resuming a Task (OSTaskResume())
This function allows a task suspended by OSTaskSuspend or OSTimeDly to regain its ready state, followed by task scheduling.
This article is sourced from the internet, freely conveying knowledge, and copyright belongs to the original author. If there are copyright issues with the work, please contact me for deletion.
Past Recommendations
“Complete Guide to Embedded Linux Drivers”