Ch 2 · 16 System Software · AS & A Level Computer Science 9618
Topic 2 of 3 in Hardware, System Software and Security — AS & A Level Computer Science 9618 — 98 lessons.
Introduction
At AS you met the tasks of an operating system. Here you look at how it shares the processor and memory between many programs, and at how a compiler turns source code into machine code, including how a language's grammar is defined and how expressions are evaluated. (Syllabus topic 16: sections 16.1–16.2.)
Key ideas — 16.1 (a) Maximising the use of resources
The OS makes the best use of the computer's resources (processor, memory, storage, I/O devices):
🧑🏫 Teacher's explanation
Imagine a busy restaurant kitchen. The chef (the CPU) is the most expensive resource. If the chef spends time waiting for a delivery of onions (I/O), they are wasting money. To maximize efficiency, the chef starts chopping carrots while waiting for the onions. This is multitasking.
📖 Definitions
🔍 Worked example — Easy
A process is currently waiting for a user to input data via a keyboard. Identify the current state of this process and determine the next state once the user presses 'Enter'.
🔍 Worked example — Standard
A system has 8GB of RAM. A user opens three applications: App A (3GB), App B (3GB), and App C (4GB). How much space must be allocated to virtual memory to allow all three to be loaded into memory simultaneously?
🔍 Worked example — Exam-style
Three processes, P1, P2, and P3, arrive at the same time. Their burst times (execution time) are: P1 = 10ms, P2 = 4ms, P3 = 7ms. Using the Shortest Job First (SJF) scheduling algorithm, determine the total waiting time for all processes.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Draw a Gantt chart showing the execution order of these processes. [3] (b) Explain how the use of interrupts allows the kernel to manage this scheduling. [2] [5 marks]
Key ideas — 16.1 (b) Processes and multitasking
A process is a program that is being executed (with its data, registers and state). Multitasking means several processes appear to run at the same time: the OS switches the processor between them so quickly that each seems to run continuously.
🧑🏫 Teacher's explanation
Imagine you are a chef in a busy restaurant kitchen. You have one stove (the CPU), but you have five different orders to cook (the processes). You cannot cook them all at the exact same microsecond, so you switch between them rapidly. You might chop onions for Order A, then quickly flip a pancake for Order B, then wait for the water to boil for Order C. To the customers waiting in the dining room, it looks like you are cooking everything simultaneously. This illusion is multitasking.
📖 Definitions
🔍 Worked example — Easy
A process is currently in the 'running' state. It issues a request to read a large file from the hard drive. Describe the state transition this process undergoes and explain why it cannot move directly back to the 'running' state once the file is read.
🔍 Worked example — Standard
Three processes, P1, P2, and P3, are in the 'ready' queue. The OS uses a First-Come, First-Served (FCFS) scheduling algorithm. P1 arrived at t=0, P2 at t=2, and P3 at t=5. If P1 requires 4 seconds of CPU time, P2 requires 2 seconds, and P3 requires 3 seconds, calculate the completion time for P3.
🔍 Worked example — Exam-style
A scheduler uses Round Robin with a time slice of 5ms. Process A needs 12ms. Process B needs 4ms. Both enter the 'ready' queue at the same time. Trace the CPU usage for the first 15ms.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 16.1 (c) Scheduling
The scheduler decides which ready process runs next. It is needed to share the processor fairly, keep it busy, give a fast response to users, and maximise the number of processes completed.
🧑🏫 Teacher's explanation
Imagine a busy doctor's office. If the doctor sees patients strictly in the order they walk in, that is First Come First Served. If the doctor looks at the chart and sees a patient only needs a quick prescription while another needs a two-hour surgery, and chooses the quick one first to clear the waiting room, that is Shortest Job First. However, if a new patient arrives with a life-threatening emergency that takes less time than the current patient's procedure, the doctor might pause the current patient to deal with the emergency—this is Pre-emption, used in Shortest Remaining Time.
📖 Definitions
🔍 Worked example — Easy
Three processes arrive at time t=0. P1 has a burst time of 5ms, P2 has 2ms, and P3 has 8ms. Calculate the average waiting time using First Come First Served (FCFS).
🔍 Worked example — Standard
Using Shortest Job First (SJF) for the following processes (all arrive at t=0): P1 (burst 10), P2 (burst 3), P3 (burst 6). Calculate the average waiting time.
🔍 Worked example — Exam-style
A system uses Round Robin scheduling with a time quantum of 4ms. Processes: P1 (burst 5), P2 (burst 2). Both arrive at t=0. Calculate the average waiting time.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Key ideas — 16.1 (d) The kernel as an interrupt handler
The kernel is the core of the OS that stays in memory. It acts as the interrupt handler, and interrupts drive low-level scheduling:
🧑🏫 Teacher's explanation
Imagine you are a chef in a busy kitchen. You are currently chopping onions (the 'running' process). Suddenly, a timer rings on the oven (an 'interrupt'). You cannot ignore it, or the cake will burn. You must stop chopping, remember exactly how many onion slices you had left (saving the 'state'), and quickly turn to the oven to check the cake. Once the oven task is handled, you return to the onions.
📖 Definitions
🔍 Worked example — Easy
A process is currently in the 'Running' state. A timer interrupt occurs. Describe the sequence of events the kernel must perform to switch to a different process.
🔍 Worked example — Standard
A process is in the 'Blocked' state waiting for a keyboard input. An I/O interrupt is triggered by the keyboard. What is the new state of the process and why?
🔍 Worked example — Exam-style
A system uses Round Robin scheduling with a time slice of 10ms. Process A is running. At t=10ms, a timer interrupt occurs. If Process A's Program Counter was at address 0x004, and the next instruction is at 0x008, what information must be saved in the PCB?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Describe the role of the kernel in response to this interrupt. [3] (b) Explain why the process P1 is moved to the 'Ready' state rather than the 'Running' state immediately after the interrupt. [2] [5 marks]
Key ideas — 16.1 (e) Virtual memory, paging and segmentation
Page replacement. When a needed page is not in RAM (a page fault) and no frame is free, a page in RAM must be swapped out to disk. The page to replace is chosen by an algorithm such as:
🧑🏫 Teacher's explanation
Imagine you are studying for a massive exam using a small desk (RAM) and a huge bookshelf (Secondary Storage). Your desk is too small to hold all your textbooks at once. Instead of trying to fit everything on the desk, you keep only the specific chapters you are currently reading on the desk (Paging) and leave the rest on the shelf (Virtual Memory). If you need a chapter that is on the shelf, you swap it with a chapter on your desk that you haven't looked at in a while.
📖 Definitions
🔍 Worked example — Easy
A system uses paging with a page size of 4 ext KB. A process requires 13 ext KB of memory. Calculate the number of pages required and the amount of internal fragmentation in the last page.
🔍 Worked example — Standard
A program is divided into segments. Segment A is 5 ext KB, Segment B is 12 ext KB, and Segment C is 8 ext KB. If the available contiguous RAM is 20 ext KB, can all segments be loaded? Explain why or why not.
🔍 Worked example — Exam-style
A system uses LRU (Least Recently Used) page replacement. The access sequence for pages is: 1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5. If the RAM can only hold 3 pages, identify the page that is replaced when page 5 is accessed for the first time.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Calculate the number of pages that must be allocated to this process. [2] (b) Calculate the amount of internal fragmentation caused by this allocation. [2] [4 marks]
Key ideas — 16.2 (a) How an interpreter executes a program
An interpreter does not produce a translated (object code) version. For each statement in turn, it: reads (fetches) the source statement, analyses it (checks the syntax), and if it is valid, executes it immediately by calling pre-written routines in the interpreter that carry out that operation. If an error is found, execution stops at that statement. The process is repeated every time the program runs.
🧑🏫 Teacher's explanation
Imagine you are following a recipe written in a foreign language. A compiler is like a professional translator who translates the entire recipe into your language and prints a new book for you to keep. An interpreter, however, is like a live interpreter standing next to you; they read one line of the foreign recipe, tell you what it means in your language, and you perform that action immediately. They don't give you a new book; they just guide you through the original one, line by line.
📖 Definitions
🔍 Worked example — Easy
Identify the stages of translation for the statement: x arrow 5 + 3
🔍 Worked example — Standard
Evaluate the following expression using Reverse Polish Notation (RPN): 5, 3, + , 2, ×
🔍 Worked example — Exam-style
A program contains the following line: IF x > 10 THEN. During the compilation process, what specific stage is responsible for identifying that the 'THEN' keyword is missing or misplaced?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Describe the process an interpreter follows when it encounters a statement in the source code. [3] (b) State one advantage and one disadvantage of using an interpreter instead of a compiler. [2] [5 marks]
Key ideas — 16.2 (b) Stages of compilation
🧑🏫 Teacher's explanation
Think of a compiler like a professional translator converting a complex, handwritten novel into a standardized, printed book for a foreign audience. You can't just swap words one-for-one; you have to understand the structure of the sentences and the context of the story first.
📖 Definitions
🔍 Worked example — Easy
Identify the tokens produced during the lexical analysis stage for the following line of code: x <- 5 + y
🔍 Worked example — Standard
A compiler performs optimisation on the following loop:
🔍 Worked example — Exam-style
During syntax analysis, a compiler encounters the following token sequence: IF, x, +, 5, THEN. Explain why this results in a syntax error.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
(a) Identify the stage of compilation where the compiler checks the sequence of tokens against the grammar of the programming language. [1] (b) Describe the purpose of the 'optimisation' stage in the compilation process. [2] [3 marks]
Key ideas — 16.2 (c) Syntax diagrams and BNF
The grammar (syntax rules) of a language can be defined precisely.
🧑🏫 Teacher's explanation
Imagine you are following a recipe. A recipe has rules: 'an egg OR a substitute', or 'a bowl containing flour AND sugar'. If the recipe says 'a bowl containing a bowl containing flour', it's a recursive instruction. In computer science, programming languages have strict rules about how words (tokens) can be combined to make valid code. If you break these rules, the compiler throws a 'syntax error'.
📖 Definitions
🔍 Worked example — Easy
Given the following BNF rules, determine if the string 'A1' is valid: <letter> ::= A|B|C <digit> ::= 0|1|2 <identifier> ::= <letter> | <identifier><letter> | <identifier><digit>
🔍 Worked example — Standard
Using the BNF rules: <digit> ::= 0|1|2 <number> ::= <digit> | <digit><number> Determine if the string '123' is valid.
🔍 Worked example — Exam-style
A syntax diagram for <integer> shows a path through a rectangle labeled [digit], followed by a loop that allows another path through a rectangle labeled [digit]. If <digit> is defined as 0|1|2, how many valid integers can be formed using exactly 2 digits?
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
<expr> ::= <term> | <expr> '+' <term> <term> ::= <factor> | <term> '*' <factor> <factor> ::= <number> | '(' <expr> ')' <number> ::= <digit> | <digit><number> <digit> ::= 0|1|2|3|4|5|6|7|8|9
Key ideas — 16.2 (d) Reverse Polish Notation (RPN)
Reverse Polish Notation (postfix) writes each operator after its operands: A + B becomes A B +. RPN needs no brackets and no rules of precedence, so a compiler or interpreter can evaluate expressions simply, from left to right, using a stack:
🧑🏫 Teacher's explanation
In standard math (infix notation), we use brackets and rules like BODMAS to decide which part of an expression to solve first. This is hard for a computer because it has to look ahead to see if a multiplication is coming up later. Reverse Polish Notation (RPN), also known as postfix notation, solves this by placing the operator immediately after the numbers it acts upon.
📖 Definitions
🔍 Worked example — Standard
Evaluate the RPN expression: 10\ 2\ /\ 3\ +
🔍 Worked example — Exam-style
Convert the infix expression (5 + 3) × (10 - 2) to RPN and evaluate it.
⚠️ Common errors
🧠 Quick check 1
🧠 Quick check 2
🎯 Exam question
Worked example
When many programs run with too little RAM, virtual memory is used heavily. A page is swapped out to disk to make room, but is needed again almost immediately and must be swapped back in, forcing out another page that is soon needed. The disk is constantly busy reading and writing pages, which is very slow compared with RAM, so the processor spends most of its time waiting for page swaps instead of executing instructions.
🔍 Worked example — Easy
A system has 8GB of RAM. The current active processes require 10GB of memory. Explain why the system uses virtual memory and identify the primary performance bottleneck.
🔍 Worked example — Standard
A process requires 4 pages to run. The system has only 2 physical page frames available in RAM. If the process accesses pages in the sequence: 1, 2, 3, 1, 2, 3, calculate the number of page faults (swaps from disk to RAM) assuming a FIFO (First-In-First-Out) replacement policy.
🔍 Worked example — Exam-style
A computer is experiencing 'thrashing'. Describe the relationship between the Page Fault Rate and CPU Utilization during this state.
⚠️ Common errors
Common mistakes
Practice
Answers: (1) The user gives commands through a GUI or CLI (e.g. clicking Save), and the OS and device drivers carry out the hardware-level operations, so the user does not need to know how the hardware works. (2) Running: being executed; ready: waiting for processor time; blocked: waiting for an event such as I/O. E.g. running → blocked when the process requests I/O. (3) Each process gets a short time slice in turn, so every user's process gets regular processor time and the response time is good. (4) Paging divides programs into fixed-size pages (a physical division); segmentation divides them into variable-size logical segments. (5) Whitespace and comments are removed, the code is converted into tokens, and identifiers are added to the symbol table. (6) AB12 is valid; A-1 is not (- is neither a letter nor a digit). (7) A B + C D − *; (3 + 5) × (9 − 4) = 8 × 5 = 40.