2.2.2 Task Scheduling Rules
The T-Kernel speci.cation 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. Speci.cally, 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 RUN state and the others go to READY state. In determining precedence among tasks, of those tasks having di.erent priority levels, that with the highest priority has the highest precedence. Among tasks having the same priority, the one .rst going to a run state (RUN state or READY state) 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 RUN state is switched over. If no dispatch occurs, however, the switching of the task in RUN state is held o. until dispatch occurs.
According to the scheduling rules adopted in the T-Kernel speci.cation, so long as there is a high-precedence task in a run state, a task with lower precedence will simply not run. That is, unless the highest-precedence goes to WAIT 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.
Figure 2.2: Precedence in Initial State
Figure 2.2 and following illustrate how the task that .rst goes to a run state (RUN state or READY state) gains precedence among tasks having the same priority. Figure 2.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 RUN state.
When Task A exits, Task B with the next-highest precedence goes to RUN state (Figure 2.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.2.
Next, consider what happens when Task B goes to WAIT state in the conditions in Figure 2.3. Since task precedence is defined among tasks that can be run, the precedence among tasks becomes as shown in Figure 2.4. Thereafter when the Task B wait state is released, Task B went to run state after Task C and Task D, and thus assumes the lowest precedence among tasks of the same priority (Figure 2.5). Summarizing the above, immediately after a task that went from READY state to RUN state reverts to READY state, it has the highest precedence among tasks of the same priority; but after a task goes from RUN state to WAIT state and then the wait is released, its precedence is the lowest among tasks of the same priority.
Figure 2.3: Precedence After Task B Goes To RUN State
Figure 2.4: Precedence After Task B Goes To WAIT State
Note that after a task goes from SUSPEND state to a run state, it has the lowest precedence among tasks of the same priority. In a virtual memory system, since a task is made to wait for paging by putting the task in SUSPEND state, in such a system the task precedence changes as a result of a paging wait.
Figure 2.5: Precedence After Task B WAIT State Is Released
Comments