The Following is to be implemented using JAVA - CONCURRENCY

Q5 We have seen in Lecture 10 how to implement a set data structure using linked lists. We first showed an implementation that worked for sequential access, and then different linked set implementations allowing for parallel access. Figures 7 and 8 show one such implementation: a "fine-grained locking" implementation of parallel linked sets. This implementation extends the SequentialSet class seen in the course (the methods rawAdd, rawHas and rawRemove are methods defined in the Sequential Set class to add an element to the set, check whether an element is in the set, and remove an element from the set, respectively). (Part a) (10 p). The implementation contains 2 errors. Find them and propose a fix. You don't need to rewrite the whole program: If the error is on a specific line just point out that ("Error in Figure X, line Y") and write down the correct line which is intended to replace the faulty one. If the error is about some missing piece of code, just indicate in between which lines the missing code should be inserted (Code missing in Figure X, in between lines Y1 and Y2') and provide the new code to be inserted in that place. If the error is about reordering two more lines, indicate which lines are the faulty ones ("Wrong order in Figure X, in between lines Y1 and Y2") and provide the right code to be inserted in their place (Part b) (10 p). Let us assume that you want to implement a queue and use a linked list as the underlying data structure. You look at the implementation of the fine-grained locking version of a parallel linked set the correct version of the code shown in Figures 7 and 8) for inspiration, and you want to refactor it. In particular, you want to implement an unbounded queue (instead of a set), and you will then write a class Queue, Background: A queue is a FIFO (First In, First Out) data structure with the following operations: enqueue (Q,E): Adds element E to the queue Q. (It gives as result the updated new queue.) dequeue (Q): It retrieves (removes) an element of the queue. The el- ements are popped (dequeued) in the same order in which they are pushed (enqueued). If the queue is empty, then it is said to be an Un- derflow condition and no element is given; otherwise it gives as result the dequeued element. 10 The implementation of a lock-free queue data structure (a class Queue without using locks) presented in Lecture 11 is a paradigm of how to implement a parallel queue in every object oriented lan- guage, being unconditionally correct. front(Q): Get the front element from the queue Q without removing it. rear(Q): Get the last element from the queue Q without removing it. We say that a queue is unbounded when there is no limit on the number of elements it might contain (you can always enqueue a new element). In what follows you will get 10 assertions concerning the implementa- tion of a class Queue that allows for parallel access. The assertions are both general statements about such an implementation and also re- lated to the possibility of reusing the code for sets (the correct version of the code shown in Figures 7 and 8): refactoring FineSet into a new class Queue. For each assertion, you need to say whether it is correct or not. You need to justify your answer in each case. NOTE: An answer without a justification will not be granted full points. 1 The enqueue method will be exactly the same as the add method (just changing names). In other words, can you use add as it is to implement enqueue? 2 You don't need to use a key in the queue data structure as the elements don't need to be added in order according to the key. 3 The dequeue method is different from the remove among other things because in a queue we don't need to remove elements from the middle of the linked) data structure. 4 Implementing a Queue class by refactoring the FineSet class is a bad idea since there are too many changes to be made (not much can be reused). 5 A class Queue that implements a linked queue that supports parallel access requires the use of locks in other words, it is im- possible to program a linked queue that supports parallel access without using locks). 6 As for FineSet, any implementation of a class Queue allow- ing for parallel access might get an inconsistency if one thread tries to add (enqueue) an element while another tries to remove (dequeue) it. 7 Adding (enqueuing) an element on a parallel queue is not prob- lematic in general if the list has four elements or more. 8 The implementation of a class Queue allowing for parallel ac- cess cannot be implemented with semaphores. 9 It is not possible to implement a class Queue allowing for par- allel access without using CAS (compare-and-set) operation. 1 package sets; 2 3 public class FineSet extends SequentialSet 4 { 5 public FineSet() { 6 super(); 7 } 8 9 @Override 10 protected Position find (Node start, int key) { 11 Node pred, curr; 12 pred = start; 13 pred. lock(); 14 curr = start.next(); 15 curr. lock(); 16 while (curr.key() (pred, curr); 23 } 24 25 @Override 26 public boolean add(T item) { 27 Node node = newNode (item); 28 Node pred = null, curr = null; 29 try { 30 Position where = find(head, node. key(); 31 pred = where.pred; 32 curr = where.curr; 33 return rawAdd(pred, curr, node); 34 } finally { 35 pred. unlock(); 36 curr.unlock(); 37 } 38 } 39 40 code continues in Figure 5. Figure 7: Q5: A "fine-grained locking implementation of parallel linked sets. 1 2 3 4 5 6 7 8 9 @Override public boolean remove(T item) { int key = item. hash Code(); Node pred = null, curr = null; try { Position where = find(head, key); pred = where.pred; curr = where.curr; return rawRemove (pred, curr, key); } finally { pred. unlock(); curr.unlock(); } } 10 11 12 13 14 15 16 17 18 19 20 21 @Override public boolean has (T item) { int key = item.hashCode(); Node pred = null, curr = null; try { Position where = find(head, key); pred = where.pred; curr = where.curr; return rawHas(curr, key); } finally { } } 22 23 24 25 26 27 28 29 30 @Override protected Node newNode (T item) { return new LockableNode (item); } 31 32 33 34 35 @Override protected Node newNode(int key) { return new LockableNode-> (key); } 36 37 38 } Figure 8: Q5: A "fine-grained locking implementation of parallel linked sets. [CONT.) Q5 We have seen in Lecture 10 how to implement a set data structure using linked lists. We first showed an implementation that worked for sequential access, and then different linked set implementations allowing for parallel access. Figures 7 and 8 show one such implementation: a "fine-grained locking" implementation of parallel linked sets. This implementation extends the SequentialSet class seen in the course (the methods rawAdd, rawHas and rawRemove are methods defined in the Sequential Set class to add an element to the set, check whether an element is in the set, and remove an element from the set, respectively). (Part a) (10 p). The implementation contains 2 errors. Find them and propose a fix. You don't need to rewrite the whole program: If the error is on a specific line just point out that ("Error in Figure X, line Y") and write down the correct line which is intended to replace the faulty one. If the error is about some missing piece of code, just indicate in between which lines the missing code should be inserted (Code missing in Figure X, in between lines Y1 and Y2') and provide the new code to be inserted in that place. If the error is about reordering two more lines, indicate which lines are the faulty ones ("Wrong order in Figure X, in between lines Y1 and Y2") and provide the right code to be inserted in their place (Part b) (10 p). Let us assume that you want to implement a queue and use a linked list as the underlying data structure. You look at the implementation of the fine-grained locking version of a parallel linked set the correct version of the code shown in Figures 7 and 8) for inspiration, and you want to refactor it. In particular, you want to implement an unbounded queue (instead of a set), and you will then write a class Queue, Background: A queue is a FIFO (First In, First Out) data structure with the following operations: enqueue (Q,E): Adds element E to the queue Q. (It gives as result the updated new queue.) dequeue (Q): It retrieves (removes) an element of the queue. The el- ements are popped (dequeued) in the same order in which they are pushed (enqueued). If the queue is empty, then it is said to be an Un- derflow condition and no element is given; otherwise it gives as result the dequeued element. 10 The implementation of a lock-free queue data structure (a class Queue without using locks) presented in Lecture 11 is a paradigm of how to implement a parallel queue in every object oriented lan- guage, being unconditionally correct. front(Q): Get the front element from the queue Q without removing it. rear(Q): Get the last element from the queue Q without removing it. We say that a queue is unbounded when there is no limit on the number of elements it might contain (you can always enqueue a new element). In what follows you will get 10 assertions concerning the implementa- tion of a class Queue that allows for parallel access. The assertions are both general statements about such an implementation and also re- lated to the possibility of reusing the code for sets (the correct version of the code shown in Figures 7 and 8): refactoring FineSet into a new class Queue. For each assertion, you need to say whether it is correct or not. You need to justify your answer in each case. NOTE: An answer without a justification will not be granted full points. 1 The enqueue method will be exactly the same as the add method (just changing names). In other words, can you use add as it is to implement enqueue? 2 You don't need to use a key in the queue data structure as the elements don't need to be added in order according to the key. 3 The dequeue method is different from the remove among other things because in a queue we don't need to remove elements from the middle of the linked) data structure. 4 Implementing a Queue class by refactoring the FineSet class is a bad idea since there are too many changes to be made (not much can be reused). 5 A class Queue that implements a linked queue that supports parallel access requires the use of locks in other words, it is im- possible to program a linked queue that supports parallel access without using locks). 6 As for FineSet, any implementation of a class Queue allow- ing for parallel access might get an inconsistency if one thread tries to add (enqueue) an element while another tries to remove (dequeue) it. 7 Adding (enqueuing) an element on a parallel queue is not prob- lematic in general if the list has four elements or more. 8 The implementation of a class Queue allowing for parallel ac- cess cannot be implemented with semaphores. 9 It is not possible to implement a class Queue allowing for par- allel access without using CAS (compare-and-set) operation. 1 package sets; 2 3 public class FineSet extends SequentialSet 4 { 5 public FineSet() { 6 super(); 7 } 8 9 @Override 10 protected Position find (Node start, int key) { 11 Node pred, curr; 12 pred = start; 13 pred. lock(); 14 curr = start.next(); 15 curr. lock(); 16 while (curr.key() (pred, curr); 23 } 24 25 @Override 26 public boolean add(T item) { 27 Node node = newNode (item); 28 Node pred = null, curr = null; 29 try { 30 Position where = find(head, node. key(); 31 pred = where.pred; 32 curr = where.curr; 33 return rawAdd(pred, curr, node); 34 } finally { 35 pred. unlock(); 36 curr.unlock(); 37 } 38 } 39 40 code continues in Figure 5. Figure 7: Q5: A "fine-grained locking implementation of parallel linked sets. 1 2 3 4 5 6 7 8 9 @Override public boolean remove(T item) { int key = item. hash Code(); Node pred = null, curr = null; try { Position where = find(head, key); pred = where.pred; curr = where.curr; return rawRemove (pred, curr, key); } finally { pred. unlock(); curr.unlock(); } } 10 11 12 13 14 15 16 17 18 19 20 21 @Override public boolean has (T item) { int key = item.hashCode(); Node pred = null, curr = null; try { Position where = find(head, key); pred = where.pred; curr = where.curr; return rawHas(curr, key); } finally { } } 22 23 24 25 26 27 28 29 30 @Override protected Node newNode (T item) { return new LockableNode (item); } 31 32 33 34 35 @Override protected Node newNode(int key) { return new LockableNode-> (key); } 36 37 38 } Figure 8: Q5: A "fine-grained locking implementation of parallel linked sets. [CONT.)