Concurrency

Notes

  • A semaphore is like an integer, with three differences:

    • it can be initialised to any integer value, but the only allowed operations are increment and decrement (you cannot read the current value of the semaphore)

    • when a thread decrements the semaphore, if the result is negative, the thread blocks itself until another thread increments the semaphore

    • when a thread increments the semaphore, if there are other threads blocked, one of them gets unblocked

  • The simplest use for a semaphore is signaling, which means one thread sends a message to another thread to indicate that something has happened.

  • A second common use for a semaphore is to enforce mutual exclusion (mutex) around some portion of the code called critical section. When a single thread is allowed to execute (so the semaphore is initialised with the value 1) we have a mutex, when n threads are allowed to execute we have a multiplex.

  • A rendezvous is a synchronisation problem for which two threads have to reach a certain point in the execution, and neither is allowed to proceed further until both have arrived. The generalisation for n threads instead of just two is called a barrier.

  • A deadlock is a situation in which one thread is holding a resource and waiting for another to be available, while at the same another thread is holding the resource the first thread wants and is waiting on the resource held by the first thread. This situation must be avoided, as it will halt indefinitely the execution of a program.

  • Another situation to avoid as much as possible is called starvation: one or more threads might be waiting forever to enter in a critical section while other threads are able to carry on with theirs. In order to avoid this situation, we enforce a requirement of bounded waiting, which means the time a threads waits on a resource has to be provably finite.

Resources

Articles

Books

Images

PreviousComputer ScienceNextContinuous Integration / Delivery

Last updated