7404 lines · 180.6 KB · C
RawDownload
/* *  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 *  2007-04-15  Work begun on replacing all interactivity tuning with a *              fair scheduling design by Con Kolivas. *  2007-05-05  Load balancing (smp-nice) and other improvements *              by Peter Williams *  2007-05-06  Interactivity improvements to CFS by Mike Galbraith *  2007-07-01  Group scheduling enhancements by Srivatsa Vaddagiri */ #include <linux/mm.h>#include <linux/module.h>#include <linux/nmi.h>#include <linux/init.h>#include <linux/uaccess.h>#include <linux/highmem.h>#include <linux/smp_lock.h>#include <asm/mmu_context.h>#include <linux/interrupt.h>#include <linux/capability.h>#include <linux/completion.h>#include <linux/kernel_stat.h>#include <linux/debug_locks.h>#include <linux/security.h>#include <linux/notifier.h>#include <linux/profile.h>#include <linux/freezer.h>#include <linux/vmalloc.h>#include <linux/blkdev.h>#include <linux/delay.h>#include <linux/pid_namespace.h>#include <linux/smp.h>#include <linux/threads.h>#include <linux/timer.h>#include <linux/rcupdate.h>#include <linux/cpu.h>#include <linux/cpuset.h>#include <linux/percpu.h>#include <linux/kthread.h>#include <linux/seq_file.h>#include <linux/sysctl.h>#include <linux/syscalls.h>#include <linux/times.h>#include <linux/tsacct_kern.h>#include <linux/kprobes.h>#include <linux/delayacct.h>#include <linux/reciprocal_div.h>#include <linux/unistd.h>#include <linux/pagemap.h> #include <asm/tlb.h>#include <asm/irq_regs.h> /* * Scheduler clock - returns current time in nanosec units. * This is default implementation. * Architectures and sub-architectures can override this. */unsigned long long __attribute__((weak)) sched_clock(void){	return (unsigned long long)jiffies * (NSEC_PER_SEC / HZ);} /* * Convert user-nice values [ -20 ... 0 ... 19 ] * to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ], * and back. */#define NICE_TO_PRIO(nice)	(MAX_RT_PRIO + (nice) + 20)#define PRIO_TO_NICE(prio)	((prio) - MAX_RT_PRIO - 20)#define TASK_NICE(p)		PRIO_TO_NICE((p)->static_prio) /* * 'User priority' is the nice value converted to something we * can work with better when scaling various scheduler parameters, * it's a [ 0 ... 39 ] range. */#define USER_PRIO(p)		((p)-MAX_RT_PRIO)#define TASK_USER_PRIO(p)	USER_PRIO((p)->static_prio)#define MAX_USER_PRIO		(USER_PRIO(MAX_PRIO)) /* * Some helpers for converting nanosecond timing to jiffy resolution */#define NS_TO_JIFFIES(TIME)	((unsigned long)(TIME) / (NSEC_PER_SEC / HZ))#define JIFFIES_TO_NS(TIME)	((TIME) * (NSEC_PER_SEC / HZ)) #define NICE_0_LOAD		SCHED_LOAD_SCALE#define NICE_0_SHIFT		SCHED_LOAD_SHIFT /* * These are the 'tuning knobs' of the scheduler: * * default timeslice is 100 msecs (used only for SCHED_RR tasks). * Timeslices get refilled after they expire. */#define DEF_TIMESLICE		(100 * HZ / 1000) #ifdef CONFIG_SMP/* * Divide a load by a sched group cpu_power : (load / sg->__cpu_power) * Since cpu_power is a 'constant', we can use a reciprocal divide. */static inline u32 sg_div_cpu_power(const struct sched_group *sg, u32 load){	return reciprocal_divide(load, sg->reciprocal_cpu_power);} /* * Each time a sched group cpu_power is changed, * we must compute its reciprocal value */static inline void sg_inc_cpu_power(struct sched_group *sg, u32 val){	sg->__cpu_power += val;	sg->reciprocal_cpu_power = reciprocal_value(sg->__cpu_power);}#endif static inline int rt_policy(int policy){	if (unlikely(policy == SCHED_FIFO) || unlikely(policy == SCHED_RR))		return 1;	return 0;} static inline int task_has_rt_policy(struct task_struct *p){	return rt_policy(p->policy);} /* * This is the priority-queue data structure of the RT scheduling class: */struct rt_prio_array {	DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */	struct list_head queue[MAX_RT_PRIO];}; #ifdef CONFIG_FAIR_GROUP_SCHED #include <linux/cgroup.h> struct cfs_rq; /* task group related information */struct task_group {#ifdef CONFIG_FAIR_CGROUP_SCHED	struct cgroup_subsys_state css;#endif	/* schedulable entities of this group on each cpu */	struct sched_entity **se;	/* runqueue "owned" by this group on each cpu */	struct cfs_rq **cfs_rq;	unsigned long shares;	/* spinlock to serialize modification to shares */	spinlock_t lock;	struct rcu_head rcu;}; /* Default task group's sched entity on each cpu */static DEFINE_PER_CPU(struct sched_entity, init_sched_entity);/* Default task group's cfs_rq on each cpu */static DEFINE_PER_CPU(struct cfs_rq, init_cfs_rq) ____cacheline_aligned_in_smp; static struct sched_entity *init_sched_entity_p[NR_CPUS];static struct cfs_rq *init_cfs_rq_p[NR_CPUS]; /* Default task group. *	Every task in system belong to this group at bootup. */struct task_group init_task_group = {	.se     = init_sched_entity_p,	.cfs_rq = init_cfs_rq_p,}; #ifdef CONFIG_FAIR_USER_SCHED# define INIT_TASK_GRP_LOAD	2*NICE_0_LOAD#else# define INIT_TASK_GRP_LOAD	NICE_0_LOAD#endif static int init_task_group_load = INIT_TASK_GRP_LOAD; /* return group to which a task belongs */static inline struct task_group *task_group(struct task_struct *p){	struct task_group *tg; #ifdef CONFIG_FAIR_USER_SCHED	tg = p->user->tg;#elif defined(CONFIG_FAIR_CGROUP_SCHED)	tg = container_of(task_subsys_state(p, cpu_cgroup_subsys_id),				struct task_group, css);#else	tg = &init_task_group;#endif	return tg;} /* Change a task's cfs_rq and parent entity if it moves across CPUs/groups */static inline void set_task_cfs_rq(struct task_struct *p, unsigned int cpu){	p->se.cfs_rq = task_group(p)->cfs_rq[cpu];	p->se.parent = task_group(p)->se[cpu];} #else static inline void set_task_cfs_rq(struct task_struct *p, unsigned int cpu) { } #endif	/* CONFIG_FAIR_GROUP_SCHED */ /* CFS-related fields in a runqueue */struct cfs_rq {	struct load_weight load;	unsigned long nr_running; 	u64 exec_clock;	u64 min_vruntime; 	struct rb_root tasks_timeline;	struct rb_node *rb_leftmost;	struct rb_node *rb_load_balance_curr;	/* 'curr' points to currently running entity on this cfs_rq.	 * It is set to NULL otherwise (i.e when none are currently running).	 */	struct sched_entity *curr; 	unsigned long nr_spread_over; #ifdef CONFIG_FAIR_GROUP_SCHED	struct rq *rq;	/* cpu runqueue to which this cfs_rq is attached */ 	/*	 * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in	 * a hierarchy). Non-leaf lrqs hold other higher schedulable entities	 * (like users, containers etc.)	 *	 * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This	 * list is used during load balance.	 */	struct list_head leaf_cfs_rq_list;	struct task_group *tg;	/* group that "owns" this runqueue */#endif}; /* Real-Time classes' related field in a runqueue: */struct rt_rq {	struct rt_prio_array active;	int rt_load_balance_idx;	struct list_head *rt_load_balance_head, *rt_load_balance_curr;}; /* * 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. */struct rq {	/* runqueue lock: */	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.	 */	unsigned long nr_running;	#define CPU_LOAD_IDX_MAX 5	unsigned long cpu_load[CPU_LOAD_IDX_MAX];	unsigned char idle_at_tick;#ifdef CONFIG_NO_HZ	unsigned char in_nohz_recently;#endif	/* capture load from *all* tasks on this cpu: */	struct load_weight load;	unsigned long nr_load_updates;	u64 nr_switches; 	struct cfs_rq cfs;#ifdef CONFIG_FAIR_GROUP_SCHED	/* list of leaf cfs_rq on this cpu: */	struct list_head leaf_cfs_rq_list;#endif	struct rt_rq rt; 	/*	 * 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:	 */	unsigned long nr_uninterruptible; 	struct task_struct *curr, *idle;	unsigned long next_balance;	struct mm_struct *prev_mm; 	u64 clock, prev_clock_raw;	s64 clock_max_delta; 	unsigned int clock_warps, clock_overflows;	u64 idle_clock;	unsigned int clock_deep_idle_events;	u64 tick_timestamp; 	atomic_t nr_iowait; #ifdef CONFIG_SMP	struct sched_domain *sd; 	/* For active balancing */	int active_balance;	int push_cpu;	/* cpu of this runqueue: */	int cpu; 	struct task_struct *migration_thread;	struct list_head migration_queue;#endif #ifdef CONFIG_SCHEDSTATS	/* latency stats */	struct sched_info rq_sched_info; 	/* sys_sched_yield() stats */	unsigned int yld_exp_empty;	unsigned int yld_act_empty;	unsigned int yld_both_empty;	unsigned int yld_count; 	/* schedule() stats */	unsigned int sched_switch;	unsigned int sched_count;	unsigned int sched_goidle; 	/* try_to_wake_up() stats */	unsigned int ttwu_count;	unsigned int ttwu_local; 	/* BKL stats */	unsigned int bkl_count;#endif	struct lock_class_key rq_lock_key;}; static DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);static DEFINE_MUTEX(sched_hotcpu_mutex); static inline void check_preempt_curr(struct rq *rq, struct task_struct *p){	rq->curr->sched_class->check_preempt_curr(rq, p);} static inline int cpu_of(struct rq *rq){#ifdef CONFIG_SMP	return rq->cpu;#else	return 0;#endif} /* * Update the per-runqueue clock, as finegrained as the platform can give * us, but without assuming monotonicity, etc.: */static void __update_rq_clock(struct rq *rq){	u64 prev_raw = rq->prev_clock_raw;	u64 now = sched_clock();	s64 delta = now - prev_raw;	u64 clock = rq->clock; #ifdef CONFIG_SCHED_DEBUG	WARN_ON_ONCE(cpu_of(rq) != smp_processor_id());#endif	/*	 * Protect against sched_clock() occasionally going backwards:	 */	if (unlikely(delta < 0)) {		clock++;		rq->clock_warps++;	} else {		/*		 * Catch too large forward jumps too:		 */		if (unlikely(clock + delta > rq->tick_timestamp + TICK_NSEC)) {			if (clock < rq->tick_timestamp + TICK_NSEC)				clock = rq->tick_timestamp + TICK_NSEC;			else				clock++;			rq->clock_overflows++;		} else {			if (unlikely(delta > rq->clock_max_delta))				rq->clock_max_delta = delta;			clock += delta;		}	} 	rq->prev_clock_raw = now;	rq->clock = clock;} static void update_rq_clock(struct rq *rq){	if (likely(smp_processor_id() == cpu_of(rq)))		__update_rq_clock(rq);} /* * The domain tree (rq->sd) is protected by RCU's quiescent state transition. * See detach_destroy_domains: synchronize_sched for details. * * The domain tree of any CPU may only be accessed from within * preempt-disabled sections. */#define for_each_domain(cpu, __sd) \	for (__sd = rcu_dereference(cpu_rq(cpu)->sd); __sd; __sd = __sd->parent) #define cpu_rq(cpu)		(&per_cpu(runqueues, (cpu)))#define this_rq()		(&__get_cpu_var(runqueues))#define task_rq(p)		cpu_rq(task_cpu(p))#define cpu_curr(cpu)		(cpu_rq(cpu)->curr) /* * Tunables that become constants when CONFIG_SCHED_DEBUG is off: */#ifdef CONFIG_SCHED_DEBUG# define const_debug __read_mostly#else# define const_debug static const#endif /* * Debugging: various feature bits */enum {	SCHED_FEAT_NEW_FAIR_SLEEPERS	= 1,	SCHED_FEAT_WAKEUP_PREEMPT	= 2,	SCHED_FEAT_START_DEBIT		= 4,	SCHED_FEAT_TREE_AVG		= 8,	SCHED_FEAT_APPROX_AVG		= 16,}; const_debug unsigned int sysctl_sched_features =		SCHED_FEAT_NEW_FAIR_SLEEPERS	* 1 |		SCHED_FEAT_WAKEUP_PREEMPT	* 1 |		SCHED_FEAT_START_DEBIT		* 1 |		SCHED_FEAT_TREE_AVG		* 0 |		SCHED_FEAT_APPROX_AVG		* 0; #define sched_feat(x) (sysctl_sched_features & SCHED_FEAT_##x) /* * Number of tasks to iterate in a single balance run. * Limited because this is done with IRQs disabled. */const_debug unsigned int sysctl_sched_nr_migrate = 32; /* * For kernel-internal use: high-speed (but slightly incorrect) per-cpu * clock constructed from sched_clock(): */unsigned long long cpu_clock(int cpu){	unsigned long long now;	unsigned long flags;	struct rq *rq; 	local_irq_save(flags);	rq = cpu_rq(cpu);	/*	 * Only call sched_clock() if the scheduler has already been	 * initialized (some code might call cpu_clock() very early):	 */	if (rq->idle)		update_rq_clock(rq);	now = rq->clock;	local_irq_restore(flags); 	return now;

Lines 1–500 of 7404.

Keyboard shortcuts

General

Show keyboard shortcuts
?
Focus the current search
/

Issues and pull requests

Open filters
f

Issues, pull requests and Inbox

Select next item
j↓
Select previous item
k↑
Open selected item
Enter
Dismiss filters or clear selection
Esc

Repository code

Go to file
t