updated O(1) scheduler for 2.4

diff -urN linux-2.4.19-pre7/init/do_mounts.c linux/init/do_mounts.c
@@ -774,10 +774,8 @@
 
 	pid = kernel_thread(do_linuxrc, "/linuxrc", SIGCHLD);
 	if (pid > 0) {
-		while (pid != wait(&i)) {
-			current->policy |= SCHED_YIELD;
-			schedule();
-		}
+		while (pid != wait(&i))
+			yield();
 	}
 
 	sys_mount("..", ".", NULL, MS_MOVE, NULL);

diff -urN linux-2.4.19-pre7/arch/m68k/mm/fault.c linux/arch/m68k/mm/fault.c
@@ -181,8 +181,7 @@
 out_of_memory:
 	up_read(&mm->mmap_sem);
 	if (current->pid == 1) {
-		current->policy |= SCHED_YIELD;
-		schedule();
+		yield();
 		down_read(&mm->mmap_sem);
 		goto survive;
 	}

diff -urN linux-2.4.19-pre7/arch/mips/mm/fault.c linux/arch/mips/mm/fault.c
@@ -211,8 +211,7 @@
 out_of_memory:
 	up_read(&mm->mmap_sem);
 	if (tsk->pid == 1) {
-		tsk->policy |= SCHED_YIELD;
-		schedule();
+		yield();
 		down_read(&mm->mmap_sem);
 		goto survive;
 	}

diff -urN linux-2.4.19-pre7/arch/mips64/mm/fault.c linux/arch/mips64/mm/fault.c
@@ -240,8 +240,7 @@
 out_of_memory:
 	up_read(&mm->mmap_sem);
 	if (tsk->pid == 1) {
-		tsk->policy |= SCHED_YIELD;
-		schedule();
+		yield();
 		down_read(&mm->mmap_sem);
 		goto survive;
 	}

@@ -644,6 +644,8 @@
 extern void FASTCALL(interruptible_sleep_on(wait_queue_head_t *q));
 extern long FASTCALL(interruptible_sleep_on_timeout(wait_queue_head_t *q,
 						    signed long timeout));
+extern int FASTCALL(wake_up_process(task_t * p));
+extern void FASTCALL(wake_up_forked_process(task_t * p));
 
 #define wake_up(x)			__wake_up((x),TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1)
 #define wake_up_nr(x, nr)		__wake_up((x),TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, nr)

diff -urNp o1-sched-ref/include/linux/wait.h o1-sched/include/linux/wait.h
@@ -59,6 +59,7 @@ typedef struct __wait_queue wait_queue_t
 # define wq_write_lock_irq write_lock_irq
 # define wq_write_lock_irqsave write_lock_irqsave
 # define wq_write_unlock_irqrestore write_unlock_irqrestore
+# define wq_write_unlock_irq write_unlock_irq
 # define wq_write_unlock write_unlock
 #else
 # define wq_lock_t spinlock_t

@@ -71,6 +72,7 @@ typedef struct __wait_queue wait_queue_t
 # define wq_write_lock_irq spin_lock_irq
 # define wq_write_lock_irqsave spin_lock_irqsave
 # define wq_write_unlock_irqrestore spin_unlock_irqrestore
+# define wq_write_unlock_irq spin_unlock_irq
 # define wq_write_unlock spin_unlock
 #endif
 

diff -urNp o1-sched-ref/kernel/sched.c o1-sched/kernel/sched.c
@@ -850,15 +850,15 @@ void complete(struct completion *x)
 {
 	unsigned long flags;
 
-	spin_lock_irqsave(&x->wait.lock, flags);
+	wq_write_lock_irqsave(&x->wait.lock, flags);
 	x->done++;
 	__wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1);
-	spin_unlock_irqrestore(&x->wait.lock, flags);
+	wq_write_unlock_irqrestore(&x->wait.lock, flags);
 }
 
 void wait_for_completion(struct completion *x)
 {
-	spin_lock_irq(&x->wait.lock);
+	wq_write_lock_irq(&x->wait.lock);
 	if (!x->done) {
 		DECLARE_WAITQUEUE(wait, current);
 

@@ -866,14 +866,14 @@ void wait_for_completion(struct completi
 		__add_wait_queue_tail(&x->wait, &wait);
 		do {
 			__set_current_state(TASK_UNINTERRUPTIBLE);
-			spin_unlock_irq(&x->wait.lock);
+			wq_write_unlock_irq(&x->wait.lock);
 			schedule();
-			spin_lock_irq(&x->wait.lock);
+			wq_write_lock_irq(&x->wait.lock);
 		} while (!x->done);
 		__remove_wait_queue(&x->wait, &wait);
 	}
 	x->done--;
-	spin_unlock_irq(&x->wait.lock);
+	wq_write_unlock_irq(&x->wait.lock);
 }
 
 #define	SLEEP_ON_VAR				\

@@ -1499,8 +1499,8 @@ typedef struct {
  * is removed from the allowed bitmask.
  *
  * NOTE: the caller must have a valid reference to the task, the
- * task must not exit() & deallocate itself prematurely.  The
- * call is not atomic; no spinlocks may be held.
+ * task must not exit() & deallocate itself prematurely.  No
+ * spinlocks can be held.
  */
 void set_cpus_allowed(task_t *p, unsigned long new_mask)
 {

@@ -1523,16 +1523,6 @@ void set_cpus_allowed(task_t *p, unsigne
 		return;
 	}
 
-	/*
-	 * If the task is not on a runqueue, then it is safe to
-	 * simply update the task's cpu field.
-	 */
-	if (!p->array) {
-		p->cpu = __ffs(p->cpus_allowed);
-		task_rq_unlock(rq, &flags);
-		return;
-	}
-
 	init_MUTEX_LOCKED(&req.sem);
 	req.task = p;
 	list_add(&req.list, &rq->migration_queue);

@@ -569,7 +569,7 @@ skip_queue:
 #define CAN_MIGRATE_TASK(p,rq,this_cpu)					\
 	((jiffies - (p)->sleep_timestamp > cache_decay_ticks) &&	\
 		((p) != (rq)->curr) &&					\
-			((p)->cpus_allowed & (1 << (this_cpu))))
+			((p)->cpus_allowed & (1UL << (this_cpu))))
 
 	if (!CAN_MIGRATE_TASK(tmp, busiest, this_cpu)) {
 		curr = curr->next;

@@ -248,7 +248,6 @@ static inline void resched_task(task_t *
 	int need_resched;
 
 	need_resched = p->need_resched;
-	wmb();
 	set_tsk_need_resched(p);
 	if (!need_resched && (p->cpu != smp_processor_id()))
 		smp_send_reschedule(p->cpu);

@@ -794,7 +793,7 @@ switch_tasks:
 		 * if the new task was last running on a different
 		 * CPU - thus re-load it.
 		 */
-		mb();
+		smp_mb();
 		rq = this_rq();
 		spin_unlock_irq(&rq->frozen);
 	} else {

@@ -712,7 +712,6 @@ int do_fork(unsigned long clone_flags, u
 	 * total amount of pending timeslices in the system doesnt change,
 	 * resulting in more scheduling fairness.
 	 */
-	__save_flags(flags);
 	__cli();
 	if (!current->time_slice)
 		BUG();

@@ -728,7 +727,7 @@ int do_fork(unsigned long clone_flags, u
 		scheduler_tick(0,0);
 	}
 	p->sleep_timestamp = jiffies;
-	__restore_flags(flags);
+	__sti();
 
 	/*
 	 * Ok, add it to the run-queues and make it

diff -urNp o1-sched-ref/include/linux/sched.h o1-sched/include/linux/sched.h
@@ -371,6 +371,7 @@ struct task_struct {
 	unsigned long policy;
 	unsigned long cpus_allowed;
 	unsigned int time_slice;
+	int get_child_timeslice;
 
 	task_t *next_task, *prev_task;
 

diff -urNp o1-sched-ref/kernel/exit.c o1-sched/kernel/exit.c
@@ -231,6 +231,7 @@ static inline void forget_original_paren
 			else
 				p->p_opptr = reaper;
 
+			p->get_child_timeslice = 0;
 			if (p->pdeath_signal) send_sig(p->pdeath_signal, p, 0);
 		}
 	}

diff -urNp o1-sched-ref/kernel/fork.c o1-sched/kernel/fork.c
@@ -729,6 +729,8 @@ int do_fork(unsigned long clone_flags, u
 	}
 	p->sleep_timestamp = jiffies;
 	__sti();
+	/* Tell the parent if it can get back its timeslice when child exits */
+	p->get_child_timeslice = 1;
 
 	/*
 	 * Ok, add it to the run-queues and make it

diff -urNp o1-sched-ref/kernel/sched.c o1-sched/kernel/sched.c
@@ -360,9 +360,11 @@ void wake_up_forked_process(task_t * p)
 void sched_exit(task_t * p)
 {
 	__cli();
-	current->time_slice += p->time_slice;
-	if (unlikely(current->time_slice > MAX_TIMESLICE))
-		current->time_slice = MAX_TIMESLICE;
+	if (p->get_child_timeslice) {
+		current->time_slice += p->time_slice;
+		if (unlikely(current->time_slice > MAX_TIMESLICE))
+			current->time_slice = MAX_TIMESLICE;
+	}
 	__sti();
 	/*
 	 * If the child was a (relative-) CPU hog then decrease

@@ -673,6 +675,7 @@ void scheduler_tick(int user_tick, int s
 		 */
 		if ((p->policy == SCHED_RR) && !--p->time_slice) {
 			p->time_slice = TASK_TIMESLICE(p);
+			p->get_child_timeslice = 0;
 			set_tsk_need_resched(p);
 
 			/* put it at the end of the queue: */

@@ -696,6 +699,7 @@ void scheduler_tick(int user_tick, int s
 		set_tsk_need_resched(p);
 		p->prio = effective_prio(p);
 		p->time_slice = TASK_TIMESLICE(p);
+		p->get_child_timeslice = 0;
 
 		if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
 			if (!rq->expired_timestamp)

diff -urNp o1-sched/include/linux/sched.h o1-sched-child-first/include/linux/sched.h
@@ -509,6 +509,7 @@ extern void set_user_nice(task_t *p, lon
 extern int task_prio(task_t *p);
 extern int task_nice(task_t *p);
 
+extern void __sched_yield(void);
 asmlinkage long sys_sched_yield(void);
 #define yield()	sys_sched_yield()
 

diff -urNp o1-sched/kernel/fork.c o1-sched-child-first/kernel/fork.c
@@ -770,12 +770,14 @@ int do_fork(unsigned long clone_flags, u
 	++total_forks;
 	if (clone_flags & CLONE_VFORK)
 		wait_for_completion(&vfork);
-	else
+	else {
 		/*
 		 * Let the child process run first, to avoid most of the
 		 * COW overhead when the child exec()s afterwards.
 		 */
+		__sched_yield();
 		current->need_resched = 1;
+	}
 
 fork_out:
 	return retval;

diff -urNp o1-sched/kernel/sched.c o1-sched-child-first/kernel/sched.c
@@ -1182,7 +1182,7 @@ out_unlock:
 	return retval;
 }
 
-asmlinkage long sys_sched_yield(void)
+void __sched_yield(void)
 {
 	runqueue_t *rq;
 	prio_array_t *array;

@@ -1215,6 +1215,11 @@ asmlinkage long sys_sched_yield(void)
 		__set_bit(current->prio, array->bitmap);
 	}
 	spin_unlock(&rq->lock);
+}
+
+asmlinkage long sys_sched_yield(void)
+{
+	__sched_yield();
 
 	schedule();