Add P-EDF Scheduling Logic
In this step, we are going to define how the DEMO plugin selects the task that should be scheduled next. Remember that we are implementing P-EDF: we can therefore use the helper function edf_preemption_needed(), declared in litmus/edf_common.h, to determine when the previous task prev should be preempted.
Headers
Since the scheduling logic deals with job parameters and execution budgets, we need to add two additional header files.
Helper Functions
Before diving into the scheduling function, we are going to define two helper functions that will aid in preventing the schedule() implementation from becoming too convoluted.
The first helper, demo_job_completion() is called to process a job when it is complete. In this simple example, it actually delegates all of the work to the common helper prepare_for_next_period(), which is declared in litmus/jobs.h. In more complicated scheduling policies, additional housekeeping code to be run on job completions may be put here.
1 /* this helper is called when task `prev` exhausted its budget or when
2 * it signaled a job completion */
3 static void demo_job_completion(struct task_struct *prev, int budget_exhausted)
4 {
5 /* call common helper code to compute the next release time, deadline,
6 * etc. */
7 prepare_for_next_period(prev);
8 }
Next, we add the demo_requeue() helper function. It is used to place a task on the appropriate queue. Depending on whether the task has a pending job, it is placed either in the (core-local) ready queue (if it has a pending job) or in the (also core-local) release queue (if the next job's earliest release time is in the future).
1 /* Add the task `tsk` to the appropriate queue. Assumes caller holds the ready lock.
2 */
3 static void demo_requeue(struct task_struct *tsk, struct demo_cpu_state *cpu_state)
4 {
5 if (is_released(tsk, litmus_clock())) {
6 /* Uses __add_ready() instead of add_ready() because we already
7 * hold the ready lock. */
8 __add_ready(&cpu_state->local_queues, tsk);
9 } else {
10 /* Uses add_release() because we DON'T have the release lock. */
11 add_release(&cpu_state->local_queues, tsk);
12 }
13 }
Note that demo_requeue() uses __add_ready(), but not __add_release(). This is because demo_requeue() will be called only from contexts where the calling thread already holds the lock for the ready queue.
Scheduling Logic
Finally, we can define the P-EDF scheduling logic. Conceptually, it
- first checks what state the previously scheduled real-time task is in (if any),
- then checks whether a higher-priority job is waiting in the ready queue (i.e., if a preemption is required),
- and finally returns the next task to be scheduled (which may be NULL if there is no real-time workload pending.
The scheduler is serialized (with respect to each core) using the ready queue lock local_state->local_queues.ready_lock. Reusing the ready queue lock to serialize scheduling decisions is a common idiom in LITMUSRT; alternatively, we could also define an additional spinlock inside struct demo_cpu_state.
1 static struct task_struct* demo_schedule(struct task_struct * prev)
2 {
3 struct demo_cpu_state *local_state = local_cpu_state();
4
5 /* next == NULL means "schedule background work". */
6 struct task_struct *next = NULL;
7
8 /* prev's task state */
9 int exists, out_of_time, job_completed, self_suspends, preempt, resched;
10
11 raw_spin_lock(&local_state->local_queues.ready_lock);
12
13 BUG_ON(local_state->scheduled && local_state->scheduled != prev);
14 BUG_ON(local_state->scheduled && !is_realtime(prev));
15
16 exists = local_state->scheduled != NULL;
17 self_suspends = exists && !is_running(prev);
18 out_of_time = exists && budget_enforced(prev)
19 && budget_exhausted(prev);
20 job_completed = exists && is_completed(prev);
21
22 /* preempt is true if task `prev` has lower priority than something on
23 * the ready queue. */
24 preempt = edf_preemption_needed(&local_state->local_queues, prev);
25
26 /* check all conditions that make us reschedule */
27 resched = preempt;
28
29 /* if `prev` suspends, it CANNOT be scheduled anymore => reschedule */
30 if (self_suspends)
31 resched = 1;
32
33 /* also check for (in-)voluntary job completions */
34 if (out_of_time || job_completed) {
35 demo_job_completion(prev, out_of_time);
36 resched = 1;
37 }
38
39 if (resched) {
40 /* First check if the previous task goes back onto the ready
41 * queue, which it does if it did not self_suspend.
42 */
43 if (exists && !self_suspends)
44 demo_requeue(prev, local_state);
45 next = __take_ready(&local_state->local_queues);
46 } else
47 /* No preemption is required. */
48 next = local_state->scheduled;
49
50 local_state->scheduled = next;
51
52
53 if (exists && prev != next)
54 TRACE_TASK(prev, "descheduled.\n");
55 if (next)
56 TRACE_TASK(next, "scheduled.\n");
57
58 /* This mandatory. It triggers a transition in the LITMUS^RT remote
59 * preemption state machine. Call this AFTER the plugin has made a local
60 * scheduling decision.
61 */
62 sched_state_task_picked();
63
64 raw_spin_unlock(&local_state->local_queues.ready_lock);
65
66 return next;
67 }
The scheduler is serialized in Line 11. Note that interrupts are already disabled when a scheduler plugin's schedule() callback is invoked, so we do not have to worry about (local) interrupts within demo_schedule().
Lines 13-14 assert that the following invariant holds: when a real-time task is scheduled on the local core, then it is pointed to by local_state->scheduled. If there is no real-time task scheduled, then local_state->scheduled is NULL. Note that prev may refer to a non-real-time task.
Lines 16-20 establish the state of prev:
exists is true if the previous task is a real-time task;
self_suspends is true if prev cannot be scheduled any longer;
out_of_time is true if the current job overran its budget; and
job_completed is true if the current job signaled completion via syscall.
Line 24 checks whether higher-priority work is pending (i.e., jobs with earlier deadlines) on the local ready queue.
Lines 30-37 determine whether a preemption / scheduling decision is required. No change in scheduling is required if the previous task does not self-suspend or complete and if no higher-priority work is pending.
Note that Line 35 calls the helper demo_job_completion(), which is simply a wrapper around prepare_for_next_period) as described above.
Finally, Lines 39-50 carry out the actual scheduling decision. If prev needs to be preempted (Lines 39-46), then the previous task is requeued (if required) in Lines 43-44 and a new task is taken from the ready queue in Line 45. Otherwise, next is simply the locally scheduled task (local_state->scheduled), which may be NULL. The "local state invariant" is maintained in Line 50.
Testing
With these changes in place, the kernel should compile and boot without problems. However, no scheduling is actually possible yet because all tasks are still being rejected. Before tasks can be accepted, however, we first need to add support for task state changes (i.e., self-suspensions).
On to the next step.