diff options
author | Joel Sherrill <joel.sherrill@oarcorp.com> | 2014-07-07 14:26:13 -0500 |
---|---|---|
committer | Joel Sherrill <joel.sherrill@oarcorp.com> | 2014-07-15 12:43:44 -0500 |
commit | ed7a02895e3bedda5edb33c91f0ffc956e9cab06 (patch) | |
tree | 0266870aab25e0eca278237aca3e11a621a12c9e /cpukit/score/include | |
parent | rbtree: Reduce RBTree_Control size (diff) | |
download | rtems-ed7a02895e3bedda5edb33c91f0ffc956e9cab06.tar.bz2 |
Thread Queue Priority Discipline Reimplemented with RBTree
Diffstat (limited to '')
-rw-r--r-- | cpukit/score/include/rtems/score/thread.h | 4 | ||||
-rw-r--r-- | cpukit/score/include/rtems/score/threadq.h | 23 | ||||
-rw-r--r-- | cpukit/score/include/rtems/score/threadqimpl.h | 71 |
3 files changed, 38 insertions, 60 deletions
diff --git a/cpukit/score/include/rtems/score/thread.h b/cpukit/score/include/rtems/score/thread.h index 0d9025fdfa..be357895dd 100644 --- a/cpukit/score/include/rtems/score/thread.h +++ b/cpukit/score/include/rtems/score/thread.h @@ -304,6 +304,8 @@ typedef struct { typedef struct { /** This field is the object management structure for each proxy. */ Objects_Control Object; + /** This field is used to enqueue the thread on RBTrees. */ + RBTree_Node RBNode; /** This field is the current execution state of this proxy. */ States_Control current_state; /** This field is the current priority state of this proxy. */ @@ -541,6 +543,8 @@ typedef struct { struct Thread_Control_struct { /** This field is the object management structure for each thread. */ Objects_Control Object; + /** This field is used to enqueue the thread on RBTrees. */ + RBTree_Node RBNode; /** This field is the current execution state of this thread. */ States_Control current_state; /** This field is the current priority state of this thread. */ diff --git a/cpukit/score/include/rtems/score/threadq.h b/cpukit/score/include/rtems/score/threadq.h index c8f2aa44bf..35e0f1d617 100644 --- a/cpukit/score/include/rtems/score/threadq.h +++ b/cpukit/score/include/rtems/score/threadq.h @@ -8,7 +8,7 @@ */ /* - * COPYRIGHT (c) 1989-2008. + * COPYRIGHT (c) 1989-2014. * On-Line Applications Research Corporation (OAR). * * The license and distribution terms for this file may be @@ -22,6 +22,7 @@ #include <rtems/score/chain.h> #include <rtems/score/states.h> #include <rtems/score/threadsync.h> +#include <rtems/score/rbtree.h> #ifdef __cplusplus extern "C" { @@ -48,22 +49,6 @@ typedef enum { } Thread_queue_Disciplines; /** - * This is one of the constants used to manage the priority queues. - * - * There are four chains used to maintain a priority -- each chain - * manages a distinct set of task priorities. The number of chains - * is determined by TASK_QUEUE_DATA_NUMBER_OF_PRIORITY_HEADERS. - * The following set must be consistent. - * - * The set below configures 4 headers -- each contains 64 priorities. - * Header x manages priority range (x*64) through ((x*64)+63). If - * the priority is more than half way through the priority range it - * is in, then the search is performed from the rear of the chain. - * This halves the search time to find the insertion point. - */ -#define TASK_QUEUE_DATA_NUMBER_OF_PRIORITY_HEADERS 4 - -/** * This is the structure used to manage sets of tasks which are blocked * waiting to acquire a resource. */ @@ -74,8 +59,8 @@ typedef struct { union { /** This is the FIFO discipline list. */ Chain_Control Fifo; - /** This is the set of lists for priority discipline waiting. */ - Chain_Control Priority[TASK_QUEUE_DATA_NUMBER_OF_PRIORITY_HEADERS]; + /** This is the set of threads for priority discipline waiting. */ + RBTree_Control Priority; } Queues; /** This field is used to manage the critical section. */ Thread_blocking_operation_States sync_state; diff --git a/cpukit/score/include/rtems/score/threadqimpl.h b/cpukit/score/include/rtems/score/threadqimpl.h index 91f09383f2..0acc66ee6c 100644 --- a/cpukit/score/include/rtems/score/threadqimpl.h +++ b/cpukit/score/include/rtems/score/threadqimpl.h @@ -8,7 +8,7 @@ */ /* - * COPYRIGHT (c) 1989-2009. + * COPYRIGHT (c) 1989-2014. * On-Line Applications Research Corporation (OAR). * * The license and distribution terms for this file may be @@ -37,18 +37,6 @@ extern "C" { #define THREAD_QUEUE_WAIT_FOREVER WATCHDOG_NO_TIMEOUT /** - * This is one of the constants used to manage the priority queues. - * @ref TASK_QUEUE_DATA_NUMBER_OF_PRIORITY_HEADERS for more details. - */ -#define TASK_QUEUE_DATA_PRIORITIES_PER_HEADER 64 - -/** - * This is one of the constants used to manage the priority queues. - * @ref TASK_QUEUE_DATA_NUMBER_OF_PRIORITY_HEADERS for more details. - */ -#define TASK_QUEUE_DATA_REVERSE_SEARCH_MASK 0x20 - -/** * The following type defines the callout used when a remote task * is extracted from a local thread queue. */ @@ -117,13 +105,25 @@ void _Thread_queue_Enqueue_with_handler( * and cancels any timeouts associated with this blocking. * * @param[in] the_thread_queue is the pointer to the ThreadQ header - * @param[in] the_thread is the pointer to a thread control block that is to be removed + * @param[in] the_thread is the pointer to a thread control block that + * is to be removed */ void _Thread_queue_Extract( Thread_queue_Control *the_thread_queue, Thread_Control *the_thread ); +/** + * @brief Extracts thread from thread queue (w/return code). + * + * This routine removes @a the_thread from @a the_thread_queue + * and cancels any timeouts associated with this blocking. + * + * @param[in] the_thread_queue is the pointer to the ThreadQ header + * @param[in] the_thread is the pointer to a thread control block that + * is to be removed + * @param[in] return_code specifies the status to be returned. + */ void _Thread_queue_Extract_with_return_code( Thread_queue_Control *the_thread_queue, Thread_Control *the_thread, @@ -227,8 +227,7 @@ Thread_Control *_Thread_queue_Dequeue_priority( * well as filling in *@ level_p with the previous interrupt level. * * - INTERRUPT LATENCY: - * + forward less than - * + forward equal + * + single case */ Thread_blocking_operation_States _Thread_queue_Enqueue_priority ( Thread_queue_Control *the_thread_queue, @@ -245,8 +244,9 @@ Thread_blocking_operation_States _Thread_queue_Enqueue_priority ( * @param[in] the_thread pointer to a thread control block * @param[in] requeuing true if requeuing and should not alter * timeout or state + * * - INTERRUPT LATENCY: - * + EXTRACT_PRIORITY + * + single case * * @retval true The extract operation was performed by the executing context. * @retval false Otherwise. @@ -262,9 +262,9 @@ void _Thread_queue_Extract_priority_helper( * * This macro wraps the underlying call and hides the requeuing argument. */ - #define _Thread_queue_Extract_priority( _the_thread, _return_code ) \ _Thread_queue_Extract_priority_helper( _the_thread, _return_code, false ) + /** * @brief Get highest priority thread on the_thread_queue. * @@ -377,35 +377,24 @@ void _Thread_queue_Process_timeout( ); /** - * This function returns the index of the priority chain on which - * a thread of the_priority should be placed. - */ - -RTEMS_INLINE_ROUTINE uint32_t _Thread_queue_Header_number ( - Priority_Control the_priority -) -{ - return (the_priority / TASK_QUEUE_DATA_PRIORITIES_PER_HEADER); -} - -/** - * This function returns true if the_priority indicates that the - * enqueue search should start at the front of this priority - * group chain, and false if the search should start at the rear. + * @brief Compare two thread's priority for RBTree Insertion. + * + * @param[in] left points to the left thread's RBnode + * @param[in] right points to the right thread's RBnode + * + * @retval 1 The @left node is more important than @right node. + * @retval 0 The @left node is of equal importance with @right node. + * @retval 1 The @left node is less important than @right node. */ - -RTEMS_INLINE_ROUTINE bool _Thread_queue_Is_reverse_search ( - Priority_Control the_priority -) -{ - return ( the_priority & TASK_QUEUE_DATA_REVERSE_SEARCH_MASK ); -} +int _Thread_queue_Compare_priority( + const RBTree_Node *left, + const RBTree_Node *right +); /** * This routine is invoked to indicate that the specified thread queue is * entering a critical section. */ - RTEMS_INLINE_ROUTINE void _Thread_queue_Enter_critical_section ( Thread_queue_Control *the_thread_queue ) |