Project 5 - Multithreaded Space Simulation

Introduction

In this project, you will develop a multi-threaded Ruby program that can be used to simulate space travel. You will also write code to process simulation output to display the state of the simulation and verify its feasibility.

Getting Started

• Download the archive file p5.zip and extract its contents.

Along with files used to make direct submissions to the submit server (submit.jar, .submit , submit.rb), you will find the following project files:

• Your Ruby program
  • space.rb - space simulator
• Public tests and example simulation output
  • public1.in
  • public2.in
  • public3.in
  • public4.in
  • public5.in
  • public6.in
• Display outputs for public tests
  • public1_display.out
  • public2_display.out
  • public3_display.out
  • public4_display.out
  • public5_display.out
  • public6_display.out
• Public test verify outputs
  • public6.in and public_6_verify.out
  • public7.in and public_7_verify.out
• goTest.rb - Ruby script to run public tests

Project Description

Space Simulation Rules

• Starports
  • A list of starports (and its capacity in ships) is provided.

• Starships
  • A list of starships (and its capacity in travelers) is provided.

  • Starships are initially in space (not docked to a starport).

  • Starships visit starports, in order from first to last in the list. When a starship visits the last starport in the list, it repeats the process starting from the first starport on the list.

  • The total number of starships docked at a starport must not exceed the capacity of the starport. If there are multiple starships waiting to dock with a starport, the order they dock is unspecified.

• Travelers
  • A list of travelers (and their itinerary) is provided.

  • Each traveler's itinerary specifies which starport they must visit, and in which order. Travelers ride starships from port to port on their itinerary until they reach their final destination.

  • The same starport may occur on the itinerary multiple times, but may not be adjacent to itself.

  • At the start of the simulation, each traveler is at the first starport on their itinerary.

  • Travelers wait at starports until a starship arrives, then try to board the starship and ride it to the next starport on the traveler's itinerary. Travelers may ride aboard any starship, as long as the capacity of the starship is not exceeded. If multiple travelers are trying to board a starship, the order they do so is unspecified.

  • When a starship carrying a traveler arrives at the next starport on the traveler's itinerary, the traveler may attempt to disembark (depart the starship and enters the starport) while the starship is docked to the starport.

  • It is possible that a traveler at a starport may miss boarding a starship as it passes through. In that case, the traveler remains at the starport and waits for an opportunity to board another starship.

  • Similarly, a traveler riding on a starship may miss the opportunity to leave the starship while it is in port. In that case the traveler remains on the starship to wait for another opportunity to disembark at the desired starport.

  • Travelers continue moving from starport to starport until they reach the final starport on their itinerary.

  • The simulation ends when all travelers reach the final starport on their itinerary.

Space Simulation Outputs

• starship docking at starport
• starship departing from starport
• traveler boarding starship at starport
• traveler departing starship at starport

Because the simulation is multithreaded, the order messages are output is dependent on the thread scheduler. Running the same simulation will likely produce different outputs each time.

The simulation output provided in the public tests is simply an example of one possible output. The output of your simulator does not need to match it exactly. In fact it will be unlikely for your simulation output to be identical to the example output provided, especially for large numbers of threads.

Space Simulation Parameters

• Starports - name of each starport and its capacity
• Starships - name of each starship and its capacity
• Travelers - name of each traveler followed by list of starports in itinerary
• Output - possible simulation output for simulation

=== Starports ===
Earth 1
Vulcan 1
=== Starships ===
Enterprise 1
=== Travelers ===
Kirk Earth Vulcan 
=== Output ===
Enterprise docking at Earth
  Kirk boarding Enterprise at Earth
Enterprise departing from Earth
Enterprise docking at Vulcan
  Kirk departing Enterprise at Vulcan

Space Simulation Driver

     ruby space.rb [simulate|display|verify] simFileName

The code in space.rb outputs simulation parameters before simulation output, so that its output (if saved in a file) may be passed directly to the simulation display/verify routines for use in debugging your simulation.

Project Implementation

Part 1: Simulation Display

The first part of your project is to implement a model of the simulation (by processing simulation event messages) sufficiently detailed to display the following

• Starships at each starport
• Travelers at each starport
• Travelers on board each starship

For instance, for the simulation parameters in public1.in described above, your code should display the initial state of the simulation as follows:

----------------------------------------
Earth         Kirk 
Vulcan        
----------------------------------------  

----------------------------------------
Enterprise docking at Earth
----------------------------------------
Earth         Kirk 
  Enterprise  
Vulcan        
----------------------------------------
Kirk boarding Enterprise at Earth
----------------------------------------
Earth         
  Enterprise  Kirk 
Vulcan        
----------------------------------------
Enterprise departing from Earth
----------------------------------------
Earth         
Vulcan        
----------------------------------------
Enterprise docking at Vulcan
----------------------------------------
Earth         
Vulcan        
  Enterprise  Kirk 
----------------------------------------
Kirk departing Enterprise at Vulcan
----------------------------------------
Earth         
Vulcan        Kirk 
  Enterprise  
----------------------------------------

Part 2: Simulation Verifier

It should be clear that a multithreaded simulation may have many different behaviors, depending on the thread scheduler. However, there are certain restrictions on the simulation output, e.g., travelers can board starships only when those starships are docked at the starport. To help you debug your simulator, you will write a verifier to examine your simulation outputs and checks whether they are valid (i.e., follows all the simulation rules in the project description).

The list of possible errors in the simulation output is huge, so you only need to check some common errors associated with data races resulting from incorrect synchronization. Many of these errors manifest as missing or out-of-order simulation messages. Some conditions you need to check are:

• Starships are traveling between starports in the correct order
• Starships always dock at a starport before leaving it
• Starships do not exceed the capacity of a starport
• Travelers follow their itinerary
• Travelers only board or leave a starship while it is at a starport
• Travelers do not exceed the capacity of a starship
• All travelers have reached their final destination when simulation ends

Your verifier should output either "VALID" or "INVALID", depending on whether any illegal output is found.

Part 3: Space Simulation

• Each starship and traveler in the simulation must be represented by its own thread. Thus, if you are simulating m starships and n travelers, you should be creating m+n threads.

• The initial state of the simulation should be as described in the space simulation rules (i.e., all travelers at the first starport in their itinerary, all starships poised to enter the first starport in the list of starports).

• You must use synchronization (i.e., Ruby monitors) to avoid data races and ensure your simulation is valid. You must use conditional variables to ensure your simulation uses synchronization efficiently.

• Initially you may use a single monitor and conditional variable for the entire simulation. For a more efficient implementation you should have a separate monitor for each starport, and multiple conditional variables for each monitor.

• Each starship should sleep for 0.001 seconds after docking at a starport (by calling "sleep 0.001"). Each traveler should sleep for 0.001 seconds after departing a starship. The thread should release any locks it has acquired before calling sleep.

• The simulation ends when all travelers have arrived at their final starport. To determine when this condition is reached, each traveler thread should exit when its traveler reaches its final starport, and the main thread can call join on all the traveler threads. Notice that it is legal if starship threads continue running for a while even after all passengers have reached their final destinations, since the join is not instantaneous.

• You should set Thread.abort_on_exception = true in your code, to detect errors if any thread throws an exception.

• In order to see what's going on during your simulation, your program must print out various messages as simulation events occur. For the simulation output to make sense, you must do the following:
  • Create a lock (e.g., $printMonitor) that all threads must acquire when printing messages for simulation events
  • Before a thread prints out the message for a simulation event, acquire both the lock for printing messages, and the lock preventing data races for the simulation event
  • Immediately after printing, and before you release either locks, call $stdout.flush to flush the simulation message to standard output.

  Your code for printing simulation output may look like the following:

    starportMonitor.synchronize { 
      ...starship docks at starport...
      $printMonitor.synchronize { 
        puts "starship docking at starport"
        $stdout.flush
      }
    }
  

  Following the rules above should ensure that if you build the simulation correctly, your simulation output will be valid. Otherwise, you might get strange interleavings of output messages that look incorrect even if your simulation code is actually correct.

The submit server tests will ignore any lines output beginning with "%".

TAs will look at your submitted code to check that you are using synchronization correctly.

Submission

• Submit your file space.rb directly to the submit server by clicking on the submit link in the column "web submission".

  

  Next, use the submit dialog to submit your space.rb file.

  

  Select your file using the "Browse" button, then press the "Submit project!" button.

• You may also submit directly by executing a Java program on a computer with Java and network access. Use the submit.jar file from the archive p5.zip, To submit, go to the directory containing your project, then either execute submit.rb (preferred method) by typing:
  ruby submit.rb

  or use the java jar directly using the following command:

  java -jar submit.jar

  You will be asked to enter your class account and password, then all files in the directory (and its subdirectories) will be put in a jar file and submitted to the submit server. If your submission is successful you will see the message:

  Successful submission # received for project 5

Academic Integrity

The Campus Senate has adopted a policy asking students to include the following statement on each assignment in every course: "I pledge on my honor that I have not given or received any unauthorized assistance on this assignment." Consequently your program is requested to contain this pledge in a comment near the top.

Please carefully read the academic honesty section of the course syllabus. Any evidence of impermissible cooperation on projects, use of disallowed materials or resources, or unauthorized use of computer accounts, will be submitted to the Student Honor Council, which could result in an XF for the course, or suspension or expulsion from the University. Be sure you understand what you are and what you are not permitted to do in regards to academic integrity when it comes to project assignments. These policies apply to all students, and the Student Honor Council does not consider lack of knowledge of the policies to be a defense for violating them. Full information is found in the course syllabus---please review it at this time.