The Big Lie About the Life of the Mind

Earlier this year Thomas Benton wrote an essay The Big Lie About the ‘Life of the Mind, skewering academic humanities in the United States. His thesis is that there is effectively a conspiracy to produce many more PhDs than there are faculty slots, and to keep the carrot of the tenure-track faculty position just out of reach so that graduate students and PhDs will work for little or no money and without job security.

Is there a Big Lie? A conspiracy? The conspiracy angle doesn’t ring true for me; rather, it’s a flawed system. But really, it doesn’t seem so difficult to be more or less completely honest with students about the realities of academic life, though undoubtedly this is easier in a field like mine where PhDs who fail to get faculty positions still have bright job prospects. Although a professor’s ethical position can be a bit complicated — requiring a balance of loyalty between the students, the institution, and the field — simple human decency seems to demand that students get straightforward advice when they need it.

An ethical conflict that comes up fairly often is when an undergrad asks whether she should go to grad school somewhere else, or stay at her current institution. The accepted wisdom, at least as I learned it, is that a student in this situation is always encouraged to leave. Not all professors agree, and also some who agree in principle are perfectly willing to bend the rule in practice to keep a talented student on the local team. Of course the situation can get genuinely murky when a student has good reasons — family or whatever — to stay local. Other examples where people differ: when an undergrad asks if he should go to grad school, or if a PhD student asks if she should pursue a faculty position. Many profs reflexively answer “yes” to both questions, but it would seem that a more nuanced view is called for. Would this person really benefit from an advanced degree? Would it give her a happier and more productive life than she’d otherwise have? I’ve actually caught a bit of flak from colleagues for creating a “should you go to grad school?” talk that doesn’t portray the PhD program in a sufficiently positive light.

In terms of advice for students, you first must find people you can trust and get their advice. In my experience most faculty will not lie to a student’s face about their prospects. If you’re exceptionally unlucky and find yourself in some sort of den of liars, use the Internet. Second, you have spent the last N years learning to think critically (if not, you’re sort of screwed); use this ability to answer some important questions:

  • Are you smarter and harder-working than the average grad student in your field? It’s no fun to be below average. Related question: Would you rather be in the dumbest, laziest 20% at MIT or the smartest, most diligent 20% at a lower-ranked school? (Not trying to be snooty here — I didn’t apply to MIT and wouldn’t have gotten in if I had.)
  • Are people in your field getting the jobs they want? It should be possible to find data, not just anecdotes.
  • If you were highly successful in grad school, would that lead to a life that you want?
  • If grad school doesn’t go well for you, are you going to be really mad that you wasted a few years?

A bit of economic thinking can go far towards understanding the lay of the land. Is your field expanding, contracting, or staying the same size? A non-expanding field makes it extremely tough to get a tenure-track faculty position since a slot only appears when someone retires. What are the magnitudes of the various sources of money (state salaries, government grants, tuition, etc.)? What are the magnitudes of the various money sinks (faculty / postdoc / staff salaries, student stipends, etc.)?

In summary, I’d like to think there is no Big Lie about academia, although there may well be plenty of little lies and white lies. Combat this by not being a Pollyanna. Being a professor is a pretty good job and all good jobs have significant barriers to entry. Find people you trust, ask them hard questions, and think hard about the answers. If you don’t like the answers or if things smell fishy, there’s probably a reason.

[The Truth About the Life of the Mind is a loose followup to this piece.]

Why Take an Embedded Systems Course?

Embedded systems are special-purpose computers that users don’t think of as computers. Examples include cell phones, traffic light controllers, and programmable thermostats. In earlier posts I argued why any computer scientist should take a compilers course and an operating systems course. These were easy arguments to make since these areas are core CS: all graduates are expected to understand them. Embedded systems, on the other hand, often get little respect from mainstream computer scientists. So why should you take a course on them?

Most Computers are Embedded

Around 99% of all processors manufactured go into embedded systems.  In 2007 alone, 2.9 billion chips based on the ARM processor architecture were manufactured; essentially all of these were used in embedded applications. These processors live in your car, appliances, and toys; they are scattered throughout our buildings; they are critical to efficient operation of the infrastructure providing transportation, water, and power. More and more the world depends on embedded systems; as a technical expert, it’s useful to understand how they work. The market for desktop computers is pretty much saturated; the embedded world is growing and looks to continue to do so as long as people continue to find it valuable to place computation close to the world.

Embedded Programming Can Be Fun and Accessible

Make Magazine has done a fantastic job popularizing embedded systems projects. Lego Mindstorms, Arduinos, and the like are not that expensive and can be used to get a feel for embedded programming.  Controlling the physical world is addictive and fun; head over to Hack A Day and search for “paintball sentry,” I defy any nerd to tell me with a straight face that this stuff is not totally cool. This spring I heard a fantastic talk by Sebastian Thrun about his team’s winning effort in the DARPA Grand Challenge (some of his presentation materials are online).

Embedded is Different

Monitoring and controlling the physical world is very different from other kinds of programming. For example, instead of nice clean discrete inputs, you may find yourself dealing with a stream of noisy accelerometer data. When controlling a motor, your code suddenly has to take the momentum of an actual piece of metal into account; if you’re not careful, you might break the hardware or burn out the driver chip. Similarly, robots live in a bewildering world of noisy, conflicting sensor inputs; they never go quite in a straight line or return to the angle they started at. Solving all of these problems requires robust methods that are very different from the algorithmically-flavored problems we often solve in CS.

Embedded Makes You Solve Hard Problems

Difficult embedded programming problems force you to create highly reliable systems on constrained platforms. The software is concurrent (often using both interrupts and threads), must respect timing constraints from hardware devices and from the outside world, and must gracefully deal with a variety of error conditions. In summary, many of the hardest programming problems are encountered all at once.

Debugging facilities may be lacking. In the worst case, even the humble printf() is not available and you’ll be debugging using a logic analyzer and perhaps some LEDs. It brings me joy every year to sit a collection of CS students down in a lab full of logic analyzers; at first most of them are greatly confused, but by the end of the semester people are addicted to (or at least accustomed to) the ability to look at a real waveform or measure a pulse that lasts well under a microsecond.

Modern high-level programming environments are great, but they provide an awful lot of insulation from the kinds of bare-metal details that embedded programmers deal with all the time. People like me who learned to program during the 1980s have a reasonable intuition for what you can accomplish in 1 KB of RAM. On the other hand, programmers raised on Java do not. I’ve helped students working on a research project in sensor networks where their program didn’t work because it allocated more than a thousand times more RAM than was available on the platform they were trying to run on. Many years ago I spent far too long debugging problems that came from calling a printf() variant that allocated about 8 KB of stack memory from a thread that had 4 KB of stack.

All of these difficulties can be surmounted through careful design, careful implementation, and other techniques. By learning these things, students acquire valuable skills and thought processes that can also be applied to everyday programming.

Embedded is in Demand

I don’t have good data supporting this, but anecdotally the kind of student who does well in an embedded systems course is in high demand. A lot of CS graduates understand only software; a lot of EE and ME graduates can’t program their way out of a paper bag. Students who combine these skill sets — regardless of what department gives them a degree — are really valuable.

An Epidemic of Rat Farming

In Hanoi, as the story goes, the French placed a bounty on rat pelts. The locals responded by farming rats. A child who gets candy for cleaning up a big mess is likely to create another mess the next day. These are perverse incentives: incentives that have unintended and often undesirable side effects. As a particularly stupid example, I recently decided to start putting only one sugar cube in my morning coffee and then caught myself pouring small cups of coffee and having two or three.

Once we see the pattern it should be easy to predict when happens when you reward professors, postdocs, and grad students for producing many publications. The rewards are significant: a long CV can get a candidate in the door for a job interview or permit an assistant professor to keep her job during a tenure evaluation. Obviously numbers aren’t everything, but they matter a lot.

It’s true: there is a large number of low-quality publications being produced. I end up reviewing maybe 100 papers per year, and quite a few of them are just bad (I won’t try to define “bad” here but I took a stab at this earlier). I make an effort to be selective about the things that I review, turning down many requests to review journal papers and a few invitations to be on program committees each year.

The recent Chronicle article We Must Stop the Avalanche of Low-Quality Research says that the main costs of the avalanche are increasing the reviewing load, raising the bar for younger researchers, encouraging shallow inquiry, creating a difficult-to-surf ocean of results, and hurting the environment. There’s some truth to all of these, but I’m not sure they represent the main costs. For one thing, the peer review system is fairly effective at weeding out the bad stuff, and it is continuously improving as we adapt to the increasing paper load. For example, many conferences now have multiple rounds of reviewing to avoid wasting reviewer time on the worst submissions. As for the ocean of results, it is effectively tamed by Google. Suresh makes some similar points in his recent blog post where he equates the paper flood with spam email. It’s not a terrible analogy but it makes it easy to overlook some the true costs of the perverse inventive to maximize publications.

It isn’t the flood of bad research that’s the problem, it’s the secondary effects of this flood. First, promising young academics learn and propagate a misleading view of the research process, reducing the likelihood that the high-value, high-impact, once-a-decade results will be produced. To become and remain competitive, talented researchers waste time on short-term results and on spreading results across multiple papers in order to avoid exceeding the LPU by much. Bad research isn’t free: it is produced using grant money, which comes from taxes paid by hardworking citizens. Not only is it unethical to waste this resource, but waste has a high opportunity cost because it prevents useful work from being funded.

Fixing the problem is not so easy because the incentives are hard to change. The fixes offered by the Chronicle article are quite unconvincing when applied to my field. My read of the situation in CS is that little fixing is needed at the top-tier schools: a prolific publisher of worthless results is unlikely to be hired or tenured there. (This is one of the many reasons why the top schools tend to stay there.) On the other hand, the incidence of highly quantitative evaluation of faculty in the next few tiers — schools ranked 5-75, maybe — is significant and troubling.

One of the lessons from Michael Lewis’s fantastic book Moneyball is that if almost everyone is using broken metrics, there’s a tremendous opportunity to scoop up players who are undervalued by these metrics. This is exactly what forward-thinking, non-top-tier research departments should be doing at hiring time. The problem is that identifying these candidates and pushing them through internal hiring barriers is hard work. My guess is that departments who do this will win big in the long run; it is simply inconceivable that a focused practice of hiring paper machines will be a long-term advantage. You can fool the university, the tenure committee, and the awards committee at your favorite conference, but you cannot fool the larger ecosystem where significant research results are those that change how people think about the world, or spawn billion-dollar industries.

Extra credit question: What happens if the amount of grant money a professor earns becomes as important as her publishing record for purposes of tenure, raises, and internal prestige?

Self-Checking Projects

Matching students up with research projects is entertaining but difficult. The project has to be at the right level of difficulty, has to fit the student’s time frame, and has to interest the student. If grant money is going to be used to pay the student, the work has to fit into the funded project. This is all pretty basic, but slowly I’ve come to recognize a less obvious criterion that can make the difference between success and failure. Some projects have the property of being self-checking: a student can easily, on her own, check whether the implementation parts of the project are correct. For example:

  • If a tool that is supposed to find bugs in other programs finds some real bugs, we know that it works, at least to some extent (we can determine if a reported bug is real by inspection). If the tool fails to find real bugs, we can always fall back to seeding software with deliberate errors and try to find them.
  • A compiler is highly self-checking because we can ask it to compile large existing programs and see if the resulting executables work as expected.

On the other hand:

  • Projects whose top-level result is numerical tend to be very hard to check. I once heard a horror story from a professor who had published a paper based on a student’s work showing that his new algorithm performed much better than the previous best one. Unfortunately, the paper was totally wrong: the student had made an error while implementing the competing algorithm, hurting its performance considerably.
  • A formal program verification project is not self-checking because it’s very easy to accidentally prove the wrong properties, or even vacuous properties.

Of course, not all projects need to be self-checking. It’s just that those that aren’t require significant extra attention from the advisor. Additionally, there are some students who will just fail to make progress on a project that isn’t self-checking. It is not exactly the weakest students who do this, but students who somehow lack a strong innate sense of technical right and wrong. In summary, it is useful to ask whether a research project is self checking, and to use the answer to this question to help decide whether the project is a good match for a particular student.

The self-checking principle can be applied to undergraduate education. A course I taught several years ago came with automated test suites that permitted students to determine their score for each homework assignment before turning it in. This approach makes students happy and it is a good match for very difficult assignments that people would otherwise fail to complete. However, when designing a course myself, I have tended to create easier assignments that are not self-checking based on the idea that this encourages students to ask themselves whether they’ve done the right thing–an important skill that is unfortunately somewhat under-developed in CS undergraduates. The weaker half of the students hate this, but it builds character.

White Baldy

White Baldy, on the ridge between the Red Pine and White Pine drainages of Little Cottonwood Canyon in Utah’s Wasatch Range, is an infrequently visited 11,000′ mountain with no really easy routes: its east, west, and north ridges are all messes of bus-sized boulders. Bill and I decided that if we were ever going to climb this mountain, it would be via a snow climb of its broad north face. This face could be a fun scramble in summer, but getting to it would necessitate an hours-long session of boulder hopping in upper Red Pine. Better to just walk on top of it all.

On June 21 we hiked not-speedily to Red Pine Lake, one of the prettiest locations in the Wasatch. The snow was very firm and the small patch of open water on the lake had accumulated a skin of ice overnight. We had good walking to Red Pine’s highest bowl at around 10,200′ and from there the climbing began. The problem with this north face is that it doesn’t have any really pleasant couloirs; as the slope became steeper, there were always sharp rocks sticking out of the snow below us–not so fun to imagine falling into them. As the angle crept past 30 degrees we started running into patches of icy crust where my light mountaineering boots were failing to kick very good steps. With about 600′ to go we chickened out and turned around; putting on crampons (which we hadn’t brought) or waiting an hour for the snow to soften would have also been solutions, but neither of us was super invested in summiting.

We traversed over to the west ridge, stopping to do a bit of self-arrest practice along the way, including a few of the always-frightening backwards / headfirst falls. I hadn’t practiced stopping fast slides for a few years so this was good review. We had lunch looking into American Fork Canyon. It was a great day: sunny and warm in the lee of a boulder, but surprisingly cold in the wind–my hands started to get numb while I was taking pictures. On the way down the snow was getting sloppy but the partially broken-down snow bridge over the Red Pine stream held up fine. Overall, it was an excellent spring snow climb.

Here’s a 360° panorama with White Baldy in the middle.

[nggallery id=22]

INT_MIN % -1 = ?

If you spend much time testing compilers, you’ll run into some strange phenomena even in apparently simple areas like computer arithmetic. For example John Cook wrote a post today explaining why IEEE floats have two different values of zero. Integer arithmetic is generally a lot simpler than floating point math, but it still contains a few surprises. Today we’ll ask the question: What is the value of the C99 expression (INT_MIN % -1)?  Or to put it in English, what is the remainder when the smallest integer value is divided by negative one?

Mathematically speaking, it should be obvious that the result is 0 because any integer divided by -1 or 1 leaves no remainder. Looking at section 6.5.5 p5 of the C99 standard (I’m using N1124) we find:

The result of the / operator is the quotient from the division of the first operand by the second; the result of the % operator is the remainder. In both operations, if the value of the second operand is zero, the behavior is undefined.

There are no surprises here. Perhaps the only interesting thing is that (in keeping with C’s design) dividing by zero results in undefined behavior instead of causing a math exception to fire.

Next let’s look at the behavior of some C implementations.  Given this source code:

int my_mod (int x, int y)
{
  return x % y;
}

the current version of GCC for x86 gives this assembly code:

my_mod:
  movl    4(%esp), %eax
  movl    %eax, %edx
  sarl    $31, %edx
  idivl   8(%esp)
  movl    %edx, %eax
  ret

The other x86 compilers that I tried (Intel, Sun, more versions of GCC, LLVM, Microsoft VC) generate more or less the same code. At first glance it looks good: the x86 idiv instruction leaves the quotient in EAX and the remainder in EDX. The sar instruction is a right-shift that implements a sign-extend.

But there’s a small problem: when we compute INT_MIN % -1, the quotient is -INT_MIN which is not representable in a standard 2’s complement integer (recall that INT_MIN is commonly defined as -INT_MAX-1). In this case the idiv instruction does not compute the result but rather throws an exception. Thus, despite the fact that the remainder is representable in an integer, and despite the fact that the C standard says what to do here, we’ll end up with a processor exception that probably kills the program.

If computing (INT_MIN % -1) reliably resulted in a processor exception, it wouldn’t be that bad. However, the behavior is not reliable. For example, when GCC can show that the arguments to the expression are constant, it folds the expression into the expected zero result. In effect, this is a new kind of undefined behavior (LLVM explicitly gives undefined semantics to this case).

The real problem here is that the C standard has specified a semantics for the % operator that doesn’t have a fast implementation on common instruction set architectures. C people really hate it when their language does anything slowly. So this is basically a flaw in the standard that should be fixed — I’ve heard that C1X will do exactly that.

I should point out that not everyone agrees that the C standard requires INT_MIN % -1 to evaluate to 0. Section 6.5.5 p6 it says:

When integers are divided, the result of the / operator is the algebraic quotient with any fractional part discarded. If the quotient a/b is representable, the expression (a/b)*b + a%b shall equal a.

Some people read this as saying “if / has an undefined result, then % does also.” The more common reading is “if the quotient is representable, this equality holds, but the definition of % is unaffected.”

Why Take a Compiler Course?

[Also see why take an OS course and why take an embedded systems course.]

All good computer science departments offer a compilers course, but relatively few make it a required part of the undergraduate curriculum. This post answers the question: Why should you take this course, even if you never plan on writing a compiler?

One of the reasons I’m writing this post is that although I enjoyed the compilers class I took as an undergrad, I had a hard time seeing the practical use. Most of the material seemed either obvious or esoteric. (As a matter of fact there are still wide areas of the compilers literature that I find totally uninteresting.) Anyway, it took several years before I pieced together the actual reasons why this kind of course is broadly useful. Here they are.

Parsers and Interpreters are Everywhere

Serious programmers have to understand parsers and interpreters because we end up writing little ones all the time. Every time you make a program extensible or deal with a new kind of input file, you’re doing these things. The extreme version of this claim is Greenspun’s 10th law:

Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.

Given that we spend so much time writing these things, we can either do each one in one-off, hacky way, or we can bring 60 years of theoretical and practical knowledge to bear on the problem, and do it right. The important things to know are: When should you borrow existing code or use an existing tool? When does the theory have something to offer? What principles of language design can be brought to bear on our daily little languages?

You’ll Be Better Able to Write Correct Code

A compiler is supposed to correctly translate every valid program in its input language. To meet this goal the compiler developers must understand the entire input language including corner cases never seen by normal programmers. This understanding is an important step towards seeing programming languages are they really are, as opposed to seeing them as they are usually written. For example, my understanding of the C language changed entirely after I learned the details of sequence points, undefined behaviors, and the usual arithmetic conversions. These concepts are second nature to C compiler writers, but largely unknown to beginning and intermediate programmers. It’s not an exaggeration to say that you’ll think about a language quite differently, and a lot more accurately, once you see how the sausage is made. This applies to any programming language, but particularly to the more semantically unclean ones like C and C++.

You’ll Be Able to Write Faster Code

By understanding a compiler, you’ll end up with a very clear idea about which optimizations are in-scope for a compiler, and also which ones they cannot do, no matter how plausible and simple they seem. You’ll learn what kinds of code constructs commonly block optimization, why this happens, and what to do about it. You’ll learn why some of the world’s most excellent optimizations, such as an FIR filter that uses half of the register file to cache filter coefficients and half of the register file to cache samples, are unlikely to be implemented by any general-purpose optimizer. You and your favorite compiler are a team working together to create fast code; you can cooperate with it in an effective way, or you can fight against it with premature optimization and other silly tricks.

Second, compiler backends are intimately connected to their target architectures, and of course modern architectures are not remotely intended to be friendly targets for human assembly language programmers. By understanding a compiler backend and why it generates the code that it does, you’ll arrive at a better operational understanding of computer architectures.

Summary

Compilers (ideally) have three parts:

  • language-dependent frontend (parsing, type-checking)
  • language and target independent middle end (optimization)
  • target-dependent backend (code generation)

In this post I’ve tried to argue that understanding each of these parts has value — even if you’ll never implement or modify them.

Good Fun and Bad Weather on Mount Baker

The problem posed by this trip was to find a route that was interesting for my hiking buddy Bill while still being feasible for me. Bill is a seasoned mountaineer and has done some difficult climbs. I’m a strong hiker and feel comfortable on moderate snow slopes, but I haven’t done any technical mountaineering. Technical, in this case, means roped up in order to gain safety on glaciers and on steep snow or ice where a self-arrest is unlikely to succeed.

Our solution was to spend six days on Mount Baker with a guide. During the early part of the trip I’d get brought up to speed on roped travel, crevasse rescue, etc. and then we’d attempt the Park Glacier Headwall: an interesting, moderately technical route to the summit. The 2009/2010 winter ended up not bringing a lot of snow, so we felt comfortable scheduling a trip in May, on the early side of the season.  However, the spring turned ugly and a lot of snow was dumped on the northwest. Going into this trip we knew the forecast was poor for the whole week and we’d be lucky to get anything done.

On Saturday May 15, Bill and I traveled up Bellingham, WA. Sunday we woke up early and headed over to the AAI offices where we met Jason Martin, our guide. After a bit of gear sorting and renting me some plastic boots, we headed up to Baker’s Heliotrope Ridge trailhead. It was great driving through the dense forest: living in Utah one gets used to the desert and it’s nice to see so much green.

The hike up to “Mirkwood,” a sheltered campsite at around 5200′ on a moraine overlooking the lower Coleman Glacier, was a bit grim since my pack was overloaded. It’s hard to be light when carrying six days of food, a full set of climbing gear including two ice axes, and plenty of cold-weather clothes. Also Bill and I weren’t that interested in sharing a tent so we each had one of those to carry. I was delighted to discover that hiking in plastic mountain boots is not at all uncomfortable. Over the course of this trip I learned to love these boots, although keeping the insides dry in the rain and wet snow was a challenge.

Setting up tents on snow is quick and easy. After settling in we did a bit of snow review: self arrest, anchor-building, etc. I built a snow bollard and then, simulating a fall, pulled the rope right through it, yikes. After a while it started raining hard enough that these activities stopped being fun. After dinner the weather cleared up a bit and I started feeling enclosed by the big trees, but just a 15-minute hike up the moraine the trees petered out and a quick scramble got me onto a nice rock pinnacle where I had a great view of the mountains in BC and a gorgeous sunset.

Ugh, should have brought a bigger pack!

Monday the weather was beautiful, though Baker’s summit had an ominous cloud cap. We decided to spend the morning doing glacier skills and then head up to a high camp, make a snow cave, and attempt the Park Glacier headwall on Tuesday if the weather held.  I was a little nervous about this since we skipped over the crevasse rescue stuff and, in fact, on the way up to the high camp both Bill and Jason put legs into hidden crevasses. It is a little scary walking past a hole in the snow that has been produced in this manner because it is 100% clear that a serious crevasse is lurking right there, and there’s no easy way to tell exactly where it is or if the rest of the snow bridge will hold.

Our high camp was at 7700′ on the next ridge east of Baker’s North Ridge.  The hike was long and fairly warm and really quite tiring due to poor snow conditions, like walking in mashed potatoes. Bill and I volunteered to break trail but perhaps not very convincingly since Jason took the lead the whole way. As soon as we stopped walking the wind picked up and it got cold. We immediately started work on the snow cave a bit down from the ridge crest, but above the glacier. This cave (I’d never dug one before) turned out to be a very large amount of work: just below the surface snow was some great structural snow with about the consistency of sheetrock. We traded off often and made progress slowly, eventually deciding that we didn’t need to fit our entire bodies into the cave; if it rained we’d sit out the rest of the night leaning against the back wall. The flaw in this plan was that a serious drip developed along the interface between the sloppy surface snow and the hard snow beneath. We didn’t manage to eliminate it, nor did it stop as the night became colder. So we slept with our bivy bags getting dripped on, not the end of the world but not that great.  We set alarms for 2am.

At 2:00 the sky was not clear and the snow had not come close to freezing. We decided to bail on this summit attempt. This turned out to be the right decision; we’d not have summited in any case, and descending might have been pretty adventurous depending on where we were when the weather turned. We woke again at 7 and headed back down to Mirkwood in a whiteout. The cloud cover felt shallow and while we couldn’t see much of anything, the solar radiation was burning hot. We got back to camp around lunchtime and napped for a while, during which time a nice cold rain began. At this point the floor of my tent was very wet due to condensation. I’m not sure how to avoid this when camping on snow in humid weather, perhaps a footprint made out of very thin foam?

Wednesday it was gorgeous in the morning, but again with a cloud cap over the summit. We did a full-on crevasse rescue practice, my first one. First we found a nice crevasse and probed an area near it so that we could move around without ropes. Next, Bill and I roped up for glacier travel and he jumped into the crevasse! This took a bit of convincing, it was not very fun for him. However, Jason had him belayed on a second rope so that we wouldn’t both end up at the bottom of the crevasse if I failed to stop his fall or if my anchor blew. Here’s a short video Jason took of this. After I self-arrested, we went through the entire drill which is pretty involved, Jason has a great blog post giving the details. Extracting Bill took perhaps 45 minutes of hard work, here’s me working a C on Z pulley system. When it was my turn in the crevasse, Jason lowered me; I was perfectly happy not to jump in. Being inside the glacier was pretty cool: it was drippy and there were lots of moving-ice noises that couldn’t be heard on the surface. Bill’s rotator cuff problems made him less than excited about operating a pulley system so I got to prusik out, which is actually quick and easy except for getting over the crevasse lip.

In the afternoon we found a serac with perhaps 40′ of vertical ice to climb on, another thing I hadn’t done before. It was fun: in this glacier ice you can plant a tool just about anywhere and it sticks. My first time up, I had trouble and it turned out I was doing only two things wrong: placing my feet and placing my ice tools. But both were easy to fix. First, when Jason said to use four crampon points I thought he meant two on each foot, not four on each foot. By drooping my heels some, I was able to use all four front points, making things greatly easier. The problem with my ice tools is they are quite mismatched: a sweet little 50cm Petzl Aztar hammer in one hand and my beat-up, off-brand 70cm mountaineering axe in the other. The longer, heavier tool was tough to swing properly and I did a lot better once I borrowed Bill’s matched tools. Bill zipped right up the slope and I did OK after a few practice runs. Perhaps the most fun part was climbing a slightly less steep ice slope (probably 80 degrees) with just one axe.

By mid-afternoon it was raining and we retired to camp. We had dinner in the cold rain and later it started storming properly. Luckily the Mirkwood camp is sheltered, but even so we had at least 30 mph gusts, not friendly for my slightly crappy 3-season tent which is sort of a wind tunnel due to having too much mesh and a very open fly design. Tent stakes setup as deadmen and frozen into snow are impossible to dislodge, my main worry was the fabric ripping. Eventually the rain turned to sleet and then snow. I was pretty cold but felt fine after getting into my bivy bag inside my tent.

Thursday morning the weather was good but basically all of our gear including boots and sleeping bags was soaked from days of humidity and rain. Our harnesses and packs had frozen stiff overnight. The forecast remained crappy.  We decided to bail from Baker and do some rock climbing near Bellingham. The hike out was beautiful and sunny at first, but by the time we got to the car it was blowing snow again, and we were glad to get out.

We headed to Mt Erie near Anacortes, a beautiful spot. The forecast was still for rain but we had a great afternoon. Baker, we noticed, was shrouded in ugly dark clouds. I’m not a rock climber at all but struggled my way up some pitches in the 5.4 to 5.6 range. 5.8 appears out of reach for now. We spent Thursday night at the Deception Pass campground, located in a gorgeous temperate rain forest.

Friday we did more cragging and a gear sort at AAI in late afternoon. Bill and I checked into our motel and I used basically every available surface for drying gear. Beers and dinner went down well.

Overall, we had a great trip. At least part of each day had decent weather and neither Bill nor I was hugely invested in reaching the summit. We got to do lots of mountaineering stuff that can’t be done in Utah (no glaciers here). Jason turned out to be a really interesting guy and was fun to spend a week with; he’s the guide manager at AAI and also writes plays and screenplays, and previously was a high school drama teacher.

All photos © Jason Martin, William B. Thompson, or John Regehr 2010.

Why Take an Operating Systems Course?

[Also see why take a compilers course and why take an embedded systems course.]

The other day, while having coffee with a colleague, I mentioned that I’ll be teaching OS in the fall. His area is far from computer systems and he asked me what’s the point of this class? What are the students supposed to get out of it? These are fair questions and I think I had reasonable answers. Here I’ll elaborate a bit; let me know if I missed anything major.

The last time I taught OS, in 2002, it was still a required course at Utah and got about 80 students. It is no longer required, having been subsumed by a great class based on the O’Hallaron and Bryant book. Even so, there are already 50 people signed up for the Fall semester offering, which seems pretty reasonable. The course is split into two sections: an advanced undergrad course and an introductory/remedial graduate student class. This is not my favorite arrangement but it’s not a big deal.

Probably I should mention that an OS course that involved a ton of Minix hacking was what got me interested in computer science. Previously, I had been sort of tolerating CS classes but hadn’t found much that was challenging or interesting.

Using a simple case analysis we can deduce that the point of an OS course is not to teach students how to write their own OS. First, there are some students interested in and capable of writing an OS. They do not need to see that material in class, they’re perfectly capable of picking it up on their own. Second, we have students incapable of or uninterested in implementing a new OS. They do not need that material either.

So what is the point?

Concurrency

Writing concurrent code is not easy, especially using threads with shared memory and locks. However, a large number of current CS students will do this at some point in their careers. There is a growing trend to address concurrency at points in the curriculum outside of an OS course, but even so this is traditionally the place where students get their first serious introduction to threads, races, deadlocks, and all that. The material is hard (actually the material is easy, but applying it is hard) and it would be useful to see it several times before graduating. A solid introduction to concurrent programming is a major benefit of taking an OS course.

Resource Management

At the hardware level resources are typically dedicated. An OS provides versions of these resources that are either virtualized (each user gets the illusion of having a copy of the resource) or arbitrated (one user at a time, but with queuing handled by the OS). The strategies used to give multiple users access to a dedicated physical resource are fundamental and are also used in many user-level programs. By studying these issues explicitly, students learn patterns that can be reused in many other contexts.

Performance Analysis and Contention Resolution

Also known as “why the #*$ is my machine paging?” When resources are shared, contention typically follows. Contention can be resolved in many ways, for example using queuing, fair sharing, or prioritization. In some cases, such as CPU scheduling, no single technique suffices and the best known solutions are bizarre hybrids. Often, the most interesting problem is in figuring out what kind of contention is the root cause of some observable problem. I spent a good part of a summer one time figuring out all the ways that Windows NT would cause an MP3 to skip. An OS is a perfect context for learning these ideas, whose applicability is much broader than computer science.

Interfaces and Hiding Complexity

A well-designed interface is a beautiful thing. It is even more beautiful to fully appreciate what it takes to transform a nasty, low-level interface (a modem or NE2000 card) into a usable and efficient high-level abstraction (a stream socket). While students should have been exposed to these ideas in course material about abstract data types, the examples given there are often pretty trivial and the full power of abstraction and complexity hiding is not necessarily apparent at that level. I consider the ability to put a collection of useful abstractions like sockets, file systems, and address spaces into a single, convenient package to be probably one of the top 10 overall contributions of computer science.  This is so commonplace that it’s easy to overlook the real awesomeness.

No Magic Here

From user mode, it’s easy to view the OS as a magical force that is both good — giving us smooth multitasking, efficient storage management, etc. — and evil — giving us blue screens, thrashing, security problems, and scheduling anomalies. This view is fine for the general public. On the other hand, if you plan to tell people you’re a computer scientist, you need to have peeked behind this curtain. What will you find there? Too often it seems like sort of a sad collection of mundane linked lists, dodgy resource heuristics, and ill-maintained device drivers. A good OS course should show students that:

  • There is great code in the kernel, you just have to know where to look. When you first see it, you will not understand it. But when you understand it, your mind will expand a little bit.
  • Mostly, kernel code is perfectly mundane. Anyone can write it, it just takes a bit more care and attention to detail than user-mode code because the consequences of a bug are greater.

Dealing with Big Software

There is no doubt about it: being dropped into the middle of somebody else’s multi-million line code base is a nightmare. Documentation is incorrect and scattered, interfaces are klunky and wide, interactions are subtle, and error messages inscrutable. But welcome to real life, folks: we can’t usually just start over due to problems like these. As a student, if you can begin to develop a systematic approach to learning the relevant parts of a big piece of software that your code has to fit in with, your life will be a lot easier later on. You can hate the Linux kernel but it’s far better software than other stuff you’ll run into during your career.

Computer System Design

Designing any engineered system, including a software system, is an exercise in compromise. How much emphasis is placed on reliability? Performance? Cost? Maintainability? Since operating systems are large, performance-critical programs that tend to last for decades, they are a great place to learn about these kinds of tradeoffs. Students who develop a sharp eye for finding an appropriate design point are incredibly useful in industry. This stuff is more of an art than a science, you need to look at a lot of code, understand the issues, and learn to think about this stuff for yourself.

Summary

I have tried to make it clear that an OS course isn’t just about operating systems and its purpose goes well beyond giving ammunition to the UNIX / Windows / MacOS partisans. A well-taught OS course gives you skills and ways to think about computer systems that are broadly applicable even if you never touch a line of kernel code. Disregarding the fact that a CS degree at my university does not require an OS course, my opinion is that all real computer scientists either have taken this course or have picked up the equivalent skills and knowledge in some other way.

Flower Power

The Wasatch Range peaks are 7000′ higher than the nearby Salt Lake Valley. This has many nice side effects but one of my favorites is that a wide variety of micro-climates is available within a small geographical region. In late Fall or early Spring it can be calmly drizzling in the city, but in the mountains it’s storming like the Himalayas. Before having kids I’d often get up around 5am in July and August to go for a hike. Even on days that are going to be over 100 degrees in the valley, it’s generally pretty chilly at 8000′ at that time of day.

This week the foothills near my house have the most flowers in the 6000′ to 7000′ range. Below this things are starting to dry out; higher up, the snow has only recently melted and buds are still trying to open. As the summer progresses, the band where flowers are found will slowly increase in elevation. The nice thing about this arrangement is that for about four months of the year, there’s somewhere within about a 45 minute drive that has wildflowers at their peak. The density of flowers in the foothills doesn’t approach the wall-to-wall color seen in some of the real alpine meadows, but some of these photos came out pretty well.

[nggallery id=14]