Modern Operating System(1)

Introduction

Computer are equipped with a layer of software called the operating system, whose job is to provide user programs with a better, simple, cleaner, model of the computer and to handle managing all the resources just mentioned.

Most computers have two modes of operation: kernel mode and user mode.

  • kernel mode: it has complete access to all the hardware and can execute any instruction the machine is capable of executing.

  • user mode: only a subset of the machine instructions is available.

What is an Operating System

Operating system perform two essentially unrelated functions:

  1. providing application programmers a clean abstract set of resources instead of the messy hard ware ones

  2. managing these hardware resources.

The Operating System as an Extended Machine

The abstraction is the key to managing all this complexity. Good abstractions turn a nearly impossible task into two manageable ones: the first is defining and implementing the abstractions; the second is using these abstractions to solve the problem at hand.

The Operating System as a Resource Manager

The concept of an operating system as primarily providing abstractions to application programs is a top-down view. A bottom-up view holds that the operating system is there to manage all the pieces of a complex system.

Resources management includes multiplexing resources in two different ways: in time and in space.

When a resource is time multiplexed, different programs or users take turns using it. Determining how the resource is time multiplexed -- who goes next and for how long -- is the task of the operating system.

The other kind of multiplexing is space multiplexing. Instead of the customers taking turns, each one gets part of the resource.

Computer Hardware Review

An operating system is intimatedly tied to the hardware of the computer it runs on. It extends the computer's instruction set and manages it resources.

The CPU, memory, and I/O devices are all connected by a system bus and communicate with one another over it.

Processors

It fetches instructions from memory and executes them. Each CPU has a specific set of instructions that it can execute. The instruction set generally contains instructions to load a word from memory into a register, and store a word from a register into memory.

Most computers have several special registers that are visible to the programmer, one of these is the program counter, which contains the memory address of the next instruction to be fetched. After that instruction has been fetched, the program counter is updated to point to its successor.

Another register is the stack pointer, which points to the top of the current stack in memory. The stack contains one frame for each procedure that has been entered but not yet exited. A procedure's stack frame holds those input parameters, local variables, and temporary variables that are not kept in registers.

Yet another register is the PSW(Program Status Word). This register contains the condition code bits, which are set by comparison instructions, the CPU priority, the mode, and various other control bits. The PSW plays an important role in system calls and I/O.

When time multiplexing the CPU, the operating system will often stop the running program to start another one. Every time it stops a running program, the operating system must save all the registers so they can be restored when the program runs later.

Many modern CPUs have facilities for executing more than one instruction at the same time.

More advanced than a pipeline design is a superscalar CPU. Multiple execution units are present, two or more instructions are fetched at once, decoded, and dumped into a holding buffer until they can be executed.

Most CPUs have two modes, kernel mode and user mode. Usually, a bit in the PSW controls the mode. When running in kernel mode, the CPU can execute every instruction in its instruction set and use every feature of the hardware. User programs always run in user mode, which permits only a subset of the instructions to be executed and a subset of the features to be accessed. Generally, all instructions involving I/O and memory protection are disallowed in user mode.

To obtain services from the operating system, a user program must make a system call, which traps into the kernel and invokes the operating system. The TRAP instruction switches from user mode to kernel mode and starts the operating system. When the work has been completed, control is returned to the user program at the instruction following the system call.

When the program has announced in advance that it wants to handle certain kinds of conditions, control can be passed back to the program to let it deal with the program.

Multithreaded and Multicore Chips

Moore's law states that the number of transistors on a chip doubles every 18 months. The obvious next step is to replicate not only the functional units, but also some of the control logic. To a first approximation, what it does is allow the CPU to hold the state of two different threads and then switch back and forth on a nanosecond time scale. Multithreading does not offer true parallelism. Only one process at a time is running, but thread-switching time is reduced to the order of a nanosecond.

Beyond multithreading, many CPU chips now have four or more complete processors or cores on them. A GPU is a processor with, literally, thousands of tiny cores. They are very good for many small computations done in parallel, like rendering polygons in graphics applications.

Memory

The second major component in any computer is the memory.

The top layer consists of the register internal to the CPU. Consequently, there is no delay in accessing them. The storage capacity available in them is typically 64*64 bits on a 64-bit CPU. Programs must manage the registers themselves, in software.

Next comes the cache memory, which is mostly controlled by the hardware. Main memory is divided up into cache lines, typically 64 bytes, with addresses 0 to 63 in cache line 0, 64 to 127 in cache line 1, and so on. When the program needs to read a memory word, the cache hardware checks to see if the line needed is in the cache. If it is, called a cache hit, the request is satisfied from the cache and no memory request is sent over the bus to the main memory. Cache hits normally take about two clock cycles. Cache misses have to go to memory, with a substantial time penalty.

In any caching system, several questions come up fairly soon, including:

  1. When to put a new item into the cache
  2. Which cache line to put the new item in
  3. Which item to remove from the cache when a slot is needed
  4. Where to put a newly evicted item in the larger memory
Disks

A disk consists of one or more metal platters that rotate at 5400, 7200, 10800 RPM or more. Information is written on to the disk in a series of concentric circles. At any given arm position, each of the heads can read an annular region called a track. Together, all the tracks for a given arm position form a cylinder.

SSDs(Solid State Disks) do not have moving parts, do not contain platters in the shape of disks, and store data in memory.

Many computer support a scheme known as virtual memory. This scheme makes it possible to run programs larger than physical memory by placing them on the disk and using main memory as a kind of cache for the most heavily executed parts. This scheme requires remapping memory addresses on the fly to convert the address the program generated to the physical address in RAM where the word is located. This mapping is done by a part of the CPU called the MMU(Mmemory Management Unit).

The presence of caching and the MMU can have a major impact on performance. In a multiprogramming system, when switching from one program to another, sometimes called a context switch, it may be necessary to flush all modified blocks from the cache and change the mapping registers in the MMU.

I/O Devices

I/O devices generally consist of two parts: a controller and the device itself.

The software that talks to a controller, giving it commands and accepting responses, is called a device driver.

There are three ways the driver can be put into the kernel. The first way is to relink the kernel with the new driver and then reboot the system. The second way is to make an entry in an operating system file telling it that it needs the driver and then reboot the system. The third way is for the operating system to be able to accept new drivers while running and install them on the fly without the need to reboot.

Hot-pluggable devices, such as USB and IEEE 1394 devices, always need dynamically loaded drivers.

Every controller has a small number of registers that are used to communicate with it. To active the controller, the driver gets a command from the operating system, then translates it into the appropriate values to write into the device registers. The collection of all the device registers forms the I/O port space.

Input and output can be done in three different ways. In the simplest method, a user program issues a system call, which the kernel then translates into a procedure call to the appropriate driver. The driver then starts the I/O and sits in a tight loop continuously polling the device to see if it is done. When the I/O has completed, the driver puts the data where they are needed and returns. The operating system then returns control to the caller. This method called busy waiting and has the disadvantage of tying up the CPU polling the device until it is finished.

The second method is for the driver to start the device and ask it to give an interrupt when it is finished. The operating system then blocks the caller if need be and looks for other work to do. When the controller detects the end of the transfer, it generates an interrupt to signal completion. Once the CPU has decided to take the interrupt, the program counter and PSW are typically then pushed onto the current stack and the CPU switched into kernel mode. The device number may be used as an index into part of memory to find the address of the interrupt handler for this device. This part of memory is called the interrupt vector. Once the interrupt handler has started, it removes the stacked program counter and PSW and saves them, then queries the device to learn its status. When the handler is all finished, it returns to the previously running user program to the first instruction that was not yet executed.

The third method for doing I/O makes use of special hardware: a DMA(Direct Memory Access) chip that can control the flow of bits between memory and some controller without constant CPU intervention. The CPU sets up the DMA chip, telling it how many bytes to transfer, the device and memory addresses involved, and the direction, and lets it go. When the DMA chip is done, it causes an interrupt.

Interrupts can happen at highly inconvenient moments. For this reason, the CPU has a way to disable interrupts and then reenable them later. While interrupts are disabled, any devices that finish continue to assert their interrupt signals, but the CPU is not interrupted until interrupts are enabled again.

Buses

A x86 system has many buses(e.g., cache, memory, PCIe, PCI, USB, SATA, and DMI), each with a different transfer rate and function. The operating system mush be aware of all of them for configuration and management. The main bus is the PCIe(Peripheral Component Interconnect Express) bus.

Capable of transferring tens of gigabits per second, PCIe is much faster than its predecessors. Most buses were parallel and shared. A shared bus architecture means that multiple devices use the same wires to transfer data. PCIe makes use of dedicated, point-to-pint connections. A parallel bus architecture as used in traditional PCI means that you send each word of data over multiple wires. PCIe uses a serial bus architecture and sends all bits in a message through a single connection, known as a a lane, much like a network packet.

The CPU talks to memory over a fast DDR3 bus, to an external graphics device over PCIe and to all other devices via a hub over a DMI(Direct Media Interface) bus.

The USB(Universal Serial Bus) was invented to attach all the slow I/O devices. USB uses a small connector with four to eleven wires, some of which supply electrical power to the USB devices or connect to ground. Any USB device can be connected to a computer and it will function immediately, without requiring a reboot.

The SCSI(Small Computer System Interface) bus is a high-performance bus intended for fast disks, scanners, and other devices needing considerable band width.

What plug and play does is have the system automatically collect information about the I/O devices, centrally assign interrupt levels and I/O addresses, and then tell each card what its number are.

Booting the Computer

Every PC contains a parentboard. On the parentboard is a program called the system BIOS. The BIOS contains low-level I/O software, including procedures to read the keyboard, write to the screen, and do disk I/O, among other things.

BIOS first checks to see how much RAM is installed and whether the keyboard and other basic devices are installed and responding correctly. It starts out by scanning the PCIe and PCI buses to detect all the devices attached to them.

The BIOS then determines the boot device by trying a list of devices stored in the CMOS memory. The first sector from the boot device is read into memory and executed. This sector contains a program that normally examines the partition table at the end of the boot sector to determine which partition is active. Then a secondary boot loader is read in from that partition. This loader reads in the operating system from the active partition and starts it.

The operating system then queries the BIOS to get the configuration information. Once it has all the device drivers, the operating system loads them into the kernel.

The Operating System Zoo

Mainframe Operating Systems

Mainframes differ from personal computers in terms of their I/O capacity.

The operating systems for mainframes are heavily oriented toward processing many jobs at once, most of which need prodigious amounts of I/O. They typically offer three kinds of services: batch, transaction processing, and timesharing. A batch system is one that processes routine jobs without any interactive user present. Transaction-processing system handle large numbers of small requests. Timesharing systems allow multiple remote users to run jobs on the computer at once.

Server Operating Systems

Servers serve multiple users at once over a network and allow the users to share hardware and software resources.

Multiprocessor Operating Systems

An increasingly common way to get major-league computing power is to connect multiple CPUs into a single system. Depending on precisely how they connected and what is shared, these systems are called parallel computers, multi-computers, or multiprocessors.

Personal Computer Operating Systems

Modern ones all support multiprogramming, often with dozens of programs started up at boot time.

Handheld Computer Operating Systems

Most of these devices boast multicore CPUs, GPS, cameras and other sensors, copious amounts of memory, and sophisticated operating systems.

Embedded Operating Systems

The main property which distinguishes embedded systems from handhelds is the certainty that no untrusted software will ever run on it. All the software is in ROM. This means that there is no need to protection between applications.

Sensor-Node Operating Systems

Sensor networks are used to protect perimeters of buildings, guard national boarders, detect fires in forests, measure temperature and precipitation for weather forecasting, glean information about enemy movements on battlefields.

Each sensor node is a real computer, with a CPU, RAM, ROM, and one or more environmental sensors. The operating system has to be small and simple because the nodes have little RAM and battery lifetime is a major issue.

Real-Time Operating System

These systems are characterized by having time as a key parameter. Often there are hard deadlines that must be met. If the action absolutely mush occur at a certain moment, we have a hard real-time system. These systems must provide absolute guarantees that a certain action will occur by a certain time.

A soft real-time system, is one where missing an occasional deadline, while not desirable, is acceptable and does not cause any permanent damage.

Since meeting deadlines is crucial in real-time systems, sometimes the operating system is simply a library linked in with the application programs, with everything tightly coupled and no protection between parts of the system.

Smart Card Operating Systems

The smallest operating systems run on smart cards, which are credit-card-sized devices containing a CPU chip. Resource management and protection also become an issue when two or more applets are present at the same time. These issues must be handled by the operating system present on the card.

Operating System Concepts

Most operating systems provide certain basic concepts and abstractions such as processes, address spaces, and files that are central to understanding them.

Processes

A key concept in all operating systems is the process. A process is basically a program in execution. Associated with each process is its address space, a list of memory locations from 0 to some maximum, which the process can read and write. The address space contains the executable program, the program's data, and its stack. Also associated with each process is a set of resources, commonly including registers, a list of open files, outstanding alarms, lists of related processes, and all the other information needed to run the program. A process is fundamentally a container that holds all the information needed to run a program.

When a process is suspended temporarily, it must later be restarted in exactly the same state it had when it was stopped. This means that all information about the process must be explicitly saved somewhere during the suspension.

When a process is temporarily suspended, all these pointers must be saved so that a read call executed after the process is restarted will read the proper data. In many operating systems, all the information about each process is stored in an operating system table called the process table, which is an array of structures, one for each process currently in existence.

Thus, a process consists of its address space, usually called the core image, and its process table entry, which contains the contents of its registers and many other items needed to restart the process later.

The key process-management system calls are those dealing with the creation and termination of processes.

If a process can create one or more other processes(referred to as child processes) and these processes in turn can create child processes. Related processes that are cooperating to get some job done often need to communicate with one another and synchronize their activities. This communication is called interprocess communication.

Other process system calls are available to request more memory, wait for a child process to terminate, and overlay its program with a different one.

When the specified number of seconds has elapsed, the operating system sends an alarm signal to the process. The signal causes the process to temporarily suspend whatever it was doing ,save its registers on the stack, and start running a special signal-handling procedure. When the signal handler is done, the running process is restarted in the state it was in just before the signal. Signals are the software analog of hardware interrupts and can be genereated by a variety of causes in addition to timers expiring.

Each person authorized to use a system is assigned a UID by the system administrator. Every process started has the UID of the person who started. A child process has the same UID as its parent. Users can be members of groups, each of which has a GID(Group IDentification).

Address Spaces

Every computer has some main memory that it uses to hold executing programs.

Files

Another key concept supported by virtually all operating systems is the file system. To provide a place to keep files, most PC operating systems have the concept of a directory as a way of grouping files together. System calls are then needed to create and remove directories. Calls are also provided to put an existing file in a directory and to remove a file from a directory.

Every file within the directory hierarchy can be specified by giving its path name from the top of the directory hierarchy, the root directory.

Another important concept in UNIX is the special file. Special files are provided in order to make I/O devices look like files. Two kinds of special files exist: block special files and character special files. Block special files are used to model devices that consist of a collection of randomly addressable blocks, such as disks. Character special files are used to model printers, modems, and other devices that accept or output a character stream.

A pipe is a sort of pseudofile that can be used to connect two processes.

Input/Output

Every operating system has an I/O subsystem for managing its I/O devices.

Protection

Files in UNIX are protected by assigning each one a 9-bit binary protection code. The protection code consists of three 3-bit fields, one for the owner, one for other members of the owner's group, and one for everyone else.

The Shell

System Calls