Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

My task is to implement a distributed semaphore system (links to description) and an application for it. I will be using Java sockets, and it will use watermark arrays and priority queues (not sure where), and so I am curious about how to tackle this project. Specifically, I'd like to know what is a good first-step goal, or a simple subsystem I can implement. At the moment, I just don't know where to focus my attention.

The application is a floating license system - like in a computer lab with only one copy of a software (maybe a CAD program), which allows only one PC at a time to use the software. When one machine is using the software, the access to the software is locked. When that machine is done using it, it gives it up and whomever was first in requesting should be next.

Here's the pseudo-code algorithm referenced - http://i.imgur.com/q9kRm.png

share|improve this question
1  
Sounds like a fun project. A good "first step" would be getting the app to publish its running state to the local network. Second: other apps can refuse to run while the first is running. Thirdly: apps can join a queue and wait until it's their turn. Finally: Let the apps know their place in the queue, perhaps give them the opportunity to buy a better spot. ;-) –  Sedate Alien Dec 8 '11 at 5:05

2 Answers 2

up vote 5 down vote accepted

Consider starting with "handshake" sub-system - the one that will allow licensed application running at particular machine to register a session at your license server and obtain a token uniquely identifying it for further interactions.

I think it would be reasonable for this subsystem to also include some "negotiation" about further communication protocol ("heartbeat signals will be expected to exchange at a rate between 5 and 10 seconds" - stuff like that).

Next logical step would probably be establishing kind of "heartbeat" module - the one that would allow registered machine and server to... oops sorry you asked about first-step goal that one doesn't fit.

share|improve this answer

Generic Answer

Semaphore is a resource allocation technique to manage deadlocks and race conditions via priority queues. Putting it metaphorically, you have 3 bicycles for hire. Suppose, you hire it on a first come first serve basis. So if you have hired all your 3 bicycles and a fourth person requests it, he must wait until one of them has brought the bicycle back. There are chances that you may reserve the bike for someone, someone may cancel a already reserved bike and so on. Similar in case of processes that want to acquire some resources, semaphores are used.

In case of a distributed semaphore, there could be multiple resources that could be accessed by multiple processes. Assume a server hosts an application and can host multiple instances of it and the user can use the application if it is free. Let server be S1,S2,.. Sn while the application be A1,A2,...An and users be U1,U2,...Un. So if the first server could host three instances of the application then it would be denoted as S1A1,S1A2,S1A3. Also assume the application instances as slots or boxes for easy understanding. A slot is considered empty when it is free and full when it is busy. So, in this case, the following method is suggested

  • User requests the application
  • The request is passed to a priority queue.
  • The queue runs a continuous background process to search for free slots and once a free slot is found, passes the request to the application to start processing
  • Once a slot gets the request, they mark themselves busy and starts processing and marks themselves free when they finish processing
  • The slots periodically broadcasts their status to the queue so that the queue could forward the requests once a slot becomes free

Recommended resources

  • This model is based on centralized message brokering. The queue that processes the request should always be available. There can also be broker-less model that could be implemented in a different way
  • Semaphore Programming on Wikipedia
  • The Little Book on Semaphores is a superb resources freely available
  • Semaphore is based on shared memory model. Actor Model would give a new insight to solve this problem in a different way

Specific answer to the question in context

Looking at the code, I prefer the classical version of a semaphore. Java has a built-in semaphore package to do this and you could just easily build on it.

Specifically, I'd like to know what is a good first-step goal, or a simple subsystem I can implement.

Assuming only one instance of the application should be run on the LAN

  • Use the package suggested above
  • Create the semaphore with a built-in queue mechanism (similar to a stack) and implement it as a server
  • When a user starts the application, it searches for the semaphore, decrements the count (in this case just 0 since only a single instance is to be allowed) and gives user the access to the application
  • When an other user starts the application, it searches for the semaphore, since it is 0, puts the user in the queue and gives a message to the user that the application is busy
  • When the first user exits the application, the semaphore is incremented, the resource becomes available, the user is intimated and he can now start the application.
  • The semaphore can be implemented as a stand-alone server (possibly with a simple web interface) that could be coupled with the application.

The following caveats are worth thinking

  1. Queues may be flushed entirely or priority can be changed
  2. Coupling it with the application as a server, requires there would be only one version of the server on the LAN
  3. Prepare for crashes or unattended message queues (User request access but not available when the application is free)

I would probably suggest the following for better understanding

  • Follow this link for better understanding
  • Try SCALA. You can use all your existing JAVA libraries plus you get good concurrency
  • Have a look at ZMQ. This could be the option if you abstract out the entire process into a separate messaging application that interacts with the resources
  • Read about the AutoCAD licensing system (they implement a licensing model that matches few of your requirements)

EDIT Answer completely edited since the original answer is based on a much broader perspective

share|improve this answer
    
Thank You So Much for this thorough answer. I am reading through the materials you've provided. Mainly, all I know is that the project has the implement that algorithm in figure 9.3. –  Adel Jan 13 '12 at 21:58
1  
@Adel Answer updated to match the requirement. Links also changed –  Ubermensch Jan 16 '12 at 9:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.