Description

Consider a stream of tasks executing in two processors, P1 and P2. The arrival rate of the tasks follow a Poisson arrival process with mean arrival rate of 1 / λa. On arrival a task is allocated to P1 with a probability of 0.4 and to P2 with a probability of 0.6. Each processor executes the tasks allocated to it sequentially one after the other. The execution time of the tasks follow the exponential distribution with mean λb. We wish to simulate the system and compute various features of the system, such as task throughput (number of tasks completed per second), average load on each processor (number of tasks pending in its queue), and expected waiting time (time for which a task waits before being executed). In an event driven simulator, we maintain a queue of events ordered by time stamps. In this case, we will use two types of events, namely arrival events for the arrival of the tasks one after the other (separated by time), and service events (representing the completion of tasks). Broadly, we do the following: 1. In the beginning, we have only the arrival event, 〈 Ea, t 〉, for the first task. In general, every arrival event, 〈 Ea, t 〉, tells us that the next task will arrive at time t. 2. In each iteration, simulation time progresses to the time of the first event, that is, the time stamp of the first event in the queue. 3. When an arrival event with timestamp, t, is processed to create the next task, Tj, we do the following: (a) We choose the processor, X, (where X=1 or X=2) for executing the task. The choice of X (1 or 2) is made randomly, such that P[X=1] = 0.4 and P[X=2] = 0.6. (b) We add a service event, 〈 Es, X, t + δ 〉, for that task into the queue. The execution time, δ, for the task is chosen randomly following the exponential distribution. This will be explained shortly. (c) We also add another arrival event, 〈 Ea, t + ∆ 〉, into the queue. This models the arrival of the next task, where the inter-arrival time, ∆, is chosen as per the Poisson arrival process. This will be explained shortly. 4. When a service event is processed, we mark the task as completed and note the completion time. Note that time is incremented in non-uniform amounts, that is, the time between successive events. This makes event driven simulators much faster than simulators which increase time by a constant amount