CS241 - Operating Systems and Computer Networks

Introduction to Operating Systems

The operating system is intermediary software between the user and device hardware. The OS is responsible for allocating hardware resources to processes and controlling their execution.

Functions of the operating system

The OS performs the following actions:

  • Program execution - The system must be able to load a program into memory, execute it and stop it.
  • IO operations - While running a program may need to perform IO. For efficiency and protection, users can't control devices directly. The OS controls IO devices using drivers and interrupts.
  • File system management - Programs need to read or write files or directories and copy or move them. These operations may be subject to permission management. The OS provides system calls to achieve this.
  • Communication - The OS can enable communication between multiple processes, either on the same system or remotely.
  • Error handling - The OS needs to detect and correct errors. Errors may occur in hardware or software. The OS can handle these errors using error handling routines or by shutting down the process causing an error.
  • Resource allocation - The OS is responsible for allocating resources to multiple users and processes. The OS has to schedule processes as efficiently as possible.
  • Accounting - The OS keeps track of which processes are running and which resources they are using and how much they are using them. The OS gets this information from process control blocks.
  • Protection and security - Processes should not be able to interfere with other processes or the OS itself. The OS has to protect the system from outside attacks using authentication and encryption.

Kernel

The kernel is the core of an operating system. It is loaded into the main memory at start up. It is running at all times on the computer and there are certain functions only the kernel can perform such as memory management and process scheduling.

The kernel space is the part of the memory where the kernel executes. The user space is the section of memory where the user processes run. The kernel space is kept protected from the user space. Kernel space can be accessed from user processes using system calls. System calls perform services like IO operations or process creation.

System calls

When a user process requires a service from the kernel, it invokes a system call. System calls are required since user processes can't perform privileged operations. System calls are low level functions provided by the OS. They provide a consistent interface for common operations.

Dual mode operation

Dual mode operation is a mechanism to distinguish between OS operations and user operations. Hardware operates in two modes, kernel mode or user mode. Some instructions are privileged and can only be executed in kernel mode.

Modular design

Early operating systems did not have well defined structures. This led to monolithic kernels which were harder to debug but had less overhead for system calls.

Dependencies between different parts of the kernel code can be reduced using a modular kernel design approach. Modular design can be achieved through separation of different layers. The bottom layer is the hardware and the top layer is the user. Layer n uses the services of layer n-1 and provides services to layer n+1.

Modular design makes operating systems easier to construct and debug and gives a clear interface between layers. It can be difficult to define the layers and multiple layers can affect efficiency because system calls access multiple layers leading to more overhead.

Microkernels are smaller kernels which remove all non-essential components. These are then implemented as either system or user-level processes.

The most modern approach to operating system design involves loadable kernel modules. The kernel provides core services while other services are loaded dynamically as the kernel is running.

Processes

A process is a program in execution. A program is a passive entity stored on disk as an executable file. A process is active. A program becomes a process when it is loaded into memory. One program can have several processes.

The virtual address space of a process in memory consists of text, data, heap and stack. The text stores instructions, data stores global variables, the heap is used for dynamically allocated memory and the stack is used for local variables and function parameters.

A process undergoes several state changes. A new process can be admitted to a ready process. The ready process is scheduled and becomes running. If the process runs for longer than its allocated time it is interrupted and goes back to ready. While it is running the process can wait for IO or some other event and changes state to waiting. Once the wait is over, it becomes ready again. Once the process has finished executing it exits and is terminated.

The process control block (PCB) is a data structure maintained by the operating system for every process currently running. It stores the state, process ID, program counter, CPU registers, CPU scheduling information, memory management information, accounting information and IO status for a process. The PCB can be used to resume the execution state of a process after an interrupt.

Process scheduling

To maximise CPU utilisation, most modern OSs support multi-programming. The process scheduler efficiently schedules processes for execution. It maintains a queue of processes. The job queue is the set of processes in the new state and is called the long term scheduler. The ready queue is the set of processes in the ready state and is called the short term scheduler. The device queues are the sets of processes waiting for IO devices.

Process creation

The OS provides system calls for a user process to create another user process. In UNIX, this is done using the fork system call.

Process termination

Processes terminate automatically after executing the last statement. A process can also be terminated with the exit system call. A process returns an exit code which indicates its status. Once the process has terminated, its resources are freed by the OS.

After a child process has terminated and before its exit status is collected by the parent the child is said to be a zombie process. During this time the child resources are released but its PCB still exists. Once the parent receives the exit status the child PCB can be removed.

If the parent process finishes executing before the parent the child process becomes an orphan process. In UNIX, there is a process assigned to the parent which collects the exit status of orphan processes to allow them to be terminated.

A parent process can terminate the execution of child processes using the abort system call.

Interprocess communication

Processes running concurrently may want to communicate with each other.

The main methods of interprocess communication are message passing and shared memory.

Message passing allows process to interact by sending messages to each other. The kernel provides a communication channel and system calls used to pass messages.

Alternatively, processes interact by reading from or writing to a shared part of memory. The kernel allocates the shared memory but the processes have to handle communication. The shared memory can be used to store a circular buffer to enable communication.

The message passing system provides send and receive operations for communicating with the message queue. Message passing can be either direct or indirect.

With direct communication, processes must name each other explicitly. Communication links are established automatically and are associated with exactly one pair of communicating processes.

Indirect communication uses ports which messages are sent to and read from. A link is established only if the processes share a port. A link may be associated with many processes and each pair of processes may share several communication links.

Message passing synchronisation

Blocking is considered synchronous. The sender is blocked until the message is received or the receiver is blocked until a message is available.

Non-blocking is considered asynchronous. The sender sends the message and continues or the receiver receives either a valid message or a null message.

Message passing buffers

The communication link is a buffer. Buffers can have varying capacities.

  • Zero capacity - the queue has a maximum length of 0, so the sender must block until the recipient receives the message.
  • Bounded capacity - The queue has a finite length. When it is full the sender must be blocked
  • Unbounded capacity - The queue has potentially infinite length. The sender is never blocked.

Examples of interprocess communication systems

  • Shared memory can be allocated using mmap.
  • Ordinary pipes - these allow simple one way communication through message passing using | in bash or pipe in C.
  • Named pipes - Ordinary pipes are only accessible from the process that created them and only exist while the processes are running. Named pipes are not process dependent. They are created using mkfifo.

Introduction to computer networks

Components of a network

  • Network edge - consists of end hosts which run network applications
  • Network core - consists of packet switches which forward data packets
  • Communication links - carry data between network devices as electromagnetic waves

Functions of an end host

  • Run application processes which generate messages
  • Breaks down application messages into smaller chunks called packets
  • Adds additional information as packet headers to the packets so they can be successfully routed
  • Sends bits over a physical medium
  • May also ensure reliability and correct ordering of packet transfer
  • May also control the rate of transmission of packets

Functions of the network core

  • Routing - Run routing algorithms to construct routing tables
  • Forwarding - Once a packet arrives, it is forwarded to the appropriate output link according to the routing table

If arrival rate to a link exceeds its transmission rate then packets will queue to be transmitted and packets can be dropped if the queue gets too full.

There are four sources of packet delay - transmission, queueing, nodal processing and propagation.

  • Transmission delay is caused by waiting for packets to be fully transmitted from an end host to a link. It is given by $L/R$ where $L$ is the packet length and $R$ is the link bandwidth.
  • Queueing delay is caused by waiting in the queue at a link.
  • Nodal processing delay is the time taken to check bit errors and determine the output link.
  • Propagation delay is given by $d/s$, where $d$ is the length of a physical link and $s$ is the propagation speed in the medium.

Throughput is the rate at which data is transferred from a source to a destination in a given time. The throughput is determined by the bottleneck link, which is the link with the lowest bandwidth between the source and destination.

Protocols

Communicating nodes need to agree on certain rules. A protocol defines rules for communication. Protocols can be implemented in hardware or software. The Internet Protocol (IP) is an example of a software protocol. Ethernet is an example of a hardware protocol.

Packet switching

The internet uses packet switching technology. Different flows (source-destination pairs) share resources along their routes. Internet traffic is bursty. If one flow is not using a link then the other flows can use it. Flows can change routes if links fail or become congested.

Circuit switching

Before the internet, circuit switching was used in telephone networks. A circuit consists of all communication links along a path from source to destination. A circuit is reserved for each flow for its entire duration giving a guaranteed rate of communication but greater resource usage. If a link fails the transmission ends. This is not ideal for internet traffic as it is bursty instead of continuous.

Layering

Network devices perform complex functions. This functionality can be divided into layers. Each layer performs a subset of functions and the services of below layers and provides services to the above layers. The IP stack has 5 layers, application, transport, network, link and physical from highest to lowest.

IP stack

  • Application - Generate data to be communicated over the internet. Includes HTTPS, SMTP and DNS.
  • Transport - Turns data into packets, adds port number and manages sequencing and error correction. Includes TCP and UDP.
  • Network - Adds source and destination address, routes packets. Includes IP and routing protocols.
  • Link - Adds source and destination MAC addresses, pass frames onto NIC drivers. Includes Ethernet and WiFi.
  • Physical - Sends individual bits through the physical medium. Protocol varies by transmission medium.

Application layer

A network application consists of processes running on different host machines which communicate by sending messages over a network.

Sockets are a networking interface to the kernel used by user processes. The kernel handles the transport layer and below.

Messages need to be addressed to the correct process running within the correct end host. Devices can be identified by IP addresses and processes are identified by port numbers.

An application can choose to use TCP or UDP for transport layer services. TCP has reliable and in-order data transfer. TCP establishes a connection between processes using a handshake before sending data. UDP provides no guarantees on data transfer. It just sends packets and hopes for the best. It is faster than TCP as the connection does not have to be established and the headers are smaller.

HTTP

HTTP is the application layer protocol used by web browsers and web servers. HTTP uses TCP and port 80.

There are two main versions of HTTP.

  • HTTP 1.0 (Non-persistent) - Each object is obtained over a separate TCP connection
  • HTTP 1.1 (Persistent) - Multiple objects can be sent over a single TCP connection

Threads

A thread is a unit of CPU execution. In a single threaded process, one chain of execution of running each line sequentially. Multithreading allows multiple concurrent chains of execution, sharing code, data, the heap, opened files and signals with the parent.

A thread is comprised of a thread id, program counter, register set and stack.

Thread creation has less overhead than process creation as threads share more resources with the parent than processes. Threads also allow for more scalable and responsive applications.

Concurrency and parallelism

Concurrency means multiple tasks are executed over time and this is possible on a single core CPU by interleaving execution. Parallelism means multiple tasks can be performed simultaneously and needs at least 2 cores.

Data parallelism distributes subsets of the same data across multiple cores, performing the same operation on each core. Task parallelism split threads performing different tasks across multiple cores. Applications can use a mixture of both.

Amdahl's Law states that the speed-up due to parallelism is given by $$speedup \leq \frac{1}{S+\frac{1-S}{N}}$$ where $S$ is the time taken to run the serial part and $\frac{1-S}{N}$ is the time taken to run the parallelisable part with $N$ cores.

Race conditions and mutex locks

When two threads try to modify a shared variable, they cause a race condition where only the value from one thread is kept.

Threads can be kept synchronised using mutex (mutual exclusion) locks. A thread has to acquire a lock before performing updates on shared variables. It can then release the lock once it is done.

User level and kernel level threads

A multithreaded kernel will use kernel level threads. Kernel threads are used to run OS or user processes. The kernel can schedule them on different CPUs.

User level threads are used by multithreaded processes. User level threads have to be associated with a kernel level thread to be executed.

The user-kernel thread mapping can be done in different ways

  • One-to-one - Each user level thread maps to a kernel thread. Other threads can run even when one thread is blocking and different threads can be run on different cores in parallel. A kernel level thread needs to be created for each user level thread, which can be expensive.
  • Many-to-one - Many user threads are mapped to a single kernel thread. This results in less overhead, but reduces parallelism and if one thread is blocking, all of the threads are blocked.
  • Many-to-many - Combination of both of the above. Kernel threads can run in parallel and one blocking call does not block the entire process. The programmer can decide how may kernel and user threads to use, meaning less overhead.

Threading strategies

A threading strategy determines the interactions between threads within a process.

  • One thread per request strategy - Create a worker thread for each request. High overhead, can't handle high traffic.
  • Threadpool strategy - Create a fixed number of worker threads. Add each request to a queue. The workers will then process requests until the queue is empty. This is faster than creating a new thread, but a request may have to wait before being served.

Condition variables

Condition variables are like mutex locks used for synchronising the actions of different threads. A thread can use wait(&condition) to wait until another thread uses signal(&condition) or broadcast(&condition).

Signal handling

Signals are used to inform a process about the occurrence of an event. Signals can either be synchronous (generated by a process, such as illegal memory access) or asynchronous (generated externally, such as SIGINT).

All signals follow the same pattern:

  • A signal is generated by an event
  • The signal is delivered to the applicable process
  • The signal must be handled by the process

Signals have default handlers which can be overridden by the user. For example, it is possible to override the SIGINT handler. In a multithreaded program, a signal can be delivered to all threads or just one. Synchronous signals are usually sent to the thread which generated it whereas asynchronous signals are sent to all threads.

Selected topics in networking

Networking topics relevant to the coursework.

Network interfaces

A network interface is the point of interconnection between a device and a network. A network interface is typically associated with a hardware network interface card (NIC). The loopback interface (localhost) is a virtual network interface which doesn't have a hardware NIC. Each network interface has an IP address. Interfaces associated to hardware NIC also have a MAC address.

The link layer header contains 48-bit source and destination MAC addresses and the 16 bits for the protocol for the next layer. 0x0800 corresponds to IPv4 and 0x0806 to ARP. The total size of the link layer header is 14 bytes.

Network layer header

This header contains several fields. The ones needed for coursework are

  • IHL - 4 bits, denotes header length in 4 byte words
  • Protocol - 8 bits, describes the protocol for the next layer
  • Source and destination - 32 bit IP addresses

Transport layer header

The coursework does not use UDP. The useful TCP header fields are

  • Source and destination port numbers (16 bits each)
  • Data offset (4 bits) - Similar to IHL, specifies length of header in 4 byte words
  • URG, ACK, PSH, RST, SYN, FIN - 6 control bits used to indicate special functions of TCP packets. The coursework only concerns SYN and ACK

SYN attack

A normal user will send a SYN packet to the server to establish a connection. The server will then create a half open connection and send back a SYN ACK packet. When the client receives it, they send an ACK packet back. When the server receives this, the connection is fully established.

A malicious user can send many SYN packets from spoofed source IPs. The server will then try to accept these requests and create a half open connection for each and send back SYN ACK packets. The half open connections take up resources and the SYN ACK packets are never ACK'd so the server might crash.

ARP cache poisoning attack

The address resolution protocol (ARP) is used to resolve an IP address to a MAC address. An interface can send an ARP request to all connected interfaces to try to resolve the IP. The request should be responded to by the interface with the IP in the request, but anyone can reply to an ARP request so an attacker can send back an incorrect ARP reply to poison the cache.

CPU Scheduling

The OS had to manage allocation of jobs to the CPU. It should aim to maximise CPU utilisation.

The performance of a CPU scheduling method can be measured using

  • CPU utilisation - Time the CPU spends busy when there are jobs is the ready queue
  • Throughput - number of processes completed per unit time
  • Turnaround time - time taken to complete a process
  • Waiting time - amount of time a process spends in the ready queue
  • Response time - amount of time from when a request is enqueued to when its first response

Types of scheduling

  • Non-preemptive - The CPU will execute a single process until it's current CPU burst finishes
  • Pre-emptive - The execution of a process can be interrupted to schedule another. These algorithms are typically faster and more responsive but can lead to race conditions.

First come, first served

Processes are assigned to the CPU in order of arrival. This method works better when shorter jobs arrive first. It is non-preemptive.

Shortest job first

Processes the job with shortest execution time first. This is the best scheduling algorithm for minimising average waiting time. The execution times can be estimated using the exponential moving average which uses the time taken for previous processes to execute to estimate the time for the next one.

The SJF method can be either pre-emptive or non-preemptive. In the pre-emptive version, if a new, shorter process arrives when a process is already executing then execution will switch to the new process. In the non-preemptive version the original process will continue as usual.

Priority scheduling

The CPU is allocated to the highest priority process in the queue. SJF is a case of priority scheduling where the priority is determined by execution time. One problem with priority based scheduling is starvation, where low priority processes may never get scheduled. A solution to this is ageing, where the longer a process waits the higher its priority gets.

Round robin scheduling

Each process is allocated a small unit of CPU time, called a time quantum. After this time has passed, the process is pre-empted and added to the end of the ready queue. The scheduler visits the processes in order of queue arrival. If there are $n$ processes in the ready queue and time quantum $q$ then each process gets $1/n$ of the CPU time in chunks of at most $q$. Therefore no process waits more than $(n-1) \times q$ time for its next turn. Round robin is pre-emptive as it interrupts processes when their time quantum has passes. For large $q$, the performance is similar to first come, first server. For small $q$ there are too many context switches so CPU time is wasted.

Synchronisation

Without synchronisation, concurrently running threads or processes enter into a race condition when trying to update shared variables. Only the last change made will be kept. This can be avoided using synchronisation.

For synchronisation, the term processes refers to both processes and threads. The part of the code where a process updates shared variables is called a critical section. A process can have multiple critical sections. When one process is in a critical section, no other process should be allowed to at the same time. This is called mutual exclusion.

The critical section problem

The critical section problem is to design a protocol such that no two processes can concurrently execute their critical sections. Ideal solutions to the critical section problem must satisfy three criteria.

  1. Mutual exclusion - If a process is executing its critical section then no other processes can be executing their critical sections
  2. Progress - If no process is executing in its critical section and there exist some processes that wish to enter their critical section then one of the waiting processes must be able to enter into its critical section
  3. Bounded waiting - No one process should have to wait indefinitely to enter its critical section while other processes are being allowed to enter and exit their critical sections continually.

Peterson's algorithm

Peterson's algorithm makes use of a turn variable and an array of flags for each process. The flag array will indicate whether a process wants to enter the critical section. Consider two processes $a$ and $b$.

Process $a$ will set its flag to true, then set turn to $b$ and wait until $b$ has its flag set to false or turn is equal to $a$ before executing the critical section.

Process $b$ will set its flag to true, then set turn to $a$. It will then wait until $a$ has its flag set to false or turn is $b$ before executing the critical section.

After the critical sections, both processes will set their flags to false.

Peterson's algorithm meets all three critical section problem criteria, but isn't perfect as it uses busy wait and may not work on modern architectures as red and write operations may be reordered to make programs more efficient.

Locks

Another way to solve the critical section problem is the use of locks. This is where a process has to acquire a lock before entering its critical section and releases it when it leaves. If another process wants to enter its critical section when the lock is held by another process it has to wait until the lock is released.

It is important that locking and unlocking are performed atomically. Modern architectures provide atomic hardware instructions to implement locks. Hardware level instructions are not usually available, so operating systems make synchronisation primitives available. These primitives are mutex locks, condition variables and semaphores.

Semaphores

Semaphores can have integer values unlike mutex locks, which are boolean. A zero value indicates the semaphore is not available and a positive value indicates it is available. The semaphore can be accesses using two atomic operations, wait() and signal(). The wait operation decrements the semaphore and waits until it becomes available and signal increments the semaphore by 1.

Semaphores can be used to allow multiple concurrent access to a resource.

Synchronisation issues

Several issues can occur when using synchronisation primitives

  • Deadlock
  • Starvation
  • Priority inversion

Deadlock occurs when two or more processes are waiting indefinitely for each other to do something.

Starvation occurs when a specific process has to wait indefinitely while others make progress. To avoid this, a random process should be woken when a lock becomes available.

Priority inversion is a scheduling problem that occurs when a lower priority process holds a lock needed by a higher priority process. This can be solved using a priority-inheritance protocol.

Classic synchronisation problems

  • Bounded buffer problem - Consider a buffer capable of storing $n$ items, a producer which produces items and writes them to the buffer and a consumer which consumes items from the buffer. The producer should not write when the buffer is full, the consumer should not read when the buffer is empty and the producer and consumer should not access the buffer at the same time.

  • Readers and writers problem - A data set is shared among a number of concurrent processes. Readers only read the data set and writers can read and write. Multiple readers are allowed to read at the same time but only one writer can access the data set data at the same time. There are different versions of this problem, for this module readers are given preference over writers when no process is active and writers may starve.

  • Dining philosophers problem - There are $n$ philosophers and $n$ shared chopsticks used to eat a bowl of rice. A philosopher needs two chopsticks to eat.

All of these problems can be solved using synchronisation primitives. No I will not elaborate.

Transport layer

The transport layer provides logical communication between processes running on different hosts. The sender breaks data into segments, adds headers and passes it to the network layer. The receiver reassembles segments into data which is then passed to the application layer.

UDP

User datagram protocol (UDP) provides the bare minimum services. It turns data into packets, adds the UDP header and sends them to the network layer. If the packets reach the destination, UDP delivers them to the correct process. No effort is made to recover lost or out of order packets. Each UDP datagram is treated independently, there is no persistent connection.

UDP is fast because it has less overhead. This is ideal for video and voice streaming as high transmission speed is needed and some packet loss is acceptable.

TCP

Transmission control protocol (TCP) provides reliable data transfer. It ensures packets are not lost and that they are reordered on arrival. It matches the sending rate to the reading rate of the receiver unlike UDP, which can send traffic as quickly as it likes. TCP also limits the sending rate based on perceived network congestion.

In an unreliable channel there can be bit errors, packet loss and unordered packets arrival. Checksums can be used to detect bit errors. ACKs are sent by recipients to confirm a packet has been correctly received. If the sender does not receive an ACK after some time, it retransmits the packet. This is called an automatic repeat request (ARQ). TCP uses sequence numbers to allow packets to be reordered on receipt.

Stop and wait ARQ

The sender sends a packet and waits for an ACK. If no ACK arrives, it retransmits the packet. This provides reliable data transfer but only sends another packet once the previous one is ACK'd. This has a long round trip time, which can cause poor performance. Instead, the sender could send the delay bandwidth product number of packets without waiting for an ACK. The delay bandwidth product is the product of the round trip time (delay) and the bandwidth. This results in better utilisation and performance. The delay bandwidth product is also called the length of the pipeline. The rate at which the receiver processes packets should also be considered. The sender should not send more packets than the receiver can receive, so the length of the pipeline is the smaller of the recipient buffer size and the delay bandwidth product.

Go-Back-N protocol

Sender can send up to N packets without waiting for an ACK. These N packets are called the send window. The receiver keeps track of the next expected sequence number. If the receiver receives a packet and it has the expected sequence number then it sends back a cumulative ACK which ACKs all packets since the last packet was ACK'd. If the packet received is not the expected sequence number it is dropped and the previous ACK is resent. The sender will resend packets after the dropped packets times out.

Selective repeat protocol

Selective repeat does not discard out of order packers, as long as they fall within the receive window. ACKs are individual, not cumulative. The sender selectively resends packets whose ACK did not arrive. It maintains a timer for each non-ACK'd packet in its send window. The sender does not have to retransmit out of order packets.

TCP reliable data transfer

TCP uses a combination of the GBN and SR protocols. It uses cumulative ACKs and only retransmits timed out segments.

In TCP, each byte of data is numbered. The sequence number of a segment is the number of the first byte in the segment. The ACK contains the number of the next expected byte. TCP uses cumulative ACKs, so all previous bytes get ACK'd as well.

TCP duplex

TCP allows bidirectional communication. To reduce the number of transmission, TCP allows sending ACKs with data.

TCP flow control

The data in the pipeline should not exceed the receiver buffer size otherwise data will be lost. Flow control tries to adjust the sending speed based on the remaining size of the receive buffer. To do this, the receiver specifies the free buffer space in the receive window field. The sender then limits it's rate to this value.

TPC congestion control

Congestion control limits the rate of transmission according to the perceived level of congestion in the network. Congestion at a router occurs when the input rate exceed the output rate. This can cause packet loss or delays. Congestion is caused by senders sending packets too fast. Congestion control aims to prevent congestion and ensure fair access to resources.

Congestion is detected through losses and delays. A TCP sender assumes the network is congested when timeouts occur or duplicate ACKs are received.

The send window determines the rate of transmission. The rate of transmission is given by window size divided by round trip time. The number of segments needed to transmit the window is given by window size divided by maximum segment size.

The sender maintains a congestion window size. The window size is at most the minimum of the receiver window size and the congestion window size. The size of the congestion window is determined using additive increase multiplicative decrease (AIMD). [FINISH THESE NOTES]

Deadlocks

A set of processes is in a deadlock when each process in the set is waiting for an event that can only be caused by another process in the set. These events usually involve acquisition or release of a resource such as a mutex lock or the CPU.

System model

A system consists of different types of resource, $R_1, R_2, ..., R_n$ and each resource type $R_i$ has $W_i$ instances. A process uses a resource by requesting, using and then releasing it.

Necessary conditions for deadlock

  • Mutual exclusion - only one process can use an instance of a resource at a time
  • Hold and wait - there must be a process holding some resources while waiting to acquire additional resources held by other processes
  • No pre-emption - a resource can only be released voluntarily by the process holding it
  • Circular wait - there exists a subset of processes which circularly wait for each other

Resource allocation graph

A resource allocation graph can be used to represent a system. It is a directed graph with vertices partitioned into processes and resources. There is a directed edge from a process to a resource if it requests the resource and from a resource to a process if it is assigned to a process. Resource allocation graphs can be used to identify deadlock in a system. If there is no cycle in the graph, there is no circular wait and therefore no deadlock but a cycle does not necessarily indicate there is deadlock.

The deadlock detection algorithm can be used to check for deadlock when there is a cycle. The graph is represented as a table with a row for each process and 3 sets of columns for allocation, availability and requests of resources. There is also a flag for each process to indicate if it has finished.

Each step of the algorithm checks for a process which hasn't finished and doesn't have any requests. If such a process exists, it can finish executing, release its resource and be marked as finished. Otherwise it checks if there are processes requesting an available resource. If so, the process can be executed, marked as finished and the resource can be released. This is repeated until no such process exists, in which case deadlock has occurred.

Deadlock prevention

Deadlocks can be prevented by ensuring that at least one of the necessary conditions for deadlocks does not occur.

  • Mutual exclusion - can't be prevented for non-shareable resources
  • Hold and wait - when a process requests resources, it does not hold other resources. It either holds all or none.
  • No pre-emption - if a process holding some resources requests additional resources then all resources currently held are released
  • Circular wait - number the resources and require the processes request resources in that order

Deadlock prevention can be quite restrictive, so deadlock avoidance can be used instead. It determines if a request should be granted based on whether the resulting allocation leaves the system in a safe state. A safe state is one in which deadlock can never occur. A deadlock avoidance algorithm can be used to check for safe states. It needs information on resource requirements, so each process has to declare the maximum number of instances of each resource it may need.

Banker's safety algorithm

[make better notes for this]

The resource request algorithm uses Banker's algorithm to determine if granting the current request results in a safe state.

Main memory

A program must be copied from disk to memory so it can be executed. Once in the memory, the process occupies some addresses which store data and instructions. These addresses need to be unique for every process. The OS must ensure that a process can only access its allocated memory.

Logical and physical address space

During execution, the CPU needs to access different memory addresses. Logical (virtual) addresses are generated by the CPU to fetch instructions or read/write data and may be different from the physical address. The physical address refers to a physical memory unit. The memory management unit (MMU) is responsible for translating logical addresses to physical addresses.

Contiguous memory allocation

Contiguous memory allocation allocates a single contiguous block of memory to a process. The MMU consists of a relocation and limit register which store the base address and range of addresses for a process. When a process is scheduled, the OS is responsible for loading the relocation and limit register values.

One way of dividing memory is fixed size partitions. Memory is divided into fixed size partitions, each partition is allocated to one process and when a process is terminated the partition is freed. The problem with this approach is that the number of partitions limits the number of concurrent processes.

Another method is variable sized partitions. Any available block of memory is called a hole. When a process arrives, it is allocated memory from a hole large enough to accommodate it. When a process exits it leaves a new hole which can be merged with other adjacent holes. There are several methods to assign holes to a process. First-fit allocates the first hole that is big enough. Best-fit allocates the smallest hole that is big enough. Worst-fit allocates the largest hole possible.

Memory allocation can fragment the usable memory space. External fragmentation occurs with variable sized partitions and is where enough total memory space exists but is not contiguous. Internal fragmentation occurs with fixed size partitioning when the allocated partition is much larger than the needed memory. This can result in large areas of unused memory.

Fragmentation can be resolved by using compaction or non-contiguous memory allocation. Compaction shuffles memory contents to place all free memory together in one contiguous block. This has significant overhead. Non-contiguous memory allocation allows a process to be scattered throughout the memory.

Non-contiguous memory allocation

Segmentation is where the program is divided into segments. Each segment is stored in a contiguous block of memory, but segments are not necessarily contiguous. Each logical address consists of the segment number and offset. Segment number can be mapped to the base address of a segment in memory and then added to the offset to produce the physical address. A segment table is used to store bases addresses and lengths for each segment number. Segmentation can still suffer from external fragmentation. This can be avoided with paging.

Paging is where the program is split into fixed-sized blocks called pages. Physical memory is divided into fixed-sized blocks called frames. The page size is equal to the frame size. Pages are assigned to frames. The mapping between page numbers and frame numbers is stored in a page table. The OS maintains a page table for each process. The logical addresses consist of a page number and page offset. These can be mapped to physical addresses using the page table. Smaller pages mean larger page tables but larger pages mean more internal fragmentation. An ideal page size is a balance of the two.

[paging notes from the 'lecture you did aoc in instead' go here]

Network Layer

The main function of the network layer is to move packets from the source node to destination node through intermediate nodes (routers). One of the main protocols running on the network layer is the internet protocol (IP).

Routing

Routing protocols are used to construct routing tables. These tables map destination IP address ranges to output links. As IP address ranges don't necessarily divide nicely, longest prefix matching is used. This looks for the entry with the longest address prefix that matches the destination address.

IP addresses belonging to the same subnet have the same subnet mask. The subset mask is a common address prefix. Interfaces in the same subnet are connected by a link layer switch which uses MAC addresses.

Classless Inter-Domain Routing (CIDR) notation is used to indicate the size of the subnet mask. For example, 192.168.0.1/24 indicates a subnet mask of 24 bits.

When sending packets in the same subnet, the sender can check if a destination IP address has the same subnet mask as itself. If so, it is in the same subnet. It can then obtain the destination MAC address by ARP and then forward the packet through the link layer switch.

If the sender and destination are in different subnets, the sender forwards the packet to its default gateway. A gateway router connects one subnet to other subnets.

Assigning IP addresses

IP addresses can either be manually assigned by an administrator or assigned using the Dynamic Host Configuration Protocol (DHCP). DHCP dynamically assigns IP addresses from a server (usually the default gateway) to clients. For both methods the subnet mask and default gateway must be specified as well.

Networks are allocated subnet masks by ISPs, which are allocated blocks of IP addresses by ICANN.

Network address translation

There are too many interface for each to have a unique IP address. Instead, every gateway is given a unique address and the interfaces in a subnet have private IP addresses which are unique within the subnet. There are several blocks of IP addresses reserved for private. Network address translation (NAT) translates between public and private IP addresses. When sending a packet, the sender provides a source private source IP and source port. The NAT router replaces the source address with its public IP. This mapping is stored. When a response is received, the mapping can be used to translate public IP and port into private IP and port.

Routing

Networks can be abstracted to weighted graphs which can then be used to find shortest cost routes. There are two types of routing algorithm

  • Global algorithms need a complete knowledge of the network. These are referred to as link state algorithms
  • Local algorithms only need knowledge os adjacent routers at each router

For link state algorithm, each node broadcasts its link costs so after broadcasts all nodes have knowledge of the whole network. Dijkstra's algorithm can then be used for routing.

The distance vector algorithm is used in the routing information protocol (RIP). This is a local algorithm and uses the Bellman-Ford algorithms.