Operating Systems Notes

1. What is an OS (P5)
• An OS is a layer of software which separates application software from the hardware,
and is responsible for system security and allowing multi-tasking.
• Some OSs are multi-user, allowing a machine to be used simultaneously by multiple
people.

1.1 Resources (P5)

• Resource management is one of the most important roles of an OS, which has to
manage resource usage amongst competing processes.
• Resources include CPU time, memory, files and interfaces (I/O).
• An OS should keep track of which resources are used by which process and ensure that
they are made available again when the process terminates.
• The OS should keep count of the number of links to shared memory and should
deallocate the memory when the last process using it terminates.
• Some resources are preemptable, they can be reassigned to another process before
the first process has finished with it, e.g. the CPU, whereas non-preemptable resources
must be finished with first, e.g. a printer half way through a job.

1.2 Virtualisation (P4)

• An OS aims to create a virtual environment for applications to run so that they do not
need to be concerned about other running applications, this is achieved using virtual
memory and timesharing of processors.
• Some modern systems introduce a hypervisor layer so that separate processes may
use resources, such as the filesystem, as if they were private resources.

2. Memory (P3)
• Computers hold data in a memory which is a large array of equal-sized storage spaces,
usually each holding bytes. Each location has an address, with which its contents can
be retrieved.
• Most computer memory can be written to so can be used to store variables, software
variable names are aliases for addresses.
• Most memory is Random Access Memory (RAM), meaning that all addresses can be
accessed at the same speed and at any time.

2.1 Memory Sizes (P3)

• The size of the virtual address space is fixed by the architecture of the processor and is
a power of two.
• Physical memory size is governed by technology and economics, as the price per bit of
memory has decreased, feasible memory sizes have expanded in line with Moore’s
Law.
 • In the past, new architectures have appeared, supporting new address sizes that are
larger than people can make use of, then as time goes by people can afford to use it
all, leading to the development of a new architecture.

2.2 Arrays (P1)

• In C arrays are pointers to locations in memory.
• When the array is declared the required memory is allocated.
• When indexing array items the compiler adds the the correct offset to the array
address to access the correct value.
• It is possible to get the address of individual array items,
e.g. pointer = &(array[2]).

2.3 Structures (P2)

• In C a structure is an element that contains a set of variables, similar to Java objects
but simpler and without instance methods.
• Similar data structures may be known as records.

2.4 Pointers (P4)

• A pointer is a variable that stores a memory address.
• It is standard practice to use NULL (or 0) to signify unset or invalid pointer.
• Pointers can be used to access arrays of data by using an offset to a pointer to the start
of the array.

3. Memory Management (P4)

• Any running process requires one or more logical memory segments, these are
contiguous parts of the address space.
• Some of this space can be allocated by the OS when a process runs whilst some must
be allocated dynamically, in most processes the memory use falls into five sections:
o Code – the executable binary – fixed size and read only.
o Read-only data – strings, tables, etc – fixed size and read only.
o Static data – global variables – fixed size and read/write.
o Stack – local variables – dynamic size and read/write.
o Heap – run time structures – dynamic and read/write.
• The application can take some responsibility for dynamic memory allocation by
requesting large blocks of data that it then allocates from, but these blocks must first
come from the OS, which is ultimately responsible for memory management.
• The OS can keep records of which memory is in use and in a virtual memory
environment can track which physical pages are being used by what.
• The OS may also need to manage access permissions, allocate additional space if the
heap or stack overflows and retrieve memory when a process terminates.

3.1 Segmentation (P3)

• At times it may be useful to group areas of memory into a logical segment, which may
have a set of attributes associated with it, e.g. read-only.
 • Segments can be of an arbitrary size and are usually supported as dedicated parts of
memory which are mapped using hardware pages, though the OS may also keep track
of segments for page allocation purposes.

3.2 Memory Mapping (P5)

• In a virtual memory system each process uses its own set of virtual memory
addresses which are translated via a set of page tables to physical addresses.
• The mapping is done in hardware by a Memory Management Unit (MMU) which
stores the page tables in RAM.
• The OS is involved in setting up the translations.
• Addresses are not translated individually, they are organised into pages which share
a translation, keeping the size of the page tables manageable, every process has its
own set of page tables so that it can have its own set of virtual memory.
• The most significant bits of the virtual address define the page number and only the
page number is translated, the rest of the address works an offset to the start of the
page.
• Multiple virtual pages can be mapped to the same physical page but this is rarely
useful.
• Not every virtual page has an allocation in RAM, in which case it is marked as invalid.
• As the page tables would take up a lot of space if they were all held in memory at the
same time it is normal use a hierarchical structure of page tables.
• The first set of bits in a virtual address are used in a level 1 page table to get a pointer
to a next level page table where the next set of bits are used, this pattern continues
until the correct page address has been found, then the last bits are used to access
the memory within the page.
• Using this structure reduces the memory requirements per process as they only need
to store in memory the page tables that are being used, the rest can be paged to disk.
• As the process rarely uses memory spread across the entire range, using a tree
structure saves using unnecessarily large tables.
• The newest intel x86-64 architectures support up to 5 levels of page tables.

3.3 Dynamic Memory Allocation(P4)

• As the memory space is used by processes it may become fragmented over time,
with various gaps in the memory that are unused.
• Fragmentation can be alleviated by allocating fixed size blocks but this can be
wasteful or inconvenient when the programmer wants a larger block.
• When allocating memory the manager has several options:
o Allocate from the largest block – quick but increases fragmentation.
o Choose any hole that is large enough – requires more searching but leaves
large blocks for later use.
o Find the smallest hole that is large enough – requires extensive searching and
may leave tiny holes that cannot be used but does decrease fragmentation.
• Some modern OSs randomise the allocation somewhat as a security feature to make
it difficult for attackers to predict memory allocations.
 • Memory should be freed when it is no longer in use, failure to do so can lead to
memory leaks which can crash a system, environments like Java use garbage
collection to do this automatically, whereas in C it is up to the programmer to free
unwanted memory.

3.4 Memory Leak (P1)

• When dynamically allocated memory is not freed when it is no longer in use it is
referred to as a memory leak and is usually caused by poor programming practice.
• Memory leaks increase a processes memory footprint and can slow it down as it
results in extra paging, it can also cause crashes in the process and others, including
the OS, if all available memory is used.
• Unix tracks the memory resources allocated to every process and can claim every
resource when the process terminates.

3.5 Shared Memory (P2)

• Some memory can be shared between multiple process, in a memory mapped
system, this requires OS support and is achieved by mapping a portion of the virtual
address in each process to the same physical address space.
• Shared memory can be used to facilitate IPC, though there must be some software
protocol used by each process to control the data flow.
• Commonly used library routines can be held in memory that is shared between
processes that call the routine.

4. Caching (P3)
• Caches monitor outgoing memory requests and if it recognises the address it will
intercept the request and respond to it locally.
• A cache miss refers to a request that cannot be satisfied by the cache.
• Caches rely on temporal locality – if something was used recently it will probably be
used again, and spatial locality – if one address is used then nearby addresses will
probably be used, these principles form the basis for algorithms such as least recently
used (LRU) to decide what to keep in the cache.

4.1 Cache (P2)

• A memory cache is a small, fast memory that is close to the processor, used to
increase performance, high performance machines often have multiple caches, going
from a level one cache upwards, lower level caches are smaller but faster.
• Typically, a level one cache uses virtual addresses and is therefore a virtual cache,
after a context switch the cache becomes invalid and has to be flushed by the
operating system.
• Higher level caches often use physical addresses so may retain their contents through
multiple context switches.
• It is the role of the OS scheduler to keep track of any caches that need to be flushed.
 • A shared-memory multiprocessor will have separate level one caches for data and
instructions for each processor and a level two cache for each processor, all the
processors then share the level three cache.

4.2 Cacheability (P2)

• Something is cacheable if it is appropriate to store it in a cache, memory mapped I/O
devices are likely to change autonomously so should not be cached, nor should
shared areas of memory.
• Cacheability is often a property held in page table entries.

4.3 Dirty Bit (P2)

• Typically used in caching, a dirty bit is used to indicate that a change has taken place.
• When a cache is about to be flushed the dirty bit is checked, if the cache is clean it
can be dropped, else the entry must be copied down the memory hierarchy.

5. Virtual Memory (P5)

• An OS is responsible for allowing processes to view and use memory as if they are the
only running process, this is achieved by creating a virtual address space for each
process that is mapped by the OS to physical memory.
• Mappings are done in terms of pages, usually 4KiB, where one page of virtual
memory is mapped to a contiguous page of physical memory.
• When processes use more virtual space than there is physical space then pages may
be copied to a “swap” space on disk, this is time consuming but allows everything to
keep running.
• The size of the virtual address space is defined by the hardware architecture. A 64-bit
machine can address 264 bytes.
• Memory protections are implemented to stop processes accessing each others
memory, and is usually supported by the memory management unit in hardware.

5.1 Memory Pages (P4)

• A page is a division of the virtual memory system, in Windows a page is 4KiB, where
each byte has a separate address.
• As a page is an indivisible block the OS allocates memory to processes in pages,
therefore if it needs only 1KiB it will still be allocated a whole page (4KiB).
• The 12 least significant bits of a virtual address act as an offset from the start of the
page, whilst the rest of the address is used to select the page.
• Pages can be arbitrarily swapped or paged.
• Some systems support varied size pages sizes, though they are all 2N bytes in size so
that they can work together.

5.2 Paging (P4)

• A virtual memory system will typically divide its memory into pages of a fixed size,
these can then be mapped to any page frame.
 • Pages that are not currently being used by the processor may be stored in a swap
space on disk.
• The processor produces a virtual address, which the MMU uses to look up a page
reference and get the physical address so that the memory can be accessed.
• If the page is not resident in memory the MMU raises a page fault and the OS
intervenes.
• When the OS handles such a page fault it first selects a page to evict, copying any
changes made to it to disk, and then loads the required page into the page frame,
updating the page tables at the same time.
• Loading pages as required is referred to as demand paging.
• Sometimes a process may raise a page fault when first requesting access to an item
that is already in another processes virtual address space, e.g. application code, the
OS can spot this and share the page between the two processes.

5.3 Page Eviction (P3)

• When a new page needs to be loaded into memory then an old one usually needs to
be evicted, there are several different algorithms for selecting which page:
o Random – choose a random page, simple and works surprisingly well.
o First-In, First-Out (FIFO) – the page which has been in memory the longest is
replaced, usually implemented using a FIFO queue to list the pages in memory.
o Least Recently Used (LRU) – the page which was last used is replaced, this is very
effective but complicated as references need to be stored chronologically and
must be supported by hardware.
• Sophisticated OSs and some modern hardware collect data about system use to help
select pages to evict.
• Before a page can be evicted it must be made up to date by flushing the caches that
reference the page.
• Some pages may be pinned so that they cannot be evicted, such as the pages
containing interrupt service routines which require low latency, pages holding disk
drivers and pages in use for DMA.
• A paging daemon is a background task that makes page eviction quicker by cleaning
pages (synchronising their contents with disk) and sorting them during less busy
periods.

5.4 Page Monitoring (P1)

• Pages can be monitored to collect data which aids with page eviction selection.
• Read only pages may be preferable to evict as they have not been modified, one way
to check if a page is read from is make it read only on fetch, if it is written to this will
raise a page fault, at which point the handler can set it to be read/write.

5.5 Trashing
• Trashing occurs during caching when the working set exceeds the physical capacity of
the system.
6. Memory Protection (P3)
• It is often useful to protect memory from being accessed by other pages, this can be
done using memory mapping to hide memory that a process shouldn’t be able to see,
however any user needs to be able to interact with OS services.
• Access permissions can be assigned to pages which can be checked during memory
access, if there is a breach of permission based on the address, action and processor
privilege then a hardware exception can be raised to invoke the OS to deal with it.
• The access permissions are specified by the MMU may include:
o No access – can be used when a page should not be accessed and can trigger a
segmentation fault, or could be used if the page does not yet exist in physical
memory, in which case a page fault is invoked.
o Supervior read-only – used to protect OS code from being viewed by a user
process.
o Supervisor read/write – used to protect OS data, such as passwords.
o Read-only – used to protect instruction code from accidentally being overwritten.
o Read/write – normal permissions for user pages, usually not accessed by the OS.

6.1 Processor Privilege (P4)

• OS protections can be facilitated by hardware support in the processor, modern
processors have different levels of privilege, usually at least a user and supervisor
mode.
• The supervisor mode can do anything, whereas the user mode forbids certain
actions, including changing the mode.
• The mode can be viewed by the hardware and is used to decide if an operation can
be carried out.
• The kernel of an OS is often defined by what can only be done in supervisor mode.
• Privilege is monitored in hardware, so it it does not affect normal application process
until the process misbehaves or asks the OS to do something it can’t.
• Access permission to memory is often defined in page table entries, the memory
containing page tables is also protected.
• Interrupt status can only be modified in privileged mode as the ISRs are part of the
OS and should not be turned on or off by the user.
• Sufficient protection can be provided using just these two modes but some systems
add additional levels, such as ARMs TrustZone which allows trusted access to some
resources by user-mode applications.

6.2 Memory Fault (P4)

• A memory fault occurs when an exception is raised during a memory access, there
are a few typical causes:
o Privilege violation – e.g. the user trying to access kernel space.
o Page faults – when there is no physical memory at the virtual address.
o The operation has stalled and timed out – usually associated with I/O.
o Memory corruption detected.
 • Memory faults can occur in various stages of the memory cycle and are caught by the
OS which then deals with it, solutions include:
o Segmentation fault – terminate the process.
o Page fault – fetch the page from disk and return to retry the operation.
o I/O routine – return to the software to deal with it.
o Memory corruption – system dependent, may be able to recover data, else
terminate process.

6.3 Superuser (P2)

• A superuser is able to attain privileges that are not available to ordinary users.
• Superusers have different names in different systems, such as root or admin.
• The superuser is a software concept but may allow the execution of programs with
supervisor privilege on the hardware.
• Superuser status should only be used when absolutely necessary to avoid accidental
misuse.
• Superusers may change file permissions and ownership, which may allow them to
limit access to I/O ports to other users.

6.4 Memory Management Unit (MMU) (P3)

• The Memory Management Unit (MMU) is a hardware unit that performs the
mapping of virtual to physical addresses and checks the processor privilege level
against the permission of the memory being accessed.
• MMUs also help prevent the caching of volatile memory regions, such as I/O
peripheral areas, which are liable to change independent of the processor.
• An MMU takes a virtual address, an operation – read/write and possibly size, and the
processors privilege level as input and returns a physical address and information,
e.g, cacheability, or returns a memory fault.
• The MMU usually works in parallel with the level one cache, which is keyed using
virtual addresses
• The actual page tables are usually stored in memory as they are quite large, however,
the Translation Look-aside Buffer (TLB) caches some commonly used page
translations locally.
• If there is an address miss then the MMU will stall the processor whilst it looks up the
reference before updating the TLB, this process is known as table walking.

6.5 Write Buffer (P2)

• It is often the case that writes are far less urgent than reads, as such it can be
practical to place writes in a buffer to be carried out at a less busy time.
• Write buffers are often used in paging when a page is evicted and replaced, usually
the OS keeps a couple of clean pages free to copy into, it can then copy the old page
to disk when it has time to spare.
• Write buffers are also commonly used for disk writes.
• If a process wants to read a value which has been written to the buffer then this must
be detected so that the data in the buffer can be forwarded to the reading process.
 • It is often possible to mark memory pages so that a write buffer is not used, this is
important when I/O is involved as it may not be clear that there is a dependency.
• Device drivers sometimes use barriers to ensure that write buffers are emptied
before a read operation is attempted.

6.6 Translation Look-aside Buffer (TLB) (P3)

• Most memory mapping systems contain a Translation Look-aside Buffer (TLB) which
is used to cache the mappings of page tables to physical addresses to avoid having to
look up the page tables in memory, which may require multiple memory accesses.
• The level one cache in most systems uses virtual addresses and as the TLB is only
required if there is a miss on the level one cache, the two are usually placed in
parallel so that the page address can be retrieved while the cache is checked.
• Even a small TLB is usually enough to accommodate the the page table entries for a
single application.
• The TLB can be left as it is until there is a change to the underlying page structure
which usually happens during a context switch, at which point is has to be flushed
and allowed to refill, incurring a performance penalty.

6.7 Memory Barrier (P2)

• A memory barriers is an instruction which ensures that all memory operation that
precede it have been completed before continuing.
• This is useful in processors where memory operations may be queued, buffered or
pipelined, especially when working with I/O devices which use different addresses for
input and output so the processor does not know to forward the correct value.
• Barriers can help with synchronisation within a given thread and when processes
communicate through RAM.

7. Interfaces

7.1 Libraries (P3)

• Libraries are collections of code, usually with a common theme, that provide useful
function for other applications to access and can usually be run entirely in user mode.
• Libraries can provide applications with an interface to a specific OS so the application
can be linked with the right library for the OS they are running on.
• Some libraries intermediate between the user/application and OS for efficiency, e.g.
when a malloc call is made in C the library may request more than the user from the
OS for use in the next malloc.
• Static libraries are incorporated into the application at compile time, this can
however lead to multiple copies of the same library code existing in memory,
however it does not require any OS support.
• Dynamic libraries are loaded when an application is run, this saves space and allows
for shared libraries in RAM, updates to the library do not require a recompilation of
all the applications that use it.
 • Dynamic loading involves having the application load the library and extract the
required contents, the OS may keep one copy open and share it among processes.
• Dynamic linking is an OS process, invoked by an application, which identifies the
required libraries and links the function addresses, the libraries are loaded and
integrated with little work from the application.
• Shared library code must be reentrant, relocatable and dynamically linked, the OS is
responsible for tracking how many processes are using the library.
• The most well known implementation of dynamic libraries is Windows’ Dynamic-Link
Library (DLL).

7.2 System Calls (P4)

• An OS provides a set of system calls, these are trusted functions that can be run in
supervisor privilege and provide a well defined interface for applications to interact
with hardware.
• Programs usually access system calls via language specific libraries which are
themselves untrusted but contain system calls.
• System calls may also be known as supervisor calls, software interrupts, traps or
breaks.
• Switches to a system call must be atomic, ensuring that switches in privilege level and
address space happen simultaneously.
• As system calls behave like normal functions, it is possible to nest system calls,
therefore the OS may end up making system calls.
• System calls may include filesystem access, IPC and resource management.

7.3 Man (P2)

• Man is the default manual page application in Unix and allows the user to access the
manual entries for installed software.
• Passing the name of an page to man will return the given page, pages exist for
applications, system calls, games and others.
• The man pages are stored in sections, the first of which is for applications, and when
man is called it will by default search the sections in a set order until it gets a result,
however one can specify which section to look in.

7.4 Shell (P2)

• The shell is an interface program that allows the user to give commands to the
computer, both Command Line Interface (CLI) and Graphical user Interface (GUI)
shells exist.
• The most common Unix shell is the GNU Bash shell.
• Shells load and maintain a set of environment variables.
• Usually when a shell executes a file it forks the application in a new process and then
waits for it to signal it has finished before resuming, this wait can be suppressed to
allow a shell to run multiple processes.
• It is possible to run multiple processes in a single command and link them by
redirecting standard streams through pipes.
7.5 Environment Variables (P3)
• Processes run within an environment supported by the OS, which provides
environment variables, a mapping of names to string values.
• Environment variables can act as a form of interprocess communication, though they
are used more like additional arguments to be passed to child processes.
• Some environment variables are held by the shell and it is easy to add more as the
shell initialises from a config file, .bashrc in bash.
• In bash an environment variable is referenced by prepending $ to the variable name,
variables are initialised as an empty string, bash also uses special symbols for some
variable names, such as $ for the current bash process id.
• When a process forks a child process it does not automatically inherit the variables
unless they had previously been marked for export.
• Significant variables used within Unix/bash include:
o PATH – the list of directories to search for a program.
o HOME – the users home directory.
o SHELL – the users default shell.
o PWD – the present working directory, bash specific.
o RANDOM – always gives a random integer value, bash specific.
o LINES and COLUMNS – the number of lines and columns in the terminal bash is
running in, bash specific.
o MANPATH – the list of directories to search for man page entries.
o EDITOR – used by some applications which load a text editor, e.g. less.
o LANG – defines part of the users locale.
o HOSTNAME – the name of the current host, bash specific.
• Some programs may use a startup script to set their own local user parameters
before launching the main program.

7.6 Errors (P2)

• Sometimes a process may cause an error, such as asking for too much memory, when
this happens the OS will handle the error and then return control to the process so
that it can respond and possibly adapt.
• Sometimes a process that causes an error may have to communicate with child
processes so that they can also respond, such as when a user shuts a window the
program may want all the windows to close.
• As part of the response to an error a program should tidy up by freeing any resources
or shared memory it has, as shared memory does not belong to one process the OS
does not know to claim it until explicitly told.
• When Unix system calls fail a diagnostic code is returned, in C this is readable as the
global value errno.
• In Unix exiting a program is a form of error, exit() does not return but closes owned
file descriptors and allows resource recovery, it also sends a signal (SIGCHLD) to its
parent to say that has terminated, with a value of 0 if it terminated normally, else any
other value.
• If a process closes without signalling its child processes to end then they are
orphaned and inherited by the init process.
8. Exceptions (P5)
• Exceptions are circumstances which are outside the normal flow of operations, such
as an index out of bounds exception.
• The OS is capable of generating exceptions but most come from hardware and are
then usually handled by the OS.
• An exception acts as a call to the processor, causing it to call a subroutine, the call
also raises the privilege of the processor so that it can deal with the hardware.
• Protections should exist so that processes cannot abuse exception handling.
• During the subroutine the processor can determine the cause of the exception and
attempt remedial action, either fixing and returning to the user code or else
scheduling some other action.
• The exception handler can sometimes send a signal to communicate the information
back to the user process, allowing them to sometimes register their own signal
handlers for some exceptions.

8.1 Reset (P2)

• Reset is the highest priority exception in a system and is invoked by hardware, it is
not expected to return and is used to initiate a boot process.
• The reset hardware will generally leave the processor in a well-defined but limited
state:
o The highest privilege level will be set.
o All interrupts will be disabled.
o Memory mapping will be turned off.
o Caches will be disabled, invalidating any cached data.
• Code will then be run from an address specified by the processor architecture.
• It is up to the OS to initialise various facilities before they are enabled.
• In embedded systems the reset may be the result of a problem, e.g. a watchdog
reset, requiring a recovery process before the boot process.
• Some processor architectures boot into modes that emulate earlier architectures, the
boot process may need to alter this before starting the boot process.

8.2 Boot (P2)

• The booting process encompasses everything from the reset to the normal operation.
• In simple devices, such as embedded controllers, all the software may be present in a
non-volatile store and the program can just run.
• In more complex systems the boot sequence consists of several stages, that are
chained together, the process in a typical PC is as follows:
o Execution starts from a small preset address to some non-volatile memory which
holds the BIOS, the BIOS may perform some system checks and see how much
RAM is available.
o The BIOS will have a basic ability to read and execute code from a backing store
and will have a list of possible boot sources, as well as the ability to check for a
‘plug-in’ device such as a disk or live USB.
 o In x86 systems the first sector of a disk contains a Master Boot Record (MBR)
which is read and then executed if it is valid, the MBR is only 512 bytes so is quite
simple. More modern systems use alternatives to MBR but work in a similar
manner.
o The second stage boot loaded by the MBR may perform more extensive system
checks and is able to load the OS, it may also give the user some options.
o A final stage will then load and start the OS, it may do further system tests, e.g.
checking the hardware configuration so it can load the correct drivers, finally it
will run an application such as a shell or window system.

8.3 Emulator Trap (P1)

• A processor may throw a hardware exception when it tries to execute an instruction
it does not recognise, likely to be due to an outdated/budget processor or if the
program has crashed and is no longer executing code.
• If it is the latter then the best action is to terminate the process, otherwise a service
and return may be provided, this allows the processor to execute a model of the
instruction in software.
• Software emulation allows old processors to run newer code, though there is a
significant performance penalty.
• This can also be used to see of certain instruction classes are being used by the
running process by deliberately disabling them.

9. Processes (P5)
• A running program is associated with a set of values, such as the owner and used
resources, the program with these values is referred to as a process.
• Most OSs allow multiple processes to run at the same time without interfering with
each other, even if they are running the same program.
• Most of a processes context will be held in memory and each process will have some
address space which it can use to store variables and code.
• The OS will store the data about a process in a PCB.
• A process will rarely run continuously, it may get blocked, e.g. waiting for a key press,
or may get set aside so another process can run.
• In Unix, each process has a parent, at boot the first process forks the init process and
then becomes the idle process, the init process goes on to create all child processes.
• The processes parent is held in the PCB.
• If a parent process terminates before its children then the children are orphaned and
adopted by the init process.
• Sometimes a process terminates without the parent being informed, causing the the
parent process to continue holding data about the zombie process until the OS
synchronises with it, this situation is usually the result of a program error.
9.1 Process States (P5)
• Processes can exist in different states to facilitate multi-tasking, a process can be
blocked, ready or running.
• A running process is a process that is currently being executed by a processor, it may
yield execution or be forced to by the OS, in which case it becomes ready,
alternatively, it may become blocked when it is waiting for an I/O resource.
• A ready process is a process that is waiting for a chance to use the processor, it will
switch to running when scheduled by the OS.
• A blocked process is waiting for an external event to take place before becoming
ready, such as I/O input or availability or if it has put itself to sleep.
• It is important that each I/O resource be owned by a single blocked process.
• A process can be terminated by an external influence when it is in any state.
• Any number of processes can be ready at a time, they will be put into a queue and
allocated time-slices by the scheduler, any number of processes can be blocked at a
time.
• The number or running processes is limited to the number of cores available.

9.2 Idle (P1)

• Some modern processors have a sleep type instruction that puts the processor into a
low power mode until an interrupt is requested.
• The idle process is used to occupy a processor whilst waiting for processes to become
ready to use the processor, in a real time system it may be run continuously at a low
priority.
• The idle process may sometimes log its start and stop times for use as a CPU usage
metric.

9.3 Sleep (P1)

• In Unix sleep refers to a process that is blocked for a set period of time.
• In hardware there is usually only one clock, so the OS may keep a linked list of the
processes that need waking in chronological order, with a link to the first item to
wakeup.
• When the time is reached the OS will then signal the first process to wake up before
unlinking it from the list.

9.4 Daemons (P1)

• A daemon is a background process that provide useful services and which are not
responsible to any user or process.
• An example is cron, a Unix job scheduler used to run other processes at regular
intervals (e.g. making a file backup in the morning every day)

9.5 Unix Signals (P2)

• In Unix a signal signifies to a program that an event has occurred and may be used in
synchronisation or error detection.
• Programs can be setup to perform certain actions when signals are detected.
 • Some Linux signals include:
o SIGINT – received after keyboard input.
o SIGSEGV – received when a user tries to access invalid memory.
o SIGKILL – received when the OS is trying to kill the process.
• The kill command is able to send specific signals to a processes.

9.6 Threads (P3)

• A thread is a sequence of executed machine instructions, each thread belongs to a
process and a process may have multiple threads but must have at least one.
• Threads within one process share most of the context but may have their own stack
and local variables, threads also share the process memory map and resources.
• Switching threads is significantly faster than switching processes as there is less
context to switch, it is also easier to create/destroy threads than processes.
• Threads can be managed by the OS scheduler, an application scheduler or both, each
thread exists in a ready, running or blocked state.
• User controlled thread switching is often faster than OS thread switching but usually
relies on cooperative scheduling, if threads hang then this can cause the application
to crash.
• User level thread management also requires management software, usually in the
form of a library.

9.7 Multi-Threading (P3)

• Multi-threading refers to running multiple process or threads at the same time on
one machine.
• Splitting code into separate threads can make it easier to understand when the same
piece of code has to fulfil several functions.
• The timing of functions is unpredictable in a sequential piece of code, putting them in
an order may not be as efficient as letting the scheduler run them as separate
threads.
• Parallel code with unknown timings is referred to as asynchronous code.
• As CPU cores are becoming more common on chip, it is often more efficient to use
multiple threads to exploit the multiple cores.
• Writing multi-threaded code is more difficult than normal code and often leads to
faults, especially when there are dependencies between the threads, it often
becomes necessary to synchronise them to avoid deadlock.

9. 8 Synchronisation (P4)
• When multiple threads/processes are running, the schedule of their execution may
be unpredictable leading to asynchronous execution.
• When threads and processes interact it is necessary to synchronise them in order to
avoid race conditions and other errors, there are numerous approaches to
synchronisation:
o Barrier – a counter in shared memory is initialised to the number of relevant
threads/processes, then when each reaches a certain point it atomically
 decrements the counter and then blocks until the counter reaches 0, at which
point all the threads are signalled to unblock.
o Thread join – a form of barrier where two threads merge into one before
continuing.
o Mutual exclusion – used to provide atomicity of a section of code.
o Asynchronous message passing – one process sends messages to its counterpart,
though it may end up sending faster than the other can receive.
o Synchronous message passing – if a process reaches a message point before the
other it blocks and waits for the other process, after which the processes
exchange information before continuing, this is introduces some overhead but
allows two way message passing.
• In some cases the synchronisation is not between processors, e.g. when a DMA
transfer is ongoing the processors must avoid accessing the relevant memory.

9.9 Ordering (P2)

• When there are multiple processes/threads running it is impossible to predict the
ordering of operations, e.g. when two threads add a new item to a linked list the list
may be broken if both try to add the item at the same time.
• Such issues can be caused by context switches, interrupts or multi-core processing.
• A simple solution is lock the critical section so that only one process/thread can act at
a time on the item, however this introduces complexity in all processes/threads.
• if it is possible to make a section of code safe without locking then this is generally
preferred, this should usually be well commented.
• Some compilers reorder code to optimise execution speed, this feature can usually
be disabled for a critical section.

9.10 Context (P4)

• An executing process has a context which is mostly kept in the main memory.
• Each process has its own Process Control Block (PCB) which is used to hold
information between process switches.
• Context includes: state held within the memory (e.g. register values), the memory
management page tables, a list of resources owned by the process and any specific
cached information.

9.11 Process Control Block (PCB) (P2)

• The Process Control Block (PCB) holds the information about a process, including its
identifier (PID in Unix) and priority.
• PCBs are used to store the state of a process between context switches, so they
usually have space for the register values and pointers to the lists of used memory,
file, and I/O resources, where these lists are large they may be formed of linked
blocks.
• Some PCB implementations contain a pointer to the next PCB so that they can be
used to form linked lists, useful for queuing processes.
9.12 Context Switching (P3)
• When there are multiple processes running on a system then at some point the
running process will be evicted from the processor to allow another process to run.
• When this change occurs it is called a context switch and is managed by the
scheduler.
• During a context switch, all information held in the hardware, such as registers, will
be stored to the PCB, the scheduler will then choose a new process and load its state
from the new processes PCB.
• There may also be cached information from the old process that needs to be flushed
to memory so that the new process can start its caching.
• Usually page tables are held in memory for different processes and when each is run
the page table base pointer is set to point to the tables for the running process, when
this happens the TLB needs to be flushed and allowed to reload as the process runs.
• If a process terminates the OS needs to ensure that all resources owned by the
process are reclaimed, including memory, I/O devices and files.
• Any caches specific to the process become obsolete after a context switch so have to
be flushed, possibly leading to the data being copied down the memory hierarchy,
this will be the case with any cache that used virtual addresses.
• Switching thread within the same process is often confined to just changing the
register state held in the processor, making thread switches within the same process
relatively cheap as all the threads share the same view of memory and have access to
the same resources.

9.13 Locks (P4)

• It is sometimes useful to ensure atomicity of code, e.g. entering/exiting system calls,
the software may request a lock before entering the critical section of code, if the
lock is unavailable the process can either keep polling it or block – allowing another
process to run.
• There are many different locking mechanisms, a mutex is a one-at-a-time permission
mechanism, whilst a semaphore is allows a set number of thread into a critical
section.
• Some processors implement the ability to lock operations so that other cores do not
interfere between the read and write stages of an operation, this forms the basis of
many software mutual exclusion mechanisms.
• Locks come with an implementation overhead, one alternative is to use transactions,
where operations are allowed to fail if the information fetched at the beginning has
since become out of date.

9.13.1 Deadlock (P1)

• Deadlock is a situation where progress cannot be made, in this context it refers to
processes and is possible when two or more processes compete for a resource.
• There are ways to stop potential deadlocks, often using a mutex or semaphore.
9.13.2 Philosophers (P2)
• The dining philosophers problem is a scenario used to highlight the issue of deadlock.
• In the scenario multiple philosophers sit around a table with a plate of food in front
of them and one fork between each pair of neighbouring philosophers, each
philosopher requires two forks to start eating.
• When the scenario starts, each philosopher pauses for an unknown period before
trying to pick up the adjacent forks, one after the other, and start eating.
• If left to run randomly then the philosophers will eventually deadlock, with each
holding one fork.
• There are several solutions to the problem, including using a waiter and numbering
the forks.

9.13.3 Starvation (P1)

• A process becomes starved when it is not able to progress as it is not given access to
the resource it needs, usually because another resource is in use.
• In an interactive system, low priority processes may become starved of CPU time, to
avoid this the OS may “age” them by raising their priority over time, starvation
should not occur in a real-time system, otherwise it is being given too much to
process.

9.13.4 Race Conditions (P4)

• In a multi-core system there is a risk of a race-condition, where multiple processes try
to access the same area of memory at the same time.
• Race conditions can be avoided by guarding critical sections of code with mutual
exclusion elements, which are often provided by the OS.
• “Time of check to time of use” or TOCTOU is a term to refer to bugs caused by race
conditions when a value is checked to see if an operation should take place but the
value is changed in between the check and the operation.

9.13.5 Atomicity (P3)

• Atomicity refers to a set of actions that have to happen together, this is often a
requirement to stop programs interfering with each other, e.g. when two programs
edit the same memory location, each must atomically load and change the value.
• In a single processor system, disabling interrupts is usually enough to ensure
atomicity.
• In a multiple processor system a lock is needed to stop a thread entering a critical
section when it is dangerous.

9.13.6 Signal and Wait (P3)

• It is common for a process to become blocked until an external event has taken
place, at which point a wait call (P) will be made, when a process already in the
critical section completes it a signal call (V) will be made, which unblocks the waiting
process.
 • When a buffer is in use and is empty when a process tries to access it the process
may sleep until another process writes to it and signals the sleeping process – this is
known as a wakeup.
• Signal and wait calls can be implemented in various ways, with signals either only
going to waiting processes or going to all processes, the signal calls may also be
implemented as part of an ISR.

9.13.7 Semaphores (P3)

• A semaphore is a means of setting up access control.
• A semaphore is initialised as certain value, then when a process enters a critical
section it atomically decrements the value if it is greater than zero before
proceeding, once it has completed it atomically increments the value.
• If a process reaches a semaphore with a value of 0 then it will become blocked whilst
it waits for the semaphore to become available.
• This mechanism allows a number of processes into a critical section but does not
keep track of which processes, an initial value of 1 can be used to create a mutex.
• When multiple processes use multiple semaphores it is possible for deadlock to
occur.

9.13.8 Mutex (P3)

• Some operations have to be performed atomically when there are multiple processes
or threads running asynchronously, this requires a way of guaranteeing that only one
thread is in a particular section of code at a time.
• A software mutex is a Boolean flag that can be set to true by a thread when it enters
the critical section, at the end of the section it may be reset to false.
• If a thread reaches the critical section and finds the flag is already true then it can
continuously poll the flag until it becomes false, referred to as busy-wait, or it can
wait and let another process run.
• If a the wait approach is taken, then the process in the critical section must signal the
waiting process to continue when it resets the flag to false.
• The flag is usually held in shared memory and is accessed via a machine instruction
created for atomic access.
• The entry sequence – test and lock – must itself be atomic so that two processes do
not believe that they can proceed at the same time.

9.13.9 Process Priority (P3)

• When multiple processes are running on a system the scheduler needs to select
which process runs when, in simple systems each process gets the same access to the
processor using a simple round-robin algorithm.
• A period in which a process has access to a processor is called a time-slice.
• In more complex systems, processes can be assigned different levels of priority so
that some may be favoured over others, this may be useful when running intensive
background jobs that have little urgency.
• Priority can be set by the user or calculated dynamically, if a process blocks because
it uses I/O then it may be useful to raise its priority when the I/O is available.
 • Different strategies exist for running processes, in real-time systems the highest
priority process is usually the one to run, whereas in interactive systems the priority
may decided the length and frequency of time-slices.
• Sometimes a low priority task prevents the running of a higher priority task when
shared resources are involved, this is referred to as a priority inversion, e.g.:
o A high priority process, A, and a low priority process, B, use a mutex, as B usually
completes the critical section quickly it is allowed to block A.
o Whilst B is holding the mutex a medium priority process, C, becomes unblocked,
as it has higher priority than B it is scheduled to run.
o Process A cannot become unblocked until after C has completed and B has
released the mutex, thus causing a priority inversion.
• One solution to priority inversion is to increase the priority of any process that is
holding a resource that a higher priority process depends on so that they have the
same priority.

9.14 Scheduling (P4)

• In many systems there may appear to be multiple processes running at a time, but
the number of processes running at a time is limited to the number of available
cores.
• Scheduling is used to assign processors to processes such that they can be shared,
this is managed by the scheduler.
• Scheduling can be split into three main categories:
o Interactive processing – when all processes are given equal or similar access to a
processor, usually uses a round-robin approach with cooperative or time slicing
allocation, priority has some influence.
o Real-time processing – requires a minimum latency and relies heavily on process
priority to allocate the CPU to processes.
o Batch processing – often used in supercomputer/mainframe applications,
processes are allowed to complete before the next is started, a common approach
is to always choose the shortest available job to complete next.

9.15 Scheduler (P4)

• The scheduler in an OS is responsible for running processes to give the appearance of
multi-tasking.
• The scheduler is invoked when a process changes state, at which point it must select
the next process to run from the list of ready processes.
• There are three main types of scheduling:
o Cooperative – processes yield the processor when they are done.
o Time-sliced – each process is given the processor for a maximum amount of time,
after which another process gets the processor.
o Pre-emptive – a ready process takes control of the processor if it is currently held
by a lower priority process.
• Systems that use time-slices make use of a time-slice interrupt, which is supported by
the hardware, to invoke the scheduler.
 • In batch processing system a process will rarely be interrupted until it has completed,
thus the main role of the scheduler is to select the next process.
• Some schedulers look at the scheduling history of a process and use this to
dynamically assign priority.

9.15.1 Real Time (P3)

• Real-time systems are systems in which results are required with real-time
constraints, e.g. a flight control system.
• Real-time systems can be divided into hard and soft real-time systems.
• Hard real-time systems may fail catastrophically if they fail to meet their timing
constraints and are often safety-critical systems.
• Soft real-time systems will try to meet performance requirements but will not regard
it as critical, there is some elasticity in the timing, for example a video player may be
regarded as a soft real-time system.
• In a general system the average performance is important, whereas in a real-time
system the emphasis is on predictability and reducing the latency from input to
output.
• Real-time systems may not use a hardware memory cache and may instead manage
memory in software, this will reduce average performance but avoids the
unpredictable delays of paging to and from disk.
• Real-time systems tend to avoid time-slicing of processes and instead allow high
priority processes to pre-empt lower priority processes that are already running and
sort ready queues by priority.
• In a real-time system the required processing must be less than what the processor
can achieve.
• Many real-time systems are embedded systems and may contain features to
maintain reliability, such as crash-resistance and may contain a watchdog reset.

9.16 Watchdog (P1)

• Watchdog timers are often found in high-reliability real-time systems.
• They rely on a running process to tell a supervisory layer that everything is running
correctly, if it does not after a certain time period then something is assumed to have
gone wrong, leading the hardware to trigger a reset.

9.17 Multiprocessors (P2)

• Many modern computers have multiple hardware `cores’ meaning they can execute
more than one process at once, each with its own context.

10. Interprocess Communication (IPC) (P4)

• When multiple processes are running it is often useful for them to be able to
communicate, as each runs in its own context, some OS support is required.
• There are several ways to implement interprocess communication (IPC), each of
which may be more or less appropriate depending on the situation.
 • A common and simple method is to have some shared memory through which the
processes can pass data, as the process run asynchronously, some form of protocol is
required to ensure the correct passing of data, the protocol used is up to the
application.
• Some applications use files for IPC, this convenient for large quantities of data but is
inefficient for regular communications.
• Messages are blocks of data that are sent from one process to another, e.g. client
communicating with a web-server, in synchronous message passing there is
requirement for one process to listen while the other is sending, whereas
asynchronous message passing uses a buffer so there are fewer scheduling issues.
• Processes can raise signals, an asynchronous that is similar to an interrupt and that is
managed by the OS.
• In Unix systems a pipe is a FIFO structure where one process is able to write to the
pipe and another is able to read from it.
• A synchronisation barrier is a mechanism for ensuring that a single process or thread
does not get too far ahead of the others, a barrier is created in software that stops
further execution until all other threads/processes reach the same point.

10.1 Pipes (P3)

• In Unix a pipe is a method for passing a serial stream of data from one process to
another.
• A pipe is a FIFO queue with separate interfaces for inserting and removing data.
• Pipes can be used to direct the output of one process into the input of another by
linking them together from the terminal.
• Pipes can be given names so that they can be treated like files and accessed in
software, when a process opens a named pipe then other processes are blocked from
opening until it closes.
• In Unix processes have three standard I/O streams:
o stdin – the default input – usually the keyboard.
o stdout – the default output – usually the display/terminal.
o stderr – the diagnostic output – usually the display/terminal.
• These three streams are created when a process starts and are inherited from the
parent process.

10.2 Queues (P4)

• Within an OS there may be many different kinds of queue.
• Pipes make use of a First-In, First-Out queue, where the items are removed in the
same order that they were placed in the queue
• As moving all items forward every time an item is removed, most FIFOs use a cyclic
buffer with pointers to the head and tail of the queue, when an item is added the tail
moves, while the head moves when items are removed.
• If the FIFO is full then write operations will block, while read operations will block if it
is empty.
 • I/O buffers usually use a FIFO structure but may be moderated by hardware, either as
an ISR or DMA operation, they may also be done in blocks, e.g. when writing to a file
then blocks of data may be moved instead of individual characters.
• Ready processes are often queued by creating a linked list of the PCBs, which can be
used in a round-robin algorithm to schedule the next process by choosing the first
process and then un-linking it from the list.
• Different levels of priority may be implemented by adding processes to the list such
that the list is ordered by priority, or by maintaining different lists for different levels
of priority.
• Processes that have put themselves to sleep may be put into a linked list of
chronological order of when they need waking up, the OS clock will then have a
pointer to the first process which it can set ready when the time is reached.
• When processes are waiting for a lock they may be placed into a linked list ordered
by priority, with the highest priority process at the start of the list.
• A producer is defined as a process that puts items into a queue while a consumer is a
process that takes them out.

10.3 Spooling and Buffering (P1)

• A spooler is a device that accepts a series of job which it places into a queue, each job
may be checked for validity and edited by the spooler, spoolers are most commonly
associated with printers.
• Double buffering is a strategy employed when a buffer need to br read from and
written to at a time, one buffer is used to read from while another is written to, then
when the second buffer is full or the first is empty they are swapped over.
• Double buffering may be used in video application where the buffer being viewed
must be stable.

10.4 Sockets (P2)

• Sockets behave similarly to pipes but are more sophisticated and abstracted.
• Sockets are commonly used for IPC across a network.
• In Unix, sockets can be used to connect streams or datagrams.

10.5 Reentrancy (P1)

• A fragment of code is reentrant when it can be executed correctly multiple times
simultaneously.
• Reentrancy can usually be achieved by using local variables and avoiding changing
external state.
• Recursive code should usually be reentrant, as should most OS routines as they may
be called by multiple processes.

10.6 Relocation (P1)

• Code is relocatable when it can run successfully regardless of where it is positioned in
memory, this usually means using relative instead of fixed addresses.
• Most modern processors achieve relocatability quite easily, though some flags may
need to be set when code is compiled.
 • Attention needs to be paid to relocatability in simple systems without memory
mapping or when creating shared libraries.

11. Input and Output (I/O) (P5)

• It is the role of the OS to intermediate between peripheral devices and application
software as well as providing a sensible abstraction of the I/O resources.
• It may be useful for the OS to try to treat different devices in a similar manner, e.g. as
a serial stream of bytes.
• I/O devices can be virtual, such as when when a USB port is used by multiple devices.
• Devices can usually be divided into block devices – which handle data in welldefined
and fixed size blocks, e.g. disks, dvd, usb, and character devices – which use streams
of an indefinite length, e.g. keyboard, screen, printer, network.
• There are four layers in a software I/O stack:
o User-level processing – application code, the application is responsible for the
correct formatting of the data it wants to send/receive.
o Device-independent system calls – forces different devices to follow similar
interface conventions and helps applications interface with any hardware.
o Device driver – translates standard commands to communicate with the hardware
into the specific required sequences, drivers only support one or a few devices,
during initialisation it may communicate directly with the hardware.
o Interrupt handlers – handle the normal servicing of a device using ISRs.
• Typical I/O jobs involve transferring data between main memory and the device, this
can done by the processor during the ISR (Interrupt Service Routine) or the ISR can
set up a DMA (Direct Memory Access) transfer if the hardware exists.

11.1 Streams (P3)

• A stream is a serial flow of data, although they may be treated like files, they cannot
be randomly addresses, reading will always return the next byte, if and when there is
one.
• I/O devices, such as a keyboard, can be treated as a stream.
• In Unix processes have three standard I/O streams:
o stdin – the default input – usually the keyboard.
o stdout – the default output – usually the display/terminal.
o stderr – the diagnostic output – usually the display/terminal.
• These three streams are created when a process starts and are inherited from the
parent process.
• Processes can get from and put to streams in various ways.
• In Unix it is possible to redirect a stream to a file or to another process via a pipe.

11.2 Peripherals (P2)

• A processes address space usually contains some reserved space for peripheral
devices which is protected and can only be accessed via system calls.
• A typical peripheral interface uses 8 or 16 registers.
 • A peripheral is an external device to the system which usually can interact with the
real world.
• Some peripherals communicate data in analogue using a single line to represent
more than two values using variable voltages, this has to be converted to digital
before interfacing with the processor.

11.3 Using Peripherals (P4)

• In simple systems, peripheral devices are polled in software, where a process
continuously checks the device registers to check for change, when a change occurs
then some action is taken.
• A more efficient alternative is interrupt driven I/O, where a connected device will
raise an interrupt when it wants some action to be taken, the processor will then halt
its current process to deal with the interrupt via an ISR.
• For some high speed I/O, e.g. a disk, it may be impractical to raise an interrupt for
every action, it may instead use some supporting hardware to handle actions, this is
usually means letting a DMA controller handle the transfer of data and raise an
interrupt when it is finished.
• Devices usually interact with application software via device drivers, a piece of
trusted software that provides a standard interface for using the device.
• An MMU will usually protect device pages and will mark them as uncacheable as
values are liable to change independent of the processor.

11.4 Device Drivers (P3)

• Peripheral devices interface with a computer via a hardware device that presents
data, control and status through a set of software readable registers.
• As different devices have different interfaces a device driver is required, this is a
piece of software that simplifies the hardware interface into a standardised
abstracted interface.
• Drivers often support block operations and character streams and are often frequent
users of interrupts when operations take a long time.
• As there may be several concurrent users of a particular driver it is usually important
that the code be reentrant.
• Drivers are also usually responsible for setting up DMA transfers.
• Monolithic kernels keep drivers as part of the privileged code whereas in a
microkernal the drivers have user privileges and use system calls to access the
hardware, though the drivers are still logically part of the OS.
• Device drivers are typically written by the hardware manufacturer and are installed
when a device is added to the computer.

11.5 Interrupts (P5)

• Interrupts are a form of hardware level exception that is handled by a privileged
function before returning to the code that was originally running, similar to system
calls, however, interrupts are triggered by hardware when it requires software
support.
 • When an interrupt is handled an interrupt service routine (ISR) is called which
borrows the processor, some data, such as register state, has to be saved but not the
entire process context.
• Interrupt services are generally kept quite quick and lightweight, though interrupts
are often urgent and keeping the interrupt latency low is important.
• Interrupt service code is part of the OS and the ISR will generally be kept in memory
to keep latency low, due to hardware behaviour ISRs should not be re-entrant and
each interrupt will be handled by one processor in multi-core system.
• Each interrupt source usually has a separate enable control which controls whether
or not the hardware can raise an interrupt, these signals can be implemented in the
peripheral or a central interrupt controller or both.
• There often exist calls that can dynamically control interrupt enable signals, these are
privileged functions to stop users tinkering.
• There is a global interrupt priority controlled by the processor, this can be a simple
enable/disable system or have priority levels, this is important at boot time when
hardware is uninitialised so liable to produce random inputs.
• When an ISR is started, interrupts of a lower priority are disabled so that only higher
priority interrupts can interrupt the one currently being serviced.
• Interrupts are by their nature asynchronous and typically operated by transferring
data to and from buffers.
• ISR code is privileged and should not be accessible by the user for security reasons.
• Applications can interact with ISRs via system calls to the buffer, these could block if
the buffer is empty, allowing the application to wait until the buffer has some data in
it.
• Alternatively, an ISR can send a message to the application or the ISR could create a
new thread or process.

11.6 Interrupt Service Routine (ISR) (P3)

• When an interrupt is called the processor will save a return address, any mode
information and a small subset of the processors state as the ISR should not need the
entire processor.
• There are usually multiple sources of interrupt which could be using the same
interrupt line so the processor has to determine which piece of hardware raised the
interrupt, this can be done in hardware or software.
• A hardware interrupt controller can determine the highest priority active interrupt
and return a pre-programmed pointer to the relevant service routines.
• In software the processor has to read each potential interrupt source until it finds the
active on of the highest priority and then jump to the associated address, this is
easily expandable but significantly slower than doing it in hardware.
• Sometimes a combination of hardware and software may be used, for example if the
interrupt controller cannot hold all the required interrupt vectors (addresses).
• Usually a hardware controller is required if ISRs are to be able to interrupt each other
to track the priority, using a priority stack, and control interrupt enables.
 • When an ISR finishes it must restore the processor state, nested interrupts have to
tell the interrupt controller so that it can edit the priority stack and set the correct
enables.

11.7 Direct Memory Access (DMA) (P4)

• Direct memory access is a technique for letting I/O devices interact with memory via
a simple DMA controller rather than via the CPU so that the CPU can be used for
something else.
• A DMA controller is a simple processor capable of moving data from one place to
another and counting how much it has done.
• The CPU will setup the data transfer and tell the DMA controller the device, the
memory address and the amount to transfer, when the transfer is complete the DMA
controller will raise an interrupt with the CPU.
• The DMA controller is outside the MMU so must work on physical addresses.
• Physical pages scheduled for DMA transfer have to be pinned so that they are not re-
used until the transfer is complete.
• A typical DMA controller can move data in either direction and multiple channels
may be provided so that different DMA processes can run concurrently.
• DMA processes can interfere with CPU memory access but as most of the DMA time
is spent waiting for I/O and the CPU usually works on caches this is rare.
• Some sophisticated DMA controllers can perform block copies within memory but
this is not as relevant to the OS.

11.8 Universal Serial Bus (USB) (P1)

• The Universal Serial Bus (USB) is a hardware interface that provides a local network
for I/O devices.
• Multiple devices can timeshare the connection, allowing a single USB interface to
support up to 127 devices.

11.9 Timers (P1)

• Timers are a type of I/O device, though they can be read explicitly they often make
use of interrupts instead, and a system may have access to several timers.
• Free running timers are continuously operating, providing interrupts at regular
intervals, typically used for maintaining a system time.
• One shot timers provide a single interrupt after a preprogrammed delay, useful for
time-slicing processes CPU access.
• A real-time embedded system may have a watchdog timer which is used to reset the
system if it appears to have crashed.

11.10 Power Management (P3)

• Power management in most systems focuses more on energy management to
preserve battery life.
• The OS is responsible for identifying the biggest energy consumers and trying to
mitigate their usage as well as putting the system into active, sleep, hibernate and off
states.
 • Some modern processors have multiple sleep modes which can halt instruction
execution or even switch off the cache, though this requires a big wake-up penalty,
alternatively the supply voltage can be reduced which slows execution but reduces
energy consumption.
• Memory contents can be saved to a non-volatile store to reduce energy
consumption, though this requires a big wake-up penalty.
• Some systems use different processors depending on demand, e.g. ARMs big.LITTLE
system uses a small and energy efficient processor for most tasks and a larger
processor when demand increases.

12. Filing System (P5)

• A filing system is a persistent and large data store that all processes can access.
• The primary technologies for holding filing systems are magnetic disks, flash memory
and optical discs.
• Access to the filing system is done via device drivers that are part of the OS.
• In Windows separate devices are identified and each acts as the root of its own
hierarchical file structure, whereas in Unix the file-store mounts devices so different
disks appear as branches of the tree.

12.1 Disks (P2)

• A disk generally refers to some find of auxiliary memory and its details of operation
can be extracted away.
• Disk addresses are managed by software so may be different in size to main memory
addresses.
• As disk memory operations are typically relatively slow, storage is used for blocks of
data much larger than 8 bits, usually of 512 bytes and an address will refer to one
block.
• Auxiliary or secondary memory is used primarily for paging in virtual memory systems
and as the file store.

12.2 Disk Partition (P1)

• A partition is a virtual disk which is mapped onto a physical disk.
• A single disk may be divided into multiple partitions which serve different purposes,
e.g. one for page swapping and another for file store.

12.3 Files (P3)

• A file is the basic storage unit a filing system, they are large but slow to access and
permanent.
• Access to a file is usually via a series of system calls and typically subject to access
permissions.
• Each file consists of a set of attributes and a number of blocks/clusters containing the
file data.
• Data may be structured into records but most modern OSs leave this to the user and
view the file as a large array of bytes.
 • Some files used to be only read as a stream, from beginning to end but now it is
usually possibly to move the point of reading or writing arbitrarily.
• When reading or writing the access process maintains a pointer, it is possible to have
multiple processes accessing a file at the same time.
• A file may have a type which is maintained by the file system or user.
• Every file has a unique identifier in addition to a file name, in some filing systems the
file name is not part of a files attributes, allowing it to have multiple file names, such
as in Unix.

12.4 File Attributes (P3)

• Every file in a system usually has a set of attributes associated with it, such as it size,
these attributes are not held in the file but are held by the file system.
• File permissions are usually stored as a file attribute.
• In multi-user systems it is common for file attributes to include the owner of the file
and in Unix a file may also belong to a group.

12.5 File Types (P2)

• The inode of a file specifies the files type, e.g. whether it is a directory or a regular
file, however this does not give any distinction between regular files, some file
browser carry out tests on files to identify their contents.
• Such tests include looking at the filesystem attributes, checking for magic numbers at
known points and language usage tests.
• Users often try to imply the type of file using a suffix, e.g. .txt, abd in some systems
this is logically separate and is part of the metadata.

12.6 File Permissions (P3)

• Most filing systems include some kind of access control, usually at least so that each
user can keep their files private from other users.
• Unix-like systems, files generally have an owner (UID) and a group (GID) as well as
three groups of permissions, owner, group and user permission, this information is
held as part of the files attributes.
• Read permission allows the user to see the contents of the file, write permission
allows it to be edited and execute permission allows the file to be run as a binary or
shell script
• The permissions are usually shown as a string -rwxrwxrwx, where each character is
replaced by – if the permission is not set/given , it is in owner,group, user order, the
permissions can also be represented as three numbers, each 0-7.
• Directories have the same permissions, though execute allows the following of links
within the directory, even if it is not readable.
• Groups are defined in a system file which is owned by and only editable by root.
• General applications are generally also owned by root to protect them from
accidentally being overwritten, similarly many some file types are set by default to be
non executable so that they are not accidentally run, e.g. image files.
 • In Unix-like file systems the umask is the default set of permissions set for each file a
process creates, the process inherits the umask from its parent process and is
represented in the numerical format.
• Access Control Lists (ACLs) are a more sophisticated permission system used in
Windows and some Unix systems which specifies a list of permissions for each file,
allowing for more selective permissions.
• Access control can provide other features, such as logging access to certain files.

12.7 File Access (P4)

• When interacting with a file it is usual to use a file handle leading to the file in use
rather than using the filename/path as this is inconvenient for the OS, this handle
acts as an identifier for the file.
• Various method calls use the handle to access the file descriptor.
• When accessing a file the first thing to do is open it, doing so fetches a block of the
file into a buffer so that a disk access is not required for every read.
• When opening, the OS assigns a handle to the required filename/path, checks and
sets up the appropriate permissions and resets the files internal pointer to the start
or end of the file (for appending), if the opening fails it signals the error.
• Reads are then made from the buffer, which is refilled as required, read operations
continue until the End Of File (EOF) which prevents further reading.
• Some things can be mapped to look files and be read as streams, however with true
files it is possible to use seek operations to move the point in the file being read.
• When a file is finished with it should be closed, this flushes any buffered data to the
file, if a process terminates the OS may close any remaining files the process owned.
• It is common to read or write blocks of data to reduce the number of system calls, as
such read and write operations move contiguous blocks between the buffer and the
file, advancing the pointer in the file descriptor each time.

12.8 File Descriptor (P2)

• A file descriptor is created when a file is opened and is associated with a particular
process.
• It holds the access permissions, the current position in the file, the error status and
control flags.
• Unix maintains a table of files for each process.
• Opened files can be shared between processes.

12.9 Memory mapped Files (MMAP) (P2)

• Memory mapped files appear within a processes virtual address space, thus they can
be accessed as normal memory, rather than via system calls.
• All of the files that a process has open must fit within a processes address space.
• Rather than loading the entire file into memory, paging is used so that only the
required parts of files are ever held in memory.
• Changes to the file are periodically flushed to the filestore, though this can be forced
via a system call.
 • It is possible for multiple processes to have the same view of a memory mapped file,
making it suitable for IPC.

12.10 Filing System Implementation (P3)

• There are many different ways to implement a filing system but most
implementations have similar characteristics, allocation is done in blocks, some of
which hold system organisation data.
• Most systems allow block placement for a given file to be fragmented to allow files to
grow.
• Example implementations include inodes (as used in ext2) and FAT.
• To reduce the impact of fragmentation on performance a disk may be partitioned so
that binary files that are not modified are placed together.

12.10.1 File Allocation Tables (FAT) (P3)

• File Allocation Tables (FAT) is a legacy file system implementation which had
disadvantages in scaling, used in legacy Windows systems and contemporary
embedded systems.
• A FAT is an array of pointers, each of which points to a cluster on disk, each pointer is
used to define a linked list as each cluster contains a pointer to the next cluster that
is part of the file.
• The end of a file is marked by a reserved NULL value in the final cluster.
• As each cluster points to the next it is possible to have parts of files stored in
different regions of the disk and files can grow in length while there are free clusters.
• Files are located through a directory entry that contains pointers to the first cluster of
each file as well as various attributes about each file.

12.10.2 Inodes (P3)

• Inodes are a structure used in Unix filesystems which contain file attributes and
pointers to the blocks used by the file.
• The attributes contain the file type which can be one of:
o -- a regular file.
o d – a directory.
o l – a symbolic link.
o p – a named pipe.
o s – a socket.
o c – a character device.
o b – a block device.
• Inodes are held in an array in the filestore and are loaded into memory when the
associated file is in use.
• Every inode has a unique fixed size identifier associated with it called the inode
number.
• As there are only so many pointers that can be held in an inode, larger files can use
pointers to blocks that contain pointers, it is possible to have multiple layers of
pointers to pointers in this manner.
12.10.3 Links (P3)
• In some file structures it may be useful to have a file exist in more than one place,
rather than copy the whole file a link may be used as an alias for a file.
• Creating links turns a filesystem from a tree structure into a directed graph, as such
some systems ensure that cycles do not form, else recursive searches would fail
become stuck.
• Symbolic or soft links are special files that are simply pointers to other files, this could
be a directory or possibly something that doesn’t exist, every symbolic link has its
own inode.
• Hard links are entries in the directory table that contain the inode number of the file
they are linking to.
• The filing system tracks the number of links to an inode so that deleting a file with
multiple hard links does not free the space for reuse until all the links are deleted.
• Filenames are not held within inodes, instead they are held by directories which
associate a name with each files inode in the directory.

12.10.4 Journalling File System (P1)

• Journalling file systems keep track of changes to be made to the filesystem in a
journal, for example when writing to a file a new file copy is made and edited, when
the new file is complete it replaces the original.
• Journalling file systems are useful in embedded systems which operate in unreliable
conditions.

12.10.5 Fragmentation (P2)

• Fragmentation occurs when a physical resource can be divided and different parts
can be allocated at different times, and an allocation has to be made that makes use
of two or more separate parts that are not contiguous, this predominantly refers to
main memory and the file store.
• In a virtual memory system the physical RAM can be remapped arbitrarily at the page
level, within a processes virtual address space however, dynamic
allocation/deallocation can lead to a failure to allocate even if the total free space is
large enough.
• In a filestore space is allocated on a block by block basis which can be mapped
arbitrarily, however if the disk is highly fragmented it will slow down as the read head
has to move between the blocks.
• When virtual memory is freed it is often worth the expense of organising the free
blocks to be next to the existing free space, garbage collectors usually do this
automatically.
• Defragmenting of disks usually takes significant effort and may be done offline to
avoid moving parts of files while they are in use.
• It is common to partition disks so that files that are rarely modified, such as system
files, are all in one area while user files are in another.
13. Security (P4)
• When systems are interconnected and not all code run on a system is trusted then
the OS must implement security features to guard against malicious actions.
• Most OSs require that a user log in with a username and password before access is
granted, passwords are never stored in plain text, instead the hash is stored,
additionally, the password may also be salted before the hash is calculated.
• Privilege levels are used to stop untrusted code from carrying out certain actions,
including accessing certain areas of memory, whilst still allowing the process to run
on the bare hardware, if the processor tries something disallowed then an exception
is raised and the OS can intervene.
• Different files may often give different permissions, read write or execute, to
different users, these permissions are usually part of the filesystem, there is also an
increasing trend towards using access control lists instead which are implemented by
the OS.
• One way round such security measures is to exploit a buffer overflow within trusted
code.
• Access to a system can be blocked in a typical Denial of Service (DoS) attack, where a
system may be overloaded with jobs, each of which are legitimate.

14. Abstraction

14.1 Hypervisor (P2)

• An OS can be seen as creating a virtual machine for applications to run on and has
been seen as a supervisor, a hypervisor extends this idea by adding an extra layer of
software between the OS and the hardware so that multiple OSs can run
simultaneously.
• If hardware is upgraded it does not affect the OSs that are being run as only the
hypervisor needs to be updated.
• There are two types of hypervisor, type 1 and type 2.
• Type 1 hypervisors separate the hardware from all the OSs being run, this requires an
extra level of privilege in the hardware to catch the OSs modifying hardware so that
they do not conflict with each other.
• A type 1 hypervisor also need to have its own set of page tables to map the OS page
tables to those held by the MMU.
• A type 2 hypervisor runs like an application on top of a host OS, this requires less
hardware support but as more work is done in software there is a performance
penalty, furthermore, as each virtual machine has RAM allocated statically there is
less flexibility for reallocation.

14.2 Virtual Machines (P2)

• Virtualisation can be extended such that a single physical machine may appear as
multiple virtual machines.
• Simple virtual machines use a software model of a separate machine on which the
virtualised application code is run, this is known as an emulator.
 • Emulators allow for simple security as the application is contained by the emulator
and they can emulate any machine.
• Emulators can also provide additional monitoring information, which can aid with
debugging.
• Emulators are quite slow as much has to be modelled in software, where possible
most emulators try to run application code on the processor directly, using the
hardware to trap operations within the virtual machine.
• The emulator model can be extended to run a virtualised OS, which can in turn run
multiple applications within its own model
• Specialised host OSs, known as hypervisors, have been developed which are more
efficient at running multiple virtual OSs on one machine.

15. Miscellaneous

15.1 Application Binary Interface (ABI) (P1)

• Application binary interface (ABI) is a specification for communication between
different programme elements at the object code level.
• For example when function arguments are passed on the stack the ABI specifies in
which order they should go.
• The ABI is a lower level specification than an API which specifies which arguments are
passed and their order in the source code.

15.2 Kernel (P3)

• The kernel is the core of an OS and resides in protected space and is accessed by the
user via system calls.
• The kernel is responsible for implementing mechanisms, e.g. how a scheduler
switches process, but there are different approaches as to whether the kernel is
responsible for policy, e.g. when the scheduler switches, and in some design
philosophies the kernel encompasses the entire OS.
• In a monolithic kernel, everything is included in the kernel and runs in privileged
mode, all routines have direct access to the OS memory, this leads to large Oss which
may be less reliable and portable.
• A microkernel only contains the handlers which need to be privileged, while device
drivers and and such are separated as user-mode processes, only the required drivers
are ever loaded, interactions are more complex and the increased system calls incur
a speed penalty.
• A hybrid kernel is a compromise between the two, with some functions inside the
privilege boundary for efficiency.

15.3 Monitoring (P1)

• There are many different types of monitor, in the context of OSs a monitor usually
refers to a system monitor which may show useful stats, such as the CPU and RAM
usage.