Architecture of the Linux kernel

1 Architecture of the Linux kernelGerion EntrupFelix HerrmannSophie MatterElias EntrupMatthias JakobJan EberhardtMathias CasseltMarch 21, 2018 Contents1 Overview of Linux components.. License..92 Process Processes.. Process creation - Forking a process.. Threads..163 Scheduling in Scheduling-Classes.. Process Categories.. (1)-Scheduler.. Priorities and Timeslices.. Completely Fair Scheduler.. Implementation details.. kernel Preemption..214 Interrupt processing.. Interrupt entry.. Event handler.

2 Example: Generic Top Halve.. Example: Handler.. /proc/interrupts.. Conclusion..255 Bottom Selecting the correct Bottom Halve mechanism.. Preemption and Priorities.. Softirq.. Tasklet.. Work queue.. Conclusion..306 kernel Synchronization Why Is Synchronization Needed?.. Standard Synchronization Methods.. Special Synchronization Methods.. Interaction with Interrupts, Bottom Halves and kernel Preemption.. Which one to choose.. Problems.. Conclusion..377 System Thesyncsystem call.. Userland part.

3 kernel part.. Syscalls with arguments.. Other input paths.. Conclusion..448 Hz.. Jiffies.. Calculating with Jiffies.. The timer interrupt handling.. Timer.. The timer wheel.. Waiting.. Conclusion..509 Memory Description of Physical Memory.. UMA and NUMA Architectures.. Nodes.. Zones.. Pages.. Managing Memory.. Allocating and Freeing Pages.. High Memory Mappings.. Per-CPU Allocations.. Allocation Interfaces.. The Buddy System.. The Slab Allocator.. Slab Caches.. Slob and Slub Allocator.

4 Allocating a Slab.. kmalloc, kfree.. Allocating Non-Contiguous Memory.. Choosing an Allocation Method.. Conclusion..6010 Filesystem.. filesystemtype.. superblock.. vfsmount.. Resolving a file path.. dentry.. inode.. file.. Process-specific information.. Summary..6411 Virtual Adress mmstruct.. Virtual Memory Areas.. Page tables.. Recent developments.. Summary..684 Contents12 Block I/O (BIO) Devices and Units.. Data structures.. I/O Scheduler.. Linus Elevator.. Deadline Scheduler.. Complete Fair Queuing Scheduler.

5 Noop Scheduler.. Budget Fair Queuing Scheduler.. Kyber Scheduler..7213 Page Cache and Page Basic concepts and terms.. The Linux Page Cache.. Dirty Page Writeback..7414 Data structures.. Kobjects.. Ksets.. Subsystems.. Checkpoint.. Mapping Kobjects.. Directories.. Files.. Interaction.. Summary..8215 Source code.. kernel Exported Interfaces.. Format.. Providing parameters.. Example.. In-tree compilation.. External compilation.. Loading modules.. Dependencies.. Loading from inside the kernel .. Summary.

6 89 Bibliography9151 IntroductionOn 26. August 1991 Linus Torvalds wrote in the following message:Hello everybody out there using minix - I m doing a (free) operating system (just a hobby, won tbe big and professional like gnu) for 386(486) AT clones. This has been brewing since april, andis starting to get ready. I d like any feedback on things people like/dislike in minix, as my OSresembles it somewhat (same physical layout of the file-system (due to practical reasons) amongother things).I ve currently ported bash( ) and gcc( ), and things seem to work.

7 This implies that I llget something practical within a few months, and I d like to know what features most peoplewould want. Any suggestions are welcome, but I won t promise I ll implement them :-)Linus Yes - it s free of any minix code, and it has a multi-threaded fs. It is NOT protable (uses386 task switching etc), and it probably never will support anything other than AT-harddisks,as that s all I have :-(.This was the first public announcement of the Linux operating system, that is nowadays one of the biggestoperating systems in the most exiting part of Linux is that it is Free Software.

8 It is licensed under the GNU GPL and developedin such a way that everybody can study the internals of Linux , dive into the code, improve it and contributeit back. This has formed a huge community around Linux and leads to a very unique software developmentmodel conditioned by the huge code base and amount of different book focuses on the internals of Linux . It will present the functionality of the different subsystemsand also give a quick overview about the development Overview of Linux componentsLinux is divided in several subsystems that handle one operating system specific task.

9 Presentsan overview about the most common call interfaceTo connect with the userland, Linux uses the concept of system calls. They aredefined as C-functions, that internally translate to specific assembler calls, to bring the processor in thesupervisor mode. The system call interface is actually not a subsystem, but part of the whole management (PM)A core concept of operating systems is the handling of processes. Thissubsystem defines processes and threads and how they interact with each other. The CPU is a limitedresource, so a scheduler is needed to distribute the technique of interrupts, Linux can react as soon as possible to events.

10 This comes with the costof context switches and therefore needs some synchronization IntroductionUser ModeKernel ModeSystem call interface sysfsMemory management Virtual memory In- kernel memory (Slab) SwapProcess management Processes/Threads (CPU-)scheduler Interrupts/Synchronization TimerVirtual file system i-Nodes/dentrys/files ext/btrfs/..Device driversBlock I/O IO-scheduler Page-cacheNetwork Process address spaceFigure : Overview of Linux subsystemsMemory management (MM)Processes and the kernel itself need memory to work.