Multitasking

Technical Notes

Overview
What Is Cooperative Multitasking?
What Are Tasks?
The Active Task
Task Handles
The Default Task
The Task Scheduler
Terminology of Task Stacks
Stack Heap Characteristics
Managing the Stack Heap
Initializing the Multitasking System
Adding Tasks
Manipulating Tasks
Yielding
Determining and Setting Task Information
Suspending Multitasking
Stack Overflow Checking
Sharing Resources and Avoiding Deadlock
Sample Program

Overview

This unit provides a complete system of functions for cooperative (non-preemptive) multitasking. It consists of functions which perform the following: add, remove, suspend, and resume tasks; yield to the next or specified task; set and determine the priority of a task; set and determine the skip count of a task; make a task sleep until a specified time of day or for a specified period of time; get a task's descriptor; determine the number of tasks; suspend or resume multitasking; dynamically allocate task stacks; determine the available stack space for a specified task; and detect and handle task stack overflow.

What Is Cooperative Multitasking?

For the purposes of this unit, multitasking is a method of switching between processes or tasks so that each gets an equitable share of CPU time. Multitasking is not parallel processing, but merely a method of simulating parallel processing in software. In cooperative multitasking it is the responsibility of the individual task to release the CPU resource at logical intervals. This is in contrast to preemptive multitasking where the task switching occurs at either the system or hardware level and the task is generally unaware of the switch. Cooperative multitasking is generally more efficient than preemptive multitasking because a task can wait until it reaches a logical breaking point before it switches. In cooperative multitasking, a task is never unexpectedly interrupted.

The key to cooperative multitasking is that the tasks must be cooperative, that is, each task has the responsibility of explicitly releasing the CPU resource periodically so that other tasks can have a turn. This is done by either yielding to the task scheduler or directly yielding to a specified task. Based on the specified priority scheme, the task scheduler preserves the state of the system (registers and flags) and switches contexts to the next task. When a task releases the CPU, it usually expects to get it back in a reasonable amount of time.

It is the programmer's responsibility to optimize the number and location of yields in tasks. The number and placement of yields within tasks determines if a task will appear to operate smoothly or coarsely. A balance needs to be found between how smoothly a task operates and how much CPU time is spent in switching between tasks. Normally yields are inserted just prior to loops or lengthy sections of code that are time critical, or they are inserted inside loops that are waiting for an event to occur. Yields are already inserted in Spontaneous Assembly console I/O functions which perform keyboard I/O (i.e. _cget_chr, _cget_chre, and _cget_str).

What Are Tasks?

For the Spontaneous Assembly multitasking system, tasks are independent programs or routines that follow a few simple rules to allow them to multitask in this system. Each task must yield periodically so that other tasks may have a turn. Each task has its own stack. Task stacks can easily be set up and managed using functions provided in this unit. Each task is defined by a task descriptor which defines and maintains the task's priority and status.

Tasks may execute indefinitely, or they may return when they finish their work. When a task returns, it is either removed from the task list or it is automatically restarted at the beginning of the task. The final disposition of a returning task is specified in the task descriptor at the time the task is added.

The Active Task

The active task is the task which is currently executing. Only one task is executing at a time. The active task may perform operations on itself (e.g., sleep, suspend, and change priority). The active task may always be accessed by specifying -1 as the handle.

Task Handles

Task handles are assigned when a task is added to the task list. When a task is added, its handle may be specified directly. If a handle value of -1 is specified, the next available handle is allocated by the multitasking system. These handles are used to select and manipulate tasks when using the multitasking functions.

Tasks in the task scheduler list are ordered in increasing order based on the value of each task handle. The handle order, NOT the order in which tasks are added, determines the order in which tasks are considered for control by the scheduler. This makes it possible to optimize the order in which tasks are executed by the task scheduler. Handle values are allocated sequentially when task handles are allowed to default to the next available handle.

A handle value of 0 always denotes the default task and cannot be changed. Multitasking operations are performed on the active task when -1 is specified as the handle value (except _task_add, as explained above).

The Default Task

The multitasking system always contains a default task. Multitasking starts with the first call to _task_yield or _task_yieldto from the default task. The default task may be main or it can be specified in the default task descriptor at the time _tasking_init is called.

Control is passed to the default task by _tasking_init. The default task is called if its address is explicitly specified in the default task descriptor; otherwise, _tasking_init simply returns and the code following the original call to _tasking_init is treated as the default task. When the default task returns, control is returned to the code following the original call to _tasking_init if the default task was explicitly specified; otherwise, the return is treated as a normal return from the function which contains the default task.

All of the multitasking functions can be used on the default task except _task_add, _task_remove, and the task stack management functions.

The Task Scheduler

The task scheduler saves the current state of the task which is yielding, selects the next task, and restores the state of the next task to be given control. Every time a yield is encountered, the task scheduler examines the next task in the task list. If the next task is suspended, it is skipped. If it is sleeping, the wake-up time is compared against the current time; if it is time to wake up, the task is no longer treated as a suspended task; otherwise, the task is skipped. If the task is not suspended or sleeping, its skip count is checked. If the skip count is non-zero, its skip count is decremented and the task is skipped. If the skip count is zero, the task is given control. Tasks in the scheduler task list are examined in sequential order based on the value of their task handles.

Task Priority and Skip Count

Each task has a priority and skip count. The task scheduler uses these two values to determine how often each task gains control of the CPU. The skip count is a "count down to zero" variable; the priority is a reload value for the skip count. A non-suspended task's skip count is decremented each cycle through the task scheduler. The scheduler only passes control to a task if its skip count is zero when it is polled and if it is not suspended or sleeping. Each time a task receives control, its skip count is reloaded with its priority.

A task's priority and skip count do not need to be set to identical values. In fact, the priority and/or skip count of a task may be modified dynamically by any task in the system, including the task itself. The initial and continuing priority of the task depends on how these values are set. For example:

Skip CountPriorityThe task gains control on...

    0      0    ...the first cycle and every cycle thereafter
    0      9    ...the first cycle and every tenth cycle thereafter
    9      0    ...the tenth cycle and every first cycle thereafter
    9      9    ...the tenth cycle and every tenth cycle thereafter

Valid values for the priority and skip count are 0 to 255.

Terminology of Task Stacks

Each task must have its own stack, which may be allocated statically or dynamically. Dynamic stack allocation may be performed using conventional methods (near or far heaps, DOS memory allocation, etc.), or it may be performed using the multitasking stack heap management functions provided in this unit.

The task stack heap itself may be allocated dynamically or statically. Once it has been allocated, the stack heap must be initialized using the custom stack heap initialization function. (Due to differences between compilers, the default stack heap initialization function is not available in Spontaneous Assembly For C/C++.)

Task stacks are described as being on a heap after they are allocated from the stack heap. Most of the operations permitted on near, far, and relative heaps are also provided for the stack heap. The stack heap memory management functions use the relative heap memory management functions internally.

Basic Rules of Stack Heap Operation

The task stack heap must be initialized with the custom stack heap initialization function before it may be used.
Once the stack heap has been initialized, heap space may be allocated by calling the heap memory allocation function.
Stack memory is allocated in blocks. Block sizes are arbitrary and are specified in the task descriptor of the task for which the stack memory is being allocated.
Stack blocks are allocated on the stack heap using a first fit algorithm.
Allocated stacks remain fixed in size and position until they are released.
Allocated stacks cannot be moved within the stack heap.

Stack Heap Characteristics

Initialization Due to compiler limitations, only custom initialization is provided. The size is user-specified.

Number of heaps supported: One.

Heap location: Must be in DGROUP (global or static non-far data) for small data models, anywhere in conventional memory for large data models.

Assumptions: Custom initialization assumes memory has already been allocated for use by the stack heap. Memory may be pre-allocated either statically or dynamically from heap memory or DOS.

Maximum heap size       Up to 64K, including heap control variables.

Maximum stack size      32,764 bytes.

Minimum stack size      0 bytes

Overhead per stack      2 bytes.

Granularity             2 bytes.

Stack alignment          Word.

Heap control variables Stored in the first paragraph of the heap segment, documented in MEMALLOC.H.

Managing the Stack Heap

_tstack_avail: Returns the number of available bytes on the stack of the active task.
_tstack_free: Frees a block on the stack heap.
_tstack_initc: Initializes the stack heap to a custom size and location.
_tstack_malloc: Allocates space for a task stack on the stack heap.
_tstack_max: Returns the size of the largest available block on the stack heap.

These function manage and return information about the task stack heap. _tstack_initc, _tstack_malloc, and _tstack_free may be called prior to initializing the multitasking system.

_tstack_avail returns the number of bytes of unused stack space for the current task. This function also detects and reports task stack overflow.

_tstack_free may be used to deallocate a block on the stack heap. The address of the stack block to be freed is returned by the _task_remove function. Since the stack is used by the task, it is critical to remove the task before de-allocating its stack.

_tstack_initc initializes already-allocated memory as the task stack heap and must be called before the stack heap may be used. Memory may be statically or dynamically. This function may be called either before or after calling _tasking_init.

_tstack_malloc allocates stack heap memory for use as a task stack. This function accepts a size from the task descriptor and returns the stack address in the descriptor. In small data models the stack address is a near pointer (an offset relative to the default data segment, DGROUP). In large data models the stack address is a far pointer (segment:offset).

_tstack_max returns the size of the largest available stack heap block.

WARNING! In small data models, the stack heap must reside within the 64K region beginning at the start of DGROUP (global or static non-far data). This condition is satisfied if the stack heap is allocated on the near heap. In large data models the stack heap may reside anywhere in conventional memory.

Initializing the Multitasking System

_tasking_init: Initializes the multitasking system.
_tasking_init: initializes the multitasking system. The multitasking system must be initialized before any of the multitasking functions may be used (except the task stack heap management functions mentioned above). This function adds the default task to the task list and turns multitasking on. This function has no effect if the multitasking system is already active.

Adding Tasks

_task_add: Adds a task to the scheduler task list.
_task_add: adds a task to the task list. This function expects a task descriptor which specifies the task handle, the task starting address, and the characteristics of the task. Each task must also be assigned a stack before it may be added to the task list.

Adding a task does not automatically make that task active. A task becomes active only when it is yielded to via _task_yield or _task_yieldto.

Task descriptors may be created using the satask structure defined in MTASK.H. This structure is defined as follows:


typedef struct {
   unsigned int t_handle;       /* task handle (-1 to use next avail handle) */
   void *t_addr;                /* task starting address */
   unsigned int t_stksize;      /* task stack size (default=256 bytes) */
   char *t_stkaddr;             /* task stack address (default=inherit) */
   unsigned char t_priority;    /* priority of task (0-255, default=0) */
   unsigned char t_numskips;    /* skip count (initial priority) (0-255, def=0) */
   unsigned long t_waketime;    /* time of day to wake up task */
   void *t_nextlink;            /* address of next descriptor in task list */
   char *t_stksave;             /* task stack address when task yields */
   unsigned int t_dstack;       /* offset of task stack relative to heap segment
                                    (small data models only) */
   unsigned char t_statbyte;    /* current status of task */
   char reserved;               /* (RESERVED) */
} satask;

Each field in the satask definition structure specifies or maintains information about the task. The satask structure fields are defined as follows:

t_handle: Task handle. The task handle may be specified explicitly, or -1 may be specified to default to the next available handle number. The task scheduler cycles through the task list based on handle number order. Valid values are 0 to 65534.
t_addr: Task starting address. This is a near pointer (offset only) in small code models, and it is a far pointer (segment:offset) in large code models. This must be set by the programmer before adding the task.
t_stksize: Size of the task stack. If the stack was manually allocated, this field must indicate the size of the stack. If the stack block is to be allocated with _tstack_malloc, this field must indicate the required stack block size. The default size is 256 bytes.
t_stkaddr: Stack address. This is a near pointer (offset only) relative to DGROUP in small data models; it is a far pointer (segment:offset) in large data models. This field is automatically filled in if _tstack_malloc is used. If the stack was manually allocated, this field must be set by the programmer.
t_priority: Priority of the task. This is the reload value for t_numskips each time the task gains control of the CPU.
t_numskips: Skip count. The number of times the task will be skipped before it receives control from the task scheduler. This value is decremented by the task scheduler on each scheduler cycle. The task is considered for control when the skip count equals 0.
t_waketime: Time of day the task is scheduled to wake up. This field is set by a call to _task_sleep or _task_sleeptime. The task scheduler only checks this field if the T_SLEEP bit in the t_statbyte field is set. The time is stored in Spontaneous Assembly unsigned long time format.
t_nextlink: Descriptor address of the next task in the task list. This field is set when a task is added with _task_add.
t_stksave: Task stack pointer. The stack pointer is preserved here while the task is inactive. The stack pointer is restored from this field when the task receives control again.
t_dstack: Offset of the stack block relative to the stack heap segment. This field is used only in small data models. This offset and the segment of the stack heap are returned by _task_remove and used by _tstack_free to facilitate disposing of unused stack heap blocks.
t_statbyte: Status of the task. A specific bit in this field is used for each status condition maintained by the multitasking system. This field may be modified to specify if the task should be automatically removed or restarted when the task returns. By default, the task remains in the task list and is restarted at the address specified in t_addr the next time the task is given control. If the T_AUTOREMOVE flag is set when the task is added, the task will be removed from the task list when it returns. The following symbolic constant is defined in MTASK.H to set and check the t_statbyte field for the auto remove feature:

T_AUTOREMOVE: (0x01) Automatically remove task on return

The following symbolic constants are defined in MTASK.H to check the remaining bits in the t_statbyte field:

T_SUSPEND: (0x02) Task is suspended
T_SLEEP: (0x04) Task is sleeping
T_STACKHEAP: (0x10) Task stack is allocated on the stack heap

Manipulating Tasks

_task_remove: Removes a task from the scheduler task list.
_task_resume: Resumes a suspended task.
_task_sleep: Suspends a task for a specified period of time.
_task_sleeptime: Suspends a task until a specified time of day.
_task_suspend: Suspends a task.

These functions resume, suspend, and remove tasks.

_task_remove is the inverse of the _task_add function. This function deletes a task from the task scheduler list and returns the address of the task's stack. It is the programmer's responsibility to properly dispose of the removed task's stack memory block. If the stack was allocated from the stack heap, the stack memory is usually freed by calling _tstack_free immediately after the task is removed.

_task_suspend suspends a task, preventing it from receiving control via the task scheduler. Whenever the task scheduler encounters a suspended task, it immediately skips to the next task without adjusting the skip count of the suspended task. A suspended task remains in the task list while it is suspended. This function has no effect if the task is already suspended.

_task_resume cancels the effect of a previous call to _task_suspend. The resumed task does not receive control until it is either yielded to directly or until the task scheduler selects it for control using the normal selection criteria. This function has no effect if the task is not suspended.

_task_sleep suspends a task for a specified period of time. _task_sleeptime suspends a task until a specified time of day. Both functions accept time values in a std_time structure, but _task_sleeptime only allows the wake up time to be specified to the nearest hour and minute. (See the Date and Time Manipulation technical notes for more information on the std_time structure.)

Yielding

_task_yield: Saves the state of the active task and yields to the task scheduler.
_task_yieldto: Saves the state of the active task and yields to a specific task.

These functions allow other tasks to gain control of the CPU. When a task calls _task_yield or _task_yieldto, the task scheduler considers all other applicable tasks according to their priority and status, passes control to the appropriate tasks, and then returns control to the next instruction afterthe _task_yield... function call. The strategic placement of yields in tasks allows the programmer to control when a task is interrupted and how much processing time elapses before control is passed to the other tasks in the system. If stack overflow is detected by a yield function, control is immediately passed to the stack overflow handler (see Stack Overflow Checking, later in this chapter).

_task_yield saves the state of the current task and passes control to the task scheduler. The scheduler then examines the priority and status of each task in the system and passes control to the next available task.

_task_yieldto saves the state of the current task and passes control to a specified task. Control is passed to the specified task even if it is suspended, sleeping, or if its skip count is not zero. If the new task calls _task_yield, the scheduler will determine the next available task as described for _task_yield, above; return of control to the parent is not automatic.

Yields are already supported in Spontaneous Assembly console I/O functions which perform keyboard I/O (e.g., _cget_chr, _cget_chre, and _cget_str). The Spontaneous Assembly DOS console I/O functions do not yield to the multitasking system because they allow DOS to wait for the keystroke. If a yield needs to be performed while waiting for DOS keyboard input, it may be performed as follows:


   ...
   while (!_check_key())/* is a keystroke waiting? */
      _task_yield(); /*   n: allow other tasks to execute while waiting for a key
   _get_chre();  /*   y: handle keystroke
   ...

If a yield function is called while multitasking is suspended, control is immediately returned to the task that yielded. Multitasking is automatically resumed when the current task returns.

WARNING! It is possible to create a combination of _task_yield and _task_yieldto functions that would always skip a task or group of tasks.

Determining and Setting Task Information

_get_numtasks: Returns the number of tasks currently in the task scheduler list.
_get_tpriority: Returns the current priority and skip count of a task.
_get_tspec: Returns a copy of a specified task descriptor.
_get_tstatus: Determines if any of the specified task status flags are set.
_set_tpriority: Sets the priority and skip count of a task.

These functions return miscellaneous information about tasks and allow the priority and skip count of a task to be specified.

_get_numtasks returns the current number of tasks in the task list. The return value includes tasks that are suspended and sleeping.

_get_tpriority returns the current priority and skip count for a specified task. (See Task Priority and Skip Count, above.)

_get_tspec returns a copy of the task descriptor for a given task. (See Adding Tasks, above, for a detailed explanation of task descriptors). The returned descriptor contains all current information about the task, including its stack size, stack location, priority, skip count, and status. This function is frequently used to preserve the state of a task before it is removed.

_get_tstatus determines the status of selected bits in the t_statbyte field of the task descriptor assigned to a specified task. The following symbolic constants, defined in MTASK.H, indicate the status bits which may be tested:

T_AUTOREMOVE: (0x01) Automatically remove task on return
T_SUSPEND: (0x02) Task is suspended
T_SLEEP: (0x04) Task is sleeping
T_STACKHEAP: (0x10) Task stack is allocated on the stack heap

Testing these conditions can be especially valuable before yielding to a task, as in the following code sample:


   ...
   if (!_get_tstatus(handle_01, T_SUSPEND+T_SLEEP))      /* is task suspended or sleeping? */
      _task_yieldto(handle_01);                                          /*   n: ok to yield to it */
   ...

_set_tpriority sets the priority and skip count of a specified task. (See Task Priority and Skip Count, above.) If -1 is specified for either value, that value remains unchanged.

Suspending Multitasking

_yield_suspend: Temporarily suspends multitasking.
_yield_resume: Resumes multitasking.

_yield_suspend suspends the action of the _task_yield and _task_yieldto functions. This function allows a task with embedded calls to the yield functions to continue execution without yielding control. While yielding is suspended, calls to _task_yield and _task_yieldto immediately return control to the active task. The state of the task list at the time _yield_suspend is called is preserved. When multitasking is suspended, it remains suspended until _yield_resume is called or until the active task returns. When the default task returns, the multitasking system is assumed to be off; multitasking is not automatically resumed. When any other task returns, the task scheduler receives control and multitasking is automatically resumed. _yield_resume resumes multitasking by re-enabling the action of the _task_yield and _task_yieldto functions.

Stack Overflow Checking

_exit_overflow: Displays a stack overflow message and exits to DOS with an ERRORLEVEL of 1.
overflow_addr: (Variable) Contains the address of the current stack overflow handler.

_exit_overflow displays a DOS-like error message ("Stack overflow"), sets the ERRORLEVEL to 1, and terminates the program. This function is the default stack overflow handler for the multitasking system. overflow_addr contains the address of the current stack overflow handler. This function pointer is initialized with the address of _exit_overflow. If stack overflow is detected by the multitasking system, control is unconditionally passed to the stack overflow handler address in overflow_addr. To specify an alternate stack overflow handler, load the address of the new handler into overflow_addr. Stack overflow checking takes place in the _task_yield and _task_yieldto functions. When a task is added to the multitasking system, the last word (int) on each task stack is initialized to a known marker value. This location is checked each time the task yields. If the stack overflow marker changes, the current stack overflow handler is called. Because of the sequence in which stack overflow checking is performed, the active task is usually the task which caused the overflow.

The stack overflow marker value is defined by the T_STKMARKER symbolic constant (defined in MTASK.H). The default value is 0xABC7. If this value is changed, the new value takes effect only after the multitasking functions are reassembled with the modified header file.

T_STKMARKER: (0xABC7) Marker used for stack overflow checking

Sharing Resources and Avoiding Deadlock

In most programs, different tasks need to use the same, non-sharable resources. For example, two different tasks may need to use DOS file I/O services to read data from different files, and both tasks may need to use the same global buffer for the read. When cooperative multitasking is used, non-sharable functions (the DOS file I/O services) are never a problem as long as such functions never yield to the multitasking system. Global data, however (the buffer) can be a serious problem if it is not carefully managed. Management of global data is usually accomplished by usingsemaphores to indicate that specific resources are in use. Before any task uses a resource, it must check the appropriate semaphore (flag) to see if the resource is already in use. If the resource is available, the task then "locks" the resource for its own use by setting the flag. This prevents a later task from corrupting data which is in use by a previous task.

While semaphores are simple to implement, a condition known as deadlock must be carefully avoided in multitasked systems which allow "locking" of non-sharable resources as described above. Deadlock can be seen in the following scenario: assume Task 1 owns Resource A and Task 2 owns resource B. If Task 1 needs Resource B, it must wait for it to become available. Then, if Task 2 has a need for Resource A before Resource B becomes available to Task 1, Task 2 must wait for it to become available. This leaves both tasks waiting for the other to free a needed resource before they can continue executing. Because these situations are timing-dependent, deadlock can cause hard-to-reproduce errors where tasks (and even the entire system) appears to be "hung."

Fortunately, deadlock is easily avoided in a cooperative multitasking system. The rules are as follows: 1) Each task must wait until all needed resources are available before locking any of them; and 2) All needed resources must be locked at the same time. This means that if a task already owns some resources and needs more, it must first release the resources it owns before it waits for all of the resources to become available at the same time.

Sample Program

The sample program shown above (MTASK.C) is provided on the distribution diskettes and may be compiled and linked using the following Microsoft C and Borland C command lines:

Microsoft C:


cl /c /I\msc\include /I\sa\include mtask.c
link mtask,mtask,,\sa\lib\_sas \msc\lib\slibce

Borland C:


bcc /c /ms /I\bc\include /I\sa\include mtask.c
tlink \bc\lib\c0s mtask,mtask,,\sa\lib\_sas \bc\lib\cs