System Software (A Level)

This chapter develops chapter 5 for Paper 3. You need to explain how an operating system manages processes and memory, how a program is turned into machine code, and how the rules of a language can be written down precisely.

16.1 Purposes of an operating system (OS)

Maximising the use of resources

The processor, memory and input/output devices are very different in speed. The OS keeps them busy and shares them between users and programs:

• Multitasking: several programs are in memory and the processor is switched between them very quickly, so they appear to run at the same time. While one program waits for input or a slow device, the processor runs another, which stops the processor being idle.
• Memory is shared out and virtual memory allows programs bigger than the physical RAM to run.
• Input/output is managed with buffers, spooling (for example queuing print jobs on disk) and interrupts, so the processor does not have to wait for slow devices.
• Resources are shared fairly and safely between multiple users, with each program kept separate from the others.

The user interface hides the hardware

The OS gives the user a user interface so they do not need to know how the hardware works. A graphical user interface (GUI) uses windows, icons, menus and a pointer: the user clicks "Save" without knowing how the data is written to sectors on the disk. A command line interface (CLI) takes typed commands, which is faster for experts and can be scripted. Other interfaces are touch, voice and gesture. In each, the OS hides the complexity (an example of abstraction): programs use system calls and device drivers to use hardware, and the user need not know the details such as memory addresses, or the exact commands a printer needs.

Process management

A program is a set of instructions; a process is a program in execution, along with its data and the state of its registers.

Process states:

• Running: the process is currently using the processor.
• Ready: the process is waiting for the processor, with everything else it needs.
• Blocked (waiting): the process is waiting for an event, such as input or a disk transfer, and cannot continue even if it is given the processor.

Transitions: ready → running (the scheduler dispatches it); running → ready (its time slice ended, or a higher priority process arrived: it is pre-empted); running → blocked (it needs an I/O operation); blocked → ready (the I/O has finished, signalled by an interrupt).

Tap to enlarge

A process moves between three states: ready, running and blocked; the scheduler dispatches a ready process to running, a running process returns to ready when its time slice ends, moves to blocked when it waits for input or output, and a blocked process returns to ready when the event happens

Close

The OS keeps a process control block (PCB) for each process, which stores its state, the program counter, the contents of the registers, its priority, and the memory and files in use. When the processor is switched from one process to another (a context switch), the OS saves the registers into the PCB of the old process and loads those of the new one, so that the old process can later resume exactly where it stopped.

The scheduler decides which ready process runs next and for how long, with these aims: keep the processor busy, give a fast response to users, be fair to all processes, and make sure every process gets some time (no starvation). Scheduling algorithms:

The kernel and interrupts. The kernel is the core of the OS that always stays in memory. It acts as the interrupt handler: a timer interrupt ends a process's time slice, an I/O interrupt moves a blocked process to ready, and a system call or error interrupt hands control to the kernel. The kernel then uses the scheduler to choose the next process and does the context switch, so interrupt handling is how low-level scheduling is carried out.

Memory management: paging, segmentation and virtual memory

Paging. Main memory is divided into fixed-size blocks called frames, and each program is divided into pages of the same size. Pages can be put into any free frame, so they need not be next to each other in memory. A page table records which frame holds each page. Paging has no external fragmentation, but the last page of a program may not be full (internal fragmentation). Pages have no logical meaning to the programmer.

Tap to enlarge

A program split into four pages, a page table showing page 0 in frame 2, page 1 in frame 5, page 2 on disk and page 3 in frame 0, main memory frames holding those pages, and the swap file on disk holding page 2, which is loaded when a page fault occurs

Close

Segmentation. A program is divided into logical segments of different sizes (the main code, a subroutine, the data, the stack). A segment table holds the start address and the length of each segment. Segments match the way the program is organised, so they can be shared and protected individually, but variable sizes lead to external fragmentation as memory becomes full of small gaps.

Virtual memory. If there is not enough RAM, the OS uses part of the secondary storage (the hard disk or SSD) as an extension of main memory. Only the pages currently needed are kept in RAM; the others are held in a swap file on disk. When the processor needs a page that is not in memory, a page fault occurs: the OS loads that page from disk, and if RAM is full, replaces another page (using a page replacement algorithm such as least recently used), writing it back first if it has changed.

Replacing pages. When RAM is full and a new page must be loaded, the OS chooses a page to remove (and writes it back to disk first if it has changed). Algorithms include first in first out (remove the page that has been in memory longest), least recently used (remove the page not used for the longest time, which usually performs better) and the optimal algorithm (remove the page that will not be needed for the longest time, which cannot be known in advance, so it is used only as a measure).

Benefits: programs can be larger than the RAM, more programs can run at the same time, and each has its own address space. Drawback: disk is far slower than RAM, so too many page swaps cause disk thrashing, in which the computer spends most of its time moving pages between disk and memory and does little useful work. Adding more RAM reduces it.

16.2 Translation software

Interpreters

An interpreter carries out a program by analysing and executing one statement at a time, without producing a translated version (object code) of the program. For each statement it: reads the statement, checks the syntax, works out what it means, and executes it immediately by calling a routine of its own that does that operation. The source code is needed every time the program runs, and if a statement is inside a loop it is translated again each time, so the execution is slow. An interpreter reports an error as soon as it reaches the faulty statement.

Stages of compilation

A compiler translates a whole program in stages:

1. Lexical analysis: the source code is read and split into tokens (keywords, identifiers, operators, numbers, punctuation). Comments and spaces are removed, and identifiers are entered in a symbol table with details such as their type. Errors such as an illegal character are found here.
2. Syntax analysis (parsing): the tokens are checked against the grammar of the language, building a parse tree. Syntax errors (a missing bracket, a misspelt keyword) are reported here.
3. Semantic analysis: checks that the statements make sense: that variables have been declared, that the types match, and so on.
4. Code generation: the tree is converted into object code (machine code or intermediate code), with the addresses taken from the symbol table.
5. Code optimisation: the code is improved to run faster or use less memory, for example by removing code that is never used, avoiding repeated calculations, and replacing a calculation that uses constants by its result (constant folding).

Tap to enlarge

The stages of compiling the line total = price * 2: lexical analysis splits it into tokens, syntax analysis builds a parse tree, code generation produces object code and optimisation improves it, with a symbol table built at the first stage

Close

Backus-Naur Form (BNF) and syntax diagrams

The grammar of a language must be defined precisely, so that every compiler agrees on what is allowed. Two notations describe it.

BNF uses rules. Each rule has a non-terminal (in angle brackets) defined by ::= ("is defined as") in terms of other non-terminals and terminals (the actual symbols). The symbol | means or. A rule can refer to itself (recursion) to allow repetition.

<digit>    ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer>  ::= <digit> | <integer><digit>
<sign>     ::= + | -
<number>   ::= <integer> | <sign><integer>

Here an <integer> is either a single digit or an integer followed by a digit, so 407 is valid: 4, then 40, then 407. To check whether a string follows the grammar, break it down using the rules.

A syntax diagram shows the same rules as a diagram, with rounded boxes for terminals, rectangles for non-terminals, and arrows to show the paths; a loop back shows repetition. It is easier to read, but BNF is easier to write and to process by program.

Reverse Polish Notation (RPN)

Reverse Polish Notation is a way of writing expressions with the operator after its operands (postfix), instead of between them (infix). It needs no brackets and no rules about precedence.

Evaluating RPN with a stack: read the expression from left to right. If the item is an operand, push it on the stack. If it is an operator, pop the top two items (the first popped is the second operand), apply the operator, and push the result. At the end the answer is the only item left.

Evaluate 6 2 3 + * : push 6; push 2; push 3; + pops 3 and 2 and pushes 5; * pops 5 and 6 and pushes 30. The result is 30.

Compilers convert infix expressions to RPN because it is easy to evaluate with a stack and needs no precedence rules at run time; some calculators and stack-based processors use it directly.