+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

Joseph RyanFinish 3f5b5dc4

master
4.2 KiB148 linesraw
1// jkj858
2// jbr2558
3
4import java.util.concurrent.Semaphore;
5import java.util.concurrent.locks.*;
6
7public class PriorityQueue {
8    final Node head;
9    final Semaphore notEmpty;
10    final Semaphore notFull;
11
12    public PriorityQueue(int maxSize) {
13        head = new Node("Head", 10);
14        head.next = new Node("Tail", -1);
15        notEmpty = new Semaphore(0);
16        notFull = new Semaphore(maxSize);
17    }
18
19    // Adds the name with its priority to this queue.
20    // Returns the current position in the list where the name was inserted;
21    // otherwise, returns -1 if the name is already present in the list.
22    // This method blocks when the list is full.
23    public int add(String name, int priority) {
24        try {
25            notFull.acquire();
26        } catch (InterruptedException e) { e.printStackTrace(); }
27
28        head.lock();
29        int index = 0;
30        Node curr = head;
31
32        // find the insertion point (bailing if we find a duplicate)
33        while (curr.next.priority > priority) {
34            if (curr.next.name.equals(name)) {
35                curr.unlock();
36                notFull.release();
37                return -1;
38            }
39            // move the lock to the next node making sure no one can swap it out
40            // from under us
41            curr.next.lock();
42            Node prev = curr;
43            curr = curr.next;
44            prev.unlock();
45            ++index;
46        }
47
48        // now go through the rest of the queue to make sure there arent
49        // duplicates we leave the lock back at the insertion point so no one
50        // can progress
51        curr.next.lock();
52        Node temp = curr.next;
53        while (temp.priority != -1) {
54            if (temp.name.equals(name)) {
55                temp.unlock();
56                curr.unlock();
57                notFull.release();
58                return -1;
59            }
60            temp.next.lock();
61            Node prev = temp;
62            temp = temp.next;
63            prev.unlock();
64        }
65        temp.unlock();
66
67        // finally insert the new node and remove the lock
68        temp = curr.next;
69        curr.next = new Node(name, priority);
70        curr.next.next = temp;
71        notEmpty.release();
72        curr.unlock();
73        return index;
74    }
75
76    // Returns the position of the name in the list;
77    // otherwise, returns -1 if the name is not found.
78    public int search(String name) {
79        head.lock();
80        Node curr = head;
81        for (int i = 0; curr.next.priority != -1; ++i) {
82            // swap the lock to the next node
83            curr.next.lock();
84            Node prev = curr;
85            curr = curr.next;
86            prev.unlock();
87            // ... and check its name
88            if (curr.name.equals(name)) {
89                curr.unlock();
90                return i;
91            }
92        }
93        curr.unlock();
94        return -1;
95    }
96
97    // Retrieves and removes the name with the highest priority in the list,
98    // or blocks the thread if the list is empty.
99    public String getFirst() {
100        try {
101            notEmpty.acquire();
102        } catch (InterruptedException e) { e.printStackTrace(); }
103
104        // need to lock the head and the 2 following nodes so we can take out
105        // the one in between
106        head.lock();
107        head.next.lock();
108        Node temp = head.next;
109        temp.next.lock();
110        head.next = temp.next;
111        head.next.unlock();
112        temp.unlock();
113        head.unlock();
114
115        notFull.release();
116        return temp.name;
117    }
118
119    @Override
120    public String toString() {
121        String str = "[";
122        Node curr = head.next;
123        while (curr.next.priority != -1) {
124            str += curr.toString() + ", ";
125            curr = curr.next;
126        }
127        return str + curr.toString() + "]";
128    }
129
130    class Node {
131        public String name;
132        public int priority;
133        public Node next;
134        private ReentrantLock lock;
135
136        public Node(String name, int priority) {
137            this.name = name;
138            this.priority = priority;
139            lock = new ReentrantLock();
140        }
141        public void lock() { lock.lock(); }
142        public void unlock() { lock.unlock(); }
143        @Override
144        public String toString() {
145            return name + ":" + priority;
146        }
147    }
148}