Kernel Synchronization in Linux Uni processor and Multi processor Environment By 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 Conclusion Linux 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 License Kernel 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 Interrupts Synchronization Technique Nonpreemptability Atomic Operations Interrupt Disabling Locks Condition 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 systems Kernel 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 waiting The 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 sleep Kernel 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 Continued CPU 1 CPU n system bus Graphical card Memory 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 memory Hardware Support for Synchronization Shared Memory Memory 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 Synchronization Hardware cache is utilized using the locality principle In multiprocessor environment each CPU has its own cache Process of updating cache cache snooping Hardware 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 location Hardware Support for Synchronization Continued Distributed Interrupt Handling CPU 1 CPU n Local APIC Local APIC ICC bus I O APIC IRQ lines APIC Advanced Programmable Interrupt Controller ICC Interrupt Controller Communication I O APIC router Linux SMP Kernel Process Descriptor Modification has cpu if has cpu 0 process is running Processor logical number of its CPU Spin Locks Blocked 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 system Supports up to 32 CPUs Bibliography 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 Kernel Prentice Hall PTR 2002 Thank You Any Questions