Operating Systems Spring 2011
Exercise 1: The Cost of Trap
Man is the only kind of varmint who sets his own trap, baits it, then steps in it. John Steinbeck, Sweet Thursday
Due Date: 3.3.2011
Before you start, don't forget to read the
course guidelines!
Background
Operating system code runs in "kernel mode", in which the full range of instructions of the architecture is allowed by the CPU. This includes many privileged instructions that are used to control the hardware, and must not be used by normal user code. Therefore, changing execution mode from "user mode" to "kernel mode" so that the operating system can run is not trivial. This operation is called a "trap", and it occurs at the beginning of each system call. In this exercise we will
measure the overhead involved in executing a trap.
Assignment
Your assignment is to build a library called osm that provides functions to measure the time it takes to perform three different operations: a simple instruction (such as addition or bitwise and), an empty function call with no arguments, and a trap. It also provides a function which returns a struct containing all the data we are interested in (see below). The header file for the library is osm.h - it includes the struct definition, and you should implement all its functions.
To measure the time it takes to perform an operation, you should use the function gettimeofday (run man gettimeofday for how to use it). Since any single operation takes a very short time, you will need to measure each operation over many iterations done in a loop, and calculate
the average time the operation took (notice that one may run the program on 31/12/2011, 23:59:59 - to commemorate the year - and your program should work in this case as well). The number of iterations is fed as input to the library initialization function osm_init.
To measure the time it takes to perform a trap, we have provided you with an empty system call, called 'OSM_NULLSYSCALL', which traps into the operating system but does nothing. It is defined in the library header file. Be aware that this call works on CS labs computers (and "river", for connecting from outside), but it may not work on other versions of Unix-based 64-bit operating systems.
To measure the time it takes to run a single instruction, it is advisable that you perform loop unrolling, that is: in every iteration of the loop, run many instructions instead of just one instruction, and divide the time by the total number to get the average. Try to make the individual instructions independent from each other, so as to avoid delays in the processor's pipeline.
The function: timeMeasurmentStructure measureTimes (int numOfIterations) should return a struct containing all the data we are interested in, comparing the various times. The argument denotes the number of loop iterations to perform, and if the argument received isn't valid, the function should default to 50,000 iterations (If you use loop unrolling, it is permissible to round UP the number of iterations to a multiple of the unrolling factor). The struct requires the following data:
- Machine name - check
man 2 gethostname.
- Number of iterations.
- Instruction time - in nano-seconds.
- Function time - in nano-seconds.
- Trap time - in nano-seconds.
- Function/instruction ratio - the respective times divided.
- Trap/instruction ratio - the respective times divided.
Notice that gettimeofday has a resolution of microseconds.
If any calculation had an error, the value of respective struct member should be -1. If there is an error in the machine name, a null string should be the value of the relevant struct member.
Submission
Submit a tar file on-line containing the following:
- A README file. The README should be structured according to
the course
guidelines, and contain an explanation on how and why your library functions
are built the way they are.
- The source files for your implementation of the library.
- Your Makefile. Running make with no arguments should generate the
libosm.a library. You can use
this makefile as an example. Note that it is not
a good idea to compile with optimizations in this exercise (can you see why?).
Do not change the header file. Your exercise should work with our version of osm.h.
Guidelines
- The programming in this exercise is trivial.
But you need to look at the results and think about how to make them
reasonably accurate, and this may take time.
-
How can you tell your measurements are good enough?
It is hard to get exact measurements. Approximate measurements are good enough
for this exercise.
You should check that:
- When you run the measurements several times on the same machine, you get
similar results. Note that machine load can affect measurements.
- The time you measure for a function call should be several times the time
of a single instruction, and the time for a trap is significantly
higher.
- Ideally, the time for a simple operation should be one cycle, and other
times should be a multiple of this.
- Make sure to check the exit status of all the system calls you use.
- Make your code readable (indentation, function names, etc.).