Kernel Synchronization in Linux.Professor: M.Khalil2. IntroductionThe 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.Figure 14.2 Pentium dual-processing system, process synchronization on hardware levelRAM chips may be accessed concurrently by independent CPUs. Since read/write operations on a RAM chip must be performed serially (according to [BC00]), a hardware circuit called a memory arbiter is inserted between the bus and every RAM chip. It grants access to a CPU if the chip is free and delays access if the chip is busy.Lock instruction prefixes (a special byte prefixed to an assembly language instruction) have been introduced. Whenever a control unit detects this byte, it locks the memory bus so that no other process can access the memory location specified by the destination operand of any following assembly language instruction.Distributed Interrupt HandlingFigure 2Kernel Synchronization in Linux.Professor: M.KhalilStudents: K. Bean and W. JaffalCSE 83431. AbstractThis survey paper introduces a kernel synchronization technique implemented by Linux, avery popular and relatively new Unix-like operating system. The presented work considersuniprocessor and multiprocessor environments supported by Linux.2. IntroductionAs part of his computer science project at the University of Helsinki (1991), LinusTorvalds developed Linux to serve as an operating system for IBM-compatible personalcomputers (based upon the Intel 80386 microprocessor) [ME02]. This work was presented in1997 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 Windows-based operating systems, Linux is not a commercial operating system. Its source code underGNU General Public License is available to the public and is downloadable viahttp://www.kernel.org/. In the “Kernel Control Path” section of this paper, problems that could occur during kernelcontrol path interleaving are investigated. In “Synchronization Techniques,” different techniques to avoid race conditions are considered. In “Linux Multiprocessor Architecture,” the SMP 1multiprocessor 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 PathKernel 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. 24. Synchronization Techniques4.1 Non-preemptability of a Process in Kernel ModeAccording 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 OperationAs 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:3atomic_int(v) v++atomic_dec(v) v— and so on.For more complete list of these functions, see [BC00].3.2 Interrupt DisablingThe 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. Interruptdisabling 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