Operating system

Definition

The operating system (OS) is specialized computer software that allocates memory and manages system resources. When a computer is turned on, the OS is loaded into memory and works as an abstraction layer between the physical hardware and the software. While the Operating system doesn't perform a specific function it helps other programs run smoothly and effeciently.

History

To understand why Operating systems not only exist today but why they take the forms they do one has to have an understanding of the development of computers. The first computers were only designed to do a specific task. From calculators came computers or machines that could do a series of operations in a specific order but it was a single chain of events and once the program had ended the computer shut off. Soon it was found that it was very useful to not only have a computer that looped indefinitely to monitor certain activities, it was useful to run multiple programs at once. It was decided that a mediator was needed to run all these tasks to make sure everything ran smoothly and so the operating system was born.

Job of an Operating System

Coordination

The goal of an operating system (OS) is to allow multiple applications and users to work together in fair and efficient ways.

• security - prevent jobs from interfering with one another
• communication - let jobs talk to one another
• resource management - give jobs fair share of resources

Abstraction / Standard Services

An operating system provides a set of standard services (or API) for applications to use the various system resources. Instead of forcing every application programmer to know how to write a complicated device driver just to read the CD-ROM, for instance, a modern-day operating system will simply provide a routine to access the device. This not only simplifies the job of an application programmer, but also provides the ability to manage system resources effectively and protects against malicious behavior. We will explore the trade-offs that decisions about operating system designs involve when we introduce the concept of a kernel.

Operating System Principles

• OS as illusionist

Make hardware limitations disappear. An operating system provides an application with the illusion of an infinite amount of memory and an infinite amount of processors.

• OS as government

Protect users from each other and allocate resources fairly and efficiently.

• OS as complex system

Keep things simple is the key to functionality.

• OS as history teacher

Learn from the past to predict the future. As the technology progresses, design principles change.

Operating Systems Structure

Hardware Abstraction Layer

A hardware abstraction layer (HAL) is a layer between the physical hardware of a computer and the software that runs on that computer. The function is to hide differences in hardware and therefore provide a consistent platform to run applications on.

The best example of an HAL can be found in the AS/400 architecture. The implementation of the LIC, or Licensed Internal Code, was so successful that software written on the predecessor, the S/38, runs without modifications on an AS/400. That, regardless of the underlying hardware having been changed dramatically; at least 3 different types of processors have been in use.

Windows NT implements a unique HAL technology that is extremely fast and makes Windows NT far more portable than most other OS technologies. Windows NT's HAL technology resides between the hardware and the base NT kernel. Windows NT is designed and optimized towards a specific architecture platform coded in portable C that is completely agnostic to the underlying hardware architecture.

Since the HAL only has to provide the differences between the Windows NT's targeted architecture platform and the actual hardware architecture it only has to translate a few operations. This approach allows Windows NT to be very fast as the HAL is under 300KB, needing to only translate the actual differences of what Windows NT expects and what the hardware provides. Because Windows NT portable C code is also compiled to native machine code for the actual hardware architecture it permits Windows NT to run as fast as the hardware architecture allows.

The specific design of the HAL in Windows NT is how Microsoft can quickly recompile and target several architectures, as they did with NT 4.0 and are once again able to easily adapt Windows 8 for ARM and several other architectures.

Windows CE borrows from Windows NT's HAL technology with an OEM Abstraction Layer (OAL), which has allowed Microsoft to easily deploy Windows CE on over a 1,000 different hardware architectures, and still compile to native machine code for each different architecture. This makes Windows CE one of the most ported OSes in history, and extremely fast even on low end hardware.

OS X, DOS, CP/M, Solaris, BSD and Linux based OS technologies use HAL technologies but are not necessary and are not inherently designed into the OS technology. These type of HAL implementations often provide very specific direct hardware access to devices that allow drivers and applications to bypass the kernel when working with the hardware. More commonly a HAL is used to provide generic drivers, especially on kernel models that require drivers to be compiled into the kernel or compiled directly to the specific device on the architecture. So a HAL is used to provide a generic interface for essential boot devices, like IDE, SCSI, PCI, ISA, etc. allowing the generic compiled driver/kernel to talk to the HAL which implements the device specific calls the devices need. This is a clever way to get generic drivers to work without needing the specific device driver to be compiled for the specific architecture.

Operating systems having a defined HAL are easily portable across different hardware. This is especially important for embedded systems that run on dozens of different microcontrollers.

Virtual Machines

For multi-platform operating systems, trying to generalize core components tends to make things very complex. A new philosophy emerging is to use a hypervisor (like Xen) to create a common machine interface which can then be extended to any architecture.

The Kernel

The fundamental program that is the basis of an operating system is typically referred to as a kernel. An operating system kernel is not strictly needed to run a computer. Programs can be directly loaded and executed on the "bare metal" machine, provided that the authors of those programs are willing to do without any hardware abstraction or operating system support. This was the normal operating method of many early computers, which were reset and reloaded between the running of different programs. Eventually, small ancillary programs such as program loaders and debuggers were typically left in-core between runs, or loaded from read-only memory. As these were developed, they formed the basis of what became early operating system kernels.

Graphical overview of a microkernel

Graphical overview of a monolithic kernel

There are four broad categories of kernels :

• Monolithic kernels provide rich and powerful abstractions of the underlying hardware.
• Microkernels provide a small set of simple hardware abstractions and use applications called servers to provide more functionality.
• Hybrid (modified microkernels) are very much like pure microkernels, except that they include some additional code in kernelspace so that it runs more quickly.
• Exokernels provide no abstractions but allow the use of libraries to provide more functionality via direct or nearly direct access to hardware.

Tradeoffs (micro vs macro)

• simplicity vs complexity
• more overhead vs less overhead

Processes

A computer process is a running instance of a program, including all variables and other states. The three important components of a process are:

• Program Code - Sometimes called the "text" section, this contains the instructions to be performed for the process.
• Program Counter - Maintains the specific instruction in the program code to be executed next (imagine check marks in a checklist).
• Stack Area - Sometimes called the "data" section, this includes all static memory allocated to the process.

A multitasking operating system switches between processes to give the appearance of simultaneous execution, though in fact, in general, only one process can be executing per CPU core. Some new processors, such as Intel's Pentium 4 with Hyperthreading capability, can actually execute more than one process at a time.

Reality vs. Abstraction

• physical memory vs. virtual memory
• no protection vs. protection
• limited size vs. unlimited
• data scattered vs. contiguous virtual address range
• easy sharing vs. controlled sharing

Boot Loader

The function of a boot loader, whether a boot ROM or a Unix boot loader such as uboot or grub, is to initialize the hardware, set boot parameters, load a kernel image into RAM, and pass control of the hardware to the loaded kernel image.

Virtual Memory

Introduction

File:Virtual memory-Virtualmem.png

Virtual memory is intended to help the programmer by taking care of some memory housekeeping duties.

Virtual memory is a computer design feature that permits software to use more main memory (the memory which the CPU can read and write to directly) than the computer actually physically possesses.

Most computers possess four kinds of memory: registers in the CPU, caches both inside and adjacent to the CPU, physical memory, generally in the form of RAM which the CPU can read and write to directly and reasonably quickly; and disk storage, which is much slower, but also much larger. Many applications require access to more information (code as well as data) than can be stored in physical memory. This is especially true when the operating system is one that wishes to allow multiple processes/applications to run seemingly in parallel. The obvious response to the problem of the maximum size of the physical memory being less than that required for all running programs is for the application to keep some of its information on the disk, and move it back and forth to physical memory as needed, but there are a number of ways to do this.

One option is for the application software itself to be responsible both for deciding which information is to be kept where, and also for moving it back and forth. The programmer would do this by determining which sections of the program (and also its data) were mutually exclusive, and then arranging for loading and unloading the appropriate sections from physical memory, as needed. The disadvantage of this approach is that each application's programmer must spend time and effort on designing, implementing, and debugging this mechanism, instead of focusing on their application; this hampered programmers' efficiency. Also, if any programmer could truly choose which of their items of data to store in the physical memory at any one time, they could easily conflict with the decisions made by another programmer, who also wanted to use all the available physical memory at that point.

The alternative is to use virtual memory, in which a combination of special hardware and operating system software makes use of both kinds of memory to make it look as if the computer has a much larger main memory than it actually does. It does this in a way that is invisible to the rest of the software running on the computer. It usually provides the ability to simulate a main memory of almost any size (as limited by the size of the addresses being used by the operating system and cpu; the total size of the Virtual Memory can be 2³² for a 32 bit system, or approximately 4 Gigabytes, while newer 64 bit chips and operating systems use 64 or 48 bit addresses and can index much more virtual memory).

This makes the job of the application programmer much simpler. No matter how much memory the application needs, it can act as if it has access to a main memory of that size. The programmer can also completely ignore the need to manage the moving of data back and forth between the different kinds of memory.

In technical terms, virtual memory allows software to run in a memory address space whose size and addressing are not necessarily tied to the computer's physical memory. While conceivably virtual memory could be implemented solely by operating system software, in practice its implementation almost universally uses a combination of hardware and operating system software.

Multiprogramming

Introduction

Multiprogramming became possible when disks were introduced to the computing world. The concept of multiprogramming relies on the capability of a computer to store instructions (programs) for long-term use. The goal is to reduce CPU idle time by allowing new jobs to take over the CPU whenever the currently running job needed to wait (e.g. for user I/O).

It was also at this point when operating systems received a new responsibility - decision making. Before multiprogramming was introduced, the role of the operating system was simple and straight-forward - load a program into memory and execute it via the CPU.

With the advent of multiprogramming, operating systems now faced different mechanics for program execution as multiple jobs now needed to be loaded into memory at the same time and several options existed for allocating CPU time.

Two types of scheduling were introduced to handle this decision-making - job scheduling and CPU scheduling. Job scheduling refers to the selection of jobs to load into memory. CPU scheduling refers to the selection of a job existing in memory to execute via the CPU. In a computer system, both these decisions are made by the operating system.

Scheduling Algorithms

Scheduling Basics

Process scheduling is one of the most important functions of an operating system that supports multiprogramming. This function is heavily dependent on queues. There are three types of queues that are used in process scheduling:

• Job Queue - Contains all processes that have been introduced into the system
• Ready Queue - Contains processes that are waiting for CPU time, and can be selected to run at any time
• Device Queue - Contains processes waiting on a certain device. Each device has its own queue for processes that need input/output from it.

Scheduling Statistics

To gauge the performance of a scheduling algorithm, several statistics are used.

• Turnaround Time = Time Job Finished - Time Job First Ready
• Average Turnaround Time = Average of Turnaround Time of all jobs
• Throughput = Number of Jobs Finished / Total CPU Time
• CPU Utilization = (Total CPU Time - Idle Time)/Total CPU Time

The general goals of scheduling are:

• Reduce average turnaround time.
• Increase the throughput
• Increase CPU Utilization

First Come First Serve

The name of this algorithm is self-explanatory. This is the simplest (but least efficient) algorithm used to schedule processes for execution.

The first process to arrive in the ready queue will be executed first. Since this is not a preemptive algorithm, an incoming process is not allowed to take over the CPU if the running process is not complete. Thus, the running process will continue until it is completed.

Shortest Job First

In this algorithm, if more than one process is ready to execute, the scheduler selects the process with the shortest "burst time" (time to finish) and assigns it to the CPU. This is also a non-preemptive algorithm, so as soon as a process is assigned to the CPU, it will not be replaced until it is completed.

Shortest Remaining Time First

This is similar to Shortest Job First, but this algorithm is preemptive. If a new process becomes ready, the scheduler will check if its burst time is shorter than the remaining time of the currently running process, then the new process will "preempt" the current process. The current process will be returned to the ready queue.

Threads

The concept of threading was introduced to address the issue of concurrent execution within a single process. Since the overhead for switching between multiple processes was too expensive in terms of computing resources, programmers needed a way to perform concurrent execution without resorting to the use of multiple processes.

A thread is simply a lightweight process. Although each thread executes a separate program code, all threads belonging to the same process share the same memory space and context. This allows more convenient communication and data sharing. More importantly, switching between threads takes much less time compared to the context switch between processes.

Threads come in two types:

1. Kernel Threads - Kernel threads are managed by the kernel itself. It is created in kernel space and the switching between threads is performed by the kernel. Although management is more efficient, the trade-off is the overhead required to create these threads.
2. User Threads - User threads are created as part of a user process. Implementation-wise, the mechanism for creating and managing user threads is found within a programming language's application program interface.

File Systems

Caching

Caching, as a concept, simply refers to the usage of a faster (albeit usually smaller) storage medium to store copied data from a slower medium to allow faster access to data. The trade-off is a decreased reliability of data, although this disadvantage is eliminated when a good caching algorithm is implemented.

Although a hardware cache exists within and parallel to the processor in a computer system, in theory, any storage medium can serve as a cache for a slower storage medium. The hardware cache itself is slower than general purpose registers but faster than main memory. Thus, it serves as a cache for main memory. In cases when larger amounts of data from secondary storage needs to be cached, the main memory can be used.

A new type of caching came into play with the advent of the world wide web. A server PC (e.g. web server, FTP server) could now act as a "virtual" storage medium. In this case, a secondary storage medium, presumably providing faster access compared to TCP/IP, could now serve a cache for data acquired through a network (e.g. HTML and images in the case of a web server).

Consistency and coherency is an important consideration in the design of a cache system. The principle is to maintain consistent data across the storage hierarchy (from registers to network servers) in order to avoid erratic computations. This is a problem commonly noted, although not having a significant effect, in the case of web browsers. Oftentimes, you will need to refresh the page or clear the cache in order to see the most recent images on screen.

Disk Scheduling

File Structure, Disk Scheduling

File: a named collection of bytes stored on disk. From the OS’ standpoint, the file consists of a bunch of blocks stored on the device. Programmer may actually see a different interface (e.g., records), but this doesn’t matter to the file system (just pack bytes into disk blocks, unpack them again on reading). Common addressing patterns: • Sequential: information is processed in order, one piece after the other. This is a common mode: e.g. editor writes out new file, compiler compiles it, etc. • Random Access: can address any block in the file directly without passing through its predecessors. E.g. the data set for demand paging, databases. • Content based: search for blocks with particular values, e.g. hash table, associative database, dictionary. Not provided by all operating system.

References

External References

• Operating System related tutorials.

Popular operating systems include:

• BeOS
• BSD family systems
• b: Mac OS X
• Linux (and b: Linux)
• b: Unix
• b: Windows
• b: Solaris

Other related wikibooks:

• Distributed Operating Systems
• b: A Neutral Look at Operating Systems
• b: Embedded Systems/Real-Time Operating Systems