Recall: Atomic Read-Modify-Write
• test&set (&address) { result = M[address];
M[address] = 1;
return result;
Copyright By PowCoder代写 加微信 powcoder
• swap (&address, register) { temp = M[address];
M[address] = register;
register = temp;
/* most architectures */
// return result from “address” and
// set value at “address” to 1
// swap register’s value to
// value at “address”
• compare&swap (&address, reg1, reg2) { /* x86 (returns old value), 68000 */
if (reg1 == M[address]) {
M[address] = reg2;
return success;
return failure;
// If memory still == reg1,
// then put reg2 => memory
// Otherwise do not change memory
• load-linked&store-conditional(&address) { /* R4000, alpha */ loop:
ll r1, M[address];
movi r2, 1;
sc r2, M[address];
beqz r2, loop;
// Can do arbitrary computation
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Better Locks using test&set
• Can we build test&set locks without busy-waiting?
– Mostly. Idea: only busy-wait to atomically check lock value
int guard = 0; // Global Variable!
int mylock = FREE; // Interface: acquire(&mylock);
acquire(int *thelock) {
// Short busy-wait time
while (test&set(guard));
if (*thelock == BUSY) {
put thread on wait queue;
go to sleep() & guard = 0;
// guard == 0 on wakup!
*thelock = BUSY;
guard = 0;
• Note: sleep has to be sure to reset the guard variable – Why can’t we do it just before or just after the sleep?
release(&mylock);
release(int *thelock) {
// Short busy-wait time
while (test&set(guard));
if anyone on wait queue {
take thread off wait queue
Place on ready queue;
*thelock = FREE;
guard = 0;
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Linux futex: Fast Userspace Mutex
#include
int futex(int *uaddr, int futex_op, int val, const struct timespec *timeout );
uaddr points to a 32-bit value in user space futex_op
– FUTEX_WAIT – if val == *uaddr sleep till FUTEX_WAIT
» Atomic check that condition still holds after we disable interrupts (in kernel!)
– FUTEX_WAKE – wake up at most val waiting threads
– FUTEX_FD, FUTEX_WAKE_OP, FUTEX_CMP_REQUEUE: More interesting operations! timeout
– ptr to a timespec structure that specifies a timeout for the op
• Interface to the kernel sleep() functionality! – Let thread put themselves to sleep – conditionally!
• futex is not exposed in libc; it is used within the implementation of pthreads – Can be used to implement locks, semaphores, monitors, etc…
1/15/2022 Joesph & Kubiatowicz CS162 © UCB Spring 2022 Lec 9.3
Recall: Lock Using Atomic Instructions and Futex
• Three (3) states:
– UNLOCKED: No one has lock
– LOCKED: One thread has lock
– CONTESTED: Possibly more than one (with someone sleeping)
• Clean interface!
• Lock grabbed cleanly by either
– compare_and_swap() – First swap()
• No overhead if uncontested!
• Could build semaphores in a similar way!
typedef enum { UNLOCKED,LOCKED,CONTESTED } Lock;
Lock mylock = UNLOCKED; // Interface: acquire(&mylock);
// release(&mylock);
acquire(Lock *thelock) {
// If unlocked, grab lock!
if (compare&swap(thelock,UNLOCKED,LOCKED))
// Keep trying to grab lock, sleep in futex
while (swap(mylock,CONTESTED) != UNLOCKED))
// Sleep unless someone releases hear!
futex(thelock, FUTEX_WAIT, CONTESTED);
release(Lock *thelock) {
// If someone sleeping,
if (swap(thelock,UNLOCKED) == CONTESTED)
futex(thelock,FUTEX_WAKE,1);
1/15/2022 Joesph & Kubiatowicz CS162 © UCB Spring 2022 Lec 9.4
Recall: Producer-Consumer with a Bounded Buffer
• Problem Definition
– Producer(s) put things into a shared buffer
– Consumer(s) take them out
– Need synchronization to coordinate producer/consumer
• Don’t want producer and consumer to have to work in lockstep, so put a fixed-size buffer between them
– Need to synchronize access to this buffer – Producer needs to wait if buffer is full
– Consumer needs to wait if buffer is empty
• Example 1: GCC compiler
– cpp | cc1 | cc2 | as | ld
• Example 2: Coke machine
– Producer can put limited number of Cokes in machine – Consumer can’t take Cokes out if machine is empty
• Others:Web servers, Routers, ….
Producer Producer
Consume Consume
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Circular Buffer Data Structure (sequential case)
typedef struct buf {
int write_index;
int read_index;
• Insert: write & bump write ptr (enqueue)
• Remove: read & bump read ptr (dequeue)
• How to tell if Full (on insert) Empty (on remove)?
• And what do you do if it is?
• What needs to be atomic?
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Recall: Circular Buffer – first cut
mutex buf_lock =
Producer(item) {
acquire(&buf_lock);
while (buffer full) {}; // Wait for a free slot
enqueue(item);
release(&buf_lock);
Consumer() {
acquire(&buf_lock);
while (buffer empty) {}; // Wait for arrival
item = dequeue();
release(&buf_lock);
return item
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Will we ever come out of the wait loop?
Circular Buffer – 2nd cut ∅ mutex buf_lock =
Producer(item) {
acquire(&buf_lock);
while (buffer full) {release(&buf_lock); acquire(&buf_lock);}
enqueue(item);
release(&buf_lock);
Consumer() {
acquire(&buf_lock);
while (buffer empty) {release(&buf_lock); acquire(&buf_lock);}
item = dequeue();
release(&buf_lock);
return item
What happens when one is waiting for the other?
– Multiple cores ? – Single core ?
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Higher-level Primitives than Locks
• What is right abstraction for synchronizing threads that share memory? – Want as high a level primitive as possible
• Good primitives and practices important!
– Since execution is not entirely sequential, really hard to find bugs, since they happen rarely
– UNIX is pretty stable now, but up until about mid-80s
(10 years after started), systems running UNIX would crash every week or so – concurrency bugs
• Synchronization is a way of coordinating multiple concurrent activities that are using shared state
– This lecture presents some ways to structuring sharing
1/15/2022 Joesph & Kubiatowicz CS162 © UCB Spring 2022 Lec 9.9
Semaphores
• Semaphores are a kind of generalized lock
– First defined by Dijkstra in late 60s
– Main synchronization primitive used in original UNIX
• Definition: a Semaphore has a non-negative integer value and supports the following operations:
– Set value when you initialize
– Down() or P(): an atomic operation that waits for semaphore to become positive, then decrements it by 1
» Think of this as the wait() operation
– Up() or V(): an atomic operation that increments the semaphore by 1, waking up a waiting P, if any
» This of this as the signal() operation
• Technically examining value after initialization is not allowed.
1/15/2022 Joesph & Kubiatowicz CS162 © UCB Spring 2022 Lec 9.10
Semaphores Like Integers Except…
• Semaphores are like integers, except:
– No negative values
– Only operations allowed are P and V – can’t read or write value, except initially
– Operations must be atomic
» Two P’s together can’t decrement value below zero
» Thread going to sleep in P won’t miss wakeup from V – even if both happen at same time
• POSIX adds ability to read value, but technically not part of proper interface!
• Semaphore from railway analogy
– Here is a semaphore initialized to 2 for resource control:
Value=01210 Value=2
1/15/2022 Joesph & Kubiatowicz CS162 © UCB Spring 2022 Lec 9.11
Two Uses of Semaphores
Mutual Exclusion (initial value = 1)
• Also called “Binary Semaphore” or “mutex”.
• Can be used for mutual exclusion, just like a lock:
semaP(&mysem);
// Critical section goes here
semaV(&mysem);
Scheduling Constraints (initial value = 0)
• Allow thread 1 to wait for a signal from thread 2
– thread 2 schedules thread 1 when a given event occurs
• Example: suppose you had to implement ThreadJoin which must wait for thread to terminate:
Initial value of semaphore = 0
ThreadJoin {
semaP(&mysem);
ThreadFinish {
semaV(&mysem);
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Revisit Bounded Buffer: Correctness constraints for solution
• Correctness Constraints:
– Consumer must wait for producer to fill buffers, if none full (scheduling constraint) – Producer must wait for consumer to empty buffers, if all full (scheduling constraint) – Only one thread can manipulate buffer queue at a time (mutual exclusion)
• Remember why we need mutual exclusion
– Because computers are stupid
– Imagine if in real life: the delivery person is filling the machine and somebody comes up and tries to stick their money into the machine
• General rule of thumb: Use a separate semaphore for each constraint – Semaphore fullBuffers; // consumer’s constraint
– Semaphore emptyBuffers;// producer’s constraint
– Semaphore mutex; // mutual exclusion
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Full Solution to Bounded Buffer (coke machine)
Semaphore fullSlots = 0; // Initially, no coke
Semaphore emptySlots = bufSize;
// Initially, num empty slots
Semaphore mutex = 1; //
Producer(item) { semaP(&emptySlots); // se
semaV(&fullSlots); //
No one using machine
Wait until space
Tell consumers there is
fullSlots signals coke Check if there’s a coke
tell producer need more
maP(&mutex); // Wait until machine free
queue(item);
maV(&mutex);
// more coke
Critical sections using mutex protect integrity of the queue
Consumer() { semaP(&fullSlots); // se
se semaV(&emptySlots); // return item;
maP(&mutex); // Wait until machine free
em = Dequeue();
maV(&mutex);
emptySlots
signals space
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Discussion about Solution
Decrease # of Increase # of empty slots occupied slots
• Why asymmetry?
– Producer does:semaP(&emptyBuffer), semaV(&fullBuffer) – Consumer does:semaP(&fullBuffer), semaV(&emptyBuffer)
• Is order of P’s important?
• Is order of V’s important?
– No, except that it might affect scheduling efficiency
• What if we have 2 producers or 2 consumers?
– Do we need to change anything?
– Yes! Can cause deadlock
Decrease # of Increase # of occupied slots empty slots
Producer(item) {
semaP(&mutex);
semaP(&emptySlots);
Enqueue(item);
semaV(&mutex);
} semaV(&fullSlots);
Consumer() {
semaP(&fullSlots);
semaP(&mutex);
item = Dequeue();
semaV(&mutex);
semaV(&emptySlots);
return item;
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Semaphores are good but…Monitors are better!
• Semaphores are a huge step up; just think of trying to do the bounded buffer with only loads and stores or even with locks!
• Problem is that semaphores are dual purpose:
– They are used for both mutex and scheduling constraints
– Example: the fact that flipping of P’s in bounded buffer gives deadlock is not immediately obvious. How do you prove correctness to someone?
• Cleaner idea: Use locks for mutual exclusion and condition variables for scheduling constraints
• Definition: Monitor: a lock and zero or more condition variables for managing concurrent access to shared data
– Some languages like Java provide this natively
– Most others use actual locks and condition variables
• A “Monitor” is a paradigm for concurrent programming! – Some languages support monitors explicitly
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Condition Variables
• How do we change the consumer() routine to wait until something is on the queue?
– Could do this by keeping a count of the number of things on the queue (with semaphores), but error prone
• Condition Variable: a queue of threads waiting for something inside a critical section
– Key idea: allow sleeping inside critical section by atomically releasing lock at time we go to sleep
– Contrast to semaphores: Can’t wait inside critical section • Operations:
–Wait(&lock):Atomically release lock and go to sleep. Re-acquire lock later, before returning.
– Signal():Wake up one waiter, if any
– Broadcast():Wake up all waiters
• Rule: Must hold lock when doing condition variable ops!
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Monitor with Condition Variables
• Lock: the lock provides mutual exclusion to shared data
– Always acquire before accessing shared data structure – Always release after finishing with shared data
– Lock initially free
• Condition Variable: a queue of threads waiting for something inside a critical section – Key idea: make it possible to go to sleep inside critical section by atomically releasing
lock at time we go to sleep
– Contrast to semaphores: Can’t wait inside critical section
Joesph & Kubiatowicz CS162 © UCB Spring 2022 Lec 9.18
Synchronized Buffer (with condition variable)
• Here is an (infinite) synchronized queue:
lock buf_lock; // Initially unlocked
condition buf_CV; // Initially empty
queue queue; // Actual queue!
Producer(item) {
acquire(&buf_lock); // Get Lock enqueue(&queue,item); // Add item cond_signal(&buf_CV); // Signal any waiters release(&buf_lock); // Release Lock
Consumer() {
acquire(&buf_lock); // Get Lock while (isEmpty(&queue)) {
cond_wait(&buf_CV, &buf_lock); // If empty, sleep
item = dequeue(&queue); // Get next item release(&buf_lock); // Release Lock return(item);
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Mesa vs. Hoare monitors
• Need to be careful about precise definition of signal and wait. Consider a piece of our dequeue code:
while (isEmpty(&queue)) {
cond_wait(&buf_CV,&buf_lock); // If nothing, sleep
item = dequeue(&queue); // Get next item
– Why didn’t we do this?
if (isEmpty(&queue)) {
cond_wait(&buf_CV,&buf_lock); // If nothing, sleep
item = dequeue(&queue); // Get next item
• Answer: depends on the type of scheduling
– Mesa-style: Named after Xerox-Park Mesa Operating System
» Most OSes use Mesa Scheduling!
– Hoare-style: Named after British logician
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Hoare monitors
• Signaler gives up lock, CPU to waiter; waiter runs immediately
• Then, Waiter gives up lock, processor back to signaler when it exits critical section or if it waits again
acquire(&buf_lock);
… Lock, CPU
cond_signal(&buf_CV);
release(&buf_lock);
acquire(&buf_lock);
if (isEmpty(&queue)) {
cond_wait(&buf_CV,&buf_lock);
release(&buf_lock);
• On first glance, this seems like good semantics
– Waiter gets to run immediately, condition is still correct!
• Most textbooks talk about Hoare scheduling – However, hard to do, not really necessary!
– Forces a lot of context switching (inefficient!)
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Mesa monitors
• Signaler keeps lock and processor
• Waiter placed on ready queue with no special priority
Put waiting … thread on
acquire(&buf_lock) ready queue …
cond_signal(&buf_CV);
release(&buf_lock));
acquire(&buf_lock);
while (isEmpty(&queue)) {
cond_wait(&buf_CV,&buf_lock);
lock.Release();
• Practically, need to check condition again after wait
– By the time the waiter gets scheduled, condition may be false again – so, just check again with the “while” loop
• Most real operating systems do this! – More efficient, easier to implement
– Signaler’s cache state, etc still good
Joesph & Kubiatowicz CS162 © UCB Spring 2022
schedule thread (sometime later!)
Circular Buffer – 3rd cut (Monitors, pthread-like)
lock buf_lock =
condition producer_CV =
condition consumer_CV =
Producer(item) {
acquire(&buf_lock);
while (buffer full) { cond_wait(&producer_CV, &buf_lock); }
enqueue(item);
cond_signal(&consumer_CV);
release(&buf_lock);
Consumer() {
acquire(buf_lock);
while (buffer empty) { cond_wait(&consumer_CV, &buf_lock); }
item = dequeue();
cond_signal(&producer_CV);
release(buf_lock);
return item
What does thread do when it is waiting?
– Sleep, not busywait!
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Again:Why the while Loop? • MESA semantics
• For most operating systems, when a thread is woken up by signal(), it is simply put on the ready queue
• It may or may not reacquire the lock immediately!
– Another thread could be scheduled first and “sneak in” to empty the queue
– Need a loop to re-check condition on wakeup • Is this busy waiting?
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Readers/Writers Problem
• Motivation: Consider a shared database
– Two classes of users:
» Readers – never modify database
» Writers – read and modify database
– Is using a single lock on the whole database sufficient? » Like to have many readers at the same time
» Only one writer at a time
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Basic Structure of Mesa Monitor Program
• Monitors represent the synchronization logic of the program
– Wait if necessary
– Signal when change something so any waiting threads can proceed
• Basic structure of mesa monitor-based program:
while (need to wait) {
condvar.wait();
Check and/or update state variables Wait if necessary
do something so no need to wait
condvar.signal();
Check and/or update state variables
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Basic Readers/Writers Solution
• Correctness Constraints:
– Readers can access database when no writers
– Writers can access database when no readers or writers – Only one thread manipulates state variables at a time
• Basic structure of a solution:
– Reader()
Wait until no writers
Access data base
Check out – wake up a waiting writer
– Writer()
Wait until no active readers or writers Access database
Check out – wake up waiting readers or writer
– State variables (Protected by a lock called “lock”): » int AR: Number of active readers; initially = 0
» int WR: Number of waiting readers; initially = 0
» int AW: Number of active writers; initially = 0
» int WW: Number of waiting writers; initially = 0 » Condition okToRead = NIL
» Condition okToWrite = NIL
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Code for a Reader
Reader() {
// First check self into system
acquire(&lock);
while ((AW + WW) > 0) { // Is it safe to read?
WR++; // No. Writers exist
cond_wait(&okToRead,&lock);// Sleep on cond var
WR–; // No longer waiting
AR++; // Now we are active!
release(&lock);
// Perform actual read-only access
AccessDatabase(ReadOnly);
// Now, check out of system
acquire(&lock);
AR–; // No longer active
if (AR == 0 && WW > 0) // No other active readers
cond_signal(&okToWrite);// Wake up one writer
release(&lock);
Joesph & Kubiatowicz CS162 © UCB Spring 2022
Code for a Writer
Writer() {
// First check self into system
acquire(&lock);
while ((AW + AR) > 0) { // Is it safe to write?
WW++; // No. Active users exist
cond_wait(&okToWrite,
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com