CSCI 8710

Topics Covered since Midterm:

• Ch. 4 -- Performance Engineering Methodology
• Ch. 5 -- Case Study: DB Server
• Ch. 6 -- Case Study: Web Server
• Ch. 7 -- Case Study: Data Center
• Ch. 8 -- Case Study: E-Business Service
• Ch. 9 -- Case Study: Help Desk Service
• Ch. 10 -- Markov Models
• Ch. 11 -- Single Queue Systems (lightly -- the names of the types of queues (G/G/1, M/G/1, M/M/1 and what they mean)
• Ch. 12 -- Single Class MVA Additional class notes
  • Protocols

  Elements of the Final Exam

  Problems (60%) -- Similar in flavor to ...

  • Give a set of 10 integer values, calculate values such as max, min, range, first quartile, median, third quartile, midhinge, interquartile range, variance, standard deviation, coefficient of variation
  • Building a performance model: apportioning resource utilization to various classes. Imagine that you are in the process of building a performance model. You have a trace of the resource utilization of a series of requests and have already performed clustering analysis on the trace, with the following result:

    Cluster_num	cpu_time	i/o ops		i/o ops		points in
    		(msec)		disk 1		disk 2		cluster
    -----------------------------------------------------------------------------
      1		 67.5		8.0		11.0		50
    
      2		434.2	       62.4		73.1            80
    
      3             136.1          69.8             36.7            70
    
    -----------------------------------------------------------------------------
    

    Calculate apportionment factors (percentages) for each class for each device.
    If the overall CPU utilization is 80%, what portion of this is attributable to class 1?

  • Computing average concurrency level. A system is monitored for 60 seconds. 4 jobs(A, B, C, D) are active during that period. A is active for 20 seconds, B is active for 14 seconds, C is active for 32 seconds, and D is active for 38 seconds. What is the average concurrency level of the system?

  • Example: A web server receives 10 requests/sec. The maximum number of requests in the server is 2. Requests that arrive and find three requests being processed are rejected. The throughput of the system varies with the number of requests, as follows:

    
    	Num_requests	Throughput
    	===========================
    		0		0
    		1	       12
    		2	       18
    
    

    • Construct a markov model graph for this problem. Label the nodes and edges.
    • Compute the probability of each state.
    • What is the probability that an incoming request is rejected?
    • What is the average number of requests in execution?
    • What is the average throughput?
    • What is the average time that a request spends in the server?
  • Single-Queue systems: given formula sheet and problem description, select appropriate queue type and formula (G/G/1, M/M/1, M/G/1, M/G/1 with vacations, M/G/1 with priorities. Justify choice of formula, set up equations (not necessarily solve ...)
  • Additional sample problems in class on Tues and Wed

  Short answer questions (40%) -- of this type ...

  • Given partially solved problems similar to those described above, provide or select correct choice for element of problem.

  • Clustering analysis -- why do we do it, how does k-means work, parameter transformation(act - min/max-min)(log)

  • Confidence Interval Estimation of the Mean -- understand concept and know terminology. Be able to interpret graphs of confidence intervals.

     	Pr[ c1 <= mean <= c2] = 1 - a
    
    	(c1,c2): confidence interval
    	a: significance level (e.g., 0.05)
    	1-a: confidence coefficient (e.g., 0.95)
    	100(1-a): confidence level (e.g., 95%)
    	

  • Section 11.2 -- Single Queue, Single Server Systems : terminology, formulas, relationships.

  • What does it mean for a queue to be G/G/1? M/M/1? M/G/1?

  • Given a description of the properties of a queue, classify it as M/M/1, M/G/1 or G/G/1.

  • What does it mean for a queue to be M/G/1 with "vacations"?

  • Given a textual description of the MVA algorithm, and some of the formulas, be able to fill in the missing formulas.

  • Given the series of formulas employed in the MVA algorithm and a partial textual description, be able to fill in the missing text.

  • Given a partially solved iteration of the MVA algorithm, compute the values at the next step.

  • What is a balanced system? How does the existence of a balanced system simplify solution of the MVA algorithm?

  • Queueing disciplines: FCFS, PS, IS, LCFS-PR -- given a textual description of properties, identify type of queue. Given type of queue, select correct description.

  • Given formulas / algorithms for solution of multi-class queuing networks (as in chapter 13), be able to provide a textual explanation of a particular step, or select the correct explanation from a list of steps.

  • Workload models: what are they? natural v. artificial, executable v. non-executable

  • System-level modeling terminology: population size (infinite v. finite), service rate (fixed v. variable), max_queue_size (unlimite v. limited)
  • BCMP -- what is it? What does it guarantee? What are the assumptions?
  • Inputs and outputs for multiclass closed models
  • Inputs and outputs for multiclass open models
  • "Arrival theorem" -- interpretation for open v. closed
  • Additional sample problems in class on Tues and Wed