/ Edward A. Billard / Assistant Professor
/ Alice Riedmiller / Research Associate
The Operating Systems Laboratory is participating in both top-down education and state-of-the-art research.
In education, the final phase of development of a workstation-based laboratory has been completed. The laboratory has a special layout for programmers to share 19 Sun-based workstations and 4 X terminals, connected to the laboratory file server via a network. In addition, a multi-media Macintosh has a scanner, video camera, video recorder, and television monitor.
An office for students has been built next to the laboratory for lab assistants, lab members, and visiting students. The lab assistants are exceptional students who help with lab software and exercises; the lab members are students who have made significant progress on their projects; and the visiting students are from other laboratories who are doing temporary work in the Operating Systems Lab. The students use the office to work on special projects for the laboratory and for general homework. Some of these students acted as teaching assistants for the Operating Systems course. They have been trained on special new software, developed in the lab, that demonstrates concurrent programming - an important aspect of the course.
In addition to concurrent programming, the laboratory has developed special simulation tools for students to learn the practical and theoretical aspects of queueing systems. The software is written in a new high-level script language (Tcl/Tk) that allows the rapid-prototyping of software, particularly educational software. The software has been used in the Performance Evaluation course and another tool has been used in the Database course.
Students in SCCP have been invited into the laboratory to test and examine the new software; it is apparent that students can quickly grasp the essentials of queueing networks, operating systems, databases, automata, sorting, and graph theory. The advanced students design their own queueing experiments and/or write their own graphical user interfaces.
Three seniors are doing their Graduation Research in the laboratory - the topic is Distributed Minimum-Weight Spanning Tree. This is much more difficult than a centralized version and involves the exchange of nine different message types.
The students are implementing the distributed algorithm in C and need to be concerned with message encoding and the requeueing of messages. In addition, each student is researching special areas including 1) Tcl/Tk to build a GUI for the MST, 2) networked messages, and 3) experiments on message complexity.
In research, two new refereed journal articles have been accepted for publication this year (and four previously accepted journal articles appeared this year). The members of the lab also had an interesting paper in ACM Software Engineering Notes on the use of Tcl/Tk for managing lightweight processes.
The major themes of the research are stability, adaptation, and group formation under the constraint of delayed information. The general goal of the research in the laboratory is to establish principles that improve the performance of highly distributed systems. The systems require adaptability, reliability, and expandability; the solutions are characterized by self-organizing and learning behaviors. The agents, or controllers, in the system make autonomous decisions and are expected to maintain reasonable performance, even as the system operates under aged or misleading information or evolves into unforeseen environments.
Some of the topics covered are the
and some of the specific topics on stability are the
Refereed Journal Papers
The Huberman-Hogg model of computational ecosystems is applied to resources with queues. The previous theoretical results indicate that instabilities, due to delayed information, can be controlled by adaptive mechanisms, particularly schemes which employ diverse past horizons. A stochastic learning automaton, with rewards based on queueing parameters, is implemented to test the theoretical results. The effects of the learning step size and horizon are shown for systems with various delays and traffic intensities. The instabilities are controlled with appropriate choices of parameters and reward mechanism. Long horizons permit non-adaptive agents to achieve similar results, with the possible loss of responsiveness to dynamic environments.
A controller selects the shortest queue for data entering a network, however, the state of the queues is subject to a delay $\tau$. A fluid-flow model approximates the packet arrivals, with analysis and simulation showing the inherent periodicity of peak loads. A formula for periodicity is derived for $r$ channels with utilization $\rho$ and is approximated by $\rho r\tau$ for a large number of channels.