1 7966faa9 2004-09-23 devnull /*
  2 7966faa9 2004-09-23 devnull  * Thread scheduler.
  3 7966faa9 2004-09-23 devnull  */
  4 cd7ddc9b 2003-11-23 devnull #include "threadimpl.h"
  5 76193d7c 2003-09-30 devnull 
  6 7966faa9 2004-09-23 devnull static Thread *runthread(Proc*);
  7 7966faa9 2004-09-23 devnull static void schedexit(Proc*);
  8 76193d7c 2003-09-30 devnull 
  9 7966faa9 2004-09-23 devnull /*
 10 7966faa9 2004-09-23 devnull  * Main scheduling loop.
 11 7966faa9 2004-09-23 devnull  */
 12 76193d7c 2003-09-30 devnull void
 13 7966faa9 2004-09-23 devnull _threadscheduler(void *arg)
 14 76193d7c 2003-09-30 devnull {
 15 76193d7c 2003-09-30 devnull 	Proc *p;
 16 76193d7c 2003-09-30 devnull 	Thread *t;
 17 c6687d45 2004-09-21 devnull 
 18 76193d7c 2003-09-30 devnull 	p = arg;
 19 c6687d45 2004-09-21 devnull 
 20 7966faa9 2004-09-23 devnull 	_threadlinkmain();
 21 19564553 2004-11-08 devnull 	_threadsetproc(p);
 22 7966faa9 2004-09-23 devnull 
 23 c6687d45 2004-09-21 devnull 	for(;;){
 24 7966faa9 2004-09-23 devnull 		/* 
 25 7966faa9 2004-09-23 devnull 		 * Clean up zombie children.
 26 7966faa9 2004-09-23 devnull 		 */
 27 7966faa9 2004-09-23 devnull 
 28 7966faa9 2004-09-23 devnull 		/*
 29 7966faa9 2004-09-23 devnull 		 * Find next thread to run.
 30 7966faa9 2004-09-23 devnull 		 */
 31 7966faa9 2004-09-23 devnull 		_threaddebug(DBGSCHED, "runthread");
 32 c6687d45 2004-09-21 devnull 		t = runthread(p);
 33 7966faa9 2004-09-23 devnull 		if(t == nil)
 34 7966faa9 2004-09-23 devnull 			schedexit(p);
 35 7966faa9 2004-09-23 devnull 	
 36 7966faa9 2004-09-23 devnull 		/*
 37 7966faa9 2004-09-23 devnull 		 * If it's ready, run it (might instead be marked to die).
 38 7966faa9 2004-09-23 devnull 		 */
 39 7966faa9 2004-09-23 devnull 		lock(&p->lock);
 40 7966faa9 2004-09-23 devnull 		if(t->state == Ready){
 41 7966faa9 2004-09-23 devnull 			_threaddebug(DBGSCHED, "running %d.%d", p->id, t->id);
 42 7966faa9 2004-09-23 devnull 			t->state = Running;
 43 7966faa9 2004-09-23 devnull 			t->nextstate = Ready;
 44 7966faa9 2004-09-23 devnull 			p->thread = t;
 45 7966faa9 2004-09-23 devnull 			unlock(&p->lock);
 46 7966faa9 2004-09-23 devnull 			_swaplabel(&p->context, &t->context);
 47 7966faa9 2004-09-23 devnull 			lock(&p->lock);
 48 7966faa9 2004-09-23 devnull 			p->thread = nil;
 49 c6687d45 2004-09-21 devnull 		}
 50 c6687d45 2004-09-21 devnull 
 51 7966faa9 2004-09-23 devnull 		/*
 52 7966faa9 2004-09-23 devnull 		 * If thread needs to die, kill it.
 53 5093c3fa 2004-10-22 devnull 		 * t->proc == p may not be true if we're
 54 5093c3fa 2004-10-22 devnull 		 * trying to jump into the exec proc (see exec-unix.c).
 55 7966faa9 2004-09-23 devnull 		 */
 56 76193d7c 2003-09-30 devnull 		if(t->moribund){
 57 7966faa9 2004-09-23 devnull 			_threaddebug(DBGSCHED, "moribund %d.%d", p->id, t->id);
 58 5093c3fa 2004-10-22 devnull 			if(t->moribund != 1)
 59 5093c3fa 2004-10-22 devnull 				print("moribund broke %p %d\n", &t->moribund, t->moribund);
 60 76193d7c 2003-09-30 devnull 			assert(t->moribund == 1);
 61 76193d7c 2003-09-30 devnull 			t->state = Dead;
 62 5093c3fa 2004-10-22 devnull 			_procdelthread(p, t);
 63 76193d7c 2003-09-30 devnull 			unlock(&p->lock);
 64 7966faa9 2004-09-23 devnull 			_threadfree(t);
 65 76193d7c 2003-09-30 devnull 			t = nil;
 66 c6687d45 2004-09-21 devnull 			continue;
 67 76193d7c 2003-09-30 devnull 		}
 68 5093c3fa 2004-10-22 devnull 
 69 5093c3fa 2004-10-22 devnull 		/*
 70 5093c3fa 2004-10-22 devnull 		 * If the thread has asked to move to another proc,
 71 5093c3fa 2004-10-22 devnull 		 * let it go (only to be used in *very* special situations).
 72 5093c3fa 2004-10-22 devnull 		if(t->nextproc != p)
 73 5093c3fa 2004-10-22 devnull 			_procdelthread(p, t);
 74 5093c3fa 2004-10-22 devnull 		 */
 75 5093c3fa 2004-10-22 devnull 
 76 7966faa9 2004-09-23 devnull 		unlock(&p->lock);
 77 7966faa9 2004-09-23 devnull 
 78 7966faa9 2004-09-23 devnull 		/*
 79 5093c3fa 2004-10-22 devnull 		 * If the thread has asked to move to another proc,
 80 5093c3fa 2004-10-22 devnull 		 * add it to the new proc.
 81 5093c3fa 2004-10-22 devnull 		 */
 82 5093c3fa 2004-10-22 devnull 		if(t->nextproc != p){
 83 5093c3fa 2004-10-22 devnull 		//	lock(&t->nextproc->lock);
 84 5093c3fa 2004-10-22 devnull 		//	_procaddthread(t->nextproc, t);
 85 5093c3fa 2004-10-22 devnull 		//	unlock(&t->nextproc->lock);
 86 5093c3fa 2004-10-22 devnull 			t->proc = t->nextproc;
 87 5093c3fa 2004-10-22 devnull 		}
 88 5093c3fa 2004-10-22 devnull 
 89 5093c3fa 2004-10-22 devnull 		/*
 90 7966faa9 2004-09-23 devnull 		 * If there is a request to run a function on the 
 91 7966faa9 2004-09-23 devnull 		 * scheduling stack, do so.
 92 7966faa9 2004-09-23 devnull 		 */
 93 7966faa9 2004-09-23 devnull 		if(p->schedfn){
 94 7966faa9 2004-09-23 devnull 			_threaddebug(DBGSCHED, "schedfn");
 95 7966faa9 2004-09-23 devnull 			p->schedfn(p);
 96 7966faa9 2004-09-23 devnull 			p->schedfn = nil;
 97 7966faa9 2004-09-23 devnull 			_threaddebug(DBGSCHED, "schedfn ended");
 98 76193d7c 2003-09-30 devnull 		}
 99 7966faa9 2004-09-23 devnull 
100 7966faa9 2004-09-23 devnull 		/*
101 7966faa9 2004-09-23 devnull 		 * Move the thread along.
102 7966faa9 2004-09-23 devnull 		 */
103 76193d7c 2003-09-30 devnull 		t->state = t->nextstate;
104 5093c3fa 2004-10-22 devnull 		_threaddebug(DBGSCHED, "moveon %d.%d", t->proc->id, t->id);
105 76193d7c 2003-09-30 devnull 		if(t->state == Ready)
106 76193d7c 2003-09-30 devnull 			_threadready(t);
107 76193d7c 2003-09-30 devnull 	}
108 c6687d45 2004-09-21 devnull }
109 c6687d45 2004-09-21 devnull 
110 7966faa9 2004-09-23 devnull /*
111 7966faa9 2004-09-23 devnull  * Called by thread to give up control of processor to scheduler.
112 7966faa9 2004-09-23 devnull  */
113 c6687d45 2004-09-21 devnull int
114 c6687d45 2004-09-21 devnull _sched(void)
115 c6687d45 2004-09-21 devnull {
116 c6687d45 2004-09-21 devnull 	Proc *p;
117 c6687d45 2004-09-21 devnull 	Thread *t;
118 c6687d45 2004-09-21 devnull 
119 c6687d45 2004-09-21 devnull 	p = _threadgetproc();
120 c6687d45 2004-09-21 devnull 	t = p->thread;
121 c6687d45 2004-09-21 devnull 	assert(t != nil);
122 7966faa9 2004-09-23 devnull 	_swaplabel(&t->context, &p->context);
123 c6687d45 2004-09-21 devnull 	return p->nsched++;
124 76193d7c 2003-09-30 devnull }
125 76193d7c 2003-09-30 devnull 
126 7966faa9 2004-09-23 devnull /*
127 7966faa9 2004-09-23 devnull  * Called by thread to yield the processor to other threads.
128 7966faa9 2004-09-23 devnull  * Returns number of other threads run between call and return.
129 7966faa9 2004-09-23 devnull  */
130 7966faa9 2004-09-23 devnull int
131 7966faa9 2004-09-23 devnull yield(void)
132 7966faa9 2004-09-23 devnull {
133 7966faa9 2004-09-23 devnull 	Proc *p;
134 7966faa9 2004-09-23 devnull 	int nsched;
135 7966faa9 2004-09-23 devnull 
136 7966faa9 2004-09-23 devnull 	p = _threadgetproc();
137 7966faa9 2004-09-23 devnull 	nsched = p->nsched;
138 7966faa9 2004-09-23 devnull 	return _sched() - nsched;
139 7966faa9 2004-09-23 devnull }
140 7966faa9 2004-09-23 devnull 
141 7966faa9 2004-09-23 devnull /*
142 7966faa9 2004-09-23 devnull  * Choose the next thread to run.
143 7966faa9 2004-09-23 devnull  */
144 50e628cb 2003-11-23 devnull static Thread*
145 76193d7c 2003-09-30 devnull runthread(Proc *p)
146 76193d7c 2003-09-30 devnull {
147 76193d7c 2003-09-30 devnull 	Thread *t;
148 76193d7c 2003-09-30 devnull 	Tqueue *q;
149 76193d7c 2003-09-30 devnull 
150 7966faa9 2004-09-23 devnull 	/*
151 7966faa9 2004-09-23 devnull 	 * No threads left?
152 7966faa9 2004-09-23 devnull 	 */
153 e97ceade 2003-12-06 devnull 	if(p->nthreads==0 || (p->nthreads==1 && p->idle))
154 76193d7c 2003-09-30 devnull 		return nil;
155 7966faa9 2004-09-23 devnull 
156 19564553 2004-11-08 devnull 	_threadschednote();
157 76193d7c 2003-09-30 devnull 	lock(&p->readylock);
158 7966faa9 2004-09-23 devnull 	q = &p->ready;
159 65de82a3 2004-06-09 devnull 	if(q->head == nil){
160 7966faa9 2004-09-23 devnull 		/*
161 7966faa9 2004-09-23 devnull 		 * Is this a single-process program with an idle thread?
162 7966faa9 2004-09-23 devnull 		 */
163 e97ceade 2003-12-06 devnull 		if(p->idle){
164 7966faa9 2004-09-23 devnull 			/*
165 7966faa9 2004-09-23 devnull 			 * The idle thread had better be ready!
166 7966faa9 2004-09-23 devnull 			 */
167 7966faa9 2004-09-23 devnull 			if(p->idle->state != Ready)
168 7966faa9 2004-09-23 devnull 				sysfatal("all threads are asleep");
169 7966faa9 2004-09-23 devnull 
170 7966faa9 2004-09-23 devnull 			/*
171 7966faa9 2004-09-23 devnull 			 * Run the idle thread.
172 7966faa9 2004-09-23 devnull 			 */
173 e97ceade 2003-12-06 devnull 			unlock(&p->readylock);
174 32f69c36 2003-12-11 devnull 			_threaddebug(DBGSCHED, "running idle thread", p->nthreads);
175 e97ceade 2003-12-06 devnull 			return p->idle;
176 e97ceade 2003-12-06 devnull 		}
177 e97ceade 2003-12-06 devnull 
178 7966faa9 2004-09-23 devnull 		/*
179 7966faa9 2004-09-23 devnull 		 * Wait until one of our threads is readied (by another proc!).
180 7966faa9 2004-09-23 devnull 		 */
181 32f69c36 2003-12-11 devnull 		q->asleep = 1;
182 bcf527a9 2004-09-17 devnull 		p->rend.l = &p->readylock;
183 19564553 2004-11-08 devnull 		while(q->asleep){
184 19564553 2004-11-08 devnull 			_procsleep(&p->rend);
185 19564553 2004-11-08 devnull 			_threadschednote();
186 19564553 2004-11-08 devnull 		}
187 7966faa9 2004-09-23 devnull 
188 7966faa9 2004-09-23 devnull 		/*
189 7966faa9 2004-09-23 devnull 		 * Maybe we were awakened to exit?
190 7966faa9 2004-09-23 devnull 		 */
191 ba15d71b 2004-10-22 devnull 		if(_threadexitsallstatus){
192 ba15d71b 2004-10-22 devnull 			_threaddebug(DBGSCHED, "time to exit");
193 bcf527a9 2004-09-17 devnull 			_exits(_threadexitsallstatus);
194 ba15d71b 2004-10-22 devnull 		}
195 7966faa9 2004-09-23 devnull 		assert(q->head != nil);
196 76193d7c 2003-09-30 devnull 	}
197 7966faa9 2004-09-23 devnull 
198 76193d7c 2003-09-30 devnull 	t = q->head;
199 76193d7c 2003-09-30 devnull 	q->head = t->next;
200 76193d7c 2003-09-30 devnull 	unlock(&p->readylock);
201 7966faa9 2004-09-23 devnull 
202 76193d7c 2003-09-30 devnull 	return t;
203 fb36ed82 2004-04-21 devnull }
204 fb36ed82 2004-04-21 devnull 
205 7966faa9 2004-09-23 devnull /*
206 7966faa9 2004-09-23 devnull  * Add a newly-ready thread to its proc's run queue.
207 7966faa9 2004-09-23 devnull  */
208 76193d7c 2003-09-30 devnull void
209 76193d7c 2003-09-30 devnull _threadready(Thread *t)
210 76193d7c 2003-09-30 devnull {
211 76193d7c 2003-09-30 devnull 	Tqueue *q;
212 76193d7c 2003-09-30 devnull 
213 7966faa9 2004-09-23 devnull 	/*
214 7966faa9 2004-09-23 devnull 	 * The idle thread does not go on the run queue.
215 7966faa9 2004-09-23 devnull 	 */
216 32f69c36 2003-12-11 devnull 	if(t == t->proc->idle){
217 32f69c36 2003-12-11 devnull 		_threaddebug(DBGSCHED, "idle thread is ready");
218 e97ceade 2003-12-06 devnull 		return;
219 32f69c36 2003-12-11 devnull 	}
220 e97ceade 2003-12-06 devnull 
221 76193d7c 2003-09-30 devnull 	assert(t->state == Ready);
222 7966faa9 2004-09-23 devnull 	_threaddebug(DBGSCHED, "readying %d.%d", t->proc->id, t->id);
223 7966faa9 2004-09-23 devnull 
224 7966faa9 2004-09-23 devnull 	/*
225 7966faa9 2004-09-23 devnull 	 * Add thread to run queue.
226 7966faa9 2004-09-23 devnull 	 */
227 76193d7c 2003-09-30 devnull 	q = &t->proc->ready;
228 76193d7c 2003-09-30 devnull 	lock(&t->proc->readylock);
229 7966faa9 2004-09-23 devnull 
230 76193d7c 2003-09-30 devnull 	t->next = nil;
231 7966faa9 2004-09-23 devnull 	if(q->head == nil)
232 76193d7c 2003-09-30 devnull 		q->head = t;
233 76193d7c 2003-09-30 devnull 	else
234 76193d7c 2003-09-30 devnull 		q->tail->next = t;
235 76193d7c 2003-09-30 devnull 	q->tail = t;
236 7966faa9 2004-09-23 devnull 
237 7966faa9 2004-09-23 devnull 	/*
238 7966faa9 2004-09-23 devnull 	 * Wake proc scheduler if it is sleeping.
239 7966faa9 2004-09-23 devnull 	 */
240 76193d7c 2003-09-30 devnull 	if(q->asleep){
241 cd7ddc9b 2003-11-23 devnull 		assert(q->asleep == 1);
242 76193d7c 2003-09-30 devnull 		q->asleep = 0;
243 bcf527a9 2004-09-17 devnull 		_procwakeup(&t->proc->rend);
244 bcf527a9 2004-09-17 devnull 	}
245 bcf527a9 2004-09-17 devnull 	unlock(&t->proc->readylock);
246 76193d7c 2003-09-30 devnull }
247 76193d7c 2003-09-30 devnull 
248 7966faa9 2004-09-23 devnull /*
249 7966faa9 2004-09-23 devnull  * Mark the given thread as the idle thread.
250 7966faa9 2004-09-23 devnull  * Since the idle thread was just created, it is sitting
251 7966faa9 2004-09-23 devnull  * somewhere on the ready queue.
252 7966faa9 2004-09-23 devnull  */
253 76193d7c 2003-09-30 devnull void
254 7966faa9 2004-09-23 devnull _threadsetidle(int id)
255 e97ceade 2003-12-06 devnull {
256 e97ceade 2003-12-06 devnull 	Tqueue *q;
257 7966faa9 2004-09-23 devnull 	Thread *t, **l, *last;
258 e97ceade 2003-12-06 devnull 	Proc *p;
259 e97ceade 2003-12-06 devnull 
260 e97ceade 2003-12-06 devnull 	p = _threadgetproc();
261 7966faa9 2004-09-23 devnull 
262 e97ceade 2003-12-06 devnull 	lock(&p->readylock);
263 e97ceade 2003-12-06 devnull 
264 7966faa9 2004-09-23 devnull 	/*
265 7966faa9 2004-09-23 devnull 	 * Find thread on ready queue.
266 7966faa9 2004-09-23 devnull 	 */
267 7966faa9 2004-09-23 devnull 	q = &p->ready;
268 7966faa9 2004-09-23 devnull 	for(l=&q->head, last=nil; (t=*l) != nil; l=&t->next, last=t)
269 7966faa9 2004-09-23 devnull 		if(t->id == id)
270 7966faa9 2004-09-23 devnull 			break;
271 7966faa9 2004-09-23 devnull 	assert(t != nil);
272 c4097c29 2004-05-11 devnull 
273 7966faa9 2004-09-23 devnull 	/* 
274 7966faa9 2004-09-23 devnull 	 * Remove it from ready queue.
275 7966faa9 2004-09-23 devnull 	 */
276 7966faa9 2004-09-23 devnull 	*l = t->next;
277 7966faa9 2004-09-23 devnull 	if(t == q->head)
278 7966faa9 2004-09-23 devnull 		q->head = t->next;
279 7966faa9 2004-09-23 devnull 	if(t->next == nil)
280 7966faa9 2004-09-23 devnull 		q->tail = last;
281 7966faa9 2004-09-23 devnull 
282 7966faa9 2004-09-23 devnull 	/*
283 7966faa9 2004-09-23 devnull 	 * Set as idle thread.
284 7966faa9 2004-09-23 devnull 	 */
285 7966faa9 2004-09-23 devnull 	p->idle = t;
286 7966faa9 2004-09-23 devnull 	_threaddebug(DBGSCHED, "p->idle is %d\n", t->id);
287 7966faa9 2004-09-23 devnull 	unlock(&p->readylock);
288 76193d7c 2003-09-30 devnull }
289 02a1a5c1 2004-03-05 devnull 
290 19564553 2004-11-08 devnull /*
291 19564553 2004-11-08 devnull  * Mark proc as internal so that if all but internal procs exit, we exit.
292 19564553 2004-11-08 devnull  */
293 19564553 2004-11-08 devnull void
294 19564553 2004-11-08 devnull _threadinternalproc(void)
295 19564553 2004-11-08 devnull {
296 19564553 2004-11-08 devnull 	Proc *p;
297 19564553 2004-11-08 devnull 
298 19564553 2004-11-08 devnull 	p = _threadgetproc();
299 19564553 2004-11-08 devnull 	if(p->internal)
300 19564553 2004-11-08 devnull 		return;
301 19564553 2004-11-08 devnull 	lock(&_threadpq.lock);
302 19564553 2004-11-08 devnull 	if(p->internal == 0){
303 19564553 2004-11-08 devnull 		p->internal = 1;
304 19564553 2004-11-08 devnull 		--_threadnprocs;
305 19564553 2004-11-08 devnull 	}
306 19564553 2004-11-08 devnull 	unlock(&_threadpq.lock);
307 19564553 2004-11-08 devnull }
308 19564553 2004-11-08 devnull 
309 7966faa9 2004-09-23 devnull static void
310 7966faa9 2004-09-23 devnull schedexit(Proc *p)
311 02a1a5c1 2004-03-05 devnull {
312 7966faa9 2004-09-23 devnull 	char ex[ERRMAX];
313 7966faa9 2004-09-23 devnull 	int n;
314 7966faa9 2004-09-23 devnull 	Proc **l;
315 76193d7c 2003-09-30 devnull 
316 7966faa9 2004-09-23 devnull 	_threaddebug(DBGSCHED, "exiting proc %d", p->id);
317 7966faa9 2004-09-23 devnull 	lock(&_threadpq.lock);
318 7966faa9 2004-09-23 devnull 	for(l=&_threadpq.head; *l; l=&(*l)->next){
319 7966faa9 2004-09-23 devnull 		if(*l == p){
320 7966faa9 2004-09-23 devnull 			*l = p->next;
321 7966faa9 2004-09-23 devnull 			if(*l == nil)
322 7966faa9 2004-09-23 devnull 				_threadpq.tail = l;
323 7966faa9 2004-09-23 devnull 			break;
324 7966faa9 2004-09-23 devnull 		}
325 7966faa9 2004-09-23 devnull 	}
326 19564553 2004-11-08 devnull 	if(p->internal)
327 19564553 2004-11-08 devnull 		n = _threadnprocs;
328 19564553 2004-11-08 devnull 	else
329 19564553 2004-11-08 devnull 		n = --_threadnprocs;
330 7966faa9 2004-09-23 devnull 	unlock(&_threadpq.lock);
331 7966faa9 2004-09-23 devnull 
332 7966faa9 2004-09-23 devnull 	strncpy(ex, p->exitstr, sizeof ex);
333 7966faa9 2004-09-23 devnull 	ex[sizeof ex-1] = '\0';
334 7966faa9 2004-09-23 devnull 	free(p);
335 ba15d71b 2004-10-22 devnull 	if(n == 0){
336 ba15d71b 2004-10-22 devnull 		_threaddebug(DBGSCHED, "procexit; no more procs");
337 19564553 2004-11-08 devnull 		_kthreadexitallproc(ex);
338 ba15d71b 2004-10-22 devnull 	}else{
339 ba15d71b 2004-10-22 devnull 		_threaddebug(DBGSCHED, "procexit");
340 19564553 2004-11-08 devnull 		_kthreadexitproc(ex);
341 ba15d71b 2004-10-22 devnull 	}
342 02a1a5c1 2004-03-05 devnull }
343 7966faa9 2004-09-23 devnull