Operating Systems
Scheduling your processes…
Initializing Sorting Algorithms...
Sorting
Trees
Graphs
Preparing interactive visualizations...
Operating Systems
Scheduling your processes…
An operating system is a set of policies for sharing one machine. Watch a scheduler build its Gantt chart, page frames fill and evict, a disk head sweep, and threads race, block and deadlock.
The units a scheduler hands the CPU to: separate address spaces, the process control block, and what threads share.
fork: O(1) CoWseparate ASOS SchedulingFCFS, SJF, SRTF and Priority on the same workload — watch the Gantt chart grow and the average waiting time move.
O(n log n)O(n)Scheduling PolicyA ready queue that cycles every time quantum. Shrink the quantum and response improves while context switches pile up.
O(1) per dispatchO(n) queueTime SlicingPage tables, the TLB and page faults — the machinery that page replacement has to manage when RAM runs out.
O(1) TLB hit4KB pagesMMU + Page TableFIFO, LRU and Optimal deciding which frame to evict — including the reference string where more frames cause more faults.
O(n·f)O(f) framesEviction PolicyFirst, best, worst and next fit carving holes in memory until a request fails with enough space free — then compaction.
O(h) per requestO(h) hole listContiguous AllocationAllocation, Max, Need and Available — the safety check that finds a safe sequence before any request is granted.
O(m·n²)O(m·n)Deadlock AvoidanceCollapse a resource-allocation graph into a wait-for graph and walk it for a cycle, with the four Coffman conditions on screen.
O(V + E)O(V)Cycle DetectionFCFS, SSTF, SCAN, C-SCAN, LOOK and C-LOOK plotted as head movement across the cylinders, with total seek distance.
O(n log n)O(n)Seek OptimisationBlocks, inodes, directory entries and journaling — what sits above the disk head that disk scheduling moves.
O(depth) lookup4 KB blocksInode + JournalTime slicing, a first race condition, mutex locks and a two-lock deadlock — the overview the next three pages go deeper on.
O(1) ctx switch1–8 MB/threadShared MemoryTwo threads run counter++ as load, add, store. Explore all twenty interleavings, then make them all correct with a mutex.
C(2k, k) interleavingsO(1) sharedCritical SectionA bounded buffer guarded by empty, full and mutex semaphores — producers and consumers blocking and waking each other.
O(1) per operationO(N) bufferSemaphoresFive philosophers grab their left fork and deadlock. Number the forks, take the lower one first, and the cycle cannot close.
O(1) per pick-upO(n) forksResource OrderingProtection rings and the trap into the kernel — how a process asks the OS for anything on this page.
~50–200 nsring 3 → 0Trap + DispatchL1, L2 and L3 cache lines and locality — the same hit-or-miss question page replacement asks, one level closer to the core.
L1: ~4 cycles64-byte linesCache HierarchyNamespaces and cgroups: isolation built from the kernel features a scheduler and memory manager already have.
ms startupshared layersNamespaces + cgroupsYour code never owns the CPU, the memory or the disk — it is lent them. Knowing the lending rules explains latency spikes, out-of-memory kills and why a busy machine feels slow.
No scheduler, eviction policy or disk algorithm wins everywhere. Running them side by side on the same input shows exactly what each one gives up.
Race conditions and deadlocks appear only under some orderings of perfectly correct-looking code. Stepping through those orderings is the fastest way to learn to see them.