Simple LinkedList and Queue synchronization

Question

For a college Assignment I need to implement part of a hospital patient waiting system.The system uses a Collection of Patients on a waiting list, and a set of Patients registered for an operation during a specified period, for example this year.

I have implemented the method required as below, using a HashSet and a LinkedList. The method is almost completely synchronized, so I am wondering if there is a more efficient implementation with less synchronization, or perhaps more granular read write synchronization using locks?

public Class OperationPeriod {
...
private Set<Patient> registeredPatients=new HashSet<Patient>();
private Collection<Patient> waitingListPatients=new LinkedList<Patient>();
    private int capacity;
...

    public boolean bookOperation(Patient patient){
    if (!Operation.checkHasMetRequirements(patient)) {
        return false;
    }

    //patient could already be registered
    synchronized(this) {
        if(registeredPatients.contains(patient)) {
            return true;
        }
        if(waitingListPatients.contains(patient) ) {
            return false;
        }
        //Not already registered so register or add to waiting list
        return addPatient(patient);
    }
}

private boolean addPatient(Patient patient) {
    if(registeredPatients.size() < capacity) {
        registeredPatients.add(patient);
        return true;
    }
    else {
        waitingListPatients.add(patient);
        return false;
    }
}

Why don't you use a BlockingQueue, no need to maintain 2 data structures and bother about synchronization — Nitin Dandriyal
– Nitin Dandriyal, Commented Nov 13, 2013 at 2:59
Its a college assignment, I have to use the collection and set as its part of the requirements, but thanks anyway. — user2977365
– user2977365, Commented Nov 13, 2013 at 3:04

Paul Draper · Accepted Answer · 2013-11-13 02:31:33Z

1

You only have some of your code here, but your synchronization looks good.

FYI, your LinkedList.contains takes O(n). I would do one of the following

Use a LinkedHashSet which has constant lookup, but maintains the order. However, depending on your use of this later, this might not be satisfactory.
Use a HashSet to augment your LinkedList. Use the LinkedList except when checking .contains().

answered Nov 13, 2013 at 2:31

Paul Draper

84.2k53 gold badges216 silver badges303 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user2977365 Over a year ago

A LinkedHashSet is a really nice idea. Thanks for pointing that out. It also provides constant remove, which is useful for when a patient booking is cancelled. Why do you say it may not be satisfactory for other uses? Do you mean if the queue needs to be ordered in a different order to the insertion order e.g. natural order? Or maybe if I wanted a reinsertion of an element (without removal and reinsertion) at a later point in the queue?

Paul Draper Over a year ago

@user2977365, if you intend to use it as a FIFO queue, it will work great (create an iterator, call next, then call remove). If you need all the functionality of LinkedList, like a FILO queue, then it is not a good fit.

Glenn Lane · Accepted Answer · 2013-11-13 02:59:16Z

1

You could consider a read/write lock... but choosing that depends on your expectations of how often users will be only reading the collections, versus reading and writing.

A. How many times users try to add a patient that already exists (read)

B. How often you'll be reading the lists from another part of your application not shown above (read)

C. How many times users successfully add a patient (read + write)

If (A + B) is huge when compared to C, consider a read/write lock like java.util.concurrent.locks.ReentrantReadWriteLock. Call readLock() to start your reading (which only blocks writers, not other readers), and if necessary, release the read lock and call writeLock() to escalate to writing (thereby blocking all other reads and writes). After obtaining the write lock, be sure to re-check your assertions you checked during the read-lock stage.

That aside, your existing synchronization looks fine.

edited Nov 13, 2013 at 2:59

answered Nov 13, 2013 at 2:37

Glenn Lane

4,06022 silver badges32 bronze badges

2 Comments

Paul Draper Over a year ago

Read/write locks are really only beneficial if there are many, many more reads than writes. That is why the Java's synchronized Collections do not use them (stackoverflow.com/questions/11638233/…)

user2977365 Over a year ago

IMHO This is a good and well explained answer.Thanks for clarifying, I thought this was the case but wasn't completely confident of the implementation. As it stands right now, in my app (A + B) < C, but this good to know.

TwoThe · Accepted Answer · 2013-11-14 14:02:47Z

One idea would be a ReadWriteLock. Because in this part of the code:

synchronized(this) {
  if(registeredPatients.contains(patient)) {
    return true;
  }
  if(waitingListPatients.contains(patient) ) {
    return false;
  }
  //Not already registered so register or add to waiting list
  return addPatient(patient);
}

you are blocking access to the entire list, even though just reading on the list wouldn't cause any threading issues, but then you need to lock just in case the instruction could write later on. This is solved by the ReadWriteLock, by granting unlimited read access unless someone actually wants to write. This could be implemented like this:

lock.readLock().lock();
try {
  if(registeredPatients.contains(patient)) {
    return true;
  }
  if(waitingListPatients.contains(patient) ) {
    return false;
  }
} finally {
  lock.readLock().unlock();
}

//Not already registered so register or add to waiting list
lock.writeLock().lock();
try {
  // need to re-check here, as the list could have been changed in between
  if(registeredPatients.contains(patient)) {
    return true;
  }
  if(waitingListPatients.contains(patient) ) {
    return false;
  }
  return addPatient(patient);
} finally {
  lock.writeLock().unlock();
}

Now if many threads only need to read, but rarely write, this will increase the speed of your application. If almost all threads that read as well write, this would actually slow things down, as you not only need to check twice, but as well need to lock twice. In addition synchronized is faster than lock.

Collectives™ on Stack Overflow

Simple LinkedList and Queue synchronization

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related