9. Operating Systems.
Operating Systems
• When a computer starts up it executes its reset handler which is in ROM. Programs permanently in ROM on a computer are known as firmware.
• In a dedicated machine (e.g. an embedded computer), with just one task, this can start immediately.
• In a more general system firmware will include a limited system, often called a BIOS (basic input- output system) which can run tests, allow users to change setup parameters for the machine and load (boot) a full OS from non-volatile secondary storage.
• Once a full OS is loaded into primary memory its aim is to facilitate access to the capabilities of the hardware for application programs and users.
• Many different types. Examples: Windows, Unix, iOS, Android, various real-time OSs, main frame OSs etc.
• The most simple OSs can only run one program at a time but nowadays most can run many programs simultaneously (called multitasking or concurrency).
• Issues involved with multitasking are much more involved, including protections for programs and data in both primary and secondary memory and management of all shared resources including the CPU, memory and I/O devices.
• Additionally multitasking operating systems may support multiple users and must ensure that these are also fully secured from each other.
• An OS can be viewed as a collection of a large number of services, some of which are provided all the time and others available to user programs via machine code requests (usually via an instruction like TRAP).
– In multitasking all access to shared resources must be granted by the OS.
Systems and Networks 9. Operating Systems 2
Historical Motivation: Waiting for I/O
• Physical input/output involves getting data codewords (bits) from external I/O peripheral devices into primary memory or vice versa (not discussed much so far).
– Some I/O devices are input-only (keyboard), some output-only (screen), some both (disk).
• I/O devices are often complex to setup and hard for programmers to use directly.
• One of the motivations for the first operating systems was to avoid programs doing I/O from having to “reinvent the wheel”. Provided “always-present” I/O services accessible via TRAP instructions.
– This also made it easier to offer OS facilities to allow users to interact with the computer using keyboard and screen, leading to support for commands to help load applications etc.
– But this still just supports one program running at a time (single tasking).
• But while CPU calculations are fast, I/O is slow. E.g. reading a character of input from a keyboard is much
slower than executing an inst (> 100 million times slower).
– So, a machine running a single program, will often spend most time waiting for I/O. – CPU can do nothing but execute an idle loop (sometimes called a busy wait)
Time
Executing useful instructions Waiting on I/O devices
• An idle CPU is a wasted resource! Solution: find it something else to do!
• Example: when a computer prints a document, it doesn’t just freeze up until the printout is ready.
Systems and Networks 9. Operating Systems 3
Processes and State
• The idea of a process is related to that of a program but differs from it as follows.
– A program is a static entity, either a source program written as text, or a binary image containing
machine code.
– A process is a running program and so is dynamic, continually changing as time passes and its instructions are executed.
• When a program is loaded into primary memory and is ready to run, it becomes a process.
• As it runs, the only things that change are the CPU internal registers (including the program counter) and the values of (some of) the memory locations it uses.
• A process can stop running for several reasons.
– It can terminate because it is finished (e.g. TRAP R0,R0,R0).
– It can be aborted by the OS or a user with no intention of resuming it.
– It can be suspended by the operating system with the intention of resuming it later.
– To resume a process successfully, the contents of all the CPU registers and memory locations it is using must be preserved.
– Note that it is less complicated to resume a process if it is suspended between instruction cycles.
• The collection of information needed to resume a process later is called its state.
• If any parts of a process state might be overwritten when the process is suspended (e.g. if the CPU or memory is to be used for something else) then these parts must be saved somewhere until the time comes to resume the process.
Systems and Networks 9. Operating Systems 4
A Solution: Concurrent Processes
• By suspending a process which is waiting on I/O, and carefully saving its state, another process can be run to keep the CPU busy. The first process is said to block on I/O and the change of process is called a context switch.
• By repeating this switching between two (or more) processes, several processes can make progress at the same time on one CPU. This is multi-tasking.
– In reality, to prevent unfairness, a modern OS uses a hardware timer capable of interrupting the CPU at regular intervals to implement multitasking.
– An interrupt is a hardware signal from a device to the CPU which will stop it executing the current process (this is called a process break) after a set period of time called a time slice and jump to interrupt handler code elsewhere in memory.
Process 1 Process 2
Ready—not actually executing, but ready to go when CPU becomes available
Systems and Networks 9. Operating Systems 5
Two activities can make progress; neither is frozen because of the presence of the other
The OS Controls Processes
• In multitasking there may be many independent processes running together.
– A programmer writing one of the programs cannot know what other processes will be running if an I/O block or process break occurs and cannot manage the context switching.
• Other issues that must be tackled include:
– Sharing I/O devices which multiple processes may need (screen, keyboard, printer etc.);
– Preventing independently written processes from over-writing each other’s memory.
• The solution is an OS designed to support multitasking. This will:
– Maintains a table of all running processes;
– Mediates every process break, deciding what to do next (this is called process scheduling).;
– Controls which process gets to access which I/O devices at any given time;
– Controls access to physical memory with the help of a hardware device capable of translating outgoing addresses (a memory management unit or MMU).
• Process control is the most fundamental service provided by any multitasking OS.
– Implemented by the most central code in the OS, called the kernel.
Systems and Networks 9. Operating Systems 6
Multitasking on one CPU
• At any moment in time, a CPU is executing just one instruction!
– This belongs either to one of the processes, or to the operating system
– One process is running, the others are waiting.
• CPU switches execution between the processes rapidly (e.g 100 times per second)
• From a user point of view a computer can seem to be running several applications at the same time.
• From the CPU’s point of view however the hardware is executing only one instruction at a time but it rapidly context switches between processes so all get a fair allocation of time.
• In summary a process in a multitasking system will always be in one of the following states (see slide 5)
– Running: at this very instant, the digital circuitry in the computer is executing an instruction belonging to the process
– Blocked: the process is waiting for I/O
– Ready: the process is not waiting for I/O and is ready to run; however, the it must wait
because the CPU is doing something else.
Systems and Networks 9. Operating Systems 7
Concurrency and Parallelism
• Several processes run concurrently when all make progress on user’s time scale.
• Processes run in parallel when their instructions execute truly simultaneously on
separate CUs and EUs.
• Concurrency is a generic term which includes parallelism as a special case.
– When a single CPU multitasks by context switching this is concurrency but not parallelism
• Parallelism requires multiple control units and execution units.
– Many modern microprocessors have multiple cores: these are essentially multiple CPUs on one chip, sharing the same bus interfaces, and can genuinely execute processes in parallel.
– Somewhat confusingly, with a multicore chip, the whole chip is called a CPU, even though it is actually a collection of CPUs (called cores) on one die.
– An individual core can itself context-switch multiple processes concurrently (i.e. not truly in parallel).
– More powerful machines may have several CPUs, each with multiple cores.
• The number of processes running concurrently in a typical OS is usually larger than the number of cores available so a combination of true parallelism and context switching on each core is used together.
Systems and Networks 9. Operating Systems 8
Co-operative & Pre-emptive Scheduling
• Context switching can be achieved without timer hardware (co-operative scheduling) but this makes the programmer’s job much harder.
– Applications must be written to process break voluntarily, giving up control to the OS at regular intervals.
– This is programmed into the app using a TRAP instruction with appropriate parameter.
– If an app fails to process break, it has all machine resources: other processes are starved.
– Co-operative scheduling needs no extra hardware.
– This was used in Classic MacOS and (for 16-bit applications) in the Windows 9x systems that ran over MSDOS before Windows NT (the first version of modern Windows).
• The timer based approach is called pre-emptive scheduling.
– Hardware & OS enforce a policy of regular process breaks (e.g. once every 10ms).
– These is provided via an external hardware timer with an interrupt line to the CPU.
– On interrupt the CPU stops the process it is executing and jumps to a special interrupt handler routine which is part of the OS and which now decides what to do.
– The handler for the timer interrupt is called the process scheduler (part of the kernel).
– The process scheduler uses a scheduling algorithm to choose which process goes next if
more than one is ready to run (this may include some concept of process priorities).
– No process gets more time than the period of the timer (the time slice).
Systems and Networks 9. Operating Systems 9
Input and Output
• Data (and machine code) in primary memory has to be moved there from an input peripheral (e.g a keyboard, disk) or another computer (via a network).
• Results in primary memory can’t stay there forever and must be moved to an output peripheral (e.g a screen, printer, disk) or to other computers over a network.
• Input and output (collectively I/O) therefore involves the movement of binary codewords from/to external input or output peripherals.
• Disks (secondary storage) are both input and output devices.
• Internal disks are often thought of as part of a computer and this is physically true but they are outside the CPU/primary memory/bus structure so in this discussion we will consider them to be (external) I/O peripherals.
• I/O peripherals are connected by wires (or wirelessly) to devices in the computer called (hardware) ports. A port may be an input port, an output port or both.
• Ports are subsystems (often on their own chips) which, like memory, are attached to the address and data buses and contain some internal registers.
• Usually these registers appear at fixed locations (chosen by the computer design engineers) in areas of the CPU’s normal physical address space not populated by memory and are accessed by usual CPU load and store operations. They are then said to be memory mapped.
Systems and Networks 9. Operating Systems 10
Ports and I/O
• At least one register in each port will be a data register.
• If the CPU stores data in an output port’s data register, the port will send the word to any output
peripheral attached to it.
– Typically an output peripheral will not accept a data word from its port until it is ready (remember peripherals are usually very slow compared to the CPU).
– The CPU must not write to the port data register again until the device has accepted the word or the data will be lost (overwritten before it was properly output).
• Data from an input peripheral will appear in the peripherals port data register and then can be read by the CPU (and moved to a memory location).
– In this case the CPU must read the data before the input device sends more or it will be lost.
– But it must be careful not to read the same word twice or data will be duplicated
• Ports also contain control registers that may be used for configuration and status reporting.
– A configuration control register will be written to by the CPU, usually before any I/O starts.
– The bits in a status register are set or reset by the port’s own hardware to indicate that something has happened.
– The exact uses of control registers vary with the port design (manual for the exact design must usually be consulted.
• The most important status bit is the ready flag
– Typically this is set (1) when a new word has appeared in the data register (input port) or the last word
written to the data register has been accepted by the peripheral (output port)
– The ready flag is then automatically reset (to 0) by the port when the CPU reads its data register (input port) or writes to its data register (output port).
Systems and Networks 9. Operating Systems 11
Synchronous and Asynchronous I/O
• If there is no OS or an OS without multitasking a process may do it’s own I/O directly. This must be written by the programmer.
• When there is a multitasking OS in place, a process will usually not be allowed to access ports directly. All I/O requests must instead go through the OS.
• Most I/O devices are slow, so a process doing I/O will have to wait for it to complete.
• Suppose a process needs to do I/O and cannot do anything useful until that completes. Such I/O is called synchronous.
– If the process is handling its own I/O (no multitasking OS) it may wait by looping and polling the port (repeatedly reading the ready flag). This is called a busy wait.
– If there is a multitasking OS, the process will be blocked when it asks for I/O.
• Alternatively, if a process has other useful work to do, it can be notified by a (port) interrupt when a request completes. This causes the CPU to jump to an interrupt handler. This is asynchronous I/O.
– If the process is handling its own I/O, the programmer must write the interrupt handler.
– If a multitasking OS is handling the I/O, the interrupt handler will be in the OS. The OS may then let the process finish its time slice and will notify it when the I/O is complete.
Systems and Networks 9. Operating Systems 12
OS-controlled I/O
• OS-control relieves application processes (and programmer!) of responsibility for directly accessing I/O devices and ensures that each device is shared properly between applications.
• Some I/O devices can be shared between several applications at once (e.g. disk, screen); others can only service one at a time (e.g. printer, keyboard) and the OS must form and manage a queue of processes when necessary.
• Under OS control, application will normally access a device via OS calls. These are usually implemented at low level by special instructions often called TRAP or Software Interrupt. OS calls requesting I/O are translated into physical access by an OS routine called a device driver. There will be a different device driver for each type of attached peripheral.
• When a process asks the OS to do I/O for it, it may suspended (blocked) by the OS (synchronous I/O) or it may be allowed to carry on running until there is a timer interrupt (asynchronous I/O). In asynchronous I/O, the OS will notify the process when the I/O completes.
• Programs using asynchronous I/O are more complex to write because they must be able to receive notifications from the OS while running. This requires the OS to support (and programmer to use) a signalling system to allow it to send notifications to processes (beyond the scope of this course).
Systems and Networks 9. Operating Systems 13
Interrupts
• A hardware interrupt allows an external hardware device to indicate to a CPU that it should perform a process break and jump to an interrupt handler.
– Carried from I/O port or timer to CPU by an interrupt line.
– They are initiated by hardware so can occur at any time but CPU always finishes the
instruction it is processing before jumping to the handler.
• When an interrupt occurs the CPU goes to the handler routine for that interrupt, prepared in advance, which it begins executing.
– If a process is doing its own I/O, a return address must be saved so that the CPU can return to the interrupted process when the handler has completed (c.f. a subroutine). An interrupt is only supposed to suspend a process not terminate it. The programmer writes the handler and must ensure it returns correctly.
– In OS-controlled interrupts the OS decides what to do next and may not return control to the process immediately. Handlers are part of the OS code, not part of the process.
– All registers in the programmer’s model are saved when an interrupt handler is called and these are restored when it finishes. Why just the programmer’s model?
• Hardware interrupts are not initiated by the CPU itself. They come from either I/O ports or other devices like the system timer.
• Most CPUs allow interrupts to be masked (ignored) temporarily when critical code that should not be interrupted is running. This is usually done by a special instruction.
Systems and Networks 9. Operating Systems 14