Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism

Anderson, et. Al

Threads either built at user-level or kernel-level.

Advantages of kernel-threads:

• Order of magnitude better performance than using traditional processes.
• Each thread gets mapped to a physical processor while it is running.

Problems with kernel-threads:

• When a single thread in an application blocks, say due to an I/O operation, the entire application is blocked/context-switched out instead of running another runnable-thread in that application.
• Performance is an order of magnitude worse because thread operations (fork/join, wait/signal, etc.) require a switch into the kernel. Crossing this extra protection boundary needs to take place even to switch between two threads in the same process/address space.
• Scheduling policy is not as flexible as in user-level threads because the scheduling policy is implemented in the kernel—it is hard to change things that are “hardcoded” in the kernel. Modifying the kernel is hard. [Because the scheduling policy cannot be changed easily later on, an OS is likely to implement a policy that is “too sophisticated” for most applications (such as preemptive priority queuing), when all that may be required for most applications could be a simpler policy (such as FIFO queuing). ]

Advantages of user-level threads:

• Thread management operations require no kernel intervention, and as a result execute very efficiently.
• User-level thread scheduling policies can be customized or changed on a per application basis without requiring modification to the kernel.
• Misuse of the thread library only affects the mis-using application.

Problems with user-level (“green”) threads:

• User-level threads are not directly mapped to physical processors. A process that has many user-level threads running is only allocated one processor, and the threads share that processor.
• Operating system activity such as multiprogramming, I/O, and page faults “distort” ??? the equivalence between virtual and physical processors.

Current approaches to user-level thread problems in Mach and Topaz are avoided by implementing user-level threads on top of kernel threads. Of course, by doing so, the thread implementations inherit all of the problems that come along with kernel-level threads.

• User-level threads implemented on top of kernel-threads block, resume, are pre-empted, and are scheduled without notification to, and obliviously to the user-level thread state. (A user-level thread that is holding a lock could be obliviously de-scheduled by the kernel, thereby preventing some other thread that needs the lock from making progress.)

One bad idea to solve these problems is to have the application make calls to the kernel to state preferences about how to schedule its threads. This will result in bad performance due to the overhead of crossing into the kernel each time to make these calls. (Or, I guess it would really depend upon how often these calls would need to be made, but this still sounds like a bad idea.)

Scheduler Activations attempts to provide the best of both kernel and user-level threads, while avoiding the disadvantages of both.

• Each application is provided with a virtual multiprocessor.
• Each application has its own thread scheduler, and decides which threads should run on physical processors that it is assigned by the kernel.
• The kernel is told how many threads an application would like to run so it can try to allocate that many physical processors for it.
• The application needs is told when the kernel gives (and takes away) physical processors from it. This is done by having the kernel do an up-call to the application when such events need to take place.

• A scheduler activation is the kernel mechanism that makes an up-call to the application’s thread scheduler when events (processor allocations and deallocations) need to take place.

Explain this quote to me: “The application programmer sees no difference, except for performance, from programming directly with kernel threads.” Hmm… I thought one of the benefits is that the application programmer could provide his/her own thread scheduler, and that the application programmer would indeed need to specify how much parallelism (i.e, how many physical processor sthe application wants) in order to really gain all the advantages described for scheduler activations.

Scheduler Activation Upcalls

1) Add this processor

2) Processor has been preempted

3) Scheduler activation has blocked

4) Scheduler activation has unblocked

Application “downcalls”

1) Add more processors

2) This processor is idle

Implementation

Scheduler Activations implements on DEC SRC Firefly multiprocessor. FastThreads user-level thread library and Topaz kernel-level thread library modified to implement scheduler activations.

If a user-level thread is in a critical section (and holds locks) when in becomes blocked or preempted, the thread is continued temporarily until it exists the critical section. This technique prevents deadlock. (This is a deadlock recovery strategy. The authors considered a deadlock prevention strategy, but it was too expensive / would cause performance problems due to requiring the pinning down of pages while in a critical section, etc.)

Would be useful to compare/contrast this work with all of the “application-controlled virtual memory management” papers. Scheduler Activations is sort of like “application-controlled thread management.”

Miscellaneous Interesting Points

• Authors argue that user-level threads is only one type of concurrency model for applications, but that other application-level concurrency models would suffer from the same problems as user-level threads. Scheduler activations, of course, they claim would address these problems in these other application-level concurrency models as well. (I haven’t heard about any other “application-level concurrency models;” have you?)
• Time-slicing when you have more kernel threads than physical processors is a very bad idea in the presence of spin-locks. [Zahorjan]

So this is funny… in the Java community, “native” threads instead of “green” threads were welcomed (or perhaps marketed) as a big plus. I guess no one has brought up scheduler activations! J

I noted that there were a lot (>250) citations to this scheduler activations paper in citeseer. Has this become commercial yet?