Priorities, Scheduling and Real-time
By davidholmes on Jan 31, 2008
Since I first teamed up with Doug Lea to teach people about concurrent programming in Java there have been two main rules that we always stress with regards to synchronization and scheduling of threads:
- You should always assume that the actions of any two threads can be interleaved in any way.
- You should never require that the actions of any two threads will be interleaved in some specific way.
The consequence of rule 1 is that you must always use an appropriate synchronization mechanism whenever you access shared, mutable state - eg. using synchronized methods/blocks or using explicit java.util.concurrent Locks.
The consequence of rule 2 is that you must always use explicit synchronization mechanisms when you want threads to coordinate their actions in a particular way - eg. using wait/notify, Thread.join or explicit synchronizers from java.util.concurrent to establish the desired inter-thread communication pattern.
You must never try to use scheduling as a replacement for proper synchronization.
These two rules capture the vagueness of scheduling as defined in the Java platform. In short the Java platform does not define a scheduling model for threads but instead defers to the underlying thread implementation - typically the native threads of the host operating system. There is a notion of priority in the Java threading model, but this is just a hint to the scheduler as to the perceived relative importance of one thread compared to another in the same JVM. The way in which the JVM maps these hints to the underlying OS scheduler not only varies from JVM to JVM, but from platform to platform for a given JVM, and from release to release for a given JVM on a given platform! The capriciousness of this mapping is described in Dave Dice's blog entries and linked articles.
While rule 1 is taken as given by most programmers, rule 2 is often overlooked, particularly when it comes to progression and fairness. Many applications have many threads (think of a classic server application) doing essentially the same job and relatively independently. Many of those applications desire these threads to be treated in a "fair" manner such that each makes progress to completing its task in a relatively uniform rate. Such fairness is not guaranteed by the Java platform, but it is typically the behaviour of the underlying operating system schedulers which use time-slicing to ensure threads across different processes (and thus also within a process) get a "fair" share of CPU time. Such behaviour is usually effected by using the "time-sharing" scheduling class of the OS.
This utopian scheduling world is turned on its head when it comes to real-time systems. In a real-time system, priority rules. Priority-preemptive scheduling ensures that the highest priority runnable threads will always run. If those threads choose never to voluntarily relinquish a CPU (e.g. by performing an operation that inherently blocks: contended lock acquisition, monitor wait, sleep, blocking I/O operation) then they never relinquish that CPU. It is this "run to block" behaviour that most often surprises applications developers when they move to a real-time system. (It is also why executing in the real-time scheduling class requires explicit privileges.)
Note:There are real-time scheduling policies that perform time-slicing amongst threads of the same priority, however such a policy is not defined as part of the Real-Time Specification for Java.
In a real-time system, priority is a system-wide concept. You're not only prioritizing one thread in your application with respect to another thread in your application, you are prioritizing it with respect to other threads in other processes, possibly even key operating system services, on which your application (and others) might rely. A real-time system requires a holistic approach to priority assignment. One of the goals of Sun's Java Real-time System (Java RTS) is to enable application developers to access the full range of real-time priorities available on the underlying platform. But in doing so, the developer must be aware that they are responsible for making sensible priority choices in the context of the system as a whole.
The maximum number of real-time priorities available for Java RTS to use depends on the host operating system:
- Solaris: there are 60 real-time priorities (numbered 0 to 59). To use the real-time priorities you have to assign the thread to the real-time (RT) scheduling class. Non-real-time threads use the interactive (IA) or time-sharing (TS) scheduling classes.
- Linux: there are 99 real-time priorities (numbered 1 to 99). To use the real-time priorities you have to assign the thread the SCHED_FIFO scheduling policy. Non-real-time threads are assigned the SCHED_OTHER scheduling policy (which is an unspecified policy typically implemented as a time-sharing scheduler). Linux uses the POSIX real-time extensions for supporting real-time scheduling. These POSIX interfaces are also supported by Solaris but on Solaris, Java RTS works directly with the native layer rather than this portable layer (that's the 'P' in POSIX).
The minimum real-time priority value, RTSJMinPriority, is always 11 - one greater than the maximum java.lang.Thread priority. The maximum real-time priority value, RTSJMaxPriority, is (RTSJMinPriority+RTSJNumRTPrio-1). The RTSJMaxPriority value is reserved for use by Java RTS itself, so the maximum real-time priority available to application code is RTSJMaxPriority-1 (and the number of available real-time priorities is RTSJNumRTPrio-1). Application code should always use the methods of the PriorityScheduler instance to determine the minimum and maximum real-time priorities available to it.
Solaris ranks all the different scheduling classes and their associated local notion of "priority" into a global priority scheme. There are four priority groups in that scheme:
- The lowest priority group contains the interactive and time-sharing threads.
- The next group is reserved for "system" tasks/services.
- The next group is for the real-time scheduling class; and
- Finally, the highest priority group is for interrupt service routines.
In contrast, the default value of RTSJNumRTPrio on Linux is 49 - allowing Java RTS to only use real-time priorities 1 through 49. The reason for this value is that by default real-time Linux systems assign priorities as follows. There are no reserved priority bands. Most system services are non-realtime as with Solaris; whereas interrupt service routines are all real-time. However, in Linux, interrupt service routines are split into two parts: the hard-IRQ handlers and the soft-IRQ handlers. The hard handlers have top priority at 99, whereas the soft handlers only have (in most cases) priority 50. If application threads use priority 50, or higher, they can interfere with these soft handlers and, for example, cause delays in the processing of system timers and so in the release of periodic real-time threads, or deadline miss handlers. In simple terms the application/VM threads can interfere with the very operating system services they rely upon for correct, and timely, execution! By limiting RTSJNumRTPrio to 49 this interference can not happen. If the user has determined that their application code must run at a higher priority, and perhaps after reconfiguring critical soft handlers to use a higher priority themselves, then the user can set RTSJNumRTPrio to a value of their choosing. But this must be done with care - again taking a holistic approach to priority assignment - setting RTSJNumRTPrio too high could make your system unstable or unresponsive.