m physical modeling / IICSM

PHYSICS / ENGINEERING / COMPUTING

Operating systems and computer science models

Understand CPU scheduling, virtual memory, concurrency costs, storage, and queues through derivations and twenty worked examples.

Subject library · 51 guides · derivations & worked examples

Fundamental physics

Space and flight

Materials and transport

Systems and mathematics

Marine and road vehicles

Electrical and computing

Companion site

Matter pathway: atom → solid → liquid → gas → plasma. Quantum mechanics and quantum field theory provide foundations across the pathway; they are not additional phases. This is a connected modeling route, not a universal heating curve. Actual phases depend on pressure, composition, and kinetics.

1. CPU scheduling metrics

Definitions & inputs. A arrival time, F completion time, C service time, S first start; all on one time axis.

  1. Measure completion delay and first-service delay separately.

    Tturn=F−A,Tresponse=S−AT_{turn}=F-A,\quad T_{response}=S-A

  2. Remove actual CPU service to obtain ready-queue wait in this model.

    Twait=Tturn−CT_{wait}=T_{turn}-C

  3. Average over the stated job population, not over arbitrary clock samples.

    Tˉ=∑iTi/n\bar T=\sum_i T_i/n

Interpretation. First-come scheduling and shortest-job scheduling trade fairness and mean delay.

↑ Return to definitions and contents

2. Virtual memory and caches

Definitions & inputs. P page size, a virtual address, h TLB hit probability, tT TLB access, tM memory access.

  1. Split an address into page index and within-page offset.

    VPN=⌊a/P⌋,offset=a mod PVPN=\lfloor a/P\rfloor,\quad offset=a\bmod P

  2. Weight the hit and miss paths.

    E[t]=h(tT+tM)+(1−h)(tT+2tM)E[t]=h(t_T+t_M)+(1-h)(t_T+2t_M)

  3. Rare disk-backed faults may dominate the average latency.

    E[tfault]=(1−p)tnormal+ptpagefaultE[t_{fault}]=(1-p)t_{normal}+pt_{pagefault}

Interpretation. Multilevel walks, caches, and overlap change the latency model.

↑ Return to definitions and contents

3. Concurrency and scaling

Definitions & inputs. s serial fraction, N parallel workers, E efficiency, a per-operation overhead.

  1. Only the parallel portion benefits from more workers.

    TN/T1=s+(1−s)/NT_N/T_1=s+(1-s)/N

  2. Invert normalized time and compare to linear speedup.

    SN=1/[s+(1−s)/N],EN=SN/NS_N=1/[s+(1-s)/N],\quad E_N=S_N/N

  3. Context-switch overhead accumulates with switch frequency.

    Uoverhead=afswitchU_{overhead}=a f_{switch}

Interpretation. Contention, synchronization, coherence, and imbalance can reduce speedup further.

↑ Return to definitions and contents

4. Storage and queues

Definitions & inputs. λ arrivals/s, μ service completions/s, W mean system time, L mean jobs in system.

  1. Queueing delay grows as utilization approaches unity.

    ρ=λ/μ,W=1/(μ−λ)\rho=\lambda/\mu,\quad W=1/(\mu-\lambda)

  2. Little’s law applies more broadly to stable systems with consistent boundaries.

    L=λWL=\lambda W

  3. A simple rotating-disk model adds positioning and sequential transfer.

    tio=tseek+trotation+B/rt_{io}=t_{seek}+t_{rotation}+B/r

Interpretation. Solid-state storage has different latency mechanisms; do not reuse disk rotation formulas there.

↑ Return to definitions and contents

Graphical worked example

Stable M/M/1 queue with service rate 100/s; time includes service and waiting. X axis: Arrival rate (requests/s). Y axis: Mean time in system (s).
Stable M/M/1 queue with service rate 100/s; time includes service and waiting. Related worked calculation · Download SVG · Plot data

Twenty worked examples

Open a problem to see its defined inputs, assumptions, equation, numerical substitution, result, and interpretation. Values are illustrative analytical exercises.

Example 01. Turnaround time

Definitions & inputs. Job arrives at 3 ms and finishes at 15 ms.

  1. Choose the governing model and isolate the requested quantity.

    T=F−AT=F-A

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    T=15−3T=15-3

  3. Evaluate the expression; the result uses the units shown.

    Result=12 ms\mathrm{Result}=12\ {\rm ms}

Interpretation. This includes queueing and service.

↑ Return to definitions and contents
Example 02. Response time

Definitions & inputs. Job arrives at 3 ms; first scheduled at 7 ms.

  1. Choose the governing model and isolate the requested quantity.

    R=S−AR=S-A

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    R=7−3R=7-3

  3. Evaluate the expression; the result uses the units shown.

    Result=4 ms\mathrm{Result}=4\ {\rm ms}

Interpretation. Response time is not completion time.

↑ Return to definitions and contents
Example 03. Waiting time

Definitions & inputs. Turnaround 12 ms, CPU burst 5 ms, no blocked time.

  1. Choose the governing model and isolate the requested quantity.

    W=T−CW=T-C

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    W=12−5W=12-5

  3. Evaluate the expression; the result uses the units shown.

    Result=7 ms\mathrm{Result}=7\ {\rm ms}

Interpretation. Subtract blocked intervals too if they are present.

↑ Return to definitions and contents
Example 04. FCFS mean waiting

Definitions & inputs. Three jobs arrive at zero with bursts 6,2,1 ms, in that order.

  1. Choose the governing model and isolate the requested quantity.

    Wˉ=(0+6+8)/3\bar W=(0+6+8)/3

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    Wˉ=14/3\bar W=14/3

  3. Evaluate the expression; the result uses the units shown.

    Result=4.666667 ms\mathrm{Result}=4.666667\ {\rm ms}

Interpretation. Nonpreemptive FCFS retains arrival order.

↑ Return to definitions and contents
Example 05. Shortest-job mean waiting

Definitions & inputs. Same simultaneous bursts sorted 1,2,6 ms.

  1. Choose the governing model and isolate the requested quantity.

    Wˉ=(0+1+3)/3\bar W=(0+1+3)/3

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    Wˉ=4/3\bar W=4/3

  3. Evaluate the expression; the result uses the units shown.

    Result=1.333333 ms\mathrm{Result}=1.333333\ {\rm ms}

Interpretation. Burst lengths are assumed known in advance.

↑ Return to definitions and contents
Example 06. Round-robin overhead

Definitions & inputs. Useful quantum 4 ms; switch cost 0.1 ms each quantum.

  1. Choose the governing model and isolate the requested quantity.

    fo=ts/(q+ts)f_o=t_s/(q+t_s)

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    fo=0.1/(4+0.1)f_o=0.1/(4+0.1)

  3. Evaluate the expression; the result uses the units shown.

    Result=0.02439024 \mathrm{Result}=0.02439024\ {}

Interpretation. This assumes a switch after every quantum.

↑ Return to definitions and contents
Example 07. Context-switch CPU share

Definitions & inputs. 5000 switches/s, 2 μs cost each.

  1. Choose the governing model and isolate the requested quantity.

    U=ntsU=nt_s

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    U=5000(2×10−6)U=5000(2\times10^{-6})

  3. Evaluate the expression; the result uses the units shown.

    Result=0.01 \mathrm{Result}=0.01\ {}

Interpretation. Cache refill costs are not included unless measured in the switch cost.

↑ Return to definitions and contents
Example 08. Virtual page number

Definitions & inputs. Byte address 12345, page size 4096 bytes.

  1. Choose the governing model and isolate the requested quantity.

    VPN=⌊a/P⌋VPN=\lfloor a/P\rfloor

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    VPN=⌊12345/4096⌋VPN=\lfloor12345/4096\rfloor

  3. Evaluate the expression; the result uses the units shown.

    Result=3 \mathrm{Result}=3\ {}

Interpretation. Page numbering starts at zero.

↑ Return to definitions and contents
Example 09. Page offset

Definitions & inputs. Byte address 12345, page size 4096 bytes.

  1. Choose the governing model and isolate the requested quantity.

    o=a−P⌊a/P⌋o=a-P\lfloor a/P\rfloor

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    o=12345−3(4096)o=12345-3(4096)

  3. Evaluate the expression; the result uses the units shown.

    Result=57 bytes\mathrm{Result}=57\ {\rm bytes}

Interpretation. The offset is unchanged by ordinary page translation.

↑ Return to definitions and contents
Example 10. Page-table storage

Definitions & inputs. 32-bit byte virtual space, 4 KiB pages, 4-byte entry, flat table.

  1. Choose the governing model and isolate the requested quantity.

    B=(232/212)4B=(2^{32}/2^{12})4

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    B=222B=2^{22}

  3. Evaluate the expression; the result uses the units shown.

    Result=4 MiB\mathrm{Result}=4\ {\rm MiB}

Interpretation. Sparse multilevel tables can consume much less for sparse mappings.

↑ Return to definitions and contents
Example 11. Mean final-page waste

Definitions & inputs. Uniform positive allocation remainder across a 4096-byte page; continuous approximation.

  1. Choose the governing model and isolate the requested quantity.

    E[w]≃P/2E[w]\simeq P/2

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    E[w]≃4096/2E[w]\simeq4096/2

  3. Evaluate the expression; the result uses the units shown.

    Result=2048 bytes\mathrm{Result}=2048\ {\rm bytes}

Interpretation. Exact discrete-byte averaging differs by half a byte.

↑ Return to definitions and contents
Example 12. TLB effective access

Definitions & inputs. Hit probability .99, TLB 1 ns, memory 100 ns; serial lookup and one-level walk.

  1. Choose the governing model and isolate the requested quantity.

    E[t]=h(1+100)+(1−h)(1+200)E[t]=h(1+100)+(1-h)(1+200)

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    E[t]=0.99(101)+0.01(201)E[t]=0.99(101)+0.01(201)

  3. Evaluate the expression; the result uses the units shown.

    Result=102 ns\mathrm{Result}=102\ {\rm ns}

Interpretation. The model excludes overlapping lookup and page faults.

↑ Return to definitions and contents
Example 13. Page-fault effective latency

Definitions & inputs. Normal 100 ns; fault path total 10 ms; fault probability 10⁻⁶.

  1. Choose the governing model and isolate the requested quantity.

    E[t]=(1−p)tn+ptfE[t]=(1-p)t_n+pt_f

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    E[t]=(1−10−6)100+10−6(107)E[t]=(1-10^{-6})100+10^{-6}(10^7)

  3. Evaluate the expression; the result uses the units shown.

    Result=109.9999 ns\mathrm{Result}=109.9999\ {\rm ns}

Interpretation. A very small fault probability still adds noticeable average cost.

↑ Return to definitions and contents
Example 14. Working-set footprint

Definitions & inputs. 200 resident pages, each 4 KiB.

  1. Choose the governing model and isolate the requested quantity.

    B=NPB=NP

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    B=200(4)B=200(4)

  3. Evaluate the expression; the result uses the units shown.

    Result=800 KiB\mathrm{Result}=800\ {\rm KiB}

Interpretation. Sharing can reduce distinct physical frames across processes.

↑ Return to definitions and contents
Example 15. Amdahl speedup

Definitions & inputs. Serial fraction .1, four workers.

  1. Choose the governing model and isolate the requested quantity.

    S=[s+(1−s)/N]−1S=[s+(1-s)/N]^{-1}

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    S=[0.1+0.9/4]−1S=[0.1+0.9/4]^{-1}

  3. Evaluate the expression; the result uses the units shown.

    Result=3.076923 \mathrm{Result}=3.076923\ {}

Interpretation. This upper estimate omits parallel overhead.

↑ Return to definitions and contents
Example 16. Parallel efficiency

Definitions & inputs. Speedup 3 with 4 workers.

  1. Choose the governing model and isolate the requested quantity.

    E=S/NE=S/N

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    E=3/4E=3/4

  3. Evaluate the expression; the result uses the units shown.

    Result=0.75 \mathrm{Result}=0.75\ {}

Interpretation. Efficiency is a ratio to ideal linear scaling.

↑ Return to definitions and contents
Example 17. Queue mean system time

Definitions & inputs. M/M/1 λ=80/s and μ=100/s.

  1. Choose the governing model and isolate the requested quantity.

    W=1/(μ−λ)W=1/(\mu-\lambda)

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    W=1/(100−80)W=1/(100-80)

  3. Evaluate the expression; the result uses the units shown.

    Result=0.05 s\mathrm{Result}=0.05\ {\rm s}

Interpretation. The mean includes service, not only queue wait.

↑ Return to definitions and contents
Example 18. Mean outstanding requests

Definitions & inputs. Throughput 200/s, mean system time .03 s, stable queue.

  1. Choose the governing model and isolate the requested quantity.

    L=λWL=\lambda W

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    L=200(0.03)L=200(0.03)

  3. Evaluate the expression; the result uses the units shown.

    Result=6 requests\mathrm{Result}=6\ {\rm requests}

Interpretation. The measurement boundary for L and W must match.

↑ Return to definitions and contents
Example 19. Disk mean rotational delay

Definitions & inputs. 7200 revolutions/minute; random arrival angle.

  1. Choose the governing model and isolate the requested quantity.

    t=12(60/rpm)t=\tfrac12(60/\mathrm{rpm})

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    t=30/7200t=30/7200

  3. Evaluate the expression; the result uses the units shown.

    Result=4.166667 ms\mathrm{Result}=4.166667\ {\rm ms}

Interpretation. This applies to a rotating disk and excludes seek time.

↑ Return to definitions and contents
Example 20. Sequential transfer time

Definitions & inputs. 100 MB at 200 MB/s, decimal units; positioning excluded.

  1. Choose the governing model and isolate the requested quantity.

    t=B/rt=B/r

  2. Insert the stated inputs in consistent units or the explicitly defined normalized units.

    t=100/200t=100/200

  3. Evaluate the expression; the result uses the units shown.

    Result=0.5 s\mathrm{Result}=0.5\ {\rm s}

Interpretation. Controller, filesystem, and contention overhead may add latency.

↑ Return to definitions and contents

Symbols and units

Each derivation and problem defines its own symbols and inputs. Symbols may be reused with different meanings in other subjects. Keep units consistent, retain sufficient precision during calculation, and apply the stated validity limits.