Purposes of an operating system and translation software

What an operating system is for

An operating system (OS) is system software that sits between the hardware and the programs the user runs. Nothing else can touch the hardware directly: a word processor does not know which disk controller your machine has or which memory addresses are free, and it does not need to, because the OS provides the services it asks for. The OS is loaded by the boot program when the machine is switched on and stays in memory while the machine is running.

The first purpose in the syllabus is that the OS maximises the use of resources. The resources are the processor, main memory, backing store and the input/output devices, and they are all slower to share out than they look. The processor is thousands of times faster than a disk, so if the OS let one program wait for a disk read, the processor would stand idle for the whole wait. The OS avoids that by keeping several processes in memory, giving the processor to another one whenever the current one has to wait, and using interrupts to be told the instant a device has finished instead of repeatedly asking it. It also buffers and spools data, so a slow printer receives a job at its own speed from a queue while the processor carries on. Add memory management, which keeps each process in its own area, and file management, which tracks where every block of every file is stored, and the picture is complete: the OS is what turns a set of separate components into a machine that is busy nearly all of the time.

The second purpose is that the OS provides a user interface that hides the complexity of the hardware. You click an icon and a document opens; you never think about tracks, sectors, cylinder numbers, device registers, interrupt lines or memory addresses. The interface may be a graphical user interface (GUI) with windows, icons, menus and a pointer, or a command line interface where you type a command such as `copy report.txt backup`, or both. Whichever it is, the same hiding is going on: a single instruction from the user is translated by the OS into hundreds of low-level operations, and the hardware is presented as a small set of simple, familiar objects - files, folders, printers, windows - rather than as electrical components.

The hiding runs in several directions at once. Device drivers give every printer, graphics card and network adapter the same set of commands, so a program does not have to be rewritten for each make of hardware. The file system gives the user named files in named folders instead of numbered blocks scattered across a disk. Memory management gives each program a clean block of addresses starting from zero, so the programmer never handles a real physical address and two programs cannot overwrite each other. And error handling means a disk failure appears as a message box, not as a crash: the OS detects the problem, tries to recover, and reports it in terms the user can act on.

• Resource management: the OS allocates processor time, memory, backing store and I/O devices to processes, and stops them interfering with one another.
• Maximising use: multi-tasking keeps the processor busy while a process waits for I/O; interrupts report device completion immediately; buffering and spooling let slow peripherals work in parallel with the processor.
• Hiding complexity: the user issues one high-level command (print, save, open) and the OS carries out the low-level device and memory operations needed to satisfy it.
• Uniform interface to hardware: device drivers present different makes of device in the same way, so application software is not tied to particular hardware.
• File system: named files and folders instead of physical disk addresses, with the OS keeping the mapping and the free-space list.
• Memory protection: each process is given its own address space, so a fault in one program cannot corrupt another or the OS itself.

Processes, the process control block and the three process states

A program is a passive list of instructions stored on disk. A process is that program in execution: it has instructions being carried out, values in registers, a program counter, memory allocated to it and files or devices open. The same program can be run twice and produce two separate processes, each with its own state. Multi-tasking (multiprogramming) is the technique of holding several processes in memory and switching the processor between them so quickly that they appear to run at the same time; on a single-core processor only one instruction is genuinely being executed at any instant, and the switching is what creates the illusion.

To switch between processes the OS must be able to stop one and later resume it exactly where it left off. It does this with a process control block (PCB) for every process, a record held by the OS containing the process identifier, the process state, the program counter and saved register values, the scheduling priority, the memory allocated (page table or segment table), the files and I/O devices in use, and accounting information such as CPU time used. When a process is taken off the processor, its current register values and program counter are saved into its PCB; when it is put back, they are restored. This save-and-restore is a context switch, and it costs time, because no useful work is done by the process during it.

The syllabus names three process states, and exam questions nearly always turn on the transitions between them. Running means the process currently has the processor and its instructions are being executed. Ready means the process could run immediately if it were given the processor, but another process has it. Blocked (waiting) means the process cannot continue at all until some event happens, usually the completion of an input/output operation it has requested, or a signal from another process.

The transitions are worth learning as a diagram in your head. A process moves from ready to running when the scheduler chooses it; from running to ready when its time slice runs out or a higher-priority process becomes ready (it is pre-empted); from running to blocked when it requests a file, a keystroke or a print and must wait; from blocked to ready when the interrupt arrives saying the I/O is complete; and out of running altogether when it finishes or is terminated. Notice that a blocked process cannot become running directly - it has to go back through ready and wait its turn, because the OS cannot know how long it will take to be scheduled.

Scheduling and the four scheduling routines

Scheduling is the OS deciding which of the ready processes gets the processor next and for how long. It is needed because there is one processor and many processes, because processes arrive at unpredictable times, and because some are far more urgent than others. A scheduler is judged on throughput (how many processes are completed per unit time), CPU utilisation (how little time the processor spends idle), turnaround time (how long a process takes from arrival to completion), waiting time and response time (how quickly an interactive user sees something happen). It must also be fair, so that no process is left in the queue indefinitely - a condition called starvation.

First come, first served (FCFS) is the simplest: processes are served in the order they arrive, like a queue at a till, and each runs to completion or until it blocks. It is easy to implement and cannot starve anyone, but it is poor for interactive use, because a single long process at the front holds everyone up. This is the convoy effect: a queue of short jobs stuck behind one long one, giving a very long average waiting time.

Shortest job first (SJF) always picks the ready process with the smallest expected total processor time. If the times are known, it gives the lowest possible average waiting time, which is why it is the benchmark against which others are measured. In practice the times are not known and have to be estimated from past behaviour, long jobs can be starved if short ones keep arriving, and it is not usable in an interactive system where you cannot know how long the user's next command will take. Shortest remaining time (SRT) is SJF made pre-emptive: whenever a new process arrives, the scheduler compares its expected time with the remaining time of the running process and switches if the newcomer is shorter. It gives even better average turnaround and responds quickly to short jobs, but it needs a running estimate of remaining time and it causes more context switches.

Round robin (RR) gives each process a fixed time slice (quantum) in turn, cycling through the ready queue; when the slice expires a timer interrupt returns control to the OS and the process goes to the back of the queue. It is pre-emptive, it is fair, no process can starve, and response time is good, which is why it is the standard choice for time-shared and interactive systems. The size of the slice is the whole design decision: too small and the processor spends a large fraction of its time on context switches; too large and round robin behaves like FCFS, with long waits for the processes at the back.

Paging, virtual memory and disk thrashing

Paging divides the virtual (logical) address space of a process into pages of a fixed size, typically 4 KiB, and divides physical memory into frames of exactly the same size. Any page can be loaded into any free frame, so memory does not have to be contiguous: the program is scattered around memory and a page table for each process maps each page number to the frame number where it currently sits along with a present/absent bit. Because every page is the same size, there are no awkward gaps between loaded pieces - no external fragmentation - though the last page of a program is usually only partly used, which wastes a little space inside that frame (internal fragmentation).

Virtual memory uses backing store as an extension of main memory. Only the pages a process is actually using are held in memory; the rest stay in a page file (swap file) on disk. The processor generates virtual addresses that are translated through the page table into physical addresses, so a program can be written as though it had far more memory than the machine really has, and more processes can be resident at once because each one occupies only a few of its pages.

The mechanism only works because of the page fault. When a process refers to a page whose present bit is clear, the processor traps to the OS, which finds a free frame, reads the page in from disk, updates the page table and restarts the instruction. The process is blocked while the transfer happens, because a disk read takes milliseconds while the processor works in nanoseconds. If there is no free frame, a resident page must be evicted to make room; if that page has been changed (it is dirty) it must first be written back to disk. The rule for choosing the victim is the page replacement algorithm: first in, first out (evict the oldest page, simple but can evict a heavily used page), least recently used (evict the page not used for the longest time, better because it follows the pattern of use), and optimal (evict the page that will not be needed for the longest time - the best possible, but it needs knowledge of the future, so it is only a theoretical comparison).

The benefit of all this is that programs can be larger than physical memory, more programs can run at once, and less memory is wasted. The cost is speed: a page fault means a disk access, which is thousands of times slower than a memory access. Disk thrashing is what happens when the system spends almost all of its time moving pages between memory and disk and almost none of it executing instructions. It is caused by there being too little physical memory for the number of processes running, or by running too many processes at once, so that every process is constantly faulting on pages that another process has just evicted. The symptoms are continuous disk activity, a queue of processes all in the blocked state waiting for pages, and low processor utilisation - which is the trap, because a naive OS responds to low utilisation by admitting yet another process, making the thrashing worse. The cures are to reduce the number of processes running, add more memory, use a better replacement algorithm, or give each process a working set of pages large enough that it does not keep faulting.

• Page: a fixed-size block of a program's virtual address space. Frame: a fixed-size block of physical memory, the same size as a page.
• Page table: one per process, mapping page number to frame number and recording whether the page is currently in memory.
• Page fault: the trap raised when a referenced page is not in memory; the OS loads it from disk, possibly evicting another page, and the process is blocked meanwhile.
• Replacement algorithms: FIFO, least recently used, and optimal (theoretical) decide which page to evict when memory is full.
• Benefits of virtual memory: programs larger than RAM can run, more processes fit in memory, and physical memory is used more fully.
• Costs: a page fault is a disk access and is far slower than memory; heavy faulting reduces performance and wears the disk.
• Thrashing: continuous paging, so the system spends nearly all its time swapping rather than executing. Cause: too little memory for the number of processes. Symptoms: high disk activity and low CPU utilisation.

Segmentation and how it differs from paging

Segmentation divides a program into segments that are variable in length and chosen to match the logical structure of the program: one segment for the main program, one for each procedure or function, one for global data, one for the stack, one for a shared library. Each segment has a number and a length, and the segment table stores the base address of each segment in memory together with its limit, so that every address is checked against the limit and an attempt to read past the end of a segment is trapped. Because the divisions follow the program's structure, a segment can be given its own protection (read-only for code, read/write for data) and can be shared between processes - a single copy of a library segment can be mapped into several processes at once.

The cost of variable sizes is external fragmentation. As segments are loaded and removed, memory fills with gaps of various sizes, and a new segment may not fit into any one of them even when the total free space is large enough. The OS then has to compact memory - shuffle the loaded segments together to make one big free block - which costs processor time, or it must refuse the request.

The difference between the two is the classic exam comparison. In paging the divisions are fixed in size and are made by the system, invisible to the programmer; the address is a page number plus an offset, memory suffers internal fragmentation in the partly used final page, and the page table is a simple array. In segmentation the divisions are variable in size and reflect the logical parts of the program, visible to the programmer; the address is a segment number plus an offset that must be checked against the limit, memory suffers external fragmentation that may need compaction, and the segment table must store both a base and a limit for each entry. Paging exists to solve the mechanics of fitting a program into memory; segmentation exists to reflect and protect the structure of the program. Real systems often combine them: a program is divided into segments, and each segment is itself divided into pages, which gives the logical structure of segmentation with the fixed-size convenience of paging for loading.

Interrupts and the kernel as interrupt handler

An interrupt is a signal to the processor that an event needs immediate attention, causing it to suspend what it is doing and transfer control to a handler routine. Interrupts can come from hardware - a keystroke, a printer signalling that it has finished, a disk completing a read, the system timer ticking - or from software: a program making a system call (a trap), a divide-by-zero, or an attempt to access memory that is not there, such as a page fault. Without interrupts the processor would have to keep stopping to check every device (polling), which wastes enormous amounts of time; an interrupt lets the processor work at full speed until a device actually needs it.

The kernel is the core of the operating system: the part that stays in memory all the time, runs in privileged mode and has direct access to the hardware. It is the kernel that acts as the interrupt handler. When an interrupt arrives, the processor finishes the instruction it is executing, saves the current state - the program counter and register contents - into the PCB of the running process, and jumps to the handler whose address it finds in the interrupt vector table. The handler identifies the source, performs the small amount of work needed (for example copying the arriving data out of the device's buffer, or updating the page table after a page fault), records that the event has happened, and then the scheduler decides what runs next. The saved state is restored and the interrupted process continues, apparently unaware that anything happened.

Two refinements matter. Interrupts have priorities, so that a power failure or a disk error is dealt with before a keystroke, and a higher-priority interrupt can itself interrupt a lower-priority handler. Interrupts can also be temporarily disabled (masked) while the kernel is in a critical section, so that a data structure cannot be changed half-way through; the interrupt is not lost, only held until the section ends.

This is how interrupt handling manages low-level scheduling. The timer interrupt is the mechanism that makes pre-emptive scheduling possible: it fires at the end of each process's time slice, hands control back to the kernel, and the kernel saves the running process, moves it to the ready queue and dispatches the next one. An I/O completion interrupt is what moves a process from blocked to ready - the disk finishes reading, the handler updates the PCB, and the process is now eligible to run again. Every context switch in a multi-tasking system therefore depends on an interrupt, which is why interrupt handling is described as the low-level half of scheduling: the scheduler decides policy, the interrupt mechanism supplies the opportunities.

• Interrupt: a signal that causes the processor to suspend the current process and run a handler.
• Sources: hardware (timer, keyboard, disk completion, printer) and software (system call, error, page fault).
• Sequence: finish the current instruction, save the state in the PCB, look up the handler through the interrupt vector table, run the handler, restore the state, resume.
• The kernel is the resident, privileged core of the OS and the part that handles interrupts.
• Priorities let urgent interrupts pre-empt less urgent ones; interrupts can be masked during critical sections.
• Low-level scheduling: the timer interrupt ends a time slice and forces a context switch, and I/O completion interrupts return blocked processes to the ready state.

Compilers and interpreters

Source code written in a high-level language has to be translated before the processor can execute it, and there are two ways of doing it. A compiler translates the whole program in one go, before it is run, and produces an object code file that is combined with libraries to make an executable. Once compiled, the program can be run any number of times without the compiler or the source code being present, and it runs at the speed of machine code. Compilation is a separate step that takes time, and the compiler reports errors only after it has examined the whole program, in a list, which is harder for a beginner because the first error may have been caused by something earlier.

An interpreter does not produce a translated version of the program. It takes the source code, translates one statement, executes it, then translates and executes the next, and so on until the program ends or an error is found. Nothing is saved, so the next run starts the translation all over again. This makes an interpreter slow to run, because translation happens every time, and the source code must be available every time. In exchange it is excellent for learning and for development: the program starts immediately without a compile step, and it stops at the first error it reaches, pointing at the exact statement, so bugs are found one at a time and fixed quickly. It is also easy to run the same source on any machine that has an interpreter.

The two are often combined. Many modern languages are translated to an intermediate bytecode which is then executed by a virtual machine: the source is compiled once into bytecode, and the bytecode is interpreted (or compiled further) at run time. Python is the standard example - the standard implementation compiles the source to bytecode and then interprets it - and Java compiles to bytecode that runs on the Java Virtual Machine. This gives some of the speed and error-checking of compilation with some of the portability of interpretation.

The stages of compilation

A compiler does not translate in one leap. It works through a pipeline of stages, and each stage takes the output of the previous one and produces something more machine-like. The syllabus names four: lexical analysis, syntax analysis, code generation and optimisation.

Lexical analysis (tokenising) reads the source as a stream of characters and groups them into tokens: keywords, identifiers, constants, operators and punctuation. It discards whitespace and comments, since they mean nothing to the compiler, and it builds the symbol table, the list of every identifier used with its type, scope and location, which later stages keep updating and the final code generation uses to attach addresses. A character that cannot begin any token - an illegal symbol, or an unterminated string - produces an error at this stage.

Syntax analysis (parsing) checks that the sequence of tokens obeys the grammar of the language, using rules that can be written as BNF or drawn as syntax diagrams. It builds a parse tree (or abstract syntax tree) showing how the tokens combine into statements and expressions, and it reports syntax errors such as a missing bracket or a missing `then`. It is important to be clear about the difference: lexical analysis would accept `total = 4` token by token, because each token is legal; only syntax analysis can object that `` cannot follow `=`.

Code generation turns the parse tree into object code - machine code for the target processor, or an intermediate code - allocating registers and memory addresses, choosing instructions for each operation, and resolving identifiers using the symbol table. Optimisation then improves that code without changing what it does: removing code that can never be reached, removing repeated calculations that can be done once, folding constants (`2 * 3` becomes `6`), and keeping frequently used variables in registers instead of memory. Optimisation can be done on the intermediate code before machine code is produced, which is why it is often described as sitting between syntax analysis and final code generation. The result is an object file, which the linker joins with library routines to make the executable.

BNF, syntax diagrams and Reverse Polish Notation

The grammar of a language can be written formally, and the syllabus requires two notations for it. Backus-Naur Form (BNF) is a set of rules in which a non-terminal symbol (written in angle brackets) is defined in terms of other symbols, with `::=` meaning 'is defined as' and `|` meaning 'or'. Terminals - the actual characters or keywords of the language - appear literally or in quotes. A rule can be recursive, defining a symbol partly in terms of itself, which is how repetition is expressed. For example: <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <integer> ::= <digit> | <digit><integer> <identifier> ::= <letter> | <identifier><letter> | <identifier><digit> Read the second line as: an integer is either a single digit, or a digit followed by an integer - which is exactly 'one or more digits'.

A syntax diagram is the graphical equivalent: terminals are drawn in circles, non-terminals in rounded rectangles, and the arrows show the paths that are allowed through the rule. A path that loops back expresses repetition, and a fork expresses a choice, so a syntax diagram and a set of BNF rules can always be converted into one another. Both are used to check whether a string is valid in the language, and both are used by the syntax analyser as the specification of the grammar it must enforce.

Reverse Polish Notation (RPN), or postfix notation, is a way of writing arithmetic in which the operator comes after its two operands: `3 4 +` instead of `3 + 4`. Because every operator knows exactly where its operands are, brackets are never needed and there is no ambiguity about precedence. RPN is evaluated with a stack: read the expression left to right, push each number as it arrives, and when an operator arrives pop the top two values, apply the operator to them (the second popped is the left operand) and push the result. At the end, the single value left on the stack is the answer.

Work through `(3 + 4) 5`, which in RPN is `3 4 + 5 `. Push 3, push 4; `+` pops 4 and 3, adds them and pushes 7; push 5; `` pops 5 and 7 and pushes 35. The answer is 35. Converting from infix needs the precedence rules: deal with the bracketed expression first, so inside the bracket `3 + 4` becomes `3 4 +`, then the multiplication needs its left operand (the result of the bracket) and its right operand `5`, giving `3 4 + 5 `. Getting the operand order right matters for subtraction and division: `8 3 -` is 8 - 3 = 5, not 3 - 8.