Merge branch 'prop/robust-tie-break' into wip-gpu-rtas12

Conflicts:
	include/litmus/binheap.h
	include/litmus/fdso.h
	include/litmus/litmus.h
	litmus/Makefile
	litmus/binheap.c
	litmus/edf_common.c
	litmus/fdso.c
	litmus/jobs.c
	litmus/locking.c

31 files changed, 2840 insertions, 321 deletions

diff --git a/arch/x86/include/asm/feather_trace_32.h b/arch/x86/include/asm/feather_trace_32.h
index 70202f90f169..75e81a9f9382 100644
--- a/arch/x86/include/asm/feather_trace_32.h
+++ b/arch/x86/include/asm/feather_trace_32.h
@@ -1,12 +1,45 @@
+/* Copyright (c) 2007-2012 Björn Brandenburg, <bbb@mpi-sws.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
 /* Do not directly include this file. Include feather_trace.h instead */
 
-#define feather_callback __attribute__((regparm(0)))
+#define feather_callback __attribute__((regparm(3)))  __attribute__((used))
 
 /*
- * make the compiler reload any register that is not saved in
- * a cdecl function call
+ * Make the compiler reload any register that is not saved in a cdecl function
+ * call (minus the registers that we explicitly clobber as output registers).
  */
-#define CLOBBER_LIST "memory", "cc", "eax", "ecx", "edx"
+#define __FT_CLOBBER_LIST0 "memory", "cc", "eax", "edx", "ecx"
+#define __FT_CLOBBER_LIST1 "memory", "cc", "eax", "ecx"
+#define __FT_CLOBBER_LIST2 "memory", "cc", "eax"
+#define __FT_CLOBBER_LIST3 "memory", "cc", "eax"
+
+#define __FT_TMP1(x) "=d" (x)
+#define __FT_ARG1(x) "0" ((long) (x))
+#define __FT_TMP2(x) "=c" (x)
+#define __FT_ARG2(x) "1" ((long) (x))
+
+#define __FT_ARG3(x) "r" ((long) (x))
 
 #define ft_event(id, callback)                                  \
         __asm__ __volatile__(                                   \
@@ -16,64 +49,67 @@
             ".long " #id  ", 0, 1b, 2f                    \n\t" \
             ".previous                                    \n\t" \
             "2:                                           \n\t" \
-        : : : CLOBBER_LIST)
+            : : : __FT_CLOBBER_LIST0)
 
 #define ft_event0(id, callback)                                 \
         __asm__ __volatile__(                                   \
             "1: jmp 2f                                    \n\t" \
-            " subl $4, %%esp                              \n\t" \
-            " movl $" #id  ", (%%esp)                     \n\t" \
+            " movl $" #id  ", %%eax                       \n\t" \
             " call " #callback "                          \n\t" \
-            " addl $4, %%esp                              \n\t" \
             ".section __event_table, \"aw\"               \n\t" \
             ".long " #id  ", 0, 1b, 2f                    \n\t" \
             ".previous                                    \n\t" \
             "2:                                           \n\t" \
-        : :  : CLOBBER_LIST)
+            : : : __FT_CLOBBER_LIST0)
 
-#define ft_event1(id, callback, param)                          \
+#define ft_event1(id, callback, param)                          \
+        do {                                                    \
+                long __ft_tmp1;                                 \
         __asm__ __volatile__(                                   \
             "1: jmp 2f                                    \n\t" \
-            " subl $8, %%esp                              \n\t" \
-            " movl %0, 4(%%esp)                           \n\t" \
-            " movl $" #id  ", (%%esp)                     \n\t" \
+            " movl $" #id  ", %%eax                       \n\t" \
             " call " #callback "                          \n\t" \
-            " addl $8, %%esp                              \n\t" \
             ".section __event_table, \"aw\"               \n\t" \
             ".long " #id  ", 0, 1b, 2f                    \n\t" \
             ".previous                                    \n\t" \
             "2:                                           \n\t" \
-        : : "r" (param)  : CLOBBER_LIST)
+            : __FT_TMP1(__ft_tmp1)                              \
+            : __FT_ARG1(param)                                  \
+            : __FT_CLOBBER_LIST1);                              \
+        } while (0);
 
 #define ft_event2(id, callback, param, param2)                  \
+        do {                                                    \
+                long __ft_tmp1, __ft_tmp2;                      \
         __asm__ __volatile__(                                   \
             "1: jmp 2f                                    \n\t" \
-            " subl $12, %%esp                             \n\t" \
-            " movl %1, 8(%%esp)                           \n\t" \
-            " movl %0, 4(%%esp)                           \n\t" \
-            " movl $" #id  ", (%%esp)                     \n\t" \
+            " movl $" #id  ", %%eax                       \n\t" \
             " call " #callback "                          \n\t" \
-            " addl $12, %%esp                             \n\t" \
             ".section __event_table, \"aw\"               \n\t" \
             ".long " #id  ", 0, 1b, 2f                    \n\t" \
             ".previous                                    \n\t" \
             "2:                                           \n\t" \
-        : : "r" (param), "r" (param2)  : CLOBBER_LIST)
+            : __FT_TMP1(__ft_tmp1), __FT_TMP2(__ft_tmp2)        \
+            : __FT_ARG1(param), __FT_ARG2(param2)               \
+            : __FT_CLOBBER_LIST2);                              \
+        } while (0);
 
 
-#define ft_event3(id, callback, p, p2, p3)                      \
+#define ft_event3(id, callback, param, param2, param3)          \
+        do {                                                    \
+                long __ft_tmp1, __ft_tmp2;                      \
         __asm__ __volatile__(                                   \
             "1: jmp 2f                                    \n\t" \
-            " subl $16, %%esp                             \n\t" \
-            " movl %2, 12(%%esp)                          \n\t" \
-            " movl %1, 8(%%esp)                           \n\t" \
-            " movl %0, 4(%%esp)                           \n\t" \
-            " movl $" #id  ", (%%esp)                     \n\t" \
+            " subl $4, %%esp                              \n\t" \
+            " movl $" #id  ", %%eax                       \n\t" \
+            " movl %2, (%%esp)                            \n\t" \
             " call " #callback "                          \n\t" \
-            " addl $16, %%esp                             \n\t" \
+            " addl $4, %%esp                              \n\t" \
             ".section __event_table, \"aw\"               \n\t" \
             ".long " #id  ", 0, 1b, 2f                    \n\t" \
             ".previous                                    \n\t" \
             "2:                                           \n\t" \
-        : : "r" (p), "r" (p2), "r" (p3)  : CLOBBER_LIST)
-
+            : __FT_TMP1(__ft_tmp1), __FT_TMP2(__ft_tmp2)        \
+            : __FT_ARG1(param), __FT_ARG2(param2), __FT_ARG3(param3)    \
+            : __FT_CLOBBER_LIST3);                              \
+        } while (0);
diff --git a/arch/x86/include/asm/feather_trace_64.h b/arch/x86/include/asm/feather_trace_64.h
index 54ac2aeb3a28..5ce49e2eebba 100644
--- a/arch/x86/include/asm/feather_trace_64.h
+++ b/arch/x86/include/asm/feather_trace_64.h
@@ -1,67 +1,124 @@
+/* Copyright (c) 2010 Andrea Bastoni, <bastoni@cs.unc.edu>
+ * Copyright (c) 2012 Björn Brandenburg, <bbb@mpi-sws.org>
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining
+ * a copy of this software and associated documentation files (the
+ * "Software"), to deal in the Software without restriction, including
+ * without limitation the rights to use, copy, modify, merge, publish,
+ * distribute, sublicense, and/or sell copies of the Software, and to
+ * permit persons to whom the Software is furnished to do so, subject to
+ * the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+ * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
+ * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
+ * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
+ * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+ * SOFTWARE.
+ */
+
 /* Do not directly include this file. Include feather_trace.h instead */
 
 /* regparm is the default on x86_64 */
-#define feather_callback
+#define feather_callback  __attribute__((used))
 
-# define _EVENT_TABLE(id,from,to) \
+#define __FT_EVENT_TABLE(id,from,to) \
             ".section __event_table, \"aw\"\n\t" \
             ".balign 8\n\t" \
             ".quad " #id  ", 0, " #from ", " #to " \n\t" \
             ".previous \n\t"
 
 /*
- * x86_64 callee only owns rbp, rbx, r12 -> r15
- * the called can freely modify the others
+ * x86_64 caller only owns rbp, rbx, r12-r15;
+ * the callee can freely modify the others.
  */
-#define CLOBBER_LIST    "memory", "cc", "rdi", "rsi", "rdx", "rcx", \
+#define __FT_CLOBBER_LIST0      "memory", "cc", "rdi", "rsi", "rdx", "rcx", \
+                        "r8", "r9", "r10", "r11", "rax"
+
+#define __FT_CLOBBER_LIST1      "memory", "cc", "rdi", "rdx", "rcx", \
+                        "r8", "r9", "r10", "r11", "rax"
+
+#define __FT_CLOBBER_LIST2      "memory", "cc", "rdi", "rcx", \
                         "r8", "r9", "r10", "r11", "rax"
 
+#define __FT_CLOBBER_LIST3      "memory", "cc", "rdi", \
+                        "r8", "r9", "r10", "r11", "rax"
+
+/* The registers RDI, RSI, RDX, RCX, R8 and R9 are used for integer and pointer
+ * arguments. */
+
+/* RSI */
+#define __FT_TMP1(x) "=S" (x)
+#define __FT_ARG1(x) "0" ((long) (x))
+
+/* RDX */
+#define __FT_TMP2(x) "=d" (x)
+#define __FT_ARG2(x) "1" ((long) (x))
+
+/* RCX */
+#define __FT_TMP3(x) "=c" (x)
+#define __FT_ARG3(x) "2" ((long) (x))
+
 #define ft_event(id, callback)                                  \
         __asm__ __volatile__(                                   \
             "1: jmp 2f                                    \n\t" \
             " call " #callback "                          \n\t" \
-            _EVENT_TABLE(id,1b,2f) \
+            __FT_EVENT_TABLE(id,1b,2f)                          \
             "2:                                           \n\t" \
-        : : : CLOBBER_LIST)
+        : : : __FT_CLOBBER_LIST0)
 
 #define ft_event0(id, callback)                                 \
         __asm__ __volatile__(                                   \
             "1: jmp 2f                                    \n\t" \
             " movq $" #id ", %%rdi                        \n\t" \
             " call " #callback "                          \n\t" \
-            _EVENT_TABLE(id,1b,2f) \
+            __FT_EVENT_TABLE(id,1b,2f)                          \
             "2:                                           \n\t" \
-        : :  : CLOBBER_LIST)
+        : :  : __FT_CLOBBER_LIST0)
 
 #define ft_event1(id, callback, param)                          \
+        do {                                                    \
+                long __ft_tmp1;                                 \
         __asm__ __volatile__(                                   \
             "1: jmp 2f                                    \n\t" \
-            " movq %0, %%rsi                              \n\t" \
             " movq $" #id ", %%rdi                        \n\t" \
             " call " #callback "                          \n\t" \
-            _EVENT_TABLE(id,1b,2f) \
+            __FT_EVENT_TABLE(id,1b,2f)                          \
             "2:                                           \n\t" \
-        : : "r" (param)  : CLOBBER_LIST)
+            : __FT_TMP1(__ft_tmp1)                              \
+            : __FT_ARG1(param)                                  \
+            : __FT_CLOBBER_LIST1);                              \
+        } while (0);
 
 #define ft_event2(id, callback, param, param2)                  \
+        do {                                                    \
+                long __ft_tmp1, __ft_tmp2;                      \
         __asm__ __volatile__(                                   \
             "1: jmp 2f                                    \n\t" \
-            " movq %1, %%rdx                              \n\t" \
-            " movq %0, %%rsi                              \n\t" \
             " movq $" #id ", %%rdi                        \n\t" \
             " call " #callback "                          \n\t" \
-            _EVENT_TABLE(id,1b,2f) \
+            __FT_EVENT_TABLE(id,1b,2f)                          \
             "2:                                           \n\t" \
-        : : "r" (param), "r" (param2)  : CLOBBER_LIST)
+            : __FT_TMP1(__ft_tmp1), __FT_TMP2(__ft_tmp2)        \
+            : __FT_ARG1(param), __FT_ARG2(param2)               \
+            : __FT_CLOBBER_LIST2);                              \
+        } while (0);
 
-#define ft_event3(id, callback, p, p2, p3)                      \
+#define ft_event3(id, callback, param, param2, param3)          \
+        do {                                                    \
+                long __ft_tmp1, __ft_tmp2, __ft_tmp3;           \
         __asm__ __volatile__(                                   \
             "1: jmp 2f                                    \n\t" \
-            " movq %2, %%rcx                              \n\t" \
-            " movq %1, %%rdx                              \n\t" \
-            " movq %0, %%rsi                              \n\t" \
             " movq $" #id ", %%rdi                        \n\t" \
             " call " #callback "                          \n\t" \
-            _EVENT_TABLE(id,1b,2f) \
+            __FT_EVENT_TABLE(id,1b,2f)                          \
             "2:                                           \n\t" \
-        : : "r" (p), "r" (p2), "r" (p3)  : CLOBBER_LIST)
+            : __FT_TMP1(__ft_tmp1), __FT_TMP2(__ft_tmp2), __FT_TMP3(__ft_tmp3) \
+            : __FT_ARG1(param), __FT_ARG2(param2), __FT_ARG3(param3)    \
+            : __FT_CLOBBER_LIST3);                              \
+        } while (0);
diff --git a/include/litmus/binheap.h b/include/litmus/binheap.h
index 9e966e3886cb..901a30a3e296 100644
--- a/include/litmus/binheap.h
+++ b/include/litmus/binheap.h
@@ -42,10 +42,10 @@ struct binheap_node {
  * inlined (similar to Linux red/black tree) for greater efficiency.
  */
 typedef int (*binheap_order_t)(struct binheap_node *a,
-                                                           struct binheap_node *b);
+                                struct binheap_node *b);
 
 
-struct binheap_handle {
+struct binheap {
         struct binheap_node *root;
 
         /* pointer to node to take next inserted child */
@@ -59,6 +59,9 @@ struct binheap_handle {
 };
 
 
+/* Initialized heap nodes not in a heap have parent
+ * set to BINHEAP_POISON.
+ */
 #define BINHEAP_POISON  ((void*)(0xdeadbeef))
 
 
@@ -146,9 +149,8 @@ static inline void INIT_BINHEAP_NODE(struct binheap_node *n)
         n->ref_ptr = NULL;
 }
 
-static inline void INIT_BINHEAP_HANDLE(
-        struct binheap_handle *handle,
-        binheap_order_t compare)
+static inline void INIT_BINHEAP_HANDLE(struct binheap *handle,
+                                binheap_order_t compare)
 {
         handle->root = NULL;
         handle->next = NULL;
@@ -156,27 +158,25 @@ static inline void INIT_BINHEAP_HANDLE(
         handle->compare = compare;
 }
 
-/* Returns true (1) if binheap is empty. */
-static inline int binheap_empty(struct binheap_handle *handle)
+/* Returns true if binheap is empty. */
+static inline int binheap_empty(struct binheap *handle)
 {
         return(handle->root == NULL);
 }
 
-/* Returns true (1) if binheap node is in a heap. */
+/* Returns true if binheap node is in a heap. */
 static inline int binheap_is_in_heap(struct binheap_node *node)
 {
         return (node->parent != BINHEAP_POISON);
 }
 
+/* Returns true if binheap node is in given heap. */
+int binheap_is_in_this_heap(struct binheap_node *node, struct binheap* heap);
 
-int binheap_is_in_this_heap(struct binheap_node *node, struct binheap_handle* heap);
-
-
-
+/* Add a node to a heap */
 void __binheap_add(struct binheap_node *new_node,
-        struct binheap_handle *handle,
-        void *data);
-
+                                struct binheap *handle,
+                                void *data);
 
 /**
  * Removes the root node from the heap. The node is removed after coalescing
@@ -185,22 +185,21 @@ void __binheap_add(struct binheap_node *new_node,
  * The 'last' node in the tree is then swapped up to the root and bubbled
  * down.
  */
-void __binheap_delete_root(struct binheap_handle *handle,
-        struct binheap_node *container);
+void __binheap_delete_root(struct binheap *handle,
+                                struct binheap_node *container);
 
 /**
  * Delete an arbitrary node.  Bubble node to delete up to the root,
  * and then delete to root.
  */
-void __binheap_delete(
-        struct binheap_node *node_to_delete,
-        struct binheap_handle *handle);
+void __binheap_delete(struct binheap_node *node_to_delete,
+                                struct binheap *handle);
 
 /**
  * Bubble up a node whose pointer has decreased in value.
  */
 void __binheap_decrease(struct binheap_node *orig_node,
-                                                struct binheap_handle *handle);
+                                                struct binheap *handle);
 
 
 #endif
diff --git a/include/litmus/budget.h b/include/litmus/budget.h
index 732530e63491..33344ee8d5f9 100644
--- a/include/litmus/budget.h
+++ b/include/litmus/budget.h
@@ -5,4 +5,31 @@
  * the next task. */
 void update_enforcement_timer(struct task_struct* t);
 
+inline static int budget_exhausted(struct task_struct* t)
+{
+        return get_exec_time(t) >= get_exec_cost(t);
+}
+
+inline static lt_t budget_remaining(struct task_struct* t)
+{
+        if (!budget_exhausted(t))
+                return get_exec_cost(t) - get_exec_time(t);
+        else
+                /* avoid overflow */
+                return 0;
+}
+
+#define budget_enforced(t) (tsk_rt(t)->task_params.budget_policy != NO_ENFORCEMENT)
+
+#define budget_precisely_enforced(t) (tsk_rt(t)->task_params.budget_policy \
+                                      == PRECISE_ENFORCEMENT)
+
+static inline int requeue_preempted_job(struct task_struct* t)
+{
+        /* Add task to ready queue only if not subject to budget enforcement or
+         * if the job has budget remaining. t may be NULL.
+         */
+        return t && (!budget_exhausted(t) || !budget_enforced(t));
+}
+
 #endif
diff --git a/include/litmus/fdso.h b/include/litmus/fdso.h
index 1f5d3bd1a1db..35be59b970ee 100644
--- a/include/litmus/fdso.h
+++ b/include/litmus/fdso.h
@@ -12,7 +12,7 @@
 #include <linux/fs.h>
 #include <linux/slab.h>
 
-#define MAX_OBJECT_DESCRIPTORS 32
+#define MAX_OBJECT_DESCRIPTORS 85
 
 typedef enum  {
         MIN_OBJ_TYPE    = 0,
@@ -29,7 +29,13 @@ typedef enum  {
         KFMLP_SIMPLE_GPU_AFF_OBS = 7,
         KFMLP_GPU_AFF_OBS = 8,
 
-        MAX_OBJ_TYPE    = 8
+        MPCP_SEM        = 9,
+        MPCP_VS_SEM     = 10,
+        DPCP_SEM        = 11,
+
+        PCP_SEM         = 12,
+
+        MAX_OBJ_TYPE    = 12
 } obj_type_t;
 
 struct inode_obj_id {
diff --git a/include/litmus/fp_common.h b/include/litmus/fp_common.h
new file mode 100644
index 000000000000..dd1f7bf1e347
--- /dev/null
+++ b/include/litmus/fp_common.h
@@ -0,0 +1,105 @@
+/* Fixed-priority scheduler support.
+ */
+
+#ifndef __FP_COMMON_H__
+#define __FP_COMMON_H__
+
+#include <litmus/rt_domain.h>
+
+#include <asm/bitops.h>
+
+
+void fp_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
+                    release_jobs_t release);
+
+int fp_higher_prio(struct task_struct* first,
+                   struct task_struct* second);
+
+int fp_ready_order(struct bheap_node* a, struct bheap_node* b);
+
+#define FP_PRIO_BIT_WORDS (LITMUS_MAX_PRIORITY / BITS_PER_LONG)
+
+#if (LITMUS_MAX_PRIORITY % BITS_PER_LONG)
+#error LITMUS_MAX_PRIORITY must be a multiple of BITS_PER_LONG
+#endif
+
+/* bitmask-inexed priority queue */
+struct fp_prio_queue {
+        unsigned long   bitmask[FP_PRIO_BIT_WORDS];
+        struct bheap    queue[LITMUS_MAX_PRIORITY];
+};
+
+void fp_prio_queue_init(struct fp_prio_queue* q);
+
+static inline void fpq_set(struct fp_prio_queue* q, unsigned int index)
+{
+        unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
+        __set_bit(index % BITS_PER_LONG, word);
+}
+
+static inline void fpq_clear(struct fp_prio_queue* q, unsigned int index)
+{
+        unsigned long *word = q->bitmask + (index / BITS_PER_LONG);
+        __clear_bit(index % BITS_PER_LONG, word);
+}
+
+static inline unsigned int fpq_find(struct fp_prio_queue* q)
+{
+        int i;
+
+        /* loop optimizer should unroll this */
+        for (i = 0; i < FP_PRIO_BIT_WORDS; i++)
+                if (q->bitmask[i])
+                        return __ffs(q->bitmask[i]) + i * BITS_PER_LONG;
+
+        return LITMUS_MAX_PRIORITY; /* nothing found */
+}
+
+static inline void fp_prio_add(struct fp_prio_queue* q, struct task_struct* t, unsigned int index)
+{
+
+        BUG_ON(bheap_node_in_heap(tsk_rt(t)->heap_node));
+
+        fpq_set(q, index);
+        bheap_insert(fp_ready_order, &q->queue[index], tsk_rt(t)->heap_node);
+}
+
+static inline void fp_prio_remove(struct fp_prio_queue* q, struct task_struct* t, unsigned int index)
+{
+        BUG_ON(!is_queued(t));
+
+        bheap_delete(fp_ready_order, &q->queue[index], tsk_rt(t)->heap_node);
+        if (likely(bheap_empty(&q->queue[index])))
+                fpq_clear(q, index);
+}
+
+static inline struct task_struct* fp_prio_peek(struct fp_prio_queue* q)
+{
+        unsigned int idx = fpq_find(q);
+        struct bheap_node* hn;
+
+        if (idx < LITMUS_MAX_PRIORITY) {
+                hn = bheap_peek(fp_ready_order, &q->queue[idx]);
+                return bheap2task(hn);
+        } else
+                return NULL;
+}
+
+static inline struct task_struct* fp_prio_take(struct fp_prio_queue* q)
+{
+        unsigned int idx = fpq_find(q);
+        struct bheap_node* hn;
+
+        if (idx < LITMUS_MAX_PRIORITY) {
+                hn = bheap_take(fp_ready_order, &q->queue[idx]);
+                if (likely(bheap_empty(&q->queue[idx])))
+                        fpq_clear(q, idx);
+                return bheap2task(hn);
+        } else
+                return NULL;
+}
+
+int fp_preemption_needed(struct fp_prio_queue*  q, struct task_struct *t);
+
+
+#endif
diff --git a/include/litmus/ikglp_lock.h b/include/litmus/ikglp_lock.h
index af6f15178cb1..0b89c8135360 100644
--- a/include/litmus/ikglp_lock.h
+++ b/include/litmus/ikglp_lock.h
@@ -76,18 +76,18 @@ struct ikglp_semaphore
         int max_fifo_len; // max len of a fifo queue
         int nr_in_fifos;
 
-        struct binheap_handle top_m;  // min heap, base prio
+        struct binheap top_m;  // min heap, base prio
         int top_m_size;  // number of nodes in top_m
 
-        struct binheap_handle not_top_m; // max heap, base prio
+        struct binheap not_top_m; // max heap, base prio
 
-        struct binheap_handle donees;   // min-heap, base prio
+        struct binheap donees;  // min-heap, base prio
         struct fifo_queue *shortest_fifo_queue; // pointer to shortest fifo queue
 
         /* data structures for holding requests */
         struct fifo_queue *fifo_queues; // array nr_replicas in length
-        struct binheap_handle priority_queue;   // max-heap, base prio
-        struct binheap_handle donors;   // max-heap, base prio
+        struct binheap priority_queue;  // max-heap, base prio
+        struct binheap donors;  // max-heap, base prio
 
 #ifdef CONFIG_LITMUS_AFFINITY_LOCKING
         struct ikglp_affinity *aff_obs;
diff --git a/include/litmus/litmus.h b/include/litmus/litmus.h
index 71df378236f5..1d70ab713571 100644
--- a/include/litmus/litmus.h
+++ b/include/litmus/litmus.h
@@ -48,41 +48,28 @@ void litmus_exit_task(struct task_struct *tsk);
 /*      Realtime utility macros */
 #define get_rt_flags(t)         (tsk_rt(t)->flags)
 #define set_rt_flags(t,f)       (tsk_rt(t)->flags=(f))
+#define is_priority_boosted(t)  (tsk_rt(t)->priority_boosted)
+#define get_boost_start(t)  (tsk_rt(t)->boost_start_time)
+
+/* task_params macros */
 #define get_exec_cost(t)        (tsk_rt(t)->task_params.exec_cost)
-#define get_exec_time(t)        (tsk_rt(t)->job_params.exec_time)
 #define get_rt_period(t)        (tsk_rt(t)->task_params.period)
+#define get_rt_relative_deadline(t)     (tsk_rt(t)->task_params.relative_deadline)
 #define get_rt_phase(t)         (tsk_rt(t)->task_params.phase)
 #define get_partition(t)        (tsk_rt(t)->task_params.cpu)
+#define get_priority(t)         (tsk_rt(t)->task_params.priority)
+#define get_class(t)        (tsk_rt(t)->task_params.cls)
+
+/* job_param macros */
+#define get_exec_time(t)    (tsk_rt(t)->job_params.exec_time)
 #define get_deadline(t)         (tsk_rt(t)->job_params.deadline)
 #define get_period(t)           (tsk_rt(t)->task_params.period)
 #define get_release(t)          (tsk_rt(t)->job_params.release)
-#define get_class(t)            (tsk_rt(t)->task_params.cls)
-
-#define is_priority_boosted(t)  (tsk_rt(t)->priority_boosted)
-#define get_boost_start(t)      (tsk_rt(t)->boost_start_time)
+#define get_lateness(t)     (tsk_rt(t)->job_params.lateness)
 
 #define effective_priority(t) ((!(tsk_rt(t)->inh_task)) ? t : tsk_rt(t)->inh_task)
 #define base_priority(t) (t)
 
-inline static int budget_exhausted(struct task_struct* t)
-{
-        return get_exec_time(t) >= get_exec_cost(t);
-}
-
-inline static lt_t budget_remaining(struct task_struct* t)
-{
-        if (!budget_exhausted(t))
-                return get_exec_cost(t) - get_exec_time(t);
-        else
-                /* avoid overflow */
-                return 0;
-}
-
-#define budget_enforced(t) (tsk_rt(t)->task_params.budget_policy != NO_ENFORCEMENT)
-
-#define budget_precisely_enforced(t) (tsk_rt(t)->task_params.budget_policy \
-                                      == PRECISE_ENFORCEMENT)
-
 #define is_hrt(t)               \
         (tsk_rt(t)->task_params.cls == RT_CLASS_HARD)
 #define is_srt(t)               \
diff --git a/include/litmus/locking.h b/include/litmus/locking.h
index 36647fee03e4..296bbf6f7af0 100644
--- a/include/litmus/locking.h
+++ b/include/litmus/locking.h
@@ -14,7 +14,7 @@ struct nested_info
     struct binheap_node hp_binheap_node;
 };
 
-static inline struct task_struct* top_priority(struct binheap_handle* handle) {
+static inline struct task_struct* top_priority(struct binheap* handle) {
         if(!binheap_empty(handle)) {
                 return (struct task_struct*)(binheap_top_entry(handle, struct nested_info, hp_binheap_node)->hp_waiter_eff_prio);
         }
diff --git a/include/litmus/rt_param.h b/include/litmus/rt_param.h
index 04239c747f06..419ff0c88a65 100644
--- a/include/litmus/rt_param.h
+++ b/include/litmus/rt_param.h
@@ -26,7 +26,6 @@ static inline int lt_after_eq(lt_t a, lt_t b)
 typedef enum {
         RT_CLASS_HARD,
         RT_CLASS_SOFT,
-        RT_CLASS_SOFT_W_SLIP,
         RT_CLASS_BEST_EFFORT
 } task_class_t;
 
@@ -36,11 +35,33 @@ typedef enum {
         PRECISE_ENFORCEMENT  /* budgets are enforced with hrtimers */
 } budget_policy_t;
 
+/* We use the common priority interpretation "lower index == higher priority",
+ * which is commonly used in fixed-priority schedulability analysis papers.
+ * So, a numerically lower priority value implies higher scheduling priority,
+ * with priority 1 being the highest priority. Priority 0 is reserved for
+ * priority boosting. LITMUS_MAX_PRIORITY denotes the maximum priority value
+ * range.
+ */
+
+#define LITMUS_MAX_PRIORITY     512
+#define LITMUS_HIGHEST_PRIORITY   1
+#define LITMUS_LOWEST_PRIORITY    (LITMUS_MAX_PRIORITY - 1)
+
+/* Provide generic comparison macros for userspace,
+ * in case that we change this later. */
+#define litmus_higher_fixed_prio(a, b)  (a < b)
+#define litmus_lower_fixed_prio(a, b)   (a > b)
+#define litmus_is_valid_fixed_prio(p)           \
+        ((p) >= LITMUS_HIGHEST_PRIORITY &&      \
+         (p) <= LITMUS_LOWEST_PRIORITY)
+
 struct rt_task {
         lt_t            exec_cost;
         lt_t            period;
+        lt_t            relative_deadline;
         lt_t            phase;
         unsigned int    cpu;
+        unsigned int    priority;
         task_class_t    cls;
         budget_policy_t budget_policy; /* ignored by pfair */
 };
@@ -107,6 +128,12 @@ struct rt_job {
         /* How much service has this job received so far? */
         lt_t    exec_time;
 
+        /* By how much did the prior job miss its deadline by?
+         * Value differs from tardiness in that lateness may
+         * be negative (when job finishes before its deadline).
+         */
+        long long       lateness;
+
         /* Which job is this. This is used to let user space
          * specify which job to wait for, which is important if jobs
          * overrun. If we just call sys_sleep_next_period() then we
@@ -237,7 +264,7 @@ struct rt_param {
 
 #ifdef CONFIG_LITMUS_NESTED_LOCKING
         raw_spinlock_t                  hp_blocked_tasks_lock;
-        struct binheap_handle   hp_blocked_tasks;
+        struct binheap                  hp_blocked_tasks;
 
         /* pointer to lock upon which is currently blocked */
         struct litmus_lock* blocked_lock;
diff --git a/include/litmus/sched_trace.h b/include/litmus/sched_trace.h
index b1b71f6c5f0c..7af12f49c600 100644
--- a/include/litmus/sched_trace.h
+++ b/include/litmus/sched_trace.h
@@ -309,34 +309,93 @@ feather_callback void do_sched_trace_migration(unsigned long id,
 
 #endif
 
+#ifdef CONFIG_SCHED_LITMUS_TRACEPOINT
+
+#include <trace/events/litmus.h>
+
+#else
+
+/* Override trace macros to actually do nothing */
+#define trace_litmus_task_param(t)
+#define trace_litmus_task_release(t)
+#define trace_litmus_switch_to(t)
+#define trace_litmus_switch_away(prev)
+#define trace_litmus_task_completion(t, forced)
+#define trace_litmus_task_block(t)
+#define trace_litmus_task_resume(t)
+#define trace_litmus_sys_release(start)
+
+#endif
+
 
 #define SCHED_TRACE_BASE_ID 500
 
 
-#define sched_trace_task_name(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 1, do_sched_trace_task_name, t)
-#define sched_trace_task_param(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 2, do_sched_trace_task_param, t)
-#define sched_trace_task_release(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 3, do_sched_trace_task_release, t)
-#define sched_trace_task_switch_to(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 4, do_sched_trace_task_switch_to, t)
-#define sched_trace_task_switch_away(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 5, do_sched_trace_task_switch_away, t)
-#define sched_trace_task_completion(t, forced) \
-        SCHED_TRACE2(SCHED_TRACE_BASE_ID + 6, do_sched_trace_task_completion, t, \
-                     (unsigned long) forced)
-#define sched_trace_task_block(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 7, do_sched_trace_task_block, t)
-#define sched_trace_task_resume(t) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 8, do_sched_trace_task_resume, t)
-#define sched_trace_action(t, action) \
-        SCHED_TRACE2(SCHED_TRACE_BASE_ID + 9, do_sched_trace_action, t, \
-                     (unsigned long) action);
-/* when is a pointer, it does not need an explicit cast to unsigned long */
-#define sched_trace_sys_release(when) \
-        SCHED_TRACE(SCHED_TRACE_BASE_ID + 10, do_sched_trace_sys_release, when)
+#define sched_trace_task_name(t)                                        \
+        SCHED_TRACE(SCHED_TRACE_BASE_ID + 1,                            \
+                        do_sched_trace_task_name, t)
+
+#define sched_trace_task_param(t)                                       \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 2,                    \
+                                do_sched_trace_task_param, t);          \
+                trace_litmus_task_param(t);                             \
+        } while (0)
+
+#define sched_trace_task_release(t)                                     \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 3,                    \
+                                do_sched_trace_task_release, t);        \
+                trace_litmus_task_release(t);                           \
+        } while (0)
+
+#define sched_trace_task_switch_to(t)                                   \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 4,                    \
+                        do_sched_trace_task_switch_to, t);              \
+                trace_litmus_switch_to(t);                              \
+        } while (0)
+
+#define sched_trace_task_switch_away(t)                                 \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 5,                    \
+                        do_sched_trace_task_switch_away, t);            \
+                trace_litmus_switch_away(t);                            \
+        } while (0)
+
+#define sched_trace_task_completion(t, forced)                          \
+        do {                                                            \
+                SCHED_TRACE2(SCHED_TRACE_BASE_ID + 6,                   \
+                                do_sched_trace_task_completion, t,      \
+                                (unsigned long) forced);                \
+                trace_litmus_task_completion(t, forced);                \
+        } while (0)
+
+#define sched_trace_task_block(t)                                       \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 7,                    \
+                        do_sched_trace_task_block, t);                  \
+                trace_litmus_task_block(t);                             \
+        } while (0)
+
+#define sched_trace_task_resume(t)                                      \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 8,                    \
+                                do_sched_trace_task_resume, t);         \
+                trace_litmus_task_resume(t);                            \
+        } while (0)
+
+#define sched_trace_action(t, action)                                   \
+        SCHED_TRACE2(SCHED_TRACE_BASE_ID + 9,                           \
+                do_sched_trace_action, t, (unsigned long) action);
 
+/* when is a pointer, it does not need an explicit cast to unsigned long */
+#define sched_trace_sys_release(when)                                   \
+        do {                                                            \
+                SCHED_TRACE(SCHED_TRACE_BASE_ID + 10,                   \
+                        do_sched_trace_sys_release, when);              \
+                trace_litmus_sys_release(when);                         \
+        } while (0)
 
 #define sched_trace_tasklet_release(t) \
         SCHED_TRACE(SCHED_TRACE_BASE_ID + 11, do_sched_trace_tasklet_release, t)
diff --git a/include/litmus/wait.h b/include/litmus/wait.h
new file mode 100644
index 000000000000..ce1347c355f8
--- /dev/null
+++ b/include/litmus/wait.h
@@ -0,0 +1,57 @@
+#ifndef _LITMUS_WAIT_H_
+#define _LITMUS_WAIT_H_
+
+struct task_struct* __waitqueue_remove_first(wait_queue_head_t *wq);
+
+/* wrap regular wait_queue_t head */
+struct __prio_wait_queue {
+        wait_queue_t wq;
+
+        /* some priority point */
+        lt_t priority;
+        /* break ties in priority by lower tie_breaker */
+        unsigned int tie_breaker;
+};
+
+typedef struct __prio_wait_queue prio_wait_queue_t;
+
+static inline void init_prio_waitqueue_entry(prio_wait_queue_t *pwq,
+                                             struct task_struct* t,
+                                             lt_t priority)
+{
+        init_waitqueue_entry(&pwq->wq, t);
+        pwq->priority    = priority;
+        pwq->tie_breaker = 0;
+}
+
+static inline void init_prio_waitqueue_entry_tie(prio_wait_queue_t *pwq,
+                                                 struct task_struct* t,
+                                                 lt_t priority,
+                                                 unsigned int tie_breaker)
+{
+        init_waitqueue_entry(&pwq->wq, t);
+        pwq->priority    = priority;
+        pwq->tie_breaker = tie_breaker;
+}
+
+unsigned int __add_wait_queue_prio_exclusive(
+        wait_queue_head_t* head,
+        prio_wait_queue_t *new);
+
+static inline unsigned int add_wait_queue_prio_exclusive(
+        wait_queue_head_t* head,
+        prio_wait_queue_t *new)
+{
+        unsigned long flags;
+        unsigned int passed;
+
+        spin_lock_irqsave(&head->lock, flags);
+        passed = __add_wait_queue_prio_exclusive(head, new);
+
+        spin_unlock_irqrestore(&head->lock, flags);
+
+        return passed;
+}
+
+
+#endif
diff --git a/include/trace/events/litmus.h b/include/trace/events/litmus.h
new file mode 100644
index 000000000000..0fffcee02be0
--- /dev/null
+++ b/include/trace/events/litmus.h
@@ -0,0 +1,231 @@
+/*
+ * LITMUS^RT kernel style scheduling tracepoints
+ */
+#undef TRACE_SYSTEM
+#define TRACE_SYSTEM litmus
+
+#if !defined(_SCHED_TASK_TRACEPOINT_H) || defined(TRACE_HEADER_MULTI_READ)
+#define _SCHED_TASK_TRACEPOINT_H
+
+#include <linux/tracepoint.h>
+
+#include <litmus/litmus.h>
+#include <litmus/rt_param.h>
+
+/*
+ * Tracing task admission
+ */
+TRACE_EVENT(litmus_task_param,
+
+        TP_PROTO(struct task_struct *t),
+
+        TP_ARGS(t),
+
+        TP_STRUCT__entry(
+                __field( pid_t,         pid     )
+                __field( unsigned int,  job     )
+                __field( lt_t,          wcet    )
+                __field( lt_t,          period  )
+                __field( lt_t,          phase   )
+                __field( int,           partition )
+        ),
+
+        TP_fast_assign(
+                __entry->pid    = t ? t->pid : 0;
+                __entry->job    = t ? t->rt_param.job_params.job_no : 0;
+                __entry->wcet   = get_exec_cost(t);
+                __entry->period = get_rt_period(t);
+                __entry->phase  = get_rt_phase(t);
+                __entry->partition = get_partition(t);
+        ),
+
+        TP_printk("period(%d, %Lu).\nwcet(%d, %Lu).\n",
+                __entry->pid, __entry->period,
+                __entry->pid, __entry->wcet)
+);
+
+/*
+ * Tracing jobs release
+ */
+TRACE_EVENT(litmus_task_release,
+
+        TP_PROTO(struct task_struct *t),
+
+        TP_ARGS(t),
+
+        TP_STRUCT__entry(
+                __field( pid_t,         pid     )
+                __field( unsigned int,  job     )
+                __field( lt_t,          release )
+                __field( lt_t,          deadline        )
+        ),
+
+        TP_fast_assign(
+                __entry->pid    = t ? t->pid : 0;
+                __entry->job    = t ? t->rt_param.job_params.job_no : 0;
+                __entry->release        = get_release(t);
+                __entry->deadline       = get_deadline(t);
+        ),
+
+        TP_printk("release(job(%u, %u)): %Lu\ndeadline(job(%u, %u)): %Lu\n",
+                        __entry->pid, __entry->job, __entry->release,
+                        __entry->pid, __entry->job, __entry->deadline)
+);
+
+/*
+ * Tracepoint for switching to new task
+ */
+TRACE_EVENT(litmus_switch_to,
+
+        TP_PROTO(struct task_struct *t),
+
+        TP_ARGS(t),
+
+        TP_STRUCT__entry(
+                __field( pid_t,         pid     )
+                __field( unsigned int,  job     )
+                __field( lt_t,          when    )
+                __field( lt_t,          exec_time       )
+        ),
+
+        TP_fast_assign(
+                __entry->pid    = is_realtime(t) ? t->pid : 0;
+                __entry->job    = is_realtime(t) ? t->rt_param.job_params.job_no : 0;
+                __entry->when           = litmus_clock();
+                __entry->exec_time      = get_exec_time(t);
+        ),
+
+        TP_printk("switch_to(job(%u, %u)): %Lu (exec: %Lu)\n",
+                        __entry->pid, __entry->job,
+                        __entry->when, __entry->exec_time)
+);
+
+/*
+ * Tracepoint for switching away previous task
+ */
+TRACE_EVENT(litmus_switch_away,
+
+        TP_PROTO(struct task_struct *t),
+
+        TP_ARGS(t),
+
+        TP_STRUCT__entry(
+                __field( pid_t,         pid     )
+                __field( unsigned int,  job     )
+                __field( lt_t,          when    )
+                __field( lt_t,          exec_time       )
+        ),
+
+        TP_fast_assign(
+                __entry->pid    = is_realtime(t) ? t->pid : 0;
+                __entry->job    = is_realtime(t) ? t->rt_param.job_params.job_no : 0;
+                __entry->when           = litmus_clock();
+                __entry->exec_time      = get_exec_time(t);
+        ),
+
+        TP_printk("switch_away(job(%u, %u)): %Lu (exec: %Lu)\n",
+                        __entry->pid, __entry->job,
+                        __entry->when, __entry->exec_time)
+);
+
+/*
+ * Tracing jobs completion
+ */
+TRACE_EVENT(litmus_task_completion,
+
+        TP_PROTO(struct task_struct *t, unsigned long forced),
+
+        TP_ARGS(t, forced),
+
+        TP_STRUCT__entry(
+                __field( pid_t,         pid     )
+                __field( unsigned int,  job     )
+                __field( lt_t,          when    )
+                __field( unsigned long, forced  )
+        ),
+
+        TP_fast_assign(
+                __entry->pid    = t ? t->pid : 0;
+                __entry->job    = t ? t->rt_param.job_params.job_no : 0;
+                __entry->when   = litmus_clock();
+                __entry->forced = forced;
+        ),
+
+        TP_printk("completed(job(%u, %u)): %Lu (forced: %lu)\n",
+                        __entry->pid, __entry->job,
+                        __entry->when, __entry->forced)
+);
+
+/*
+ * Trace blocking tasks.
+ */
+TRACE_EVENT(litmus_task_block,
+
+        TP_PROTO(struct task_struct *t),
+
+        TP_ARGS(t),
+
+        TP_STRUCT__entry(
+                __field( pid_t,         pid     )
+                __field( lt_t,          when    )
+        ),
+
+        TP_fast_assign(
+                __entry->pid    = t ? t->pid : 0;
+                __entry->when   = litmus_clock();
+        ),
+
+        TP_printk("(%u) blocks: %Lu\n", __entry->pid, __entry->when)
+);
+
+/*
+ * Tracing jobs resume
+ */
+TRACE_EVENT(litmus_task_resume,
+
+        TP_PROTO(struct task_struct *t),
+
+        TP_ARGS(t),
+
+        TP_STRUCT__entry(
+                __field( pid_t,         pid     )
+                __field( unsigned int,  job     )
+                __field( lt_t,          when    )
+        ),
+
+        TP_fast_assign(
+                __entry->pid    = t ? t->pid : 0;
+                __entry->job    = t ? t->rt_param.job_params.job_no : 0;
+                __entry->when   = litmus_clock();
+        ),
+
+        TP_printk("resume(job(%u, %u)): %Lu\n",
+                        __entry->pid, __entry->job, __entry->when)
+);
+
+/*
+ * Trace synchronous release
+ */
+TRACE_EVENT(litmus_sys_release,
+
+        TP_PROTO(lt_t *start),
+
+        TP_ARGS(start),
+
+        TP_STRUCT__entry(
+                __field( lt_t,          rel     )
+                __field( lt_t,          when    )
+        ),
+
+        TP_fast_assign(
+                __entry->rel    = *start;
+                __entry->when   = litmus_clock();
+        ),
+
+        TP_printk("SynRelease(%Lu) at %Lu\n", __entry->rel, __entry->when)
+);
+
+#endif /* _SCHED_TASK_TRACEPOINT_H */
+
+/* Must stay outside the protection */
+#include <trace/define_trace.h>
diff --git a/kernel/sched.c b/kernel/sched.c
index f3d9a69a3777..9e8d8698323b 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -80,6 +80,9 @@
 #include "workqueue_sched.h"
 #include "sched_autogroup.h"
 
+#define CREATE_TRACE_POINTS
+#include <trace/events/sched.h>
+
 #include <litmus/sched_trace.h>
 #include <litmus/trace.h>
 
@@ -89,9 +92,6 @@
 
 static void litmus_tick(struct rq*, struct task_struct*);
 
-#define CREATE_TRACE_POINTS
-#include <trace/events/sched.h>
-
 /*
  * Convert user-nice values [ -20 ... 0 ... 19 ]
  * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
diff --git a/litmus/Kconfig b/litmus/Kconfig
index 8c156e4da528..95e0671e2aec 100644
--- a/litmus/Kconfig
+++ b/litmus/Kconfig
@@ -115,6 +115,52 @@ config SCHED_CPU_AFFINITY
 
           Say Yes if unsure.
 
+choice
+        prompt "EDF Tie-Break Behavior"
+        default EDF_TIE_BREAK_LATENESS_NORM
+        help
+          Allows the configuration of tie-breaking behavior when the deadlines
+          of two EDF-scheduled tasks are equal.
+        
+        config EDF_TIE_BREAK_LATENESS
+        bool "Lateness-based Tie Break"
+        help
+          Break ties between two jobs, A and B, based upon the lateness of their
+          prior jobs. The job with the greatest lateness has priority. Note that
+          lateness has a negative value if the prior job finished before its
+          deadline.
+        
+        config EDF_TIE_BREAK_LATENESS_NORM
+        bool "Normalized Lateness-based Tie Break"
+        help
+          Break ties between two jobs, A and B, based upon the lateness, normalized
+          by relative deadline, of their prior jobs. The job with the greatest
+          normalized lateness has priority. Note that lateness has a negative value
+          if the prior job finished before its deadline.
+          
+          Normalized lateness tie-breaks are likely desireable over non-normalized
+          tie-breaks if the execution times and/or relative deadlines of tasks in a
+          task set vary greatly.
+        
+        config EDF_TIE_BREAK_HASH
+        bool "Hash-based Tie Breaks"
+        help
+          Break ties between two jobs, A and B, with equal deadlines by using a
+          uniform hash; i.e.: hash(A.pid, A.job_num) < hash(B.pid, B.job_num). Job
+          A has ~50% of winning a given tie-break.
+        
+        config EDF_PID_TIE_BREAK
+        bool "PID-based Tie Breaks"
+        help
+          Break ties based upon OS-assigned thread IDs. Use this option if
+          required by algorithm's real-time analysis or per-task response-time
+          jitter must be minimized.
+        
+          NOTES:
+            * This tie-breaking method was default in Litmus 2012.2 and before.
+                
+endchoice
+
 endmenu
 
 menu "Tracing"
@@ -174,6 +220,24 @@ config SCHED_TASK_TRACE_SHIFT
                    10 =>   1k events
                     8 =>  512 events
 
+config SCHED_LITMUS_TRACEPOINT
+        bool "Enable Event/Tracepoint Tracing for real-time task tracing"
+        depends on TRACEPOINTS
+        default n
+        help
+          Enable kernel-style events (tracepoint) for Litmus. Litmus events
+          trace the same functions as the above sched_trace_XXX(), but can
+          be enabled independently.
+          Litmus tracepoints can be recorded and analyzed together (single
+          time reference) with all other kernel tracing events (e.g.,
+          sched:sched_switch, etc.).
+
+          This also enables a quick way to visualize schedule traces using
+          trace-cmd utility and kernelshark visualizer.
+
+          Say Yes for debugging and visualization purposes.
+          Say No for overhead tracing.
+
 config SCHED_OVERHEAD_TRACE
         bool "Record timestamps for overhead measurements"
         depends on FEATHER_TRACE
diff --git a/litmus/Makefile b/litmus/Makefile
index 080cbf694a41..59c018560ee9 100644
--- a/litmus/Makefile
+++ b/litmus/Makefile
@@ -11,15 +11,16 @@ obj-y     = sched_plugin.o litmus.o \
             sync.o \
             rt_domain.o \
             edf_common.o \
+            fp_common.o \
             fdso.o \
             locking.o \
             srp.o \
             bheap.o \
-        binheap.o \
+            binheap.o \
             ctrldev.o \
             sched_gsn_edf.o \
             sched_psn_edf.o \
-        kfmlp_lock.o
+            sched_pfp.o
 
 obj-$(CONFIG_PLUGIN_CEDF) += sched_cedf.o
 obj-$(CONFIG_PLUGIN_PFAIR) += sched_pfair.o
@@ -30,6 +31,7 @@ obj-$(CONFIG_SCHED_TASK_TRACE) += sched_task_trace.o
 obj-$(CONFIG_SCHED_DEBUG_TRACE) += sched_trace.o
 obj-$(CONFIG_SCHED_OVERHEAD_TRACE) += trace.o
 
+obj-$(CONFIG_LITMUS_LOCKING) += kfmlp_lock.o
 obj-$(CONFIG_LITMUS_NESTED_LOCKING) += rsm_lock.o ikglp_lock.o
 obj-$(CONFIG_LITMUS_SOFTIRQD) += litmus_softirq.o
 obj-$(CONFIG_LITMUS_PAI_SOFTIRQD) += litmus_pai_softirq.o
diff --git a/litmus/binheap.c b/litmus/binheap.c
index 8d42403ad52c..40a913f4b5a7 100644
--- a/litmus/binheap.c
+++ b/litmus/binheap.c
@@ -1,10 +1,8 @@
 #include <litmus/binheap.h>
 
-//extern void dump_node_data(struct binheap_node* parent, struct binheap_node* child);
-//extern void dump_node_data2(struct binheap_handle *handle, struct binheap_node* bad_node);
-
+/* Returns true of the root ancestor of node is the root of the given heap. */
 int binheap_is_in_this_heap(struct binheap_node *node,
-        struct binheap_handle* heap)
+        struct binheap* heap)
 {
         if(!binheap_is_in_heap(node)) {
                 return 0;
@@ -17,9 +15,10 @@ int binheap_is_in_this_heap(struct binheap_node *node,
         return (node == heap->root);
 }
 
+
 /* Update the node reference pointers.  Same logic as Litmus binomial heap. */
 static void __update_ref(struct binheap_node *parent,
-        struct binheap_node *child)
+                                struct binheap_node *child)
 {
         *(parent->ref_ptr) = child;
         *(child->ref_ptr) = parent;
@@ -27,15 +26,11 @@ static void __update_ref(struct binheap_node *parent,
         swap(parent->ref_ptr, child->ref_ptr);
 }
 
+
 /* Swaps data between two nodes. */
 static void __binheap_swap(struct binheap_node *parent,
-        struct binheap_node *child)
+                                struct binheap_node *child)
 {
-//      if(parent == BINHEAP_POISON || child == BINHEAP_POISON) {
-//              dump_node_data(parent, child);
-//              BUG();
-//      }
-
         swap(parent->data, child->data);
         __update_ref(parent, child);
 }
@@ -44,9 +39,9 @@ static void __binheap_swap(struct binheap_node *parent,
 /* Swaps memory and data between two nodes. Actual nodes swap instead of
  * just data.  Needed when we delete nodes from the heap.
  */
-static void __binheap_swap_safe(struct binheap_handle *handle,
-        struct binheap_node *a,
-        struct binheap_node *b)
+static void __binheap_swap_safe(struct binheap *handle,
+                                struct binheap_node *a,
+                                struct binheap_node *b)
 {
         swap(a->data, b->data);
         __update_ref(a, b);
@@ -130,7 +125,7 @@ static void __binheap_swap_safe(struct binheap_handle *handle,
  * Update the pointer to the last node in the complete binary tree.
  * Called internally after the root node has been deleted.
  */
-static void __binheap_update_last(struct binheap_handle *handle)
+static void __binheap_update_last(struct binheap *handle)
 {
         struct binheap_node *temp = handle->last;
 
@@ -154,16 +149,15 @@ static void __binheap_update_last(struct binheap_handle *handle)
                 temp = temp->left;
         }
 
-        //BUG_ON(!(temp->left == NULL && temp->right == NULL));
-
         handle->last = temp;
 }
 
+
 /**
  * Update the pointer to the node that will take the next inserted node.
  * Called internally after a node has been inserted.
  */
-static void __binheap_update_next(struct binheap_handle *handle)
+static void __binheap_update_next(struct binheap *handle)
 {
         struct binheap_node *temp = handle->next;
 
@@ -188,34 +182,22 @@ static void __binheap_update_next(struct binheap_handle *handle)
 
 
 /* bubble node up towards root */
-static void __binheap_bubble_up(
-        struct binheap_handle *handle,
-        struct binheap_node *node)
+static void __binheap_bubble_up(struct binheap *handle,
+                                struct binheap_node *node)
 {
-        //BUG_ON(!binheap_is_in_heap(node));
-//      if(!binheap_is_in_heap(node))
-//      {
-//              dump_node_data2(handle, node);
-//              BUG();
-//      }
+        /* let BINHEAP_POISON data bubble to the top */
 
         while((node->parent != NULL) &&
-                  ((node->data == BINHEAP_POISON) /* let BINHEAP_POISON data bubble to the top */ ||
+                  ((node->data == BINHEAP_POISON) ||
                    handle->compare(node, node->parent))) {
                           __binheap_swap(node->parent, node);
                           node = node->parent;
-
-//                        if(!binheap_is_in_heap(node))
-//                        {
-//                                dump_node_data2(handle, node);
-//                                BUG();
-//                        }
         }
 }
 
 
 /* bubble node down, swapping with min-child */
-static void __binheap_bubble_down(struct binheap_handle *handle)
+static void __binheap_bubble_down(struct binheap *handle)
 {
         struct binheap_node *node = handle->root;
 
@@ -242,17 +224,10 @@ static void __binheap_bubble_down(struct binheap_handle *handle)
 }
 
 
-
 void __binheap_add(struct binheap_node *new_node,
-        struct binheap_handle *handle,
-        void *data)
+                                struct binheap *handle,
+                                void *data)
 {
-//      if(binheap_is_in_heap(new_node))
-//      {
-//              dump_node_data2(handle, new_node);
-//              BUG();
-//      }
-
         new_node->data = data;
         new_node->ref = new_node;
         new_node->ref_ptr = &(new_node->ref);
@@ -296,7 +271,6 @@ void __binheap_add(struct binheap_node *new_node,
 }
 
 
-
 /**
  * Removes the root node from the heap. The node is removed after coalescing
  * the binheap_node with its original data pointer at the root of the tree.
@@ -304,17 +278,11 @@ void __binheap_add(struct binheap_node *new_node,
  * The 'last' node in the tree is then swapped up to the root and bubbled
  * down.
  */
-void __binheap_delete_root(struct binheap_handle *handle,
-        struct binheap_node *container)
+void __binheap_delete_root(struct binheap *handle,
+                                struct binheap_node *container)
 {
         struct binheap_node *root = handle->root;
 
-//      if(!binheap_is_in_heap(container))
-//      {
-//              dump_node_data2(handle, container);
-//              BUG();
-//      }
-
         if(root != container) {
                 /* coalesce */
                 __binheap_swap_safe(handle, root, container);
@@ -392,23 +360,11 @@ void __binheap_delete_root(struct binheap_handle *handle,
  * and then delete to root.
  */
 void __binheap_delete(struct binheap_node *node_to_delete,
-        struct binheap_handle *handle)
+                                struct binheap *handle)
 {
         struct binheap_node *target = node_to_delete->ref;
         void *temp_data = target->data;
 
-//      if(!binheap_is_in_heap(node_to_delete))
-//      {
-//              dump_node_data2(handle, node_to_delete);
-//              BUG();
-//      }
-//
-//      if(!binheap_is_in_heap(target))
-//      {
-//              dump_node_data2(handle, target);
-//              BUG();
-//      }
-
         /* temporarily set data to null to allow node to bubble up to the top. */
         target->data = BINHEAP_POISON;
 
@@ -416,28 +372,17 @@ void __binheap_delete(struct binheap_node *node_to_delete,
         __binheap_delete_root(handle, node_to_delete);
 
         node_to_delete->data = temp_data;  /* restore node data pointer */
-        //node_to_delete->parent = BINHEAP_POISON; /* poison the node */
 }
 
+
 /**
  * Bubble up a node whose pointer has decreased in value.
  */
 void __binheap_decrease(struct binheap_node *orig_node,
-        struct binheap_handle *handle)
+                                struct binheap *handle)
 {
         struct binheap_node *target = orig_node->ref;
 
-//      if(!binheap_is_in_heap(orig_node))
-//      {
-//              dump_node_data2(handle, orig_node);
-//              BUG();
-//      }
-//
-//      if(!binheap_is_in_heap(target))
-//      {
-//              dump_node_data2(handle, target);
-//              BUG();
-//      }
-//
         __binheap_bubble_up(handle, target);
 }
+
diff --git a/litmus/budget.c b/litmus/budget.c
index 310e9a3d4172..f7712be29adb 100644
--- a/litmus/budget.c
+++ b/litmus/budget.c
@@ -5,6 +5,8 @@
 #include <litmus/litmus.h>
 #include <litmus/preempt.h>
 
+#include <litmus/budget.h>
+
 struct enforcement_timer {
         /* The enforcement timer is used to accurately police
          * slice budgets. */
diff --git a/litmus/ctrldev.c b/litmus/ctrldev.c
index 6677a67cc945..9969ab17c190 100644
--- a/litmus/ctrldev.c
+++ b/litmus/ctrldev.c
@@ -30,27 +30,19 @@ static int alloc_ctrl_page(struct task_struct *t)
 static int map_ctrl_page(struct task_struct *t, struct vm_area_struct* vma)
 {
         int err;
-        unsigned long pfn;
 
         struct page* ctrl = virt_to_page(tsk_rt(t)->ctrl_page);
 
-        /* Increase ref count. Is decreased when vma is destroyed. */
-        get_page(ctrl);
-
-        /* compute page frame number */
-        pfn = page_to_pfn(ctrl);
-
         TRACE_CUR(CTRL_NAME
-                  ": mapping %p (pfn:%lx, %lx) to 0x%lx (prot:%lx)\n",
-                  tsk_rt(t)->ctrl_page, pfn, page_to_pfn(ctrl), vma->vm_start,
+                  ": mapping %p (pfn:%lx) to 0x%lx (prot:%lx)\n",
+                  tsk_rt(t)->ctrl_page,page_to_pfn(ctrl), vma->vm_start,
                   vma->vm_page_prot);
 
-        /* Map it into the vma. Make sure to use PAGE_SHARED, otherwise
-         * userspace actually gets a copy-on-write page. */
-        err = remap_pfn_range(vma, vma->vm_start, pfn, PAGE_SIZE, PAGE_SHARED);
+        /* Map it into the vma. */
+        err = vm_insert_page(vma, vma->vm_start, ctrl);
 
         if (err)
-                TRACE_CUR(CTRL_NAME ": remap_pfn_range() failed (%d)\n", err);
+                TRACE_CUR(CTRL_NAME ": vm_insert_page() failed (%d)\n", err);
 
         return err;
 }
@@ -63,19 +55,19 @@ static void litmus_ctrl_vm_close(struct vm_area_struct* vma)
         TRACE_CUR(CTRL_NAME
                   ": %p:%p vma:%p vma->vm_private_data:%p closed.\n",
                   (void*) vma->vm_start, (void*) vma->vm_end, vma,
-                  vma->vm_private_data, current->comm,
-                  current->pid);
+                  vma->vm_private_data);
 }
 
 static int litmus_ctrl_vm_fault(struct vm_area_struct* vma,
                                       struct vm_fault* vmf)
 {
-        /* This function should never be called, since
-         * all pages should have been mapped by mmap()
-         * already. */
-        TRACE_CUR("%s flags=0x%x\n", __FUNCTION__, vma->vm_flags);
+        TRACE_CUR("%s flags=0x%x (off:%ld)\n", __FUNCTION__,
+                  vma->vm_flags, vmf->pgoff);
+
+        /* This function should never be called, since all pages should have
+         * been mapped by mmap() already. */
+        WARN_ONCE(1, "Page faults should be impossible in the control page\n");
 
-        /* nope, you only get one page */
         return VM_FAULT_SIGBUS;
 }
 
@@ -103,9 +95,16 @@ static int litmus_ctrl_mmap(struct file* filp, struct vm_area_struct* vma)
                 return -EINVAL;
 
         vma->vm_ops = &litmus_ctrl_vm_ops;
-        /* this mapping should not be kept across forks,
-         * and cannot be expanded */
-        vma->vm_flags |= VM_DONTCOPY | VM_DONTEXPAND;
+        /* This mapping should not be kept across forks,
+         * cannot be expanded, and is not a "normal" page. */
+        vma->vm_flags |= VM_DONTCOPY | VM_DONTEXPAND | VM_IO;
+
+        /* We don't want the first write access to trigger a "minor" page fault
+         * to mark the page as dirty.  This is transient, private memory, we
+         * don't care if it was touched or not. __S011 means RW access, but not
+         * execute, and avoids copy-on-write behavior.
+         * See protection_map in mmap.c.  */
+        vma->vm_page_prot = __S011;
 
         err = alloc_ctrl_page(current);
         if (!err)
diff --git a/litmus/edf_common.c b/litmus/edf_common.c
index b346bdd65b3b..a1cdc10ea6f1 100644
--- a/litmus/edf_common.c
+++ b/litmus/edf_common.c
@@ -18,6 +18,30 @@
 
 #include <litmus/edf_common.h>
 
+#ifdef CONFIG_EDF_TIE_BREAK_LATENESS_NORM
+#include <litmus/fpmath.h>
+#endif
+
+#ifdef CONFIG_EDF_TIE_BREAK_HASH
+#include <linux/hash.h>
+static inline long edf_hash(struct task_struct *t)
+{
+        /* pid is 32 bits, so normally we would shove that into the
+         * upper 32-bits and and put the job number in the bottom
+         * and hash the 64-bit number with hash_64(). Sadly,
+         * in testing, hash_64() doesn't distribute keys were the
+         * upper bits are close together (as would be the case with
+         * pids) and job numbers are equal (as would be the case with
+         * synchronous task sets with all relative deadlines equal).
+         *
+         * A 2006 Linux patch proposed the following solution
+         * (but for some reason it wasn't accepted...).
+         *
+         * At least this workaround works for 32-bit systems as well.
+         */
+        return hash_32(hash_32((u32)tsk_rt(t)->job_params.job_no, 32) ^ t->pid, 32);
+}
+#endif
 
 
 /* edf_higher_prio -  returns true if first has a higher EDF priority
@@ -88,58 +112,90 @@ int edf_higher_prio(struct task_struct* first, struct task_struct* second)
 
 #endif
 
-//      // rate-monotonic for testing
-//      if (!is_realtime(second_task)) {
-//              return true;
-//      }
-//
-//      if (shorter_period(first_task, second_task)) {
-//              return true;
-//      }
-//
-//      if (get_period(first_task) == get_period(second_task)) {
-//              if (first_task->pid < second_task->pid) {
-//                      return true;
-//              }
-//              else if (first_task->pid == second_task->pid) {
-//                      return !second->rt_param.inh_task;
-//              }
-//      }
-
         if (!is_realtime(second_task)) {
-                return true;
+                return 1;
         }
-
-        if (earlier_deadline(first_task, second_task)) {
-                return true;
+        else if (earlier_deadline(first_task, second_task)) {
+                return 1;
         }
-        if (get_deadline(first_task) == get_deadline(second_task)) {
-
-                if (shorter_period(first_task, second_task)) {
-                        return true;
+        else if (get_deadline(first_task) == get_deadline(second_task)) {
+                /* Need to tie break. All methods must set pid_break to 0/1 if
+                 * first_task does not have priority over second_task.
+                 */
+                int pid_break;
+
+#if defined(CONFIG_EDF_TIE_BREAK_LATENESS)
+        /* Tie break by lateness. Jobs with greater lateness get
+                 * priority. This should spread tardiness across all tasks,
+                 * especially in task sets where all tasks have the same
+                 * period and relative deadlines.
+                 */
+                if (get_lateness(first_task) > get_lateness(second_task)) {
+                        return 1;
+                }   
+                pid_break = (get_lateness(first_task) == get_lateness(second_task));
+
+
+#elif defined(CONFIG_EDF_TIE_BREAK_LATENESS_NORM)
+                /* Tie break by lateness, normalized by relative deadline. Jobs with
+                 * greater normalized lateness get priority.
+                 *
+                 * Note: Considered using the algebraically equivalent
+                 *      lateness(first)*relative_deadline(second) >
+                                        lateness(second)*relative_deadline(first)
+                 * to avoid fixed-point math, but values are prone to overflow if inputs
+                 * are on the order of several seconds, even in 64-bit.
+                 */
+                fp_t fnorm = _frac(get_lateness(first_task),
+                                                   get_rt_relative_deadline(first_task));
+                fp_t snorm = _frac(get_lateness(second_task),
+                                                   get_rt_relative_deadline(second_task));
+                if (_gt(fnorm, snorm)) {
+                        return 1;
+                }
+                pid_break = _eq(fnorm, snorm);
+                
+                
+#elif defined(CONFIG_EDF_TIE_BREAK_HASH)
+                /* Tie break by comparing hashs of (pid, job#) tuple.  There should be
+                 * a 50% chance that first_task has a higher priority than second_task.
+                 */
+                long fhash = edf_hash(first_task);
+                long shash = edf_hash(second_task);
+                if (fhash < shash) {
+                        return 1;
                 }
-                if (get_rt_period(first_task) == get_rt_period(second_task)) {
+                pid_break = (fhash == shash);
+#else
+                
+                
+                /* CONFIG_EDF_PID_TIE_BREAK */
+                pid_break = 1; // fall through to tie-break by pid;
+#endif
+
+                /* Tie break by pid */
+                if(pid_break) {
                         if (first_task->pid < second_task->pid) {
-                                return true;
+                                return 1;
                         }
-                        if (first_task->pid == second_task->pid) {
+                        else if (first_task->pid == second_task->pid) {
 #ifdef CONFIG_LITMUS_SOFTIRQD
-                                if (first_task->rt_param.is_proxy_thread <
+                                if (first_task->rt_param.is_proxy_thread < 
                                         second_task->rt_param.is_proxy_thread) {
-                                        return true;
-                                }
-                                if(first_task->rt_param.is_proxy_thread == second_task->rt_param.is_proxy_thread) {
-                                        return !second->rt_param.inh_task;
+                                        return 1;
                                 }
-#else
-                                return !second->rt_param.inh_task;
 #endif
+                                /* If the PIDs are the same then the task with the
+                                 * inherited priority wins.
+                                 */
+                                if (!second_task->rt_param.inh_task) {
+                                        return 1;
+                                }
                         }
-
                 }
         }
 
-        return false;
+        return 0; /* fall-through. prio(second_task) > prio(first_task) */
 }
 
 
diff --git a/litmus/fdso.c b/litmus/fdso.c
index 18fc61b6414a..bac6a35fa17d 100644
--- a/litmus/fdso.c
+++ b/litmus/fdso.c
@@ -36,6 +36,10 @@ static const struct fdso_ops* fdso_ops[] = {
         &generic_affinity_ops, /* KFMLP_SIMPLE_GPU_AFF_OBS */
         &generic_affinity_ops, /* KFMLP_GPU_AFF_OBS */
 #endif
+        &generic_lock_ops, /* MPCP_SEM */
+        &generic_lock_ops, /* MPCP_VS_SEM */
+        &generic_lock_ops, /* DPCP_SEM */
+        &generic_lock_ops, /* PCP_SEM */
 };
 
 static int fdso_create(void** obj_ref, obj_type_t type, void* __user config)
diff --git a/litmus/fp_common.c b/litmus/fp_common.c
new file mode 100644
index 000000000000..31fc2db20adf
--- /dev/null
+++ b/litmus/fp_common.c
@@ -0,0 +1,119 @@
+/*
+ * litmus/fp_common.c
+ *
+ * Common functions for fixed-priority scheduler.
+ */
+
+#include <linux/percpu.h>
+#include <linux/sched.h>
+#include <linux/list.h>
+
+#include <litmus/litmus.h>
+#include <litmus/sched_plugin.h>
+#include <litmus/sched_trace.h>
+
+#include <litmus/fp_common.h>
+
+/* fp_higher_prio -  returns true if first has a higher static priority
+ *                   than second. Deadline ties are broken by PID.
+ *
+ * both first and second may be NULL
+ */
+int fp_higher_prio(struct task_struct* first,
+                   struct task_struct* second)
+{
+        struct task_struct *first_task = first;
+        struct task_struct *second_task = second;
+
+        /* There is no point in comparing a task to itself. */
+        if (unlikely(first && first == second)) {
+                TRACE_TASK(first,
+                           "WARNING: pointless FP priority comparison.\n");
+                return 0;
+        }
+
+
+        /* check for NULL tasks */
+        if (!first || !second)
+                return first && !second;
+
+#ifdef CONFIG_LITMUS_LOCKING
+
+        /* Check for inherited priorities. Change task
+         * used for comparison in such a case.
+         */
+        if (unlikely(first->rt_param.inh_task))
+                first_task = first->rt_param.inh_task;
+        if (unlikely(second->rt_param.inh_task))
+                second_task = second->rt_param.inh_task;
+
+        /* Check for priority boosting. Tie-break by start of boosting.
+         */
+        if (unlikely(is_priority_boosted(first_task))) {
+                /* first_task is boosted, how about second_task? */
+                if (!is_priority_boosted(second_task) ||
+                    lt_before(get_boost_start(first_task),
+                              get_boost_start(second_task)))
+                        return 1;
+                else
+                        return 0;
+        } else if (unlikely(is_priority_boosted(second_task)))
+                /* second_task is boosted, first is not*/
+                return 0;
+
+#endif
+
+
+        return !is_realtime(second_task)  ||
+
+                get_priority(first_task) < get_priority(second_task) ||
+
+                /* Break by PID.
+                 */
+                (get_priority(first_task) == get_priority(second_task) &&
+                (first_task->pid < second_task->pid ||
+
+                /* If the PIDs are the same then the task with the inherited
+                 * priority wins.
+                 */
+                (first_task->pid == second_task->pid &&
+                 !second->rt_param.inh_task)));
+}
+
+int fp_ready_order(struct bheap_node* a, struct bheap_node* b)
+{
+        return fp_higher_prio(bheap2task(a), bheap2task(b));
+}
+
+void fp_domain_init(rt_domain_t* rt, check_resched_needed_t resched,
+                    release_jobs_t release)
+{
+        rt_domain_init(rt,  fp_ready_order, resched, release);
+}
+
+/* need_to_preempt - check whether the task t needs to be preempted
+ */
+int fp_preemption_needed(struct fp_prio_queue *q, struct task_struct *t)
+{
+        struct task_struct *pending;
+
+        pending = fp_prio_peek(q);
+
+        if (!pending)
+                return 0;
+        if (!t)
+                return 1;
+
+        /* make sure to get non-rt stuff out of the way */
+        return !is_realtime(t) || fp_higher_prio(pending, t);
+}
+
+void fp_prio_queue_init(struct fp_prio_queue* q)
+{
+        int i;
+
+        for (i = 0; i < FP_PRIO_BIT_WORDS; i++)
+                q->bitmask[i] = 0;
+        for (i = 0; i < LITMUS_MAX_PRIORITY; i++)
+                bheap_init(&q->queue[i]);
+}
diff --git a/litmus/jobs.c b/litmus/jobs.c
index 1d97462cc128..fb093c03d53d 100644
--- a/litmus/jobs.c
+++ b/litmus/jobs.c
@@ -6,26 +6,13 @@
 #include <litmus/litmus.h>
 #include <litmus/jobs.h>
 
-void prepare_for_next_period(struct task_struct *t)
+static inline void setup_release(struct task_struct *t, lt_t release)
 {
-        BUG_ON(!t);
         /* prepare next release */
-
-        if(tsk_rt(t)->task_params.cls == RT_CLASS_SOFT_W_SLIP) {
-                /* allow the release point to slip if we've passed our deadline. */
-                lt_t now = litmus_clock();
-                t->rt_param.job_params.release =
-                        (t->rt_param.job_params.deadline < now) ?
-                                now : t->rt_param.job_params.deadline;
-                t->rt_param.job_params.deadline =
-                        t->rt_param.job_params.release + get_rt_period(t);
-        }
-        else {
-                t->rt_param.job_params.release   = t->rt_param.job_params.deadline;
-                t->rt_param.job_params.deadline += get_rt_period(t);
-        }
-
+        t->rt_param.job_params.release = release;
+        t->rt_param.job_params.deadline = release + get_rt_relative_deadline(t);
         t->rt_param.job_params.exec_time = 0;
+
         /* update job sequence number */
         t->rt_param.job_params.job_no++;
 
@@ -33,10 +20,24 @@ void prepare_for_next_period(struct task_struct *t)
         t->rt.time_slice = 1;
 }
 
+void prepare_for_next_period(struct task_struct *t)
+{
+        BUG_ON(!t);
+
+        /* Record lateness before we set up the next job's
+         * release and deadline. Lateness may be negative.
+         */
+        t->rt_param.job_params.lateness =
+                (long long)litmus_clock() - 
+                (long long)t->rt_param.job_params.deadline;
+
+        setup_release(t, get_release(t) + get_rt_period(t));
+}
+
 void release_at(struct task_struct *t, lt_t start)
 {
-        t->rt_param.job_params.deadline = start;
-        prepare_for_next_period(t);
+        BUG_ON(!t);
+        setup_release(t, start);
         set_rt_flags(t, RT_F_RUNNING);
 }
 
diff --git a/litmus/litmus.c b/litmus/litmus.c
index 91ec65894379..83a860c52e17 100644
--- a/litmus/litmus.c
+++ b/litmus/litmus.c
@@ -128,21 +128,25 @@ asmlinkage long sys_set_rt_task_param(pid_t pid, struct rt_task __user * param)
                 goto out_unlock;
         }
 
+        /* set relative deadline to be implicit if left unspecified */
+        if (tp.relative_deadline == 0)
+                tp.relative_deadline = tp.period;
+
         if (tp.exec_cost <= 0)
                 goto out_unlock;
         if (tp.period <= 0)
                 goto out_unlock;
         if (!cpu_online(tp.cpu))
                 goto out_unlock;
-        if (tp.period < tp.exec_cost)
+        if (min(tp.relative_deadline, tp.period) < tp.exec_cost) /*density check*/
         {
                 printk(KERN_INFO "litmus: real-time task %d rejected "
-                       "because wcet > period\n", pid);
+                       "because task density > 1.0\n", pid);
                 goto out_unlock;
         }
-        if (    tp.cls != RT_CLASS_HARD &&
-                tp.cls != RT_CLASS_SOFT &&
-                tp.cls != RT_CLASS_BEST_EFFORT)
+        if (tp.cls != RT_CLASS_HARD &&
+            tp.cls != RT_CLASS_SOFT &&
+            tp.cls != RT_CLASS_BEST_EFFORT)
         {
                 printk(KERN_INFO "litmus: real-time task %d rejected "
                                  "because its class is invalid\n", pid);
@@ -415,11 +419,14 @@ long litmus_admit_task(struct task_struct* tsk)
 
         BUG_ON(is_realtime(tsk));
 
-        if (get_rt_period(tsk) == 0 ||
-            get_exec_cost(tsk) > get_rt_period(tsk)) {
-                TRACE_TASK(tsk, "litmus admit: invalid task parameters "
-                           "(%lu, %lu)\n",
-                           get_exec_cost(tsk), get_rt_period(tsk));
+        if (get_rt_relative_deadline(tsk) == 0 ||
+            get_exec_cost(tsk) >
+                        min(get_rt_relative_deadline(tsk), get_rt_period(tsk)) ) {
+                TRACE_TASK(tsk,
+                        "litmus admit: invalid task parameters "
+                        "(e = %lu, p = %lu, d = %lu)\n",
+                        get_exec_cost(tsk), get_rt_period(tsk),
+                        get_rt_relative_deadline(tsk));
                 retval = -EINVAL;
                 goto out;
         }
diff --git a/litmus/locking.c b/litmus/locking.c
index 718a5a3281d7..12a23eb715cc 100644
--- a/litmus/locking.c
+++ b/litmus/locking.c
@@ -5,6 +5,7 @@
 #include <litmus/sched_plugin.h>
 #include <litmus/trace.h>
 #include <litmus/litmus.h>
+#include <litmus/wait.h>
 
 #ifdef CONFIG_LITMUS_DGL_SUPPORT
 #include <linux/uaccess.h>
@@ -507,6 +508,38 @@ asmlinkage long sys_litmus_dgl_unlock(void* __user usr_dgl_ods, int dgl_size)
 
 #endif
 
+unsigned int __add_wait_queue_prio_exclusive(
+        wait_queue_head_t* head,
+        prio_wait_queue_t *new)
+{
+        struct list_head *pos;
+        unsigned int passed = 0;
+
+        new->wq.flags |= WQ_FLAG_EXCLUSIVE;
+
+        /* find a spot where the new entry is less than the next */
+        list_for_each(pos, &head->task_list) {
+                prio_wait_queue_t* queued = list_entry(pos, prio_wait_queue_t,
+                                                       wq.task_list);
+
+                if (unlikely(lt_before(new->priority, queued->priority) ||
+                             (new->priority == queued->priority &&
+                              new->tie_breaker < queued->tie_breaker))) {
+                        /* pos is not less than new, thus insert here */
+                        __list_add(&new->wq.task_list, pos->prev, pos);
+                        goto out;
+                }
+                passed++;
+        }
+
+        /* if we get to this point either the list is empty or every entry
+         * queued element is less than new.
+         * Let's add new to the end. */
+        list_add_tail(&new->wq.task_list, &head->task_list);
+out:
+        return passed;
+}
+
 #else  // CONFIG_LITMUS_LOCKING
 
 struct fdso_ops generic_lock_ops = {};
diff --git a/litmus/rt_domain.c b/litmus/rt_domain.c
index d405854cd39c..d0b796611bea 100644
--- a/litmus/rt_domain.c
+++ b/litmus/rt_domain.c
@@ -300,9 +300,11 @@ void rt_domain_init(rt_domain_t *rt,
  */
 void __add_ready(rt_domain_t* rt, struct task_struct *new)
 {
-        TRACE("rt: adding %s/%d (%llu, %llu) rel=%llu to ready queue at %llu\n",
-              new->comm, new->pid, get_exec_cost(new), get_rt_period(new),
-              get_release(new), litmus_clock());
+        TRACE("rt: adding %s/%d (%llu, %llu, %llu) rel=%llu "
+                "to ready queue at %llu\n",
+                new->comm, new->pid,
+                get_exec_cost(new), get_rt_period(new), get_rt_relative_deadline(new),
+                get_release(new), litmus_clock());
 
         BUG_ON(bheap_node_in_heap(tsk_rt(new)->heap_node));
 
diff --git a/litmus/sched_cedf.c b/litmus/sched_cedf.c
index be14dbec6ed2..0460e232d6e6 100644
--- a/litmus/sched_cedf.c
+++ b/litmus/sched_cedf.c
@@ -35,6 +35,7 @@
 #include <litmus/litmus.h>
 #include <litmus/jobs.h>
 #include <litmus/preempt.h>
+#include <litmus/budget.h>
 #include <litmus/sched_plugin.h>
 #include <litmus/edf_common.h>
 #include <litmus/sched_trace.h>
@@ -134,7 +135,7 @@ typedef struct clusterdomain {
         /* map of this cluster cpus */
         cpumask_var_t   cpu_map;
         /* the cpus queue themselves according to priority in here */
-        struct binheap_handle cpu_heap;
+        struct binheap cpu_heap;
         /* lock for this cluster */
 #define cluster_lock domain.ready_lock
 
@@ -362,11 +363,11 @@ static void check_for_preemptions(cedf_domain_t *cluster)
                                                 &per_cpu(cedf_cpu_entries, task_cpu(task)));
                         if(affinity)
                                 last = affinity;
-                        else if(last->linked)
+                        else if(requeue_preempted_job(last->linked))
                                 requeue(last->linked);
                 }
 #else
-                if (last->linked)
+                if (requeue_preempted_job(last->linked))
                         requeue(last->linked);
 #endif
                 link_task_to_cpu(task, last);
@@ -861,9 +862,9 @@ static struct task_struct* cedf_schedule(struct task_struct * prev)
         /* Any task that is preemptable and either exhausts its execution
          * budget or wants to sleep completes. We may have to reschedule after
          * this. Don't do a job completion if we block (can't have timers running
-         * for blocked jobs). Preemption go first for the same reason.
+         * for blocked jobs).
          */
-        if (!np && (out_of_time || sleep) && !blocks && !preempt)
+        if (!np && (out_of_time || sleep) && !blocks)
                 job_completion(entry->scheduled, !sleep);
 
         /* Link pending task if we became unlinked.
diff --git a/litmus/sched_gsn_edf.c b/litmus/sched_gsn_edf.c
index 8c48757fa86c..11304d634661 100644
--- a/litmus/sched_gsn_edf.c
+++ b/litmus/sched_gsn_edf.c
@@ -22,6 +22,7 @@
 #include <litmus/sched_trace.h>
 
 #include <litmus/preempt.h>
+#include <litmus/budget.h>
 
 #include <litmus/bheap.h>
 #include <litmus/binheap.h>
@@ -136,7 +137,7 @@ DEFINE_PER_CPU(cpu_entry_t, gsnedf_cpu_entries);
 cpu_entry_t* gsnedf_cpus[NR_CPUS];
 
 /* the cpus queue themselves according to priority in here */
-static struct binheap_handle gsnedf_cpu_heap;
+static struct binheap gsnedf_cpu_heap;
 
 static rt_domain_t gsnedf;
 #define gsnedf_lock (gsnedf.ready_lock)
@@ -340,11 +341,11 @@ static void check_for_preemptions(void)
                                                 &per_cpu(gsnedf_cpu_entries, task_cpu(task)));
                         if (affinity)
                                 last = affinity;
-                        else if (last->linked)
+                        else if (requeue_preempted_job(last->linked))
                                 requeue(last->linked);
                 }
 #else
-                if (last->linked)
+                if (requeue_preempted_job(last->linked))
                         requeue(last->linked);
 #endif
 
@@ -786,9 +787,8 @@ static struct task_struct* gsnedf_schedule(struct task_struct * prev)
         /* (0) Determine state */
         exists      = entry->scheduled != NULL;
         blocks      = exists && !is_running(entry->scheduled);
-        out_of_time = exists &&
-                                  budget_enforced(entry->scheduled) &&
-                                  budget_exhausted(entry->scheduled);
+        out_of_time = exists && budget_enforced(entry->scheduled)
+                && budget_exhausted(entry->scheduled);
         np          = exists && is_np(entry->scheduled);
         sleep       = exists && get_rt_flags(entry->scheduled) == RT_F_SLEEP;
         preempt     = entry->scheduled != entry->linked;
@@ -837,9 +837,9 @@ static struct task_struct* gsnedf_schedule(struct task_struct * prev)
         /* Any task that is preemptable and either exhausts its execution
          * budget or wants to sleep completes. We may have to reschedule after
          * this. Don't do a job completion if we block (can't have timers running
-         * for blocked jobs). Preemption go first for the same reason.
+         * for blocked jobs).
          */
-        if (!np && (out_of_time || sleep) && !blocks && !preempt)
+        if (!np && (out_of_time || sleep) && !blocks)
                 job_completion(entry->scheduled, !sleep);
 
         /* Link pending task if we became unlinked.
diff --git a/litmus/sched_pfair.c b/litmus/sched_pfair.c
index 16f1065bbdca..72c06a492ef9 100644
--- a/litmus/sched_pfair.c
+++ b/litmus/sched_pfair.c
@@ -850,6 +850,13 @@ static long pfair_admit_task(struct task_struct* t)
             cpu_cluster(pstate[task_cpu(t)]))
                 return -EINVAL;
 
+        if (get_rt_period(t) != get_rt_relative_deadline(t)) {
+                printk(KERN_INFO "%s: Admission rejected. "
+                        "Only implicit deadlines are currently supported.\n",
+                        litmus->plugin_name);
+                return -EINVAL;
+        }
+
         /* Pfair is a tick-based method, so the time
          * of interest is jiffies. Calculate tick-based
          * times for everything.
diff --git a/litmus/sched_pfp.c b/litmus/sched_pfp.c
new file mode 100644
index 000000000000..62be699629b1
--- /dev/null
+++ b/litmus/sched_pfp.c
@@ -0,0 +1,1685 @@
+/*
+ * litmus/sched_pfp.c
+ *
+ * Implementation of partitioned fixed-priority scheduling.
+ * Based on PSN-EDF.
+ */
+
+#include <linux/percpu.h>
+#include <linux/sched.h>
+#include <linux/list.h>
+#include <linux/spinlock.h>
+#include <linux/module.h>
+
+#include <litmus/litmus.h>
+#include <litmus/wait.h>
+#include <litmus/jobs.h>
+#include <litmus/preempt.h>
+#include <litmus/fp_common.h>
+#include <litmus/sched_plugin.h>
+#include <litmus/sched_trace.h>
+#include <litmus/trace.h>
+#include <litmus/budget.h>
+
+#include <linux/uaccess.h>
+
+
+typedef struct {
+        rt_domain_t             domain;
+        struct fp_prio_queue    ready_queue;
+        int                     cpu;
+        struct task_struct*     scheduled; /* only RT tasks */
+/*
+ * scheduling lock slock
+ * protects the domain and serializes scheduling decisions
+ */
+#define slock domain.ready_lock
+
+} pfp_domain_t;
+
+DEFINE_PER_CPU(pfp_domain_t, pfp_domains);
+
+pfp_domain_t* pfp_doms[NR_CPUS];
+
+#define local_pfp               (&__get_cpu_var(pfp_domains))
+#define remote_dom(cpu)         (&per_cpu(pfp_domains, cpu).domain)
+#define remote_pfp(cpu) (&per_cpu(pfp_domains, cpu))
+#define task_dom(task)          remote_dom(get_partition(task))
+#define task_pfp(task)          remote_pfp(get_partition(task))
+
+/* we assume the lock is being held */
+static void preempt(pfp_domain_t *pfp)
+{
+        preempt_if_preemptable(pfp->scheduled, pfp->cpu);
+}
+
+static unsigned int priority_index(struct task_struct* t)
+{
+#ifdef CONFIG_LOCKING
+        if (unlikely(t->rt_param.inh_task))
+                /* use effective priority */
+                t = t->rt_param.inh_task;
+
+        if (is_priority_boosted(t)) {
+                /* zero is reserved for priority-boosted tasks */
+                return 0;
+        } else
+#endif
+                return get_priority(t);
+}
+
+
+static void pfp_release_jobs(rt_domain_t* rt, struct bheap* tasks)
+{
+        pfp_domain_t *pfp = container_of(rt, pfp_domain_t, domain);
+        unsigned long flags;
+        struct task_struct* t;
+        struct bheap_node* hn;
+
+        raw_spin_lock_irqsave(&pfp->slock, flags);
+
+        while (!bheap_empty(tasks)) {
+                hn = bheap_take(fp_ready_order, tasks);
+                t = bheap2task(hn);
+                TRACE_TASK(t, "released (part:%d prio:%d)\n",
+                           get_partition(t), get_priority(t));
+                fp_prio_add(&pfp->ready_queue, t, priority_index(t));
+        }
+
+        /* do we need to preempt? */
+        if (fp_higher_prio(fp_prio_peek(&pfp->ready_queue), pfp->scheduled)) {
+                TRACE_CUR("preempted by new release\n");
+                preempt(pfp);
+        }
+
+        raw_spin_unlock_irqrestore(&pfp->slock, flags);
+}
+
+static void pfp_domain_init(pfp_domain_t* pfp,
+                               int cpu)
+{
+        fp_domain_init(&pfp->domain, NULL, pfp_release_jobs);
+        pfp->cpu                = cpu;
+        pfp->scheduled          = NULL;
+        fp_prio_queue_init(&pfp->ready_queue);
+}
+
+static void requeue(struct task_struct* t, pfp_domain_t *pfp)
+{
+        if (t->state != TASK_RUNNING)
+                TRACE_TASK(t, "requeue: !TASK_RUNNING\n");
+
+        set_rt_flags(t, RT_F_RUNNING);
+        if (is_released(t, litmus_clock()))
+                fp_prio_add(&pfp->ready_queue, t, priority_index(t));
+        else
+                add_release(&pfp->domain, t); /* it has got to wait */
+}
+
+static void job_completion(struct task_struct* t, int forced)
+{
+        sched_trace_task_completion(t,forced);
+        TRACE_TASK(t, "job_completion().\n");
+
+        set_rt_flags(t, RT_F_SLEEP);
+        prepare_for_next_period(t);
+}
+
+static void pfp_tick(struct task_struct *t)
+{
+        pfp_domain_t *pfp = local_pfp;
+
+        /* Check for inconsistency. We don't need the lock for this since
+         * ->scheduled is only changed in schedule, which obviously is not
+         *  executing in parallel on this CPU
+         */
+        BUG_ON(is_realtime(t) && t != pfp->scheduled);
+
+        if (is_realtime(t) && budget_enforced(t) && budget_exhausted(t)) {
+                if (!is_np(t)) {
+                        litmus_reschedule_local();
+                        TRACE("pfp_scheduler_tick: "
+                              "%d is preemptable "
+                              " => FORCE_RESCHED\n", t->pid);
+                } else if (is_user_np(t)) {
+                        TRACE("pfp_scheduler_tick: "
+                              "%d is non-preemptable, "
+                              "preemption delayed.\n", t->pid);
+                        request_exit_np(t);
+                }
+        }
+}
+
+static struct task_struct* pfp_schedule(struct task_struct * prev)
+{
+        pfp_domain_t*   pfp = local_pfp;
+        struct task_struct*     next;
+
+        int out_of_time, sleep, preempt, np, exists, blocks, resched, migrate;
+
+        raw_spin_lock(&pfp->slock);
+
+        /* sanity checking
+         * differently from gedf, when a task exits (dead)
+         * pfp->schedule may be null and prev _is_ realtime
+         */
+        BUG_ON(pfp->scheduled && pfp->scheduled != prev);
+        BUG_ON(pfp->scheduled && !is_realtime(prev));
+
+        /* (0) Determine state */
+        exists      = pfp->scheduled != NULL;
+        blocks      = exists && !is_running(pfp->scheduled);
+        out_of_time = exists &&
+                                  budget_enforced(pfp->scheduled) &&
+                                  budget_exhausted(pfp->scheduled);
+        np          = exists && is_np(pfp->scheduled);
+        sleep       = exists && get_rt_flags(pfp->scheduled) == RT_F_SLEEP;
+        migrate     = exists && get_partition(pfp->scheduled) != pfp->cpu;
+        preempt     = migrate || fp_preemption_needed(&pfp->ready_queue, prev);
+
+        /* If we need to preempt do so.
+         * The following checks set resched to 1 in case of special
+         * circumstances.
+         */
+        resched = preempt;
+
+        /* If a task blocks we have no choice but to reschedule.
+         */
+        if (blocks)
+                resched = 1;
+
+        /* Request a sys_exit_np() call if we would like to preempt but cannot.
+         * Multiple calls to request_exit_np() don't hurt.
+         */
+        if (np && (out_of_time || preempt || sleep))
+                request_exit_np(pfp->scheduled);
+
+        /* Any task that is preemptable and either exhausts its execution
+         * budget or wants to sleep completes. We may have to reschedule after
+         * this.
+         */
+        if (!np && (out_of_time || sleep) && !blocks && !migrate) {
+                job_completion(pfp->scheduled, !sleep);
+                resched = 1;
+        }
+
+        /* The final scheduling decision. Do we need to switch for some reason?
+         * Switch if we are in RT mode and have no task or if we need to
+         * resched.
+         */
+        next = NULL;
+        if ((!np || blocks) && (resched || !exists)) {
+                /* When preempting a task that does not block, then
+                 * re-insert it into either the ready queue or the
+                 * release queue (if it completed). requeue() picks
+                 * the appropriate queue.
+                 */
+                if (pfp->scheduled && !blocks  && !migrate)
+                        requeue(pfp->scheduled, pfp);
+                next = fp_prio_take(&pfp->ready_queue);
+        } else
+                /* Only override Linux scheduler if we have a real-time task
+                 * scheduled that needs to continue.
+                 */
+                if (exists)
+                        next = prev;
+
+        if (next) {
+                TRACE_TASK(next, "scheduled at %llu\n", litmus_clock());
+                set_rt_flags(next, RT_F_RUNNING);
+        } else {
+                TRACE("becoming idle at %llu\n", litmus_clock());
+        }
+
+        pfp->scheduled = next;
+        sched_state_task_picked();
+        raw_spin_unlock(&pfp->slock);
+
+        return next;
+}
+
+#ifdef CONFIG_LITMUS_LOCKING
+
+/* prev is no longer scheduled --- see if it needs to migrate */
+static void pfp_finish_switch(struct task_struct *prev)
+{
+        pfp_domain_t *to;
+
+        if (is_realtime(prev) &&
+            is_running(prev) &&
+            get_partition(prev) != smp_processor_id()) {
+                TRACE_TASK(prev, "needs to migrate from P%d to P%d\n",
+                           smp_processor_id(), get_partition(prev));
+
+                to = task_pfp(prev);
+
+                raw_spin_lock(&to->slock);
+
+                TRACE_TASK(prev, "adding to queue on P%d\n", to->cpu);
+                requeue(prev, to);
+                if (fp_preemption_needed(&to->ready_queue, to->scheduled))
+                        preempt(to);
+
+                raw_spin_unlock(&to->slock);
+
+        }
+}
+
+#endif
+
+/*      Prepare a task for running in RT mode
+ */
+static void pfp_task_new(struct task_struct * t, int on_rq, int running)
+{
+        pfp_domain_t*   pfp = task_pfp(t);
+        unsigned long           flags;
+
+        TRACE_TASK(t, "P-FP: task new, cpu = %d\n",
+                   t->rt_param.task_params.cpu);
+
+        /* setup job parameters */
+        release_at(t, litmus_clock());
+
+        /* The task should be running in the queue, otherwise signal
+         * code will try to wake it up with fatal consequences.
+         */
+        raw_spin_lock_irqsave(&pfp->slock, flags);
+        if (running) {
+                /* there shouldn't be anything else running at the time */
+                BUG_ON(pfp->scheduled);
+                pfp->scheduled = t;
+        } else {
+                requeue(t, pfp);
+                /* maybe we have to reschedule */
+                preempt(pfp);
+        }
+        raw_spin_unlock_irqrestore(&pfp->slock, flags);
+}
+
+static void pfp_task_wake_up(struct task_struct *task)
+{
+        unsigned long           flags;
+        pfp_domain_t*           pfp = task_pfp(task);
+        lt_t                    now;
+
+        TRACE_TASK(task, "wake_up at %llu\n", litmus_clock());
+        raw_spin_lock_irqsave(&pfp->slock, flags);
+
+#ifdef CONFIG_LITMUS_LOCKING
+        /* Should only be queued when processing a fake-wake up due to a
+         * migration-related state change. */
+        if (unlikely(is_queued(task))) {
+                TRACE_TASK(task, "WARNING: waking task still queued. Is this right?\n");
+                goto out_unlock;
+        }
+#else
+        BUG_ON(is_queued(task));
+#endif
+        now = litmus_clock();
+        if (is_tardy(task, now)
+#ifdef CONFIG_LITMUS_LOCKING
+        /* We need to take suspensions because of semaphores into
+         * account! If a job resumes after being suspended due to acquiring
+         * a semaphore, it should never be treated as a new job release.
+         */
+            && !is_priority_boosted(task)
+#endif
+                ) {
+                /* new sporadic release */
+                release_at(task, now);
+                sched_trace_task_release(task);
+        }
+
+        /* Only add to ready queue if it is not the currently-scheduled
+         * task. This could be the case if a task was woken up concurrently
+         * on a remote CPU before the executing CPU got around to actually
+         * de-scheduling the task, i.e., wake_up() raced with schedule()
+         * and won. Also, don't requeue if it is still queued, which can
+         * happen under the DPCP due wake-ups racing with migrations.
+         */
+        if (pfp->scheduled != task)
+                requeue(task, pfp);
+
+out_unlock:
+        raw_spin_unlock_irqrestore(&pfp->slock, flags);
+        TRACE_TASK(task, "wake up done\n");
+}
+
+static void pfp_task_block(struct task_struct *t)
+{
+        /* only running tasks can block, thus t is in no queue */
+        TRACE_TASK(t, "block at %llu, state=%d\n", litmus_clock(), t->state);
+
+        BUG_ON(!is_realtime(t));
+
+        /* If this task blocked normally, it shouldn't be queued. The exception is
+         * if this is a simulated block()/wakeup() pair from the pull-migration code path.
+         * This should only happen if the DPCP is being used.
+         */
+#ifdef CONFIG_LITMUS_LOCKING
+        if (unlikely(is_queued(t)))
+                TRACE_TASK(t, "WARNING: blocking task still queued. Is this right?\n");
+#else
+        BUG_ON(is_queued(t));
+#endif
+}
+
+static void pfp_task_exit(struct task_struct * t)
+{
+        unsigned long flags;
+        pfp_domain_t*   pfp = task_pfp(t);
+        rt_domain_t*            dom;
+
+        raw_spin_lock_irqsave(&pfp->slock, flags);
+        if (is_queued(t)) {
+                BUG(); /* This currently doesn't work. */
+                /* dequeue */
+                dom  = task_dom(t);
+                remove(dom, t);
+        }
+        if (pfp->scheduled == t) {
+                pfp->scheduled = NULL;
+                preempt(pfp);
+        }
+        TRACE_TASK(t, "RIP, now reschedule\n");
+
+        raw_spin_unlock_irqrestore(&pfp->slock, flags);
+}
+
+#ifdef CONFIG_LITMUS_LOCKING
+
+#include <litmus/fdso.h>
+#include <litmus/srp.h>
+
+static void fp_dequeue(pfp_domain_t* pfp, struct task_struct* t)
+{
+        BUG_ON(pfp->scheduled == t && is_queued(t));
+        if (is_queued(t))
+                fp_prio_remove(&pfp->ready_queue, t, priority_index(t));
+}
+
+static void fp_set_prio_inh(pfp_domain_t* pfp, struct task_struct* t,
+                            struct task_struct* prio_inh)
+{
+        int requeue;
+
+        if (!t || t->rt_param.inh_task == prio_inh) {
+                /* no update  required */
+                if (t)
+                        TRACE_TASK(t, "no prio-inh update required\n");
+                return;
+        }
+
+        requeue = is_queued(t);
+        TRACE_TASK(t, "prio-inh: is_queued:%d\n", requeue);
+
+        if (requeue)
+                /* first remove */
+                fp_dequeue(pfp, t);
+
+        t->rt_param.inh_task = prio_inh;
+
+        if (requeue)
+                /* add again to the right queue */
+                fp_prio_add(&pfp->ready_queue, t, priority_index(t));
+}
+
+static int effective_agent_priority(int prio)
+{
+        /* make sure agents have higher priority */
+        return prio - LITMUS_MAX_PRIORITY;
+}
+
+static lt_t prio_point(int eprio)
+{
+        /* make sure we have non-negative prio points */
+        return eprio + LITMUS_MAX_PRIORITY;
+}
+
+static int prio_from_point(lt_t prio_point)
+{
+        return ((int) prio_point) - LITMUS_MAX_PRIORITY;
+}
+
+static void boost_priority(struct task_struct* t, lt_t priority_point)
+{
+        unsigned long           flags;
+        pfp_domain_t*   pfp = task_pfp(t);
+
+        raw_spin_lock_irqsave(&pfp->slock, flags);
+
+
+        TRACE_TASK(t, "priority boosted at %llu\n", litmus_clock());
+
+        tsk_rt(t)->priority_boosted = 1;
+        /* tie-break by protocol-specific priority point */
+        tsk_rt(t)->boost_start_time = priority_point;
+
+        if (pfp->scheduled != t) {
+                /* holder may be queued: first stop queue changes */
+                raw_spin_lock(&pfp->domain.release_lock);
+                if (is_queued(t) &&
+                    /* If it is queued, then we need to re-order. */
+                    bheap_decrease(fp_ready_order, tsk_rt(t)->heap_node) &&
+                    /* If we bubbled to the top, then we need to check for preemptions. */
+                    fp_preemption_needed(&pfp->ready_queue, pfp->scheduled))
+                                preempt(pfp);
+                raw_spin_unlock(&pfp->domain.release_lock);
+        } /* else: nothing to do since the job is not queued while scheduled */
+
+        raw_spin_unlock_irqrestore(&pfp->slock, flags);
+}
+
+static void unboost_priority(struct task_struct* t)
+{
+        unsigned long           flags;
+        pfp_domain_t*   pfp = task_pfp(t);
+        lt_t                    now;
+
+        raw_spin_lock_irqsave(&pfp->slock, flags);
+        now = litmus_clock();
+
+        /* assumption: this only happens when the job is scheduled */
+        BUG_ON(pfp->scheduled != t);
+
+        TRACE_TASK(t, "priority restored at %llu\n", now);
+
+        /* priority boosted jobs must be scheduled */
+        BUG_ON(pfp->scheduled != t);
+
+        tsk_rt(t)->priority_boosted = 0;
+        tsk_rt(t)->boost_start_time = 0;
+
+        /* check if this changes anything */
+        if (fp_preemption_needed(&pfp->ready_queue, pfp->scheduled))
+                preempt(pfp);
+
+        raw_spin_unlock_irqrestore(&pfp->slock, flags);
+}
+
+/* ******************** SRP support ************************ */
+
+static unsigned int pfp_get_srp_prio(struct task_struct* t)
+{
+        return get_priority(t);
+}
+
+/* ******************** FMLP support ********************** */
+
+struct fmlp_semaphore {
+        struct litmus_lock litmus_lock;
+
+        /* current resource holder */
+        struct task_struct *owner;
+
+        /* FIFO queue of waiting tasks */
+        wait_queue_head_t wait;
+};
+
+static inline struct fmlp_semaphore* fmlp_from_lock(struct litmus_lock* lock)
+{
+        return container_of(lock, struct fmlp_semaphore, litmus_lock);
+}
+int pfp_fmlp_lock(struct litmus_lock* l)
+{
+        struct task_struct* t = current;
+        struct fmlp_semaphore *sem = fmlp_from_lock(l);
+        wait_queue_t wait;
+        unsigned long flags;
+        lt_t time_of_request;
+
+        if (!is_realtime(t))
+                return -EPERM;
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        /* tie-break by this point in time */
+        time_of_request = litmus_clock();
+
+        /* Priority-boost ourself *before* we suspend so that
+         * our priority is boosted when we resume. */
+        boost_priority(t, time_of_request);
+
+        if (sem->owner) {
+                /* resource is not free => must suspend and wait */
+
+                init_waitqueue_entry(&wait, t);
+
+                /* FIXME: interruptible would be nice some day */
+                set_task_state(t, TASK_UNINTERRUPTIBLE);
+
+                __add_wait_queue_tail_exclusive(&sem->wait, &wait);
+
+                TS_LOCK_SUSPEND;
+
+                /* release lock before sleeping */
+                spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+                /* We depend on the FIFO order.  Thus, we don't need to recheck
+                 * when we wake up; we are guaranteed to have the lock since
+                 * there is only one wake up per release.
+                 */
+
+                schedule();
+
+                TS_LOCK_RESUME;
+
+                /* Since we hold the lock, no other task will change
+                 * ->owner. We can thus check it without acquiring the spin
+                 * lock. */
+                BUG_ON(sem->owner != t);
+        } else {
+                /* it's ours now */
+                sem->owner = t;
+
+                spin_unlock_irqrestore(&sem->wait.lock, flags);
+        }
+
+        return 0;
+}
+
+int pfp_fmlp_unlock(struct litmus_lock* l)
+{
+        struct task_struct *t = current, *next;
+        struct fmlp_semaphore *sem = fmlp_from_lock(l);
+        unsigned long flags;
+        int err = 0;
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        if (sem->owner != t) {
+                err = -EINVAL;
+                goto out;
+        }
+
+        /* we lose the benefit of priority boosting */
+
+        unboost_priority(t);
+
+        /* check if there are jobs waiting for this resource */
+        next = __waitqueue_remove_first(&sem->wait);
+        if (next) {
+                /* next becomes the resouce holder */
+                sem->owner = next;
+
+                /* Wake up next. The waiting job is already priority-boosted. */
+                wake_up_process(next);
+        } else
+                /* resource becomes available */
+                sem->owner = NULL;
+
+out:
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+        return err;
+}
+
+int pfp_fmlp_close(struct litmus_lock* l)
+{
+        struct task_struct *t = current;
+        struct fmlp_semaphore *sem = fmlp_from_lock(l);
+        unsigned long flags;
+
+        int owner;
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        owner = sem->owner == t;
+
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+        if (owner)
+                pfp_fmlp_unlock(l);
+
+        return 0;
+}
+
+void pfp_fmlp_free(struct litmus_lock* lock)
+{
+        kfree(fmlp_from_lock(lock));
+}
+
+static struct litmus_lock_ops pfp_fmlp_lock_ops = {
+        .close  = pfp_fmlp_close,
+        .lock   = pfp_fmlp_lock,
+        .unlock = pfp_fmlp_unlock,
+        .deallocate = pfp_fmlp_free,
+};
+
+static struct litmus_lock* pfp_new_fmlp(void)
+{
+        struct fmlp_semaphore* sem;
+
+        sem = kmalloc(sizeof(*sem), GFP_KERNEL);
+        if (!sem)
+                return NULL;
+
+        sem->owner   = NULL;
+        init_waitqueue_head(&sem->wait);
+        sem->litmus_lock.ops = &pfp_fmlp_lock_ops;
+
+        return &sem->litmus_lock;
+}
+
+/* ******************** MPCP support ********************** */
+
+struct mpcp_semaphore {
+        struct litmus_lock litmus_lock;
+
+        /* current resource holder */
+        struct task_struct *owner;
+
+        /* priority queue of waiting tasks */
+        wait_queue_head_t wait;
+
+        /* priority ceiling per cpu */
+        unsigned int prio_ceiling[NR_CPUS];
+
+        /* should jobs spin "virtually" for this resource? */
+        int vspin;
+};
+
+#define OMEGA_CEILING UINT_MAX
+
+/* Since jobs spin "virtually" while waiting to acquire a lock,
+ * they first must aquire a local per-cpu resource.
+ */
+static DEFINE_PER_CPU(wait_queue_head_t, mpcpvs_vspin_wait);
+static DEFINE_PER_CPU(struct task_struct*, mpcpvs_vspin);
+
+/* called with preemptions off <=> no local modifications */
+static void mpcp_vspin_enter(void)
+{
+        struct task_struct* t = current;
+
+        while (1) {
+                if (__get_cpu_var(mpcpvs_vspin) == NULL) {
+                        /* good, we get to issue our request */
+                        __get_cpu_var(mpcpvs_vspin) = t;
+                        break;
+                } else {
+                        /* some job is spinning => enqueue in request queue */
+                        prio_wait_queue_t wait;
+                        wait_queue_head_t* vspin = &__get_cpu_var(mpcpvs_vspin_wait);
+                        unsigned long flags;
+
+                        /* ordered by regular priority */
+                        init_prio_waitqueue_entry(&wait, t, prio_point(get_priority(t)));
+
+                        spin_lock_irqsave(&vspin->lock, flags);
+
+                        set_task_state(t, TASK_UNINTERRUPTIBLE);
+
+                        __add_wait_queue_prio_exclusive(vspin, &wait);
+
+                        spin_unlock_irqrestore(&vspin->lock, flags);
+
+                        TS_LOCK_SUSPEND;
+
+                        preempt_enable_no_resched();
+
+                        schedule();
+
+                        preempt_disable();
+
+                        TS_LOCK_RESUME;
+                        /* Recheck if we got it --- some higher-priority process might
+                         * have swooped in. */
+                }
+        }
+        /* ok, now it is ours */
+}
+
+/* called with preemptions off */
+static void mpcp_vspin_exit(void)
+{
+        struct task_struct* t = current, *next;
+        unsigned long flags;
+        wait_queue_head_t* vspin = &__get_cpu_var(mpcpvs_vspin_wait);
+
+        BUG_ON(__get_cpu_var(mpcpvs_vspin) != t);
+
+        /* no spinning job */
+        __get_cpu_var(mpcpvs_vspin) = NULL;
+
+        /* see if anyone is waiting for us to stop "spinning" */
+        spin_lock_irqsave(&vspin->lock, flags);
+        next = __waitqueue_remove_first(vspin);
+
+        if (next)
+                wake_up_process(next);
+
+        spin_unlock_irqrestore(&vspin->lock, flags);
+}
+
+static inline struct mpcp_semaphore* mpcp_from_lock(struct litmus_lock* lock)
+{
+        return container_of(lock, struct mpcp_semaphore, litmus_lock);
+}
+
+int pfp_mpcp_lock(struct litmus_lock* l)
+{
+        struct task_struct* t = current;
+        struct mpcp_semaphore *sem = mpcp_from_lock(l);
+        prio_wait_queue_t wait;
+        unsigned long flags;
+
+        if (!is_realtime(t))
+                return -EPERM;
+
+        preempt_disable();
+
+        if (sem->vspin)
+                mpcp_vspin_enter();
+
+        /* Priority-boost ourself *before* we suspend so that
+         * our priority is boosted when we resume. Use the priority
+         * ceiling for the local partition. */
+        boost_priority(t, sem->prio_ceiling[get_partition(t)]);
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        preempt_enable_no_resched();
+
+        if (sem->owner) {
+                /* resource is not free => must suspend and wait */
+
+                /* ordered by regular priority */
+                init_prio_waitqueue_entry(&wait, t, prio_point(get_priority(t)));
+
+                /* FIXME: interruptible would be nice some day */
+                set_task_state(t, TASK_UNINTERRUPTIBLE);
+
+                __add_wait_queue_prio_exclusive(&sem->wait, &wait);
+
+                TS_LOCK_SUSPEND;
+
+                /* release lock before sleeping */
+                spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+                /* We depend on the FIFO order.  Thus, we don't need to recheck
+                 * when we wake up; we are guaranteed to have the lock since
+                 * there is only one wake up per release.
+                 */
+
+                schedule();
+
+                TS_LOCK_RESUME;
+
+                /* Since we hold the lock, no other task will change
+                 * ->owner. We can thus check it without acquiring the spin
+                 * lock. */
+                BUG_ON(sem->owner != t);
+        } else {
+                /* it's ours now */
+                sem->owner = t;
+
+                spin_unlock_irqrestore(&sem->wait.lock, flags);
+        }
+
+        return 0;
+}
+
+int pfp_mpcp_unlock(struct litmus_lock* l)
+{
+        struct task_struct *t = current, *next;
+        struct mpcp_semaphore *sem = mpcp_from_lock(l);
+        unsigned long flags;
+        int err = 0;
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        if (sem->owner != t) {
+                err = -EINVAL;
+                goto out;
+        }
+
+        /* we lose the benefit of priority boosting */
+
+        unboost_priority(t);
+
+        /* check if there are jobs waiting for this resource */
+        next = __waitqueue_remove_first(&sem->wait);
+        if (next) {
+                /* next becomes the resouce holder */
+                sem->owner = next;
+
+                /* Wake up next. The waiting job is already priority-boosted. */
+                wake_up_process(next);
+        } else
+                /* resource becomes available */
+                sem->owner = NULL;
+
+out:
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+        if (sem->vspin && err == 0) {
+                preempt_disable();
+                mpcp_vspin_exit();
+                preempt_enable();
+        }
+
+        return err;
+}
+
+int pfp_mpcp_open(struct litmus_lock* l, void* config)
+{
+        struct task_struct *t = current;
+        struct mpcp_semaphore *sem = mpcp_from_lock(l);
+        int cpu, local_cpu;
+        unsigned long flags;
+
+        if (!is_realtime(t))
+                /* we need to know the real-time priority */
+                return -EPERM;
+
+        local_cpu = get_partition(t);
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        for (cpu = 0; cpu < NR_CPUS; cpu++)
+                if (cpu != local_cpu)
+                {
+                        sem->prio_ceiling[cpu] = min(sem->prio_ceiling[cpu],
+                                                     get_priority(t));
+                        TRACE_CUR("priority ceiling for sem %p is now %d on cpu %d\n",
+                                  sem, sem->prio_ceiling[cpu], cpu);
+                }
+
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+        return 0;
+}
+
+int pfp_mpcp_close(struct litmus_lock* l)
+{
+        struct task_struct *t = current;
+        struct mpcp_semaphore *sem = mpcp_from_lock(l);
+        unsigned long flags;
+
+        int owner;
+
+        spin_lock_irqsave(&sem->wait.lock, flags);
+
+        owner = sem->owner == t;
+
+        spin_unlock_irqrestore(&sem->wait.lock, flags);
+
+        if (owner)
+                pfp_mpcp_unlock(l);
+
+        return 0;
+}
+
+void pfp_mpcp_free(struct litmus_lock* lock)
+{
+        kfree(mpcp_from_lock(lock));
+}
+
+static struct litmus_lock_ops pfp_mpcp_lock_ops = {
+        .close  = pfp_mpcp_close,
+        .lock   = pfp_mpcp_lock,
+        .open   = pfp_mpcp_open,
+        .unlock = pfp_mpcp_unlock,
+        .deallocate = pfp_mpcp_free,
+};
+
+static struct litmus_lock* pfp_new_mpcp(int vspin)
+{
+        struct mpcp_semaphore* sem;
+        int cpu;
+
+        sem = kmalloc(sizeof(*sem), GFP_KERNEL);
+        if (!sem)
+                return NULL;
+
+        sem->owner   = NULL;
+        init_waitqueue_head(&sem->wait);
+        sem->litmus_lock.ops = &pfp_mpcp_lock_ops;
+
+        for (cpu = 0; cpu < NR_CPUS; cpu++)
+                sem->prio_ceiling[cpu] = OMEGA_CEILING;
+
+        /* mark as virtual spinning */
+        sem->vspin = vspin;
+
+        return &sem->litmus_lock;
+}
+
+
+/* ******************** PCP support ********************** */
+
+
+struct pcp_semaphore {
+        struct litmus_lock litmus_lock;
+
+        struct list_head ceiling;
+
+        /* current resource holder */
+        struct task_struct *owner;
+
+        /* priority ceiling --- can be negative due to DPCP support */
+        int prio_ceiling;
+
+        /* on which processor is this PCP semaphore allocated? */
+        int on_cpu;
+};
+
+static inline struct pcp_semaphore* pcp_from_lock(struct litmus_lock* lock)
+{
+        return container_of(lock, struct pcp_semaphore, litmus_lock);
+}
+
+
+struct pcp_state {
+        struct list_head system_ceiling;
+
+        /* highest-priority waiting task */
+        struct task_struct* hp_waiter;
+
+        /* list of jobs waiting to get past the system ceiling */
+        wait_queue_head_t ceiling_blocked;
+};
+
+static void pcp_init_state(struct pcp_state* s)
+{
+        INIT_LIST_HEAD(&s->system_ceiling);
+        s->hp_waiter = NULL;
+        init_waitqueue_head(&s->ceiling_blocked);
+}
+
+static DEFINE_PER_CPU(struct pcp_state, pcp_state);
+
+/* assumes preemptions are off */
+static struct pcp_semaphore* pcp_get_ceiling(void)
+{
+        struct list_head* top = __get_cpu_var(pcp_state).system_ceiling.next;
+
+        if (top)
+                return list_entry(top, struct pcp_semaphore, ceiling);
+        else
+                return NULL;
+}
+
+/* assumes preempt off */
+static void pcp_add_ceiling(struct pcp_semaphore* sem)
+{
+        struct list_head *pos;
+        struct list_head *in_use = &__get_cpu_var(pcp_state).system_ceiling;
+        struct pcp_semaphore* held;
+
+        BUG_ON(sem->on_cpu != smp_processor_id());
+        BUG_ON(in_list(&sem->ceiling));
+
+        list_for_each(pos, in_use) {
+                held = list_entry(pos, struct pcp_semaphore, ceiling);
+                if (held->prio_ceiling >= sem->prio_ceiling) {
+                        __list_add(&sem->ceiling, pos->prev, pos);
+                        return;
+                }
+        }
+
+        /* we hit the end of the list */
+
+        list_add_tail(&sem->ceiling, in_use);
+}
+
+/* assumes preempt off */
+static int pcp_exceeds_ceiling(struct pcp_semaphore* ceiling,
+                              struct task_struct* task,
+                              int effective_prio)
+{
+        return ceiling == NULL ||
+                ceiling->prio_ceiling > effective_prio ||
+                ceiling->owner == task;
+}
+
+/* assumes preempt off */
+static void pcp_priority_inheritance(void)
+{
+        unsigned long   flags;
+        pfp_domain_t*   pfp = local_pfp;
+
+        struct pcp_semaphore* ceiling = pcp_get_ceiling();
+        struct task_struct *blocker, *blocked;
+
+        blocker = ceiling ?  ceiling->owner : NULL;
+        blocked = __get_cpu_var(pcp_state).hp_waiter;
+
+        raw_spin_lock_irqsave(&pfp->slock, flags);
+
+        /* Current is no longer inheriting anything by default.  This should be
+         * the currently scheduled job, and hence not currently queued. */
+        BUG_ON(current != pfp->scheduled);
+
+        fp_set_prio_inh(pfp, current, NULL);
+        fp_set_prio_inh(pfp, blocked, NULL);
+        fp_set_prio_inh(pfp, blocker, NULL);
+
+
+        /* Let blocking job inherit priority of blocked job, if required. */
+        if (blocker && blocked &&
+            fp_higher_prio(blocked, blocker)) {
+                TRACE_TASK(blocker, "PCP inherits from %s/%d (prio %u -> %u) \n",
+                           blocked->comm, blocked->pid,
+                           get_priority(blocker), get_priority(blocked));
+                fp_set_prio_inh(pfp, blocker, blocked);
+        }
+
+        /* check if anything changed */
+        if (fp_higher_prio(fp_prio_peek(&pfp->ready_queue), pfp->scheduled))
+                preempt(pfp);
+
+        raw_spin_unlock_irqrestore(&pfp->slock, flags);
+}
+
+/* called with preemptions off */
+static void pcp_raise_ceiling(struct pcp_semaphore* sem,
+                              int effective_prio)
+{
+        struct task_struct* t = current;
+        struct pcp_semaphore* ceiling;
+        prio_wait_queue_t wait;
+        unsigned int waiting_higher_prio;
+
+        do {
+                ceiling = pcp_get_ceiling();
+                if (pcp_exceeds_ceiling(ceiling, t, effective_prio))
+                        break;
+
+                TRACE_CUR("PCP ceiling-blocked, wanted sem %p, but %s/%d has the ceiling \n",
+                          sem, ceiling->owner->comm, ceiling->owner->pid);
+
+                /* we need to wait until the ceiling is lowered */
+
+                /* enqueue in priority order */
+                init_prio_waitqueue_entry(&wait, t, prio_point(effective_prio));
+                set_task_state(t, TASK_UNINTERRUPTIBLE);
+                waiting_higher_prio = add_wait_queue_prio_exclusive(
+                        &__get_cpu_var(pcp_state).ceiling_blocked, &wait);
+
+                if (waiting_higher_prio == 0) {
+                        TRACE_CUR("PCP new highest-prio waiter => prio inheritance\n");
+
+                        /* we are the new highest-priority waiting job
+                         * => update inheritance */
+                        __get_cpu_var(pcp_state).hp_waiter = t;
+                        pcp_priority_inheritance();
+                }
+
+                TS_LOCK_SUSPEND;
+
+                preempt_enable_no_resched();
+                schedule();
+                preempt_disable();
+
+                /* pcp_resume_unblocked() removed us from wait queue */
+
+                TS_LOCK_RESUME;
+        } while(1);
+
+        TRACE_CUR("PCP got the ceiling and sem %p\n", sem);
+
+        /* We are good to go. The semaphore should be available. */
+        BUG_ON(sem->owner != NULL);
+
+        sem->owner = t;
+
+        pcp_add_ceiling(sem);
+}
+
+static void pcp_resume_unblocked(void)
+{
+        wait_queue_head_t *blocked =  &__get_cpu_var(pcp_state).ceiling_blocked;
+        unsigned long flags;
+        prio_wait_queue_t* q;
+        struct task_struct* t = NULL;
+
+        struct pcp_semaphore* ceiling = pcp_get_ceiling();
+
+        spin_lock_irqsave(&blocked->lock, flags);
+
+        while (waitqueue_active(blocked)) {
+                /* check first == highest-priority waiting job */
+                q = list_entry(blocked->task_list.next,
+                               prio_wait_queue_t, wq.task_list);
+                t = (struct task_struct*) q->wq.private;
+
+                /* can it proceed now? => let it go */
+                if (pcp_exceeds_ceiling(ceiling, t,
+                                        prio_from_point(q->priority))) {
+                    __remove_wait_queue(blocked, &q->wq);
+                    wake_up_process(t);
+                } else {
+                        /* We are done. Update highest-priority waiter. */
+                        __get_cpu_var(pcp_state).hp_waiter = t;
+                        goto out;
+                }
+        }
+        /* If we get here, then there are no more waiting
+         * jobs. */
+        __get_cpu_var(pcp_state).hp_waiter = NULL;
+out:
+        spin_unlock_irqrestore(&blocked->lock, flags);
+}
+
+/* assumes preempt off */
+static void pcp_lower_ceiling(struct pcp_semaphore* sem)
+{
+        BUG_ON(!in_list(&sem->ceiling));
+        BUG_ON(sem->owner != current);
+        BUG_ON(sem->on_cpu != smp_processor_id());
+
+        /* remove from ceiling list */
+        list_del(&sem->ceiling);
+
+        /* release */
+        sem->owner = NULL;
+
+        TRACE_CUR("PCP released sem %p\n", sem);
+
+        /* Wake up all ceiling-blocked jobs that now pass the ceiling. */
+        pcp_resume_unblocked();
+
+        pcp_priority_inheritance();
+}
+
+static void pcp_update_prio_ceiling(struct pcp_semaphore* sem,
+                                    int effective_prio)
+{
+        /* This needs to be synchronized on something.
+         * Might as well use waitqueue lock for the processor.
+         * We assume this happens only before the task set starts execution,
+         * (i.e., during initialization), but it may happen on multiple processors
+         * at the same time.
+         */
+        unsigned long flags;
+
+        struct pcp_state* s = &per_cpu(pcp_state, sem->on_cpu);
+
+        spin_lock_irqsave(&s->ceiling_blocked.lock, flags);
+
+        sem->prio_ceiling = min(sem->prio_ceiling, effective_prio);
+
+        spin_unlock_irqrestore(&s->ceiling_blocked.lock, flags);
+}
+
+static void pcp_init_semaphore(struct pcp_semaphore* sem, int cpu)
+{
+        sem->owner   = NULL;
+        INIT_LIST_HEAD(&sem->ceiling);
+        sem->prio_ceiling = INT_MAX;
+        sem->on_cpu = cpu;
+}
+
+int pfp_pcp_lock(struct litmus_lock* l)
+{
+        struct task_struct* t = current;
+        struct pcp_semaphore *sem = pcp_from_lock(l);
+
+        int eprio = effective_agent_priority(get_priority(t));
+        int from  = get_partition(t);
+        int to    = sem->on_cpu;
+
+        if (!is_realtime(t) || from != to)
+                return -EPERM;
+
+        preempt_disable();
+
+        pcp_raise_ceiling(sem, eprio);
+
+        preempt_enable();
+
+        return 0;
+}
+
+int pfp_pcp_unlock(struct litmus_lock* l)
+{
+        struct task_struct *t = current;
+        struct pcp_semaphore *sem = pcp_from_lock(l);
+
+        int err = 0;
+
+        preempt_disable();
+
+        if (sem->on_cpu != smp_processor_id() || sem->owner != t) {
+                err = -EINVAL;
+                goto out;
+        }
+
+        /* give it back */
+        pcp_lower_ceiling(sem);
+
+out:
+        preempt_enable();
+
+        return err;
+}
+
+int pfp_pcp_open(struct litmus_lock* l, void* __user config)
+{
+        struct task_struct *t = current;
+        struct pcp_semaphore *sem = pcp_from_lock(l);
+
+        int cpu, eprio;
+
+        if (!is_realtime(t))
+                /* we need to know the real-time priority */
+                return -EPERM;
+
+        if (get_user(cpu, (int*) config))
+                return -EFAULT;
+
+        /* make sure the resource location matches */
+        if (cpu != sem->on_cpu)
+                return -EINVAL;
+
+        eprio = effective_agent_priority(get_priority(t));
+
+        pcp_update_prio_ceiling(sem, eprio);
+
+        return 0;
+}
+
+int pfp_pcp_close(struct litmus_lock* l)
+{
+        struct task_struct *t = current;
+        struct pcp_semaphore *sem = pcp_from_lock(l);
+
+        int owner = 0;
+
+        preempt_disable();
+
+        if (sem->on_cpu == smp_processor_id())
+                owner = sem->owner == t;
+
+        preempt_enable();
+
+        if (owner)
+                pfp_pcp_unlock(l);
+
+        return 0;
+}
+
+void pfp_pcp_free(struct litmus_lock* lock)
+{
+        kfree(pcp_from_lock(lock));
+}
+
+
+static struct litmus_lock_ops pfp_pcp_lock_ops = {
+        .close  = pfp_pcp_close,
+        .lock   = pfp_pcp_lock,
+        .open   = pfp_pcp_open,
+        .unlock = pfp_pcp_unlock,
+        .deallocate = pfp_pcp_free,
+};
+
+
+static struct litmus_lock* pfp_new_pcp(int on_cpu)
+{
+        struct pcp_semaphore* sem;
+
+        sem = kmalloc(sizeof(*sem), GFP_KERNEL);
+        if (!sem)
+                return NULL;
+
+        sem->litmus_lock.ops = &pfp_pcp_lock_ops;
+        pcp_init_semaphore(sem, on_cpu);
+
+        return &sem->litmus_lock;
+}
+
+/* ******************** DPCP support ********************** */
+
+struct dpcp_semaphore {
+        struct litmus_lock litmus_lock;
+        struct pcp_semaphore  pcp;
+        int owner_cpu;
+};
+
+static inline struct dpcp_semaphore* dpcp_from_lock(struct litmus_lock* lock)
+{
+        return container_of(lock, struct dpcp_semaphore, litmus_lock);
+}
+
+/* called with preemptions disabled */
+static void pfp_migrate_to(int target_cpu)
+{
+        struct task_struct* t = current;
+        pfp_domain_t *from;
+
+        if (get_partition(t) == target_cpu)
+                return;
+
+        /* make sure target_cpu makes sense */
+        BUG_ON(!cpu_online(target_cpu));
+
+        local_irq_disable();
+
+        /* scheduled task should not be in any ready or release queue */
+        BUG_ON(is_queued(t));
+
+        /* lock both pfp domains in order of address */
+        from = task_pfp(t);
+
+        raw_spin_lock(&from->slock);
+
+        /* switch partitions */
+        tsk_rt(t)->task_params.cpu = target_cpu;
+
+        raw_spin_unlock(&from->slock);
+
+        /* Don't trace scheduler costs as part of
+         * locking overhead. Scheduling costs are accounted for
+         * explicitly. */
+        TS_LOCK_SUSPEND;
+
+        local_irq_enable();
+        preempt_enable_no_resched();
+
+        /* deschedule to be migrated */
+        schedule();
+
+        /* we are now on the target processor */
+        preempt_disable();
+
+        /* start recording costs again */
+        TS_LOCK_RESUME;
+
+        BUG_ON(smp_processor_id() != target_cpu);
+}
+
+int pfp_dpcp_lock(struct litmus_lock* l)
+{
+        struct task_struct* t = current;
+        struct dpcp_semaphore *sem = dpcp_from_lock(l);
+        int eprio = effective_agent_priority(get_priority(t));
+        int from  = get_partition(t);
+        int to    = sem->pcp.on_cpu;
+
+        if (!is_realtime(t))
+                return -EPERM;
+
+        preempt_disable();
+
+        /* Priority-boost ourself *before* we suspend so that
+         * our priority is boosted when we resume. */
+
+        boost_priority(t, get_priority(t));
+
+        pfp_migrate_to(to);
+
+        pcp_raise_ceiling(&sem->pcp, eprio);
+
+        /* yep, we got it => execute request */
+        sem->owner_cpu = from;
+
+        preempt_enable();
+
+        return 0;
+}
+
+int pfp_dpcp_unlock(struct litmus_lock* l)
+{
+        struct task_struct *t = current;
+        struct dpcp_semaphore *sem = dpcp_from_lock(l);
+        int err = 0;
+        int home;
+
+        preempt_disable();
+
+        if (sem->pcp.on_cpu != smp_processor_id() || sem->pcp.owner != t) {
+                err = -EINVAL;
+                goto out;
+        }
+
+        home = sem->owner_cpu;
+
+        /* give it back */
+        pcp_lower_ceiling(&sem->pcp);
+
+        /* we lose the benefit of priority boosting */
+        unboost_priority(t);
+
+        pfp_migrate_to(home);
+
+out:
+        preempt_enable();
+
+        return err;
+}
+
+int pfp_dpcp_open(struct litmus_lock* l, void* __user config)
+{
+        struct task_struct *t = current;
+        struct dpcp_semaphore *sem = dpcp_from_lock(l);
+        int cpu, eprio;
+
+        if (!is_realtime(t))
+                /* we need to know the real-time priority */
+                return -EPERM;
+
+        if (get_user(cpu, (int*) config))
+                return -EFAULT;
+
+        /* make sure the resource location matches */
+        if (cpu != sem->pcp.on_cpu)
+                return -EINVAL;
+
+        eprio = effective_agent_priority(get_priority(t));
+
+        pcp_update_prio_ceiling(&sem->pcp, eprio);
+
+        return 0;
+}
+
+int pfp_dpcp_close(struct litmus_lock* l)
+{
+        struct task_struct *t = current;
+        struct dpcp_semaphore *sem = dpcp_from_lock(l);
+        int owner = 0;
+
+        preempt_disable();
+
+        if (sem->pcp.on_cpu == smp_processor_id())
+                owner = sem->pcp.owner == t;
+
+        preempt_enable();
+
+        if (owner)
+                pfp_dpcp_unlock(l);
+
+        return 0;
+}
+
+void pfp_dpcp_free(struct litmus_lock* lock)
+{
+        kfree(dpcp_from_lock(lock));
+}
+
+static struct litmus_lock_ops pfp_dpcp_lock_ops = {
+        .close  = pfp_dpcp_close,
+        .lock   = pfp_dpcp_lock,
+        .open   = pfp_dpcp_open,
+        .unlock = pfp_dpcp_unlock,
+        .deallocate = pfp_dpcp_free,
+};
+
+static struct litmus_lock* pfp_new_dpcp(int on_cpu)
+{
+        struct dpcp_semaphore* sem;
+
+        sem = kmalloc(sizeof(*sem), GFP_KERNEL);
+        if (!sem)
+                return NULL;
+
+        sem->litmus_lock.ops = &pfp_dpcp_lock_ops;
+        sem->owner_cpu = NO_CPU;
+        pcp_init_semaphore(&sem->pcp, on_cpu);
+
+        return &sem->litmus_lock;
+}
+
+
+/* **** lock constructor **** */
+
+
+static long pfp_allocate_lock(struct litmus_lock **lock, int type,
+                                 void* __user config)
+{
+        int err = -ENXIO, cpu;
+        struct srp_semaphore* srp;
+
+        /* P-FP currently supports the SRP for local resources and the FMLP
+         * for global resources. */
+        switch (type) {
+        case FMLP_SEM:
+                /* FIFO Mutex Locking Protocol */
+                *lock = pfp_new_fmlp();
+                if (*lock)
+                        err = 0;
+                else
+                        err = -ENOMEM;
+                break;
+
+        case MPCP_SEM:
+                /* Multiprocesor Priority Ceiling Protocol */
+                *lock = pfp_new_mpcp(0);
+                if (*lock)
+                        err = 0;
+                else
+                        err = -ENOMEM;
+                break;
+
+        case MPCP_VS_SEM:
+                /* Multiprocesor Priority Ceiling Protocol with virtual spinning */
+                *lock = pfp_new_mpcp(1);
+                if (*lock)
+                        err = 0;
+                else
+                        err = -ENOMEM;
+                break;
+
+        case DPCP_SEM:
+                /* Distributed Priority Ceiling Protocol */
+                if (get_user(cpu, (int*) config))
+                        return -EFAULT;
+
+                if (!cpu_online(cpu))
+                        return -EINVAL;
+
+                *lock = pfp_new_dpcp(cpu);
+                if (*lock)
+                        err = 0;
+                else
+                        err = -ENOMEM;
+                break;
+
+        case SRP_SEM:
+                /* Baker's Stack Resource Policy */
+                srp = allocate_srp_semaphore();
+                if (srp) {
+                        *lock = &srp->litmus_lock;
+                        err = 0;
+                } else
+                        err = -ENOMEM;
+                break;
+
+        case PCP_SEM:
+                /* Priority Ceiling Protocol */
+                if (get_user(cpu, (int*) config))
+                        return -EFAULT;
+
+                if (!cpu_online(cpu))
+                        return -EINVAL;
+
+                *lock = pfp_new_pcp(cpu);
+                if (*lock)
+                        err = 0;
+                else
+                        err = -ENOMEM;
+                break;
+        };
+
+        return err;
+}
+
+#endif
+
+static long pfp_admit_task(struct task_struct* tsk)
+{
+        if (task_cpu(tsk) == tsk->rt_param.task_params.cpu &&
+#ifdef CONFIG_RELEASE_MASTER
+            /* don't allow tasks on release master CPU */
+            task_cpu(tsk) != remote_dom(task_cpu(tsk))->release_master &&
+#endif
+            litmus_is_valid_fixed_prio(get_priority(tsk)))
+                return 0;
+        else
+                return -EINVAL;
+}
+
+static long pfp_activate_plugin(void)
+{
+#if defined(CONFIG_RELEASE_MASTER) || defined(CONFIG_LITMUS_LOCKING)
+        int cpu;
+#endif
+
+#ifdef CONFIG_RELEASE_MASTER
+        for_each_online_cpu(cpu) {
+                remote_dom(cpu)->release_master = atomic_read(&release_master_cpu);
+        }
+#endif
+
+#ifdef CONFIG_LITMUS_LOCKING
+        get_srp_prio = pfp_get_srp_prio;
+
+        for_each_online_cpu(cpu) {
+                init_waitqueue_head(&per_cpu(mpcpvs_vspin_wait, cpu));
+                per_cpu(mpcpvs_vspin, cpu) = NULL;
+
+                pcp_init_state(&per_cpu(pcp_state, cpu));
+                pfp_doms[cpu] = remote_pfp(cpu);
+        }
+
+#endif
+
+        return 0;
+}
+
+
+/*      Plugin object   */
+static struct sched_plugin pfp_plugin __cacheline_aligned_in_smp = {
+        .plugin_name            = "P-FP",
+        .tick                   = pfp_tick,
+        .task_new               = pfp_task_new,
+        .complete_job           = complete_job,
+        .task_exit              = pfp_task_exit,
+        .schedule               = pfp_schedule,
+        .task_wake_up           = pfp_task_wake_up,
+        .task_block             = pfp_task_block,
+        .admit_task             = pfp_admit_task,
+        .activate_plugin        = pfp_activate_plugin,
+#ifdef CONFIG_LITMUS_LOCKING
+        .allocate_lock          = pfp_allocate_lock,
+        .finish_switch          = pfp_finish_switch,
+#endif
+};
+
+
+static int __init init_pfp(void)
+{
+        int i;
+
+        /* We do not really want to support cpu hotplug, do we? ;)
+         * However, if we are so crazy to do so,
+         * we cannot use num_online_cpu()
+         */
+        for (i = 0; i < num_online_cpus(); i++) {
+                pfp_domain_init(remote_pfp(i), i);
+        }
+        return register_sched_plugin(&pfp_plugin);
+}
+
+module_init(init_pfp);
+
diff --git a/litmus/sched_psn_edf.c b/litmus/sched_psn_edf.c
index 8e4a22dd8d6a..b0c8126bd44a 100644
--- a/litmus/sched_psn_edf.c
+++ b/litmus/sched_psn_edf.c
@@ -17,6 +17,7 @@
 #include <litmus/litmus.h>
 #include <litmus/jobs.h>
 #include <litmus/preempt.h>
+#include <litmus/budget.h>
 #include <litmus/sched_plugin.h>
 #include <litmus/edf_common.h>
 #include <litmus/sched_trace.h>