Linux semaphores

Re: Schedule idle
Wed, 11 Nov 1998 04:09:32 +0100 (CET)
> _please_ We can do better than this. Only semaphores (not spinlocks) need
> to have the priority inheritance. […]
nope there are _not_ only semaphores, but many other types of locks.
> […] This can be done with lists off the
> semaphore and tasks… […]
it’s _not_ easy to extend Linux semaphores to handle priority inheritance. currently semaphore operations can be done via hw-atomic test-and-set instructions. If we do anything more complex, we cannot use simple instructions anymore. Linux semaphores are 2 instructions for an up() and 2 for a down(), and thats one of our crown jewels 🙂

the whole point is not quite valid, RT and filesystem IO doesnt mix well anyway … the solution: use system calls that are guaranteed to not block, either by design, or by system policy (ie. separate filesystem on a RAMDISK) … or use a device that doesnt introduce large latencies. (RAMdisk or solid state disk)

And then ….


Why Computer Science is a failed field #2

I mentioned the phobia against mere experimentation recently, but now I have some more fascinating glimpses into “peer review”. I have some theoretical work I’m trying to finish up and get published somewhere so someone smart can do something with it. It may be junk or not – that’s why we have “peer review” in science. So I send a paper to LATA as something of a first effort. The reviews were negative. Pravda, well Pravda said: it stinks. Oh wait, that was a Tom Lehrer lyric.

Have I mentioned how happy I am to have found a way of earning a living outside of Academia? In any case, here’s the most annoying of the three reviews:

OVERALL RATING: -2 (reject)

The authors discuss well-known methods for specifying Moore machines.
The referee did not find anything new in this paper.
The general direction of this research seems useful.

Certainly a fair comment and one that is pertinent except for one glaring omission – the citation. Perhaps the paper does repeat material that is well known to the expert reviewer and not the poor author. So where is the “for example, Perrin’s 1995 survey describes the same methods” ? Without a citation, the review has a strong flavor of humbug.  But it’s not just the reviewer who comes into question here. The proceedings editor received this review and did not ask for clarification. If I had not seen similar responses to papers written by other people, perhaps I’d be less skeptical.  But I have been in the position of a conference editor where I asked reviewers for citations – and most of the time, the reviewer was not able to substantiate. Why? Because if the reviewer  can substantiate, if she or he really thinks that the paper covers known material, the natural inclination is to point to the known material. Of course, I complained to the conference program committee chairs and got this response.

PS: At conferences, there is usually no discussion on acceptance /
non-acceptance with the authors.

I’m not sure about “usually”, but often there is discussion.  For example

In author response, also called rebuttal, reviewers enter their reviews, authors read the reviews, enter a response, and then reviewers make their final decisions. The purpose is to provide authors a forum to correct and directly address issues raised in the reviews.”Improving Publication Quality by Reducing Bias with Double-Blind Reviewing and Author Response” Kathryn S McKinley, The University of Texas at Austin ACM SIGPLAN Notices, 43(8):5–9, August 2008.

See, that is known as a “citation”. I made a statement and then made a reference to backing material so that the reader could look it up.  Was that so hard? Going back to the problem with articles on experimental systems, reviewers who find the data unsurprising should be required to point to the literature that provide the same information. “It’s well known” without backup is offensive to the whole scientific process. If it is well known, then point to where it is explained. If not, then be silent.

I gotta add that this is far from the worst quality review I ever received. The all time star, included something like this: “The author fails to understand that while in a set {a,b} [something], if the ordering is different and the set is {b,a} then …”. But I’m just starting to send out papers again, there’s hope that something even more amusing will appear.

[updated with clarification Feb6]

Linux descends into priority inheritance hell

The PI chain walk is implemented by the function rt_mutex_adjust_prio_chain. The implementation has gone through several iterations, and has ended up with what we believe is the best. It walks the PI chain by only grabbing at most two locks at a time, and is very efficient. The rt_mutex_adjust_prio_chain can be used either to boost or lower process priorities. rt_mutex_adjust_prio_chain is called with a task to be checked for PI (de)boosting (the owner of a mutex that a process is blocking on), a flag to check for deadlocking, the mutex that the task owns, and a pointer to a waiter that is the process’s waiter struct that is blocked on the mutex (although this parameter may be NULL for deboosting). For this explanation, I will not mention deadlock detection. This explanation will try to stay at a high level. When this function is called, there are no locks held. That also means that the state of the owner and lock can change when entered into this function. Before this function is called, the task has already had rt_mutex_adjust_prio performed on it. This means that the task is set to the priority that it should be at, but the plist nodes of the task’s waiter have not been updated with the new priorities, and that this task may not be in the proper locations in the pi_lists and wait_lists that the task is blocked on. This function solves all that. A loop is entered, where task is the owner to be checked for PI changes that was passed by parameter (for the first iteration) […]

In Linux kernel documentation. Author:  Steven Rostedt <>
Reviewers:  Ingo Molnar, Thomas Gleixner, Thomas Duetsch, and Randy Dunlap

Bias in academic reviewing

EURYI applications were first submitted to the relevant national research councils, who could nominate a specific number of candidates. This selection cut the proportion of women from one-quarter to one-fifth. Each national research council oversaw a drop in the number of selected women. In Spain, where nearly a third of the applicants were women, not one was nominated. The all-male Spanish list emerged with the highest success rate in the later European rounds, nearly three times the average. From 133 national nominees, European evaluation committees created a shortlist of 67, causing the largest drop in the proportion of women: 9.90+/-.5% of men applying made the European short list , but only 4.7+/-1.4% of women did. [cite]

For more see here.

Computer Science as a failed discipline


I write an email to a CS Prof. asking if they have any followup work on some nice OS measurement research they published a couple of years back. The response is that there is no followup and then:

Me: Too bad. Is it just me or has everyone given up on measurement in OS research?

Prof: It is tough to get reviewers to not have the “there is nothing surprising here” reaction to a measurement study.

For many years, people working in academic computer science argued about whether the field was “science” or “engineering”. To me, this is a silly distinction for a lot of reasons, but currently the field seems to have settled on “neither”.