[ Main ] [ Home ] [ Work ] [ Code ] [ Rants ] [ Readings ] [ Links ]

{Latest update: 16 November 2006}

  1. Introduction
  2. Computer-System Structures
  3. Operating-System Structures
  4. Processes
Introduction

  • Primary goals of an operating system:
    • To make the computer system convenient.
    • To use the computer hardware in an efficient manner.
  • Main components of a computer system:
    • Hardware
    • Operating system
    • Application programs
    • Users
  • An operating system functions as a resource allocator on the computer system, as some form of control program or central government.
  • There is no universally accepted definition of what is part of the operating system and what is not. It is generally accepted that it is the only program running at all times on the computer, while everything else is an application program.
  • Short historical review of operating systems and types of computer architecture:
    • Simple batch systems: there is no interaction between the user and the job while it is executing; jobs that are similar are batched together and run as a group; the CPU is often idle; and uses spooling as a mechanism to print out the information when the job has finished, therefore using the disk as a buffer for reading as far ahead as possible and storing the output until the moment when the output devices are able to accept them.
    • Multiprogrammed batch systems: there is now a job pool that makes it possible to perform scheduling; multiprogramming increases the CPU utilization by organizing jobs in such a way that the CPU always has one to execute; the operating system now has to make decisions for the users for the first time ever; after selecting a job from the job pool, it is loaded into memory and run, which requires some form of memory management.
    • Time-sharing systems: multiple jobs are executed by the CPU switching between them, although the switches happen so often that users may interact with each program while running; computer interactivity; an on-line filesystem must be available; the concept of a process is born, to refer to a program that is loaded into memory and is executing; virtual memory is used as a way to allow for the excution of a job that may not be completly in memory.
    • Personal computers systems: hardware costs decreased in the 1970s; I/O devices changed from switches and card readers to display screens, mice and keyboards; personal workstations.
    • Parallel systems: there is a trend toward multiprocessor systems, systems with more than one processor that share the computer bus, the system clock, and even the memory and peripheral devices quite often; there is an increase in throughput, although it is never equivalent to the amount of processors on the system (i.e., adding one more processor will not necesarily double the trhoughput); there is an increase in the overall reliability, with the systems becoming more fault-tolerant; distinguish between symmetric multiprocessing (each processor runs an identical copy of the OS) and asymmetric multiprocessing (each processor is assigned a specific task), which can be a consequence of either hardware or software design.
    • Distributed systems: unlike in the case of tightly coupled systems (i.e., parallel systems), the processors do not share memory or a clock, each processor having its own memory instead, therefore being called loosely-coupled systems or distributed systems; they provide resource sharing between separate sites, some computation speedup, higher reliability and better communication between the programs so they can exchange data.
    • Real-time systems: used when there are rigid time requirements on the operation of a processor or the flow of data (i.e., processing must be done within the defined constraints); divided in two main types (hard real-time systems, which guarantee that critical tasks complete on time by setting bounds to delays, and soft real-time systems, where a critical real-time task gets priority over other tasks, and retains that priority until it completes).

Computer-System Structures

  • The hardware must provide appropriate mechanisms to ensure correct behavior.
  • The CPU and the device controllers can execute concurrently, therefore competing for memory cycles. To ensure orderly access to the shared memory, a memory controller may be present.

Computer-System Operation

  • The bootstrap program must locate and load into memory the operating system kernel, which then starts executing the first process (for example, init) and then waits for some event to occur.
  • When an event occurs, there is an interrupt from either the hardware of the software: the hardware by sending a signal to the CPU via the system bus, usually; the software via a system call.
  • Each interrupt has a service routine associated with it, which is responsible for dealing with it.
  • Once the CPU is interrupted, it stops whatever it is doing at that time and it transfers execution to a given memory location, which is where the service routine is located.
  • The particular design of the interrupt mechanism depends on the architecture itself.
  • Since there is a limited amount of possible interrupts, a table of pointers to interrupt routines (which is stored in low memory) is generally used. This table contains the addresses of the service routines for the different types of interrupt that could occur.
  • The interrupt architecture also saves the address of the interrupted instruction.
  • Other interrupts are normally disabled while an interrupt is being processed, although some architectures allow for one interrupt to be processed while another is being taken care of.
  • Modern operating systems are interrupt driven: the system will be sitting in idle until an interrupt (or a trap) occurs, at which point the hardware will transfer execution to the kernel.

I/O Structure

  • A device controller maintains some local buffer storage and a set of special-purpose registers. The device controller is responsible for moving the data between the peripheral devices that it controls and its local buffer storage.
  • Two main types of responses to I/O interrupts:
    • Synchronous I/O: the I/O operation is started and, when completed, control is returned to the user process. This can be accomplished either via a special wait instruction that idles the CPU until the next interrupt, or by means of a wait loop if they do not have such instruction.
    • Asynchronous I/O: control is returned to the user process without waiting for the I/O operation to complete. In this case we need a specific system call to allow the user program to wait for I/O completion as well as a device-status table containing an entry for each I/O device together with information about its current status. Finally, since other processes may also issue requests to the same device that is being used, we also need a wait queue to be implemented.
  • Direct memory access or DMA is used for high-speed I/O devices: once we set up buffers, pointers and counters for the devices, the device controller transfers an entire block of data directly to or from its own buffer storage to memory without any intervention whatsoever by the CPU.

Storage Structure

  • Main memory is the only large storage area that the processor can access directly. That is where the programs must be in order to be executed.
  • The CPU uses a sequence of load and store instructions to specific memory addresses in order to interact with the memory.
  • For a more convenient access to I/O devices, many architectures provide memory-mapped I/O, which are ranges of memory addresses set aside and mapped to the device registers.
  • Since memory access can take several CPU cycles, modern architectures have added fast memory between the CPU and the main memory (i.e., a cache).
  • Overall structure of magnetic disks:
    • They are form by disk platters with a circular shape similar to that of a CD, disposed one on top of the other around a spindle in the middle that allows for rotation.
    • A read-write head flies above each surface of every platter, and this head is attached to a disk arm which moves all the heads together.
    • The surface of a disk platter is divided into circular tracks subdivided into sectors. The set of tracks that are at one arm position forms a cylinder.
  • Disk speed has two components:
    • The transfer rate is the rate at which data flows between the drive and the computer.
    • The positioning time (also called random access time) is the time to move the disk arm to the desired cylinder (i.e., the seek time) as well as the time it takes for the desired sector to rotate to the disk head (i.e., the rotational latency).
  • A head crash happens when the head damages the magnetic surface of the disk.
  • A disk drive is attached to the system by a set of wires called an I/O bus. The actual operation to transfer data, on the other hand, is carried out by the controllers:
    • The host controller is at the computer end of the bus.
    • The disk controller is built into each disk drive.
  • Finally, magnetic tapes are used mainly for backup. They are kept in a spool that is wound or rewound past a read-write head, and provide very slow access times compared to the other storage devices mentioned here.

Storage Hierarchy

  • Storage systems on a computer can be arranged in a hierarchy where the higher levels are expensive but fast and, as we move down, the cost decreases but so does the access time:
    • Registers.
    • Cache.
    • Main memory.
    • Electronic disk.
    • Magnetic disk.
    • Optical disk.
    • Magnetic tapes.
  • Another issue to take into account is that of storage volatility.
  • Cache is used to provide faster access to the information: as information is used, it is also copied into a faster storage system; the next time that we need a particular piece of information, we check the cache for it first. Due to its limited size, cache management becomes an important design problem.
  • Since the same data may appear in different levels of the storage hierarchy, isues such as the coherency and consistency of the data become quite important, especially in a multiprocessor or a distributed environment.

Hardware Protection

  • Since several programs may be in memory at the same time, a properly designed operating system must ensure that a program cannot cause other programs to execute incorrectly. Quite often, the hardware will trap the error and will transfer control to the operating system through an interrupt. Typically, an error message is given and the memory of the program is dumped.
  • In order to provide the protection described above, we need two separate modes of operation: user mode and privileged mode (also called supervisor mode, system mode or monitor mode). Whenever a trap or interrupt occurs, the hardware switches from user mode to priviledge mode.
  • The lack of a hardware-supported dual mode can cause serious shortcomings, as it was the case of MS-DOS on the Intel 8088 architecture.
  • In order to avoid illegal I/O operations, all I/O instructions are usually privileged.
  • When it comes to memory, the hardware provides protection for the interrupt vector itself, as well as the interrupt service routines. This is usually accomplished by determining the range of legal addresses that the program may access, which is done using a base and a limit. The operating system is the only one that can change and load these base and limit settings.
  • Finally, we also need that the operating system is always in control, which means preventin an user program from taking over the CPU and running in a permanent loop. In order to accomplish this, a timer is set to interrupt the computer after a specified period and control is automatically transferred to the operating system at that point. The timer is also used to implement time sharing through the time slices as well as to compute the current time.

General System Architecture

  • Another instruction that is usually classified as privileged is the halt instruction.
  • Since only the kernel is allowed to perform I/O operations, any user program will have to request it, which is done via a system call (also called a monitor call or an operating-system function call). It usually takes the form of a trap to a specific location in the interrupt vector, but it may differ from architecture to architecture. When a system call is executed, we have a software interrupt.

Operating-System Structures

System Components

  • All the pieces or subsystems that form an operating system have to be clearly designed with very well defined inputs, outputs and functionality in order to avoid problems. The main such components to be considered are:
    • Process management.
    • Main memory management.
    • File management.
    • I/O system management.
    • Secondary storage management.
    • Networking.
    • Protection system.
    • Command-line interpreter.
  • A process is a program in execution, and will always have certain resources associated to it: CPU time, memory, files and I/O devices, among others. A process is the main unit of work in a system, and the operating system is responsible for all activities involved in process management:
    • Creation and deletion of user and system processes.
    • Suspension and resumption of processes.
    • Mechanisms for process synchronization.
    • Mechanisms for process communication.
    • Mechanisms for handling of deadlock situations.
  • Main memory contains all the data that needs to be accessed quickly by the CPU and I/O devices. It is accessed by the CPU directly, unlike other storage devices. A process is executed after it is mapped to addresses and loaded into memory. Every operating system implements different memory management schemes which are usually highly dependent on the hardware design of the system they run on. Some of the most important elements of this scheme are:
    • Keeping track of which parts of the memory are currently in use and by which process.
    • Decide which processes are to be loaded into memory when memory space becomes available.
    • Allocate and deallocate memory space as needed by the processes.
  • The operating system provides a logical or abstract view of the disk storage using the file as a storage unit. There are certain file management operations that any OS will have to handle:
    • Creation and deletion of files.
    • Creation and deletion of directories.
    • Support of primitives for manipulating files and directories.
    • Mapping of files onto secondary storage.
    • Backup of files on stable (nonvolatile) storage media.
  • The I/O subsystem hides the peculiarities of each I/O device from the OS, leaving such knowledge only to the device drivers which are the ones that deal with the specific device. The main elements of the I/O subsystem are:
    • A memory management component to take care of things such as buffering, caching and spooling.
    • A general device-driver interface.
    • Drivers for specific hardware devices.
  • While the running programs and the data they access must be in main memory during execution, they may also have additional data stored on disk. The main components of the disk management subsystem are:
    • Free-space management.
    • Storage allocation.
    • Disk scheduling.
  • Network access is usually implemented as a form of file access, with all the details of the actual connection to the remote system encapsulated in the network interface's device driver.
  • A modern OS with multiple users and concurrent execution of processes needs a protection system to control access to the system resources.
  • Some operating systems include the command-line interpreter in the kernel, while others (MS-DOS, UNIX...) implement it as a special program.

Operating-System Services

  • All operating systems provide certain services to programs and their users which make it more convenient for programmers and users to interact with the system:
    • Program execution: the system loads the program into memory and executes its instructions, then the program must be able to end its execution and exit.
    • I/O operations: in order to provide enough protection, users usually cannot access the devices. So, it is the OS itself that provides the means to perform I/O operations.
    • File-system manipulation: the OS assists programs in reading and writing files, as well as creating and deleting them.
    • Communications: sometimes a process may need to exchange information with another process running on the same or a different system. These communications can be implemented in two ways:
      • Shared memory.
      • Messag passing: packets of information are moved between processes by the operating system.
    • There is another set of operating system services that exist in order to ensure the efficient operation of the system itself:
      • Resource allocation: the operating system follows certain routines to allocate the different resources users and their processes can access: CPU, peripherals...
      • Accounting: the OS can sometimes keep track of which users use how much and what types of computer resources. This data can be used to bill the usrs or just to keep usage statistics for other purposes.
      • Protection: it should not be possible for a process to interfere with another, thererfore access to the system resources should also be controlled with security in mind.

System Calls

System Programs

System Structure

Virtual Machines

System Design and Implementation

System Generation

Processes

Process Concept

Process Scheduling

Operations on Processes

Cooperating Processes

Threads

Interprocess Communication

Resources