1/*-
2 * Copyright (c) 2002-2003, Jeffrey Roberson <jeff@freebsd.org>
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice unmodified, this list of conditions, and the following
10 * disclaimer.
11 * 2. Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 *
15 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
17 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
18 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
19 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
20 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
21 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
22 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
24 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27#include <sys/cdefs.h>
|
28__FBSDID("$FreeBSD: head/sys/kern/sched_ule.c 121872 2003-11-02 04:25:59Z jeff $");
|
| 28__FBSDID("$FreeBSD: head/sys/kern/sched_ule.c 121896 2003-11-02 10:56:48Z jeff $"); |
29
30#include <sys/param.h>
31#include <sys/systm.h>
32#include <sys/kernel.h>
33#include <sys/ktr.h>
34#include <sys/lock.h>
35#include <sys/mutex.h>
36#include <sys/proc.h>
37#include <sys/resource.h>
38#include <sys/sched.h>
39#include <sys/smp.h>
40#include <sys/sx.h>
41#include <sys/sysctl.h>
42#include <sys/sysproto.h>
43#include <sys/vmmeter.h>
44#ifdef DDB
45#include <ddb/ddb.h>
46#endif
47#ifdef KTRACE
48#include <sys/uio.h>
49#include <sys/ktrace.h>
50#endif
51
52#include <machine/cpu.h>
53#include <machine/smp.h>
54
55#define KTR_ULE KTR_NFS
56
57/* decay 95% of `p_pctcpu' in 60 seconds; see CCPU_SHIFT before changing */
58/* XXX This is bogus compatability crap for ps */
59static fixpt_t ccpu = 0.95122942450071400909 * FSCALE; /* exp(-1/20) */
60SYSCTL_INT(_kern, OID_AUTO, ccpu, CTLFLAG_RD, &ccpu, 0, "");
61
62static void sched_setup(void *dummy);
63SYSINIT(sched_setup, SI_SUB_RUN_QUEUE, SI_ORDER_FIRST, sched_setup, NULL)
64
65static SYSCTL_NODE(_kern, OID_AUTO, sched, CTLFLAG_RW, 0, "SCHED");
66
67static int sched_strict;
68SYSCTL_INT(_kern_sched, OID_AUTO, strict, CTLFLAG_RD, &sched_strict, 0, "");
69
70static int slice_min = 1;
71SYSCTL_INT(_kern_sched, OID_AUTO, slice_min, CTLFLAG_RW, &slice_min, 0, "");
72
73static int slice_max = 10;
74SYSCTL_INT(_kern_sched, OID_AUTO, slice_max, CTLFLAG_RW, &slice_max, 0, "");
75
76int realstathz;
77int tickincr = 1;
78
79#ifdef SMP
80/* Callout to handle load balancing SMP systems. */
81static struct callout kseq_lb_callout;
82#endif
83
84/*
85 * These datastructures are allocated within their parent datastructure but
86 * are scheduler specific.
87 */
88
89struct ke_sched {
90 int ske_slice;
91 struct runq *ske_runq;
92 /* The following variables are only used for pctcpu calculation */
93 int ske_ltick; /* Last tick that we were running on */
94 int ske_ftick; /* First tick that we were running on */
95 int ske_ticks; /* Tick count */
96 /* CPU that we have affinity for. */
97 u_char ske_cpu;
98};
99#define ke_slice ke_sched->ske_slice
100#define ke_runq ke_sched->ske_runq
101#define ke_ltick ke_sched->ske_ltick
102#define ke_ftick ke_sched->ske_ftick
103#define ke_ticks ke_sched->ske_ticks
104#define ke_cpu ke_sched->ske_cpu
105#define ke_assign ke_procq.tqe_next
106
107#define KEF_ASSIGNED KEF_SCHED0 /* KSE is being migrated. */
108
109struct kg_sched {
110 int skg_slptime; /* Number of ticks we vol. slept */
111 int skg_runtime; /* Number of ticks we were running */
112};
113#define kg_slptime kg_sched->skg_slptime
114#define kg_runtime kg_sched->skg_runtime
115
116struct td_sched {
117 int std_slptime;
118};
119#define td_slptime td_sched->std_slptime
120
121struct td_sched td_sched;
122struct ke_sched ke_sched;
123struct kg_sched kg_sched;
124
125struct ke_sched *kse0_sched = &ke_sched;
126struct kg_sched *ksegrp0_sched = &kg_sched;
127struct p_sched *proc0_sched = NULL;
128struct td_sched *thread0_sched = &td_sched;
129
130/*
131 * The priority is primarily determined by the interactivity score. Thus, we
132 * give lower(better) priorities to kse groups that use less CPU. The nice
133 * value is then directly added to this to allow nice to have some effect
134 * on latency.
135 *
136 * PRI_RANGE: Total priority range for timeshare threads.
137 * PRI_NRESV: Number of nice values.
138 * PRI_BASE: The start of the dynamic range.
139 */
140#define SCHED_PRI_RANGE (PRI_MAX_TIMESHARE - PRI_MIN_TIMESHARE + 1)
141#define SCHED_PRI_NRESV ((PRIO_MAX - PRIO_MIN) + 1)
142#define SCHED_PRI_NHALF (SCHED_PRI_NRESV / 2)
143#define SCHED_PRI_BASE (PRI_MIN_TIMESHARE)
144#define SCHED_PRI_INTERACT(score) \
145 ((score) * SCHED_PRI_RANGE / SCHED_INTERACT_MAX)
146
147/*
148 * These determine the interactivity of a process.
149 *
150 * SLP_RUN_MAX: Maximum amount of sleep time + run time we'll accumulate
151 * before throttling back.
152 * SLP_RUN_FORK: Maximum slp+run time to inherit at fork time.
153 * INTERACT_MAX: Maximum interactivity value. Smaller is better.
154 * INTERACT_THRESH: Threshhold for placement on the current runq.
155 */
156#define SCHED_SLP_RUN_MAX ((hz * 5) << 10)
157#define SCHED_SLP_RUN_FORK ((hz / 2) << 10)
158#define SCHED_INTERACT_MAX (100)
159#define SCHED_INTERACT_HALF (SCHED_INTERACT_MAX / 2)
160#define SCHED_INTERACT_THRESH (30)
161
162/*
163 * These parameters and macros determine the size of the time slice that is
164 * granted to each thread.
165 *
166 * SLICE_MIN: Minimum time slice granted, in units of ticks.
167 * SLICE_MAX: Maximum time slice granted.
168 * SLICE_RANGE: Range of available time slices scaled by hz.
169 * SLICE_SCALE: The number slices granted per val in the range of [0, max].
170 * SLICE_NICE: Determine the amount of slice granted to a scaled nice.
171 * SLICE_NTHRESH: The nice cutoff point for slice assignment.
172 */
173#define SCHED_SLICE_MIN (slice_min)
174#define SCHED_SLICE_MAX (slice_max)
175#define SCHED_SLICE_NTHRESH (SCHED_PRI_NHALF - 1)
176#define SCHED_SLICE_RANGE (SCHED_SLICE_MAX - SCHED_SLICE_MIN + 1)
177#define SCHED_SLICE_SCALE(val, max) (((val) * SCHED_SLICE_RANGE) / (max))
178#define SCHED_SLICE_NICE(nice) \
179 (SCHED_SLICE_MAX - SCHED_SLICE_SCALE((nice), SCHED_SLICE_NTHRESH))
180
181/*
182 * This macro determines whether or not the kse belongs on the current or
183 * next run queue.
184 */
185#define SCHED_INTERACTIVE(kg) \
186 (sched_interact_score(kg) < SCHED_INTERACT_THRESH)
187#define SCHED_CURR(kg, ke) \
188 (ke->ke_thread->td_priority != kg->kg_user_pri || \
189 SCHED_INTERACTIVE(kg))
190
191/*
192 * Cpu percentage computation macros and defines.
193 *
194 * SCHED_CPU_TIME: Number of seconds to average the cpu usage across.
195 * SCHED_CPU_TICKS: Number of hz ticks to average the cpu usage across.
196 */
197
198#define SCHED_CPU_TIME 10
199#define SCHED_CPU_TICKS (hz * SCHED_CPU_TIME)
200
201/*
202 * kseq - per processor runqs and statistics.
203 */
204
205#define KSEQ_NCLASS (PRI_IDLE + 1) /* Number of run classes. */
206
207struct kseq {
208 struct runq ksq_idle; /* Queue of IDLE threads. */
209 struct runq ksq_timeshare[2]; /* Run queues for !IDLE. */
210 struct runq *ksq_next; /* Next timeshare queue. */
211 struct runq *ksq_curr; /* Current queue. */
|
212 int ksq_loads[KSEQ_NCLASS]; /* Load for each class */
|
| 212 int ksq_load_timeshare; /* Load for timeshare. */ |
213 int ksq_load; /* Aggregate load. */
214 short ksq_nice[SCHED_PRI_NRESV]; /* KSEs in each nice bin. */
215 short ksq_nicemin; /* Least nice. */
216#ifdef SMP
|
| 217 int ksq_load_transferable; /* kses that may be migrated. */ |
218 unsigned int ksq_rslices; /* Slices on run queue */
219 int ksq_cpus; /* Count of CPUs in this kseq. */
220 struct kse *ksq_assigned; /* KSEs assigned by another CPU. */
221#endif
222};
223
224/*
225 * One kse queue per processor.
226 */
227#ifdef SMP
228static int kseq_idle;
229static struct kseq kseq_cpu[MAXCPU];
230static struct kseq *kseq_idmap[MAXCPU];
231#define KSEQ_SELF() (kseq_idmap[PCPU_GET(cpuid)])
232#define KSEQ_CPU(x) (kseq_idmap[(x)])
233#else
234static struct kseq kseq_cpu;
235#define KSEQ_SELF() (&kseq_cpu)
236#define KSEQ_CPU(x) (&kseq_cpu)
237#endif
238
239static void sched_slice(struct kse *ke);
240static void sched_priority(struct ksegrp *kg);
241static int sched_interact_score(struct ksegrp *kg);
242static void sched_interact_update(struct ksegrp *kg);
243static void sched_interact_fork(struct ksegrp *kg);
244static void sched_pctcpu_update(struct kse *ke);
245
246/* Operations on per processor queues */
247static struct kse * kseq_choose(struct kseq *kseq);
248static void kseq_setup(struct kseq *kseq);
249static void kseq_add(struct kseq *kseq, struct kse *ke);
250static void kseq_rem(struct kseq *kseq, struct kse *ke);
251static void kseq_nice_add(struct kseq *kseq, int nice);
252static void kseq_nice_rem(struct kseq *kseq, int nice);
253void kseq_print(int cpu);
254#ifdef SMP
255#if 0
256static int sched_pickcpu(void);
257#endif
258static struct kse *runq_steal(struct runq *rq);
259static struct kseq *kseq_load_highest(void);
260static void kseq_balance(void *arg);
261static void kseq_move(struct kseq *from, int cpu);
262static int kseq_find(void);
263static void kseq_notify(struct kse *ke, int cpu);
264static void kseq_assign(struct kseq *);
265static struct kse *kseq_steal(struct kseq *kseq);
|
| 266#define KSE_CAN_MIGRATE(ke, class) ((class) != PRI_ITHD) |
267#endif
268
269void
270kseq_print(int cpu)
271{
272 struct kseq *kseq;
273 int i;
274
275 kseq = KSEQ_CPU(cpu);
276
277 printf("kseq:\n");
278 printf("\tload: %d\n", kseq->ksq_load);
|
277 printf("\tload ITHD: %d\n", kseq->ksq_loads[PRI_ITHD]);
278 printf("\tload REALTIME: %d\n", kseq->ksq_loads[PRI_REALTIME]);
279 printf("\tload TIMESHARE: %d\n", kseq->ksq_loads[PRI_TIMESHARE]);
280 printf("\tload IDLE: %d\n", kseq->ksq_loads[PRI_IDLE]);
|
279 printf("\tload REALTIME: %d\n", kseq->ksq_load_timeshare);
280#ifdef SMP
281 printf("\tload transferable: %d\n", kseq->ksq_load_transferable);
282#endif |
283 printf("\tnicemin:\t%d\n", kseq->ksq_nicemin);
284 printf("\tnice counts:\n");
285 for (i = 0; i < SCHED_PRI_NRESV; i++)
286 if (kseq->ksq_nice[i])
287 printf("\t\t%d = %d\n",
288 i - SCHED_PRI_NHALF, kseq->ksq_nice[i]);
289}
290
291static void
292kseq_add(struct kseq *kseq, struct kse *ke)
293{
|
| 294 int class; |
295 mtx_assert(&sched_lock, MA_OWNED);
|
293 kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]++;
|
296 class = PRI_BASE(ke->ke_ksegrp->kg_pri_class);
297 if (class == PRI_TIMESHARE)
298 kseq->ksq_load_timeshare++;
299#ifdef SMP
300 if (KSE_CAN_MIGRATE(ke, class))
301 kseq->ksq_load_transferable++;
302 kseq->ksq_rslices += ke->ke_slice;
303#endif |
304 kseq->ksq_load++;
305 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
306 CTR6(KTR_ULE, "Add kse %p to %p (slice: %d, pri: %d, nice: %d(%d))",
307 ke, ke->ke_runq, ke->ke_slice, ke->ke_thread->td_priority,
308 ke->ke_ksegrp->kg_nice, kseq->ksq_nicemin);
309 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
310 kseq_nice_add(kseq, ke->ke_ksegrp->kg_nice);
|
301#ifdef SMP
302 kseq->ksq_rslices += ke->ke_slice;
303#endif
|
311}
312
313static void
314kseq_rem(struct kseq *kseq, struct kse *ke)
315{
|
| 316 int class; |
317 mtx_assert(&sched_lock, MA_OWNED);
|
310 kseq->ksq_loads[PRI_BASE(ke->ke_ksegrp->kg_pri_class)]--;
|
318 class = PRI_BASE(ke->ke_ksegrp->kg_pri_class);
319 if (class == PRI_TIMESHARE)
320 kseq->ksq_load_timeshare--;
321#ifdef SMP
322 if (KSE_CAN_MIGRATE(ke, class))
323 kseq->ksq_load_transferable--;
324 kseq->ksq_rslices -= ke->ke_slice;
325#endif |
326 kseq->ksq_load--;
327 ke->ke_runq = NULL;
328 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE)
329 kseq_nice_rem(kseq, ke->ke_ksegrp->kg_nice);
|
315#ifdef SMP
316 kseq->ksq_rslices -= ke->ke_slice;
317#endif
|
330}
331
332static void
333kseq_nice_add(struct kseq *kseq, int nice)
334{
335 mtx_assert(&sched_lock, MA_OWNED);
336 /* Normalize to zero. */
337 kseq->ksq_nice[nice + SCHED_PRI_NHALF]++;
|
326 if (nice < kseq->ksq_nicemin || kseq->ksq_loads[PRI_TIMESHARE] == 1)
|
| 338 if (nice < kseq->ksq_nicemin || kseq->ksq_load_timeshare == 1) |
339 kseq->ksq_nicemin = nice;
340}
341
342static void
343kseq_nice_rem(struct kseq *kseq, int nice)
344{
345 int n;
346
347 mtx_assert(&sched_lock, MA_OWNED);
348 /* Normalize to zero. */
349 n = nice + SCHED_PRI_NHALF;
350 kseq->ksq_nice[n]--;
351 KASSERT(kseq->ksq_nice[n] >= 0, ("Negative nice count."));
352
353 /*
354 * If this wasn't the smallest nice value or there are more in
355 * this bucket we can just return. Otherwise we have to recalculate
356 * the smallest nice.
357 */
358 if (nice != kseq->ksq_nicemin ||
359 kseq->ksq_nice[n] != 0 ||
|
348 kseq->ksq_loads[PRI_TIMESHARE] == 0)
|
| 360 kseq->ksq_load_timeshare == 0) |
361 return;
362
363 for (; n < SCHED_PRI_NRESV; n++)
364 if (kseq->ksq_nice[n]) {
365 kseq->ksq_nicemin = n - SCHED_PRI_NHALF;
366 return;
367 }
368}
369
370#ifdef SMP
371/*
372 * kseq_balance is a simple CPU load balancing algorithm. It operates by
373 * finding the least loaded and most loaded cpu and equalizing their load
374 * by migrating some processes.
375 *
376 * Dealing only with two CPUs at a time has two advantages. Firstly, most
377 * installations will only have 2 cpus. Secondly, load balancing too much at
378 * once can have an unpleasant effect on the system. The scheduler rarely has
379 * enough information to make perfect decisions. So this algorithm chooses
380 * algorithm simplicity and more gradual effects on load in larger systems.
381 *
382 * It could be improved by considering the priorities and slices assigned to
383 * each task prior to balancing them. There are many pathological cases with
384 * any approach and so the semi random algorithm below may work as well as any.
385 *
386 */
387static void
388kseq_balance(void *arg)
389{
390 struct kseq *kseq;
391 int high_load;
392 int low_load;
393 int high_cpu;
394 int low_cpu;
395 int move;
396 int diff;
397 int i;
398
399 high_cpu = 0;
400 low_cpu = 0;
401 high_load = 0;
402 low_load = -1;
403
404 mtx_lock_spin(&sched_lock);
405 if (smp_started == 0)
406 goto out;
407
408 for (i = 0; i < mp_maxid; i++) {
409 if (CPU_ABSENT(i) || (i & stopped_cpus) != 0)
410 continue;
411 kseq = KSEQ_CPU(i);
412 if (kseq->ksq_load > high_load) {
413 high_load = kseq->ksq_load;
414 high_cpu = i;
415 }
416 if (low_load == -1 || kseq->ksq_load < low_load) {
417 low_load = kseq->ksq_load;
418 low_cpu = i;
419 }
420 }
421
422 kseq = KSEQ_CPU(high_cpu);
423
|
412 high_load = kseq->ksq_loads[PRI_IDLE] + kseq->ksq_loads[PRI_TIMESHARE] +
413 kseq->ksq_loads[PRI_REALTIME];
|
| 424 high_load = kseq->ksq_load_transferable; |
425 /*
426 * Nothing to do.
427 */
428 if (high_load < kseq->ksq_cpus + 1)
429 goto out;
430
431 high_load -= kseq->ksq_cpus;
432
433 if (low_load >= high_load)
434 goto out;
435
436 diff = high_load - low_load;
437 move = diff / 2;
438 if (diff & 0x1)
439 move++;
440
441 for (i = 0; i < move; i++)
442 kseq_move(kseq, low_cpu);
443
444out:
445 mtx_unlock_spin(&sched_lock);
446 callout_reset(&kseq_lb_callout, hz, kseq_balance, NULL);
447
448 return;
449}
450
451static struct kseq *
452kseq_load_highest(void)
453{
454 struct kseq *kseq;
455 int load;
456 int cpu;
457 int i;
458
459 mtx_assert(&sched_lock, MA_OWNED);
460 cpu = 0;
461 load = 0;
462
463 for (i = 0; i < mp_maxid; i++) {
464 if (CPU_ABSENT(i) || (i & stopped_cpus) != 0)
465 continue;
466 kseq = KSEQ_CPU(i);
467 if (kseq->ksq_load > load) {
468 load = kseq->ksq_load;
469 cpu = i;
470 }
471 }
472 kseq = KSEQ_CPU(cpu);
473
|
463 if ((kseq->ksq_loads[PRI_IDLE] + kseq->ksq_loads[PRI_TIMESHARE] +
464 kseq->ksq_loads[PRI_REALTIME]) > kseq->ksq_cpus)
|
| 474 if (kseq->ksq_load_transferable > kseq->ksq_cpus) |
475 return (kseq);
476
477 return (NULL);
478}
479
480static void
481kseq_move(struct kseq *from, int cpu)
482{
483 struct kse *ke;
484
485 ke = kseq_steal(from);
486 runq_remove(ke->ke_runq, ke);
487 ke->ke_state = KES_THREAD;
488 kseq_rem(from, ke);
489
490 ke->ke_cpu = cpu;
491 sched_add(ke->ke_thread);
492}
493
494static int
495kseq_find(void)
496{
497 struct kseq *high;
498
499 if (!smp_started)
500 return (0);
501 if (kseq_idle & PCPU_GET(cpumask))
502 return (0);
503 /*
504 * Find the cpu with the highest load and steal one proc.
505 */
506 if ((high = kseq_load_highest()) == NULL ||
507 high == KSEQ_SELF()) {
508 /*
509 * If we couldn't find one, set ourselves in the
510 * idle map.
511 */
512 atomic_set_int(&kseq_idle, PCPU_GET(cpumask));
513 return (0);
514 }
515 /*
516 * Remove this kse from this kseq and runq and then requeue
517 * on the current processor. We now have a load of one!
518 */
519 kseq_move(high, PCPU_GET(cpuid));
520
521 return (1);
522}
523
524static void
525kseq_assign(struct kseq *kseq)
526{
527 struct kse *nke;
528 struct kse *ke;
529
530 do {
531 ke = kseq->ksq_assigned;
532 } while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke, NULL));
533 for (; ke != NULL; ke = nke) {
534 nke = ke->ke_assign;
535 ke->ke_flags &= ~KEF_ASSIGNED;
536 sched_add(ke->ke_thread);
537 }
538}
539
540static void
541kseq_notify(struct kse *ke, int cpu)
542{
543 struct kseq *kseq;
544 struct thread *td;
545 struct pcpu *pcpu;
546
547 ke->ke_flags |= KEF_ASSIGNED;
548
549 kseq = KSEQ_CPU(cpu);
550
551 /*
552 * Place a KSE on another cpu's queue and force a resched.
553 */
554 do {
555 ke->ke_assign = kseq->ksq_assigned;
556 } while(!atomic_cmpset_ptr(&kseq->ksq_assigned, ke->ke_assign, ke));
557 pcpu = pcpu_find(cpu);
558 td = pcpu->pc_curthread;
559 if (ke->ke_thread->td_priority < td->td_priority ||
560 td == pcpu->pc_idlethread) {
561 td->td_flags |= TDF_NEEDRESCHED;
562 ipi_selected(1 << cpu, IPI_AST);
563 }
564}
565
566static struct kse *
567runq_steal(struct runq *rq)
568{
569 struct rqhead *rqh;
570 struct rqbits *rqb;
571 struct kse *ke;
572 int word;
573 int bit;
574
575 mtx_assert(&sched_lock, MA_OWNED);
576 rqb = &rq->rq_status;
577 for (word = 0; word < RQB_LEN; word++) {
578 if (rqb->rqb_bits[word] == 0)
579 continue;
580 for (bit = 0; bit < RQB_BPW; bit++) {
581 if ((rqb->rqb_bits[word] & (1 << bit)) == 0)
582 continue;
583 rqh = &rq->rq_queues[bit + (word << RQB_L2BPW)];
584 TAILQ_FOREACH(ke, rqh, ke_procq) {
|
575 if (PRI_BASE(ke->ke_ksegrp->kg_pri_class) !=
576 PRI_ITHD)
|
585 if (KSE_CAN_MIGRATE(ke,
586 PRI_BASE(ke->ke_ksegrp->kg_pri_class))) |
587 return (ke);
588 }
589 }
590 }
591 return (NULL);
592}
593
594static struct kse *
595kseq_steal(struct kseq *kseq)
596{
597 struct kse *ke;
598
599 if ((ke = runq_steal(kseq->ksq_curr)) != NULL)
600 return (ke);
601 if ((ke = runq_steal(kseq->ksq_next)) != NULL)
602 return (ke);
603 return (runq_steal(&kseq->ksq_idle));
604}
605#endif /* SMP */
606
607/*
608 * Pick the highest priority task we have and return it.
609 */
610
611static struct kse *
612kseq_choose(struct kseq *kseq)
613{
614 struct kse *ke;
615 struct runq *swap;
616
617 mtx_assert(&sched_lock, MA_OWNED);
618 swap = NULL;
619
620 for (;;) {
621 ke = runq_choose(kseq->ksq_curr);
622 if (ke == NULL) {
623 /*
624 * We already swaped once and didn't get anywhere.
625 */
626 if (swap)
627 break;
628 swap = kseq->ksq_curr;
629 kseq->ksq_curr = kseq->ksq_next;
630 kseq->ksq_next = swap;
631 continue;
632 }
633 /*
634 * If we encounter a slice of 0 the kse is in a
635 * TIMESHARE kse group and its nice was too far out
636 * of the range that receives slices.
637 */
638 if (ke->ke_slice == 0) {
639 runq_remove(ke->ke_runq, ke);
640 sched_slice(ke);
641 ke->ke_runq = kseq->ksq_next;
642 runq_add(ke->ke_runq, ke);
643 continue;
644 }
645 return (ke);
646 }
647
648 return (runq_choose(&kseq->ksq_idle));
649}
650
651static void
652kseq_setup(struct kseq *kseq)
653{
654 runq_init(&kseq->ksq_timeshare[0]);
655 runq_init(&kseq->ksq_timeshare[1]);
656 runq_init(&kseq->ksq_idle);
|
647
|
657 kseq->ksq_curr = &kseq->ksq_timeshare[0];
658 kseq->ksq_next = &kseq->ksq_timeshare[1];
|
650
651 kseq->ksq_loads[PRI_ITHD] = 0;
652 kseq->ksq_loads[PRI_REALTIME] = 0;
653 kseq->ksq_loads[PRI_TIMESHARE] = 0;
654 kseq->ksq_loads[PRI_IDLE] = 0;
|
659 kseq->ksq_load = 0;
|
| 660 kseq->ksq_load_timeshare = 0; |
661#ifdef SMP
|
| 662 kseq->ksq_load_transferable = 0; |
663 kseq->ksq_rslices = 0;
664 kseq->ksq_assigned = NULL;
665#endif
666}
667
668static void
669sched_setup(void *dummy)
670{
671#ifdef SMP
672 int i;
673#endif
674
675 slice_min = (hz/100); /* 10ms */
676 slice_max = (hz/7); /* ~140ms */
677
678#ifdef SMP
679 /* init kseqs */
680 /* Create the idmap. */
681#ifdef ULE_HTT_EXPERIMENTAL
682 if (smp_topology == NULL) {
683#else
684 if (1) {
685#endif
686 for (i = 0; i < MAXCPU; i++) {
687 kseq_setup(&kseq_cpu[i]);
688 kseq_idmap[i] = &kseq_cpu[i];
689 kseq_cpu[i].ksq_cpus = 1;
690 }
691 } else {
692 int j;
693
694 for (i = 0; i < smp_topology->ct_count; i++) {
695 struct cpu_group *cg;
696
697 cg = &smp_topology->ct_group[i];
698 kseq_setup(&kseq_cpu[i]);
699
700 for (j = 0; j < MAXCPU; j++)
701 if ((cg->cg_mask & (1 << j)) != 0)
702 kseq_idmap[j] = &kseq_cpu[i];
703 kseq_cpu[i].ksq_cpus = cg->cg_count;
704 }
705 }
706 callout_init(&kseq_lb_callout, CALLOUT_MPSAFE);
707 kseq_balance(NULL);
708#else
709 kseq_setup(KSEQ_SELF());
710#endif
711 mtx_lock_spin(&sched_lock);
712 kseq_add(KSEQ_SELF(), &kse0);
713 mtx_unlock_spin(&sched_lock);
714}
715
716/*
717 * Scale the scheduling priority according to the "interactivity" of this
718 * process.
719 */
720static void
721sched_priority(struct ksegrp *kg)
722{
723 int pri;
724
725 if (kg->kg_pri_class != PRI_TIMESHARE)
726 return;
727
728 pri = SCHED_PRI_INTERACT(sched_interact_score(kg));
729 pri += SCHED_PRI_BASE;
730 pri += kg->kg_nice;
731
732 if (pri > PRI_MAX_TIMESHARE)
733 pri = PRI_MAX_TIMESHARE;
734 else if (pri < PRI_MIN_TIMESHARE)
735 pri = PRI_MIN_TIMESHARE;
736
737 kg->kg_user_pri = pri;
738
739 return;
740}
741
742/*
743 * Calculate a time slice based on the properties of the kseg and the runq
744 * that we're on. This is only for PRI_TIMESHARE ksegrps.
745 */
746static void
747sched_slice(struct kse *ke)
748{
749 struct kseq *kseq;
750 struct ksegrp *kg;
751
752 kg = ke->ke_ksegrp;
753 kseq = KSEQ_CPU(ke->ke_cpu);
754
755 /*
756 * Rationale:
757 * KSEs in interactive ksegs get the minimum slice so that we
758 * quickly notice if it abuses its advantage.
759 *
760 * KSEs in non-interactive ksegs are assigned a slice that is
761 * based on the ksegs nice value relative to the least nice kseg
762 * on the run queue for this cpu.
763 *
764 * If the KSE is less nice than all others it gets the maximum
765 * slice and other KSEs will adjust their slice relative to
766 * this when they first expire.
767 *
768 * There is 20 point window that starts relative to the least
769 * nice kse on the run queue. Slice size is determined by
770 * the kse distance from the last nice ksegrp.
771 *
772 * If the kse is outside of the window it will get no slice
773 * and will be reevaluated each time it is selected on the
774 * run queue. The exception to this is nice 0 ksegs when
775 * a nice -20 is running. They are always granted a minimum
776 * slice.
777 */
778 if (!SCHED_INTERACTIVE(kg)) {
779 int nice;
780
781 nice = kg->kg_nice + (0 - kseq->ksq_nicemin);
|
776 if (kseq->ksq_loads[PRI_TIMESHARE] == 0 ||
|
| 782 if (kseq->ksq_load_timeshare == 0 || |
783 kg->kg_nice < kseq->ksq_nicemin)
784 ke->ke_slice = SCHED_SLICE_MAX;
785 else if (nice <= SCHED_SLICE_NTHRESH)
786 ke->ke_slice = SCHED_SLICE_NICE(nice);
787 else if (kg->kg_nice == 0)
788 ke->ke_slice = SCHED_SLICE_MIN;
789 else
790 ke->ke_slice = 0;
791 } else
792 ke->ke_slice = SCHED_SLICE_MIN;
793
794 CTR6(KTR_ULE,
795 "Sliced %p(%d) (nice: %d, nicemin: %d, load: %d, interactive: %d)",
796 ke, ke->ke_slice, kg->kg_nice, kseq->ksq_nicemin,
|
791 kseq->ksq_loads[PRI_TIMESHARE], SCHED_INTERACTIVE(kg));
|
| 797 kseq->ksq_load_timeshare, SCHED_INTERACTIVE(kg)); |
798
799 return;
800}
801
802/*
803 * This routine enforces a maximum limit on the amount of scheduling history
804 * kept. It is called after either the slptime or runtime is adjusted.
805 * This routine will not operate correctly when slp or run times have been
806 * adjusted to more than double their maximum.
807 */
808static void
809sched_interact_update(struct ksegrp *kg)
810{
811 int sum;
812
813 sum = kg->kg_runtime + kg->kg_slptime;
814 if (sum < SCHED_SLP_RUN_MAX)
815 return;
816 /*
817 * If we have exceeded by more than 1/5th then the algorithm below
818 * will not bring us back into range. Dividing by two here forces
819 * us into the range of [3/5 * SCHED_INTERACT_MAX, SCHED_INTERACT_MAX]
820 */
821 if (sum > (SCHED_INTERACT_MAX / 5) * 6) {
822 kg->kg_runtime /= 2;
823 kg->kg_slptime /= 2;
824 return;
825 }
826 kg->kg_runtime = (kg->kg_runtime / 5) * 4;
827 kg->kg_slptime = (kg->kg_slptime / 5) * 4;
828}
829
830static void
831sched_interact_fork(struct ksegrp *kg)
832{
833 int ratio;
834 int sum;
835
836 sum = kg->kg_runtime + kg->kg_slptime;
837 if (sum > SCHED_SLP_RUN_FORK) {
838 ratio = sum / SCHED_SLP_RUN_FORK;
839 kg->kg_runtime /= ratio;
840 kg->kg_slptime /= ratio;
841 }
842}
843
844static int
845sched_interact_score(struct ksegrp *kg)
846{
847 int div;
848
849 if (kg->kg_runtime > kg->kg_slptime) {
850 div = max(1, kg->kg_runtime / SCHED_INTERACT_HALF);
851 return (SCHED_INTERACT_HALF +
852 (SCHED_INTERACT_HALF - (kg->kg_slptime / div)));
853 } if (kg->kg_slptime > kg->kg_runtime) {
854 div = max(1, kg->kg_slptime / SCHED_INTERACT_HALF);
855 return (kg->kg_runtime / div);
856 }
857
858 /*
859 * This can happen if slptime and runtime are 0.
860 */
861 return (0);
862
863}
864
865/*
866 * This is only somewhat accurate since given many processes of the same
867 * priority they will switch when their slices run out, which will be
868 * at most SCHED_SLICE_MAX.
869 */
870int
871sched_rr_interval(void)
872{
873 return (SCHED_SLICE_MAX);
874}
875
876static void
877sched_pctcpu_update(struct kse *ke)
878{
879 /*
880 * Adjust counters and watermark for pctcpu calc.
881 */
882 if (ke->ke_ltick > ticks - SCHED_CPU_TICKS) {
883 /*
884 * Shift the tick count out so that the divide doesn't
885 * round away our results.
886 */
887 ke->ke_ticks <<= 10;
888 ke->ke_ticks = (ke->ke_ticks / (ticks - ke->ke_ftick)) *
889 SCHED_CPU_TICKS;
890 ke->ke_ticks >>= 10;
891 } else
892 ke->ke_ticks = 0;
893 ke->ke_ltick = ticks;
894 ke->ke_ftick = ke->ke_ltick - SCHED_CPU_TICKS;
895}
896
897#if 0
898/* XXX Should be changed to kseq_load_lowest() */
899int
900sched_pickcpu(void)
901{
902 struct kseq *kseq;
903 int load;
904 int cpu;
905 int i;
906
907 mtx_assert(&sched_lock, MA_OWNED);
908 if (!smp_started)
909 return (0);
910
911 load = 0;
912 cpu = 0;
913
914 for (i = 0; i < mp_maxid; i++) {
915 if (CPU_ABSENT(i) || (i & stopped_cpus) != 0)
916 continue;
917 kseq = KSEQ_CPU(i);
918 if (kseq->ksq_load < load) {
919 cpu = i;
920 load = kseq->ksq_load;
921 }
922 }
923
924 CTR1(KTR_ULE, "sched_pickcpu: %d", cpu);
925 return (cpu);
926}
927#endif
928
929void
930sched_prio(struct thread *td, u_char prio)
931{
932 struct kse *ke;
933
934 ke = td->td_kse;
935 mtx_assert(&sched_lock, MA_OWNED);
936 if (TD_ON_RUNQ(td)) {
937 /*
938 * If the priority has been elevated due to priority
939 * propagation, we may have to move ourselves to a new
940 * queue. We still call adjustrunqueue below in case kse
941 * needs to fix things up.
942 */
943 if (prio < td->td_priority && ke &&
944 (ke->ke_flags & KEF_ASSIGNED) == 0 &&
945 ke->ke_runq != KSEQ_CPU(ke->ke_cpu)->ksq_curr) {
946 runq_remove(ke->ke_runq, ke);
947 ke->ke_runq = KSEQ_CPU(ke->ke_cpu)->ksq_curr;
948 runq_add(ke->ke_runq, ke);
949 }
950 adjustrunqueue(td, prio);
951 } else
952 td->td_priority = prio;
953}
954
955void
956sched_switch(struct thread *td)
957{
958 struct thread *newtd;
959 struct kse *ke;
960
961 mtx_assert(&sched_lock, MA_OWNED);
962
963 ke = td->td_kse;
964
965 td->td_last_kse = ke;
966 td->td_lastcpu = td->td_oncpu;
967 td->td_oncpu = NOCPU;
968 td->td_flags &= ~TDF_NEEDRESCHED;
969
970 if (TD_IS_RUNNING(td)) {
971 if (td->td_proc->p_flag & P_SA) {
972 kseq_rem(KSEQ_CPU(ke->ke_cpu), ke);
973 setrunqueue(td);
974 } else {
975 /*
976 * This queue is always correct except for idle threads
977 * which have a higher priority due to priority
978 * propagation.
979 */
980 if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE) {
981 if (td->td_priority < PRI_MIN_IDLE)
982 ke->ke_runq = KSEQ_SELF()->ksq_curr;
983 else
984 ke->ke_runq = &KSEQ_SELF()->ksq_idle;
985 }
986 runq_add(ke->ke_runq, ke);
987 /* setrunqueue(td); */
988 }
989 } else {
990 if (ke->ke_runq)
991 kseq_rem(KSEQ_CPU(ke->ke_cpu), ke);
992 /*
993 * We will not be on the run queue. So we must be
994 * sleeping or similar.
995 */
996 if (td->td_proc->p_flag & P_SA)
997 kse_reassign(ke);
998 }
999 newtd = choosethread();
1000 if (td != newtd)
1001 cpu_switch(td, newtd);
1002 sched_lock.mtx_lock = (uintptr_t)td;
1003
1004 td->td_oncpu = PCPU_GET(cpuid);
1005}
1006
1007void
1008sched_nice(struct ksegrp *kg, int nice)
1009{
1010 struct kse *ke;
1011 struct thread *td;
1012 struct kseq *kseq;
1013
1014 PROC_LOCK_ASSERT(kg->kg_proc, MA_OWNED);
1015 mtx_assert(&sched_lock, MA_OWNED);
1016 /*
1017 * We need to adjust the nice counts for running KSEs.
1018 */
1019 if (kg->kg_pri_class == PRI_TIMESHARE)
1020 FOREACH_KSE_IN_GROUP(kg, ke) {
1021 if (ke->ke_runq == NULL)
1022 continue;
1023 kseq = KSEQ_CPU(ke->ke_cpu);
1024 kseq_nice_rem(kseq, kg->kg_nice);
1025 kseq_nice_add(kseq, nice);
1026 }
1027 kg->kg_nice = nice;
1028 sched_priority(kg);
1029 FOREACH_THREAD_IN_GROUP(kg, td)
1030 td->td_flags |= TDF_NEEDRESCHED;
1031}
1032
1033void
1034sched_sleep(struct thread *td, u_char prio)
1035{
1036 mtx_assert(&sched_lock, MA_OWNED);
1037
1038 td->td_slptime = ticks;
1039 td->td_priority = prio;
1040
1041 CTR2(KTR_ULE, "sleep kse %p (tick: %d)",
1042 td->td_kse, td->td_slptime);
1043}
1044
1045void
1046sched_wakeup(struct thread *td)
1047{
1048 mtx_assert(&sched_lock, MA_OWNED);
1049
1050 /*
1051 * Let the kseg know how long we slept for. This is because process
1052 * interactivity behavior is modeled in the kseg.
1053 */
1054 if (td->td_slptime) {
1055 struct ksegrp *kg;
1056 int hzticks;
1057
1058 kg = td->td_ksegrp;
1059 hzticks = (ticks - td->td_slptime) << 10;
1060 if (hzticks >= SCHED_SLP_RUN_MAX) {
1061 kg->kg_slptime = SCHED_SLP_RUN_MAX;
1062 kg->kg_runtime = 1;
1063 } else {
1064 kg->kg_slptime += hzticks;
1065 sched_interact_update(kg);
1066 }
1067 sched_priority(kg);
1068 if (td->td_kse)
1069 sched_slice(td->td_kse);
1070 CTR2(KTR_ULE, "wakeup kse %p (%d ticks)",
1071 td->td_kse, hzticks);
1072 td->td_slptime = 0;
1073 }
1074 setrunqueue(td);
1075}
1076
1077/*
1078 * Penalize the parent for creating a new child and initialize the child's
1079 * priority.
1080 */
1081void
1082sched_fork(struct proc *p, struct proc *p1)
1083{
1084
1085 mtx_assert(&sched_lock, MA_OWNED);
1086
1087 sched_fork_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(p1));
1088 sched_fork_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(p1));
1089 sched_fork_thread(FIRST_THREAD_IN_PROC(p), FIRST_THREAD_IN_PROC(p1));
1090}
1091
1092void
1093sched_fork_kse(struct kse *ke, struct kse *child)
1094{
1095
1096 child->ke_slice = 1; /* Attempt to quickly learn interactivity. */
1097 child->ke_cpu = ke->ke_cpu; /* sched_pickcpu(); */
1098 child->ke_runq = NULL;
1099
1100 /* Grab our parents cpu estimation information. */
1101 child->ke_ticks = ke->ke_ticks;
1102 child->ke_ltick = ke->ke_ltick;
1103 child->ke_ftick = ke->ke_ftick;
1104}
1105
1106void
1107sched_fork_ksegrp(struct ksegrp *kg, struct ksegrp *child)
1108{
1109 PROC_LOCK_ASSERT(child->kg_proc, MA_OWNED);
1110
1111 child->kg_slptime = kg->kg_slptime;
1112 child->kg_runtime = kg->kg_runtime;
1113 child->kg_user_pri = kg->kg_user_pri;
1114 child->kg_nice = kg->kg_nice;
1115 sched_interact_fork(child);
1116 kg->kg_runtime += tickincr << 10;
1117 sched_interact_update(kg);
1118
1119 CTR6(KTR_ULE, "sched_fork_ksegrp: %d(%d, %d) - %d(%d, %d)",
1120 kg->kg_proc->p_pid, kg->kg_slptime, kg->kg_runtime,
1121 child->kg_proc->p_pid, child->kg_slptime, child->kg_runtime);
1122}
1123
1124void
1125sched_fork_thread(struct thread *td, struct thread *child)
1126{
1127}
1128
1129void
1130sched_class(struct ksegrp *kg, int class)
1131{
1132 struct kseq *kseq;
1133 struct kse *ke;
|
1134 int nclass;
1135 int oclass; |
1136
1137 mtx_assert(&sched_lock, MA_OWNED);
1138 if (kg->kg_pri_class == class)
1139 return;
1140
|
1141 nclass = PRI_BASE(class);
1142 oclass = PRI_BASE(kg->kg_pri_class); |
1143 FOREACH_KSE_IN_GROUP(kg, ke) {
1144 if (ke->ke_state != KES_ONRUNQ &&
1145 ke->ke_state != KES_THREAD)
1146 continue;
1147 kseq = KSEQ_CPU(ke->ke_cpu);
1148
|
1139 kseq->ksq_loads[PRI_BASE(kg->kg_pri_class)]--;
1140 kseq->ksq_loads[PRI_BASE(class)]++;
|
1149#ifdef SMP
1150 if (KSE_CAN_MIGRATE(ke, oclass))
1151 kseq->ksq_load_transferable--;
1152 if (KSE_CAN_MIGRATE(ke, nclass))
1153 kseq->ksq_load_transferable++;
1154#endif
1155 if (oclass == PRI_TIMESHARE)
1156 kseq->ksq_load_timeshare--;
1157 if (nclass == PRI_TIMESHARE)
1158 kseq->ksq_load_timeshare++; |
1159
1160 if (kg->kg_pri_class == PRI_TIMESHARE)
1161 kseq_nice_rem(kseq, kg->kg_nice);
1162 else if (class == PRI_TIMESHARE)
1163 kseq_nice_add(kseq, kg->kg_nice);
1164 }
1165
1166 kg->kg_pri_class = class;
1167}
1168
1169/*
1170 * Return some of the child's priority and interactivity to the parent.
1171 */
1172void
1173sched_exit(struct proc *p, struct proc *child)
1174{
1175 mtx_assert(&sched_lock, MA_OWNED);
1176 sched_exit_kse(FIRST_KSE_IN_PROC(p), FIRST_KSE_IN_PROC(child));
1177 sched_exit_ksegrp(FIRST_KSEGRP_IN_PROC(p), FIRST_KSEGRP_IN_PROC(child));
1178}
1179
1180void
1181sched_exit_kse(struct kse *ke, struct kse *child)
1182{
1183 kseq_rem(KSEQ_CPU(child->ke_cpu), child);
1184}
1185
1186void
1187sched_exit_ksegrp(struct ksegrp *kg, struct ksegrp *child)
1188{
1189 /* kg->kg_slptime += child->kg_slptime; */
1190 kg->kg_runtime += child->kg_runtime;
1191 sched_interact_update(kg);
1192}
1193
1194void
1195sched_exit_thread(struct thread *td, struct thread *child)
1196{
1197}
1198
1199void
1200sched_clock(struct thread *td)
1201{
1202 struct kseq *kseq;
1203 struct ksegrp *kg;
1204 struct kse *ke;
1205
1206 /*
1207 * sched_setup() apparently happens prior to stathz being set. We
1208 * need to resolve the timers earlier in the boot so we can avoid
1209 * calculating this here.
1210 */
1211 if (realstathz == 0) {
1212 realstathz = stathz ? stathz : hz;
1213 tickincr = hz / realstathz;
1214 /*
1215 * XXX This does not work for values of stathz that are much
1216 * larger than hz.
1217 */
1218 if (tickincr == 0)
1219 tickincr = 1;
1220 }
1221
1222 ke = td->td_kse;
1223 kg = ke->ke_ksegrp;
1224
1225 mtx_assert(&sched_lock, MA_OWNED);
1226 KASSERT((td != NULL), ("schedclock: null thread pointer"));
1227
1228 /* Adjust ticks for pctcpu */
1229 ke->ke_ticks++;
1230 ke->ke_ltick = ticks;
1231
1232 /* Go up to one second beyond our max and then trim back down */
1233 if (ke->ke_ftick + SCHED_CPU_TICKS + hz < ke->ke_ltick)
1234 sched_pctcpu_update(ke);
1235
1236 if (td->td_flags & TDF_IDLETD)
1237 return;
1238
1239 CTR4(KTR_ULE, "Tick kse %p (slice: %d, slptime: %d, runtime: %d)",
1240 ke, ke->ke_slice, kg->kg_slptime >> 10, kg->kg_runtime >> 10);
1241 /*
1242 * We only do slicing code for TIMESHARE ksegrps.
1243 */
1244 if (kg->kg_pri_class != PRI_TIMESHARE)
1245 return;
1246 /*
1247 * We used a tick charge it to the ksegrp so that we can compute our
1248 * interactivity.
1249 */
1250 kg->kg_runtime += tickincr << 10;
1251 sched_interact_update(kg);
1252
1253 /*
1254 * We used up one time slice.
1255 */
1256 ke->ke_slice--;
1257 kseq = KSEQ_SELF();
1258#ifdef SMP
1259 kseq->ksq_rslices--;
1260#endif
1261
1262 if (ke->ke_slice > 0)
1263 return;
1264 /*
1265 * We're out of time, recompute priorities and requeue.
1266 */
1267 kseq_rem(kseq, ke);
1268 sched_priority(kg);
1269 sched_slice(ke);
1270 if (SCHED_CURR(kg, ke))
1271 ke->ke_runq = kseq->ksq_curr;
1272 else
1273 ke->ke_runq = kseq->ksq_next;
1274 kseq_add(kseq, ke);
1275 td->td_flags |= TDF_NEEDRESCHED;
1276}
1277
1278int
1279sched_runnable(void)
1280{
1281 struct kseq *kseq;
1282 int load;
1283
1284 load = 1;
1285
1286 mtx_lock_spin(&sched_lock);
1287 kseq = KSEQ_SELF();
1288#ifdef SMP
1289 if (kseq->ksq_assigned)
1290 kseq_assign(kseq);
1291#endif
1292 if ((curthread->td_flags & TDF_IDLETD) != 0) {
1293 if (kseq->ksq_load > 0)
1294 goto out;
1295 } else
1296 if (kseq->ksq_load - 1 > 0)
1297 goto out;
1298 load = 0;
1299out:
1300 mtx_unlock_spin(&sched_lock);
1301 return (load);
1302}
1303
1304void
1305sched_userret(struct thread *td)
1306{
1307 struct ksegrp *kg;
1308
1309 kg = td->td_ksegrp;
1310
1311 if (td->td_priority != kg->kg_user_pri) {
1312 mtx_lock_spin(&sched_lock);
1313 td->td_priority = kg->kg_user_pri;
1314 mtx_unlock_spin(&sched_lock);
1315 }
1316}
1317
1318struct kse *
1319sched_choose(void)
1320{
1321 struct kseq *kseq;
1322 struct kse *ke;
1323
1324 mtx_assert(&sched_lock, MA_OWNED);
1325 kseq = KSEQ_SELF();
1326#ifdef SMP
1327retry:
1328 if (kseq->ksq_assigned)
1329 kseq_assign(kseq);
1330#endif
1331 ke = kseq_choose(kseq);
1332 if (ke) {
1333#ifdef SMP
1334 if (ke->ke_ksegrp->kg_pri_class == PRI_IDLE)
1335 if (kseq_find())
1336 goto retry;
1337#endif
1338 runq_remove(ke->ke_runq, ke);
1339 ke->ke_state = KES_THREAD;
1340
1341 if (ke->ke_ksegrp->kg_pri_class == PRI_TIMESHARE) {
1342 CTR4(KTR_ULE, "Run kse %p from %p (slice: %d, pri: %d)",
1343 ke, ke->ke_runq, ke->ke_slice,
1344 ke->ke_thread->td_priority);
1345 }
1346 return (ke);
1347 }
1348#ifdef SMP
1349 if (kseq_find())
1350 goto retry;
1351#endif
1352
1353 return (NULL);
1354}
1355
1356void
1357sched_add(struct thread *td)
1358{
1359 struct kseq *kseq;
1360 struct ksegrp *kg;
1361 struct kse *ke;
1362 int class;
1363
1364 mtx_assert(&sched_lock, MA_OWNED);
1365 ke = td->td_kse;
1366 kg = td->td_ksegrp;
1367 if (ke->ke_flags & KEF_ASSIGNED)
1368 return;
1369 kseq = KSEQ_SELF();
1370 KASSERT((ke->ke_thread != NULL), ("sched_add: No thread on KSE"));
1371 KASSERT((ke->ke_thread->td_kse != NULL),
1372 ("sched_add: No KSE on thread"));
1373 KASSERT(ke->ke_state != KES_ONRUNQ,
1374 ("sched_add: kse %p (%s) already in run queue", ke,
1375 ke->ke_proc->p_comm));
1376 KASSERT(ke->ke_proc->p_sflag & PS_INMEM,
1377 ("sched_add: process swapped out"));
1378 KASSERT(ke->ke_runq == NULL,
1379 ("sched_add: KSE %p is still assigned to a run queue", ke));
1380
1381 class = PRI_BASE(kg->kg_pri_class);
1382 switch (class) {
1383 case PRI_ITHD:
1384 case PRI_REALTIME:
1385 ke->ke_runq = kseq->ksq_curr;
1386 ke->ke_slice = SCHED_SLICE_MAX;
1387 ke->ke_cpu = PCPU_GET(cpuid);
1388 break;
1389 case PRI_TIMESHARE:
1390#ifdef SMP
1391 if (ke->ke_cpu != PCPU_GET(cpuid)) {
1392 kseq_notify(ke, ke->ke_cpu);
1393 return;
1394 }
1395#endif
1396 if (SCHED_CURR(kg, ke))
1397 ke->ke_runq = kseq->ksq_curr;
1398 else
1399 ke->ke_runq = kseq->ksq_next;
1400 break;
1401 case PRI_IDLE:
1402#ifdef SMP
1403 if (ke->ke_cpu != PCPU_GET(cpuid)) {
1404 kseq_notify(ke, ke->ke_cpu);
1405 return;
1406 }
1407#endif
1408 /*
1409 * This is for priority prop.
1410 */
1411 if (ke->ke_thread->td_priority < PRI_MIN_IDLE)
1412 ke->ke_runq = kseq->ksq_curr;
1413 else
1414 ke->ke_runq = &kseq->ksq_idle;
1415 ke->ke_slice = SCHED_SLICE_MIN;
1416 break;
1417 default:
1418 panic("Unknown pri class.");
1419 break;
1420 }
1421#ifdef SMP
1422 /*
1423 * If there are any idle processors, give them our extra load.
1424 */
1425 if (kseq_idle && class != PRI_ITHD &&
|
1408 (kseq->ksq_loads[PRI_IDLE] + kseq->ksq_loads[PRI_TIMESHARE] +
1409 kseq->ksq_loads[PRI_REALTIME]) >= kseq->ksq_cpus) {
|
| 1426 kseq->ksq_load_transferable >= kseq->ksq_cpus) { |
1427 int cpu;
1428
1429 /*
1430 * Multiple cpus could find this bit simultaneously but the
1431 * race shouldn't be terrible.
1432 */
1433 cpu = ffs(kseq_idle);
1434 if (cpu) {
1435 cpu--;
1436 atomic_clear_int(&kseq_idle, 1 << cpu);
1437 ke->ke_cpu = cpu;
1438 ke->ke_runq = NULL;
1439 kseq_notify(ke, cpu);
1440 return;
1441 }
1442 }
1443 if (class == PRI_TIMESHARE || class == PRI_REALTIME)
1444 atomic_clear_int(&kseq_idle, PCPU_GET(cpumask));
1445#endif
1446 if (td->td_priority < curthread->td_priority)
1447 curthread->td_flags |= TDF_NEEDRESCHED;
1448
1449 ke->ke_ksegrp->kg_runq_kses++;
1450 ke->ke_state = KES_ONRUNQ;
1451
1452 runq_add(ke->ke_runq, ke);
1453 kseq_add(kseq, ke);
1454}
1455
1456void
1457sched_rem(struct thread *td)
1458{
1459 struct kseq *kseq;
1460 struct kse *ke;
1461
1462 ke = td->td_kse;
1463 /*
1464 * It is safe to just return here because sched_rem() is only ever
1465 * used in places where we're immediately going to add the
1466 * kse back on again. In that case it'll be added with the correct
1467 * thread and priority when the caller drops the sched_lock.
1468 */
1469 if (ke->ke_flags & KEF_ASSIGNED)
1470 return;
1471 mtx_assert(&sched_lock, MA_OWNED);
1472 KASSERT((ke->ke_state == KES_ONRUNQ), ("KSE not on run queue"));
1473
1474 ke->ke_state = KES_THREAD;
1475 ke->ke_ksegrp->kg_runq_kses--;
1476 kseq = KSEQ_CPU(ke->ke_cpu);
1477 runq_remove(ke->ke_runq, ke);
1478 kseq_rem(kseq, ke);
1479}
1480
1481fixpt_t
1482sched_pctcpu(struct thread *td)
1483{
1484 fixpt_t pctcpu;
1485 struct kse *ke;
1486
1487 pctcpu = 0;
1488 ke = td->td_kse;
1489 if (ke == NULL)
1490 return (0);
1491
1492 mtx_lock_spin(&sched_lock);
1493 if (ke->ke_ticks) {
1494 int rtick;
1495
1496 /*
1497 * Don't update more frequently than twice a second. Allowing
1498 * this causes the cpu usage to decay away too quickly due to
1499 * rounding errors.
1500 */
1501 if (ke->ke_ltick < (ticks - (hz / 2)))
1502 sched_pctcpu_update(ke);
1503 /* How many rtick per second ? */
1504 rtick = min(ke->ke_ticks / SCHED_CPU_TIME, SCHED_CPU_TICKS);
1505 pctcpu = (FSCALE * ((FSCALE * rtick)/realstathz)) >> FSHIFT;
1506 }
1507
1508 ke->ke_proc->p_swtime = ke->ke_ltick - ke->ke_ftick;
1509 mtx_unlock_spin(&sched_lock);
1510
1511 return (pctcpu);
1512}
1513
1514int
1515sched_sizeof_kse(void)
1516{
1517 return (sizeof(struct kse) + sizeof(struct ke_sched));
1518}
1519
1520int
1521sched_sizeof_ksegrp(void)
1522{
1523 return (sizeof(struct ksegrp) + sizeof(struct kg_sched));
1524}
1525
1526int
1527sched_sizeof_proc(void)
1528{
1529 return (sizeof(struct proc));
1530}
1531
1532int
1533sched_sizeof_thread(void)
1534{
1535 return (sizeof(struct thread) + sizeof(struct td_sched));
1536}
|