15.4 Modeling Priority Scheduling

Priority scheduling schemes have been used for managing and controlling resource allocation in many types of computer systems, such as database management systems [12], Web servers [1], operating systems [23] and in utility grid environments. In Web servers, priority-based request scheduling at both user and kernel level has been used to provide different levels of quality of service among clients [1]. Most operating systems use priorities as a way to implement a processor scheduling policy. Newly arriving high-priority processes are given the processor, even though processes of lower priority may have been waiting longer for the processor. Priority scheduling may be preemptive or non-preemptive. In the preemptive case, processes lose control of the resource when processes of higher priority arrive. The suspended processes resume their execution when there are no processes of higher priority waiting for the processor. This is called preemptive resume priority scheduling. This is the type of priority scheduling that is considered in this section. In the nonpreemptive case, low-priority processes are never interrupted by processes of higher priority while being served. Unfortunately, the use of priority as a scheduling discipline violates the conditions given in Chapter 13 for the existence of a product-form solution for QNs. This means that an approximate solution is needed. The motivation for the approximation is shown through an example. Then, the general algorithm is presented.

Table 15.3. Response Time Profile per Service Center

Class	Response Time (sec)
	Average	Blocking	Processor	Disk 1	Disk 2
Query	2.17	1.39	0.19	0.59	-
Update	5.36	2.77	0.68	1.67	0.24

15.4.1 Two-Priority Example

Consider a server composed of a powerful processor and two disks (D1 and D2) used to support an interactive service with 500 simultaneous clients. The total workload may be further decomposed into two workloads: corporate partners and consumers. Table 15.4 presents the service demands and workload intensity parameters for the two workloads. Since corporate partners have a more strict response time requirement, one would like to answer the following questions. How would the response time of the corporate partner and consumer workloads classes change if one assigned a higher CPU scheduling priority to the corporate partners? Would the response time for the consumer class be increased significantly?

Table 15.4. Input Parameters for Priority Example

Parameter	Class
	Consumers	Corporate
Service Demand (sec)
Processor	0.015	0.033
D1	0.011	0.018
D2	0.015	0.022
Number of clients	400	100
Think time (sec)	8	5

Before answering these questions, one must use the models to obtain the average response time of both classes when both of them have the same priority. The model is composed of four devices: a delay device to represent the think time at the clients, three queuing load-independent devices to represent the processor, and the two disks. The following response times are obtained with the multiclass MVA algorithm (see Chapter 13): 3.74 sec and 1.75 sec for corporate and customer classes, respectively.

The modeling of priorities is considered now. For that matter, the approach called stepwise inclusion of classes (SWIC) is used [2]. Note that the consumer class does not interfere at all with corporate requests at the CPU since the latter have preemptive priority at the CPU over the former. Thus, in this respect, corporate requests see the CPU as if it were dedicated to them. On the other hand, consumer requests see the portion of the CPU that is left after corporate requests have used it. On the remaining part of the computer system (i.e., the I/O subsystem), both classes have the same priority.

Start by obtaining an estimate of the CPU utilization due to the corporate class only. This can be done by building a model with the corporate class as the only class. Now, build a model with both the corporate and consumer classes and an additional processor, called shadow processor (see Fig. 15.6).

Figure 15.6. Shadow CPU for priority modeling.

The use of the original and shadow processors by corporate and consumer classes is governed by the following rules:

• corporate requests use only the original CPU.

• consumer requests use only the shadow CPU.

The problem now is how to compute the service demands of the original and shadow CPUs, and respectively, for class r, where r may be p (for corporate) or c (for consumer). Since each class uses only its own dedicated CPU, it follows that

Since the corporate class has higher priority over the consumer class, its service demand at the original CPU is equal to its CPU service demand D_cpu,p. Hence,

The CPU service demand of consumer requests at the shadow CPU has to be inflated to reflect the fact that it will take these requests longer to go through the CPU due to the presence of higher-priority requests. The higher the CPU utilization due to corporate requests, the more the service demand of consumer requests has to be inflated. The inflation factor 1/(1 U_cpu,p) has the desired properties. Thus,

The steps necessary to solve the priority model are:

1. Build a single-class model. This model includes the corporate class only, the original CPU, the terminals, and the disks. Using the parameters of Table 15.4 in the MVA algorithm yields the throughput of the corporate class as 11.44 request/sec. Therefore, the CPU utilization can be computed as U_cpu,p = D_cpu,p x X_0,p = 0.033 x 11.44 = 0.378.

2. Add the shadow CPU and the consumer class. Compute the service demands at the shadow and original CPUs as follows:

   

   
   

   Using the MVA algorithm, the response time for the corporate class is computed as 1.04 sec and as 1.78 sec for the consumer class. So there is a significant improvement in the response time of the corporate class (from 3.74 sec to 1.04 sec) with very little increase in the response time of the consumer class (2% increase). The reason is that the consumer class has a much smaller service demand at the processor than that of the corporate class. So, giving priority to the corporate class at the processor does not hurt the lower-priority class too much.

The next section generalizes the algorithm presented in this example to the case of more than two priorities.

15.4.2 SWIC Priority Algorithm

Using the notation introduced in Chapter 2, consider that there are P priority groups numbered from 1 to P. Let Prior (r) denote the priority of class r customers. Classes in priority group 1 have the highest priority, while those in group P have the lowest one. The SWIC algorithm builds P different models. The first model contains all classes of the highest priority (priority 1) only. The second model contains all classes of priority 1 and 2 and a shadow CPU to be used exclusively by customers of priority 2. As in the previous example, the service demand at this shadow CPU has to be inflated by dividing the original service demand by (1 - CPU utilization of higher-priority customers). In general, each step introduces an additional priority, an additional shadow CPU, and the service demands of the classes just included in the model are inflated. The P different QN models considered by the SWIC algorithm are denoted Q₁, ..., Q_P. Figure 15.7 shows the SWIC algorithm. Let indicate the service demand of a class r job of priority p at shadow CPU p. The notation D_cpu,r stands, as usual, for the service demand of class r jobs at the CPU. Denote by W(p) the set of classes of priority p. Thus, W(p) = {r | Prior(r) = p}.

Figure 15.7. SWIC algorithm for priority modeling.

The SWIC algorithm was shown to be very accurate. In Ref. [2], the authors compare the results obtained with SWIC with exact results obtained by solving global balance equations and with results from other approximations. The global balance equation method (explained in Chapter 10) can only be used in very small examples since the number of states grows very fast with the degree of multiprogramming. Other approximations have been proposed. Agrawal presents a nice treatment of various approximation methods for modeling priorities [3]. Lazowska et al. propose another method, which is also based on the notion of shadow CPUs and service demand inflation, but is iterative in nature [23]. A discussion of this method is left as an exercise.

Example 15.4.

Table 15.5 contains parameters for an example of the execution of the SWIC algorithm. The example has four classes and three priorities. The assignment of priorities to classes is reflected in the following W function: W(1) = {1,2}, W(2) = {3}, and W(3) = {4}. The system in question has one CPU and only one disk.

Table 15.5. Input Parameters for SWIC Algorithm Example

Class	Priority	Dcpu,r (sec)	Ddisk,r (sec)	Number of Processes
1 2 3 4	1 1 2 3	0.10 0.15 0.80 0.90	0.50 0.35 0.20 0.06	3 4 2 1

Table 15.6 shows the results of the execution of the algorithm. The response times per class are 4.03 sec, 2.93 sec, 3.34 sec, and 4.08 sec, for classes 1 through 4, respectively.

Table 15.6. Results for the SWIC Algorithm Example

	Model
	Q1	Q2	Q3
	0.10	0.10	0.10
	0.15	0.15	0.15
	-	0.8/(1 0.324) = 1.18	0.8/(1 0.287) = 1.12
	-	-	0.9/(1 0.751) = 3.61
Ucpu,1	0.87 x 0.1 = 0.087	0.77 x 0.1 = 0.077	0.75 x 0.1 = 0.075
Ucpu,2	1.58 x 0.15 = 0.237	1.40 x 0.15 = 0.210	1.36 x 0.15 = 0.204
Ucpu,3	-	0.58 x 0.8 = 0.464	0.60 x 0.8 = 0.480
Ucpu,4	-	-	0.25 x 0.9 = 0.225
Ucpu,r	0.324	0.751	0.984