Chapter 21: The LinuxChapter 21: The Linux System - 國立臺灣大學

Process Context The (constantly changing) state of a running program at any point in time TheTh schedulingh d li contextt t isi ththe mostt iimportantt t partt off theth process context;t t itis the information that the scheduler needs to suspend and restart theprocess The kernel maintains accounting information about the resources currentlybeing consumed by each process, and the total resources consumed by theprocess in its lifetime so far The file table is an array of pointers to kernel file structureszWhen making file I/O system calls, processes refer to files by their indexinto this tableOperating System Concepts – 8th Edition21.21Silberschatz, Galvin and Gagne 2009Process Context (Cont) Whereas the file table lists the existing open files, thefile-system context applies to requests to open new fileszThe current root and default directories to be used for new file searchesare stored here The signal-handler table defines the routine in the process’s addressspace to be called when specific signals arrive The virtualvirtual-memorymemory context of a process describes the full contents of theits private address spaceOperating System Concepts – 8th Edition21.22Silberschatz, Galvin and Gagne 2009

Processes and Threads Linux uses the same internal representation for processes and threads; athread is simply a new process that happens to share the same addressspace as its parent A distinction is only made when a new thread is created by the clonesystemtcallllzfork creates a new process with its own entirely new process contextzclone creates a new pprocess with its own identity,y, but that is allowed toshare the data structures of its parent Using clone gives an application fine-grained control over exactly what isshared between two threadsOperating System Concepts – 8th Edition21.23Silberschatz, Galvin and Gagne 2009Scheduling The job of allocating CPU time to different tasks within an operating system While scheduling is normally thought of as the running and interrupting ofprocesses, in Linux, scheduling also includes the running of the variouskkernell ttasksk Running kernel tasks encompasses both tasks that are requested by arunning process and tasks that execute internally on behalf of a devicedriver As of 2.5,, new schedulingg ime rangeznice valueOperating System Concepts – 8th Edition21.24Silberschatz, Galvin and Gagne 2009

Relationship Between Priorities and Time-sliceLengthOperating System Concepts – 8th Edition21.25Silberschatz, Galvin and Gagne 2009List of Tasks Indexed by PriorityOperating System Concepts – 8th Edition21.26Silberschatz, Galvin and Gagne 2009

Kernel Synchronization A request for kernel-mode execution can occur in two ways:zA runningi program may requestt an operatingti systemtservice,ieitherithexplicitly via a system call, or implicitly, for example, when a page faultoccurszA device driver may deliver a hardware interrupt that causes the CPU tostart executing a kernel-defined handler for that interrupt Kernel synchronization requires a framework that will allow the kernel’skernel scritical sections to run without interruption by another critical sectionOperating System Concepts – 8th Edition21.27Silberschatz, Galvin and Gagne 2009Kernel Synchronization (Cont) Linux uses two techniques to protect critical sections:1 N1.Normall kkernell coded iis nonpreemptibletibl ((untiltil 22.4)4)– when a time interrupt is received while a process isexecuting a kernel system service routine, the kernel’sneed rescheddh d flagfl isi sett so thatth t theth schedulerh d l willill runonce the system call has completed and control isabout to be returned to user mode2. The second technique applies to critical sections that occur in aninterrupt service routines– Byy usingg the pprocessor’s interruptp control hardware to disableinterrupts during a critical section, the kernel guarantees that it canproceed without the risk of concurrent access of shared data structuresOperating System Concepts – 8th Edition21.28Silberschatz, Galvin and Gagne 2009

Kernel Synchronization (Cont) To avoid performance penalties, Linux’s kernel uses a synchronizationarchitecture that allows long critical sections to run without having interruptsdisabled for the critical section’s entire duration Interrupt service routines are separated into a top half and a bottom half.zThe top half is a normal interrupt service routine, and runs withrecursive interrupts disabledzThe bottom half is run, with all interrupts enabled, by a miniaturescheduler that ensures that bottom halves never interrupt themselveszThis architecture is completed by a mechanism for disabling selectedbottom halves while executing normalnormal, foreground kernel codeOperating System Concepts – 8th Edition21.29Silberschatz, Galvin and Gagne 2009Interrupt Protection Levels Each level may be interrupted by code running at a higherlevel, but will never be interrupted by code running at thesame or a lower level User processes can always be preempted by another processwhen a time-sharing scheduling interrupt occursOperating System Concepts – 8th Edition21.30Silberschatz, Galvin and Gagne 2009

Process Scheduling Linux uses two process-scheduling algorithms:zA time-sharing algorithm for fair preemptive scheduling betweenmultiple processeszA real-timeeaeaalgorithmgoforo tasksas s wheree e absoabsoluteuepprioritieso es aaree moreoeimportant than fairness A process’s scheduling class defines which algorithm to apply ForF time-sharingtih i processes, LinuxLiuses a prioritized,i iti d creditdit bbaseddalgorithmzThe crediting rulecredits : credits priority2factors in both the process’s history and its priorityzThis crediting system automatically prioritizes interactive or I/Oprocessesbound pOperating System Concepts – 8th Edition21.31Silberschatz, Galvin and Gagne 2009Process Scheduling (Cont) Linux implements the FIFO and round-robin real-time scheduling classes; inboth cases,cases each process has a priority in addition to its scheduling classzThe scheduler runs the process with the highest priority; for equalpriority processes, it runs the process waiting the longestzFIFO processes continue to run until they either exit or blockzA round-robin process will be preempted after a while and moved to theend of the scheduling queue, so that round-robinground robing processes of equalpriority automatically time-share between themselvesOperating System Concepts – 8th Edition21.32Silberschatz, Galvin and Gagne 2009

Symmetric Multiprocessing Linux 2.0 was the first Linux kernel to support SMP hardware; separateprocesses or threads can execute in parallel on separate processors To preserve the kernel’s nonpreemptible synchronization requirements,SMP imposes the restriction, via a single kernel spinlock, that only oneprocessor at a time may execute kernel-mode codeOperating System Concepts – 8th Edition21.33Silberschatz, Galvin and Gagne 2009Memory Management Linux’s physical memory-management system deals with allocating andfreeing pagespages, groups of pagespages, and small blocks of memory It has additional mechanisms for handling virtual memory, memory mappedi t thintothe addressddspace off runningi processes Splits memory into 3 different zones due to hardware characteristicsOperating System Concepts – 8th Edition21.34Silberschatz, Galvin and Gagne 2009

Relationship of Zones and Physical Addresseson 80x86Operating System Concepts – 8th Edition21.35Silberschatz, Galvin and Gagne 2009Splitting of Memory in a Buddy HeapOperating System Concepts – 8th Edition21.36Silberschatz, Galvin and Gagne 2009

Managing Physical Memory The page allocator allocates and frees all physical pages; it canallocate ranges of physically-contiguous pages on request The allocator uses a buddy-heap algorithm to keep track of availablephysical pagesz EachE h allocatablellt bl memory regioni iis pairedi d withith an adjacentdjtpartnerzWhenever two allocated partner regions are both freed up theyare combined to form a larger regionzIf a small memory request cannot be satisfied by allocating anexisting small free region, then a larger free region will besubdivided into two partners to satisfy the request Memory allocations in the Linux kernel occur either statically (driversreserve a contiguous area of memory during system boot time) ordynamically (via the page allocator) Also uses slab allocator for kernel memoryOperating System Concepts – 8th Edition21.37Silberschatz, Galvin and Gagne 200921.07Operating System Concepts – 8th Edition21.38Silberschatz, Galvin and Gagne 2009

Virtual Memory The VM system maintains the address space visible to each process: Itcreates pages of virtual memory on demand,demand and manages the loading ofthose pages from disk or their swapping back out to disk as required The VM manager maintains two separate views of a process’s addressspace:zA logical view describing instructions concerning the layout of theaddress space zThe address space consists of a set of nonoverlapping regions, eachrepresenting a continuous, page-aligned subset of the addressspacepA physical view of each address space which is stored in the hardwarepage tables for the processOperating System Concepts – 8th Edition21.39Silberschatz, Galvin and Gagne 2009Virtual Memory (Cont) Virtual memory regions are characterized by:zThe backingThb ki store,twhichhi h ddescribesib ffrom wherehththe pages ffor a regionicome; regions are usually backed by a file or by nothing (demand-zeromemory)zThe region’s reaction to writes (page sharing or copy-on-write) The kernel creates a new virtual address space1. When a process runs a new program with the exec system call2. Upon creation of a new process by the fork system callOperating System Concepts – 8th Edition21.40Silberschatz, Galvin and Gagne 2009

Virtual Memory (Cont) On executing a new program, the process is given a new, completely emptyvirtual-address space; the program-loading routines populate the addressspace with virtual-memory regions Creating a new process with fork involves creating a complete copy of theexistingi ti process’s’ virtuali t l addressddspacezThe kernel copies the parent process’s VMA descriptors, then creates anew set of page tables for the childzThe parent’s page tables are copied directly into the child’s, with thereference count of each page covered being incrementedzAfter the fork,fork the parent and child share the same physical pages ofmemory in their address spacesOperating System Concepts – 8th Edition21.41Silberschatz, Galvin and Gagne 2009Virtual Memory (Cont) The VM paging system relocates pages of memory from physical memoryout to disk when the memory is needed for something else The VM paging system can be divided into two sections:zThe pageout-policy algorithm decides which pages to write out to disk,and whenzThe paging mechanism actually carries out the transfer, and pages databack into physical memory as neededOperating System Concepts – 8th Edition21.42Silberschatz, Galvin and Gagne 2009

Virtual Memory (Cont) The Linux kernel reserves a constant, architecture-dependent region of thevirtual address space of every process for its own internal use This kernel virtual-memory area contains two regions:zA static area that contains page table references to every availablephysical page of memory in the system, so that there is a simpletranslation from physical to virtual addresses when running kernel codezThe reminder of the reserved section is not reserved for any specificpurpose; its page-table entries can be modified to point to any otherareas of memoryyOperating System Concepts – 8th Edition21.43Silberschatz, Galvin and Gagne 2009Executing and Loading User Programs Linux maintains a table of functions for loading programs; it gives eachfunction the opportunity to try loading the given file when an exec systemcall is made The registration of multiple loader routines allows Linux to support both theELF andd a.outt binarybifformatst Initially, binary-file pages are mapped into virtual memoryzOnly when a program tries to access a given page will a page faultresult in that page being loaded into physical memory An ELF-format binary file consists of a header followed by several page-aligned sectionszThe ELF loader works by reading the header and mapping the sectionsof the file into separate regions of virtual memoryOperating System Concepts – 8th Edition21.44Silberschatz, Galvin and Gagne 2009

Memory Layout for ELF ProgramsOperating System Concepts – 8th Edition21.45Silberschatz, Galvin and Gagne 2009Static and Dynamic Linking A program whose necessary library functions are embedded directly in theprogram’sprograms executable binary file is statically linked to its libraries The main disadvantage of static linkage is that every program generatedmustt containt i copiesi off exactlytl theth same common systemtlibrarylibffunctionsti Dynamic linking is more efficient in terms of both physical memory and disk-space usage because it loads the system libraries into memory only onceOperating System Concepts – 8th Edition21.46Silberschatz, Galvin and Gagne 2009

File Systems To the user, Linux’s file system appears as a hierarchical directory treeobeying UNIX semantics Internally, the kernel hides implementation details and manages the multipledifferent file systems via an abstraction layer, that is, the virtual file system(VFS) The Linux VFS is designed around object-oriented principles and iscomposed of two components:zzA set of definitions that define what a file object is allowed to look like The inode-object and the file-object structures represent individualfiles the file system object represents an entire file systemA layery of software to manipulate those objectsjOperating System Concepts – 8th Edition21.47Silberschatz, Galvin and Gagne 2009The Linux Ext2fs File System Ext2fs uses a mechanism similar to that of BSD Fast File System (ffs)for locating data blocks belonging to a specific file The main differences between ext2fs and ffs concern their diskallocation policiesz InI ffs,ff theth diskdi k isi allocatedllt d tto filfiles iin blblocksk off 8Kb8Kb, withith blblockskbeing subdivided into fragments of 1Kb to store small files orpartially filled blocks at the end of a filez Ext2fs does not use fragments; it performs its allocations insmaller unitsThe default block size on ext2fs is 1Kb, although 2Kb and 4Kbblocks are also supportedExt2fs uses allocation policies designed to place logicallyadjacent blocks of a file into physically adjacent blocks on disk, sothat it can submit an I/O request for several disk blocks as asingle operation zOperating System Concepts – 8th Edition21.48Silberschatz, Galvin and Gagne 2009

Ext2fs Block-Allocation PoliciesOperating System Concepts – 8th Edition21.49Silberschatz, Galvin and Gagne 2009The Linux Proc File System The proc file system does not store data, rather, its contents are computedon demand according to user file I/O requests proc must implement a directory structure, and the file contents within; itmust then define a unique and persistent inode number for each directoryandd filfiles it containst izIt uses this inode number to identify just what operation is requiredwhen a user tries to read from a particular file inode or perform a lookupin a particular directory inodezWhen data is read from one of these files, proc collects the appropriateinformation,, formats it into text form and placespit into the requestingqgprocess’s read bufferOperating System Concepts – 8th Edition21.50Silberschatz, Galvin and Gagne 2009

Input and Output The Linux device-oriented file system accesses disk storage through twocaches:zData is cached in the page cache, which is unified with the virtualmemory systemzMetadata is cached in the buffer cache, a separate cache indexed bythe physical disk block Linux splits all devices into three classes:zblock devices allow random access to completely independent, fixedsize blocks of datazcharacter devices include most other devices; they don’t’ need tosupport the functionality of regular filesznetwork devices are interfaced via the kernel’s networkingg subsystemyOperating System Concepts – 8th Edition21.51Silberschatz, Galvin and Gagne 2009Device-Driver Block StructureOperating System Concepts – 8th Edition21.52Silberschatz, Galvin and Gagne 2009

Block Devices Provide the main interface to all disk devices in a system The block buffer cache serves two main purposes:zit acts as a pool of buffers for active I/Ozit serves as a cache for completed I/O The request manager manages the reading and writing of buffer contents toand from a block device driverOperating System Concepts – 8th Edition21.53Silberschatz, Galvin and Gagne 2009Character Devices A device driver which does not offer random access to fixed blocks of data A characterht deviced i ddriverimustt registeri t a sett off functionsftiwhichhi h iimplementltthe driver’s various file I/O operations The kernel performs almost no preprocessing of a file read or write requestto a character device, but simply passes on the request to the device The main exception to this rule is the special subset of character devicedrivers which implement terminal devices, for which the kernel maintains astandard interfaceOperating System Concepts – 8th Edition21.54Silberschatz, Galvin and Gagne 2009

Interprocess Communication Like UNIX, Linux informs processes that an event has occurred via signals ThereThiis a lilimitedit d numberb off signals,il andd ththey cannott carry iinformation:ftiOnly the fact that a signal occurred is available to a process The Linux kernel does not use signals to communicate with processes withare running in kernel mode, rather, communication within the kernel isaccomplished via scheduling states and wait.queue structuresOperating System Concepts – 8th Edition21.55Silberschatz, Galvin and Gagne 2009Passing Data Between Processes The pipe mechanism allows a child process to inherit a communicationchannel to its parent,parent data written to one end of the pipe can be read a theother SharedSh d memory offersffan extremelytl fastf t way off communicating;i tiany datad twritten by one process to a shared memory region can be read immediatelyby any other process that has mapped that region into its address space To obtain synchronization, however, shared memory must be used inconjunction with another Interprocess-communication mechanismOperating System Concepts – 8th Edition21.56Silberschatz, Galvin and Gagne

Linux networking-administration tools were derived from 4.3BSD code; recent BSD derivatives such as Free BSD have borrowed code from Linux in return . Components of a Linux System (Cont) Like most UNIX implementations, Linux is composed of three main bodies of code; the most important distinction between the kernelbodies of code; the most .