fairsched + O(1) process scheduler

On Tue, Apr 01, 2003 at 02:51:59PM +0200, Antonio Vargas wrote:

kernel/sched.c renamed from kernel/sched.c~fairsched-A0 +4 -0

+
+	if(fairsched){
+		/* special processing for per-user fair scheduler */
+	}

I suspect something more needs to happen there. =)

I'd recommend a different approach, i.e. stratifying the queue into a user top level and a task bottom level. The state is relatively well encapsulated so it shouldn't be that far out.

-- wli

Quoted 7 lines · William Lee Irwin III

On Tue, Apr 01, 2003 at 02:51:59PM +0200, Antonio Vargas wrote:

(quoted diff) +4 -0

+
+	if(fairsched){
+		/* special processing for per-user fair scheduler */
+	}

I suspect something more needs to happen there. =)

:) I haven't even compiled with this patch, I'm just trying
to get around my ideas and thus I posted so that:

a. We had an off-site backup

b. People with experience could shout out loud if they saw
some big-time silliness.

Quoted 6 lines

I'd recommend a different approach, i.e. stratifying the queue into a user top level and a task bottom level. The state is relatively well encapsulated so it shouldn't be that far out.

-- wli

I suspect you mean the scheduler runqueues?

My initial idea runs as follows:

a. On each array switch, we add some fixed value
to user->ticks. (HZ perhaps?)

b. When adding, we cap at some maximum value.
(2*HZ perhaps?)

c. On each timer tick, we decrement current->user->ticks.

d. When decrementing, if it's below zero we just
end this thread. (user has expired)

e. When switching threads, we take the first one that belongs
to a non-expired user. I think this can be done by sending the user-expired threads to the expired array, just like when they expire themselves.

I'll try to code this tonight, so I'll post later on if I'm lucky.

I think this needs much less complexity for a first version, but I would try what you propose if I get intimate enough with the scheduler.

Greets, Antonio.

On Wed, Apr 02, 2003 at 02:46:43PM +0200, Antonio Vargas wrote:

kernel/sched.c renamed from kernel/sched.c~fairsched-A1 +8 -0

+static inline void update_user_timeslices(void)
...
+	list_for_each(entry, &user_list) {
+		user = list_entry(entry, struct user_struct, uid_list);
+
+		if(!user) continue;
+
+		if(0){
+			user_time_slice = user->time_slice;

Hmm, this looks very O(n)... BTW, doesn't uidhash_lock lock user_list?

kernel/user.c struct user_struct root_user = { · line 46

Quoted 6 lines · Antonio Vargas

kernel/user.c renamed from kernel/user.c~fairsched-A1 +1 -0

@@ -39,10 +42,12 @@ struct user_struct root_user = {
 static inline void uid_hash_insert(struct user_struct *up, struct list_head *hashent)
 {
 	list_add(&up->uidhash_list, hashent);
+	list_add(&up->uid_list, &user_list);
 }

Okay, there are three or four problems:

(1) uidhash_lock can't be taken in interrupt context
(2) you aren't taking uidhash_lock at all in update_user_timeslices()
(3) you're not actually handing out user timeslices due to an if (0)
(4) walking user_list is O(n)

I've been thinking about this thing a while ago, and I think I could do this:

a. Have a kernel thread which wakes up on each tick.

Also, this locking rule means I can't even read current->user->time_slice? What if I changed the type to an atomic_int?

Quoted 3 lines · Antonio Vargas

I've been thinking about this thing a while ago, and I think I could do this:

a. Have a kernel thread which wakes up on each tick.

Why not use the timer tick itself? It already calls scheduler_tick()...

Oh, because you need to grab uidhash_lock? Ew. Needing a kernel thread for this is not pretty.

Quoted 2 lines

Also, this locking rule means I can't even read current->user->time_slice? What if I changed the type to an atomic_int?

You can always read a single word-sized type atomically. No need for atomic_t's.

Hmmm, we had some way for executing code just after an interrupt, but outside interrupt scope... was it a bottom half? Can you point me to some place where it's done?

Ok, I did know m68k can do it, but wasn't sure about all other arches :)

Quoted 3 lines · Antonio Vargas

Hmmm, we had some way for executing code just after an interrupt, but outside interrupt scope... was it a bottom half? Can you point me to some place where it's done?

Unfortunately uidhash_lock cannot be used from a bottom half either.

You can push it into a work queue. See schedule_work() and the default events queue.

Quoted 1 line

Ok, I did know m68k can do it, but wasn't sure about all other arches :)

Yep. Everyone architecture I know of - and certainly all that Linux support - can do atomic read/writes to a word. Thinking about it, it would be odd if not (two writes to a single word interleaving?). There are places this assumption is used.

Anything more complicated, of course, needs atomic operations or locks.

Yep. Everyone architecture I know of - and certainly all that Linux support - can do atomic read/writes to a word. Thinking about it, it would be odd if not (two writes to a single word interleaving?). There are places this assumption is used.

I believe this is true if the data is aligned. I don't think it's true for unaligned access on an x86.

Quoted 2 lines · Antonio Vargas

Quoted 1 line · William Lee Irwin III

On Tue, Apr 01, 2003 at 02:51:59PM +0200, Antonio Vargas wrote:

To add to my previous reply...
In your approach you might have a problem with starvation. High priority processes simply can eat all the ticks allocated to a user and when lower priority tasks pop up at the top of the active list they are move to the inactive list. This could happen over and over again, thus starving those tasks.

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.

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

Quoted 8 lines · Antonio Vargas

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.

Quoted 11 lines · Antonio Vargas

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.

Quoted 4 lines

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.

Quoted 4 lines

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.

Just out of experimenting, I've coded something that looks reasonable and would not experience starvation.
In the normal scheduler, a non-interactive task will, when used all his timeslice, reset p->time_slice and queue onto the expired array. I'm now reseting p->reserved_time_slice instead and queuing the task onto a per-user pending task queue.
A separate kernel thread walks the user list, calculates the user timeslice and distributes it to it's pending tasks. When a task receives timeslices, it's moved from the per-user pending queue to the expired array of the runqueue, thus preparing it to run on the next array-switch.

If the user has many timeslices, he can give timeslices to many tasks, thus getting more work done.
While the implementation may not be good enough, due to locking problems and the use of a kernel-thread, I think the fundamental algorithm feels right. William, should I take the lock on the uidhash_list when adding a task to a per-user task list?

Quoted 4 lines · William Lee Irwin III

Quoted 4 lines

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.

[...]

Quoted 4 lines

Quoted 4 lines

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.

Quoted 11 lines · Antonio Vargas

Just out of experimenting, I've coded something that looks reasonable and would not experience starvation.
In the normal scheduler, a non-interactive task will, when used all his timeslice, reset p->time_slice and queue onto the expired array. I'm now reseting p->reserved_time_slice instead and queuing the task onto a per-user pending task queue.
A separate kernel thread walks the user list, calculates the user timeslice and distributes it to it's pending tasks. When a task receives timeslices, it's moved from the per-user pending queue to the expired array of the runqueue, thus preparing it to run on the next array-switch.

Hmm, priorities getting recalculated by a kernel thread sounds kind of scary, but who am I to judge?

Quoted 6 lines

If the user has many timeslices, he can give timeslices to many tasks, thus getting more work done.
While the implementation may not be good enough, due to locking problems and the use of a kernel-thread, I think the fundamental algorithm feels right. William, should I take the lock on the uidhash_list when adding a task to a per-user task list?

Possible, though I'd favor a per-user spinlock.

The code looks reasonable now, modulo that race you asked about.

Quoted 1 line

Possible, though I'd favor a per-user spinlock.

So, when trying to add a task to the per-user pending tasks, I'd have to do this:
1. spin_lock_irqsave(uidhash_lock, flags)
2. spin_lock(my_user->user_lock)
3. spin_unlock_restore(uidhash_lock, flags);
Is this any good?
Could I simply do "spin_unlock(my_user->user_lock)" at end without taking the uidhash_lock again?

Quoted 1 line

The code looks reasonable now, modulo that race you asked about.

What do I need to lock when I want to add a task to a runqueue? I'm doing a "spin_lock_irq(this_rq()->lock);"
As you can see, I'm not yet at speed with the locking rules... any online references to the latest locking rules? The BKL was really easy to understand in comparison! *grin*

Quoted 50 lines · Antonio Vargas

Quoted 28 lines · William Lee Irwin III

Quoted 8 lines · Antonio Vargas

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.

Quoted 11 lines · Antonio Vargas

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

Quoted 4 lines

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.

Just out of experimenting, I've coded something that looks reasonable and would not experience starvation.

In the normal scheduler, a non-interactive task will, when used all his timeslice, reset p->time_slice and queue onto the expired array. I'm now reseting p->reserved_time_slice instead and queuing the task onto a per-user pending task queue.

A separate kernel thread walks the user list, calculates the user timeslice and distributes it to it's pending tasks. When a task receives timeslices, it's moved from the per-user pending queue to the expired array of the runqueue, thus preparing it to run on the next array-switch.

If the user has many timeslices, he can give timeslices to many tasks, thus getting more work done.

Quoted 8 lines

While the implementation may not be good enough, due to locking problems and the use of a kernel-thread, I think the fundamental algorithm feels right.

William, should I take the lock on the uidhash_list when adding a task to a per-user task list?

Greets, Antonio.

Antonio, I am going right now through some stuff.
Again I am coming from a class based approach, but fundamentally now difference.

First there are several issues that need to be addressed and they might have to be handled differently.
Shares can be observed under hard limits or soft limits (work preserving). The first proposal you put forward was clearly work preserving. The latter one (if I understood correctly reading it in 2 seconds) would facilitate hard working limits. The problem to simply do it at array switch time is that you could spent increased time in schedule() simply moving tasks between active and expired until ticks are regranted to the user.

I have two concerns (and pardon me again if you already addressed them)

(A) starvation problem.
---------------------------------
One process could eat all the ticks
assigned to a user, leading that subsequent scheduled task will always move to the expired list.

Effectively, the sum(timeslices) per user is the number of ticks I need to give (given all cpu bound) for a user to get all tasks execute.

The ratio between the sums of the different users is effectively what is dictated by the shares.
One has effectively two means to manipulate that
(a) modifying the static_priority of tasks belonging to a user
(b) modifying the effective_priority of tasks belonging to a user
(c) modifying the time_slice of tasks

all modifications are based on whether a user is overspending or underspending at some given rate.
To me (a) is not an option.
(b) tells me to modify the urgency of a task to be scheduled
(c) tells me how long task should run, its also depends on (a).

What needs to be achieved is that starving tasks move up in the effective_priority above the ones that keep eating allotted ticks.

(B) O(1) issues
-------------------------

By setting tasks aside to wait for replenishment of ticks for the users you might introduce an non O(1) effect, that Ingo might object against. One could argue, that you simply put the tasks asleep..

I am currently doing the math and coming up with a scheme. I should be hopefully close to something by Monday, which I can then share and if you want you can experiment around with. Need to do this anyway for the OLS paper we are presenting.
Also, I need to go through your latest patch in more detail, before I give you injustice, I just want to have the framework in my head first.

Ping me on Monday...

-- Hubertus

Antonio, while you are coding here is some additional input.

By intoducing the user based pending queue and leaking the tasks back into the runqueue based on the per user ticks, you are changing semantics slightly.

If the task is reinserted back into the runqueue oit should be reinserted into the expired queue iff and only no expired/active queue switch has happened.
Otherwise it should be reinserted into the active list.

This will becoe important when we later distinguish between users that have limited share and those that have unlimited.

Can be implemented by keeping a per runqueue array switch count and store it with the pending task. On reinsertion, if the task has the same as the current it goes to the expired. If its older than the current, then the task missed the array switch and it should go into the active queue.

Also, I don't follow necessarily your reason to put an INTERACTIVE task back on the active queue immediately, rather than going first through the pending queue again.

This way, a high priority job with even a small sleep_avg already being declared INTERACTIVE, will continue to suck up cycles beyond its user's limits. This can be as long as 8 secs currently.

Instead, things to consider is to feed these as well through the pending queue and distinguish in the pending queue ? More thoughts required here... I let you know when any of them is successful at my end.