CSS 430 for 2016 Summer
Program 3: Synchronization

Due Date: See the syllabus

This document is final (please begin work on it)
(note that the grading guide has been posted - it's at the end)

1. Purpose

This assignment has two overall sections.  In the first section you will examine code provided in your textbook and explain how a problem might (or might not) occur when the provided code is modified. In the second section you will write multithread code that needs to be synchronized for correct execution.

2. Examining Multithreaded Code For Errors

For this assignment you must explain all your answers in your own words.  Plagiarism will be harshly punished

The questions that you need to answer are listed in the following sections (i.e., section 2, section 3, etc).

For each question clearly describe the problem that can occur in each situation (or else clear explain there will be no problems)

Please start by clearly stating whether a problem could occur or not (just so it's clear to the instructor what you're arguing in favor of :) )

If the change will never cause any problems then explain why the change to the code is benign.  Depending on the details of the code the most direct way to explain why the changes are beneign is to enumerate all possible scenarios that the program might encounter and then show why each one is ok (This blue highlighted material was added on August 1st - if it's useful please use it BUT if you've already got good answers then don't worry about it).

If a problem can occur then clearly explain how the situation could happen.  Do this by downloading a 'Process Problem Chart' (one for each question), and filling it in. 
Start by explaining what the processes were doing prior to the problem. 
Next, provide a clear, concise explanation of the problem itself.
Lastly, fill in one table per process detailing exactly what each process was doing when the problem occurred.

Notes on filling in the chart:

  1. Please name the file with the section and the part.  So question "A", below, should be located in a file named "2A.docx" (or "2A.pdf")
  2. The "Line #" should list the line number in the file where the process is when the problem occurs
  3. Make sure that you list all the values of the relevant variables when the problem occurs.  Irrelevant variables can be left out of the table.  List each variable on a separate line.
  4. If you need more processes for your example then you should  copy-and-paste the last table, and then increase the process # for your new table/process.
  5. If you want to add more stuff to the file you should do so.
    In particular, you're encouraged to draw pictures if it helps illustrate your point.
    One easy way to draw a picture is to write the picture out on paper, snap a picture of it using your phone, and to then paste the picture into your Word document.

Some general notes about your answers:

  1. The topic we're studying is synchronization, so focus your answers on describing what the effects of mis-synchronizing the code would have.
    For example, if you're asked "Describe a problem that would happen if the mutex variable was left out." focus your answer on the program would be behave differently when the mutex variable was completely removed from the program.  An answer like "When you remove line 25 (private Semaphore mutex;) the program won't compile because the variable mutex is undefined" will get you zero points because it doesn't actually talk about synchronization.
  2. Strive for conciseness.
    After you've thought up an example please go back and ask yourself if there's any way of simplifying it.  It's going to be a lot of work to fill in these table for each process (and to double-check that everything is exactly the way that it should be) so the smallest possible example will be easier for you to describe correctly.
  3. Remember that synchronization problems (especially race conditions) may or may not occur during any given run of the program.  In other words, if you run the program and everything "looks fine" the program may be ok or there may be a problem (such as a race condition) that you just happened to not see during that run of the program. 
    Because of this you're strongly encouraged to focus on analyzing the code for problems (instead of running the program and trying to detect problems in each specific run).
    ( This blue highlighted material was added on August 3rd, after it was discussed in class. )

 

There is an example of how to use the Process Problem Chart here. 
The source code for the above example is provided here.
(This blue highlighted material was added on August 1st - if it's useful please use it BUT if you've already got good answers then don't worry about it)

 

Finding and Fixing Errors With The Semaphore-Based Bounded Buffer Problem

Click here to get download .ZIP containing just the material that we're looking at for this part of the lab

Note/Citing my sources: I obtained the above materials from a subdirectory of the 'Ch6' materials at the publisher's website.  Students: Please ignore this link and use the one that's highlighted in yellow, above :)

For each of the following questions please explain whether or not a problem can occur when the provided code is changed.  

  1. Describe a problem that would happen if one of the lines containing .release() were left out.
    For this question pick a single line to remove (instead of removing all the lines)
    E.g, describe a problem that would result from leaving line 62 (mutex.release();) out of the code.
    Or line 63 (full.release();), or any other line that contains .release().
    1. Make sure that you start by clearly stating which line you're leaving out.  Do this by stating both the line number and a quick description of what that line does (in your own words).
  2. Describe a problem that would happen if the mutex variable was left out.
  3. Describe a problem that would happen if you reversed lines 62 and 63, so that the program read:
    full.release(); // this is the old line 63, but now it's line 62
    mutex.release();
Finding and Fixing Errors With The Dining Philosophers Problem

Answer these questions the same way that you answered questions in the previous part of the lab.

  1. On pages 267-268 the textbook mentions that when a process in a monitor calls the signal method that the signaling process can either signal and wait or signal and continue.  On page 268 the textbook mentions that Concurrent Pascal instead uses a third option: the signaling process exits the monitor when signal is executed. 
    Let's imagine that by 'exit the monitor' what the author really meant is that the signaling process will exit the function (instead of being put back in the wait queue).  E.g., in the code in Figure 6.26 (on page 269), in the returnForks() method's call to first test(), calling signal would in fact exit both test() and returnForks().
    Will this interpretation cause a problem?

3. Writing Synchronized, Multithreaded Code

Click here to download the .ZIP file containing the starter project this part of the lab

In this section of the homework assignment you will solve the Dining Philosopher's problem in Java with a monitor-style class.

IMPORTANT NOTE: It is not enough to solve this problem somehow, anyhow.  You must solve this problem using a monitor.  In  particular, you are not allowed to solve this problem using the semaphore-based approach that was explained to you in class.

Before attempting to code up your solution you should of course read the relevant sections of the textbook, and then investigate your options for solving this problem in Java.  It would be a good idea to read through the API defined in the starter project and/or the test code in that starter project.

Part A: Investigating Java support for solving the Dining Philosophers problem

For this part you should investigate the following options for solving this problem.  For each of the following put write a brief comment about how you could use it to solve the problem, along with a short list of pros & cons for each one.

  1. synchronized / wait / notify / notifyAll
  2. counting semaphores
  3. reentrant locks

Please put your answers into a file named DiningPhilosophers.docx (or .pdf, etc), in a section named "Investigating Java Synchronization".

Step B: Explaining your solution

In the same file (DiningPhilosophers.docx) put in a section named "How My Solution Works".  In this section you must clearly do two things:

  1. Clearly explain, in your own words, how your solution works
    Your goal is to write this so that the grader can read your explanation, can verify that your algorithm works, and can then quickly and easily verify that the  source code you wrote in the next part accurately implements that algorithm.
     
  2. Cite your sources.
    This includes referencing books you've used (if any) and websites that helped you figure out how to solve this problem (please include the URL for any websites).

    Important Note:     For this section of the lab you're focused on writing code to solve a particular problem.  Looking for examples elsewhere (in the book, online) and then basing your solution off of what you find is ok as long as you understand the algorithm that you're implementing.  As such, a substantial amount of the points for this section will come from you clear, original, concise-yet-insightful, explanation of your algorithm.  This must be written in your own words and display a real understanding of how you solved the problem.
     

Step C: Write the code

Finally, you need to write up a solution to the problem in Java. 

You must download the starter project provided above (in the yellow highlighted link) and implement the DiningPhilosophers class inside the DiningPhilosophers.java file.  You must make sure that your code passes all the tests defined in that starter project.  There are comments in the starter files explaining what each test does, and the API that you're expected to implement is described here:

Note: You do not need to use IntelliJ to do this lab if you don't want to, but you still need to make sure that your solution passes all the tests provided in the starter project.

Method Explanation
public DiningPhilosophers(int nPhilosophers) When the DiningPhilosophers object is created this constructor is called; the parameter specifies how many philosophers will be sitting at the table.
public void takeForks(int i) Remember that each 'philosopher' will be represented in Java as a separate thread.  Each thread will call takeForks when that philosopher wishes to begin eating.  It is expected that each thread will store an 'id number' that it will pass to takeForks.
If a given philosopher cannot eat immediately then it should block, waiting until it's a good time for it to eat.
public void returnForks(int i) When a given philosopher (thread) is done eating it calls this method to tell the DiningPhilosophers object that it's finished.
public int numPhilosophers() This method is used by the test code, in order to know how many philosophers are sitting at the table. 
Your method return the number of philosophers at the table (this will be the same number as the nPhilosophers parameter that was passed to the constructor)
public DiningState getDiningState(int i) This method is used by the test code, in order to verify that the philosophers are doing the right thing after a given API call.  The possible responses are:
DiningState.EATING (if the philosopher called takeForks AND successfully picked up the left and right chopsticks, and is not currently eating).
DiningState.THINKING (if the philosopher is neither eating nor attempting to eat.  This will happen either when the thread has never called takeForks, or else after calling both takeForks and then returnForks)
DiningState.HUNGRY (if the philosopher called takeForks but was unable to obtain both the left and right chopstick, and it now blocked (waiting) for a chopstick to become available).

 

Step D: Debug your code

First, you should aware that the test code is pretty "rough" - it works but is not polished.  This is on purpose - most test code used in production environments isn't super-well maintained and so it's good to get used to dealing with 'quick and dirty' code.

Second, you should anticipate that you will need to spend a substantial amount of time debugging your code.  It's certainly possible to write the code correctly and have it all work right the first time (and/or to find your problem(s) quickly), but debugging multithreaded code can be very difficult. 

Part of what makes debugging this code is just that it's hard to figure out what each thread is doing, and when.  It doesn't help that the debugger can alter how things happen (either because of what the debugger is doing, or because the debugger hit a breakpoint and then you stared at the code for a minute)(if you do use a debugger make sure that you search the Internet for advice on how to switch threads, and then MAKE SURE YOU'RE ON THE RIGHT THREAD!!! :)  )

I instead recommend adding lots of 'print' statements (aka 'logging') to your code, so that your program will produce a 'trace' or a 'transcript' of what it's done.  You can then run the program normally (without the debugger) and examine all the output on the console to try and figure out what happened.

In order to make this easy to do the starter project includes a method named 'Main.TPrint':

public class Main {

    private static boolean DEBUG = true;
    // Print the message and the thread that's executing this code
    // This is used for debugging purposes
    public static void TPrint(String msg) {
        if( DEBUG )
            System.out.println(Thread.currentThread().getName()+": " +msg);
    }

This will print out both your message and the thread that is running this code.  If you want to turn off all of these debugging messages simply set the DEBUG variable to be false.

A typical example of using the TPrint method is:

public void takeForks(int i) {
    Main.TPrint( "TakeForks:   i=" + i);
}

Notice that because the TPrint method is static you need to call it by listing the name of the class ("Main.TPrint") instead of listing an individual object.

4. What to Turn In

5. Grading Guide

Lab_3_Grading_Template.txt is the grading guide for the assignment 3.
Note that the grading guide here may override the percentages described in the Canvas page (link below).

6. Note

Visit the Canvas page about general assignment information in order to double-check your working environment and turn-in procedure

 

Link to previous HW (for formatting, etc)