Introduction
The way in which a queue, or a waiting line, operates is called the discipline. The discipline describes the method by which the queue processes an item or customer in the queue. A discipline can be either preemptive priority or non-preemptive priority. Two examples of non-preemptive priority disciplines are “first come, first served” (FCFS; aka “first in, first out” (LIFO)) and “service in random order” (SIRO; aka “random order service” (ROS)). An example of a preemptive priority queue discipline is “last come, first served” (LCFS; aka “last in, first out” (LIFO)). It is important to note that the LCFS discipline can sometimes operate as non-preemptive; however, for the purpose of this discussion, LCFS will be discussed as preemptive priority.
Non-preemptive Priority Queue Disciplines
FCFS
An FCFS queue services each item in the order that each item enters the queue for service. No new arrival to the queue affects the order in which all preexisting arrivals will be serviced.
Think of a check-out line at a grocery store. Assume that only one cashier is working and that each customer in line stays in the line in the order in which they entered the line. The cashier services each customer in the order in which they entered the line. No customer preempts another other customer. If a customer is fifth in line, then that customer will be serviced fifth and nothing will change that.
SIRO
An SIRO queue that services each item randomly. No one item as any priority over any other item in the queue. Each item in the queue has an equal probability of being serviced next.
Think of a manufacturing process that includes a materials testing queue of some product. A batch of product is provided to a worker who is tasked with functionally testing each product for defects. The entire batch must be tested, but there is no order in which each product of the batch must be tested. The worker services the queue in random order.
Preemptive Priority Queue Discipline
LCFS
An LCFS queue services each item from the last arrival to the first arrival. A new arrival preempts service over the service of a previous arrival.
Think about inventory management of produce at a grocery store again. The produce manager is tasked with inventory management. The produce manager must ensure that no customer purchases expired produce. The produce manager’s budget allows for obsolete inventory (an accounting term that is often used for some expired good). The produce manager stocks, say, 10 packs of berries on Sunday and will receive a new delivery of 10 packs of berries on Wednesday. Ideally, the produce manager will move all 10 packs of berries before the next delivery to avoid obsolete inventory. Berries expire quickly, however, and leaving a pack of berries in the display box for too long could result in spoilage. Because of this risk, the new delivery of berries will preempt the stocking space upon arrival, resulting in the removal of all existing packs of berries in the display and the recording of obsolete inventory. A new arrival replaces the previous arrival.
For more information about preemptive priority queues, specifically about the preemptive-resume policy, the preemptive-repeat-identical policy, and the preemptive-repeat-different policy, see Three Preemptive Priority Policies.
Daniel M. Packer 