🖥️ A Level · Chapter 16
System Software
Operating Systems · Process Management · Memory · Translation Software · BNF · RPN
16.1 Operating System Purposes
Core job of the OS
The OS sits between hardware and user applications. Its job is to maximise resource usage, abstract hardware complexity, and provide a safe, fair environment for multiple processes to run.
Process Management & States
A process is a program in execution. Every process moves between three states:
🟡 Ready
Waiting for CPU
→
Scheduled
🟢 Running
Using CPU
→
I/O wait
🔴 Blocked
Waiting for I/O
Transitions
Ready → Running: scheduler picks the process. Running → Blocked: process requests I/O (disk, network). Blocked → Ready: I/O completes. Running → Ready: time slice expires (pre-emption).
Scheduling Algorithms
| Algorithm | How it works | Pros | Cons |
|---|---|---|---|
| Round Robin | Each process gets a fixed time slice in turn | Fair, responsive, no starvation | High-priority jobs wait equally |
| Shortest Job First (SJF) | Process with shortest estimated runtime goes next | Minimises average waiting time | Long jobs may starve; need to know runtime |
| First Come First Served | Queue — earliest arrival runs first | Simple, no starvation | Long jobs block short ones (convoy effect) |
| Shortest Remaining Time | Pre-emptive SJF — switch if new job has less time remaining | Optimal average wait time | Context-switching overhead; needs runtime estimates |
Virtual Memory, Paging & Segmentation
When RAM is full, the OS uses virtual memory — treating part of the disk as extra RAM. This allows programs larger than physical RAM to run.
Memory is divided into fixed-size blocks called pages (in RAM) and frames (on disk). The OS maintains a page table mapping virtual page numbers to physical frame addresses.
P0
RAM
RAM
P1
RAM
RAM
P2
DISK
DISK
P3
free
free
P4
DISK
DISK
P5
RAM
RAM
When a process accesses a page not in RAM → page fault → OS loads it from disk (swapping out another page if needed).
Disk Thrashing
If too many processes compete for too little RAM, the OS spends more time swapping pages than executing instructions. Performance collapses. Fix: add RAM or reduce running processes.
Paging
- Fixed-size blocks
- No external fragmentation
- Pages don’t map to logical meaning
- Simpler to manage
Segmentation
- Variable-size blocks (matching logical sections: code, data, stack)
- Can cause external fragmentation
- More meaningful to programmer
- Protection: code segment can be read-only
16.2 Translation Software
Stages of Compilation
1
Lexical Analysis
Tokenises source code: removes whitespace/comments, converts keywords/identifiers/literals into tokens. Builds a symbol table.
2
Syntax Analysis
Checks token stream against grammar rules (using a parse tree). Reports syntax errors. Produces Abstract Syntax Tree (AST).
3
Semantic Analysis
Checks meaning: type checking, variable declarations, scope. Are operations valid? (e.g. can’t add integer to string)
4
Code Generation
Translates AST into intermediate or target machine code.
5
Optimisation
Improves generated code: removes dead code, simplifies loops, reorders instructions for speed/efficiency.
BNF — Backus-Naur Form
BNF is a formal notation for defining the grammar (syntax rules) of a programming language.
Symbols:
::= means “is defined as”
| means “or”
< > encloses a non-terminal (something to be expanded)
Example — defining a digit and integer:
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<integer> ::= <digit> | <integer> <digit>
This says: an integer is either a single digit,
OR an existing integer followed by another digit
→ allows: 5, 42, 317, 9001…
Syntax diagrams
Syntax diagrams (railroad diagrams) are the visual equivalent of BNF — boxes represent terminals/non-terminals, arrows show valid paths through the grammar.
Reverse Polish Notation (RPN)
RPN places operators after their operands. No brackets needed — operator precedence is explicit in position. Evaluates using a stack.
Infix → RPN
Infix: (3 + 4) × 5
RPN: 3 4 + 5 ×
Infix: A + B × C
RPN: A B C × +(higher precedence × goes first)
Evaluating RPN with a stack
Expression: 3 4 + 5 ×
Token Stack
3 [3]
4 [3, 4]
+ [7] (3+4)
5 [7, 5]
× [35] (7×5)
Result: 35 ✓
Why RPN?
Compilers use RPN internally because it eliminates operator precedence ambiguity and maps directly to stack-machine instructions. Easy to evaluate with a simple stack algorithm.
| Compiler | Interpreter | |
|---|---|---|
| Translation | Entire program before execution | Line-by-line at runtime |
| Speed | Fast execution (pre-compiled) | Slower (translates each run) |
| Error detection | All errors at compile time | Stops at first runtime error |
| Distribution | Can distribute executable (no source) | Source code usually needed |
| Debugging | Harder — re-compile each change | Easier — run and see immediately |
| Use case | Production software (C, C++) | Development/scripting (Python, JavaScript) |
Hybrid (Java)
Java compiles to bytecode (platform-independent), then the JVM interprets or JIT-compiles bytecode at runtime. Gets some benefits of both.
⚡ Exam Essentials
- Name all 3 process states and transitions between them
- Compare all 4 scheduling algorithms with pros and cons
- Explain paging, page fault, and disk thrashing
- Distinguish paging from segmentation
- Name all 4–5 compilation stages in order
- Write and interpret BNF grammar rules
- Convert infix to RPN and evaluate RPN using a stack trace