UNIVERSITY OF CALIFORNIA College of Engineering Department of Electrical Engineering and Computer Sciences Computer Science Division CS 162 Prof. Alan J. Smith Assignment 1 In this assignment, you are to write a simulation of CPU schedul- ing. How to do this will be discussed in section. You are to simulate a simple open queueing system that looks like this: _____ ______ | | | ---------->------>||||||||--------> | CPU |------------> ^ _____| _____| | | | | |---------<---------<------| Arrivals You are to simulate the arrival of 1000 customers. Cus- tomers arrive with exponentially distributed interarrival times with mean interarrival time 1.0. Please generate the interar- rival times only once; save them in an array and reuse the same interarrival times for each simulation. (Please discard any interarrival time that is less than 0.02 or greater than 40.0. If you have such a value, throw it away and generate a new one.) The simulation ends when the 1000’th customer arrives. Please compute the actual mean and standard deviation of the interar- rival times, for all 1000, and print them out as part of your answer. Note that the system starts empty, and that the first customer arrives at time T1, (not 0); i.e. after the first inter- arrival time is added to zero. Note: Use at least 32-bit arithmetic for all calculations; 64-bit would be even better. (That includes all random number generation, interarrival times and service times.) With 32-bit arithmetic, the chances that two numbers will be equal (e.g. that two events will happen at the same time) should be less than one in one million. -2- Service Times The service time of customers will be hyperexponential, dis- tributed as follows: With probability .8, the customer’s service time will be exponential with mean 0.20. With probability .15, the customer’s service time will be exponential with mean service time 1.0. With probability .05, the customer’s service time will be exponential with mean 10.0. Please generate the service times only once, and save them for use in each simulation. (Please discard any service time that is less than 0.02 or greater than 40.0. If you have such a value, throw it away and generate a new one.) Please compute the actual mean and standard deviation of the service times, for all 1000, and print them out as part of your answer. Note that for each simulation (below), the i’th customer will arrive at the same time, and will require the same amount of service time. Thus any difference in performance should be due to the different scheduling algorithms, not differences in the random numbers. Scheduling Algorithms You are to simulate the following scheduling algorithms. In each case, consider three cases: The time X to switch between processes is either 0.0, 0.01, or 0.10. (I.e. each simulation is run 3 times.) This overhead is incurred whenever: (a) there is a task switch from job A to job B or (b) a job arrives to an empty system. If (c) the clock interrupts at the end of a quantum and the same job is resumed, the overhead is X/2. (d) When a job arrives to a busy system, the overhead is X/2 if the currently running job continues (after the arrival of the new job), and is X if the running (currently active) job changes. Logically, you can consider the overhead in item (d) to consist of two parts: X/2 overhead to accept the new job, and put it in the job queue. X/2 overhead to start whichever job starts next, if it is a dif- ferent job. Overhead times are not atomic. If a job arrives in the mid- dle of a task switch overhead, the task switch is suspended, the arrival is processed (with its own overhead), and then the prior task switch is resumed. In each case, please compute the mean flow time for all cus- tomers that have completed service and left the system, the mean number of customers in the system (in the queue + in service), the standard deviation of the flow time, and the mean and stan- dard deviation of f(i)/s(i), where s(i) is the service time for the i’th customer and f(i) is the flow time for the i’th cus- tomer. For the flow time computation, please ignore any cus- tomers left in the system after the 1000’th customer arrives. (I.e. your computation includes only customers who have completed service and have left the system.) -3- First Come, First Serve Please simulate the system using FCFS scheduling, with each job run to completion. Shortest Remaining Processing Time Please simulate the system using SRPT scheduling. At any given time, you are to be running the job with the least remain- ing processing time. Note: Consider the following case: You are running job A. Job B arrives, which is shorter than the remaining time of job A. You enter the task switch overhead to switch to job B. While in the task switch overhead, job C arrives, and C is shorter than the remaining time for B. You should process it the following way: Overhead X/2 to accept job B and put it in the job queue. Overhead of X/2 to accept job C and put it in the job queue. Overhead of X/2 to start job C. Round Robin Please simulate the system with round robin scheduling, using a time slice (quantum) of Q=0.0111, 0.11, and 1.0. (I.e. each of these simulations is run for each quantum size. Thus this item requires that you run 9 simulations.) If there is only one job in the system, the switching overhead (X/2) still occurs every time quantum, since the clock interrupts at that interval. When a new job arrives, it always goes in the back of the queue. Shortest Job First Please simulate the system using SJF scheduling. Note that this is not preemptive; once a job starts, it runs to completion (except for overhead to accept new jobs and enter them in the queue). Shortest Elapsed Time Please simulate the system using SET scheduling. Note that when a job starts a period of execution, it will be allowed to run for some time Q (Q=0.0111, 0.11, and 1.0) before being inter- rupted, unless it completes first. (I.e. each of these simula- tions is run for each value of Q.) Note that an arriving job isn’t eligible to run until the quantum for the currently running job ends. Data As noted above, you should generate your own arrival and service times. For debugging purposes, we will also provide you with a sample set of arrival and service times. They will be in -4- the ~cs162/Homework directory. You should also show the results of all of your simulations using the provided (sample) arrival and service times. Writeup Please put together a table showing your simulation results in some clear and useful manner. Please do a writeup, approxi- mately one page single spaced, commenting and explaining on what you’ve observed from the simulation runs. Please relate what you observed to what was presented in lecture. Part of your grade will depend on the quality and clarity of your writeup; it should be in grammatically correct standard English. Frequently Asked Questions Below are the answers to some questions that have occurred. 1. If the first job ends at the same time the second job enters the queue, is this considered entry into an empty system, assum- ing no other jobs in the queue? This shouldn’t happen, but if it does, the answer is "no." Note: If two events appear to happen at identical times, then assume that the one that was entered in the event list first happens first. But in general, there should never be genuinely simultaneous events - if you are using 32-bit or 64-bit arith- metic, what are the chances that two numbers are exactly the same?? 2. Is the "arrival time" of a job affected by the overhead asso- ciated with getting the job into the system? Do we say a job has not arrived until the work has been done to introduce it into the system? No, the arrival time is simply (arrival time of j(i-1)) + (interarrival time of j(i)). 3. In the timesliced algorithms, if a job arrives in the middle of an executing job’s quantum, a. is the overhead of the arriving job during or after the quantum? b. does the running job get to run until the end of its quantum, or does the scheduler run right away? c. does the running job get to run for its entire alotted time, i.e. t(end_of_quantum) + overhead of all arriving jobs, if overhead is incurred during a quantum? -5- a. during; b. the arriving job is put into the job queue immediately, and then the job continues to run to the end of its quantum; c. yes, the job runs for its entire alloted time, so the time of the end of the quantum will be affected by the number of jobs that arrive during it. General Instructions 1. The assignment must be programmed in Java. 2. The following files, and _only_ the following files, must be submitted: program source, writeup, README (optional - special information for readers), makefile (optional). 3. If the program is run with no arguments, it should generate random data for 1000 customers as specified in parts 1 and 2 of the assignment and run the simulation on that data. If the program is run with the name of a file in the current directory as an argument, it should read data (interarrival and service times) from that file and run a simulation on that data. 4. The program should print the following to the standard output when run (with the table filled in, of course): % hw1 mean interarrival time: xx std dev of interarrival times: xx mean service time: xx std dev of service times: xx A B C D E F G -------------------------------------------------------------------- FCFS 0 FCFS 0.01 FCFS 0.1 SRPT 0 SRPT 0.01 SRPT 0.1 RR 0 0.0111 RR 0 0.11 RR 0 1.0 RR 0.01 0.0111 RR 0.01 0.11 RR 0.01 1.0 RR 0.1 0.0111 RR 0.1 0.11 RR 0.1 1.0 SJF 0 SJF 0.01 SJF 0.1 SET 0 0.0111 SET 0 0.11 -6- SET 0 1.0 SET 0.01 0.0111 SET 0.01 0.11 SET 0.01 1.0 SET 0.1 0.0111 SET 0.1 0.11 SET 0.1 1.0 key -- A: Switching overhead B: Quantum (if applicable) C: Mean Flow Time D: Std Dev of Flow Time E: Mean flow_time(i) / service_time(i) F: Std dev of flow_time(i) / service_time(i) G: Mean number of customers Hints and Information 1. You should write an event driven simulation, not a clock or interval type simulation. What this means is that your simu- lator basically cycles through the following loop: (get event) (reset clock to event time) (update system statistics) (update system state) (generate any new events and put them on event list) (continue loop). The TAs will talk more about event driven simulation in dis- cussion section. 2. You can generate an exponentially distributed random variable with mean 1.0 by generating a Uniform (0,1] random num- ber U, and computing (-ln (U)). ("ln" is the natural log.) If you want an exponentially distributed random number with mean K, multiply the one you generate by K. 3. Any further information about this (and other) assign- ment(s) will be given out in discussion section or posted online.