ECS150 FQ20
March 27, 2020
Lecture Notes 5 Synchronizing Access to Shared Objects
• Independent Threads – Threads that operate in completely independent locations in memory
• Cooperating Threads – Threads that read/write shared state
• Multi-threaded program execution
• Program execution depends on the possible interleavings of threads’ access to shared state
• Program execution can be nondeterministic
• Compilers and processor hardware can reorder instructions
• Heisenbugs – Bugs that change or disappear when try to examine them
• Bohr bugs – Deterministic bugs
• Structured Synchronization – Structured approach to synchronizing accessed to shared
objects
Multi-threaded Challenges
• Race Conditions – The result of multiple processes accessing and manipulating the same data concurrently depends upon order of access
• Atomic Operations – Indivisible operations
• Safety Property – Never more than one accesses shared object at once
• Liveness Property – If access is needed, eventually one will access it
• Stable Property – Invariant that is always true once it becomes true
• Peterson’s Solution – Shared memory software solution to critical section problem
• Two Processes
#define FALSE 0
#define TRUE 1
#define N 2
volatile int Turn; volatile int Interested[N];
void EnterSection(void){
Interested [Me] = TRUE;
Turn = Other;
while(Interested [Other] && Turn == Other);
}
void ExitSection(void){ Interested [Me] = FALSE;
}
• Busy-Waiting – Consuming processor time while waiting
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 5
1 of 4
ECS150 FQ20 March 27, 2020
• Memory Barrier – Prevents compiler or processor from reordering instructions across the barrier
Structuring Shared Objects
• Shared Object – An object that can be safely accessed by multiple threads
• Synchronization Variable – Data structure used for coordinating concurrent access
• State Variable – Normal member variables of an object
• Atomic Read-Modify-Write Instructions – Processor instructions that allow atomic
access to memory
Locks: Mutual Exclusion
• Lock – Synchronization variable that provides mutual exclusion
• Formal Properties
• Mutual Exclusion – If process Pi is executing in critical section no other process is executing in the critical section
• Progress – Only processes not in remainder section can decide on next to enter
• Bounded Waiting – Limit on the number of times process is “skipped” before
entrance to critical section is granted
• Bounded Queue – A queue with a fixed size limit
• Thread-Safe Bounded Queue – Safe to call operations on queue from multiple threads
• Critical Sections – Critical portion of code that only one process can execute concurrently
Condition Variables: Waiting for a Change
• Poll – Repeatedly check the shared state
• Condition Variable – A synchronized object that lets a thread efficiently wait
• wait() – Releases lock and suspends execution with thread on waiting list
• signal() – Takes processor off waiting list and makes it able to run
• broadcast() – Takes all threads off condition variables waiting list
• Blocking Bounded Queue – Thread trying to remove from empty queue will wait, or adding to full queue will wait
Designing and Implementing Shared Objects
• High Level Methodology
1. Add a lock
2. Add code to acquire and release the lock
3. Identify and add condition variables
4. Add loops to wait using the condition variables
5. Add signal and broadcast calls
• Implement Best Practices
1. Consistent structure.
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 5
2 of 4
ECS150 FQ20 March 27, 2020
2. Always synchronize with locks and condition variables.
3. Always acquire the lock at the beginning of a method and release it right before
return.
4. Always hold the lock when operating on a condition variable.
5. Always wait in a while() loop.
6. (Almost) never use thread_sleep.
• Three Pitfalls
1. Double-Checked Locking
2. Avoid defining a synchronized block in the middle of a method.
3. Keep shared classes separate from thread classes.
Case Studies
• Readers/Writers Lock – Multiple readers are allowed to read shared state, only one writer
• Synchronization Barriers – Mechanism to check all threads have completed work
• FIFO Blocking Bounded Queue
• Starvation-freedom – The thread that waits to insert is guaranteed to proceed after a bounded amount of removes
• FIFO – Stronger constraint requiring FIFO access to insterts Implementing Synchronization Objects
• Uniprocessor Disable Interrupts – Disable can lock the processor, enable can release lock
• Uniprocessor Queuing Locks – If lock is acquired, then do context switch
• Implementing Multiprocessor Spinlocks
• Atomic Read-Modify-Write – A single instruction that will atomically read/modify/write the memory location
• Test and Set – Atomically tests and sets a memory location EnterSection:
tsl lock
jnz EnterSection
ret
ExitSection:
move lock, #0
ret
• Swap – Atomically swaps one memory location for register value EnterSection:
move register, #1
swap register, lock
cmp register, #0
jne EnterSection
ret
ExitSection:
move lock, #0
ret
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 5
3 of 4
ECS150 FQ20 March 27, 2020
• Spinlock – Busy wait for a lock
• Implementing Multiprocessor Queuing Locks – Use spinlock to check lock/queue state
• Implementing Condition Variables – Similar approach to implementing locks
• Implementing Application-level Synchronization
• Kernel-Managed Threads – Kernel takes care of the wait lists
• User-Managed Thread – User library takes care of the wait lists
Semaphores Considered Harmful
• Semaphore Semaphores – Integer value that is access through atomic operations
• P, V? (Proberen, Verhogen) or up/down or wait/signal
• Counting Semaphore – Allows over unrestricted domain
• Binary Semaphore (Mutex Lock) – Limited to 0 and 1 typedef struct{
int Value;
struct processqueue Waiting; } Semaphore;
void down(Semaphore *s){ s->Value–; if(s->Value < 0){
enqueue(S->Waiting, thisproc);
void up(Semaphore *s){ process P; s->Value++; if(s->Value <= 0){
block(); }}
}}
P = dequeue(s->Waiting); wakeup(P);
• Semaphores considered harmful. – Separate lock and condition variables is more readable, and stateless condition variable is better that one with state
This content is protected and may not be shared, uploaded, or distributed. Lecture Notes 5
4 of 4