Time slicing -- How does 4.3bsd do it?

[Bret McKee]

The BSD scheduler is a non-trivial animal.  The following description is 
actually for 4.2, but I believe it is little changed in 4.3.

Each process is assigned a priority between 0 and 127.  In the BSD
scheme lower numbers mean higher priority.  The scheduler maintains 32
queues, numbered 0 to 31.  (There are 31 queues instead of 127 for reasons
of efficiency) Each process is maintained on queue[priority/4].  At any 
instant in time the process with the highest priority (lowest number) is 
the running process (for these purposes all processes on the same queue 
are considered to have the same priority).

These queues are divided into two distinct groups: processes on queues 0-11 are 
said to be executing at kernel priority while those on queues 12-31 are 
executing at user priority.  The major differences between the two priority
levels is that kernel priority processes are never preempted and kernel 
priority does not degrade.  User priorities on the other hand do degrade based 
upon system load and process CPU usage. 

non-kernel priority process priority is computed as follows:

     priority = P_USER + cpu_used/CPU_DIVISOR + nice_value*NICE_MULTIPLIER
where:
	P_USER is the constant 50
	CPU_DIVISOR is the constant 4
	NICE_MULTIPLIER is the constant 2


The P_USER term is added to prevennt a process from "aging" its way into
kernel priority.

Every 10ms the cpu component of the priority of a process is incremented, 
and whenever it is divisible by CPU_DIVISOR the process is moved to 
a lower queue.  

Once per second the cpu_component is recomputed to be:

	(new)cpu_usage = cpu_usage*load_decay_factor+nice_value
where:
	load_decay_factor = load_factor/(load_factor+1)
 	load_factor = DECAY_SCALE*load_average
	DECAY_SCALE is a constant whose value is 2
	load_average is the average number of waiting processes over the last 
		60 seconds

This will allow a process to be "forgiven" for time it has used in the past.
As the system becomes more loaded, the load_decay_factor approaches 1, making
the usage degrade more slowly.

Kernel priority is assigned when a process must sleep waiting for some event.
The idea is that since this process is going to be waiting for a while, it 
should be quickly restarted when the wait is over.  This will I/O bound
processes to make better progress.  When the process is awakened its priority
is raised until it is finished with the system call it had made, at which time
its priority is recomputed.  While sleeping, the cpu_usage term is 
aged as:

	(new)cpu_usage = cpu_usage*load_decay_factor^(seconds slept-1)

Once every 100 ms the scheduler recomputes prioritys of all processes to allow
multiple processes in the bottom queue to fight for time.  The scheduler can
also be invoked when an interrupt as been serviced.  

So, the answer to "what is the quantum" is approximately CPU_DIVISOR*10ms for
a system with "a normal load".  What a long winded answer to a simple 
question. Sigh. 


---
Bret Mckee

Hewlett Packard 
HP-UX Kernel Group
Phone:(303)229-6116	email: mckee%hpfcde at hplabs.hp.com