Talk:COMP 3000 Essay 1 2010 Question 5 - Revision history

CFaibish: /* Essay Preview */

2010-10-14T19:00:07Z

Essay Preview

← Older revision		Revision as of 19:00, 14 October 2010
Line 303:		Line 303:

	Since their just minimal fixes like commas, pluralization, and apostrophes, I'll just go ahead and edit them in-essay. I've saved a backup as well in case you guys feel I ruined anything.		Since their just minimal fixes like commas, pluralization, and apostrophes, I'll just go ahead and edit them in-essay. I've saved a backup as well in case you guys feel I ruined anything.

			--[[User:CFaibish\|CFaibish]] 14:52, 14 October 2010 (UTC)

	= Sources =		= Sources =

CFaibish: /* Essay Preview */

2010-10-14T15:13:22Z

Essay Preview

← Older revision		Revision as of 15:13, 14 October 2010
Line 301:		Line 301:

	--[[User:CFaibish\|CFaibish]] 14:42, 14 October 2010 (UTC)		--[[User:CFaibish\|CFaibish]] 14:42, 14 October 2010 (UTC)

			Since their just minimal fixes like commas, pluralization, and apostrophes, I'll just go ahead and edit them in-essay. I've saved a backup as well in case you guys feel I ruined anything.

	= Sources =		= Sources =

CFaibish: /* Essay Preview */

2010-10-14T14:53:36Z

Essay Preview

← Older revision		Revision as of 14:53, 14 October 2010
Line 297:		Line 297:
	--[[User:CFaibish\|CFaibish]] 22:59, 13 October 2010 (UTC)		--[[User:CFaibish\|CFaibish]] 22:59, 13 October 2010 (UTC)

	I'm reading through what's up there now looking for typos/rewording certain aspects. Should I just go and edit it? Or should I compose a mirrored version and go from there?
			I'm reading through what's up there now looking for typos/rewording certain aspects [mostly typos tho, this is very well written]. Should I just go and edit it? Or should I compose a mirrored version and go from there?

	--[[User:CFaibish\|CFaibish]] 14:42, 14 October 2010 (UTC)		--[[User:CFaibish\|CFaibish]] 14:42, 14 October 2010 (UTC)

CFaibish: /* Essay Preview */

2010-10-14T14:42:54Z

Essay Preview

← Older revision		Revision as of 14:42, 14 October 2010
Line 296:		Line 296:

	--[[User:CFaibish\|CFaibish]] 22:59, 13 October 2010 (UTC)		--[[User:CFaibish\|CFaibish]] 22:59, 13 October 2010 (UTC)

			I'm reading through what's up there now looking for typos/rewording certain aspects. Should I just go and edit it? Or should I compose a mirrored version and go from there?
			--[[User:CFaibish\|CFaibish]] 14:42, 14 October 2010 (UTC)

	= Sources =		= Sources =

Sschnei1: /* Essay Preview */

2010-10-14T00:24:59Z

Essay Preview

← Older revision		Revision as of 00:24, 14 October 2010
Line 200:		Line 200:

	Here's something I put into the Linux: Overview section:		Here's something I put into the Linux: Overview section:
			<br />I (Sschnei1) added some text to the Round-Robin Scheduling and the Multilevel Queue Scheduling.

	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] 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.		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] 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.
Line 207:		Line 208:
	<li>Shortest Time Remaining: Limited multi-tasking. The CPU handles the easiest tasks first, and complex, time-consuming tasks are handled last.</li>		<li>Shortest Time Remaining: Limited multi-tasking. The CPU handles the easiest tasks first, and complex, time-consuming tasks are handled last.</li>
	<li>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.</li>		<li>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.</li>
	<li>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.</li>		<li>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. The Round-Robin Scheduling is used in Linux-1.2.</li>
	<li>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.</li>		<li>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. The O(1) algorithm in 2.6 up to 2.6.23 is based on a Multilevel Queue.</li>
	</ul>		</ul>

Line 214:		Line 215:
	-- [[User:abondio2\|Austin Bondio]] Last edit: 22:27, 13 October 2010 (UTC)		-- [[User:abondio2\|Austin Bondio]] Last edit: 22:27, 13 October 2010 (UTC)

			-- [[User:Sschnei1\|Sschnei1]] 00:24, 14 October 2010 (UTC)

Sschnei1: /* Essay Preview */

2010-10-14T00:14:48Z

Essay Preview

← Older revision		Revision as of 00:14, 14 October 2010
Line 218:		Line 218:
	I'm writing on a contrast of the CFS scheduler right now, please don't edit it.		I'm writing on a contrast of the CFS scheduler right now, please don't edit it.

	In contrast the the O(1) scheduler, CFS realizes the model of a scheduler which can execute precise on real multitasking on real hardware. Precise multitasking means that each process can run at equal speed. If 4 processes are running at the same time, CFS assigns 25% of the CPU time to each process. On real hardware, only one task can be executed at a time and other tasks have to wait, which gives the running tasks an unfair amount of CPU time.		In contrast the the O(1) scheduler, CFS realizes the model of a scheduler which can execute precise on real multitasking on real hardware. Precise multitasking means that each process can run at equal speed. If 4 processes are running at the same time, CFS assigns 25% of the CPU time to each process. On real hardware, only one task can be executed at a time and other tasks have to wait, which gives the running tasks an unfair amount of CPU time.

	To avoid an unfair balance over the processes, CFS has a wait run-time for each process. CFS tries to pick the process with the highest wait run-time value. To provide a real multitasking, CFS splits up the CPU time between running processes.		To avoid an unfair balance over the processes, CFS has a wait run-time for each process. CFS tries to pick the process with the highest wait run-time value. To provide a real multitasking, CFS splits up the CPU time between running processes. This allows multiple processes to parallel on a single CPU.

	Processes are not stored in a run queue, such in the O(1) scheduler, but in a self-balancing red-black tree, where self-balancing means that the task with the highest need for CPU time is stored in the most left node. Tasks with a lower need for CPU time are stored on the right side of the Tree, where tasks with a higher need for CPU time are stored on the left side. The task on the left side is picked by the scheduler and put in a virtual runtime. If the process is ready to run, it is given CPU time to run. The tree re-balances itself and new tasks can be taken out by the CPU.		Processes are not stored in a run queue, such in the O(1) scheduler, but in a self-balancing red-black tree, where self-balancing means that the task with the highest need for CPU time is stored in the most left node. Tasks with a lower need for CPU time are stored on the right side of the Tree, where tasks with a higher need for CPU time are stored on the left side. The task on the left side is picked by the scheduler and put in a virtual runtime. If the process is ready to run, it is given CPU time to run. The tree re-balances itself and new tasks can be taken out by the CPU.

	CFS is designed in a way that it does not need timeslicing and still provide most performance with as much ~~cpu~~ utilization. This is due to the nanosecond granularity, which removes the need for jiffies or other HZ details. [http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt]		CFS is designed in a way that it does not need to do timeslicing on the CPU, and still provide most performance with as much CPU utilization. This is due to the nanosecond granularity, which removes the need for jiffies or other HZ details. [http://people.redhat.com/mingo/cfs-scheduler/sched-design-CFS.txt]

CFaibish: /* Essay Preview */

2010-10-13T23:27:34Z

Essay Preview

← Older revision		Revision as of 23:27, 13 October 2010
Line 228:		Line 228:

	-- [[User:Sschnei1\|Sschnei1]] 16:32, 13 October 2010 (UTC)		-- [[User:Sschnei1\|Sschnei1]] 16:32, 13 October 2010 (UTC)



Line 238:		Line 239:
	[1] In older BSD systems, (and I mean old, as in 20 or so years ago), a 1 second quantum was used for the round-robin scheduling algorithm. Later, in BSD 4.2, it did rescheduling every 0.1 seconds, and priority re-computation every second, and these values haven’t changed since. Round-robin scheduling is done by a timeout mechanism, which informs the clock interrupt driver to call a certain system routine after a specified interval. The subroutine to be called, in this case, causes the rescheduling and then resubmits a timeout to call itself again 0.1 sec later. The priority re-computation is also timed by a subroutine that resubmits a timeout for itself.		[1] In older BSD systems, (and I mean old, as in 20 or so years ago), a 1 second quantum was used for the round-robin scheduling algorithm. Later, in BSD 4.2, it did rescheduling every 0.1 seconds, and priority re-computation every second, and these values haven’t changed since. Round-robin scheduling is done by a timeout mechanism, which informs the clock interrupt driver to call a certain system routine after a specified interval. The subroutine to be called, in this case, causes the rescheduling and then resubmits a timeout to call itself again 0.1 sec later. The priority re-computation is also timed by a subroutine that resubmits a timeout for itself.

	The ULE Scheduler was first introduced in FreeBSD 5, however disabled by default in favor of the default 4BSD scheduler. It was not until FreeBSD 7.1 that the ULE scheduler became the new default. The ULE scheduler was an overhaul of the original scheduler, and allowed it support for symmetric multiprocessing (SMP), support for symmetric multithreading (SMT) on multi-core systems, and improve the scheduler algorithm to ensure execution is no longer limited by the number of threads in the system.		The ULE Scheduler was first introduced in FreeBSD 5, however disabled by default in favor of the default 4BSD scheduler. It was not until FreeBSD 7.1 that the ULE scheduler became the new default. The ULE scheduler was an overhaul of the original scheduler, and allowed it support for symmetric multiprocessing (SMP), support for symmetric multithreading (SMT) on multi-core systems, and improve the scheduler algorithm to ensure execution is no longer limited by the number of threads in the system.
	<more to ~~come>~~
			The ULE has a constant execution time of O(1), regardless of the number of threads. In addition, it also is careful to identify interactive tasks and give them the lowest latency response possible. The scheduling components include several queues, two CPU load-balancing algorithms, an interactivity scorer, a CPU usage estimator, a priority calculator, and a slice calculator.

			Since ULE is an event driven scheduler, there is no periodic timer that adjusts thread priority to prevent starvation. Fairness is implemented by maintaining two queues: the current and the next queue. Each thread that is granted a CPU slice is assigned to either the current or next queue. Threads are then picked from the current queue in order of priority until it is empty, which is when the next and current queues are switched, and the process begins again. This guarantees that each thread will be given use of its slice once every two queue cycles, regardless of priority. Interrupt and real-time threads (and threads with these priority levels) are inserted onto the current queue, for they are of the highest priority. There is also an idle class of threads, which is checked only when there are no other runnable tasks.

			In order to promptly discover when a thread changes from interactive to non-interactive, the ULE scheduler uses Interactivity Scoring, a key part of the scheduler affecting the responsiveness of the system, and subsequently, user experience. An interactivity score is computed from the relationship between run and sleep time, using a formula that is out of scope for this project. Interactive threads usually have high sleep times because they are often waiting for user input. This usually is followed by quick bursts in CPU activity from processing the user's request.

			The ULE also implements a priority calculator, not to maintain fairness, but only to order the threads by priority. Only time-sharing threads use the priority calculator, the rest are allotted statically. ULE uses the interactivity score to determine the nice value of a thread, which will allow it to in turn decide upon its priority.

			The way that the ULE uses its nice values in combination with slices is by implementing a moving window of nice values allowed slices. The threads within the window are given a slice oppositely proportional to the difference between their nice value and the lowest recorded nice value. This results in smaller slices to nicer threads, which subsequently defines their amount of allotted CPU time. On x86, FreeBSD allows for a minimum slice value of 10ms, and a maximum of 140ms. Interactive tasks receive the smallest nice value, in order to more promptly find that the interactive task is no longer interacting.

			The ULE uses a CPU usage estimator to show roughly how much CPU a thread is using. It operates on an event driven basis. ULE keeps track of the number of clock ticks that occurred within a sliding window of the thread's execution time. The window slides to upwards of one second past threshold, and then back down to regulate the ratio of run time to sleep time.

			The ULE enables SMP (Symmetric Multiprocessing) in order to greater achieve CPU affinity, which is when you schedule threads onto the last CPU they were run on, as to avoid unnecessary CPU migrations. Processors typically have large caches to aid the performance of threads and processes. CPU affinity is key because the thread may still have leftover data in the caches of the previous CPU, and when a thread migrates, it not only has to load this data into the new CPU's cache, but must also clear the data from the previous CPU's cache. ULE has two methods for CPU load balancing: pull and push. Pull is when an idle CPU grabs a thread from a non-idle CPU to lend a hand. Push is when a periodic task evaluates the current load situation of the CPUs and balances it out amongst them. These two function side by side, and allow for an optimally balanced CPU workload.

			SMT (Symmetric Multithreading), a concept of non-uniform processors, is not fully present in ULE. The foundations are there, however, which can eventually be extended to support NUMA (Non-Uniform Memory Architecture). This involves expressing the penalties of CPU migration through separate queues, which could be extended to add a local and global load-balancing policy. As far as my sources go, FreeBSD does not at this point support NUMA, however the groundwork is there, and it is a real possibility for it to appear in a future version.


	1 = http://www.cim.mcgill.ca/~franco/OpSys-304-427/lecture-notes/node46.html		1 = http://www.cim.mcgill.ca/~franco/OpSys-304-427/lecture-notes/node46.html
Line 248:		Line 265:
	Notes: Lots of this is just paraphrasing stuff you guys said in the discussion section. In terms of citations, should it be a superscripted citation next to the fact snippet we used, or should it just be a list of sources at the bottom?		Notes: Lots of this is just paraphrasing stuff you guys said in the discussion section. In terms of citations, should it be a superscripted citation next to the fact snippet we used, or should it just be a list of sources at the bottom?

	--[[User:CFaibish\|CFaibish]] 17:51, 13 October 2010 (UTC)		--[[User:CFaibish\|CFaibish]] 23:27, 13 October 2010 (UTC)

CFaibish: /* Essay Preview */

2010-10-13T23:00:38Z

Essay Preview

← Older revision		Revision as of 23:00, 13 October 2010
Line 267:		Line 267:
	-- [[User:Sschnei1\|Sschnei1]] 20:56, 13 October 2010 (UTC)		-- [[User:Sschnei1\|Sschnei1]] 20:56, 13 October 2010 (UTC)

	Hi, here's a little forward on schedulers in relation to types of threads I've composed based off of one of my sources, I'm not sure if its necessary since there is one Mike typed ~~below~~, but here it just for you guys to examine:		Hi, here's a little forward on schedulers in relation to types of threads I've composed based off of one of my sources, I'm not sure if its necessary since there is one Mike typed above, but here it just for you guys to examine:

	Threads that perform a lot of I/O require a fast response time to keep input and output devices busy, but need little CPU time. On the other hand, compute-bound threads need to receive a lot of CPU time to finish their work, but have no requirement for fast response time. Other threads lie somewhere in between, with periods of I/O punctuated by periods of computation, and thus have requirements that vary over time. A well-designed scheduler should be able accommodate threads with all these requirements simultaneously.		Threads that perform a lot of I/O require a fast response time to keep input and output devices busy, but need little CPU time. On the other hand, compute-bound threads need to receive a lot of CPU time to finish their work, but have no requirement for fast response time. Other threads lie somewhere in between, with periods of I/O punctuated by periods of computation, and thus have requirements that vary over time. A well-designed scheduler should be able accommodate threads with all these requirements simultaneously.

CFaibish: /* Essay Preview */

2010-10-13T22:59:49Z

Essay Preview

← Older revision		Revision as of 22:59, 13 October 2010
Line 266:		Line 266:

	-- [[User:Sschnei1\|Sschnei1]] 20:56, 13 October 2010 (UTC)		-- [[User:Sschnei1\|Sschnei1]] 20:56, 13 October 2010 (UTC)

			Hi, here's a little forward on schedulers in relation to types of threads I've composed based off of one of my sources, I'm not sure if its necessary since there is one Mike typed below, but here it just for you guys to examine:

			Threads that perform a lot of I/O require a fast response time to keep input and output devices busy, but need little CPU time. On the other hand, compute-bound threads need to receive a lot of CPU time to finish their work, but have no requirement for fast response time. Other threads lie somewhere in between, with periods of I/O punctuated by periods of computation, and thus have requirements that vary over time. A well-designed scheduler should be able accommodate threads with all these requirements simultaneously.


			Also: as Mike said earlier about BSD's issue with locking mechanisms, should I go into greater detail about that, or just include a little, few sentence description of the issue? I've found a source for what I think is what he was referring to: http://security.freebsd.org/advisories/FreeBSD-EN-10:02.sched_ule.asc

			I'll be posting more of what I've got on the BSD stuff under the hour.

			--[[User:CFaibish\|CFaibish]] 22:59, 13 October 2010 (UTC)

	= Sources =		= Sources =

CFaibish: /* Discussion */

2010-10-13T22:58:59Z

Discussion

← Older revision		Revision as of 22:58, 13 October 2010
Line 134:		Line 134:

	Sebastian Schneider - sebastian@gamersblog.ca		Sebastian Schneider - sebastian@gamersblog.ca


	Hi, here's a little forward on schedulers in relation to types of threads I've composed based off of one of my sources, I'm not sure if its necessary since there is one Mike typed below, but here it just for you guys to examine:

	Threads that perform a lot of I/O require a fast response time to keep input and output devices busy, but need little CPU time. On the other hand, compute-bound threads need to receive a lot of CPU time to finish their work, but have no requirement for fast response time. Other threads lie somewhere in between, with periods of I/O punctuated by periods of computation, and thus have requirements that vary over time. A well-designed scheduler should be able accommodate threads with all these requirements simultaneously.


	Also: as Mike said earlier about BSD's issue with locking mechanisms, should I go into greater detail about that, or just include a little, few sentence description of the issue? I've found a source for what I think is what he was referring to: http://security.freebsd.org/advisories/FreeBSD-EN-10:02.sched_ule.asc
	~~--[[User:CFaibish\|CFaibish]] 17:54, 13 October 2010 (UTC)~~

	= Essay Preview =		= Essay Preview =