Operating Systems and Optimization
Last month, I wrapped up an operating systems course at the University of Waterloo, codenamed ECE 350. I would consider it to be one of the most important, yet also one of the most difficult courses so far. It heavily pushed both theoretical concepts in lectures and practical applications in lab projects. For example, many exam questions would ask 'why' for an unseen scenario rather than just 'what,' opening the possibility of multiple correct/incorrect answers.
Studying well for it was a combination of doing practice problems effectively and capturing every detail of the lectures. The memorization aspect was rather unpleasant, and some would say, unnecessary. On the other hand, the professor made many analogies in lectures, which highlighted the many ways in which the course concepts (scheduling, memory, I/O) can also be applied as life lessons, as we naturally share those traits.
Since my own grade was decent and I still enjoyed the course, I hope to extend the spirit by mapping the concepts to another one of my favorite subjects, optimization, in the hope that it will help others and me abstract the course in a memorable way.
Overview
Why Optimization?
In a nutshell, operating systems are about algorithms to allocate computer hardware resources to multiple users and processes under constraints and uncertainty.
This fits perfectly into the model of optimization, which generally goes like:
Here, is a vector to adjust, the "solution." If it does not lie inside the constraint set , it is completely unacceptable. Among the solutions within the constraint set, the one which is a global minimum for , the objective function, is the optimal point.
To gloss over some more optimization math, there are convex and nonconvex optimization problems, of which convex ones are easier to solve. In some cases, is constrained to only integer values, which can make the problem harder. In practice, optimization is applied in countless areas, such as finance, power grids, and robotics.
To further look into the math, I would recommend Convex Optimization, the MOSEK Cookbook, and Algorithms for Optimization.
In the subsequent sections, I will simply point out the objective functions, optimization variables, and constraints corresponding to various topics in OS. To maximize conciseness, I have omitted descriptions of algorithms, since I think they flow naturally from the optimization framework as simple approximations, heuristics, or policy-based rules.
To demonstrate the analogies tangibly, I also ran experimental simulation scenarios, benchmarking the "optimality" of various algorithms against the most global optimum found via an OR-Tools CP-SAT solver. The code and results table are at the link here.
Scheduling
Scheduling was the heaviest topic of the course. Reframing it using optimization is multi-faceted, since the objectives and constraints vary by the hardware used.
However, all scheduling mechanisms want maximum fairness, maximum priority adherence, and balanced resource usage as objectives. The constraint is ensuring no starvation under the limited computing resources.
Additionally, the multi-level feedback or round-robin variants have the time-slice length and feedback queue parameters as decision variables. Other decision variables include priority assignment rules or preemption points, which can be dynamic (e.g. users can have a say in priority).
For batch systems, the objective is focused on maximizing throughput, minimizing turnaround, and maximizing resource utilization. It is often said that the most optimal algorithm is the shortest job first.
For interactive systems, the objective is focused on minimizing response time and maximizing predictability.
For multicore systems, the objective is not only to maximize processor utilization, but also to minimize load imbalance and minimize cache misses. Notice how the last two objectives are conflicting, which is a commonly occurring phenomenon (and relates to the topic of Pareto optimality). Hence, in practice, there are multiple levels to processor affinity and varying penalties associated with work stealing.
In mobile systems, the objective is geared towards maximizing battery life. Hence, the decision/control variables used can include CPU DVFS knobs, task migration, and the settings of idle or background tasks.
For real-time systems, adherence to deadlines is paramount. In the hard real-time case, it becomes a feasibility constraint. In soft real-time, it is more of a heavily weighted objective. However, deadline estimation is probabilistic, since it is impossible to determine when tasks finish, so various worst-case confidence bounds are applied in practice. Moreover, server mechanisms maximize/ensure the deadline adherence of periodic (predictable arrival) tasks while maximizing the responsiveness of aperiodic (unpredictable arrival) tasks.
Concurrency
Like most other offerings, our course dug into the internals of concurrency control implementations, such as mutexes, condition variables, and readers-writers locks. From the optimization framework, it is not complex.
At a high-level, the objective is maximizing the forward progress of tasks (minimizing blockage) and minimizing synchronization overhead, while being constrained by ensuring liveness.
The decision variables are synchronization granularity (coarse vs. fine-grained locking), the choice between mutex/futex/condition variable/readers-writers lock/etc, and general blocking/unblocking policy.
The core constraints are mutual exclusion on shared data, guarantee of no deadlocks/livelocks, and bounded waiting time.
In a system with priority-assigned tasks, priority inheritance is a cool mechanism to enforce the constraint and avert an infeasibility case via priority inversion.
Memory
The mapping from memory management to optimization is also simple.
The objective is to minimize page fault rate, minimize effective access time, and minimize internal/external fragmentation (the two types of fragmentation tend to trade off as objectives).
The decision variables include page replacement policy, working set size, cache replacement policy, and others, depending on the hardware setup.
The OS is constrained by the memory size, workload type, and hardware requirements. As new memory technologies get released and workload memory demands grow, the constraint set is constantly evolving over time, which presents many interesting challenges.
I/O
Scheduling input-output devices is quite similar to CPU scheduling, but instead of tasks with unpredictable arrival execution times, it is about devices with different speeds, data transfer methods, access patterns (concurrent or serial), and data access methods.
Hence, the objective is similar: to minimize device downtime and latency, while maximizing fairness and device throughput.
The decision variables are more specific to CPU communication with other devices, through memory and device interfaces: request order, buffer size, device communication interface (polling/PIO, interrupts, or DMA).
The constraints are device bandwidth, hardware latency, limited buffers, device protocol requirements, interrupt/DMA overhead, memory safety, ordering requirements, fairness requirements, and workload burstiness.
Device bandwidth limits how quickly requests can actually be served, no matter how good the OS policy is. Hardware latency captures the fact that devices may have setup time, seek time, transfer delay, or completion delay outside the CPU’s control. Limited buffers constrain how much data can be queued before the OS must block, drop, or apply backpressure.
Device protocol requirements are also hard constraints: drivers must communicate with hardware in the order and format the device expects. Interrupts and DMA reduce CPU involvement, but introduce their own overheads and synchronization requirements. DMA especially creates memory safety constraints, because the device may directly read or write main memory.
Disks
Disk scheduling is another example of optimization under physical constraints. Unlike CPU scheduling, where the “distance” between two jobs is abstract, disk scheduling has literal distance: the disk head must move, and rotational position matters. Serving requests in arrival order may be fair, but it can cause the head to bounce back and forth across the platter like an inefficient elevator.
SSTF looks locally optimal: serve the closest request next. But this greedy objective can starve far-away requests. SCAN and C-SCAN add structure by making the disk arm sweep in a predictable direction, sacrificing some local optimality for global fairness and bounded waiting.
In optimization language, FCFS optimizes simplicity and fairness, SSTF optimizes immediate seek cost, and SCAN-style algorithms regularize the solution by adding a fairness constraint. The interesting lesson is that the locally cheapest next move is not necessarily the best system policy.
File Systems
The file system is the translation layer that decides where bytes live, how names map to metadata, when cached writes become durable, and what must happen if the machine crashes halfway through an update.
The optimization variables include block allocation, inode or metadata layout, directory indexing, free-space management, caching policy, write-back timing, and journaling strategy. But unlike CPU scheduling, correctness has a heavier meaning here. A slow file system is annoying; a file system that loses data or corrupts metadata is unacceptable.
This makes crash consistency a constraint, not just an objective. Journaling is a classic example: before modifying the main file system state, the OS records enough information to recover after a crash. This improves reliability and repairability, but it adds write amplification and latency. Again, the OS is not simply maximizing speed; it is choosing how much performance to spend on trust.
Virtualization
Virtualization is where the hypervisor optimizes an illusion: each guest believes it owns the machine, even though CPU time, memory, storage, and devices are shared underneath.
The objective is to maximize resource utilization and isolation while minimizing virtualization overhead and performance unpredictability. In cloud systems, this also becomes an economic optimization problem: fit as many workloads as possible onto physical machines without violating performance or security expectations.
The decision variables include VM placement, virtual CPU scheduling, memory allocation, overcommitment ratios, page sharing, ballooning policy, virtual disk placement, I/O virtualization strategy, and migration timing.
The constraints include finite hardware resources, isolation requirements, guest OS compatibility, NUMA/cache effects, device limitations, and unavoidable trap/emulation overhead.
A central tradeoff is consolidation versus predictability. If the hypervisor packs many VMs onto one physical server, utilization improves. But if those VMs become active at the same time, they compete for CPU, memory bandwidth, cache, disk, and network resources. The system may still be correct, but its performance becomes noisy.
Another tradeoff is isolation versus efficiency. A VM gives stronger isolation than a regular process because it virtualizes a whole machine boundary, but that boundary is more expensive to maintain. Containers reduce overhead by sharing the host kernel, but the shared kernel also becomes part of the security boundary.
Security
Security is where the OS optimization problem becomes adversarial. In scheduling, memory, and I/O, the system mostly optimizes against limited resources and uncertain workloads.
The objective is to maximize confidentiality, integrity, and availability, while minimizing overhead. Minimizing overhead matters because a perfectly locked-down system that nobody can efficiently use is not a good operating system.
The optimization variables are access control granularity, sandbox boundaries, and capability revocation timing. They generally decide how detailed the permission model should be and trade off security guarantees with maintenance overhead.
The constraints are access control rules, side-channel budget, and the principle of least privilege. The constraints limit the feasible actions of both processes and the OS policy itself. A process is constrained because it cannot perform operations outside its authority. The OS is constrained because it cannot optimize performance or usability by simply allowing every request.
Conclusion
The analogies from Operating Systems extend very far beyond optimization. For example, I recently heard in agentic AI, LLMs are like CPUs, context is like memory management, and the agentic system is the operating system itself. Perhaps in that case, MCP servers are a form of I/O. Then, at an even higher level, what are AI agents optimizing? Perhaps it is minimizing the difference between its output and the human-prompted "trajectory."