Use a message-passing mutual exclusion server with an A client sends
owner field and a FIFO queue. A request includes its client's identity. The server handles one received message at a time, and a client has at most one outstanding request. The following pseudocode assumes reliable message passing and compliant clients:owner = NONE
waiting = empty FIFO queue
forever:
(kind, client) = receive_from_any_client()
if kind == REQUEST:
waiting.push_back(client)
else if kind == RELEASE:
assert client == owner
owner = NONE
if owner == NONE and not waiting.empty():
owner = waiting.pop_front()
send(owner, GRANT)REQUEST, waits for GRANT, runs its complete animation, and sends RELEASE before making another request.The invariant proving mutual exclusion is: at most one client has received an unreturned grant, and that client is
owner. Only the final block issues a grant, and it first requires no current owner. A valid release removes that ownership. Since clients use the display only while holding a grant, simultaneous use is impossible. The FIFO queue prevents accepted requests from being overtaken by later ones. With eventual message delivery, continued server execution, and finite animations, each accepted request is eventually served; these progress assumptions are separate from the safety invariant.Use two FIFO queues, one for each priority class, and perform nonpreemptive strict-priority arbitration whenever the display becomes free: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
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)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.
A LIFO stack can make waiting clients starve. Suppose client waits at the bottom of the stack. Before each current owner releases, a fresh client submits a request. That newest request is pushed above and is selected next. Every animation can finish promptly while waits forever.
This is LIFO starvation: service completion alone does not ensure starvation freedom. A FIFO queue prevents newer same-priority requests from passing , whereas replacing either priority-class FIFO queue by a LIFO stack adds this problem even within one priority class. Strict priority can already starve ordinary work, as in (b); the LIFO stack introduces a further unfairness that can also affect urgent work.
Articles by others on the same topic
There are currently no matching articles.