|
|
Await && Locks is a thread synchronization library enveloped in a couple of macros. It proposes some statements that allow programmer to express his/her intention more clearly.
The simplest statement that Await && Locks propose is await statement.
await(condition) { action }
Executing this statement, thread waits until the condition becomes true. The condition is evaluated inside the global critical section, therefore none of the other threads can mutate it while it is evaluated. If the condition is already true, thread doesn't stop and goes further. Then (still being inside the critical section) thread performs the action. Because the condition may be evaluated more then once, it should be evaluated as fast as possible and without side effect. But the action is evaluated only once and here is the best place to mutate variables shared among the threads.
The await statement is very powerful and expressive. In order to see this, let's consider some examples.
Example 1 Counting Semaphore
Here is the class that represents counting semaphore.
class Semaphore { private: int m_nCount; public: Semaphore(int nInitial): m_nCount(nInitial) {} ~Semaphore() {} // here is acquire operation // it decrements semaphore count when it become positive void acquire() { await(m_nCount>0) --m_nCount; } // here is release operation // it always increments semaphore count void release() { await(true) ++m_nCount; } };
Example 2 Group of Boolean Semaphores
Here is the class that represents group of boolean semaphores.
class GBS { private: // each bit in this mask corresponds to the separate semaphore unsigned long m_nMask; public: GBS(): m_nMask(~0) {} ~GBS() {} // here is acquire operation // it allows to acquire any number of semaphores void acquire(unsigned long nMask) { await((m_nMask & nMask) == nMask) m_nMask &= ~nMask; } // here is release operation void release(unsigned long nMask) { await(true) m_nMask |= nMask; } };
Example 3 Recursive Mutex
Here is the class that represents recursive mutex. It uses getCurrentThreadId() external function in order to identify threads.
Note: This example is for demonstration purpose only. You should better use lock_it statement instead.
class Mutex { private: threadid m_tOwner; int m_nLockCount; public: Mutex(): m_nLockCount(0) {} ~Mutex() {} // here is lock operation void lock() { await((m_nLockCount == 0) || (m_tOwner == getCurrentThreadId())) { ++m_nLockCount; m_tOwner = getCurrentThreadId(); } } // here is unlock operation void unlock() { await(true) --m_nLockCount; } };
Example 4 Pipe
And here is more complex example. This class is to communicate between two threads. The first one sends data using Pipe::put method and the second one receives these data using Pipe::get method.
template<class T> class Pipe { private: std::queue<T> m_oContainer; public: Pipe() {} ~Pipe() {} // here is get operation T get() { T result; // it waits for incoming elements and gets first await(!m_oContainer.empty()) { result = m_oContainer.front(); m_oContainer.pop(); } return result; } // here is put operation void put(T obj) { await(true) m_oContainer.push(obj); } };
Sometimes there are situations when it's necessary to wait for some different events. Of course, it's possibly to write following code:
await(event 1 || event 2) { if(event 1) { action 1 } else if(event 2) { action 2 } }
But it looks rather awkward - the same conditions are present in two places of code. For this special case Await && Locks propose another statement. This is await_switch statement. Consider:
await_switch(FOREVER) { await_case(event 1) { action 1 } await_case(event 2) { action 2 } }
There can be arbitrary amount of await_case clauses inside await_switch statement. In the case that more then one condition becomes true, only one clause is selected. And it's undefined which of true condition will be selected. Anyone can be.
Example 5 Producer and Consumer
Let's consider following task: the Producer produces some data and notifies the Consumer about this. When the Producer quits, it notifies too. And the Consumer, on the other hand, waits for either availability of the data or quitting.
// producer for(int i=0; i<N; ++i) { // waiting for request from the consumer await(g_bCanWrite) g_bCanWrite = false; // PRODUCING . . . // notifying the consumer about availability of the data await(true) g_bCanRead = true; } // notifying the consumer about quitting await(true) g_bCanQuit = true;
// consumer while(true) { // sending request to the producer await(true) g_bCanWrite = true; bool bQuit = false; // waiting for any event from the producer await_switch(FOREVER) { await_case(g_bCanRead) g_bCanRead = false; await_case(!g_bCanRead && g_bCanQuit) bQuit = true; } if(bQuit) break; // CONSUMING . . . }
It's also possible to specify timeout for await_switch statement.
await_switch(timeout) { await_case(condition 1) { action 1 } await_case(condition 2) { action 2 } . . . . . . . await_timeout() { action timeout } }
The timeout is a relative time in milliseconds. So, await_switch statement is waiting at most timeout milliseconds from the moment when it has started. If during the specifying period any of conditions did not become true, the await_timeout clause would be selected.
Example 6 Producer and Consumer (with timeout)
Here is slightly modified previous example. The Producer doesn't notify about quitting and the Consumer quits by timeout.
// producer for(int i=0; i<N; ++i) { // waiting for request from the consumer await(g_bCanWrite) g_bCanWrite = false; // PRODUCING . . . // notifying the consumer about availability of the data await(true) g_bCanRead = true; } // producer forgot to notify consumer about quitting
// consumer while(true) { // sending request to the producer await(true) g_bCanWrite = true; bool bQuit = false; // waiting for any event from the producer await_switch(5000) { // waiting at most 5 seconds await_case(g_bCanRead) g_bCanRead = false; await_timeout() bQuit = true; } if(bQuit) break; // CONSUMING . . . }
One of the most important sorts of thread synchronization is locks. Using await statements it's possible to express required locks, but Await && Locks offers separate statements for this purposes. The simplest one is lock_it statement.
Let's imagine that one thread is going to access exclusively to variable named g_oResource. In this case we should write following:
lock_it(wlock(g_oResource)) { // here the thread can access to g_oResource exclusively }
Sometimes it's necessary simply to read a variable, not updating it. In such cases we can impose lock for reading. Then all "readers" can access to this variable simultaneously.
lock_it(rlock(g_oResource)) { // here the thread has shared access to g_oResource (only for reading) }
It's also possible to use combination of any lock using && operator.
lock_it(rlock(g_oRes0) && wlock(g_oRes1)) { // here we can only read g_oRes0 and both read and write g_oRes1 }
Generalizing, lock_it statement looks so:
lock_it(combination of locks) { action }
where combination of locks consists of arbitrary amount shared and exclusive locks, joined with &&. Use rlock for shared lock and wlock for exclusive one. Parameter for both rlock and wlock should be l-value because Await && Locks distinguishes resources by the address.
Note: The current version of Await && Locks supports only two types of locks. But, apparently, it should suffice for the majority of tasks. Await && Locks also doesn't check how you use locked resources, i.e. you shouldn't but you can change the variable that is locked only for read. And the current version doesn't lock memory area, i.e. it cannot distinguish what you want to lock, whole array of 10 bytes or only the first 4, for example.
The lock_it statements can be nested. Also it's possible to lock the same resource many times.
lock_it(wlock(g_oRes0)) { lock_it(rlock(g_oRes1)) { lock_it(rlock(g_oRes0)) { // . . . } } }
Now, using an analogy it's easy to imagine how lock_switch statement looks and works. :) Generally, it looks so:
lock_switch(timeout) { lock_case(combination 1 of locks) { action 1 } lock_case(combination 2 of locks) { action 2 } . . . . . . . lock_timeout() { action timeout } }
There can arise deadlock in the multithreaded programs. Generally speaking, deadlock is such situation when one of the threads waits for event that will not ever happen. In most cases it concerned with locks. Consider following code:
// thread 1 lock_it(wlock(g_oRes0)) { // point 1 lock_it(wlock(g_oRes1)) { // point 2 } }
// thread 2 lock_it(wlock(g_oRes1)) { // point 1 lock_it(wlock(g_oRes0)) { // point 2 } }
If both threads reached point 1 simultaneously, they cannot reach point 2. Because thread 1 waits for resource g_oRes1, which has been already locked by thread 2, and thread 2, in turn, waits for g_oRes0, which has been locked by thread 1. So, these threads are deadlocked.
Deadlock is bad situation and there are some ways to prevent it. They are
lock_switch(timeout) { lock_case(combination 1 of locks) { action 1 } lock_case(combination 2 of locks) { action 2 } . . . . . . . lock_timeout() { action timeout } lock_victim() { action, when deadlock detected } }
Be sure that the condition in await statement does not identically equal to false. The code like this:
await(false) { // . . . }
cause deadlock, which will not be detected by Await && Locks.
Always declare variables that are present in the condition of await statement as volatile. You program may work in Debug configuration correctly, but when you turn on compiler optimization for Release configuration, volatile may save you from sleepless nights.
Do not use ExitThread, pthread_exit or another similar API. Await && Locks doesn't provide any statement for thread creation and deletion, because it doesn't depend on way how threads were created. Thus you should use native OS API for this purpose or your favourite library. But if you write code like this:
void ThreadProc() { SomeClass oLocalVar; lock_it(rlock(g_oGlobalVar)) { ExitThread(0); } }
shared lock for g_oGlobalVar will be never released. This problem of sudden termination will touch also oLocalVar. Its destructor will not be called. But you can avoid the problem slightly modifying the code:
void ThreadProc() { try { SomeClass oLocalVar; lock_it(rlock(g_oGlobalVar)) { throw ThreadDeath(); } } catch(ThreadDeath) { // simply catch, nothing more } }
Do not use TerminateThread, pthread_cancel or another API that absolutly cancels from the outside execution of the thread. This is because of sudden termination problem described before. I don't have general recipe. Suitable solution should be found in each particular case.
Use lock_it and lock_switch statements everywhere it's needed. This code:
await(!g_bVarLocked) g_bVarLocked = true; doSomethingWithVar(g_oVar); await(true) g_bVarLocked = false;
should better be rewritten so:
lock_it(wlock(g_oVar)) { doSomethingWithVar(g_oVar); }
because of following reason. First reason, if doSomethingWithVar would throw an exception in first sample, g_bVarLocked will not become false, hence g_oVar will not be unlocked. But second sample works correctly in this case. Second reason, using lock_it and lock_switch statement guarantees that possible deadlock will be resolved.
Prefer await_switch and lock_switch statements to await and lock_it. Use await and lock_it constructs only if you completely sure that waiting will not be indefinitely long.
Do not avoid lock_victim clause. Because deadlock is often programmer's fault. I advise code like this:
lock_victim() { assert(("Deadlock detected!", 0)); }
Well, Await && Locks is a great thing. Is is simple, expressive, platform independent and able to detect deadlocks. But it has some disadvantages too. It uses macros. Preprocessor came to C++ after C. And C++ couldn't get out of it. Preprocessor makes language more flexible but it change language. And language loses its own purity and beauty. As regards the Await && Locks, if you made a misprint in its constructs, you would get some strange compiler errors, which would tell you nothing useful about misuse of these constructs. So, be ready. Then Await && Locks relies on some C++ tricks such as for(;;) statement and automatic destructor call. Therefore the Await && Locks statements are implemented not as optimally as it was possible when they were build-in into the language.
Despite of all said in the previous paragraph, Await && Locks are still very useful and usable. And I intent to extend it with memory area locking and extensible locking feature (that allow programmer not to be limited with shared and exclusive locks but allow to define semantic of custom type of lock).