Implementation of the EDZL scheduler.wip-edzl-final

Implementation of the EDZL scheduler.  Zero-laxity points are
tracked by timers while jobs are in the pending state.  Locking
primatives are not supported.

1 files changed, 84 insertions, 22 deletions

diff --git a/litmus/sched_global_plugin.c b/litmus/sched_global_plugin.c
index 22dffa7d62fc..e94247b66b59 100644
--- a/litmus/sched_global_plugin.c
+++ b/litmus/sched_global_plugin.c
@@ -105,31 +105,11 @@ struct sched_global_plugin* active_gbl_plugin;
 /*********************************************************************/
 
 /* Priority-related functions */
-int gbl_preemption_needed(struct task_struct *t)
-{
-        /* we need the read lock for active_gbl_domain's ready_queue */
-        /* no need to preempt if there is nothing pending */
-        if (!__jobs_pending(&active_gbl_domain))
-                return 0;
-        /* we need to reschedule if t doesn't exist */
-        if (!t)
-                return 1;
-    
-        /* NOTE: We cannot check for non-preemptibility since we
-         *       don't know what address space we're currently in.
-         */
-    
-        /* make sure to get non-rt stuff out of the way */
-        return !is_realtime(t) || active_gbl_plugin->prio_order(__next_ready(&active_gbl_domain), t);
-}
-
 int gbl_ready_order(struct bheap_node* a, struct bheap_node* b)
 {
         return active_gbl_plugin->prio_order(bheap2task(a), bheap2task(b));
 }
 
-
-
 int gbl_cpu_lower_prio(struct bheap_node *_a, struct bheap_node *_b)
 {
         cpu_entry_t *a, *b;
@@ -243,7 +223,6 @@ void gbl_unlink(struct task_struct* t)
         }
 }
 
-
 /* preempt - force a CPU to reschedule
  */
 void gbl_preempt(cpu_entry_t *entry)
@@ -268,6 +247,71 @@ void gbl_requeue(struct task_struct* task)
         }
 }
 
+/*
+ * update_queue_position - call after changing the priority of 'task'.
+ */
+void gbl_update_queue_position(struct task_struct *task)
+{
+        /* We don't know whether task is in the ready queue. It should, but
+         * on a budget overrun it may already be in a release queue.  Hence,
+         * calling unlink() is not possible since it assumes that the task is
+         * not in a release queue.
+     */
+    
+        /* Assumption: caller holds active_gbl_domain_lock */
+    
+        int check_preempt = 0;
+    
+        if (tsk_rt(task)->linked_on != NO_CPU) {
+                TRACE_TASK(task, "%s: linked  on %d\n",
+                   __FUNCTION__, tsk_rt(task)->linked_on);
+                /* Task is scheduled; need to re-order CPUs.
+                 * We can't use heap_decrease() here since
+                 * the cpu_heap is ordered in reverse direction, so
+                 * it is actually an increase. */
+                bheap_delete(gbl_cpu_lower_prio, &active_gbl_plugin->cpu_heap,
+                     active_gbl_plugin->cpus[tsk_rt(task)->linked_on]->hn);
+                bheap_insert(gbl_cpu_lower_prio, &active_gbl_plugin->cpu_heap,
+                     active_gbl_plugin->cpus[tsk_rt(task)->linked_on]->hn);
+        } else {
+                /* task may be queued: first stop queue changes */
+                raw_spin_lock(&active_gbl_domain.release_lock);
+                if (is_queued(task)) {
+                        TRACE_TASK(task, "%s: is queued\n",
+                       __FUNCTION__);
+                        /* We need to update the position
+                         * of task in some heap. Note that this
+                         * may be a release heap. */
+                        check_preempt =
+            !bheap_decrease(gbl_ready_order,
+                            tsk_rt(task)->heap_node);
+                } else {
+                        /* Nothing to do: if it is not queued and not linked
+                         * then it is currently being moved by other code
+                         * (e.g., a timer interrupt handler) that will use the
+                         * correct priority when enqueuing the task. */
+                        TRACE_TASK(task, "%s: is NOT queued => Done.\n",
+                       __FUNCTION__);
+                }
+                raw_spin_unlock(&active_gbl_domain.release_lock);
+        
+                /* If task was enqueued in a release heap, then the following
+                 * preemption check is pointless, but we can't easily detect
+                 * that case. If you want to fix this, then consider that
+                 * simply adding a state flag requires O(n) time to update when
+                 * releasing n tasks, which conflicts with the goal to have
+                 * O(log n) merges. */
+                if (check_preempt) {
+                        /* heap_decrease() hit the top level of the heap: make
+                         * sure preemption checks get the right task, not the
+                         * potentially stale cache. */
+                        bheap_uncache_min(gbl_ready_order,
+                              &active_gbl_domain.ready_queue);
+                        gbl_check_for_preemptions();
+                }
+        }
+}
+
 
 /* check for any necessary preemptions */
 void gbl_check_for_preemptions(void)
@@ -276,7 +320,7 @@ void gbl_check_for_preemptions(void)
         cpu_entry_t* last;
     
         for(last = lowest_prio_cpu();
-            gbl_preemption_needed(last->linked);
+            active_gbl_plugin->preemption_needed(last->linked);
             last = lowest_prio_cpu())
     {
                 /* preemption necessary */
@@ -392,6 +436,24 @@ void gblv_job_arrival(struct task_struct* task)
         gbl_check_for_preemptions();
 }
 
+int gblv_preemption_needed(struct task_struct *t)
+{
+        /* we need the read lock for active_gbl_domain's ready_queue */
+        /* no need to preempt if there is nothing pending */
+        if (!__jobs_pending(&active_gbl_domain))
+                return 0;
+        /* we need to reschedule if t doesn't exist */
+        if (!t)
+                return 1;
+    
+        /* NOTE: We cannot check for non-preemptibility since we
+         *       don't know what address space we're currently in.
+         */
+    
+        /* make sure to get non-rt stuff out of the way */
+        return !is_realtime(t) || active_gbl_plugin->prio_order(__next_ready(&active_gbl_domain), t);
+}
+
 /* gbl_tick - this function is called for every local timer interrupt.
  *
  *                   checks whether the current task has expired and checks