= 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. {{{#!highlight c #include #include }}} == 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. {{{#!highlight c /* this helper is called when task `prev` exhausted its budget or when * it signaled a job completion */ static void demo_job_completion(struct task_struct *prev, int budget_exhausted) { /* call common helper code to compute the next release time, deadline, * etc. */ prepare_for_next_period(prev); } }}} 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). {{{#!highlight c /* Add the task `tsk` to the appropriate queue. Assumes caller holds the ready lock. */ static void demo_requeue(struct task_struct *tsk, struct demo_cpu_state *cpu_state) { if (is_released(tsk, litmus_clock())) { /* Uses __add_ready() instead of add_ready() because we already * hold the ready lock. */ __add_ready(&cpu_state->local_queues, tsk); } else { /* Uses add_release() because we DON'T have the release lock. */ add_release(&cpu_state->local_queues, tsk); } } }}} 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 LITMUS^RT^; alternatively, we could also define an additional spinlock inside `struct demo_cpu_state`. {{{#!highlight c static struct task_struct* demo_schedule(struct task_struct * prev) { struct demo_cpu_state *local_state = local_cpu_state(); /* next == NULL means "schedule background work". */ struct task_struct *next = NULL; /* prev's task state */ int exists, out_of_time, job_completed, self_suspends, preempt, resched; raw_spin_lock(&local_state->local_queues.ready_lock); BUG_ON(local_state->scheduled && local_state->scheduled != prev); BUG_ON(local_state->scheduled && !is_realtime(prev)); exists = local_state->scheduled != NULL; self_suspends = exists && !is_running(prev); out_of_time = exists && budget_enforced(prev) && budget_exhausted(prev); job_completed = exists && is_completed(prev); /* preempt is true if task `prev` has lower priority than something on * the ready queue. */ preempt = edf_preemption_needed(&local_state->local_queues, prev); /* check all conditions that make us reschedule */ resched = preempt; /* if `prev` suspends, it CANNOT be scheduled anymore => reschedule */ if (self_suspends) resched = 1; /* also check for (in-)voluntary job completions */ if (out_of_time || job_completed) { demo_job_completion(prev, out_of_time); resched = 1; } if (resched) { /* First check if the previous task goes back onto the ready * queue, which it does if it did not self_suspend. */ if (exists && !self_suspends) demo_requeue(prev, local_state); next = __take_ready(&local_state->local_queues); } else /* No preemption is required. */ next = local_state->scheduled; local_state->scheduled = next; if (exists && prev != next) TRACE_TASK(prev, "descheduled.\n"); if (next) TRACE_TASK(next, "scheduled.\n"); /* This mandatory. It triggers a transition in the LITMUS^RT remote * preemption state machine. Call this AFTER the plugin has made a local * scheduling decision. */ sched_state_task_picked(); raw_spin_unlock(&local_state->local_queues.ready_lock); return next; } }}} 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 [[../Step6|next step]].