Philip K. Thomas received the B.S. degree in Physics from the California Polytechnic State University and is currently in the process of defending his Ph.D. dissertation in Computer Science at the George Washington University. Philip also serves as Director of System Architecture at PRC corporation in Mclean, Virginia and can be reached at philip@rsi.prc.com.
Shmuel Rotenstreich received the B.S. degree in Computer Science from the Tel Aviv University and the Ph.D. degree also in Computer Science from the University of California at San Diego. Shmuel is currently Professor of Engineering and Applied Sciences at the George Washington University and can be reached at shmuel@sparko.gwu.edu.
Introduction
On most computer systems, users interact with the system through command-language interpreters called shells. These shells accept user input and interpret them as commands for the system. There are three major UNIX shells: Bourne, C and Korn (kshell). Other shells include command.com for MS-DOS and for OS/2.The Korn Shell, which we consider here, offers sophisticated management of past commands (history). We have enhanced this functionality to include a learning automaton that predicts the next command. This command prediction often allows the user to avoid entering the command sequence in its entirety. In most of the computing environments we considered, this enhanced shell predicted the next command with a high degree of accuracy.
This article describes our shell enhancements and details some of the methods we used to implement them. Although the Korn Shell was our target shell, we have applied these same enhancements to the C Shell. We believe this article will show that our enhancements are applicable to other shells as well.
Attaining Command Cycle Consciousness
In our research we have found that most users exhibit cyclic behavior when interacting with an operating system. For example, to create and execute a program, users may produce the following:1. Command: Evoke editor — create the source file.
2. Command: Create executable — compile & link the source file.
3. Command: Execute the file created in (2) — examine the results.
The user typically repeats this sequence until he or she has completed and thoroughly debugged the program.
If a shell can recognize such cyclical behavior (we say it has cycle consciousness) it can predict the user's next command at any point in the sequence. We incorporate cycle consciousness into the shell by integrating it with the Predictor module outlined in the next section.
The Predictor Module
To incorporate cycle-based knowledge into various operating system facilities, we have developed an abstract data type module called a Predictor (Listing 1) . The Predictor is a learning automation representative of the learning-from-analogy class of learning strategies. In learning-from-analogy strategies, the learner reaches a conclusion about the current case by considering previously processed cases bearing strong similarities to the current case. For the predictor module, the previously processed cases are the sequences of commands already encountered from the command stream.The Predictor module incorporates an abstract component as well as several concrete components. The abstract component is the prediction algorithm, which we describe shortly. The concrete components consist of three major classes:
1. Control Class: The two instances of this class supply entry points for initializing and terminating the Predictor Module.
2. Input Class: This class obtains the next command from external modules.
3. Predict Class: This class makes predictions for the Predictor module. predictor can make two types of predictions:
1) The next command
2) When a particular command will next occur
By creating a predictor class, we encapsulate all cycle-dependent code and data, making it easier to modify. This method of encapsulation also permits the coexistence of multiple predictors. (Environments where multiple command streams exist require multiple predictors.) We describe the predictor class in detail later in this article.
The Algorithm
For this discussion we say that a command stream C is a sequence of N commands composed of M unique commands. These commands arrive at the predictor one at a time via the input interface. These commands determine the current state of the cycle (command stream).The predictor module maintains a weighted adjacency matrix A. A is an M x M matrix which represents a command stream C (this command stream dynamically increases in length as each subsequent command arrives), where the ijth element A[i,j] is 0 if command j never follows command i, or some positive integer indicating the number of times command j follows command i. (Some readers may recogonize this implementation as part of a semantic network.)
To predict the next command, the algorithm locates the corresponding row for the latest command n in the adjacency matrix A. The algorithm then selects command i such that command i is: MAX(A[n,i]) i=1,2..M (index of command i) and A[n,i] >1
If such a command exists, the algorithm returns command i as the best prediction of the next command to occur. If no such command exists, the algorithm returns indicating that the predictor module cannot predict the next command given its current state.
The algorithm performs the following steps to predict when a particular command will next occur:
1. Save the current state of the predictor module.
2. Set count=0.
3. Call the predict-the-next-command interface repeatedly until the return value command i is
a) Equal to the specified command b) A value indicating that the predictor cannot make a prediction c) A value previously returned by the predict-the-next-command interface (this implies that the predictor assumes the command stream will cycle without an occurrence of the specified command). For each time the predict-the-next-command interface is called, increment count.4. Restore the original state of the predictor module.5. Return count if step 3 terminated because of condition 3.a, otherwise return a value indicating that the predictor cannot predicting when the specified command will next occur.
The Predictor Class
The predictor class contains three publicly accessible functions to perform input and output:PutNextCommand — This function registers commands occurring on the system. We modified the main control loop of the kshell to call this function whenever the kshell assembled a command and registered it to provide "history" functionality. This function returns values corresponding to internal fatal errors and success.
GetNextCommand — This function passes the next predicted command to the system, if it can be predicted. We augmented the kshell source to recognize when the user types ESC-p (in emacs mode) at the prompt, and to call GetNextCommand. As a result, the kshell produces either a beep (to indicate the inability to predict the next command) or a command string adjacent to the prompt, which the user may execute by typing a carriage return.
WhenNextCommand — As its name implies, this function predicts when a particular command will occur. We do not use this function in the kshell. We have included it in the predictor module because it is invaluable in other systems that require this kind of prediction. (e.g. in a file caching system — when a file needs "flushing," information about when a file will next be used is advantageous.) This function returns zero to indicate that the command stream will cycle before it encounters the specified command. This function returns a value of less than zero to signal an internal error.
These last two functions maintain and manipulate the adjacency matrix mentioned previously.
Results
To show how well the predictor works, we have derived the following examples from a command stream in a programming environment. Figure 1 shows the first example. The first column shows the actual command stream. The second column, with the prefix p: shows the predicted command stream. The last two columns show the current percentile of successful predictions and the maximum percentile of successful predictions, respectively. The second example (Figure 2) differs from the first only by one command; we have removed this command, ls, from the stream in example 2. This command represents an "exception" to the cyclical nature of the command stream. Thus, example 2 shows the effect of filtering out exceptions.
Open Issues:
To keep this article consice several items have not been sufficiently developed. The following are a few points that we believe require further clarification.
How are command parameters handled?
Commands can be classified as either tightly coupled or loosely coupled with their parameters. The degree of coupling is context dependent. For instance, when the predictor is used in a file caching subsystem, predicting the sequence of parameters (e.g. file names) is more important than predicting the sequence of the commands themselves. We say the commands are loosely coupled. In the case of tightly coupled commands, we treat parameters and their commands as one predictor unit, that is, the predictor considers the same command with different parameters as distinct and dissimilar commands. (The predictor outlined in this article works this way.) In the loosely coupled scenario, we either parse the parameters out and use them as distinct predictor units, or, as is usually more beneficial, we still treat command-parameter sets as tightly coupled and treat them as single predictor units.
Are command cycles common?
Yes. When we remove a lot of the "noise" from command streams, we find that most of the commands are members of command cycles. The "noise," we have discovered, comes in many forms. Many commands streams are sprinkled with commands we isolate as "exceptions." These exceptions would be commands like ls, dir, who etc. Users tend to use commands like these with enough randomness that it is easy to filter these commands out of otherwise perfectly healthy command streams. Another form of noise is the partial cycle. The partial cycle is best illustrated using the example session. In the edit-compile-execute cycle mentioned above, evoking the compiler sometimes results in errors that require the user to re-visit the editor without completing the cycle. Partial cycles are much harder to deal with than exceptions and, consequently, our success rate with these tends to be lower.
GUI Environments
We have also begun investigations into incorporating cycle consciousness into graphical user interface (GUI) environments. The essential problem here is defining a command primitive. In a command-oriented interface a command primitve is well defined, but in a modern GUI a command primitive is more loosely defined and may incorporate several user actions, such as mouse moves and button clicks. User activity is hard to partition into distinct commands.
Conclusion
As is any article of this nature, we had to summarize a large body of work both theoretical and experimental to present here. The algorithm presented here is a first-degree learning automation. We have added several filters and general enhancements to this automation resulting in several different predictors that, depending on the situation, are selected and evoked at run time (late binding — virtual functions). Our work leveraged the predictor across several operating-system elements including memory management, schedulings and disk allocation. Overall, we think our assertions for incorporating cycle consciousness have been well founded. We have had favorable results in the areas we have studied.
References:
Peterson, James L.; Silberschatz, Abraham, Operating System Concepts, Addison-Wesley Publishing Co, 1985.Tanimoto, Steven L., The Elements of Artificial Intelligence, Computer Science Press, 1990.
Thomas, Philip K., Rotenstreich, Shmuel, "Command Cycles," Ph. D. Dissertation, George Washington University, 1993.
Sidebar: "Anatomy of a Command Shell"
Sidebar: "Patching the Korn Shell"