My Faults My Own

…willing to sacrifice something we don't have

for something we won't have, so somebody will someday.

IN WHICH Ross Rheingans-Yoo, a sometimes-poet and erstwhile student of Computer Science and Math, oc­cas­ion­al­ly writes on things of int­erest.

Reading Feed (last update: December 15)

A collection of things that I was glad I read. Views expressed by linked authors are chosen because I think they're interesting, not because I think they're correct, unless indicated otherwise.


(15)

Blog: Marginal Revolution | A social credit system for scientists? — Chinese scientists, that is, and fraudsters at that. What, would you rather be soft on fraud?


(14)

Blog: JeffTK | Taking a Safety Report

Comic: xkcd | arXiv — "...invaluable projects which, if they didn't exist, we would dismiss as obviously ridiculous and unworkable."


(13)

Blog: Thing of Things | Scrupulosity Sequence #3: Load-Bearing Things

Blog: JeffTK | Not losing things — "I almost never lose things, especially important things like my keys, laptop, or ear warmers. Here's an attempt to write up the system I use, in case it's useful to others..."


(12)

Blog: Tyler

READ MORE

[CS161] The Classic CV Error

This is a very technical post, largely for the benefit of the students of CS161: Operating Systems, for which I am a Teaching Fellow this semester. It may be useful to you if you're interested in operating systems for some reason, but if you're not in a CS mood today, maybe just move along.

From what I've seen as a TF for this course, it is very, very normal to write condition-variables code that looks like this:
struct cv {  
    struct semaphore *sem;
    volatile int waiters;
}

void cv_wait(struct cv *cv, struct lock *lock) {  
    KASSERT(lk_do_i_hold(lock));

    cv->waiters++;
    lk_release(lock);
    P(cv->sem);
    lk_acquire(lock);
}

void cv_broadcast(struct cv *cy struct lock *lock) {  
    KASSERT(lk_do_i_hold(lock));

    for (; cv->waiters > 0; cv->waiters--)
        V(cv->sem);
}
This code is wrong (or, more specifically, badly synchronized). And it is such a common error that I'm choosing to dub it The Classic CV Error. It's subject to a race condition in e.g.
READ MORE

[CS161] On Scheduling

This is a very technical post, largely for the benefit of the students of CS161: Operating Systems, for which I am a Teaching Fellow this semester. It may be useful to you if you're interested in operating systems for some reason, but if you're not in a CS mood today, maybe just move along.

Why Do We Schedule, Master Bruce?

A scheduler, as you know, is responsible for determining which threads run, for how long, and in what order. As much as possible, it should give the shared illusion that each process is running constantly to completion, using the entire processor. To this end, there are three major desiderata:

  • That interactive threads (in particular, user-interactive threads) are responsive.
  • That no process starves.
  • That the system, on average, runs quickly.

These high-level desiderata factor into the low-level conditions that:

  • Threads which block expecting a response are rescheduled promptly after waking.
  • Time is allocated more-or-less fairly, subject to:
  • Processes closer to completion are prioritized (recall that shortest-time-to-completion-first is provably optimal in total
READ MORE
1 / 1