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

Discussion

• The graphs in the paper could show confidence intervals, to alleviate suspicions about the data. Some "interesting" things are done to simulate page faults and I/O; it is not certain whether this might have any unintended effects on the performance results.
• Linux maintainers rejected scheduler activations.
• The cost of context switches have gone down since 1992.
• In fact, a simple question that someone asked was why was kernel threads so expensive? Other than the address space switch and possibily TLB flush, there doesn't seem to be any particularly good reason for this. Recent work has been made to reduce the traditionally expensive overhead associated with kernel threads, in a yet to be published paper.
• If applications honestly and accurately report usage, can the OS safely use this information to better schedule workloads? Will the overhead from the reporting be made back up by performance enhancements from better scheduling?
• Discussion on user threads: generally tricky exercise with a few lines of code. Using signals, it is possible to have preemptive user threads implementation.
• Schedulers: generally consumer OSes uses some heuristics for scheduling; typically workloads are either one of: interactive and responsive, or long running computations intensive; it is hard to classify workloads.

Questions

Michael DiBernardo

1. While context switches are fast in this model, will this performance increase always outweigh the overhead required to have communication between the OS and thread library schedulers?
2. From a software engineering perspective, does it not seem fundamentally flawed to replicate scheduling logic in both the user-level threading library that is already present in OS?
3. Is the assignation of virtual processors too coarse a mechanism for load balancing?

Haoran Song

1. I am curious on the description from page 61 that the creation of every new threads and notification from the kernel may cause the kernel to create an additional scheduler activation. Is this very costly to the kernel? and when multiple threads that sharing the same address space, is it possible to let them execute in the the context of an activation?
2. In the Solaris system, LWP (lightweight process) is provided as an interface between kernel threads and user-level threads. Comparing LWP with scheduler Activations, what is the similarities and differences?

Mirna Limic

1. We know for fact that user-level scheduler threads run user-level threads inside of their address space on the processors allocated to that address space by the kernel. The authors haven't discussed: What happens to the performance of the overall system, when there are a number of theads with high priority that require a lot of CPU activity, on all CPUs? Would this create stalls in non-user-level threads?
2. The number of address spaces has to be balaced to the number of available pages in memory so that there is a "reasonable" number of page faults. How would they manage a situation of needing to create many high priority address spaces while preserving space for the low priority address spaces?
3. They use a LIFO order of the ready list in any address space in order to improve cache locality. Could this cause starvation?
4. They don't discuss the impact of the number of scheduler activations and kernel-scheduler-thred communications on the system performace. Would you say that it is negligeable in all cases? Could there be a situation where this number of up and down-calls could slow up the system?
5. They say that one way to fix a problem of address spaces not wanting to give up free processors would be for the kernel to penalize them. They say that SRTF (Shortest Remaining Time First) scheduling algorithm could be used. But here the problem is in that all of the data regarding the threads (e.g. the remaining running time, their position in the queue, ...) is kept within the user-level thread scheduler, so in effect the kernel does not have any information it could use to penalize the address spaces using any scheduling algorithm. What do you think could be a solution?

Kevin Loken

1. The issue of preempting a user-level thread while it is in a critical section is dealt with through recovery rather than prevention. (Section 3, page 14-15). Does the proposed technique really avoid the issue that was raised for not using prevention -- violating semantics of address space priority. How does 'temporarily' continuing using a context switch differ from holding off the preemption?
2. The paper makes a significant point out of the fact that the kernel merely signals the user-level scheduler so that the application "knows" how many processors it has, which threads are running on those processors, and so forth. It isn't clear to me whether this scheduler is something that is application specific (i.e. having to be written in to each application), or is part of some sort of system library that provides a standard implementation.

Aiman Erbad

1. What is the role of the two stacks in the scheduler activation?
2. What is the main difference between upcalls and interrupts?

Ivan Sham

1. The Scheduler Activations combines features of user and kernel level threads. This ends up having a a structure of n user level threads mapping to m virtual processor. How is this approach different from using a thread pool?
2. Are there any commerical applications of the scheduler activations? Other then an implementation in NetBSD, I was not able to find any other usages of scheduler activations. What could've caused this lack of application other than the complicated communications between the kernel and user level threads. What are other alternatives that have be adobted?

Sam Davis

1. Couldn't the use of hysteresis (page 68) in the user-level threads package be seen as cheating? The effect is that an application holds on to a processor it is not using, possibly while another application is waiting for a processor. It might improve overall system performance, but so might the "cheating" described in Paper #1, where a thread avoids acquiring a lock if it can. After all, that also avoids an "extra" context switch. To what extent can "cheating" be justified by the argument that it could improve the performance of the whole system?
2. The paper makes a strong argument for user-level management of concurrency with better communication with the OS kernel. In the 14 years since it was written, has the idea taken off at all?

Wilson Fung

1. Is Scheduler Activation, seemingly superior to both user-level thread and kernel-level thread, used in the commercial operating systems (Linux, Unix, Windows... etc.) nowadays? If not, why?
2. To enhance the performance of Scheduler Activation with critical sections, an exact copy of every low-level critical section is made. While this allows the user-level thread to exit the critical section before preemption, how does this guarentee correctness for systems with more than one processor?

Lloyd Markle

1. What are the disadvantages of this approach apart from the complexity of the implementation?
2. Can you explain more about why upcalls are cheaper than talking to the kernel the normal way. Aren't we still crossing the same boundaries and aren't we kind of breaking the layered approach to operating systems?

Seonah Lee

1. What are the advantages of kernel threads? The paper addresses the problems of kernel threads in the Section 2 but does not explain the necessity of kernel threads.
2. How many do current operating systems adopt this Scheduler Activations mechanism? How about Windows XP and Linux? (The Scheduler Activations that the paper suggests seems to be an effective way to manage threads on multi-programmed multi-processors, so I am asking).

Jean-Sébastien Légaré

1. Where do scheduler activations fit in modern threading implementations (e.g. pthreads) ? Are modern threading implementations still using predefined entry points in user space to be notified of kernel scheduling decisions ?
2. As an improvement to the scheduler activations design, the implementation allows temporary continuation of critical sections so that a user space thread inside a critical section (the critical sections are defined at compilation) can relinquish the processor only once it reaches a "safe" place. What happens if a thread needs to be preempted while it's in a critical section that does not end (due to a bug for instance)?

Ali Bakhoda

1. The paper has claimed that user-level threads built on top of traditional processes can exhibit incorrect behaviour(P.54) Can you give an example of this faulty behaviour?
2. The paper says that in the approach only those subset of user-level thread operations that might affect processor allocation decisions are reported to the kernel by user-level threads. What are these operations?

Billy Cheung

1. Do you happen to know if they ever did a follow- up on the fine-tuning of thier upcall system? The entire "we expect that...performance would be commensurate with Topaz" did not sound all that convincing.
2. This is slightly off-topic, but regarding the topic of cheating by getting assigned more processors, is it not entirely possible for a program to constantly appear to be 'almost done' and thus always get a higher priority? Does the kernel also keep track of overall process time assigned to a particular address space and throttle things accordingly to retain some resemblance of fairness?

Gary Huang

1. Why is difficult to implement user-level threads that have the same level of integration with system services as is available with kernel threads?
2. From Figure 2 Speedup of N-Body application versus number of processors, why is the performance of orig FastThrds and new FastThrds very closed?

Nguyet Nguyen

1. What is the idea behind the concept of virtual multiprrocessor that is provided for each application address space?
2. Why do user-level threads suffer from poor system integration because of inadequate kernel support?

M. Argun Alparslan

1. Referring to the example in figure 1; when the priorities of the threads are also considered it`s stated that the user level will tell the kernel which processor should be preempted for upcall. How will the user level be aware of the I/O completion(and ask kernel to preempt specific processor) before the kernel makes an upcall?
2. How well are the scheduler activations supported in the current operating systems, as well as parallel and uniprocessor architectures? Are they implemented in different systems(other than Topaz) and with different thread packages(i.e. Other than FastThreads)?

Dutch Meyer

1. Could rapidly changing information at the kernel or user levels increase the performance overhead of passing information between kernel and user mode?
2. To what degree does this system open itself up to gaming by a user mode process?
3. I'd be curious to learn what the impact on memory footprint is. Keeping copies of every critical section in memory could be expensive.

Henry Wong

1. How would the system deal with the (common) case where there are no ready threads? If the idle loop is in the user-level thread system, how would the HLT (x86) instruction be used, and would dynamic frequency-voltage scaling work? (At least in the x86, both are privileged)
2. What effect does a buggy (or malicious) user-level thread manager do to performance? e.g. not returning from upcalls, or p67: continuing a thread which has a lock, but said thread doesn't release the lock in a timely fashion (or even never)? Am I correct in thinking that a malfunctioning upcall can be pre-empted?

Erica (Jun) Zhang

1. If the schedule activation is blocked for some reasons, e.g. page fault, then what will happen ? Will another schedule activation be allocated to do responding job or just wait until unblocked ?
2. In this paper, if a thread creates more user threads and request additional processors, then kernel will create an additional scheduler activation for each processor.. Is it right ? If yes, then why this paper does not use one scheduler activation to inform user-level scheduler about events of all those processors information?

Anoop Karollil

1. Won't user space threads running on a process be faster than when running on kernel threads (kernel threads having acessing and generality costs)? Its said that they are equal on page 55 line 5 - how?
2. When using scheduler activation method, the processor context of an executing user-level thread is stored in the kernel. Won't that be a problem when dealing with a whole lot of threads?