Prolog declarative database

Exercise 2: Arbiter

Arbiter is a mechanism for allocating resources eciently in concurrent systems. The purpose of this exercise is to model an arbiter which allocates resources to two processes P and Q in such a way that every process eventually gets the requested resource. The following constraints apply for resource sharing between processes:

R is a nite set of resources.

for r R there exists tr N, denoting the maximum utilization time.

a process can request the arbiter for any resource in R.

arbiter will accept all requests from P and Q.

every resource requested by a process should be allocated to it by the arbiter.

a process which received a resource r at time t must return it to the arbiter before time t + tr.

Here is the EFSM specication for the system:

Simulation and assignment

Use Prolog program to translate the specification into a declarative database, and define the following rules:

1. Rule get_events succeeds by obtaining a collection of state, event pairs where event is a legal event on state.

2. Rule get_actions succeeds by obtaining a collection of all actions that the system can perform.

3. Rule path reads a state and succeeds by obtaining a collection of state-event pairs that can lead from the initial state to the given state. For simplicity, do not consider nested states, i.e. the rule applies to a single level of abstraction.

The EFSM of the arbiter is the tuple S (Q, 1, SC2, qo, V A), where Q RP, Ra, unallocated E1 request, return 2 tallocate, return, t t tr qo unallocated V tr N, t N, t maar N A: Transition specifications 1. urn allocated request P allocate; t t-+tr) maar 2. unallocated request Q/ allocate; t 3. unallocated t +tr) maar return 4. R allocated 5. R return unallocated It atmazl/ return P unallocated 6. R It maal return 7. R unallocated