Kernel Synchronization in Linux Uni-processor and Multi-processor EnvironmentTopicsLinux HistoryKernel Control PathSynchronization TechniqueCondition to be PreemptedAtomic OperationInterrupt DisablingLockingKernel Semaphore ImplementationKernel Semaphore Implementation, ContinuedSlide 12SMP ArchitectureSMP Architecture, ContinuedOther Multiprocessor ArchitecturesHardware Support for SynchronizationHardware Support for Synchronization, ContinuedSlide 18Linux/SMP KernelConclusionBibliographyThank YouKernel Synchronization in Linux Uni-processor and Multi-processor EnvironmentBy Kathryn Bean and Wafa’ Jaffal (Group A3)TopicsLinux HistoryKernel Control PathSynchronization TechniqueSMP ArchitectureHardware Support for Synchronization (Pentium-based Architecture)Linux/SMP kernelConclusionLinux HistoryUniversity of Helsinki (1997), Master’s thesis –“Linux, a Portable Operating System” by L. Torvalds OS for IBM-compatible personal computers (Intel 80386 microprocessor). Source code under GNU General Public LicenseKernel Control PathKernel control path is the sequence of instructions executed in Kernel Mode to handle a kernel request. Kernel control path executes due to the following reasons:–System calls –Exceptions–InterruptsSynchronization TechniqueNonpreemptabilityAtomic OperationsInterrupt DisablingLocksCondition to be Preempted•Kernel control path can preempt a running process; however, when an interrupt handle terminates, the process resumes.•Only kernel control path can interrupt another kernel control path.Atomic Operation•An atomic operation - performed by executing a single assembly language instruction •Linux kernel provides special functions such as:atomic_int(v)  v++Interrupt DisablingBecause of its simplicity, interrupt disabling is used by kernel functions for implementing a critical region. This technique does not always prevent kernel control path interleaving. Critical section should be short because any communication between CPU and I/O is blocked while a kernel control path is running in this section.LockingTwo kinds of locking:–Kernel semaphores, used by both uni-processor and multiprocessor systems –Spin Locks, used by only multiprocessor systemsKernel Semaphore ImplementationKernel semaphore – is object of type structure semaphore, see include/asm/semaphore.h file Fields–count – integer numbercount > 0 – semaphore is availablecount  0 – semaphore is busy, |count| - number of processes waiting for resource.Count = 0 – one use, nothing is waitingThe count field is decremented when a process acquires the lock and is incremented when the same process releases it.Kernel Semaphore Implementation, Continued–wait – the address of a wait queue.–waking – integer. The releasing process increments waking field(s).Each of awakened process PI then enters a critical region of the down() functionIs PI’s waking <> 0, if waking > 0 – 1. acquire the resource 2. other PK’s waking-- if waking < 0 – go back to sleepKernel Semaphore Implementation, ContinuedFunction–down() – called, if process wishes to acquire a semaphore.count --count <> 0, if count  0 – process enter the critical section if count < 0 – process is suspended–up() – called, if process releases a semaphorecount ++count <> 0 – if count > 0 – up() terminates if count < 0 – wake up other processesDeadlock – semaphore requests are performed in the address order.SMP ArchitectureScalability of Linux - supports multiprocessing through Shared Memory Symmetric Multiprocessors (SMM) architecture.scalability is the capability of a system to adapt to an ever-increasing work load.SMP Architecture, Continuedsystem busCPU 1 CPU nGraphical cardMemory• CPUs share the same memory unit• application processing and kernel processing are spread amongst all CPUs.Other Multiprocessor ArchitecturesAsymmetric Multiprocessing Master CPU executes the operating system code and application programs run on the remaining CPUs. Massively Parallel Processing (MPP) Assemble hundreds or thousand of CPUs, each with own system memoryHardware Support for Synchronization Shared MemoryMemory arbiter – (chip between bus and every RAM chip) grants access to a CPU if the chip is free and delays access if the chip is busy. Cache SynchronizationHardware cache is utilized using the locality principle. In multiprocessor environment, each CPU has its own cache. Process of updating cache -cache snoopingHardware Support for Synchronization, ContinuedSMP Atomic Operation–Lock instruction prefixes for atomic operations were introduced.–If control unit detects them  lock the memory bus, no other processes can access this memory locationHardware Support for Synchronization, Continued• Distributed Interrupt HandlingICC busLocal APIC Local APICI/O APICCPU 1 CPU nIRQ linesAPIC – Advanced Programmable Interrupt ControllerICC – Interrupt Controller Communication I/O APIC - routerLinux/SMP Kernel Process Descriptor Modification–has_cpu: if has_cpu > 0 – process is running–Processor – logical number of its CPUSpin LocksBlocked process keeps its own CPU by spinning while waiting for a resource.ConclusionModern versions of Linux are available –Compaq Alpha –SPARC–PowerPC–Motorola MC680x0 –IBM System/390 Multiprocessor operating systemSupports up to 32 CPUsBibliographyD. P. Bovet, M. Cesati. Understanding the Linux Kernel. O’Reilly, 2000Linus Torvalds. Linux: a Portable Operating System. Master of Science Thesis, University of Helsinki, Finland, 1997D. Mosberg, S. Eranian IA-64 Linux KernelPrentice Hall PTR, 2002Thank YouAny