A locker room contains a number of lockers (L), and a number of elves (E). The elves are attempting to put cakes in the lockers, cake by cake, to feed cake-eating gremlins (obviously) that have access to the lockers through a rear door. We can assume E << L, and that some external entity is regulating the supply of cake and rate of cake consumption.
Your algorithm is repeatedly asked to find an empty locker, and place a cake in it. The cake is eaten some time later (unknown to you) by a gremlin.
Each elf may open any locker to see whether it it has a cake in, but opening and checking the locker is a time consuming process. Further, whilst one elf is opening and checking the locker, other elves may be checking (and filling) other lockers. If a one elf attempts to open a locker, and another attempts to open the same one, they are queued (i.e. assume there is a locker-specific mutex on each locker).
What is the most efficient way (i.e. requiring the least average number of locker checks) to find a free locker?
A reasonable strategy would simply be to pick a locker at random, and if it already has a cake in it, pick another. This tends to perform badly when nearly all the lockers have cakes in, as any given full locker may be tried several times before an empty one is found. Specifically, the maximum number of attempts to find a free locker is (technically) infinite, meaning it’s impossible to put an upper bound on the time taken to find an empty locker. And I’m after consistent low-latency cake placement.
Another reasonable strategy would be to pick a locker at random, and if it’s full try the next one along. However, this creates ‘bunching’ of full lockers – contiguous lockers all full of cake. If a subsequent elf picks one in this line, he’ll have to work his way right to the end of it before finding a free locker.
To avoid this being too easy, I’ve introduced three additional restrictions:
- I’ve switched the lights off and forbade the elves to talk, so they can’t tell what each other are doing. We have no IEC (inter elf communication).
- We can assume the number of lockers is sufficiently large and the elves sufficiently forgetful that no elf can remember what lockers it’s tried, let alone anything about its last attempt to place a cake.
- Assuming there is at least one locker that remains empty throughout an elf’s attempt to find a free locker, it must find that empty locker in no more than L attempts.
I have what I believe is a reasonable solution to this which appears to work in practice. I’ll post this in a few days. In the mean time, I’d be interested in other ideas in the comments below.
Addition based on comments off-line: you can assume that it takes much longer for a gremlin to eat a cake than it takes for an elf to check all the lockers.