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 nonreentrant 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 SQNHQN and consists of a twolayer 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 productform 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. Multiservers can be handled by using loaddependent servers (see Chapter 14) or approximations [34]. 15.5.1 Single Class Algorithm Consider the case of N processes P_{1}, ···, P_{N} that alternate between executing noncritical section and critical section code. Any number of processes can be concurrently executing their noncritical 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 noncritical section code is the CPU and that the CPU scheduling discipline is processorsharing. 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 delayresource (illustrated as a rectangle) that corresponds to the noncritical 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. : softwarehardware 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 noncritical section code. This time does not include the time spent waiting to use the CPU while executing noncritical 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 noncritical 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 SQNHQN 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 N^{h}, 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. SQNHQN 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 B^{k}. In the case of our example, this is equal to the average number of processes waiting in the queue for the CS resource. Thus, B^{k} = U_{cs}, where is the average number of processes at resource CS in the SQN and U_{cs} is the utilization of resource CS. In general, Equation 15.5.21 where L_{j} is the average number of processes in the waiting line for software resource j. Step 4  Solve the HQN with as service demands and N^{h} = N B^{k} as customer population. Note that the solution to a QN with a noninteger 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  (B^{k} B^{k} 1)/B^{k} > 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 righthand side of Eq. (15.5.27) is the total time (waiting + service) spent at the CPU by a process while executing noncritical 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 noncritical 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 noncritical 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 SQNHQN 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 SQNHQN approach is very small and does not exceed 3.05% in this example. Table 15.8. Throughput (processes/sec) for Example 15.xN  SQNHQN 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 SQNHQN 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 (N^{h}) 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  N^{h}  R  N^{s}  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. = (N_{1}, ..., N_{R}): population vector for the SQN. N_{r} is the multithreading level for class r. = (N_{1}, ..., N_{R}): population vector for the HQN. N_{r} is the number of customers in class r. = (B_{1}, ..., B_{R}): vector of number of processes blocked, i.e., waiting for a software resource. B_{r} is the number of class r processes blocked for a software resource. : softwarehardware 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 L_{j,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 noninteger 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 max_{r} 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 multithreaded software server can be considered by including a multiserver queue in the SQN and using approximation techniques [34] to solve QNs with multiservers or QNs with loaddependent servers as done in Chapter 14. Other approaches to modeling software contention were presented before [4, 20, 22, 32, 29, 36, 42].
