CS2106 Notes

Layered Systems

• Generalisation of monolithic system
• Upper layers make use of lower layers
  • Highest: User Interface
  • Lowest: Hardware

Client-Server Model

• Variation of microkernel
• 2 classes of processes
  • Client processes request service from server process
  • Server process built on top of microkernel
  • Client & Server can be on separate machines

Type 1 Hypervisor

• Similar to normal OS
• Provides individual virtual machines to guest OS

Type 2 Hypervisor

• Runs in a host OS
• Don't need to emulate everything, because there is a real OS below
• e.g. VirtualBox

Stack Frame

• Return address of the caller
• Arguments for the function
• Storage for local variables
• Stack Pointer points to top of stack (first free location)
  • Either points above first (start of free space), or at first (aka last item on stack)
  • May change while a function is executing; data cannot be reliably referenced through constant offsets
  • Used for allocating space for local variables in middle of function (i.e. int i = 0; not at start of function)
  • Used for returning to caller function after frame pointer is restored
• Frame Pointer points to fixed location (doesn't change in function execution) in a stack frame
  • Other items are accessed as displacement (+-) from FP
  • Usage of FP is platform dependent (some don't have FP); FP is not actually required

One Way

These are done by compiler, not OS or HW.

Setup

1. Caller: pass parameters with registers and / or stack
2. Caller: save return PC on stack
3. Transfers control to Callee
4. Callee: save registers used by caller, old FP, old SP
5. Callee: allocate space for local variables of callee on stack
6. Callee: adjust SP to point to new stack top

Teardown

1. Callee: place return result on stack (if applicable)
2. Callee: restores saved registers, FP, SP
3. Transfers control to Caller
4. Caller: utilise return result (if applicable)
5. Caller: resumes execution

Saved Registers

• Register Spilling
  • Use memory to temporarily hold GPR values
  • GPR then used for other purpose
  • Then, restore GPR afterwards

Context Switch

• Saves state of A into PCB for A
• Reloads state of B from PCB of B
• Hardware Context: GPR, PC, SP, FP, ...

Interrupt Handling

1. PUSH (PC) -- hardware
2. PUSH (status register) -- hardware
3. Disable interrupts in status register -- hardware
4. Read Interrupt Vector Table (IVT) entry by using syscall number as index -- hardware
5. Switch to kernel mode -- hardware
6. PC <- handler_XX() -- hardware
7. handler_XX() execution -- software

IVT = table where OS stores addresses of all interrupt handlers, one of the first few things created by OS

Synchronisation Behaviours

Blocking (Synchronous)

• send(): Sender is blocked until message is received
  • Can use this to rendezvous (sync up processes)
  • No intermediate buffering by OS is required
• receive(): Receiver is blocked until message has arrived

Non-Blocking (Asynchronous)

• send(): Sender resumes operation immediately (if message buffer isn't full, either blocks or errors)
• receive(): If no message, resume without a message (rarely used)

Tradeoffs

• Pros
  • Applicable beyond a single machine
  • Portable, easily implemented on many platforms and environments; Parties on different platforms can communicate
  • Synchronisation is implicit
  • No data racing
• Cons
  • Inefficient because OS is involved with every message
  • Requires packing / unpacking the message into a supported message format

Unix Pipes

Unix Pipes is an example of a message passing IPC.

• Producer P, Consumer Q (P --> Q)
  • Writers wait when buffer is full
  • Readers wait when buffer is empty
  • Can have multiple readers / writers (although normal shell pipe has only one of each)
• Data is FIFO, like an anonymous file
• May be
  • unidirectional (half-duplex): one write-end, one read-end
  • bidirectional (full-duplex): both ends can read / write
• int pipe(int fd[])
  • returns 0 for success; non-0 for errors
  • fd[0]: reading end
  • fd[1]: writing end
• close(fd[0]), write(fd[0]), read(fd[0], buf, sizeof(buf)), where char buf[N]
  • Need to close the pipes not being used.
• Can redirect stdin / stdout / stderr to one of the pipes using dup

Unix Signal

• signal(SIGSEGV, signal_handler)
  • void signal_handler(int signo)
  • Replaces the handler for Segmentation Fault with our own signal_handler

Batch

• Turnaround time for a task
  • Total time taken: finish time - arrival time (when it became ready)
  • Related to waiting time: time spent waiting for CPU
• Throughput
  • Number of tasks finished per unit time
• Makespan
  • Total time from start to finish to process all tasks
• CPU utilisation
  • Percentage of time CPU is used
• Waiting Time (for CPU)
  • turnaround time - work done - IO waiting time
    
• First Come First Serve (FCFS)
  • non-preemptive; does not starve (number of tasks in front of task X is always decreasing)
  • Convoy Effect: CPU bound Task A followed by many IO-bound Tasks X (Task A caused all those IO bound tasks to wait for CPU, when they could have completed first, and started waiting for IO)
• Shortest Job First (SJF)
  • Needs to know / guess total CPU time for a task in advance.
    • Predicted$_{n+1}$ = $\alpha$ * Actual$_n$ + (1 - $\alpha$) * Predicted$_n$, where 0 <= $\alpha$ <= 1
  • non-preemptive; starves (consider a very long job, while shorter jobs keep coming in)
  • guarantees smallest average waiting time (use exchange argument)
• Shortest Remaining Time (SRT)
  • new job with shorter remaining time can preempt currently running job (good service for short jobs that arrive late)
  • preemptive version of SJF; starves (similar to SJF)
  • does not guarantee smallest average waiting time

Interactive

• Scheduler takes over CPU through interrupts
• OS ensures timer interrupt cannot be intercepted by any other program
• Interval of Timer Interrupt (ITI)
  • OS scheduler invoked on every timer interrupt (typically 1ms to 10ms)
• Time Quantum
  • Execution duration given to process (can be constant or variable across processes)
  • Must be a multiple of ITI (commonly 5ms to 100ms)
  • Higher time quantum => less responsive / more waiting time
  • Lower time quantum => more time wasted context switching (overhead)

Test and Set (Atomic Instruction)

• TestAndSet Register, MemoryLocation (atomic machine instruction)
  • Loads current content at MemoryLocation into Register
  • Stores a 1 into MemoryLocation

Semaphore

Can be initialised to any non-negative integer value. The following two operations are atomic.

• P() = Wait() = Down()
  • If S <= 0, blocks (goes to sleep)
  • Decrements S
• V() = Signal() = Up()
  • Increments S
  • Wakes up one sleeping process, if any (depends on library implementation)
  • Never blocks

$S_{\text{current}} = S_{\text{initial}}$ + (number of Signal() executed) - (number of Wait() completed, aka succeeded)

• General / Counting Semaphore
  • S >= 0 (S = 0, 1, 2, ...)
  • Only provided for convenience, can be mimicked by Binary Semaphore
• Binary Semaphore
  • S = {0, 1}
• Mutex (Mutual Exclusion)
  • Special case of binary semaphore
  • Used to guard a resource

The following can still cause deadlock (initially, P = 1, Q = 1). Consider order: A.Wait(P), B.Wait(Q), A.Wait(Q), B.Wait(P).

// Process A
Wait(P)
Wait(Q)
// code
Signal(Q)
Signal(P)

// Process B
Wait(Q) // Waits are swapped from Process A
Wait(P)
// code
Signal(P)
Signal(Q)

Semaphore: Critical Section

mutex = 1 // Binary Semaphore

wait(mutex)
// critical section
signal(mutex)

Semaphore: Safe-Distancing Problem

sem = N // General Semaphore

wait(sem)
// safely eat
signal(sem)

Semaphore: General Synchronisation

sem = 0

P1() {
  produce(X)
  signal(sem)
}
P2() {
  wait(sem)
  consume(X)
}

Semaphore: Barrier

arrived = 0, mutex = 1, waitQ = 0

Barrier(N) {
  wait(mutex)
  arrived++
  signal(mutex)
  if (arrived == N)
    signal(waitQ)

  wait(waitQ)
  signal(waitQ)
}

Producer-Consumer

• producers produce when buffer isn't full
• consumers consume when buffer isn't empty

notEmpty = 0, notFull = k, mutex = 1, in = out = 0

Produce(N) {
    while (TRUE) {
        Produce item
        wait(notFull)
        wait(mutex)
        buffer[in] = item
        in = (in+1) % k
        signal(mutex)
        signal(notEmpty)
        // Consume (for consumer)
    }
}
// Consumer same but flipped

Alternatively, use message passing with a fixed capacity. Everything is handled by system.

Reader-Writer

Writer has exclusive access, readers can access with other readers.

// Note: this version starves the Writer
roomEmpty = 1, mutex = 1, nReader = 0

Writer(N) {
    wait(revDoor) // to prevent starvation
    wait(roomEmpty)
    // modify data
    signal(roomEmpty)
    signal(revDoor)
}
Reader(N) {
    wait(revDoor) // immediately let reader through
    signal(revDoor) // if no writer
    wait(mutex)
    nReader++
    if nReader == 1 { // first reader waits
        wait(roomEmpty)
    }
    signal(mutex)
    // read data
    wait(mutex)
    nReader--
    if nReader == 0 { // last reader signals
        signal(roomEmpty)
    }
    signal(mutex)
}

Dining Philosophers

• five single chopstick between each pair of philosophers
• when he wants to eat, has to acquire both left & right chopsticks
• goal: starvation free, deadlock free, livelock free
• solution: allow at most $k-1$ of them to eat => deadlock is impossible

// Limited Eaters Solution
seats = k - 1

Philosophers() {
    while (TRUE) {
        Think()
        wait(seats)
        take(LEFT)
        take(RIGHT)
        Eat()
        put(LEFT)
        put(RIGHT)
        signal(seats)
    }
}

// Tanenbaum Solution
// no deadlock cos each philosopher only waits for own semaphore
int state[N]
sem_t mutex = 1, s[N]

Philospher(int i) {
    while (TRUE) {
        Think()
        take(i)
        Eat()
        put(i)
    }
}
take(int i) {
    wait(mutex)
    state[i] = HUNGRY
    safeToEat(i)
    signal(mutex)
    wait(s[i])
}
safeToEat(int i) {
    if state[i] == HUNGRY
        && state[LEFT] != EATING && state[right] != EATING
    {
        state[i] = EATING
        signal(s[i])
    }
}
put(int i) {
    wait(mutex)
    state[i] = THINKING
    safeToEat(left) // notify neighbours to eat
    safeToEat(right)
    signal(mutex)
}

Memory Partitioning

Paging Scheme (* predominant)

• physical memory is split into regions of fixed size (physical frames)
  • frame sizes are decided by hardware
  • kept as powers of 2
• similarly, logical memory is split into regions of same size (logical pages)
  • physical frame size == logical page size (for now)
• at execution time, pages of process are loaded into any available memory frame
  • logical memory space remain contiguous
  • occupied physical memory space may be disjoint
  • requires Page Table (lookup table that translates Logical -> Physical)
    • PhysicalAddress = FrameNumber * sizeof(PhysicalFrame) + offset
      • offset = displacement from beginning of physical frame
• observations
  • external fragmentation not possible, because every single free frame can be used
  • internal fragmentation is insignificant because only one page per process is not fully utilised, i.e. 10.5 (only 0.5 wasted)
  • clean separation of logical and physical space (more flexibility, simple address translation)

Segmentation Scheme

Split logical memory space into disjoint physical segments: Text, Data, Heap, Stack. Set permissions for everything in a segment (as opposed to page-by-page). Enables easier growing / shrinking at execution time. Segments can be of different sizes.

Each memory segment:

• has a name: for ease of reference
• has limit: to indicate exact range of segment

All memory references specified as <SegmentID + Offset>, i.e. <1 + 245>.

• SegID used to look up <Base, Limit> of segment in Segment Table (small lookup table, don't need a TLB, just use 4 registers)
  • PhysicalAddress = Base + Offset
  • Offset < Limit for valid access

Pros & Cons

• pros
  • each segment is independent contiguous memory space
  • more efficient bookkeeping
  • segments can grow / shrink, and can be protected / shared independently
• cons
  • segmentation requires variable-sized contiguous memory segments
  • causes external fragmentation

Growing Stack and Heap towards each other is the best as it is the most flexible, and accounts for both heavy stack and heavy heap use cases.

Segmentation with Paging

Segmentation but solves external fragmentation issue. Each segment has own Page Table.

<Segment, Logical Page, Offset> -> <Physical Frame, Offset>

Accessing a Page

1. check Page Table (HW)
   1. if page X is memory resident: just access as usual. done.
   2. else: raise Page Fault exception
2. Page Fault: OS takes control (OS from here onwards)
3. locate page X in secondary storage
4. load page X into physical memory
5. update Page Table
6. go to step 1 to re-execute same instruction (but with the page now in-memory)

i.e. worst case requires 3 memory accesses (check Page Table, re-check Page Table, read data)

Transfer usually done by DMA (Direct Memory Access) Controller (a HW part), so CPU is free. Process will be changed to blocked state so other processes can run. Process will not be blocked if no Page Fault occurs!

Page Fault most of the time: known as trashing (not good)

• use locality principles to amortise cost of loading pages
  • temporal locality: likely to be used again
  • spatial locality: nearby memory addresses likely to be used soon, i.e. arrays
• higher levels of memory hierarchy stores "hotter" subset of lower level

Demand Paging

• process starts with no memory resident pages (all resident bits are F) - even first instruction will Page Fault!
• only allocate page when Page Fault
• pros: fast startup, small memory footprint (minimise usage of in-memory)
• cons: process may appear sluggish due to multiple Page Faults, might cause other processes to trash

Page Table Structure

Problems with huge table: high overhead, Page Table can occupy several frames.

Page Replacement Algorithms

If no free physical memory frame during Page Fault, have to evict a free memory page. If dirty, have to write back.

$T_{access} = (1-p) * T_{mem} + p * T_{page\_fault}$, where $p$ is probability of Page Fault, $T_{mem}$ is access time for memory-resident page, $T_{page\_fault}$ is access time for Page Fault. Need $p < 0.000002$ to massively reduce access time.

• Optimal Page Replacement (magic algorithm)
  • replace page not needed for longest period of time
  • guarantees minimum number of Page Faults
• FIFO: evicts oldest memory page based on loading time
  • OS maintains queue (no need HW)
  • Belady's Anomaly: increased frames -> increased Page Faults because does not exploit temporal locality
• LRU: evicts least recently used memory page (good in practice)
  • two possible implementations (requires HW support)
    • PTE has "time-of-use": update whenever referred
      • replace the page with smallest "time-of-use"
      • problem: need to linearly scan, and "time-of-use" might overflow...
    • OS maintains "stack"
      • entries can be removed from anywhere in stack for updating (then pushed to top)
      • easy eviction: just pop from bottom of stack
      • hard to implement in HW (HW caches do something like this)
• Clock / Second-Chance - implemented with Circular Linked List in HW
  • maintain reference bit (1 = accessed since last reset, 0 = not accessed)
  • take the page if reference bit == 0
  • degenerates into FIFO when all pages have reference == 1

* When replacing a frame, you take its position!

Frame Allocation

$N$ physical memory frames, $M$ processes that want frames

• allocation
  • equal allocation: each process gets $N/M$ frames
  • proportional allocation: each process gets $(size_p/size_{total})*N$ frames
• replacement
  • local replacement: select from own process
    • number of frames for each process is constant (stable performance between multiple runs)
    • thrashing is limited to one process
    • if not enough frames: hinders progress :/
    • can use up I/O bandwidth and still degrade performance
  • global replacement: select from any process (can be other processes)
    • allows self-adjustment between processes
    • one bad process can affect other processes!
      • can have Cascading Trashing (Trashing page steals from others and causes others to thrash)
    • number of frames for each process can differ run to run

Working Set Model

Working Set = set of virtual pages that are currently resident in physical memory, is relative constant in a period of time = $W(t, \Delta)$, $\Delta$ is interval of time

• when Working Set is stable and well-defined: Page Faults are rare
• when transitioning to new Working Set: many Page Faults
• allocate enough frames for pages in $W(t, \Delta)$ to reduce possibility of Page Faults
  • transient region: working set changing in size
  • stable region: working set almost same for long time
  • $\Delta$ too small: may miss pages in current working set
  • $\Delta$ too large: may contain pages in different working set (wasted)

File Data: Access Methods

• Sequential Access (i.e. magnetic tapes, audio cassette)
  • must be read in order, from the start. cannot skip, but can rewind
• Random Access (byte-based access) - used by Unix & Windows
  • Read(offset), Seek(offset): must explicitly state offset
• Direct Access (random, but record-based instead)
  • used for fixed-length records, allows random access to any record directly
• generic operations
  • create: new file is created with no data
  • open: to prepare for further file ops
  • read: read data to file, usually from current position
  • write: write data to file, usually from current position
  • repositioning / seek: move current position (without read / write)
  • truncate: removes data between specified & end of file
• OS provides file ops as syscalls to provide protection, concurrent and efficient access (some are thread-safe)
• info kept for opened file (in OS)
  • file pointer: tracks current position in file
  • file descriptor (fd): unique ID of file
  • disk location: actual file location on disk
  • open / reference count: how many processes has this file opened (so can tell when to remove from table)

Process Sharing Files (Unix)

• file is opened twice from two processes
  • two entries in system-wide open-file table (with ref counts of 1), but point to same V-node (with ref count of 2)
  • requires different entries because offset can be different!
• two processes using same open file table entry (because of fork)
  • I/O changes offset for both processes
  • ref count = 2

File Block Allocation: Contiguous

• only need to store table of <file, start, length>, where length is number of contiguous blocks
• makes use of sequential access, which is easy & faster (because hard-disk rotate / seek) than random access
• has external fragmentation, hard to expand file (might need to reallocate new space)

File Block Allocation: Linked List

• store table of <file, start, end>, where start is the starting block of the LL, end is used for appending to file
  • each disk block stores actual file data & next disk block number (as pointer)
• no more external fragmentation
• random access is slow because need to traverse linked list in-storage (and data might not be in same sector)
• overhead for storing pointer to next block
• less reliable (because pointer might be incorrect)

File Block Allocation: File Allocation Table (FAT)

• move all block pointers into a single FAT table, in Kernel memory at all time
  • pulled & flushed on boot up & shut down respectively
• uses linked list idea, but doesn't store the pointers in the node, uses FAT instead
• faster random access because linked list is traversed in memory
• FAT can be huge & consumes a lot of memory space

File Block Allocation: Indexed Allocation

• don't track every file in the system, each file has a index block:
  • an array of disk block addresses
  • IndexBlock[N] = Nth block address
• less memory overhead, only index blocks of opened files are in-memory
• still has fast direct access
• limited maximum file size: maximum number of blocks for file == number of index block entries available
• still has overhead of index block

Free Space Management: Bitmap

• each disk block represented by 1 bit (occupied = 0 by convention)
• easy to manipulate; but requires sequential scan to find first free block
• but, need to store in-memory for efficiency
• constant time updating because bitmap $\ne$ array

Free Space Management: Linked List

• each disk block contains:
  • number of free disk block numbers
  • OR pointer to next free space disk block
• easy to locate first block
• only first pointer is needed in-memory (but can cache the others)
• cons: high overhead (compared to just bits)

Directory: Linear List

• linear list, each entry contains:
  • file name + metadata
  • file information (or pointer to file information)
• locating files require doing a linear search through this list
  • inefficient for larger directories / deep tree traversal
  • can use cache to cache the latest few searches

Directory: Hash Table

• hash table of size $N$ (usually resolved by chaining), hashed by file name
• fast lookup
• but relies on good hash function & need to expand table

Microsoft FAT File System

FAT-K = use K bits

• file data are allocated to
  • number of data blocks / data block clusters (pointers kept in FAT)
  • file allocation information kept as linked list
• FAT ($2^K - 1$ entries, each entry is $K$ bits)
  • one entry per data block / cluster
  • store disk block information (free?, next block (if occupied)?, damaged?)
    • FREE (unused block), BlockNumber (of next block), EOF (i.e. NULL pointer), BAD (unusable block - may be because of disk error)
  • OS caches this in RAM to facilitate LL traversal
• directory is stored as
  • special type of file
  • root directory / is stored in special location (the rest are stored in regular data blocks)
  • each file / subdirectory within directory is represented as directory entry
• directory entry
  • fixed-size 32-bytes: contains name + extension (8 + 3 characters), attributes (permissions, dir / file flag, hidden flag, ...), creation date + time, first disk block + file size, first disk block index (K-bits)

Extended-2 FS (Ext2)

• disk space is split into blocks (which are grouped into block groups)
• superblock (duplicated in each block group for redundancy): describes whole FS, includes:
  • total i-node number, i-nodes per group
  • total disk blocks, disk-blocks per group
• group descriptor table (duplicated in each block group for redundancy): has a group descriptor for each block groups, contains:
  • number of free disk blocks, free i-nodes
  • location of disk block bitmaps & i-node bitmaps
• partition information:
  • block bitmap, i-node bitmap - keeps track of usage status of blocks in block group (1 = occupied, 0 = free)
  • i-node table: array of i-nodes (accessed by unique index)
  • contains only i-nodes of this block group
• each file / directory is described by i-node (index node) - each i-node is 128bytes, contains:
  • file metadata
  • 15 disk block pointers (assuming 1KiB per block)
    • first 12: direct blocks (fast for small files)
    • 13th: single indirect blocks
      • 1KiB = $2^{10}$ bytes, and 4 bytes for FAT-32 => stores $2^{10} / 4 = 256$ entries, so 256 * 1KiB = 256KiB
    • 14th: double indirect blocks
      • $256^2$ * 1KiB = 64MiB
    • 15th: triple indirect blocks (but can still handle large files)
      • $256^3$ * 1KiB = 16GiB
• root directory / stored at special i-node number (e.g. 2)
• directory structure: data blocks of directory stores LL of directory entries for files / subdirectories in this directory, each entry contains:
  • i-node number for that file / subdirectory
  • size of directory entry (for locating next directory entry)
  • length of file / subdirectory name
  • type (file / subdirectory / other type)
  • file / subdirectory name (up to 255 chars)