Question

Compare and contrast the evolution of the default BSD/FreeBSD and Linux schedulers.

Answer

(This work belongs to --Mike Preston 23:01, 13 October 2010 (UTC))

One of the most difficult problems that operating systems must handle is process management. In order to ensure that a system will run efficiently, processes must be maintained, prioritized, categorized and communicated with all without experiencing critical errors such as race conditions or process starvation. A critical component in the management of such issues is the operating system’s scheduler. The goal of a scheduler is to ensure that all processes of a computer system get access to the system resources they require as efficiently as possible while maintaining fairness for each process, limiting CPU wait times, and maximizing the throughput of the system (Jensen: 1985). As computer hardware has increased in complexity, for example multiple core CPUs, schedulers of operating systems have similarly evolved to handle these additional challenges. In this article we will compare and contrast the evolution of two such schedulers; the default BSD/FreeBSD and Linux schedulers.

BSD/Free BSD Schedulers

Overview & History

(This work belongs to --Mike Preston 23:41, 13 October 2010 (UTC))

The FreeBSD kernel originally inherited its scheduler from BSD which itself is a version of the UNIX scheduler. In order to understand the evolution of the FreeBSD scheduler it is important to understand the original purpose and limitations of the BSD scheduler. The BSD scheduler was designed to work on a single core computer system and handle relatively small numbers of processes. As a result, managing resources with a scheduler which operates in O(n) time did not raise any performance issues for BSD. To ensure fairness, the scheduler would switch between processes every 0.1 seconds in a round-robin format [1].

As computer systems increased in complexity, specifically the addition of multiple processors, computer programs increased in size as well. Although the additional complexity increased what could be accomplished with a computer, it also highlighted the problem of having a O(n) scheduler; as more items are added to the scheduling algorithm, performance decreases. With symmetric multiprocessing becoming inevitable a better scheduler was required. This was the driving force behind the creation of FreeBSD.

Older Versions

(This work belongs to --Mike Preston 00:02, 14 October 2010 (UTC))

The FreeBSD kernel originally used an enhanced version of the BSD scheduler. Specifically, the FreeBSD scheduler included classes of threads which was a drastic change from the round-robin scheduling used in BSD. Initially, there were two types of thread class, real-time and idle [2], and the scheduler would give processor time to real-time threads first and the idle threads had to wait until there were no real-time threads that needed access to the processor.

To manage the various threads, FreeBSD had data structures called runqueues into which the threads were placed. The scheduler would evaluate the runqueues based on priority from highest to lowest and execute the first thread of a non-empty runqueue it found. Once a non-empty runqueue was found, each thread in the runqueue would be assigned an equal value time slice of 0.1 seconds, a value that has not changed in over 20 years [3].

Unfortunately, like the BSD scheduler it was based on, the origianl FreeBSD scheduler was not built to handle Symmetric Multiprocessing or Symmetric Multithreading on multi-core systems. The sheduler was still limited by a O(n) algorithm which could not efficiently handle the loads required on ever increasingly powerful systems. To allow FreeBSD to operate with more modern computer systems, a new scheduler, the ULE scheduler, was necessary.

Current Version

(This work is owned by --Mike Preston 00:23, 14 October 2010 (UTC))

In order to effectively manage multi-core computer systems, FreeBSD needed a scheduler with an algorithm which would execute in constant time regardless of the number of threads involved. The ULE scheduler was designed for this purpose. It is of interest to note that throughout the course of the BSD/FreeBSD scheduler evolution, each iteration has just been an improvement on existing scheduler technologies. Although each version was designed to provide support for some current reality of computing, like multi-core systems, the evolution was out of necessity and not due to a desire to re-evaluate how the current version accomplished its tasks.

The "slow" evolution of the FreeBSD scheduler becomes even more evident when comparing it to the Linux scheduler which has evolved through a series of attempts to provide alternative ways to solve scheduling tasks. From dynamic time slices, to various data structure implimentations, and even various ways of describing prioritiy levels (see: "nice" levels), the Linux scheduler advancement has occurred through a series of drastic changes. In comparison, the FreeBSD scheduler has been changed only when the current version was no longer able to meet the needs of the existing computing climate.

Linux Schedulers

(Note to the other group members: Feel free to modify or remove anything I post here. I'm just trying to piece together what you've all posted in the discussion section and turn it into a single paragraph. You know. Just to see how it looks.)

-- Austin Bondio Last edit: 22:17, 13 October 2010 (UTC)

(Same for me, I'm trying to put together the overview/history and work on the comparison section of the essay, all based off the history you guys give. If I miss anything or get anything wrong, feel free to correct.)

-- Wesley Lawrence

(Austin - I added a reference to one of your sections as the current reference only went to wikipedia which the prof has kind of implied is not a good idea, I also added another one that was to a blog post as that was another thing the prof mentioned was not the best idea. I am hoping this will provide additional alidations to the sources.) --Mike Preston 00:29, 14 October 2010 (UTC)

Overview & History

(This work belongs to Wesley Lawrence)

The Linux scheduler has a large history of improvement, always aiming towards having a fair and fast scheduler. Various methods and concepts have been tried over different versions to get this fair and fast scheduler, including round robins, iteration, and queues. A quick read through of the history of Linux implies that firstly, equal and balanced use of the system was the goal of the scheduler, and once that was in place, speed was soon improved. Early schedulers did their best to give processes equal time and resources, but used a bit of extra time (in computer terms) to accomplish this. By Linux 2.6, after experimenting with different concepts, the scheduler was able to provide fair access and time, as well as run as quickly as possible, with various features to allow personal tweaking by the system user, or even the processes themselves.

(This work was done by Austin Bondio)

The Linux kernel has undergone many changes over the decades since its original release as the UNIX operating system in 1969 [4](Stallings: 2009). The early versions had relatively inefficient schedulers which operated in linear time with respect to the number of tasks to schedule; currently the Linux scheduler is able to operate in constant time, independent of the number of tasks being scheduled.

There are five basic algorithms for allocating CPU time[5][6]:

First-in, First-out: No multi-tasking. Processes are queued in the order they are called. A process gets full, uninterrupted use of the CPU until it has finished running.
Shortest Time Remaining: Limited multi-tasking. The CPU handles the easiest tasks first, and complex, time-consuming tasks are handled last.
Fixed-Priority Preemptive Scheduling: Greater multi-tasking. Processes are assigned priority levels which are independent of their complexity. High-priority processes can be completed quickly, while low-priority processes can take a long time as new, higher-priority processes arrive and interrupt them.
Round-Robin Scheduling: Fair multi-tasking. This method is similar in concept to Fixed-Priority Preemptive Scheduling, but all processes are assigned the same priority level; that is, every running process is given an equal share of CPU time.
Multilevel Queue Scheduling: Rule-based multi-taksing. This method is also similar to Fixed-Priority Preemptive Scheduling, but processes are associated with groups that help determine how high their priorities are. For example, all I/O tasks get low priority since much time is spent waiting for the user to interact with the system.

Older Versions

(This work belongs to Sschnei1)

In Linux 1.2 a scheduler operated with a round robin policy using a circular queue, allowing the scheduler to be efficient in adding and removing processes. When Linux 2.2 was introduced, the scheduler was changed. It now used the idea of scheduling classes, thus allowing it to schedule real-time tasks, non real-time tasks, and non-preemptible tasks. It was the first scheduler which supported SMP.

With the introduction of Linux 2.4, the scheduler was changed again. The scheduler started to be more complex than its predecessors, but it also has more features. The running time was O(n) because it iterated over each task during a scheduling event. The scheduler divided tasks into epochs, allowing each task to execute up to its time slice. If a task did not use up all of its time slice, the remaining time was added to the next time slice to allow the task to execute longer in its next epoch. The scheduler simply iterated over all tasks, which made it inefficient, low in scalability and did not have a useful support for real-time systems. On top of that, it did not have features to exploit new hardware architectures, such as multi-core processors.

Current Version

(This work was done by Sschnei1)

As of the Linux 2.6.23 introduction the CFS scheduler took its place in the kernel. CFS uses the idea of maintaining fairness in providing processor time to tasks, which means each tasks gets a fair amount of time to run on the processor. When the time task is out of balance, it means the tasks has to be given more time because the scheduler has to keep fairness. To determine the balance, the CFS maintains the amount of time given to a task, which is called a virtual runtime.

The model how the CFS executes has changed, too. The scheduler now runs a time-ordered red-black tree. It is self-balancing and runs in O(log n) where n is the amount of nodes in the tree, allowing the scheduler to add and erase tasks efficiently. Tasks with the most need of processor are stored in the left side of the tree. Therefore, tasks with a lower need of cpu are stored in the right side of the tree. To keep fairness the scheduler takes the left most node from the tree. The scheduler then accounts execution time at the CPU and adds it to the virtual runtime. If runnable the task then is inserted into the red-black tree. This means tasks on the left side are given time to execute, while the contents on the right side of the tree are migrated to the left side to maintain fairness.

(This work was done by Austin Bondio)

Under a recent Linux system (version 2.6.35 or later), scheduling can be handled manually by the user by assigning programs different priority levels, called "nice levels." Put simply, the higher a program's nice level is, the nicer it will be about sharing system resources. A program with a lower nice level will be more greedy, and a program with a higher nice level will more readily give up its CPU time to other, more important programs. This spectrum is not linear; programs with high negative nice levels run significantly faster than those with high positive nice levels. The Linux scheduler accomplishes this by sharing CPU usage in terms of time slices (also called quanta), which refer to the length of time a program can use the CPU before being forced to give it up. High-priority programs get much larger time slices, allowing them to use the CPU more often and for longer periods of time than programs with lower priority. Users can adjust the niceness of a program using the shell command nice( ). Nice values can range from -20 to +19.

In previous versions of Linux, the scheduler was dependent on the clock speed of the processor. While this dependency was an effective way of dividing up time slices, it made it impossible for the Linux developers to fine-tune their scheduler to perfection. In recent releases, specific nice levels are assigned fixed-size time slices instead. This keeps nice programs from trying to muscle in on the CPU time of less nice programs, and also stops the less nice programs from stealing more time than they deserve.

In addition to this fixed style of time slice allocation, Linux schedulers also have a more dynamic feature which causes them to monitor all active programs. If a program has been waiting an abnormally long time to use the processor, it will be given a temporary increase in priority to compensate. Similarly, if a program has been hogging CPU time, it will temporarily be given a lower priority rating.

Tabulated Results

(Once I read/see some history on the BSD section above, I'll do the best comparison I can. I'm balancing 3000/3004 and other courses (like most of you), so I don't think I can research/write BSD and write the comparison, but I will try to help out as much as I can)

-- Wesley Lawrence

Current Challenges

Resources

1. Jensen, Douglas E., C. Douglass Locke and Hideyuki Tokuda, A Time-Driven Scheduling Model for Real-Time Operating Systems, Carnegie-Mellon University, 1985.

2. Stallings, William, Operating Systems: Internals and Design Principles, Pearson Prentice Hall, 2009.