Re: fairsched + O(1) process scheduler

[Antonio Vargas <wind@cocodriloo.com>]

On Wed, Apr 02, 2003 at 08:35:12AM -0800, William Lee Irwin III wrote:
> On Wed, Apr 02, 2003 at 02:46:43PM +0200, Antonio Vargas wrote:
> +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?
> 
> 
> On Wed, Apr 02, 2003 at 02:46:43PM +0200, Antonio Vargas wrote:
> > @@ -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)

Yes I know there are problems, I'm just trying to make it run compile and run :)

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.

b. The thread just takes the first user_truct from the list, adds one tick to his
   timeslice and sends it to the back. This makes the thread giveone
   tick to each user in turn and slowly, instead of trying to give all ticks
   at the same time.

Now, I don't know too much about the locking rules, but I think I could
send a signal, semaphore o spinlock which wakes the thread from the
scheduler_tick(), and the thread could take the uidhash_lock for the update.

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

Greets, Antonio.