/* * kernel/sched.c * * Kernel scheduler and related syscalls * * Copyright (C) 1991-2002 Linus Torvalds * * 1996-12-23 Modified by Dave Grothe to fix bugs in semaphores and * make semaphores SMP safe * 1998-11-19 Implemented schedule_timeout() and related stuff * by Andrea Arcangeli * 2002-01-04 New ultra-scalable O(1) scheduler by Ingo Molnar: * hybrid priority-list and round-robin design with * an array-switch method of distributing timeslices * and per-CPU runqueues. Cleanups and useful suggestions * by Davide Libenzi, preemptible kernel bits by Robert Love. * 2003-09-03 Interactivity tuning by Con Kolivas. * 2004-04-02 Scheduler domains code by Nick Piggin */
/** * radix_tree_insert - insert into a radix tree * @root: radix tree root * @index: index key * @item: item to insert * * Insert an item into the radix tree at position @index. */ intradix_tree_insert(struct radix_tree_root *root, unsignedlong index, void *item) { structradix_tree_node *node =NULL, *slot; unsignedint height, shift; int offset; int error;
/* Make sure the tree is high enough. */ if ((!index && !root->rnode) || index > radix_tree_maxindex(root->height)) { error = radix_tree_extend(root, index); if (error) return error; }
/* * This is the main, per-CPU runqueue data structure. * * Locking rule: those places that want to lock multiple runqueues * (such as the load balancing or the thread migration code), lock * acquire operations must be ordered by ascending &runqueue. */ structrunqueue { spinlock_t lock;
/* * nr_running and cpu_load should be in the same cacheline because * remote CPUs use both these fields when doing load calculation. */ unsignedlong nr_running; #ifdef CONFIG_SMP unsignedlong cpu_load[3]; #endif unsignedlonglong nr_switches;
/* * This is part of a global counter where only the total sum * over all CPUs matters. A task can increase this counter on * one CPU and if it got migrated afterwards it may decrease * it on another CPU. Always updated under the runqueue lock: */ unsignedlong nr_uninterruptible;
/* TICK_USEC_TO_NSEC is the time between ticks in nsec assuming real ACTHZ and */ /* a value TUSEC for TICK_USEC (can be set bij adjtimex) */ #define TICK_USEC_TO_NSEC(TUSEC) (SH_DIV (TUSEC * USER_HZ * 1000, ACTHZ, 8))
/* some arch's have a small-data section that can be accessed register-relative * but that can only take up to, say, 4-byte variables. jiffies being part of * an 8-byte variable may not be correctly accessed unless we force the issue */ #define __jiffy_data __attribute__((section(".data")))
/* * The 64-bit value is not volatile - you MUST NOT read it * without sampling the sequence number in xtime_lock. * get_jiffies_64() will do this for you as appropriate. */ extern u64 __jiffy_data jiffies_64; externunsignedlongvolatile __jiffy_data jiffies;