Kernel Synchronization in Linux Professor M Khalil Students K Bean and W Jaffal CSE 8343 1 Abstract This survey paper introduces a kernel synchronization technique implemented by Linux a very popular and relatively new Unix like operating system The presented work considers uniprocessor and multiprocessor environments supported by Linux 2 Introduction As part of his computer science project at the University of Helsinki 1991 Linus Torvalds developed Linux to serve as an operating system for IBM compatible personal computers based upon the Intel 80386 microprocessor ME02 This work was presented in 1997 as a Master s thesis entitled Linux a Portable Operating System by L Torvalds LinTor97 Modern versions of Linux are now available on other architectures such as Alpha SPARC Motorola MC680x0 PowerPC and IBM System 390 In contrast with the Windowsbased operating systems Linux is not a commercial operating system Its source code under GNU General Public License is available to the public and is downloadable via http www kernel org In the Kernel Control Path section of this paper problems that could occur during kernel control path interleaving are investigated In Synchronization Techniques different techniques to avoid race conditions are considered In Linux Multiprocessor Architecture the SMP 1 multiprocessor architecture is compared with other architectures At the end of this section process synchronization on hardware level is considered In The Linux SMP Kernel Linux support of multiprocessor environment is described 3 Kernel Control Path Kernel processes execute due to the following reasons BC00 A process executing in User Mode caused some exception i e divide by zero An external device sent a signal to a Programmable Interrupt Controller using an IRQ with a corresponding interrupt being enabled According to BC00 a kernel control path is the sequence of instructions executed in Kernel Mode to handle a kernel request A kernel control path can handle various situations system calls exceptions or interrupts When one of the following conditions occurs the CPU does not execute a kernel control path sequentially A context switch occurs An interrupt occurs CPU starts processing another kernel control path A race condition outcome of some computation depends on how two or more processes are scheduled can occur not only when a user process is preempted by a higher priority process but when a CPU interleaves a kernel control path 2 4 Synchronization Techniques 4 1 Non preemptability of a Process in Kernel Mode According to BC00 the Linux kernel is not preemptive a higher priority process cannot preempt a process running in Kernel Mode The following assertions always hold true for a running process in Kernel Mode within Linux The process cannot be replaced by another process except when the former voluntary relinquish control of the CPU Interrupt or exception handling can preempt a running process however when an interrupt handle terminates the process resumes Only a kernel control path can interrupt another kernel control path 4 2 Atomic Operation As defined in BC00 an atomic operation is an operation performed by executing a single assembly language instruction therefore this instruction cannot be interrupted in the middle C language operations such as a a 1 or a could be implemented by a compiler as single atomic operations or it could be compiled into more complicated code To guarantee that some operations compiled every time as single atomic operations Linux kernel provides special functions such as 3 atomic int v v atomic dec v v and so on For more complete list of these functions see BC00 3 2 Interrupt Disabling The concept of a critical section only a single process executes in this section is introduced Such a task could be very complicated to code as a single atomic operation Interrupt disabling is one of the techniques implemented to ensure that a sequence of kernel statements is performed as a critical section In this case a kernel control path should not be interleaved while a hardware device issues an IRQ signal This technique does not always prevent kernel control path interleaving For example a program executed in Protected Mode could raise a Page Fault exception Because of its simplicity interrupt disabling is widely used by kernel functions for implementing a critical region Interrupts are disabled enabled by assembly language instructions placed at the beginning and at the end of the section To obtain a more detail description one can use BC00 as a reference According to the same authors a critical section should be short since any communication between CPU and I O is blocked while a kernel control path is running in this section 3 3 Locking Through Kernel Semaphores This locking technique allows a kernel process to access shared data entering a critical section only after acquiring a lock A kernel control path releases the lock after leaving the critical section allowing another kernel process to access shared data 4 According to BC00 Linux offers two kind of locking Kernel semaphores used by both uni processor and multiprocessor systems Spin Locks used by only multiprocessor systems Spin locks will be considered in a later section while introducing multiprocessor environments Implementation kernel semaphore described in BC00 is an object of type structure semaphore found within the include asm semaphore h file and has the following fields count an integer number Possible values of count o If count is greater than zero the resource is currently available o If count is less than or equal to zero the semaphore is busy and a protected resource is currently unavailable The absolute value of count should equal the number of kernel control paths waiting for resources o If count is equal to zero one kernel control path is using the resource and nothing is waiting for it to complete The count field is decremented when a process acquires the lock and is incremented when the same process releases it The value of count can be initialized to n in this case n processes can concurrently access the resource wait the address of a wait queue list that contains all blocking processes that are currently waiting for the resource If count is greater or equal than zero the wait queue is empty waking ensures only one of the sleeping process in the waiting queue can wake up and acquire a resource 5 When a process wishes to acquire a kernel semaphore lock it invokes the down function The