My kitchen is a very tiny diner.  It has limited seating, limited resources, and too many cooks cause deadlocks and or starvation. This is a thought experiment, it outlines a fairness based scheduling algorithm to remedy the dilemma outlined in this scenario.

Some necessary definitions & clarifications:

  • Recipe – aka Task, a repeatable, well defined, process.
  • Cooking – aka Job, an invocation of a recipe, it is when a cook starts to work on a recipe and engages resources.
  • Chef – aka Agent, the actor that will receive a request and ‘cook’ a recipe.
  • Requester – the customer or user that ‘requests’ a task to be completed.
  • Resource – like a natural resource, it has limited availability and must be ‘shared’ amongst jobs; in our diner analogy it might be something like the stove, or cooktop.

Thought Experiment

If you’ve ever worked in a diner you know how challenging it can be to make sure that the food is prepared in a timely manner and that no guests have to wait too long of a time for their food to be served. This problem is intensified when the kitchen is small and timing is very important.  For our hypothetical scenario guests order à la carte off a short order menu. Lets constrain the experiment such that:

  • all necessary recipes are available
  • all necessary raw ingredients are available
  • as soon as a requester orders any recipe, the server immediately tells the Chef to begin preparation, regardless of if the requester has additional orders to place
  • once an order has started to cook, it should not be preempted, blocked, or delayed.
  • once a request has been made, a new Chef spawns that attempts to handle the request. Chefs in this scenario don’t talk much, they only know what the Request is, how to fulfill the recipe and whether or not the critical resource is available.

The problem then comes down to managing resources, and sequencing ‘cooking’ and sharing the critical resource – the cooktop.

Scenario 1 – No Lock Requested

  1. Guest Albert orders a chicken sandwich.
  2. The server Ingrid tells Chef 1 to start cooking Albert’s order.
  3. Guest Baker then immediately orders a pork sandwich.
  4. The server Juliet tells Chef 2 to start cooking Baker’s order.

Because neither order needs a lock on the critical resource, they can both cook at the same time and both are finished at about the same time.

Scenario 2 – Lock Requested First

  1. Guest Albert orders a chicken sandwich and tells the server he needs an exclusive lock on the cook top because of his severe food allergies.
  2. The server Ingrid tells Chef 1 to start cooking Albert’s order, and locks the cook top so only requests from Albert can be served.
  3. Guest Baker then immediately orders a pork sandwich.
  4. The server Juliet  tells Chef 2 to start cooking Baker’s order.
  5. Chef 2 cannot begin cooking because of Albert’s lock.
  6. Guest Baker’s order is blocked.
  7. Guest Albert then immediately orders a side of hash browns.

What should happen with the next part of Albert’s order?

  1. Should it be ignored because Baker wasn’t serviced?
  2. Should it be queued to be prepared after Bakers?
  3. Should it be prepared because Albert already has a lock and the request was made in a reasonable time?

If the value of the system is to blindly service guests in a first come first serve (FIFO) method, then Albert’s order second request should probably be delayed until after Baker’s.  This could mean the Chef patiently waits until the cooktop is available, or the server could inform Albert that he will need to place his order again later.  However if the value of the system is to maximize efficiency and maximize individual satisfaction then Albert’s second order should be prepared because Albert already has a lock on the resource.

Scenario 3 – Lock Requested Second

  1. Guest Albert orders a fried PB&J and does not request the lock.
  2. The server Ingrid tells Chef 1 to start cooking Albert’s order.
  3. Guest Baker then immediately orders a pork sandwich and requests a lock on the cooktop.
  4. The server Juliet tells Chef 2 to start cooking Baker’s order.
  5. Chef 2 cannot begin cooking because he cannot attain the exclusive lock because he must wait for the existing order to be finished.
  6. Guest Charlie then immediately orders a burger.
  7. The server Kevin tells Chef 3 to start cooking Charlie’s order.

What should happen with Baker’s order?

  1. Should it be ignored because Baker wasn’t able to attain the lock?
  2. Should it be queued to be prepared after Alberts?
  3. Should any future orders be prevented until Baker’s order is fulfilled?

What should happen with Charlie’s order?

  1. Should it be ignored because Baker wasn’t serviced?
  2. Should it be queued to be prepared after Bakers?
  3. Should it be prepared because there is no lock on the cook top?

If the value of the system was to maximize efficiency then Charlie’s order should probably be prepared, as there is no lock on the cook top. If the value of the system is fairness then neither Baker or Charlie’s order should be prepared immediately, perhaps they should be queued.

These scenarios seem quite contrived (they are), but they illustrate that in a non-preemptive, first come first serve (FIFO) environment fairness is difficult to guarantee.

To Queue or Not to Queue

To answer our questions and maximize both efficiency and fairness we must decide if the system will allow queueing or not.  In a queued system, there is some overhead to the system. The queuing method will affect the amount of overhead the system needs in order to queue. The overhead may be paid for by busy-waiting, or polling or some other technique but they all have tradeoffs.  An additional consideration is where the burden of responsibility rests, or how close to the critical resource the overhead is paid.

In a simple first come first serve model without queueing, the burden is mostly on the requester.  As an example, if you try to go to the grocery store but they are closed, you must come back later. You may decided to go grocery shopping somewhere else, or come back the next day, but the point is the system will not service you.  Beyond the inconvenience of having to come back later, when you do return you must go the back of the line to enter the grocery store like everyone else.

Contrasting is first come first serve with queuing. A good example is voting day, as long as you are in the line before the polls close, the system is obligated to eventually service you and let you vote, the polls cannot close without you. However, if you leave to go home and get dinner, you will have lost your spot in line and will not be able to vote.

If the value of the system is to minimize overhead to the system but still guarantee some sort of fairness and ideal solution is to use the appointment metaphor.

The Appointment Metaphor

The appointment metaphor allows a requester to queue for the next available resource but places the burden of responsibility upon the requester to ensure they are serviced.  It works like this:

  1. A requestor makes a request to lock.
  2. The critical resource is currently locked so they reject the requestor but give them a token to try back later with.
  3. If the requestor tries back again before the token expires they can be serviced if the original lock has been released.
    1. If the system is not yet available from the original request, the token can be renewed for another short duration
  4. If the requestor does not try back again before the token expires they lose their appointment and must go to the back of the line.

This guarantees that no other requestor will be serviced before the blocked requestor.  A positive trade off is that the system takes on very minimal overhead as it has shifted the burden or responsibility to the requester.  A negative trade off is that if the token period is set too long, the system will not service any critical requestors during that interlude.

Extending Tokens

Recalling Scenario 2, where Albert locks the cook top with his original request and then makes a subsequent request, an advantage of using tokens is they can be naturally extended to be used as a semaphore.   The token can allow Albert in quick succession to his original request to make more requests for the same session.  The spirit of this is if Albert knows he wants a burger, fries, a sandwich and a fried pickle, he can be allowed to order all four items, one at a time, without being blocked by his own lock, or by the queued requests of other guests.  Of course for such tokenization to be successful there should be limits on the number of requests Albert can make within a specified time frame, as this shouldn’t be a vehicle for Albert to monopolize the system, but rather to provide the most efficient service to any guests as possible.

Non-Critical Resource Requests

It is possible that a request may come in that does not need or request the critical resource. In our diner analogy this would be akin to a guest requesting a refill of coffee. The critical resource, the cook-top isn’t affected so a Chef can fulfil the request.  This quality may vary from diner to diner, but ideally a system should prevent non-critical resources from being fulfilled if the request truly does not impact the critical resource.

Visualization

This flowchart is a partial embodiment of the routine the Chef would complete when spawned to handle a request.

0 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *