Priority Queue

Source and Output

"""Example: priority queue serving jobs in priority order."""

from asimpy import Environment, PriorityQueue, Process
from _util import example

SERVICE_DURATION = 2  # ticks to process each job
# Each entry is (priority, label): lower priority number is served first.
JOBS = [
    (3, "low-A"),
    (1, "high-B"),
    (2, "mid-C"),
    (1, "high-D"),
]


class Submitter(Process):
    """Submits all jobs at t=0 then stops."""

    def init(self, queue):
        self._queue = queue

    async def run(self):
        for priority, label in JOBS:
            self._env.log("submitter", f"submit ({priority}, {label})")
            await self._queue.put((priority, label))


class Server(Process):
    """Processes jobs one at a time in priority order."""

    def init(self, queue):
        self._queue = queue

    async def run(self):
        while True:
            priority, label = await self._queue.get()
            self._env.log("server", f"start ({priority}, {label})")
            await self.timeout(SERVICE_DURATION)
            self._env.log("server", f"finish ({priority}, {label})")


def main():
    env = Environment()
    queue = PriorityQueue(env)
    Submitter(env, queue)
    Server(env, queue)
    env.run()
    return env


if __name__ == "__main__":
    example(main)

Key Points

1. PriorityQueue is a drop-in replacement for Queue that serves items in ascending sorted order rather than arrival order. Items must be comparable.

2. Tuples compare lexicographically in Python, so (priority, label) pairs are ordered first by priority number and then by label string. Wrapping jobs in a tuple is a simple way to attach a priority.

3. All four jobs are submitted at t=0. The server picks the smallest tuple each time: (1, "high-B") before (1, "high-D") (same priority, earlier alphabetically) before (2, "mid-C") before (3, "low-A").

4. Arrival order has no effect once items are in the queue: (3, "low-A") was submitted first but served last.

Check for Understanding

If you changed the label "high-B" to "high-Z", would (1, "high-D") or (1, "high-Z") be served first, and why?