Purposes of an Operating System (OS)

A computer needs a program that starts to run as soon as it is switched on. At that moment there is no operating system (OS) running, because the OS programs are stored on disk. Instead, the computer has a basic input/output system (BIOS) stored in ROM. The BIOS starts a bootstrap program, and it is this bootstrap program that loads the operating system into memory and sets it running.

An operating system can keep more than one program in memory at the same time. Only one program can use the CPU at any moment, but the others are ready to use it when their chance comes. This is called multi-programming, and it happens even for one single user. Some systems are designed to have many users logged in at the same time: this is called a time-sharing system.

Note Exam questions often call this idea multi-tasking: the OS manages the running of many programs so that they appear to run at the same time, by swapping the CPU between them.

The purposes of an operating system can be looked at from two viewpoints:

• The internal viewpoint is about how the OS organises its own activities to make the best use of the resources available. The main resources here are the CPU, the memory and the I/O (input and output) system.
• The external viewpoint is about the facilities the OS gives to the user of the system.

An operating system is structured to give a platform for two things: managing the resources, and providing facilities for users. Its logical structure gives two modes of operation:

• User mode is the mode available to the user or to an application program.
• Kernel mode (it has other names, but this one is used most often) has sole access to part of the memory and to certain system functions that user mode cannot reach.

The parts of the OS that provide the two modes are kept separate. The kernel runs all of the time. The rest of the OS runs in user mode, so each part is only used when it is needed.

One way to organise this is a layered structure, shown below. Application programs or utility programs can make system calls to the kernel. To work properly, each higher layer must be fully served by the layer below it, just as in a network protocol stack.

Each program running on a computer is called a process. The OS manages how processes share the resources of the system.

For example, most software needs to save data to a storage device, such as a hard disk. Imagine three processes running at the same time, all saving data regularly. A process might ask to save data while the storage device is already in use. The operating system manages these requests so that all three processes can save their data.

Managing processing time. When several processes are running, the OS must share out processing time between them. To do this it runs a scheduler, which swaps between processes as needed. The scheduler follows a scheduling algorithm, which decides:

• how the processing time is divided: for example, the processes may not all get the same amount of processing time
• the order in which processes get processing time: for example, based on how important each running process seems to be, and on how interrupts are handled.

When the OS swaps between processes:

• the process that is running now is paused, its state is saved, and it is moved back into a queue
• the scheduler decides which process should run next.

In a multiprocessor system, the scheduler also shares the processes out between the cores, as well as sharing out processing time between them.

The instructions and data that a process needs must be in main memory. To make sure of this, the OS runs a memory manager program, which:

• keeps track of which parts of memory have been allocated: memory is mapped as addresses, and the memory manager records which addresses are allocated to each process
• decides how much memory to allocate to each process
• decides when a part of memory should be made available to a process.

A key job of the operating system is controlling and using input and output (I/O) devices. The OS manages I/O devices in several ways:

• It records which device needs processor time, so the processor can communicate with each device without any conflicts.
• It sets the priority of processes using the control signals that the I/O device sends and receives.
• If an I/O device makes a more urgent request than the task being executed now, the OS can interrupt the current task and swap to the more important one.

When files and folders are on a secondary storage device that is connected to the computer, the operating system:

• gives access to the data and programs that must be loaded from secondary storage into main memory
• keeps track of where programs and files are stored
• carries out backups
• supports a user-friendly interface by providing a file management system, which lets the user create, edit and delete files and folders on secondary storage devices.

Managing the CPU as a resource is mainly about scheduling, so that the CPU is used efficiently. These notes treat the CPU as a single unit; the extra issues of a multiprocessor system are not covered.

Programs that can be run are stored on disk at first. A user could submit a program as a job, which holds the program and some instructions about how it should be run. The figure shows the parts involved when a program is run.

• A long-term or high-level scheduler chooses which program stored on disk is moved into main memory.
• Sometimes a program has to be moved back to disk because memory is getting overcrowded. This is controlled by the medium-term scheduler.
• Once the program is in memory, a short-term or low-level scheduler controls when it gets the CPU.

A process control block (PCB) is a data structure that holds all the data a process needs in order to run. It can be created in memory when data needs to be received while the process is running. The PCB stores:

• the current process state (ready, running or blocked)
• the process privileges (for example, which resources it is allowed to use)
• the register values (PC, MAR, MDR and ACC)
• the process priority and any other scheduling information
• the amount of CPU time the process will need to complete
• a process ID, which lets the process be uniquely identified.

A process state is one of three possible conditions of a process:

1. running: the program is running on a CPU
2. ready: the program is waiting for CPU time
3. blocked: the program is waiting for an event or for I/O.

Note The diagram has no arrow from blocked to running: a blocked process must go back to the READY queue first and wait to be chosen by the scheduler.

Some interrupts are caused by errors that end a running process early. Apart from these, there are two reasons for interrupts:

• A process has periods of using the CPU and periods of using I/O, one after the other. I/O takes far too long for the CPU to sit idle waiting for it. So when a running process makes a system call that needs an I/O operation, an interrupt is used and the process moves to the blocked state.
• The scheduler decides to stop the process, for one of the reasons given in the scheduling algorithms below.

Whatever the reason for an interrupt, the OS kernel must call an interrupt-handling routine. This may have to decide the priority of the interrupt. One thing it must always do is save the current values in the registers into the process control block. This lets the process carry on from where it stopped when it returns to the running state.

To switch between tasks, the OS must control the suspension of the process that is running now, and then control the continuation of another process. The running process is not stopped for good: it is suspended and saved into memory. When the processor is ready to serve it again, the state it was suspended in is reloaded and the process carries on running.

The OS may do this many times over, for a great many tasks. The scheduling algorithm decides the order in which the OS executes the processes. The four scheduling algorithms (also called scheduling routines) below are the ones you need: round robin, first come first served, shortest job first and shortest remaining time first.

In round robin scheduling, processor time is divided equally between all the running tasks. Each period of time is called a time slice. Each process gets a time slice. If the process has not finished when its time is up, it stops running and the computer switches to the next process. A suspended process can only carry on when it is next given processor time.

Round robin is like sharing sweets with friends: you give each person one sweet in turn, until everyone has the number of sweets they want.

In first come, first served scheduling, processes run from start to finish in the order in which the processor receives their requests to run. It is like the queue at a supermarket till: customers are served in the order in which they arrive at the till.

Starvation is when a process cannot complete its execution because it is constantly denied processor time.

In shortest job first scheduling, the processes are queued and the process that needs the shortest total time to complete goes first. It is like a supermarket queue in which the person with the fewest items in their basket is allowed to pay first.

In shortest remaining time first scheduling (also called shortest time remaining), the process with the shortest time left to completion goes first, until a new task is added that has a shorter time to completion. The new task then takes priority.

This is different from shortest job first, because it looks at the time left, not the total time. A long job that is nearly complete may have a very short time remaining, so it would be given priority.

Memory management covers several jobs:

• Providing protected memory space for the OS kernel.
• Loading a program into memory, which means setting the memory addresses for the program itself, for the procedures it uses and for the data it needs.
• In a multiprogramming system this may not be simple. The processes stored in main memory can become fragmented, in the same way as files stored on a hard disk. The medium-term scheduler may need to move a process out of main memory to ease the problem.
• Deciding how large a part of memory to give to each of the processes that share memory.

An early way of managing memory, when several processes were loaded into memory at the same time, was to partition the memory. The aim was to load the whole of a process into one partition. This wasted memory when the process was smaller than the partition. An improvement was dynamic partitioning, where the partition size could change to match the process size. The rule of one process per partition stayed.

An extension of this idea, which let larger processes be handled, was segmentation. A large process is divided into segments, and each segment is loaded into a dynamic partition in memory. A segment table records, for each segment number, the base address where the segment starts in memory and its size (limit).

Two things limited how efficient this was:

1. The segments did not have to be the same size.
2. A process could be too big for all of its segments to be in memory at the same time. Segments had to be moved from disk to memory, and then back to disk when a different segment was needed in memory.

Together, these caused fragmentation of both the memory and the disk storage, which made the system perform worse.

The modern approach is paging. The process is divided into equal-sized pages, and memory is divided into page frames of the same size. Secondary storage can also be divided into frames.

It might be possible to load all the pages into memory at the same time. But even then, not all parts of the program are usually needed at the same time: a large program is likely to have optional routes through its execution.

A special case is a program so large that the address space it needs is bigger than the memory. Paging then supports virtual memory management: secondary storage is used as if it were extra main memory, and only the pages that are needed are loaded into memory.

Paging needs the CPU to pass address values to a memory management unit (MMU), which gives the matching address on a page. An address is made of two parts: the page number and the offset from the start of the page. The memory management unit works by using a page table.

Here is a very simple system that shows how this works. A program has 48 instructions, which fill three pages and so take up the first 48 logical addresses. Only 8 bits are used for a logical address: the four most significant bits store the page number and the four least significant bits store the offset. So there can only be 16 pages, each holding 16 addresses.

The first two pages of the program have been loaded into page frames in physical memory. The page frames used do not have to be next to each other:

The page table for this process is shown below (every process in memory has its own page table). The page number works as the index. The presence flag shows whether or not the page is in memory, and the third column gives the page frame number. Instead, it could have recorded the physical address of the first item in the page frame.

When paging is used, all the pages of a process start off stored on disk. One or more of them is loaded into memory as the process moves to the ready state. When the process is dispatched to the running state, it starts executing. At some point the process will need a page that the page table shows is not in memory. This is called a page fault.

To bring the needed page in from secondary storage, a page almost always has to be taken out of memory first. This is when a page replacement algorithm is needed. There are several options:

• A simple algorithm uses first in, first out: the page that has been in memory longest is removed.
• A more sensible method removes the least recently used page, but this needs statistics about page use to be recorded.

The extra work the system does to run virtual memory can be a disadvantage. The worst problem is disk thrashing: part of a process on one page needs another page that is on disk. When that page is loaded, it almost immediately needs the original page again.

This can lead to almost never-ending loading and unloading of pages. Algorithms have been developed to guard against this, but the problem can still happen.

The table compares paging with segmentation, point by point.

Users and programmers never have to deal with the hardware directly. The operating system does that work for them and gives them a simpler way to use the computer:

• User interface: a graphical user interface (GUI) lets the user click icons, menus and windows instead of typing instructions. A command line interface gives expert users short typed commands. Either way, the user does not need to know how the hardware carries out the task.
• Device drivers: each device has a driver that turns general instructions from the OS into the exact signals that device needs. A program just asks for a page to be printed; it does not need to know which printer is attached.
• File management: the user sees named files and folders. The OS works out where the data is actually stored on the disk.
• System calls: programmers use ready-made OS routines, for example to open a file or read a key press, instead of writing code to control the hardware themselves.

The OS tries to keep every part of the computer busy, so that more work gets done in the same time:

• Multiprogramming: several programs are kept in memory at once. When one process has to wait, for example for input or for a file to load, the scheduler gives the CPU to another process instead of leaving it idle.
• Direct memory access (DMA): a DMA controller moves data between a device and main memory without using the CPU. The CPU carries on with other work and gets an interrupt when the transfer is finished.
• Memory management: paging and virtual memory let more processes run at the same time than main memory could hold on its own, because only the pages in use need to be in RAM. Memory is given back as soon as a process ends.