CPS110: Implementing locksRecap and looking aheadUsing interrupt disable-enableWhy use locks?Lock implementation #1Slide 6Slide 7Using read-modify-write instructionsSlide 9Too much milk, Solution 2Test&set on most architecturesLock implementation #2Course administrationLocks and busy-waitingLock implementation #3Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25How is switch returned to?Slide 27Interrupts and returning to switchSlide 29Lock implementation #4Slide 31Slide 32Summary of implementing locksCPS110: Implementing locksLandon CoxFebruary 2, 2009Recap and looking aheadHardwareHardwareOSOSApplicationsApplicationsIf you don’t have atomic operations, you can’t make any.Using interrupt disable-enableDisable-enable on a uni-processorAssume atomic (can use atomic load/store)How do threads get switched out (2 ways)?Internal events (yield, I/O request)External events (interrupts, e.g. timers)Easy to prevent internal eventsUse disable-enable to prevent external eventsWhy use locks?If we have disable-enable, why do we need locks?Program could bracket critical sections with disable-enableMight not be able to give control back to thread libraryCan’t have multiple locks (over-constrains concurrency)Not sufficient on multiprocessorProject 1: disable interrupts only in thread librarydisable interruptswhile (1){}Disable interrupts, busy-waitingLock implementation #1lock () { disable interrupts while (value != FREE) { enable interrupts disable interrupts } value = BUSY enable interrupts}unlock () { disable interrupts value = FREE enable interrupts}Why is it ok for lock code to disable interrupts?It’s in the trusted kernel (we have to trust something).Disable interrupts, busy-waitingLock implementation #1lock () { disable interrupts while (value != FREE) { enable interrupts disable interrupts } value = BUSY enable interrupts}unlock () { disable interrupts value = FREE enable interrupts}Do we need to disable interrupts in unlock?Only if “value = FREE” is multiple instructions (safer)Disable interrupts, busy-waitingLock implementation #1lock () { disable interrupts while (value != FREE) { enable interrupts disable interrupts } value = BUSY enable interrupts}unlock () { disable interrupts value = FREE enable interrupts}Why enable-disable in lock loop body?Otherwise, no one else will run (including unlockers)Using read-modify-write instructionsDisabling interruptsOk for uni-processor, breaks on multi-processorWhy?Could use atomic load-store to make a lockInefficient, lots of busy-waitingHardware people to the rescue!Using read-modify-write instructionsMost modern processor architecturesProvide an atomic read-modify-write instructionAtomicallyRead value from memory into registerWrite new value to memoryImplementation detailsLock memory location at the memory controllerToo much milk, Solution 2What key part of lock code had to be atomic?if (noMilk) { if (noNote){ leave note; buy milk; remove note; }}Block is not atomic.Must atomically• check if lock is free• grab itTest&set on most architecturestest&set (X) { tmp = X X = 1 return (tmp)}Set: sets location to 1Test: returns old valueSlightly different on x86 (Exchange)Atomically swaps value between register and memoryUse test&setInitially, value = 0Lock implementation #2lock () { while (test&set(value) == 1) { }}unlock () { value = 0}What happens if value = 1?What happens if value = 0?Course administrationProject 1Due in a little less than two weeksShould be finishing up 1d in the next few daysDo not put off starting 1t!!HintsRead through entire spec firstUse STL for data structures (will probably make life easier)OO might be overkillGlobal variables are fineIn thread library, only use swapcontext, never uc_linkLocks and busy-waitingAll implementations have used busy-waitingWastes CPU cyclesTo reduce busy-waiting, integrateLock implementationThread dispatcher data structuresInterrupt disable, no busy-waitingLock implementation #3lock () { disable interrupts if (value == FREE) { value = BUSY // lock acquire } else { add thread to queue of threads waiting for lock switch to next ready thread // don’t add to ready queue } enable interrupts}unlock () { disable interrupts value = FREE if anyone on queue of threads waiting for lock { take waiting thread off queue, put on ready queue value = BUSY } enable interrupts}Lock implementation #3lock () { disable interrupts if (value == FREE) { value = BUSY // lock acquire } else { add thread to queue of threads waiting for lock switch to next ready thread // don’t add to ready queue } enable interrupts}unlock () { disable interrupts value = FREE if anyone on queue of threads waiting for lock { take waiting thread off queue, put on ready queue value = BUSY } enable interrupts}Who gets the lock after someone calls unlock?This is called a “hand-off” lock.Lock implementation #3lock () { disable interrupts if (value == FREE) { value = BUSY // lock acquire } else { add thread to queue of threads waiting for lock switch to next ready thread // don’t add to ready queue } enable interrupts}unlock () { disable interrupts value = FREE if anyone on queue of threads waiting for lock { take waiting thread off queue, put on ready queue value = BUSY } enable interrupts}Who might get the lock if it weren’t handed-off directly? (e.g. if value weren’t set BUSY in unlock)This is called a “hand-off” lock.Lock implementation #3lock () { disable interrupts if (value == FREE) { value = BUSY // lock acquire } else { add thread to queue of threads waiting for lock switch to next ready thread // don’t add to ready queue } enable interrupts}unlock () { disable interrupts value = FREE if anyone on queue of threads waiting for lock { take waiting thread off queue, put on ready queue value = BUSY } enable interrupts}What kind of ordering of lock acquisition guarantees does the hand-off lock provide? Fumble lock?This is called a “hand-off” lock.Lock implementation #3lock () { disable interrupts if (value == FREE) { value = BUSY // lock acquire } else { add thread to queue of threads waiting for lock switch to next ready thread // don’t add to ready queue }