Systems Software
Operating system functions, memory management and paging, every scheduling algorithm, interrupts, and the four types of operating system.
Memory management and scheduling
Memory management
The operating system must decide what occupies physical memory and where.
Paging divides memory into fixed size pages and physical memory into equally sized frames. Any page can go in any frame, so pages of a process need not be contiguous. A page table maps logical page numbers to physical frame numbers.
Segmentation divides memory into variable sized segments that reflect the logical structure of the program, such as a function, an array or a module.
| Paging | Segmentation | |
|---|---|---|
| Size | Fixed | Variable |
| Divided by | The operating system | The logical structure of the program |
| Fragmentation | Internal, since the last page is rarely full | External, as gaps appear between segments |
| Address | Page number plus offset | Segment number plus offset |
Virtual memory uses secondary storage to hold pages that do not fit in RAM. When a required page is absent a page fault occurs, the operating system loads it, evicting another page if necessary. Excessive page faults cause disk thrashing.
Scheduling
The scheduler decides which process gets the processor and for how long, aiming to maximise throughput, keep the processor busy, be fair and stay responsive.
| Algorithm | How it works | Strengths and weaknesses |
|---|---|---|
| Round robin | Each process gets a fixed time slice in turn | Fair and responsive, but ignores priority and urgency |
| First come first served | Processes run in arrival order until they finish or block | Simple, but one long job blocks everything behind it, the convoy effect |
| Shortest job first | The process with the shortest total time runs next | Best average waiting time, but requires knowing run times in advance and can starve long jobs |
| Shortest remaining time | Pre-emptive version of shortest job first | Very responsive, but high overhead and worse starvation |
| Multi level feedback queues | Several queues of differing priority, with processes moved between them based on behaviour | Flexible and adaptive, but complex to tune |
A pre-emptive scheduler can interrupt a running process to give the processor to another. Round robin, shortest remaining time and multi level feedback queues are pre-emptive. First come first served and shortest job first are not.
- RAM holds the programs that are running. It is fast, and it is small.
- Open one program too many and there is no room left.
- A page that has not been used lately is written out to the disk.
- That frees real memory, so the new program can start.
- Needed again, the page is fetched back, which is why it goes slow.
- First come first served: jobs run in arrival order, so the long job A holds up B and C.
- Shortest job first: the lowest average wait, but it needs to know the lengths and can starve long jobs.
- Round robin: each job gets a short slice in turn, so everyone starts quickly and shares the CPU fairly.
Types of operating system and other functions
Types
- Distributed. One system spread across multiple networked machines, sharing work and appearing to the user as a single system.
- Embedded. Built for one dedicated task, minimal, stored in ROM, highly reliable and low power.
- Multi tasking. Several processes appear to run at once through rapid context switching between them.
- Multi user. Several users share one system simultaneously, requiring scheduling and access control to keep them separated fairly.
- Real time. A guaranteed maximum response time, essential where a late answer is a wrong answer, as in an anti lock braking system or a pacemaker.
Other operating system functions
- Interrupt handling. The end of cycle check, saving state to a stack, running the interrupt service routine, restoring state.
- Device drivers. Translating generic operating system instructions into commands a specific hardware device understands, which is why the same operating system supports thousands of printers.
- File management. Directory structure, permissions, allocation of blocks, and tracking free space.
- Security. Authentication, access rights, encryption support and auditing.
The BIOS and the boot process
- Power on. The processor begins executing at a fixed address in ROM.
- The BIOS or UEFI firmware runs a power on self test, checking that essential hardware responds.
- It identifies the boot device and loads the bootstrap loader from it.
- The bootstrap loads the operating system kernel into RAM.
- Control passes to the kernel, which initialises drivers, memory management and the user interface.
Virtual machines
A virtual machine is a software implementation of a computer.
- Intermediate code, such as Java bytecode, is executed by a virtual machine, so the same compiled code runs on any platform with a suitable VM. The cost is slower execution than native code.
- System virtual machines run a complete guest operating system in software, allowing several operating systems on one physical machine, sandboxed testing of untrusted software, and consolidation of servers.
- The operating system sits between the applications and the hardware, so a program never has to deal with the hardware directly.
- It shares out the computer's resources: memory, processor time and storage.
- It also talks to devices through drivers, keeps the system secure and provides the user interface.
Key terms you must be able to define
- Paging
- Dividing memory into fixed size pages mapped to equally sized physical frames.
- Segmentation
- Dividing memory into variable sized segments reflecting the logical structure of a program.
- Page fault
- An event raised when a required page is not present in physical memory.
- Scheduler
- The operating system component deciding which process runs and for how long.
- Pre-emptive
- A scheduling approach that can interrupt a running process to give the processor to another.
- Round robin
- Scheduling giving each process an equal time slice in turn.
- Starvation
- A process never receiving processor time because others are continually prioritised.
- Device driver
- Software translating operating system instructions into commands for specific hardware.
- Real time operating system
- An operating system guaranteeing a maximum response time.
- Virtual machine
- A software implementation of a computer, used to run intermediate code or a guest operating system.
- BIOS
- Firmware that performs the power on self test and loads the bootstrap loader.
Flashcards
Say the definition out loud before you flip the card. Retrieving it from memory is what builds recall, reading it again is not.
Reach the top grade on this topic
- Compare paging and segmentation on size, who decides the division, and the kind of fragmentation each causes
- Name each scheduling algorithm with both a strength and a weakness, including starvation and the convoy effect
- Identify which algorithms are pre-emptive and explain what that means
- Explain intermediate code and virtual machines in terms of portability against execution speed
- Explain a real time operating system as one where a late answer is a wrong answer
Mistakes that cost marks here
- Saying paging and segmentation are the same. Pages are fixed size and decided by the OS, segments are variable and follow program structure.
- Describing round robin as efficient. It is fair and responsive, which is a different property.
- Forgetting starvation as the weakness of shortest job first.
- Saying a real time OS is simply fast. It guarantees a maximum response time.
- Saying intermediate code runs everywhere with no cost. It executes more slowly than native code.
Round robin scheduling was designed to be fair, not fast. Every process gets an equal slice whether it needs a microsecond or an hour, which is exactly what makes an interactive system feel responsive.
Knowledge check
Exam-style questions
Five written questions in the style of the real paper. Write a full answer, then let the marker check it against the mark scheme.
- LPages are fixed size divisions of memory
- LSegments are variable in size
- LPaging is decided by the operating system regardless of program structure
- LSegmentation follows the logical structure of the program such as functions or arrays
Paging divides memory into fixed size blocks called pages, with physical memory divided into frames of exactly the same size, so any page can be placed in any free frame. The division is made by the operating system purely on the basis of size and takes no account of what the memory contains, which means a single function might be split across two pages. Segmentation instead divides memory into variable sized segments that correspond to the logical structure of the program, so one segment might hold a particular function, another an array and another the stack. Because segments vary in size, allocating and freeing them leaves gaps between them, producing external fragmentation, whereas paging produces internal fragmentation because the final page of an allocation is rarely completely full.
- LEach process is given a fixed time slice or quantum
- LWhen the slice expires the process is pre-empted and moved to the back of the queue
- LAdvantage: it is fair and gives good responsiveness for interactive processes
- LDisadvantage: it ignores priority and urgency, and context switching adds overhead
In round robin scheduling every ready process is placed in a queue and each is given the processor for a fixed period known as a time slice or quantum. When that slice expires the process is pre-empted, its state is saved, and it is moved to the back of the queue while the next process runs. The cycle continues so that every process receives processor time regularly. Its main advantage is fairness and responsiveness: no process can monopolise the processor and none can be starved, which makes an interactive system feel consistently responsive to user input. Its main disadvantage is that it takes no account of priority or urgency, so a critical process waits exactly as long as a trivial one, and the frequent context switching consumes processor time that does no useful work, which becomes significant if the quantum is set too short.
- LIt guarantees a response within a defined maximum time
- LA late response is treated as a failure even if it is correct
- LGives a valid example such as anti lock brakes, a pacemaker or industrial control
A real time operating system is one that guarantees a response to an event within a defined maximum time, rather than merely aiming to be fast on average. The essential property is determinism: the worst case response time is known and bounded. In such a system a correct result delivered after the deadline counts as a failure, because the moment for acting has already passed. An anti lock braking system is a clear example: when a wheel locks, the controller must reduce brake pressure within milliseconds, and a decision arriving even slightly late is worthless because the vehicle has already skidded. Other examples include pacemakers, aircraft flight control systems and industrial machinery controllers.
- LThe source is compiled once into platform independent intermediate code
- LThe same code runs on any platform that has a suitable virtual machine
- LThis removes the need to compile separately for every target platform
- LExecution is slower than native machine code because of the translation layer
- LA virtual machine must be installed on the target system
With intermediate code, the source is compiled once into a platform independent form such as Java bytecode rather than into the machine code of a particular processor. The main advantage is portability: the same compiled file will run on Windows, macOS, Linux or a mobile platform provided a suitable virtual machine is present, so the developer maintains and distributes one version rather than building and testing a separate binary for every target. This substantially reduces development and distribution effort, and it also allows the virtual machine to provide a controlled sandbox, which improves security. The principal disadvantage is performance. The virtual machine must translate the intermediate code to native instructions as the program runs, and this additional layer means execution is slower than equivalent natively compiled code, even with just in time compilation reducing the gap. There is also a dependency cost, since the appropriate virtual machine must be installed on the target system before the program will run at all, and the program cannot access platform specific hardware features directly.
- LThe processor begins executing firmware from a fixed address in ROM
- LA power on self test checks that essential hardware is present and working
- LThe firmware identifies the boot device
- LThe bootstrap loader is loaded and run
- LThe operating system kernel is loaded into RAM and takes control
When power is applied, the processor begins executing instructions from a fixed address which points into ROM, so the first code to run is firmware rather than anything on the disk. That firmware, the BIOS or UEFI, performs a power on self test which verifies that essential hardware such as memory, the processor and the display adapter are present and responding, halting with an error if anything critical fails. It then consults its configuration to determine the boot order and identifies the device to boot from. The bootstrap loader is read from that device into memory and executed, and its job is to locate and load the operating system kernel into RAM. Control is then transferred to the kernel, which initialises memory management, loads device drivers, starts system services and finally presents the user interface.