Operating Systems Concepts

Overview

• An operating system acts as an intermediary between the user of a computer and the computer hardware. The purpose of an operating system is to provide an environment in which a user can execute programs in a convenient and efficient manner.
• An operating system is software that manages the computer hardware, The hardware must provide appropriate mechanisms to ensure the correct operation of the computer system and to prevent user programs from interfering with the proper operation of the system.

Introduction

• A computer system can roughly be divided into four components: the hardware, the operating system, the application programs, and the users.
• The hardware - the central processing unit (CPU), the memory, and the input/output (I/O) devices - provides the basic computing resources for the system. The application programs - such as word processors, spreadsheets, compilers, and web browsers - define the ways in which these resources are used to solve users' computing problems. The operating system controls and coordinates the use of the hardware among various application programs for the various users.
• From the computer's point of view, the operating system is most intimately involved with the hardware. In this context, we can view an operating system as a resource allocator. An operating system is a control program. A control program manages the execution of user programs to prevent errors and improper usage of the computer.
• No one way to define operating systems. A more common definition is that the operating system is the one program running at all times on the computer (usually called the kernel), with all else being system programs and application programs.

Computer System Organization

• A modern general-purpose computer system consists of one or more CPUs and a number of device controllers connected through a common bus that provides access to shared memory. Each device controller is in charge of a specific type of device. The CPU and the device controllers can execute concurrently, competing for memory cycles. To ensure orderly access to the shared memory, a memory controller is provided whose function is to synchronize access to the memory.
• For a computer to start running - for instance, when it is powered up or rebooted - it needs to have an initial program to run. The initial program, or bootstrap program, tends to be simple. Typically, it is stored in read-only memory (ROM) or electrically erasable programmable read-only memory (EEPROM), known by the general term firmware, within the computer hardware. It initializes all aspects of the system, from CPU registers to device controllers to memory contents.

• The bootstrap program must know how to load the operating system and start executing that system. To accomplish this goal, the bootstrap program must locate and load into memory the operating-system kernel. The operating system then starts executing the first process, such as "init", and waits for some event to occur.
• The occurrence of an event is usually signaled by an interrupt from either the hardware of the software. Software may trigger an interrupt by executing a special operation called a system call. When the CPU is interrupted, it stops what it is doing and immediately transfers execution to a fixed location. The fixed location usually contains the starting address where the service routine for the interrupt is located. The interrupt service routine executes; on completion, the CPU resumes the interrupted computation. An interrupt vector, or addresses is then indexed by a unique device number, given the interrupt request, to provide the address of the interrupt service routine for the interrupting device.
• Computer programs must be in main memory (also called random-access memory or RAM) to be executed. Main memory is the only large storage area that the processor can access directly. It commonly is implemented in a semiconductor technology called dynamic random-access memory (DRAM), which forms an array of memory words. Each word has its own address. Interaction is achieved through a sequence of load or store instructions to specific memory addresses. The load instruction moves a word from main memory to an internal register within the CPU, whereas the store instruction moves the content of a register to main memory.
• A typical instruction - execution cycle, as executed on a system with a von Neumann architecture, first fetches an instruction from memory and stores the instruction in the instruction register. The memory sees only a stream of memory addresses, it does not know how they were executed or what they are for.
• Programs and data can not stay in main memory forever because:
• • Main memory is too small to store all needed programs and data permanently
  • Main memory is a volatile storage device that loses its contents when power is turned off or otherwise lost.
• Thys, most computer systems provide secondary storage as an extension of main memory. The main requirement for secondary storage is that it be able to hold large quantities of data permanently.
• The most common secondary-storage device is a magnetic disk, which provides storage for both programs and data. Most programs are stored on disk until they are loaded into memory. Many programs then use the disk as both a source and destination of the information in their processing.
• Each storage system provide the basic functions of storing a datum and of holding that datum until it is retrieved at a later time. The main differences among the various storage systems lie in speed, cost, size, and volatility. The wide variety of storage systems in a computer can be organized in a hierarchy according to speed and cost.

• Volatile storage loses its contents when the power to the device is removed. Data must be moved to nonvolatile storage for safe keeping.
• Storage is only one of many types of I/O devices within a computer. A general purpose computer consists of CPUs and managed device controllers that are connected through a common bus. Each device controller is in charge of a specific type of device. The device controller is responsible for moving the data between peripheral devices that it controls and its local buffer storage. Typically, operating systems have a device driver for each device controller. This device driver understands the device controller and presents a uniform interface to the device to the rest of the operating system.

• Direct Memory Access (DMA) - after setting up buffers, pointers, and counters for the I/O device, the device controller transfers the entire block of data directly to or from its own buffer storage to memory, with no intervention by the CPU.

Computer System Architecture

• Most systems use a single processor. On a single-processor system, there is one main CPU capable of executing a general-purpose instruction set, including instructions from user processes. Almost all systems have special-purpose processors as well. All of these special-purpose processors run a limited instruction set and do not run user processors.
• Multiprocessor systems have two or more processors in close communication, sharing the computer bus and sometimes the clock, memory, and peripheral devices. They increase throughput, benefit from economies of scale, and have increased reliability.
• The ability to continue providing service proportional to the level of surviving hardware is called graceful degradation. Some systems go beyond graceful degradation and are called fault tolerant, because they can suffer a failure of any single component and still continue operation.
• The multiprocessor systems in use today are of two types: Some use asymmetric multiprocessing in which each processor is assigned a specific task. A master process controls the system, and other processes either look to the master for instruction or have predefined tasks (Master-slave relationship). The most common systems use symmetric multiprocessing (SMP) in which each processor performs all tasks within the operating system. In SMP, all processors are peers. The benefit of SMP is that each process can run simultaneously without causing a significant deterioration of performance. SMPs will allow processes and resources - such as memory - to be shared dynamically among the various processors and can lower the variance among processors.

• A recent trend in CPU design is to include multiple compute cores on a single chip.
• Clustered Systems: Like SMPs, they gather together multiple CPUs to accomplish computational work. Clustered systems are composed of two or more individual systems coupled together. The general accepted definition is that clustered computers share storage and are closely linked via a local-area network (LAN). Clustering is used to provide a high-availability service - service will continue even if one or more systems in the cluster fail. Clustering can be structured asymmetrically or symmetrically.

Operating System Structure

• An operating system provides an environment within which programs are executed.
• One of the most important aspects of operating systems is the ability to multiprogram. A single user cannot keep either the CPU or the I/O devices busy at all time. Multiprogramming increases CPU utilization by organizing jobs (code and data) so that the CPU always has one to execute. As long as there is one job needs to execute, the CPU is never idle.
• Multiprogrammed systems provide an environment in which the various system resources (e.g., the CPU, memory, and peripheral devices) are utilized effectively, but they do not provide for user interaction with the computer system. Time sharing (or multitasking) is the logical extension of multiprogramming, In time-sharing systems, the CPU executes multiple jobs by switching among them, but the switches occur so frequently that the users can interact with each program while it is running.
• Time sharing requires an interactive computer system which provides direct communication between the user and the system. The response time should be short for a user switching tasks. This also allows multiple users to use the system. A program loaded into memory and executing is called a process. When a process executes, it typically executes for only a short time before it either finishes or needs to perform I/O.
• Since time sharing requires multiple programs to be in memory and since multiple jobs are too large to be kept in memory, the jobs are kept initially in the job pool. This pool consists of all processes residing on the disk awaiting allocation of main memory. Job scheduling is deciding which jobs to bring into memory from the job pool. CPU scheduling is deciding which jobs to run when multiple jobs are in memory.
• How to achieve reasonable response time: swapping, where processes are swapped in and out of main memory to the disk; virtual memory, a technique that allows the execution of a process that is not completely in memory - enables users to run programs that are larger than actual physical memory.
• Time sharing systems must provide a file system, a mechanism from protecting resources from inappropriate use, mechanisms for job synchronization and communication, and ensure that jobs do not get stuck in deadlock.

Operating System Operations

• Operating systems are interrupt driven. Events are almost always signaled by the occurrence of an interrupt or a trap. A trap (or an exception) is a software generated interrupt caused either by an error or by a specific request from a user program that an operating system service be performed.
• We need two separate modes of execution: user mode and kernel mode (also called supervisor mode, system mode, or privileged mode). A bit, called the mode bit, is added to the hardware of the computer to indicate the current mode: kernel (0) or user (1). When the computer system is executing on behalf of an application, it is in user mode. When a user requests service from an operating system, it must transition to kernel mode to complete the request.
• When the user boots, it is in kernel mode.

• Dual mode protects the OD from errant users. Privileged instructions are a means of protecting the system and can only be executing in kernel mode. Examples of privileged instructions: switching modes, I/O control, timer management, and interrupt management.

We can now see the life cycle of instruction execution in a computer system. Initial control is within the operating system, where instructions are executed in kernel mode. When control is given to a user application, the mode is set to user mode. Eventually, control is switched back to the operating system via an interrupt, a trap, or a system call.

• A system call is a method used by a process to request action by the operating system.
• We use a timer to ensure that the operating system maintains control over the CPU and that the application program does not get stuck in an infinite loop. A timer can be set to interrupt the computer after a specified period. A variable timer is generally implemented by a fixed-rate clock and a counter.

Process Management

• A program itself is not a process. A program is a passive entity, such as the contents of a file stored on disk, whereas a process is an active entity. A single-threaded process has one program counter specifying the next instruction to execute. An operating system is responsible for the following activities in connection with process management:
• • Creating and deleting both user and system processes
  • Suspending and resuming processes
  • Providing mechanisms for process synchronization
  • Providing mechanisms for process communication
  • Providing mechanisms for deadlock handling

Memory Management

• The main memory is central to the operation of a modern computer system. Main memory is a large array of words or bytes, ranging in size from hundreds of thousands to billions. Rach word or byte has its own address. Main memory is a repository of quickly accessible data shared by the CPU and I/O devices. The central processor reads instructions from main memory during the instruction-fetch cycle and both reads and writes data from main memory during the data-fetch cycle. For a program to be executed, it must be mapped to absolute addresses and loaded into memory.
• The operating system is responsible for the following activities in connection with memory management:
• • Keeping track of which parts of memory are currently being used and by whom
  • Deciding which processes (or parts thereof) and data to move into and out of memory
  • Allocating and deallocating memory space as needed.

Storage Management

• To make the computer system convenient for users, the operating system provides a uniform, logical view of information storage. The operating system abstracts from the physical properties of its storage devices to define a logical storage unit, the file. The operating system maps files onto physical media and accesses these files via the storage devices to define a logical storage unit, the file. The operating system maps files onto physical media and accesses these files via the storage devices. A file is a collection of related information defined by its creator. Commonly, files represent programs and data.
• The operating system implements the abstract concept of a file by managing mass storage media and the device that control them. The operating system is responsible for the following activities in connection with file management:
• • Creating and deleting files
  • Creating and deleting directories to organize files
  • Supporting primitives for manipulating files and directories
  • Mapping files onto secondary storage
  • Backing up files on stable (nonvolatile) storage media
• The operating system is responsible for the following activities in connection with disk management:
• • Free-space management
  • Storage allocation
  • Disk scheduling
• Caching is an important principle of computer systems. Information is normally kept in some storage system (such as main memory). As it is used, it is copied into a faster storage system - the cache - on a temporary basis. When we need a particular piece of information, we first check whether it is in the cache. If it is, we use the information directly from the cache; if it is not, we use the information from the source, putting a copy in the cache under the assumption that we will need it again soon.
• Because caches have limited size, cache management is an important design problem.

• In a multitasking environment, where CPU is switched back and worth among various processes, extreme care must be taken to ensure that, if several processes wish to access A, then each of these processes will obtain the most recently updated value of A.

• We must make sure to update the value of A in one cache is immediately reflected in all other caches where A resides. This situation is called cache coherency, and it is usually a hardware problem.
• The I/O subsystem consists of several components:
• • A memory management component that includes buffering, caching, and spooling
  • A general device-driver interface
  • Drivers for specific hardware devices

Protection and Security

• If a computer system has multiple users and allows the concurrent execution of multiple processes, the access to data must be regulated. For that purpose, mechanisms ensure that files, memory segments, CPU, and other resources can be operated on by only those processes that have gained proper authorization from the operating system. Protection is any mechanism for controlling the access of processes or users to the resources defined by a computer system. This mechanism must provide means for specification of the controls to be imposed and means for enforcement.
• It is a job of security to defend a system from external and internal attacks. Prevention of some attacks is considered an operating system function on some systems, while others leave the prevention to policy or additional software. Most operating systems maintain a list of user names and associated user identifiers (user IDs). Group functionality can be implemented as a system-wide list of group names and group identifiers. A user sometimes needs to escalate privileges to gain extra permissions for an activity.

Distributed Systems

• A distributed system is a collection of physically separate, possibly heterogeneous computer systems that re networked to provide the users with access to various resources that the system maintains. Access to a shared resource increases computation speed, functionality, data availability, and reliability. A network in the simplest terms is a communication path between two or more systems. Distributed systems depend on networking for their functionality. To an operating system, a network protocol simply needs an interface device - a network adapter, for example - with a device driver to manage it, as well as software to handle data.
• Networks are characterized based on the distances between their nodes. A local-area network (LAN) connects computers with a room, a floor, or a building. A wide-area network (WAN) usually links buildings, cities, or countries. These networks may run one protocol or several protocols. A metropolitan area network (MAN) could link buildings within a city. Bluetooth and 802.11 devices use wireless technology to communicate over a distance of several feet, in essence creating a small-area network, such as might be found in a home. A network operating system is an operating system that provides features such as file sharing across the network and that includes a communication scheme that allows different processes on different computers to exchange messages.

Special-Purpose Systems

• There are different classes of computer systems whose functions are more limited and whose objective is to deal with limited computation domains. Embedded computers are the most prevalent form of computers in existence. These devices are found everywhere, from car engines and manufacturing robots to VCRs and microwave ovens. They tend to have very specific tasks. The systems they run on are usually primitive, and so the operating systems provide limited features.
• Embedded systems almost always are real-time operating systems. A real-time system is used when rigid time requirements have been place on the operation of a processor or the flow of data; thus, it is often used as a control device in a dedicated application.
• Multimedia data consists of audio and video files. Handheld systems include personal digital assistants (PDAs) such as cellular telephones, many of which use special-purpose embedded operating systems.

Computing Environments

• Companies establish portals, which provide web accessibility to their internal servers. Network computers are essentially terminals that understand web-based computing. Handheld computers can synchronize with PCs to allow very portable use of company information. Handheld PDAs can also connect to wireless networks to use the company's web portal.
• May of todays systems act as server systems to satisfy requests generated by client systems. This form of specialized distributed system, called client-server system, has the structure seen below.

• The compute-server system provides an interface to which a client can send a request to perform an action; in response, the server executes the action and sends back the result to the client. A server running a database that responds to client requests for data is an example for such system.
• The file-server system provides a file-system interface where clients can create, update, read, and delete files. An example of such a system is a web server that delivers files to clients running web browsers.
• To participate in a peer to peer system, a node must first join the network of peers. once a node has joined the network, it can begin providing services to - and requesting services form - other nodes in the network.
• The implementation of web-based computing has given rise to new categories of devices, such as load balancers, which distribute network connections among a pool of similar servers.

Operating Systems Structures

• One set of operating-system services provides functions that are helpful to the user
• • User interface - Almost all operating systems have a user interface (UI). This interface can take several forms. One is a command line interface (CLI), which uses text commands and a method for entering them. Another is batch interface, in which commands and directives to control these commands are entered into files, and those files are executed. Most commonly, a graphical user interface (GUI) is used. Here, the interface is a window system with a pointing device to direct I/O, choose from menus, and make selections and a keyboard to enter text.
  • Program Execution - The system must be able to load a program into memory and to run that program. The program must be able to end its execution, either normally or abnormally (indicating error).
  • I/O Operations - The OS must provide a means to do I/O.
  • File System Manipulation - Read, write, create, delete, and change permissions on files and directories.
  • Communication - Communication between processes.
  • Error Detection - The OS needs to be aware of possible errors.
  • Resource Allocation - resources must be allocated to different users and jobs
  • Accounting - keep track of which users use how much and what kinds of computer resources
  • Protection and Security - control the use of information
• Two fundamental approaches for users to interface with the operating system:
• • Command interpreter allows users to directly enter commands that are to be performed by the OS.
  • Graphical User Interface provides a desktop metaphor where the mouse is moved to position its pointers on images, or icons, on the screen that represent various things. GUI directories are known as folders.
• System calls provide an interface to the services made available by an operating system. These calls are generally available as routines written in C and C++, although certain low-level tasks (tasks where hardware must be accessed directly) may need to be written using assembly-language instructions.
• Application developers design programs according to an application programming interface (API). The API specifies a set of functions that are available to an application programmer, including the patterns that are passes to each function and the return values the programmer can expect. The POSIX API is used for UNIX and Linux systems.
• The run-time support system (a set of functions built into libraries included with a compiler) for most programming languages provides a system call interface that serves as the link to system calls made available by the operating system.

• System calls can be grouped roughly into five major categories:
• • Process Control
  • • end, abort
    • load, execute
    • create process, terminate process
    • get process attributed, set process attributes
    • wait for time
    • wait event, signal event
    • allocate and free memory
  • File Manipulation
  • • create file, delete file
    • open, close
    • read, write, reposition
    • get file attributes, set file attributes
  • Device Manipulation
  • • request device, release device
    • read, write, reposition
    • get device attributes, set device attributes
    • logically attach or detach devices
  • Information Maintenance
  • • get time or date, set time or date
    • get system data, set system data
    • get process file, or set device attributes
    • set process file, or device attributes
  • Communication
  • • create, delete communication connection
    • send, receive messages
    • transfer status information
    • attach or detach remote devices
• System programs provide a convenient environment for program development and execution
• • File management
  • Status information
  • File modification
  • Programming language support
  • Program loading and execution
  • Communications
• The fundamental idea behind a virtual machine is to abstract the hardware of a single computer into several different execution environments, thereby creating the illusion that each separate execution environment is running its own private computer.
• VMware allows host systems to run several different guest operating systems as independent virtual machines.

• Garbage collection - the practice of reclaiming memory from objects no longer in use and returning it to the system.
• System generation - OSs must run on computers of different specs, so the system must be configured or generated for each specific computer site. This can be done by reading from a given file, asking the operator of the system for information concerning the specific configuration of the hardware system, or probing the hardware directly to determine what components are there.
• The procedure of starting a computer by loading the kernel is known as booting the system. On most computer systems, a small piece of code known as the bootstrap program or bootstrap loader locates the kernel, loads it into main memory, and starts its execution.
• When a computer is rebooted, the instruction register is loaded with a predefined memory location, and execution starts there. At that location is the initial bootstrap program. This program is in the form of read only memory (ROM) because RAM is in an unknown state at system startup. ROM is convenient because it needs no initialization and cannot be infected by a computer virus. Erasable Programmable Read-Only memory is memory that is read only except when explicitly given a command to become writable. All forms of ROM are known as firmware since their characteristics fall somewhere between those of hardware and software.

Process Management

A process can be thought of as a program in execution. A process will need certain resources - such as CPU time, memory, files, and I/O devices - to accomplish its task. These resources are allocated to the process either when it is created or while it is executing.
A process is the unit or work in most systems. Systems consist of a collection of processes: Operating system processes execute system code, and user processes execute user code. All these processes may execute concurrently.
Most modern operating systems now support processes that have multiple threads. The operating system is responsible for the create and deletion of both user and system processes; the scheduling of processes; and the provision of mechanisms for synchronization, communication, and deadlock handling for processes.

Processes

Process - a program in execution. A process is a unit of work in a modern time-sharing system.

• A process includes program code, the current activity, represented by the program counter, and the contents of the processor's registers. A process generally also includes the process stack, which contains temporary data (such as function parameters, return addresses, and local variables), and a data section, which contains global variables. A process may also include a heap, which is memory that is dynamically allocated during process run time. A process is an active entity with a program counter specifying the next instruction to execute and a set of associated resources. A program becomes a process when an executable file is loaded into memory.

• The process changes state as it executes. State may be new, running, waiting, ready, or terminated.
• Each process is represented in the OS by a process control block.

• The process scheduler selects an available process for program execution on the CPU - the objective of time sharing is to switch the CPU among processes so frequently that users can interact with each program while it is running.
• A lot of queues involved in scheduling. Job queue consists of all processes in the system. The process that are ready and waiting to execute are kept on a list called the ready queue.
• An I/O bound process is one that spends more of its time doing I/O than it spends doing computations. A CPU bound process generates I/O requests infrequently, using more of its time doing computations.
• Changing processes involves swapping, which is a process that requires saving and restoring the state of the process.
• Most OS systems identify processes according to a unique process identifier (or pid) which is typically an integer number.
• There are parent and child processes.
• A process is independent if it cannot affect or be affected by other processes executing in the system. Any process that does not share data with any other process is independent. A process is cooperating it it can affect or be affected by the other processes executing in the system.
• Cooperating processes require an interprocess communication (IPC) mechanism that will allow them to exchange data and information. There are two fundamental models of interprocess communication: (1) shared memory and (2) message passing.

• A socket is defined as an endpoint for communication. A pair of processes communicating over a network employ a pair of sockets - one for each process. A socket is identified by an IP address concatenated with a port number. In general, sockets use a client-server architecture. The server waits for incoming client requests by listening to a specified port. Once a request is received, the server accepts a connection from the client socket to complete the connection.
• A port is simply a number included at the start of a message packet. Whereas a system normally has one network address, it can have many ports within that address to differentiate the many network services its supports.
• Remote procedure calls - when a process calls a procedure on a remote application.

Threads

• A thread is a basic unit of CPU utilization; it comprises a thread ID, a program counter, a register set, and a stack. It shares with other threads belonging to the same process and its code section, data section, and other operating-system resources, such as open files and signals. A traditional (or heavyweight) process has a single thread of control. If a process has multiple threads of control, it can perform more than one task at a time.

• Benefits of multithreaded programming (quick, shared resources):
• • responsiveness
  • resource sharing
  • economy
  • utilization of multiprocessor architectures
• Threads may be provided at the user level by user threads or at the kernel level by kernel threads. A thread library provides the programmer an API for creating and managing threads.
• Thread cancellation is the task of terminating a thread before it has completed.
• A signal is used in UNIX systems to notify a process that a particular event has occurred. A signal may be received either synchronously or asynchronously, depending on the source of and the reason for the event being signaled. All signals, whether asynchronous or synchronous, follow the same pattern:
• • A signal is generated by the occurrence of a particular event
  • A generated signal is delivered to a process
  • Once delivered, the signal must be handled.

CPU Scheduling

• Every signal may be handled by a default signal handler or a user defined signal handler.
• Thread pool - create a number of threads at process startup and place them into a pool, where they sit and wait for work. When a server receives a request, it awakens a thread from this pool - if one is available - and passes it the request to service.
• Thread specific data - when a certain thread needs its own copy of specific data

• Process execution consists of a cycle of CPU execution and I/O wait. Processes alternate between these two states. Process execution begins with a CPU burst. That is followed by an I/O burst, which is followed by another CPU burst, ...
• Whenever the CPU becomes idle, the operating system must select one of the processes in the ready queue to be executed. The selection process is carries out by the short-term scheduler (or CPU scheduler).

Notes will be pretty sparse from hear on out. I really only want to have a rudimentary understanding of Operating Systems right now, and I can come back later to this if I need to.

• CPU scheduling is the task of selecting a waiting process form the read queue and allocating CPU to it. The CPU is allocated to the selected process by the dispatcher.
• First come, first server (FCFS) scheduling is the simplest scheduling algorithm, but it can cause short processes to wait for very long processes. Shortest job first (SJF) is provably optimal, providing the shortest average waiting time. Implementing shortest job first scheduling is difficult because predicting the length of the next CPU burst is difficult. The SJF algorithm is a special case of the general priority scheduling algorithm, which simply allocates the CPU to the highest-priority process. Both priority and SJF scheduling may suffer from starvation. Aging is a technique to prevent starvation.
• Round robin (RR) scheduling is more appropriate for a time-shared (interactive) system. RR scheduling allocates the CPU to the first process in the ready queue for q time slots, where q is the time quantum. After q time units, if the process has not yet relinquished the CPU, it is preempted, and the process is put at the tail of the ready queue. The major problem is the selection of the time quantum. If the time quantum is too large, RR scheduling degenerates to FCFS scheduling, if the quantum is too small, scheduling overhead in the form of context-switch time becomes expensive.
• Multilevel queue algorithms allow different algorithms to be used for different classes of processes. Many contemporary computer systems support multiple processors and allow each processor to schedule itself independently. Operating systems supporting threads at the kernel level must schedule threads - not processes - for execution.
• Many contemporary computer systems support multiple processors and allow each processor to schedule itself independently.
• Operating systems supporting threads at the kernel level must schedule threads - not processes - for execution.
• The wide variety of scheduling algorithms demands that we have methods to select among algorithms.

Process Synchronization

• Given a collection of cooperating sequential processes that share data, mutual exclusion must be provided. One solution is to ensure that a critical section of code is in use by only one process or thread at a time. Different algorithms exist for solving the critical-section problem, with the assumption that only storage interlock is available.
• The operating system must provide the means to guard against timing errors. Operating systems must provide support for synchronization. A transaction is a program unit that must be executed atomically; that is, either all the operations associated with it are executed to completion, or none are performed. To ensure serializability, when the execution of several transactions overlaps, we must use a concurrency-control scheme.

Deadlocks

• A deadlock occurs when two or more processes are waiting indefinitely for an event that can be cause only by one or more writing processes. There are three principal methods for dealing with deadlocks:
• • Use some protocol to prevent or avoid deadlocks, ensuring that the system will never enter a deadlock state
  • Allow the system to enter a deadlock state, detect it, and then recover
  • Ignore the problem altogether and pretend that deadlocks never occur in the system.
  • • Most operating systems, including UNIX and Windows, do this.

A deadlock can occur only if four necessary conditions hold simultaneously in the system: mutual exclusion, hold and wait no preemption, and circular wait. To prevent deadlocks, we can ensure that at least one of the necessary conditions never holds

Memory Management

• The main purpose of a computer system is to execute programs. These programs, together with the data they access, must be in main memory (at least partially) during execution.
• To improve both the utilization of the CPU and the speed of its response to users, the computer must keep several processes in memory. Many memory management schemes exist, reflecting various approaches, and the effectiveness of each algorithm depends on the situation. Selection of a memory management scheme for a system depends on many factors, especially on the hardware design of a system. Each algorithm requires its own hardware support.

Main Memory

• Memory management algorithms for multiprogrammed operating systems range from the simple single-user system approach to pages segmentation. The various memory management algorithms differ in many aspects. In comparing the strategies, we use the following considerations:
• • Hardware support
  • Performance
  • Fragmentation
  • Relocation
  • Swapping
  • Sharing
  • Protection

Virtual Memory

• It is desirable to be able to execute a process whose logical address space is larger than the available physical address space. Virtual memory us a technique that enables us to map a large logical address space onto a smaller physical memory. Virtual memory allows us to run extremely large processes and to raise the degree of multiprogramming, increasing CPU utilization.
• Virtual memory is commonly implemented by demand paging. Pure demand paging never brings in a page until that page is referenced.

Storage Management

• For most users, the file system is the most visible aspect of an operating system. It provides the mechanism for on-line storage of and access to both data and programs of the operating system and all the users of the computer system. The file system consists of two distinct parts: a collection of files, each storing related data, and a directory structure, which organizes and provides information about all the files in the system.

File System Interface

• A file is an abstract data type defined and implemented by the operating system. It is a sequence of logical records. A logical record may be a byte, a lone, or a more complex data item. The operating system may specifically support various record types or may leave that support to the application program.
• The major task for the operating system is to map the logical file concept onto physical storage devices such as magnetic tape or disk.
• Each device in a file system keeps a volume table of contents or device directory listing the location of files on the device. In addition, it is useful to create directories to allow files to be organized.

File System Implementation

• The file system resides permanently on secondary storage, which is designed to hold large amount of data permanently. The most common secondary storage medium is a disk.
• Network file systems, such as NFS, use client-server methodology to allow users to access files and directories from remote machines as if they were on local file systems,

Mass-Storage Structure

• Disk drives are the major secondary-storage I/O devices on most computers. Most secondary storage devices are either magnetic disks or magnetic tapes. Modern disk drives are structures as large one-dimensional array of logical disk blocks which is usually 512 bytes. Disks may be attached to a computer system in one of two ways: (1) using the logical I/O ports on the host computer or (2) using a network connection such as storage area network.

I/O Systems

• The basic hardware elements involved in I/O are buses, device controllers, and the devices themselves. The work of moving data between devices and main memory is performed by the CPU as programmed I/O or is offloaded to a DMA controller. The kernel module that controls a device is a device driver.

Protection and Security

• The processes in an operating system must be protected from one another's activities. To provide such protection, we can use various mechanisms to ensure that only processes that have gained proper authorization from the operating system can operate on the files, memory segments, CPU, and other resources of a system.
• Protection refers to a mechanism for controlling the access of programs, processes, or users to the resources defined by a computer system. This mechanism must provide a means for specifying the controls to be imposed, together with a means of enforcement. We distinguish between protection and security, which is a measure of confidence that the integrity of a system and its data will be preserved.

Protection

• An access right is permission to perform an operation on an object. A domain is a set of access rights.

Security

• Security must consider both the computer system and the environment - people, buildings, businesses, valuable objects, and threats - within which the system is used. Encryption limits the domain of the receivers of data, while authentication limits the domain of senders.

Distributed Systems

• A distributed system is a collection of processors that do not share memory or a clock. Instead, each processor has its own local memory. The processors communicate with one another through various communication networks, such as high-speed buses or telephone lines. In this chapter, we discuss the general structure of distributed systems and the networks that interconnect them.

Special-Purpose Systems

• There are special-purpose systems with requirements different from those of general-purpose operating systems. A real-time system is a computer system that requires that computed results be "correct" but also that the results be produced within a specified deadline period. A multimedia system must be able to handle not only conventional data, such as text files, programs, and word-processing documents, but also multimedia data - such as audio and video data.

Case Studies

The Linux System

• The Linux system has grown to include much UNIX functionality. The Linux Kernel is an entirely original piece of software developed from scratch by the Linux community. The Linux system includes a multitude of components. The basic Linux system is a standard environment for applications and user programming, but it does not enforce any standard means of managing the available functionality as a whole. Linux Distributions provide another layer of functionality on top of the Linux system - it includes the standard components of the Linux system, plus a set of administrative tools to simplify the initial installation and subsequent upgrading of other packages on the system.
• Linux is not Public Domain software - copyright rights in Linux code are still held by the code's various authors, but it is free.
• Linux resembles any other traditional, nonmicrokernel UNIX implementation. It is multiuser, multitasking system with a full set of UNIX-compatible tools. Linux's file system adheres to traditional UNIX semantics, and the standard UNIX networking model is implemented fully. The internal details of Linux's design have been influenced heavily by the history of this operating system's development.
• The Linux system is composed of three main bodies of code, in line with most traditional UNIX implementations:
• • Kernel - responsible for maintaining all the important abstractions of the operating system, including such things as virtual memory and processes
  • System Libraries - the system libraries define a standard set of functions through which applications can interact with the kernel. Those functions implement much of the operating system functionality that does not need the full privileges of kernel code.
  • System Utilities - The system utilities are programs that perform individual, specialized management tasks. Some system utilities may be invoked just once to initialize and configure some aspect of the system; others - known as daemons in UNIX terminology - may run permanently; handling tasks such as responding to incoming network connections, accepting logon terminals and updating log files.
• All kernel code executes in the processor's privileged mode with full access to all physical resources of the computer. Linux refers to this privileged mode as kernel mode.

• The kernel is created as a single, monolithic binary.
• The module support under Linux has three components:
• • The module management allows modules to be loaded into memory and talk to the rest of the kernel.
  • The driver registration allows modules to tell the rest of the kernel that a new driver has become available.
  • • Registration tables include the following items:
    • • Device Drivers
      • File systems
      • Network Protocols
      • Binary Format - specifies a way of recognizing, and loading, a new type of executable file.
  • A conflict resolution mechanism allows different device drivers to reserve hardware resources and to protect resources from accidental use by another driver.
• Under UNIX, a process encompasses all the information that the OS must maintain to track the context of a single execution of a single program. Under Linux, this information falls into three groups: identity, environment, and context.
• • A process identity consists of a Process ID (PID), credentials (each process must have an associated user ID and one or more group IDs), and personality (modify slightly the semantics of some system calls).
  • A process's environment is inherited from its parent and is composed of two null-terminated vectors: the argument vector and the environment vector. The argument vector simply lists the command line arguments used to invoke the running program. The environment vector is a list of "NAME=VALUE" pairs that associates named environment variables with arbitrary textual values.
  • Process context includes scheduling context - the information the scheduler needs to suspend and restart the process, accounting - maintains information about the resources currently being consumed by each process, file table - array of pointers to kernel file structures, file-system context - requests to open new files, signal-handler table - defines the routine in the process's address space to be called when specific signals arrive, and virtual memory context (describes the full contents of a process's private address space).
• Linux does not distinguish between processes and threads. Linux uses the term task, rather process or thread - when referring to a flow of control within a program.
• Linux has two separate process-scheduling algorithms One is a time-sharing algorithm for fair, preemptive scheduling among multiple processes; the other is designed for real-time tasks, where absolute priorities are more important than fairness. The Linux scheduler is a preemptive, priority based algorithm with two separate priority ranges: a real-time range from 0-99 and a nice value ranging from 100 to 140. These two ranges map into a global priority scheme whereby numerically lower values indicate higher priorities.

A runnable task is considered eligible for execution on the CPU so long as it has time remaining in its time slice. When a task has exhausted its time slice, it is considered expired and is not eligible for execution again until all other tasks have also exhausted their time quanta. The kernel maintains a list of all runnable tasks in a runqueue data structure. Because of its support for SMP, each processor maintains its own runqueue and schedules itself independently. Each runqueue contains two priority arrays-active and expired.

• Memory management under Linux has two components. The first deals with allocating and freeing physical memory - pages, groups of pages, and small blocks of memory. The second handles virtual memory, which is the memory mapped into the address space of running processes.
• Linux retains UNIX's standard file system model. In UNIX, a files does not have to be an object stored on disk or fetched over a network from a remote file server. Rather, UNIX files can be anything capable of handling the input or output of a stream of data. Device drivers can appear as files, and interprocess communication channels or network connections also look like files to the user. The Linux kernel handles all these types of file by hiding the implementation of any single file type behind a layer of software, the virtual file system (VFS).
• Linux's security model is closely related to typical UNIX security mechanisms. The security concerns can be classified in two groups:
• • Authentication - Making sure that nobody can access the system without first proving that they have entry rights
  • Access Control - Providing a mechanism for checking whether a user has the right to access a certain object and preventing access to objects as required.

+60