Scheduling and Synchronization

As the attentive reader may have already noticed in the previous sections, scheduling and synchronization are closely related. Scheduling threads that do not interact is quite simple; however, interaction is necessary for sharing data among cooperating tasks. This interaction requires synchronization to ensure data integrity. There are implications on scheduling of threads and synchronization beyond memory access issues.

Schedulable Entities

RTSJ introduces new scheduling entities to Java. RealtimeThread and NoHeapRealtimeThread are thread types with clearer semantics than normal Java threads of class Thread and additional scheduling possibilities. Events are the other new thread-like construct used for transient computations. To save resources (mainly operating system threads, and thus memory and performance), AsyncEvents can be used for short code sequences instead. They are easy to use because they can easily be triggered programmatically, but they must not be used for blocking. Also, there are BoundAsyncEvents which each require their own thread and thus can be used for blocking. They are as easy to use as normal AsyncEvents, but do not use any fewer resources than normal threads. AsyncEventHandlers are triggered by an asynchronous event. All three execution environment, RealtimeThreads, NoHeapRealtimeThreads and AsyncEventHandlers, are schedulable entities, i.e., they all have release parameters and scheduling parameters that are considered by the scheduler.

RealtimeThreads and NoHeapRealtimeThreads

RTSJ includes new thread classes RealtimeThreads and NoHeapRealtimeThreads to improve the semantics of threads for realtime systems. These threads can use a priority range that is higher than that of all normal Java Threads with at least 28 unique priority levels. The default scheduler uses these priorities for fixed priority, preemptive scheduling. In addition to this, the new thread classes can use the new memory areas ScopedMemory and ImmortalMemory that are not under the control of the garbage collector.

As previously mentioned, threads of class NoHeapRealtimeThreads are not permitted to access any object that was allocated on the garbage collected heap. Consequently, these threads do not suffer from garbage collector activity as long as they run at a priority that is higher than that of any other schedulable object that accesses the garbage collected heap. In the JamaicaVM Java environment, the memory access restrictions present in NoHeapRealtimeThreads are not required to achieve realtime guarantees. Consequently, the use of NoHeapRealtimeThreads is neither required nor recommended.

Apart from the extended priority range, RealtimeThreads provide features that are required in many realtime applications. Scheduling parameters for periodic tasks, deadlines, and resource constraints can be given for RealtimeThreads, and used to implemented more complex scheduling algorithms. For instance, periodic threads in the JamaicaVM use these parameters. In the JamaicaVM Java environment, normal Java threads also profit from strict fixed priority, preemptive scheduling; but for realtime code, the use of RealtimeThread is still recommended.

AsyncEventHandlers vs. BoundAsyncEventHandlers

An alternative execution environment is provided through classes AsyncEventHandler and BoundAsyncEventHandler. Code in an event handler is executed to react to an event. Events are bound to some external happening (e.g, a processor interrupt), which triggers the event.

AsyncEventHandler and BoundAsyncEventHandler are schedulable entities that are equipped with release and scheduling parameters exactly as RealtimeThread and NoHeapRealtimeThread. The priority scheduler schedules both, threads and event handlers, according to their priority. Also, admission checking may take the release parameters of threads and asynchronous event handlers in account. The release parameters include values such as execution time, period, and minimum interarrival time.

One important difference from threads is that an AsyncEventHandler is not bound to one single thread. This means, that several invocations of the same handler may be performed in different thread environments. A pool of preallocated RealtimeThreads is used for the execution of these handlers. Event handlers that may execute for a long time or that may block during their execution may block a thread from this pool for a long time. This may make the timely execution of other event handlers impossible.

Any event handler that may block should therefore have one RealtimeThread that is assigned to it alone for the execution of its event handler. Handlers for class BoundAsyncEventHandler provide this feature. They do not share their thread with any other event handler and they may consequently block without disturbing the execution of other event handlers.

Due to the additional resources required for a BoundAsyncEventHandler, their use should be restricted to blocking or long running events only. The sharing of threads used for normal AsyncEventHandlers permits the use of a large number of event handlers with minimal resource usage.

Synchronization

Synchronization is essential to data sharing, especially between cooperating realtime tasks. Passing data between threads at different priorities without impairing the realtime behavior of the system is the most important concern. It is essential to ensure that a lower priority task cannot preempt a higher priority task.

The situation in Figure 12-5 depicts a case of priority inversion when using monitors, the most common priority problem. The software problems during the Pathfinder mission on Mars is the most popular example of a classic priority inversion error [Jones97].

In this situation, a higher priority thread A has to wait for a lower priority thread B because another thread C with even lower priority is holding a monitor for which A is waiting. In this situation, B will prevent A and C from running, because A is blocked and C has lower priority. In fact, this is a programming error. If a thread might enter a monitor which a higher priority thread might require, then no other thread should have a priority in between the two.

Since errors of this nature are very hard to locate, the programming environment should provide a means for avoiding priority inversion. The RTSJ defines two possible mechanisms for avoiding priority inversion: Priority Inheritance and Priority Ceiling Emulation. The JamaicaVM implements both mechanisms.

Figure 12-5. Priority Inversion

Priority Inheritance

Priority Inheritance is a protocol which is easy to understand and to use, but that poses the risk of causing deadlocks. If priority inheritance is used, whenever a higher priority thread waits for a monitor that is held by a lower priority thread, the lower priority thread's priority is boosted to the priority of the blocking thread. Figure 12-6 illustrates this.

Figure 12-6. Priority Inheritance

Priority Ceiling Emulation

Priority Ceiling Emulation is widely used in safety-critical system. The priority of any thread entering a monitor is raised to the highest priority of any thread which could ever enter the monitor. Figure 12-7 illustrates the Priority Ceiling Emulation protocol.

As long as no thread that holds a priority ceiling emulation monitor blocks, any thread that tries to enter such a monitor can be sure not to block [1]. Consequently, the use of priority ceiling emulation automatically ensures that a system is deadlock-free.

Figure 12-7. Priority Ceiling Emulation Protocol

Priority Inheritance vs. Priority Ceiling Emulation

Priority Inheritance should be used with care, because it can cause deadlocks when two threads try to enter the same two monitors in different order. This is shown in Figure 12-8. Thus it is safer to use Priority Ceiling Emulation, since when used correctly, deadlocks cannot occur there. Priority Inheritance deadlocks can be avoided, if all programmers make sure to always enter monitors in the same order.

Figure 12-8. Deadlocks are possible with Priority Inheritance

Unlike classic priority ceiling emulation, RTSJ permits blocking while holding a priority ceiling emulation monitor. Other threads that may want to enter the same monitor will be stopped exactly as they would be for a normal monitor. This fall back to standard monitor behavior permits the use of priority ceiling emulation even for monitors that are used by legacy code.

The advantage of a limited and short execution time for entering a priority ceiling monitor, working on a shared resource, then leaving this monitor are, however, lost when a thread that has entered this monitor may block. Therefore the system designer should restrict the use of priority ceiling monitors to short code sequences that only access a shared resource and that do not block. Entering and exiting the monitor can then be performed in constant time, and the system ensures that no thread may try to enter a priority ceiling monitor that is held by some other thread.

Since priority ceiling emulation requires adjusting a thread's priority every time a monitor is entered or exited, there is an additional runtime overhead for this priority change when using these monitors. This overhead can be significant compared to the low runtime overhead that is incurred to enter or leave a normal, priority inheritance monitor. In this case, there is a priority change penalty only when a monitor has already been taken by another thread.

Future versions of the Jamaica Java implementation may optimize priority ceiling and avoid unnecessary priority changes. The JamaicaVM uses atomic code sequences and restricts thread switches to certain points in the code. A synchronized code sequence that is protected by a priority ceiling monitor and that does not contain a synchronization point may not require entering and leaving of the monitor at all since the code sequence is guaranteed to be executed atomically due to the fact that it does not contain a synchronization point.

Notes

[1]

If any other thread owns the monitor, its priority will have been boosted to the ceiling priority. Consequently, the current thread cannot run and try to enter this monitor.