LIFO starvation 2026-10-25
View more
With a LIFO stack of waiting requests, an old request may remain at the bottom while a new request arrives before each completion and is served next. Every service can finish in finite time while the old request waits forever. A FIFO queue prevents this overtaking within one priority class. Nonpreemptive strict-priority arbitration can separately starve a lower-priority class; using a LIFO stack adds potential starvation even among requests of equal priority.
Read the full article
Past exam of the year 1 of the computer science course of the University of Oxford / 2023 / Digital systems, linear algebra and introduction to formal proof / 2 / b / Solution 2026-10-25
View more
Use two FIFO queues, one for each priority class, and perform nonpreemptive strict-priority arbitration whenever the display becomes free:
owner = NONE
ordinary = empty FIFO queue
urgent = empty FIFO queue

forever:
    message = receive_from_any_client()
    if message.kind == REQUEST:
        assert message.priority in {0, 1}
        if message.priority == 1:
            urgent.push_back(message.client)
        else:
            ordinary.push_back(message.client)
    else if message.kind == RELEASE:
        assert message.client == owner
        owner = NONE

    if owner == NONE:
        if not urgent.empty():
            owner = urgent.pop_front()
        else if not ordinary.empty():
            owner = ordinary.pop_front()
        if owner != NONE:
            send(owner, GRANT)
The same ownership invariant proves mutual exclusion. Among requests already accepted by the server, every pending urgent request takes precedence over every ordinary one. Each class retains its own arrival order. A newly received urgent request goes ahead of waiting ordinary requests but waits for the current animation's RELEASE; the given protocol has no interruption or revocation operation.
This is strict priority at dispatch, based on requests the server has received. Requests still in transit cannot influence a decision. If the transport provides a mailbox-draining operation, the server may also collect all currently delivered requests before dispatching; the two-FIFO queue selection rule remains the same.
Strict priority does not guarantee starvation freedom for ordinary clients under an endless supply of urgent work. If urgent traffic eventually stops, accepted requests have only finitely many earlier requests, and all service times are finite, every pending ordinary request is eventually granted. Guaranteeing ordinary progress under unlimited urgent traffic would require a different fairness policy, such as limiting consecutive urgent grants; that would relax strict priority.
Read the full article