高级操作系统高级操作系统 (35).pdf

第 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 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(preemptable 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 disable;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 trueconcurrencyAlternatives 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 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 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(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 locks 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 SMPspin_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-lockShould 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 already 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 acquires 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 SMPspin_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 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 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 softirqsAllows 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 hold 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 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 ormore 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()Attempts 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_rwlock);/*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_write(&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