\documentstyle[11pt]{article}


\setlength{\topmargin}{-2.0cm}
\setlength{\textheight}{22cm}
\setlength{\oddsidemargin}{1cm}
\setlength{\evensidemargin}{1cm}
\setlength{\textwidth}{15cm}

\renewcommand{\baselinestretch}{1.125}

\author{\small Chee H Chew, Ken Duda, Umesh Maheshwari, Hideo Segawa, Thomas Lee,
Derek White} 
\date{\small \today}
\title{\bf Research Areas in Operating Systems}


\begin{document}
\maketitle

\section{Overall System Structure}
 
\subsection{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 multi-processor systems, location independent
naming of objects, capability based protection, and fault tolerance.

\subsection{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.
 
\subsection{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].
 
\subsection{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.
 
\subsection{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.
 
\subsection{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.
 
\subsection{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).
 
\section{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.

% This also results in course-grain parallelism, which is important for MIMD
% machines.
% Chee: Feel free to reinstate this stmt.
%       I don't see how the granularity of paralleism is affected - umesh.
%
%       Seems to me the granularity of parallelism is determined by the 
%       structure of the parallel algorithm, not by the scheduling 
%	mechanism.. but if I'm confused put it back --- Ken

\section{Multiprocessor Support}

Research on multiprocessor architecture has been focused on achieving
two conflicting goals:
    \begin{itemize}
    \item Scalability to achieve high performance.
    \item Sharing of resources for ease of programing.
    \end{itemize}

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.


\subsection{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 {\em
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 {\em 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].

\subsection{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. 

%In scheduler activation, threads share a virtual address space, and a
%thread will give up the processor and return it to
%kernel when it waits for an I/O completion.

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].

\section{Fine-Grained Access-Control}

Future operating systems should provide fine-grained protection
for its objects on a per-principal per-operation basis.
Traditionally,  access-control information has been managed in two
different ways: {\em access control lists} (ACLs) and {\em 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 {\em
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 client-server system. 
Further, the owner server can {\em delegate} the distribution of
capabilities to other trusted servers. 

One drawback with capabilities is that it is difficult to 
{\em 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, {\em 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.


\section{Naming in A Distributed System}

\begingroup  % Hide all my crap

{
\catcode`\ =\active
\catcode`\^^M=\active
\gdef\beginverbatim{\begingroup%
\def\\{\char92}%
\catcode`\ =\active%
\catcode`\^^M=\active%
\catcode`\$=12%
\catcode`\&=12%
\catcode`\^=12%
\catcode`\#=12%
\def {\ }%
\def
{\hfil\break\noindent\strut}%
\tt}}
\let\endverbatim\endgroup
\catcode`\@=\active\def@{\beginverbatim\let@\endverbatim}

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 {\it container} objects;
their only purpose is to contain other objects, and the only
operations that most users perform on them are {\it list} and {\it
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 {\it substitute}
and {\it resolve.} Substitute, as mentioned above, turns a name with
variable references into a fully-qualified name.  Resolve converts a
name into an {\it object identifier}.  This identifier is enough
information for the process with the name to call methods of the
object.  A {\it 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 {\it 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 read-only 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, \hfil\break
@/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 {\it kill} method on \hfil\break
@/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 \hfil\break
@$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.

\endgroup

\section{Fault-Tolerant Computing}


\newpage
\section*{References}
{\small

\begin{description}

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

\item[Ber92] Brian Bershad et al.
{\em Midway: Shared Memory Parallel Programing with Entry Consistency for
Distributed Memory Multiprocessors.}
CMU-CS-91-170, September 1991.

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

\item[Cha92] J. S. Chase, H. M. Levy, E. D. Lazowska, and M.
Baker-Harvey.  Lightweight
shared objects in a 64-bit operating system.  {\em Proceedings of the Conference on
Object-Oriented Programming Systems, Languages, and Applications,} October 1992.
 
\item[Gha89] Gharachorloo et al. 
Memory Consistency and Event Ordering in Scalable Shared Memory
Multiprocessor.
{\em Proceedings of the 16th Annual Symposium on Computer Architecture,}
May 1989.

\item[Kol92] E. J. Koldinger, J. S. Chase, and S. J. Eggers. {\em Architectural Support for
Single Address Space Operating Systems.}  In ASPLOS, pages 175-186, October
1992.
 
\item[Kub92] John Kubiatowicz et al.
Closing the Window of Vulnerability in Multiphase Memory Transactions. 
{\em ASPLOS V,} October 1992.

\item[MT86] S. J. Mullender, and A. S. Tanenbaum. 
The Design of a Capability-Based Distributed Operating System.
{\em The Computer Journal,} 29(4), 1986.

\item[Pat93] David Patterson. 
Massive Parallelism and Massive Storage. 
{\em Second International Conference on Parallel and Distributed Information
Systems,} 1993. 

\item[LaR91] LaRowe et al.
The robustness of NUMA Memory Management.
{\em Operating Systems Review,} Vol.25, No.5, October 1991. 

\item[RSC92] J. Richardson, P. Schwartz, and L-F Cabrera.
CACL: Efficient Fine-Grained Protection for Objects.
{\em OOPSLA'92,} pp 263--275, 1992.

\item[Zor92] Glen Zorpette. 
The power of parallelism.
{\em IEEE Spectrum,} September, 1992.


\end{description}

}



\end{document}