Operating Systems formula sheet

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.

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.

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.

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).

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.

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.

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.