## 3 The CPN Model
### The CPN Model
#### 3.2.1 The Core of Queue Members of a Queue System  
Our resource allocation scheduler is composed of \(m\) queue systems, each having \(m\) queues. In this subsection we will describe the core for the DSQ (the first queue, \(Q_{1}\)) of a queue system. Figure 4 shows this core. Inside each core a number of transitions which involve the DSQ are implemented. These transitions are symbolized by \(\overrightarrow{T}_{1x}\) and \(\overrightarrow{T}_{x1}\), where \(x\
eq 1,\ xin[2,\ldots m]\), and are described as follows:  
1. \(\overrightarrow{T}_{12}\): The transition from the DSQ \(Q_{1}\) to \(Q_{2}\), in other words, the dominant resources have been allocated to a job, which then applies for resources from server \(S_{2}\), thus it enters its queue. 2. \(\overrightarrow{T}_{13}\): The transition from the DSQ \(Q_{1}\) to \(Q_{3}\), in other words, the dominant resources have been allocated to a job, which then apply for resources from server \(S_{3}\), thus it enters its queue. 3. \(\overrightarrow{T}_{21}\): The transition from the \(Q_{2}\) to the DSQ; the requested resources have been allocated from \(S_{2}\) to a job, that returns to request extra resources from the DSQ, thus it re-enters its queue. 4. \(\overrightarrow{T}_{31}\): The transition from the \(Q_{3}\) to the DSQ; the requested resources have been allocated from \(S_{3}\) to a job, that returns to request extra resources from the DSQ, thus it re-enters its queue. The places and transitions of the DSQ core are given below:  
**Places**  
\(p_{1}\): Jobs requesting DSQ resources  
\(p_{2}\): Processing of next job request  
\(p_{3}\): Jobs requesting resources from server \(Q_{2}\)  
\(p_{4}\): Fair allocation policy over DSQ  
Figure 4: The dominant server queue (DSQ) core. \(p_{5}\): All ToRRs (Type of Resources Required, see Section 3.2.2 where the token structure is described) updated, Next job selection  
\(p_{6}\): \(S_{1}\) Fair allocation policy over \(Q_{2}\)  
\(p_{7}\): \(S_{2}\) Fair allocation policy over \(Q_{3}\)  
\(p_{8}\): Jobs requesting resources from server \(Q_{3}\)  
**Transitions**  
\(t_{1}\): Compute DSQ resources to be allocated for the job in a fair way  
\(t_{2}\): Process the next job's allocation request,  
\(t_{3}\): Compute \(Q_{2}\) resources to be allocated for the job in a fair way  
\(t_{4}\): Allocate DSQ resources, update ToRRs accordingly  
\(t_{5}\): Allocate \(Q_{2}\) resources  
\(t_{6}\): Compute \(Q_{3}\) resources to be allocated for the job in a fair way  
\(t_{7}\): Allocate \(Q_{3}\) resources  
One should notice the hierarchy behind this model: each of the queues is implemented with a subset of places and transitions and also, the queues have some places and transitions in common. For example, the DSQ is implemented with places \(p_{1}\) and \(p_{4}\) and with transitions \(t_{1}\) and \(t_{4}\) and shares \(p_{2}\) and \(p_{5}\) with both the other queues. This sort of design can be helpful in expanding the model for more resources (queues) and larger number of tokens (that is, larger number of resource requests). The places and transitions of the core model presented in Figure 4 translate in a pictorial straightforward way the basic procedures of our resource allocation strategy described in Section 2. These procedures are repeatedly executed into different parts of the hierarchical model, depending on the resource being allocated (DSQ or \(Q_{1}\) or \(Q_{2}\)). **Procedure 1-Requests for resources:** When one job requests a DSQ resource (meaning that there is a red token in place \(p_{1}\)), then it enters the DSQ and has to wait there until its turn. When the preceding job finishes, then the next job request can start. This is modeled by places \(p_{1}\) and \(p_{2}\). When they have one token, the next job's request can be processed. Then, transition \(t_{1}\) can fire, which triggers our fair allocation policy: the DSQ resources must be computed, in order to fairly allocate the dominant resource to the requesting job. This fair allocation policy terminates when a token is placed in \(p_{4}\).