[beginner]-lottery scheduling

[justint]

Hi, I'm just trying to wrap my head around the implementation of a very basic lottery scheduling.

I understand that each process can be assigned some number of tickets, but I don't understand how a winning ticket gets mapped to a certain process.

E.g.

Proc. A has 5 tickets
Proc. B has 1 ticket

So A has probability 5/6 to win, and B has 1/6 to win.

So in the scheduler, I'll choose: rand() % ((6 +1) - 1)) + 1, to give me the winning ticket in the range [1,6]. Just say the winning ticket = 4. How do I determine which process has this ticket #?

When I assigned A 5 tickets, how do I tell A which tickets he has? How do real implementations make this decision?

Thanks a lot!

[DutchDaemon]

Is this in any way FreeBSD-related?

[justint]

I guess not directly, but I'm trying to implement the lottery scheduling in FreeBSD...

[expl]

enum{
HOLDER_1,
HOLDER_2
};

#define NTICKETS 6

void give_tickets(int how_many, int *tickets, int holder){
int i;

for(i = 0; i != how_many; i++)
tickets[i] = holder;
}

/*returns the winner*/
int do_lottery(void){
int tickets[NTICKETS], i, lucky_ticket;

give_tickets(5, tickets, HOLDER_1);
give_tickets(1, &tickets[5], HOLDER_2);

lucky_ticket = get_lucky_ticket(); /*your ticket generator*/

return tickets[lucky_ticket];
}

[justint]

Thanks, that code makes the lottery very clear to me!

[GPF]

Follow the link found here for lottery scheduling, if you haven't done so already. There's code and a paper that you will find helpful

http://www.freebsd.org/projects/#kernelandsecurity