Synchronization

* Types of Synchronization
- Resource sync: critical section and resource mutual exclusion
- Activity sync

* Approaches
Low weight ones: TSL(Test Set Lock, H/W), semaphore, mutex, conditional variable
High weight ones: message passing, spinlock, monitor, read-write lock, barrier, interrupt lock, and preemption(scheduling) lock.
- Resource sync
Resource could be either data or codes:
mutex for single shared resource access
recursive mutex for recursive shared resource access
counting semaphore plus mutex, the mixing of non-blocking and blocking mutexes for multiple shared resource access
interrupt lock for the shared resource with ISR
preemption lock for the shared resource without waiting
read-write lock for multiple reads and exclusive write (broadcasting)
locking hierarchy and locking chain for dependent resources
- Activity sync
1) Single-task waiting and single-task signaling: conditional variable and semaphore
2) Multiple-task waiting and single-task signaling: conditional variable(broadcasting) and semaphore(flushing)
3) Single-task waiting and multiple-task signaling: ONE semaphore with iterative checking MULTIPLE input sources from ISR; ONE counting semaphore associated with the each input queue which might be redesigned.
4) Flow control: counting semaphore
5) Rendezvous and barrier sync: TWO semaphore without comm. Two conditional variables. TWO message queues of one entry for comm. Callback mechanism with comm. And barrier for multiple tasks.
6) Event occurrence: conditional variable or event object, counting semaphore (support to count the times of event happening)

* Issues
- Race
A race occurs when two or more threads try to get something or do something at the same time. Only one can win. Race is the result of resource conflicts caused by insufficient sync. Race is difficult to diagnose since every thread would keep going.
- Deadlock
Deadlock is the result of resource conflicts caused by wrong sync. It is easy to be detected since threads stop. In general, if multiple mutexes are used sequentially for dependent resources, deadlock happens probably. The general solutions are:
1) fixed locking hierarchy and
2) try and backoff with reverse unlocking sequence.
Note: Lock chaining is a special case of locking hierarchy, where the scope of two locks overlap. With one mutex locked, the code enters a region where another mutex is required. After successfully locking that second mutex, the first is no longer needed, and can be released.

* Sleep and Non-sleep
Many facilities would make current threads to sleep, like semaphore, mutex, etc. However, in the following cases it is not allowed to sleep:
- ISR
- critical sections

* Semaphore, mutex and conditional variable
- Binary semaphore is too simple to use since programmers need to make sure both mutual exclusion and synchronization of threads by using multiple semaphores. Semaphore has no owner and anyone could release it. Also it needs no predicate associated.
- Mutex is for mutual exclusion and it has its owner which needs to release mutex after using it. Mutex supports to task delete safety, recursive access and priority inheritance for priority inversion.
- Conditional variable is for thread synchronization and is dependent of a SINGLE (not multiple) predicate of the shared resource. Always test your predicate; and then test it again by using while loop. It must be associated with a mutex. But a mutex may have any number of condition variables associated with it.

* Spinlock and monitor
- Spinlock can be effective in very restricted circumstances. The critical section must be short, you must have significant contention for the lock, and you must be running on more than one CPU since it would not block the task. The trylock of mutex could be used to implement it. Spinlock could be used in ISR to do resource sync due to its non-sleep & non-interruptible property.
- Monitor integrates the shared resource with its mutual exclusion utilities together. In many situations, monitors are an excellent synchronization technique. By forcing the programmer to manipulate shared data via monitored code, you ensure that there can never be a failure to lock its use, and that the access methods will be well-defined. Monitors cannot handle all types of locking situations, however. When you want to use the “trylock” functions, you must use regular mutexes.

* Initialization/destroy and blocking/non-blocking
All these utilities need to be initialized before using them and deleted in the end. It is possible that memory associated is allocated within the initialization. Therefore this memory should be freed in the delete routine. Also, it must be sure that when they are deleted, no other tasks are waiting or holding them so that no deadlock happens. One general deletion is:
{
     lock(mutex);
     unlock(mutex);
     delete(mutex);
}
On the other hand, when these utilities are used, two types of functions are provided in general, i.e. blocking access and non-blocking or time-out access.