Fix the replay of an atomic rate limiter
Your task
An assistant's Rust rate limiter loads a counter, checks it against the limit, then stores the counter plus 1. Each step is atomic, but the three together are not, so under load it admits more than max. The team wants a replay that counts admissions, with and without a compare-and-swap fix (an update that only lands if the value has not changed since it was read).
An assistant wrote admit_waves(wave_sizes, max_permits, use_compare_and_swap). It is in the editor. It has a bug. Find it and fix it.
Input and output:
wave_sizes: for each wave, in order, how many threads call the limiter at the same moment. A size can be 0 or negative.max_permits: the limit, an integer.use_compare_and_swap: true for the fixed limiter, false for the load, check, store version.- Return how many threads each wave admits, in wave order.
Rules the tests check:
- The counter starts at 0.
- A wave of size 0 or less admits 0 and changes nothing.
- With compare-and-swap, the threads take turns. The wave admits the smaller of its size and the permits left:
max_permitsminus the counter, never below 0. The counter goes up by the number admitted. - Without it, every thread in the wave loads the same counter value.
- If that value is below
max_permits, every thread passes the check, so the wave admits its whole size. Every thread then stores that same value plus 1, so the counter goes up by exactly 1, however many threads passed. - Otherwise the wave admits 0, and the counter stays as it is.
- If that value is below
Examples
admit_waves(wave_sizes: list[int], max_permits: int, use_compare_and_swap: bool) -> list[int]Example 1
Input
admit_waves([4, 4, 4], 5, False)Output
[4, 4, 4]Example 2
Input
admit_waves([4, 4, 4], 5, True)Output
[4, 1, 0]