ECS150-L14

📗 -> 02/09/26: ECS150-L14

---

Sync

🎤 Vocab

❗ Unit and Larger Context

Picking up from last week, we’re we covered:

• Race conditions: (unexpected/undesirable) results of concurrency
• Synchronization strategies: Peterson’s algorithm with busy waiting and locks

✒️ -> Scratch Notes

Locks

A sync variable that provides mutual exclusion

• 2 states: locked and free
• API: lock/acquire and unlock/release

void thread(void) {
	lock(&lock);
	if (!milk)
		milk++;
	unlock(&lock);	
}

Naive Uniprocessor Implementation:

Race conditions come mostly from indeterministic scheduling
Solution: disable the interrupts

Issues:

• Very sensitive operation, user applications can’t be given this permission
• Only works on uniprocessor system
• Dangerous to have unpreemptable critical section
• Distinct critical sections protected by the same lock (bottleneck)

• Oh want more granularity with locking then just disabling interrupts

Hardware Support:

• IE allows a CPU to dominate/ensure that memory read/modify/write operation is safe, despite hardware implementation regarding interrupts/competition

Test-and-Set primitive

In order to take advantage of hardware support, we can write inline assembly

To implement synchronization, use this atomic procedure

1. Read current value of memory location
2. Set memory location to 1
3. Return original value

Now, we have an atomic procedure to probe the memory of a

Implementation

void spinlock_lock(int *lock) {
	/* spin until old value was 0 */
	while (test_and_set(lock) == 1);
}
void spinlock_unlock(int *lock) {
	*lock = 0
}

Issues
Busy-waiting wastes CPU cycles

• Only to reduce latency
  Solution
  Cheap Busy waiting:
• Yield/sleep when unable to get the lock
  • while (test_and_set(lock==1)) { thread_yield() }
    Cons:
• Yielding still wastes cpu cycles
• Sleeping impacts latency as well

Better: Block thread until they can proceed

• while (test_and_set(lock==1)) { thread_block(lock) }
  Examples:
• Semaphores
• Mutexes

Semaphores

Invented by Dijkstra in the 60s

Semaphore:

• A generalized lock
  • Used for different types of synchronization (including mutual exclusion)
  • Tracks an arbitrary resource count
    • Queue of threads waiting to access resource

Kind of a line with posibililty for multiple resources to share
Like a line for a restaurant. A queue for multiple spots.

API

Initial count value (not a maximum value)

• sem = sem_create(count)
• down() or P()
  • Decrement by one, or block if already 0
• up() or V()
  • Increment by one, and wake up a waiting thread if they exist

🔗 -> Links

Resources

• Put useful links here

Connections

• Link all related words