NSPR 2.0: Thread priorities

The notion of a priority associated with a thread of execution is fairly well established. The implication is that a thread with the most urgent priority level that is schedulable will be running. In operating systems that provide threading and those threads are scheduled based purely on their priority, that is a fairly basic and implementable model.

However, there are effectively no such systems in existence today. The reason is that the model is very unsafe. Any thread that elevates its priority above other threads in the system and then, intentionally or not, misbehaves, can starve all the other threads. If the threads are globally scheduled, that could effectively deadlock an entire system. Therefore most vendors have chosen a more safe (and complicated) model for scheduling. NSPR, being subject to all such models (and there are several) has tried to get a working common solution.

There are inconsistent mechanisms to control the priority of globally scheduled execution entities. Where they are available to a non privileged user, NSPR will attempt to make use of them. In cases where there seems to be no reliable mechanism available, NSPR will silently suppress client attempts to control priorities in the belief that the host OS will be doing the right thing.

NSPR implements a virtual processor called a CPU. A CPU is globally scheduled, i.e., it is scheduled by the host operating system. In UNIX or NT, this would be equivalent to a process. In other systems such as Macintosh or WIN16, full process semantics are not available, but a similar concept (perhaps called an application) is available. Some systems provide multiple global scheduable entities per process (threads). There are several such systems available in the community today and more showing up all the time (e.g., Solaris threads, WIN32 threads, IRIX' sprocs and pthreads on several UNIXs).  NSPR exploits such systems by allowing the creation of multiple CPUs per process.

Associated with each CPU are one or more locally scheduled NSPR threads. Local threads are another level of virtual processor, each possessing their own stack and processor state. NSPR directly manages (schedules) local threads; the host operating system is not aware that they exist. Therefore, one can say that NSPR will schedule the highest priority thread associated with a particular CPU.

The thread priority is only a relationship between the threads being supported by a single CPU, and assumes that the CPUs are scheduled fairly by the OS. The implementation may be considered to be an array where there are as many elements in the array as there are unique priority levels. The contents of the array's elements are a circular list of ready threads. To select a thread for scheduling, take the thread off the head of the circular list from the highest priority element of the array. When descheduling a thread, put it at the tail of the list of the priority at which that thread is running.

The caveat is that one cannot predict what CPU is supporting a thread at any given time.

Thread priorities a specified by the client. NSPR provides the opportunity to assign a priority when the thread is created and later through another API item (SetThreadPriority()). This latter function is troublesome. It allows one thread to modify the priority of another. This is not a safe operation, and it is expensive to implement in the likely expected manner. Consequently, the semantics of SetThreadPriority() are that it will take effect the first time a thread is descheduled. This is very close to the expected behavior if the thread affected is the current thread (self). However, it may not behave exactly as expected if the affected thread is other than self since the affected thread must actually get scheduled before the affect can be recorded.

The reasons for this strategy are due to runtime considerations. Any operation where one thread affects the state of another is expensive in the runtime. Most of the expense of the operations goes away if the thread is only allowed to modify its own state. Specifically in the NSPR runtime, the issues are as follows: The priority field of a thread structure is a full, aligned word. We can write that word safely without any locking. What the runtime needs to protect is when the field is to be applied. The only time that the priority has any effect is when a thread is descheduled - it indicates what slot to store it in. If we don't attempt to apply the change in priority until such time the affected thread is descheduled, then we really need no locking.