CMP 426/697, Operating Systems, Lehman College, CUNY, Fall 2016

Project Guidelines and Grading Scheme

Groups of 1 or 2: You may work on each project by yourself or with another student. You can change who you work with from project to project.
Code outline: For all projects, you must submit an outline of your proposed code design, which will be due at least a week before the project deadline.
For Project 1: The outline can be informal but should explain the flow/algorithm of your program and any major methods that you will write. You can use any combination of diagrams, paragraphs explaining your plan, or pseudo-code (which can be comments and method headers in a .java file).
For Projects 2 - 4: The outline must be done in pseudo-code. The goal of this is two-fold: 1) to practice writing pseudo-code, and 2) to think about how your program will be organized before you begin coding. Here is a good description of what pseudo-code is and how to write it.
If the project you turn in differs significantly from your plan, you must include a paragraph explaining why you made the change (i.e. what was wrong with your plan and how your new design fixes it) If your plan only covers some of the parts (see Grading section) and you later decide you want to submit more parts, you should include an outline for the missing parts with your final project submission.
Late days: Each student has three late days total (NOT per project) to use as they see fit. If you use 1 late day you can submit your project up to 24 hours after the due date and it will still be accepted. If you use 2 late days you can submit your project up to 48 hours after the due date, etc. If a group of 2 uses a late day, then both students in that group will use up one of their late days. To use a late day, send me an email (megan.owen@lehman.cuny.edu) saying so. Late days can only be used as the whole day and not as some amount of hours. i.e. if you want to submit a project 5 hours late, you still need to use 1 late day.
Grading: Each project will have 3 parts. Completing only part 1 successfully will result in a C grade. Completing only parts 1 and 2 successfully will result in a B grade. Completing all parts (1, 2, and 3) successfully will result in an A grade. Successful completion means all (or almost all) automatic test cases pass. If some of your test cases pass in part 1, then you will receive a C- (regardless of what you have done for parts 2 and 3). If all of your test cases pass in part 1, but only some in part 2, then you will receive a B- (regardless of what you have done for part 3). If all of your test cases pass in parts 1 and 2, but only some in part 3, then you will receive an A-. If your code is clearly written and follows good coding practices (see next item), then your grade will be one higher (i.e. B- becomes B, B becomes B+, etc.)
Good coding practices: To receive the grade boost, your code must:
- be commented
- use meaningful variable, method, and class names
- use proper indenting
- use objects, as well as static and non-static variables and methods, properly
- be readable
If you are wondering if your code follows good coding practices and will receive the grade boost, I am happy to look at it during office hours. If you can not make office hours, email me to make an appointment for another time, as I will NOT look at this over email.

Project 1
For this project, you will write a basic command line interpreter or shell in Java. CMP 426 students should do everything except that indicated for CMP 697 students. CMP 679 should do everything.
Part 1
Write a basic interactive shell in Java in a class called MyShell. Your shell should print the prompt "prompt>" when it is started and wait for the user to enter a command. Once the user has entered a command and pressed the enter key, your program should fork a new process and have this child process execute the entered command. Your shell should wait for the child process to finish and then display a new prompt "prompt>". Again the user can enter a command and it should be executed using a child process, etc. When the user is finished, they should be able to enter "exit" at the prompt, and the shell program will end.
You can use the following Java classes to create and monitor the child process:
- Runtime class
- Process class
The method Runtime.exec() will create a child process that executes the specified command.
The method waitFor() in class Process can be used to wait until a (child) process has finished.
Assume that the user gives the full path name for all commands/executables. For example, the user would give "/bin/ls" rather than "ls".
Part 2

For this part, you will add error checking of input to your shell. Your shell should be able to deal with the user hitting enter but not writing any commands, extra white space, etc.
As well, you should write a second Java program/class called CommandLineTest. This class should have its own main() method, and we will run it at the command line (your prompt) using the build-in 'java' command.
This program takes in 1 mandatory command line argument and two optional command line arguments. The optional command line arguments should be able to be entered in any order. The syntax is:
java CommandLineTest <optional arguments> num
where num is an integer greater than or equal to 0 and the optional arguments are:-s and -e.
This program should print out "middle" num times. If the -s option is included, it should print out "Starting..." at the start of the program, and if the -e option is included it should print out "Ending..." at the end of the program.
For example, prompt>java CommandLineTest 5 should print out:
middle middle middle middle middle
prompt>java CommandLineTest -e -s 3 OR prompt>java CommandLineTest -s -e 3 should print out:
Starting... middle middle middle Ending...
prompt>java CommandLineTest -e 0 should print out:
Ending...
Do NOT use a pre-existing command line argument parser. You should write your own. It only needs to be able to handle this one program
CMP 697 students: Your -e option should also be able to take in an optional parameter (i.e. -e 3) that specifies the number of times to print "Ending...". If no number is given, print "Ending..." once. All of the above example still hold. Here is another example with the optional parameter:
prompt>java CommandLineTest -s -e 2 0 should print out:
Starting... Ending... Ending...
Hint 1: Consider using switch.
Hint 2: You can run a program with arguments in Eclipse, by going to menu item Run->Run Configurations, and clicking on the Arguments tab. Enter the command line arguments in the white box. Eclipse will run your program as if it has been run at the command line with these arguments.
Part 3

In Parts 1 and 2, the shell was used interactively by the user. That is, the user would enter a command, the shell would parse and execute it, and then the user could enter another command, etc.
For Part 3, you will expand your shell program so that it can also run in batch mode. In batch mode, the user will specify a file containing a list of commands, one per line. The shell will then read in the commands, and execute them one at a time, in the order they appear in the file. In other words, these commands are not executed interactively, but as a group (or batch!). To enter batch mode, the user will type prompt>run <batch file name>. Your shell should then execute all commands in the file <batch file name>. Then it should become an interactive shell again.
Submission
To submit your project on Mimir, you must first join the course:
To join the course on Mimir:
1. Go to mimirplatform.io
2. Click on the Login button (upper right corner) and create an account.
3. Once you are logged in, click on "Join a course" and enter the course code: cb83a462c3
Do NOT pay for Mimir. There should be a 2 week free trial, and we will supply free license keys before the end of it.
Project 2

For this project, you will write a program to simulate how page tables and pages work in memory. The main method will be inside a class called OS, which represents an operating system. This class will contain a page table and an array of Page objects, which represent pages in memory. We will assume there is only one process/page table/set of pages for this project.
CMP 426 Part 1; CMP 697 Part 1a

For this part, you will start writing the two classes: OS, which represents an operating system; and Page, which represent a page in memory. You may change the method parameter names below, but not the names of the methods themselves (since they are used for testing in Mimir).
The class Page should contain:
- an instance variable to store its virtual page number
- an instance variable that is a byte array and represents the data stored in that page (so the byte in position 0 in the array would be the first byte of data stored in the page, etc.), and
- a method called getData(int offset) which returns the byte at position offset in the data array. This method should throw an exception with the message "invalid offset" if offset is invalid (i.e. if it is a negative number or greater than the size of the data array).
The class OS should contain:
- an array of Page objects, representing the computer's physical memory. In Part 1, the size of the array will always be 8, but in parts 2 and 3, the size can vary. The index of a Page in this array is considered its physical address.
- for some kind of data structure representing a page table. The simplest option is to use an array, but you can use a more complex data structure if you prefer. This data structure should allow the user to look up the physical page number (ppn), given the virtual page number (vpn). It will be accessed and tested using the following method.
- a method called getPPN(int vpn), which looks up the virtual page number (vpn) in the page table and returns the corresponding ppn (physical page number).
- a method called getDataAtVirtAddress(int virtAddress), which returns the byte stored at virtual address virtAddress. In Part 1, we will only use the last 7 bits of virtAddress to represent the address. The last 4 bits will represent the offset and the next 3 bits will represent the virtual page number. In parts 2 and 3, the size of the offset and virtual page number can vary. To find the byte to return, you must consult the page table to determine the corresponding physical page number, find that Page object, and return the byte in its data array at index corresponding to the offset. You should use bit manipulation as much as possible in doing the calculations.
- a constructor OS(String filename) that loads page table and page data from the file called filename into the corresponding data structure and objects. The file will have the following format:
  - first line contains two integers, separated by a space, representing the number of pages (numPages) and the number of bytes in each page (numBytes). For Part 1, all files will begin with "8 16".
  - the next numPages lines represent the entries of the page table. Each line will be in the format "vpn->ppn" (i.e. "5->6").
  - the next numPages lines will contain numBytes bytes of data for each page, ordered by physical page number. That is, the first of these lines is the data for physical page 0, the next of these lines is the data for physical page 1, etc.
  Two examples of data files for Part 1, which are also used in the test cases: proj2_data1.txt and proj2_data2.txt. These files are also used in the test case and are encoded using UTF-8, so each character represents 1 byte.
- [added Sept. 25 for use in test cases, but does not need to be in your outline] a method getPage(int ppn) which returns the Page instance with physical page number ppn. i.e. the Page instance at index ppn in your array of Pages.
CMP 426 Part 2; CMP 697 Part 1b

Modify your code so that it can accept any number of pages and bytes of data per page, with the constraint that the corresponding virtual address size will be less than or equal to 32 bits (= size of an int in Java). The number of pages and number of bytes per page will always be given at the top of the data file. Two sample data files (also used in the test cases): proj2_data3.txt and proj2_data4.txt.
CMP 426 Part 3; CMP 697 Part 2

For this part, you will create a (simulated) Translation Lookaside Buffer (TLB) that uses the random replacement policy. There are no Mimir test cases, so you have more freedom in how you implement this part.
You can simulate the TLB however you would like, but you should be able to specify the number of entries it holds. One way is to create a 2D array as an instance variable of your OS class, where the size of the array is (number of entries in TLB) x 2. If your array name is tlb, then tlb[i][0] would be the virtual page number at entry i and tlb[i][1] would be the corresponding physical page number. Or, if you are planning to do the next part, you could make a new class to represent an entry in the TLB, and use an array (or some other data structure) of this class as the TLB.
Once all of the TLB entries are filled for the first time, the entry to be replaced should be chosen at random.
To simulate it taking more time to find the physical address if the virtual address is not in the TLB, add a delay for this case using TimeUnit.MILLISECONDS.sleep(...) (or a similar method).
There should be an easy way to specify the number of entries in the TLB and the delay used if the physical address is not in the TLB. For example, you could make a second constructor that also takes in these parameters.
Now you will use your code to perform some analysis. Either choose i) 2 different delay times and 5 different TLB size, or ii) 5 different delay times and 2 different TLB sizes. Run your code on the following four files, which contain lists of virtual memory addresses to access (i.e. the memory calls a process might make). For each delay time and TLB size, compute the total time it took your program to calculate the corresponding physical addresses for each file. Display this information in a graph or a chart. What do you notice? Why do you think that is the case?
~~Lists of virtual memory addresses to come! Note that you will also have to write code to read in these files and time the computations.~~ Still to come. This section will be updated first on Mimir (and posted as an annoucement on Blackboard).
CMP 426 extra credit; CMP 697 Part 3

Add an option to choose the entry to replace in your TLB using a Least-Recently Used (LRU) policy instead of randomly selecting the entry.
Repeat your computations and analysis from the previous part using the LRU replacement policy. When is the LRU policy better the random replacement? Are there any cases in which it is worse?
Submission
Submit your project on Mimir. For Part 3 and extra credit (CMP 426) or Parts 2 and 3 (CMP 697), submit your analysis in a .txt or .pdf file. There are no test cases for these parts.
A license should have been applied to your account so that you can use Mimir for free. If it is still saying you are in the 2 week free trial period, please contact me.
Project 3
Project 4

CMP 426/697: Operating Systems Lehman College, City University of New York Fall 2016

Project Guidelines and Grading Scheme

Project 1

Part 1

Part 2

Part 3

Submission

Project 2

CMP 426 Part 1; CMP 697 Part 1a

CMP 426 Part 2; CMP 697 Part 1b

CMP 426 Part 3; CMP 697 Part 2

CMP 426 extra credit; CMP 697 Part 3

Submission

Project 3

Project 4

CMP 426/697: Operating Systems
Lehman College, City University of New York
Fall 2016