| Real Time Systems: Notes |
These notes are intended to provide a brief introduction to the concept and implementation of a discrete-even simulation program. Such simulations are often used in the field of computer science to evaluate the performance of algorithms. Examples of the kinds of algorithms whose performance has been evaluated experimentally by simulation include processor and disk scheduling algorithms, virtual memory algorithms, and routing algorithms.
A simulation is an imitation of a real system, that faithfully reproduces enough of the characteristics of the real system that one can pretend it is the real system for certain purposes. Probably the most familiar examples of simulations are video games, like flight simulators. A person who is flying a flight simulator is not really flying an airplane, but if the simulator is good the experience is close enough to flying a real airplane that skills developed on the simulator transfer to flying a real airplane. The obvious advantage of using a simulation is a safer and cheaper way to train a pilot than using a real airplane.
In general, a simulation program attempts to mimic in abstract form, using computations, some real-world system. This is sometimes also called computer modeling.
Simulations are used in computer science to test out ideas for software systems before full scale implemntation. For example, before implementing an operating system with virtual memory one might write a simulation to evaluate the comparative performance of different page replacement policies. The objective of the simulation would be to determine which of the given policies results in better system performance. Doing such a simulation would generally be less costly than producing different versions of the actual operating system. It may also be easier in the simulation than in a working operating sytems to extract the performance measures of interest, or to set up test scenarios that explore the particular questions of interest.
A discrete-event simulation starts with an abstract model of the real system to be simulated, expressed in terms of transitions of the system state that occur at discrete points in time. Each state such transition corresponds to an event. Events are classified as instances of a finite number of types, each of which has its own associated action on the system state. Each event instance is associated with a particular time of occurrence. Times are represented by integer counts of some fundamental time unit. The granularity of the time unit is chosen to fit the type of system being simulated and the level of detail one hopes to extract about the system's behavior.
The algorithmic structure of a discrete-event simulation is as follows:
loop
update clock to time of next event;
execute the action(s) associated with this event,
to update the system state;
end loop;
As we get into more detail in the design of the simulation, we have to make a choice. One approach is to simulate every tick of the clock explicitly, as follows:
loop
now := now + 1;
execute the action(s) associated with this clock tick;
end loop;
In an object-oriented simulation, we might have several different software objects, that correspond to different conceptual components of the real system being simulated. For example, in a coarse-grained simulation of an compuer system there might be a system clock object, a simulated CPU object, and several simulated disk objects. The simulator loop might look like the following:
loop
clock.increment;
cpu.update;
for disk in disks'range loop
disk.update;
end loop;
end loop;
This tick-by-tick architecture makes a lot of sense if we are doing a detailed simulating a digital computer, where we expect some kind of change in state on every tick of the hardware clock. On the other hand, it does not work very well if we are simulating CPU or disk scheduling in an operating system, where there may be very many clock ticks between significant events.
To simulate systems where the timings of events are sparse and irregular, we can introduce a queue of events, ordered by time of occurrence. The simulator loop then looks like the following:
loop
remove next event from queue, and make it the current event;
now := time of current event;
execute the action(s) associated with the current event;
end loop;
I have provided three examples of discrete events simulations on line. One is written in C, one in C++, and one is written in Ada. The Ada example is most relevant to this course, since it was used to generate the graphs that are included in the paper "Aperiodic Servers in A Deadline Environment" ( http://www.cs.fsu.edu/~baker/papers/dss.pdf). The C and C++ examples are not so directly related. They were produced for use in an undergrade course on operating systems.
|
© 2003 T. P. Baker.
No part of this publication may be reproduced, stored in a retrieval system, or
transmitted in any form or by any means without written permission.
$Id |