Monday, 30 January 2012

Thread and process synchronisation with semaphores

Semaphore is a synchronisation object that controls resource access (critical section execution) by maintaining the number (count, n) of accessors (threads or processes) (still) allowed to access the resource. While mutex strictly limits access to a single accessor at a time, semaphore allows up to N (N > 0) parallel accessors. N is defined when semaphore is being created and it represents maximum possible value of the semaphore count.

Semaphore count is changed through following operations:
  • wait() - which, on return,  decreases count on successful return (minimum is 0)
  • release() - which increases count (maximum is N)

Semaphore has two states:
  • signalled - when 0 < n <= N; wait() does not block
  • non-signalled - when n == 0; wait() blocks till semaphore gets signalled (or returns on expired timeout)

There are two types of semaphores:
  • counting - based on the count 0 <= n <= N where N > 1
  • binary - (specialisation of counting) where N == 1; when in signalled state we say it is unlocked; when in non-signalled state we say it is locked

Semaphores are signalling accessors the right of way - just as traffic semaphores, but unlike them, accessors themselves are controlling when the light for others will become green - through wait() and release() operations. Accessors are wait()-ing for a semaphore. If semaphore is signalled (n > 0), wait() returns immediately, decreasing semaphore count. When accessor (this one or any other) is finished with the shared resource it calls release() on the semaphore, increasing its count. Accessor will block on wait()-ing if semaphore is non-signalled (when maximum allowed number of accessors are sharing the resource). As soon as some accessor finishes the work and releases the semaphore, accessor's wait() will unblock and it will be allowed to access the resource.

Obviously, if N is set to 1, semaphore (called binary semaphore in this case) logically behaves like a mutex, allowing only one accessor at a time. There is a difference between two of them though: only accessor that locked the mutex can unlock it (mutex is owned by the accessor), but any accessor can release semaphore.

Majority of semaphore examples on the internet are focused on consumer-producer problem. I wanted to show use of semaphore on the example of traffic control - something that resembles the real semaphore. So, let's say we have three single-lane, one way roads joining just before a bridge which is one way but has two lanes. To reduce congestion on the bridge, traffic from only two access roads is allowed at a time. There is a semaphore with the red and green light by the each road and once it turns green, it remains in that state for some time period T. First two opened roads get green light first. As soon as the timeout expires for one of those roads and semaphore shows red, semaphore will show green for traffic that has been waiting at the third road.

Semaphore-example

We can think of roads (traffic on them) as accessors and the bridge as a resource: two roads can lead traffic to the bridge at the same time (two accessors are allowed to access shared resource). Obviously, we will set the maximum value for the semaphore count to 2 in our model. Thread will wait() as long as count is 0 but as soon as it gets increased to 1, wait() returns (decreasing count to 0 again).

This example aims to show how semaphore limits parallel access to the shared resource and how accessors (threads in this case) themselves control semaphore by wait()-ing for the semaphore and release()-ing it.

To stop threads I tend to use event object - not a flag (volatile bool variable). They are thread-safe and thread callbacks don't need to return with delay of one additional wait() cycle in the case when termination has been requested.

I wrapped event and semaphore objects (handles) into RAII-compliant classes - CScopedEvent and CScopedSemaphore.

main.cpp:




Output:

Road 1 opened
0 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
1 road(s) is(are) generating traffic...
Road 2 opened
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...
Road 3 opened
2 road(s) is(are) generating traffic...

Road 1 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 3 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 3 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 1 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 3 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 3 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 1 got red light. Waiting for a green light...
Road 3 got green light for the next 10 seconds. Generating traffic...
1 road(s) is(are) generating traffic...2 road(s) is(are) generating traffic...


Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 3 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 1 got red light. Waiting for a green light...
Road 3 got green light for the next 10 seconds. Generating traffic...
1 road(s) is(are) generating traffic...
2 road(s) is(are) generating traffic...

Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 3 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...
Closing road 3 ...
Road 3 got request to get closed
Road 3 closed
Closing road 2 ...

Road 1 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 1 got green light for the next 10 seconds. Generating traffic...
2 road(s) is(are) generating traffic...

Road 2 got red light. Waiting for a green light...
1 road(s) is(are) generating traffic...
Road 2 got request to get closed
Road 2 closed
Closing road 1 ...

Road 1 got red light. Waiting for a green light...
0 road(s) is(are) generating traffic...
Road 1 got request to get closed
Road 1 closed

The example above shows how semaphore controls access to the resource by multiple threads. But please note that resource was NOT made thread safe! Semaphore was just allowing up to N threads (2 in our case) to be active at a time (and generate the traffic towards the bridge). If we wanted to limit the number of vehicles on the bridge and to control traffic lights depending on the current bridge load, we would have had to limit the number of active threads to 1. In that case only one road would have green light at a time.

In the next example I want to show how to synchronise multiple processes in accessing shared resource. Let's say we have an app which writes some log into the file and does it in a loop. The code could look like this:

main.cpp:



If run with parameter of value e.g. "012345", this app will create text file with the following content:

test.log:

[PID = 4408] Iteration # 1 012345
[PID = 4408] Iteration # 2 012345
[PID = 4408] Iteration # 3 012345
[PID = 4408] Iteration # 4 012345
...

If we run simultaneously two or more instances of this process, they will all write into the same file, increasing its size with each write operation. Manipulator endl inserts new line character ('\n') at the end of the line and flushes the buffer to the disk. Obviously, before writing to the disk, our file stream object needs to know the current size of the file in order to move write pointer to the file end. If Process2 appends a new line to the file after Process1 reads file size but before Process1 writes into it, Process2 will increase file size but Process1 will know only about the previous file size and start writing at the position set accordingly, effectively overwriting Process2's last written line!

The following code is the content of the script (DOS batch file) which runs three instances of our application, providing each with different argument:

run_processes.bat:

@start Process.exe 012345
@start Process.exe ABCDEFHIJKLM
@start Process.exe 987654321

Arguments are of different length so we can easily detect the place of the corruption in the output file, like this one:

test.log:

...
[PID = 8280] Iteration # 214 ABCDEFHIJKLM
[PID = 8120] Iteration # 208 987654321
M
[PID = 8280] Iteration # 216 ABCDEFHIJKLM
...

What happened here? First of all, we need to know that on Windows, \n read from stream buffer is expanded to \r\n (CR-LF) before writing it to the file on disk. Process 8120 has updated its knowledge of file size but before it wrote iteration #208 log, process 8280 had written its log for iteration #215 so basically we had this:

test.log (showing hidden CR-LF characters):

...
[PID = 8280] Iteration # 214 ABCDEFHIJKLM\r\n
[PID = 8280] Iteration # 215 ABCDEFHIJKLM\r\n
...

Then process 8120 wrote its #208 log, but effectively overwriting 8280's #215, after what 8280 wrote its log #216:

test.log (showing hidden CR-LF characters):

...
[PID = 8280] Iteration # 214 ABCDEFHIJKLM\r\n
[PID = 8120] Iteration # 208 987654321\r\nM\r\n
[PID = 8280] Iteration # 216 ABCDEFHIJKLM\r\n
...

Obviosuly, we need to protect file so only one process is accessing it at a time. We can do that with semaphore or mutex which are shared between multiple processes (and therefore must be named).

In this article I will show how to achieve it with semaphore:

main.cpp:



All processes are competing to get semaphore signal. First process whose wait() returns (decreasing semaphore count by 1 - possibly to minimal value of 0 in which case all other processes block on their wait()) gets a exclusive access to a file and updates its content after which it releases semaphore (increasing its count to 1 again). All processes are competing again and the one whose wait() returns first gets its slot of exclusive access. There is no corruption in the file any more:

test.log:

...
[PID = 6036] Iteration # 213 987654321
[PID = 10940] Iteration # 213 012345
[PID = 11644] Iteration # 213 ABCDEFHIJKLM
[PID = 6036] Iteration # 214 987654321
[PID = 10940] Iteration # 214 012345
[PID = 11644] Iteration # 214 ABCDEFHIJKLM
[PID = 6036] Iteration # 215 987654321
[PID = 10940] Iteration # 215 012345
[PID = 11644] Iteration # 215 ABCDEFHIJKLM
...

Note: Although this example uses semaphore for process synchronisation, mutex is here more natural solution - we don't want to limit number of accessors to several (N) but only to 1. Only process that locks the mutex can unlock it and with binary semaphore we are just emulating this behaviour.

Links and References:
Semaphore Objects (MSDN)
Using Semaphore Objects (MSDN)
Semaphore (Wikipedia)
Windows Thread Synchronization - Synchronization Using Semaphores
Joseph M. Newcomer: Semaphores
Mutex or Semaphore for Performance?
Mutex vs Semaphore
Mutex vs Semaphores
Difference between binary semaphore and mutex

No comments: