Homework #4

Due: Wednesday, November 9th at 11:59pm

This homework is intended to serve to practice understanding more complicated concurrent linked list implementations.

Getting started

For each assignment, a Git repository will be created for you on GitHub. However, before that repository can be created for you, you need to have a GitHub account. If you do not yet have one, you can get an account here: https://github.com/join.

To actually get your private repository, you will need this invitation URL:

When you click on an invitation URL, you will have to complete the following steps:

  1. You will need to select your CNetID from a list. This will allow us to know what student is associated with each GitHub account. This step is only done for the very first invitation you accept.

  2. You must click “Accept this assignment” or your repository will not actually be created.

  3. After accepting the assignment, Github will take a few minutes to create your repository. You should receive an email from Github when your repository is ready. Normally, it’s ready within seconds and you can just refresh the page.

  4. You now need to clone your repository (i.e., download it to your machine).

    • Make sure you’ve set up SSH access on your GitHub account.

    • For each repository, you will need to get the SSH URL of the repository. To get this URL, log into GitHub and navigate to your project repository (take into account that you will have a different repository per project). Then, click on the green “Code” button, and make sure the “SSH” tab is selected. Your repository URL should look something like this: git@github.com:mpcs52060-spr22/hw4-GITHUB-USERNAME.git.

    • If you do not know how to use git clone to clone your repository then follow this guide that Github provides: Cloning a Repository

If you run into any issues, or need us to make any manual adjustments to your registration, please let us know via Ed Discussion.

Short Answer Questions

Each assignment may include a section dedicated to answering a few short answer questions. Please turn in a readable text file named saqs (e.g., saqs.pdf). Store this file inside the hw4/saqs directory. You will place your answers to the following questions in this document. The file is not required to be a PDF but any text document that is easy to open is fine.

SAQ 1

Explain why the fine-grained locking algorithm is not subject to deadlock.

SAQ 2

Show a scenario in the optimistic algorithm where a thread is forever attempting to delete a node.

SAQ 3

Consider the following code:

type Semaphore struct {
       value int
}
func (sema *Semaphore) Down() {
   // Implementation details are hidden
   // Assume this is implemented correctly based
   // on the lecture slides.
}
func (sema *Semaphore) Up() {
   // Implementation details are hidden
   // Assume this is implemented correctly based
   // on the lecture slides.
}
var num int = 0
var sema1 Semaphore = Semaphore{0}
var mutex Semaphore = Semaphore{1}
func foo(group *sync.WaitGroup) {
   mutex.Down()
   for num == 0 {
      sema1.Down()
   }
   num--
   mutex.Up()
   group.Done()
}
func bar(group *sync.WaitGroup) {
   mutex.Down()
   num++
   sema1.Up()
   mutex.Up()
   group.Done()
}
func main() {

    var wg sync.WaitGroup
    wg.Add(2)
    go foo(&wg)
    go bar(&wg)
    wg.Wait()
}

Assume the global variables are shared variables and are accessible in both functions and are not copies.

For each statement below, answer whether the statement is True or False and provide a brief explanation:

  1. This code provides safety and liveness.

  2. This code provides safety and liveness, as long as the goroutines can be interrupted/pre-empted (i.e., descheduled).

  3. The goroutine in the bar function might never return.

  4. The goroutine in the foo function might never return.

  5. The variable num might go negative.

SAQ 4

You must finish the coding problem before attempting this SAQ. Refer back to your project #1 solution, and replace the coarse grain implementation with the lazy-list implementation. You should only need to make a few modifications to make this work. Submit your original speedup graph from project 1 and a new speedup graph that shows any speedups based on using the lazy-list implementation. Do you see any improvement in performance? Explain.

Programming Question(s)

For this assignment you are only allowed to use the following Go concurrent constructs:

  • go statement

  • sync.Mutex and its associated methods.

  • sync/atomic package. You may use any of the atomic operations.

  • sync.WaitGroup and its associated methods.

As the course progresses, you will be able to use other constructs provided by Go such as channels, conditional variables, etc. I want you to learn the basics and build up from there. This way you’ll have a good picture of how parallel programs and their constructs are built from each other. If you are unsure about whether you are able to use a language feature then please ask on Ed before using it.

Programming Problem: Lazy Feed

For the first part of project #1, you implemented a specific type of concurrent list. For this homework, we will also be implementing concurrent list using the lazy list algorithm presented in class. We will use the same starter code structure that from project #1. To recap, imagine you are a new software engineer at Twitter and your first assignment is to redesign the data structure that represents a user’s feed. Your implementation will redefine it as a lazy concurrent linked list.

Your task to implement the remaining incomplete methods of a feed (i.e. the Add, Remove, and Contains methods). Your implementation must have the following:

  1. Defines and uses the Feed interface:

    type Feed interface {
Add(body string, timestamp float64)
Remove(timestamp float64) bool
Contains(timestamp float64) bool
}

  2. Defines and uses the NewFeed function. This function returns a Feed value, which represents your lazy list.

    // NewFeed creates a empty user feed
func NewFeed() Feed {...}

How you define the struct that implements the Feed interface is up to you. There are no requirements like in project 1. Remember that you will want to define sentinel (i.e., dummy) nodes for the head and tail as presented in the lecture slides. This makes the algorithm much easier to implement. You can use math.MaxFloat64 as the maximum timestamp value and -math.MaxFloat64 as the minimum timestamp value.

Test your implementation of feed by using the test file called feed_test.go. You should only run the sequential tests first:

  • TestSimpleSeq

  • TestAdd

  • TestContains

  • TestRemove

As a reminder from prior assignments, you can run individual tests by using the -run flag when using go test. This flag takes in a regular expression to know which tests to run. Make sure are you in the directory that has the *_test.go file.

Sample run of the SimpleSeq test:

//Run top-level tests matching "SimpleSeq", such as "TestSimpleSeq".
$ go test -run "SimpleSeq"
PASS
ok    hw4/feed        0.078s

Sample run of the SimpleSeq and TestAdd tests:

//Run top-level tests matching "SimpleSeq" such as "TestSimpleSeq" and "TestAdd".
$ go test -v -run "SimpleSeq|TestAdd"
=== RUN   TestSimpleSeq
--- PASS: TestSimpleSeq (0.00s)
=== RUN   TestAdd
--- PASS: TestAdd (0.00s)
PASS
ok    hw4/feed        0.078s

You can also run specific tests by using anchors. For example to run only TestAdd then execute the following command:

$ go test -v -run ^TestAdd$
=== RUN   TestAdd
--- PASS: TestAdd (0.00s)
PASS
ok      hw4/feed      0.103s

Grading

Programming assignments will be graded according to a general rubric. Specifically, we will assign points for completeness, correctness, design, and style. (For more details on the categories, see our Assignment Rubric page.)

The exact weights for each category will vary from one assignment to another. For this assignment, the weights will be:

  • Completeness: 52%

  • Correctness: 8%

  • Design & Style: 5%

  • Short Answer Questions: 35%

Obtaining your test score

The completeness part of your score will be determined using automated tests. To get your score for the automated tests, simply run the following from the Terminal. (Remember to leave out the $ prompt when you type the command.)

$ cd grader
$ go run hw4/grader hw4

This should print total score after running all test cases inside the individual problems. This printout will not show the tests you failed. You must run the problem’s individual test file to see the failures.

Design, Style and Cleaning up

Before you submit your final solution, you should, remove

  • any Printf statements that you added for debugging purposes and

  • all in-line comments of the form: “YOUR CODE HERE” and “TODO …”

  • Think about your function decomposition. No code duplication. This homework assignment is relatively small so this shouldn’t be a major problem but could be in certain problems.

Go does not have a strict style guide. However, use your best judgment from prior programming experience about style. Did you use good variable names? Do you have any lines that are too long, etc.

As you clean up, you should periodically save your file and run your code through the tests to make sure that you have not broken it in the process.

Submission

Before submitting, make sure you’ve added, committed, and pushed all your code to GitHub. You must submit your final work through Gradescope (linked from our Canvas site) in the “Homework #4” assignment page via two ways,

  1. Uploading from Github directly (recommended way): You can link your Github account to your Gradescope account and upload the correct repository based on the homework assignment. When you submit your homework, a pop window will appear. Click on “Github” and then “Connect to Github” to connect your Github account to Gradescope. Once you connect (you will only need to do this once), then you can select the repsotiory you wish to upload and the branch (which should always be “main” or “master”) for this course.

  2. Uploading via a Zip file: You can also upload a zip file of the homework directory. Please make sure you upload the entire directory and keep the initial structure the same as the starter code; otherwise, you run the risk of not passing the automated tests.

Note

For either option, you must upload the entire directory structure; otherwise, your automated test grade will not run correctly and you will be penalized if we have to manually run the tests. Going with the first option will do this automatically for you. You can always add additional directories and files (and even files/directories inside the stater directories) but the default directory/file structure must not change.

Depending on the assignment, once you submit your work, an “autograder” will run. This autograder should produce the same test results as when you run the code yourself; if it doesn’t, please let us know so we can look into it. A few other notes:

  • You are allowed to make as many submissions as you want before the deadline.

  • Please make sure you have read and understood our Late Submission Policy.

  • Your completeness score is determined solely based on the automated tests, but we may adjust your score if you attempt to pass tests by rote (e.g., by writing code that hard-codes the expected output for each possible test input).

  • Gradescope will report the test score it obtains when running your code. If there is a discrepancy between the score you get when running our grader script, and the score reported by Gradescope, please let us know so we can take a look at it.