exam2

Scheduler

Part of the OS kernel that decides which process runs and for how long

Scheduling Algorithm

Determines which process to run next based on a policy

First In First Out (FIFO)

Runs processes in the order they arrive, to completion

Shortest Job First (SJF)

Runs the process with the shortest total runtime next

Shortest Time to Completion First (STCF)

Preempts current process if a new one has shorter remaining time

Round-Robin (RR)

Each process gets a fixed time slice before being preempted and placed at the end of the queue

Turnaround Time

Completion Time - Arrival Time

Response Time

First Run Time - Arrival Time

Throughput

Number of processes completed per unit time

CPU-bound process

Spends most time doing computation

I/O-bound process

Spends most time waiting for I/O

Timer Interrupt

Preempts a process if it has exceeded its timeslice

System Call Trap

Scheduler may run after a system call if higher priority task is available

MLFQ

Scheduling algorithm with multiple priority queues

MLFQ Rule 1

Higher priority process runs before lower priority

MLFQ Rule 2

Equal priority processes run in round-robin

MLFQ Rule 3

New process starts in highest priority queue

MLFQ Rule 4a

Process that uses full timeslice is demoted

MLFQ Rule 4b

Process that yields early keeps its priority

MLFQ Rule 5

All processes promoted to top after time S to prevent starvation

CFS Goal

Divide CPU time fairly among processes using vruntime

Virtual Runtime (vruntime)

Amount of CPU time a process has used, adjusted by weight

Nice Value

Ranges from -20 (high priority) to +19 (low priority); default is 0

CFS Timeslice

sched_latency / number of processes

Process with lowest vruntime

Scheduled next

Lottery Scheduling

Each process gets tickets; one ticket is picked at random to choose next process

More tickets

Higher chance of being scheduled

Real-Time System

Must meet both logical and timing correctness

Hard Real-Time System

Missing a deadline is a system failure

Soft Real-Time System

Occasional deadline misses tolerated

Earliest Deadline First (EDF)

Dynamic priority; task with earliest deadline gets CPU

Rate Monotonic Scheduling (RMS)

Static priority; task with shortest period gets highest priority

Utilization (ui)

Execution Time / Period

Total Utilization (U)

Sum of all task utilizations

Priority Inversion

High-priority task is blocked by a lower-priority one holding a needed resource

Priority Inheritance

Temporarily boosts priority of blocking task to unblock high-priority one

Pipe

One-way communication channel between processes

pipe(int fd[2])

Creates a pipe; fd[0] for reading, fd[1] for writing

dup2(oldfd, newfd)

Duplicates a file descriptor; used to redirect input/output

Socket

Endpoint for network communication

SOCK_STREAM

Used for TCP (reliable, ordered, byte-stream)

SOCK_DGRAM

Used for UDP (unreliable, message-oriented)

AF_INET

Address family for IPv4 Internet

bind()

Assigns address to socket

listen()

Marks socket as passive to accept connections

accept()

Accepts an incoming connection

connect()

Initiates a connection to server

read(), write()

Used for reading/writing on socket

TCP

Reliable, ordered, connection-oriented protocol

UDP

Unreliable, unordered, connectionless protocol

Filesystem

Collection of files and directories organized hierarchically

Superblock

Stores metadata about filesystem (e.g., size, number of inodes)

Inode

Metadata for a file (owner, size, timestamps, data block pointers)

Directory

Special file mapping names to inode numbers

Extents

In ext4, store starting block + length of contiguous blocks

Data Block

Contains actual file content

Indirect Pointer

Pointer to a block of pointers

Double Indirect Pointer

Pointer to a block of indirect pointers

Triple Indirect Pointer

Pointer to a block of double indirect pointers

Journaling

Write-ahead log of updates to ensure crash consistency

Metadata Journaling

Only metadata (not data) is written to journal

Journal Write

Write update to journal

Journal Commit

Write commit block

Checkpoint

Apply updates to actual disk

Free Journal Entry

Mark journal transaction as complete

Polling

CPU repeatedly checks if device is ready

Interrupts

Device notifies CPU when ready

PIO (Programmed I/O)

CPU transfers data to/from device

DMA (Direct Memory Access)

Device transfers data directly to memory

Memory-Mapped I/O

Device registers mapped to memory addresses

SJF Average Turnaround Time Formula

(Completion Time - Arrival Time) for each / number of processes

CFS selects task with

Lowest vruntime

CFS time slice is same for all tasks

False

Scheduler that preempts dynamically

Earliest Deadline First (EDF)

When high priority waits for low priority holding resource

Priority Inversion

Pipes communication direction

One-way

Pipes require same machine?

True

User Datagram Protocol (UDP)

Preserving message boundaries

Structure with file metadata

Inode

Directory maps

Filename, Inode number

Journaling doesn't store

Data blocks

Third journaling phase

Checkpoint

Total utilization U = sum of ei/pi

Real-time task system scheduling

Crash causes space leak if order is

db -> i -> dm

Hybrid I/O method order

Polling then interrupt (False on "interrupts then polling")