The response time of a transaction or request submitted to a computer system can be broken down into three components. The first is the total service time, i.e., the total time spent by transactions obtaining service from the various physical resources such as processors, disks, and networks. The second component is the total time spent waiting to use a physical resource. Finally, the third component (software contention) is the time spent to access a software resource such as a non-reentrant software module, a software thread, or a database lock. It is important to take into account the effect of software contention when estimating the total response time. This section provides a simple analytical modeling technique for estimating software contention delays. The technique, first presented in [25], is called SQN-HQN and consists of a two-layer queuing network model. Software resources are modeled by a software queuing network (SQN) and physical resources by a hardware queuing network (HQN). The effect of software contention on the physical QN and the effect of physical resource contention on the software QN requires an iterative technique to solve this dependency. The technique relies on existing solution techniques for open, closed, multiclass queuing networks and can be used with both product-form QNs and approximations [3] used to handle situations such as simultaneous resource possession [3, 21, 26] and priorities [2, 3, 33] as discussed in this chapter. Multi-servers can be handled by using load-dependent servers (see Chapter 14) or approximations [34]. 15.5.1 Single Class Algorithm Consider the case of N processes P1, ···, PN that alternate between executing non-critical section and critical section code. Any number of processes can be concurrently executing their non-critical code. However, only one of them can be executing the critical section code. If a process attempts to enter its critical section code while another process is inside the critical section, the attempting process is put to sleep at the queue associated with the semaphore that controls access to the critical section. Assume in this simple example that the only physical device used by all processes during the execution of the critical and non-critical section code is the CPU and that the CPU scheduling discipline is processor-sharing. The software phases of a process execution can be depicted by a software queuing network (SQN) as in the top part of Fig. 15.8. The SQN has two resources (software modules). One is a delay-resource (illustrated as a rectangle) that corresponds to the non-critical section code; there is no queuing for a software resource during this phase. The other software resource is a queuing resource, which corresponds to the critical section code. Figure 15.8. Software and hardware QNs for the critical section example. While a process a customer in the SQN is using the software resources in the SQN, it is also using or waiting to use physical resources (e.g., CPUs and disks). Delay resources are used in the SQN to represent software resources for which there is no software contention. The queuing network associated with the physical resources, the hardware queuing network (HQN), is shown in the bottom part of Fig. 15.8. Customers in the HQN are processes using the physical resources as a result of the execution of software modules. The time spent at the NCS and CS resources in the SQN depends on the contention for access to the physical resources, the CPU in this case. Also, the number of processes contending for the CPU, i.e., the number of processes in the HQN, is equal to the number of concurrent processes that are not blocked waiting for entry to the critical section. The blocked processes are sleeping and are therefore not present in any HQN queue. Therefore, the customer population in the HQN is equal to N B where B is the number of processes blocked for a software resource. Some notation needs to be defined before proceeding with an explanation on how contention for access to software resources can be computed in the single class case. : software-hardware service demand, i.e., total service time of a process executing software module j when using physical resource i in the HQN. The superscript "sh" indicates that these service demands are related to the mapping between the software and hardware QNs. For example, is the total CPU time for the execution of the non-critical section code. This time does not include the time spent waiting to use the CPU while executing non-critical section code. : software service demand, i.e., total service time to execute module j in the SQN. The superscript "s" indicates that this service demand relates to the software QN. For example, is the total service time to execute the non-critical section code. The service demand is the sum of all service times at all physical devices during the execution of module j. Thus, Equation 15.5.15
: hardware service demand, i.e., total service time of a process at physical resource i in the hardware QN. For example, is the total service time of a process at the CPU. This time is the sum of the service demands due to the execution of all modules of the process. Thus, Equation 15.5.16
For example, . n): residence time, i.e., total time spent by a process at physical resource i, waiting for or receiving service, when there are n processes at the HQN. An iterative algorithm, the SQN-HQN algorithm, can then be used to estimate software contention time and to compute all performance metrics (e.g., response time and throughput). The inputs to the algorithm are the service demands and the number N of processes. The algorithm iterates between solving the SQN and the HQN. Figure 15.9 illustrates the relationship between the SQN and HQN models. The SQN model receives as input the number of processes N and the software service demands and produces the number B of processes blocked for software resources as output. The HQN model takes as input a number of customers Nh, which is the original number of processes minus the number of processes blocked for software resources, and the hardware service demands. The output of the HQN model is the set of residence times at each physical device. These residence times are used to adjust (see step 5 of the algorithm) the software service demands for the SQN model. The iteration starts by solving the SQN assuming zero contention for physical resources. The algorithm iterates until successive values of the number, B, of processes blocked for software contention are sufficiently close. Figure 15.9. SQN-HQN scheme. Step 1 - Initialization: Equation 15.5.17 Equation 15.5.18 Equation 15.5.19 Equation 15.5.20 Step 2 - Solve the SQN with as service demands and N as customer population. Step 3 - Compute the average number of blocked processes Bk. In the case of our example, this is equal to the average number of processes waiting in the queue for the CS resource. Thus, Bk = Ucs, where is the average number of processes at resource CS in the SQN and Ucs is the utilization of resource CS. In general, Equation 15.5.21 where Lj is the average number of processes in the waiting line for software resource j. Step 4 - Solve the HQN with as service demands and Nh = N Bk as customer population. Note that the solution to a QN with a non-integer customer population can be obtained using Schweitzer's approximation [35]. Step 5 - Adjust the service demands at the SQN to account for contention at the physical resources as follows Equation 15.5.22 Thus, for the critical section example these equations become Equation 15.5.23 Equation 15.5.24 Step 6 - (Convergence Test): If | (Bk Bk 1)/Bk |> x then k Step 5 of the above algorithm can be explained using the critical section example. The residence time equation for MVA applied to the HQN is Equation 15.5.25 But, Equation 15.5.26 Hence, using Eqs. (15.5.25) and (15.5.26), yields Equation 15.5.27 The first term of the right-hand side of Eq. (15.5.27) is the total time (waiting + service) spent at the CPU by a process while executing non-critical section code and the second term is the total time spent at the CPU by a process while executing the critical section code. For example, using Eqs. (15.5.25) and (15.5.27) one can write the total time spent at the CPU while executing the non-critical section code as Equation 15.5.28 Example 15.5. Consider a computer system with one CPU and three disks (see bottom part of Fig. 15.10). Processes execute non-critical section code and then enter one of two critical sections (see top portion of Fig. 15.10). Figure 15.10. Software and hardware queuing networks for Example 15.x The service demands (i.e, the values of ) are given in Table 15.7 and are the same as in [4]. The last row shows the values of and the last column contains the values of . Table 15.7. Service demands (in sec) for the example in [4] | Software Module | Hardware Demands |
---|
Device | NCS | CS 1 | CS 2 |
---|
CPU | 0.2000 | 0.0600 | 0.0808 | 0.3408 | Disk 1 | 0.0560 | 0.0576 | 0.1212 | 0.1136 | Disk 2 | 0.0360 | 0.0000 | 0.000 | 0.1572 | Disk 3 | 0.0360 | 0.0000 | 0.0000 | 0.0360 | Software Demands | 0.3280 | 0.1176 | 0.2020 | | Table 15.8 shows the results (i.e., throughputs) obtained with the SQN-HQN algorithm and with global balance equations (i.e., exact solutions), as reported in [4], for eight values of the number of concurrent processes N. The last column of the table shows the absolute percent relative error relative to the global balance equations solution. The error of the SQN-HQN approach is very small and does not exceed 3.05% in this example. Table 15.8. Throughput (processes/sec) for Example 15.xN | SQN-HQN Solution | Exact Solution | Absolute % Relative Error |
---|
1 | 1.544 | 1.54 | 0.27 | 2 | 2.088 | 2.11 | 1.06 | 3 | 2.317 | 2.37 | 2.22 | 4 | 2.428 | 2.49 | 2.49 | 5 | 2.487 | 2.56 | 2.86 | 6 | 2.521 | 2.60 | 3.05 | 7 | 2.541 | 2.62 | 3.00 | 8 | 2.555 | 2.63 | 2.86 | 15.5.2 Open QN at the Software Level The SQN-HQN technique can be extended to include the case in which the SQN is modeled as an open queuing network as illustrated in Figure 15.11. In that case, processes arrive at a rate of l requests/sec. The rest of the SQN and the HQN are the same as in the example of Figure 15.10 and the service demands are as in Table 15.7. Figure 15.11. Open QN at the software level. Steps 2 and 4 of the algorithm described in Section 15.5.1 should be replaced by the following to contemplate the case of open SQNs. Table 15.9 contains results of running the modified algorithm for the case of l = 3 processes/sec. The table shows the results of the first 10 iterations. Column 2 (Nh) is the customer population used to solve the HQN at each iteration. The next column shows the average response time R. Columns 4 and 5 show the average number of requests in the SQN and the average number of blocked requests in the CS1 and CS2 queues, respectively. The last three columns show the modified service demands for the SQN at each step. Note that the values for iteration 0 are the original values of these demands. The relative error in B is 0.123% at the tenth iteration. Table 15.9. Results of the first 10 iterations for the open SQN example | Modified SQN Demands |
---|
Iter | Nh | R | Ns | B | NCS | CS1 | CS2 |
---|
0 | - | | | | 0.3280 | 0.1176 | 0.2020 | 1 | 1.295 | 0.821 | 1.641 | 0.346 | 0.3662 | 0.1302 | 0.2235 | 2 | 1.440 | 0.946 | 1.893 | 0.453 | 0.3858 | 0.1365 | 0.2342 | 3 | 1.513 | 1.014 | 2.028 | 0.515 | 0.3958 | 0.1397 | 0.2396 | 4 | 1.550 | 1.050 | 2.100 | 0.549 | 0.4010 | 0.1414 | 0.2424 | 5 | 1.570 | 1.069 | 2.137 | 0.568 | 0.4037 | 0.1423 | 0.2438 | 6 | 1.580 | 1.079 | 2.157 | 0.577 | 0.4051 | 0.1427 | 0.2446 | 7 | 1.585 | 1.084 | 2.167 | 0.582 | 0.4059 | 0.1430 | 0.2450 | 8 | 1.588 | 1.086 | 2.173 | 0.585 | 0.4062 | 0.1431 | 0.2452 | 9 | 1.589 | 1.088 | 2.175 | 0.587 | 0.4064 | 0.1432 | 0.2453 | 10 | 1.590 | 1.088 | 2.177 | 0.587 | | | | 15.5.3 The Multiclass Algorithm The algorithm presented in Section 15.5.1 generalizes in a straightforward manner to multiple classes. A generalized notation for the multiple class case is in order. Let R: number of classes in the SQN and in the HQN. = (N1, ..., NR): population vector for the SQN. Nr is the multi-threading level for class r. = (N1, ..., NR): population vector for the HQN. Nr is the number of customers in class r. = (B1, ..., BR): vector of number of processes blocked, i.e., waiting for a software resource. Br is the number of class r processes blocked for a software resource. : software-hardware service demand, i.e., total service time at physical resource i of a class r software module j. : software service demand, i.e., total service time to execute module j of class r in the SQN. The service demand is the sum of all service times at all physical devices during the execution of module j. Thus Equation 15.5.29
: hardware service demand, i.e., total service time at physical resource i for class r in the hardware QN. This time is the sum of the service demands due to the execution of all modules of a process. Thus Equation 15.5.30
: residence time, i.e., total time spent by a class r process at resource i, waiting for or receiving service, when the customer population at the HQN is given by the vector . The iterative algorithm used to estimate the software contention time and to compute all performance metrics (e.g., response time and throughput) is given below. The inputs to the algorithm are the service demands and the vector . The algorithm iterates until successive values of are sufficiently close. Step 1 - Initialization: Equation 15.5.31 Equation 15.5.32 Equation 15.5.33 Equation 15.5.34 Step 2 - Solve the SQN with as service demands and as customer population. Step 3 - Compute the average number of blocked processes per class as Equation 15.5.35 where Lj,r, r = 1, ..., R, is the average number of class r processes in the waiting line for software resource j. Step 4 - Solve the HQN with as service demands and population vector as customer population. Note that the solution to a QN with a non-integer customer population can be obtained using Schweitzer's approximation [35]. The solution to the HQN provides the residence time values for all devices i and classes r. Step 5 - Adjust the service demands at the SQN to account for contention at the physical resources as follows Equation 15.5.36 Step 6 (Convergence Test): If maxr then k The same considerations discussed in Section 15.5.1 can be applied to the multiclass case. Situations that require modeling a queue for a multi-threaded software server can be considered by including a multi-server queue in the SQN and using approximation techniques [34] to solve QNs with multi-servers or QNs with load-dependent servers as done in Chapter 14. Other approaches to modeling software contention were presented before [4, 20, 22, 32, 29, 36, 42].
|