MigratingThreads
Migrating threads implementation. Threads start living in kernel and make excursions to user tasks and above. Mach style - thread/activation duality with similar semantics to Mach's.
Separation between "kernel" and "glue code".
Tasks make "bindings" which declares which interfaces and calls they can perform. Security checks are performed when binding. Token revocation can happen during runtime as well at interface granularity level (?).
atomic-osdi99:
scheduler activations [2]
Quicksilver [17] and Nonstop [3] are transactional operating systems; in both of these systems, the kernel provides primitives for maintaining transactional semantics in a distributed system. In this way, transactional semantics are provided for high-level services such as file operations even though the basic kernel operations on which they are built may not be.
Atomic "stateless" IPC - no continuations. Purely atomic kernel API [Fluke, atomic-osdi99].
both process- and interrupt-models are possible for testing thanks to fluke architecture. (process-model improves preemptibility, interrupt-model improves memory usage)
process-fully-preemptible model is good for low-latency desktop. interrupt-partially-preemptible shall be fine for embedded/memory constrained devices and appliances.
For example, Mach’s average per-thread kernel memory overhead was reduced by 85% when the kernel was changed to use a partial interrupt model [10, 11].
[passive.pdf]
Passive objects - entities which do not have their own threads and client threads migrate to these objects to do useful work. (@sa thread-migrate)
A passive object model provides enhanced performance and simplicity because it is more closely matched to the basic nature of microprocessors and the requirements of applications. It also provides more functionality by making the flow of control between objects a first-class abstraction which can be examined, manipulated, and used to carry information about the operation in progress.
Presented benefits:
- Passive objects more naturally support synchronous object invocation, which is the common case.
- Passive objects more closely model the nature of the underlying hardware.
- The implementation of inter-object control transfer is simpler and faster with passive objects.
- The explicit nature of inter-object control transfer makes more optimized implementations possible.
- Passive objects can be smaller and more lightweight, because they involve less storage overhead.
- Passive objects more accurately model the requirements of real-time systems.
- Passive objects make accurate resource accounting easier.
- Interruption of operations in progress is more easily implemented with passive objects.
- Passive objects are easier to implement and manage in user code.
- In a passive model, it is easier for personality servers to control the execution environment of their subjects.
Q: "A passive model provides less protection, because clients must trust servers with their threads."
A: Migration of a thread to a server object does not necessarily grant the server any rights other than the right to temporarily execute in its scheduling context. With proper design, even this right can be revoked or transferred back into the client object in a way that fully maintains the protection of both the server and the client. Our work on supporting migrating threads on Mach [7] demonstrates how this can be done.
Q: "It is more difficult to program in a passive model, because all objects must handle internal synchronization issues." A: It is true that in an active object model, a simple object can be created requiring no internal synchronization by creating just one thread in the object. However, in a full microkernel implementation of passive objects, it often turns out to be extremely easy to achieve the same effect, such as by creating only one "activation record" on which incoming threads can run, or by maintaining a global lock acquired and released automatically on entry and exit from the object.
[7] Bryan Ford and Jay Lepreau. Evolving Mach 3.0 to use migrating threads. Technical Report UUCS-93-022, University of Utah, August 1993. A portion of this paper will appear in Proc. of the Winter 1994 USENIX Conference. [thread-migrate.pdf]
[1] Brian N. Bershad, Thomas E. Anderson, Edward D. Lazowska, and Henry M. Levy. Lightweight remote procedure call. ACM Transactions on Computer Systems, 8(1):37-55, February 1990. (contains general-purpose migrating threads model) [lrpc.pdf]
[thread-migrate.pdf]
The key element of our design is decoupling of the thread abstraction into the execution context and the schedulable thread of control, consisting of a chain of contexts. A key element of our implementation is that threads are now "based" in the kernel, and temporarily make excursions into tasks via upcalls.
- Thread - a sequential flow of control.
- Single process - single kernel-provided thread (traditional Unix).
- Single task - multiple kernel-provided threads (Mach).
- User threads - provided by user-level libraries on top of kernel threads, by manipulation of PC and stack from user-space.
In many systems, a thread includes much more than the flow of control. In Mach, a thread also:
- is a schedulable entity, with priority and scheduling policy attributes.
- contains resource accounting statistics (e.g. accumulated CPU time).
- contains execution context of a computation - state of registers, PC, SP, references to containing task and designated exception handler.
- provides the point of thread control, visible to user programs through a thread control port.
During migrating threads RPC:
- only partial context switch (PD and subset of registers, like stack pointer),
- scheduler is never involved.
- there's no server thread state (registers, stack) to restore at all.
Note that binding in this model can be very similar to that in thread switching (static) model [Section 6.2] <-#DFN
Changes to Mach model:
Thread decoupled into:
- logical flow of control, represented by stack of activations in tasks; (per-space UTCB)
- schedulable entity, with priority and resource accounting. (in-kernel KTCB)
Activation represents:
- execution context of a computation, including a task whose code it is executing, its exception handler, PC, registers and SP
- user-visible point of control.
Activation is now exported to user-code as "thread". This is necessary to provide controllability and protection at the same time. "Thread" migrates between tasks and enters and leaves the kernel. "Activation", a user-mode part, remains permanently fixed to a particular task. Arbitrary control is permitted only on a specific activation, but not the thread as a whole.
Clouds [16]
"Scheduler activations"[1] - kernel threads with special support for user-level scheduling (primarily concerned with behavior of kernel threads within a PD, orthogonal to this paper). Theoretically could be combined in the same system.
In an object-based environment, invocation of relatively fine-grained objects is prohibitively inefficient if all objects must be active.
A distinction should be made between the "kernel" and the "glue code". The kernel is conceptually a PD much like a user-level task, in which threads can execute, wait, migrate in and out, and so on; its primary distinction is that it is specially privileged and provides basic system control services. Glue code is the low-level, highly system-dependent code that enacts the transitions between all protection domains, both user and kernel. This distinction between kernel and glue code is often overlooked because both types of code usually execute in supervisor mode and are often linked together in a single binary image. However, this does not necessarily have to be the case; in QNX the 7K nucleus consists of essentially nothing but glue code, while the "kernel proper" is placed in a specially privileged but otherwise ordinary process. In the presence of migrating threads the distinction between them becomes extremely important.
Termination mechanism used (splicing up activations at the point of termination and letting the upper half continue work, while the original thread returns to the previous activation) required careful planning of kernel data structures and locking mechanisms, in particular, the line between the kernel and glue code had to be defined precisely. Once worked out, this technique not only added additional controllability, but considerably simplified the implementation of control mechanisms in the kernel.
temporary mapping [23]
thread migrations to other nodes researched in depth in Alpha [11]
[11] Raymond K. Clark, E. Douglas Jensen, and Franklin D. Reynolds. An architectural overview of the Alpha real-time distributed kernel. In Proc. of the USENIX Workshop on Micro-kernels and Other Kernel Architectures, pages 127-146, Seattle, WA, April 1992. [AlphaRtDistributedKernel.pdf]
- protothreads
- above kernel threads a userspace scheduling system like Grand Central Dispatch/Dryad can be used.