-
Notifications
You must be signed in to change notification settings - Fork 0
/
sched.c
2005 lines (1746 loc) · 47.7 KB
/
sched.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/*
* 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. Additional code by Davide
* Libenzi, Robert Love, and Rusty Russell.
*/
#include <linux/mm.h>
#include <linux/nmi.h>
#include <linux/init.h>
#include <asm/uaccess.h>
#include <linux/highmem.h>
#include <linux/smp_lock.h>
#include <asm/mmu_context.h>
#include <linux/interrupt.h>
#include <linux/completion.h>
#include <linux/kernel_stat.h>
#define WAIT_AND_PRINT(s) \
do { \
printk("%s\n", s); \
unsigned long i = 1; \
while (i++ != 0); \
} while(0)
/*
* Convert user-nice values [ -20 ... 0 ... 19 ]
* to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
* and back.
*/
#define NICE_TO_PRIO(nice) (MAX_SHORT_PRIO + (nice) + 20)
#define PRIO_TO_NICE(prio) ((prio) - MAX_SHORT_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_SHORT_PRIO)
#define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)
#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))
/*
* These are the 'tuning knobs' of the scheduler:
*
* Minimum timeslice is 10 msecs, default timeslice is 150 msecs,
* maximum timeslice is 300 msecs. Timeslices get refilled after
* they expire.
*/
#define MIN_TIMESLICE ( 10 * HZ / 1000)
#define MAX_TIMESLICE (300 * HZ / 1000)
#define CHILD_PENALTY 95
#define PARENT_PENALTY 100
#define EXIT_WEIGHT 3
#define PRIO_BONUS_RATIO 25
#define INTERACTIVE_DELTA 2
#define MAX_SLEEP_AVG (2*HZ)
#define STARVATION_LIMIT (2*HZ)
/*
* If a task is 'interactive' then we reinsert it in the active
* array after it has expired its current timeslice. (it will not
* continue to run immediately, it will still roundrobin with
* other interactive tasks.)
*
* This part scales the interactivity limit depending on niceness.
*
* We scale it linearly, offset by the INTERACTIVE_DELTA delta.
* Here are a few examples of different nice levels:
*
* TASK_INTERACTIVE(-20): [1,1,1,1,1,1,1,1,1,0,0]
* TASK_INTERACTIVE(-10): [1,1,1,1,1,1,1,0,0,0,0]
* TASK_INTERACTIVE( 0): [1,1,1,1,0,0,0,0,0,0,0]
* TASK_INTERACTIVE( 10): [1,1,0,0,0,0,0,0,0,0,0]
* TASK_INTERACTIVE( 19): [0,0,0,0,0,0,0,0,0,0,0]
*
* (the X axis represents the possible -5 ... 0 ... +5 dynamic
* priority range a task can explore, a value of '1' means the
* task is rated interactive.)
*
* Ie. nice +19 tasks can never get 'interactive' enough to be
* reinserted into the active array. And only heavily CPU-hog nice -20
* tasks will be expired. Default nice 0 tasks are somewhere between,
* it takes some effort for them to get interactive, but it's not
* too hard.
*/
#define SCALE(v1,v1_max,v2_max) \
(v1) * (v2_max) / (v1_max)
#define DELTA(p) \
(SCALE(TASK_NICE(p), 40, MAX_USER_PRIO*PRIO_BONUS_RATIO/100) + \
INTERACTIVE_DELTA)
#define TASK_INTERACTIVE(p) \
((p)->prio <= (p)->static_prio - DELTA(p))
/*
* TASK_TIMESLICE scales user-nice values [ -20 ... 19 ]
* to time slice values.
*
* The higher a process's priority, the bigger timeslices
* it gets during one round of execution. But even the lowest
* priority process gets MIN_TIMESLICE worth of execution time.
*/
#define TASK_TIMESLICE(p) (MIN_TIMESLICE + \
((MAX_TIMESLICE - MIN_TIMESLICE) * (MAX_PRIO-1-(p)->static_prio)/39))
#define OVERDUE_SHORT_TASK_TIMESLICE(p) \
((10 * (140 - (p)->short_priority)) * HZ / 1000)
/*
* These are the runqueue data structures:
*/
#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
typedef struct runqueue runqueue_t;
struct prio_array {
int nr_active;
unsigned long bitmap[BITMAP_SIZE];
list_t queue[MAX_PRIO];
};
/*
* 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 process migration code), lock
* acquire operations must be ordered by ascending &runqueue.
*/
struct runqueue {
spinlock_t lock;
unsigned long nr_running, nr_switches, expired_timestamp;
signed long nr_uninterruptible;
task_t *curr, *idle;
prio_array_t *active, *expired, *overdue, arrays[3];
int prev_nr_running[NR_CPUS];
task_t *migration_thread;
list_t migration_queue;
} ____cacheline_aligned;
static struct runqueue runqueues[NR_CPUS] __cacheline_aligned;
#define cpu_rq(cpu) (runqueues + (cpu))
#define this_rq() cpu_rq(smp_processor_id())
#define task_rq(p) cpu_rq((p)->cpu)
#define cpu_curr(cpu) (cpu_rq(cpu)->curr)
#define rt_task(p) ((p)->prio < MAX_RT_PRIO)
#define short_task(p) ((p)->policy == SCHED_SHORT)
/*
* Default context-switch locking:
*/
#ifndef prepare_arch_schedule
# define prepare_arch_schedule(prev) do { } while(0)
# define finish_arch_schedule(prev) do { } while(0)
# define prepare_arch_switch(rq) do { } while(0)
# define finish_arch_switch(rq) spin_unlock_irq(&(rq)->lock)
#endif
/*
* task_rq_lock - lock the runqueue a given task resides on and disable
* interrupts. Note the ordering: we can safely lookup the task_rq without
* explicitly disabling preemption.
*/
static inline runqueue_t *task_rq_lock(task_t *p, unsigned long *flags)
{
struct runqueue *rq;
repeat_lock_task:
local_irq_save(*flags);
rq = task_rq(p);
spin_lock(&rq->lock);
if (unlikely(rq != task_rq(p))) {
spin_unlock_irqrestore(&rq->lock, *flags);
goto repeat_lock_task;
}
return rq;
}
static inline void task_rq_unlock(runqueue_t *rq, unsigned long *flags)
{
spin_unlock_irqrestore(&rq->lock, *flags);
}
/*
* rq_lock - lock a given runqueue and disable interrupts.
*/
static inline runqueue_t *this_rq_lock(void)
{
runqueue_t *rq;
local_irq_disable();
rq = this_rq();
spin_lock(&rq->lock);
return rq;
}
static inline void rq_unlock(runqueue_t *rq)
{
spin_unlock(&rq->lock);
local_irq_enable();
}
/*
* Adding/removing a task to/from a priority array:
*/
static inline void dequeue_task(struct task_struct *p, prio_array_t *array)
{
array->nr_active--;
list_del(&p->run_list);
if (list_empty(array->queue + p->prio))
__clear_bit(p->prio, array->bitmap);
}
static inline void enqueue_task(struct task_struct *p, prio_array_t *array)
{
list_add_tail(&p->run_list, array->queue + p->prio);
__set_bit(p->prio, array->bitmap);
array->nr_active++;
p->array = array;
}
static inline int effective_prio(task_t *p)
{
int bonus, prio;
/*
* Here we scale the actual sleep average [0 .... MAX_SLEEP_AVG]
* into the -5 ... 0 ... +5 bonus/penalty range.
*
* We use 25% of the full 0...39 priority range so that:
*
* 1) nice +19 interactive tasks do not preempt nice 0 CPU hogs.
* 2) nice -20 CPU hogs do not get preempted by nice 0 tasks.
*
* Both properties are important to certain workloads.
*/
bonus = MAX_USER_PRIO*PRIO_BONUS_RATIO*p->sleep_avg/MAX_SLEEP_AVG/100 -
MAX_USER_PRIO*PRIO_BONUS_RATIO/100/2;
prio = p->static_prio - bonus;
if (prio < MAX_SHORT_PRIO)
prio = MAX_SHORT_PRIO;
if (prio > MAX_PRIO-1)
prio = MAX_PRIO-1;
return prio;
}
static inline void activate_task(task_t *p, runqueue_t *rq)
{
unsigned long sleep_time = jiffies - p->sleep_timestamp;
prio_array_t *array = (p->policy == SCHED_SHORT && p->is_overdue) ? rq->overdue : rq->active;
if (!rt_task(p) && sleep_time && !short_task(p)) {
/*
* This code gives a bonus to interactive tasks. We update
* an 'average sleep time' value here, based on
* sleep_timestamp. The more time a task spends sleeping,
* the higher the average gets - and the higher the priority
* boost gets as well.
*/
p->sleep_avg += sleep_time;
if (p->sleep_avg > MAX_SLEEP_AVG)
p->sleep_avg = MAX_SLEEP_AVG;
p->prio = effective_prio(p);
}
enqueue_task(p, array);
if (!(p->policy == SCHED_SHORT && p->is_overdue))
rq->nr_running++;
}
static inline void deactivate_task(struct task_struct *p, runqueue_t *rq)
{
if (!(p->policy == SCHED_SHORT && p->is_overdue))
rq->nr_running--;
if (p->state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible++;
dequeue_task(p, p->array);
p->array = NULL;
}
static inline void resched_task(task_t *p)
{
#ifdef CONFIG_SMP
int need_resched;
need_resched = p->need_resched;
wmb();
set_tsk_need_resched(p);
if (!need_resched && (p->cpu != smp_processor_id()))
smp_send_reschedule(p->cpu);
#else
set_tsk_need_resched(p);
#endif
}
#ifdef CONFIG_SMP
/*
* Wait for a process to unschedule. This is used by the exit() and
* ptrace() code.
*/
void wait_task_inactive(task_t * p)
{
unsigned long flags;
runqueue_t *rq;
repeat:
rq = task_rq(p);
if (unlikely(rq->curr == p)) {
cpu_relax();
goto repeat;
}
rq = task_rq_lock(p, &flags);
if (unlikely(rq->curr == p)) {
task_rq_unlock(rq, &flags);
goto repeat;
}
task_rq_unlock(rq, &flags);
}
/*
* Kick the remote CPU if the task is running currently,
* this code is used by the signal code to signal tasks
* which are in user-mode as quickly as possible.
*
* (Note that we do this lockless - if the task does anything
* while the message is in flight then it will notice the
* sigpending condition anyway.)
*/
void kick_if_running(task_t * p)
{
if (p == task_rq(p)->curr)
resched_task(p);
}
#endif
/*
* Wake up a process. Put it on the run-queue if it's not
* already there. The "current" process is always on the
* run-queue (except when the actual re-schedule is in
* progress), and as such you're allowed to do the simpler
* "current->state = TASK_RUNNING" to mark yourself runnable
* without the overhead of this.
*/
static int try_to_wake_up(task_t * p, int sync)
{
unsigned long flags;
int success = 0;
long old_state;
runqueue_t *rq;
repeat_lock_task:
rq = task_rq_lock(p, &flags);
old_state = p->state;
if (!p->array) {
/*
* Fast-migrate the task if it's not running or runnable
* currently. Do not violate hard affinity.
*/
if (unlikely(sync && (rq->curr != p) &&
(p->cpu != smp_processor_id()) &&
(p->cpus_allowed & (1UL << smp_processor_id())))) {
p->cpu = smp_processor_id();
task_rq_unlock(rq, &flags);
goto repeat_lock_task;
}
if (old_state == TASK_UNINTERRUPTIBLE)
rq->nr_uninterruptible--;
activate_task(p, rq);
/*
* If sync is set, a resched_task() is a NOOP
*/
if (p->prio < rq->curr->prio || ((rq->curr->policy == SCHED_SHORT && rq->curr->is_overdue) && !(p->policy == SCHED_SHORT && p->is_overdue)))
resched_task(rq->curr);
success = 1;
}
p->state = TASK_RUNNING;
task_rq_unlock(rq, &flags);
return success;
}
int wake_up_process(task_t * p)
{
return try_to_wake_up(p, 0);
}
void wake_up_forked_process(task_t * p)
{
runqueue_t *rq = this_rq_lock();
p->state = TASK_RUNNING;
if (!rt_task(p) && !short_task(p)) {
/*
* We decrease the sleep average of forking parents
* and children as well, to keep max-interactive tasks
* from forking tasks that are max-interactive.
*/
current->sleep_avg = current->sleep_avg * PARENT_PENALTY / 100;
p->sleep_avg = p->sleep_avg * CHILD_PENALTY / 100;
p->prio = effective_prio(p);
}
p->cpu = smp_processor_id();
activate_task(p, rq);
rq_unlock(rq);
}
/*
* Potentially available exiting-child timeslices are
* retrieved here - this way the parent does not get
* penalized for creating too many processes.
*
* (this cannot be used to 'generate' timeslices
* artificially, because any timeslice recovered here
* was given away by the parent in the first place.)
*/
void sched_exit(task_t * p)
{
__cli();
if (p->first_time_slice) {
current->time_slice += p->time_slice;
if (unlikely(current->time_slice > MAX_TIMESLICE))
current->time_slice = MAX_TIMESLICE;
}
__sti();
/*
* If the child was a (relative-) CPU hog then decrease
* the sleep_avg of the parent as well.
*/
if (p->sleep_avg < current->sleep_avg)
current->sleep_avg = (current->sleep_avg * EXIT_WEIGHT +
p->sleep_avg) / (EXIT_WEIGHT + 1);
}
#if CONFIG_SMP
asmlinkage void schedule_tail(task_t *prev)
{
finish_arch_switch(this_rq());
finish_arch_schedule(prev);
}
#endif
static inline task_t * context_switch(task_t *prev, task_t *next)
{
struct mm_struct *mm = next->mm;
struct mm_struct *oldmm = prev->active_mm;
if (unlikely(!mm)) {
next->active_mm = oldmm;
atomic_inc(&oldmm->mm_count);
enter_lazy_tlb(oldmm, next, smp_processor_id());
} else
switch_mm(oldmm, mm, next, smp_processor_id());
if (unlikely(!prev->mm)) {
prev->active_mm = NULL;
mmdrop(oldmm);
}
/* Here we just switch the register state and the stack. */
switch_to(prev, next, prev);
return prev;
}
unsigned long nr_running(void)
{
unsigned long i, sum = 0;
for (i = 0; i < smp_num_cpus; i++)
sum += cpu_rq(cpu_logical_map(i))->nr_running;
return sum;
}
unsigned long nr_uninterruptible(void)
{
unsigned long i, sum = 0;
for (i = 0; i < smp_num_cpus; i++)
sum += cpu_rq(cpu_logical_map(i))->nr_uninterruptible;
return sum;
}
unsigned long nr_context_switches(void)
{
unsigned long i, sum = 0;
for (i = 0; i < smp_num_cpus; i++)
sum += cpu_rq(cpu_logical_map(i))->nr_switches;
return sum;
}
#if CONFIG_SMP
/*
* Lock the busiest runqueue as well, this_rq is locked already.
* Recalculate nr_running if we have to drop the runqueue lock.
*/
static inline unsigned int double_lock_balance(runqueue_t *this_rq,
runqueue_t *busiest, int this_cpu, int idle, unsigned int nr_running)
{
if (unlikely(!spin_trylock(&busiest->lock))) {
if (busiest < this_rq) {
spin_unlock(&this_rq->lock);
spin_lock(&busiest->lock);
spin_lock(&this_rq->lock);
/* Need to recalculate nr_running */
if (idle || (this_rq->nr_running > this_rq->prev_nr_running[this_cpu]))
nr_running = this_rq->nr_running;
else
nr_running = this_rq->prev_nr_running[this_cpu];
} else
spin_lock(&busiest->lock);
}
return nr_running;
}
/*
* Current runqueue is empty, or rebalance tick: if there is an
* inbalance (current runqueue is too short) then pull from
* busiest runqueue(s).
*
* We call this with the current runqueue locked,
* irqs disabled.
*/
static void load_balance(runqueue_t *this_rq, int idle)
{
int imbalance, nr_running, load, max_load,
idx, i, this_cpu = smp_processor_id();
task_t *next = this_rq->idle, *tmp;
runqueue_t *busiest, *rq_src;
prio_array_t *array;
list_t *head, *curr;
/*
* We search all runqueues to find the most busy one.
* We do this lockless to reduce cache-bouncing overhead,
* we re-check the 'best' source CPU later on again, with
* the lock held.
*
* We fend off statistical fluctuations in runqueue lengths by
* saving the runqueue length during the previous load-balancing
* operation and using the smaller one the current and saved lengths.
* If a runqueue is long enough for a longer amount of time then
* we recognize it and pull tasks from it.
*
* The 'current runqueue length' is a statistical maximum variable,
* for that one we take the longer one - to avoid fluctuations in
* the other direction. So for a load-balance to happen it needs
* stable long runqueue on the target CPU and stable short runqueue
* on the local runqueue.
*
* We make an exception if this CPU is about to become idle - in
* that case we are less picky about moving a task across CPUs and
* take what can be taken.
*/
if (idle || (this_rq->nr_running > this_rq->prev_nr_running[this_cpu]))
nr_running = this_rq->nr_running;
else
nr_running = this_rq->prev_nr_running[this_cpu];
busiest = NULL;
max_load = 1;
for (i = 0; i < smp_num_cpus; i++) {
int logical = cpu_logical_map(i);
rq_src = cpu_rq(logical);
if (idle || (rq_src->nr_running < this_rq->prev_nr_running[logical]))
load = rq_src->nr_running;
else
load = this_rq->prev_nr_running[logical];
this_rq->prev_nr_running[logical] = rq_src->nr_running;
if ((load > max_load) && (rq_src != this_rq)) {
busiest = rq_src;
max_load = load;
}
}
if (likely(!busiest))
return;
imbalance = (max_load - nr_running) / 2;
/* It needs an at least ~25% imbalance to trigger balancing. */
if (!idle && (imbalance < (max_load + 3)/4))
return;
nr_running = double_lock_balance(this_rq, busiest, this_cpu, idle, nr_running);
/*
* Make sure nothing changed since we checked the
* runqueue length.
*/
if (busiest->nr_running <= nr_running + 1)
goto out_unlock;
/*
* We first consider expired tasks. Those will likely not be
* executed in the near future, and they are most likely to
* be cache-cold, thus switching CPUs has the least effect
* on them.
*/
if (busiest->expired->nr_active)
array = busiest->expired;
else
array = busiest->active;
new_array:
/* Start searching at priority 0: */
idx = 0;
skip_bitmap:
if (!idx)
idx = sched_find_first_bit(array->bitmap);
else
idx = find_next_bit(array->bitmap, MAX_PRIO, idx);
if (idx == MAX_PRIO) {
if (array == busiest->expired) {
array = busiest->active;
goto new_array;
}
goto out_unlock;
}
head = array->queue + idx;
curr = head->prev;
skip_queue:
tmp = list_entry(curr, task_t, run_list);
/*
* We do not migrate tasks that are:
* 1) running (obviously), or
* 2) cannot be migrated to this CPU due to cpus_allowed, or
* 3) are cache-hot on their current CPU.
*/
#define CAN_MIGRATE_TASK(p,rq,this_cpu) \
((jiffies - (p)->sleep_timestamp > cache_decay_ticks) && \
((p) != (rq)->curr) && \
((p)->cpus_allowed & (1UL << (this_cpu))))
curr = curr->prev;
if (!CAN_MIGRATE_TASK(tmp, busiest, this_cpu)) {
if (curr != head)
goto skip_queue;
idx++;
goto skip_bitmap;
}
next = tmp;
/*
* take the task out of the other runqueue and
* put it into this one:
*/
dequeue_task(next, array);
busiest->nr_running--;
next->cpu = this_cpu;
this_rq->nr_running++;
enqueue_task(next, this_rq->active);
if (next->prio < current->prio)
set_need_resched();
if (!idle && --imbalance) {
if (curr != head)
goto skip_queue;
idx++;
goto skip_bitmap;
}
out_unlock:
spin_unlock(&busiest->lock);
}
/*
* One of the idle_cpu_tick() or the busy_cpu_tick() function will
* gets called every timer tick, on every CPU. Our balancing action
* frequency and balancing agressivity depends on whether the CPU is
* idle or not.
*
* busy-rebalance every 250 msecs. idle-rebalance every 1 msec. (or on
* systems with HZ=100, every 10 msecs.)
*/
#define BUSY_REBALANCE_TICK (HZ/4 ?: 1)
#define IDLE_REBALANCE_TICK (HZ/1000 ?: 1)
static inline void idle_tick(void)
{
if (jiffies % IDLE_REBALANCE_TICK)
return;
spin_lock(&this_rq()->lock);
load_balance(this_rq(), 1);
spin_unlock(&this_rq()->lock);
}
#endif
/*
* We place interactive tasks back into the active array, if possible.
*
* To guarantee that this does not starve expired tasks we ignore the
* interactivity of a task if the first expired task had to wait more
* than a 'reasonable' amount of time. This deadline timeout is
* load-dependent, as the frequency of array switched decreases with
* increasing number of running tasks:
*/
#define EXPIRED_STARVING(rq) \
((rq)->expired_timestamp && \
(jiffies - (rq)->expired_timestamp >= \
STARVATION_LIMIT * ((rq)->nr_running) + 1))
/*
* This function gets called by the timer code, with HZ frequency.
* We call it with interrupts disabled.
*/
void scheduler_tick(int user_tick, int system)
{
int cpu = smp_processor_id();
runqueue_t *rq = this_rq();
task_t *p = current;
if (p == rq->idle) {
if (local_bh_count(cpu) || local_irq_count(cpu) > 1)
kstat.per_cpu_system[cpu] += system;
#if CONFIG_SMP
idle_tick();
#endif
return;
}
if (TASK_NICE(p) > 0)
kstat.per_cpu_nice[cpu] += user_tick;
else
kstat.per_cpu_user[cpu] += user_tick;
kstat.per_cpu_system[cpu] += system;
/* Task might have expired already, but not scheduled off yet */
if (p->array != rq->active) {
set_tsk_need_resched(p);
return;
}
spin_lock(&rq->lock);
if (unlikely(rt_task(p))) {
/*
* RR tasks need a special form of timeslice management.
* FIFO tasks have no timeslices.
*/
if ((p->policy == SCHED_RR) && !--p->time_slice) {
p->time_slice = TASK_TIMESLICE(p);
p->first_time_slice = 0;
set_tsk_need_resched(p);
/* put it at the end of the queue: */
dequeue_task(p, rq->active);
enqueue_task(p, rq->active);
}
goto out;
}
if (short_task(p)) {
if (--p->time_slice == 0) {
deactivate_task(p,rq);
set_tsk_need_resched(p);
p->is_overdue = OVERDUE;
p->first_time_slice = 0;
p->time_slice = OVERDUE_SHORT_TASK_TIMESLICE(p);
p->prio = MAX_PRIO-1; /* All short procceses should run the same */
activate_task(p,rq);
}
goto out;
}
/*
* The task was running during this tick - update the
* time slice counter and the sleep average. Note: we
* do not update a process's priority until it either
* goes to sleep or uses up its timeslice. This makes
* it possible for interactive tasks to use up their
* timeslices at their highest priority levels.
*/
if (p->sleep_avg)
p->sleep_avg--;
if (!--p->time_slice) {
dequeue_task(p, rq->active);
set_tsk_need_resched(p);
p->prio = effective_prio(p);
p->first_time_slice = 0;
p->time_slice = TASK_TIMESLICE(p);
if (!TASK_INTERACTIVE(p) || EXPIRED_STARVING(rq)) {
if (!rq->expired_timestamp)
rq->expired_timestamp = jiffies;
enqueue_task(p, rq->expired);
} else
enqueue_task(p, rq->active);
}
out:
#if CONFIG_SMP
if (!(jiffies % BUSY_REBALANCE_TICK))
load_balance(rq, 0);
#endif
spin_unlock(&rq->lock);
}
void scheduling_functions_start_here(void) { }
/*
* 'schedule()' is the main scheduler function.
*/
asmlinkage void schedule(void)
{
task_t *prev, *next;
runqueue_t *rq;
prio_array_t *array;
list_t *queue;
int idx;
if (unlikely(in_interrupt()))
BUG();
need_resched:
prev = current;
rq = this_rq();
release_kernel_lock(prev, smp_processor_id());
prepare_arch_schedule(prev);
prev->sleep_timestamp = jiffies;
spin_lock_irq(&rq->lock);
switch (prev->state) {
case TASK_INTERRUPTIBLE:
if (unlikely(signal_pending(prev))) {
prev->state = TASK_RUNNING;
break;
}
default:
deactivate_task(prev, rq);
case TASK_RUNNING:
;
}
#if CONFIG_SMP
pick_next_task:
#endif
if (unlikely(!rq->nr_running)) {
if (rq->overdue->nr_active) {
array = rq->overdue;
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
rq->expired_timestamp = 0;
goto switch_tasks;
}
#if CONFIG_SMP
load_balance(rq, 1);
if (rq->nr_running)
goto pick_next_task;
#endif
next = rq->idle;
rq->expired_timestamp = 0;
goto switch_tasks;
}
array = rq->active;
if (unlikely(!array->nr_active)) {
/*
* Switch the active and expired arrays.
*/
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
rq->expired_timestamp = 0;
}
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);
switch_tasks:
prefetch(next);
clear_tsk_need_resched(prev);
if (likely(prev != next)) {
rq->nr_switches++;
rq->curr = next;
prepare_arch_switch(rq);
prev = context_switch(prev, next);
barrier();
rq = this_rq();
finish_arch_switch(rq);
} else
spin_unlock_irq(&rq->lock);
finish_arch_schedule(prev);
reacquire_kernel_lock(current);
if (need_resched())
goto need_resched;
}
/*
* The core wakeup function. Non-exclusive wakeups (nr_exclusive == 0) just
* wake everything up. If it's an exclusive wakeup (nr_exclusive == small +ve
* number) then we wake all the non-exclusive tasks and one exclusive task.
*
* There are circumstances in which we can try to wake a task which has already
* started to run but is not in state TASK_RUNNING. try_to_wake_up() returns
* zero in this (rare) case, and we handle it by continuing to scan the queue.
*/
static inline void __wake_up_common(wait_queue_head_t *q, unsigned int mode, int nr_exclusive, int sync)
{
struct list_head *tmp;
unsigned int state;
wait_queue_t *curr;
task_t *p;
list_for_each(tmp, &q->task_list) {
curr = list_entry(tmp, wait_queue_t, task_list);
p = curr->task;
state = p->state;
if ((state & mode) && try_to_wake_up(p, sync) &&
((curr->flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive))
break;
}
}
void __wake_up(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
{
unsigned long flags;
if (unlikely(!q))
return;
spin_lock_irqsave(&q->lock, flags);
__wake_up_common(q, mode, nr_exclusive, 0);
spin_unlock_irqrestore(&q->lock, flags);
}
#if CONFIG_SMP
void __wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr_exclusive)
{
unsigned long flags;
if (unlikely(!q))
return;
spin_lock_irqsave(&q->lock, flags);
if (likely(nr_exclusive))
__wake_up_common(q, mode, nr_exclusive, 1);
else
__wake_up_common(q, mode, nr_exclusive, 0);
spin_unlock_irqrestore(&q->lock, flags);
}
#endif
void complete(struct completion *x)
{
unsigned long flags;
spin_lock_irqsave(&x->wait.lock, flags);
x->done++;
__wake_up_common(&x->wait, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1, 0);
spin_unlock_irqrestore(&x->wait.lock, flags);
}
void wait_for_completion(struct completion *x)
{
spin_lock_irq(&x->wait.lock);
if (!x->done) {
DECLARE_WAITQUEUE(wait, current);
wait.flags |= WQ_FLAG_EXCLUSIVE;
__add_wait_queue_tail(&x->wait, &wait);
do {
__set_current_state(TASK_UNINTERRUPTIBLE);
spin_unlock_irq(&x->wait.lock);
schedule();
spin_lock_irq(&x->wait.lock);
} while (!x->done);
__remove_wait_queue(&x->wait, &wait);