11.6 MG1 with Priorities

11.6 M/G/1 with Priorities

Many computer systems (e.g., operating systems and communication systems) assign different priorities to the incoming requests. Figure 11.3 illustrates a situation with different waiting lines and one server. The different waiting lines are used by requests of different priorities. The priority of an arriving customer determines which priority waiting line is entered. Thus, customers are classified into P different static priorities before arriving into the system. Upon arrival, customers join the waiting line that corresponds to their priority class. Priority classes are numbered from 1 to P with P being the highest priority class and 1 being the lowest. The arrival rate of requests of priority p (p = 1, ···, P) is denoted by l_p. The average service time and second moment of class p requests are denoted by E[S_p] and , respectively.

Figure 11.3. A single server system with priority classes.

The server processes the customer of highest priority according to either a non-preemptive strategy or with a preemptive resume strategy [3]:

• Non-preemptive. In this case, when the server becomes idle it takes the first request from the highest priority queue to serve. Once service begins on a request it is not interrupted until the request is completed, even if a request of higher priority than the one in service arrives. In other words, requests cannot be preempted once service begins.

• Preemptive resume. If a request of priority p arrives and finds a request of priority q (q < p) being served, the higher priority request seizes the server (i.e., preempts the server by interrupting service of the priority q request). Once there are no more requests of priority higher than q, the preempted request resumes its processing from the point at which it was interrupted.

11.6.1 Non-Preemptive Priorities

The waiting time W_p of requests of priority p (p = 1, ···, P) is computed as [3]:

Equation 11.6.20

where

Equation 11.6.21

Equation 11.6.22

W₀ represents the average time an arriving request has to wait for the server to complete processing the current request in service. The product l_j E[S_j] is the utilization r_j due to priority j requests. The total utilization r is then

Equation 11.6.23

The average response time of priority class p requests is T_p = W_p + E[S_p].

Example 11.6.

A router receives packets at a rate of 1.2 packets/msec from a Poisson process. All packets are transmitted through the same outgoing link. Assume that 50% percent of the packets are of priority 1, 30% percent are of priority 2, and 20% percent are of priority 3. Assume that the mean and second moment of the packet transmission times are as shown in Table 11.2. What is the average waiting time per packet class?

Table 11.2. Data for Example 11.5

Priority (p)	E[Sp] (msec)	E[S2p] (msec2)
1	0.5	0.375
2	0.4	0.400
3	0.3	0.180

The arrival rates per class are: l₁ = 1.2 x 0.50 = 0.6 packets/msec, l₂ = 1.2 x 0.3 = 0.36 packets/msec, and l₃ = 1.2 x 0.2 = 0.24 packets/msec. Then, from Eq. (11.6.22):

From Eq. (11.6.21):

Finally, from Eq. (11.6.20):

The average response times for each priority class are T₁ =W₁ + E[S₁] = 0.543 + 0.5 = 1.043 msec, T₂ = W₂ +E[S₂]2 = 0.283 + 0.4 = 0.683 msec, and T₃ = W₃ + E[S₃] = 0.222 + 0.3 = 0.522 msec.

11.6.2 Preemptive Resume Priorities

The average response time T_p in this case is given by [3]:

Equation 11.6.24

Note that classes of priority lower than p are not represented in Eq. (11.6.24) because of preemption. That is, because of preemptions, requests of a lower priority have no impact on higher priority requests.

Example 11.7.

Assume the same data of the previous example and assume a preemptive resume server. What are the average response times of each customer class?

Equation (11.6.24) yields,

Note that class 3 receives improved response time in the preemptive case than in the non-preemptive case (i.e., 0.323 vs. 0.522 msec of response time). This is due to the fact that class 3 is not affected by classes 1 and 2. Class 1 receives degraded performance in the preemptive case (i.e., 1.181 vs. 1.043 msec of response time) since it only uses the server when there are no requests of classes 2 and 3 present in the system. The behavior of class 2 depends on the specific parameters of the problem. In the preemptive case, class 2 requests do not have to wait for class 1 requests to complete service but can be preempted by class 3 requests.