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 <thread.h>
25#include <timer.h>
26
27#include "scheduler_common.h"
28#include "scheduler_tracing.h"
29
30
31//#define TRACE_SCHEDULER
32#ifdef TRACE_SCHEDULER
33#	define TRACE(x) dprintf_no_syslog x
34#else
35#	define TRACE(x) ;
36#endif
37
38
39const bigtime_t kThreadQuantum = 3000;
40
41
42// The run queue. Holds the threads ready to run ordered by priority.
43static Thread *sRunQueue = NULL;
44
45
46static int
47_rand(void)
48{
49	static int next = 0;
50
51	if (next == 0)
52		next = system_time();
53
54	next = next * 1103515245 + 12345;
55	return (next >> 16) & 0x7FFF;
56}
57
58
59static int
60dump_run_queue(int argc, char **argv)
61{
62	Thread *thread;
63
64	thread = sRunQueue;
65	if (!thread)
66		kprintf("Run queue is empty!\n");
67	else {
68		kprintf("thread    id      priority name\n");
69		while (thread) {
70			kprintf("%p  %-7" B_PRId32 " %-8" B_PRId32 " %s\n", thread,
71				thread->id, thread->priority, thread->name);
72			thread = thread->queue_next;
73		}
74	}
75
76	return 0;
77}
78
79
80/*!	Enqueues the thread into the run queue.
81	Note: thread lock must be held when entering this function
82*/
83static void
84simple_enqueue_in_run_queue(Thread *thread)
85{
86	thread->state = thread->next_state = B_THREAD_READY;
87
88	Thread *curr, *prev;
89	for (curr = sRunQueue, prev = NULL; curr
90			&& curr->priority >= thread->next_priority;
91			curr = curr->queue_next) {
92		if (prev)
93			prev = prev->queue_next;
94		else
95			prev = sRunQueue;
96	}
97
98	T(EnqueueThread(thread, prev, curr));
99
100	thread->queue_next = curr;
101	if (prev)
102		prev->queue_next = thread;
103	else
104		sRunQueue = thread;
105
106	thread->next_priority = thread->priority;
107
108	// notify listeners
109	NotifySchedulerListeners(&SchedulerListener::ThreadEnqueuedInRunQueue,
110		thread);
111
112	if (thread->priority > thread_get_current_thread()->priority) {
113		gCPU[0].invoke_scheduler = true;
114		gCPU[0].invoke_scheduler_if_idle = false;
115	}
116}
117
118
119/*!	Sets the priority of a thread.
120	Note: thread lock must be held when entering this function
121*/
122static void
123simple_set_thread_priority(Thread *thread, int32 priority)
124{
125	if (priority == thread->priority)
126		return;
127
128	if (thread->state != B_THREAD_READY) {
129		thread->priority = priority;
130		return;
131	}
132
133	// The thread is in the run queue. We need to remove it and re-insert it at
134	// a new position.
135
136	T(RemoveThread(thread));
137
138	// notify listeners
139	NotifySchedulerListeners(&SchedulerListener::ThreadRemovedFromRunQueue,
140		thread);
141
142	// find thread in run queue
143	Thread *item, *prev;
144	for (item = sRunQueue, prev = NULL; item && item != thread;
145			item = item->queue_next) {
146		if (prev)
147			prev = prev->queue_next;
148		else
149			prev = sRunQueue;
150	}
151
152	ASSERT(item == thread);
153
154	// remove the thread
155	if (prev)
156		prev->queue_next = item->queue_next;
157	else
158		sRunQueue = item->queue_next;
159
160	// set priority and re-insert
161	thread->priority = thread->next_priority = priority;
162	simple_enqueue_in_run_queue(thread);
163}
164
165
166static bigtime_t
167simple_estimate_max_scheduling_latency(Thread* thread)
168{
169	// TODO: This is probably meant to be called periodically to return the
170	// current estimate depending on the system usage; we return fixed estimates
171	// per thread priority, though.
172
173	if (thread->priority >= B_REAL_TIME_DISPLAY_PRIORITY)
174		return kThreadQuantum / 4;
175	if (thread->priority >= B_DISPLAY_PRIORITY)
176		return kThreadQuantum;
177
178	return 2 * kThreadQuantum;
179}
180
181
182static int32
183reschedule_event(timer *unused)
184{
185	// This function is called as a result of the timer event set by the
186	// scheduler. Make sure the reschedule() is invoked.
187	thread_get_current_thread()->cpu->invoke_scheduler = true;
188	thread_get_current_thread()->cpu->invoke_scheduler_if_idle = false;
189	thread_get_current_thread()->cpu->preempted = 1;
190	return B_HANDLED_INTERRUPT;
191}
192
193
194/*!	Runs the scheduler.
195	Note: expects thread spinlock to be held
196*/
197static void
198simple_reschedule(void)
199{
200	Thread *oldThread = thread_get_current_thread();
201	Thread *nextThread, *prevThread;
202
203	// check whether we're only supposed to reschedule, if the current thread
204	// is idle
205	if (oldThread->cpu->invoke_scheduler) {
206		oldThread->cpu->invoke_scheduler = false;
207		if (oldThread->cpu->invoke_scheduler_if_idle
208			&& oldThread->priority != B_IDLE_PRIORITY) {
209			oldThread->cpu->invoke_scheduler_if_idle = false;
210			return;
211		}
212	}
213
214	TRACE(("reschedule(): current thread = %ld\n", oldThread->id));
215
216	oldThread->state = oldThread->next_state;
217	switch (oldThread->next_state) {
218		case B_THREAD_RUNNING:
219		case B_THREAD_READY:
220			TRACE(("enqueueing thread %ld into run queue priority = %ld\n",
221				oldThread->id, oldThread->priority));
222			simple_enqueue_in_run_queue(oldThread);
223			break;
224		case B_THREAD_SUSPENDED:
225			TRACE(("reschedule(): suspending thread %ld\n", oldThread->id));
226			break;
227		case THREAD_STATE_FREE_ON_RESCHED:
228			break;
229		default:
230			TRACE(("not enqueueing thread %ld into run queue next_state = %ld\n",
231				oldThread->id, oldThread->next_state));
232			break;
233	}
234
235	nextThread = sRunQueue;
236	prevThread = NULL;
237
238	while (nextThread) {
239		// select next thread from the run queue
240		while (nextThread && nextThread->priority > B_IDLE_PRIORITY) {
241#if 0
242			if (oldThread == nextThread && nextThread->was_yielded) {
243				// ignore threads that called thread_yield() once
244				nextThread->was_yielded = false;
245				prevThread = nextThread;
246				nextThread = nextThread->queue_next;
247			}
248#endif
249
250			// always extract real time threads
251			if (nextThread->priority >= B_FIRST_REAL_TIME_PRIORITY)
252				break;
253
254			// find next thread with lower priority
255			Thread *lowerNextThread = nextThread->queue_next;
256			Thread *lowerPrevThread = nextThread;
257			int32 priority = nextThread->priority;
258
259			while (lowerNextThread != NULL
260				&& priority == lowerNextThread->priority) {
261				lowerPrevThread = lowerNextThread;
262				lowerNextThread = lowerNextThread->queue_next;
263			}
264			// never skip last non-idle normal thread
265			if (lowerNextThread == NULL
266				|| lowerNextThread->priority == B_IDLE_PRIORITY)
267				break;
268
269			int32 priorityDiff = priority - lowerNextThread->priority;
270			if (priorityDiff > 15)
271				break;
272
273			// skip normal threads sometimes
274			// (twice as probable per priority level)
275			if ((_rand() >> (15 - priorityDiff)) != 0)
276				break;
277
278			nextThread = lowerNextThread;
279			prevThread = lowerPrevThread;
280		}
281
282		break;
283	}
284
285	if (!nextThread)
286		panic("reschedule(): run queue is empty!\n");
287
288	// extract selected thread from the run queue
289	if (prevThread)
290		prevThread->queue_next = nextThread->queue_next;
291	else
292		sRunQueue = nextThread->queue_next;
293
294	T(ScheduleThread(nextThread, oldThread));
295
296	// notify listeners
297	NotifySchedulerListeners(&SchedulerListener::ThreadScheduled,
298		oldThread, nextThread);
299
300	nextThread->state = B_THREAD_RUNNING;
301	nextThread->next_state = B_THREAD_READY;
302	oldThread->was_yielded = false;
303
304	// track kernel time (user time is tracked in thread_at_kernel_entry())
305	scheduler_update_thread_times(oldThread, nextThread);
306
307	// track CPU activity
308	if (!thread_is_idle_thread(oldThread)) {
309		oldThread->cpu->active_time +=
310			(oldThread->kernel_time - oldThread->cpu->last_kernel_time)
311			+ (oldThread->user_time - oldThread->cpu->last_user_time);
312	}
313
314	if (!thread_is_idle_thread(nextThread)) {
315		oldThread->cpu->last_kernel_time = nextThread->kernel_time;
316		oldThread->cpu->last_user_time = nextThread->user_time;
317	}
318
319	if (nextThread != oldThread || oldThread->cpu->preempted) {
320		bigtime_t quantum = kThreadQuantum;	// TODO: calculate quantum?
321		timer* quantumTimer = &oldThread->cpu->quantum_timer;
322
323		if (!oldThread->cpu->preempted)
324			cancel_timer(quantumTimer);
325
326		oldThread->cpu->preempted = 0;
327		if (!thread_is_idle_thread(nextThread)) {
328			add_timer(quantumTimer, &reschedule_event, quantum,
329				B_ONE_SHOT_RELATIVE_TIMER | B_TIMER_ACQUIRE_SCHEDULER_LOCK);
330		}
331
332		if (nextThread != oldThread)
333			scheduler_switch_thread(oldThread, nextThread);
334	}
335}
336
337
338static status_t
339simple_on_thread_create(Thread* thread, bool idleThread)
340{
341	// do nothing
342	return B_OK;
343}
344
345
346static void
347simple_on_thread_init(Thread* thread)
348{
349	// do nothing
350}
351
352
353static void
354simple_on_thread_destroy(Thread* thread)
355{
356	// do nothing
357}
358
359
360/*!	This starts the scheduler. Must be run in the context of the initial idle
361	thread. Interrupts must be disabled and will be disabled when returning.
362*/
363static void
364simple_start(void)
365{
366	SpinLocker schedulerLocker(gSchedulerLock);
367
368	simple_reschedule();
369}
370
371
372static scheduler_ops kSimpleOps = {
373	simple_enqueue_in_run_queue,
374	simple_reschedule,
375	simple_set_thread_priority,
376	simple_estimate_max_scheduling_latency,
377	simple_on_thread_create,
378	simple_on_thread_init,
379	simple_on_thread_destroy,
380	simple_start
381};
382
383
384// #pragma mark -
385
386
387void
388scheduler_simple_init()
389{
390	gScheduler = &kSimpleOps;
391
392	add_debugger_command_etc("run_queue", &dump_run_queue,
393		"List threads in run queue", "\nLists threads in run queue", 0);
394}
395