CS 736 - Spring 2007 - Paper Discussion

i like the notion of separating the policy that the determines how resources are used from the mechanism that facilitates the sharing and using of the resources. The Hydra paper explains how the mechanism for scheduling, paging, and process control [protection of a process from it's scheduler] are in implemented. As evident from the implemented kernel, Hydra was built on the notion of flexibly and the idea that users should be able to determine the policy which controls how their applications use the system's resource.

Users can only determine policy via user applications or a combination of user applications and parametrization of the kernel's resource. In order for user app to manage the policy the system must perform a context switch to the user app each time it needs policy advice. This context switch is extremely expensive and as a result parametrization was used to reduce the number of context switching. The context switching problem also restricted the level of separation that could be achieved in the design of the paging system.

In an attempt to provide control to the users many innovative ideas were dreamed up and implemented;
*PM, the idea that a user can decide the scheduling policy to by used by it's application; also the fact that the scheduling discipling of one process can vary over it's life time.
*ability for an application to explicitly state it's working set, allowing the system to efficiently decide which pages to take out of memory and how many pages a process needs to be given in order for it to run efficiently.
*parametrized of the paging system: a pm can decide the maximum amount of pages that a process can have in it's working set.

In order to gain flexibly, they system may have given up speed and simplicity. An example where simplicity is lost is in requiring applications to actively track and state their working sets. Speed on the other hand is lost whenever a process transitions out of the running state and it's PM needs to run to determine what should be done with the process. Another instance where speed is sacrificed is with the short term scheduler. By allow the different users to choose different discipling and providing a hard guarantee of processor time, global optimizations are lost – we could easily perceive low cpu utilization and perhaps even the caravan effect.

This paper is relevant because it shows what type of a system can arise when designers attempt to separate policy from mechanism – it also shows the extent to which this separation can be feasibly done. While this separation provides an interesting system it ultimately provides an inadequate multiprogramming system – multiprogramming arose as a way to efficiency use the resources of a system and to do this it might require that policy to determine how resources are used be implemented in the system.

I've neglected the section on protection. Section 4 basically states that the PM running a process isn't necessarily trust by the process; the would prefer to hide as much information from the PM and it would also like to know when the PM is actively giving it less resources or perform maliciously towards it. The kernel informs the process via an error if the PM acts maliciously.

SUMMARY

In "Policy/Mechanism Separation in Hydra" Levin et al. argue for the concept of "policy/mechanism separation" wherein the kernel provides only basic mechanisms, while policies are implemented in the user space. The authors argue that such approach will result in the most flexible systems. At the same time authors acknowledge that complete policy/mechanism separation is impractical and discuss trade-offs. The authors illustrate their ideas by considering how scheduling, paging and protection are implemented in Hydra operating system.

PROBLEM

Kernel design. What are the appropriate facilities for the kernel to provide? How much control should user-space be given? What restrictions should the kernel impose?

CONTRIBUTION

Maximizing policy/mechanism separation allows for the most flexible systems. However, total policy/mechanism separation is impractical because of required overhead and risk of deterioration of system stability and fairness (i.e. user-space software cannot be fully trusted, thus the kernel has to enforce some rules)

Discussion of parametrized policy as a mechanism. Since total separation is impractical a parametrized kernel policy that excludes a minimal number of "undesirable" userspace policies is a necessary compromise.

Description of Hydra's Kernel Multiprocessing System (KMPS), a parametrized scheduler. KMPS targets the following goals: allow user-space schedulers, allow multiple concurrent schedulers. Scheduling mechanism and parametrized policy are described. Policies required for enforce fairness are listed.

Paging mechanism and policies in Hydra OS are described. Compared to the scheduler, paging mechanisms and policies are more significantly affected by considerations of practicality that are linked to hardware capability. The authors attempt to abstract away some of that dependence by providing a more indirect interface to the user.

Protection mechanism and policies are discussed. Unlike in scheduling and paging, protection feature of Hydra exemplifies a much more defined separation of mechanism and policy because few restrictions are imposed.

FLAWS

Perhaps more abstract discussion of tradeoffs and sacrifices required for separating mechanisms and policies would be useful.

I personally would welcome a discussion of when a system becomes "too flexible". In my opinion consciously limiting features of a system is the most difficult and important design task. Those limitations in turn are very influential when attempting to decide on the right degree of separation between mechanism and policies. Often (examples below) I was not convinced that what the features the authors provided are that necessary. However, without knowing target applications I cannot be too confident about passing my judgments, since general-purpose computers that I am familiar with are very different from the machines the authors worked with.

Concurrent interacting schedulers is an interesting idea, but I feel that the authors sufficiently justified its necessity.

Requiring the user to manually manage programs above a certain size (which is determined by hardware capabilities), is in my opinion a clear failure of applying mechanism/policy separation. It is difficult to say from my position whether such approach is justified. The authors should have elaborated a bit more about how much performance can be gained and under which circumstances.

RELEVANCE

Separation on mechanism and policy is an issue important in design of virtually any software, though it is perhaps most pronounced in the kernel. Striking the right balance is difficult and important. Therefore the paper will be relevant for foreseeable future.

Summary
This paper provides an overview of the HYDRA kernel and explains the reasoning behind the decisions made in its creation. The kernel is designed to provide general mechanisms to sub-systems that implement system policies such as security and file access. The approach taken for process scheduling and protection is discussed in detail and illustrated by way of an example.

Problems addressed
The main objectives of this project were to 1) provide an environment where hardware resources would be utilized effectively and 2) create an environment that could host user-visible operating environments.

Contributions
An important idea that came out of this paper is that of the separation between mechanisms and policy which can facilitate the creation of a general purpose system. Though complete separation was not possible in Hydra for speed and fairness reasons its an ideal situation that is something most modern day operating systems aspire to. This paper also extends the idea of capabilities to include another layer of indirection to make access control more fine grained and easier to manage.

Flaw
There appears to be multiple levels of scheduling going on, at the lower level the KPMS is ultimately in charge of what is scheduled to run but then the separate PM modules work to determine which process within their control should be put on the ready list. This seems like it would incur more processing time to be switching between multiple scheduling processes rather then using a single global scheduler.

Relevance
Even though the HYDRA system was deemed a failure in the end I think the idea that was stressed in this paper of separating mechanisms and policy is one that is still very relevant in operating systems today and help to break the system down into smaller more manageable parts. Hardware designs also try to use this theory where the hardware provides primitive mechanisms that complex systems can be built on top of.

Summary:
This paper describes the parts of policy and mechanism that are in the kernel versus user space for process scheduling, paging, and protection.

Problem:
There is a desire to separate policy and mechanisms in order to make the Hydra kernel more flexible, but at the same time a complete separation would lead to way too much overhead in the form of context switches to the user space processes that implement policy.

Contribution:
1. Hydra almost feels like an early microkernel. It still could happen that true microkernels will become prevalent some day; if they do, then Hydra will have been way ahead of its time. In either case, it sounds like they were the first or one of the first to move what we think of as OS jobs like scheduling out of the kernel proper. In fairness, I'm not totally convinced as to how close Hydra is to a microkernel. I suspect that it would be quite heavyweight in comparison to something like Mach or L4. However, the idea of moving policy to user space smells like microkernel to me.

2. A discussion of the algorithms that they use, at least somewhat. For instance, the idea of having a fast scheduler make short term decisions about what to run but have a slower one make more intelligent decisions is an interesting idea. Sort of a two-level scheduler.

3. The discussions about how programs have to trust the process managers, but the trust doesn't have to be complete because of certain provisions in the kernel for returning early from syscalls is potentially interesting.

Flaws:
The authors try to downplay the influence of the PDP-11's architecture and how it prohibits demand paging, but I think it has a bigger effect on the system than they'd like to admit.

They implement the ability to support multiple PMs in the kernel, but I'm not convinced this is necessary. It might be possible to create a PM that holds capabilities to other PMs then multiplexes out to the secondary ones in the same way the kernel does in their system. This doubles the number of times a protection barrier is crossed, so it's possible that it would have insufficient performance. It's also possible that the kernel has information that such a PM would need to operate that it doesn't want to give out. But in any case, I would have liked a mention of why they didn't take that route.

Relevance:
The debate over microkernels is still going today about whether the performance tradeoffs of doing a complete separation between mechanism and policy is worth it. Microsoft seems to now be pushing for most kinds of drivers to be written in user space, so it seems like the balance might be starting to shift in favor of the microkernel. However, to what extent this will continue is unknown; will it stop soon with performance critical drivers like viedo remaining in the kernel, will it continue untill they are pushed out as well but traditional OS functions like scheduling remain, or will we reach the point of a commidity microkernel where you can implement the sorts of decisions that Hydra would allow?

Summary

In this paper, the authors present a very useful concept of separating the mechanisms from policies in a kernel. The authors discuss how to separate mechanisms from policy in three major components i.e. Scheduling, Paging, and Protection methodology of the kernel. The main idea that the authors are advocating is "to provide primitives, not solution".

Problem Description

Since each user-level policy program is required to execute in their own protection domain and that domain switching is quite costly, it is quite time consuming and impractical to invoke such programs each time a policy decision is required. In order to overcome this problem, the authors suggest the idea of policy/mechanism separation. Policies are encoded in user-level software while mechanisms are provided by the kernel to implement the policies.

Summary of Contributions

A few contributions of this paper are as follows.
1. The authors provide a relatively detailed model of the scheduling mechanism that they propose. KMPS is the portion of the kernel which provides mechanisms to support policies for scheduling user programs. Since, mechanisms to implement the scheduler are provided by the kernel, scheduler can run as a user level program and multiple schedulers can run at the same time. The authors also suggest using the concepts of priority, mask bits, time quantum etc. in a scheduler.
2. The authors also propose the idea of paging and how the kernel should provide mechanisms to manage the pages. In HYDRA, pages are treated as objects. The authors also seem to present the concept of memory hierarchy when they talk about RPS (relocation page set), CPS (current page set) and LNS (local name space). The authors also suggest a way to fairly allocate the number of pages to a process. Another contribution of this paper is that it also talks about the replacement policies that must be used to replace pages. The authors also suggest having hardware support for paging mechanisms provided by the kernel for performance optimizations.
3. The authors also propose concept of a "System Administrator". This concept was missing in the papers we read previously. Only the administrator is allowed to modify policy objects. This provides an improved protection scheme as compared to the previous papers.

Flaws

Some of the flaws in the paper are as follows.
1. The authors propose the idea of having multiple schedulers which they call PMs to run concurrently. All these PMs communicate with KMPS to implement their scheduling policy. This can result in performance degradation due to a lot of communication between PMs and KMPS.
2. The authors present the idea of Paging but they require the programmers to manage the page sets if the program size is larger than 32K words. This is an example where separating mechanisms and policy is not a good idea. The underlying memory subsystem should be transparent to the programmer as is suggested by the concept of "Virtual Memory". Based on how a programmer uses the mechanisms to manage the page sets, performance of his program can be severely affected. In this case it is better for the kernel to provide a page swapping policy instead of providing mechanisms to manage the page set.

Relevance

The idea of separating the mechanisms from policy suggested in this paper is still used in the modern operating systems. Based on experience, people have realized that it is better not to separate policy from mechanisms in some cases like virtual memory. Secondly, the scheduling mechanisms suggested in this paper like priority, masks, time quantum etc. are being used in the modern schedulers as well. Finally, the idea of paging proposed in this paper is also being used today.