T-Kernel 2.0 Specification
Prev	T-Kernel Concepts	Next

Task States and Scheduling Rules

Task States

Task states are classified primarily into the five below. Of these, Waiting state in the broad sense is further classified into three states. Saying that a task is in a RUN state means it is in either RUNNING state or READY state.

RUNNING state

The task is currently being executed. When a task-independent portion is executing, except when otherwise specified, the task that was executing prior to the start of task-independent portion execution is said to be in RUNNING state.

READY state

The task has completed preparations for running, but cannot run because a task with higher precedence is running. In this state, the task is able to run whenever it becomes the task with the highest precedence among the tasks in READY state.

Waiting states

The task cannot run because the conditions for running are not in place. In other words, the task is waiting for the conditions for its execution to be met. While a task is in one of the Waiting states, the program counter and register values, and the other information representing the program execution state, are saved. When the task resumes running from this state, the program counter, registers and other values revert to their values immediately prior to going to the Waiting state. This state is subdivided into the following three states.

WAITING state

Execution is stopped because a system call was invoked that interrupts execution of the invoking task until some condition is met.

SUSPENDED state

Execution was forcibly interrupted by another task.

WAITING-SUSPENDED state

The task is in both WAITING state and SUSPENDED state at the same time. WAITING-SUSPENDED state results when another task requests suspension of a task already in WAITING state.

T-Kernel makes a clear distinction between WAITING state and SUSPENDED state. A task cannot go to SUSPENDED state on its own.

DORMANT state

The task has not yet been started or has completed execution. While a task is in DORMANT state, information presenting its execution state is not saved. When a task is started from DORMANT state, execution starts from the task start address. Except when otherwise specified, the register values are not saved.

NON-EXISTENT state

A virtual state before a task is created, or after it is deleted, and is not registered in the system.

Depending on the implementation, there may also be transient states that do not fall into any of the above categories (see the Section called System States).

When a task going to READY state has higher precedence than the currently running task, a dispatch may occur at the same time as the task goes to READY state and it may make an immediate transition to RUNNING state. In such a case the task that was in RUNNING state up to that time is said to have been preempted by the task that goes to RUNNING state anew. Note also that in explanations of system call functions, even when a task is said to go to READY state, depending on the task precedence it may go immediately to RUNNING state.

Task starting means transferring a state from DORMANT state to READY state. A task is therefore said to be in "started" state if it is in any state other than DORMANT or NON-EXISTENT. Task exit means that a task in started state goes to DORMANT state.

Task wait release means that a task in WAITING state goes to READY state, or a task in WAITING-SUSPENDED state goes to SUSPENDED state. The resumption of a suspended task means that a task in SUSPENDED state goes to READY state, or a task in WAITING-SUSPENDED state goes to WAITING state.

Task state transitions in a typical implementation are shown in Figure 1. Depending on the implementation, there may be other states besides those shown here.

Figure 1. Task State Transition Diagram

A feature of T-Kernel is the clear distinction made between system calls that perform operations affecting the invoking task and those whose operations affect other tasks (see Table 1). The reason for this is to clarify task state transitions and facilitate understanding of system calls. This distinction between system call operations in the invoking task and operations affecting other tasks can also be seen as a distinction between state transitions from RUNNING state and those from other states.

Table 1. State Transitions Distinguishing Invoking Task and Other Tasks

	Operations in invoking tasks (Transition from RUNNING state)	Operations on other tasks (Transitions from other states)
Task transition to a waiting state (including SUSPENDED)	tk_slp_tsk RUNNING state → WAITING state	tk_sus_tsk READY state, WAITING state → SUSPENDED state, WAITING-SUSPENDED state
Task exit	tk_ext_tsk RUNNING state → DORMANT state	tk_ter_tsk READY state, WAITING state → DORMANT state
Task deletion	tk_exd_tsk RUNNING state → NON-EXISTENT state	tk_del_tsk DORMANT state → NON-EXISTENT state

Operations in invoking tasks

(Transition from RUNNING state)

Operations on other tasks

(Transitions from other states)

Task transition to a waiting state (including SUSPENDED)

tk_slp_tsk

RUNNING state → WAITING state

tk_sus_tsk

READY state, WAITING state → SUSPENDED state, WAITING-SUSPENDED state

Task exit

tk_ext_tsk

RUNNING state → DORMANT state

tk_ter_tsk

READY state, WAITING state → DORMANT state

Task deletion

tk_exd_tsk

RUNNING state → NON-EXISTENT state

tk_del_tsk

DORMANT state → NON-EXISTENT state

	Additional Notes
	WAITING state and SUSPENDED state are orthogonally related, in that a request for transition to SUSPENDED state cannot have any effect on the conditions for task wait release. That is, the task wait release conditions are the same whether the task is in WAITING state or WAITING-SUSPENDED state. Thus even if transition to SUSPENDED state is requested for a task that is in a state of waiting to acquire some resource (semaphore resource, memory block, etc.), and the task goes to WAITING-SUSPENDED state, the conditions for allocation of the resource do not change but remain the same as before the request to go to SUSPENDED state.

Additional Notes

WAITING state and SUSPENDED state are orthogonally related, in that a request for transition to SUSPENDED state cannot have any effect on the conditions for task wait release. That is, the task wait release conditions are the same whether the task is in WAITING state or WAITING-SUSPENDED state. Thus even if transition to SUSPENDED state is requested for a task that is in a state of waiting to acquire some resource (semaphore resource, memory block, etc.), and the task goes to WAITING-SUSPENDED state, the conditions for allocation of the resource do not change but remain the same as before the request to go to SUSPENDED state.

	Rationale for the Specification
	The reason the T-Kernel makes a distinction between WAITING state (wait caused by the invoking task) and SUSPENDED state (wait caused by another task) is that these states sometimes overlap. By recognising these overlapped states as WAITING-SUSPENDED states, the task state transitions become clearer and system calls are easier to understand. On the other hand, since a task in WAITING state cannot invoke a system call, different types of WAITING state (e.g., waiting for wakeup, or waiting to acquire a semaphore resource) will never overlap. Since there is only one kind of waiting state caused by another task (SUSPENDED state), the T-Kernel treats repeated entries to SUSPENDED state as nesting, thereby achieving clarity of task state transitions.

Rationale for the Specification

The reason the T-Kernel makes a distinction between WAITING state (wait caused by the invoking task) and SUSPENDED state (wait caused by another task) is that these states sometimes overlap. By recognising these overlapped states as WAITING-SUSPENDED states, the task state transitions become clearer and system calls are easier to understand. On the other hand, since a task in WAITING state cannot invoke a system call, different types of WAITING state (e.g., waiting for wakeup, or waiting to acquire a semaphore resource) will never overlap. Since there is only one kind of waiting state caused by another task (SUSPENDED state), the T-Kernel treats repeated entries to SUSPENDED state as nesting, thereby achieving clarity of task state transitions.

Task Scheduling Rules

The T-Kernel adopts a preemptive priority-based scheduling method based on priority levels assigned to each task. Tasks having the same priority are scheduled on a FCFS (First Come First Served) basis. Specifically, task precedence is used as the task scheduling rule, and precedence among tasks is determined as follows based on the priority of each task. If there are multiple tasks that can be run, the one with the highest precedence goes to RUNNING state and the others go to READY state. In determining precedence among tasks, of those tasks having different priority levels, that with the highest priority has the highest precedence. Among tasks having the same priority, the one that entered a run state (RUNNING state or READY state) first has the highest precedence. It is possible, however, to use a system call to change the precedence among tasks having the same priority.

When the task with the highest precedence changes from one task to another, a dispatch occurs immediately and the task in RUNNING state is switched. If no dispatch occurs (during execution of a handler, during dispatch disabled state, etc.), however, the switching of the task in RUNNING state is held off until the next dispatch occurs.

	Additional Notes
	According to the scheduling rules adopted in the T-Kernel, so long as there is a higher precedence task in a run state, a task with lower precedence will simply not run. That is, unless the highest-precedence task goes to WAITING state or for other reason cannot run, other tasks are not run. This is a fundamental difference from TSS (Time Sharing System) scheduling in which multiple tasks are treated equally. It is possible, however, to issue a system call changing the precedence among tasks having the same priority. An application can use such a system call to realize round-robin scheduling, which is a typical kind of TSS scheduling. Examples in figures below illustrate how the task that first goes to a run state (RUNNING state or READY state) gains precedence among tasks having the same priority. Figure 2 shows the precedence among tasks after Task A of priority 1, Task E of priority 3, and Tasks B, C and D of priority 2 are started in that order. The task with the highest precedence, Task A, goes to RUNNING state. When Task A exits, Task B with the next-highest precedence goes to RUNNING state (Figure 3). When Task A is again started, Task B is preempted and reverts to READY state; but since Task B went to a run state earlier than Task C and Task D, it still has the highest precedence among tasks with the same priority. In other words, the task precedence reverts to that in Figure 2. Next, consider what happens when Task B goes to WAITING state in the conditions in Figure 3. Since task precedence is defined among tasks that can be run, the precedence among tasks becomes as shown in Figure 4. Thereafter when the Task B waiting state is released, Task B goes to run state after Task C and Task D, and thus assumes the lowest precedence among tasks of the same priority (Figure 5). Summarizing the above, immediately after a task that goes from READY state to RUNNING state reverts to READY state, it has the highest precedence among tasks of the same priority; but after a task goes from RUNNING state to WAITING state and then the wait is released, its precedence is the lowest among tasks of the same priority. Note that after a task goes from SUSPENDED state to a run state, it has the lowest precedence among tasks of the same priority. In a virtual memory system, if a task is made to wait for paging by putting the task in SUSPENDED state, in such a system the task precedence changes as a result of a paging wait. Figure 2. Precedence in Initial State Figure 3. Precedence After Task B Goes To RUNNING State Figure 4. Precedence After Task B Goes To WAITING State Figure 5. Precedence After Task B WAITING State Is Released

Additional Notes

According to the scheduling rules adopted in the T-Kernel, so long as there is a higher precedence task in a run state, a task with lower precedence will simply not run. That is, unless the highest-precedence task goes to WAITING state or for other reason cannot run, other tasks are not run. This is a fundamental difference from TSS (Time Sharing System) scheduling in which multiple tasks are treated equally.

It is possible, however, to issue a system call changing the precedence among tasks having the same priority. An application can use such a system call to realize round-robin scheduling, which is a typical kind of TSS scheduling.

Examples in figures below illustrate how the task that first goes to a run state (RUNNING state or READY state) gains precedence among tasks having the same priority. Figure 2 shows the precedence among tasks after Task A of priority 1, Task E of priority 3, and Tasks B, C and D of priority 2 are started in that order. The task with the highest precedence, Task A, goes to RUNNING state.

When Task A exits, Task B with the next-highest precedence goes to RUNNING state (Figure 3). When Task A is again started, Task B is preempted and reverts to READY state; but since Task B went to a run state earlier than Task C and Task D, it still has the highest precedence among tasks with the same priority. In other words, the task precedence reverts to that in Figure 2.

Next, consider what happens when Task B goes to WAITING state in the conditions in Figure 3. Since task precedence is defined among tasks that can be run, the precedence among tasks becomes as shown in Figure 4. Thereafter when the Task B waiting state is released, Task B goes to run state after Task C and Task D, and thus assumes the lowest precedence among tasks of the same priority (Figure 5).

Summarizing the above, immediately after a task that goes from READY state to RUNNING state reverts to READY state, it has the highest precedence among tasks of the same priority; but after a task goes from RUNNING state to WAITING state and then the wait is released, its precedence is the lowest among tasks of the same priority.

Note that after a task goes from SUSPENDED state to a run state, it has the lowest precedence among tasks of the same priority. In a virtual memory system, if a task is made to wait for paging by putting the task in SUSPENDED state, in such a system the task precedence changes as a result of a paging wait.

Figure 2. Precedence in Initial State

Figure 3. Precedence After Task B Goes To RUNNING State

Figure 4. Precedence After Task B Goes To WAITING State

Figure 5. Precedence After Task B WAITING State Is Released