Blu3c4t Journal

Few days ago... I got read some articles about new thread scheduler in Freebsd, and the name of that new scheduler is ULE. And then what are the new features of ULE scheduler or the differences between ULE scheduler with 4BSD scheduler (FreeBSD's old scheduler) ?

Ok... let's discuss it !!!

The current FreeBSD scheduler (4BSD scheduler) has its roots in the 4.3BSD scheduler.
It has excellent interactive performance and efficient algorithms with small loads. It does not, however, take full advantage of multiple CPUs. It has no support for processor affinity or binding. It also has no mechanism for distinguishing between CPUs of varying capability, which is important for SMT (Symmetric Multi-Threading).

FreeBSD inherited the traditional BSD scheduler when it branched off from 4.3BSD. FreeBSD extended the scheduler's functionality, adding scheduling classes and basic SMP support.
Two new classes, real-time and idle, were added early on in FreeBSD. Idle priority threads are only run when there are no time sharing or real-time threads to run. Real-time threads are allowed to run until they block or until a higher priority real-time thread becomes available. When the SMP project was introduced, an interrupt class was added as well. Interrupt class threads have the same properties as real-time except that their priorities are lower, where lower priorities are given preference in BSD. The classes are simply implemented as subdivisions of the available priority space. The time sharing class is the only subdivision which adjusts priorities based on CPU usage. Much effort went into tuning the various parameters of the 4BSD scheduler to achieve good interactive performance under heavy load as was required by BSD's primary user base. It was very important that systems remain responsive while being used as a server. In addition to this, the nice concept was further refined. To facilitate the use of programs that wish to only consume idle CPU slices, processes with a nice setting more than 20 higher than the least nice currently running process will not be permitted to run at all. This allows distributed programs such as SETI or the rc4 cracking project to run without impacting the normal workload of a machine.

And... the ULE scheduler was designed to address the growing needs of FreeBSD on SMP/SMT platforms and under heavy workloads. It supports CPU affinity and has constant execution time regardless of the number of threads. In addition to these primary performance related goals, it also is careful to identify interactive tasks and give them the lowest latency response possible. The core scheduling components include several queues, two CPU load-balancing algorithms, an interactivity scorer, a CPU usage estimator, a slice calculator, and a priority calculator.

The original FreeBSD scheduler maintains a global list of threads that it traverses once per second to recalculate their priorities. The use of a single list for all threads means that the performance of the scheduler is dependent on the number of tasks in the system, and as the number of tasks grows, more CPU time must be spent in the scheduler maintaining the list. A design goal of the ULE scheduler was to avoid the need to consider all the runnable threads in the system to make a scheduling decision.

The ULE scheduler creates a set of three queues for each CPU in the system. Having per-processor queues makes it possible to implement processor affinity in an SMP system.

One queue is the idle queue, where all idle threads are stored. The other two queues are designated current and next. Threads are picked to run, in priority order, from the current queue until it is empty, at which point the current and next queues are swapped and scheduling is started again. Threads in the idle queue are run only when the other two queues are empty. Realtime and interrupt threads are always inserted into the current queue so that they will have the least possible scheduling latency. Interactive threads are also inserted into the current queue to keep the interactive response of the system acceptable. A thread is considered to be interactive if the ratio of its voluntary sleep time versus its runtime is below a certain threshold. The interactivity threshold is defined in the ULE code and is not configurable. ULE uses two equations to compute the interactivity score of a thread. For threads whose sleep time exceeds their runtime, the following equation is used :


When a thread’s runtime exceeds its sleep time, the following equation is used instead :


The scaling factor is the maximum interactivity score divided by two. Threads that score below the interactivity threshold are considered to be interactive; all others are noninteractive. The sched_interact_update() routine is called at several points in a thread’s existence—for example, when the thread is awakened by a wakeup() call—to update the thread’s runtime and sleep time. The sleep-time and runtime values are allowed to grow only to a certain limit. When the sum of the runtime and sleep time passes the limit, the values are reduced to bring them back into range. An interactive thread whose sleep history was not remembered at all would not remain interactive, resulting in a poor user experience. Remembering an interactive thread’s sleep time for too long would allow the thread to have more than its fair share of the CPU. The amount of history that is kept and the interactivity threshold are the two values that most strongly influence a user’s interactive experience on the system.

Noninteractive threads are put into the next queue and are scheduled to run when the queues are switched. Switching the queues guarantees that a thread gets to run at least once every two queue switches regardless of priority, which ensures fair sharing of the processor.


--------

Now, i will try to recompile my FreeBSD kernel and append the ULE Scheduler as thread scheduler on my system...

[blu3c4t@mahardhika ~]$ cd /usr/src/sys/i386/conf
[blu3c4t@mahardhika /usr/src/sys/i386/conf]$ su
Password:
[root@mahardhika /usr/src/sys/i386/conf]# cp GENERIC ULEKERNEL
[root@mahardhika /usr/src/sys/i386/conf]# vi ULEKERNEL

[edit the configuration file]
1. Comment out line "options SCHED_4BSD" with a # in the front. And add this line :

options SCHED_ULE # ULE scheduler

2. Change the ident line as follows :

ident GENERIC

Change the line to read :

ident ULEKERNEL

[save the configuration file]

It's time to compile the kernel.
[root@mahardhika /usr/src/sys/i386/conf]# cd /usr/src
[root@mahardhika /usr/src]# make buildkernel KERNCONF=ULEKERNEL
[root@mahardhika /usr/src]# make installkernel KERNCONF=ULEKERNEL

It's done, let's reboot now !!!

[root@mahardhika /usr/src]# shutdown -r now

Then after the reboot...

[root@mahardhika ~]# uname -a
FreeBSD mahardhika.stttelkom.ac.id 6.2-RELEASE FreeBSD 6.2-RELEASE #0: Sun Nov 25 23:02:06 WIT 2007 blu3c4t@mahardhika.stttelkom.ac.id:/usr/obj/usr/src/sys/mahardhika i386



Summary

Until now there are many debates about ULE Sceheduler performance compare to 4BSD Scheduler, but as a FreeBSD fan, I hope the new scheduler will bring advance improvement to FreeBSD.

You can see ULE vs. 4BSD performance benchmark at this link:
http://www.thejemreport.com/mambo/content/view/113/