When Synchronization Is Not Necessary
by Marco Cesati, Daniel P. Bovet
Understanding the Linux Kernel, Second Edition
- Understanding the Linux Kernel, 2nd Edition
- Preface
- 1. Introduction
- Linux Versus Other Unix-Like Kernels
- Hardware Dependency
- Linux Versions
- Basic Operating System Concepts
- An Overview of the Unix Filesystem
- An Overview of Unix Kernels
- 2. Memory Addressing
- 3. Processes
- 4. Interrupts and Exceptions
- 5. Kernel Synchronization
- Kernel Control Paths
- When Synchronization Is Not Necessary
- Synchronization Primitives
- Synchronizing Accesses to Kernel Data Structures
- Choosing Among Spin Locks, Semaphores, and Interrupt Disabling
- Protecting a data structure accessed by exceptions
- Protecting a data structure accessed by interrupts
- Protecting a data structure accessed by deferrable functions
- Protecting a data structure accessed by exceptions and interrupts
- Protecting a data structure accessed by exceptions and deferrable functions
- Protecting a data structure accessed by interrupts and deferrable functions
- Protecting a data structure accessed by exceptions, interrupts, and deferrable functions
- Choosing Among Spin Locks, Semaphores, and Interrupt Disabling
- Examples of Race Condition Prevention
- 6. Timing Measurements
- 7. Memory Management
- Page Frame Management
- Memory Area Management
- The Slab Allocator
- Cache Descriptor
- Slab Descriptor
- General and Specific Caches
- Interfacing the Slab Allocator with the Buddy System
- Allocating a Slab to a Cache
- Releasing a Slab from a Cache
- Object Descriptor
- Aligning Objects in Memory
- Slab Coloring
- Local Array of Objects in Multiprocessor Systems
- Allocating an Object in a Cache
- Releasing an Object from a Cache
- General Purpose Objects
- Noncontiguous Memory Area Management
- 8. Process Address Space
- The Process’s Address Space
- The Memory Descriptor
- Memory Regions
- Page Fault Exception Handler
- Creating and Deleting a Process Address Space
- Managing the Heap
- 9. System Calls
- 10. Signals
- 11. Process Scheduling
- 12. The Virtual Filesystem
- 13. Managing I/O Devices
- I/O Architecture
- Device Files
- Device Drivers
- Block Device Drivers
- Character Device Drivers
- 14. Disk Caches
- 15. Accessing Files
- 16. Swapping: Methods for Freeing Memory
- What Is Swapping?
- Swap Area
- The Swap Cache
- Transferring Swap Pages
- Swapping Out Pages
- Swapping in Pages
- Reclaiming Page Frame
- 17. The Ext2 and Ext3 Filesystems
- 18. Networking
- 19. Process Communication
- 20. Program Execution
- A. System Startup
- B. Modules
- C. Source Code Structure
- 21. Bibliography
- Index
- Colophon
As already pointed out, the Linux kernel is not preemptive — that is, a running process cannot be preempted (replaced by a higher-priority process) while it remains in Kernel Mode. In particular, the following assertions always hold in Linux:
No process running in Kernel Mode may be replaced by another process, except when the former voluntarily relinquishes control of the CPU.[38]
Interrupt, exception, or softirq handling can interrupt a process running in Kernel Mode; however, when the handler terminates, the kernel control path of the process is resumed.
A kernel control path performing interrupt handling cannot be interrupted by a kernel control path executing a deferrable function or a system call service routine.
Thanks to these assertions, on uniprocessor systems kernel control paths dealing with nonblocking system calls are atomic with respect to other control paths started by system calls. This simplifies the implementation of many kernel functions: any kernel data structures that are not updated by interrupt, exception, or softirq handlers can be safely accessed. However, if a process in Kernel Mode voluntarily relinquishes the CPU, it must ensure that all data structures are left in a consistent state. Moreover, when it resumes its execution, it must recheck the value of all previously accessed data structures that could be changed. The change could be caused by a different kernel control path, possibly running the same code on behalf of a separate process.
As you would expect, things are much more complicated in multiprocessor systems. Many CPUs may execute kernel code at the same time, so kernel developers cannot assume that a data structure can be safely accessed just because it is never touched by an interrupt, exception, or softirq handler.
The rest of this chapter describes what to do when synchronization is necessary — i.e., how to prevent data corruption due to unsafe accesses to shared data structures.
[38] Of course, all process switches are performed in Kernel Mode. However, a process switch may occur only when the current process is going to return in User Mode.
-
No Comment