COMP 3000 Essay 1 2010 Question 5 - Revision history

Soma: Unprotected "COMP 3000 Essay 1 2010 Question 5"

2010-11-08T15:33:26Z

Unprotected "COMP 3000 Essay 1 2010 Question 5"

← Older revision	Revision as of 15:33, 8 November 2010
(No difference)

Soma: /* Answer */

2010-10-17T18:07:35Z

Answer

← Older revision		Revision as of 18:07, 17 October 2010
Line 4:		Line 4:

	=Answer=		=Answer=

	~~(This work belongs to --[[User:Mike Preston\|Mike Preston]] 23:01, 13 October 2010 (UTC))~~
	~~(modified by --[[User:AbsMechanik\|AbsMechanik]] 03:00, 14 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).		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).


	~~(This work was done by [[User:abondio2\|Austin Bondio]] 22:27, 13 October 2010 (UTC))~~
	~~(Modified by [[User:Mike Preston\|Mike Preston]] and [[User:Sschnei1\|Sschnei1]])~~
	~~(edited by --[[User:AbsMechanik\|AbsMechanik]] 09:43, 15 October 2010 (UTC))~~
	There are several different algorithms which are utilized in different schedulers, but a few key algorithms are outlined below[http://joshaas.net/linux/linux_cpu_scheduler.pdf][http://www.sci.csueastbay.edu/~billard/cs4560/node6.html][http://www.articles.assyriancafe.com/documents/CPU_Scheduling.pdf]: <ul>		There are several different algorithms which are utilized in different schedulers, but a few key algorithms are outlined below[http://joshaas.net/linux/linux_cpu_scheduler.pdf][http://www.sci.csueastbay.edu/~billard/cs4560/node6.html][http://www.articles.assyriancafe.com/documents/CPU_Scheduling.pdf]: <ul>

Line 37:		Line 31:

	===Overview & History===		===Overview & History===

	~~(This work belongs to --[[User:Mike Preston\|Mike Preston]] 23:41, 13 October 2010 (UTC))~~
	~~(modified by --[[User:AbsMechanik\|AbsMechanik]] 13:21, 14 October 2010 (UTC))~~

	The FreeBSD kernel originally inherited its scheduler from 4.3BSD which itself is a version of the UNIX scheduler [http://dspace.hil.unb.ca:8080/bitstream/handle/1882/100/roberson.pdf?sequence=1].		The FreeBSD kernel originally inherited its scheduler from 4.3BSD which itself is a version of the UNIX scheduler [http://dspace.hil.unb.ca:8080/bitstream/handle/1882/100/roberson.pdf?sequence=1].
Line 47:		Line 38:

	===Older Versions===		===Older Versions===

	~~(This work belongs to --[[User:Mike Preston\|Mike Preston]] 00:02, 14 October 2010 (UTC))~~
	~~(modified and edited by --[[User:AbsMechanik\|AbsMechanik]] 08:51, 15 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 [https://www.usenix.org/events/bsdcon03/tech/full_papers/roberson/roberson.pdf], 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.		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 [https://www.usenix.org/events/bsdcon03/tech/full_papers/roberson/roberson.pdf], 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.
Line 60:		Line 48:
	===Current Version===		===Current Version===

	~~(This work is owned by --[[User:Mike Preston\|Mike Preston]] 00:23, 14 October 2010 (UTC))~~
	~~(modified by--[[User:AbsMechanik\|AbsMechanik]] 08:27, 15 October 2010 (UTC))~~

	ULE was first implemented as part of an "experimental" process (by Jeff Roberson) in FreeBSD v5.1, before being added to the FreeBSD v5.3 development cycle. It was designed with modern hardware and requirements in mind and had proper support for Symmetric Multi-Processing (SMP) (and HTT), Symmetric Multi-Threading (SMT) platforms and handle heavy workloads. Primarily being an event-driven scheduler, ULE utilized a double-queue mechanism (borrowed from Linux's <b>O(1) scheduler</b>) for ensuring fairness. This mechanism is briefly outlined as follows[http://dspace.hil.unb.ca:8080/bitstream/handle/1882/100/roberson.pdf?sequence=1]:		ULE was first implemented as part of an "experimental" process (by Jeff Roberson) in FreeBSD v5.1, before being added to the FreeBSD v5.3 development cycle. It was designed with modern hardware and requirements in mind and had proper support for Symmetric Multi-Processing (SMP) (and HTT), Symmetric Multi-Threading (SMT) platforms and handle heavy workloads. Primarily being an event-driven scheduler, ULE utilized a double-queue mechanism (borrowed from Linux's <b>O(1) scheduler</b>) for ensuring fairness. This mechanism is briefly outlined as follows[http://dspace.hil.unb.ca:8080/bitstream/handle/1882/100/roberson.pdf?sequence=1]:
Line 84:		Line 70:

	===Overview & History===		===Overview & History===

	~~(This work belongs to [[User:Wlawrenc\|Wesley Lawrence]])~~
	~~(edited & modified by --[[User:AbsMechanik\|AbsMechanik]] 08:50, 15 October 2010 (UTC))~~

	Unlike its competitor, FreeBSD, the Linux scheduler has undergone several different cycles of evolution [http://www.unix.com/whats-your-mind/110099-unix-40th-birthday.html], always aiming towards having a fair and fast scheduler. Various methods and concepts have been tried over different versions such as round robin, iterations, 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 (to ensure fairness). Eventually, the speed issue was also tackled to ensure that the run times were not affected.		Unlike its competitor, FreeBSD, the Linux scheduler has undergone several different cycles of evolution [http://www.unix.com/whats-your-mind/110099-unix-40th-birthday.html], always aiming towards having a fair and fast scheduler. Various methods and concepts have been tried over different versions such as round robin, iterations, 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 (to ensure fairness). Eventually, the speed issue was also tackled to ensure that the run times were not affected.
Line 92:		Line 75:

	===Older Versions===		===Older Versions===

	~~(This work belongs to [[User:Sschnei1\|Sschnei1]])~~

	In Linux 1.2 a scheduler operated with a <b>round robin policy</b> 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 and 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 that supported SMP.		In Linux 1.2 a scheduler operated with a <b>round robin policy</b> 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 and 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 that supported SMP.
Line 100:		Line 81:

	===Current Version===		===Current Version===

	~~(This work was done by [[User:Sschnei1\|Sschnei1]])~~

	As of the Linux 2.6.23 introduction, the CFS (Completely Fair 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.		As of the Linux 2.6.23 introduction, the CFS (Completely Fair 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 of 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.		The model of 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 [[User:abondio2\|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.		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.
Line 118:		Line 94:
	==Conclusion==		==Conclusion==

	~~(This work was done by--[[User:AbsMechanik\|AbsMechanik]] 09:33, 15 October 2010 (UTC))~~
	A few key differences between the Linux & FreeBSD schedulers are outlined as below:		A few key differences between the Linux & FreeBSD schedulers are outlined as below:
	<ul>		<ul>

Soma: Protected "COMP 3000 Essay 1 2010 Question 5" ([edit=sysop] (indefinite) [move=sysop] (indefinite))

2010-10-15T13:35:15Z

Protected "COMP 3000 Essay 1 2010 Question 5" ([edit=sysop] (indefinite) [move=sysop] (indefinite))

← Older revision	Revision as of 13:35, 15 October 2010
(No difference)

AbsMechanik: /* Answer */

2010-10-15T09:43:37Z

Answer

← Older revision		Revision as of 09:43, 15 October 2010
Line 13:		Line 13:
	(This work was done by [[User:abondio2\|Austin Bondio]] 22:27, 13 October 2010 (UTC))		(This work was done by [[User:abondio2\|Austin Bondio]] 22:27, 13 October 2010 (UTC))
	(Modified by [[User:Mike Preston\|Mike Preston]] and [[User:Sschnei1\|Sschnei1]])		(Modified by [[User:Mike Preston\|Mike Preston]] and [[User:Sschnei1\|Sschnei1]])
			(edited by --[[User:AbsMechanik\|AbsMechanik]] 09:43, 15 October 2010 (UTC))
	There are several different algorithms which are utilized in different schedulers, but a few key algorithms are outlined below[http://joshaas.net/linux/linux_cpu_scheduler.pdf][http://www.sci.csueastbay.edu/~billard/cs4560/node6.html][http://www.articles.assyriancafe.com/documents/CPU_Scheduling.pdf]: <ul>		There are several different algorithms which are utilized in different schedulers, but a few key algorithms are outlined below[http://joshaas.net/linux/linux_cpu_scheduler.pdf][http://www.sci.csueastbay.edu/~billard/cs4560/node6.html][http://www.articles.assyriancafe.com/documents/CPU_Scheduling.pdf]: <ul>

AbsMechanik: /* Overview & History */

2010-10-15T09:42:42Z

Overview & History

← Older revision		Revision as of 09:42, 15 October 2010
Line 87:		Line 87:
	(This work belongs to [[User:Wlawrenc\|Wesley Lawrence]])		(This work belongs to [[User:Wlawrenc\|Wesley Lawrence]])
	(edited & modified by --[[User:AbsMechanik\|AbsMechanik]] 08:50, 15 October 2010 (UTC))		(edited & modified by --[[User:AbsMechanik\|AbsMechanik]] 08:50, 15 October 2010 (UTC))

	Unlike its competitor, FreeBSD, the Linux scheduler has undergone several different cycles of evolution [http://www.unix.com/whats-your-mind/110099-unix-40th-birthday.html], always aiming towards having a fair and fast scheduler. Various methods and concepts have been tried over different versions such as round robin, iterations, 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 (to ensure fairness). Eventually, the speed issue was also tackled to ensure that the run times were not affected.		Unlike its competitor, FreeBSD, the Linux scheduler has undergone several different cycles of evolution [http://www.unix.com/whats-your-mind/110099-unix-40th-birthday.html], always aiming towards having a fair and fast scheduler. Various methods and concepts have been tried over different versions such as round robin, iterations, 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 (to ensure fairness). Eventually, the speed issue was also tackled to ensure that the run times were not affected.
	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. With the advent of more complicated hardware (multi-core CPU's), Linux also faced new challenges, as experienced by BSD. Various techniques were employed to accommodate for these changes ranging from the inefficient O(n) scheduler to the CFS (current version) [http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/index.html].		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. With the advent of more complicated hardware (multi-core CPU's), Linux also faced new challenges, as experienced by BSD. Various techniques were employed to accommodate for these changes ranging from the inefficient O(n) scheduler to the CFS (current version) [http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/index.html].

AbsMechanik: /* Conclusion */

2010-10-15T09:39:45Z

Conclusion

← Older revision		Revision as of 09:39, 15 October 2010
Line 122:		Line 122:
	<li>ULE runs in O(1) time whereas CFS runs in O(log(n)) time</li>		<li>ULE runs in O(1) time whereas CFS runs in O(log(n)) time</li>
	<li>ULE is based on run-queues whereas CFS utilizes a red-black tree</li>		<li>ULE is based on run-queues whereas CFS utilizes a red-black tree</li>
	<li>Linux ~~was the first OS to implement support for SMP~~</li>		<li>Context switching is done much faster by ULE than Linux [http://jeffr-tech.livejournal.com/19139.html]</li>
	</ul>		</ul>
	Hardware innovation has primarily been the driving force behind the evolution of the schedulers and with the ever increasing complexity of parallel & distributed systems and managing multi-threaded it is clear that even the current schedulers will undergo some radical changes to meet those new challenges.
			Hardware innovation has primarily been the driving force behind the evolution of the schedulers and with the ever increasing complexity of parallel & distributed systems and managing multi-threaded it is clear that even the current schedulers will undergo some radical changes to meet those new challenges. It remains to be seen what each group comes up with to address these growing challenges

	== Resources ==		== Resources ==

AbsMechanik: /* Answer */

2010-10-15T09:33:09Z

Answer

← Older revision		Revision as of 09:33, 15 October 2010
Line 94:		Line 94:
	(This work belongs to [[User:Sschnei1\|Sschnei1]])		(This work belongs to [[User:Sschnei1\|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 that supported SMP.		In Linux 1.2 a scheduler operated with a <b>round robin policy</b> 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 and 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 that 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 its entire 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.		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 provided 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 its entire 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===		===Current Version===
Line 115:		Line 115:
	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.		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~~==		==Conclusion==

	(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)

	~~-- [[User:Wlawrenc\|Wesley Lawrence]]~~

	I've got this. Hopefully most of the sections I created properly answer the question. I'm still going to go over everyone's answers and keep in mind that wikipedia cannot be cited as a resource. --[[User:AbsMechanik\|AbsMechanik]] 02:29, 14 October 2010 (UTC)

	~~==Current Challenges==~~


			(This work was done by--[[User:AbsMechanik\|AbsMechanik]] 09:33, 15 October 2010 (UTC))
			A few key differences between the Linux & FreeBSD schedulers are outlined as below:
			<ul>
			<li>ULE runs in O(1) time whereas CFS runs in O(log(n)) time</li>
			<li>ULE is based on run-queues whereas CFS utilizes a red-black tree</li>
			<li>Linux was the first OS to implement support for SMP</li>
			</ul>
			Hardware innovation has primarily been the driving force behind the evolution of the schedulers and with the ever increasing complexity of parallel & distributed systems and managing multi-threaded it is clear that even the current schedulers will undergo some radical changes to meet those new challenges.
	== Resources ==		== Resources ==

AbsMechanik: /* Older Versions */

2010-10-15T08:51:01Z

Older Versions

← Older revision		Revision as of 08:51, 15 October 2010
Line 49:		Line 49:

	(This work belongs to --[[User:Mike Preston\|Mike Preston]] 00:02, 14 October 2010 (UTC))		(This work belongs to --[[User:Mike Preston\|Mike Preston]] 00:02, 14 October 2010 (UTC))
			(modified and edited by --[[User:AbsMechanik\|AbsMechanik]] 08:51, 15 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 [https://www.usenix.org/events/bsdcon03/tech/full_papers/roberson/roberson.pdf], 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.		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 [https://www.usenix.org/events/bsdcon03/tech/full_papers/roberson/roberson.pdf], 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.

AbsMechanik: /* Overview & History */

2010-10-15T08:50:09Z

Overview & History

← Older revision		Revision as of 08:50, 15 October 2010
Line 85:		Line 85:

	(This work belongs to [[User:Wlawrenc\|Wesley Lawrence]])		(This work belongs to [[User:Wlawrenc\|Wesley Lawrence]])
			(edited & modified by --[[User:AbsMechanik\|AbsMechanik]] 08:50, 15 October 2010 (UTC))
	~~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 robin, iterations, 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.~~		Unlike its competitor, FreeBSD, the Linux scheduler has undergone several different cycles of evolution [http://www.unix.com/whats-your-mind/110099-unix-40th-birthday.html], always aiming towards having a fair and fast scheduler. Various methods and concepts have been tried over different versions such as round robin, iterations, 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 (to ensure fairness). Eventually, the speed issue was also tackled to ensure that the run times were not affected.
			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. With the advent of more complicated hardware (multi-core CPU's), Linux also faced new challenges, as experienced by BSD. Various techniques were employed to accommodate for these changes ranging from the inefficient O(n) scheduler to the CFS (current version) [http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/index.html].

	(~~This work was done by [[User:abondio2\|Austin Bondio]], modified by [[User:Sschnei1\|Sschnei1]]~~ )

	~~The Linux kernel has undergone many changes over the decades since its original release as the UNIX operating system in 1969~~ [http://www.~~unix~~.com/~~whats-your-mind~~/~~110099~~-~~unix~~-~~40th~~-~~birthday~~.html](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.

	===Older Versions===		===Older Versions===

AbsMechanik: /* Current Version */

2010-10-15T08:27:40Z

Current Version

← Older revision		Revision as of 08:27, 15 October 2010
Line 60:		Line 60:

	(This work is owned by --[[User:Mike Preston\|Mike Preston]] 00:23, 14 October 2010 (UTC))		(This work is owned by --[[User:Mike Preston\|Mike Preston]] 00:23, 14 October 2010 (UTC))
			(modified by--[[User:AbsMechanik\|AbsMechanik]] 08:27, 15 October 2010 (UTC))

	ULE was first implemented as part of an "experimental" process (by Jeff Roberson) in FreeBSD v5.1, before being added to the FreeBSD v5.3 development cycle. It was designed with modern hardware and requirements in mind and had proper support for Symmetric Multi-Processing (SMP) (and HTT), Symmetric Multi-Threading (SMT) platforms and handle heavy workloads. Primarily being an event-driven scheduler, ULE utilized a double-queue mechanism (borrowed from Linux's <b>O(1) scheduler</b>) for ensuring fairness. This mechanism is briefly outlined as follows[http://dspace.hil.unb.ca:8080/bitstream/handle/1882/100/roberson.pdf?sequence=1]:		ULE was first implemented as part of an "experimental" process (by Jeff Roberson) in FreeBSD v5.1, before being added to the FreeBSD v5.3 development cycle. It was designed with modern hardware and requirements in mind and had proper support for Symmetric Multi-Processing (SMP) (and HTT), Symmetric Multi-Threading (SMT) platforms and handle heavy workloads. Primarily being an event-driven scheduler, ULE utilized a double-queue mechanism (borrowed from Linux's <b>O(1) scheduler</b>) for ensuring fairness. This mechanism is briefly outlined as follows[http://dspace.hil.unb.ca:8080/bitstream/handle/1882/100/roberson.pdf?sequence=1]:
Line 70:		Line 71:

	</ul>		</ul>
	It has been implemented as the default scheduler since v7.1 onwards. ULE works really well on both single or uni-processor environments as well as multi-core environments. It prevents unnecessary CPU migration, while making good use of CPU resources. However, 2 key practical problems arose due to the double-queue mechanism.		It has been implemented as the default scheduler since v7.1 onwards. ULE works really well on both single or uni-processor environments as well as multi-core environments. It prevents unnecessary CPU migration, while making good use of CPU resources. However, 2 key practical problems arose due to the double-queue mechanism [http://jeffr-tech.livejournal.com/3729.html]:
			<ul>
			<li>Implementing queues meant more memory usage and cache hits</li>
			<li>Having multiple threads on different queues caused problems for the rest of the system</li>
			</ul>
			This problem was resolved by implementing a circular queue, inspired by the calendar queue data structure. Since there is only one queue, there is little extra cpu overhead. There is more flexibility in deciding how much runtime each thread gets relative to those with a lower priority.
			With these design approaches in mind, ULE is also slightly faster on uni-processor systems than the 4.4BSD.

	==Linux Schedulers==		==Linux Schedulers==