WebSVN – HelenOS-historic – Diff – /kernel/trunk/generic/src/proc/scheduler.c


/*
 * Copyright (C) 2001-2004 Jakub Jermar
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * - Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 * - Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 * - The name of the author may not be used to endorse or promote products
 *   derived from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
#include <proc/scheduler.h>
#include <proc/thread.h>
#include <proc/task.h>
#include <cpu.h>
#include <mm/vm.h>
#include <config.h>
#include <context.h>
#include <func.h>
#include <arch.h>
#include <arch/asm.h>
#include <list.h>
#include <typedefs.h>
#include <mm/page.h>
#include <synch/spinlock.h>
 
#ifdef __SMP__
#include <arch/smp/atomic.h>
#endif /* __SMP__ */
 
/*
 * NOTE ON ATOMIC READS:
 * Some architectures cannot read __u32 atomically.
 * For that reason, all accesses to nrdy and the likes must be protected by spinlock.
 */
 
spinlock_t nrdylock;
volatile int nrdy;
 
void before_thread_runs(void)
{
    before_thread_runs_arch();
    fpu_context_restore();
}
 
 
void scheduler_init(void)
{
    spinlock_initialize(&nrdylock);
}
 
/* cpu_priority_high()'d */
struct thread *find_best_thread(void)
{
    thread_t *t;
    runq_t *r;
    int i, n;
 
loop:
    cpu_priority_high();
 
    spinlock_lock(&CPU->lock);
    n = CPU->nrdy;
    spinlock_unlock(&CPU->lock);
 
    cpu_priority_low();
   
    if (n == 0) {
        #ifdef __SMP__
        /*
         * If the load balancing thread is not running, wake it up and
         * set CPU-private flag that the kcpulb has been started.
         */
        if (test_and_set(&CPU->kcpulbstarted) == 0) {
                waitq_wakeup(&CPU->kcpulb_wq, 0);
            goto loop;
        }
        #endif /* __SMP__ */
       
        /*
         * For there was nothing to run, the CPU goes to sleep
         * until a hardware interrupt or an IPI comes.
         * This improves energy saving and hyperthreading.
         * On the other hand, several hardware interrupts can be ignored.
         */
         cpu_sleep();
         goto loop;
    }
 
    cpu_priority_high();
 
    for (i = 0; i<RQ_COUNT; i++) {
        r = &CPU->rq[i];
        spinlock_lock(&r->lock);
        if (r->n == 0) {
            /*
             * If this queue is empty, try a lower-priority queue.
             */
            spinlock_unlock(&r->lock);
            continue;
        }
   
        spinlock_lock(&nrdylock);
        nrdy--;
        spinlock_unlock(&nrdylock);    
 
        spinlock_lock(&CPU->lock);
        CPU->nrdy--;
        spinlock_unlock(&CPU->lock);
 
        r->n--;
 
        /*
         * Take the first thread from the queue.
         */
        t = list_get_instance(r->rq_head.next, thread_t, rq_link);
        list_remove(&t->rq_link);
 
        spinlock_unlock(&r->lock);
 
        spinlock_lock(&t->lock);
        t->cpu = CPU;
 
        t->ticks = us2ticks((i+1)*10000);
        t->pri = i; /* eventually correct rq index */
 
        /*
         * Clear the X_STOLEN flag so that t can be migrated when load balancing needs emerge.
         */
        t->flags &= ~X_STOLEN;
        spinlock_unlock(&t->lock);
 
        return t;
    }
    goto loop;
 
}
 
/*
 * This function prevents low priority threads from starving in rq's.
 * When it decides to relink rq's, it reconnects respective pointers
 * so that in result threads with 'pri' greater or equal 'start' are
 * moved to a higher-priority queue.
 */
void relink_rq(int start)
{
    link_t head;
    runq_t *r;
    int i, n;
 
    list_initialize(&head);
    spinlock_lock(&CPU->lock);
    if (CPU->needs_relink > NEEDS_RELINK_MAX) {
        for (i = start; i<RQ_COUNT-1; i++) {
            /* remember and empty rq[i + 1] */
            r = &CPU->rq[i + 1];
            spinlock_lock(&r->lock);
            list_concat(&head, &r->rq_head);
            n = r->n;
            r->n = 0;
            spinlock_unlock(&r->lock);
       
            /* append rq[i + 1] to rq[i] */
            r = &CPU->rq[i];
            spinlock_lock(&r->lock);
            list_concat(&r->rq_head, &head);
            r->n += n;
            spinlock_unlock(&r->lock);
        }
        CPU->needs_relink = 0;
    }
    spinlock_unlock(&CPU->lock);               
 
}
 
/*
 * The scheduler.
 */
void scheduler(void)
{
    volatile pri_t pri;
 
    pri = cpu_priority_high();
 
    if (haltstate)
        halt();
 
    if (THREAD) {
        spinlock_lock(&THREAD->lock);
        if (!context_save(&THREAD->saved_context)) {
            /*
             * This is the place where threads leave scheduler();
             */
            before_thread_runs();
                spinlock_unlock(&THREAD->lock);
            cpu_priority_restore(THREAD->saved_context.pri);
            return;
        }
        THREAD->saved_context.pri = pri;
    }
 
    /*
     * We may not keep the old stack.
     * Reason: If we kept the old stack and got blocked, for instance, in
     * find_best_thread(), the old thread could get rescheduled by another
     * CPU and overwrite the part of its own stack that was also used by
     * the scheduler on this CPU.
     *
     * Moreover, we have to bypass the compiler-generated POP sequence
     * which is fooled by SP being set to the very top of the stack.
     * Therefore the scheduler() function continues in
     * scheduler_separated_stack().
     */
    context_save(&CPU->saved_context);
    CPU->saved_context.sp = (__address) &CPU->stack[CPU_STACK_SIZE-8];
    CPU->saved_context.pc = (__address) scheduler_separated_stack;
    context_restore(&CPU->saved_context);
    /* not reached */
}
 
void scheduler_separated_stack(void)
{
    int priority;
 
    if (THREAD) {
        switch (THREAD->state) {
            case Running:
                THREAD->state = Ready;
                spinlock_unlock(&THREAD->lock);
                thread_ready(THREAD);
                break;
 
            case Exiting:
                frame_free((__address) THREAD->kstack);
                if (THREAD->ustack) {
                    frame_free((__address) THREAD->ustack);
                }
               
                /*
                 * Detach from the containing task.
                 */
                spinlock_lock(&TASK->lock);
                list_remove(&THREAD->th_link);
                spinlock_unlock(&TASK->lock);
 
                spinlock_unlock(&THREAD->lock);
               
                spinlock_lock(&threads_lock);
                list_remove(&THREAD->threads_link);
                spinlock_unlock(&threads_lock);
               
                free(THREAD);
               
                break;
               
            case Sleeping:
                /*
                 * Prefer the thread after it's woken up.
                 */
                THREAD->pri = -1;
 
                /*
                 * We need to release wq->lock which we locked in waitq_sleep().
                 * Address of wq->lock is kept in THREAD->sleep_queue.
                 */
                spinlock_unlock(&THREAD->sleep_queue->lock);
 
                /*
                 * Check for possible requests for out-of-context invocation.
                 */
                if (THREAD->call_me) {
                    THREAD->call_me(THREAD->call_me_with);
                    THREAD->call_me = NULL;
                    THREAD->call_me_with = NULL;
                }
 
                spinlock_unlock(&THREAD->lock);
               
                break;
 
            default:
                /*
                 * Entering state is unexpected.
                 */
                panic("tid%d: unexpected state %s\n", THREAD->tid, thread_states[THREAD->state]);
                break;
        }
        THREAD = NULL;
    }
   
    THREAD = find_best_thread();
   
    spinlock_lock(&THREAD->lock);
    priority = THREAD->pri;
    spinlock_unlock(&THREAD->lock);
   
    relink_rq(priority);       
 
    spinlock_lock(&THREAD->lock);  
 
    /*
     * If both the old and the new task are the same, lots of work is avoided.
     */
    if (TASK != THREAD->task) {
        vm_t *m1 = NULL;
        vm_t *m2;
 
        if (TASK) {
            spinlock_lock(&TASK->lock);
            m1 = TASK->vm;
            spinlock_unlock(&TASK->lock);
        }
 
        spinlock_lock(&THREAD->task->lock);
        m2 = THREAD->task->vm;
        spinlock_unlock(&THREAD->task->lock);
       
        /*
         * Note that it is possible for two tasks to share one vm mapping.
         */
        if (m1 != m2) {
            /*
             * Both tasks and vm mappings are different.
             * Replace the old one with the new one.
             */
            if (m1) {
                vm_uninstall(m1);
            }
            vm_install(m2);
        }
        TASK = THREAD->task;   
    }
 
    THREAD->state = Running;
 
    #ifdef SCHEDULER_VERBOSE
    printf("cpu%d: tid %d (pri=%d,ticks=%d,nrdy=%d)\n", CPU->id, THREAD->tid, THREAD->pri, THREAD->ticks, CPU->nrdy);
    #endif  
 
    context_restore(&THREAD->saved_context);
    /* not reached */
}
 
#ifdef __SMP__
/*
 * This is the load balancing thread.
 * It supervises thread supplies for the CPU it's wired to.
 */
void kcpulb(void *arg)
{
    thread_t *t;
    int count, i, j, k = 0;
    pri_t pri;
 
loop:
    /*
     * Sleep until there's some work to do.
     */
    waitq_sleep(&CPU->kcpulb_wq);
 
not_satisfied:
    /*
     * Calculate the number of threads that will be migrated/stolen from
     * other CPU's. Note that situation can have changed between two
     * passes. Each time get the most up to date counts.
     */
    pri = cpu_priority_high();
    spinlock_lock(&CPU->lock);
    count = nrdy / config.cpu_active;
    count -= CPU->nrdy;
    spinlock_unlock(&CPU->lock);
    cpu_priority_restore(pri);
 
    if (count <= 0)
        goto satisfied;
 
    /*
     * Searching least priority queues on all CPU's first and most priority queues on all CPU's last.
     */
    for (j=RQ_COUNT-1; j >= 0; j--) {
        for (i=0; i < config.cpu_active; i++) {
            link_t *l;
            runq_t *r;
            cpu_t *cpu;
 
            cpu = &cpus[(i + k) % config.cpu_active];
            r = &cpu->rq[j];
 
            /*
             * Not interested in ourselves.
             * Doesn't require interrupt disabling for kcpulb is X_WIRED.
             */
            if (CPU == cpu)
                continue;
 
restart:        pri = cpu_priority_high();
            spinlock_lock(&r->lock);
            if (r->n == 0) {
                spinlock_unlock(&r->lock);
                cpu_priority_restore(pri);
                continue;
            }
       
            t = NULL;
            l = r->rq_head.prev;    /* search rq from the back */
            while (l != &r->rq_head) {
                t = list_get_instance(l, thread_t, rq_link);
                /*
                     * We don't want to steal CPU-wired threads neither threads already stolen.
                 * The latter prevents threads from migrating between CPU's without ever being run.
                     */
                spinlock_lock(&t->lock);
                if (!(t->flags & (X_WIRED | X_STOLEN))) {
                    /*
                     * Remove t from r.
                     */
 
                    spinlock_unlock(&t->lock);
                   
                    /*
                     * Here we have to avoid deadlock with relink_rq(),
                     * because it locks cpu and r in a different order than we do.
                     */
                    if (!spinlock_trylock(&cpu->lock)) {
                        /* Release all locks and try again. */
                        spinlock_unlock(&r->lock);
                        cpu_priority_restore(pri);
                        goto restart;
                    }
                    cpu->nrdy--;
                    spinlock_unlock(&cpu->lock);
 
                    spinlock_lock(&nrdylock);
                    nrdy--;
                    spinlock_unlock(&nrdylock);                
 
                        r->n--;
                    list_remove(&t->rq_link);
 
                    break;
                }
                spinlock_unlock(&t->lock);
                l = l->prev;
                t = NULL;
            }
            spinlock_unlock(&r->lock);
 
            if (t) {
                /*
                 * Ready t on local CPU
                 */
                spinlock_lock(&t->lock);
                #ifdef KCPULB_VERBOSE
                printf("kcpulb%d: TID %d -> cpu%d, nrdy=%d, avg=%d\n", CPU->id, t->tid, CPU->id, CPU->nrdy, nrdy / config.cpu_active);
                #endif
                t->flags |= X_STOLEN;
                spinlock_unlock(&t->lock);
   
                thread_ready(t);
 
                cpu_priority_restore(pri);
   
                if (--count == 0)
                    goto satisfied;
                   
                /*
                             * We are not satisfied yet, focus on another CPU next time.
                 */
                k++;
               
                continue;
            }
            cpu_priority_restore(pri);
        }
    }
 
    if (CPU->nrdy) {
        /*
         * Be a little bit light-weight and let migrated threads run.
         */
        scheduler();
    }
    else {
        /*
         * We failed to migrate a single thread.
         * Something more sophisticated should be done.
         */
        scheduler();
    }
       
    goto not_satisfied;
   
satisfied:
    /*
     * Tell find_best_thread() to wake us up later again.
     */
    CPU->kcpulbstarted = 0;
    goto loop;
}
 
#endif /* __SMP__ */
 

Rev 22	Rev 52
1	/*	1	/*
2	* Copyright (C) 2001-2004 Jakub Jermar	2	* Copyright (C) 2001-2004 Jakub Jermar
3	* All rights reserved.	3	* All rights reserved.
4	*	4	*
5	* Redistribution and use in source and binary forms, with or without	5	* Redistribution and use in source and binary forms, with or without
6	* modification, are permitted provided that the following conditions	6	* modification, are permitted provided that the following conditions
7	* are met:	7	* are met:
8	*	8	*
9	* - Redistributions of source code must retain the above copyright	9	* - Redistributions of source code must retain the above copyright
10	* notice, this list of conditions and the following disclaimer.	10	* notice, this list of conditions and the following disclaimer.
11	* - Redistributions in binary form must reproduce the above copyright	11	* - Redistributions in binary form must reproduce the above copyright
12	* notice, this list of conditions and the following disclaimer in the	12	* notice, this list of conditions and the following disclaimer in the
13	* documentation and/or other materials provided with the distribution.	13	* documentation and/or other materials provided with the distribution.
14	* - The name of the author may not be used to endorse or promote products	14	* - The name of the author may not be used to endorse or promote products
15	* derived from this software without specific prior written permission.	15	* derived from this software without specific prior written permission.
16	*	16	*
17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR	17	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES	18	* IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.	19	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,	20	* IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT	21	* INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,	22	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY	23	* DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT	24	* THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF	25	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.	26	* THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27	*/	27	*/
28		28
29	#include <proc/scheduler.h>	29	#include <proc/scheduler.h>
30	#include <proc/thread.h>	30	#include <proc/thread.h>
31	#include <proc/task.h>	31	#include <proc/task.h>
32	#include <cpu.h>	32	#include <cpu.h>
33	#include <mm/vm.h>	33	#include <mm/vm.h>
34	#include <config.h>	34	#include <config.h>
35	#include <context.h>	35	#include <context.h>
36	#include <func.h>	36	#include <func.h>
37	#include <arch.h>	37	#include <arch.h>
38	#include <arch/asm.h>	38	#include <arch/asm.h>
39	#include <list.h>	39	#include <list.h>
40	#include <typedefs.h>	40	#include <typedefs.h>
41	#include <mm/page.h>	41	#include <mm/page.h>
42	#include <synch/spinlock.h>	42	#include <synch/spinlock.h>
43		43
44	#ifdef __SMP__	44	#ifdef __SMP__
45	#include <arch/smp/atomic.h>	45	#include <arch/smp/atomic.h>
46	#endif /* __SMP__ */	46	#endif /* __SMP__ */
47		47
48	/*	48	/*
49	* NOTE ON ATOMIC READS:	49	* NOTE ON ATOMIC READS:
50	* Some architectures cannot read __u32 atomically.	50	* Some architectures cannot read __u32 atomically.
51	* For that reason, all accesses to nrdy and the likes must be protected by spinlock.	51	* For that reason, all accesses to nrdy and the likes must be protected by spinlock.
52	*/	52	*/
53		53
54	spinlock_t nrdylock;	54	spinlock_t nrdylock;
55	volatile int nrdy;	55	volatile int nrdy;
56		56
-		57	void before_thread_runs(void)
-		58	{
-		59	before_thread_runs_arch();
-		60	fpu_context_restore();
-		61	}
-		62
-		63
57	void scheduler_init(void)	64	void scheduler_init(void)
58	{	65	{
59	spinlock_initialize(&nrdylock);	66	spinlock_initialize(&nrdylock);
60	}	67	}
61		68
62	/* cpu_priority_high()'d */	69	/* cpu_priority_high()'d */
63	struct thread *find_best_thread(void)	70	struct thread *find_best_thread(void)
64	{	71	{
65	thread_t *t;	72	thread_t *t;
66	runq_t *r;	73	runq_t *r;
67	int i, n;	74	int i, n;
68		75
69	loop:	76	loop:
70	cpu_priority_high();	77	cpu_priority_high();
71		78
72	spinlock_lock(&CPU->lock);	79	spinlock_lock(&CPU->lock);
73	n = CPU->nrdy;	80	n = CPU->nrdy;
74	spinlock_unlock(&CPU->lock);	81	spinlock_unlock(&CPU->lock);
75		82
76	cpu_priority_low();	83	cpu_priority_low();
77		84
78	if (n == 0) {	85	if (n == 0) {
79	#ifdef __SMP__	86	#ifdef __SMP__
80	/*	87	/*
81	* If the load balancing thread is not running, wake it up and	88	* If the load balancing thread is not running, wake it up and
82	* set CPU-private flag that the kcpulb has been started.	89	* set CPU-private flag that the kcpulb has been started.
83	*/	90	*/
84	if (test_and_set(&CPU->kcpulbstarted) == 0) {	91	if (test_and_set(&CPU->kcpulbstarted) == 0) {
85	waitq_wakeup(&CPU->kcpulb_wq, 0);	92	waitq_wakeup(&CPU->kcpulb_wq, 0);
86	goto loop;	93	goto loop;
87	}	94	}
88	#endif /* __SMP__ */	95	#endif /* __SMP__ */
89		96
90	/*	97	/*
91	* For there was nothing to run, the CPU goes to sleep	98	* For there was nothing to run, the CPU goes to sleep
92	* until a hardware interrupt or an IPI comes.	99	* until a hardware interrupt or an IPI comes.
93	* This improves energy saving and hyperthreading.	100	* This improves energy saving and hyperthreading.
94	* On the other hand, several hardware interrupts can be ignored.	101	* On the other hand, several hardware interrupts can be ignored.
95	*/	102	*/
96	cpu_sleep();	103	cpu_sleep();
97	goto loop;	104	goto loop;
98	}	105	}
99		106
100	cpu_priority_high();	107	cpu_priority_high();
101		108
102	for (i = 0; i<RQ_COUNT; i++) {	109	for (i = 0; i<RQ_COUNT; i++) {
103	r = &CPU->rq[i];	110	r = &CPU->rq[i];
104	spinlock_lock(&r->lock);	111	spinlock_lock(&r->lock);
105	if (r->n == 0) {	112	if (r->n == 0) {
106	/*	113	/*
107	* If this queue is empty, try a lower-priority queue.	114	* If this queue is empty, try a lower-priority queue.
108	*/	115	*/
109	spinlock_unlock(&r->lock);	116	spinlock_unlock(&r->lock);
110	continue;	117	continue;
111	}	118	}
112		119
113	spinlock_lock(&nrdylock);	120	spinlock_lock(&nrdylock);
114	nrdy--;	121	nrdy--;
115	spinlock_unlock(&nrdylock);	122	spinlock_unlock(&nrdylock);
116		123
117	spinlock_lock(&CPU->lock);	124	spinlock_lock(&CPU->lock);
118	CPU->nrdy--;	125	CPU->nrdy--;
119	spinlock_unlock(&CPU->lock);	126	spinlock_unlock(&CPU->lock);
120		127
121	r->n--;	128	r->n--;
122		129
123	/*	130	/*
124	* Take the first thread from the queue.	131	* Take the first thread from the queue.
125	*/	132	*/
126	t = list_get_instance(r->rq_head.next, thread_t, rq_link);	133	t = list_get_instance(r->rq_head.next, thread_t, rq_link);
127	list_remove(&t->rq_link);	134	list_remove(&t->rq_link);
128		135
129	spinlock_unlock(&r->lock);	136	spinlock_unlock(&r->lock);
130		137
131	spinlock_lock(&t->lock);	138	spinlock_lock(&t->lock);
132	t->cpu = CPU;	139	t->cpu = CPU;
133		140
134	t->ticks = us2ticks((i+1)*10000);	141	t->ticks = us2ticks((i+1)*10000);
135	t->pri = i; /* eventually correct rq index */	142	t->pri = i; /* eventually correct rq index */
136		143
137	/*	144	/*
138	* Clear the X_STOLEN flag so that t can be migrated when load balancing needs emerge.	145	* Clear the X_STOLEN flag so that t can be migrated when load balancing needs emerge.
139	*/	146	*/
140	t->flags &= ~X_STOLEN;	147	t->flags &= ~X_STOLEN;
141	spinlock_unlock(&t->lock);	148	spinlock_unlock(&t->lock);
142		149
143	return t;	150	return t;
144	}	151	}
145	goto loop;	152	goto loop;
146		153
147	}	154	}
148		155
149	/*	156	/*
150	* This function prevents low priority threads from starving in rq's.	157	* This function prevents low priority threads from starving in rq's.
151	* When it decides to relink rq's, it reconnects respective pointers	158	* When it decides to relink rq's, it reconnects respective pointers
152	* so that in result threads with 'pri' greater or equal 'start' are	159	* so that in result threads with 'pri' greater or equal 'start' are
153	* moved to a higher-priority queue.	160	* moved to a higher-priority queue.
154	*/	161	*/
155	void relink_rq(int start)	162	void relink_rq(int start)
156	{	163	{
157	link_t head;	164	link_t head;
158	runq_t *r;	165	runq_t *r;
159	int i, n;	166	int i, n;
160		167
161	list_initialize(&head);	168	list_initialize(&head);
162	spinlock_lock(&CPU->lock);	169	spinlock_lock(&CPU->lock);
163	if (CPU->needs_relink > NEEDS_RELINK_MAX) {	170	if (CPU->needs_relink > NEEDS_RELINK_MAX) {
164	for (i = start; i<RQ_COUNT-1; i++) {	171	for (i = start; i<RQ_COUNT-1; i++) {
165	/* remember and empty rq[i + 1] */	172	/* remember and empty rq[i + 1] */
166	r = &CPU->rq[i + 1];	173	r = &CPU->rq[i + 1];
167	spinlock_lock(&r->lock);	174	spinlock_lock(&r->lock);
168	list_concat(&head, &r->rq_head);	175	list_concat(&head, &r->rq_head);
169	n = r->n;	176	n = r->n;
170	r->n = 0;	177	r->n = 0;
171	spinlock_unlock(&r->lock);	178	spinlock_unlock(&r->lock);
172		179
173	/* append rq[i + 1] to rq[i] */	180	/* append rq[i + 1] to rq[i] */
174	r = &CPU->rq[i];	181	r = &CPU->rq[i];
175	spinlock_lock(&r->lock);	182	spinlock_lock(&r->lock);
176	list_concat(&r->rq_head, &head);	183	list_concat(&r->rq_head, &head);
177	r->n += n;	184	r->n += n;
178	spinlock_unlock(&r->lock);	185	spinlock_unlock(&r->lock);
179	}	186	}
180	CPU->needs_relink = 0;	187	CPU->needs_relink = 0;
181	}	188	}
182	spinlock_unlock(&CPU->lock);	189	spinlock_unlock(&CPU->lock);
183		190
184	}	191	}
185		192
186	/*	193	/*
187	* The scheduler.	194	* The scheduler.
188	*/	195	*/
189	void scheduler(void)	196	void scheduler(void)
190	{	197	{
191	volatile pri_t pri;	198	volatile pri_t pri;
192		199
193	pri = cpu_priority_high();	200	pri = cpu_priority_high();
194		201
195	if (haltstate)	202	if (haltstate)
196	halt();	203	halt();
197		204
198	if (THREAD) {	205	if (THREAD) {
199	spinlock_lock(&THREAD->lock);	206	spinlock_lock(&THREAD->lock);
200	if (!context_save(&THREAD->saved_context)) {	207	if (!context_save(&THREAD->saved_context)) {
201	/*	208	/*
202	* This is the place where threads leave scheduler();	209	* This is the place where threads leave scheduler();
203	*/	210	*/
204	before_thread_runs();	211	before_thread_runs();
205	spinlock_unlock(&THREAD->lock);	212	spinlock_unlock(&THREAD->lock);
206	cpu_priority_restore(THREAD->saved_context.pri);	213	cpu_priority_restore(THREAD->saved_context.pri);
207	return;	214	return;
208	}	215	}
209	THREAD->saved_context.pri = pri;	216	THREAD->saved_context.pri = pri;
210	}	217	}
211		218
212	/*	219	/*
213	* We may not keep the old stack.	220	* We may not keep the old stack.
214	* Reason: If we kept the old stack and got blocked, for instance, in	221	* Reason: If we kept the old stack and got blocked, for instance, in
215	* find_best_thread(), the old thread could get rescheduled by another	222	* find_best_thread(), the old thread could get rescheduled by another
216	* CPU and overwrite the part of its own stack that was also used by	223	* CPU and overwrite the part of its own stack that was also used by
217	* the scheduler on this CPU.	224	* the scheduler on this CPU.
218	*	225	*
219	* Moreover, we have to bypass the compiler-generated POP sequence	226	* Moreover, we have to bypass the compiler-generated POP sequence
220	* which is fooled by SP being set to the very top of the stack.	227	* which is fooled by SP being set to the very top of the stack.
221	* Therefore the scheduler() function continues in	228	* Therefore the scheduler() function continues in
222	* scheduler_separated_stack().	229	* scheduler_separated_stack().
223	*/	230	*/
224	context_save(&CPU->saved_context);	231	context_save(&CPU->saved_context);
225	CPU->saved_context.sp = (__address) &CPU->stack[CPU_STACK_SIZE-8];	232	CPU->saved_context.sp = (__address) &CPU->stack[CPU_STACK_SIZE-8];
226	CPU->saved_context.pc = (__address) scheduler_separated_stack;	233	CPU->saved_context.pc = (__address) scheduler_separated_stack;
227	context_restore(&CPU->saved_context);	234	context_restore(&CPU->saved_context);
228	/* not reached */	235	/* not reached */
229	}	236	}
230		237
231	void scheduler_separated_stack(void)	238	void scheduler_separated_stack(void)
232	{	239	{
233	int priority;	240	int priority;
234		241
235	if (THREAD) {	242	if (THREAD) {
236	switch (THREAD->state) {	243	switch (THREAD->state) {
237	case Running:	244	case Running:
238	THREAD->state = Ready;	245	THREAD->state = Ready;
239	spinlock_unlock(&THREAD->lock);	246	spinlock_unlock(&THREAD->lock);
240	thread_ready(THREAD);	247	thread_ready(THREAD);
241	break;	248	break;
242		249
243	case Exiting:	250	case Exiting:
244	frame_free((__address) THREAD->kstack);	251	frame_free((__address) THREAD->kstack);
245	if (THREAD->ustack) {	252	if (THREAD->ustack) {
246	frame_free((__address) THREAD->ustack);	253	frame_free((__address) THREAD->ustack);
247	}	254	}
248		255
249	/*	256	/*
250	* Detach from the containing task.	257	* Detach from the containing task.
251	*/	258	*/
252	spinlock_lock(&TASK->lock);	259	spinlock_lock(&TASK->lock);
253	list_remove(&THREAD->th_link);	260	list_remove(&THREAD->th_link);
254	spinlock_unlock(&TASK->lock);	261	spinlock_unlock(&TASK->lock);
255		262
256	spinlock_unlock(&THREAD->lock);	263	spinlock_unlock(&THREAD->lock);
257		264
258	spinlock_lock(&threads_lock);	265	spinlock_lock(&threads_lock);
259	list_remove(&THREAD->threads_link);	266	list_remove(&THREAD->threads_link);
260	spinlock_unlock(&threads_lock);	267	spinlock_unlock(&threads_lock);
261		268
262	free(THREAD);	269	free(THREAD);
263		270
264	break;	271	break;
265		272
266	case Sleeping:	273	case Sleeping:
267	/*	274	/*
268	* Prefer the thread after it's woken up.	275	* Prefer the thread after it's woken up.
269	*/	276	*/
270	THREAD->pri = -1;	277	THREAD->pri = -1;
271		278
272	/*	279	/*
273	* We need to release wq->lock which we locked in waitq_sleep().	280	* We need to release wq->lock which we locked in waitq_sleep().
274	* Address of wq->lock is kept in THREAD->sleep_queue.	281	* Address of wq->lock is kept in THREAD->sleep_queue.
275	*/	282	*/
276	spinlock_unlock(&THREAD->sleep_queue->lock);	283	spinlock_unlock(&THREAD->sleep_queue->lock);
277		284
278	/*	285	/*
279	* Check for possible requests for out-of-context invocation.	286	* Check for possible requests for out-of-context invocation.
280	*/	287	*/
281	if (THREAD->call_me) {	288	if (THREAD->call_me) {
282	THREAD->call_me(THREAD->call_me_with);	289	THREAD->call_me(THREAD->call_me_with);
283	THREAD->call_me = NULL;	290	THREAD->call_me = NULL;
284	THREAD->call_me_with = NULL;	291	THREAD->call_me_with = NULL;
285	}	292	}
286		293
287	spinlock_unlock(&THREAD->lock);	294	spinlock_unlock(&THREAD->lock);
288		295
289	break;	296	break;
290		297
291	default:	298	default:
292	/*	299	/*
293	* Entering state is unexpected.	300	* Entering state is unexpected.
294	*/	301	*/
295	panic("tid%d: unexpected state %s\n", THREAD->tid, thread_states[THREAD->state]);	302	panic("tid%d: unexpected state %s\n", THREAD->tid, thread_states[THREAD->state]);
296	break;	303	break;
297	}	304	}
298	THREAD = NULL;	305	THREAD = NULL;
299	}	306	}
300		307
301	THREAD = find_best_thread();	308	THREAD = find_best_thread();
302		309
303	spinlock_lock(&THREAD->lock);	310	spinlock_lock(&THREAD->lock);
304	priority = THREAD->pri;	311	priority = THREAD->pri;
305	spinlock_unlock(&THREAD->lock);	312	spinlock_unlock(&THREAD->lock);
306		313
307	relink_rq(priority);	314	relink_rq(priority);
308		315
309	spinlock_lock(&THREAD->lock);	316	spinlock_lock(&THREAD->lock);
310		317
311	/*	318	/*
312	* If both the old and the new task are the same, lots of work is avoided.	319	* If both the old and the new task are the same, lots of work is avoided.
313	*/	320	*/
314	if (TASK != THREAD->task) {	321	if (TASK != THREAD->task) {
315	vm_t *m1 = NULL;	322	vm_t *m1 = NULL;
316	vm_t *m2;	323	vm_t *m2;
317		324
318	if (TASK) {	325	if (TASK) {
319	spinlock_lock(&TASK->lock);	326	spinlock_lock(&TASK->lock);
320	m1 = TASK->vm;	327	m1 = TASK->vm;
321	spinlock_unlock(&TASK->lock);	328	spinlock_unlock(&TASK->lock);
322	}	329	}
323		330
324	spinlock_lock(&THREAD->task->lock);	331	spinlock_lock(&THREAD->task->lock);
325	m2 = THREAD->task->vm;	332	m2 = THREAD->task->vm;
326	spinlock_unlock(&THREAD->task->lock);	333	spinlock_unlock(&THREAD->task->lock);
327		334
328	/*	335	/*
329	* Note that it is possible for two tasks to share one vm mapping.	336	* Note that it is possible for two tasks to share one vm mapping.
330	*/	337	*/
331	if (m1 != m2) {	338	if (m1 != m2) {
332	/*	339	/*
333	* Both tasks and vm mappings are different.	340	* Both tasks and vm mappings are different.
334	* Replace the old one with the new one.	341	* Replace the old one with the new one.
335	*/	342	*/
336	if (m1) {	343	if (m1) {
337	vm_uninstall(m1);	344	vm_uninstall(m1);
338	}	345	}
339	vm_install(m2);	346	vm_install(m2);
340	}	347	}
341	TASK = THREAD->task;	348	TASK = THREAD->task;
342	}	349	}
343		350
344	THREAD->state = Running;	351	THREAD->state = Running;
345		352
346	#ifdef SCHEDULER_VERBOSE	353	#ifdef SCHEDULER_VERBOSE
347	printf("cpu%d: tid %d (pri=%d,ticks=%d,nrdy=%d)\n", CPU->id, THREAD->tid, THREAD->pri, THREAD->ticks, CPU->nrdy);	354	printf("cpu%d: tid %d (pri=%d,ticks=%d,nrdy=%d)\n", CPU->id, THREAD->tid, THREAD->pri, THREAD->ticks, CPU->nrdy);
348	#endif	355	#endif
349		356
350	context_restore(&THREAD->saved_context);	357	context_restore(&THREAD->saved_context);
351	/* not reached */	358	/* not reached */
352	}	359	}
353		360
354	#ifdef __SMP__	361	#ifdef __SMP__
355	/*	362	/*
356	* This is the load balancing thread.	363	* This is the load balancing thread.
357	* It supervises thread supplies for the CPU it's wired to.	364	* It supervises thread supplies for the CPU it's wired to.
358	*/	365	*/
359	void kcpulb(void *arg)	366	void kcpulb(void *arg)
360	{	367	{
361	thread_t *t;	368	thread_t *t;
362	int count, i, j, k = 0;	369	int count, i, j, k = 0;
363	pri_t pri;	370	pri_t pri;
364		371
365	loop:	372	loop:
366	/*	373	/*
367	* Sleep until there's some work to do.	374	* Sleep until there's some work to do.
368	*/	375	*/
369	waitq_sleep(&CPU->kcpulb_wq);	376	waitq_sleep(&CPU->kcpulb_wq);
370		377
371	not_satisfied:	378	not_satisfied:
372	/*	379	/*
373	* Calculate the number of threads that will be migrated/stolen from	380	* Calculate the number of threads that will be migrated/stolen from
374	* other CPU's. Note that situation can have changed between two	381	* other CPU's. Note that situation can have changed between two
375	* passes. Each time get the most up to date counts.	382	* passes. Each time get the most up to date counts.
376	*/	383	*/
377	pri = cpu_priority_high();	384	pri = cpu_priority_high();
378	spinlock_lock(&CPU->lock);	385	spinlock_lock(&CPU->lock);
379	count = nrdy / config.cpu_active;	386	count = nrdy / config.cpu_active;
380	count -= CPU->nrdy;	387	count -= CPU->nrdy;
381	spinlock_unlock(&CPU->lock);	388	spinlock_unlock(&CPU->lock);
382	cpu_priority_restore(pri);	389	cpu_priority_restore(pri);
383		390
384	if (count <= 0)	391	if (count <= 0)
385	goto satisfied;	392	goto satisfied;
386		393
387	/*	394	/*
388	* Searching least priority queues on all CPU's first and most priority queues on all CPU's last.	395	* Searching least priority queues on all CPU's first and most priority queues on all CPU's last.
389	*/	396	*/
390	for (j=RQ_COUNT-1; j >= 0; j--) {	397	for (j=RQ_COUNT-1; j >= 0; j--) {
391	for (i=0; i < config.cpu_active; i++) {	398	for (i=0; i < config.cpu_active; i++) {
392	link_t *l;	399	link_t *l;
393	runq_t *r;	400	runq_t *r;
394	cpu_t *cpu;	401	cpu_t *cpu;
395		402
396	cpu = &cpus[(i + k) % config.cpu_active];	403	cpu = &cpus[(i + k) % config.cpu_active];
397	r = &cpu->rq[j];	404	r = &cpu->rq[j];
398		405
399	/*	406	/*
400	* Not interested in ourselves.	407	* Not interested in ourselves.
401	* Doesn't require interrupt disabling for kcpulb is X_WIRED.	408	* Doesn't require interrupt disabling for kcpulb is X_WIRED.
402	*/	409	*/
403	if (CPU == cpu)	410	if (CPU == cpu)
404	continue;	411	continue;
405		412
406	restart: pri = cpu_priority_high();	413	restart: pri = cpu_priority_high();
407	spinlock_lock(&r->lock);	414	spinlock_lock(&r->lock);
408	if (r->n == 0) {	415	if (r->n == 0) {
409	spinlock_unlock(&r->lock);	416	spinlock_unlock(&r->lock);
410	cpu_priority_restore(pri);	417	cpu_priority_restore(pri);
411	continue;	418	continue;
412	}	419	}
413		420
414	t = NULL;	421	t = NULL;
415	l = r->rq_head.prev; /* search rq from the back */	422	l = r->rq_head.prev; /* search rq from the back */
416	while (l != &r->rq_head) {	423	while (l != &r->rq_head) {
417	t = list_get_instance(l, thread_t, rq_link);	424	t = list_get_instance(l, thread_t, rq_link);
418	/*	425	/*
419	* We don't want to steal CPU-wired threads neither threads already stolen.	426	* We don't want to steal CPU-wired threads neither threads already stolen.
420	* The latter prevents threads from migrating between CPU's without ever being run.	427	* The latter prevents threads from migrating between CPU's without ever being run.
421	*/	428	*/
422	spinlock_lock(&t->lock);	429	spinlock_lock(&t->lock);
423	if (!(t->flags & (X_WIRED \| X_STOLEN))) {	430	if (!(t->flags & (X_WIRED \| X_STOLEN))) {
424	/*	431	/*
425	* Remove t from r.	432	* Remove t from r.
426	*/	433	*/
427		434
428	spinlock_unlock(&t->lock);	435	spinlock_unlock(&t->lock);
429		436
430	/*	437	/*
431	* Here we have to avoid deadlock with relink_rq(),	438	* Here we have to avoid deadlock with relink_rq(),
432	* because it locks cpu and r in a different order than we do.	439	* because it locks cpu and r in a different order than we do.
433	*/	440	*/
434	if (!spinlock_trylock(&cpu->lock)) {	441	if (!spinlock_trylock(&cpu->lock)) {
435	/* Release all locks and try again. */	442	/* Release all locks and try again. */
436	spinlock_unlock(&r->lock);	443	spinlock_unlock(&r->lock);
437	cpu_priority_restore(pri);	444	cpu_priority_restore(pri);
438	goto restart;	445	goto restart;
439	}	446	}
440	cpu->nrdy--;	447	cpu->nrdy--;
441	spinlock_unlock(&cpu->lock);	448	spinlock_unlock(&cpu->lock);
442		449
443	spinlock_lock(&nrdylock);	450	spinlock_lock(&nrdylock);
444	nrdy--;	451	nrdy--;
445	spinlock_unlock(&nrdylock);	452	spinlock_unlock(&nrdylock);
446		453
447	r->n--;	454	r->n--;
448	list_remove(&t->rq_link);	455	list_remove(&t->rq_link);
449		456
450	break;	457	break;
451	}	458	}
452	spinlock_unlock(&t->lock);	459	spinlock_unlock(&t->lock);
453	l = l->prev;	460	l = l->prev;
454	t = NULL;	461	t = NULL;
455	}	462	}
456	spinlock_unlock(&r->lock);	463	spinlock_unlock(&r->lock);
457		464
458	if (t) {	465	if (t) {
459	/*	466	/*
460	* Ready t on local CPU	467	* Ready t on local CPU
461	*/	468	*/
462	spinlock_lock(&t->lock);	469	spinlock_lock(&t->lock);
463	#ifdef KCPULB_VERBOSE	470	#ifdef KCPULB_VERBOSE
464	printf("kcpulb%d: TID %d -> cpu%d, nrdy=%d, avg=%d\n", CPU->id, t->tid, CPU->id, CPU->nrdy, nrdy / config.cpu_active);	471	printf("kcpulb%d: TID %d -> cpu%d, nrdy=%d, avg=%d\n", CPU->id, t->tid, CPU->id, CPU->nrdy, nrdy / config.cpu_active);
465	#endif	472	#endif
466	t->flags \|= X_STOLEN;	473	t->flags \|= X_STOLEN;
467	spinlock_unlock(&t->lock);	474	spinlock_unlock(&t->lock);
468		475
469	thread_ready(t);	476	thread_ready(t);
470		477
471	cpu_priority_restore(pri);	478	cpu_priority_restore(pri);
472		479
473	if (--count == 0)	480	if (--count == 0)
474	goto satisfied;	481	goto satisfied;
475		482
476	/*	483	/*
477	* We are not satisfied yet, focus on another CPU next time.	484	* We are not satisfied yet, focus on another CPU next time.
478	*/	485	*/
479	k++;	486	k++;
480		487
481	continue;	488	continue;
482	}	489	}
483	cpu_priority_restore(pri);	490	cpu_priority_restore(pri);
484	}	491	}
485	}	492	}
486		493
487	if (CPU->nrdy) {	494	if (CPU->nrdy) {
488	/*	495	/*
489	* Be a little bit light-weight and let migrated threads run.	496	* Be a little bit light-weight and let migrated threads run.
490	*/	497	*/
491	scheduler();	498	scheduler();
492	}	499	}
493	else {	500	else {

Subversion Repositories HelenOS-historic

(root)/kernel/trunk/generic/src/proc/scheduler.c @ 1757 – Rev 22 → 52