meianoite's blog

Something's cooking

Blog post by meianoite on Thu, 2009-06-25 16:07

Just like Austin Powers, I'm back, baby!

(Except that I wasn't kept locked in a cryochamber for 30 years. I managed to escape after only two. ;))

So, to paraphrase and one-up Duke Nukem (hope you too escape the chamber sooner rather than later, mate!), let's roll!

And yet another deadline wooshed by...

Blog post by meianoite on Fri, 2009-03-06 09:46

Rule #1: never set deadlines when you're moving houses.
Rule #2: no, they won't reconnect the Internet on a timely fashion, so don't count on it. Telcos make no distinction between "worst case scenario" and "average turnaround time".
Rule #3: by Murphy's law, don't plan on spending some minutes of your lunch time at work writing the blog entry you promised. Your boss will ask you favours if s/he has the slightest suspicion that you're idling.
Rule #4: smartphones aren't made for writing texts of any real length. Don't be tempted to use one for this purpose, else prepare yourself for a lot of grief.

This is bothering me to no end. I'll spend some time at my dad's this weekend, and I'll set aside some quality hours to write. Stay tuned.

Remember the "Young Offender"

Blog post by meianoite on Wed, 2009-02-25 16:46

"We're busy running out of time", said the lyrics.

Actually, the whole lyrics to that song just ring so true to me. Never really liked the song itself, though.

I expect to post the promised (on the mailing list) blog entry by tomorrow.

And those decisions lead us to...

(Or: knitting a delicate fabric, part II: sewing it all together)
(Or: Right, Joker, the underwear might be on the outside, but I get to drive the Batmobile!)
(Or: I just had to say something about Batman and the Batmobile. Couldn't help it.)

Cool, now we have a space- and time-efficient data structure (which is nothing more than a nice structure to handle non-overlapping numeric ranges) we can use to implement the simplified stride scheduling thing I've been discussing ou the previous posts, which will remain small most of the time, and won't change its shape like mad, so it's also very gentle on the CPU cache. Not only that, but the same effects hold for any trees, shall we decide that red-black trees aren't adequate and set ourselves to use splay trees, AA trees, AVL trees, Huffman trees, unbalanced binary trees (please: no.), whatever. So far we took care of the (not any more) skewed proportions due to randomness (by using strides), the mapping of "tickets" to tasks (by using trees to store the queues, "indexes" as the tickets, offsets to simulate "special" tickets, and lazy evaluation to efficiently implement offset propagation to upper queues), and the order of complexity (by using the queues as the node elements of the tree, where the key is base priority times number of threads in that queue).

Some design decisions

(Or: knitting a delicate fabric, part I: the wool[1])

I sincerely hope you've read the disclaimer by now, but I guess I'd better link to it anyway :) Thanks.

I spent the better part of the last post explaining how simple strides would yield an approximation of the ideal shuffling of tickets. What I didn't explain, however, was why the hell am I insisting on using tickets when strides/passes avoids those issues completely.

Well, the thing is, I didn't ditch my previous attempt completely. It had flaws, but there were some gems there as well. I don't know a single programmer who can't recognise it's possible to find sound ideas and really clever excerpts of code even when, on the whole, the code was crap.

(Yes, programmers and software architects are a proud bunch of people.)

And tickets are making a comeback, but in a very different context.

Anyway, suppose we're starting with a clean slate, and all we have so far are the tasks and their respective priorities. Now let's scribble a little in that slate :)

Going back to the basics... kinda.

(Or: what you finally learn to do after a number of false starts)

But first, the obligatory disclaimer, in case you missed it. Thanks.

After I admitted the basic flaws of my previous attempts, I decided to go back to the basics and use a "bottom-up" approach to come up with a solution that suited the needs of the Haiku scheduler: fairness, responsiveness, responsive, scalability, succinctness and efficiency.

Right. So let's keep in mind that the BeBook already hints at what the priority numbers should roughly mean: frequency of scheduling. We have 120 priority levels; the higher 20 are reserved to real-time threads.

This post is not going to address these directly. Instead, today I'll be telling the background story of how quite a number of pieces are being woven together to fulfill those specific needs and constraints. OK, enough metablogging ;)

After letting go of the previous approach, I decided to study the subject on the very traditional literature about it. And while I was studying classic scheduler approaches on the Minix book, I noticed that the description of lottery-based scheduling was very compatible with that description of priorities meaning approximate frequency of being chosen by the scheduler. Lottery scheduling was proposed by Carl Waldspurger in 1994, and it works roughly like this[1]:

The first (or nth, even) attempt: a cautionary tale

(Or: rose-coloured glasses are both the blessing and the curse of being in love)

But first, the obligatory disclaimer, in case you missed