+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
f5b5dc4
master
1// jkj858 2// jbr2558 3 4import java .util .concurrent .Semaphore ; 5import java .util .concurrent .locks .*; 6 7public class PriorityQueue { 8final Node head ; 9final Semaphore notEmpty ; 10final Semaphore notFull ; 11 12public PriorityQueue (int maxSize ) { 13head =new Node ("Head" ,10 ); 14head .next =new Node ("Tail" , -1 ); 15notEmpty =new Semaphore (0 ); 16notFull =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. 23public int add (String name ,int priority ) { 24try { 25notFull .acquire (); 26 }catch (InterruptedException e ) {e .printStackTrace (); } 27 28head .lock (); 29int index =0 ; 30Node curr =head ; 31 32// find the insertion point (bailing if we find a duplicate) 33while (curr .next .priority >priority ) { 34if (curr .next .name .equals (name )) { 35curr .unlock (); 36notFull .release (); 37return -1 ; 38 } 39// move the lock to the next node making sure no one can swap it out 40// from under us 41curr .next .lock (); 42Node prev =curr ; 43curr =curr .next ; 44prev .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 51curr .next .lock (); 52Node temp =curr .next ; 53while (temp .priority != -1 ) { 54if (temp .name .equals (name )) { 55temp .unlock (); 56curr .unlock (); 57notFull .release (); 58return -1 ; 59 } 60temp .next .lock (); 61Node prev =temp ; 62temp =temp .next ; 63prev .unlock (); 64 } 65temp .unlock (); 66 67// finally insert the new node and remove the lock 68temp =curr .next ; 69curr .next =new Node (name ,priority ); 70curr .next .next =temp ; 71notEmpty .release (); 72curr .unlock (); 73return index ; 74 } 75 76// Returns the position of the name in the list; 77// otherwise, returns -1 if the name is not found. 78public int search (String name ) { 79head .lock (); 80Node curr =head ; 81for (int i =0 ;curr .next .priority != -1 ; ++i ) { 82// swap the lock to the next node 83curr .next .lock (); 84Node prev =curr ; 85curr =curr .next ; 86prev .unlock (); 87// ... and check its name 88if (curr .name .equals (name )) { 89curr .unlock (); 90return i ; 91 } 92 } 93curr .unlock (); 94return -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. 99public String getFirst () { 100try { 101notEmpty .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 106head .lock (); 107head .next .lock (); 108Node temp =head .next ; 109temp .next .lock (); 110head .next =temp .next ; 111head .next .unlock (); 112temp .unlock (); 113head .unlock (); 114 115notFull .release (); 116return temp .name ; 117 } 118 119@ Override 120public String toString () { 121String str ="[" ; 122Node curr =head .next ; 123while (curr .next .priority != -1 ) { 124str +=curr .toString () +", " ; 125curr =curr .next ; 126 } 127return str +curr .toString () +"]" ; 128 } 129 130class Node { 131public String name ; 132public int priority ; 133public Node next ; 134private ReentrantLock lock ; 135 136public Node (String name ,int priority ) { 137this .name =name ; 138this .priority =priority ; 139lock =new ReentrantLock (); 140 } 141public void lock () {lock .lock (); } 142public void unlock () {lock .unlock (); } 143@ Override 144public String toString () { 145return name +":" +priority ; 146 } 147 } 148}