CS 475, Spring 2018, Homework 2, Due Feb 21, 2pm Feb 23, 11:59pm

Start by downloading the handout:

Download the handout

Clarifications:

  • 2/19: Added hints for collection exceptions from threads; copying the lists when returning
  • 2/18: Strike the sentence “Finally, check that the total number of tags on all of those files matches the count returned by listTags.” from testP2ConcurrentDeleteTagTagFile
  • 2/17: Clarify in ‘help’ output, that add tag is used to “Add a tag to the list of known tags” (like the addTag method)
  • 2/14: Clarify: listAllFiles should not throw any exception (previously said “throws exception if tag does not exist”, but does not take an argument)
  • 2/13: You do not need to use any of the fields that I included on Tag or TaggedFile – this was accidental. You may find it easier to (ncurrrectly) manage relationships between tags and files a different way – you should feel free to use or remove those fields.
  • 2/13: Revised testP1AddAndListTag spec
  • 2/12: Added hint code in part 4 (Java snippet that creates a bunch of threads)
  • 2/11: catall should print the contents of each file with a line break in between. You should not print the name of each file.
  • 2/10: You are free to use any standard (java.* or javax.*) API/library
  • 2/10: You are free to add new methods or member variables to FileTagManager, Tag, TaggedFile, or ConcurrentTests. But: you must make sure that your ConcurrentTests only references the interface/abstract methods (so that OUR ConcurrentTests can run on your code)

Please post questions on Piazza

The purpose of this assignment is to get you familiar with basic concurrency control topics in Java. We will build on the concepts of HW1 (the shell), focusing specifically on building a file management system. In particular: it has recently become more and more popular to organize files by keywords and tags, rather than by their location in a hierarchical filesystem. Users of Mac OS X might find themselves turning more to using Spotlight to open documents (rather than manually locating them in a hierarchical path),  and Windows users might find themselves using Cortana to do the same.

The remainder of the assignments (and project) in this class will involve building parts of an intelligent file management tool, which you could use to browse and search through your files. We will call this tool  VCFS (VeryCoolFileSystem).

For this first assignment, your task will be to build a Java application that allows users to list and tag their files. You will build it so that multiple users can interact with it simultaneously without corrupting any of the internal structures. In the next assignment (HW3), we will re-envision VCFS to use a client-server architecture.

Your primary interface for debugging your VCFS will be a shell driver that we have provided. We have provided stubs for all of the various commands you will need to implement, with a wrapper so that you can interact with VCFS interactively. When you run the compiled jar file, you’ll get a command prompt, like this:

As you implement the various functionality in the parts below, the commands above will begin to work.

We have also provided a baseline suite of unit tests, which you can execute by calling  mvn -Ptest test

General requirements:

We have provided you a baseline implementation of VCFS that handles all user interaction, but does not do anything (that is, you will not need to implement any UI or command processors). You may not include any additional libraries (e.g. download and and require additional JARs), although feel free to use any of the various libraries included with Java 8 or already included by the starter project.

Your VCFS will be compiled and tested using apache maven, which automatically downloads the various dependencies for VCFS and executes the provided JUnit tests. Please install Maven on your computer. Unfortunately, Maven is not installed on Zeus, however you can download the most recent version (e.g. apache-maven-3.5.2-bin.zip) and unzip it in your home directory. Then, to run maven, type ~/apache-maven-3.5.2/bin/mvn in the snippets below (instead of just mvn). Note that you can easily import maven projects into eclipse and IntelliJ.

To compile and run your shell, run mvn package and then run  java -jar target/filemanager-0.0.1-SNAPSHOT.jar. You’ll notice that the text-mode interface we’ve provided for you has a handy help command

Your shell will be automatically graded for correctness (note that there will be a manual grading phase to check hard-to-automatically-catch concurrency issues). Included with your handout is a simple version of the (large) test script that we will use to grade your assignment. Upon submitting your assignment, our server will automatically compile and test your assignment and provide you with test results. You can resubmit an unlimited number of times until the deadline. To run these tests, simply execute mvn -Ptest test (of course, if you do this first off, you’ll see that they all fail!)

Note: Your code must compile and run on the autograder, under Java 8. It is unlikely that you will have any difficulties developing on a Mac, Linux or Windows. When you feel satisfied with implementing one phase of the assignment, submit to AutoLab and verify that AutoLab agrees.

Academic honesty reminder: You may NOT share any of your code with anyone else. You may NOT post your code in a publicly viewable place (e.g. in a public GitHub repository).  You may face severe penalties for sharing your code, even “unintentionally.” Please review the course’s academic honesty policy.

Tips and References

You might find it useful to reference the official Java tutorial on concurrency, which does a nice job outlining at a high level how you can create threads and locks. If you find any useful references, please feel free to share them on Piazza and we will update this page as well.

Part 1: The Tag Database (20%)

Your VCFS tool will allow users to maintain a list of Tags. In part 2, we’ll look at labeling files with tags. Users can interact with VCFS to create new tags, rename existing tags, and delete existing tags. The key focus for this part of the assignment will be to implement this functionality Thread Safe. You will likely find it very easy to implement this behavior that will work in a single-threaded situation, but it can become tricky when multiple threads are interacting with the same VCFS. Of the 20% that Part 1 will count towards your grade on this assignment, the breakdown will be roughly: 5% for implementing this functionality, and 15% for implementing it with correct concurrency control.

You will implement this behavior in  edu.gmu.cs475.FileTagManager, specifically in the following four methods:

Note the following requirements:

  1. You should feel free to add whatever methods you would like to the  Tag or  FileTagManager classes
  2. Your code must be thread-safe: concurrent calls to any of these methods (or any other method in  FileTagManager) should not have any races. If two concurrent calls are made to addTag to add the same tag, exactly one of them must throw a  TagExistsException, and the other must succeed (similarly for editTag and deleteTag). listTags must be tolerant of other threads concurrently calling add/edit/deleteTag.
  3. Your code must not over synchronize. We will deduct marks for solutions that include unnecessary locks.
  4. You must not store any state in static fields
  5. You do not need to use any of the fields that I included on Tag or TaggedFile – this was accidental. You may find it easier to (correctly) manage relationships between tags and files a different way – you should feel free to use or remove those fields.

Hint: In order to make it thread-safe to iterate over the result of listTags, you will need to return a new collection containing the entire contents of the original

Precise grading breakdown:

  • Non-Concurrent issues: 5 points
    • 8 JUnit tests, 5/8 points each
  • Concurrent issues: 15 points
    • 3 JUnit tests, 3 points each
    • 6 points from manual grading

Part 2: File Operations (20%)

Once you allow users to create and edit tags, you will implement file-oriented functionality, allowing users to browse files, tag them, and edit those tags. The first method you will implement is  init(List<Path> files);

This function will be called automatically when VCFS starts up. In init, you will initialize VCFS, creating a special starting tag “untagged.” Every file that exists (when VCFS starts) should receive this tag.

Next, implement the following five core file-oriented methods:

As with Part 1, Of the 20% that Part 2 will count towards your grade on this assignment, the breakdown will be roughly: 5% for implementing this functionality, and 15% for implementing it with correct concurrency control. Note the following requirements (generally the same as from part 1):

  1. You should feel free to add whatever methods you would like to the  Tag,  TaggedFile or  FileTagManager classes
  2. Your code must be thread-safe: concurrent calls to any of these methods (or any other method in  FileTagManager) should not have any races. If two concurrent calls are made to tagFile to add the same tag, exactly one of them must return true and the other must return false (similarly for removeTag).  getTags and  listFilesByTag must be tolerant to other threads tagging files concurrently.
  3. Your code must not over synchronize. We will deduct marks for solutions that include unnecessary locks.
  4. You must not store any state in static fields

Precise grading breakdown:

  • Non-Concurrent issues: 5 points
    • 8 JUnit tests, 5/8 points each
  • Concurrent issues: 15 points
    • 3 JUnit tests, 3 points each
    • 6 points from manual grading

Part 3: Bulk Operations (20%)

There are four remaining methods that you will need to implement, which will support the bulk operations ( echo-all and  cat-all). Note the documentation on these two methods:

These methods will require you to utilize Java  ReadWriteLocks. We ask you to put your lock and unlock code in two specific methods (for ease of testing):

Of the 30% that Part 2 will count towards your grade on this assignment, the breakdown will be roughly: 10% for implementing this functionality, and 20% for implementing it with correct concurrency control. Note the following requirements (generally the same as from part 1/2):

Again:

  1. You should feel free to add whatever methods you would like to the  Tag,  TaggedFile or  FileTagManager classes. You must not change any other files.
  2. You should use the existing  writeFile and  readFile methods (in  AbstractFileTagManager) to do the actual reading and writing. You should not be concerned with the thread-safety of  writeFile and  readFile (they are not thread safe). It is up to you to take out whatever synchronization is necessary before calling them.
  3. Your code must be thread-safe: concurrent calls to any of these methods (or any other method in  FileTagManager) should not have any races. Of particular note: we require that you guarantee that if there are two concurrent calls to echoToAllFiles (writing to the same values), all of those files will have the same value at the end, rather than some files getting overwritten by one call, then others by another call.
  4. Your code must not over synchronize. We will deduct marks for solutions that include unnecessary locks. 
  5. You must not store any state in static fields

Precise grading breakdown:

  • Non-Concurrent issues: 5 points
    • 4 JUnit tests, 5/4 points each
  • Concurrent issues: 15 points
    • 2 JUnit tests, 4 points each
    • 7 points from manual grading

Part 4: Multi-threaded test cases (40%)

We have included several functional tests that simply test the behavior of each of these methods. We have not provided any tests (for you to see) that test the behavior of your software under concurrency. One of your tasks is to write such tests.

Note that it is generally impossible to automatically prove that concurrent programs have no races, it is often to test for low-hanging fruit. For instance, you might create a handful of threads, and then repeatedly perform some operations in each thread, checking the system state to make sure that it doesn’t become corrupt. It can be difficult to get such tests to expose issues. We have written eight pretty good tests, which we used in the prior sections to grade the concurrency aspects of your code.

We are asking you to implement the same eight JUnit test cases (in the class edu.gmu.cs475.ConcurrentTests), using the inline documentation as a guide for the specification of each:

Note that we have configured this test runner automatically to (1) automatically time out each test after 10 seconds, (2) automatically detect (most) deadlocks, and (3) to repeatedly rerun tests that passed in order to attempt to increase the odds of seeing it fail.

You should perform all of your testing on the provided  FileManager instance ( edu.gmu.cs475.NonConcurrentTests.fileManager) – this field will be automatically reset for each execution of each test. You must only reference methods in AbstractFileManagerITag and  ITaggedFile (NOT  FileManagerTag, and  TaggedFile) – since we will be grading the quality of your tests by running them on implementations of VCFS with known concurrency bugs. When we run our own test suite against these known buggy implementations, every test fails on every implementation. This is what you should strive for.

We can not provide the code for the buggy implementations to you because that might (1) give you tricks to make parts 1-3 easier, and (2) once you know what is buggy, you might find it easier to write the tests. However, you are free to submit as often as you like on AutoLab and see your marks.

Hints: Here is an example Java snippet that creates a bunch of threads, then waits for them to complete. This snippet also demonstrates keeping track of the number of successful operations, the number of failed operations, and the number of exceptions reported in each thread.

Also: Keep in mind that for the autograder to detect that your test failed, you need to actually call assert*** or fail() from JUnit. You can see examples in the NonConcurrentTests.

Precise grading breakdown for part 4:

  • Tests all pass on our own (correct) implementation: 8 pts
    • 8 tests, 1 point for each test that passes
  • 3 Expected tests fail on buggy version 1: 6 pts
    • Expected failures are:
    • testP2TagFileAndListFiles: 2 pts
    • testP3ConcurrentEchoAll: 2 pts
    • testP3EchoAllAndCatAll: 2 pts
  • All tests fail on buggy version 2: 16 pts
    • 8 tests, all should fail.  2 points for each test that fails
  • Manual inspection of test quality: 10 pts

No marks will be awarded for empty tests, or tests that have no assertions (note that otherwise, these tests would all pass on our correct implementation).

Grading

Your assignment will be graded on a series of functional tests, making sure that it implements the specification above. Your tests will be graded by running them on purposely buggy code and verifying that they throw some errors, and then manually inspecting them for completeness. We have provided a (not exhaustive) test suite which should help you judge (on your own) how well you have done with the functional requirements (although not the concurrent parts). We may add additional tests beyond what we are providing you with now, so please do not rely entirely on them (in particular, again, the automated tests do not verify that your code is correctly synchronized).

In accordance with the “reasonable person principle,” we reserve the right to audit your code and correct any marks that are improperly assigned, for instance, due to your code incorrectly following the specification, but passing the test.  For instance: in HW1, there was a test that made sure that you allowed for very long argument lines (the requirement was that you allowed for arbitrarily long lines). The test had a very long line, of say, 9,000 characters. Hence, some students hard-coded their shells to accept input lines of 10,000 characters, which passes the test but does not meet the specification. We would encourage you to spend your time correctly implementing the assignment, and not trying to force it to pass the test, even if it is not following the spirit of the assignment.

Hand In Instructions

You must turn in your assignment using Autolab (You MUST be on the campus network, or connected to the GMU VPN to connect to Autolab). If you did not receive a confirmation email from Autolab to set a password, enter your @gmu.edu (NOT @masonlive) email, and click “forgot password” to get a new password.

Create a zip file of only the  src directory in your assignment (please:  .zip, not  .tgz or  .7z etc). When you upload your assignment, Autolab will automatically compile and test it. You should verify that the result that Autolab generates is what you expect. Your code is built and tested in a Linux VM. Assignments that do not compile using our build script will receive a maximum of 50%. Note that we have provided ample resources for you to verify that our view of your assignment is the same as your own: you will see the result of the compilation and test execution for your assignment when you submit it.

You can resubmit your assignment an unlimited number of times before the deadline. Note the course late-submission policy: assignments will be accepted up until 24 hours past the deadline at a penalty of 10%; after 24 hours, no late assignments will be accepted, no exceptions.

Understanding the Autolab output

You MUST be on the campus network, or connected to GMU VPN to connect to Autolab.

Autolab will give you a score across a variety of problems, with each problem scored between 0-1. This score will help you understand how well you have done implementing the assignment, but you should realize that it does not directly map to a grade on the assignment (for one thing, the test cases don’t map to the weightings provided above). We will not provide you with copies of the complete test suite this time. Since we will grade the quality of your concurrent test cases by running them on our own (correct and buggy) code, we can not distribute the auto grading script without also distributing a correct and complete implementation of parts 1-3.

Questions

Please post questions on Piazza

 

Contact