Kernel Synchronization

• critical regions: Code paths that access and manipulate shared data are called critical regions
• atomic operation: operations complete without interruption as if the entire critical region were one indivisible instruction
• Race condition: it is the condition when two threads of execution to be simultaneously executing within the same critical region.
• If the critical region is a very minimal instruction, making the execution as atomic operation will avoid the race condition. For eg, i++ will be performed by 3 or 4 instructions in assembly language. This can be made as an atomic operation for synchronization.
• The kernel provides two sets of interfaces for atomic operations—one that operates on integers and another that operates on individual bits.These interfaces are implemented on every architecture that Linux supports. Most architectures contain instructions that provide atomic versions of simple arithmetic operations. Other architectures, lacking direct atomic operations, provide an operation to lock the memory bus for a single operation, thus guaranteeing that another memory-affecting operation cannot occur simultaneously.
• Generally, a few instructions can be made atomic by the processor. When a huge instructions are to be synchronized, a locking mechanism is required. In this case only the locking operation will be atomic.
• Locking mechanisms can be different that when a thread finds that a critical region is locked, it can busy wait(eg, spin lock) or sleep.
• On the popular x86 architecture, locks are implemented using such an instruction called compare and exchange.
• Causes of concurrency in user space programs.
• true concurrency occurs because of multi processors.
• pseudo-concurrency occurs because of preemption(or yielding) or receiving of signals in a user space program.
• Causes of concurrency in kernel space programs.
• Interrupts— An interrupt can occur asynchronously at almost any time, interrupting the currently executing code.
• Softirqs and tasklets— The kernel can raise or schedule a softirq or tasklet at almost any time, interrupting the currently executing code.
• Kernel preemption— Because the kernel is preemptive, one task in the kernel can preempt another.
• Sleeping and synchronization with user-space— A task in the kernel can sleep and thus invoke the scheduler, resulting in the running of a new process.
• Symmetrical multiprocessing— Two or more processors can execute kernel code at exactly the same time.
• The term lock contention, or simply contention, describes a lock currently in use but that another thread is trying to acquire.
• spin lock:
• A spin lock is a lock that can be held by at most one thread of execution.
• If a thread of execution attempts to acquire a spin lock while it is already held, which is called contended, the thread busy loops—spins—waiting for the lock to become available.
• It is not wise to hold a spin lock for a long time.This is the nature of the spin lock: a lightweight single-holder lock that should be held for short durations.
• Making the process to sleep if the lock is already contended incurs a bit of overhead—most notably the two context switches required to switch out of and back into the blocking thread, which is certainly a lot more code than the handful of lines used to implement a spin lock.Therefore, it is wise to hold spin locks for less than the duration of two context switches.
• On uniprocessor machines, the locks compile away and do not exist; they simply act as markers to disable and enable kernel preemption. If kernel preempt is turned off, the locks compile away entirely.
• Spin locks can be used in interrupt handlers, whereas semaphores cannot be used because they sleep.
• If a lock is used in an interrupt handler, you must also disable local interrupts (interrupt requests on the current processor) before obtaining the lock. Otherwise, it is possible for an interrupt handler to interrupt kernel code while the lock is held and attempt to reacquire the lock.The interrupt handler spins, waiting for the lock to become
  available.The lock holder, however, does not run until the interrupt handler completes. This is an example of the double-acquire deadlock. Note that you need to disable interrupts only on the current processor. If an interrupt occurs on a different processor, and it spins on the same lock, it does not prevent the lock holder (which is on a different processor) from eventually releasing the lock.
• Because a bottom half might preempt process context code, if data is shared between a bottom-half process context, you must protect the data in process context with both a lock and the disabling of bottom halves. Likewise, because an interrupt handler might preempt a bottom half, if data is shared between an interrupt handler and a bottom half, you must both obtain the appropriate lock and disable interrupts
• reader-writer spin lock
•