Scheduling policies
Each task is assigned a priority level.
Many tasks may co-exist at a priority level.
- The default scheduling policy is a FIFO i.e. MQX will run the oldest task at the highest priority level.
- A round-robin scheduling can optionally be implemented on a per-task or a per-processor basis.
Under the round-robin scheduling, a task is allocated an interval of time (time slice) to run. At the end of the time slice and if the task has not completed, the task yields to the next task at the same level of priority.
A task can execute if and only if no higher priority tasks are ready.
Ready Queues.
Tasks at each priority level are arranged in a queue. This is implemented in the kernel through the ready-queue structure which is a linked list of task descriptors.
Each task that becomes ready, is entered at the tail of the queue at its priority level.
The scheduler scans the ready queue starting at the highest priority proceeding towards the lowest priority level. It starts scheduling tasks that it finds being READY at the first "populated" level encountered.
- If the scheduling policy is FIFO, then a running task is allowed to run until it is completed, blocked or pre-emptied by a higher priority task becoming READY.
- If the scheduling policy is Round-Robin, then a running task will be pre-emptied at the end of its time slice. At that point, it will be moved to the tail of the queue of its priority level. Additionally, a running task will be pre-emptied by a higher priority task, but then it maintains its relative priority position within its level.
Task Descriptor Structure
|
typedef struct td_struct | ||
| { | ||
| struct td_struct _PTR_ TD_NEXT; | ||
| struct td_struct _PTR_ TD_PREV; | ||
| uint_32 | STATE; | |
| _task_id | TASK_ID; | |
| void | PTR_STACK_BASE; | |
| pointer | STACK_PTR; | |
| void | PTR_STACK_LIMIT; | |
| void | PTR_MY_QUEUE: | |
| pointer | MSG_QUEUE_HEAD; | |
| pointer | MSG_QUEUE_TAIL; | |
| uint_32 | MESSAGES_AVAILABLE; | |
| pointer | MESSAGES; | |
| _task_id | CORRESPONDENT; | |
| pointer | MEMORE_RESOURCE_LIST; | |
| uint_32 | TASK_ERROR_CODE; | |
| _task_id | FATHER; | |
| uint_32 | TASK_INDEX; | |
| pointer | STDIN_STREAM; | |
| pointer | STDOUT_STREAM; | |
| pointer | STDERR_STREAM; | |
| uint_16 | < TASK_SR; | |
| uint_16 | RESERVED; | |
| TASK_TEMPLATE_STRUCT_PTR | TASK_TEMPLATE_PTR; | |
| uint_32 | PROCESSOR_NUMBER; | |
| TIME_STRUCT | TIMEOUT; | |
| uint_32 | DISABLED_LEVEL; | |
| uint_32 | FLAGS; | |
| uint_32 | TIMESLICE; | |
| uint_32 | CURRENT_TIME_SLICE; | |
| uint_32 | BOOSTED; | |
| struct | ready_q_struct_PTR_HOME_QUEUE; | |
| uint_32 | WATCHDOG_TIME; | |
| TD_STRUCT, _TR_TD_STRUCT_PTR; | ||
| } | ||
Blocked Tasks
When a task ceases to be active, its context is saved in a BLOCKED_STATE_STRUCT on the task's stack which is hardware dependent.
For example the format of the BLOCKED_STATE structure is:
| 80X86 | ||
| typedef struct blocked_stack_struct | ||
| { | ||
| STORED_REGISTERS_STRUCT | REGISTERS; | |
| pointer | PROGRAM_COUNTER; | |
| uint_16 | FLAGS; | |
| } | BLOCKED_STACK_STRUCT, | _PTR_BLOCKED_STACK_STRUCT_PTR, |
| _PTR_STACK_FRAME_STRUCT_PTR; | ||
| 68XXX | ||
| typedef struct blocked_stack_struct | ||
| { | ||
| STORED_REGISTERS_STRUCT | REGISTERS; | |
| uint_16 | STATUS_REGISTER; | |
| pointer | RETURN_ADDRESS; | |
| uint_16 | FORMAT_AND_VECTOR; | |
| } | BLOCKED_STACK_STRUCT, | _PTR_BLOCKED_STACK_STRUCT_PTR; |