Differences between revisions 1 and 2

Task State Changes

Task state changes, and in particular self-suspensions (e.g., due to I/O), is one of the "real-world" aspects that make scheduling difficult in practice.

The scheduling function implemented in the previous step handles tasks that suspend because a task must be scheduled before it can self-suspend. In addition, a plugin also needs to handle "new" tasks (i.e., tasks that transition to real-time mode) and exiting tasks (i.e., tasks that leave real-time mode or quit unexpectedly). Finally, any plugin must handle resuming tasks (i.e., tasks that become available for execution again after a self-suspension ends).

New and Exiting Tasks

When a task is "new", i.e., when it becomes a real-time task, then it may be either already running or still be suspended. For example, the former happens if real-time tasks initialize themselves, whereas the latter happens if multiple real-time tasks are initialized by some initialization task.

In either case, the scheduler state pertaining to this task must be properly initialized:

the release time of the current job and its deadline must be set;
a running task must further be recorded in the ->scheduled field of the local struct demo_cpu_state instance; and
a task that is not running but part of the runqueue must be added to the ready queue.

   1 static void demo_task_new(struct task_struct *tsk, int on_runqueue,
   2                           int is_running)
   3 {
   4         unsigned long flags; /* needed to store the IRQ flags */
   5         struct demo_cpu_state *state = cpu_state_for(get_partition(tsk));
   6         lt_t now;
   7 
   8         TRACE_TASK(tsk, "is a new RT task %llu (on_rq:%d, running:%d)\n",
   9                    litmus_clock(), on_runqueue, is_running);
  10 
  11         /* acquire the lock protecting the state and disable interrupts */
  12         raw_spin_lock_irqsave(&state->local_queues.ready_lock, flags);
  13 
  14         now = litmus_clock();
  15 
  16         /* the first job exists starting as of right now */
  17         release_at(tsk, now);
  18 
  19         if (is_running) {
  20                 /* if tsk is running, then no other task can be running
  21                  * on the local CPU */
  22                 BUG_ON(state->scheduled != NULL);
  23                 state->scheduled = tsk;
  24         } else if (on_runqueue) {
  25                 demo_requeue(tsk, state);
  26         }
  27 
  28         raw_spin_unlock_irqrestore(&state->local_queues.ready_lock, flags);
  29 }

Similarly, when a task exits, it must be ensured that the scheduler state invariant is maintained.

   1 static void demo_task_exit(struct task_struct *tsk)
   2 {
   3         unsigned long flags; /* needed to store the IRQ flags */
   4         struct demo_cpu_state *state = cpu_state_for(get_partition(tsk));
   5 
   6         /* acquire the lock protecting the state and disable interrupts */
   7         raw_spin_lock_irqsave(&state->local_queues.ready_lock, flags);
   8 
   9         if (state->scheduled == tsk)
  10                 state->scheduled = NULL;
  11 
  12         /* For simplicity, we assume here that the task is no longer queued anywhere else. This
  13          * is the case when tasks exit by themselves; additional queue management is
  14          * is required if tasks are forced out of real-time mode by other tasks. */
  15 
  16         raw_spin_unlock_irqrestore(&state->local_queues.ready_lock, flags);
  17 }

Note that for the purpose of keeping the tutorial simple, the above implementation of demo_task_exit() does not handle the case that a task A revokes the real-time status of task B while B is still queued on the ready queue. A robust implementation would have to handle this as well by checking whether the exiting task is still part of some queue. For learning and testing purposes, this scenario can be avoided, which is why it is not being handled here.

Resuming Tasks

Tasks that resume must be re-added to the ready or release queue, depending on when they resume. Additionally, sporadic tasks that were suspended for a "long" time are considered to experience a sporadic job release and thus must be equipped with a new budget and deadline.

   1 /* Called when the state of tsk changes back to TASK_RUNNING.
   2  * We need to requeue the task.
   3  *
   4  * NOTE: if a sporadic task suspended for a long time,
   5  * this might actually be an event-driven release of a new job.
   6  *
   7  */
   8 static void demo_task_resume(struct task_struct  *tsk)
   9 {
  10         unsigned long flags; /* needed to store the IRQ flags */
  11         struct demo_cpu_state *state = cpu_state_for(get_partition(tsk));
  12         lt_t now;
  13 
  14         TRACE_TASK(tsk, "wake_up at %llu\n", litmus_clock());
  15 
  16         /* acquire the lock protecting the state and disable interrupts */
  17         raw_spin_lock_irqsave(&state->local_queues.ready_lock, flags);
  18 
  19         now = litmus_clock();
  20 
  21         if (is_sporadic(tsk) && is_tardy(tsk, now)) {
  22                 /* This sporadic task was gone for a "long" time and woke up past
  23                  * its deadline. Give it a new budget by triggering a job
  24                  * release. */
  25                 release_at(tsk, now);
  26         }
  27 
  28         /* This check is required to avoid races with tasks that resume before
  29          * the scheduler "noticed" that it resumed. That is, the wake up may
  30          * race with the call to schedule(). */
  31         if (state->scheduled != tsk)
  32                 demo_requeue(tsk, state);
  33 
  34         raw_spin_unlock_irqrestore(&state->local_queues.ready_lock, flags);
  35 }

There are two important things to note. First, in Line 11, note that the CPU that is processing the wakeup is not necessarily the CPU that the task is assigned to. This is because tasks are often resumed by interrupts, which (in general) may be handled on any CPU.

Second, in lines 31-32, note that it may be the case that tsk is still scheduled: this can happen if the wakeup happens shortly after the task initiated its self-suspension, which allows the wakeup on a remote CPU to race with the suspension and to be handled before the local CPU managed to process the self-suspension. (Note that the ready queue lock serializes remote wakeups and local scheduling decisions.)

Plugin Definition

Finally, the plugin definition is updated to hook up the callbacks to the function pointers (or methods) in the plugin object.

   1 static struct sched_plugin demo_plugin = {
   2         .plugin_name            = "DEMO",
   3         .schedule               = demo_schedule,
   4         .task_wake_up           = demo_task_resume,
   5         .admit_task             = demo_admit_task,
   6         .task_new               = demo_task_new,
   7         .task_exit              = demo_task_exit,
   8         .activate_plugin        = demo_activate_plugin,
   9 };

Testing

The kernel should compile and boot fine, but all tasks are still being rejected by demo_admit_task().

In the next step, we are going to enable preemptive scheduling.

-  ⇤ ← Revision 1 as of 2012-08-14 10:01:21 → 
  Size: 6165
  Editor: bbb
  Comment:
+   ← Revision 2 as of 2014-06-12 15:00:17 → ⇥
  Size: 6453
  Editor: bbb
  Comment:
-Deletions are marked like this.
+Additions are marked like this.
 Line 9:
-When a task is "new", i.e., when it becomes a real-time task, then it may be either already running or still be suspended (the former happens if real-time tasks initialize themselves, whereas the latter happens if multiple real-time tasks are initialized by some initialization task). In either case, job accounting must be initialized; a running task must further be recorded in `->scheduled` field of the local `struct demo_cpu_state` instance; a task that is not running but part of the runqueue must be added to the ready queue.
+When a task is "new", i.e., when it becomes a real-time task, then it may be either already running or still be suspended. For example, the former happens if real-time tasks initialize themselves, whereas the latter happens if multiple real-time tasks are initialized by some initialization task.

In either case, the scheduler state pertaining to this task must be properly initialized:
 * the release time of the current job and its deadline must be set;
 * a running task must further be recorded in the `->scheduled` field of the local `struct demo_cpu_state` instance; and
 * a task that is not running but part of the runqueue must be added to the ready queue.
-Line 26:
+Line 31:
- /* the first job exists starting of right now */
+ /* the first job exists starting as of right now */
-Line 30:
+Line 35:
+  /* if tsk is running, then no other task can be running
   * on the local CPU */
-Line 69:
+Line 76:
-Tasks that resume must be re-added to the ready or release queue, depending on when they resume. Additionally, tasks that were suspended for a "long" time are considered to experience a sporadic job release and thus must be equipped with a new budget and deadline.
+Tasks that resume must be re-added to the ready or release queue, depending on when they resume. Additionally, sporadic tasks that were suspended for a "long" time are considered to experience a sporadic job release and thus must be equipped with a new budget and deadline.
-Line 75:
+Line 82:
- * NOTE: if it suspended for a long time, this might actually be
 * an event-driven new job release.
+ * NOTE: if a sporadic task suspended for a long time,
 * this might actually be an event-driven release of a new job.
-Line 92:
+Line 99:
- if (is_tardy(tsk, now)) {
  /* This task was gone for a "long" time and woke up past
+ if (is_sporadic(tsk) && is_tardy(tsk, now)) {
  /* This sporadic task was gone for a "long" time and woke up past
-Line 111:
+Line 118:
-Second, in lines 31-32, note that it may be the case that `tsk` is still scheduled: this can happen if the wakeup happens shortly after the task initiated its self-suspension, which allows the wakeup on remote CPU to race with the suspension and be handled ''before'' the local CPU managed to process the self-suspension. (Note that the ready queue lock serializes remote wakeups and local scheduling decisions.)
+Second, in lines 31-32, note that it may be the case that `tsk` is still scheduled: this can happen if the wakeup happens shortly after the task initiated its self-suspension, which allows the wakeup on a remote CPU to race with the suspension and to be handled ''before'' the local CPU managed to process the self-suspension. (Note that the ready queue lock serializes remote wakeups and local scheduling decisions.)

Diff for "CreateAPluginTutorial/Step6"

Task State Changes

New and Exiting Tasks

Resuming Tasks

Plugin Definition

Testing