Threads, Synchronizations, Locks Flashcards
Mutual exclusion
when one thread accesses a shared resource, no other threads can access it. It is important that any thread trying to access the shared resource eventually gets access.
Synchronization
methods that ensure operation of things does not disrupt dependencies. For example, semaphores, locks, and many more!
Critical sections
parts of the program that access shared resources. It is important that no more than one thread executes a critical section at a time.
race condition
when the order at which threads run a piece of code matters and it is not done in the right order leading to wrong program behaviour.
Progress
It is important that in solving the critical section problem, a thread outside the critical section does not block other threads from entering the critical section.
Semaphores
Uses wait and signal to manage the threads that can access a shared resource. A thread either waits for an available space or when its done it signal that a space is available.
Semaphores can be binary (0/1) or counting (1-n) spaces
Thread_join
means all threads above waits right before the join command, when all threads have reached, they are joined into one thread.
Condition variables
Similar to binary semaphores but instead of 0 and 1 representing if a space is occupied or not. It signifies a boolean condition where an event is completed or not.
Spinlocks
If lock is acquired, wait in a loop and repeatingly check if the lock is free until the thread has acquired it
Queuing locks
Synchronisation method that is more advanced version of spin lock. Uses a linked list and serves threads in FIFO order (same as ticket locks). Each location is used by a thread to spin. Once a thread has freed the lock, the next element in the queue will exit spinning.
Lock points to the node that has the lock.
Ticket locks
A synchronisation method. It works exactly like a ticketing counter for a clinic. Every thread is served in the order it arrived/requested the resource. Every thread that arrives is given a position. Once a thread is served, the ‘Now Serving’ variable is increment atomically. This holds the position of the thread that will be served next. This is dequeued from the queue.
MCS locks
Similar to queuing lock but with a tail pointer pointing to the last node in the list. Every new thread is added to the back of the list using CAS (compare and swap).
New thread comes, update tail node. Compare tail node with old. New node points to previous last node.
When a thread wants to release a lock, the next field is set and the node is removed from the list.
MCS is complete when tail pointer points to NULL.
Atomic instructions
a hardware feature in which an instruction is executed completely or not at all.
CAS
compare and swap. Compare a value with the old value. If the value is old, swap it for the new one.
TAS
test and set. Returns the old value. When the old value is false, then we can get out of the spin stage.
