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