COMP 3000 Essay 1 2010 Question 7 - Revision history

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

2010-11-08T15:33:43Z

Unprotected "COMP 3000 Essay 1 2010 Question 7"

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

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

2010-10-15T13:35:40Z

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

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

Gautam: /* Scalable Threads: The Problems */

2010-10-15T06:15:50Z

Scalable Threads: The Problems

← Older revision		Revision as of 06:15, 15 October 2010
Line 22:		Line 22:

	Bottlenecks can be from '''multiple problems.''' One example of that is the multiqueue scheduler from linux 2.4. Altogether, the multiqueue scheduler ate up 25% of the CPU time. It had two problems: the spinlock ate up a fair majority of the CPU time, it was course-grained. While, the rest went into computing and recomputing information in the cache, a needless expensive operation. The Scheduler also had O(n) time complexity which essentially meant that the scheduler had scalability issues and would become inefficient after a particular number of processes. These problems were fixed by replacing the scheduler (That scheduler was then replaced by a more efficient scheduler with a O(1)time complexity which meant that any number of threads/processes could be scheduled without any overhead.		Bottlenecks can be from '''multiple problems.''' One example of that is the multiqueue scheduler from linux 2.4. Altogether, the multiqueue scheduler ate up 25% of the CPU time. It had two problems: the spinlock ate up a fair majority of the CPU time, it was course-grained. While, the rest went into computing and recomputing information in the cache, a needless expensive operation. The Scheduler also had O(n) time complexity which essentially meant that the scheduler had scalability issues and would become inefficient after a particular number of processes. These problems were fixed by replacing the scheduler (That scheduler was then replaced by a more efficient scheduler with a O(1)time complexity which meant that any number of threads/processes could be scheduled without any overhead.


	----		----


	Introduction of Windows NT and OS/2 brought about innovation that provides cheap threading while having expensive processing. UMS which reflects such design is a recommended mechanism for high performance requirements that handle many threads on multicore systems. A scheduler has to be implemented to manage the UMS threads and decide when they should be run or stopped. This implementation is not desirable for moderate performance systems because concurrent execution of this sort naturally allows for non-intuitive outcomes or behaviors such as race condition which requires careful programming and design choices. The framework used by UMS threading is divided into smaller abstractions depending on the final desired utility. For instance, UMS scheduling can be assigned to each logical processor and thereby creating affinity for related threads to function around one scheduler[http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx]. This could turn out inefficient depending whether there are many related threads that could end up starving other processes.		Introduction of Windows NT and OS/2 brought about innovation that provides cheap threading while having expensive processing. UMS which reflects such design is a recommended mechanism for high performance requirements that handle many threads on multicore systems. A scheduler has to be implemented to manage the UMS threads and decide when they should be run or stopped. This implementation is not desirable for moderate performance systems because concurrent execution of this sort naturally allows for non-intuitive outcomes or behaviors such as race condition which requires careful programming and design choices. The framework used by UMS threading is divided into smaller abstractions depending on the final desired utility. For instance, UMS scheduling can be assigned to each logical processor and thereby creating affinity for related threads to function around one scheduler[http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx]. This could turn out inefficient depending whether there are many related threads that could end up starving other processes.

Gautam: /* References */

2010-10-15T04:15:16Z

References

← Older revision		Revision as of 04:15, 15 October 2010
Line 63:		Line 63:

	== References ==		== References ==
	Native POSIX Threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf]<br>		Native POSIX Threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf]<br>
	Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>		Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>
	PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]<br>		PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]<br>
Line 69:		Line 69:
	Fibers [http://msdn.microsoft.com/en-us/library/ms682661.aspx http://msdn.microsoft.com/en-us/library/ms682661.aspx]<br>		Fibers [http://msdn.microsoft.com/en-us/library/ms682661.aspx http://msdn.microsoft.com/en-us/library/ms682661.aspx]<br>
	Thread pools queues [http://www.ibm.com/developerworks/java/library/j-jtp0730.html http://www.ibm.com/developerworks/java/library/j-jtp0730.html]<br>		Thread pools queues [http://www.ibm.com/developerworks/java/library/j-jtp0730.html http://www.ibm.com/developerworks/java/library/j-jtp0730.html]<br>
	On the design of Chant: a talking threads package [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=344298]<br>		On the design of Chant: a talking threads package [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=344298 http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=344298]<br>

Gautam: /* References */

2010-10-15T04:11:51Z

References

← Older revision		Revision as of 04:11, 15 October 2010
Line 64:		Line 64:
	== References ==		== References ==
	Native POSIX Threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf]<br>		Native POSIX Threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf]<br>
	~~On the design of Chant: a talking threads package [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=344298]<br>~~
	Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>		Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>
	PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]<br>		PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]<br>
Line 70:		Line 69:
	Fibers [http://msdn.microsoft.com/en-us/library/ms682661.aspx http://msdn.microsoft.com/en-us/library/ms682661.aspx]<br>		Fibers [http://msdn.microsoft.com/en-us/library/ms682661.aspx http://msdn.microsoft.com/en-us/library/ms682661.aspx]<br>
	Thread pools queues [http://www.ibm.com/developerworks/java/library/j-jtp0730.html http://www.ibm.com/developerworks/java/library/j-jtp0730.html]<br>		Thread pools queues [http://www.ibm.com/developerworks/java/library/j-jtp0730.html http://www.ibm.com/developerworks/java/library/j-jtp0730.html]<br>
			On the design of Chant: a talking threads package [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=344298]<br>

Gautam: /* References */

2010-10-15T04:11:24Z

References

← Older revision		Revision as of 04:11, 15 October 2010
Line 63:		Line 63:

	== References ==		== References ==
	Native POSIX Threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf]		Native POSIX Threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf]<br>
			On the design of Chant: a talking threads package [http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=344298]<br>
	Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>		Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>
	PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]<br>		PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]<br>

Gautam: /* References */

2010-10-15T03:45:24Z

References

← Older revision		Revision as of 03:45, 15 October 2010
Line 63:		Line 63:

	== References ==		== References ==
			Native POSIX Threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf]
	Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>		Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>
	PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]<br>		PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]<br>

Praubic: /* References */

2010-10-15T03:06:06Z

References

← Older revision		Revision as of 03:06, 15 October 2010
Line 63:		Line 63:

	== References ==		== References ==
	Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>		Linux Symposium, pg83 [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83]<br>
	PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]		PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]<br>
			UMS Threading [http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx]<br>
	UMS Threading [http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx]		Fibers [http://msdn.microsoft.com/en-us/library/ms682661.aspx http://msdn.microsoft.com/en-us/library/ms682661.aspx]<br>
			Thread pools queues [http://www.ibm.com/developerworks/java/library/j-jtp0730.html http://www.ibm.com/developerworks/java/library/j-jtp0730.html]<br>
	Fibers [http://msdn.microsoft.com/en-us/library/ms682661.aspx http://msdn.microsoft.com/en-us/library/ms682661.aspx]

	Thread pools queues [http://www.ibm.com/developerworks/java/library/j-jtp0730.html http://www.ibm.com/developerworks/java/library/j-jtp0730.html]

Praubic: /* References */

2010-10-15T03:04:33Z

References

← Older revision		Revision as of 03:04, 15 October 2010
Line 66:		Line 66:
	PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]		PicoThreads: Lightweight Threads in Java [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf]

	UMS Threading http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx		UMS Threading [http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx]

	Fibers http://msdn.microsoft.com/en-us/library/ms682661.aspx		Fibers [http://msdn.microsoft.com/en-us/library/ms682661.aspx http://msdn.microsoft.com/en-us/library/ms682661.aspx]

	Thread pools queues http://www.ibm.com/developerworks/java/library/j-jtp0730.html		Thread pools queues [http://www.ibm.com/developerworks/java/library/j-jtp0730.html http://www.ibm.com/developerworks/java/library/j-jtp0730.html]

Praubic: /* Scalable Threads: The Problems */

2010-10-15T03:03:12Z

Scalable Threads: The Problems

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


	Introduction of Windows NT and OS/2 brought about innovation that provides cheap threading while having expensive processing. UMS which reflects such design is a recommended mechanism for high performance requirements that handle many threads on multicore systems. A scheduler has to be implemented to manage the UMS threads and decide when they should be run or stopped. This implementation is not desirable for moderate performance systems because concurrent execution of this sort naturally allows for non-intuitive outcomes or behaviors such as race condition which requires careful programming and design choices. The framework used by UMS threading is divided into smaller abstractions depending on the final desired utility. For instance, UMS scheduling can be assigned to each logical processor and thereby creating affinity for related threads to function around one scheduler[http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx ~~[1]~~]. This could turn out inefficient depending whether there are many related threads that could end up starving other processes.		Introduction of Windows NT and OS/2 brought about innovation that provides cheap threading while having expensive processing. UMS which reflects such design is a recommended mechanism for high performance requirements that handle many threads on multicore systems. A scheduler has to be implemented to manage the UMS threads and decide when they should be run or stopped. This implementation is not desirable for moderate performance systems because concurrent execution of this sort naturally allows for non-intuitive outcomes or behaviors such as race condition which requires careful programming and design choices. The framework used by UMS threading is divided into smaller abstractions depending on the final desired utility. For instance, UMS scheduling can be assigned to each logical processor and thereby creating affinity for related threads to function around one scheduler[http://msdn.microsoft.com/en-us/library/dd627187(VS.85).aspx]. This could turn out inefficient depending whether there are many related threads that could end up starving other processes.

	Fibers embrace essentially the same abstraction as coroutines. The distinction emerges from the fact that fibers are on the system level while coroutines execute on the language level[http://msdn.microsoft.com/en-us/library/ms682661.aspx ~~[2]~~]. Unlike UMS, fibers do not utilize multiprocessor machines, however, they require less operating system support. Symbian Operating System presents an example of fibers usage in its Active Scheduler. An object of active scheduler contains a single fiber that is scheduled when an asynchronous call returns and blocks lower priority fibers until all above are finished.		Fibers embrace essentially the same abstraction as coroutines. The distinction emerges from the fact that fibers are on the system level while coroutines execute on the language level[http://msdn.microsoft.com/en-us/library/ms682661.aspx]. Unlike UMS, fibers do not utilize multiprocessor machines, however, they require less operating system support. Symbian Operating System presents an example of fibers usage in its Active Scheduler. An object of active scheduler contains a single fiber that is scheduled when an asynchronous call returns and blocks lower priority fibers until all above are finished.

	Thread Pools consist of queues of threads that stay open and await new tasks to become assigned to them. If there is no new tasks to be completed, they sleep or wait. This pattern eliminates the overhead of creation and destruction of threads which reflects in better system stability and improved performance [http://www.ibm.com/developerworks/java/library/j-jtp0730.html ~~[3]~~]. The long living threads can, for instance, handle multiple transaction requests from socket connection from other machines over a short time frame while at the same time avoiding the millions of cycles to drop/reestablish a thread. Often, thread pool operate on server farms and therefore thread-safety has to be carefully implemented.		Thread Pools consist of queues of threads that stay open and await new tasks to become assigned to them. If there is no new tasks to be completed, they sleep or wait. This pattern eliminates the overhead of creation and destruction of threads which reflects in better system stability and improved performance [http://www.ibm.com/developerworks/java/library/j-jtp0730.html]. The long living threads can, for instance, handle multiple transaction requests from socket connection from other machines over a short time frame while at the same time avoiding the millions of cycles to drop/reestablish a thread. Often, thread pool operate on server farms and therefore thread-safety has to be carefully implemented.

	== Design Choices ==		== Design Choices ==