1
Q
Heap and stack memories
A
- Reference to an object + value type data is saved in the Stack. EX: the object ‘account’
- Object’s data is saved in the Heap. EX: ‘5000, 0.5, 12’ is saved in ‘account’.
- Every thread has its own program counter & needs its own calls stack.
2
Q
How do threads communicate?
A
- Through shared variables
- Through message passing / method calls
3
Q
Shared resources
A
- EX: Instance variables
- Multiple threads run the same method, work w/ diff values saved in the same variable & produce wrong results.
4
Q
Local variables as a shared resource?
A
- Every thread executing a method remembers the values stored in the local variables.
- When running the method at the same time = output correct.
5
Q
Local object reference as a shared resource?
A
- The reference itself is placed on the stack but object data is on the heap.
- Method is thread safe; every thread creates own instance of the object, the reference to the local object will be placed on the thread’s local stack.
- Just don’t make the local object available to another thread.
6
Q
Context switch
A
- Process of storing the state of a process or thread, so that it can be restored and resume execution at a later point.
- Threads may race to update & save the variable.
7
Q
Interleave
A
- Operation can consist of multiple steps.
- EX: k++;
1. Retrieve current value of k.
2. Increment value by 1, k = k+1
3. Store the incremented value back in k - Threads can overwrite each other by reading the initial value of k instead of the updated version.
8
Q
Atomic operation
A
- Performs completely w/o interleaving (i.e interference)
- Can’t stop in the middle. Either happens fully or doesn’t at all.
- k++; done completely by one thread before another accesses k.
9
Q
Thread Interference
A
- Condition when more than one thread, executing simultaneously, accesses the same piece of data.
- Caused by interleaving
- Data may get corrupted
- Occurs when the code is not THREAD SAFE.
10
Q
Thread safe
A
- Code is safe to call by multiple threads simultaneously.
- Non-interference: safety property. Guarantees that atomic action in a thread does not alter a shared resource.
11
Q
Avoiding thread interference
A
- Locks
- Const, readonly
- Thread-local variables
- Atomic operations (Mutual Exclusion)
12
Q
Race condition
A
- Threads race through the critical secion
- Sharing data & resources => Reading/Writing can occur in the wrong order. Erroneous output & corrupt data.
13
Q
Synchronization
A
- Process of making threads work in a way to ensure that shared data and resources are used safely.
- Possible interleaving is restricted.
- EX: locks, mutex, semaphores, monitors, condition variables.
14
Q
Sync Patterns
A
- Writer-Reader
- Producer-Consumer (bounded buffer)
15
Q
Mutual Exclusion
A
- Only one thread is allowed to be in its critical region at a certain time.
- ME is a mechanism that ensures this.
16
Q
Condition sync
A
- Wait, Pulse, PulseAll
- Signal a condition, process sets a shared variable
- One thread waits for an event signaled from another thread
- Wait for a condition to become true (called ‘busy waiting’)
16
Q
Critical Section
A
- Sequences of instructions that may get incorrect results if executed simultaneously
- Usually accesses shared variables
- Must be protected!!!
17
Q
Four Requirements for a solution
A
- Mutual Exclusion
- Progress
- Fairness
- No assumption on performance
18
Q
Requirement for solution: Mutual Exclusion
A
Only one thread in the critical section at a time.
19
Q
Requirement for solution: Progress
A
No dead/livelock. When no thread is in the CS, any thread that wants to enter should do so without delay.
20
Q
Requirement for solution: Fairness
A
No starvation. A thread shouldn’t wait indefinitely to enter the CS. => Bounded Wait (upper bound on nr of times a thread is allowed to enter its CS while another thread is waiting).
21
Q
Requirement for solution: No assumption on performance
A
Requirements must be met with any nr of CPUs with any relative speed. Overhead of entering & exiting should be small.
22
Q
What is a “lock”?
A
object lockObj = new object();
lock (lockObj)
- Simple. Ensures Mutual Exclusion but deadlock, livelock, starvation can occur.
- Lock is aquired by running thread when a statement is executed
- Automatically released at the end of the lock-block
23
Q
Lock states
A
- Held (locked) - lock is in use
- Not Held (unlocked) - lock is not in use
24
Lock operations
1. Acquire lock - if lock is not held, mark it Held and thread goes on. Else: wait for lock.
2. Release lock - mark lock Not Held, and if there is a thread that has called Aquire it gets the lock.
Other threads cannot acquire the same lock when it is used. Can aquire other locks though! Use same lock in CS accessing same data.
25
Reader/Writers problem
Many reader and writer threads share the same single resource.
26
Reader/Writer solution
- More than 1 Reader can access the shared resource concurrently
- The shared resource can be a single object or a buffer
- More than 1 Writer *SHOULD NOT* access the shared resource concurrently
- Threads need to wait for each other when they're not allowed to enter the code
27
Producer-Consumer (or Bounded-Buffer) Problem
- Thread puts data into the tail of a buffer & another thread reads & empties the data from the head of the buffer (repeatedly).
- Buffer = shared queue
- 1 Producer puts work items into buffer. 1 Consumer waits & removes items for processing.
28
Producer-Consumer Rules
1. Producer shouldn't add an item to the buffer when its full
2. Consumer shouldn't remove an item when the buffer is empty
3. Usually *1* Producer & *1* Consumer, but a solution with more producers & consumers can be programmed.
29
Classic Synchronization Problems
1. Race Condition
2. Deadlock
3. Livelock
4. Starvation
30
Race condition Example
- Imagine multiple light switches connected to a common ceiling light.
- If two people tried to turn on the light using two different switches at the same time, one instruction might cancel the other or the two actions might trip the circuit breaker.
31
Starvation
- Action in a concurrent programming situation never gets to execute.
- Never get shared resource / unable to make progress.
- Happens when: shared resources made unavailable for long periods by "greedy" threads.
32
Starvation Example
In the Dining Philosophers problem: A philosopher never gets to pick up a second fork.
33
Deadlock
Situation when two or more threads are blocked forever, waiting "deadly" for each other.
34
Deadlock Example
Dining philosophers: Everyone picks up one fork and never put it down.
35
Livelock
Situation in which a thread is spinning while waiting for a condition that will never become true.
Two or more threads are waiting actively (try to solve the situation by reverting action and retrying)
36
Livelock Example
Philosopher tries to give a fork to another. He puts it down. The other philosopher picks it up and tries to give it to the other. Puts it down as well. The cycle continues!
37
Barrier
- Sync method that makes a group of threads stop at a point. Can't proceed until all other threads reach this point.
Barrier barrier = new Barrier(n);
- n = number of participants. Each thread signals when it arrives at the barrier.
- Accounts for the fact that threads have different speeds of execution (some are slower than others).
38
Barrier Example
Adding two tables from a database, each table manipulated by a thread.
Both threads must be completed before the next step.
39
Safety
Each process/thread must have a safety property, i.e not have a bad state (variables with faulty values)
40
Liveness
Each process/thread must have a liveness property, i.e eventually eneter a good state (variables have correct values).
41
Safety Properties
- Class with correct locks is called "thread safe".
- Mutual exclusion & absence of deadlock are safety properties
- Safety Property = nothing bad will happen. Thread will NOT enter bad state.
- Cars don't crash on a one-way bridge
- A safety property must always be true.
42
Achieving Safety Property
Mutual exclusion
Condition synchronization
43
Liveness properties
- A class' ability to execute in a timely manner
- Requires that something good happens (we don't know when)
- Every car can eventually cross a one-way bridge
- Property is sometimes true
- EX: absence of dead/livelock and starvation
44
Liveness Property Solution
- No deadlock (some processes can always access a shared resource)
- No starvation (all processes can eventually access shared resource)
