CS 3733 Operating Systems, Spring 2003 Assignment 3

Due Thursday, March 27, 2003

In this assignment you will use the ring simulator to explore process scheduling and synchronization. Read the exercises after Program 4.1 in the text to get a feel for the problem. However, you will just be using the simulator and do not have to compile any programs.

Make a directory called assign3 for all of the files for this assignment.

You will be creating several log files. Each log file will have images that use the same filenames. Be sure to put each log file with the associated images in a different subdirectory so you do not write over the log and image files on the next run.

Part 0
Put the contents of this tar file in your assign3 directory. Modify the ringconfig file so the the user line contains your name instead of Local User. Make sure that /usr/local/courses/java/bin is in your path (you did this in assignment 2) and run the ring simulator using
runring

The simulator should come up and you should be able to create a log file.

Part 1
Open a log file and keep a log of the output generated for each set of runs described below. You can display the output generated by the simulated program by clicking on the Display Info button and then Display Output. Run the program several times (at least 3) with the configuration indicated and put the resulting output in the log file. Push the Reset button between runs. After logging the output, push the clr button on the output window before starting the next set of runs.

Try each of the following and record the output generated by the simulated program.

After each of these, change back to the standard configuration:
After fork: parent
Choose Process: FCFS
Scheduling: no preempt
Print Atomic

  1. The standard configuration.
  2. Change After fork from parent to child.
  3. Change After fork from parent to either.
  4. Change After fork from parent to random.
  5. Change Choose Process from FCFS to Random.
  6. Change Scheduling from no preempt to round robin with a quantum of 5 and Choose Process from FCFS to Random.
  7. Repeat the experiment above with a quantum of 2 and see if it behaves differently.
  8. Change Print Atomic to Print Not Atomic with probability 0.1.
  9. Insert a wait(NULL) call before the fprintf statement.
  10. Change Print Atomic to Print Not Atomic with probability 0.1 and insert a wait(NULL) call before the fprintf statement.
You do not have to put all 10 runs in the same log file, but remember to copy the log file and the image files to another directory after each run. On some systems the simulator may run out of memory after a few runs, so save your log file and be prepared to restart the simulator if necessary.

After running each experiment (which consists of three or more runs with the same parameters) log the output and then clear the output.

After running all of the experiments, answer the following questions:

  1. For which of the 10 experiments was the output in the same order each time it was run?
  2. For which of the 10 experiments is the order of the output determined by the ring program, rather than by the way the processes are scheduled?
  3. For experiments 1, 8, 9 and 10 explain why you think the output was in the order that it was.

Part 2
For this part you will run the Tree program. Use the Change Program button in the second column can choose the TreeOfProcesses program. This is similar to the tree of processes of Example 2.7 of PUP. This will be run with nprocs equal to 5, generating 16 processes. Make 1 run of the simulator for each of the following:

  1. The default configuration
  2. after fork: child
  3. after fork: parent, Scheduling RR, quantum = 2
  4. after fork: parent, Scheduling RR, quantum = 3
After each run, move the processes around so that the tree structure is apparent. The original process should be at the top. All of its children should be at the next level. The grandchildren of the original process should be on the next level, etc. At each level, order the processes by the number of children they have with the processes having the largest number of children on the left. Log the diagram and the output for each experiment. Make sure each log entry is labeled so you can tell which is which. Answer the following questions:
  1. Is the tree structure the same in each case? How does it differ?
  2. The process IDs are assigned in the order of creation. In each case describe the order of creation relative to the tree structure.
  3. Is the order of the output affected by the scheduling of the processes?

Part 3
For this part you will implement mutual exclusion using a semaphore. Start with the original ring program. Set the simulator for "Print Not Atomic, Probability 0.1" and Scheduling, RR, quantum 5. Run the program and confirm the the output is interleaved.

  1. Change the mode to Program Mode by using the Mode button at the top of the third column.
  2. You can now move the pointer up or down using the buttons in the third column.
  3. Create a semaphore using the New Variable button.
  4. Enter the name of the semaphore when prompted.
  5. The semaphore has been initialized to 1.
  6. Put wait(sem) and signal(sem) calls around the fprintf
    Do not use the wait(NULL) instruction.
  7. Go back into Execute mode.
Call this program ringsemaphore and save it. Modify your ringconfig as before to include this program.

Run the new program and save the the program and output in a log file. The critical section should have been protected and the lines should be printed atomically. What determines the order in which the lines are output? Try changing the scheduling algorithm and determine whether it affects the order of the output.

Use the cover sheet to hand in your assignment. Your log files for parts 1 and 2 can be in several parts, but number the pages consecutively and fill in the index on the cover sheet. Then answer the questions on the cover sheet.