score: Implement SMP-specific priority queue

1 files changed, 54 insertions, 0 deletions

diff --git a/doc/user/smp.t b/doc/user/smp.t
index 12711e5997..db4114c564 100644
--- a/doc/user/smp.t
+++ b/doc/user/smp.t
@@ -186,6 +186,60 @@ To set the scheduler of a task see @ref{Symmetric Multiprocessing Services
 SCHEDULER_IDENT - Get ID of a scheduler} and @ref{Symmetric Multiprocessing
 Services TASK_SET_SCHEDULER - Set scheduler of a task}.
 
+@subsection Task Priority Queues
+
+Due to the support for clustered scheduling the task priority queues need
+special attention.  It makes no sense to compare the priority values of two
+different scheduler instances.  Thus, it is not possible to simply use one
+plain priority queue for tasks of different scheduler instances.
+
+One solution to this problem is to use two levels of queues.  The top level
+queue provides FIFO ordering and contains priority queues.  Each priority queue
+is associated with a scheduler instance and contains only tasks of this
+scheduler instance.  Tasks are enqueued in the priority queue corresponding to
+their scheduler instance.  In case this priority queue was empty, then it is
+appended to the FIFO.  To dequeue a task the highest priority task of the first
+priority queue in the FIFO is selected.  Then the first priority queue is
+removed from the FIFO.  In case the previously first priority queue is not
+empty, then it is appended to the FIFO.  So there is FIFO fairness with respect
+to the highest priority task of each scheduler instances. See also @cite{
+Brandenburg, Björn B.: A fully preemptive multiprocessor semaphore protocol for
+latency-sensitive real-time applications. In Proceedings of the 25th Euromicro
+Conference on Real-Time Systems (ECRTS 2013), pages 292–302, 2013.
+@uref{http://www.mpi-sws.org/~bbb/papers/pdf/ecrts13b.pdf}}.
+
+Such a two level queue may need a considerable amount of memory if fast enqueue
+and dequeue operations are desired (depends on the scheduler instance count).
+To mitigate this problem an approch of the FreeBSD kernel was implemented in
+RTEMS.  We have the invariant that a task can be enqueued on at most one task
+queue.  Thus, we need only as many queues as we have tasks.  Each task is
+equipped with spare task queue which it can give to an object on demand.  The
+task queue uses a dedicated memory space independent of the other memory used
+for the task itself. In case a task needs to block, then there are two options
+
+@itemize @bullet
+@item the object already has task queue, then the task enqueues itself to this
+already present queue and the spare task queue of the task is added to a list
+of free queues for this object, or
+@item otherwise, then the queue of the task is given to the object and the task
+enqueues itself to this queue.
+@end itemize
+
+In case the task is dequeued, then there are two options
+
+@itemize @bullet
+@item the task is the last task on the queue, then it removes this queue from
+the object and reclaims it for its own purpose, or
+@item otherwise, then the task removes one queue from the free list of the
+object and reclaims it for its own purpose.
+@end itemize
+
+Since there are usually more objects than tasks, this actually reduces the
+memory demands. In addition the objects contain only a pointer to the task
+queue structure. This helps to hide implementation details and makes it
+possible to use self-contained synchronization objects in Newlib and GCC (C++
+and OpenMP run-time support).
+
 @subsection Scheduler Helping Protocol
 
 The scheduler provides a helping protocol to support locking protocols like