CSE 451: Operating Systems

CSE 451 20au Homework 0


Out: 29 Sep 2020
Due: not due, but not optional

Assignment Goal

One of the goals of the OS is "to be efficient." That already is a somewhat subtle idea. It's hard to write efficient code unless you understand what various operations cost. This assignment asks you to run some code that measures operation times and then to examine the results. The hope is that the experience will give you an intuitive feel for what is expensive and what isn't, as well as what the benefits and challenges of measuring might be.

Complications

The results you get will depend on the machine you use to run the code. They may also vary from run to run on the same machine. If you find the results interesting on one machine, you might try running again on a different one to see if they are even qualitatively simliar. For example, you might run on attu and then on your own machine.

Worse1, some of the results will probably make no sense to you. In my experience, that's almost always what happens when you measure things, and is one of the reasons to do this homework. You think you know how your system is behaving, but when you measure it, it's doing something else.

When measurements don't make sense, it could be that there's a bug in the measurement code and so we're not measuring what we thought we were. It could mean that the thing we're measuring doesn't behave like the simplified mental abstraction we've constructed for it. Figuring out why measurements are what they are is often quite hard. No one is asking you to do that for this homework. (But, who knows, this might be so interesting that you choose to spend some leisure time trying to figure it out...) You most likely will never be sure if the results you see in this assignment are "right" or not.

What to Do

  1. Copy all the files in attu.cs.washington.edu:/cse/courses/cse451/20au/hw0/ to some machine on which you'd like to run the measurements. Any machine with a reasonable C build environment could potentially work. (I've tried only Linux machines, though.)
  2. If you're on a Linux machine, execute this command: less /proc/cpuinfo. Information about the CPU on your system will be printed. That might be useful in understanding results later (but only if you get really interested in this and try to explain the results).
  3. Build the app. There is no build infrastructure provided. gcc *.c doesn't succeed, but comes kind of close. That's intentional. Fix whatever is wrong so you can build the app. (This is a build error, not a program coding error. You don't have to edit any files to fix the issue.)
  4. Run the app. It measures a lot of things, and prints very slightly annotated results.
  5. Look at the code enough to understand what each test is doing. The code is written in a somewhat bizarre, very C-language-y, way. I think you should be able to figure out what is being measured for each test, but it might be a bit of a struggle at first. Details shouldn't be critical -- aim for a general understanding.
  6. What we're actually interested in is relative costs. For example, how much slower is it to call a function that takes 8 arguments compared to calling one that takes no arguments? The answer to that might have some bearing on the function interfaces you design/implement.
    I've provided a .xlsx file that is basically a template for computing relative costs. I created it using LibreOffice on Linux, but my unverified belief is it will work with Excel. If you copy the measurement results into the spreadsheet it will provide relative costs. This is an admittedly tedious process. My apologies.
  7. Look at the relative costs of the operations.
  8. That's it, you're done. Nothing to hand in.

Post-Homework Discussion

The obvious goal of this assignment has to do with operation costs and measurement. There is another goal, though, which is working with things that are incompletely, and perhaps poorly, understood. This assignment is intentionally vague in a lot of ways, for one thing. That's a tiny step into the uncertain if you're used to the polished, detailed assignments we usually like to give in CSE. The code doesn't even build, and I'm not telling you why. (Please don't tell each other why either.)

There will likely be times during the projects that occupy the rest of the quarter when you feel that you don't know what is going on. That's okay. You'll overcome it.

Hey, Is This Even Computer Science?

If you find yourself harboring an uneasy feeling that something is terribly wrong, how can it matter if an operation takes 6 μsec or 24 μsec, it's only a constant factor, you're completely correct, in a way. That a system that runs applications 4 times faster than another is somehow better, though, is completely correct as well.

1 By "worse" I actually mean "Better yet!"