Preemptive multitasking in Z80 assembler
- Tutorial
A slow processor and a small amount of RAM - this does not mean that it is impossible to implement preemptive multitasking on such a platform. Moreover, the main purpose of organizing a multitasking environment is the efficient use of processor time so that the processor does not stand idle while some programs are waiting for an event, but are used by other programs. Even on platforms like the ZX Spectrum (Z80 3.5MHz, 48-128kB of RAM), or the 8-bit AVR microcontrollers, organizing preemptive multitasking makes a lot of sense.
I bring to your attention our own implementation of the multitask dispatcher on assembler Z80 (ZX Spectrum), which is not part of any OS, but can be used separately. There is nothing superfluous in it - only the organization of thread execution and synchronization between them. The dispatcher can be used as an integral part of a software project, as the basis for creating a more serious dispatcher for the OS, or as training material.
The architecture was inspired by the concepts of the Windows NT kernel when I studied the ReactOS sources [2]. Of these concepts, a minimum was implemented that gives the necessary features of multitasking. A more complete implementation is possible, but starting from some point, the additional functions cease to be justified because of their cost on small computers.
Threads [1] are the basic units controlled by the dispatcher. Each thread has executable code and its own stack, which can be used to store return addresses from routines and other information. The dispatcher switches execution from one thread to another so that, if possible, all threads execute as much code as they want.
Each thread can be in one of three states: waiting (waiting), readiness for execution (ready) and execution (running). In the idle state, the dispatcher prevents the thread code from executing until the event that the thread is waiting for occurs. A thread in a ready state will receive control from the controller as soon as possible. Only one thread can be in execution state, since the system has only one processor. Its code is executed by the processor until the thread enters the standby state, or until the preemption occurs, that is, the dispatcher on its own initiative does not transfer control to another thread.
The number of threads in the system is fixed. New threads do not start, and old ones do not end. For microcontroller applications or as part of a separate application, this limitation is not significant. But the dispatcher is simplified and its work is accelerated.
Each thread has a priority. If there are several threads in a ready state, then the dispatcher chooses to execute one of them whose priority is the highest. In the current version of the dispatcher, the priority of the stream cannot be changed during operation. The dynamic priority of flows is costly to implement, although this capability is necessary to solve the problem of priority inversion [1].
The priority of all threads in the system is different. This means that the dispatcher does not organize pseudo-parallel code execution with the same priority, quickly switching the processor from one thread to another (“Round-Robin”). But in fact, this restriction is not significant. Pseudo-parallel execution of several threads slows down each of them. Given the limited resources of computer memory, it is better to organize the sequential execution of such programs. The main benefit of preemptive multitasking is not the possibility of pseudo-parallel execution, but the efficient separation of the processor between short-term tasks of processing requests from important sources (for example, responding to a user pressing a key on a keyboard) and lengthy work of programs whose completion time is not critical (compilation, archiving) . If assigned to a stream,
Based on them, the thread can go into the standby state by calling the corresponding function of the dispatcher. The waiting entity may or may not be signaled. If it is signaled, then the wait function returns immediately, and the thread continues execution. If the object is not signaled, then the thread goes into a waiting state, and other threads that are in a ready state begin to execute. As soon as the object is signaled, the waiting thread will return to the ready state and will receive control from the dispatcher as soon as possible. Operating systems usually have waiting objects such as events, semaphores, mutex, etc. Two types of Events are implemented in the dispatcher under consideration: Notification Event (Manual Reset), and Synchronization Event (Auto-Reset) .
Processor status. The abbreviation in Windows NT stands for “Interrupt Request Level” [3], although this does not exactly reflect the meaning of the concept. There are three IRQL levels in the described dispatcher. PASSIVE_LEVEL - this is when the processor is currently executing the code of one of the threads. At this time, the executable thread may be crowded out by another thread, or the processor may begin to process a hardware interrupt. DISPATCH_LEVEL - the processor is in this state during execution of the critical dispatcher code. For example, switching execution between threads is an operation consisting of many actions. At this time, it cannot be said that the processor executes this or that thread - it is as if it is “between them”. In this regard, crowding out code executed in DISPATCH_LEVEL mode is not possible. Finally,
Unlike Windows NT, there is no place in my dispatcher where the current IRQL level is stored. There are also no functions that increase or decrease it explicitly. But IRQL as a concept is implied in the system and objectively exists in it, albeit implicitly.
User code can be executed either in threads (on PASSIVE_LEVEL), or in a user interrupt routine (ISR) in DIRQL. The set of available dispatcher functions is different for different IRQLs. Violation of IRQL requirements leads to a system crash.
User code executing in threads should not prohibit interrupts. ISR code is executed with forbidden interrupts, and therefore, on the contrary, they cannot be allowed. As for DISPATCH_LEVEL, in Windows NT in this mode interrupts are not prohibited, and in my dispatcher, for simplicity, interrupts are disabled on DISPATCH_LEVEL.
The purpose of the functions and a description of their work are given. Details of passing parameters to these functions are given in the comments to the source code and are not duplicated here so as not to clutter up the text. The names of the functions, if possible, are taken identically to the names of similar functions of the Windows NT kernel [2,3].
Disable the alarm of an event wait object. Can be invoked at any IRQL level.
Signal a waiting object of type Notification Event (Manual Reset). All threads that were waiting for the signaling of this object will go into a state of readiness for execution. If among them there is a thread with a higher priority than the current one, then the execution of the current thread will be supplanted in favor of the one with the highest priority.
The object will remain signaled until KeResetEvent is called.
The function can only be called on IRQL = PASSIVE_LEVEL.
The same, but for a call to IRQL> = DISPATCH_LEVEL. When this function is called from the ISR, the switching of flows, if it happens, then after the completion of the ISR.
Signal a wait object of type Synchronization Event (Auto Reset). If this object had pending flows, then one of them will go into the ready state, and the object will immediately return to the non-signaled state. The remaining threads will continue to wait. If there were no waiting threads, then the object will remain signaled until some thread calls the wait function on it, or KeResetEvent.
When several threads are waiting for the signaling of such an object, the order of their exit from the wait is not defined.
If a thread that has waited and has switched to a ready state has a higher priority than the current one, then crowding will occur.
The function can only be called on IRQL = PASSIVE_LEVEL.
The same, but for a call to IRQL> = DISPATCH_LEVEL. When this function is called from the ISR, the switching of flows, if it happens, then after the completion of the ISR.
Waiting for an object to signal (Event). If at the time of calling this function the object was signaled, then the function returns immediately. At the same time, in the case of the Synchronization Event, the object will be reset to an unsigned state. If the object was not signaled, then the current thread will go into standby mode, and the dispatcher will execute code from other threads that are in a ready state.
The function can only be called on IRQL = PASSIVE_LEVEL.
By this we mean the ability to execute a custom interrupt routine. In the form of a function, it is not highlighted, but there is a place in the dispatcher source for calling or inserting it. To interact with streams, this routine can use the functions KeSetNotifEventFromIsr and KeSetSynchrEventFromIsr and, thus, “wake up” some thread and force out another thread.
ISR execution uses a separate stack area that does not belong to any of the threads. When servicing a hardware interrupt, only the return address from the interrupt (2 bytes) is pushed onto the thread stack. Other dispatcher functions also do not abuse the stack. Therefore, you can save on stacks of threads by reserving the minimum amount of memory for them.
The rest of the manager functions are not intended to be called from user programs.
To use the dispatcher in any software project, you must configure it. In the source code, you should fill out the threads data structure for each thread. An example of filling is given in the source. The main thing to fill out is the addresses of the thread stacks. The last two bytes of the stack of each thread contain the address of its entry point. You should also specify the number of threads by setting the constant NUM_THREADS. The maximum number of threads in the system is 255.
When the system starts, all threads must be in a ready state. The last thread with the lowest priority should not go into standby mode. This thread is an analogue of the System Idle Process and does not solve any problem, but is intended to "burn" unused processor time. It recommends cyclic execution of the HALT command.
You should also configure the placement in the memory of the dispatcher itself, the table of interrupt vectors, and the ISR address of the dispatcher. The user ISR is called from the ISR manager.
The allocation of memory for waiting objects, which in principle can be an unlimited number, is left to the discretion of the user. You can store these objects on the stack, in global static variables, or connect a heap manager to the project and allocate memory for the specified objects on the heap.
The execution environment implemented by the dispatcher is characterized by situations that are problematic for preemptive multitasking systems in general [1]. These include: Starvation, Race Conditions, and Priority Inversion. The first two problems can be solved by proper system design, a reasonable distribution of tasks among the threads, a reasonable choice of their priority and the use of synchronization primitives (primarily Auto-Reset Synchronization Events). The third situation is not resolved in my dispatcher, since there are no dynamic priority for threads and synchronization objects of the Mutex type. Therefore, if this situation arises in a specific project, it should be taken into account and, if necessary, add the above funds to the dispatcher.
The source code of the dispatcher, along with a description of the data structures, function parameters and other information, can be downloaded on GitHub .
1. Wikipedia. Article " Multitasking "
2. ReactOS . Source code, ntoskrnl component
3. Windows WDK Documentation. MSDN Kernel-mode driver architecture
I bring to your attention our own implementation of the multitask dispatcher on assembler Z80 (ZX Spectrum), which is not part of any OS, but can be used separately. There is nothing superfluous in it - only the organization of thread execution and synchronization between them. The dispatcher can be used as an integral part of a software project, as the basis for creating a more serious dispatcher for the OS, or as training material.
Architecture of an Implemented Multitasking System
The architecture was inspired by the concepts of the Windows NT kernel when I studied the ReactOS sources [2]. Of these concepts, a minimum was implemented that gives the necessary features of multitasking. A more complete implementation is possible, but starting from some point, the additional functions cease to be justified because of their cost on small computers.
Threads
Threads [1] are the basic units controlled by the dispatcher. Each thread has executable code and its own stack, which can be used to store return addresses from routines and other information. The dispatcher switches execution from one thread to another so that, if possible, all threads execute as much code as they want.
Each thread can be in one of three states: waiting (waiting), readiness for execution (ready) and execution (running). In the idle state, the dispatcher prevents the thread code from executing until the event that the thread is waiting for occurs. A thread in a ready state will receive control from the controller as soon as possible. Only one thread can be in execution state, since the system has only one processor. Its code is executed by the processor until the thread enters the standby state, or until the preemption occurs, that is, the dispatcher on its own initiative does not transfer control to another thread.
The number of threads in the system is fixed. New threads do not start, and old ones do not end. For microcontroller applications or as part of a separate application, this limitation is not significant. But the dispatcher is simplified and its work is accelerated.
Each thread has a priority. If there are several threads in a ready state, then the dispatcher chooses to execute one of them whose priority is the highest. In the current version of the dispatcher, the priority of the stream cannot be changed during operation. The dynamic priority of flows is costly to implement, although this capability is necessary to solve the problem of priority inversion [1].
The priority of all threads in the system is different. This means that the dispatcher does not organize pseudo-parallel code execution with the same priority, quickly switching the processor from one thread to another (“Round-Robin”). But in fact, this restriction is not significant. Pseudo-parallel execution of several threads slows down each of them. Given the limited resources of computer memory, it is better to organize the sequential execution of such programs. The main benefit of preemptive multitasking is not the possibility of pseudo-parallel execution, but the efficient separation of the processor between short-term tasks of processing requests from important sources (for example, responding to a user pressing a key on a keyboard) and lengthy work of programs whose completion time is not critical (compilation, archiving) . If assigned to a stream,
Waiting Objects (Synchronization Objects)
Based on them, the thread can go into the standby state by calling the corresponding function of the dispatcher. The waiting entity may or may not be signaled. If it is signaled, then the wait function returns immediately, and the thread continues execution. If the object is not signaled, then the thread goes into a waiting state, and other threads that are in a ready state begin to execute. As soon as the object is signaled, the waiting thread will return to the ready state and will receive control from the dispatcher as soon as possible. Operating systems usually have waiting objects such as events, semaphores, mutex, etc. Two types of Events are implemented in the dispatcher under consideration: Notification Event (Manual Reset), and Synchronization Event (Auto-Reset) .
IRQL
Processor status. The abbreviation in Windows NT stands for “Interrupt Request Level” [3], although this does not exactly reflect the meaning of the concept. There are three IRQL levels in the described dispatcher. PASSIVE_LEVEL - this is when the processor is currently executing the code of one of the threads. At this time, the executable thread may be crowded out by another thread, or the processor may begin to process a hardware interrupt. DISPATCH_LEVEL - the processor is in this state during execution of the critical dispatcher code. For example, switching execution between threads is an operation consisting of many actions. At this time, it cannot be said that the processor executes this or that thread - it is as if it is “between them”. In this regard, crowding out code executed in DISPATCH_LEVEL mode is not possible. Finally,
Unlike Windows NT, there is no place in my dispatcher where the current IRQL level is stored. There are also no functions that increase or decrease it explicitly. But IRQL as a concept is implied in the system and objectively exists in it, albeit implicitly.
User code can be executed either in threads (on PASSIVE_LEVEL), or in a user interrupt routine (ISR) in DIRQL. The set of available dispatcher functions is different for different IRQLs. Violation of IRQL requirements leads to a system crash.
User code executing in threads should not prohibit interrupts. ISR code is executed with forbidden interrupts, and therefore, on the contrary, they cannot be allowed. As for DISPATCH_LEVEL, in Windows NT in this mode interrupts are not prohibited, and in my dispatcher, for simplicity, interrupts are disabled on DISPATCH_LEVEL.
Dispatcher functions
The purpose of the functions and a description of their work are given. Details of passing parameters to these functions are given in the comments to the source code and are not duplicated here so as not to clutter up the text. The names of the functions, if possible, are taken identically to the names of similar functions of the Windows NT kernel [2,3].
KeResetEvent
Disable the alarm of an event wait object. Can be invoked at any IRQL level.
KeSetNotifEvent
Signal a waiting object of type Notification Event (Manual Reset). All threads that were waiting for the signaling of this object will go into a state of readiness for execution. If among them there is a thread with a higher priority than the current one, then the execution of the current thread will be supplanted in favor of the one with the highest priority.
The object will remain signaled until KeResetEvent is called.
The function can only be called on IRQL = PASSIVE_LEVEL.
KeSetNotifEventFromIsr
The same, but for a call to IRQL> = DISPATCH_LEVEL. When this function is called from the ISR, the switching of flows, if it happens, then after the completion of the ISR.
KeSetSynchrEvent
Signal a wait object of type Synchronization Event (Auto Reset). If this object had pending flows, then one of them will go into the ready state, and the object will immediately return to the non-signaled state. The remaining threads will continue to wait. If there were no waiting threads, then the object will remain signaled until some thread calls the wait function on it, or KeResetEvent.
When several threads are waiting for the signaling of such an object, the order of their exit from the wait is not defined.
If a thread that has waited and has switched to a ready state has a higher priority than the current one, then crowding will occur.
The function can only be called on IRQL = PASSIVE_LEVEL.
KeSetSynchrEventFromIsr
The same, but for a call to IRQL> = DISPATCH_LEVEL. When this function is called from the ISR, the switching of flows, if it happens, then after the completion of the ISR.
KeWaitForObject
Waiting for an object to signal (Event). If at the time of calling this function the object was signaled, then the function returns immediately. At the same time, in the case of the Synchronization Event, the object will be reset to an unsigned state. If the object was not signaled, then the current thread will go into standby mode, and the dispatcher will execute code from other threads that are in a ready state.
The function can only be called on IRQL = PASSIVE_LEVEL.
User ISR
By this we mean the ability to execute a custom interrupt routine. In the form of a function, it is not highlighted, but there is a place in the dispatcher source for calling or inserting it. To interact with streams, this routine can use the functions KeSetNotifEventFromIsr and KeSetSynchrEventFromIsr and, thus, “wake up” some thread and force out another thread.
ISR execution uses a separate stack area that does not belong to any of the threads. When servicing a hardware interrupt, only the return address from the interrupt (2 bytes) is pushed onto the thread stack. Other dispatcher functions also do not abuse the stack. Therefore, you can save on stacks of threads by reserving the minimum amount of memory for them.
The rest of the manager functions are not intended to be called from user programs.
Configuring a dispatcher for a specific project
To use the dispatcher in any software project, you must configure it. In the source code, you should fill out the threads data structure for each thread. An example of filling is given in the source. The main thing to fill out is the addresses of the thread stacks. The last two bytes of the stack of each thread contain the address of its entry point. You should also specify the number of threads by setting the constant NUM_THREADS. The maximum number of threads in the system is 255.
When the system starts, all threads must be in a ready state. The last thread with the lowest priority should not go into standby mode. This thread is an analogue of the System Idle Process and does not solve any problem, but is intended to "burn" unused processor time. It recommends cyclic execution of the HALT command.
You should also configure the placement in the memory of the dispatcher itself, the table of interrupt vectors, and the ISR address of the dispatcher. The user ISR is called from the ISR manager.
The allocation of memory for waiting objects, which in principle can be an unlimited number, is left to the discretion of the user. You can store these objects on the stack, in global static variables, or connect a heap manager to the project and allocate memory for the specified objects on the heap.
Problem situations
The execution environment implemented by the dispatcher is characterized by situations that are problematic for preemptive multitasking systems in general [1]. These include: Starvation, Race Conditions, and Priority Inversion. The first two problems can be solved by proper system design, a reasonable distribution of tasks among the threads, a reasonable choice of their priority and the use of synchronization primitives (primarily Auto-Reset Synchronization Events). The third situation is not resolved in my dispatcher, since there are no dynamic priority for threads and synchronization objects of the Mutex type. Therefore, if this situation arises in a specific project, it should be taken into account and, if necessary, add the above funds to the dispatcher.
Source
The source code of the dispatcher, along with a description of the data structures, function parameters and other information, can be downloaded on GitHub .
Literature
1. Wikipedia. Article " Multitasking "
2. ReactOS . Source code, ntoskrnl component
3. Windows WDK Documentation. MSDN Kernel-mode driver architecture