Linux: History, Kernel, and File System

Unit V: Overview

• Unit V will cover the History and features of Linux
• Unit V will cover the Linux architecture
• Unit V will cover the Linux file system
• Unit V will cover the Hardware requirements
• Unit V will cover standard Linux directories
• Unit V will cover the Linux Kernel
• Unit V will cover working with Linux and KDE and Gnome graphical interfaces
• Unit V will cover the various types of shells available in Linux
• Unit V will cover the Vi editor
• Unit V will cover Linux commands
• Unit V will cover File Security in Linux

History of Linux

• A modern, free operating system based on UNIX standards
• First developed in 1991 by Linus Torvalds
• The design goal was UNIX compatibility
• History involves collaboration from users worldwide over the Internet
• Designed to run efficiently on PC hardware and other platforms
• The core Linux operating system kernel is original
• Can run much existing free UNIX software

The Linux Kernel

• Version 0.01 (May 1991) had no networking
• Version 0.01 ran only on 80386-compatible Intel processors / PC hardware
• Version 0.01 had limited device-drive support and supported only the Minix file system.
• Linux 1.0 (March 1994) included UNIX's standard TCP/IP networking protocols
• Linux 1.0 (March 1994) included Socket interface for networking programming
• Linux 1.0 (March 1994) included device-driver support for running IP over an Ethernet
• Linux 1.0 (March 1994) included an enhanced file system
• Linux 1.0 (March 1994) included better support for a range of controllers for high-performance disk access
• Linux 1.0 (March 1994) included extra hardware support
• Version 1.2 (March 1995) was the final PC-only Linux kernel
• Version 2.0 was released in June 1996
• Version 2.0 added support for multiple architectures, including a fully 64-bit native Alpha port
• Version 2.0 added support for multiprocessor architectures
• In version 2.0, other new features included Improved memory-management code/TCP/IP performance
• Version 2.0 supported internal kernel threads, for handling dependencies between loadable modules, and for automatic loading of modules on demand, plus a standardized configuration interface
• Version 2.0 was available for Motorola 68000-series processors, Sun Sparc systems, and for PC and PowerMac systems.

The Linux System

• Linux uses tools developed as part of Berkeley's BSD operating system, MIT's X Window System, and the Free Software Foundation's GNU project.
• The min system libraries were started by the GNU project
• Improvements have been provided by the Linux community.
• Linux networking-administration tools were derived
• The Linux system is maintained by a loose network of developers collaborating over the Internet
• Maintained with a small number of public ftp sites acting as standard repositories.

Linux Distributions

• Distributions- standard, precompiled sets of packages, include the basic Linux system, system installation and management utilities, and ready-to-install packages of common UNIX tools.
• First distros managed packages by unpacking all files into appropriate places
• Modern distributions include advanced package management
• Early distributions included SLS and Slackware
• Red Hat and Debian are popular distributions from commercial and noncommercial sources, respectively.
• The RPM Package file format permits compatibility among the various Linux distributions.

Linux Licensing

• Distributed under the GNU General Public License (GPL)
• Terms are set out by the Free Software Foundation.
• Those using or creating their own derivative of Linux, may not make the derived product proprietary
• Software released under the GPL may not be redistributed as a binary-only product.

Design Principles

• Linux is a multiuser, multitasking system with a full set of UNIX-compatible tools.
• The file system adheres to traditional UNIX semantics and it fully implements the standard UNIX networking model.
• Main design goals include speed, efficiency, and standardization.

Architecture of a Linux System

• Composed of three main bodies of code
• The most important distinction exists between the kernel and all other components
• The kernel is responsible for maintaining the important abstractions of the operating system
• Kernel code executes in kernel mode with full access to all the physical resources of the computer.
• All kernel code and data structures are kept in the same single address space.
• The system libraries define a standard set of functions through which applications interact with the kernel
• System libraries implement much of OS functionality without the privileges of kernel code.
• The system utilities perform individual specialized management tasks.

Kernel Modules

• Sections of kernel code can be compiled, loaded, and unloaded independent of the rest of the kernel.
• A kernel module may implement a device driver, file system, or networking protocol.
• Allows third parties to write / distribute device drivers or file systems, that could not be distributed under the GPL.
• Kernel modules allow a Linux system to be set up with a standard, minimal kernel, without extra device drivers built in.
• Three components to Linux module support include module management / driver registration / conflict resolution

Module Management

• Supports loading modules into memory and letting them talk to the rest of the kernel.
• Module loading is split into two separate sections of code:
  • Managing sections of module code in kernel memory
  • Handling symbols that modules are allowed to reference
• The module requestor manages loading requested, but currently unloaded, modules.
• Periodically, the module requestor queries the kernel to see if a dynamically loaded module is still in use
• Then the module requestor will unload the module when it is no longer actively needed.

Driver Registration

• Allows modules to tell the rest of the kernel that a new driver has become available.
• The kernel maintains dynamic tables of all known drivers.
• It also provides a set of routines to allow drivers to be added to or removed from these tables at any time.
• Registration tables include Device drivers / File systems / Network protocols / Binary format

Conflict Resolution

• Mechanism: allows different device drivers to reserve hardware resources and to protect them from accidental use by another driver
• Aims to prevent modules from clashing over access to hardware resources.
• Prevents autoprobes from interfering with existing device drivers.
• Resolves conflicts with multiple drivers trying to access the same hardware.

Process Management

• Separates the creation of processes and the running of a new program into two distinct operations.
• The fork system call creates a new process.
• A new program is run after a call to execve.
• A process encompasses the info that OS must maintain to track the context of a single execution of a single program.
• Process properties fall into three groups: the process's identity, environment, and context.

Process Identity

• Process ID (PID): The unique identifier for the process
  • Used to specify processes to the OS when an application makes a system call to signal, modify, or wait for another process.
• Credentials: Each process has a user ID and one or more group IDs
  • Determines the process's rights to access system resources and files
• Personality. Not traditionally found on UNIX systems
  • Under Linux each process has a personality identifier that can slightly modify the semantics of certain system calls
  • Used primarily by emulation libraries to request that system calls be compatible with specific flavors of UNIX.

Process Environment

• The process's environment is inherited from its parent, is composed of two null-terminated vectors
• The argument vector lists the command-line arguments used to invoke the running program.
  • Conventionally starts with the name of the program itself.
• The environment vector is a list of "NAME=VALUE" pairs that associates named environment variables with arbitrary textual values.
• Passing environment variables among processes and inheriting variables by a process's children are flexible means of passing information to components of the user-mode system software.
• Customization of the operating system can be set on a per-process basis, rather than being configured for the system as a whole through the environment-variable mechanism.

Process Context

• The (constantly changing) state of a running program at any point in time.
• The scheduling context is the most important part of the process context.
  • Info that the scheduler needs to suspend and restart the process.
• Kernel maintains accounting information about the resources consumed by each process / total resources consumed by the process
• The file table is an array of pointers to kernel file structures.
  • When making file I/O system calls, processes refer to files by their index into this table.
• The file-system context applies to requests to open new files
  • The current root /default directories to be used for new file searches are stored here.
• The signal-handler table defines the routine in the process's address space that is called when specific signals arrive.
• The virtual-memory context of a process describes the full contents of its private address space.

Processes and Threads

• Linux uses the same internal representation for processes and threads
• a thread is simply a new process that happens to share the same address space as its parent.
• Distinction is only made when a new thread is created by the clone system call.
  • fork creates a new process with its own entirely new process context
  • clone creates a new process with its own identity, but that is allowed to share the data structures of its parent
• clone gives an application control over what is shared between two threads.

Scheduling

• Allocates CPU time to different tasks within an operating system.
• Includes running and interrupting processes; also includes running the kernel tasks.
• Running kernel tasks includes requested tasks by a running process / tasks that execute internally on behalf of a device driver.

Kernel Synchronization

• A request for kernel-mode execution can occur in two ways:
  • A running program can request an OS service explicitly via a system call / implicitly if a page fault occurs.
  • A device driver may deliver a hardware interrupt that causes the CPU to start executing a kernel-defined handler for that interrupt.
• Kernel synchronization ensures that the kernel's critical sections run without interruption by another critical section.

Kernel Synchronization Techniques

• Normal kernel code is nonpreemptible
  • If a time interrupt is received while a process is executing a kernel system service routine, the kernel's need_resched flag is set so that the scheduler will run once the system call has completed and control is about to be returned to user mode.
• The second applies to critical sections that occur in interrupt routines.
  • Disabling interrupts guarantees the kernel can proceed without the risk of concurrent access of shared data structures.
• Long critical sections can run without disabled interrupts for the section's entire duration using Linux's synchronization architecture
• Interrupt service routines are separated into a top half and a bottom half.
  • The top half is a normal interrupt service routine, runs with recursive interrupts disabled.
  • The bottom half runs with enabled interrupts by a scheduler that ensures bottom halves never interrupt themselves
• This architecture is completed by a mechanism for disabling selected bottom halves while executing normal, foreground kernel code.

Interrupt Protection Levels

• Listed from highest to lowest priority, these are: top-half interrupt handlers, bottom-half interrupt handlers, kernel-system service routines (not preemptible), and user-mode programs (preemptible).
• Each level may be interrupted by code running at a higher level
• Code will never be interrupted by code running at the same or a lower level.
• User processes can be preempted by another process during a time-sharing scheduling interrupt.

Process Scheduling

• Linux uses two process-scheduling algorithms:
  • A time-sharing algorithm for fair preemptive scheduling between multiple processes
  • A real-time algorithm for tasks where absolute priorities are more important than fairness
• A process's scheduling class defines which algorithm to apply.
• For time-sharing processes, Linux uses a prioritized, credit based algorithm
  • The crediting rule credits := (credits / 2) + priority, factors in both the process's history and its priority.
• This crediting system prioritizes interactive or I/O-bound processes.
• Linux implements the FIFO / round-robin real-time scheduling classes, where each process has a priority plus its scheduling class
• The scheduler runs the process with the highest priority / for equal-priority processes, it runs the longest-waiting one
• FIFO processes continue to run until they exit/block
• Round-robin processes will be preempted after a while and moved to the end of the scheduling queue
  • Round-robing processes of equal priority automatically time-share between themselves.

Symmetric Multiprocessing

• Linux 2.0 was the first Linux kernel to support SMP hardware
  • Separate processes/threads can execute in parallel on separate processors.
• Kernel's nonpreemptible synchronization requirements
  • SMP restricts, that only one processor at a time may execute kernel-mode code

Memory Management

• Allocates/Frees pages, groups of pages, and small blocks of memory.
• Has additional mechanisms for handling virtual memory (memory mapped into the address space of running processes.)

Managing Physical Memory

• The page allocator allocates and frees all physical pages
  • Can allocate ranges of physically-contiguous pages on request.
• The allocator uses a buddy-heap algorithm to keep track of available physical pages.
  • Each allocatable memory region is paired with an adjacent partner.
  • When two allocated partner regions are freed up, they are combined to form a larger region.
• A small memory request cannot be satisfied by allocating an existing small free region
  • a larger free region will be subdivided into two partners to satisfy the request.
• Memory allocations in the Linux kernel occur either statically -drivers reserve a contiguous area of memory during system boot time
• Memory allocations occur dynamically: via the page allocator.

Virtual Memory

• The VM system: maintains the address space visible to each process
  • Creates pages of virtual memory on demand + manages the loading of those pages from disk, swapping them back out if needed
• The VM manager maintains two separate views of a process's address space:
  • A logical view describing instructions concerning the layout of the address space.
    • Nonoverlapping regions, each representing a continuous, page-aligned subset of the address space.
  • A physical view of each address space
    • Stored in the hardware page tables for the process

Virtual Memory Characterization

• Virtual memory regions are characterized by: -The backing store: what pages for a region uses -backed by a file or by nothing (demand-zero memory) -The region's reaction to writes (page sharing or copy-on-write) The kernel creates a new virtual address space when -A process runs a new program with the exec system call or upon the creation of a new process by the fork system call
  • On executing a new program, the process is given a new, empty virtual-address space
  • Program-loading routines populate the address space with virtual-memory regions.
• Creating a new process with fork involves creating a copy of the existing process's virtual address space.
  • The kernel copies the parent process's VMA descriptors creates page tables for the child.
• The parent's page tables are copies directly into the child's, with the reference count of each page covered being incremented
• the parent and child share memory in their address spaces after the fork
• The VM paging system relocates pages of memory from physical memory to disk when the memory is needed
• The VM paging system is divided into two sections:
  • The pageout-policy algorithm: decides which pages to write out to disk, and when.
  • The paging mechanism: carries out the transfer/pages data back into physical memory
• The Linux kernel reserves a constant, architecture-dependent region of the virtual address space of every process for its own internal use.
• The kernel virtual-memory area contains two regions: A static area / Unreserved section

Executing & Loading UIsr Programs

• Linux maintains a table of functions for loading programs.
  • Each function has the opportunity to try loading the given file when an exec system call is made.
• Binary-file pages are mapped into virtual memory at first only
  • Only when a program tries to access a given page will a page fault result in that page being loaded into physical memory.

Memory Layout for Programs

• Consists of: kernel virtual memory / stack / memory-mapped region / run-time data / uninitialized data / initialized data / program text

Static and Dynamic Linking

• A program with library functions, embedded directly in program's executable binary file = statically linked to libraries.
• The main disadvantage of it is, that every program generated contains copied system library functions.
• Dynamic linking loads the system libraries into memory once and is more efficient.

File Systems

• To the user, Linux's file system appears as a hierarchical directory tree obeying UNIX semantics.
• Internally, the kernel manages the different file systems using the virtual file system (VFS).
• Designed around object-oriented principles with two main components
  • A set of definitions that define what a file object is allowed to look like consisting of inode and file object structures to represent individual files . - A layer of software that can be used to manipulate those objects

The Linux Ext2fs File System

• Uses a mechanism similar to that of BSD Fast File System (ffs)
  • For locating data blocks belonging to a specific file.
• Key differences are the disk allocation policies:
• In ffs, the disk is allocated to files in blocks of 8Kb, with blocks being subdivided into fragments of 1Kb to store small files or partially filled blocks at the end of a file.
• Ext2fs does not use fragments, rather, it performs its allocations in smaller units of 1Kb (defaults)
  • 2Kb/4Kb blocks are also supported.
• Logically adjacent blocks of a file become physically adjacent blocks on disk
  • I/O request submitted for these contiguous disk blocks.

The Linux Proc File System

• Not store data, rather, its contents are computed on demand according to user file I/O requests.
• proc must implement a directory structure / the file contents within
  • Must then define a unique and persistent inode number for each directory and files it contains.
• The inodes are used to what operations are required when a user tries to read a particular file inode or performs a lookup in a directory.
• During data reads, proc collects the appropriate information, formats it and places it in the process’s read buffer.

Input and Output

• Accesses disk storage through two caches:
  • Data is cached in the page cache, which is unified with the virtual memory system Metadata cached in the buffer cache (a separate cache indexed by the physical disk block).
• All devices split into three classes:
  • block devices (random access to independent + fixed sized blocks of data) - character devices (most other devices + don't need to support functionality regular files provide)
  • network devices (interfaced via the kernel's networking subsystem)

Block Devices

• Provide central interface to all disk devices in a system.
• The block buffer cache serves two main purposes:
  • Buffers for active I/O
  • A cache for completed I/O
• The request manager manages the reading/writing of buffer contents to and from a block device driver.

Character Devices

• A device driver that does not offer random access to fixed blocks of data.
• A character device driver must register a set of functions implementing the driver's file I/O operations.
• The kernel performs almost no preprocessing of a file read/write request to a character device
  • The request is passed to the device entirely. -Terminals are a special case, of character device drivers
    • The kernel maintains these specifically, as a standard interface.

Interprocess Communication

• Linux informs processes that an event has occurred via signals.
• Signals are limited and cannot carry information
  • Only the fact that a signal occurred is available to a process.
• The Linux kernel relies on scheduling states and wait.queue structures for inter-kernel communication

Passing Data Between Processes

• The pipe mechanism allows a child process to inherit a communication channel to its parent; data written to one end of the pipe can be read at the other
• Shared memory offers communicate in a faster way
  • Data written process to a shared memory region can be read by a process which has mapped the memory to its address space.
• Shared memory must be used in conjunction with another Interprocess-communication mechanism for synchronization.

Shared Memory Object

• Serves as the backing store for memory regions that are being shared.
• The shared-memory object works in the same way as a file, such that it can act as a backing store for a memory-mapped region.
• Shared-memory mappings are designed to use direct page faults, which allows mapping in pages from a persistent shared-memory object.
• Shared-memory objects remember their contents if there are actively mapping processes/ virtual memory.

Network Structure

• Key area of functionality
• it supports the protocols (Internet ones) for UNIX to UNIX communications and also protocols native to non UNIX operating systems. e.g. Appletalk IPX -Linux kernel network structures have 3 layers the socket interface, protocol drivers and device drivers.
• the Internet Structures suite is most important
  • Allows for routing between different hosts
  • The TCP, UDP, and ICMP's are built with routing protocol.

Security

• A working authentication system called Pluggable Authentication Modules (PAM) is available
• The PAM has shared library that is able to be used by any type of components in a system in case authentication is compulsory.
• Access control: is performed by the unique numeric identifiers uid / gid. Protection Masks- allows specifying what access modes in processes with world, group, or owner access.

Security continued

• Linux enhanced UNIX's set uid (standard) It is an implementation of POSIX that allows a process repeated dropping and reaquire of the user ID.
• Linux also grants a few rights for a uid that are effectively controlled.
• There is a mechanism for a selective approach for access over many files to a server without any privilege

Wildcard Characters

• " * " - Allows for a list of more than 0 characters
• “ ? ”- Allows for a list of a single character

Linux Commands

• Creating a file “College” by inputting the name of the college and putting this file in “dir2” and “dir2” in ‘dir1’ (in the root directory) mkdir dir1 -> cd dir1 -> mkdir dir2 -> cd dir2 -> cat > college
• List files starting with “de”
  • ls de*
• Create all the following files in “dir2” which includes the following parameters:
  • abc
  • abcl
  • def
  • def1
  • xyz
  • pqr Copy the “abc1” and display them in both files “ab2” cp abc1 abc2 - > more abc1 -> more abc2 -> rm -r dirl