What's what on the scheduler in FreeBSD 5.x
yangshazhou at hotmail.com
yangshazhou at hotmail.com
Tue Aug 31 19:38:38 PDT 2004
Hi all,
I've very interested in scheduler implementation. I got some opinions on
FreeBSD5's scheduler from source codes and articles. And I presented here,
waiting for critism, for I'm new to FreeBSD.
KSE
1.an implementation of SA (Scheduler activation), two-level co-operating
scheduling of kernel and userland.
2.One process can own multiple KSEG, each with different schedule policy
and diffferent priority.
3.KSE load kernel thread and userland thread to run, as a virtual CPU.
Scheduler's choosing policy is based on the KSE-loaded thread's priority,
the highest gets running and the KSEs with the same priority get
round-robin.
4.The userland scheduler can implement more reasonable, more complex
policy. But now, it's quite simple.
Time Slice
1.Actually No time-slice. It's some periodic functions to make threads
be preemptied.
2.roundrobin() works every 100ms. Other periodic functions sleep longer
till run, eg, 1s for schedcpu(). Then we can conclude roundrobin() can
invoke a schedule action every 100ms, re-selecting better KSEs to run.
That's the same effect as constant 100ms time slice.
3.100ms is a reasonable value, maybe coming from experience. sysctl can
change it as wish.
Priority
1.The principle is lower response time as well as higher through-put.
2.The behaviour of kg_estcpu is the key: threads long-running will be
punished, ready threads long-waiting will get promotion, and the
long-sleeping threads get promotion when awaken too.
3.Priorities are stored in KSEGs, and will be updated to threads
momently. At the same time, the system update (according to kg_estcpu and
other factors) the priorities of all of the threads every 1 second. Threads
will be re-sort in run queue then.
Interactive process
1.The characters for interactive processes: sleep more and longer.
2.CPU-intensive processes run longer, be punished; The promotion will be
enlarged when sleep time extends some certain value.
3.No influence from sleep times till now.
Real-time
1.No realtime support basically. Realtime processes have higher
priority, and that's all. The same implemention in scheduling algorithm.
2.No kernel pre-emptive support.
Multi-processor
1.4BSD scheduler, the default: Giant lock, no CPU-affinity, no SMT/NUMA
support/optimizing.
2.ULE scheduler, the one especially for SMP: multi-runqueue, supporting
CPU-affinity and thread transfer according to load. Strangely, no
load-balance as 'pull' told in ULE's document, no kseq-group (multi logic
CPUs mapped to the same kseq), and then actually no SMT/NUMA support too,
which are all promised in the document.
More information about the freebsd-hackers
mailing list