Understanding Atomic Operations and Synchronization in Operating Systems
Explore atomic hardware operations and synchronization techniques in operating systems. Learn about important functions like atomic compare exchange and atomic add/sub fetch. Dive into concepts like spinlocks, futexes, and more to enhance your understanding of system organization.
Uploaded on | 0 Views
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Userspace Synchronization Chris Gill, Brian Kocoloski CSE 422S - Operating Systems Organization Washington University in St. Louis St. Louis, MO 63143 1
Atomic Operations Today, we will be exploring atomic hardware operations and synchronization in more detail Some important 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 __atomic_store_n() set a variable s value (unconditionally) 2 CSE 422S Operating Systems Organization
Compare/Exchange Syntax: cmp_exchg(ptr, expected, desired) Parameters ptr : pointer to an integer valued expected: value that ptr should have now desired: value that we want to set ptr to Semantics: (of course, this is executed atomically) 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 invoke cmp_exchg(ptr, UNLOCKED, LOCKED) If it fails, that means the value of ptr is not unlocked, so need to try again If it succeeds, value is set to LOCKED to prevent concurrent access Unlock: Invoke cmp_exchg(ptr, LOCKED, UNLOCKED) Has to succeed if not, the lock was never acquired 4 CSE 422S Operating Systems Organization
Spinlocks vs Futexes Spinlocks via cmp/xchg function correctly, but waste CPU cycles via spinning In cases of longer critical sections, it is desirable to be able to put processes/threads to sleep Similar to kernel-level mutexes/semaphores Fast userspace mutexes (futexes) are a new feature to improve lock performance 5 CSE 422S Operating Systems Organization
Futexes Three components: (1) an atomic integer variable in userspace (2) a system call to sleep/wake up contending processes (state of the atomic variable guards the sleep call) (3) a kernel-level wait queue for sleeping threads/processes Can use to synchronize multiple processes or threads In multiprocess settings, processes must explicitly share memory (e.g., lock variable location) via mmap(), etc. In multithread settings, threads implicitly share memory In their basic form, futexes offer primitive operations on which other (sleep) lock mechanisms can be built Semaphores, condition variables, readers/writer locks, etc. 6 CSE 422S Operating Systems Organization
Illustrating Futexes Optimization (using a slightly different compare exchange fxn that returns the old state) Lock acquisition (on some architectures): cmpxchg(val, UNLOCKED, LOCKED) 3 states: UNLOCKED LOCKED WAITERS WAITERS UNLOCKED LOCKED cmpxchg(val, LOCKED, WAITERS) UNLOCKED cmpxchg(val, UNLOCKED, LOCKED) LOCKED || WAITERS UNLOCKED (syscall to sleep) (success) 1. Common case code path (no lock contention) is optimized by not requiring any system calls Uncommon case - (lock contention) does not waste CPU cycles by spinning, but rather sleeps/wakes up via system calls 2. 7 CSE 422S Operating Systems Organization
Illustrating Futexes Optimization (using the atomic operations we will use in studio today) Lock acquisition: ret = __atomic_sub_fetch(&var, 1, __ATOMIC_ACQ_REL) 3 states: UNLOCKED == 1 LOCKED == 0 WAITERS < 0 (initialize variable var to UNLOCKED) WAITERS LOCKED (success) (syscall: sleep if ret == var) Lock release: __atomic_add_fetch(&var, 1, __ATOMIC_ACQ_REL) LOCKED || WAITERS UNLOCKED __atomic_store_n(&var, UNLOCKED, __ATOMIC_RELEASE) (syscall: wake up waiters) (success) 1. 2. Common case code path again optimized: no system calls Uncommon case again (conditionally) sleeps to avoid spinning 8 CSE 422S Operating Systems Organization
Todays Studio Implement userspace spinlocks and sleep locks Some Programming Considerations Volatile variables are often important Inform 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., volatile int * is a pointer to an int that s volatile (the int value, not the pointer, may change) OpenMP is for parallel programming Pragmas built into gcc, to support concurrent execution of functions, barrier synchronization before and after parallel- for loops, etc. 9 CSE 422S Operating Systems Organization
