Transcript ppt

Using Synchronization Primitives in
C, C++, and Linux Kernel
CS-3013 Operating Systems
A-term 2008
(Slides include materials from Modern Operating Systems, 3rd ed., by Andrew Tanenbaum and from
Operating System Concepts, 7th ed., by Silbershatz, Galvin, & Gagne)
CS-3013 A-term 2008
Using synchronization
primitives
1
How do we actually use synchronization
mechanisms in program design?
• Producer-Consumer (pipelined parallelism)
• Semaphores
• Mutexes for protecting shared data of pipeline
• Monitors (task parallelism)
• Mutexes for monitor locks
• Condition variables for waiting and signaling in user space
• Simulation of condition variable in kernel space
• Barrier Synchronization (data parallelism)
• Simulate with monitors in user space
• Simulate with Completion variables in kernel space
CS-3013 A-term 2008
Using synchronization
primitives
2
Producer-Consumer
• User-space operations
• semaphore.h — POSIX semaphores
• sem_init, sem_wait, sem_trywait, sem_post,
sem_getvalue, etc.
• Usable in any C or C++ user program
• Thread may sleep for long period of time
– Some other thread needs to awaken it
• Kernel-space operations
• asm/semaphore.h
• down, down_interruptible, down_trylock, up
• For putting a task to sleep for long time (if necessary)
– Some other task needs to awaken it
• May not be used while holding a spinlock or in interrupt
handler
CS-3013 A-term 2008
Using synchronization
primitives
3
Producer-Consumer (continued)
• Locking shared data structures (temporarily)
• User space operations
• pthread.h — POSIX thread tools
• pthread_mutex_init, pthread_mutex_lock,
pthread_mutex_trylock, pthread_mutex_unlock, etc.
• Only unlockable by owner (i.e., the locking thread)
• Normally used for short critical sections, no sleeping
• Kernel space operations
• linux/spinlock.h
• spin_lock, spin_trylock, spin_unlock, etc.
• Must never be used when task might sleep!
• Consume CPU cycles until locking attempt is satisfied
CS-3013 A-term 2008
Using synchronization
primitives
4
Questions?
CS-3013 A-term 2008
Using synchronization
primitives
5
Monitors
• Must be simulated by lower-level constructs
• User-space
– Monitor lock  pthread_mutex_t
• Every monitor function must be surrounded by pair
(pthread_mutex_lock, pthread_mutex_unlock)
• Not automatic in C, C++
– Condition variable  pthread_cond_t
• pthread_cond_wait, pthread_cond_signal,
pthread_cond_broadcast
• pthread_cond_wait atomically releases mutex
• Waiting thread must re-acquire mutex upon waking
– Also check situation that required the wait
– Easily adaptable to object-oriented programming
CS-3013 A-term 2008
Using synchronization
primitives
6
Monitors (continued)
• Harder to simulate in kernel space
– Monitor lock  spinlock
• Every monitor function must be surrounded by pair
(spin_lock, spin_unlock) pair
• Not automatic
– Condition variables not supported
• Must be simulated using counter and semaphore
– Amenable to object-oriented programming style
CS-3013 A-term 2008
Using synchronization
primitives
7
Simulating Condition Variables
in Kernel Space
• Condition variable = (wait_count, semaphore)
• Wait: while holding spinlock mon_lock
•
•
•
•
wait_count++
spin_unlock(mon_lock)
down(semaphore)
spin_lock(mon_lock)
• Signal: while holding spinlock mon_lock
• if (wait_count > 0) {
– up(semaphore)
– wait_count --
• }
• Question: is there a danger of a race condition between
waiting and signalling?
CS-3013 A-term 2008
Using synchronization
primitives
8
Questions?
CS-3013 A-term 2008
Using synchronization
primitives
9
Barrier Synchronization
• User space
• May be simulated with pthread_mutex and
pthread_cond_broadcast
• Kernel space
• May be simulated with completion variables
• See linux/completion.h and Robert Love, pp
148-149
CS-3013 A-term 2008
Using synchronization
primitives
10
Questions?
CS-3013 A-term 2008
Using synchronization
primitives
11