gsoc

Some design decisions

Blog post by meianoite on Sun, 2007-06-24 22:39

scheduler, gsoc, scheduling algorithm, algorithm, O(1), complexity, data structure, multiprocessor, affinity, fairness, real time, CFS, Linux, comparison, threads, responsiveness

(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.

Blog post by meianoite on Fri, 2007-06-22 05:52

scheduler, gsoc, scheduling algorithm, algorithm, O(1), complexity, data structure, multiprocessor, affinity, fairness, real time, CFS, Linux, comparison, threads, responsiveness

(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

Blog post by meianoite on Sun, 2007-06-17 22:27

scheduler, gsoc, scheduling algorithm, algorithm, O(1), complexity, data structure, multiprocessor, affinity, fairness, real time, CFS, Linux, comparison, threads, responsiveness

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

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

Remember where I left on the previous post? Now, with greater confidence, I set myself to improve my original algorithm's performance even further. But that's just because I knew it sucked. It was extremely inefficient as far as implementation goes; it looked great in the benchmarks because it was being compared to O(n) (n being the number of threads in the system) algorithms, while it had O(1) complexity, so I already had a head-start, so to speak. Still, I knew the algorithm very well and understood that there were plenty of bottlenecks to fix. I wrote it, after all.

[/pride mode=off]

Introduction to the new Haiku scheduler, and other tidbits

Blog post by meianoite on Sun, 2007-06-17 21:33

scheduler, gsoc, scheduling algorithm, algorithm, O(1), complexity, data structure, multiprocessor, affinity, fairness, real time, CFS, Linux, comparison, threads, responsiveness

Hi, folks!

For those who don't know me (or my GSoC assignment) already, I'm the one assigned to ticket #1069, namely:

Create an O(1) thread scheduler with CPU affinity and soft real-time support which targets desktop responsiveness.

I'd like to dedicate my next few blog entries to introducing myself and discussing how I got here, why I wanted to tackle this specific task, what background I have regarding the subject of thread scheduling, how I failed miserably to realise that my first attempt at designing an algorithm suitable for Haiku's needs had fundamental flaws, how far I am at my second attempt, and the obligatory comparison to Ingo Molnár's Completely Fair Scheduler that has been making the news in the Linux world.

UHCI isochronous support half done

Blog post by emitrax on Sat, 2007-06-09 21:29

usb, gsoc, uhci

Actually is more than half. This quick post is just to inform you that I wrote the part that schedule an isochronous request in the UHCI driver. I've already sent the patch to Michael for his review. The only part that is missing is the code that remove the request once it has been processed or canceled, which is not as trivial as I thought.

emitrax's blog
Login or register to post comments

The Package format

Blog post by Sil2100 on Fri, 2007-06-08 17:07

gsoc, pkg, packages

Personal rant: my university examination session draws near and with it all credit tests as well. I'm doing my best in time management not to put any of my current tasks and projects into starvation, but exactly as Ryan wrote to me - it's not easy.

Going back to more Haiku-specific topics, last week I was mostly analyzing the .pkg format Be Inc. left us behind. After some tests, most crucial parts of it are clear to me now. I must say most of their design solutions for this particular chosen concept had logical and technical grounds. To tell the truth, when I started hacking on this format I thought to myself: “Good god, who did this to you?”. I was wrong. Well... it's a very interesting one nevertheless.

Today is May 28^_^

Blog post by absabs on Mon, 2007-05-28 02:23

gsoc

Hi all,

My name is JiSheng Zhang. I come from China. I am one of the Haiku's GSOC2007 students. My work is implementing a FireWire stack with support for mass storage and DV cams. I plan to port the FreeBSD FireWire stack. I will do my development under debian.

After google anouncement on April 11, I spent time in building Haiku, running on the real PC and reading the source code of haiku's PCI and SCSI sub system and other code about driver writing.

I'm eager for the first payment ^_^. So I can buy a second hand pc with IDE disk and a DV cam with 1394. Today is May 28, I will continue to read the remaing source code and begin coding soon.

Sorry for my broken English :(