Synchronization in Linux Kernel Programming

Explore per CPU variables as a simple, efficient synchronization technique by giving each CPU its own array element, preventing race conditions and aligning with main memory to avoid cache issues.

Explore how per CPU variables are implemented with a proc file per CPU, using read and write handlers, get_cpu and put_cpu to disable and enable preemption while updating values.

The 2.6 kernel introduces a per-cpu interface to simplify per-cpu data. It explains compile-time static definitions, get and put interfaces, preemption control, and l-values.

Define a per-CPU variable, assign an initial value of five, disable kernel preemption to obtain an lvalue, increment it, re-enable preemption, and verify the value increments from five to six.

Use per cpu variables and cpu id to access other processors with locking, initialize per cpu counters, and increment to ten while reflecting updates across online cpus.

Learn to use the for_each_online_cpu macro to iterate over online CPUs in the Linux kernel, replacing manual for loops and aligning code with the num_online_cpus count.

Allocate per cpu data at runtime using the per cpu wrapper, returning a void pointer for each processor. Access the data by the pointer, disabling preemption and then re-enabling it.

Explore the problems with per-cpu variables, including lack of protection against asynchronous functions and interrupt handler interactions. Apply additional synchronization primitives to safely share data across interrupt handlers and CPUs.

Two kernel threads increment a shared global variable using non-atomic read-modify-write operations, causing race conditions and inconsistent results due to non-atomic memory access and bus arbitration.

Learn how atomic operators in the Linux kernel ensure race-free read-modify-write sequences using atomic_t, atomic.h, and lock instructions, with differences on SMP versus uniprocessor kernels.

Explore atomic operations in Linux kernel programming, using atomic.h macros such as atomic_init, atomic_inc, atomic_dec, atomic_set, atomic_read, atomic_add, and atomic_sub to ensure read-modify-write safety across CPUs.

Explore common uses of atomic operations in the Linux kernel, focusing on atomic integers to implement counters and track transmitted and received packets without heavy locking.

Understand architecture-dependent atomic operations in the Linux kernel, including decrement, increment, subtract, and add with test variants, illustrated through atomic.h usage in arch and include directories.

Explore atomic add, subtract and return to perform modification and read the latest value in a single atomic call, building on atomic add, increment, decrement, and test APIs.

Learn about atomic fetch add, atomic fetch subtract, compare and exchange, and simple exchange. These operations read the current value and return the prefetched (pre-operation) value, not the post-operation result.

Explore 64-bit atomic operations in Linux kernel programming, using atomic64_t and atomic_64 APIs, with hashed spinlocks as fallback for unsupported architectures and applications in the performance counter subsystem.

Explore how the Linux kernel provides architecture-specific atomic bitwise operations via header implementations, using generic pointers to set, clear, and toggle bits (0–31 or 0–63) with practical examples.

Explore atomic bitwise operations in linux kernel programming, including test and set bit, test and clear bit, and test and change bit, all returning the old value (0 or 1).

Explore non-atomic bitwise operations in Linux kernel programming, comparing non-atomic versions to atomic operations to understand when non-atomic may be faster, depending on processor single instruction cycles.

Limit atomic operations to word or doubleword sizes; custom structures or shared data cannot be updated atomically, while spin locks protect short critical sections by allowing only one CPU.

Learn how spinlocks in the Linux kernel protect short critical sections to ensure atomicity and prevent race conditions by using spin_lock and spin_unlock with spinlock_t.

learn how to initialize a spinlock at runtime using malloc, choosing between static or dynamic allocation. initialize to unlock, then lock, unlock, and free the memory.

Demonstrates a spinlock controlling access to a shared counter between two kernel threads, forming a critical section where only one CPU updates the counter at a time.

In the Linux kernel, spinlocks are not recursive; acquiring a spinlock already held by the same CPU causes busy spinning and deadlock, potentially stalling the CPU.

Explore implementing a busy loop using a spinlock in a character device driver to guard a shared buffer with lock in open and unlock in Linux kernel programming.

Explain how spin_trylock tries to acquire a lock, returning zero if unavailable and non-zero if successful, and how spin_lock and spin_unlock coordinate with it in kernel code.

Use spinlocks with irqsave to protect resources shared by process and interrupt contexts; disable interrupts, enter a critical section, and restore prior interrupt state after unlock.

Learn how kernel preemption interacts with spinlocks: preemption is disabled in the spinlock critical region and re-enabled on unlock, with uniprocessor and multiprocessor implications.

Understand key spinlock considerations in Linux kernel programming: keep critical regions short, avoid long holds to prevent deadlocks, and ensure no sleeping operations inside spinlocks.

This lecture demonstrates calling sleep (msleep) inside a spinlock with preemption disabled, explaining potential deadlock and why sleep in a spinlock is not recommended.

Explain spinlock behavior on uniprocessor systems, showing how preemption settings turn spinlocks into empty operations, especially when used between interrupts or in process context.

Explain how spinlocks implement mutual exclusion using a lock bit in a two-state model (locked and unlocked), with busy-wait loops and architecture-specific atomic operations in the linux code.

Understand Linux semaphores as slipping locks that allow sleeping inside a lock, and learn how a waiting task in a queue is awakened when the semaphore becomes available.

Learn how a Linux kernel semaphore uses an integer value and two operations, P and V, to control entry into critical sections; P blocks when zero, and V wakes waiters.

Explore how spin locks and semaphores control access to a critical section by setting a usage count, with binary semaphores for mutual exclusion and counting semaphores for multiple holders.

Explore whether counting semaphores can be used in a critical section and learn that binary semaphores are used in the kernel for mutual exclusion.

Learn the Linux semaphore API and its kernel implementation, including struct semaphore with a spinlock, usage count, and wait list, plus dynamic and static initialization using down and up.

Allocate memory for a semaphore with malloc and initialize it to one to create a binary semaphore. Decrement to enter the critical section and up to end it.

Linux kernel module example using semaphore down and up to control access to a critical region, showing initialization, decrementing and incrementing the count, and printed values.

Demonstrate a Linux kernel module example of calling down twice on a binary semaphore, managing entry to a critical region and queuing when blocked, and examining uninterruptible task state.

Explore a linux kernel module example that uses a binary semaphore to implement producer–consumer synchronization, with a shared buffer, mutual exclusion via down and up, and thread sleep behavior.

Explore the distinction between down and down_interruptible in linux kernel synchronization: how interruptible sleep lets a waiting process receive signals and return, unlike uninterruptible sleep.

Explore the semaphore down_trylock API: it acquires when available and returns non-zero if not. Starting with value one, down makes it zero, and a second down blocks.

Explain the down_timeout semaphore API in Linux kernel programming, which uses a timer value to wait for a semaphore; if available, it returns zero, else it sleeps and returns ETIMEDOUT.

Explore how down_killable restricts signal delivery to fatal signals in Linux kernel programming, while down_interruptible allows any signal to be delivered, as shown with SIGKILL.

Use semaphores for long-held locks, not short ones, due to queueing and sleeping overhead. They cannot run in interrupt context, do not disable preemption, and offer better utilization than spinlocks.

Compare spinlock and semaphore choices in Linux kernel synchronization by evaluating interrupt context, sleeping behavior, and lock duration; use spinlocks for short, non-sleeping operations, semaphores for longer or sleeping ones.

The lecture covers Linux 2.6 mutex as a sleeping, owner-checked mutual exclusion primitive that improves on binary semaphores by restricting unlocks to the owner and prohibiting recursion and interrupt context.

Compare mutex and semaphore: mutex uses fast, mid (optimistic spinning with a sequence lock), and slow paths for lock acquisition, while semaphore simply decrements and sleeps when zero.

Explore mutex design in the Linux kernel, focusing on fast path, mid path, and slow path within the locking code, and review mutex lock implementation in the kernel source.

Demonstrates how to use a mutex to protect a critical section by including the header, allocating, initializing, locking, unlocking, and freeing the mutex.

Illustrate a Linux kernel module example using the mutex API with static initialization. Defining a mutex eliminates extra initialization steps, demonstrating how static initialization secures synchronization.

demonstrates sleeping in a mutex protected critical section inside a Linux kernel module, showing that sleep is allowed when holding a mutex but not when using a spin lock.

Explore how mutex_trylock in Linux kernel programming returns 1 or 0, ensuring only one thread can acquire the mutex while another waits during a two-second sleep in the critical section.

Explore how unlocking a mutex from a non-owner thread behaves in Linux kernel programming, highlighting ownership checks, debug mutexes, and warning logs when debug options are enabled.

Explore why recursive mutex locks trigger errors in Linux kernel synchronization, inspect debug mutexes, spinlocks, and semaphore behavior, and understand the owner field role in mutex structures.

Explore the mutex is locked api that reports whether a mutex is locked or unlocked and helps avoid recursive mutex before locking. Return 1 when locked, 0 when unlocked.

Start with mutexes and only move to a semaphore or binary semaphore if mutex rules are not suitable, because mutexes have lower overhead and stricter semantics not present in semaphores.

Compare spinlocks and mutexes by evaluating logging overhead and lock hold time, and decide based on interrupt context and whether sleeping is required; spinlocks are needed in interrupt contexts.

Demonstrates a mutex-protected shared counter in a proc file with read and write operations, showing how a single lock blocks concurrent reads.

Explore how Linux kernel synchronization solves the read-write challenge by using reader-writer semaphores and spinlocks to allow multiple concurrent readers while ensuring a single writer enters at a time.

Introduce the read-write spinlock API, including rw_lock_t structures and read_lock/read_unlock and write_lock/write_unlock, and compare it to spinlock reader and writer variants.

Demonstrate a Linux kernel module using a rw spinlock with two readers and one writer, illustrating read and write locks, contention, and the impact of delays.

Acquire a read lock then request a write lock and see that upgrading does not occur here, causing a deadlock as the write lock waits for the reader to unlock.

Examine recursive read locks in Linux kernel programming, showing they are possible since a read lock allows multiple readers; note recursive spinlocks are not possible.

Explore how a read lock allows multiple readers to proceed while a writer waits for exclusive access, illustrating first-in, first-out fairness and writer starvation avoidance in the Linux kernel.

Illustrates a Linux kernel module example using rwlocks with three kernel threads performing read and write locks, showing how lock contention and access order evolve during sleeps.

Examine how four kernel threads contend for read and write access with rwlocks, highlighting non-deterministic ordering due to spin locks and the observed race in lock acquisition.

Explore how read-write semaphores in the Linux kernel use binary mutexes for writer-only mutual exclusion, with the rw semaphore structure and an initial zero value.

Demonstrates how read and write locks are acquired and released using down_read, up_read, down_write, up_write, with upgrade and downgrade, including an uninterruptible sleep when locking.

Learn how down_read_trylock and down_write_trylock in Linux kernel synchronization work: they return 1 when the lock is acquired, unlike the normal semaphore behavior which returns 0 on success.

Downgrade_write converts an acquired write lock to a read lock, enabling a quick write followed by longer read access in Linux kernel synchronization.

Analyze the recursive write locks in Linux kernel programming, identify possible deadlocks and the interruptable and uninterruptible task states, and explain why we may need to restart the machine.

Demonstrates a Linux kernel module example using multiple threads contending for read and write locks, detailing acquisition and release sequences and observed behavior under contention.

Explore synchronization in Linux kernel programming by examining reader-writer locks for concurrent read access, compare them with mutexes and spinlocks, and discuss solving writer starvation in critical sections.

The lecture explains lock-free and wait-free synchronization in the real-time Linux kernel, introducing sequence lock and read-copy-update to remove data locking and enable concurrent reads.

Enable fast, lock-free access for many readers; sequence locks added in Linux 2.6 permit writers to modify data during reads, while readers verify data validity with a sequence counter.

Learn how a sequence lock uses a sequence counter and a spinlock to sync readers and writers, with spinlocks for writes and an initial zero value.

Explain how a write operation uses a write sequence lock to ensure mutual exclusion with a spin lock, incrementing the sequence number on both lock and unlock, starting from zero.

Explain how sequence lock enables lock-free reads: readers check the sequence number before and after data and retry when it becomes odd or mismatched.

Explore the Linux kernel sequence lock concept, using a sequence counter to guard reads and writes, illustrating retry on data invalidation and the behavior without locks.

Examine how kernel preemption is disabled for writers and remains unpreempted for readers when no lock is acquired, highlighting spinlocks and sequence locks.

Use sequence locks only for normal data like integers and booleans, and avoid applying them to pointers because pointers can be freed or change during writes, risking dereferencing invalid memory.

Explore how sequence locks protect a 64-bit uptime value in the Linux kernel, with examples showing their use across kernel time operations and related functions.

Explore sequence locks and their interrupt-ready variants, and learn how to handle contexts that run in both interrupts and process context by saving and restoring state.

Discover read-copy-update (RCU) in the Linux kernel: enable a single writer to update pointer-based data structures without blocking readers, by copying the structure and swapping the pointer after readers finish.

Demonstrates lock-free linked-list deletion by bypassing node B (set A's next to C), waiting for readers to move on, and safely freeing B after no readers remain.

Explore the RCU design with read side critical sections and synchronization, and learn to use RCU assign pointer to update a global pointer for lock-free reads.

Use rcu_assign_pointer to enforce update order by employing memory barriers, preventing CPU and compiler reordering from disrupting pointer updates.

Learn how to perform a read operation under RCU by wrapping access in an RCU_read_lock and RCU_read_unlock read critical section, and use RCU_dereference to access a global pointer between them.

Learn why rcu_dereference prevents unsafe direct dereferences of global pointers by enforcing memory barriers and read locks. Use RCU assigned pointers and RCU references only between RCU read locks.

Demonstrate read and write threads using RCU to update a global pointer, with read side critical section and no locks, illustrating RCU’s speed.

this linux kernel module shows read and write threads updating a global pointer, revealing a memory leak from not freeing memory and need for a temporary pointer to update safely.

Explore rcu memory management: removal and reclamation occur after pre-existing readers finish, with reads inside rcu read side critical sections and pointers updated by rcu assign.

Block the calling process until all pre-existing read-side critical sections on all CPUs complete, then safely reuse or remove the old memory after synchronize_rcu returns.

Use call_rcu to defer work until all read-side critical sections finish. Embed an rcu head, register rcu_free with call_rcu, and use container_of.

Shows that RCU read-side critical sections can be nested when there is no blocking or sleeping, using memory barriers instead of locks.

Explore how synchronize_rcu works internally by tracking completion of read side critical sections through read lock, read unlock, and preemption, using context switches as the signal that readers finished.

Explore rcu terminology, including quiescent state, read side critical section, creation state, and grace period, and learn how synchronize_rcu waits for readers to finish or reach a safe state.

Learn how to implement a lock-free linked list using RCU variants for list APIs, addressing race conditions between readers and writers with RCU assigned pointers.

Learn how to implement rcu linked lists in a Linux kernel module, using a spinlock to serialize multiple writers while allowing concurrent readers.

RCU offers lock-free read operations, eliminates the need for read retries, and removes contention, enabling perfect latency measurements.

Explore synchronization in Linux kernel programming by comparing rcu and sequence lock, discussing readers and writers, grace period, copy operations, and memory costs.