Page 1 of 1

An Introduction to the Linux Scheduler What goes on in the 2.4 and 2.6 scheduler Rate Topic: ***** 1 Votes

#1 rahulbatra  Icon User is offline

  • D.I.C Head
  • member icon

Reputation: 16
  • View blog
  • Posts: 183
  • Joined: 28-December 05

Posted 03 August 2006 - 12:29 AM

An Introduction to the Linux Scheduler

Let us first understand what is a scheduler in the first place. Everybody loads an Operating System, right? And these may range from Microsoft Windows to GNU/Linux to any other that you may have heard of or tried. Now you may also have moticed that many of these operating systems (including the former two), can do a number of tasks at a time. Now the catch is that there is supposing one CPU processor on most of the computers that these operating systems use. So how the hell does the computer, or more specifically the operating system know which task to run now? And here comes the Scheduler.

The basic task of the scheduler is to manage these multiple tasks, and decide which task will get the CPU utilization now. A challenge in developing a good scheduler is to make sure that the applications get a fair amount of their share of the CPU time, also called a time slice. But keep in mind that some applications may require greater time slices than others to succeed, and thus provide a better experience.

Now if you are like me, you most probably have seen atleast two major revisions of the Linux Kernel, mostly 2.4 and 2.6. I've also seen the 2.2 in action, but we'll leave that out of the picture as of now ;-). The 2.4 Scheduler was pretty simple in nature, which has its advantages. It was simple to write and simple to debug. There was a tasklist which contained the tasks yet to be done, and the scheduler used to look over the tasklist and then select a task to execute. The selection of the task to be executed was based upon a number of criteria, one of them being the priority of the task. The tasklist was protected using a single read/write spinlock.

Unfortunately, simple and efficient, as it was, the 2.4 scheduler had to be replaced due to some major disadvantages. Firstly, it had a single tasklist, and the whole of the tasklist had to be scanned for the selection procedure. As the number of tasks grew, the amount of time to traverse through the list also increased. This also posed problems for Symmetric Multiprocessing Systems (SMP). Also, if the tasklist became very long, a lot of CPU time was spent in swapping in and out of the tasks, rather than execution of those tasks. But as all things simple, the 2.4 scheduler evolved, into the 2.6 scheduler which removes the major defects of the previous versions.

The Linux Kernel 2.6 Scheduler was developed by Ingo Molnar. His goal was to create an O(1) scheduler, which basically means that the scheduler algorithm is independant of the input to it. Thus an O(1) scheduler performs well even under testing circumstances. The major change that came in this scheduler was the fact that there was one active queue for each of the 140 priority levels for each CPU. Since this means that there are 140 queues for each processor, its simple to select the task which is to be given the time slice next. It is important to note that the first hundred queues are reserved for real-time tasks.

Unlike the 2.4 scheduler, the 2.6 scheduler does not have a single "big" lock, since it does not have a single tasklist. Instead it contains a lock for each runqueue. This makes it more suitable for Symmetric Multiprocessing Systems (SMP). The 2.6 scheduler can also dynamically change the priority of a task. It is more favorable towards tasks which involve more input/output, than tasks which make heavy use of the processor for a long time. The reason for this is quite obvious, it results in better user responsiveness.

This finishes my introduction to the Linux Scheduler. I hope I wrote all this in plain english and most of you, if not all, understood it. This by no means is exaustive, and thus if you want to explore the topic further I would suggest reading 'Understanding the Linux 2.6.8.1 CPU Scheduler by Josh Aas'. It is a PDF file and can be downloaded free of cost from,

http://josh.tranceso...u_scheduler.pdf

Good luck hacking the kernel!!

References :-
Inside the Linux scheduler by M. Tim Jones (IBM Developer Works)
Kernel Korner - What's New in the 2.6 Scheduler? by Rick Lindsley (Linux Journal)


Written by Rahul Batra

Is This A Good Question/Topic? 0
  • +

Page 1 of 1