Final exams, part 2: Operating Systems

I've finished the final exam for my Operating Systems class, and I must say, I'm glad to see the end of it. It wasn't a particularly difficult class -- while I probably got my lowest grade in this class, I would describe it as almost comically easy by engineering standards. The problem is that the class was poorly taught and I already knew most of the material in more detail than we were ever given.

I'll tell you an example: filesystems. A hard drive can be thought of as a bunch of blocks of data, and each block can be read sequentially. It can fetch any block for you, but switching to another block is much slower than sequential reading within a block. And since these blocks are small, we need to work out how to divide up files among them. It's as if you had a blackboard divided into small squares, and you needed to compose several essays on this blackboard. How do you use the little squares?

You could just start in the upper-left corner of the blackboard and use each square in order, and write down your essays. This is called contiguous allocation. It has problems, of course. What if you need to add something to the beginning or end of an essay? Maybe there will be extra space at the beginning or end; no such luck if you want to add a paragraph in the middle, and you have to recopy a bunch of words from one block to another -- in the worst case, you might even end up rewriting everything on the whole blackboard just to add a single word.

You could give each block a number and write the number of the next block on it. Then when you want to go to the next part of the essay you can just look to see the number of the next block, and go there. And so on: just follow the chain. This is called linked allocation. It makes adding paragraphs and such much easier: just change a few numbers around and add a new block to the chain. The same goes for deleting data. Finding an arbitrary place in your essays can be a little tricky, though: you have to follow a bunch of links, and each jump from block to block takes time.

Another strategy is to write the order of blocks on its own block -- a table of contents, if you will. This is called indexed allocation, and it's the most practical system of the lot. There are still issues with this, and they can be made faster by using something called a B+ tree. But we never got to that -- we spent too much time obsessing over minute details of broken implementations of things like linked indexing. I'm not kidding.

And if you ever asked a question, you would get an unrelated answer. Always.

So, as I said before, I'm very happy that this class is no longer a part of my life.