《高级操作系统高级操作系统 (35).pdf》由会员分享,可在线阅读,更多相关《高级操作系统高级操作系统 (35).pdf(30页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、第 14 讲:Concurrency in OS Kernel第一节:IntroductionResourceReference:”Is Parallel Pro rammin Hard And If So What Can You Do About It?”Paul McKenney;第 14 讲Locking In The Linux KernelWhy do we need locking in the kernel?Which problems are we trying to solve?What implementation choices do we have?Is there
2、a one-size-fits-all solution?Concurrency in LinuxLinux is a symmetric multiprocessing(SMP)preemptible kernelIts has true concurrencyAnd various forms of pseudo concurrencySources of Pseudo Concurrency in LinuxSoftware-based preemptionVoluntary preemption(sleep/yield)Involuntary preemption(preemptabl
3、e kernel)And various forms of pseudo concurrencySolutions:dont do the former,disable preemption to prevent thelatterSources of Pseudo Concurrency in LinuxHardware preemptionInterrupt/trap/fault/exception handlers can start executing at anytimeSolutions:disable interruptsUniprocessor Examplepreempt d
4、isable;r1=x;r2=x;preempt enable;assert(r1=r2)Uniprocessor Examplepreempt disable;r1=x;yield();r2=x;preempt enable;assert(r1=r2)Uniprocessor Exampleinterrupt disable;r1=x;r2=x;interrupt enable;assert(r1=r2)True Concurrency in LinuxSolutions to pseudo-concurrency do not work in the presence of truecon
5、currencyAlternatives include atomic operators,various forms of locking,RCU,and non-blocking synchronizationLocking can be used to provide mutually exclusive access to criticalsectionsLocking can not be used everywhere,i.e.,interrupt handlers cant blockLocking primitives must support coexistence with
6、 various solutions for pseudoconcurrency,i.e.,we need hybrid primitivesMultiprocessor Exampleinterrupt disable;r1=x;r2=x;interrupt enable;assert(r1=r2)Atomic Operators in LinuxSimplest synchronization primitivesPrimitive operations that are indivisibleTwo typesmethods that operate on integersmethods
7、 that operate on bitsImplementationAssembly language sequences that use the atomic read-modify-write instructions of theunderlying CPU architectureMemory Invariance Exampler1=atomic read x;r2=atomic read x;assert(r1=r2)Atomic Integer Operatorsatomic_t v;atomic_set(&v,5);/*v=5(atomically)*/atomic_add
8、(3,&v);/*v=v+3(atomically)*/atomic_dec(&v);/*v=v-1(atomically)*/printf(This will print 7:%dn,atomic_read(&v);”atomic_add(3,&v);”is NOT the same as”atomic_add(1,&v);atomic_add(2,&v);”Spin Locks in LinuxMutual exclusion for larger(than one operator)critical sections requiresadditional supportSpin lock
9、s are one possibilitySingle holder locksWhen lock is unavailable,the acquiring process keeps tryingBasic Use of Spin Locksspinlock_t mr_lock=SPIN_LOCK_UNLOCKED;spin_lock(&mr_lock);/*critical section.*/spin_unlock(&mr_lock);spin_lock()Acquires the spinlock using atomic instructions required for SMPsp
10、in_unlock()Releases the spinlockSpin Locks and InterruptsInterrupting a spin lock holder may cause problemsSpin lock holder is delayed,so is every thread spin waiting for thespin lockNot a big problem if interrupt handlers are shortInterrupt handler may access the data protected by the spin-lockShou
11、ld the interrupt handler use the lock?Can it be delayed trying to acquire a spin lock?What if the lock is already held by the thread it interrupted?Solutions for Spin Locks and InterruptsShould the interrupt handler use the lock?Can it be delayed trying to acquire a spin lock?What if the lock is alr
12、eady held by the thread it interrupted?If data is only accessed in interrupt context and is local to onespecific CPU we can use interrupt disabling to synchronizeIf data is accessed from other CPUs we need additionalsynchronization spin lockNormal code(kernel context)must disable interrupts and acqu
13、ires in lock.Spin Locks&Interrupt Disablingspinlock_t mr_lock=SPIN_LOCK_UNLOCKED;unsigned long flags;spin_lock_irqsave(&mr_lock,flags);/*critical section.*/spin_unlock_irqrestore(&mr_lock,flags);spin_lock_irqsave()Disables interrupts locallyAcquires the spinlock using instructions required for SMPsp
14、in_unlock_irqrestore()Restores interrupts to the state they were in when the lock wasacquiredContention for semaphores causes blocking not spinningShould not be used for short duration critical sections!Can be used to s nchronize with user contexts that might block or be preempted14 讲2020 年 5.Bottom
15、 Halves and SoftirqsSoftirqs,tasklets and BHs are deferrable functionsdelayed interrupt handling work that is scheduledthey can wait for a spin lock without holding up devicesthey can access non-CPU local dataSoftirqs the basic building blockstatically allocated and non-preemptively scheduledcan not
16、 be interrupted by another softirq on the same CPUcan run concurrently on different CPUs,and synchronize with each other usingspin-locksBottom Halvesbuilt on softirqscan not run concurrently on different CPUsSpin Locks&Deferred Functionsspin_lock_bh()Implements the standard spinlockDisables softirqs
17、Allows the softirq to use non-preemption onlyspin_unlock_bh()Releases the spinlockEnables softirqsSpin Lock RulesDo not try to re-acquire a spinlock you already hold!Spinlocks should not be held for a long time!Do not sleep while holding a spinlock!SemaphoresSemaphores are locks that are safe to hol
18、d for longer periods of timeContention for semaphores causes blocking not spinningShould not be used for short duration critical sections!Can be used to synchronize with user contexts that might block or be preemptedSemaphore ImplementationImplemented as a wait queue and a usage countwait queue:list
19、 of processes blocking on the semaphoreusage count:number of concurrently allowed holdersdown()Attempts to acquire the semaphore by decrementing the usage count and testing ifit is negativeBlocks if usage count is negativeup()releases the semaphore by incrementing the usage count and waking up one o
20、rmore tasks blocked on itSemaphore ImplementationImplemented as a wait queue and a usage countwait queue:list of processes blocking on the semaphoreusage count:number of concurrently allowed holdersdown_interruptible()Returns EINTR if signal received while blockedReturns 0 on successdown_trylock()At
21、tempts to acquire the semaphoreOn failure it returns nonzero instead of blockingReader-Writer LocksNo need to synchronize concurrent readers unless a writer is presentBoth spin locks and semaphores have reader/writer variantsReader-Writer Spin Locksrwlock_t mr_rwlock=RW_LOCK_UNLOCKED;read_lock(&mr_r
22、wlock);/*critical section(read only).*/read_unlock(&mr_rwlock);write_lock(&mr_rwlock);/*critical section(read and write).*/write_unlock(&mr_rwlock);Reader-Writer Semaphoresstruct rw_semaphore mr_rwsem;init_rwsem(&mr_rwsem);down_read(&mr_rwsem);/*critical region(read only).*/up_read(&mr_rwsem);down_w
23、rite(&mr_rwsem);/*critical region(read and write).*/up_write(&mr_rwsem);ConclusionsWow!Why does one system need so many different ways of doingsynchronization?Actually,there are more ways to do synchronization in Linux,this isjust“locking”!ConclusionsOne size does not fit all:Need to be aware of different contexts in which code executes(user,kernel,interrupt etc)and the implications this has for whetherhardware or software preemption or blocking can occurThe cost of synchronization is important,particularly its impact onscalability
限制150内