OSDev.org

I've decided to implement a lottery scheduler and have a few questions:

1. When a thread is first created it should get some tickets from somewhere. What kind of algorithm should be used to determine how many tickets to hand a thread on creation?
2. Is it a Better Idea to keep a fixed number of tickets, thus making each one represent a fixed amount of actual CPU time, or to make the number of tickets variable, thus making each ticket represent a fraction of whatever available CPU time there is.

As I understand the algorithm, the "tickets" represent the priority, the higher the priority, the more tickets it has. It's built on the principal of mathematical probability, if you pick a number between 1 and 4 and you give me 2 pieces of paper with a number written on each of them then I have a 50% chance of winning (and in this case, getting CPU time). Can't help with the actual implementation though.

Yeah, that's pretty much it. Question two is now moot.

Crazed123 wrote: When a thread is first created it should get some tickets from somewhere. What kind of algorithm should be used to determine how many tickets to hand a thread on creation?

If I got the concept right, "lottery scheduler" means a dynamic priority feedback scheduler - the longer a thread has not run, the higher the probability it runs next. Right?

I would say, a fixed number for user-created threads (all threads are equal). Perhaps a number of "categories" (high, normal, background). Depends on what your OS targets, and how you pass out tickets afterwards...

IIRC, ticket allocation is quite simple, if there is only one thread of priority "1 - Lowest" then it has 1 ticket, the scheduler picks a number between 1 and 1 (ie. 100% CPU time) so you just allocate based on priority:
1 - Lowest
2 - Low
3 - Normal
4 - High
5 - Highest
Normal priority will always have to be half the highest possible number of tickets per thread (to maintain probability).

That sort of "fixed priority" ticket allocation will work for giving initial tickets to new threads. Each thread gets a fixed number of tickets on start, and depending on usage has its ticket count recalculated. Yay.

In order to represent "priorities" in a more lottery-applicable fashion I think ticket currencies will be available as objects that can be accessed via capabilities, as well as the threads that use them. This way system calls could be built to give a certain thread more tickets, even if it inflates the currency, by having the caps to both thread and currency.

Thanks!