header image

CS471 Final Project Report

Project Completion Date: May 1, 2002

Report Contents

 

Introduction

Team Members

Customer Requirements

Objective

Experimental Approach

 

Specifications

Customer Specifications

System Specifications

Elements of the Simulator

System Enhancement

 

Experiments

Shell Module

Parser Module

Race Conditions/Interleaving

Virtual Machine Manager

File Directory Structure

Pipes and I/O Redirection

 

Programs

Milestone 1

Milestone 2

Milestone 3

Milestone 4

Milestone 5

Milestone 6

 

Conclusion

 

Resources

 

 

 

 

Screen Shot Gallery

Introduction

Team Members:

Yolanda Brooks – Team Lead/Quality Control

Leonard Ifeanyi – Lead Java Programmer/Documentation specialist

Hwa Kim – Testing Team Lead/Research analyst

Russell O’Neill – System Architect/Java Consultant/Programmer

 

Customer Requirements:

The customer, Dr. Peter Denning, has requested a simulated operating system. The top layers of the operating system are to be implemented; the virtual machine manager, the file/directory system, and the user shell. The operating system supports multiple user login. Enhancements to the baseline requirements have to be authorized by the customer prior to implementation. A working prototype is to be demonstrated to the customer approximately mid-way through the Spring 2002 semester. Clarifications about requirements and questions about the project are addressed by the customer during the demonstration. The completed simulated operating system is due to the customer May 1, 2002. An exhibition of the project will be provided to the customer Wednesday, May 8, 2002 at 2:00 p.m.  The demonstration will take place in the customer’s office, Science and Technology II.

 

Objective:

The objective of the project is to simulate a partial operating system. The upper layers of an operating system have been simulated with integrated modules using Java as the programming language. The upper layers included in the project are the user shell, the file and directory system, and the virtual machine manager, which executes processes representing user commands.

 

Experimental Approach:

Each module was individually tested using test cases developed by the team. Valid and invalid test cases were used to demonstrate the module is working according to specifications. Prior to each module test, expectations of the tests were discussed among the team. Tests were run three or more times depending on the complexity of the module. Tests that produced invalid results were regression tested for errors after the module was modified to correct the errors. After testing each module separately, the modules were linked together. Test cases were developed for the entire operating system. All available commands to the user were tested against the operating system. Tests included cases for the user login process, user input process, and user logout process.

 <Back to Report Contents>

Specifications

Customer Specifications:

A user logs into a shared system with the user console window. The standard input for the shell is the keyboard and the standard output is the display. A user enters a command followed by an EOL marker. The operating system interprets the command and either executes the command or returns an error message to the user.

 

System Specifications:

The operating system is simulated using Java. Java was selected as the programming language because it is portable, meaning it will run on any operating system. Java also includes the pipes, threads, and monitor structures, which will be used to help implement the upper layers of the operating system.

 

Elements of the Simulator - Baseline Requirements:

The overall structure of the simulator can be viewed as a UML Deployment diagram, or as a UML sequence diagram.

Console window The user console window provides the standard input and output for a job. The standard input is the keyboard. The standard output is the display. The input and output windows were implemented using Java’s library program. The Java console window simulates a single window in which the user types a line and the system outputs its response on the next line. System.in.readln() reads the next complete line typed by the user on the keyboard input window. System.out.println() displays the string on the console output window. The code for the console window has been integrated into the login manager and the shell.

Shell Parser – The shell is an executable program or module that displays the user command line prompt CS471> and waits for the user to type a command line. The shell scans user keyboard input until EOL. The input is parsed into tokens. The shell runs as a thread in a virtual machine. Each user gets an individual shell for entering commands. The shell recognizes only a limited set of user commands. A copy of the shell code OSEmulator.java is included. The parser pattern matches input text and parses into tokens. A copy of the command line parser CmdLineParser.java is included.  A copy of the command line tokenizer CmdLineTokenizer.java is included. A copy of OSToken.java is included. Also, a UML sequence diagram for the shell is included, as well as a UML class diagram.

Virtual Machine ManagerA virtual machine is a program in execution.1 Scripts are generated to execute the user command if the command is syntactically correct. If the user command entered is invalid, an appropriate error message is returned to the user. For the project, the following is the virtual machine structure used. The virtual machine manager is a program within the operating system that creates, manages, and deletes virtual machines for execution of user commands. The virtual machine generates and assigns handles (virtual machine pointers) to objects used by each virtual machine created.

 A handle is the system generated name for the virtual machine object. Handles prevent objects from being modified by unauthorized users. The IN field of the virtual machine structure stores the handle of the device object to be used as the input for the virtual machine. The OUT field stores the handle of the device object that is used for writing output. The thread id is the process number assigned by the operating system for the executing process. The args field is the arguments list to be passed with the executing command. The par (parent), child, and sib (sibling) fields are pointers to related virtual machines. All children virtual machines point back to the parent virtual machine that created them. The parent virtual machine points to the last child created. Each child virtual machine points to the child created directly before its own creation. Children virtual machines with the same parent virtual machine are siblings. undone is a counter that counts the number of children that are still completing their processes. When a process creates children, compute begins the children processes. A parent virtual machine sleeps until all its children virtual machines and processes have finished compute. Undone is 0 when all children virtual machines have completed execution.

This model prevents race conditions because children are "mutually excluded" in their executions.2 No race conditions can occur between children and parent for their use of the parent’s standard input and output.

File System – A directory is a "table associating strings with handles."4 Strings are the names given to the object by the user. For example, filenames are names users give to an object file. Handles are system generated identifiers that are associated with the user strings. The Directory begins with the root. Each user is mapped to their home directory /usr/ILASTAME/, which is the user directory/first initial Last name. A pathname is a sequence of directory names beginning with the root and ending with the object. For example, /usr/roneill/ is Russell O’Neill’s home directory upon login to the system.

We implemented the filesystem using a java class loader to handle dynamically creating the command class objects. In addition, we used Java's file and directory handling operatins to handle user control over the virtual filesystem. As such, an change that occured in the emulator, would also take place on the host system.

The file and directory system allow the user to manipulate files within their user directory. Commands available to the user are cat (for concatenate), ls (list a file), rm (remove a file), rmdir (remove a directory), mkdir (make a directory).

Pipes Manager – For the Pipes Manager, the project uses Java Pipes. Because of this, a simple Pipe.java class holds the virtual machine ids of the two virtual machines connected by the pipe, as well as the two streams actually doing the piping. To control the pipes, a java HashMap is used from within the VirutalMachineManager.

Commands - Commands are executable programs stored in the /bin directory, but can be executed from any user’s current directory. The State diagram for command line syntax is included.

Command Syntax

The parser checks the scanned user line for the following patterns or form:

commandline ::= cmd [< infile][ | cmd ]* [ > outfile]
cmd ::= commandname [optionflags] [arguments]
optionflags ::= -optionletter [ -optionletter]*
arguments ::= argname [argname]*
 
 

A command line consists of an optional input file and optional output file connected by a pipeline of one or more commands separated by pipe symbols (|). If the infile (or outfile) is omitted, the pipeline input (or output) is the same as the shell's input and output. The shell searches the bin directory for command names and the user’s home directory for file names. If the program or file does not exist in the specified location, the shell returns an error message to the user "command not found". Autoloading is achieved by ??? New commands can be added to the operating system by storing their programs in the bin directory. The shell module will not have to be recompiled. Commands included for the user are login, logout, shell, date, edit, help, cat, and the basic file and directory commands ls (list), rm (remove a file), rmdir (remove a directory), and mkdir (make a directory).

 

System Enhancements

The system enhancement is the user mail system. Users have the ability to send and receive mail to users of the system. Each user has a user directory assigned to them. Within each user directory is another directory called inbox. The inbox directory contains the user’s individual messages. The mail program runs in the background. The mail process checks each user’s directory for new mail and sends indicator to user when new mail is present. The mail process is set to poll the user directories every 15 seconds. When a user logs into the system, if new mail is in their inbox, "You have new mail." is displayed on the user’s screen. To enter the mail system, the user types mail from the user prompt CS471>. A popup menu is displayed with the mail options available to the user. The menu options are send, forward, check for new mail, and delete mail. Screen shots for the mail system are included as a link. URLChecker.java is included. MailSystem.java is included.

<Back to Report Contents>

 

Experiments

Each module was tested individually prior to linking all modules. The user window console module was the first module created for the project. The team had initially implemented 2 types of user console windows: the command line window and the graphical user interface (GUI) console window. Both windows were tested using the same test cases. Both console windows provided the same correct results. However, the team felt the command line window was easier to implement.

The shell module - The shell module is used as the login for the user. The shell executes the users’ keyboard commands. To test this module, we ran all commands available to the user as specified in the command section. All the commands ran successfully and returned the correct response back to the user. Screen shots for testing shell are included as a link.

The parser module - The parser module parses commands into tokens. If the command is syntactically correct, a script is generated by the operating system to execute the user’s command. If the command entered by the user is not syntactically correct, an error message is returned to the user. To test the parser module, we ran valid and invalid commands and analyzed the system’s response back to the user. Commands that were syntactically correct, were further executed by the operating system. Commands that were not syntactically correct were not executed by the operating system. An error message was displayed for the user. Invalid commands were also tested for events of the file not being found and command not found. Valid commands including non-existent files returned error message, "File not found." Valid commands not included in the operating system returned the error message, "command not found." All commands were also tested to ensure they could be run from any directory on the system. Screen shots for the parser tests are included as a link.

Race conditions/Interleaving - A race condition occurs when two or more processes request to access the same resource simultaneously. The user console window is used as the interface between the user and the operating system. The console window is used to demonstrate race conditions when 2 threads execute concurrently competing for the same resource, in this case the monitor. The operating system has to have a method to prevent race conditions from occurring. In order to achieve this functionality, mutual exclusion statements were added to code. When concurrent processes were tested, the output to the display was correct. Interleaving of the two processes had been prevented. The race condition was tested as part of CS471 assignment A2. A copy of the code is included as a link.

The virtual machine manager - The virtual machine manager (VMM) is a "subsystem that manages all the virtual machines."2 The VMM assigns each virtual machine a handle upon creation. The handles are stored in the user’s individual home directory. The parent and children virtual machines are mutually excluded in their executions. No race conditions can exist between children and their parent’s usage if the standard input/output ports. The user types in a line of text. The parser interprets the line into a valid command or an invalid command. If the command is valid and syntactically correct, the operating system generates a script. The script creates virtual machines to execute the user’s command that was interpreted by the parser. The compute command creates the VM structure for the command. The shell sleeps while the virtual machine’s children are processing. Once all the children virtual machines are completed, the shell is awakened. The shell cleans up the virtual machines and generates the command prompt CS471> to the display. The virtual machine manager module was tested for all available commands to the user. Screen shots for the virtual machine manager module are included as a link. 

The file directory structure - The project builds on the existing file directory structure of the project’s platform. The file directory module allows users to manipulate files and directories. Commands available to users are ls, mv, rm, mkdir, rmdir, and cat. Users can search a directory with the cat <filename> command. If the file is not found, the user will be returned an error message, "file not found". The user can insert text or another file into an existing file by also using the cat command. This module was tested using all the commands. Invalid commands were also entered to observe handling by the oeprating system. The cat command was executed to ensure files would display correctly on the monitor without interleaving. Screen shots for the file directory module are included as a link. 

The pipes - The IN and OUT ports are standard fields of your virtual machine They contain open-object handles for either a pepe, a file, or a device. The READ and WRITE commands work when they are applied to any one of these types of open-object handles. If you are reading from a pipe, the READ command won’t return until it has read the entire amount you need to continue processing. The same with the WRITE command, the command will not return until the entire amount has ben written into the pipe. To test the pipes module, we used the cat, sort, and date commands. The cat command copies files from input to output. Input is read until an EOF is encountered. The read input is copied into the output. Screen shots of the tests for the pipe module is included as a link.

 

<Back to Report Contents>

Programs

Milestone 1: PAR 1
Project initiation involved organizing our team, selecting the programming environment, reading the required material and build an operating console-window.

Milestone 2: PAR 2
Operating prototype shell parser; it reads lines from the console window and creates a script of the commands the OS is to execute in order to carry out the command line.

Milestone 3: PAR 3
Working basic file and directory system interface.  Commands include ls, mv, rm, mkdir, cat, etc...

Milestone 4: PAR 4
Working prototype of the command interpreter, it can invoke any single command with arguments automatically.

Milestone 5: PAR 5
Working baseline simulator including pipes and input-output redirection.

Milestone 6: PAR 6
Working full simulator and URL of a draft final report.

Executable Commands located in \bin:
cat – concatenate
cd – change directory
cp – copy
ls – list
mkdir – make directory
mv – move file or rename
pwd – current directory
rm – remove file
date - display the date
edit - create a text file
rmdir – remove directory

<Back to Report Contents>

Conclusion

The virtual machine simulator project was a good experience for all the team members. We learned to work together as a team and compromise to keep the project moving. The team did not feel overwhelmed with the project. The milestones were used as guidelines for when key items were due back to the customer. Each of the team members introduced various skill sets to the project. Work assignments to achieve the milestones was divided among the group based on your skill set. Programming the modules was done by Russell O’Neill and Leonard Ifeayni. Yolanda Brooks and Hwa Kim focused on creating, testing, and documenting findings and errors for valid and invalid test cases for all modules of the operating system. Demonstration of the prototype to the customer proved to be a valuable experience. During the prototype demonstration, the customer validated our requirements and made suggestions on how to improve the final product. The feedback the team received from the customer was incorporated into the various modules as suggested. The virtual machine simulator is functioning correctly. Users can login to the system from the shell with a username and password. The command prompt indicates to the user that the system is ready to accept input. The user can execute commands from any directory in the system. Valid commands for the operating system are stored in the /bin directory. Invalid or commands that are not syntactically correct return an appropriate error message back to the user. In addition to being able to manipulate files using the existing file directory structure, the user also has the enhanced functionality to send and receive mail from other users of the system. Users do not have to be logged into the system to receive new mail in their inboxes. When the user logs into the system, if new mail is in their inbox, "You have new mail" will be displayed.

The team found not having all the team members knowing Java programming a challenge. However, limiting the programmers to two people made it easier to integrate the individual modules. Scheduling was also a challenge because the team consists of 4 members, but the team always managed to meet once a week either in person or via email exchanges. One of the hardest areas of the program was the pipes section. This was the area that seemed to be the hardest to code and debug. One set back to the project was that we had to redevelop the shell to be recursive. The team had originally designed this module to be non-recursive. The user should be able to execute the command shell within his own shell.

Shells and user interfaces can be considered great principles. They have been around over 40 years and seem to have a bright future. As technology advances, we expect user interfaces and shells to become more user-friendly. The GUIs have made the remembering of specific commands and syntax something of the past. Users no longer have to rely on memory or manuals to search for a necessary command. Most GUIs have included familiar icons so that the user will recognize what function will be executed when they click on the icon. The team debated whether keyboard input would be eventually eliminated with all input to the system either being done through a mouse or through oral dictation. The team compromised on keeping the keyboard for the purpose of disaster recovery or continuity of operations. Otherwise, we think most user input will be done via a mouse.

 

 <Back to Report Contents>

Resources

  1. Denning, Peter J. "Notes on Virtual Machines". 1999.
  2. Denning, Peter J. "Virtual Machine Basics". 2001
  3. Denning, Peter J. "Info Objects Basics". 2001
  4. Denning, Peter J. "Handles and Directories". 2001
  5. Denning, Peter J. Hunt, James J, and Tichy, Walter F. "Operating Systems". 1999
  6. Denning, Peter J. "Mutual Exclusion". 2002
  7. Denning, Peter J. "Synchronization". 2001
  8. Denning, Peter J. "Computer Architecture Basics". 2001
  9. Gagne, Greg. Galvin, Peter. Silberschatz, Abraham. "Applied Operating System Concepts". 2000