Syllabus Lesson 50 of 141 · Borrowed machines
Borrowed machines

Borrow the hold queue: fair reservations

Why it matters Reservation systems built from scratch tend to reward whoever clicks fastest, or let one no-show block everyone. Places that hand out scarce things to people every day settled on a better design long ago.

Three counters

A library hold. You place a hold on a book that is out. When a copy comes back, it goes to the first person in the hold queue, who gets a message and a few days to collect it. If they do not come, the copy goes to the next person, and the first loses their place.

A restaurant waitlist with a buzzer. You give your name and get a buzzer. When a table frees up, the next party is buzzed and has five minutes to reach the host stand, or the table goes to the next party.

The deli counter ticket. You take a number. When your number is called and you are not there, the next number is called. You can take a new ticket, at the back.

Compare before you code

  1. In each, when does your place in line get fixed: when you ask, or when the thing becomes free?
  2. What happens to a person who does not turn up, and how long do they get?
  3. What happens to the thing while it waits for someone to collect it?
  4. State the shared rule in one sentence that mentions no books, tables or meat.

The target

The mobile team shares a small lab of test phones. Engineers request a model; when a phone of that model is free, it is offered to them, and they must claim it in the lab app within two hours. A claimed phone is booked for an eight-hour slot and then comes back automatically. Today the app gives a free phone to whoever presses "claim" first, and people have started writing scripts to press it.

stock = [("dev1", "pixel")]
events = [("request", 0, "ana", "pixel"), ("request", 5, "ben", "pixel"),
          ("claim", 10, "ben", "pixel"), ("claim", 30, "ana", "pixel")]
loans(stock, events)   # -> [("ana", "dev1", 30)]  (ben is not first)
Your turn

Write loans(stock, events). stock lists (device_id, model), all free at time 0. events are ("request", t, person, model) or ("claim", t, person, model), sorted by time t in minutes. The rules:

  1. Each model has a queue in request order. A request is ignored if that person is already queued for, or holding an offer on, that model.
  2. A free phone is offered to the first person in its model's queue (they leave the queue). If nobody is queued it waits on the shelf, and a later request for that model gets it at once. With several on the shelf, offer the smallest device id.
  3. An offer made at time o can be claimed while t < o + 120. A claim with no live offer for that person and model is ignored.
  4. At o + 120 an unclaimed offer lapses and the phone is freed again at that moment (rule 2).
  5. A claim at time t starts a loan; the phone is freed at t + 480.
  6. Lapses and returns due at or before an event's time happen before it, in order of time, then device id.
Return the loans as (person, device_id, claim_time) in the order they were claimed.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus