程序代写 CS162 © UCB Spring 2022

Recall:Too Much Milk Solution #3
• Here is a possible two-note solution: Thread A Thread B
leave note A;leave note B;
while (note B) {\\X if (noNote A) {\\Y

do nothing; if (noMilk) { } buy milk;
if (noMilk) { }
buy milk; }
} remove note B; remove note A;
• Does this work? Yes. Both can guarantee that: – It is safe to buy, or
– Other will buy, ok to quit
– If no note B,safe forA to buy,
– Otherwise wait to find out what will happen
– If no noteA,safe for B to buy
– Otherwise,A is either buying or waiting for B to quit
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Recall:Too Much Milk: Solution #4
• Solution #3 really complex and undesirable as a general solution
• Recall our target lock interface:
– acquire(&milklock) – wait until lock is free, then grab
– release(&milklock) – Unlock, waking up anyone waiting
– These must be atomic operations – if two threads are waiting for the lock and both see it’s free, only one succeeds to grab the lock
• Then, our milk problem is easy:
acquire(&milklock);
release(&milklock);
Critical Section
if (nomilk)
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Recall: Naïve use of Interrupt Enable/Disable
• How can we build multi-instruction atomic operations?
– Recall: dispatcher gets control in two ways.
» Internal:Thread does something to relinquish the CPU » External: Interrupts cause dispatcher to take CPU
– On a uniprocessor, can avoid context-switching by:
» Avoiding internal events (although virtual memory tricky) » Preventing external events by disabling interrupts
• Consequently, naïve Implementation of locks:
LockAcquire { disable interrupts; }
LockRelease { enable interrupts; }
• Problems with this approach:
– Can’t let user do this! Consider following:
LockAcquire();
While(TRUE) {;}
– Real-Time system—no guarantees on timing! » Critical Sections might be arbitrarily long
– What happens with I/O or other important events? » “Reactor about to meltdown. Help?”
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Recall: Better Implementation of Locks by Disabling Interrupts
• Key idea: maintain a lock variable and impose mutual exclusion only during operations on that variable
int value = FREE;
Acquire() {
disable interrupts;
if (value == BUSY) {
put thread on wait queue;
Go to sleep();
// Enable interrupts?
Release() {
disable interrupts;
if (anyone on wait queue) {
take thread off wait queue
Place on ready queue;
value = FREE;
enable interrupts;
value = BUSY;
enable interrupts;
• Really only works in kernel – why?
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Implementation: Discussion
• Why do we need to disable interrupts at all?
– Avoid interruption between checking and setting lock value.
– Prevent switching to other thread that might be trying to acquire lock! – Otherwise two threads could think that they both have lock!
Acquire() {
disable interrupts;
if (value == BUSY) {
put thread on wait queue;
Go to sleep();
// Enable interrupts?
value = BUSY;
enable interrupts;
“Meta-” Critical Section
• Note: unlike previous solution, this “meta-”critical section is very short
– User of lock can take as long as they like in their own critical section: doesn’t impact global machine behavior
– Critical interrupts taken in time!
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Interrupt Re-enable in Going to Sleep
• What about re-enabling ints when going to sleep?
Acquire() {
disable interrupts;
if (value == BUSY) {
put thread on wait queue;
Go to sleep();
value = BUSY;
enable interrupts;
• Before Putting thread on the wait queue?
– Release can check the queue and not wake up thread
• After putting the thread on the wait queue?
– Release puts the thread on the ready queue, but the thread still thinks it needs to go to sleep
– Misses wakeup and still holds lock (deadlock!)
Enable Position
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Interrupt Re-enable in Going to Sleep
• What about re-enabling ints when going to sleep?
Acquire() {
disable interrupts;
if (value == BUSY) {
put thread on wait queue;
Go to sleep();
value = BUSY;
enable interrupts;
• Before Putting thread on the wait queue?
– Release can check the queue and not wake up thread
• After putting the thread on the wait queue?
– Release puts the thread on the ready queue, but the thread still thinks it needs to go to sleep
– Misses wakeup and still holds lock (deadlock!)
• Want to put it after sleep(). But – how? Joseph & Kubiatowicz CS162 © UCB Spring 2022
Enable Position

How to Re-enable After Sleep()?
• In scheduler, since interrupts are disabled when you call sleep:
– Responsibility of the next thread to re-enable ints
– When the sleeping thread wakes up, returns to acquire and re-enables interrupts
Thread A Thread B
disable ints
sleep return
enable ints
disable int
sleep return
enable ints
Joseph & Kubiatowicz CS162 © UCB Spring 2022
context switch
context switch

In-Kernel Lock: Simulation
lock.Acquire();
critical section;
lock.Release();
lock.Acquire();
critical section;
lock.Release();
int value = 0;
Acquire() {
disable interrupts;
if (value == 1) {
put thread on wait-queue;
go to sleep() //??
value = 1;
enable interrupts;
Release() {
disable interrupts;
if anyone on wait queue {
take thread off wait-queue
Place on ready queue;
value = 0;
enable interrupts;
Joseph & Kubiatowicz CS162 © UCB Spring 2022

In-Kernel Lock: Simulation
Reunandiyng
lock.Acquire();
critical section;
lock.Release();
Ruenandiyng
lock.Acquire();
critical section;
lock.Release();
int value = 0;
Acquire() {
disable interrupts;
if (value == 1) {
put thread on wait-queue;
go to sleep() //??
value = 1;
enable interrupts;
Release() {
disable interrupts;
if anyone on wait queue {
take thread off wait-queue
Place on ready queue;
value = 0;
enable interrupts;
Joseph & Kubiatowicz CS162 © UCB Spring 2022

In-Kernel Lock: Simulation
Reunandiyng
lock.Acquire();
critical section;
lock.Release();
RWuaninting
lock.Acquire();
critical section;
lock.Release();
int value = 0;
Acquire() {
disable interrupts;
if (value == 1) {
put thread on wait-queue;
go to sleep() //??
value = 1;
enable interrupts;
Release() {
disable interrupts;
if anyone on wait queue {
take thread off wait-queue
Place on ready queue;
value = 0;
enable interrupts;
Joseph & Kubiatowicz CS162 © UCB Spring 2022

In-Kernel Lock: Simulation
lock.Acquire();
critical section;
lock.Release();
int value = 0;
Acquire() {
disable interrupts;
if (value == 1) {
put thread on wait-queue;
go to sleep() //??
value = 1;
enable interrupts;
Release() {
disable interrupts;
if anyone on wait queue {
take thread off wait-queue
Place on ready queue;
value = 0;
enable interrupts;
lock.Acquire();
critical section;
lock.Release();
Joseph & Kubiatowicz CS162 © UCB Spring 2022

In-Kernel Lock: Simulation
Ruenandiyng
lock.Acquire();
critical section;
lock.Release();
int value = 0;
Acquire() {
disable interrupts;
if (value == 1) {
put thread on wait-queue;
go to sleep() //??
value = 1;
enable interrupts;
Release() {
disable interrupts;
if anyone on wait queue {
take thread off wait-queue
Place on ready queue;
value = 0;
enable interrupts;
lock.Acquire();
critical section;
lock.Release();
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Atomic Read-Modify-Write Instructions
• Problems with previous solution:
– Can’t give lock implementation to users – Doesn’t work well on multiprocessor
» Disabling interrupts on all processors requires messages and would be very time consuming
• Alternative: atomic instruction sequences
– These instructions read a value and write a new value atomically – Hardware is responsible for implementing this correctly
» on both uniprocessors (not too hard)
» and multiprocessors (requires help from cache coherence protocol)
– Unlike disabling interrupts, can be used on both uniprocessors and multiprocessors
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Examples of Read-Modify-Write
• test&set (&address) { result = M[address];
M[address] = 1;
return result;
• 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
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Using of Compare&Swap for queues
compare&swap (&address, reg1, reg2) { /* x86, 68000 */
if (reg1 == M[address]) {
M[address] = reg2;
return success;
return failure;
Here is an atomic add to linkedlist function:
addToQueue(&object) {
do { // repeat until no conflict
ld r1, M[root] // Get ptr to current head
st r1, M[object] // Save link in new object
} until (compare&swap(&root,r1,object));

Implementing Locks with test&set
• Simple lock that doesn’t require entry into the kernel:
// (Free) Can access this memory location from user space!
int mylock = 0; // Interface: acquire(&mylock);
// release(&mylock);
acquire(int *thelock) {
while (test&set(thelock)); // Atomic operation!
release(int *thelock) {
*thelock = 0; // Atomic operation!
• Simple explanation:
– If lock is free, test&set reads 0 and sets lock=1, so lock is now busy. It returns 0 so while exits.
– If lock is busy, test&set reads 1 and sets lock=1 (no change) It returns 1, so while loop continues.
– When we set thelock = 0, someone else can get lock. • Busy-Waiting: thread consumes cycles while waiting
– For multiprocessors: every test&set() is a write, which makes value ping-pong around in cache (using lots of network BW)
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Problem: Busy-Waiting for Lock
• Positives for this solution
– Machine can receive interrupts – User code can use this lock
– Works on a multiprocessor
• Negatives
– This is very inefficient as thread will consume cycles waiting
– Waiting thread may take cycles away from thread holding lock (no one wins!)
– Priority Inversion: If busy-waiting thread has higher priority than thread holding lock ⇒ no progress!
• Priority Inversion problem with original Martian rover
• For higher-level synchronization primitives (e.g. semaphores or monitors), waiting thread may wait for an arbitrary long time!
– Thus even if busy-waiting was OK for locks, definitely not ok for other primitives – Homework/exam solutions should avoid busy-waiting!
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Multiprocessor Spin Locks: test&test&set
• A better solution for multiprocessors:
// (Free) Can access this memory location from user space!
int mylock = 0; // Interface: acquire(&mylock);
// release(&mylock);
acquire(int *thelock) {
while(*thelock); // Wait until might be free (quick check/test!)
} while(test&set(thelock)); // Atomic grab of lock (exit if succeeded)
release(int *thelock) {
*thelock = 0; // Atomic release of lock
• Simple explanation:
– Wait until lock might be free (only reading – stays in cache) – Then, try to grab lock with test&set
– Repeat if fail to actually get lock
• Issues with this solution:
– Busy-Waiting: thread still consumes cycles while waiting » However, it does not impact other processors!
Joseph & Kubiatowicz CS162 © UCB Spring 2022

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;
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Recap: Locks using interrupts
acquire(int *thelock) {
disable interrupts;
release(int *thelock)
enable interrupts;
If one thread in critical section, no other activity (including OS) can run!
int mylock=0;
acquire(&mylock);
critical section;
release(&mylock);
acquire(int *thelock) {
// Short busy-wait time
disable interrupts;
if (*thelock == 1) {
put thread on wait-queue;
go to sleep() //??
*thelock = 1;
enable interrupts;
release(int *thelock) {
// Short busy-wait time
disable interrupts;
if anyone on wait queue {
take thread off wait-queue
Place on ready queue;
*thelock = 0;
enable interrupts;
Lock argument not used!
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Recap: Locks using test & set
int mylock=0;
acquire(&mylock);
critical section;
release(&mylock);
int mylock = 0;
acquire(int *thelock) {
while(test&set(thelock));
int guard = 0; // global!
acquire(int *thelock) {
// Short busy-wait time
while(test&set(guard));
if (*thelock == 1) {
put thread on wait-queue;
go to sleep()& guard = 0;
// guard == 0 on wakeup
*thelock = 1;
guard = 0;
release(int *thelock) {
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 = 0;
guard = 0;
*thelock = 0;
Threads waiting to enter critical section busy-wait
Joseph & Kubiatowicz CS162 © UCB Spring 2022

Linux futex: Fast Userspace Mutex
#include #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 –

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts