Everything from the 5 lessons of this topic on a few pages: the key idea of each lesson, the diagram to remember, the points to learn and the traps examiners set. Read it, cover it, test yourself.
A process is a program that has been loaded into memory and is being executed. In multi-tasking the OS switches the processor between processes so quickly that they appear to run at the same time. Each process is running (on the processor), ready (waiting only for the processor) or blocked (waiting for an event such as I/O). The scheduler chooses the next ready process using a routine such as first come first served, shortest job first, shortest remaining time or round robin. The kernel acts as the interrupt handler: timer and I/O interrupts trigger the low-level scheduler to change which process runs.
Fig. 1: the running, ready and blocked states and the events that move a process between them
Worked example: Four jobs, three routines
Jobs A, B, C and D all arrive at time 0 in that order, needing 6, 2, 8 and 3 ms of processor time. Find the order of execution and the average waiting time for FCFS, SJF and round robin with a 4 ms time slice.
Waiting time = finish time − arrival time − burst time.
FCFS: A 0-6, B 6-8, C 8-16, D 16-19. Waits: A 0, B 6, C 8, D 16. Average = 30 / 4 = 7.5 ms.
SJF: shortest first, so B 0-2, D 2-5, A 5-11, C 11-19. Waits: B 0, D 2, A 5, C 11. Average = 18 / 4 = 4.5 ms.
Round robin, 4 ms slice: A 0-4 (2 left), B 4-6 (done), C 6-10 (4 left), D 10-13 (done), A 13-15 (done), C 15-19 (done).
RR waits: A 15 − 6 = 9, B 6 − 2 = 4, C 19 − 8 = 11, D 13 − 3 = 10. Average = 34 / 4 = 8.5 ms.
Answer: FCFS 7.5 ms, SJF 4.5 ms, RR 8.5 ms. SJF minimises the average wait; RR gives every job a turn early (all four have started by 10 ms) at the cost of a higher average.
State, routine, trigger.
States: running, ready (needs only the CPU), blocked (needs an event); blocked goes to ready, never straight to running.
Non-pre-emptive: FCFS (arrival order) and SJF (shortest burst).
Pre-emptive: SRT (least time left; a new shorter job interrupts) and RR (fixed time slice, back of the queue).
Waiting time = finish − arrival − burst. Draw the timeline first, then calculate.
Watch out!
A blocked process never goes straight to running. When its I/O completes it joins the ready queue and waits to be scheduled like everyone else.
SJF is non-pre-emptive: once a job starts it runs to the end. If a question lets a newly arrived short job interrupt the running one, it is describing SRT.
In paging, a process is divided into fixed-size pages and RAM into page frames of the same size; a page table maps each page to a frame, so a process need not be stored contiguously. In segmentation, a process is divided into variable-size logical segments (e.g. code, data, stack) recorded in a segment table. Virtual memory uses secondary storage as if it were RAM: pages not currently needed are kept on disk and swapped in when used, causing a page fault. A page replacement algorithm chooses which page to swap out. If pages are swapped in and out so often that little useful processing is done, the system suffers disk thrashing.
Fig. 1: a page table maps each page of a process to a frame in RAM, or records that the page is on disk
Worked example: Logical to physical address
Pages are 4096 bytes. A process uses logical address 9300. Using the page table in Fig. 1 (page 2 is in frame 5), find the physical address.
Page number = 9300 DIV 4096 = 2 (because 2 × 4096 = 8192 and 3 × 4096 = 12288 is too big).
Offset = 9300 MOD 4096 = 9300 − 8192 = 1108.
Look up page 2 in the page table: it is in frame 5.
Answer: Physical address 21588. The offset is unchanged; only the page number is replaced by the frame number.
Pages, segments, swaps.
Paging: fixed-size pages into frames; page table; page number + offset.
Segmentation: variable-size logical segments; segment table with base and length.
Virtual memory: disk used as RAM; page fault loads a page; thrashing when swapping dominates.
Replacement: FIFO = oldest loaded; LRU = longest since last use. Trace frame by frame and count faults.
Watch out!
Do not say segments and pages are both fixed size. Pages are fixed size and a physical division; segments are variable size and a logical division.
Thrashing is not just "using virtual memory". It is when swapping becomes so frequent that the processor spends most of its time waiting for pages, so little useful work is done.
Compilation has four main stages. Lexical analysis removes white space and comments and converts the source code into tokens, adding identifiers and constants to the symbol table. Syntax analysis (parsing) checks that the sequence of tokens obeys the grammar of the language, builds a parse tree and reports syntax errors. Code generation produces object code from the parse tree. Optimisation makes the object code run faster or use less memory without changing what it does. An interpreter analyses each statement in turn and executes it by calling its own pre-written machine code routines, so no translated version of the program is produced.
Fig. 1: the four stages of compilation, all sharing the symbol table
Worked example: Tokenise a statement
Show what lexical analysis produces from this line of source code:
Total ← Total + Price * 2 // add this item
Remove the comment // add this item and the extra spaces: they are not needed to execute the program.
Split the remaining characters into tokens: Total, ←, Total, +, Price, *, 2. That is 7 tokens.
Classify each token: Total and Price are identifiers, ← + and * are operators, 2 is a numeric constant.
Add Total, Price and the constant 2 to the symbol table (once each) so later stages can record their data type and address, and replace each identifier with a reference to its symbol table entry.
Answer: A token stream: identifier(Total) assign identifier(Total) plus identifier(Price) multiply constant(2), with Total, Price and 2 in the symbol table.
Four stages, one table.
Lexical analysis: remove spaces and comments, tokens, keyword table, symbol table.
Syntax analysis: check tokens against the grammar, parse tree, syntax errors listed.
Code generation: object code, addresses from the symbol table.
Optimisation: faster and/or smaller code, same result. Interpreter: analyse then execute with its own routines; nothing saved.
Watch out!
Saying an interpreter "translates line by line into machine code" loses the mark at A Level. The point is that it executes each statement using its own routines without producing a translated version.
Lexical analysis does not check the order of the tokens. Total + ← Price passes lexical analysis (every token is valid) and is rejected at syntax analysis.
Backus-Naur Form (BNF) is a formal notation for the grammar (syntax rules) of a language. Each rule has a non-terminal in angle brackets on the left, ::= meaning "is defined as", and on the right a sequence of terminals and non-terminals, with | separating alternatives. Terminals are the actual characters or symbols that appear in the language. Repetition is expressed by recursion: a rule that refers to itself. A syntax diagram shows the same rules graphically, following arrows through boxes, with loops for repetition.
Fig. 1: one recursive BNF rule and the equivalent syntax diagram
Worked example: Valid or not?
Using the grammar above, decide whether BAD5, 3AB and AF are valid identifiers. Show a derivation for any valid one.
BAD5 ends in a digit, so use <identifier> ::= <identifier><digit>: <identifier> → <identifier><digit>.
Expand the inner identifier twice with <identifier><letter>: → <identifier><letter><digit> → <identifier><letter><letter><digit>.
End the recursion with <identifier> ::= <letter>: → <letter><letter><letter><digit> → B A D 5. All four terminals are allowed, so BAD5 is valid.
3AB: every identifier must begin with <letter>, and 3 is a digit. Invalid.
AF: F is not one of the terminals A to E in <letter>. Invalid.
Answer: BAD5 valid; 3AB invalid (starts with a digit); AF invalid (F is not a defined letter).
Smallest parts first.
Notation: <non-terminal>, ::= is defined as, | or, terminals written as themselves.
Recursion: "one or more" means a rule that refers to itself plus a non-recursive way out.
Syntax diagrams: rectangles for non-terminals, rounded boxes for terminals, branches for |, loops for repetition.
Validity: check every character against the listed terminals and the required order and length.
Watch out!
Check every character against the terminals that are actually listed. In exam grammars <letter> or <digit> is often deliberately restricted, e.g. to A to E or to 1 to 9.
A rule like <number> ::= <digit><number> with no non-recursive alternative can never finish, so it defines no strings at all. Every recursive rule needs a way out.
In infix notation the operator is written between its operands (A + B). In Reverse Polish notation (RPN), also called postfix, the operator is written after its operands (A B +). RPN needs no brackets and no precedence rules: the order of the tokens fixes the order of the operations. It is evaluated left to right using a stack: push each operand; for each operator, pop two values, apply the operator and push the result. Compilers and interpreters convert expressions to RPN because this simple, unambiguous process is easy to turn into machine code.
Fig. 1: the expression tree for (A + B) * (C − D), its RPN form from a post-order traversal, and the stack before and after the final *
Worked example: Show the stack contents
Evaluate A B + C D − * when A = 6, B = 2, C = 7 and D = 3, showing the contents of the stack after each token.