15.5 Modeling Software Contention


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.

graphics/15fig08.gif

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.

  • graphics/435fig01.gif: 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, graphics/435fig02.gif 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.

  • graphics/435fig03.gif: 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, graphics/435fig04.gif is the total service time to execute the non-critical section code. The service demand graphics/435fig03.gif is the sum of all service times at all physical devices during the execution of module j. Thus,

    Equation 15.5.15

    graphics/15equ515.gif


  • graphics/435fig05.gif: hardware service demand, i.e., total service time of a process at physical resource i in the hardware QN. For example, graphics/435fig06.gif 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

    graphics/15equ516.gif


    For example, graphics/436fig01.gif.

  • 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 graphics/436fig02.gif 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.

graphics/15fig09.gif

  • Step 1 - Initialization:

    Equation 15.5.17

    graphics/15equ517.gif


    Equation 15.5.18

    graphics/15equ518.gif


    Equation 15.5.19

    graphics/15equ519.gif


    Equation 15.5.20

    graphics/15equ520.gif


  • Step 2 - Solve the SQN with graphics/437fig01.gif 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 = graphics/437fig05.gif Ucs, where graphics/437fig05.gif 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

    graphics/15equ521.gif


    where Lj is the average number of processes in the waiting line for software resource j.

  • Step 4 - Solve the HQN with graphics/437fig02.gif 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

    graphics/15equ522.gif


    Thus, for the critical section example these equations become

    Equation 15.5.23

    graphics/15equ523.gif


    Equation 15.5.24

    graphics/15equ524.gif


  • 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

    graphics/15equ525.gif


    But,

    Equation 15.5.26

    graphics/15equ526.gif


    Hence, using Eqs. (15.5.25) and (15.5.26), yields

    Equation 15.5.27

    graphics/15equ527.gif


    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

    graphics/15equ528.gif


    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

    graphics/15fig10.gif

    The service demands (i.e, the values of graphics/436fig02.gif) are given in Table 15.7 and are the same as in [4]. The last row shows the values of graphics/437fig01.gif and the last column contains the values of graphics/437fig02.gif.

    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.x

    N

    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.

    graphics/15fig11.gif

    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.

    • New Step 2 - Solve the SQN with graphics/437fig01.gif as service demands and l as arrival rate and obtain graphics/392fig02.gif the average number of customers in the SQN.

    • New Step 4 - Solve the HQN with graphics/437fig02.gif as service demands and Nh = graphics/392fig02.gif 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].

    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.

    • graphics/442fig01.gif = (N1, ..., NR): population vector for the SQN. Nr is the multi-threading level for class r.

    • graphics/442fig02.gif = (N1, ..., NR): population vector for the HQN. Nr is the number of customers in class r.

    • graphics/442fig03.gif = (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.

    • graphics/442fig04.gif: software-hardware service demand, i.e., total service time at physical resource i of a class r software module j.

    • graphics/443fig01.gif: software service demand, i.e., total service time to execute module j of class r in the SQN. The service demand graphics/443fig01.gif is the sum of all service times at all physical devices during the execution of module j. Thus

      Equation 15.5.29

      graphics/15equ529.gif


    • graphics/443fig03.gif: 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

      graphics/15equ530.gif


    • graphics/443fig02.gif: 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 graphics/442fig02.gif.

    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 graphics/442fig04.gif and the vector graphics/442fig01.gif. The algorithm iterates until successive values of graphics/442fig03.gif are sufficiently close.

    • Step 1 - Initialization:

      Equation 15.5.31

      graphics/15equ531.gif


      Equation 15.5.32

      graphics/15equ532.gif


      Equation 15.5.33

      graphics/15equ533.gif


      Equation 15.5.34

      graphics/15equ534.gif


    • Step 2 - Solve the SQN with graphics/443fig01.gif as service demands and graphics/442fig01.gif as customer population.

    • Step 3 - Compute the average number of blocked processes per class as

      Equation 15.5.35

      graphics/15equ535.gif


      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 graphics/443fig03.gif as service demands and population vector graphics/444fig02.gif 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 graphics/443fig02.gif 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

      graphics/15equ536.gif


    • Step 6 (Convergence Test):

      If maxr graphics/444fig01.gif 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].



Performance by Design. Computer Capacity Planning by Example
Performance by Design: Computer Capacity Planning By Example
ISBN: 0130906735
EAN: 2147483647
Year: 2003
Pages: 166

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net