Concurrency: Multi-Tasking & Synchronization Flashcards
(43 cards)
What is a race condition?
- Race Condition(data race)
○ Unprotected timing of execution.
○ The result of such a program would be indeterminate:
sometimes it produces the correct result but sometimes the results are different and are likely wrong.
What is a critical section?
○ Critical Section
Code routine that accesses a shared resource/data, if unprotected, might yield incorrect result. Might lead to race condition
What is mutual exclusion? Why does it avoid race condition
- Mutual Exclusion(mutex)
○ Atomicity is guaranteed under mutex
○ Lock(Synchronization primitive)
§ Acquire:
□ When a thread needs to use a shared resource(critical section), it must first get control (a lock) to enter the protected code area, ensuring no other thread can use it at the same time. If multiple threads try to get the lock, only one can get it and the rest must wait.
§ Release:
After the thread has finished using the shared resource, it must unlock or release the control so that other threads can use the resource.
How can we get mutual exclusion?
Atomicity of the critical section
How is atomicity achieved?
Locks- Condition variables- Channels etc
What are some of the problems with atomicity/mutual exclusion?
Where one thread must wait for another to complete some action before it continues. This interaction arises, for example, when a process performs a disk I/O and is put to sleep; when the I/O completes, the process needs to be roused from its slumber so it can continue.
How does the lock mechanism work?
We can use a special lock variable to protect data- All threads accessing a critical section share a lock- One threads succeeds in locking - owner of lock- Other threads that try to lock cannot proceed further until lock is released by the owner
What are the goals of locks?
Fairness: Every thread gets a chance to acquire the lock, preventing indefinite waiting.
Low Overhead: Acquiring, releasing, and waiting for the lock uses minimal resources for efficiency.
What are some of the different types of locks?
Spin lock (thread ligge å venta i en for loop(spinne til den fe tilgang til locken)- Sleep lock(Thread sleeps until lock is free. Sleeping results in more idle time)
What is a spin lock? What is a sleep lock?
Spins until lock is acquired| - While loops
Instead of spinning for a lock, a contending thread could simply give up the CPU and check back later- Yield() moves thread from running to ready state
When should we use locks?
A lock should be acquire before accessing any variabel or data structure that is shared between multiple threads of a process
What is the difference between a fined and coarse-grained lock?
One big lock for all shared data(Coarse grained locks) vs separate locks(fined locks)
What are the positives and negatives of fine-grained locks?
Fine grained allows more parallelism| - Multiple fine-grained locks may be harder to manage
What are the advantages and disadvantages of coarse-grained locks?
Slower| - Easier to manage
Why do we want to use sleeping locks?
CPU Waste: When threads continuously check for a spinlock’s availability (known as spinning), they use up CPU resources without doing any productive work.
Extended Blocking: The problem worsens if a thread holding a spinlock is blocked for a long time, leading to even more CPU waste by the threads waiting for the spinlock.
What are the advantages and disadvantages of spin locks?
Provides mutual exclusion- spin locks don’t provide any fairness guarantees- Spin locks, in the single CPU case, performance overheads can be quite painful
How does Compare-and-swap work for locking?
it simply checks if the flag is 0 and if so, atomically swaps in a 1 thus acquiring the lock
How does Load-Linked and Store-Conditional for locking work?
Load-Linked: This works like a regular load instruction. It just takes a value from memory and puts it in a register.
Store-Conditional: This is where it gets special. It will update the memory only if no other updates to the same memory address have happened since the load-linked. If there’s been an update in between, the store-conditional won’t go through.
How does Fetch-And-Add for locking work?
Fetch-and-add instruction atomically increments a value while returning the old value at a particular address.- Unlock is accomplished simply by incrementing the turn such that the next waiting thread (if there is one) can now enter the critical section
Why are condition variables used?
Condition variables are used to make threads wait for certain conditions to become true before they continue execution, ensuring proper sequencing and coordination in concurrent operations.
How do condition variables work?
Condition variables allow threads to wait in a queue for a certain condition. When the condition is met, another thread signals the condition variable to wake up one or all waiting threads.
How do we check a condition using condition variables?
In a while loop| We do this to avoid corner cases of thread being woken up even when condition not true
What is a semaphore?
Semaphore is a variable with an underlying counter - Synchronization primitive like condition variable- Acts like a lock- Shared between threads
How does a semaphore work?
A semaphore with a value of 1 acts like a mutex lock. Here’s how it works:
Thread 1 decreases the counter to enter the critical section, locking it. After finishing its task, Thread 1 increases the counter, unlocking it. Now, Thread 2 can enter and do the same.
