source: rtems/cpukit/score/include/rtems/score/scheduleredf.h @ 99fc1d1d

5
Last change on this file since 99fc1d1d was 99fc1d1d, checked in by Sebastian Huber <sebastian.huber@…>, on Jun 9, 2016 at 7:30:40 PM

score: Rework EDF scheduler

Use inline red-black tree insert. Do not use shifting priorities since
this is not supported by the thread queues. Due to the 32-bit
Priority_Control this currently limits the uptime to 49days with a 1ms
clock tick.

Update #2173.

  • Property mode set to 100644
File size: 7.4 KB
Line 
1/**
2 *  @file  rtems/score/scheduleredf.h
3 *
4 *  @brief Data Related to the Manipulation of Threads for the EDF Scheduler
5 *
6 *  This include file contains all the constants and structures associated
7 *  with the manipulation of threads for the EDF scheduler.
8 */
9
10/*
11 *  Copryight (c) 2011 Petr Benes.
12 *  Copyright (C) 2011 On-Line Applications Research Corporation (OAR).
13 *
14 *  The license and distribution terms for this file may be
15 *  found in the file LICENSE in this distribution or at
16 *  http://www.rtems.org/license/LICENSE.
17 */
18
19#ifndef _RTEMS_SCORE_SCHEDULEREDF_H
20#define _RTEMS_SCORE_SCHEDULEREDF_H
21
22#include <rtems/score/priority.h>
23#include <rtems/score/scheduler.h>
24#include <rtems/score/schedulerpriority.h>
25#include <rtems/score/rbtree.h>
26
27#ifdef __cplusplus
28extern "C" {
29#endif
30
31/**
32 *  @defgroup ScoreSchedulerEDF EDF Scheduler
33 *
34 *  @ingroup ScoreScheduler
35 */
36/**@{*/
37
38#define SCHEDULER_EDF_MAXIMUM_PRIORITY 0x7fffffff
39
40/**
41 *  Entry points for the Earliest Deadline First Scheduler.
42 */
43#define SCHEDULER_EDF_ENTRY_POINTS \
44  { \
45    _Scheduler_EDF_Initialize,       /* initialize entry point */ \
46    _Scheduler_EDF_Schedule,         /* schedule entry point */ \
47    _Scheduler_EDF_Yield,            /* yield entry point */ \
48    _Scheduler_EDF_Block,            /* block entry point */ \
49    _Scheduler_EDF_Unblock,          /* unblock entry point */ \
50    _Scheduler_EDF_Change_priority,  /* change priority entry point */ \
51    _Scheduler_EDF_Map_priority,     /* map priority entry point */ \
52    _Scheduler_EDF_Unmap_priority,   /* unmap priority entry point */ \
53    SCHEDULER_OPERATION_DEFAULT_ASK_FOR_HELP \
54    _Scheduler_EDF_Node_initialize,  /* node initialize entry point */ \
55    _Scheduler_default_Node_destroy, /* node destroy entry point */ \
56    _Scheduler_EDF_Update_priority,  /* update priority entry point */ \
57    _Scheduler_EDF_Release_job,      /* new period of task */ \
58    _Scheduler_default_Tick,         /* tick entry point */ \
59    _Scheduler_default_Start_idle    /* start idle entry point */ \
60    SCHEDULER_OPERATION_DEFAULT_GET_SET_AFFINITY \
61  }
62
63/**
64 * This is just a most significant bit of Priority_Control type. It
65 * distinguishes threads which are deadline driven (priority
66 * represented by a lower number than @a SCHEDULER_EDF_PRIO_MSB) from those
67 * ones who do not have any deadlines and thus are considered background
68 * tasks.
69 */
70#define SCHEDULER_EDF_PRIO_MSB 0x80000000
71
72typedef struct {
73  /**
74   * @brief Basic scheduler context.
75   */
76  Scheduler_Context Base;
77
78  /**
79   * Top of the ready queue.
80   */
81  RBTree_Control Ready;
82} Scheduler_EDF_Context;
83
84/**
85 * @brief Scheduler node specialization for EDF schedulers.
86 */
87typedef struct {
88  /**
89   * @brief Basic scheduler node.
90   */
91  Scheduler_Node Base;
92
93  /**
94   * Pointer to corresponding Thread Control Block.
95   */
96  Thread_Control *thread;
97  /**
98   * Rbtree node related to this thread.
99   */
100  RBTree_Node Node;
101
102  /**
103   * @brief The thread priority used by this scheduler instance in case no job
104   * is released.
105   */
106  Priority_Control background_priority;
107
108  /**
109   * @brief The thread priority currently used by this scheduler instance.
110   */
111  Priority_Control current_priority;
112} Scheduler_EDF_Node;
113
114/**
115 *  @brief Initialize EDF scheduler.
116 *
117 *  This routine initializes the EDF scheduler.
118 *
119 *  @param[in] scheduler The scheduler instance.
120 */
121void _Scheduler_EDF_Initialize( const Scheduler_Control *scheduler );
122
123/**
124 *  @brief Removes thread from ready queue.
125 *
126 *  This routine removes @a the_thread from the scheduling decision,
127 *  that is, removes it from the ready queue.  It performs
128 *  any necessary scheduling operations including the selection of
129 *  a new heir thread.
130 *
131 *  @param[in] scheduler The scheduler instance.
132 *  @param[in] the_thread is the thread to be blocked.
133 */
134void _Scheduler_EDF_Block(
135  const Scheduler_Control *scheduler,
136  Thread_Control          *the_thread
137);
138
139/**
140 *  @brief Sets the heir thread to be the next ready thread
141 *  in the rbtree ready queue.
142 *
143 *  This kernel routine sets the heir thread to be the next ready thread
144 *  in the rbtree ready queue.
145 *
146 *  @param[in] scheduler The scheduler instance.
147 *  @param[in] the_thread being scheduled.
148 */
149void _Scheduler_EDF_Schedule(
150  const Scheduler_Control *scheduler,
151  Thread_Control          *the_thread
152);
153
154/**
155 *  @brief Initializes an EDF specific scheduler node of @a the_thread.
156 *
157 *  @param[in] scheduler The scheduler instance.
158 *  @param[in] the_thread being initialized.
159 */
160void _Scheduler_EDF_Node_initialize(
161  const Scheduler_Control *scheduler,
162  Thread_Control          *the_thread
163);
164
165/**
166 *  @brief Updates position in the ready queue of @a the_thread.
167 *
168 *  This routine updates position in the ready queue of @a the_thread.
169 *
170 *  @param[in] scheduler The scheduler instance.
171 *  @param[in] the_thread will have its scheduler specific information
172 *             structure updated.
173 *  @param[in] new_priority is the desired new priority.
174 */
175void _Scheduler_EDF_Update_priority(
176  const Scheduler_Control *scheduler,
177  Thread_Control          *the_thread,
178  Priority_Control         new_priority
179);
180
181/**
182 *  @brief Adds @a the_thread to the scheduling decision.
183 *
184 *  This routine adds @a the_thread to the scheduling decision, that is,
185 *  adds it to the ready queue and updates any appropriate scheduling
186 *  variables, for example the heir thread.
187 *
188 *  @param[in] scheduler The scheduler instance.
189 *  @param[in] the_thread will be unblocked.
190 */
191Scheduler_Void_or_thread _Scheduler_EDF_Unblock(
192  const Scheduler_Control *scheduler,
193  Thread_Control          *the_thread
194);
195
196Scheduler_Void_or_thread _Scheduler_EDF_Change_priority(
197  const Scheduler_Control *scheduler,
198  Thread_Control          *the_thread,
199  Priority_Control         new_priority,
200  bool                     prepend_it
201);
202
203Priority_Control _Scheduler_EDF_Map_priority(
204  const Scheduler_Control *scheduler,
205  Priority_Control         priority
206);
207
208Priority_Control _Scheduler_EDF_Unmap_priority(
209  const Scheduler_Control *scheduler,
210  Priority_Control         priority
211);
212
213/**
214 *  @brief invoked when a thread wishes to voluntarily
215 *  transfer control of the processor to another thread
216 *  with equal deadline.
217 *
218 *  This routine is invoked when a thread wishes to voluntarily
219 *  transfer control of the processor to another thread in the queue with
220 *  equal deadline. This does not have to happen very often.
221 *
222 *  This routine will remove the specified THREAD from the ready queue
223 *  and place it back. The rbtree ready queue is responsible for FIFO ordering
224 *  in such a case.
225 *
226 *  @param[in] scheduler The scheduler instance.
227 *  @param[in,out] the_thread The yielding thread.
228 */
229Scheduler_Void_or_thread _Scheduler_EDF_Yield(
230  const Scheduler_Control *scheduler,
231  Thread_Control          *the_thread
232);
233
234/**
235 *  @brief Called when a new job of task is released.
236 *
237 *  This routine is called when a new job of task is released.
238 *  It is called only from Rate Monotonic manager in the beginning
239 *  of new period.
240 *
241 *  @param[in] scheduler The scheduler instance.
242 *  @param[in] the_thread is the owner of the job.
243 *  @param[in] deadline of the new job from now. If equal to 0,
244 *             the job was cancelled or deleted, thus a running task
245 *             has to be suspended.
246 */
247void _Scheduler_EDF_Release_job (
248  const Scheduler_Control *scheduler,
249  Thread_Control          *the_thread,
250  uint64_t                 deadline
251);
252
253#ifdef __cplusplus
254}
255#endif
256
257/**@}*/
258
259#endif
260/* end of include file */
Note: See TracBrowser for help on using the repository browser.