~/problems / Locks / Lock (mutex)

Last croissants at the bakery

easy ~15 min

A bakery's online shop keeps its stock in a slow external store (think: a spreadsheet behind an API). The store has two methods:

  • store.get(item) -> int: how many of item are left (0 for an item it has never seen).
  • store.put(item, count): set the stock of item.

Implement Shop(store) with:

  • buy(item, qty) -> bool: if at least qty of item are in stock, take them (lower the stock by qty) and return True. Otherwise change nothing and return False.
  • restock(item, qty) -> None: add qty to the stock of item.

Many customers' threads call these at once on the same Shop.

store = ...                  # 3 croissants, 0 baguettes
shop = Shop(store)
shop.buy("croissant", 2)     # True, 1 left
shop.buy("croissant", 2)     # False, still 1 left
shop.restock("baguette", 5)
shop.buy("baguette", 5)      # True, 0 left
# 10 threads each try buy("croissant", 1) on a stock of 4:
#   exactly 4 get True, 6 get False, the stock ends at 0 (never negative)

The trap is check-then-act: if store.get(item) >= qty: store.put(item, store.get(item) - qty). Two customers can both see "1 left" and both walk away with it. The tests' store is slow enough to make that happen.

Constraints: qty >= 1. Different shops over different stores must not block each other. Don't sleep or busy-wait.

Show hint

The check and the update must be one indivisible step: hold one threading.Lock (created in __init__) across the get, the comparison and the put, in both methods.

Topic: Lock (mutex). One thread in a critical section at a time.

0:00
Ctrl ' run · Ctrl ↵ submit
esc