Preemptive scheduling with "do not disturb"

Question

In this answer about threading it is said:

In preemptive scheduling, a thread can be interrupted at any time, either by a timer interrupt or any other interrupt or during a system call. The part of the system that performs the context switch must save all the registers and other settings, and restore the context of the new thread.

It's harder to write programs for systems with preemptive scheduling: they're prone to race conditions. On the other hand, these systems are more robust in that even if a thread is buggy and goes into an infinite loop, that doesn't prevent other threads from running.

Is it possible to create a preemptive scheduler in which threads can hang a "do not disturb" sign on their door. If the sign is there, the scheduler doesn't perform a context switch. It would be a bit like a prehistoric version of Java's synchronized keyword.

I imagine this could be easier to program for because you can mark critical sections and always have them executed directly after each other. For example, if you're changing multiple microcontroller's configuration registers, it may be that halfway through this change the settings are not as you ever want them to be for a long time. You don't want a context switch to occur right in that moment.

Has something like this been done?

As for the implementation, it seems that setting and clearing a bit when entering or leaving the critical section would be enough. The scheduler checks this bit before performing a context switch, and doesn't act if it's 0. Would that indeed be enough?

A more advanced scheduler could keep track of how long a thread is in the critical section. If that's "too long", he may still perform the context switch, possibly notifying the thread first. This "too long" may be defined by the scheduler or the thread - I see advantages for both approaches.

Answer 1

There's a lot of variety of schedulers because there's a lot of variety of needs, from real-time systems where the whole system is written in one go and the precise order and timing of scheduling is known when the device is built, to high-end systems where all threading is preemptive except for some very short sections deep inside the kernel.

It certainly is possible for a thread to declare that it is in a critical section and it doesn't want to be interrupted. By definition, this isn't a fully preemptive scheduler anymore, but some kind of hybrid mode which is based on preemption but where preemption can be disabled.

In fact, virtually every system contains at least some low-level code that must not be preempted because it's doing something to the hardware, such as the example you give of modifying multiple registers that need to be done in one go. This isn't limited to microcontrollers. Interrupt handlers and context switching code almost always contain a critical section, even if it's just a few instructions. At the bare metal level, a critical section simply means disabling interrupts. Interrupt handlers start with interrupts disabled, or, if not, there is at least some mechanism that prevents the same interrupt from interrupting a previous instance of itself.

Operating systems designed for single-core hardware may use critical sections to implement message passing mechanisms, because passing a message usually involves modifying multiple data structures (associated with the sender and the recipient) in a consistent way. On multi-core systems, this can't be done because the sender and receiver may be running on different cores.

Going higher level, there are operating systems where threads can get a guarantee that they won't be interrupted, and the API offers system calls like start_critical_section/end_critical_section. This can only be done if the thread is trusted not to go into an infinite loop or otherwise hog the CPU. Such a critical section might in fact be interrupted by interrupts, but the scheduler returns to the same thread after the interrupt.

Critical sections that are interruptible after a timeout are possible. I don't know how common they are; they would make sense in “soft real-time” systems such as multimedia processing where threads need to process audio or video frames in a timely manner, and dropping a frame is frowned upon but not ruled out.

Informing a thread that it's been preempted is difficult to do usefully. Setting a bit in a well-known location is easy. The problem is how the thread can react. It's indicated that it didn't want to be interrupted, so it presumably isn't going to check that bit. A possible design is for the thread to have checkpoints; for example, in an outer loop during frame processing, a media processing thread can check if its current frame has been dropped. Another possible design is to kill the thread (but possibly leave its stack behind for analysis) and run another thread as an exception handler. Yet another design is to raise an exception inside the thread; this requires tight coupling between the scheduling mechanism and the thread's execution environment.

There are other ways to constrain the ways in which threads can be preempted at a high level. A simple one is priorities: a scheduler will only preempt a thread to run a higher-priority thread. If thread A doesn't want to be interrupted by thread B, A declares a higher priority than B.

In a multi-application system where each application can have multiple threads, it can make sense to have a hybrid scheduler that is preemptive between applications, but cooperative between threads of the same application. This way an application thread that never yields will only prevent only threads in the same application from running. Applications can use shared memory with context switches only at predictable times for its inner workings, while inter-application communication is done via OS messaging primitives only.

Answer 2

One example of a system that used to work this way is the Linux kernel, which used to have a pair of functions called cli() and sti(). On single processor systems, these simply disabled and reenabled interrupts, thus preventing the current thread being stopped (on multiprocessor machines they were a little more complex). They were deprecated early in development of the kernel and completely removed during the 2.5.x development versions of the kernel.