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