Linux Kernel

The kernel exposes its interface through file-like mechanisms, though these files don’t actually exist.

System Calls

System calls provide system services for applications and can only be executed by the operating system kernel. Applications, as callers, must execute a trap or system call instruction to transfer control to the operating system. The operating system identifies the required calling process through parameter checking.

System call parameters are pushed onto the stack in reverse order. The system call number is placed in a specific register, then assembly executes the TRAP instruction to enter kernel mode, switching from user mode to kernel mode and beginning execution of kernel code. The kernel checks the call number and issues the correct system call processing command. The number jumps to the pointer table of the system call processor to complete the operation. After handler execution, control returns to the library procedure in user space. From the user’s perspective, this process is almost identical to a function call - cleaning up the stack and continuing execution.

Process Scheduling Algorithms

In Linux scheduling algorithms, processes are divided into two types: I/O-intensive and CPU-intensive. Therefore, to improve response speed, I/O-intensive programs should have higher priority to enhance their interactivity.

For ordinary processes, Linux uses dynamic priority scheduling, selecting processes based on the size of the process counter, which indicates the number of time slices available for use. For real-time processes, Linux employs two scheduling strategies: FIFO (First-In-First-Out scheduling) and RR (Round-Robin time-slice scheduling).

Kernel-Process Communication

1. User context environment
2. Software and hardware interrupts
3. Netlink sockets, where users create sockets and send process IDs to the kernel

Interrupts

Since the operating system also needs to manage hardware, it handles hardware requests through interrupt methods. Interrupts can be categorized into four types: interrupts, faults, traps, and aborts. Interrupts are asynchronous requests from IO devices.

Locking Mechanisms

• Atomic operations: Atomic operations are less efficient than normal operations, so they should only be used when necessary and cannot be mixed with normal operations. In single-core processors, atomic operations are the same as normal operations.
• Spin locks: Processes waiting for unlocking repeatedly check whether the lock is released without entering sleep state (busy waiting), so they are often used for short-term protection of code segments. In x86 systems, this is implemented by locking the bus through assembly instructions.
• Semaphores and mutexes: Competing for semaphores and mutexes requires process sleeping and waking, which has high overhead, making them unsuitable for short-term code protection but appropriate for protecting longer critical sections. Mutexes are used for thread mutual exclusion, while semaphores are used for thread synchronization.

CAS (Compare And Swap)

Fundamentally optimistic, if operations don’t occur for extended periods, it wastes CPU time. Double CAS can be used - dual insurance CAS to solve ABA problems, such as when checking 64-bit content on a 32-bit system.

Use CAS once to check double-length values, where the first half is a pointer (or version number) and the second half is a counter. Only when both match does the check pass to assign a new value, and the counter increments by 1. This way, when ABA occurs, although the value is the same, the counter differs (but on 32-bit systems, this counter will overflow and start from 1 again, still causing ABA problems).

Scheduled Tasks - Crontab

Early scheduled tasks were checked every minute, which was too resource-intensive. A min-heap is maintained where the top of the heap is the task to execute first, allowing sleep until the task needs to be executed before waking up to execute.

Process Sleep

sleep() The process is as follows:

1. Suspend the process (or thread) and modify its running state
2. Set a timer using the parameter provided by sleep()
3. When time expires, the timer triggers and the kernel receives an interrupt to modify the process (or thread) running state. For example, threads are marked as ready and enter the ready queue waiting for scheduling

pause() Sleep until the process receives a signal

Kernel Threads

Since processes and threads are not distinguished in the kernel, they can also be called kernel processes. Unquestionably, kernel threads are represented in the kernel through the task_struct structure as well.

Kernel threads are also scheduling entities for the kernel just like ordinary processes, except they have the following differences:

Kernel threads always run in kernel mode, while different processes can run in either user mode or kernel mode. From another perspective, kernel threads can only use address spaces greater than PAGE_OFFSET (i.e., 3GB), while ordinary processes can use the entire 4GB address space.

The difference between kernel threads and ordinary processes lies in that kernel threads do not have independent address spaces; the mm pointer is set to NULL. They only run in kernel space and never switch to user space; and like ordinary processes, they can be scheduled and preempted.