0

I've recently finished a project for an Operating Systems course, but on one specific part of the project I was wondering if I made the best decision. In this project, we need to design a PID Manager.

The purpose behind a PID Manager is to assign a unique Process Identifier (PID) to a process when it is first created. When the process completes execution, the PID is returned to the PID Manager so this same PID can be reassigned to a later process. No two processes can be assigned the same PID.

The following is the interface we needed to implement:

public interface PIDManager
{

    public static final int MIN_PID = 4;
    public static final int MAX_PID = 127;

    public int getPID();
    public int getPIDWait();
    public void releasePID(int pid);
}

So getPID() simply returns a unique PID, but returns -1 if no PIDs are available. getPIDWait() returns a unique PID, but blocks the calling process until a PID becomes available. releasePID() releases the PID so that it can become available to another process that needs to use it.

We need some type of data structure to keep track of the assigned PIDs. The problem description says that this data structure needs to be free of race conditions and deadlock. For example, the same PID could be concurrently assigned to more than one process, which is something that we would not want.

So I recently finished this project. I chose to use an ArrayList to keep track of the assigned PIDs. I chose an ArrayList because the fact that it grows and shrinks in size provided a lot of convenience, making it easy to add or remove PIDs from the ArrayList and to check to see if a PID is contained within it. But now I'm not sure if an ArrayList could cause race conditions or deadlock. Would it work to use an ArrayList for this type of situation? If you would like, I can provide my implementation.

Sam Parsons
  • 537
  • 1
  • 6
  • 17
  • 2
    If you apply appropriate synchronisation/locking, then it's fine. If you don't, then it's not ;) – Oliver Charlesworth Oct 08 '13 at 23:38
  • Oh, it would probably help to add that synchronization/locking... I can't believe I didn't think of that, considering it was the main point of the chapter. Thanks. – Sam Parsons Oct 08 '13 at 23:42
  • See [How do I make my ArrayList Thread-Safe?](http://stackoverflow.com/questions/2444005/how-do-i-make-my-arraylist-thread-safe-another-approach-to-problem-in-java) SO post. – PM 77-1 Oct 08 '13 at 23:45
  • This is from the `ArrayList` javadoc: "Note that this implementation is not synchronized. If multiple threads access an ArrayList instance concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally." – ajb Oct 08 '13 at 23:46

1 Answers1

3

If I interpret your limits correctly then your PID range is 4-127 so performance-wise you would be fine using an ArrayList so long as you Lock appropriately.

A slightly more efficient use of memory would be using a BitSet. You would still need appropriate locking.

At a slight memory cost but better performance you may find one of the concurrent sets more efficient - perhaps a ConcurrentSkipListSet. You would then not need to do any locking as it is inherently thread-safe. See here for a relevant thread.

Community
  • 1
  • 1
OldCurmudgeon
  • 64,482
  • 16
  • 119
  • 213