Metadata

The Crux: Fairness Over Speed.  Unlike the schedulers we explored in Chapter 8 (like Shortest Job First or Multi-Level Feedback Queues) that optimize for "turnaround time"  or "response time", proportional-share schedulers introduced in this Chapter aim to guarantee that each job receives a specific percentage of CPU time. (This is part of our series going through OSTEP book chapters. ) Basic Concept: Tickets Lottery Scheduling serves as the foundational example of proportional-share schedulers. It uses a randomized mechanism to achieve fairness probabilistically. The central concept of Lottery Scheduling is the ticket . Tickets represent the share of the resource a process should receive. The scheduler holds a lottery every time slice. If Job A has 75 tickets and Job B has 25 (100 total), the scheduler picks a random number between 0 and 99. Statistically, Job A will win 75% of the time. The implementation is incredibly simple. It requires a random number generat...

In a recent viral post , Matt Shumer declares dramatically that we've crossed an irreversible threshold. He asserts that the latest AI models now exercise independent judgment, that he simply gives an AI plain-English instructions, steps away for a few hours, and returns to a flawlessly finished product better than he could produce. In the near future, he claims, AI will autonomously handle all knowledge work and even build the next generation of AI itself, leaving human creators completely blindsided by the exponential curve. This was a depressing read. The dramatic tone lands well. And by extrapolating from progress in the last six years, it's hard to argue against what AI might achieve in the next six. I forwarded this to a friend of mine, who had the misfortune of reading it before bed. He told me he had a nightmare about it, dreaming of himself as an Uber driver, completely displaced from his high-tech career.

Academic writing has long been criticized for its formulaic nature. As I wrote about earlier , research papers are unfortunately written to please 3 specific expert reviewers who are overwhelmingly from academia. Given this twisted incentive structure ( looking impressive for peer-review ), the papers end up becoming formulaic, defensive, and often inpenetrable.  Ironically, this very uniformity makes it trivially easy for LLMs to replicate academic writing. It is easy to spot LLM use in personal essays, but I dare you to do it successfully in academic writing.  Aside: Ok, I baited myself with my own dare. In general, it is very hard to detect LLM usage at the paragraph level in a research paper. But LLM usage in research papers becomes obvious when you see the same definition repeated 3-4 times across consecutive pages.  The memoryless nature of LLMs causes them to recycle the same terms and phrases, and I find myself thinking "you already explained this to me four times...

The crux of this chapter is how to schedule tasks without perfect knowledge. If you remember from  the previous chapter , the core tension in CPU scheduling is these two conflicting goals: Minimizing Turnaround Time: Usually achieved by running shorter jobs first (SJF). Minimizing Response Time: Usually achieved by Round Robin scheduling (RR). Essential for interactive users. Unfortunately, the OS does not have a crystal ball. It doesn't know if a process is a short interactive job or a massive number-crunching batch job. The Multi-Level Feedback Queue (MLFQ) solves this by encoding/capturing information from history of the job, and assumes that if a job has been CPU-intensive in the past, it likely will be in the future. As we'll see below, it also gives a chance for jobs to redeem themselves through the boosting process. I really enjoyed this chapter. MLFQ, invented by Corbato in 1962, is a brilliant scheduling algorithm. This elegant solution served as the base scheduler fo...

Despite the ubiquity of the MongoDB aggregation framework, it has been lacking a formal mathematical framework/specification. This paper aims to fix this gap by providing a theoretical foundation, and proposes MQuery . The formalization in MQuery is largely based on the paper published at ICDT 2018 (for which the first author is involved), extending it to include more pipeline operators, relax the assumption that the JSON documents stored in the database comply to a predefined schema, and allow objects that are either ordered or unordered sets of key-value pairs. Motivation For decades, SQL proponents have flaunted the rigorous mathematical foundation of relational algebra (courtesy of  Edgar Codd ). The world of JSON document databases, however, has remained a bit of a Wild West in comparison. The analogy is apt because, like the frontier, there is immense opportunity here. JSON is the undisputed king of data exchange, and the MongoDB aggregation framework has emerged as the wide...

How does your computer create the illusion of running dozens of applications simultaneously when it only has a few physical cores? Wait, I forgot the question because I am now checking my email. Ok, back to it... The answer is CPU Virtualization. Chapters 6, 7 of OSTEP explore the engine behind this illusion, and how to balance raw performance with absolute control. The OSTEP textbook is freely available at Remzi's website if you like to follow along. Chapter 6. The Mechanism: Limited Direct Execution The crux of the challenge is: How do we run programs efficiently without letting them takeover the machine?  The solution is Limited Direct Execution (LDE) --the title spoils it. "Direct Execution" means the program runs natively on the CPU for maximum speed. "Limited" means the OS retains authority to stop the process and prevent restricted access. This requires some hardware support. To prevent chaos, hardware provides two execution modes. Applications run in ...

Back in 2005, when I first joined the SUNY Buffalo CSE department, the department secretary was a wonderful lady named Joann, who was over 60. She explained that my travel reimbursement process was simple: I'd just hand her the receipts after my trip, she'd fill out the necessary forms, submit them to the university, and within a month, the reimbursement check would magically appear in my department mailbox. She handled this for every single faculty member, all while managing her regular secretarial duties. Honestly, despite the 30-day turnaround, it was the most seamless reimbursement experience I've ever had. But over time the department grew, and Joann moved on. The university partnered with Concur, as corporations do, forcing us to file our own travel reimbursements through this system. Fine, I thought, more work for me, but it can't be too bad. But, the department also appointed a staff member to audit our Concur submissions. This person's job wasn't to hel...

I recently started reading "Operating Systems: Three Easy Pieces" (OSTEP) as part of Phil Eaton's offline reading group . We are tackling a very doable pace of 2 chapters a week. The book is structured into three major parts: Virtualization, Concurrency, and Persistence. It is openly accessible to everyone for free, which is a tremendous contribution to computer science education by the Arpaci-Dusseau couple (Remzi and Andrea). This is a very user-friendly book, sprinkled with a lot of jokes and asides that keep the mood light. The fourth wall is broken upfront, the authors talk directly to you, which is great. It makes it feel like we are learning together rather than being lectured at. Their approach is more than superficial; it inspires you, motivates the problems, and connects them to the big picture context. The book  builds scaffolding through "The Crux" of the problem and "Aside" panels. It actively teaches you the thought processes, not just t...

This paper describes the architecture behind CockroachDB Serverless. At first glance, the design can feel like cheating. Rather than introducing a new physically disaggregated architecture with log and page stores, CRDB retrofits its existing implementation through logical disaggregation: It splits the binary into separate SQL and KV processes and calls it serverless. But dismissing this as fake disaggregation would miss the point. I came to appreciate this design choice as I read the paper (a well written paper!). This logical disaggregation (the paper calls it cluster virtualization) provides a pragmatic evolution of the shared-nothing model. CRDB pushes the SQL–KV boundary (as in systems like TiDB and FoundationDB) to its logical extreme to provide the basis for a multi-tenant storage layer. From here on, they solve the sub-second cold starts problem and admission control problems with good engineering rather than an architectural overhaul. System Overview If you split the stack at...

Al-Gasr began as an autonomous agent town, but no one remembers now who deployed it. The original design documents were very clear. There were tasks. There were agents. There was persistence. Everything else had been added later by a minister's cousin. Al-Gasr ran on nine ministries. The Ministry of Compute handled execution, except when it didn't, in which case responsibility was transferred to the Ministry of Storage Degradation. The Ministry of Truth published daily bulletins. The Ministry of Previously Accepted Truth issued corrections. The Ministry of Future Truth prepared explanations in advance. Each ministry employed agents whose sole job was to supervise agents supervising their own nephews. At the top sat the Emir. Or possibly the late Emir. Or the Emir-in-Exile, depending on which dashboard you trusted. The system maintained three Emirs simultaneously to ensure high availability. This caused no confusion at all. The Emir du Jour governed by instinct and volume. Each ...

The premise of this position paper is appealing . We know Brooks' Law : adding manpower to a late software project makes it later. That is, human engineering capacity grows sub-linearly with headcount due to communication overhead and ramp-up time. The authors propose that AI agents offer a loophole: "Scalable Agency". Unlike humans, agents do not need days/weeks to ramp up, they load context instantly. So, theoretically, you can spin up 1,000 agents to explore thousands of design hypotheses in parallel, compressing the Time to Integrate (TTI: duration required to implement/integrate new features/technologies into infrastructure systems) for complex infrastructure from months to days. The paper calls this vision Self-Defining Systems (SDS), and suggests that thanks to Agentic AI future infrastructure will design, implement, and evolve itself. I began reading with great excitement, but by the final sections my excitement soured into skepticism. The bold claims of the intro...

Three years ago, I wrote a post titled "Getting schooled by AI, colleges must evolve" . I argued that as we entered the age of AI, the value of "knowing" was collapsing, and the value of "doing" was skyrocketing. (See Bloom's taxonomy. ) Today, that future has arrived. Entry-level hiring has stalled because AI agents absorb the small tasks where new graduates once learned the craft. So how do we prepare students for this reality? Not only do I stand by my original advice, I am doubling down. Surviving this shift requires more than minor curriculum tweaks; it requires a different philosophy of education. I find two old ideas worth reviving: a systems design mindset that emphasizes holistic foundations , and alternative education philosophies of the 1960s that give students real agency and real responsibility. Holistic Foundations Three years ago, I begged departments: "Don't raise TensorFlow disk jockeys. Teach databases! Teach compilers! Tea...

This paper (CIDR'26) presents a comprehensive analysis of cloud hardware trends from 2015 to 2025, focusing on AWS and comparing it with other clouds and on-premise hardware. TL;DR: While network bandwidth per dollar improved by one order of magnitude (10x), CPU and DRAM gains (again in performance per dollar terms) have been much more modest. Most surprisingly, NVMe storage performance in the cloud has stagnated since 2016. Check out the NVMe SSD discussion below for data on this anomaly. CPU Trends Multi-core parallelism has skyrocketed in the cloud. Maximum core counts have increased by an order of magnitude over the last decade. The largest AWS instance u7in now boasts 448 cores. However, simply adding cores hasn't translated linearly into value. To measure real evolution, the authors normalized benchmarks (SPECint, TPC-H, TPC-C) by instance cost. SPECint benchmarking shows that cost-performance improved roughly 3x over ten years. A huge chunk of that gain comes from AWS G...

While sweating it out in my gym's sauna recently, I found a neat way to illustrate the happened-before relationship in distributed systems. Imagine I suffer from a medical condition called dyschronometria , which makes me unable to perceive time reliably, such that 10 seconds and 10 minutes feel exactly the same to me. In this scenario, the sauna lacks a visible clock. I'm flying blind here, yet I want to leave after a healthy session. If I stay too short, I get no health benefits. If I stay too long, I risk passing out on the floor. The question becomes: How do I, a distributed node with no local clock, ensure operating within a safety window in an asynchronous environment? Thankfully, the sauna has a uniform arrival of people. Every couple of minutes, a new person walks in. These people don't suffer from dyschronometria and they stay for a healthy session, roughly 10 minutes. My solution is simple: I identify the first person to enter after me, and I leave when he leaves....

In this blog, we had reviewed quite a number of deterministic database papers, including Calvin , SLOG , Detock , which aimed to achieve higher throughput and lower latency. The downside of these systems is sacrificing transaction expressivity. They rely on two critical assumptions: first, that transactions are "non-interactive", meaning they are sent as a single request (one-shot) rather than engaging in a multi-round-trip conversation with the application, and second, that the database can know a transaction's read/write set before execution begins (to lock data deterministically). So when these deterministic database researchers write a paper to validate how these assumptions hold in the real world, we should be skeptical and cautious in our reading. Don't get me wrong, this is a great and valuable paper. And we still need to be critical in our reading.  Summary The study employed a semi-automated annotation tool to analyze 111 popular open-source web applications...