001 // PriorityScheduler.java, created by cata
002 // Copyright (C) 2001 Catalin Francu <cata@mit.edu>
003 // Licensed under the terms of the GNU GPL; see COPYING for details.
004 package javax.realtime;
005
006 import java.util.HashSet;
007 import java.util.LinkedList;
008 import java.util.Iterator;
009
010 /** Class which represents the required (by RTSJ) priority-based scheduler.
011 * The default instance is the required priority scheduler which does
012 * fixed priority, preemptive scheduling.
013 */
014 public class PriorityScheduler extends Scheduler {
015 // Real-time thread priorities
016 /** The maximum priority value used by the implementation. */
017 static final int MAX_PRIORITY = 38;
018 /** The minimum priority value used by the implementation. */
019 static final int MIN_PRIORITY = 11;
020 static final int NORM_PRIORITY =
021 (MAX_PRIORITY - MIN_PRIORITY) / 3 + MIN_PRIORITY;
022
023 static HashSet allThreads = null;
024 static HashSet disabledThreads = null;
025 // The runtime constraints for the threads we're maintaining
026 static ThreadConstraints thread[] = null;
027 public static RelativeTime defaultQuanta = null;
028 static PeriodicParameters mainThreadParameters = null;
029 static PeriodicParameters noRTParameters = null;
030
031 // The first threadID that we can allocate
032 long nextThreadID = 0;
033 // The number of threads we are maintaining
034 int nThreads = 0;
035
036 // The number of missed deadlines and thenumber of times that the
037 // scheduler was invoked
038 public static long missed = 0;
039 public static long invocations = 0;
040 public static long runningTimeMicros = 0;
041
042 // The thread that chooseThread selected upon the previous invocation,
043 // and how long we've allowed that thread to run
044 long runningThread = 0;
045 RelativeTime runningTime = null;
046 static PriorityScheduler instance = null;
047
048 /** Constructor for the required scheduler. */
049 protected PriorityScheduler() {
050 super();
051 if (thread == null) {
052 thread = new ThreadConstraints[10];
053 allThreads = new HashSet();
054 disabledThreads = new HashSet();
055 defaultQuanta = new RelativeTime(2, 0);
056 runningTime = new RelativeTime(0, 0);
057 mainThreadParameters =
058 new PeriodicParameters(null, new RelativeTime(5, 0),
059 new RelativeTime(1, 0), null, null, null);
060 noRTParameters =
061 new PeriodicParameters(null, new RelativeTime(50, 0),
062 new RelativeTime(1, 0), null, null, null);
063 }
064 }
065
066 /** Return a reference to an instance of <code>PriorityScheduler</code>.
067 *
068 * @return A reference to an instance of <code>PriorityScheduler</code>.
069 */
070 public static PriorityScheduler instance() {
071 if (instance == null)
072 ImmortalMemory.instance().enter(new Runnable() {
073 public void run() {
074 instance = new PriorityScheduler();
075 }
076 });
077 return instance;
078 }
079
080 /** Inform the scheduler and cooperating facilities that the resource demands,
081 * as expressed in associated instances of <code>SchedulingParameters,
082 * ReleaseParameters, MemoryParameters</code> and <code>ProcessingGroupParameters</code>,
083 * of this instance of <code>Schedulable</code> will be considered in the
084 * feasibility analysis of the associated <code>Scheduler</code> until
085 * further notice. Whether the resulting system is feasible or not, the addition
086 * is completed.
087 *
088 * @param schedulable The instance of <code>Schedulable</code> for which the
089 * changes are proposed.
090 */
091 protected void addToFeasibility(final Schedulable schedulable) {
092 allThreads.add(schedulable);
093 thread[nThreads] = new ThreadConstraints();
094 thread[nThreads].threadID = schedulable.getUID();
095 thread[nThreads].schedulable = schedulable;
096 thread[nThreads].beginPeriod = null;
097 nThreads++;
098 }
099
100 protected native void addThreadInC(Schedulable t, long threadID);
101
102 /** Trigger the execution of a schedulable object (like
103 * an instance of <code>AsyncEventHandler</code>).
104 *
105 * @param schedulable The <code>Schedulable</code> object to make active.
106 */
107 public void fireSchedulable(Schedulable schedulable) {
108 schedulable.run();
109 }
110
111 /** Gets the maximum priority available for a thread managed by this scheduler.
112 *
113 * @return The value of the maximum priority.
114 */
115 public int getMaxPriority() {
116 return MAX_PRIORITY;
117 }
118
119 /** Gets the maximum priority of the given instance of
120 * <code>java.lang.Thread</code>. If the given thread is scheduled by the
121 * required <code>PriorityScheduler</code> the maximum priority of the
122 * <code>PriorityScheduler</code> is returned; otherwise
123 * <code>Thread.MAX_PRIORITY</code> is returned.
124 *
125 * @param thread An instance of <code>java.lang.Thread</code>. If null,
126 * the maximum priority of the required
127 * <code>PriorityScheduler</code> is returned.
128 * @return The maximum priority of the given instance of
129 * <code>java.lang.Thread</code>.
130 */
131 public static int getMaxPriority(Thread thread) {
132 return (allThreads.contains(thread)) ?
133 MAX_PRIORITY : Thread.MAX_PRIORITY;
134 }
135
136 /** Gets the minimum priority available for a thread managed by this scheduler.
137 *
138 * @return The value of the minimum priority.
139 */
140 public int getMinPriority() {
141 return MIN_PRIORITY;
142 }
143
144 /** Gets the minimum priority of the given instance of
145 * <code>java.lang.Thread</code>. If the given thread is scheduled by the
146 * required <code>PriorityScheduler</code> the minimum priority of the
147 * <code>PriorityScheduler</code> is returned; otherwise
148 * <code>Thread.MIN_PRIORITY</code> is returned.
149 *
150 * @return The value of the minimum priority of the given instance of
151 * <code>java.lang.Thread</code>.
152 */
153 public static int getMinPriority(Thread thread) {
154 return (allThreads.contains(thread)) ?
155 MIN_PRIORITY : Thread.MIN_PRIORITY;
156 }
157
158 /** Gets the normal priority available for a thread managed by this scheduler.
159 *
160 * @return The value of the normal priority.
161 */
162 public int getNormPriority() {
163 return NORM_PRIORITY;
164 }
165
166 /** Gets the normal priority of the given instance of
167 * <code>java.lang.Thread</code>. If the given thread is scheduled by the
168 * required <code>PriorityScheduler</code> the normal priority of the
169 * <code>PriorityScheduler</code> is returned; otherwise
170 * <code>Thread.NORM_PRIORITY</code> is returned.
171 */
172 public static int getNormPriority(Thread thread) {
173 return (allThreads.contains(thread)) ?
174 NORM_PRIORITY : Thread.NORM_PRIORITY;
175 }
176
177 /** Gets the policy name of <code>this</code>.
178 *
179 * @return The policy name (Fixed Priority) as a string.
180 */
181 public String getPolicyName() {
182 return "EDF";
183 }
184
185 /** Determines the load on the system. If the load is less then 1, the
186 * system is feasible. If the load is greater than or equal to 1, the
187 * system is not feasible.
188 *
189 * @param releaseParams The list of the <code>ReleaseParameters</code>
190 * to be considered when determining the load.
191 * @return The load of the system.
192 */
193 private float load(LinkedList releaseParams) {
194 float l = 0.0f;
195 for (Iterator it = releaseParams.iterator(); it.hasNext(); ) {
196 ReleaseParameters rp = (ReleaseParameters)it.next();
197 if (rp instanceof PeriodicParameters)
198 l += ((PeriodicParameters)rp).getCost().time() /
199 ((PeriodicParameters)rp).getPeriod().time();
200 else l+= ((AperiodicParameters)rp).getCost().time() /
201 ((AperiodicParameters)rp).getDeadline().time();
202 }
203
204 return l;
205 }
206
207 /** Queries the system about the feasibility of the set of
208 * <code>Schedulable</code> objects with respect to their include in the
209 * feasibility set and the constraints expressed by their associated
210 * parameter objects.
211 *
212 * @return True if the system is able to satisfy the constraints expressed
213 * by the parameter object of all instances of <code>Schedulable</code>
214 * currently in the feasibility set. False if the system cannot
215 * satisfy those constraints.
216 */
217 public boolean isFeasible() {
218 return isFeasible(null, null);
219 }
220
221 protected boolean isFeasible(Schedulable s, ReleaseParameters rp) {
222 LinkedList params = new LinkedList();
223 int i = 0;
224 boolean found = false;
225 for (Iterator it = allThreads.iterator(); it.hasNext(); ) {
226 Object obj = it.next();
227 if (obj instanceof Schedulable) {
228 Schedulable sch = (Schedulable)obj;
229 if (sch == s) {
230 params.add(new ReleaseParameters(rp));
231 found = true;
232 }
233 else if (sch.getReleaseParameters() != null) {
234 params.add(new ReleaseParameters(sch.getReleaseParameters()));
235 }
236 }
237 }
238 if ((!found) && (s != null) && (rp != null)) params.add(new ReleaseParameters(rp));
239
240 return (load(params) < 1.0);
241 }
242
243 /** Inform <code>this</code> and cooperating facilities that the
244 * <code>ReleaseParameters</code> of the ginve instance of <code>Schedulable</code>
245 * should <i>not</i> be considered in feasibility analysis until further notified.
246 *
247 * @param schedulable The instance of <code>Schedulable</code> whose
248 * <code>ReleaseParameters</code> are to be removed from the
249 * feasibility set.
250 * @return True, if the removal was ssuccessful. False, if the removal was
251 * unsuccessful.
252 */
253 protected void removeFromFeasibility(Schedulable schedulable) {
254 allThreads.remove(schedulable);
255
256 int i = 0;
257 while ((thread[i] == null || thread[i].schedulable != schedulable)
258 && i < nThreads)
259 i++;
260 if (i < nThreads) {
261 thread[i] = null; // To ensure deallocation
262 thread[i] = thread[--nThreads];
263 }
264 }
265
266 /** The method appears in many classe in the RTSJ and with various parameters.
267 * The parameters are either new scheduling characteristics for an instance
268 * <code>Schedulable</code> or an instance of <code>Schedulable</code>. The
269 * method first performs a feasibility analysis using the new scheduling
270 * characteristics of the given instance of <code>Schedulable</code>. If the
271 * resultingsystem is feasible the method replaces the current scheduling
272 * characteristics, of either <code>this</code> or the given instance of
273 * <code>Schedulable</code> as appropriate, with the new scheduling characteristics.
274 *
275 * @param schedulable The instance of <code>Schedulable</code> for which the
276 * changes are proposed
277 * @param release The proposed release parameters.
278 * @param memory The proposed memory parameters.
279 * @return True, if the resulting system is feasible and the changes are made.
280 * False, if the resulting system is not feasible and no changes are made.
281 */
282 public boolean setIfFeasible(Schedulable schedulable,
283 ReleaseParameters release,
284 MemoryParameters memory) {
285 return setIfFeasible(schedulable, release, memory, schedulable.getProcessingGroupParameters());
286 }
287
288 /** The method appears in many classe in the RTSJ and with various parameters.
289 * The parameters are either new scheduling characteristics for an instance
290 * <code>Schedulable</code> or an instance of <code>Schedulable</code>. The
291 * method first performs a feasibility analysis using the new scheduling
292 * characteristics of the given instance of <code>Schedulable</code>. If the
293 * resultingsystem is feasible the method replaces the current scheduling
294 * characteristics, of either <code>this</code> or the given instance of
295 * <code>Schedulable</code> as appropriate, with the new scheduling characteristics.
296 *
297 * @param schedulable The instance of <code>Schedulable</code> for which the
298 * changes are proposed
299 * @param release The proposed release parameters.
300 * @param memory The proposed memory parameters.
301 * @param group The proposed processing group parameters.
302 * @return True, if the resulting system is feasible and the changes are made.
303 * False, if the resulting system is not feasible and no changes are made.
304 */
305 public boolean setIfFeasible(Schedulable schedulable,
306 ReleaseParameters release,
307 MemoryParameters memory,
308 ProcessingGroupParameters group) {
309 if (isFeasible(schedulable, release)) {
310 schedulable.setReleaseParameters(release);
311 schedulable.setMemoryParameters(memory);
312 schedulable.setProcessingGroupParameters(group);
313 return true;
314 }
315 else return false;
316 }
317
318
319 /** Implements EDF (Earliest Deadline First) Algorithm */
320 protected long chooseThread(long micros) {
321 long microsBegin = RealtimeClock.getTimeInC();
322 invocations++;
323 AbsoluteTime now = new AbsoluteTime(0, (int)micros*1000);
324
325 if (nThreads == 0)
326 return (runningThread = 0);
327
328 ReleaseParameters rp = null;
329 int earliest = -1; // The periodic thread returned by EDF
330 // If earliest = -1, we'll choose the sporadic thread with the
331 // earliest starting time
332 int earliestSporadic = -1;
333 for (int i = 0; i < nThreads; i++)
334 if (thread[i] != null) { // if this thread is still alive
335 // First, if this was the running thread, reduce its workLeft
336 if (runningThread == thread[i].threadID)
337 thread[i].workLeft = thread[i].workLeft.subtract(runningTime);
338
339 // Second, update the thread parameters
340 if (thread[i].threadID == 1)
341 rp = mainThreadParameters;
342 else if (thread[i].schedulable instanceof RealtimeThread)
343 rp = thread[i].schedulable.getReleaseParameters();
344
345 // If the thread has no real time parameters, make it aperiodic
346 if (rp == null)
347 rp = noRTParameters;
348 // System.out.println(rp);
349 if (thread[i].beginPeriod == null) {
350 // This is the first time we're handling this thread.
351 // If the thread is sporadic, we'll set its endPeriod when we run
352 // it for the first time.
353 thread[i].beginPeriod = now;
354 thread[i].endPeriod = (rp instanceof PeriodicParameters) ?
355 thread[i].beginPeriod.add(((PeriodicParameters)rp).getPeriod()) :
356 new AbsoluteTime(AbsoluteTime.endOfDays);
357 thread[i].workLeft = rp.getCost();
358 thread[i].deadline = thread[i].beginPeriod.add(rp.getDeadline());
359 }
360 else if (now.compareTo(thread[i].endPeriod) >= 0) {
361 // This thread is passing into a new period
362 // (1) Check to see if the thread missed its deadline
363 if (thread[i].schedulable instanceof RealtimeThread &&
364 thread[i].workLeft.compareTo(RelativeTime.ZERO) == 1) {
365 missed++;
366 // AsyncEventHandler h = rp.getDeadlineMissHandler();
367 // if (h != null) h.run();
368 }
369 // (2) Update the thread constraints
370 thread[i].beginPeriod.set(thread[i].endPeriod);
371 if (rp instanceof PeriodicParameters)
372 thread[i].beginPeriod.add(((PeriodicParameters)rp).getPeriod(),
373 thread[i].endPeriod);
374 else
375 thread[i].endPeriod.set(AbsoluteTime.endOfDays);
376 thread[i].workLeft.set(rp.getCost());
377 thread[i].beginPeriod.add(rp.getDeadline(), thread[i].deadline);
378 }
379 // Third, use the thread for the EDF algorithm The thread must
380 // (1) not be disabled, (2) have some work left to do during
381 // this period, (3) have the earliest deadline among all threads
382 if (!disabledThreads.contains(new Long(thread[i].threadID)))
383 if (rp instanceof PeriodicParameters ||
384 (rp instanceof SporadicParameters &&
385 thread[i].workLeft.compareTo(rp.getCost()) == -1)) {
386 // This thread is either periodic, or it is sporadic AND we have
387 // started running it, so now we have to finish this period in time
388 if (thread[i].workLeft.compareTo(RelativeTime.ZERO) == 1 &&
389 (earliest == -1 ||
390 thread[i].deadline.compareTo(thread[earliest].deadline)==-1))
391 earliest = i;
392 }
393 else if (rp instanceof SporadicParameters &&
394 thread[i].workLeft.compareTo(rp.getCost()) == 0) {
395 // This thread is sporadic and we haven't started this period yet,
396 // So we'll remember it in case we have nothing urgent to do
397 if (earliestSporadic == -1 ||
398 thread[i].beginPeriod.
399 compareTo(thread[earliestSporadic].beginPeriod) == -1)
400 earliestSporadic = i;
401 }
402
403 }
404
405 // If nothing urgent, run a sporadic thread
406 if (earliest == -1 && earliestSporadic != -1) {
407 earliest = earliestSporadic;
408 // We're activating a new period for this sporadic thread, so we have to
409 // set startPeriod and endPeriod
410 thread[earliest].beginPeriod.set(now);
411 thread[earliest].beginPeriod
412 .add(((SporadicParameters)thread[earliest].schedulable.
413 getReleaseParameters()).getMinimumInterarrival(),
414 thread[earliest].endPeriod);
415 }
416
417 // If the thread has enough work left to do, give it a full
418 // quanta. Otherwise, give it only the time it needs.
419 if (earliest != -1) {
420 runningThread = thread[earliest].threadID;
421 if (thread[earliest].workLeft.compareTo(defaultQuanta) == -1)
422 runningTime.set(thread[earliest].workLeft.getMilliseconds(),
423 thread[earliest].workLeft.getNanoseconds());
424 else
425 runningTime.set(defaultQuanta.getMilliseconds(),
426 defaultQuanta.getNanoseconds());
427 setQuanta(runningTime.getMilliseconds()*1000);
428 runningTimeMicros += RealtimeClock.getTimeInC() - microsBegin;
429 return runningThread;
430 }
431
432 // Nothing to do, remain idle
433 runningTimeMicros += RealtimeClock.getTimeInC() - microsBegin;
434 return runningThread = 0;
435 }
436
437 protected void disableThread(long threadID) {
438 disabledThreads.add(new Long(threadID));
439 }
440
441 protected void enableThread(long threadID) {
442 disabledThreads.remove(new Long(threadID));
443 }
444
445 public void waitForNextPeriod(RealtimeThread rt) {
446 for (int i = 0; i < nThreads; i++)
447 if (thread[i] != null && thread[i].schedulable == rt)
448 thread[i].workLeft.set(0,0);
449 }
450
451 public void addThread(RealtimeThread rt) {
452 }
453
454 public void addThread(long threadID) {
455 }
456
457 public void removeThread(RealtimeThread rt) {
458 }
459
460 public void removeThread(long threadID) {
461 }
462
463 public String toString() {
464 return "";
465 }
466 }