System software (A Level)
Cambridge AS & A Level Computer Science 9618 · Paper 3 · Unit 16
Paper 3 · Unit 16. Process and memory management, compilation stages, BNF and Reverse Polish Notation.
1. Purposes of an operating system
The OS maximises the use of resources (CPU, memory, devices) and hides hardware complexity behind a user interface.
Process management: a process is a program being executed. In multitasking, the OS switches between processes so they appear to run at once. Process states: running (on the CPU), ready (waiting for CPU time) and blocked (waiting for an event such as I/O).
| Scheduling algorithm | How it works |
|---|---|
| First come first served | Processes run in arrival order |
| Shortest job first | The process with the shortest burst time runs next |
| Shortest remaining time first | Pre-emptive: switch if a new process needs less time than what remains |
| Round robin | Each process gets a fixed time slice in turn |
Memory management: paging splits memory into fixed-size pages and frames; segmentation uses variable-size logical segments. Virtual memory uses disk space as an extension of RAM; too much swapping causes disk thrashing, where the system spends more time swapping than processing.
2. Translation software
Stages of compilation:
- Lexical analysis: removes whitespace and comments, splits code into tokens, builds the symbol table.
- Syntax analysis: checks tokens against the grammar rules (parsing), producing a parse tree and error reports.
- Code generation: produces object code.
- Optimisation: makes the code faster or smaller.
Grammar can be defined with BNF or syntax diagrams, e.g. <digit> ::= 0|1|2|3|4|5|6|7|8|9 and <number> ::= <digit> | <digit><number> (recursive).
3. Reverse Polish Notation
In RPN (postfix), operators come after their operands, e.g. (3 + 4) × 2 becomes 3 4 + 2 ×. It needs no brackets and is easy to evaluate with a stack: push operands; for an operator, pop two values, apply it, and push the result.
Try it: evaluate Reverse Polish Notation with a stack
4. Examiner tips
- Process states: explain each transition (e.g. running to blocked on an I/O request).
- Round robin uses time slices; know what happens when a slice ends.
- Lexical vs syntax analysis: tokens vs grammar.
- RPN: show the stack after every token.
- BNF recursion is how repeating items are defined.
5. Practice questions
Practice: answer and check instantly
Type a short answer, then press Check or Enter.
Show answer
Blocked.
Show answer
Round robin.
Show answer
Disk thrashing.
Show answer
Lexical analysis.
Show answer
Syntax analysis.
Show answer
(2 + 3) × 4 = 20.
Show answer
5 + (1+2)×4 − 3 = 14.
Show answer
Paging.
Exam-style questions
9. Describe the three states a process can be in, and how it moves between them. [4]
Show mark guide
Ready: waiting for CPU time [1] · running: being executed [1] · blocked: waiting for an event e.g. I/O [1] · e.g. running → blocked on I/O request, blocked → ready when I/O completes, running → ready when time slice ends [1].
10. Explain what happens during lexical analysis. [3]
Show mark guide
Whitespace and comments are removed [1] · the code is split into tokens [1] · identifiers are entered into the symbol table / keywords replaced by tokens [1].
6. Topic test: predict your grade
Topic test: predict your grade
15 questions, about 10 minutes. Answer them all, then press Mark my test.
Frequently asked questions
What are the three process states?
Running means the process is on the CPU, ready means it is waiting for CPU time, and blocked means it is waiting for an event such as input or output.
What happens in lexical analysis?
Lexical analysis removes whitespace and comments, splits the code into tokens and builds the symbol table.
How do you evaluate Reverse Polish Notation?
Read the tokens left to right using a stack. Push each number; for each operator, pop two numbers, apply the operator and push the result.