1/*
2 * Copyright 2008-2011, Ingo Weinhold, ingo_weinhold@gmx.de.
3 * Copyright 2002-2010, Axel D��rfler, axeld@pinc-software.de.
4 * Copyright 2002, Angelo Mottola, a.mottola@libero.it.
5 * Distributed under the terms of the MIT License.
6 *
7 * Copyright 2001-2002, Travis Geiselbrecht. All rights reserved.
8 * Distributed under the terms of the NewOS License.
9 */
10
11
12/*! The thread scheduler */
13
14
15#include <OS.h>
16
17#include <cpu.h>
18#include <debug.h>
19#include <int.h>
20#include <kernel.h>
21#include <kscheduler.h>
22#include <listeners.h>
23#include <scheduler_defs.h>
24#include <smp.h>
25#include <thread.h>
26#include <timer.h>
27
28#include "scheduler_common.h"
29#include "scheduler_tracing.h"
30
31
32//#define TRACE_SCHEDULER
33#ifdef TRACE_SCHEDULER
34#	define TRACE(x) dprintf_no_syslog x
35#else
36#	define TRACE(x) ;
37#endif
38
39
40const bigtime_t kThreadQuantum = 3000;
41
42
43// The run queue. Holds the threads ready to run ordered by priority.
44static Thread *sRunQueue = NULL;
45static int32 sCPUCount = 1;
46static int32 sNextCPUForSelection = 0;
47
48
49static int
50_rand(void)
51{
52	static int next = 0;
53
54	if (next == 0)
55		next = system_time();
56
57	next = next * 1103515245 + 12345;
58	return (next >> 16) & 0x7FFF;
59}
60
61
62static int
63dump_run_queue(int argc, char **argv)
64{
65	Thread *thread;
66
67	thread = sRunQueue;
68	if (!thread)
69		kprintf("Run queue is empty!\n");
70	else {
71		kprintf("thread    id      priority name\n");
72		while (thread) {
73			kprintf("%p  %-7" B_PRId32 " %-8" B_PRId32 " %s\n", thread,
74				thread->id, thread->priority, thread->name);
75			thread = thread->queue_next;
76		}
77	}
78
79	return 0;
80}
81
82
83static int32
84select_cpu(int32 currentCPU, Thread* thread, int32& targetPriority)
85{
86	if (thread->pinned_to_cpu > 0) {
87		// the thread is pinned to a specific CPU
88		int32 targetCPU = thread->previous_cpu->cpu_num;
89		targetPriority = gCPU[targetCPU].running_thread->priority;
90		return targetCPU;
91	}
92
93	// Choose the CPU running the lowest priority thread. Favor the current CPU
94	// as it doesn't require ICI to be notified.
95	int32 targetCPU = currentCPU;
96	targetPriority = B_IDLE_PRIORITY;
97	if (gCPU[currentCPU].disabled)
98		targetCPU = -1;
99	else
100		targetPriority = gCPU[currentCPU].running_thread->priority;
101
102	int32 cpu = sNextCPUForSelection;
103	for (int32 i = 0; i < sCPUCount; i++, cpu++) {
104		if (cpu >= sCPUCount)
105			cpu = 0;
106
107		if (!gCPU[cpu].disabled) {
108			int32 cpuPriority = gCPU[cpu].running_thread->priority;
109			if (targetCPU < 0 || cpuPriority < targetPriority) {
110				targetCPU = cpu;
111				targetPriority = cpuPriority;
112			}
113		}
114	}
115
116	if (++sNextCPUForSelection >= sCPUCount)
117		sNextCPUForSelection = 0;
118
119	return targetCPU;
120}
121
122
123/*!	Enqueues the thread into the run queue.
124	Note: thread lock must be held when entering this function
125*/
126static void
127enqueue_in_run_queue(Thread *thread)
128{
129	thread->state = thread->next_state = B_THREAD_READY;
130
131	Thread *curr, *prev;
132	for (curr = sRunQueue, prev = NULL; curr
133			&& curr->priority >= thread->next_priority;
134			curr = curr->queue_next) {
135		if (prev)
136			prev = prev->queue_next;
137		else
138			prev = sRunQueue;
139	}
140
141	T(EnqueueThread(thread, prev, curr));
142
143	thread->queue_next = curr;
144	if (prev)
145		prev->queue_next = thread;
146	else
147		sRunQueue = thread;
148
149	thread->next_priority = thread->priority;
150
151	if (thread->priority != B_IDLE_PRIORITY) {
152		// Select a CPU for the thread to run on. It's not certain that the
153		// thread will actually run on it, but we will notify the CPU to
154		// preempt the thread it is currently running, if the new thread has
155		// a higher priority.
156		int32 currentCPU = smp_get_current_cpu();
157		int32 targetPriority;
158		int32 targetCPU = select_cpu(currentCPU, thread, targetPriority);
159
160		// If the target CPU runs a thread with a lower priority, tell it to
161		// reschedule.
162		if (thread->priority > targetPriority) {
163			if (targetCPU == currentCPU) {
164				gCPU[targetCPU].invoke_scheduler = true;
165				gCPU[targetCPU].invoke_scheduler_if_idle = false;
166			} else {
167				if (targetPriority == B_IDLE_PRIORITY) {
168					smp_send_ici(targetCPU, SMP_MSG_RESCHEDULE_IF_IDLE, 0, 0,
169						0, NULL, SMP_MSG_FLAG_ASYNC);
170				} else {
171					smp_send_ici(targetCPU, SMP_MSG_RESCHEDULE, 0, 0, 0, NULL,
172						SMP_MSG_FLAG_ASYNC);
173				}
174			}
175		}
176	}
177
178	// notify listeners
179	NotifySchedulerListeners(&SchedulerListener::ThreadEnqueuedInRunQueue,
180		thread);
181}
182
183
184/*!	Sets the priority of a thread.
185	Note: thread lock must be held when entering this function
186*/
187static void
188set_thread_priority(Thread *thread, int32 priority)
189{
190	if (priority == thread->priority)
191		return;
192
193	if (thread->state != B_THREAD_READY) {
194		thread->priority = priority;
195		return;
196	}
197
198	// The thread is in the run queue. We need to remove it and re-insert it at
199	// a new position.
200
201	T(RemoveThread(thread));
202
203	// notify listeners
204	NotifySchedulerListeners(&SchedulerListener::ThreadRemovedFromRunQueue,
205		thread);
206
207	// find thread in run queue
208	Thread *item, *prev;
209	for (item = sRunQueue, prev = NULL; item && item != thread;
210			item = item->queue_next) {
211		if (prev)
212			prev = prev->queue_next;
213		else
214			prev = sRunQueue;
215	}
216
217	ASSERT(item == thread);
218
219	// remove the thread
220	if (prev)
221		prev->queue_next = item->queue_next;
222	else
223		sRunQueue = item->queue_next;
224
225	// set priority and re-insert
226	thread->priority = thread->next_priority = priority;
227	enqueue_in_run_queue(thread);
228}
229
230
231static bigtime_t
232estimate_max_scheduling_latency(Thread* thread)
233{
234	// TODO: This is probably meant to be called periodically to return the
235	// current estimate depending on the system usage; we return fixed estimates
236	// per thread priority, though.
237
238	if (thread->priority >= B_REAL_TIME_DISPLAY_PRIORITY)
239		return kThreadQuantum / 4;
240	if (thread->priority >= B_DISPLAY_PRIORITY)
241		return kThreadQuantum;
242
243	return 2 * kThreadQuantum;
244}
245
246
247static int32
248reschedule_event(timer *unused)
249{
250	// This function is called as a result of the timer event set by the
251	// scheduler. Make sure the reschedule() is invoked.
252	thread_get_current_thread()->cpu->invoke_scheduler = true;
253	thread_get_current_thread()->cpu->invoke_scheduler_if_idle = false;
254	thread_get_current_thread()->cpu->preempted = 1;
255	return B_HANDLED_INTERRUPT;
256}
257
258
259/*!	Runs the scheduler.
260	Note: expects thread spinlock to be held
261*/
262static void
263reschedule(void)
264{
265	Thread *oldThread = thread_get_current_thread();
266	Thread *nextThread, *prevThread;
267
268	// check whether we're only supposed to reschedule, if the current thread
269	// is idle
270	if (oldThread->cpu->invoke_scheduler) {
271		oldThread->cpu->invoke_scheduler = false;
272		if (oldThread->cpu->invoke_scheduler_if_idle
273			&& oldThread->priority != B_IDLE_PRIORITY) {
274			oldThread->cpu->invoke_scheduler_if_idle = false;
275			return;
276		}
277	}
278
279	TRACE(("reschedule(): cpu %ld, cur_thread = %ld\n", smp_get_current_cpu(),
280		thread_get_current_thread()->id));
281
282	oldThread->state = oldThread->next_state;
283	switch (oldThread->next_state) {
284		case B_THREAD_RUNNING:
285		case B_THREAD_READY:
286			TRACE(("enqueueing thread %ld into run q. pri = %ld\n",
287				oldThread->id, oldThread->priority));
288			enqueue_in_run_queue(oldThread);
289			break;
290		case B_THREAD_SUSPENDED:
291			TRACE(("reschedule(): suspending thread %ld\n", oldThread->id));
292			break;
293		case THREAD_STATE_FREE_ON_RESCHED:
294			break;
295		default:
296			TRACE(("not enqueueing thread %ld into run q. next_state = %ld\n",
297				oldThread->id, oldThread->next_state));
298			break;
299	}
300
301	nextThread = sRunQueue;
302	prevThread = NULL;
303
304	if (oldThread->cpu->disabled) {
305		// CPU is disabled - service any threads we may have that are pinned,
306		// otherwise just select the idle thread
307		while (nextThread != NULL && nextThread->priority > B_IDLE_PRIORITY) {
308			if (nextThread->pinned_to_cpu > 0
309				&& nextThread->previous_cpu == oldThread->cpu)
310				break;
311			prevThread = nextThread;
312			nextThread = nextThread->queue_next;
313		}
314	} else {
315		while (nextThread != NULL) {
316			// select next thread from the run queue
317			// TODO: nextThread cannot really be NULL here, so we should be able
318			// to remove the check, as well as the panic later on.
319			while (nextThread != NULL
320				&& nextThread->priority > B_IDLE_PRIORITY) {
321#if 0
322				if (oldThread == nextThread && nextThread->was_yielded) {
323					// ignore threads that called thread_yield() once
324					nextThread->was_yielded = false;
325					prevThread = nextThread;
326					nextThread = nextThread->queue_next;
327				}
328#endif
329
330				// skip thread, if it doesn't want to run on this CPU
331				if (nextThread->pinned_to_cpu > 0
332					&& nextThread->previous_cpu != oldThread->cpu) {
333					prevThread = nextThread;
334					nextThread = nextThread->queue_next;
335					continue;
336				}
337
338				// always extract real time threads
339				if (nextThread->priority >= B_FIRST_REAL_TIME_PRIORITY)
340					break;
341
342				// find next thread with lower priority
343				Thread *lowerNextThread = nextThread->queue_next;
344				Thread *lowerPrevThread = nextThread;
345				int32 priority = nextThread->priority;
346
347				while (lowerNextThread != NULL
348					&& priority == lowerNextThread->priority) {
349					lowerPrevThread = lowerNextThread;
350					lowerNextThread = lowerNextThread->queue_next;
351				}
352				// never skip last non-idle normal thread
353				if (lowerNextThread == NULL
354					|| lowerNextThread->priority == B_IDLE_PRIORITY)
355					break;
356
357				int32 priorityDiff = priority - lowerNextThread->priority;
358				if (priorityDiff > 15)
359					break;
360
361				// skip normal threads sometimes
362				// (twice as probable per priority level)
363				if ((_rand() >> (15 - priorityDiff)) != 0)
364					break;
365
366				nextThread = lowerNextThread;
367				prevThread = lowerPrevThread;
368			}
369
370			if (nextThread != NULL && nextThread->cpu
371				&& nextThread->cpu->cpu_num != oldThread->cpu->cpu_num) {
372				panic("thread in run queue that's still running on another CPU!\n");
373				// TODO: remove this check completely when we're sure that this
374				// cannot happen anymore.
375				prevThread = nextThread;
376				nextThread = nextThread->queue_next;
377				continue;
378			}
379
380			break;
381		}
382	}
383
384	if (nextThread == NULL)
385		panic("reschedule(): run queue is empty!\n");
386
387	// extract selected thread from the run queue
388	if (prevThread != NULL)
389		prevThread->queue_next = nextThread->queue_next;
390	else
391		sRunQueue = nextThread->queue_next;
392
393	T(ScheduleThread(nextThread, oldThread));
394
395	// notify listeners
396	NotifySchedulerListeners(&SchedulerListener::ThreadScheduled, oldThread,
397		nextThread);
398
399	nextThread->state = B_THREAD_RUNNING;
400	nextThread->next_state = B_THREAD_READY;
401	oldThread->was_yielded = false;
402
403	// track kernel time (user time is tracked in thread_at_kernel_entry())
404	scheduler_update_thread_times(oldThread, nextThread);
405
406	// track CPU activity
407	if (!thread_is_idle_thread(oldThread)) {
408		oldThread->cpu->active_time
409			+= (oldThread->kernel_time - oldThread->cpu->last_kernel_time)
410				+ (oldThread->user_time - oldThread->cpu->last_user_time);
411	}
412
413	if (!thread_is_idle_thread(nextThread)) {
414		oldThread->cpu->last_kernel_time = nextThread->kernel_time;
415		oldThread->cpu->last_user_time = nextThread->user_time;
416	}
417
418	if (nextThread != oldThread || oldThread->cpu->preempted) {
419		bigtime_t quantum = kThreadQuantum;	// TODO: calculate quantum?
420		timer* quantumTimer = &oldThread->cpu->quantum_timer;
421
422		if (!oldThread->cpu->preempted)
423			cancel_timer(quantumTimer);
424
425		oldThread->cpu->preempted = 0;
426		if (!thread_is_idle_thread(nextThread)) {
427			add_timer(quantumTimer, &reschedule_event, quantum,
428				B_ONE_SHOT_RELATIVE_TIMER | B_TIMER_ACQUIRE_SCHEDULER_LOCK);
429		}
430
431		if (nextThread != oldThread)
432			scheduler_switch_thread(oldThread, nextThread);
433	}
434}
435
436
437static status_t
438on_thread_create(Thread* thread, bool idleThread)
439{
440	// do nothing
441	return B_OK;
442}
443
444
445static void
446on_thread_init(Thread* thread)
447{
448	// do nothing
449}
450
451
452static void
453on_thread_destroy(Thread* thread)
454{
455	// do nothing
456}
457
458
459/*!	This starts the scheduler. Must be run in the context of the initial idle
460	thread. Interrupts must be disabled and will be disabled when returning.
461*/
462static void
463start(void)
464{
465	SpinLocker schedulerLocker(gSchedulerLock);
466
467	reschedule();
468}
469
470
471static scheduler_ops kSimpleSMPOps = {
472	enqueue_in_run_queue,
473	reschedule,
474	set_thread_priority,
475	estimate_max_scheduling_latency,
476	on_thread_create,
477	on_thread_init,
478	on_thread_destroy,
479	start
480};
481
482
483// #pragma mark -
484
485
486void
487scheduler_simple_smp_init()
488{
489	sCPUCount = smp_get_num_cpus();
490
491	gScheduler = &kSimpleSMPOps;
492
493	add_debugger_command_etc("run_queue", &dump_run_queue,
494		"List threads in run queue", "\nLists threads in run queue", 0);
495}
496