Homework Assignment #3 [55 points]

Overview

This is an assignment in which you reason about thread-safety in the context of a HashMap implementation.

How/What to turn in

You should turn in a PDF or plain text file with your answers in Laulima.

Overview and semantics

You join a company that, for some reason, has an in-house implementation of a Linked List of integer, and we consider the insert() and the lookup() operations only. In this assignment we consider using/modifying this implementation in a multi-threaded scenario.

For doing so, we define the correctness semantics of our Linked List precisely as follows:

• An item is considered to have been inserted in the list once insert() has returned;
• A call to lookup() is correct if it does the right thing (it says “I find the item” or “I didn’t find the item”) based on the state of the linked list when the call was placed.

What the above means is that a call to lookup() should “ignore” subsequent calls to insert().

Question #1 [10 pts]: Not thread-safe

Here it the pseudo-code of the Linked List:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// Node class
class Node {
    int content; 
    Node next;  
}

// List class
class List {

    Node head = NULL;

    // Returns true on success, false on failure
    bool insert(int x) {

        Node new_node = new Node;
        if (new_node == NULL) {
            return false; // out of memory!
        } 
        new_node.content = x;
        new_node.next = this.head;
        this.head = new_node;
        return true;
    }

    // Returns true on success, false on failure
    bool lookup(int x) {
        Node curr = this.head;
        while (curr != NULL) {
            if (curr.content == x) {
                return true;
            }
            curr = curr.next;
        }
        return false;
    }
}

Explain why this implementation is not thread-safe. Do so assuming a multi-threaded program with a single linked list in RAM that runs on a single-core machine, giving a precise scenario (i.e., starting state of the queue, what each thread does, when context-switching happens, referecing line numbers, etc.).

Question #2 [10 pts]: Thread-safe?

A new implementation is produced by your co-worker, which attempts to make it all thread-safe:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// Node class
class Node {
    int content; 
    Node next;  
}

// List class
class List {

    Node head = NULL;
    Lock mutex; 

    // Returns true on success, false on failure
    bool insert(int x) {

        mutex.lock();
        Node new_node = new Node;
        if (new_node == NULL) {
            return false; // out of memory!
        } 
        new_node.content = x;
        new_node.next = this.head;
        this.head = new_node;
        mutex.unlock();
        return true;
    }

    // Returns true on success, false on failure
    bool lookup(int x) {
        mutex.lock();
        Node curr = this.head;
        while (curr != NULL) {
            if (curr.content == x) {
                return true;
            }
            curr = curr.next;
        }
        mutex.unlock();
        return false;
    }
}

Explain why this implementation is incorrect, and how to fix it by only adding two lines of code. For each line, indicate what it should be and in between which other two lines it should be inserted. (Each of these lines of code fixes the same problem, in two different places in the code.)

Question #3 [25 pts]: Shorter critical section

As you know, making critical sections shorter is useful to make programs more concurrent (and thus more efficient on multi-core machines). Answer the following questions, which pertain to your fixed implementation from the previous question:

1. Is it safe to swap the first two lines of the lookup() method to make the critical section shorter? Explain why or why not.

2. Give a modified implementation of the insert() method that makes the critical section as short as possible. (Don’t got for something insane and/or beyond where we’re currently at in the course material! Keep it simple)

Question #4 [10 pts]: More locks

One limitation of the current implementation is that only one thread can do a lookup at a time, and yet a lookup can take a long time since it’s a full list traversal. So it would be a good idea to allow concurrent lookups. Here is an idea for implementing concurrent lookups:

• Instead of having a single lock for the entire list, we now have now one lock for each node in the list;
• When traversing the list, the code first grabs the next node’s lock and then releases the current node’s lock.

This way, multiple threads can be traversing the list at the same time (as a convoy), thus vastly enhancing concurrency.

Let us assume we have implemented (corredctly) the above. Answer these two questions

1. Even if this new implementation boosted performance dramatically, there would still be one big drawback. What is this drawback?

2. Explain why the performance gain may not be as great as one might imagine in spite of concurrency being vastly enhanced (think of the single-thread execution). For extra credit, can you think of some compromise solution?