The whole Operating Systems formula sheet, to print

F is the number of fork() calls that actually execute, summed over all processes; assumes every fork succeeds.

n fork() calls one after another with no condition and no exit; the same holds for a loop that runs n times with a fork in it and no break. New (child) processes created = 2^n - 1.

For a loop body of fork(); followed by printf("...\n"); with every process continuing the loop and each printf appearing once per process that executes it: iteration k (counting from 1) is executed by 2^k processes.

q is the length of the useful time slice before each switch and s is the context-switch time, in the same unit; assumes every slice is used in full. If each process instead runs only for T < q before blocking, use T in place of q.

Number of distinct interleavings of two independent sequences of m and n instructions, each sequence keeping its own order. Different interleavings may still give the same output.

R(S) is the set of variables statement S reads and W(S) the set it writes. If all three intersections are empty, S1 and S2 give the same result whichever runs first or if they run in parallel.

For the blocking form above: S_0 is the initial value, n_w the number of wait operations executed (including blocked ones) and n_s the number of signal operations executed. If S < 0 then -S processes are blocked. (In the busy-waiting form, n_w counts completed waits only.) Some questions use a form in which wait blocks without decrementing when S = 0, and signal wakes a blocked process instead of incrementing. There the final value is max(0, S_0 + n_s - n_w) and the number blocked is max(0, n_w - n_s - S_0).

Remaining claim of process $P_i$ for resource type $R_j$.

Free instances of $R_j$; Total is the number of instances of $R_j$ in the system.

Single resource type, $n$ processes, each needing at most $k$ units (and possibly asking for all $k$), units requested one at a time and held while waiting. Deadlock is impossible iff $R\ge n(k-1)+1$; with $R\le n(k-1)$ a deadlock can occur.

Same assumptions, $k\ge 2$. Follows from $n(k-1)+1\le R$.

Holds for every scheduling algorithm.

Valid when the process has a single CPU burst and does no I/O. With I/O bursts, WT = TAT − (total CPU time) − (total I/O time).

In a non-preemptive algorithm, RT equals WT when each process has a single CPU burst and does no I/O.

Total elapsed time runs from time 0 to the last completion unless the question defines it otherwise. Idle gaps and context-switch time count as not busy.

W = time the process has waited so far in the ready queue, S = its burst time. Recompute it at every instant the CPU becomes free.

t_n = actual length of the nth CPU burst, tau_n = its predicted value, tau_1 = the given initial guess.

For n processes that all keep using full quanta, with a context switch of s ms between any two processes. The second form is the largest quantum for which every process gets the CPU again within T ms. With s = 0, the k-th process in a queue formed at time 0 first gets the CPU within (k − 1)q.

Valid when every process uses its full quantum q and each dispatch costs a context switch of s ms.

Use when context-switch time and idle gaps are given or can be read from the Gantt chart. The denominator is the total elapsed time.

n is the logical address width in bits; the page offset has d bits and the page number n-d bits.

Physical address = frame number bits followed by d offset bits.

e is the size of one page-table entry in bytes; the number of entries equals the number of pages in the logical address space.

Extra bits are those the question lists (valid, dirty, protection and so on). Round up to whole bytes; round to a power of two only if the question says so.

k is the minimum number of levels when each table occupies one page; n-d is the number of page-number bits. If n-d is not a multiple of the bits per level, the convention used here gives the leftover bits to the outermost table, which then occupies less than a page.

One entry per frame; e is the entry size in bytes (an entry holds the process id and page number).

t = TLB lookup time, m = main-memory access time (same unit as t), k = number of page-table levels walked on a miss. The TLB is searched first on every reference, and a miss then costs k extra memory accesses. Assumes no page faults and page-table entries not cached elsewhere. If a question says the TLB lookup overlaps or is ignored, set t = 0.

k page-table accesses plus one data access.

Offsets run from 0 to limit - 1; an offset equal to the limit is out of range.

Weighted average of a hit-path access (time m) and a faulting access (total time S).

Use this form when the question gives S as a delay added on top of the normal memory access, so a faulting access costs m + S.

d is the fraction of faults whose victim is dirty; S_clean and S_dirty are the service times for a clean and a dirty victim.

Keeps EAT at most (1+ε)·m, i.e. a slowdown of at most 100ε percent, with S the total time of a faulting access. Follows from (1-p)m + pS ≤ (1+ε)m.

s_i is the size (in pages) of process i and m the number of available frames. If a share is not whole, use the rounding the question states (for example, round down and keep the leftover frames free), keeping each share at or above the minimum.

If D is greater than the number of available frames m, thrashing is likely; the OS should suspend a process (freeing its frames). If D is at most m, the OS may start another process.

Applies when each data block stores its own next-block pointer of $p$ bytes.

A pointer or FAT entry must be able to name every one of the $N_{\text{blocks}}$ blocks; questions usually round this up to whole bytes.

One entry per disk block; the entry must be wide enough to hold any block number.

Number of block addresses that fit in one index (indirect) block.

With direct, single, double and triple indirect pointers. Drop the terms for levels the i-node does not have. This is the limit imposed by the pointer scheme; a pointer width or file-size field can impose a smaller limit.

One bit per block of size $B$ bytes.

Assumes the same number of sectors on every track.

$H$ heads (surfaces), $S$ sectors per track, and $c$, $h$, $s$ all numbered from 0, with sectors numbered across a whole cylinder before moving to the next cylinder. If sectors are numbered from 1, use $s-1$ in place of $s$.

Add controller or queueing overhead only if the question gives it.

On average the wanted sector is half a turn away. If the question says worst case, use a full $T_{\text{rot}}$.

The head reads one full track per rotation, so time is the fraction of a track passed under the head times the rotation time.

One track passes under the head per rotation.