Process management is an integral part of any modern-day operating system. The OS must allocate resources to processes, enable processes to share and exchange information, protect the resources of each process from other processes and enable synchronization among processes. To meet these requirements, the OS must maintain a data structure for each process, which describes the state and resource ownership of that process, and which enables the OS to exert control over each process.

From the process management point of view, the Linux kernel is a preemptive multitasking operating system. As a multitasking OS, it allows multiple processes to share processors (CPUs) and other system resources. Each CPU executes a single task at a time. However, multitasking allows each processor to switch between tasks that are being executed without having to wait for each task to finish. For that, the kernel can, at any time, temporarily interrupt a task being carried out by the processor, and replace it by another task that can be new or a previously suspended one. The operation involving the swapping of the running task is called context switch.

💾 History: Till 2.6.39, kernel mode has only one thread protected by big kernel lock.

Processes

Process is a running user space program. Kernel starts the first process /sbin/init in function run_init_process _idusing kernel_execve _id. Processes occupy system resources, like memory, CPU time. System calls sys_fork _id and sys_execve _id are used to create new processes from user space. The process exit with an sys_exit _id system call.

Linux inherits from Unix its basic process management system calls (⚲ API ↪ ⚙️ implementations):

man 2 fork ↪ kernel_clone _id or _do_fork _id creates a new process by duplicating the process invoking it.

man 2 _exit ↪ do_exit _id terminates the calling process "immediately". Any open file descriptors belonging to the process are closed.

man 2 wait ↪ kernel_waitid _id suspends the execution of the calling process until one of its children processes terminates.

man 2 execve ↪ do_execve _id runs an executable file in the context of current process, replacing the previous executable. This system call is used by family of functions of libc man 3 exec

Linux enhances the traditional Unix process API with its own system calls man 2 clone. Clone creates a child process that may share parts of its execution context with the parent. It is often used to implement threads (though programmers will typically use a higher-level interface such as man 7 pthreads, implemented on top of clone).

📚 References

• unistd.h
• sys/types.h
• sys/wait.h
• fork (system call)
• exit (system call)
• wait (system call)
• exec (system call)

Threads or tasks

In Linux kernel "thread" and "task" are almost synonyms.

⚲ API

• linux/sched.h _inc - the main scheduler API
  • task_struct _id
• arch/x86/include/asm/current.h _src
  • current _id and get_current _id () return current task_struct _id
• uapi/linux/taskstats.h _inc per-task statistics
• linux/thread_info.h _inc
  • function current_thread_info _id() returns thread_info _id
• linux/sched/task.h _inc - interface between the scheduler and various task lifetime (fork()/exit()) functionality
• linux/kthread.h _inc - simple interface for creating and stopping kernel threads without mess.
  • kthread_run _id creates and wake a thread
  • kthread_create _id

⚙️ Internals

• kthread_run _id
  • kernel_thread _id
    • kernel_clone _id
• kernel/kthread.c _src

Process Scheduling

The process scheduler is the part of the operating system that decides which process runs at a certain point in time. It usually has the ability to pause a running process, move it to the back of the running queue and start a new process.

Active processes are placed in an array called a run queue, or runqueue - rq _id. The run queue may contain priority values for each process, which will be used by the scheduler to determine which process to run next. To ensure each program has a fair share of resources, each one is run for some time period (quantum) before it is paused and placed back into the run queue. When a program is stopped to let another run, the program with the highest priority in the run queue is then allowed to execute. Processes are also removed from the run queue when they ask to sleep, are waiting on a resource to become available, or have been terminated.

Linux uses the Completely Fair Scheduler (CFS), the first implementation of a fair queuing process scheduler widely used in a general-purpose operating system. CFS uses a well-studied, classic scheduling algorithm called "fair queuing" originally invented for packet networks. The CFS scheduler has a scheduling complexity of O(log N), where N is the number of tasks in the runqueue. Choosing a task can be done in constant time, but reinserting a task after it has run requires O(log N) operations, because the run queue is implemented as a red–black tree.

In contrast to the previous O(1) scheduler, the CFS scheduler implementation is not based on run queues. Instead, a red-black tree implements a "timeline" of future task execution. Additionally, the scheduler uses nanosecond granularity accounting, the atomic units by which an individual process' share of the CPU was allocated (thus making redundant the previous notion of timeslices). This precise knowledge also means that no specific heuristics are required to determine the interactivity of a process, for example.

Like the old O(1) scheduler, CFS uses a concept called "sleeper fairness", which considers sleeping or waiting tasks equivalent to those on the runqueue. This means that interactive tasks which spend most of their time waiting for user input or other events get a comparable share of CPU time when they need it.

The data structure used for the scheduling algorithm is a red-black tree in which the nodes are scheduler specific structures, entitled sched_entity _id. These are derived from the general task_struct process descriptor, with added scheduler elements. These nodes are indexed by processor execution time in nanoseconds. A maximum execution time is also calculated for each process. This time is based upon the idea that an "ideal processor" would equally share processing power amongst all processes. Thus, the maximum execution time is the time the process has been waiting to run, divided by the total number of processes, or in other words, the maximum execution time is the time the process would have expected to run on an "ideal processor".

When the scheduler is invoked to run a new processes, the operation of the scheduler is as follows:

1. The left most node of the scheduling tree is chosen (as it will have the lowest spent execution time), and sent for execution.
2. If the process simply completes execution, it is removed from the system and scheduling tree.
3. If the process reaches its maximum execution time or is otherwise stopped (voluntarily or via interrupt) it is reinserted into the scheduling tree based on its new spent execution time.
4. The new left-most node will then be selected from the tree, repeating the iteration.

If the process spends a lot of its time sleeping, then its spent time value is low and it automatically gets the priority boost when it finally needs it. Hence such tasks do not get less processor time than the tasks that are constantly running.

An alternative to CFS is the Brain Fuck Scheduler (BFS) created by Con Kolivas. The objective of BFS, compared to other schedulers, is to provide a scheduler with a simpler algorithm, that does not require adjustment of heuristics or tuning parameters to tailor performance to a specific type of computation workload.

The Linux kernel contains different scheduler classes (or policies). The Completely Fair Scheduler used nowadays by default is SCHED_NORMAL _id scheduler class aka SCHED_OTHER. The kernel also contains two additional classes SCHED_BATCH _id and SCHED_IDLE _id, and another two real-time scheduling classes named SCHED_FIFO _id (realtime first-in-first-out) and SCHED_RR _id (realtime round-robin), with a third realtime scheduling policy known as SCHED_DEADLINE _id that implements the earliest deadline first algorithm (EDF) added later. Any realtime scheduler class takes precedence over any of the "normal" —i.e. non realtime— classes. The scheduler class is selected and configured through the man 2 sched_setscheduler ↪ do_sched_setscheduler _id system call.

⚲ API

• linux/sched.h _inc - the main scheduler API
  • schedule _id

⚙️ Internals

• sched_init _id is called from start_kernel _id
• __schedule _id is the main scheduler function.

• runqueues _id, this_rq _id
• kernel/sched _src
• kernel/sched/core.c _src
• kernel/sched/fair.c _src

📚 References

• man 7 sched
• Scheduling _doc
• Completely Fair Scheduler _doc
• Deadline Task Scheduler _doc
• sched _ltp
• sched_setparam _ltp
• sched_getscheduler _ltp
• sched_setscheduler _ltp

Synchronization

Thread synchronization is defined as a mechanism which ensures that two or more concurrent processes or threads do not simultaneously execute some particular program segment known as mutual exclusion (mutex). When one thread starts executing the critical section (serialized segment of the program) the other thread should wait until the first thread finishes. If proper synchronization techniques are not applied, it may cause a race condition where, the values of variables may be unpredictable and vary depending on the timings of context switches of the processes or threads.

Read-Copy-Update

Another synchronization mechanism that solves the readers–writers problem is the read-copy-update (RCU) algorithm. Read-copy-update implements a kind of mutual exclusion that is wait-free (non-blocking) for readers, allowing extremely low overhead. However, RCU updates can be expensive, as they must leave the old versions of the data structure in place to accommodate pre-existing readers.

RCU was added to Linux in October 2002. Since then, there are thousandths uses of the RCU API within the kernel including the networking protocol stacks and the memory-management system. The implementation of RCU in version 2.6 of the Linux kernel is among the better-known RCU implementations.

The core API is quite small:

• rcu_read_lock _id marks an RCU-protected data structure so that it won't be reclaimed for the full duration of that critical section.

• rcu_read_unlock _id is used by a reader to inform the reclaimer that the reader is exiting an RCU read-side critical section. Note that RCU read-side critical sections may be nested and/or overlapping.

• synchronize_rcu _id blocks until all pre-existing RCU read-side critical sections on all CPUs have completed. Note that synchronize_rcu will not necessarily wait for any subsequent RCU read-side critical sections to complete.

👁 For example, consider the following sequence of events:

	         CPU 0                  CPU 1                 CPU 2
	     ----------------- ------------------------- ---------------
	 1.  rcu_read_lock()
	 2.                    enters synchronize_rcu()
	 3.                                               rcu_read_lock()
	 4.  rcu_read_unlock()
	 5.                     exits synchronize_rcu()
	 6.                                              rcu_read_unlock()

RCU API communications between the reader, updater, and reclaimer

Since synchronize_rcu is the API that must figure out when readers are done, its implementation is key to RCU. For RCU to be useful in all but the most read-intensive situations, synchronize_rcu's overhead must also be quite small.

Alternatively, instead of blocking, synchronize_rcu may register a callback to be invoked after all ongoing RCU read-side critical sections have completed. This callback variant is called call_rcu _id in the Linux kernel.

• rcu_assign_pointer _id - The updater uses this function to assign a new value to an RCU-protected pointer, in order to safely communicate the change in value from the updater to the reader. This function returns the new value, and also executes any memory barrier instructions required for a given CPU architecture. Perhaps more importantly, it serves to document which pointers are protected by RCU.

• rcu_dereference _id - The reader uses this function to fetch an RCU-protected pointer, which returns a value that may then be safely dereferenced. It also executes any directives required by the compiler or the CPU, for example, a volatile cast for gcc, a memory_order_consume load for C/C++11 or the memory-barrier instruction required by the old DEC Alpha CPU. The value returned by rcu_dereference is valid only within the enclosing RCU read-side critical section. As with rcu_assign_pointer, an important function of rcu_dereference is to document which pointers are protected by RCU.

The RCU infrastructure observes the time sequence of rcu_read_lock, rcu_read_unlock, synchronize_rcu, and call_rcu invocations in order to determine when (1) synchronize_rcu invocations may return to their callers and (2) call_rcu callbacks may be invoked. Efficient implementations of the RCU infrastructure make heavy use of batching in order to amortize their overhead over many uses of the corresponding APIs.

⚲ API:

• linux/rcupdate.h _inc

📚 References

• RCU concepts _doc
• kernel/rcu _src
• RCU initialization

Interrupts

An interrupt is a signal to the processor emitted by hardware or software indicating an event that needs immediate attention. An interrupt alerts the processor to a high-priority condition requiring the interruption of the current code the processor is executing. The processor responds by suspending its current activities, saving its state, and executing a function called an interrupt handler (or an interrupt service routine, ISR) to deal with the event. This interruption is temporary, and, after the interrupt handler finishes, the processor resumes normal activities.

There are two types of interrupts: hardware interrupts and software interrupts. Hardware interrupts are used by devices to communicate that they require attention from the operating system. For example, pressing a key on the keyboard or moving the mouse triggers hardware interrupts that cause the processor to read the keystroke or mouse position. Unlike the software type, hardware interrupts are asynchronous and can occur in the middle of instruction execution, requiring additional care in programming. The act of initiating a hardware interrupt is referred to as an interrupt request - IRQ (⚙️ do_IRQ _id).

A software interrupt is caused either by an exceptional condition in the processor itself, or a special instruction in the instruction set which causes an interrupt when it is executed. The former is often called a trap (⚙️ do_trap _id) or exception and is used for errors or events occurring during program execution that are exceptional enough that they cannot be handled within the program itself. For example, if the processor's arithmetic logic unit is commanded to divide a number by zero, this impossible demand will cause a divide-by-zero exception (⚙️ X86_TRAP_DE _id), perhaps causing the computer to abandon the calculation or display an error message. Software interrupt instructions function similarly to subroutine calls and are used for a variety of purposes, such as to request services from low-level system software such as device drivers. For example, computers often use software interrupt instructions to communicate with the disk controller to request data be read or written to the disk.

Each interrupt has its own interrupt handler. The number of hardware interrupts is limited by the number of interrupt request (IRQ) lines to the processor, but there may be hundreds of different software interrupts.

⚲ API:

• There are many ways to request ISR, two of them:
• devm_request_threaded_irq _id - preferable function to allocate an interrupt line for a managed device with a threaded ISR
• request_irq _id, free_irq _id - old and common functions to add and remove a handler for an interrupt line
• linux/interrupt.h _inc

⚙️ Internals:

• irq_desc _id, irq_data _id
• kernel/irq _src

📚 References

• IRQs _doc
• Linux generic IRQ handling _doc
• Interrupts

Deferred works

CPU specific

Some functions with different implementations for CPU architectures:

• do_boot_cpu _id > start_secondary _id >cpu_init _id
• setup_arch _id, start_thread _id, get_current _id, current _id

📚 References

• x86-specific _doc
• x86_64 Support _doc
• arch _src
  • arch/x86 _src
    • https://lwn.net/Kernel/Index/#Architectures-x86
  • arch/arm _src, ARM Architecture _doc
    • https://lwn.net/Kernel/Index/#Architectures-ARM
  • arch/arm64 _src, ARM64 Architecture _doc
• architecture-specific initialization