Re: fairsched + O(1) process scheduler

[William Lee Irwin III]

On Thu, Apr 03, 2003 at 02:53:55PM +0200, Antonio Vargas wrote:
> Sorry for not answering sooner, but I had my mail pointing at
> the lkml instead of my personal email.
> Last night I continued coding up but I think I've it a deadlock:
> it seems the system stops calling schedule_tick() when there are
> no more tasks to run, and it's there where I use a workqueue so
> that I can update the user timeslices out of interrupt context.
> I think that because if I put printk's on my code, it continues to
> run OK, but if I remove them it freezes hard.

Use spin_lock_irq(&uidhash_lock) or you will deadlock if you hold it
while you take a timer tick, but it's wrong anyway. it's O(N) with
respect to number of users present. An O(1) algorithm could easily
make use of reference counts held by tasks.

On Thu, Apr 03, 2003 at 02:53:55PM +0200, Antonio Vargas wrote:
> About giving ticks to users, I've got an idea: assuming there are N
> total processes in the system and an user has got M processes, we should
> give N * max_timeslice ticks to each user every M * max_timeslice *
> num_users ticks. I've been thinking about it and it seems it would
> balance the ticks correctly.
> About the starvation for low-priority processes, I can get and
> example.. assume user A has process X Y and user B has process Z,
> and max_timeslice = 2:
> max_timeslice = 2 and 4 total processes ==>
> give 2 * 3 = 6 ticks to user A every 2 * 2 * 2 =  8 ticks
> give 2 * 3 = 6 ticks to user B every 1 * 2 * 2 =  4 ticks

This isn't right, when expiration happens needs to be tracked by both
user and task. Basically which tasks are penalized when the user
expiration happens? The prediction is the same set of tasks will always
be the target of the penalty.

-- wli