Thomas Becker's Free Software Utilities

A Semaphore with Priority Levels for Win32

A Win32 semaphore (not to be confused with semaphores in the sense of Unix or in the sense of the progenitors of concurrent programming such as Hoare and Dijkstra) is a synchronization primitive which maintains a count between zero and a fixed maximum that is specified upon construction of the semaphore. Any thread can increment the count at any time, except that an attempt to increment the count beyond its maximum will fail. Decrementing the count, however, amounts to a wait operation. If the count is currently greater than zero, the wait operation completes immediately and the count is decremented. Otherwise, the thread is blocked until some other thread increments the count.

A classical application is the Win32 implementation of the fixed-length producer-consumer queue. In this implementation, an ordinary lock protects concurrent access to the queue itself, while two semaphores prevent producer threads from accessing the queue when it is full and consumer threads from accessing it when it is empty.

Another example is a situation where you have multiple threads accessing a resource such as a database, but your number of licenses for concurrent access of the resource is less than the potential number of threads trying to access it. A semaphore whose maximum count equals the number of licenses that you possess is the perfect solution.

Now suppose that you have a server application that can be used concurrently by a certain limited number of clients. Serving client requests involves access to a database, but you have fewer licenses for concurrent database access than there are potential concurrent users. This is exactly the situation described in the previous paragraph. But now suppose that in addition, you want to give different client requests different priorities when accessing the database. This could become necessary when all your clients are equal, but some are more equal than others. A more realistic—and perhaps more acceptable—reason for wanting different priority levels occurs when there are two kinds of client requests: one that needs only a short trip to the database to retrieve a list of options, and another, potentially lengthier one, to retrieve actual data when the client has chosen from the options. In this situation, you can enhance the client experience of your service by giving priority to the short requests. This is of course assuming that the entire system including client software is under your control and that the total number of concurrent client requests is limited; otherwise, there would be starvation issues. (My semaphore with priorities actually provides some assisstance in dealing with starvation issues, but there are no general solutions in situations with starvation potential.)

I once worked on a project that encountered exactly the situation described above. The whole thing never came to fruition, but I found the problem intriguing enough that I wrote a solution for Win32 on my own time and wrote about it in C/C++ Users Journal. The download below includes C++ source and HTML documentation.

Download the semaphore with priority levels for Win32