UserspaceSynchronization
1
Chris Gill, Brian KocoloskiCSE 422S - Operating Systems OrganizationWashington University in St. LouisSt. Louis, MO 63143
Atomic Operations
CSE 422S – Operating Systems Organization
2
Today, we will be exploring atomic hardware operationsand synchronization inmore detailImportant atomic functions:__atomic_compare_exchange()– set a variable to a new value if its old value is something we expect it to be__atomic_add_fetch()– add to a variable and return its new value__atomic_sub_fetch()– subtract from a variable and return its new value
Compare/Exchange
Syntax:cmp_exchg(ptr, expected, desired)Parametersptr: pointer to an integer valuedexpected: value thatptrshould have nowdesired:value that we want to setptrtoSemantics: (of course, this is executedatomically)if (*ptr== expected) {*ptr= desired;return true;} else {return false;}
3
CSE 422S – Operating Systems Organization
Spinlock via Compare/Exchange
Syntax:cmp_exchg(ptr, expected, desired)Lock:Repeatedly invokecmp_exchg(ptr, UNLOCKED, LOCKED)If it fails, that means the value ofptris not unlocked, so need to try againIf it succeeds, value is set to LOCKED to prevent concurrent accessUnlock:Invokecmp_exchg(ptr, LOCKED, UNLOCKED)Has to succeed – if not, the lock was never acquired
4
CSE 422S – Operating Systems Organization
Spinlocks vsFutexes
Spinlocks viacmp/xchgfunction correctly, but waste CPU cycles via spinningIn cases of longer critical sections, it is desirable to be able to put processes/threads to sleepSimilar to kernel-levelmutexes/semaphoresFastuserspacemutexes(futexes) are a new feature to improve lock performance
CSE 422S – Operating Systems Organization
5
Futexes
CSE 422S – Operating Systems Organization
6
Two components:(1) an atomic integer variable inuserspace(2) a system call to sleep/wake up contending processesCan be used to synchronize multiple processes or threadsInmultiprocesssettings, processes must explicitly share memory via something likemmap()In multithread settings, threads implicitly share memoryIn their simplest form,futexesoffer primitive operations on which other (sleep) lock mechanisms can be builtSemaphores, condition variables, readers/writer locks, etc.
FutexExample
7
CSE 422S – Operating Systems Organization
<On whiteboard>
FutexExample
8
CSE 422S – Operating Systems Organization
<On whiteboard>Takeaways:Common case code path – (no lock contention) – is optimized by not requiring any system callsUncommon case - (lock contention) – does not waste CPU cycles by spinning, but rather sleeps/wakes up via system calls
Today’s Studio
CSE 422S – Operating Systems Organization
9
Implementuserspacespinlocks andmutexesSome Programming ConsiderationsVolatile variables are often importantInform compiler (and someone reading the code) that a variable’s value may change unexpectedly)Read type declarations right-to-left in C and C++E.g.,volatileint*is a pointer to anintthat’s volatile (theintvalue, not the pointer, may change)OpenMPis for parallel programmingPragmas built intogcc, to support concurrent execution of functions, barrier synchronization before and after parallel-for loops, etc.
0
Embed
Upload