CPSC 531 Systems Modeling and Simulation (Fall 2005)

Assignment 1

A. Mahanti

Department of Computer Science

University of Calgary

Total Marks: 60

Due Date: 23:59 hours on October 16, 2005. Late Submissions will not be accepted.

Submission guideline:

Your work must be submitted using the submit system. Write-up your work using the word processing software of your choice and submit it either in PS or PDF format. Your TA will print your submission, grade it, and return them with their comments.

For question 1 and 2, you also need to submit the code. Please include a “ReadMe” file that describes how to compile and run your programs. Note that your program should compile and run on one of the department Linux servers.

Part I: Programming (40 marks)

  1. Single process Web server scheduling (25 marks)

The user perceived response time of Web requests is a function of several components such as: the transmission, propagation, and queuing delay in the network; delays caused by the client/server protocol interactions; and queuing delays at the Web server. In this assignment, we will study how the scheduling policy in use at the Web server affects the response time of the requests.

For simplicity, first consider a single-process Web server that serves static HTTP requests. Requests arrive at the server with interarrival times that are IID exponential random variables with mean 0.5 seconds. In the Web server context, the service time of a request can be estimated at the outset based on the size of the requested file. Assume that each request upon arrival specifies the size of the download, and that the file sizes are IID exponential random variables with mean 125 KB. A request arriving at the server may either immediately start receiving service (if the server process is idle) or queue for service (if the server process is busy servicing another request). Requests in queue are served according to the scheduling policy in use. In this assignment, we consider the following scheduling policies:

  • First-In-First-Out (FIFO) scheduling; and
  • Shortest Job First (SJF) scheduling, where the server’s queue is ordered according to the expected service demands of the jobs with the shorter jobs being in the front of the queue.

In your model, you will assume that the server process can deliver 1250 KB/second.

Your task is to write a simulation program in C/C++ for this Web server scheduling problem. Your program may use any standard ANSI C/C++ library and the “simlib” routines. No other packages or library routines are allowed. Each simulation run should continue until 5,000 requests are processed by the server.

Based on simulations, answer the following questions:

(a) For both policies, determine the mean and the maximum response time of the requests, the fraction of requests that are delayed in queue for more than 2 minutes, and the maximum number of requests in queue. Based on your results, which policy would you recommend?

(b) For both policies, determine the mean response time for “small”, “medium”, and “large” file transfers. Assume that file transfers of less than or equal to 25 KB are classified as “small”, file transfers of size between 125 KB and 1000 KB are classified as “medium”, and file transfers of size greater than or equal to 10,000 KB are classified as “large”. Comment on your results.

(c) Repeat (a) and (b) for mean request interarrival times of 0.25 and 4 seconds. What inference can you draw from your results?

  1. Multi-process Web server scheduling (15 marks)

Extend the simulation model developed in Question 1 to support N concurrent processes. Assume that the processing capability of each process is scaled by 1/N (i.e., each process works at (1250/N) KB/second). There is still a single queue of requests waiting for service. For this new simulation model, answer questions 1 (a), (b), and (c) for N = 2, 4, and 8. Comment on your results.

Part II: Probability and Statistics (5x4 = 20 marks)

  1. Suppose that two balanced dice are rolled, and let X denote the absolute value of the difference between the two numbers that appear. Determine and sketch the probability mass function (pmf) of X. [source DS02: Section 3.1, Q 3]
  1. Suppose that the probability density function (pdf) of a random variable X is as follows:for 0 < x < 1; , otherwise. Plot this pdf and determine the following probabilities: (a) P(X < 1/2); (b) P(1/4 < X < 3/4); and (c) P(X > 1/3). [source DS02: Section 3.2, Q 2]
  1. If an integer between 1 and 100 is to be chosen at random, what is the expected value? [source DS02: Section 4.1, Q 2]
  1. Suppose that a fair coin is tossed repeatedly until a head is obtained for the first time. (a) What is the expected number of tosses that will be required? (b) What is the expected number of tails that will be obtained before the first head is obtained? [source DS02: Section 4.2, Q 10]
  1. Show that for every random variable X, Var(X) = E(X2) – [E(X)]2.

**********************************