# COMP3301 Exam Notes

# Definitions

Trap

: An interrupt generated by software

# Multi-Processing

# Processes

## Process Control Block

- Process State
- New
- Ready
- Running
- Waiting
- Terminated
- Process number
- Program Counter
- CPU Registers
- Memory limits (allocated main memory)
- I/O Status info (open files, devices etc)

## Context Switch

From process 0 to process 1.

1. Switch initiated by interrupt or system call
1. Save state into PCB0 (cpu idle)
2. Reload state from PCB1 (idle)
3. Execute process 1
4. Save state into PCB1 (idle)
5. Reload state from PCB0 (idle)
6. Continue running process 0

## Process Cooperation

- Pros:
- Information sharing
- Computation speedup (cpu utilisation)
- Modularity
- Multi-Tasking (by users), convenience

## Interprocess Communication IPC

- Shared Memory
- Risks memory corruption
- Message Passing
- higher performance cost
- can use buffering and queues
- Easier to synchonise
- blocking send, blocking receive
- direct
- Processes must know about eachother explicitly,
- unix sockets
- pipes
- requires parent-child relationship
- pipes also need an agreed serialisation scheme
- unidirectional
- cant be used over a network
- named pipes
- bidirectional
- addressed (don't need parent child relationship)
- indirect
- processes have ports which can receive messages
- processes can communicate if they share a mailbox

# Threads

Multicore / Multiprocessor
: A system that run multiple programs simultaneously using multiple hardware threads.

Data Parallelism
: Distributing the same data across multiple cores to be worked on simultaneously

Task Parallelism
: Distributing tasks across multiple cores each doing something different

- Fork and Exec have different semantics
- does `fork` duplicate all the threads or just the caller?
- `exec` replaces ALL threads.

- Signals
- go to all threads, only the relevant thread, a specific
signal-handling thread?

Thread-local storage
: Storage tied to a specific thread, good when using a thread pool and you dont
have control over thread creation. TLS is visible across all functions in the
thread, similar to static data, unique to each thread.

## Thread Pools

- Faster thread dispatch
- Puts a bound on the number of threads in an application using the
size of the thread pool.

## OpenMP

- Threading library
- Identifies parallel regions
- Cross platform and easy to use, widely supported

# Synchronisation

- Method depends on whether the kernel is preemptive.

Deadlock
: Two processes waiting indefinintely for a resource
- circular dependency

Starvation
: Infinite blocking (a process is never removed from a)

## Deadlock Avoidance

Safe State
: No deadlocks can occur

Unsafe State
: deadlocks are possible

Deadlock Avoidance
: Ensure that the system doesnt enter an unsafe state

Deadlock Recovery
: Recover system from a deadlocked state

### Safe State

For all processes in a system Pi needing resources, and Pj holding resources.

1. If Pi's needed resources are not immediately available then it can wait until all
Pj have finished using them.
2. When Pj is finished Pi can obtain resources, execute and terminate.
3. When Pi terminates Pi+1 can obtain needed resources and so on.

- Resources can safely be passed around all processes in the system.

- Avoidance Algorithms
- Banker's Algorithm
- Single instance of a resource type, use a **resource allocation graph**
- Access only allowed if adding the resource request edge to the resource
graph doesn't create a cycle.

## Critical section problem

- in hardware
- disable interrupts (on uniprocessors) --- obviously not scalable or performant
- locking
- atomic instructions (test memory and set value, compare and swap two memory values)
- mutex locks (spinlocks)
- `acquire()` and `release()`
- Requires busywaiting to enter
- good for short waits on a multiprocerssor system
- semaphores
- Can put the process to sleep when waiting
- give it to other processes or power saving states
- counting
- read mode, write mode, can read many write one and so on with greater control
- binary
- like a mutex
- an abstracted solution to the critical section problem
- Has two operations
- `block` add process to the waiting queue until it can be
served by the critical section
- `wakeup` (when a process leaves the crit section) move the
next process from the waiting queue to the ready queue

# CPU Scheduling

Long Term Scheduler

: Selects which processes should move to the ready queue. Balanced
for the degree of multiprogramming used so that processes share time
fairly depending on their priority and importance. Invoked with a seconds
to minutes period.

Short Term Scheduler

: Selects what process to run next. Executed every number of milliseconds.
It has a large performance impact.

Medium Term Scheduler

: is sometimes used to reduce the degree of multiprogramming if it is
too high for efficient operation. (Swapping processes to disk and back).

- CPU utilisation
- Throughput
- Turnaround time (time until another process can be executing)
- Waiting time (in ready queue)
- Response time

## Types

- First come first served
- Shortest Job First
- based on next burst time
- not preemptive
- Shortest Remaining Time First
- preemptive
- time to live and priority ageing prevent starvation
- Priority
- preemptive
- By priority, then process time
- starvation mitigated by ageing (increasing priority over time)
- Roundrobin
- not preemptive
- Each process runs for a unit time $q$ in a round robin.
- $q$ close to process time is ideal, else starvation or dispath latency
- Good for frequent bursts of periodic tasks
- multilevel queue
- multiple queues with different priorities and algorithms
- promotion and demotion, ageing
- scheduling must be done between queues
- i.e. do all foreground, then do all background
- time slices, i.e. 80% to foreground 20% to background (this can use any scheudling algorithm)

### Real Time

Hard Realtime

: Guarantees processes will be serviced by their deadlines

Soft Realtime

: Prioritises realtime processes, but does not guarantee

Throughput

: Number of taks / total time

CPU Utilisation

: Fraction of cpu time spent doing anything (not waiting)

- Rate Monotonic
- Only for **Periodic** processes that need to be updated every $p$ amount of time.
- $p =$ time to deadline
- Smaller $p$ is higher priority
- Priority assigned based on the inverse of the period
- Can miss deadlines
- Earliest Deadline First
- Non-periodic, non-constant burst time.
- Theoretically optimal (minus context switch) 100% cpu and all deadlines
met.
- Smaller deadline is higher priority
- Proportional Share
- $T$ shares are allocated, each program receives $N$ of those.

# Multiprogramming & Synchronisation (TODO)

Classical problems
- Bounded buffer
- Readers and writers
- Dining philosophers
- Producer COnsumer

# Deadlocks (TODO)

## Deadlock Characterisation

1. Mutual Exclusion
- Resource held in a nonsharable mode
2. Hold and wait
- A process is holding a nonsharable resource and
waiting for another resource that is being held
3. No preemption
- Resources cannot be preempted: released only voluntarily
4. Circular Wait
- A waits for B waits for C waits for ... waits for A

Priority Inversion
: When a lower priority process is holding a resource that is being waited on by a higher priority process.

- deadlock recovery
- Abort all deadlocked processes
- Abort processes one at a time until deadlock cycle is gone, based on
- priority
- process accounting stuff (time ran, resources used, etc..)
- interactive or batch
- deadlock avoidance
- Check for cycles in resource allocation graph

Random terms
- starvation: in the mutex queue for a long time
- priority inversion: When low priority tasks hold a lock needed by a higher priority process

# Virtual Memory

## Page Faults + Demand Paging

First reference to a page will trap to OS

1. Check validity of address
2. Find a free frame
3. Swap page into fram in via scheduled operation (takes a long time)
4. Restart the process

## Page Replacement

1. Find the page
2. Find a free frame (or victim frame determined by page replacement algo.)
3. Move the page into the free frame and update tables
4. Restart process

Frame Allocation Algorithm

: how to initially allocate memory to processes

## Page Replacement Algorithms

Want the lowest page-fault rate on first access and reaccess

- FIFO Algorithm
- replace the oldest frame
- Suffers belady's anomaly (more frames can mean more page faults)
- Optimal Algorithm
- Replace the page that won't be used for the longest time.
- (you need to know what frames will be needed in the future)
- Least Recently Used (LRU)
- Earliest last-use time gets replaced
- Associate a last use clock counter value with each page
- Slow/complex without hardware support
- Hardware to approximate LRU
- LFU, MFU (least / most frequently used)
- keep a counter of each page access
- LFU: smaller count $\implies$ not used frequently, replace
- MFU: smaller count $\implies$ new and yet to be used, replaced highest
count

## Other memory

- kernel memory
- usually a free-memory pool
- Memory mapped I/O
- written when a pager scans for dirty pages, periorically, or at `close()`
- processes can share the memory mapping
- higher performance than read() and write()

# Main memory?
## Swapping

- Backing store - lage, fast disk that accommodates copies of all memory images for all users; provides direct access

- Roll out, roll in - used for priority based scheduling algorithms; lower priority process i sswapped out so higher priority process

# External I/O

## Magnetic Disks

Average I/O time

: average access time + (amount to transfer / transfer rate) + controller overhead
Bandwidth

: bytes transferred / total time of request

Rotational Latency (ms)

: $\left(\frac{rpm} { 60000}\right)^{-1}$

- Sector 0 is first on the outermost cylinder

### Disk Scheduling

Minimise seek time $\approx$ seek distance

- FCFS (first come first served)
- pro: fair (no starvation)
- con: not fast
- SSTF (Shortest Seek Time First)
- go to linearly closest cylinder next
- pro: fast
- con: may cause starvation, and make some requests wait longer
- optimal if the disk isnt under heavy load
- SCAN (elevator algorithm)
- Service all cylinders $\le$ current position in descending order, then
all cylinders $\ge$ position in ascending order.
- going all the way to the end of the disk and turn around.
- Is fair and has better performance than FTFS
- C-SCAN
- Only service cylinders when moving in one direction, them jump to
the other end.
- more uniform wait time
- LOOK and C-LOOK
- SCAN and C-SCAN but the arm only goes as far as the last request then turns around
- better performance than SCAN

### RAID

[Reference](http://www.raid-calculator.com/raid-types-reference.aspx)

- Striping = combine multiple disks into one unit
- Duplication = failure tolerance and performance

RAID 1

: Mirroring (keeps a suplicate of each disk)

RAID 1+0 and 0+1

: Striped mirrors and mirrored stripes are high performance and higgh
reliability

RAID 4,5,6

: Block interleaved parity combine multiple disks with some performance and
reliability benefit without using as much redundancy.

# File Systems

External Fragmentation

: When there are lots of small non-contigouous memory blocks which cannot be
useful.

Internal Fragmentation

: Memory allocated is too big for what it is to be used for and there is some
left over that cannot be used by another process, due to the page size.

### Directories Implementations

- Linear List
- A list of file names with a pointer to data
- Slow to traverse, linear search time (improved using a B+ tree)
- Hash Table
- much faster to find a file in a directory
- expensive to resize the hash table
- Only good if the number of entries has a fixed maximum
- even a linked list collision resolution is better than a linear list.

## File Allocation Methods

- Contiguous allocation
- Contiguous blocks are placed next to eachother on disk
- Mapping from logical to physical
- good for random access
- suffers from external fragmentation
- Linked
- Files are linked lists of blocks
- pros
- No external fragmentation
- Good for sequential access
- cons
- Locating a block can take many disk seeks and I/Os.
- Slow random access
- Generally slower than indexed
- FAT variation := the beggining of the volume has a table indexed by block number that can be cached and is faster, but still a linked list of blocks, stored separately to the blocks themselves.
- Indexed
- Every file has an index block containing all the block pointers in that file
- Good for random access without causing external fragmentation.
- blocks are in linked chains, not contiguous areas, but you have a big table to them that is stored in memory.
- Index block is a significant overhead for many small files, is generally greater than that of normal linked allocation.
- Fast

- UNIX
- Linked index table

## Free Space Management

- Contiguous Bitmap
- easy to get contiguous files
- Size on disk is, with disk size of $2^d$ bytes 8 blocks per byte of the bitmap, $n = t^d / 8$ bytes.
- Linked
- no waste of space
- cannot get contiguous space easy

## File System Performance

- Buffer cache
- Synchronous writes: prevents buffering and caching
- Async writes that are queued are faster
- Free-behind and read ahead optimise sequentnial access
- Reads slower than writes

# I/O Systems

## Hardware

- Some data tx,rx registers, control, status as bytes or a fifo buffer.
- Addressed via direct I/O instructions
- MMIO.

## Polling

- use status bits to busy-wait until both are ready
- good if device is fast but bad if the device is slow.
- can lose data if the CPU wasn't ready to copy when the device was
- Excessive CPU time demand from the OS when the device doesnt have anything for it to do
- Good for very frequent periodical events that are low latency (would require frequent interrupts)
- Not really bufferable

## Interrupts

- maskable interrupt handler, activated by an interrupt vector that watches the
CPU interrupt request lines.
- Requires a context switch which has significant performance impact if it is too frequent.
- can have a performance and power use impact
- Good for slow devices that only require the OS to wake up occasionally
- or use an interrupt to wake up into polling mode

## Direct Memory Access

- Does not require the CPU be active to transfer the data to memory (moves data concurrently)
- Avoid programmed I/O single-byte at a time
- Interrupts to signal completion
- Steals *some* cycles from CPU
- Requires more complicated hardware
- the I/O bus needs to talk to both the CPU and DMA controller to handle I/O, balancing, routing
- DMA is good for long bursts (eg a hard drive)
- DMA is also good for fixed length bursts
- Depends on device support
- via DMA controller, that can write into main memory
1. Driver asks disk for data
2. Disk sends data to DMA
3. DMA sends data to the memory buffer
4. DMA sends interrupt
- DVMA: variant understanding virtual addresses

## Device Modes

- Direct manipulation setting device data registers
- on unix using `ioctl()`
- Block Devices
- `read()` `write()` `seek()`
- Raw, direct I/O
- Can use Memory-mapped I/O through demand-paging
- Can use DMA
- Character Devices
- `get()` `put()` characters
- line editing libraries and so on
- Network Devices
- Socket interface/ structure/abstraction of the underlying device
- Separates network protocol from network operation
- Can activate callbacks/intterrupts when packets are ready
- Implemented using pipes, FIFOs, streams, queues and many ways.
- Clocks and Timers
- facility for current time, elapsed time
- Programmanble interval timer provided
- on unix covered by the `ioctl()` system calls

## Non-Blocking and Asynchronous I/O

Blocking
: the requesting process is suspended until I/O is completed

Nonblocking
: the I/O call returns as much data as is immediately available.

- used for UI, buffered data copy I/O
- implemented with multithreading
- Returns quickly with the amount of bytes that are read
- use `select()` to know whether data is ready, and `read()` or `write()` to transfer.

Asyncrhonous
: Process runs while I/O executes
- I/O subsystem signals process when I/O is completed
- Difficult to use, need to manage concurrency and signal handling

Vectored I/O
: Unix `readve()`, batching multiple I/O operations, decreases system call overhead,
context switches.

## Kernel Device Management

Buffering
: store data between transfers to cope with speed mismatch.

Caching
: Keep copies of athe data

Spooling
: Queue requests if a device can only process one at a time. (eg printers)

Device reservation
: Restrict exclusive access of device to one process

## Improving Device Performacne

- reduce context switches
- reduce data copying
- reduce interrupts by using large transfers, smart controllers, polling
- use DMA
- use smarter hardware devices, controlelrs
- Balance CPU memory, bus, IO performance for highest throughput
- move user-mode processes / daemons to kernel threads.

# Virtual Machines

Host

: the hardware system being used

VMM / Hypervisor

: Software that creates and runs machines pretending to be a physical host

Guest

: Operating system running on virtual machine

## Types

- Emulation
- Any guest CPU can be emulated on any host CPU
- terrible performance
- Type 0 Hypervisor
- hypervisor is in firmware
- Guests have dedicated resources (cpus, memory)
- Type 1 Hypervisor
- Is a specialised OS
- Implements device drivers for host HW
- Does CPU and memory management
- Can share resources and overcommit
- provides snapshots and cloning
- Type 2 hypervisor
- A eneral purpose os that privides VMM functionality
- Linux + KVM, Windows + Hyper-V
- Treats guests as just another process
- special handling to run guest code natively on cpus (for performance
benefit over emulating the CPU)
- Guest kernel runs in user mode, trap and emulate used when a guest
tries to do something privileged and control is given back in
virtual kernel mode.
- kernel code is slower, but user code is the same speed
- Containers
- Not virtualisation
- Docker, LXC, Solaris Zones
- Only one kernel (the host) running
- Little to no performance loss
- Separation of processes.

# Protection (TODO)

- Access matrix
- columns (objects) = access lists pertaining to an object
- Each object has an access list of tuples `<domain, rights>`
- rows (domains) = capability lists for each domain
- Use the capability list to restrict access to modifying the capability list itself

Implementations of access matrix
- Global Table
- Store tuples `<domain, object, rights set>`
- Really big and slow to access
- Access list for objects
- per object list of <domain, rights-set>
- Slow (every access to an object must be checked, and there are a lot of objects)
- Capability list for domains
- per domain list of <objects, rights>
- Hard to revoke rights to an object, because the permissions are stored with the domain
- Lock/key
- Comrpomise between access and capability list
- Objects have locks (bit patterns)
- Domains have keys (bit patterns)
- Can only access if keys match locks
- Can be passed freely between domains; simple to revoke

# Security

- Detecting intrusions
- repeated access denials
- odd location, ip address change
- non-human-like behaviour
- Password Security
- Hash passwords, or use one half of an asymmetric cipher, restrict user permissions to passwd file, third party authentication, 2nd factor authentication