Preemptive Multitasking

In order to breath life into a being you must get its heart beating. For a generic operating system the heart is it’s multitasking capability. In developing JANOS one of the very first modules that was created was the one responsible for coordinating the execution of multiple independent processes.

Practically every microprocessor program that has been written is responsible for, and therefore juggles, more than one task. Even those that seem to be so specific so as to be focused on one single task end up responsible for two or more sub-tasks. That doesn’t imply though that every program need implement sophisticated multitasking algorithms. In most cases a simple loop need be employed to cycle through the various tasks at hand.

With a focused application a control loop is often sufficient. In this case task A, B, C, etc. are executed in sequence if they are needed. Once all tasks have been given the chance to run the loop is repeated. Depending on the needs of the application a loop may repeat as often as possible or it may have the luxury of sleeping. The latter being helpful in reducing power requirements.

The rate at which a control loop repeats is variable and dependent on the number of tasks that needs to execute in each cycle and the amount of time each task takes to complete. If there is one task that is time sensitive there can be issues. If the total time required by the other tasks that need to run delays the loop too long, the time critical task may fail. The programmer has to take this into consideration. This can be a real problem if any task becomes dependent upon an external event and must wait for an indeterminate amount of time.

When a task has to wait it is prudent to move on and let other activities be performed in the meantime. We can employ a state machine. Here we break the current task down into a set of sub-tasks where a variable is used to keep track of the current sub-task. If a task has to wait it exits allowing other tasks in the main control loop a chance to run. When the main loop returns to the task at hand, the state machine takes us back to the point where we left off. If we still have to wait we exit again otherwise we handle the next step in the current task.

With fairly complex applications, the main control loop can become complex. The programmer may need to implement some kind of priority scheme. This would increase the time allotted for a set of tasks and force others to take a backseat. Then if multiple tasks require state machine implementations the overall dynamics start to become fuzzy. The programmer suddenly finds situations where the system may behave strangely leading to tweaks and eventually a feeling of careful balance. It works but you are now cautious not to add much more to it. Not without emphasizing testing.

Consider a generic operating system such as JANOS. Here there is a spectrum of system tasks that may be optionally running. Then there can also be multiple programs developed by others (of varying skill levels) running in the system and requiring CPU time. The resulting set of tasks can be so unpredictable that a simple tasking loop is doomed to failure.

A program may need to wait on a communications channel and the third-party programmer does not realize the need to return to allow other tasks to run. At a minimum this slows the system down and suddenly the task handling network traffic might start to cause timeouts and protocol failures. You just cannot predict this let alone control it with the simple loop approach.

So rather than to even try, JANOS employed a preemptive approach right from the start. Now every task becomes a process. Each process executes within its own context. Every context is isolated from other contexts creating independent processes. A timeslice is defined. For JANOS a timeslice is 32 milliseconds. JANOS allows each process to run for up to one timeslice before forcibly moving on to another. A process can relinquish its timeslice when it is waiting on something but it cannot monopolize the CPU.

In coding JANOS the main.c program was the first created. It performs some initial configuration and starts the Process Engine. From that moment on the system became capable of executing more than one process. The main.c procedure then dubbed itself the “Startup Process”. Once it completes its required steps it renames itself as the “Idle Process” and falls into the tight wait loop. From that point forward it becomes solely responsible for collecting unused CPU time. This being the equivalent of twiddling your thumbs.

Before becoming the Idle Process mode the Startup Process initializes the Network Service. This process runs at all times and with priority to insure that all network traffic is handled properly and in a timely fashion. The Startup Process also starts the System process. The System process consists of a simple control loop executing low-priority background tasks such as logging, memory cleanup and event notification. These are the three low-level processes in the OS that run always and cannot be stopped.

Here some of the complexity becomes apparent. In addition to the three base processes that I have described we see some others. The jaccess.jar program is running. This is an application that the HoneyPot uses to create the Mirai Botnet Map web page that it serves to the public. While the Web Server process is required for you to access those pages it is likely running here because I have the DCP open in my browser. In fact the Console process there is mine as well. This results from a session in the Console tab of the DCP and that is where I executed the PS command you see above.

Finally there is a Command process running for some other random IP address. That indicates that there is a Telnet session open. On the HoneyPot those are generally from a Mirai infected host trying (unsuccessfully) to log into this JNIOR. Under JANOS there can be as many as 16 separate processes (including the Idle Process) running at one time.

So what is in the Process Engine that creates this preemptive multitasking environment? It may or may not seem complex to you. I have managed to create a preemptive environment on a variety of processors including the Z80, HP’s early entry into the minicomputer market, CP/M running on early Intel processors and many others. Notably I added this to the Dallas DS80C400 which created the multitasking capability found in the Series 3 JNIOR. The TINI OS that forms the basis of the Series 3 OS is not originally capable of multitasking. JANOS runs preemptive multitasking quite successfully on the Renesas RX63N.

To create a preemptive multitasking environment you need a few basic things. The first is a good 1 millisecond interrupt forming a process tick. You also need a way to switch program context with a minimum of overhead. And finally there needs to be a good atomic means to create a mutex (mutual exclusion object). That being a synchronization technique to control access to system resources when multiple processes are contending for them.

The main.c program during the initialization of JANOS sets up one of the timer registers in the RX63N to divide down the system clock and generate an interrupt every millisecond. The Process Engine first uses this to tally milliseconds and thereby track uptime and to create a real-time software clock. Then on every 32nd tick the Process Engine moves forward to see if another process is pending execution. In that case the context is changed and the next process is allowed to run.

The RX63N uses two stack areas. There is a User Stack which programs normally use to PUSH and POP data. The C Subroutine entry implementation also allocates local variables on that stack. For software to be re-entrant and therefore functional in such a multitasking environment it must store all of its variables on the stack. Now that can include pointers where each instance of that subroutine might allocate its own memory blocks and save the pointers. Later the route needs to release those blocks to avoid memory leaks. The point being that the “context” is really the stack content.

In addition to the User Stack the RX63N also uses an Interrupt Stack. When an interrupt occurs, for instance when the internal timer register is ready to signal 1 millisecond, The program pointer and certain critical resisters are save on the Interrupt Stack before running the interrupt service routine.

So for JANOS to change processes it simply saves the User and Interrupt stack pointers in the Process Table for the current process and then locates the next process that is ready to execute. The User and Interrupt stack pointers are updated from the Process Table for that process and we return from the tick interrupt. Ahh, but now we are not returned to where were just interrupted but to where the new task was interrupted before and so it continues. The originally interrupted process then waits for its turn to run again.

To change processes and context we swap two stack pointers. This is an extremely efficient (time wise) and low-overhead task swap. We do have to push all of the other registers onto the stack before swapping to insure and complete context swap. It happens very quickly. JANOS jumps cleanly from one process to the next without any process realizing it had been set aside temporarily.

This approach requires that we pre-assign 16 independent User Stacks and 16 independent Interrupt Stacks in the Process Table. Fortunately the RX63N has sufficient internal high speed RAM. The Process Engine initialization called by main.c gets that done before enabling the 1 millisecond tick.

Now to create a new process a PROC_create() method is provided that defines the starting point for the new process and passes a couple of useful parameters. The Web Server for instance starts at an entry point named HTTP_process(). An new entry is added to the Process Table for the new process. The name of the new process is one of the parameters supplied. The User and Interrupt stacks for the new process are initialized with content and initial values as would be expected when a return from the 1 millisecond interrupt is executed. Once everything is in order a flag for the new process is set allowing it to execute. We return from the creation routine to do other things but when our timeslice is up, the new process also proceeds from the point we defined.

If a program runs non-stop for its 32 millisecond timeslice it will be preempted. It then waits until it can continue after other tasks get their time in the sun. If a process needs to wait it can release its timeslice by calling PROC_yield(). This call generates a software interrupt that then performs the process swap and starts a new timeslice. The yielding process will continue once others have had a chance.

Often we know about how long we will need to wait. In this case we can release our timeslice for a certain number of milliseconds by calling PROC_sleep(). Here we not only allow our process to swap but also set a timer telling the Process Engine that we won’t be ready to execute for a while.

Along these lines to keep options open and flexible there is also a PROC_delayed() call. This sets the wait time so our process won’t run again until the specified time (uptime as opposed to RTC time). Add to this a PROC_pause() method that stops a process until another process specifically allows it to run again.

Finally there is a PROC_terminate() method which, like it says, terminates the process. This removes the process from the Process Table .

A process may be preempted at any time. This is likely to be in the middle of the assembly language executing a C statement. There are times when critical system structures are being read and updated. An interruption an an inopportune moment can invalidate an update and cause system issues. This is handled through the implementation of a CRITICAL SECTION.

A process can execute an ENTER_CRITICALSECTION macro. This establishes a section of code that cannot be swapped. Once the critical system structures are updated the EXIT_CRITICALSECTION macro restores normal swapping. While this seems to violate our statement earlier that the CPU cannot be monopolized, the Critical Section functionality is only available for use in JANOS system code and not by external application programs. It is not available to third party programmers. Those programs cannot monopolize the system. At least not so easily.

Critical Sections can be nested. That is just handled as a counter which is incremented upon section entry and decremented on exit. As a result there are very few situations where system interrupts must be disabled to prevent issues. This keeps the interrupt processing system ready at all times to service interrupts. Interrupts are not missed.

As a result of all this, the Web Server for example can be written without concern for anything else that may be running. It can also execute processes of its own. An example here is the PHP Scripting Engine which is started by the Web Server. This allows the Web Server to service other requests while a PHP program is compiled and then executed. Such complex interactions occur very smoothly and cleanly.

When a tick generates an interrupt only some registers are preserved on the stack. JANOS uses some inline assembly to also push R6 thru R13 and FP register. The two stack pointers are then passed to the scheduler which may or may not update them depending on what else need to run.

/* -- inline asm -------------------------------------------------------------
** inline_call_tick()
**
** Saves processor state in a consistent manner and manages the stack 
** pointers independent of C optimization effects.
** -------------------------------------------------------------------------*/
#pragma inline_asm inline_call_tick
static void inline_call_tick(void)
{
	PUSHM	R6-R13		; save balance of registers
	PUSHC	FPSW		; save FP register

	MVFC	USP,R1		; snapshot both stack pointers
	MVFC	ISP,R2
	BSR.W	_tick_proc	; perform task processing

	MVTC	R2,ISP		; update both stack pointers
	MVTC	R1,USP

	POPC	FPSW		; restore
	POPM	R6-R13
}

These are the additional registers that I mention needed to be saved.

Once the Process Engine became available the main.c proceeded to start Network and System processes as I have mentioned. Eventually in development of JANOS the Network process has to start receiving and then sending packets over the Ethernet LAN. That makes sense but we are kind of blind. That makes it difficult to develop and debug.

So the next process that we created was designed to handle command line interaction through the serial RS-232 (COM) port. The main.cprogram had been outputting notification strings on this port as the various events were occurring but we couldn’t interact with it. Just prior to becoming the Idle process the main.c program outputs a “Hit any key to login” message. We are not going to start a process for command line interaction until we know that there is someone there to use it.

This established the need for Polling Routines. A polling routine is a routine that can optionally be associated with a process class. It is called once every millisecond tick. Obviously these routines cannot do anything lengthy or they would significantly add to the overhead in the process engine. We would use this to detect an “any key” condition on the port and to then start the command line process.

So a structure for process design had started to evolve. The main.c program calls an initialization routine for each subsystem. For the command line process it calls CMD_initialize(). This initialization routine would indicate that it is “Starting command services” and issue the “Hit any key” message. Eventually when we got the network up and running it would start a Telnet server. The CMD_initialize() routine registers the CMD_polling() routine before returning. That polling routine merely checks the status of the serial port buffer and if a character is pending (the ANY key) and the command line process is not running, the CMD_process() is started.

Eventually we will use polling routines to check and handle timeouts and watchdogs among other tasks. It is a key aspect of the process engine and perhaps even a necessity.