Research Areas in Operating Systems

Chee H Chew, Ken Duda, Umesh Maheshwari, Hideo Segawa, Thomas Lee, Derek White

May 2, 1993

1 Overall System Structure

1.1 Introduction

We believe that that there are several important directions in operating systems and distributed systems over the next several years. Future research will involve improving micro-kernel based operating systems, support for scalable and sharing problems in multiprocessor systems, location independent naming of objects, capability based protection, and fault tolerance.

1.2 Overall System Structure

There will be ongoing research into operating systems that take advantage of 64 bit addressing. 64 bit addressing can provide a single virtual address space that allows efficient message passing, data persistence and sharing over local area networks. A single virtual address space separates the concepts of address translation and memory protection.

1.3 Protection

Processes gain access to segments of virtual memory by requesting the kernel to “attach” a segment to the process. The kernel may allow or deny access to the segment based on higher-level access control list or capability based techniques. Access to unattached segments can be detected at a very low level as shown in [Kol92].

1.4 Persistence

Data persistence can be implemented by simply paging segments of virtual memory to disk. When the data is accessed again, it will be paged to the same virtual address, so saving or restoring a complex network of data does not involve modifying pointers.

1.5 Distribution

Data can be distributed across nodes on the network by dynamically partitioning the virtual address space among the nodes. The operating system may move the physical location of pages by sending the data across the network and changing the virtual-to-physical address translations of the pages. The management of the address space over the network is a variant of the distributed naming problem that all distributed systems must handle.

1.6 Data sharing

Two processes can communicate by requesting a segment of shared virtual memory from the OS. Since virtual addresses are constant among the processes, pointers are meaningful unique identifiers for objects. Complex networks of objects can be passed through the shared memory without “flattening” pointers or doing other address translation. A server may return a pointer to a client that the client can’t dereference, but the client may use that pointer is subsequent remote procedure calls (RPC). RPC can be enhanced by these techniques and by more direct transfer of control: A server can export the virtual addresses of certain entry points to clients, and the clients can call the server routines through a kernel routine, as described in [Cha92]. A single virtual address space allows the efficient LRPC scheme of [Ber90] to be implemented without pointer translation, and allows for complex data structures to be passed between processes. Furthermore, it allows the same technique to be used transparently across machine boundaries.

1.7 Summary

A large single address space allows an operating system to provide efficient message passing on a machine, which can enable truly mirco-kernel based operating systems. It also allows RPC with the same semantics as LRPC, which promotes the construction of distributed systems. Further research needs to be done in the areas of managing the virtual address space, and maintaining consistent distributed and persistent data. Techniques also need to be developed to integrate data that comes from persistent storage or networks that are not managed by the system (getting the latest copy of Microsoft Word 23.5, or some hyper-mail document from Japan for instance).

2 Process Management

Although a lot has been done to reduce the cost of a context switch, we can achieve similar effect by simply switching less frequently. Multiprocessor MIMD machines has made this a viable option because the need to preempt running threads diminishes with more processors at hand. In the APRIL project [??], context switches occur on cache misses and network requests, instead of clock-interrupts.

Another simple idea is to not schedule new threads on different processors blindfoldedly. When a new thread is spawned, it should actually be scheduled on the same processor as the parent thread. Surrounding processors will, when they are idle, look around for threads to take from other processors. This exploits the locality between related threads — such as the parent and child threads — by running them on the same processor unless another processor is idle. It allows a multithreaded program the kind of resource-sharing normally enjoyed by monolithic serial programs.

3 Multiprocessor Support

Research on multiprocessor architecture has been focused on achieving two conflicting goals:

• Scalability to achieve high performance.

• Sharing of resources for ease of programing.

Shared memory machines are generally recognized as being convenient to program because hardware provides processors with a consistent view of global memory. Unfortunately, providing this consistency limits their scalability. The current research is on providing logically shared memory built from physically distributed memory.

3.1 Scalability

The establishment of a parallel programing style has brought change in parallel computer architecture. Hardware is now designed to avoid unnecessary efforts to keep consistent view from every processor. The release consistency model proposed in DASH [Gha89] reduced the hardware overhead to provide consistent view compared with Sequent’s snoop cache model. It ensures that all previous shared data updates are consistent before a release of a synchronization variable is observed by any processor, where an explicit synchronization operation is assumed.

A new, less strict consistency model called entry consistency has been proposed [Ber92]. In an entry consistent system, a processor’s view of memory becomes consistent only when it enters a critical section. When an acquire for a synchronization variable is pending, a thread will be switched to another. That is, entry consistency model requires that synchronization accesses be thread consistent; a thread’s acquire and release accesses must be performed in the order that they were issued by the thread. In contrast, release consistency requires that synchronization accesses be processor consistent.

Midway supports this new model which runs from a network of workstations connected by Ethernet, distributed memory system to real bus connected shared memory system.

For further efficient remote memory access, multiphase memory operations has been investigated. To avoid thrashing where data can be invalidated before it is used, transaction buffers which keep track of memory requests are proposed [Kub92].

3.2 Sharing

For concurrent programming it is difficult to surpass the idea of scheduler activation [And92] because it achieves the high-performance of user-thread switching, and removes the hanging-up problem during I/O wait.

Sharing of a virtual address space by massively parallel processors is one of the intersting features. There is an effort for such machines — which have been based on message-passing in the past — to support single address space like KSR1 from Kendall Square Research [Zor92]. KSR1’s memory is physically distributed but is managed by a special main memory controller like pieces of a single large virtual memory. When a processor needs the data at a certain address, the processor’s local memory is searched first; if the address is not there, other memories are searched. The hardware oriented consistency mechanism may cause serious performance drawback for certain applications [Pat93].

On the other hand, operating system-level NUMA (Non-Uniform Memory Access) memory management is also an active research area and the effectiveness of various page placement policies was tested in [LaR91].

4 Fine-Grained Access-Control

Future operating systems should provide fine-grained protection for its objects on a perprincipal per-operation basis. Traditionally, access-control information has been managed in two different ways: access control lists (ACLs) and capabilities.

In the ACL scheme, each object stores a list of principals together with the operations they can invoke on that object. Typically, the principal owning the object has the right to modify the ACL. The Unix file system uses a coarse form of ACLs.

Capabilities, on the other hand, put access-control information with the principals. A capability is a ticket that allows the principal carrying it to invoke certain operations on the indicated object. Principals cannot forge capabilities or enhance those given to them. To this end, the capabilities can be protected by the OS while giving only indirect access to the application (as with file descriptors in Unix). Alternatively, an encrypted checksum can be added to each capability so that tampering it makes it void, as in the Amoeba system [MT86]. Sometimes, it may be desirable to disallow a capability from being replicated between principals. This is achieved by encoding the principal’s identity within the capability when it is created; the principal is authenticated when the capability is later used.

In scalable distributed systems with a large number of principals, the use of ACLs may create a bottleneck at the servers: each access must be validated by searching in a long list. Capabilities appear to be better suited for scalability and distribution. Validating the given capability is a constant-time operation independent of the number of principals. Also, the storage overhead per object is small. Admittedly, the principals must now store capabilities for various objects, but this results in a better distribution of space in a clientserver system. Further, the owner server can delegate the distribution of capabilities to other trusted servers.

One drawback with capabilities is that it is difficult to selectively revoke them from a subset of the principals. ACLs allow a tight centralized control over the object since an ACL can be modified without contacting the principals. A recent project, CACL [RSC92], provides the semantics of ACLs while employing a capability-like implementation for fast access. However, it is optimized for object-based languages or databases rather than operating systems.

5 Naming in A Distributed System

Recent development in naming in distributed systems makes it clear that names should transcend machine boundaries, and that files are not the only thing that we want to name. Sprite introduces a machine-independent naming scheme, but only for files. Windows NT introduces a heirarchical structure that includes many kinds of “objects”, but they are limited to being of classes predefined by the NT “micro”-kernel, and names are only meaningful on a given machine. Apollo’s Network Computing Architecture [Din] does not bother with the naming of objects at all, but rather pushes the responsibility of converting names to object ID’s onto each object class.

The operating system of the future will have a namespace organized in a heirarchy. Like Sprite, a fully-qualified name will have a meaning independent of the machine interpreting the name. However, names will be allowed to contain enviornment variable references whose meaning is host- (in fact process-) specific (such names are not fully-qualified; performing the variable substitution results in a fully-qualified name). This way it is possible to deal with things such as different binary types, multiple sources of system software, or the desire to store a temporary file on a local disk. For example, the object name

/edu/mit/athena/local/$localhost/fs/tmp/foo would name a temporary file on the
current host, and the object name /edu/mit/lcs/system/$cluster/$hosttype/bin/ls

might name the ls program. I could access a file stored locally on a nearby host with the

pathname /edu/mit/athena/local/w20-575-13/fs/tmp/bar.

Administration of a global namespace would be accomplished as follows. The first several levels of the heirarchy indicate the name of the administrative domain in which the object exists, as in the OSI Directory service. Objects must live in exactly one administrative domain. The objects at this high level are container objects; their only purpose is to contain other objects, and the only operations that most users perform on them are list and search. These top-level objects are read-only, and can thus be highly replicated and cheaply cached. This mechanism distributes the task of administration in the same way that the Internet host namespace does.

The fundamental operations performed on a name are substitute and resolve. Substitute, as mentioned above, turns a name with variable references into a fully-qualified name. Resolve converts a name into an object identifier. This identifier is enough information for the process with the name to call methods of the object. A name-resolution server will run on each node for this purpose, much in the way a named process runs on every host using Internet name service. The name-resolution server keeps track of where objects are located, and also keeps track of which objects exist on the current machine. However, it is the responsibility of a container object to be able to locate its children. Specifically, if a container object receives a search request for a name it contains, it must be able to provide that name’s object identifier.

For example, consider a distributed file system. The object /edu/mit/athena is a replicated, read-only container object with an entry home, which is itself a replicated readonly object with an entry for each username. Each workstation at MIT is permanently configured with the locations of the /edu/mit/athena object (this is how Internet DNS works). Now say I access a file in my home directory,

/edu/mit/athena/user/kkkken/sounds/burp. This is the first file access I make on this

workstation, so its local name-resolution server asks one of the /edu/mit/athena replicants where to find home; an object identifier is returned. It then asks this object for kkkken, and so on down the chain, much like NFS.

Things other than files can be stored in this system. For example, to kill a process on my machine, I could call the kill method on

/edu/mit/athena/local/m16-034-11/proc/kkkken/134, perhaps. Of course, variables

could be set up so I would merely need to type

$domain/local/$host/proc/$user/134 or even $myprocs/134. One nice thing about the

system is that if I accidentally left a process running on another machine, I could easly find it and kill it without remotely logging in. I would expect all user-visible operating system data structures to be accessible via object names, including machine performance statistics, access to local daemons, and objects such as semaphores, message queues, and named pipes.

6 Fault-Tolerant Computing References

And92 T. E. Anderson, et al. Schedular Activations: Effective Kernel Support for the User-Level Management of Parallelism. ACM Transactions on Computer Systems, 9(1), Feb 1992.

Ber92 Brian Bershad et al. Midway: Shared Memory Parallel Programing with Entry Consistency for Distributed Memory Multiprocessors. CMU-CS-91-170, September 1991.

Ber90 B.N Bershard, T.E. Anderson, E. D. Lazowska, and H. M. Levy. Lightweight remote procedure call. ACM Transactions on Computer Systems, 8,1 pages 37-55, February 1990.

Cha92 J. S. Chase, H. M. Levy, E. D. Lazowska, and M. Baker-Harvey. Lightweight shared objects in a 64-bit operating system. Proceedings of the Conference on Object-Oriented Programming Systems, Languages, and Applications, October 1992.

Gha89 Gharachorloo et al. Memory Consistency and Event Ordering in Scalable Shared Memory Multiprocessor. Proceedings of the 16th Annual Symposium on Computer Architecture, May 1989.

Kol92 E. J. Koldinger, J. S. Chase, and S. J. Eggers. Architectural Support for Single Address Space Operating Systems. In ASPLOS, pages 175-186, October 1992.

Kub92 John Kubiatowicz et al. Closing the Window of Vulnerability in Multiphase Memory Transactions. ASPLOS V, October 1992.

MT86 S. J. Mullender, and A. S. Tanenbaum. The Design of a Capability-Based Distributed Operating System. The Computer Journal, 29(4), 1986.

Pat93 David Patterson. Massive Parallelism and Massive Storage. Second International Conference on Parallel and Distributed Information Systems, 1993.

LaR91 LaRowe et al. The robustness of NUMA Memory Management. Operating Systems Review, Vol.25, No.5, October 1991.

RSC92 J. Richardson, P. Schwartz, and L-F Cabrera. CACL: Efficient Fine-Grained Protection for Objects. OOPSLA’92, pp 263–275, 1992.

Zor92 Glen Zorpette. The power of parallelism. IEEE Spectrum, September, 1992.