Soma-notes - User contributions [en]

COMP 3000 Essay 2 2010 Question 4

2010-11-27T19:14:19Z

Hirving: /* References */

==Accountable Virtual Machines ==
'''Authors:''' Andreas Haeberlen, Paarijaat Aditya, Rodrigo Rodrigues, Peter Druschel

'''Affiliates:'''
University of Pennsylvania, Max Planck Institute for Software Systems (MPI-SWS)]

'''Link to Paper:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Haeberlen.pdf Accountable Virtual Machines]

==Background Concepts==

'''Accountable Virtual Machine (AVM)'''

'''Deterministic Replay''': A machine can record its executions into a file so that it can be replayed in order to see the executions and follow what was happening on the machine. Remus [[#References | [1]]] has contributed a highly efficient snap-shotting mechanism for these replays.

'''Accountability:''' Accountability in the context of this paper means that every action done on the virtual machine is recorded and will be used against the machine or user to verify the correctness of the application. The AVM is responsible of its action and will answers for its action against an auditor.

'''Remote Fault Detection:''' There are programs like GridCop[[#References | [2]]] that can be used to monitor the progress and execution of a remotely executing program by requesting a beacon packet. When the remote computer is sending the packets, the receiving/logging computer must be a trusted computer (hardware,software, OS) so that the receiving of packets remains consistent. To detect a fault in a remote system, every packet must arrive safely, and any interrupts during the logging must be handled or the inconsistencies will result in an inaccurate outcome. The AVM does not require trusted hardware and can be used over wide-area networks.

'''Cheat Detection:''' Cheating in games or any specific modification in a program can be either scanned[[#References | [3][4]]] for or prevented[[#References | [5][6]]] by certain programs. The issue with these scanning and preventative software is the knowledge/awareness of specific cheats or situations that the software can handle. An AVM is designed to counter any kind of general cheat.

'''Integrity Violations:''' This refers how the consistency of normal/expected operations of an execution does not equal to that of the host/reference (Trusted) execution, hence a violation has occurred.

- The word "node" is used to refer to a computer or server in order to represent the interactions between one computer and another, or a computer and a server.

=Research problem=

The research presented in this paper tries to tackle a problem that has haunted computer scientists for a long time. How can you be sure that the software running on a remote machine is working correctly or as intended. Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a trust relation between users and a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done would be independent of the node and only dependent on the intended software. Let's say, that node A interacts with node B with execution exe1 and node A interacts with node C also with ex1, but node C has been modified and respond with exe2. Thus, we can assume that the respond of B and C will be different. Being able to prove that the node C has been modified without any doubt is the purpose of this paper.

Previous work that has been done in efforts to prevent or detect '''integrity violations''' can be separated into different categories of operations. The first would be '''Cheat Detection''', where in many different games there are cheats that users use to usually create benefits for themselves that was not intended by the original game.[[#References |[4]]] These detectors are not dynamic, in the sense that they do not actually detect whether a cheat is being used, more so they are checking if there is a cheating operation that they have logged before, being operated on the user's system. For example, if there was a known cheating program named aimbot.exe that can be run in the background of a game such as CounterStrike, and the PunkBuster system that was implemented on the user's system had the aimbot.exe program already logged as a cheating program from the developers, the PunkBuster program might notify the current game servers of this or even prevent the user from playing any games until the aimbot.exe operation is no longer running.

'''Accountability''' is another important problem that many have already worked on. The main goal of an accountable system is to be able to determine without a doubt that node is faulty and can prove it with solid evidence. It can also be used to defend a node when threatened with false accusation. Numerous systems already use accountability in their system, but they were mostly all linked to specific applications, where a point of reference must be used to compare. As example PeerReview[[#References |[7]]], which is a system closely related to what the research team have worked on, must be implemented into the application which makes it less portable and cannot be implemented as easily as an '''AVM'''. PeerReview verifies the inbound and outbound packets and can see if the software is running as intended.

Another problem that is related to the paper is '''remote fault detection''' in a distributed system. How can we determine if a remote node is running the code correctly or if the machine itself is working as intended. Network activity is a common solution to this problem, as they look at the inbound and outbound of the node. This can let them know how the software is operating, or in the case of AVM how the whole virtual machine is working. Gridcop[[#References |[8]]] is another example that inspects a small number of packets periodically. Another way of determining the fault remotely is to use a trusted node, where it can tell immediately if a fault occurs or a modification is made where it should not have been made.

The problem of logging and auditing the processes of an execution of a specific node (computer) is greatly dependent on the work done for '''deterministic replay'''. Deterministic replay programs can create a log file that can be used to replay the operations done for some execution that occurs on a node. Replaying the operations done on the node can show what the node was doing, and this would seem like it is sufficient in finding out whether a node was causing integrity violations or not. The concept of snap-shoting/recording the operations is not the issue with deterministic replay, it is the fact that the data being outputted into the replay may be tampered with by the node itself so that it generates optimal results in replay. By faking the results of the operations, the auditing computer will falsely believe that the tested computer is running all operations as normal. The logging operations done by these recording programs can be directly related to the work needed to detect integrity violations.

=Contribution=
The accountable virtual machine (AVM), that was proposed in this essay, most useful contribution was the implementation of the accountable virtual machine monitor (AVMM). It is what allows for the fault checking of virtual machines in a cloud computing environment. The AVMM can be broken down into different parts: the virtual machine monitor (VMM), the temper-evident log, and auditing mechanisms. The VMM is based off the VMM found in VMWare Workstation 6.5.1[[#References |[9]]], the temper-evident log was adapted from code in PeerReview[[#References |[7]]], and the audit tools were built up from scratch.

The accountable virtual machine monitor relies on four assumptions:

1. All transmitted messages are received, retransmitted if needed.

2. Machines and Users have access to a hash function that is pre-image resistant, second pre-image resistant, and collision resistant.

3. All parties have a certified keypair, that can be used to sign messages.

4. To audit a log, the user has a reference copy of the VM used.
The job of the AVMM is to record all incoming and outgoing messages to a tamper-evident log
and enough info of the execution to enable deterministic replay.

The AVMM must record nondeterministic inputs (such as hardware interrupts), because the input is asynchronous, and the exact timing of input must be recorded so the inputs can be injected at the same moment during the replay. Wall-clock time is not accurate enough for this recording, so the AVMM must use a combination of instruction pointer, branch counter, and additional registers. Not all inputs have to be recorded this way (software interrupts) because they send requests to the AVM, which will be issued again during replay.

Two parallels streams appear in the tamper-evident log: message exchanges and nondeterministic inputs.
It is important for the AVMM to detect inconsistencies between the user's log and the machine's log (in case of foul play), so the AVMM simply cross-references messages and inputs during replay, thus, easily detecting any discrepancies.

The AVMM periodically takes snapshots of the AVM's current state, this facilitates fine-grain audits for the user, but it also increases overhead. The overhead is lowered slightly by the snapshots being incremental (only save the state that has been changed since the last snapshot). The user can authenticate the snapshot using a hash tree of the state (generated by the AVMM) and it can update the hash tree after each snapshot.

'''Tamper-Evident Log'''

The log is made up of hash code entries.
Each log entry in form e = (s,t,c,h)
s = monotonically increasing sequence number
t = type
c = data of the type
h = hash value

The hash value is calculated by: h = H(hi-1 || s || t || H(c))
H() is a hash function.
|| stands for concatenation

Each message sent gets signed with a private key, when the AVMM logs the messages with the signature attached but removes it before sending it to the AVM. To ensure nonrepudiation, an authenticator is attached to each outgoing message.

To detect when a message is dropped, each party sends an acknowledgement for each message they receive. If an acknowledgement is not received the message is resent a few times, if the user stops receiving messages, then the machine is presumed to have failed.

To preform a log check, the user retrieves a pair of authenticators, then challenges the machine to produce the log segment between the two. The log is computationally infeasible to edit without breaking the hash chain, thus, if the log has been tampered with, the hash chain will be different and the user will notified of the tampering.

'''Auditing Mechanism'''

From VMM's perspective all things are deterministic.

To perform a audit, the user:

1. obtains a segment of the machine's log and the authenticators

2. downloads a snapshot of the AVM at the beginning of the segment

3. replays the entire segment, starting from the snapshot, to verify the events in the log are the correct execution of the software.

The user can verify the execution of software through three different methods: Verifying the log, snapshot, and execution.

When the user wants to verify a log segment, the user retrieves the authenticators from the machine with the sequence numbers in the range of the log segment. The user then downloads the log segment from the machine, and, starting with the most recent snapshot before the log segment and ending with the most recent snapshot before the end of the log segment. The user then checks the authenticators for tampering. If this step proceeds, the user can assume the log segment executed properly. If the machine is faulty, the segment will be unavailable to download or may return a corrupted log segment. This can be used to convince a third party of the fault.

When the user wants to verify the snapshot, the user obtains a snapshot of the AVM's state at the beginning of the log segment. The user then downloads a snapshot from the machine and the AVMM recomputes the hash tree. The new hash tree is compared to the hash tree contained in the orignal log segment. If any discrepancies are detected, the user can use this to convince a third party of the machine's faults.

In order for the user to verifying the execution of a log segment, the user needs three inputs: the log segment, the snapshot, and the public keys of the machine and any users of the machine. The auditing tool performs two checks on the log segment, a syntactic check (determines if log is well-formed), and a semantic check (determines if the information in the log shows the correct execution of the machine).

The syntactic check checks whether all log entries are in the proper format, the signatures in each message and acknowledgement, if each message was acknowledged, and the sequence of sent and received messages is correct when compared to the sequence of messages that enter and exit the AVM.

The semantic check creates a local VM that will execute the machine's log segment, the VM is initialized with a snapshot from the machine if possible. The local VM then runs the log segment and the data is recorded. The auditing tool then checks the log segments, inputs, outputs, and verification of snapshot hashes of the replayed execution against the original log. If any discrepancies are detected then the fault is reported and can be used as evidence against the machine.

=Critique=
=References=
[1] B. Cully, G. Lefebvre, D. Meyer, M. Feeley, N. Hutchinson, and
A. Warfield. Remus: High availability via asynchronous virtual
machine replication. In Proceedings of the USENIX Symposium
on Networked Systems Design and Implementation (NSDI), Apr.
2008.

[2] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[3] G. Hoglund. 4.5 million copies of EULA-compliant spyware.
http://www.rootkit.com/blog.php?newsid=358.

[4] PunkBuster web site. http://www.evenbalance.com/.

[5] N. E. Baughman, M. Liberatore, and B. N. Levine. Cheat-proof
playout for centralized and peer-to-peer gaming. IEEE/ACM
Transactions on Networking (ToN), 15(1):1–13, Feb. 2007.

[6] C. M¨onch, G. Grimen, and R. Midtstraum. Protecting online
games against cheating. In Proceedings of the Workshop on Network
and Systems Support for Games (NetGames), Oct. 2006.

[7] A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical
accountability for distributed systems. In Proceedings of
the ACM Symposium on Operating Systems Principles (SOSP),Oct. 2007.

[8] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[9] VMWare Workstation 6.5.1 web site. http://www.vmware.com/products/workstation/

COMP 3000 Essay 2 2010 Question 4

2010-11-27T19:12:58Z

Hirving: /* Contribution */

Talk:COMP 3000 Essay 2 2010 Question 4

2010-11-24T19:44:32Z

Hirving: /* Discussion */

= Group Essay 2 =

Hello Group. Please post your information here. I assume everybody read the email at your connect account. Anyone specific wants to send him the email with the group members inside? If not, I just go ahead tomorrow at about 13:00 and send the email with the group members who wrote their contact information in here. - [[User:Sschnei1|Sschnei1]] 03:25, 15 November 2010 (UTC)
 

Sebastian Schneider sschnei1@connect.carleton.ca

Matthew Chou mchou2@connect.carleton.ca

Mark Walts mwalts@connect.carleton.ca

Henry Irving hirving@connect.carleton.ca

Jean-Benoit Aubin jbaubin@connect.carleton.ca

Pradhan Nishant npradhan npradhan@connect.carleton.ca

Only Paul Cox didn't answer i sent this morning.

Cox Paul pcox

And I just sent an email to the teacher.

--Jean-Benoit

==Paper==

the paper's title, authors, and their affiliations. Include a link to the paper and any particularly helpful supplementary information.

'''Title:''' Accountable Virtual Machines

'''Authors:''' Andreas Haeberlen, Paarijaat Aditya, Rodrigo Rodrigues, Peter Druschel

'''Affiliates:'''
University of Pennsylvania, Max Planck Institute for Software Systems (MPI-SWS)]

'''Link to Paper:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Haeberlen.pdf Accountable Virtual Machines]

'''Supplementary Information:''' [http://research.microsoft.com/en-us/people/sriram/druschel.pptx Accountable distributed systems and the accountable cloud] - background of similar AVM implementation for distributed systems.

==Background Concepts==

Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.

'''Accountable Virtual Machine (AVM)'''

'''Deterministic Replay''': A machine can record its executions into a file so that it can be replayed in order to see the executions and follow what was happening on the machine. Remus [[#References | [1]]] has contributed a highly efficient snap-shotting mechanism for these replays.

'''Accountability:''' Accountability in the context of this paper means that every action done on the virtual machine is recorded and will be used against the machine or user to verify the correctness of the application. The AVM is responsible of its action and will answers for its action against an auditor.

'''Remote Fault Detection:''' There are programs like GridCop[[#References | [2]]] that can be used to monitor the progress and execution of a remotely executing program by requesting a beacon packet. When the remote computer is sending the packets, the receiving/logging computer must be a trusted computer (hardware,software, OS) so that the receiving of packets remains consistent. To detect a fault in a remote system, every packet must arrive safely, and any interrupts during the logging must be handled or the inconsistencies will result in an inaccurate outcome. The AVM does not require trusted hardware and can be used over wide-area networks.

'''Cheat Detection:''' Cheating in games or any specific modification in a program can be either scanned[[#References | [3][4]]] for or prevented[[#References | [5][6]]] by certain programs. The issue with these scanning and preventative software is the knowledge/awareness of specific cheats or situations that the software can handle. An AVM is designed to counter any kind of general cheat.

'''Integrity Violations:''' This refers how the consistency of normal/expected operations of an execution does not equal to that of the host/reference (Trusted) execution, hence a violation has occurred.

- The word "node" is used to refer to a computer or server in order to represent the interactions between one computer and another, or a computer and a server.

==Research problem==

What is the research problem being addressed by the paper? How does this problem relate to past related work?
**Possible alternative for the first part :

The research presented in this paper tries to tackle a problem that has haunted computer scientists for a long time. How can you be sure that the software running on a remote machine is working correctly or as intended. Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a trust relation between users and a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done would be independent of the node and only dependent on the intended software. Let's say, that node A interacts with node B with execution exe1 and node A interacts with node C also with ex1, but node C has been modified and respond with exe2. Thus, we can assume that the respond of B and C will be different. Being able to prove that the node C has been modified without any doubt is the purpose of this paper.
***Let me know what you think about it. I removed the redundant part, and I think made it clearer and more concise. [[User:Jbaubin|Jbaubin]]

** looks good to me, we'll put this part into the final essay instead of mine below --[[User:Mchou2|Mchou2]] 20:03, 22 November 2010 (UTC)

/// omit

Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a system of trust between users and a host. These different examples must have a certain amount of trust between the interactions of one user and another, as well as the user interacting with a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done with node A is the same it would be done with another node, node B. Let's say for example that node A interacts with node B with execution exe1, now when node A and B interact with node C, they would both expect to interact with execution exe1, but what happens if node C interacts differently and executes with exe2, then it would be beneficial to be notified of this difference. The previous explanation might not seem too relevant without some examples, such as; Node A is playing a game with node B, the game executed on node B is the same as on A, now when node A plays with node C, node C is executing the same operations as node A plus a cheating program; when node A buys some products from node B's server, the server processes the order and then deletes node A's sensitive information, denoted by execution 1, now when node A buys from node C's server, the order is processed as well as the sensitive information that node A has provided is also rerouted to another server so that it can be used without permission. These are only a few examples where the operations in an execution is necessary to be logged and verified. The problem that is trying to be handled here is to create a procedure that can be done so that a node can be known as accountable, and to log the operations in an execution to provide evidence of these faults done by a node.

////

Previous work that has been done in efforts to prevent or detect integrity violations can be separated into different categories of operations. The first would be Cheat Detection, where in many different games there are cheats that users use to usually create benefits for themselves that was not intended by the original game.[[#References |[4]]] These detectors are not dynamic, in the sense that they do not actually detect whether a cheat is being used, more so they are checking if there is a cheating operation that they have logged before, being operated on the user's system. For example, if there was a known cheating program named aimbot.exe that can be run in the background of a game such as CounterStrike, and the PunkBuster system that was implemented on the user's system had the aimbot.exe program already logged as a cheating program from the developers, the PunkBuster program might notify the current game servers of this or even prevent the user from playing any games until the aimbot.exe operation is no longer running.

Accountability is another important problem that many have already worked on. The main goal of an accountable system is to be able to determine without a doubt that node is faulty and can prove it with solid evidence. It can also be used to defend a node when threatened with false accusation. Numerous systems already use accountability in their system, but they were mostly all linked to specific applications, where a point of reference must be used to compare. As example PeerReview[[#References |[7]]], which is a system closely related to what the research team have worked on, must be implemented into the application which makes it less portable and cannot be implemented as easily as an AVM. PeerReview verifies the inbound and outbound packets and can see if the software is running as intended.

Another problem that is related to the paper is remote fault detection in a distributed system. How can we determine if a remote node is running the code correctly or if the machine itself is working as intended. Network activity is a common solution to this problem, as they look at the inbound and outbound of the node. This can let them know how the software is operating, or in the case of AVM how the whole virtual machine is working. Gridcop[[#References |[8]]] is another example that inspects a small number of packets periodically. Another way of determining the fault remotely is to use a trusted node, where it can tell immediately if a fault occurs or a modification is made where it should not have been made.

-and anything else you would to add or modify, or leave a note in the discussion sections if you want me to relook or change something. --[[User:Mchou2|Mchou2]] 20:10, 21 November 2010 (UTC)

The problem of logging and auditing the processes of an execution of a specific node (computer) is greatly dependent on the work done for deterministic replay. Deterministic replay programs can create a log file that can be used to replay the operations done for some execution that occurs on a node. Replaying the operations done on the node can show what the node was doing, and this would seem like it is sufficient in finding out whether a node was causing integrity violations or not. The concept of snap-shoting/recording the operations is not the issue with deterministic replay, it is the fact that the data being outputted into the replay may be tampered with by the node itself so that it generates optimal results in replay. By faking the results of the operations, the auditing computer will falsely believe that the tested computer is running all operations as normal. The logging operations done by these recording programs can be directly related to the work needed to detect integrity violations.

==Contribution==

What are the research contribution(s) of this work? Specifically, what are the key research results, and what do they mean? (What was implemented? Why is it any better than what came before?)

The accountable virtual machine (AVM), that was proposed in this essay, most useful contribution was the implementation of the accountable virtual machine monitor (AVMM). It is what allows for the fault checking of virtual machines in a cloud computing environment. The AVMM can be broken down into different parts: the virtual machine monitor (VMM), the temper-evident log, and auditing mechanisms. The VMM is based off the VMM found in VMWare Workstation 6.5.1[[#References |[9]]], the temper-evident log was adapted from code in PeerReview[[#References |[7]]], and the audit tools were built up from scratch.

The accountable virtual machine monitor relies on four assumptions:

1. All transmitted messages are received, if retransmitted sufficiently often.

2. Machines and Users have access to a has function that is pre-image resistant, second pre-image resistant, and collision resistant.

3. All parties have a certified keypair, that can be used to sign messages.

4. To audit a log, the user has a reference copy of the VM used.
The job of the AVMM is to record all incoming and outgoing messages to tamper-evident log.
and enough info of the execution to enable deterministic replay.

The AVMM must record nondeterministic inputs (such as hardware interrupts), because the input is asynchronous, the exact timing of input must be recorded, so that the inputs can be injected at the same points during replay. Wall-clock time is not accurate enough for this recording, so the AVMM must use a combination of instruction pointer, branch counter, and, possibly, additional registers. Not all inputs have to be recorded this way (software interrupts), because, they send requests to the AVM, which will be issued again during replay.

Two parallel streams appear in the tamper-evident log: message exchanges and nondeterministic inputs.
It is important for the AVMM to detect inconsistencies between the user's log and the machine's log (in case of foul play), so the AVMM simply cross-references messages and inputs during replay, thus, easily detecting any discrepancies.

The AVMM periodically takes snapshots of the AVM's current state, this facilitates fine-grain audits for the user, but it also increases overhead. The overhead is lowered slightly by the snapshots being incremental (only save the state that has been changed since the last snapshot). The user can authenticate the snapshot using a hash tree of the state (generated by the AVMM), the AVMM updates the hash tree after each snapshot.

'''Tamper-Evident Log'''

The log is made up of hash code entries.
Each log entry in form e = (s,t,c,h)
s = monotonically increasing sequence number
t = type
c = data of the type
h = hash value

The hash value is calculated by: h = H(hi-1 || s || t || H(c))
H() is a hash function.
|| stands for concatenation

Each message sent gets signed with a private key, when the AVMM logs the messages with the signature attached but removes it before sending it to the AVM. To ensure nonrepudiation, an authenticator is attached to each outgoing message.

To detect when a message is dropped, each party sends an acknowledgement for each message they receive. If an acknowledgement is not received the message is resent a few times, if the user stops receiving messages, then the machine is presumed to of failed.

To preform a log check, the user retrieves a pair of authenticators, then challenges the machine to produce the log segment between the two. The log is computationally infeasible to edit without breaking the hash chain, thus, if the log has been tampered with the hash chain will be different and the user will notified of the tampering.

'''Auditing Mechanism'''

From VVM's perspective all things are deterministic.

To preform a audit the user:

1. obtains a segment of the machine's log and the authenticators

2. downloads a snapshot of the AVM at the beginning of the segment

3. replays the entire segment, starting from the snapshot, to verify the events in the log are the correct execution of the software.

The user can verify the execution of software through three different methods: Verifying the log, snapshot, and execution.

When the user wants to verify a log segment, the user retrieves the authenticators from the machine with the sequence numbers in the range of the log segment. The user then downloads the log segment from the machine, and, starting with the most recent snapshot before the log segment and ending with the most recent snapshot before the end of the log segment. The user then check the authenticators for tampering. If this step proceeds, the user can assume the log segment executed properly. If the machine is faulty, the segment will be unavaible to download or may return a corrupted log segment. This can be used to convince a third party of the fault.

When the user wants to verify the snapshot, the user obtains a snapshot of the AVM's state at the beginning of the log segment. The user then downloads a snapshot from the machine and the AVMM recomputes the hash tree. The new hash tree is compared to the hash tree contained in the orignal log segment. If any discrepancies are detected, the user can use this to convince a third party of machine's fault.

In order for the user to verifying the execution of a log segment, the user needs three inputs: the log segment, the snapshot, and the public keys of the machine and any users of the machine. The auditing tool performs two checks on the log segment, a syntactic check (determines if log is well-formed), and a semantic check (determines if the information in the log shows the correct execution of the machine).

The syntactic check checks whether all log entries are in the proper format, the signatures in each message and acknowledgement, if each message was acknowledged, and the sequence of sent and received messages is correct when compared to the sequence of messages that enter and exit the AVM.

The semantic check creates a local VM that will execute the machine's log segment, the VM is initialized with a snapshot from the machine if possible. The local VM then runs the log segment and the data is recorded. The auditing tool then checks the log segments, inputs, outputs, and verification of snapshot hashes of the replayed execution against the original log. If any discrepancies are detected then the fault is reported and can be used as evidence as fault.

Why is it better?
[To Do]

==Critique==

What is good and not-so-good about this paper? You may discuss both the style and content; be sure to ground your discussion with specific references. Simple assertions that something is good or bad is not enough - you must explain why.

// first part of my writing; this is just part1 [[User:Sschnei1|Sschnei1]] 00:35, 24 November 2010 (UTC)

For the comprehension of the reader, it is important of a paper/article/essay to have a good overview/layout. The introduction clearly describes what the reader has to expect in the following pages, especially what problems are addressed and how they are solved.

This paper gives multiple examples about advantages and disadvantages in an AVM. A good example is "Cheat Detection". Cheaters use programs to go around the original game code to gain an major advantage over other players. Since an AVM is generic in cheat detection it has a wider support for detecting cheats than most of the other cheat detection algorithms. The logs give the game the function to replay the game. Thus, players using AVM can see the way other players play by replaying the game with the player's log.

The negative side is that the player might have to suffer from the AVM. Everything is being logged and stored on the hard drive, which takes a lot amount of space. In the example in the paper it is 148mb per hour after compression. This reduces the fps. Additionally, the connection to the AVM increases the ping time to the server.

==References==

You will almost certainly have to refer to other resources; please cite these resources in the style of citation of the papers assigned (inlined numbered references). Place your bibliographic entries in this section.

[1] B. Cully, G. Lefebvre, D. Meyer, M. Feeley, N. Hutchinson, and
A. Warfield. Remus: High availability via asynchronous virtual
machine replication. In Proceedings of the USENIX Symposium
on Networked Systems Design and Implementation (NSDI), Apr.
2008.

[2] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[3] G. Hoglund. 4.5 million copies of EULA-compliant spyware.
http://www.rootkit.com/blog.php?newsid=358.

[4] PunkBuster web site. http://www.evenbalance.com/.

[5] N. E. Baughman, M. Liberatore, and B. N. Levine. Cheat-proof
playout for centralized and peer-to-peer gaming. IEEE/ACM
Transactions on Networking (ToN), 15(1):1–13, Feb. 2007.

[6] C. M¨onch, G. Grimen, and R. Midtstraum. Protecting online
games against cheating. In Proceedings of the Workshop on Network
and Systems Support for Games (NetGames), Oct. 2006.

[7] A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical
accountability for distributed systems. In Proceedings of
the ACM Symposium on Operating Systems Principles (SOSP),Oct. 2007.

[8] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[9] VMWare Workstation 6.5.1 web site. http://www.vmware.com/products/workstation/

=Discussion=
We can use this area to discuss or leave notes on general ideas or whatever you want to write here.

-The current due date posted on the site for this essay is November 25th --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

-I think that since we are given the headings to this article, we can easily choose what parts each member would like to work on, obviously since there are more members than parts, multiple members will have to work on the same parts or can work on all parts, I guess it's really up to you. I know that most people have a lot of projects coming up so let's try to get this done asap, or at least bit by bit so it's not something we have to worry too much about. --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

- I would like to do the Contribution or Critique. -- [[User:Sschnei1|Sschnei1]] 02:40, 20 November 2010 (UTC)

- I can either work on Background Concepts, or Research problem. -[[User:Jbaubin|Jbaubin]]

- I'm not sure whether the background concepts should be in point form or a paragraph, and whether it needs to be very long or not, but I shall work on both background concepts and research problem with you Jbaubin. --[[User:Mchou2|Mchou2]] 18:11, 21 November 2010 (UTC)

-Sounds good, and As i was going to post what I had for research problem, I just saw you posted a big chunk of it. I'll be out for a while, but tonight I'll take a serious look at what you write and add what I had written. - [[User:Jbaubin|Jbaubin]]

- Sorry I didn't write anything yet to Critique. I'm making my notes and will post something tonight or tomorrow. -- [[User:Sschnei1|Sschnei1]] 14:50, 22 November 2010 (UTC)

- I have started work on the contribution section. I'll have something up today or tomorrow. --[[User:Hirving|Hirving]] 19:55, 23 November 2010 (UTC)

-if anyone has information that they are working on they can just post it up and at least others can look at it and maybe build up stuff on it, and I'm sure everyone is aware of the extension that we got also, but let's try to finish this in the next few days --[[User:Mchou2|Mchou2]] 20:43, 23 November 2010 (UTC)

- I agree with finishing it in the next few days. Then we have more time to focus on other courses like 3004. I will post something later that night. -- [[User:Sschnei1|Sschnei1]] 21:29, 23 November 2010 (UTC)

- Just added my contribution section, can someone proof read and sign it before I move it over to the essay. I didn't do the "why is it better" part because I found the implementation took a lot of writing. For anyone that wants to do the other part, I'd suggest comparing AVMs to PunkBuster and/or VAC, and a cloud computing service (focusing on the auditing). Cheers --[[User:Hirving|Hirving]] 19:44, 24 November 2010 (UTC)

COMP 3000 Essay 2 2010 Question 4

2010-11-24T19:37:18Z

Hirving: /* References */

Talk:COMP 3000 Essay 2 2010 Question 4

2010-11-24T19:34:11Z

Hirving: /* Contribution */

Talk:COMP 3000 Essay 2 2010 Question 4

2010-11-24T19:32:55Z

Hirving: /* Contribution */

= Group Essay 2 =

Hello Group. Please post your information here. I assume everybody read the email at your connect account. Anyone specific wants to send him the email with the group members inside? If not, I just go ahead tomorrow at about 13:00 and send the email with the group members who wrote their contact information in here. - [[User:Sschnei1|Sschnei1]] 03:25, 15 November 2010 (UTC)
 

Sebastian Schneider sschnei1@connect.carleton.ca

Matthew Chou mchou2@connect.carleton.ca

Mark Walts mwalts@connect.carleton.ca

Henry Irving hirving@connect.carleton.ca

Jean-Benoit Aubin jbaubin@connect.carleton.ca

Pradhan Nishant npradhan npradhan@connect.carleton.ca

Only Paul Cox didn't answer i sent this morning.

Cox Paul pcox

And I just sent an email to the teacher.

--Jean-Benoit

==Paper==

the paper's title, authors, and their affiliations. Include a link to the paper and any particularly helpful supplementary information.

'''Title:''' Accountable Virtual Machines

'''Authors:''' Andreas Haeberlen, Paarijaat Aditya, Rodrigo Rodrigues, Peter Druschel

'''Affiliates:'''
University of Pennsylvania, Max Planck Institute for Software Systems (MPI-SWS)]

'''Link to Paper:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Haeberlen.pdf Accountable Virtual Machines]

'''Supplementary Information:''' [http://research.microsoft.com/en-us/people/sriram/druschel.pptx Accountable distributed systems and the accountable cloud] - background of similar AVM implementation for distributed systems.

==Background Concepts==

Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.

'''Accountable Virtual Machine (AVM)'''

'''Deterministic Replay''': A machine can record its executions into a file so that it can be replayed in order to see the executions and follow what was happening on the machine. Remus [[#References | [1]]] has contributed a highly efficient snap-shotting mechanism for these replays.

'''Accountability:''' Accountability in the context of this paper means that every action done on the virtual machine is recorded and will be used against the machine or user to verify the correctness of the application. The AVM is responsible of its action and will answers for its action against an auditor.

'''Remote Fault Detection:''' There are programs like GridCop[[#References | [2]]] that can be used to monitor the progress and execution of a remotely executing program by requesting a beacon packet. When the remote computer is sending the packets, the receiving/logging computer must be a trusted computer (hardware,software, OS) so that the receiving of packets remains consistent. To detect a fault in a remote system, every packet must arrive safely, and any interrupts during the logging must be handled or the inconsistencies will result in an inaccurate outcome. The AVM does not require trusted hardware and can be used over wide-area networks.

'''Cheat Detection:''' Cheating in games or any specific modification in a program can be either scanned[[#References | [3][4]]] for or prevented[[#References | [5][6]]] by certain programs. The issue with these scanning and preventative software is the knowledge/awareness of specific cheats or situations that the software can handle. An AVM is designed to counter any kind of general cheat.

'''Integrity Violations:''' This refers how the consistency of normal/expected operations of an execution does not equal to that of the host/reference (Trusted) execution, hence a violation has occurred.

- The word "node" is used to refer to a computer or server in order to represent the interactions between one computer and another, or a computer and a server.

==Research problem==

What is the research problem being addressed by the paper? How does this problem relate to past related work?
**Possible alternative for the first part :

The research presented in this paper tries to tackle a problem that has haunted computer scientists for a long time. How can you be sure that the software running on a remote machine is working correctly or as intended. Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a trust relation between users and a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done would be independent of the node and only dependent on the intended software. Let's say, that node A interacts with node B with execution exe1 and node A interacts with node C also with ex1, but node C has been modified and respond with exe2. Thus, we can assume that the respond of B and C will be different. Being able to prove that the node C has been modified without any doubt is the purpose of this paper.
***Let me know what you think about it. I removed the redundant part, and I think made it clearer and more concise. [[User:Jbaubin|Jbaubin]]

** looks good to me, we'll put this part into the final essay instead of mine below --[[User:Mchou2|Mchou2]] 20:03, 22 November 2010 (UTC)

/// omit

Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a system of trust between users and a host. These different examples must have a certain amount of trust between the interactions of one user and another, as well as the user interacting with a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done with node A is the same it would be done with another node, node B. Let's say for example that node A interacts with node B with execution exe1, now when node A and B interact with node C, they would both expect to interact with execution exe1, but what happens if node C interacts differently and executes with exe2, then it would be beneficial to be notified of this difference. The previous explanation might not seem too relevant without some examples, such as; Node A is playing a game with node B, the game executed on node B is the same as on A, now when node A plays with node C, node C is executing the same operations as node A plus a cheating program; when node A buys some products from node B's server, the server processes the order and then deletes node A's sensitive information, denoted by execution 1, now when node A buys from node C's server, the order is processed as well as the sensitive information that node A has provided is also rerouted to another server so that it can be used without permission. These are only a few examples where the operations in an execution is necessary to be logged and verified. The problem that is trying to be handled here is to create a procedure that can be done so that a node can be known as accountable, and to log the operations in an execution to provide evidence of these faults done by a node.

////

Previous work that has been done in efforts to prevent or detect integrity violations can be separated into different categories of operations. The first would be Cheat Detection, where in many different games there are cheats that users use to usually create benefits for themselves that was not intended by the original game.[[#References |[4]]] These detectors are not dynamic, in the sense that they do not actually detect whether a cheat is being used, more so they are checking if there is a cheating operation that they have logged before, being operated on the user's system. For example, if there was a known cheating program named aimbot.exe that can be run in the background of a game such as CounterStrike, and the PunkBuster system that was implemented on the user's system had the aimbot.exe program already logged as a cheating program from the developers, the PunkBuster program might notify the current game servers of this or even prevent the user from playing any games until the aimbot.exe operation is no longer running.

Accountability is another important problem that many have already worked on. The main goal of an accountable system is to be able to determine without a doubt that node is faulty and can prove it with solid evidence. It can also be used to defend a node when threatened with false accusation. Numerous systems already use accountability in their system, but they were mostly all linked to specific applications, where a point of reference must be used to compare. As example PeerReview[[#References |[7]]], which is a system closely related to what the research team have worked on, must be implemented into the application which makes it less portable and cannot be implemented as easily as an AVM. PeerReview verifies the inbound and outbound packets and can see if the software is running as intended.

Another problem that is related to the paper is remote fault detection in a distributed system. How can we determine if a remote node is running the code correctly or if the machine itself is working as intended. Network activity is a common solution to this problem, as they look at the inbound and outbound of the node. This can let them know how the software is operating, or in the case of AVM how the whole virtual machine is working. Gridcop[[#References |[8]]] is another example that inspects a small number of packets periodically. Another way of determining the fault remotely is to use a trusted node, where it can tell immediately if a fault occurs or a modification is made where it should not have been made.

-and anything else you would to add or modify, or leave a note in the discussion sections if you want me to relook or change something. --[[User:Mchou2|Mchou2]] 20:10, 21 November 2010 (UTC)

The problem of logging and auditing the processes of an execution of a specific node (computer) is greatly dependent on the work done for deterministic replay. Deterministic replay programs can create a log file that can be used to replay the operations done for some execution that occurs on a node. Replaying the operations done on the node can show what the node was doing, and this would seem like it is sufficient in finding out whether a node was causing integrity violations or not. The concept of snap-shoting/recording the operations is not the issue with deterministic replay, it is the fact that the data being outputted into the replay may be tampered with by the node itself so that it generates optimal results in replay. By faking the results of the operations, the auditing computer will falsely believe that the tested computer is running all operations as normal. The logging operations done by these recording programs can be directly related to the work needed to detect integrity violations.

==Contribution==

What are the research contribution(s) of this work? Specifically, what are the key research results, and what do they mean? (What was implemented? Why is it any better than what came before?)

The accountable virtual machine (AVM), that was proposed in this essay, most useful contribution was the implementation of the accountable virtual machine monitor (AVMM). It is what allows for the fault checking of virtual machines in a cloud computing environment. The AVMM can be broken down into different parts: the virtual machine monitor (VMM), the temper-evident log, and auditing mechanisms. The VMM is based off the VMM found in VMWare Workstation 6.5.1[[#References |[9]]], the temper-evident log was adapted from code in PeerReview[[#References |[7]]], and the audit tools were built up from scratch.

The accountable virtual machine monitor relies on four assumptions:

1. All transmitted messages are received, if retransmitted sufficiently often.

2. Machines and Users have access to a has function that is pre-image resistant, second pre-image resistant, and collision resistant.

3. All parties have a certified keypair, that can be used to sign messages.

4. To audit a log, the user has a reference copy of the VM used.
The job of the AVMM is to record all incoming and outgoing messages to tamper-evident log.
and enough info of the execution to enable deterministic replay.

The AVMM must record nondeterministic inputs (such as hardware interrupts), because the input is asynchronous, the exact timing of input must be recorded, so that the inputs can be injected at the same points during replay. Wall-clock time is not accurate enough for this recording, so the AVMM must use a combination of instruction pointer, branch counter, and, possibly, additional registers. Not all inputs have to be recorded this way (software interrupts), because, they send requests to the AVM, which will be issued again during replay.

Two parallel streams appear in the tamper-evident log: message exchanges and nondeterministic inputs.
It is important for the AVMM to detect inconsistencies between the user's log and the machine's log (in case of foul play), so the AVMM simply cross-references messages and inputs during replay, thus, easily detecting any discrepancies.

The AVMM periodically takes snapshots of the AVM's current state, this facilitates fine-grain audits for the user, but it also increases overhead. The overhead is lowered slightly by the snapshots being incremental (only save the state that has been changed since the last snapshot). The user can authenticate the snapshot using a hash tree of the state (generated by the AVMM), the AVMM updates the hash tree after each snapshot.

'''Tamper-Evident Log'''

The log is made up of hash code entries.
Each log entry in form e = (s,t,c,h)
s = monotonically increasing sequence number
t = type
c = data of the type
h = hash value

The hash value is calculated by: h = H(hi-1 || s || t || H(c))
H() is a hash function.
|| stands for concatenation

Each message sent gets signed with a private key, when the AVMM logs the messages with the signature attached but removes it before sending it to the AVM. To ensure nonrepudiation, an authenticator is attached to each outgoing message.

To detect when a message is dropped, each party sends an acknowledgement for each message they receive. If an acknowledgement is not received the message is resent a few times, if the user stops receiving messages, then the machine is presumed to of failed.

To preform a log check, the user retrieves a pair of authenticators, then challenges the machine to produce the log segment between the two. The log is computationally infeasible to edit without breaking the hash chain, thus, if the log has been tampered with the hash chain will be different and the user will notified of the tampering.

'''Auditing Mechanism'''

From VVM's perspective all things are deterministic.

To preform a audit the user:

1. obtains a segment of the machine's log and the authenticators

2. downloads a snapshot of the AVM at the beginning of the segment

3. replays the entire segment, starting from the snapshot, to verify the events in the log are the correct execution of the software.

The user can verify the execution of software through three different methods: Verifying the log, snapshot, and execution.

When the user wants to verify a log segment, the user retrieves the authenticators from the machine with the sequence numbers in the range of the log segment. The user then downloads the log segment from the machine, and, starting with the most recent snapshot before the log segment and ending with the most recent snapshot before the end of the log segment. The user then check the authenticators for tampering. If this step proceeds, the user can assume the log segment executed properly. If the machine is faulty, the segment will be unavaible to download or may return a corrupted log segment. This can be used to convince a third party of the fault.

When the user wants to verify the snapshot, the user obtains a snapshot of the AVM's state at the beginning of the log segment. The user then downloads a snapshot from the machine and the AVMM recomputes the hash tree. The new hash tree is compared to the hash tree contained in the orignal log segment. If any discrepancies are detected, the user can use this to convince a third party of machine's fault.

In order for the user to verifying the execution of a log segment, the user needs three inputs: the log segment, the snapshot, and the public keys of the machine and any users of the machine. The auditing tool performs two checks on the log segment, a syntactic check (determines if log is well-formed), and a semantic check (determines if the information in the log shows the correct execution of the machine).

The syntactic check checks whether all log entries are in the proper format, the signatures in each message and acknowledgement, if each message was acknowledged, and the sequence of sent and received messages is correct when compared to the sequence of messages that enter and exit the AVM.

The semantic check creates a local VM that will execute the machine's log segment, the VM is initialized with a snapshot from the machine if possible. The local VM then runs the log segment and the data is recorded. The auditing tool then checks the log segments, inputs, outputs, and verification of snapshot hashes of the replayed execution against the original log. If any discrepancies are detected then the fault is reported and can be used as evidence as fault.

==Critique==

What is good and not-so-good about this paper? You may discuss both the style and content; be sure to ground your discussion with specific references. Simple assertions that something is good or bad is not enough - you must explain why.

// first part of my writing; this is just part1 [[User:Sschnei1|Sschnei1]] 00:35, 24 November 2010 (UTC)

For the comprehension of the reader, it is important of a paper/article/essay to have a good overview/layout. The introduction clearly describes what the reader has to expect in the following pages, especially what problems are addressed and how they are solved.

This paper gives multiple examples about advantages and disadvantages in an AVM. A good example is "Cheat Detection". Cheaters use programs to go around the original game code to gain an major advantage over other players. Since an AVM is generic in cheat detection it has a wider support for detecting cheats than most of the other cheat detection algorithms. The logs give the game the function to replay the game. Thus, players using AVM can see the way other players play by replaying the game with the player's log.

The negative side is that the player might have to suffer from the AVM. Everything is being logged and stored on the hard drive, which takes a lot amount of space. In the example in the paper it is 148mb per hour after compression. This reduces the fps. Additionally, the connection to the AVM increases the ping time to the server.

==References==

You will almost certainly have to refer to other resources; please cite these resources in the style of citation of the papers assigned (inlined numbered references). Place your bibliographic entries in this section.

[1] B. Cully, G. Lefebvre, D. Meyer, M. Feeley, N. Hutchinson, and
A. Warfield. Remus: High availability via asynchronous virtual
machine replication. In Proceedings of the USENIX Symposium
on Networked Systems Design and Implementation (NSDI), Apr.
2008.

[2] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[3] G. Hoglund. 4.5 million copies of EULA-compliant spyware.
http://www.rootkit.com/blog.php?newsid=358.

[4] PunkBuster web site. http://www.evenbalance.com/.

[5] N. E. Baughman, M. Liberatore, and B. N. Levine. Cheat-proof
playout for centralized and peer-to-peer gaming. IEEE/ACM
Transactions on Networking (ToN), 15(1):1–13, Feb. 2007.

[6] C. M¨onch, G. Grimen, and R. Midtstraum. Protecting online
games against cheating. In Proceedings of the Workshop on Network
and Systems Support for Games (NetGames), Oct. 2006.

[7] A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical
accountability for distributed systems. In Proceedings of
the ACM Symposium on Operating Systems Principles (SOSP),Oct. 2007.

[8] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[9] VMWare Workstation 6.5.1 web site. http://www.vmware.com/products/workstation/

=Discussion=
We can use this area to discuss or leave notes on general ideas or whatever you want to write here.

-The current due date posted on the site for this essay is November 25th --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

-I think that since we are given the headings to this article, we can easily choose what parts each member would like to work on, obviously since there are more members than parts, multiple members will have to work on the same parts or can work on all parts, I guess it's really up to you. I know that most people have a lot of projects coming up so let's try to get this done asap, or at least bit by bit so it's not something we have to worry too much about. --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

- I would like to do the Contribution or Critique. -- [[User:Sschnei1|Sschnei1]] 02:40, 20 November 2010 (UTC)

- I can either work on Background Concepts, or Research problem. -[[User:Jbaubin|Jbaubin]]

- I'm not sure whether the background concepts should be in point form or a paragraph, and whether it needs to be very long or not, but I shall work on both background concepts and research problem with you Jbaubin. --[[User:Mchou2|Mchou2]] 18:11, 21 November 2010 (UTC)

-Sounds good, and As i was going to post what I had for research problem, I just saw you posted a big chunk of it. I'll be out for a while, but tonight I'll take a serious look at what you write and add what I had written. - [[User:Jbaubin|Jbaubin]]

- Sorry I didn't write anything yet to Critique. I'm making my notes and will post something tonight or tomorrow. -- [[User:Sschnei1|Sschnei1]] 14:50, 22 November 2010 (UTC)

- I have started work on the contribution section. I'll have something up today or tomorrow. --[[User:Hirving|Hirving]] 19:55, 23 November 2010 (UTC)

-if anyone has information that they are working on they can just post it up and at least others can look at it and maybe build up stuff on it, and I'm sure everyone is aware of the extension that we got also, but let's try to finish this in the next few days --[[User:Mchou2|Mchou2]] 20:43, 23 November 2010 (UTC)

- I agree with finishing it in the next few days. Then we have more time to focus on other courses like 3004. I will post something later that night. -- [[User:Sschnei1|Sschnei1]] 21:29, 23 November 2010 (UTC)

Talk:COMP 3000 Essay 2 2010 Question 4

2010-11-24T19:31:49Z

Hirving: /* References */

= Group Essay 2 =

Hello Group. Please post your information here. I assume everybody read the email at your connect account. Anyone specific wants to send him the email with the group members inside? If not, I just go ahead tomorrow at about 13:00 and send the email with the group members who wrote their contact information in here. - [[User:Sschnei1|Sschnei1]] 03:25, 15 November 2010 (UTC)
 

Sebastian Schneider sschnei1@connect.carleton.ca

Matthew Chou mchou2@connect.carleton.ca

Mark Walts mwalts@connect.carleton.ca

Henry Irving hirving@connect.carleton.ca

Jean-Benoit Aubin jbaubin@connect.carleton.ca

Pradhan Nishant npradhan npradhan@connect.carleton.ca

Only Paul Cox didn't answer i sent this morning.

Cox Paul pcox

And I just sent an email to the teacher.

--Jean-Benoit

==Paper==

the paper's title, authors, and their affiliations. Include a link to the paper and any particularly helpful supplementary information.

'''Title:''' Accountable Virtual Machines

'''Authors:''' Andreas Haeberlen, Paarijaat Aditya, Rodrigo Rodrigues, Peter Druschel

'''Affiliates:'''
University of Pennsylvania, Max Planck Institute for Software Systems (MPI-SWS)]

'''Link to Paper:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Haeberlen.pdf Accountable Virtual Machines]

'''Supplementary Information:''' [http://research.microsoft.com/en-us/people/sriram/druschel.pptx Accountable distributed systems and the accountable cloud] - background of similar AVM implementation for distributed systems.

==Background Concepts==

Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.

'''Accountable Virtual Machine (AVM)'''

'''Deterministic Replay''': A machine can record its executions into a file so that it can be replayed in order to see the executions and follow what was happening on the machine. Remus [[#References | [1]]] has contributed a highly efficient snap-shotting mechanism for these replays.

'''Accountability:''' Accountability in the context of this paper means that every action done on the virtual machine is recorded and will be used against the machine or user to verify the correctness of the application. The AVM is responsible of its action and will answers for its action against an auditor.

'''Remote Fault Detection:''' There are programs like GridCop[[#References | [2]]] that can be used to monitor the progress and execution of a remotely executing program by requesting a beacon packet. When the remote computer is sending the packets, the receiving/logging computer must be a trusted computer (hardware,software, OS) so that the receiving of packets remains consistent. To detect a fault in a remote system, every packet must arrive safely, and any interrupts during the logging must be handled or the inconsistencies will result in an inaccurate outcome. The AVM does not require trusted hardware and can be used over wide-area networks.

'''Cheat Detection:''' Cheating in games or any specific modification in a program can be either scanned[[#References | [3][4]]] for or prevented[[#References | [5][6]]] by certain programs. The issue with these scanning and preventative software is the knowledge/awareness of specific cheats or situations that the software can handle. An AVM is designed to counter any kind of general cheat.

'''Integrity Violations:''' This refers how the consistency of normal/expected operations of an execution does not equal to that of the host/reference (Trusted) execution, hence a violation has occurred.

- The word "node" is used to refer to a computer or server in order to represent the interactions between one computer and another, or a computer and a server.

==Research problem==

What is the research problem being addressed by the paper? How does this problem relate to past related work?
**Possible alternative for the first part :

The research presented in this paper tries to tackle a problem that has haunted computer scientists for a long time. How can you be sure that the software running on a remote machine is working correctly or as intended. Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a trust relation between users and a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done would be independent of the node and only dependent on the intended software. Let's say, that node A interacts with node B with execution exe1 and node A interacts with node C also with ex1, but node C has been modified and respond with exe2. Thus, we can assume that the respond of B and C will be different. Being able to prove that the node C has been modified without any doubt is the purpose of this paper.
***Let me know what you think about it. I removed the redundant part, and I think made it clearer and more concise. [[User:Jbaubin|Jbaubin]]

** looks good to me, we'll put this part into the final essay instead of mine below --[[User:Mchou2|Mchou2]] 20:03, 22 November 2010 (UTC)

/// omit

Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a system of trust between users and a host. These different examples must have a certain amount of trust between the interactions of one user and another, as well as the user interacting with a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done with node A is the same it would be done with another node, node B. Let's say for example that node A interacts with node B with execution exe1, now when node A and B interact with node C, they would both expect to interact with execution exe1, but what happens if node C interacts differently and executes with exe2, then it would be beneficial to be notified of this difference. The previous explanation might not seem too relevant without some examples, such as; Node A is playing a game with node B, the game executed on node B is the same as on A, now when node A plays with node C, node C is executing the same operations as node A plus a cheating program; when node A buys some products from node B's server, the server processes the order and then deletes node A's sensitive information, denoted by execution 1, now when node A buys from node C's server, the order is processed as well as the sensitive information that node A has provided is also rerouted to another server so that it can be used without permission. These are only a few examples where the operations in an execution is necessary to be logged and verified. The problem that is trying to be handled here is to create a procedure that can be done so that a node can be known as accountable, and to log the operations in an execution to provide evidence of these faults done by a node.

////

Previous work that has been done in efforts to prevent or detect integrity violations can be separated into different categories of operations. The first would be Cheat Detection, where in many different games there are cheats that users use to usually create benefits for themselves that was not intended by the original game.[[#References |[4]]] These detectors are not dynamic, in the sense that they do not actually detect whether a cheat is being used, more so they are checking if there is a cheating operation that they have logged before, being operated on the user's system. For example, if there was a known cheating program named aimbot.exe that can be run in the background of a game such as CounterStrike, and the PunkBuster system that was implemented on the user's system had the aimbot.exe program already logged as a cheating program from the developers, the PunkBuster program might notify the current game servers of this or even prevent the user from playing any games until the aimbot.exe operation is no longer running.

Accountability is another important problem that many have already worked on. The main goal of an accountable system is to be able to determine without a doubt that node is faulty and can prove it with solid evidence. It can also be used to defend a node when threatened with false accusation. Numerous systems already use accountability in their system, but they were mostly all linked to specific applications, where a point of reference must be used to compare. As example PeerReview[[#References |[7]]], which is a system closely related to what the research team have worked on, must be implemented into the application which makes it less portable and cannot be implemented as easily as an AVM. PeerReview verifies the inbound and outbound packets and can see if the software is running as intended.

Another problem that is related to the paper is remote fault detection in a distributed system. How can we determine if a remote node is running the code correctly or if the machine itself is working as intended. Network activity is a common solution to this problem, as they look at the inbound and outbound of the node. This can let them know how the software is operating, or in the case of AVM how the whole virtual machine is working. Gridcop[[#References |[8]]] is another example that inspects a small number of packets periodically. Another way of determining the fault remotely is to use a trusted node, where it can tell immediately if a fault occurs or a modification is made where it should not have been made.

-and anything else you would to add or modify, or leave a note in the discussion sections if you want me to relook or change something. --[[User:Mchou2|Mchou2]] 20:10, 21 November 2010 (UTC)

The problem of logging and auditing the processes of an execution of a specific node (computer) is greatly dependent on the work done for deterministic replay. Deterministic replay programs can create a log file that can be used to replay the operations done for some execution that occurs on a node. Replaying the operations done on the node can show what the node was doing, and this would seem like it is sufficient in finding out whether a node was causing integrity violations or not. The concept of snap-shoting/recording the operations is not the issue with deterministic replay, it is the fact that the data being outputted into the replay may be tampered with by the node itself so that it generates optimal results in replay. By faking the results of the operations, the auditing computer will falsely believe that the tested computer is running all operations as normal. The logging operations done by these recording programs can be directly related to the work needed to detect integrity violations.

==Contribution==

What are the research contribution(s) of this work? Specifically, what are the key research results, and what do they mean? (What was implemented? Why is it any better than what came before?)

The accountable virtual machine (AVM), that was proposed in this essay, most useful contribution was the implementation of the accountable virtual machine monitor (AVMM). It is what allows for the fault checking of virtual machines in a cloud computing environment. The AVMM can be broken down into different parts: the virtual machine monitor (VMM), the temper-evident log, and auditing mechanisms. The VMM is based off the VMM found in VMWare Workstation 6.5.1, the temper-evident log was adapted from code in PeerReview[[#References |[7]]], and the audit tools were built up from scratch.

The accountable virtual machine monitor relies on four assumptions:

1. All transmitted messages are received, if retransmitted sufficiently often.

2. Machines and Users have access to a has function that is pre-image resistant, second pre-image resistant, and collision resistant.

3. All parties have a certified keypair, that can be used to sign messages.

4. To audit a log, the user has a reference copy of the VM used.
The job of the AVMM is to record all incoming and outgoing messages to tamper-evident log.
and enough info of the execution to enable deterministic replay.

The AVMM must record nondeterministic inputs (such as hardware interrupts), because the input is asynchronous, the exact timing of input must be recorded, so that the inputs can be injected at the same points during replay. Wall-clock time is not accurate enough for this recording, so the AVMM must use a combination of instruction pointer, branch counter, and, possibly, additional registers. Not all inputs have to be recorded this way (software interrupts), because, they send requests to the AVM, which will be issued again during replay.

Two parallel streams appear in the tamper-evident log: message exchanges and nondeterministic inputs.
It is important for the AVMM to detect inconsistencies between the user's log and the machine's log (in case of foul play), so the AVMM simply cross-references messages and inputs during replay, thus, easily detecting any discrepancies.

The AVMM periodically takes snapshots of the AVM's current state, this facilitates fine-grain audits for the user, but it also increases overhead. The overhead is lowered slightly by the snapshots being incremental (only save the state that has been changed since the last snapshot). The user can authenticate the snapshot using a hash tree of the state (generated by the AVMM), the AVMM updates the hash tree after each snapshot.

'''Tamper-Evident Log'''

The log is made up of hash code entries.
Each log entry in form e = (s,t,c,h)
s = monotonically increasing sequence number
t = type
c = data of the type
h = hash value

The hash value is calculated by: h = H(hi-1 || s || t || H(c))
H() is a hash function.
|| stands for concatenation

Each message sent gets signed with a private key, when the AVMM logs the messages with the signature attached but removes it before sending it to the AVM. To ensure nonrepudiation, an authenticator is attached to each outgoing message.

To detect when a message is dropped, each party sends an acknowledgement for each message they receive. If an acknowledgement is not received the message is resent a few times, if the user stops receiving messages, then the machine is presumed to of failed.

To preform a log check, the user retrieves a pair of authenticators, then challenges the machine to produce the log segment between the two. The log is computationally infeasible to edit without breaking the hash chain, thus, if the log has been tampered with the hash chain will be different and the user will notified of the tampering.

'''Auditing Mechanism'''

From VVM's perspective all things are deterministic.

To preform a audit the user:

1. obtains a segment of the machine's log and the authenticators

2. downloads a snapshot of the AVM at the beginning of the segment

3. replays the entire segment, starting from the snapshot, to verify the events in the log are the correct execution of the software.

The user can verify the execution of software through three different methods: Verifying the log, snapshot, and execution.

When the user wants to verify a log segment, the user retrieves the authenticators from the machine with the sequence numbers in the range of the log segment. The user then downloads the log segment from the machine, and, starting with the most recent snapshot before the log segment and ending with the most recent snapshot before the end of the log segment. The user then check the authenticators for tampering. If this step proceeds, the user can assume the log segment executed properly. If the machine is faulty, the segment will be unavaible to download or may return a corrupted log segment. This can be used to convince a third party of the fault.

When the user wants to verify the snapshot, the user obtains a snapshot of the AVM's state at the beginning of the log segment. The user then downloads a snapshot from the machine and the AVMM recomputes the hash tree. The new hash tree is compared to the hash tree contained in the orignal log segment. If any discrepancies are detected, the user can use this to convince a third party of machine's fault.

In order for the user to verifying the execution of a log segment, the user needs three inputs: the log segment, the snapshot, and the public keys of the machine and any users of the machine. The auditing tool performs two checks on the log segment, a syntactic check (determines if log is well-formed), and a semantic check (determines if the information in the log shows the correct execution of the machine).

The syntactic check checks whether all log entries are in the proper format, the signatures in each message and acknowledgement, if each message was acknowledged, and the sequence of sent and received messages is correct when compared to the sequence of messages that enter and exit the AVM.

The semantic check creates a local VM that will execute the machine's log segment, the VM is initialized with a snapshot from the machine if possible. The local VM then runs the log segment and the data is recorded. The auditing tool then checks the log segments, inputs, outputs, and verification of snapshot hashes of the replayed execution against the original log. If any discrepancies are detected then the fault is reported and can be used as evidence as fault.

==Critique==

What is good and not-so-good about this paper? You may discuss both the style and content; be sure to ground your discussion with specific references. Simple assertions that something is good or bad is not enough - you must explain why.

// first part of my writing; this is just part1 [[User:Sschnei1|Sschnei1]] 00:35, 24 November 2010 (UTC)

For the comprehension of the reader, it is important of a paper/article/essay to have a good overview/layout. The introduction clearly describes what the reader has to expect in the following pages, especially what problems are addressed and how they are solved.

This paper gives multiple examples about advantages and disadvantages in an AVM. A good example is "Cheat Detection". Cheaters use programs to go around the original game code to gain an major advantage over other players. Since an AVM is generic in cheat detection it has a wider support for detecting cheats than most of the other cheat detection algorithms. The logs give the game the function to replay the game. Thus, players using AVM can see the way other players play by replaying the game with the player's log.

The negative side is that the player might have to suffer from the AVM. Everything is being logged and stored on the hard drive, which takes a lot amount of space. In the example in the paper it is 148mb per hour after compression. This reduces the fps. Additionally, the connection to the AVM increases the ping time to the server.

==References==

You will almost certainly have to refer to other resources; please cite these resources in the style of citation of the papers assigned (inlined numbered references). Place your bibliographic entries in this section.

[1] B. Cully, G. Lefebvre, D. Meyer, M. Feeley, N. Hutchinson, and
A. Warfield. Remus: High availability via asynchronous virtual
machine replication. In Proceedings of the USENIX Symposium
on Networked Systems Design and Implementation (NSDI), Apr.
2008.

[2] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[3] G. Hoglund. 4.5 million copies of EULA-compliant spyware.
http://www.rootkit.com/blog.php?newsid=358.

[4] PunkBuster web site. http://www.evenbalance.com/.

[5] N. E. Baughman, M. Liberatore, and B. N. Levine. Cheat-proof
playout for centralized and peer-to-peer gaming. IEEE/ACM
Transactions on Networking (ToN), 15(1):1–13, Feb. 2007.

[6] C. M¨onch, G. Grimen, and R. Midtstraum. Protecting online
games against cheating. In Proceedings of the Workshop on Network
and Systems Support for Games (NetGames), Oct. 2006.

[7] A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical
accountability for distributed systems. In Proceedings of
the ACM Symposium on Operating Systems Principles (SOSP),Oct. 2007.

[8] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[9] VMWare Workstation 6.5.1 web site. http://www.vmware.com/products/workstation/

=Discussion=
We can use this area to discuss or leave notes on general ideas or whatever you want to write here.

-The current due date posted on the site for this essay is November 25th --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

-I think that since we are given the headings to this article, we can easily choose what parts each member would like to work on, obviously since there are more members than parts, multiple members will have to work on the same parts or can work on all parts, I guess it's really up to you. I know that most people have a lot of projects coming up so let's try to get this done asap, or at least bit by bit so it's not something we have to worry too much about. --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

- I would like to do the Contribution or Critique. -- [[User:Sschnei1|Sschnei1]] 02:40, 20 November 2010 (UTC)

- I can either work on Background Concepts, or Research problem. -[[User:Jbaubin|Jbaubin]]

- I'm not sure whether the background concepts should be in point form or a paragraph, and whether it needs to be very long or not, but I shall work on both background concepts and research problem with you Jbaubin. --[[User:Mchou2|Mchou2]] 18:11, 21 November 2010 (UTC)

-Sounds good, and As i was going to post what I had for research problem, I just saw you posted a big chunk of it. I'll be out for a while, but tonight I'll take a serious look at what you write and add what I had written. - [[User:Jbaubin|Jbaubin]]

- Sorry I didn't write anything yet to Critique. I'm making my notes and will post something tonight or tomorrow. -- [[User:Sschnei1|Sschnei1]] 14:50, 22 November 2010 (UTC)

- I have started work on the contribution section. I'll have something up today or tomorrow. --[[User:Hirving|Hirving]] 19:55, 23 November 2010 (UTC)

-if anyone has information that they are working on they can just post it up and at least others can look at it and maybe build up stuff on it, and I'm sure everyone is aware of the extension that we got also, but let's try to finish this in the next few days --[[User:Mchou2|Mchou2]] 20:43, 23 November 2010 (UTC)

- I agree with finishing it in the next few days. Then we have more time to focus on other courses like 3004. I will post something later that night. -- [[User:Sschnei1|Sschnei1]] 21:29, 23 November 2010 (UTC)

Talk:COMP 3000 Essay 2 2010 Question 4

2010-11-24T19:28:43Z

Hirving: /* Contribution */

= Group Essay 2 =

Hello Group. Please post your information here. I assume everybody read the email at your connect account. Anyone specific wants to send him the email with the group members inside? If not, I just go ahead tomorrow at about 13:00 and send the email with the group members who wrote their contact information in here. - [[User:Sschnei1|Sschnei1]] 03:25, 15 November 2010 (UTC)
 

Sebastian Schneider sschnei1@connect.carleton.ca

Matthew Chou mchou2@connect.carleton.ca

Mark Walts mwalts@connect.carleton.ca

Henry Irving hirving@connect.carleton.ca

Jean-Benoit Aubin jbaubin@connect.carleton.ca

Pradhan Nishant npradhan npradhan@connect.carleton.ca

Only Paul Cox didn't answer i sent this morning.

Cox Paul pcox

And I just sent an email to the teacher.

--Jean-Benoit

==Paper==

the paper's title, authors, and their affiliations. Include a link to the paper and any particularly helpful supplementary information.

'''Title:''' Accountable Virtual Machines

'''Authors:''' Andreas Haeberlen, Paarijaat Aditya, Rodrigo Rodrigues, Peter Druschel

'''Affiliates:'''
University of Pennsylvania, Max Planck Institute for Software Systems (MPI-SWS)]

'''Link to Paper:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Haeberlen.pdf Accountable Virtual Machines]

'''Supplementary Information:''' [http://research.microsoft.com/en-us/people/sriram/druschel.pptx Accountable distributed systems and the accountable cloud] - background of similar AVM implementation for distributed systems.

==Background Concepts==

Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.

'''Accountable Virtual Machine (AVM)'''

'''Deterministic Replay''': A machine can record its executions into a file so that it can be replayed in order to see the executions and follow what was happening on the machine. Remus [[#References | [1]]] has contributed a highly efficient snap-shotting mechanism for these replays.

'''Accountability:''' Accountability in the context of this paper means that every action done on the virtual machine is recorded and will be used against the machine or user to verify the correctness of the application. The AVM is responsible of its action and will answers for its action against an auditor.

'''Remote Fault Detection:''' There are programs like GridCop[[#References | [2]]] that can be used to monitor the progress and execution of a remotely executing program by requesting a beacon packet. When the remote computer is sending the packets, the receiving/logging computer must be a trusted computer (hardware,software, OS) so that the receiving of packets remains consistent. To detect a fault in a remote system, every packet must arrive safely, and any interrupts during the logging must be handled or the inconsistencies will result in an inaccurate outcome. The AVM does not require trusted hardware and can be used over wide-area networks.

'''Cheat Detection:''' Cheating in games or any specific modification in a program can be either scanned[[#References | [3][4]]] for or prevented[[#References | [5][6]]] by certain programs. The issue with these scanning and preventative software is the knowledge/awareness of specific cheats or situations that the software can handle. An AVM is designed to counter any kind of general cheat.

'''Integrity Violations:''' This refers how the consistency of normal/expected operations of an execution does not equal to that of the host/reference (Trusted) execution, hence a violation has occurred.

- The word "node" is used to refer to a computer or server in order to represent the interactions between one computer and another, or a computer and a server.

==Research problem==

What is the research problem being addressed by the paper? How does this problem relate to past related work?
**Possible alternative for the first part :

The research presented in this paper tries to tackle a problem that has haunted computer scientists for a long time. How can you be sure that the software running on a remote machine is working correctly or as intended. Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a trust relation between users and a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done would be independent of the node and only dependent on the intended software. Let's say, that node A interacts with node B with execution exe1 and node A interacts with node C also with ex1, but node C has been modified and respond with exe2. Thus, we can assume that the respond of B and C will be different. Being able to prove that the node C has been modified without any doubt is the purpose of this paper.
***Let me know what you think about it. I removed the redundant part, and I think made it clearer and more concise. [[User:Jbaubin|Jbaubin]]

** looks good to me, we'll put this part into the final essay instead of mine below --[[User:Mchou2|Mchou2]] 20:03, 22 November 2010 (UTC)

/// omit

Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a system of trust between users and a host. These different examples must have a certain amount of trust between the interactions of one user and another, as well as the user interacting with a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done with node A is the same it would be done with another node, node B. Let's say for example that node A interacts with node B with execution exe1, now when node A and B interact with node C, they would both expect to interact with execution exe1, but what happens if node C interacts differently and executes with exe2, then it would be beneficial to be notified of this difference. The previous explanation might not seem too relevant without some examples, such as; Node A is playing a game with node B, the game executed on node B is the same as on A, now when node A plays with node C, node C is executing the same operations as node A plus a cheating program; when node A buys some products from node B's server, the server processes the order and then deletes node A's sensitive information, denoted by execution 1, now when node A buys from node C's server, the order is processed as well as the sensitive information that node A has provided is also rerouted to another server so that it can be used without permission. These are only a few examples where the operations in an execution is necessary to be logged and verified. The problem that is trying to be handled here is to create a procedure that can be done so that a node can be known as accountable, and to log the operations in an execution to provide evidence of these faults done by a node.

////

Previous work that has been done in efforts to prevent or detect integrity violations can be separated into different categories of operations. The first would be Cheat Detection, where in many different games there are cheats that users use to usually create benefits for themselves that was not intended by the original game.[[#References |[4]]] These detectors are not dynamic, in the sense that they do not actually detect whether a cheat is being used, more so they are checking if there is a cheating operation that they have logged before, being operated on the user's system. For example, if there was a known cheating program named aimbot.exe that can be run in the background of a game such as CounterStrike, and the PunkBuster system that was implemented on the user's system had the aimbot.exe program already logged as a cheating program from the developers, the PunkBuster program might notify the current game servers of this or even prevent the user from playing any games until the aimbot.exe operation is no longer running.

Accountability is another important problem that many have already worked on. The main goal of an accountable system is to be able to determine without a doubt that node is faulty and can prove it with solid evidence. It can also be used to defend a node when threatened with false accusation. Numerous systems already use accountability in their system, but they were mostly all linked to specific applications, where a point of reference must be used to compare. As example PeerReview[[#References |[7]]], which is a system closely related to what the research team have worked on, must be implemented into the application which makes it less portable and cannot be implemented as easily as an AVM. PeerReview verifies the inbound and outbound packets and can see if the software is running as intended.

Another problem that is related to the paper is remote fault detection in a distributed system. How can we determine if a remote node is running the code correctly or if the machine itself is working as intended. Network activity is a common solution to this problem, as they look at the inbound and outbound of the node. This can let them know how the software is operating, or in the case of AVM how the whole virtual machine is working. Gridcop[[#References |[8]]] is another example that inspects a small number of packets periodically. Another way of determining the fault remotely is to use a trusted node, where it can tell immediately if a fault occurs or a modification is made where it should not have been made.

-and anything else you would to add or modify, or leave a note in the discussion sections if you want me to relook or change something. --[[User:Mchou2|Mchou2]] 20:10, 21 November 2010 (UTC)

The problem of logging and auditing the processes of an execution of a specific node (computer) is greatly dependent on the work done for deterministic replay. Deterministic replay programs can create a log file that can be used to replay the operations done for some execution that occurs on a node. Replaying the operations done on the node can show what the node was doing, and this would seem like it is sufficient in finding out whether a node was causing integrity violations or not. The concept of snap-shoting/recording the operations is not the issue with deterministic replay, it is the fact that the data being outputted into the replay may be tampered with by the node itself so that it generates optimal results in replay. By faking the results of the operations, the auditing computer will falsely believe that the tested computer is running all operations as normal. The logging operations done by these recording programs can be directly related to the work needed to detect integrity violations.

==Contribution==

What are the research contribution(s) of this work? Specifically, what are the key research results, and what do they mean? (What was implemented? Why is it any better than what came before?)

The accountable virtual machine (AVM), that was proposed in this essay, most useful contribution was the implementation of the accountable virtual machine monitor (AVMM). It is what allows for the fault checking of virtual machines in a cloud computing environment. The AVMM can be broken down into different parts: the virtual machine monitor (VMM), the temper-evident log, and auditing mechanisms. The VMM is based off the VMM found in VMWare Workstation 6.5.1, the temper-evident log was adapted from code in PeerReview[[#References |[7]]], and the audit tools were built up from scratch.

The accountable virtual machine monitor relies on four assumptions:

1. All transmitted messages are received, if retransmitted sufficiently often.

2. Machines and Users have access to a has function that is pre-image resistant, second pre-image resistant, and collision resistant.

3. All parties have a certified keypair, that can be used to sign messages.

4. To audit a log, the user has a reference copy of the VM used.
The job of the AVMM is to record all incoming and outgoing messages to tamper-evident log.
and enough info of the execution to enable deterministic replay.

The AVMM must record nondeterministic inputs (such as hardware interrupts), because the input is asynchronous, the exact timing of input must be recorded, so that the inputs can be injected at the same points during replay. Wall-clock time is not accurate enough for this recording, so the AVMM must use a combination of instruction pointer, branch counter, and, possibly, additional registers. Not all inputs have to be recorded this way (software interrupts), because, they send requests to the AVM, which will be issued again during replay.

Two parallel streams appear in the tamper-evident log: message exchanges and nondeterministic inputs.
It is important for the AVMM to detect inconsistencies between the user's log and the machine's log (in case of foul play), so the AVMM simply cross-references messages and inputs during replay, thus, easily detecting any discrepancies.

The AVMM periodically takes snapshots of the AVM's current state, this facilitates fine-grain audits for the user, but it also increases overhead. The overhead is lowered slightly by the snapshots being incremental (only save the state that has been changed since the last snapshot). The user can authenticate the snapshot using a hash tree of the state (generated by the AVMM), the AVMM updates the hash tree after each snapshot.

'''Tamper-Evident Log'''

The log is made up of hash code entries.
Each log entry in form e = (s,t,c,h)
s = monotonically increasing sequence number
t = type
c = data of the type
h = hash value

The hash value is calculated by: h = H(hi-1 || s || t || H(c))
H() is a hash function.
|| stands for concatenation

Each message sent gets signed with a private key, when the AVMM logs the messages with the signature attached but removes it before sending it to the AVM. To ensure nonrepudiation, an authenticator is attached to each outgoing message.

To detect when a message is dropped, each party sends an acknowledgement for each message they receive. If an acknowledgement is not received the message is resent a few times, if the user stops receiving messages, then the machine is presumed to of failed.

To preform a log check, the user retrieves a pair of authenticators, then challenges the machine to produce the log segment between the two. The log is computationally infeasible to edit without breaking the hash chain, thus, if the log has been tampered with the hash chain will be different and the user will notified of the tampering.

'''Auditing Mechanism'''

From VVM's perspective all things are deterministic.

To preform a audit the user:

1. obtains a segment of the machine's log and the authenticators

2. downloads a snapshot of the AVM at the beginning of the segment

3. replays the entire segment, starting from the snapshot, to verify the events in the log are the correct execution of the software.

The user can verify the execution of software through three different methods: Verifying the log, snapshot, and execution.

When the user wants to verify a log segment, the user retrieves the authenticators from the machine with the sequence numbers in the range of the log segment. The user then downloads the log segment from the machine, and, starting with the most recent snapshot before the log segment and ending with the most recent snapshot before the end of the log segment. The user then check the authenticators for tampering. If this step proceeds, the user can assume the log segment executed properly. If the machine is faulty, the segment will be unavaible to download or may return a corrupted log segment. This can be used to convince a third party of the fault.

When the user wants to verify the snapshot, the user obtains a snapshot of the AVM's state at the beginning of the log segment. The user then downloads a snapshot from the machine and the AVMM recomputes the hash tree. The new hash tree is compared to the hash tree contained in the orignal log segment. If any discrepancies are detected, the user can use this to convince a third party of machine's fault.

In order for the user to verifying the execution of a log segment, the user needs three inputs: the log segment, the snapshot, and the public keys of the machine and any users of the machine. The auditing tool performs two checks on the log segment, a syntactic check (determines if log is well-formed), and a semantic check (determines if the information in the log shows the correct execution of the machine).

The syntactic check checks whether all log entries are in the proper format, the signatures in each message and acknowledgement, if each message was acknowledged, and the sequence of sent and received messages is correct when compared to the sequence of messages that enter and exit the AVM.

The semantic check creates a local VM that will execute the machine's log segment, the VM is initialized with a snapshot from the machine if possible. The local VM then runs the log segment and the data is recorded. The auditing tool then checks the log segments, inputs, outputs, and verification of snapshot hashes of the replayed execution against the original log. If any discrepancies are detected then the fault is reported and can be used as evidence as fault.

==Critique==

What is good and not-so-good about this paper? You may discuss both the style and content; be sure to ground your discussion with specific references. Simple assertions that something is good or bad is not enough - you must explain why.

// first part of my writing; this is just part1 [[User:Sschnei1|Sschnei1]] 00:35, 24 November 2010 (UTC)

For the comprehension of the reader, it is important of a paper/article/essay to have a good overview/layout. The introduction clearly describes what the reader has to expect in the following pages, especially what problems are addressed and how they are solved.

This paper gives multiple examples about advantages and disadvantages in an AVM. A good example is "Cheat Detection". Cheaters use programs to go around the original game code to gain an major advantage over other players. Since an AVM is generic in cheat detection it has a wider support for detecting cheats than most of the other cheat detection algorithms. The logs give the game the function to replay the game. Thus, players using AVM can see the way other players play by replaying the game with the player's log.

The negative side is that the player might have to suffer from the AVM. Everything is being logged and stored on the hard drive, which takes a lot amount of space. In the example in the paper it is 148mb per hour after compression. This reduces the fps. Additionally, the connection to the AVM increases the ping time to the server.

==References==

You will almost certainly have to refer to other resources; please cite these resources in the style of citation of the papers assigned (inlined numbered references). Place your bibliographic entries in this section.

[1] B. Cully, G. Lefebvre, D. Meyer, M. Feeley, N. Hutchinson, and
A. Warfield. Remus: High availability via asynchronous virtual
machine replication. In Proceedings of the USENIX Symposium
on Networked Systems Design and Implementation (NSDI), Apr.
2008.

[2] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[3] G. Hoglund. 4.5 million copies of EULA-compliant spyware.
http://www.rootkit.com/blog.php?newsid=358.

[4] PunkBuster web site. http://www.evenbalance.com/.

[5] N. E. Baughman, M. Liberatore, and B. N. Levine. Cheat-proof
playout for centralized and peer-to-peer gaming. IEEE/ACM
Transactions on Networking (ToN), 15(1):1–13, Feb. 2007.

[6] C. M¨onch, G. Grimen, and R. Midtstraum. Protecting online
games against cheating. In Proceedings of the Workshop on Network
and Systems Support for Games (NetGames), Oct. 2006.

[7] A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical
accountability for distributed systems. In Proceedings of
the ACM Symposium on Operating Systems Principles (SOSP),Oct. 2007.

[8] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

=Discussion=
We can use this area to discuss or leave notes on general ideas or whatever you want to write here.

-The current due date posted on the site for this essay is November 25th --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

-I think that since we are given the headings to this article, we can easily choose what parts each member would like to work on, obviously since there are more members than parts, multiple members will have to work on the same parts or can work on all parts, I guess it's really up to you. I know that most people have a lot of projects coming up so let's try to get this done asap, or at least bit by bit so it's not something we have to worry too much about. --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

- I would like to do the Contribution or Critique. -- [[User:Sschnei1|Sschnei1]] 02:40, 20 November 2010 (UTC)

- I can either work on Background Concepts, or Research problem. -[[User:Jbaubin|Jbaubin]]

- I'm not sure whether the background concepts should be in point form or a paragraph, and whether it needs to be very long or not, but I shall work on both background concepts and research problem with you Jbaubin. --[[User:Mchou2|Mchou2]] 18:11, 21 November 2010 (UTC)

-Sounds good, and As i was going to post what I had for research problem, I just saw you posted a big chunk of it. I'll be out for a while, but tonight I'll take a serious look at what you write and add what I had written. - [[User:Jbaubin|Jbaubin]]

- Sorry I didn't write anything yet to Critique. I'm making my notes and will post something tonight or tomorrow. -- [[User:Sschnei1|Sschnei1]] 14:50, 22 November 2010 (UTC)

- I have started work on the contribution section. I'll have something up today or tomorrow. --[[User:Hirving|Hirving]] 19:55, 23 November 2010 (UTC)

-if anyone has information that they are working on they can just post it up and at least others can look at it and maybe build up stuff on it, and I'm sure everyone is aware of the extension that we got also, but let's try to finish this in the next few days --[[User:Mchou2|Mchou2]] 20:43, 23 November 2010 (UTC)

- I agree with finishing it in the next few days. Then we have more time to focus on other courses like 3004. I will post something later that night. -- [[User:Sschnei1|Sschnei1]] 21:29, 23 November 2010 (UTC)

Talk:COMP 3000 Essay 2 2010 Question 4

2010-11-24T19:27:07Z

Hirving: /* Contribution */

= Group Essay 2 =

Hello Group. Please post your information here. I assume everybody read the email at your connect account. Anyone specific wants to send him the email with the group members inside? If not, I just go ahead tomorrow at about 13:00 and send the email with the group members who wrote their contact information in here. - [[User:Sschnei1|Sschnei1]] 03:25, 15 November 2010 (UTC)
 

Sebastian Schneider sschnei1@connect.carleton.ca

Matthew Chou mchou2@connect.carleton.ca

Mark Walts mwalts@connect.carleton.ca

Henry Irving hirving@connect.carleton.ca

Jean-Benoit Aubin jbaubin@connect.carleton.ca

Pradhan Nishant npradhan npradhan@connect.carleton.ca

Only Paul Cox didn't answer i sent this morning.

Cox Paul pcox

And I just sent an email to the teacher.

--Jean-Benoit

==Paper==

the paper's title, authors, and their affiliations. Include a link to the paper and any particularly helpful supplementary information.

'''Title:''' Accountable Virtual Machines

'''Authors:''' Andreas Haeberlen, Paarijaat Aditya, Rodrigo Rodrigues, Peter Druschel

'''Affiliates:'''
University of Pennsylvania, Max Planck Institute for Software Systems (MPI-SWS)]

'''Link to Paper:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Haeberlen.pdf Accountable Virtual Machines]

'''Supplementary Information:''' [http://research.microsoft.com/en-us/people/sriram/druschel.pptx Accountable distributed systems and the accountable cloud] - background of similar AVM implementation for distributed systems.

==Background Concepts==

Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.

'''Accountable Virtual Machine (AVM)'''

'''Deterministic Replay''': A machine can record its executions into a file so that it can be replayed in order to see the executions and follow what was happening on the machine. Remus [[#References | [1]]] has contributed a highly efficient snap-shotting mechanism for these replays.

'''Accountability:''' Accountability in the context of this paper means that every action done on the virtual machine is recorded and will be used against the machine or user to verify the correctness of the application. The AVM is responsible of its action and will answers for its action against an auditor.

'''Remote Fault Detection:''' There are programs like GridCop[[#References | [2]]] that can be used to monitor the progress and execution of a remotely executing program by requesting a beacon packet. When the remote computer is sending the packets, the receiving/logging computer must be a trusted computer (hardware,software, OS) so that the receiving of packets remains consistent. To detect a fault in a remote system, every packet must arrive safely, and any interrupts during the logging must be handled or the inconsistencies will result in an inaccurate outcome. The AVM does not require trusted hardware and can be used over wide-area networks.

'''Cheat Detection:''' Cheating in games or any specific modification in a program can be either scanned[[#References | [3][4]]] for or prevented[[#References | [5][6]]] by certain programs. The issue with these scanning and preventative software is the knowledge/awareness of specific cheats or situations that the software can handle. An AVM is designed to counter any kind of general cheat.

'''Integrity Violations:''' This refers how the consistency of normal/expected operations of an execution does not equal to that of the host/reference (Trusted) execution, hence a violation has occurred.

- The word "node" is used to refer to a computer or server in order to represent the interactions between one computer and another, or a computer and a server.

==Research problem==

What is the research problem being addressed by the paper? How does this problem relate to past related work?
**Possible alternative for the first part :

The research presented in this paper tries to tackle a problem that has haunted computer scientists for a long time. How can you be sure that the software running on a remote machine is working correctly or as intended. Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a trust relation between users and a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done would be independent of the node and only dependent on the intended software. Let's say, that node A interacts with node B with execution exe1 and node A interacts with node C also with ex1, but node C has been modified and respond with exe2. Thus, we can assume that the respond of B and C will be different. Being able to prove that the node C has been modified without any doubt is the purpose of this paper.
***Let me know what you think about it. I removed the redundant part, and I think made it clearer and more concise. [[User:Jbaubin|Jbaubin]]

** looks good to me, we'll put this part into the final essay instead of mine below --[[User:Mchou2|Mchou2]] 20:03, 22 November 2010 (UTC)

/// omit

Cloud computing, online multi-player games, and other online services such as auctions are only a few examples that rely on a system of trust between users and a host. These different examples must have a certain amount of trust between the interactions of one user and another, as well as the user interacting with a host. When a node (user or computer) expects some sort of result or feedback from another node, they would hope that that interaction being done with node A is the same it would be done with another node, node B. Let's say for example that node A interacts with node B with execution exe1, now when node A and B interact with node C, they would both expect to interact with execution exe1, but what happens if node C interacts differently and executes with exe2, then it would be beneficial to be notified of this difference. The previous explanation might not seem too relevant without some examples, such as; Node A is playing a game with node B, the game executed on node B is the same as on A, now when node A plays with node C, node C is executing the same operations as node A plus a cheating program; when node A buys some products from node B's server, the server processes the order and then deletes node A's sensitive information, denoted by execution 1, now when node A buys from node C's server, the order is processed as well as the sensitive information that node A has provided is also rerouted to another server so that it can be used without permission. These are only a few examples where the operations in an execution is necessary to be logged and verified. The problem that is trying to be handled here is to create a procedure that can be done so that a node can be known as accountable, and to log the operations in an execution to provide evidence of these faults done by a node.

////

Previous work that has been done in efforts to prevent or detect integrity violations can be separated into different categories of operations. The first would be Cheat Detection, where in many different games there are cheats that users use to usually create benefits for themselves that was not intended by the original game.[[#References |[4]]] These detectors are not dynamic, in the sense that they do not actually detect whether a cheat is being used, more so they are checking if there is a cheating operation that they have logged before, being operated on the user's system. For example, if there was a known cheating program named aimbot.exe that can be run in the background of a game such as CounterStrike, and the PunkBuster system that was implemented on the user's system had the aimbot.exe program already logged as a cheating program from the developers, the PunkBuster program might notify the current game servers of this or even prevent the user from playing any games until the aimbot.exe operation is no longer running.

Accountability is another important problem that many have already worked on. The main goal of an accountable system is to be able to determine without a doubt that node is faulty and can prove it with solid evidence. It can also be used to defend a node when threatened with false accusation. Numerous systems already use accountability in their system, but they were mostly all linked to specific applications, where a point of reference must be used to compare. As example PeerReview[[#References |[7]]], which is a system closely related to what the research team have worked on, must be implemented into the application which makes it less portable and cannot be implemented as easily as an AVM. PeerReview verifies the inbound and outbound packets and can see if the software is running as intended.

Another problem that is related to the paper is remote fault detection in a distributed system. How can we determine if a remote node is running the code correctly or if the machine itself is working as intended. Network activity is a common solution to this problem, as they look at the inbound and outbound of the node. This can let them know how the software is operating, or in the case of AVM how the whole virtual machine is working. Gridcop[[#References |[8]]] is another example that inspects a small number of packets periodically. Another way of determining the fault remotely is to use a trusted node, where it can tell immediately if a fault occurs or a modification is made where it should not have been made.

-and anything else you would to add or modify, or leave a note in the discussion sections if you want me to relook or change something. --[[User:Mchou2|Mchou2]] 20:10, 21 November 2010 (UTC)

The problem of logging and auditing the processes of an execution of a specific node (computer) is greatly dependent on the work done for deterministic replay. Deterministic replay programs can create a log file that can be used to replay the operations done for some execution that occurs on a node. Replaying the operations done on the node can show what the node was doing, and this would seem like it is sufficient in finding out whether a node was causing integrity violations or not. The concept of snap-shoting/recording the operations is not the issue with deterministic replay, it is the fact that the data being outputted into the replay may be tampered with by the node itself so that it generates optimal results in replay. By faking the results of the operations, the auditing computer will falsely believe that the tested computer is running all operations as normal. The logging operations done by these recording programs can be directly related to the work needed to detect integrity violations.

==Contribution==

What are the research contribution(s) of this work? Specifically, what are the key research results, and what do they mean? (What was implemented? Why is it any better than what came before?)

The accountable virtual machine (AVM), that was proposed in this essay, most useful contribution was the implementation of the accountable virtual machine monitor (AVMM). It is what allows for the fault checking of virtual machines in a cloud computing environment. The AVMM can be broken down into different parts: the virtual machine monitor (VMM), the temper-evident log, and auditing mechanisms. The VMM is based off the VMM found in VMWare Workstation 6.5.1, the temper-evident log was adapted from code in PeerReview[], and the audit tools were built up from scratch.

The accountable virtual machine monitor relies on four assumptions:

1. All transmitted messages are received, if retransmitted sufficiently often.

2. Machines and Users have access to a has function that is pre-image resistant, second pre-image resistant, and collision resistant.

3. All parties have a certified keypair, that can be used to sign messages.

4. To audit a log, the user has a reference copy of the VM used.
The job of the AVMM is to record all incoming and outgoing messages to tamper-evident log.
and enough info of the execution to enable deterministic replay.

The AVMM must record nondeterministic inputs (such as hardware interrupts), because the input is asynchronous, the exact timing of input must be recorded, so that the inputs can be injected at the same points during replay. Wall-clock time is not accurate enough for this recording, so the AVMM must use a combination of instruction pointer, branch counter, and, possibly, additional registers. Not all inputs have to be recorded this way (software interrupts), because, they send requests to the AVM, which will be issued again during replay.

Two parallel streams appear in the tamper-evident log: message exchanges and nondeterministic inputs.
It is important for the AVMM to detect inconsistencies between the user's log and the machine's log (in case of foul play), so the AVMM simply cross-references messages and inputs during replay, thus, easily detecting any discrepancies.

The AVMM periodically takes snapshots of the AVM's current state, this facilitates fine-grain audits for the user, but it also increases overhead. The overhead is lowered slightly by the snapshots being incremental (only save the state that has been changed since the last snapshot). The user can authenticate the snapshot using a hash tree of the state (generated by the AVMM), the AVMM updates the hash tree after each snapshot.

'''Tamper-Evident Log'''

The log is made up of hash code entries.
Each log entry in form e = (s,t,c,h)
s = monotonically increasing sequence number
t = type
c = data of the type
h = hash value

The hash value is calculated by: h = H(hi-1 || s || t || H(c))
H() is a hash function.
|| stands for concatenation

Each message sent gets signed with a private key, when the AVMM logs the messages with the signature attached but removes it before sending it to the AVM. To ensure nonrepudiation, an authenticator is attached to each outgoing message.

To detect when a message is dropped, each party sends an acknowledgement for each message they receive. If an acknowledgement is not received the message is resent a few times, if the user stops receiving messages, then the machine is presumed to of failed.

To preform a log check, the user retrieves a pair of authenticators, then challenges the machine to produce the log segment between the two. The log is computationally infeasible to edit without breaking the hash chain, thus, if the log has been tampered with the hash chain will be different and the user will notified of the tampering.

'''Auditing Mechanism'''

From VVM's perspective all things are deterministic.

To preform a audit the user:

1. obtains a segment of the machine's log and the authenticators

2. downloads a snapshot of the AVM at the beginning of the segment

3. replays the entire segment, starting from the snapshot, to verify the events in the log are the correct execution of the software.

The user can verify the execution of software through three different methods: Verifying the log, snapshot, and execution.

When the user wants to verify a log segment, the user retrieves the authenticators from the machine with the sequence numbers in the range of the log segment. The user then downloads the log segment from the machine, and, starting with the most recent snapshot before the log segment and ending with the most recent snapshot before the end of the log segment. The user then check the authenticators for tampering. If this step proceeds, the user can assume the log segment executed properly. If the machine is faulty, the segment will be unavaible to download or may return a corrupted log segment. This can be used to convince a third party of the fault.

When the user wants to verify the snapshot, the user obtains a snapshot of the AVM's state at the beginning of the log segment. The user then downloads a snapshot from the machine and the AVMM recomputes the hash tree. The new hash tree is compared to the hash tree contained in the orignal log segment. If any discrepancies are detected, the user can use this to convince a third party of machine's fault.

In order for the user to verifying the execution of a log segment, the user needs three inputs: the log segment, the snapshot, and the public keys of the machine and any users of the machine. The auditing tool performs two checks on the log segment, a syntactic check (determines if log is well-formed), and a semantic check (determines if the information in the log shows the correct execution of the machine).

The syntactic check checks whether all log entries are in the proper format, the signatures in each message and acknowledgement, if each message was acknowledged, and the sequence of sent and received messages is correct when compared to the sequence of messages that enter and exit the AVM.

The semantic check creates a local VM that will execute the machine's log segment, the VM is initialized with a snapshot from the machine if possible. The local VM then runs the log segment and the data is recorded. The auditing tool then checks the log segments, inputs, outputs, and verification of snapshot hashes of the replayed execution against the original log. If any discrepancies are detected then the fault is reported and can be used as evidence as fault.

==Critique==

What is good and not-so-good about this paper? You may discuss both the style and content; be sure to ground your discussion with specific references. Simple assertions that something is good or bad is not enough - you must explain why.

// first part of my writing; this is just part1 [[User:Sschnei1|Sschnei1]] 00:35, 24 November 2010 (UTC)

For the comprehension of the reader, it is important of a paper/article/essay to have a good overview/layout. The introduction clearly describes what the reader has to expect in the following pages, especially what problems are addressed and how they are solved.

This paper gives multiple examples about advantages and disadvantages in an AVM. A good example is "Cheat Detection". Cheaters use programs to go around the original game code to gain an major advantage over other players. Since an AVM is generic in cheat detection it has a wider support for detecting cheats than most of the other cheat detection algorithms. The logs give the game the function to replay the game. Thus, players using AVM can see the way other players play by replaying the game with the player's log.

The negative side is that the player might have to suffer from the AVM. Everything is being logged and stored on the hard drive, which takes a lot amount of space. In the example in the paper it is 148mb per hour after compression. This reduces the fps. Additionally, the connection to the AVM increases the ping time to the server.

==References==

You will almost certainly have to refer to other resources; please cite these resources in the style of citation of the papers assigned (inlined numbered references). Place your bibliographic entries in this section.

[1] B. Cully, G. Lefebvre, D. Meyer, M. Feeley, N. Hutchinson, and
A. Warfield. Remus: High availability via asynchronous virtual
machine replication. In Proceedings of the USENIX Symposium
on Networked Systems Design and Implementation (NSDI), Apr.
2008.

[2] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

[3] G. Hoglund. 4.5 million copies of EULA-compliant spyware.
http://www.rootkit.com/blog.php?newsid=358.

[4] PunkBuster web site. http://www.evenbalance.com/.

[5] N. E. Baughman, M. Liberatore, and B. N. Levine. Cheat-proof
playout for centralized and peer-to-peer gaming. IEEE/ACM
Transactions on Networking (ToN), 15(1):1–13, Feb. 2007.

[6] C. M¨onch, G. Grimen, and R. Midtstraum. Protecting online
games against cheating. In Proceedings of the Workshop on Network
and Systems Support for Games (NetGames), Oct. 2006.

[7] A. Haeberlen, P. Kuznetsov, and P. Druschel. PeerReview: Practical
accountability for distributed systems. In Proceedings of
the ACM Symposium on Operating Systems Principles (SOSP),Oct. 2007.

[8] S. Yang, A. R. Butt, Y. C. Hu, and S. P. Midkiff. Trust but
verify: Monitoring remotely executing programs for progress
and correctness. In Proceedings of the ACM SIGPLAN Annual
Symposium on Principles and Practice of Parallel Programming
(PPoPP), June 2005.

=Discussion=
We can use this area to discuss or leave notes on general ideas or whatever you want to write here.

-The current due date posted on the site for this essay is November 25th --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

-I think that since we are given the headings to this article, we can easily choose what parts each member would like to work on, obviously since there are more members than parts, multiple members will have to work on the same parts or can work on all parts, I guess it's really up to you. I know that most people have a lot of projects coming up so let's try to get this done asap, or at least bit by bit so it's not something we have to worry too much about. --[[User:Mchou2|Mchou2]] 05:18, 19 November 2010 (UTC)

- I would like to do the Contribution or Critique. -- [[User:Sschnei1|Sschnei1]] 02:40, 20 November 2010 (UTC)

- I can either work on Background Concepts, or Research problem. -[[User:Jbaubin|Jbaubin]]

- I'm not sure whether the background concepts should be in point form or a paragraph, and whether it needs to be very long or not, but I shall work on both background concepts and research problem with you Jbaubin. --[[User:Mchou2|Mchou2]] 18:11, 21 November 2010 (UTC)

-Sounds good, and As i was going to post what I had for research problem, I just saw you posted a big chunk of it. I'll be out for a while, but tonight I'll take a serious look at what you write and add what I had written. - [[User:Jbaubin|Jbaubin]]

- Sorry I didn't write anything yet to Critique. I'm making my notes and will post something tonight or tomorrow. -- [[User:Sschnei1|Sschnei1]] 14:50, 22 November 2010 (UTC)

- I have started work on the contribution section. I'll have something up today or tomorrow. --[[User:Hirving|Hirving]] 19:55, 23 November 2010 (UTC)

-if anyone has information that they are working on they can just post it up and at least others can look at it and maybe build up stuff on it, and I'm sure everyone is aware of the extension that we got also, but let's try to finish this in the next few days --[[User:Mchou2|Mchou2]] 20:43, 23 November 2010 (UTC)

- I agree with finishing it in the next few days. Then we have more time to focus on other courses like 3004. I will post something later that night. -- [[User:Sschnei1|Sschnei1]] 21:29, 23 November 2010 (UTC)

Talk:COMP 3000 Essay 2 2010 Question 4

2010-11-23T19:55:51Z

Hirving: /* Discussion */

Talk:COMP 3000 Essay 2 2010 Question 4

2010-11-15T15:04:15Z

Hirving: /* Group Essay 2 */

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-14T19:59:12Z

Hirving: /* Log */

== Log ==
'''Suggestion:''' Let us maintain our edits here instead of on littering the main page with our names. Also please do not edit without writing to the log so that we know who has done what and when.

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

Moved around some info for clarity. Everyone should post your interpretation of the question in simplest possible English so we`re on the same page (as someone, maybe me, seems to have the wrong idea about what we`re trying to talk about)
More moving for clarity. added an essay outline at bottom (feel free to change)
filled in the outline somewhat added questions to the outline for everyone to think on.--[[User:Rannath|Rannath]]

First Draft for essay. Please modify and add on. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

Edited Scheduling Priorities and rewrote some areas to provide a better paragraph structure. --[[User:Spanke|Shane]] 15:25, 13 October 2010 (UTC)

Added to the memory management section. --[[User:Hirving|Hirving]] 21:42, 13 October 2010 (UTC)

Edited Scalable Threads Problems. Also did a little re-arrangement. --[[User:Gautam|Gautam]] 01:03, 14 October 2010 (UTC)

Answered Essay Questions in Discussion. --[[User:Spanke|Shane]] 01:25, 13 October 2010 (UTC)

I posted Main point 2. It is nearing completion, --[[User:Praubic|Praubic]] 17:43, 14 October 2010 (UTC)

Minor edits in Scheduler part. --[[User:Gautam|Gautam]] 19:09, 14 October 2010 (UTC)

Added a paragraph about locks to memory section. --[[User:Hirving|Hirving]] 19:36, 14 October 2010 (UTC)

Proof read and edited article for clarity and grammar. (commas are nice) --[[User:Hirving|Hirving]] 19:57, 14 October 2010 (UTC)

 <Add your future activities here>

== The Question ==
'''Original: '''
How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

'''Rannath: '''
The question seems to be about number and scalability of threads not the gross mechanics.

To be more clear: we can limit ourselves from the thread implementations to the thread scalability... ignore the stuff that required for all threads, unless its required for many threads. (I didn't find any implementations that required hardware)

I would also argue that since OSs have to run on multiple hardwares one cannot guarantee that unique/rare hardware bits will be there. While we can talk about hardware we should limit it to a mention at most. OR we could mention prospective hardware that could help out, but is not yet standard. It depends on whether we want to do "as it is" or "as it might be"

utility of such massively scalable thread implementations. I took this as: what functionality (of single strings) does one have to give up to make threads scalable.

'''Gautam: '''
I think the hardware is as relevant as the software. Not all things can be done in software and hardware support is an important factor in most of the solutions to many problems that OS face. My take.

'''Henry: '''
Since the question is about the system as a whole, I think the answer should include both software and hardware support for large amounts of threads. The questions revolves around how a system can handle millions of threads and what are the major factors that allow the system to do it. Also, the last part of the question seems to ask what this amount of threads allows a process to do.

'''Shane: '''
In response to the above's idea on the last part of the question, I would argue that it would enable fast execution because all threads that receive a cache miss would be picked up by the other threads so long as there was enough resources. Also the use of more threads would help synchronize the cache (through sharing) so that it would not miss. Of course this would be if they were assigned to the same task, you cannot sync threads running different applications it just wouldn't make sense. The only issue with this idea is the software must support this number.

'''vG: '''
We should talk about type of relationship models (1:1 N:M N:N and so on) also talk about the application vs hardware multi-threading within single processor.

'''Paul: '''
I discussed Main Point 2 and how UMS threading is stretched onto multiple cores. Design that involves multiple processors differs from single proc comps so hardware definitely plays significant role here.

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek <support.tamiltreasure@gmail.com>

Shane Panke <shanepanke@msn.com>

Henry Irving <sens.henry@gmail.com>

Paul Raubic <paul_raubic@hotmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: --[[User:Rannath|Rannath]]

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

== Facts We have ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far we have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere
# least number (none if at all possible) of context switches per-thread - ''5''
# use of a "thread pool" - ''3''
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space. --[[User:Rannath|Rannath]]

Multi-threading is a term used to describe:

* A facility provided by the operating system that enables an application to create threads of execution within a process
* Applications whose architecture takes advantage of the multi-threading provided by the operating system
[[vG]]
----
These are all related ideas.

Ok, since we are discussing design choices maybe we could also elaborate on the two major types of threads. Here, I already wrote a few lines, source can be found in citation section:

''Fibers (user mode threads) provide very quick and efficient switching because there is no need for a system call and kernel is oblivious to a switch - allows for millions of user mode threads. ISSUES: Blocking system calls disables all other fibers.
On the other hand managing threads through the kernel requires context switch (between user and kernel mode) on creation and removal of a thread therefore programs with prodigious number of threads would suffer huge performance hits.--[[User:Praubic|Praubic]] 18:05, 10 October 2010 (UTC)''

User-mode scheduling (UMS) is a light-weight mechanism that applications can use to schedule their own threads. The ability to switch between threads in user mode makes UMS more efficient than thread pools for short-duration work items that require few system calls. [[Paul]]

One implementation of UMS is: combination of N:N and N:M, where the N:N relationship reveals N false processors to the user-space so the user can deal with scheduling on their own. ''5'' -[[Rannath]]

----

I would scrap the first two below, at most mention them...

#time-division multiplexing
#threads vs processes
#I/O Scheduling -[[vG]]

Splitting this off because I don't think it's technically part of the answer 
Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]

----
Things that we '''need''' to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
This is a '''need''' section 4 below is not '''needed''' 
(A)Design Decisions
1. Type of threading (1:1 1:N M:N)
2. Signal handling - we might be able to leave this out as it seems some "light weight" threads use no signals
3. Synchronisation
4. Memory Handling
5. Scheduling Priorities (context switching and how it affects the CPU threading process)[[Paul]]
----

Things we might want also to cover in the essay (non-essentials here): --[[User:Rannath|Rannath]] 04:43, 10 October 2010 (UTC) 
(A)Design Decisions
1. Brief History of threading
2. examples of attempts at getting absurd numbers of threads (failures)
3. other types of threading, including heavy weight and processes
4. Examples of systems that require many threads such as mainframe servers or banking client processing.--[[User:Praubic|Praubic]] 17:34, 11 October 2010 (UTC)

Here is an example of a design: (the topic asks for key design choices here is one)

Capriccio is a specific design for scalable user level threads. They are distinct from most designs by being independent of event based mechanisms as well as kernel thread models. They are very good choice for internet servers and this implementations could easily support 100,000 threads. They are characterized by high scalability, efficient stack management and scheduling based on resource usage however the performance is not comparable to event-based systems.--[[User:Praubic|Praubic]] 13:32, 12 October 2010 (UTC)

(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Essay Outline ==

#Thesis is an answer to the question so... that's the first step, or the last step, we can always present our info and make our thesis match the info.
#List all questions and points we have about the topic

Questions:
# What makes threads non-scalable? List the problems
# What utility do some scalable implementations lack? Why?
# Just how scalable does a full utility implementation get?

Answers:
# Memory Usage, Context Switching. Consider using a thread pool.
# Signals, portability(maybe) both add overhead which would slow down threads
# If using thread pools, the scalability is then limited to the number of threads in the pool
----

Intro (fill in info)
# Thesis
# main topics

----

Body (made of many main points)

Main Point 1 -[[Rannath]] 
- efficient thread creation/destruction is more scalable 
-- NPTL's improvements over LinuxThreads- primarily due to lower overhead of creation/destruction ''1''

Main Point 2 -[[Rannath]] 
- UMS & user-space threads are more scalable - maybe 
-- context switches are costly ''From class'' 
-- blocking locks have lower latency when twinned with a user space scheduler ''8''

Ok for point 2 -> I posted a draft on the essay page but Im not certain as to whether i should talk about fibers since they are also functioning on user space but theyre not UMS. --[[User:Praubic|Praubic]] 00:18, 14 October 2010 (UTC)

Main Point 3 
- Certain bottleneck appear in scaled implementations, removing these improves scalability. 
-- "False cache-line sharing" ''14'' 
-- xtime lock to a lockless lock ''14''

Main Point 3.5 
Fine-Grain over course-grain 
-- "Big Kernel Lock" ''14'' 
-- dcache_lock ''14''

Link the Main points to the thesis

----

Conclusion
# restate info
# affirmation of thesis

Here is the first paragraph that I attempted. Please feel free to change or even delete it from here.

A thread is an independent task that executes in the same address space as other threads within a single process while sharing data synchronously. Threads require less system resources then concurrent cooperating processes and start much easier therefore there may exist millions of them in a single process. The two major types of threads are kernel and user-mode. Kernel threads are usually considered more heavy and designs that involve them are not very scalable User threads on the other hand are mapped to kernel threads by the threads library such as libpthreads. and there are a few designs that incorporate it mainly Fibers and UMS (User Mode Scheudling) which allow for very high scalability. UMS threads have their own context and resources however the ability to switch in the user mode makes them more efficient (depending on application) than Thread Pools which are yet another mechanism that allows for high scalability.
--[[User:Praubic|Praubic]] 19:04, 12 October 2010 (UTC)

we can add this for intro paragraph:

How is it possible for systems to supports millions of threads or more within a single process?

It is possible for systems to supports millions of threads or more within a single processor, it has the ability to switch execution resource between threads, thus making a concurrent execution. Concurrency is when multiple threads stays on the ques for switching but incapable of running at the same time but it has the ability to make it look like they are running at same time due to the speed they switch. [[vG]] You stated it is possible you did not state how, or rather did not make it clear. The below should be a better interpretation. --[[User:Spanke|Shane]]

Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at.

Added more == vG

Process is known as an instance of a program running in a computer which has its own resources such as address space, files, I/O devices and threads on the other hand thread is similar to a process but it but it does a single operation within the process. Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at. [[vG]]

----
I suggest that we start filling out the main points of the essay. We can discuss the intricacies as we go along. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

== Sources ==

# Short history of threads in Linux and new implementation of them. [http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ] [[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)
# This paper discusses the design choices [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf Native POSIX Threads] [[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)
# lightweight threads vs kernel threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf PicoThreads: Lightweight Threads in Java] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# [http://eigenclass.org/http://homeostasis.scs.carleton.ca/wiki/index.php?title=Talk:COMP_3000_Essay_1_2010_Question_7&action=edit&section=7hiki/lightweight-threads-with-lwt Eigenclass Comparing lightweight threads] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# A lightwight thread implementation for Unix [http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf Implementing light weight threads] --[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC) [[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC)
#Not in this group, but I thought that this paper was excellent: [http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf Qthreads: An API for Programming with Millions of Lightweight Threads]
# Difference between single and multi threading [http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process] [[vG]]
# [http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler] --[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)
# Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading] --[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)
# This site provides in-depth info about threads, threads-pooling, scheduling: http://msdn.microsoft.com/en-us/library/ms684841(VS.85).aspx [[Paul]]
# Here is another site that outlines THREAD designs and techniques: http://people.csail.mit.edu/rinard/osnotes/h2.html [[Paul]]
# [http://www.cosc.brocku.ca/Offerings/4P13/slides/threads.ppt Interesting presentation: really worth checking out] [[Paul]]
# KERNEL vs USERMODE http://www.wordiq.com/definition/Thread_(computer_science)--[[User:Praubic|Praubic]] 18:06, 10 October 2010 (UTC)
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 Scalability in linux]
# [http://hillside.net/plop/2007/papers/PLoP2007_Ahluwalia.pdf This has something to do with our question...]
# [http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx Scheduling Priorities (Windows)], Microsoft (23 September 2010) --[[User:Spanke|Shane]]
# [http://www.novell.com/coolsolutions/feature/14878.html Linux Scheduling Priorities Explained], Novell (11 October 2005) --[[User:Spanke|Shane]]
# [http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/ Inside the Linux 2.6 Completely Fair Scheduler], IBM (15 December 2009) --[[User:Spanke|Shane]]
#http://www.megaupload.com/?d=R4VMK3A1 (PDF Document on Multithreading) [[vG]]
# [http://www.linuxjournal.com/article/1363 what is multithreading?] [[vG]]
# [http://en.wikipedia.org/wiki/Thread_%28computer_science%29 type of threadings and multithreading in general] [[vG]]

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-14T19:57:36Z

Hirving: /* Log */

== Log ==
'''Suggestion:''' Let us maintain our edits here instead of on littering the main page with our names. Also please do not edit without writing to the log so that we know who has done what and when.

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

Moved around some info for clarity. Everyone should post your interpretation of the question in simplest possible English so we`re on the same page (as someone, maybe me, seems to have the wrong idea about what we`re trying to talk about)
More moving for clarity. added an essay outline at bottom (feel free to change)
filled in the outline somewhat added questions to the outline for everyone to think on.--[[User:Rannath|Rannath]]

First Draft for essay. Please modify and add on. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

Edited Scheduling Priorities and rewrote some areas to provide a better paragraph structure. --[[User:Spanke|Shane]] 15:25, 13 October 2010 (UTC)

Added to the memory management section. --[[User:Hirving|Hirving]] 21:42, 13 October 2010 (UTC)

Edited Scalable Threads Problems. Also did a little re-arrangement. --[[User:Gautam|Gautam]] 01:03, 14 October 2010 (UTC)

Answered Essay Questions in Discussion. --[[User:Spanke|Shane]] 01:25, 13 October 2010 (UTC)

I posted Main point 2. It is nearing completion, --[[User:Praubic|Praubic]] 17:43, 14 October 2010 (UTC)

Minor edits in Scheduler part. --[[User:Gautam|Gautam]] 19:09, 14 October 2010 (UTC)

Added a paragraph about locks to memory section. --[[User:Hirving|Hirving]] 19:36, 14 October 2010 (UTC)

Proof read and edited article for clarity. (commas are nice) --[[User:Hirving|Hirving]] 19:57, 14 October 2010 (UTC)

 <Add your future activities here>

== The Question ==
'''Original: '''
How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

'''Rannath: '''
The question seems to be about number and scalability of threads not the gross mechanics.

To be more clear: we can limit ourselves from the thread implementations to the thread scalability... ignore the stuff that required for all threads, unless its required for many threads. (I didn't find any implementations that required hardware)

I would also argue that since OSs have to run on multiple hardwares one cannot guarantee that unique/rare hardware bits will be there. While we can talk about hardware we should limit it to a mention at most. OR we could mention prospective hardware that could help out, but is not yet standard. It depends on whether we want to do "as it is" or "as it might be"

utility of such massively scalable thread implementations. I took this as: what functionality (of single strings) does one have to give up to make threads scalable.

'''Gautam: '''
I think the hardware is as relevant as the software. Not all things can be done in software and hardware support is an important factor in most of the solutions to many problems that OS face. My take.

'''Henry: '''
Since the question is about the system as a whole, I think the answer should include both software and hardware support for large amounts of threads. The questions revolves around how a system can handle millions of threads and what are the major factors that allow the system to do it. Also, the last part of the question seems to ask what this amount of threads allows a process to do.

'''Shane: '''
In response to the above's idea on the last part of the question, I would argue that it would enable fast execution because all threads that receive a cache miss would be picked up by the other threads so long as there was enough resources. Also the use of more threads would help synchronize the cache (through sharing) so that it would not miss. Of course this would be if they were assigned to the same task, you cannot sync threads running different applications it just wouldn't make sense. The only issue with this idea is the software must support this number.

'''vG: '''
We should talk about type of relationship models (1:1 N:M N:N and so on) also talk about the application vs hardware multi-threading within single processor.

'''Paul: '''
I discussed Main Point 2 and how UMS threading is stretched onto multiple cores. Design that involves multiple processors differs from single proc comps so hardware definitely plays significant role here.

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek <support.tamiltreasure@gmail.com>

Shane Panke <shanepanke@msn.com>

Henry Irving <sens.henry@gmail.com>

Paul Raubic <paul_raubic@hotmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: --[[User:Rannath|Rannath]]

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

== Facts We have ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far we have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere
# least number (none if at all possible) of context switches per-thread - ''5''
# use of a "thread pool" - ''3''
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space. --[[User:Rannath|Rannath]]

Multi-threading is a term used to describe:

* A facility provided by the operating system that enables an application to create threads of execution within a process
* Applications whose architecture takes advantage of the multi-threading provided by the operating system
[[vG]]
----
These are all related ideas.

Ok, since we are discussing design choices maybe we could also elaborate on the two major types of threads. Here, I already wrote a few lines, source can be found in citation section:

''Fibers (user mode threads) provide very quick and efficient switching because there is no need for a system call and kernel is oblivious to a switch - allows for millions of user mode threads. ISSUES: Blocking system calls disables all other fibers.
On the other hand managing threads through the kernel requires context switch (between user and kernel mode) on creation and removal of a thread therefore programs with prodigious number of threads would suffer huge performance hits.--[[User:Praubic|Praubic]] 18:05, 10 October 2010 (UTC)''

User-mode scheduling (UMS) is a light-weight mechanism that applications can use to schedule their own threads. The ability to switch between threads in user mode makes UMS more efficient than thread pools for short-duration work items that require few system calls. [[Paul]]

One implementation of UMS is: combination of N:N and N:M, where the N:N relationship reveals N false processors to the user-space so the user can deal with scheduling on their own. ''5'' -[[Rannath]]

----

I would scrap the first two below, at most mention them...

#time-division multiplexing
#threads vs processes
#I/O Scheduling -[[vG]]

Splitting this off because I don't think it's technically part of the answer 
Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]

----
Things that we '''need''' to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
This is a '''need''' section 4 below is not '''needed''' 
(A)Design Decisions
1. Type of threading (1:1 1:N M:N)
2. Signal handling - we might be able to leave this out as it seems some "light weight" threads use no signals
3. Synchronisation
4. Memory Handling
5. Scheduling Priorities (context switching and how it affects the CPU threading process)[[Paul]]
----

Things we might want also to cover in the essay (non-essentials here): --[[User:Rannath|Rannath]] 04:43, 10 October 2010 (UTC) 
(A)Design Decisions
1. Brief History of threading
2. examples of attempts at getting absurd numbers of threads (failures)
3. other types of threading, including heavy weight and processes
4. Examples of systems that require many threads such as mainframe servers or banking client processing.--[[User:Praubic|Praubic]] 17:34, 11 October 2010 (UTC)

Here is an example of a design: (the topic asks for key design choices here is one)

Capriccio is a specific design for scalable user level threads. They are distinct from most designs by being independent of event based mechanisms as well as kernel thread models. They are very good choice for internet servers and this implementations could easily support 100,000 threads. They are characterized by high scalability, efficient stack management and scheduling based on resource usage however the performance is not comparable to event-based systems.--[[User:Praubic|Praubic]] 13:32, 12 October 2010 (UTC)

(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Essay Outline ==

#Thesis is an answer to the question so... that's the first step, or the last step, we can always present our info and make our thesis match the info.
#List all questions and points we have about the topic

Questions:
# What makes threads non-scalable? List the problems
# What utility do some scalable implementations lack? Why?
# Just how scalable does a full utility implementation get?

Answers:
# Memory Usage, Context Switching. Consider using a thread pool.
# Signals, portability(maybe) both add overhead which would slow down threads
# If using thread pools, the scalability is then limited to the number of threads in the pool
----

Intro (fill in info)
# Thesis
# main topics

----

Body (made of many main points)

Main Point 1 -[[Rannath]] 
- efficient thread creation/destruction is more scalable 
-- NPTL's improvements over LinuxThreads- primarily due to lower overhead of creation/destruction ''1''

Main Point 2 -[[Rannath]] 
- UMS & user-space threads are more scalable - maybe 
-- context switches are costly ''From class'' 
-- blocking locks have lower latency when twinned with a user space scheduler ''8''

Ok for point 2 -> I posted a draft on the essay page but Im not certain as to whether i should talk about fibers since they are also functioning on user space but theyre not UMS. --[[User:Praubic|Praubic]] 00:18, 14 October 2010 (UTC)

Main Point 3 
- Certain bottleneck appear in scaled implementations, removing these improves scalability. 
-- "False cache-line sharing" ''14'' 
-- xtime lock to a lockless lock ''14''

Main Point 3.5 
Fine-Grain over course-grain 
-- "Big Kernel Lock" ''14'' 
-- dcache_lock ''14''

Link the Main points to the thesis

----

Conclusion
# restate info
# affirmation of thesis

Here is the first paragraph that I attempted. Please feel free to change or even delete it from here.

A thread is an independent task that executes in the same address space as other threads within a single process while sharing data synchronously. Threads require less system resources then concurrent cooperating processes and start much easier therefore there may exist millions of them in a single process. The two major types of threads are kernel and user-mode. Kernel threads are usually considered more heavy and designs that involve them are not very scalable User threads on the other hand are mapped to kernel threads by the threads library such as libpthreads. and there are a few designs that incorporate it mainly Fibers and UMS (User Mode Scheudling) which allow for very high scalability. UMS threads have their own context and resources however the ability to switch in the user mode makes them more efficient (depending on application) than Thread Pools which are yet another mechanism that allows for high scalability.
--[[User:Praubic|Praubic]] 19:04, 12 October 2010 (UTC)

we can add this for intro paragraph:

How is it possible for systems to supports millions of threads or more within a single process?

It is possible for systems to supports millions of threads or more within a single processor, it has the ability to switch execution resource between threads, thus making a concurrent execution. Concurrency is when multiple threads stays on the ques for switching but incapable of running at the same time but it has the ability to make it look like they are running at same time due to the speed they switch. [[vG]] You stated it is possible you did not state how, or rather did not make it clear. The below should be a better interpretation. --[[User:Spanke|Shane]]

Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at.

Added more == vG

Process is known as an instance of a program running in a computer which has its own resources such as address space, files, I/O devices and threads on the other hand thread is similar to a process but it but it does a single operation within the process. Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at. [[vG]]

----
I suggest that we start filling out the main points of the essay. We can discuss the intricacies as we go along. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

== Sources ==

# Short history of threads in Linux and new implementation of them. [http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ] [[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)
# This paper discusses the design choices [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf Native POSIX Threads] [[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)
# lightweight threads vs kernel threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf PicoThreads: Lightweight Threads in Java] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# [http://eigenclass.org/http://homeostasis.scs.carleton.ca/wiki/index.php?title=Talk:COMP_3000_Essay_1_2010_Question_7&action=edit&section=7hiki/lightweight-threads-with-lwt Eigenclass Comparing lightweight threads] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# A lightwight thread implementation for Unix [http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf Implementing light weight threads] --[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC) [[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC)
#Not in this group, but I thought that this paper was excellent: [http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf Qthreads: An API for Programming with Millions of Lightweight Threads]
# Difference between single and multi threading [http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process] [[vG]]
# [http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler] --[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)
# Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading] --[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)
# This site provides in-depth info about threads, threads-pooling, scheduling: http://msdn.microsoft.com/en-us/library/ms684841(VS.85).aspx [[Paul]]
# Here is another site that outlines THREAD designs and techniques: http://people.csail.mit.edu/rinard/osnotes/h2.html [[Paul]]
# [http://www.cosc.brocku.ca/Offerings/4P13/slides/threads.ppt Interesting presentation: really worth checking out] [[Paul]]
# KERNEL vs USERMODE http://www.wordiq.com/definition/Thread_(computer_science)--[[User:Praubic|Praubic]] 18:06, 10 October 2010 (UTC)
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 Scalability in linux]
# [http://hillside.net/plop/2007/papers/PLoP2007_Ahluwalia.pdf This has something to do with our question...]
# [http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx Scheduling Priorities (Windows)], Microsoft (23 September 2010) --[[User:Spanke|Shane]]
# [http://www.novell.com/coolsolutions/feature/14878.html Linux Scheduling Priorities Explained], Novell (11 October 2005) --[[User:Spanke|Shane]]
# [http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/ Inside the Linux 2.6 Completely Fair Scheduler], IBM (15 December 2009) --[[User:Spanke|Shane]]
#http://www.megaupload.com/?d=R4VMK3A1 (PDF Document on Multithreading) [[vG]]
# [http://www.linuxjournal.com/article/1363 what is multithreading?] [[vG]]
# [http://en.wikipedia.org/wiki/Thread_%28computer_science%29 type of threadings and multithreading in general] [[vG]]

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-14T19:57:12Z

Hirving: /* Log */

== Log ==
'''Suggestion:''' Let us maintain our edits here instead of on littering the main page with our names. Also please do not edit without writing to the log so that we know who has done what and when.

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

Moved around some info for clarity. Everyone should post your interpretation of the question in simplest possible English so we`re on the same page (as someone, maybe me, seems to have the wrong idea about what we`re trying to talk about)
More moving for clarity. added an essay outline at bottom (feel free to change)
filled in the outline somewhat added questions to the outline for everyone to think on.--[[User:Rannath|Rannath]]

First Draft for essay. Please modify and add on. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

Edited Scheduling Priorities and rewrote some areas to provide a better paragraph structure. --[[User:Spanke|Shane]] 15:25, 13 October 2010 (UTC)

Added to the memory management section. --[[User:Hirving|Hirving]] 21:42, 13 October 2010 (UTC)

Edited Scalable Threads Problems. Also did a little re-arrangement. --[[User:Gautam|Gautam]] 01:03, 14 October 2010 (UTC)

Answered Essay Questions in Discussion. --[[User:Spanke|Shane]] 01:25, 13 October 2010 (UTC)

I posted Main point 2. It is nearing completion, --[[User:Praubic|Praubic]] 17:43, 14 October 2010 (UTC)

Minor edits in Scheduler part. --[[User:Gautam|Gautam]] 19:09, 14 October 2010 (UTC)

Added a paragraph about locks to memory section. --[[User:Hirving|Hirving]] 19:36, 14 October 2010 (UTC)

Proof read and edited for clarity. (commas are nice) --[[User:Hirving|Hirving]] 19:57, 14 October 2010 (UTC)

 <Add your future activities here>

== The Question ==
'''Original: '''
How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

'''Rannath: '''
The question seems to be about number and scalability of threads not the gross mechanics.

To be more clear: we can limit ourselves from the thread implementations to the thread scalability... ignore the stuff that required for all threads, unless its required for many threads. (I didn't find any implementations that required hardware)

I would also argue that since OSs have to run on multiple hardwares one cannot guarantee that unique/rare hardware bits will be there. While we can talk about hardware we should limit it to a mention at most. OR we could mention prospective hardware that could help out, but is not yet standard. It depends on whether we want to do "as it is" or "as it might be"

utility of such massively scalable thread implementations. I took this as: what functionality (of single strings) does one have to give up to make threads scalable.

'''Gautam: '''
I think the hardware is as relevant as the software. Not all things can be done in software and hardware support is an important factor in most of the solutions to many problems that OS face. My take.

'''Henry: '''
Since the question is about the system as a whole, I think the answer should include both software and hardware support for large amounts of threads. The questions revolves around how a system can handle millions of threads and what are the major factors that allow the system to do it. Also, the last part of the question seems to ask what this amount of threads allows a process to do.

'''Shane: '''
In response to the above's idea on the last part of the question, I would argue that it would enable fast execution because all threads that receive a cache miss would be picked up by the other threads so long as there was enough resources. Also the use of more threads would help synchronize the cache (through sharing) so that it would not miss. Of course this would be if they were assigned to the same task, you cannot sync threads running different applications it just wouldn't make sense. The only issue with this idea is the software must support this number.

'''vG: '''
We should talk about type of relationship models (1:1 N:M N:N and so on) also talk about the application vs hardware multi-threading within single processor.

'''Paul: '''
I discussed Main Point 2 and how UMS threading is stretched onto multiple cores. Design that involves multiple processors differs from single proc comps so hardware definitely plays significant role here.

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek <support.tamiltreasure@gmail.com>

Shane Panke <shanepanke@msn.com>

Henry Irving <sens.henry@gmail.com>

Paul Raubic <paul_raubic@hotmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: --[[User:Rannath|Rannath]]

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

== Facts We have ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far we have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere
# least number (none if at all possible) of context switches per-thread - ''5''
# use of a "thread pool" - ''3''
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space. --[[User:Rannath|Rannath]]

Multi-threading is a term used to describe:

* A facility provided by the operating system that enables an application to create threads of execution within a process
* Applications whose architecture takes advantage of the multi-threading provided by the operating system
[[vG]]
----
These are all related ideas.

Ok, since we are discussing design choices maybe we could also elaborate on the two major types of threads. Here, I already wrote a few lines, source can be found in citation section:

''Fibers (user mode threads) provide very quick and efficient switching because there is no need for a system call and kernel is oblivious to a switch - allows for millions of user mode threads. ISSUES: Blocking system calls disables all other fibers.
On the other hand managing threads through the kernel requires context switch (between user and kernel mode) on creation and removal of a thread therefore programs with prodigious number of threads would suffer huge performance hits.--[[User:Praubic|Praubic]] 18:05, 10 October 2010 (UTC)''

User-mode scheduling (UMS) is a light-weight mechanism that applications can use to schedule their own threads. The ability to switch between threads in user mode makes UMS more efficient than thread pools for short-duration work items that require few system calls. [[Paul]]

One implementation of UMS is: combination of N:N and N:M, where the N:N relationship reveals N false processors to the user-space so the user can deal with scheduling on their own. ''5'' -[[Rannath]]

----

I would scrap the first two below, at most mention them...

#time-division multiplexing
#threads vs processes
#I/O Scheduling -[[vG]]

Splitting this off because I don't think it's technically part of the answer 
Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]

----
Things that we '''need''' to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
This is a '''need''' section 4 below is not '''needed''' 
(A)Design Decisions
1. Type of threading (1:1 1:N M:N)
2. Signal handling - we might be able to leave this out as it seems some "light weight" threads use no signals
3. Synchronisation
4. Memory Handling
5. Scheduling Priorities (context switching and how it affects the CPU threading process)[[Paul]]
----

Things we might want also to cover in the essay (non-essentials here): --[[User:Rannath|Rannath]] 04:43, 10 October 2010 (UTC) 
(A)Design Decisions
1. Brief History of threading
2. examples of attempts at getting absurd numbers of threads (failures)
3. other types of threading, including heavy weight and processes
4. Examples of systems that require many threads such as mainframe servers or banking client processing.--[[User:Praubic|Praubic]] 17:34, 11 October 2010 (UTC)

Here is an example of a design: (the topic asks for key design choices here is one)

Capriccio is a specific design for scalable user level threads. They are distinct from most designs by being independent of event based mechanisms as well as kernel thread models. They are very good choice for internet servers and this implementations could easily support 100,000 threads. They are characterized by high scalability, efficient stack management and scheduling based on resource usage however the performance is not comparable to event-based systems.--[[User:Praubic|Praubic]] 13:32, 12 October 2010 (UTC)

(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Essay Outline ==

#Thesis is an answer to the question so... that's the first step, or the last step, we can always present our info and make our thesis match the info.
#List all questions and points we have about the topic

Questions:
# What makes threads non-scalable? List the problems
# What utility do some scalable implementations lack? Why?
# Just how scalable does a full utility implementation get?

Answers:
# Memory Usage, Context Switching. Consider using a thread pool.
# Signals, portability(maybe) both add overhead which would slow down threads
# If using thread pools, the scalability is then limited to the number of threads in the pool
----

Intro (fill in info)
# Thesis
# main topics

----

Body (made of many main points)

Main Point 1 -[[Rannath]] 
- efficient thread creation/destruction is more scalable 
-- NPTL's improvements over LinuxThreads- primarily due to lower overhead of creation/destruction ''1''

Main Point 2 -[[Rannath]] 
- UMS & user-space threads are more scalable - maybe 
-- context switches are costly ''From class'' 
-- blocking locks have lower latency when twinned with a user space scheduler ''8''

Ok for point 2 -> I posted a draft on the essay page but Im not certain as to whether i should talk about fibers since they are also functioning on user space but theyre not UMS. --[[User:Praubic|Praubic]] 00:18, 14 October 2010 (UTC)

Main Point 3 
- Certain bottleneck appear in scaled implementations, removing these improves scalability. 
-- "False cache-line sharing" ''14'' 
-- xtime lock to a lockless lock ''14''

Main Point 3.5 
Fine-Grain over course-grain 
-- "Big Kernel Lock" ''14'' 
-- dcache_lock ''14''

Link the Main points to the thesis

----

Conclusion
# restate info
# affirmation of thesis

Here is the first paragraph that I attempted. Please feel free to change or even delete it from here.

A thread is an independent task that executes in the same address space as other threads within a single process while sharing data synchronously. Threads require less system resources then concurrent cooperating processes and start much easier therefore there may exist millions of them in a single process. The two major types of threads are kernel and user-mode. Kernel threads are usually considered more heavy and designs that involve them are not very scalable User threads on the other hand are mapped to kernel threads by the threads library such as libpthreads. and there are a few designs that incorporate it mainly Fibers and UMS (User Mode Scheudling) which allow for very high scalability. UMS threads have their own context and resources however the ability to switch in the user mode makes them more efficient (depending on application) than Thread Pools which are yet another mechanism that allows for high scalability.
--[[User:Praubic|Praubic]] 19:04, 12 October 2010 (UTC)

we can add this for intro paragraph:

How is it possible for systems to supports millions of threads or more within a single process?

It is possible for systems to supports millions of threads or more within a single processor, it has the ability to switch execution resource between threads, thus making a concurrent execution. Concurrency is when multiple threads stays on the ques for switching but incapable of running at the same time but it has the ability to make it look like they are running at same time due to the speed they switch. [[vG]] You stated it is possible you did not state how, or rather did not make it clear. The below should be a better interpretation. --[[User:Spanke|Shane]]

Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at.

Added more == vG

Process is known as an instance of a program running in a computer which has its own resources such as address space, files, I/O devices and threads on the other hand thread is similar to a process but it but it does a single operation within the process. Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at. [[vG]]

----
I suggest that we start filling out the main points of the essay. We can discuss the intricacies as we go along. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

== Sources ==

# Short history of threads in Linux and new implementation of them. [http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ] [[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)
# This paper discusses the design choices [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf Native POSIX Threads] [[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)
# lightweight threads vs kernel threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf PicoThreads: Lightweight Threads in Java] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# [http://eigenclass.org/http://homeostasis.scs.carleton.ca/wiki/index.php?title=Talk:COMP_3000_Essay_1_2010_Question_7&action=edit&section=7hiki/lightweight-threads-with-lwt Eigenclass Comparing lightweight threads] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# A lightwight thread implementation for Unix [http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf Implementing light weight threads] --[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC) [[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC)
#Not in this group, but I thought that this paper was excellent: [http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf Qthreads: An API for Programming with Millions of Lightweight Threads]
# Difference between single and multi threading [http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process] [[vG]]
# [http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler] --[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)
# Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading] --[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)
# This site provides in-depth info about threads, threads-pooling, scheduling: http://msdn.microsoft.com/en-us/library/ms684841(VS.85).aspx [[Paul]]
# Here is another site that outlines THREAD designs and techniques: http://people.csail.mit.edu/rinard/osnotes/h2.html [[Paul]]
# [http://www.cosc.brocku.ca/Offerings/4P13/slides/threads.ppt Interesting presentation: really worth checking out] [[Paul]]
# KERNEL vs USERMODE http://www.wordiq.com/definition/Thread_(computer_science)--[[User:Praubic|Praubic]] 18:06, 10 October 2010 (UTC)
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 Scalability in linux]
# [http://hillside.net/plop/2007/papers/PLoP2007_Ahluwalia.pdf This has something to do with our question...]
# [http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx Scheduling Priorities (Windows)], Microsoft (23 September 2010) --[[User:Spanke|Shane]]
# [http://www.novell.com/coolsolutions/feature/14878.html Linux Scheduling Priorities Explained], Novell (11 October 2005) --[[User:Spanke|Shane]]
# [http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/ Inside the Linux 2.6 Completely Fair Scheduler], IBM (15 December 2009) --[[User:Spanke|Shane]]
#http://www.megaupload.com/?d=R4VMK3A1 (PDF Document on Multithreading) [[vG]]
# [http://www.linuxjournal.com/article/1363 what is multithreading?] [[vG]]
# [http://en.wikipedia.org/wiki/Thread_%28computer_science%29 type of threadings and multithreading in general] [[vG]]

COMP 3000 Essay 1 2010 Question 7

2010-10-14T19:55:53Z

Hirving: /* Scalable Threads: The Problems */

=Question=

How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

=Answer=
----

== The Background ==

A 'process' is defined to be "an address-space and a group of resources dedicated to running the program". On the other hand a 'thread' is an independent sequential unit of computation that executes within the context of a kernel supported entity like a 'process'. Threads are often classified by their “weight” (or overhead), which corresponds to the amount of context that must be saved when a thread is removed from the processor, and restored when a thread is reinstated on a processor that is a context switch. The context for a process usually includes the hardware register, kernel stack, user-level stack, interrupt vectors, page tables, and more. Threads require less system resources then concurrent cooperating processes and start much easier, therefore, there may exist millions of them in a single process. Loosely based on this there are two major types of threads: kernel and user-mode. Kernel threads are usually considered heavier and designs that involve them are not very scalable. User threads, on the other hand, are mapped to kernel threads and lightwieght. The ratio of the user threads to kernel threads is an important factor when designing scalable systems.

There are a few designs, mainly Fibers and UMS (User Mode Scheduling) which allow for very high scalability. UMS threads have their own context and resources. However, the ability to switch in the user mode makes them more efficient (depending on the application) than Thread Pools, which are yet another mechanism that allows for high scalability. Systems can support millions of threads within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at. [[vG]] && [[Paul]] && [[Shane]] && [[Gautam]]
----

== Scalable Threads: The Problems ==

One of the basic challenges is to create code which is stable and at the same time scalable. Furthermore, the challenge in making an existing code base scalable is the identification and elimination of bottlenecks once scaled. Ray Bryant and John Hawkes found the following bottlenecks when porting Linux to a 64-core NUMA system. Each of these bottle necks are an example of a type of bottleneck that can appear in any program.

When expensive operations are '''needlessly called''' one type of bottleneck appears. In Linux, there can be some instances of misplaced information in the cache that can cause a "'''cache-coherency operation'''" to be called. This operation is expensive when compared to what would happen if the information was in the 'right place'. Once the misplaced information that causes this problem all the time is identified it can be moved to limit the problem. Anywhere expensive operations are called a needless number of times, this bottleneck can appear (this problem is not inherent, but is a result of bad-design).

Another type of bottleneck is from '''starvation.''' An example of one such bottleneck is the xtime_lock in Linux. Having locking read prevented writing to the timer value, causing the kernel to waste CPU time to keep trying. This problem was solved by using a lockless-read. This problem would appear anywhere that a thread must keep trying to execute, but cannot, leading to wasted CPU cycles.

The next type of bottleneck is from '''course-grained''' operations. Granularity refers to the execution time of a code segment. Both examples eat alot of CPU time, where a finer-grained implementation would eat less. The closer a segment is to the speed of an atomic action the finer its granularity. One course-grained bottleneck was the dcache_lock. It ate up some time in normal use, but it was also called in the much more popular dnotify_parent() function. This was deemed an unacceptable state of affairs. So, the dcache_lock strategy was replaced with a finer-grained strategy from a later implementation of linux. Another big course-grained bottleneck in the system is the "Big Kernel Lock" (BKL) linux's kernel synchronization control. Waiting for the BKL took up as much as 70% of the CPU time on a system with only 28 cores. The preferred method, on Linux NUMA systems, was to limit the BKL's usage. The ext2 and ext3 file systems were replaced with a file system that uses finer-grained locking (XFS), reducing the impact of the bottleneck. Both those examples are the result of course granularity.

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.
--[[Rannath]] A few additions--[[Gautam]]

'''MAIN POINT 2 Paragraph draft''' --[[User:Praubic|Praubic]] 00:21, 14 October 2010 (UTC) still in progress and debating

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. 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. 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. 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 ==
--[[User:Gautam|Gautam]] 00:29, 14 October 2010 (UTC) 
'''(A) Kernel Threads and User Threads (1:1 vs M:N) '''
This is the most basic design choice. The 1:1 boasts of a slim clean library interface on top of the kernel functions. Although, the M:N would implement a complicated library, it would offer advantages in areas of signal handling. A general consensus was that the M:N design was not compatible with the Linux kernel due to such a high cost for implementation. This gave birth to the 1:1 model.

''' (B)Signal Handling '''
The kernel implements the POSIX signal handling for use with the multitude of signal masks. Since the signal will only be sent to a thread if it is unblocked, no unnecessary interruptions through signals occur. The kernel is also in a much better situation to judge which is the best thread to receive the signal. This only holds true if the 1-on-1 model is used.

''' (C)Synchronization '''
The implementation of the synchronization primitives such as mutexes, read-write locks, conditional variables, semaphores, and barriers requires some form of kernel support. Busy waiting is not an option since threads can have different priorities (beside wasting CPU cycles). The same argument rules out the exclusive use of sched yield. Signals were the only viable solution for the old implementation. Threads would block in the kernel until woken by a signal. This method has severe drawbacks in terms of speed and reliability caused by spurious wakeups and derogation of the quality of the signal handling in the application. Fortunately, new functionality was added to the kernel to implement all kinds of synchronization.

Explaining the four types of synchronization:

*Mutex locks uses only a thread thus giving access to only certain part of the code
*Using Read/Write synchronization one can gain exclusive write and read access to protected resource but to edit the content it must have the exclusive write lock. Exclusive write lock is only permitted when all the read locks are released
*Condition variable synchronization protects the thread until the condition becomes true
*Counting semaphores delivers access to multiple threads. It has a count which keeps tracks of the number of threads can have concurrent access to the data. Once the limit is reached other threads are blocked until the limit changes.
[[vG]]
''' (D)Memory Management '''
Thread memory management is an important design choice when attempting to create a large amount of threads in a single process, from creation to maintenance and deallocation. A thread's data structure is made up of a program counter, a stack and a control block. A control block of a thread is needed for thread management as it contains the state data of a thread. The optimization of this data structure can greatly increase performance in large number of threads.

The creation of a thread can take place before the process actually requires it to run and wait until a idle processor becomes available to run the thread. Thread overhead (the required memory, CPU time, and read/write time to initialize the thread) is a problem that can arise with this creation process, since it frontloads the process. Another problem with this creation process is that the thread must allocate the memory required for it's stack at creation because it is expensive to dynamically allocate the stack memory. A way to optimize this creation process for large amounts of threads is to copy the arguments of the thread into it's control block, this allows for the thread's stack to be allocated at the thread's startup (when the thread starts being used) and not when the thread is created. When the thread enters startup it can copy it's arguments out of it's control block and allocate it's memory. Thread creation is ruled by latency (the cost of thread management on the system) and throughput (the rate that the system can create, start, and finish threads), and, if thread memory management is done in a serial processing manner, these two factor combine to create a maximum rate of thread creation.

Locks are an important part of the performance of threads and there are multiple way of controlling and creating locks in order to create a large amount of threads. Single lock (having the data structures all be in one lock) has the advantage that once the processor has acquired the lock it can modify any of the stored data. Using the single lock method means only one lock is needed per thread, decreasing the thread overhead but this also limits the throughput of the system. Multiple lock (having each data structure have it's own lock) has the advantage of that each action on the data structure is it's own locking/unlocking operations. Multiple has greater thread overhead (because there are more locks) but the thread throughput is much higher allowing for fast creation of threads. Another downside of multiple lock systems are deadlocks, a deadlock happens when two different threads are waiting for data that the other task holds. Single and multiple lock systems are the inverse of each other and using both depending on the situation can greatly increase the performance of a system.

The deallocation of a thread can also be optimized for use in increasing the scalability of threads. Storing deallocted stacks and control blocks in a free list allows the process of allocation and deallocation to be a list operation, if they are not stored in a free list then the thread overhead would include finding the correct size of free memory to store the stack. [http://portal.acm.org/citation.cfm?id=75378] [[hirving]]

''' (E)Scheduling Priorities '''
A thread is an entity that can be scheduled according to its scheduling priority which is a number ranging from 0 to 31 for Windows and a Red-Black Tree used by the CFS (Completely Fair Scheduler) in Linux. All threads are executed in a time splice assigned to them in round robin fashion and lower priority threads wait until the ones above finish performing their tasks. Threads are composed of thread context which internally breaks down into set of machine registers, the kernel and user stack all linked to the address space of the process where the thread resides. A context switch occurs as the time splice elapses and an equal (or higher) priority thread becomes available and it is responsible for allowing high scalability if it is efficiently implemented. For example fibers which are executed entirely in userspace do not require a system call during a switch which highly increases efficiency.[http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx][http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/], Microsoft (23 September 2010) --[[User:Praubic|Praubic]] 18:24, 13 October 2010 (UTC)

== References ==

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-14T19:44:58Z

Hirving: /* Log */

== Log ==
'''Suggestion:''' Let us maintain our edits here instead of on littering the main page with our names. Also please do not edit without writing to the log so that we know who has done what and when.

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

Moved around some info for clarity. Everyone should post your interpretation of the question in simplest possible English so we`re on the same page (as someone, maybe me, seems to have the wrong idea about what we`re trying to talk about)
More moving for clarity. added an essay outline at bottom (feel free to change)
filled in the outline somewhat added questions to the outline for everyone to think on.--[[User:Rannath|Rannath]]

First Draft for essay. Please modify and add on. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

Edited Scheduling Priorities and rewrote some areas to provide a better paragraph structure. --[[User:Spanke|Shane]] 15:25, 13 October 2010 (UTC)

Added to the memory management section. --[[User:Hirving|Hirving]] 21:42, 13 October 2010 (UTC)

Edited Scalable Threads Problems. Also did a little re-arrangement. --[[User:Gautam|Gautam]] 01:03, 14 October 2010 (UTC)

Answered Essay Questions in Discussion. --[[User:Spanke|Shane]] 01:25, 13 October 2010 (UTC)

I posted Main point 2. It is nearing completion, --[[User:Praubic|Praubic]] 17:43, 14 October 2010 (UTC)

Minor edits in Scheduler part. --[[User:Gautam|Gautam]] 19:09, 14 October 2010 (UTC)

Added a paragraph about locks to memory section. --[[User:Hirving|Hirving]] 19:36, 14 October 2010 (UTC)

Edited answer paragraphs for clarity. (commas are nice) --[[User:Hirving|Hirving]] 19:44, 14 October 2010 (UTC)

 <Add your future activities here>

== The Question ==
'''Original: '''
How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

'''Rannath: '''
The question seems to be about number and scalability of threads not the gross mechanics.

To be more clear: we can limit ourselves from the thread implementations to the thread scalability... ignore the stuff that required for all threads, unless its required for many threads. (I didn't find any implementations that required hardware)

I would also argue that since OSs have to run on multiple hardwares one cannot guarantee that unique/rare hardware bits will be there. While we can talk about hardware we should limit it to a mention at most. OR we could mention prospective hardware that could help out, but is not yet standard. It depends on whether we want to do "as it is" or "as it might be"

utility of such massively scalable thread implementations. I took this as: what functionality (of single strings) does one have to give up to make threads scalable.

'''Gautam: '''
I think the hardware is as relevant as the software. Not all things can be done in software and hardware support is an important factor in most of the solutions to many problems that OS face. My take.

'''Henry: '''
Since the question is about the system as a whole, I think the answer should include both software and hardware support for large amounts of threads. The questions revolves around how a system can handle millions of threads and what are the major factors that allow the system to do it. Also, the last part of the question seems to ask what this amount of threads allows a process to do.

'''Shane: '''
In response to the above's idea on the last part of the question, I would argue that it would enable fast execution because all threads that receive a cache miss would be picked up by the other threads so long as there was enough resources. Also the use of more threads would help synchronize the cache (through sharing) so that it would not miss. Of course this would be if they were assigned to the same task, you cannot sync threads running different applications it just wouldn't make sense. The only issue with this idea is the software must support this number.

'''vG: '''
We should talk about type of relationship models (1:1 N:M N:N and so on) also talk about the application vs hardware multi-threading within single processor.

'''Paul: '''
I discussed Main Point 2 and how UMS threading is stretched onto multiple cores. Design that involves multiple processors differs from single proc comps so hardware definitely plays significant role here.

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek <support.tamiltreasure@gmail.com>

Shane Panke <shanepanke@msn.com>

Henry Irving <sens.henry@gmail.com>

Paul Raubic <paul_raubic@hotmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: --[[User:Rannath|Rannath]]

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

== Facts We have ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far we have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere
# least number (none if at all possible) of context switches per-thread - ''5''
# use of a "thread pool" - ''3''
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space. --[[User:Rannath|Rannath]]

Multi-threading is a term used to describe:

* A facility provided by the operating system that enables an application to create threads of execution within a process
* Applications whose architecture takes advantage of the multi-threading provided by the operating system
[[vG]]
----
These are all related ideas.

Ok, since we are discussing design choices maybe we could also elaborate on the two major types of threads. Here, I already wrote a few lines, source can be found in citation section:

''Fibers (user mode threads) provide very quick and efficient switching because there is no need for a system call and kernel is oblivious to a switch - allows for millions of user mode threads. ISSUES: Blocking system calls disables all other fibers.
On the other hand managing threads through the kernel requires context switch (between user and kernel mode) on creation and removal of a thread therefore programs with prodigious number of threads would suffer huge performance hits.--[[User:Praubic|Praubic]] 18:05, 10 October 2010 (UTC)''

User-mode scheduling (UMS) is a light-weight mechanism that applications can use to schedule their own threads. The ability to switch between threads in user mode makes UMS more efficient than thread pools for short-duration work items that require few system calls. [[Paul]]

One implementation of UMS is: combination of N:N and N:M, where the N:N relationship reveals N false processors to the user-space so the user can deal with scheduling on their own. ''5'' -[[Rannath]]

----

I would scrap the first two below, at most mention them...

#time-division multiplexing
#threads vs processes
#I/O Scheduling -[[vG]]

Splitting this off because I don't think it's technically part of the answer 
Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]

----
Things that we '''need''' to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
This is a '''need''' section 4 below is not '''needed''' 
(A)Design Decisions
1. Type of threading (1:1 1:N M:N)
2. Signal handling - we might be able to leave this out as it seems some "light weight" threads use no signals
3. Synchronisation
4. Memory Handling
5. Scheduling Priorities (context switching and how it affects the CPU threading process)[[Paul]]
----

Things we might want also to cover in the essay (non-essentials here): --[[User:Rannath|Rannath]] 04:43, 10 October 2010 (UTC) 
(A)Design Decisions
1. Brief History of threading
2. examples of attempts at getting absurd numbers of threads (failures)
3. other types of threading, including heavy weight and processes
4. Examples of systems that require many threads such as mainframe servers or banking client processing.--[[User:Praubic|Praubic]] 17:34, 11 October 2010 (UTC)

Here is an example of a design: (the topic asks for key design choices here is one)

Capriccio is a specific design for scalable user level threads. They are distinct from most designs by being independent of event based mechanisms as well as kernel thread models. They are very good choice for internet servers and this implementations could easily support 100,000 threads. They are characterized by high scalability, efficient stack management and scheduling based on resource usage however the performance is not comparable to event-based systems.--[[User:Praubic|Praubic]] 13:32, 12 October 2010 (UTC)

(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Essay Outline ==

#Thesis is an answer to the question so... that's the first step, or the last step, we can always present our info and make our thesis match the info.
#List all questions and points we have about the topic

Questions:
# What makes threads non-scalable? List the problems
# What utility do some scalable implementations lack? Why?
# Just how scalable does a full utility implementation get?

Answers:
# Memory Usage, Context Switching. Consider using a thread pool.
# Signals, portability(maybe) both add overhead which would slow down threads
# If using thread pools, the scalability is then limited to the number of threads in the pool
----

Intro (fill in info)
# Thesis
# main topics

----

Body (made of many main points)

Main Point 1 -[[Rannath]] 
- efficient thread creation/destruction is more scalable 
-- NPTL's improvements over LinuxThreads- primarily due to lower overhead of creation/destruction ''1''

Main Point 2 -[[Rannath]] 
- UMS & user-space threads are more scalable - maybe 
-- context switches are costly ''From class'' 
-- blocking locks have lower latency when twinned with a user space scheduler ''8''

Ok for point 2 -> I posted a draft on the essay page but Im not certain as to whether i should talk about fibers since they are also functioning on user space but theyre not UMS. --[[User:Praubic|Praubic]] 00:18, 14 October 2010 (UTC)

Main Point 3 
- Certain bottleneck appear in scaled implementations, removing these improves scalability. 
-- "False cache-line sharing" ''14'' 
-- xtime lock to a lockless lock ''14''

Main Point 3.5 
Fine-Grain over course-grain 
-- "Big Kernel Lock" ''14'' 
-- dcache_lock ''14''

Link the Main points to the thesis

----

Conclusion
# restate info
# affirmation of thesis

Here is the first paragraph that I attempted. Please feel free to change or even delete it from here.

A thread is an independent task that executes in the same address space as other threads within a single process while sharing data synchronously. Threads require less system resources then concurrent cooperating processes and start much easier therefore there may exist millions of them in a single process. The two major types of threads are kernel and user-mode. Kernel threads are usually considered more heavy and designs that involve them are not very scalable User threads on the other hand are mapped to kernel threads by the threads library such as libpthreads. and there are a few designs that incorporate it mainly Fibers and UMS (User Mode Scheudling) which allow for very high scalability. UMS threads have their own context and resources however the ability to switch in the user mode makes them more efficient (depending on application) than Thread Pools which are yet another mechanism that allows for high scalability.
--[[User:Praubic|Praubic]] 19:04, 12 October 2010 (UTC)

we can add this for intro paragraph:

How is it possible for systems to supports millions of threads or more within a single process?

It is possible for systems to supports millions of threads or more within a single processor, it has the ability to switch execution resource between threads, thus making a concurrent execution. Concurrency is when multiple threads stays on the ques for switching but incapable of running at the same time but it has the ability to make it look like they are running at same time due to the speed they switch. [[vG]] You stated it is possible you did not state how, or rather did not make it clear. The below should be a better interpretation. --[[User:Spanke|Shane]]

Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at.

Added more == vG

Process is known as an instance of a program running in a computer which has its own resources such as address space, files, I/O devices and threads on the other hand thread is similar to a process but it but it does a single operation within the process. Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at. [[vG]]

----
I suggest that we start filling out the main points of the essay. We can discuss the intricacies as we go along. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

== Sources ==

# Short history of threads in Linux and new implementation of them. [http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ] [[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)
# This paper discusses the design choices [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf Native POSIX Threads] [[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)
# lightweight threads vs kernel threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf PicoThreads: Lightweight Threads in Java] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# [http://eigenclass.org/http://homeostasis.scs.carleton.ca/wiki/index.php?title=Talk:COMP_3000_Essay_1_2010_Question_7&action=edit&section=7hiki/lightweight-threads-with-lwt Eigenclass Comparing lightweight threads] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# A lightwight thread implementation for Unix [http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf Implementing light weight threads] --[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC) [[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC)
#Not in this group, but I thought that this paper was excellent: [http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf Qthreads: An API for Programming with Millions of Lightweight Threads]
# Difference between single and multi threading [http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process] [[vG]]
# [http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler] --[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)
# Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading] --[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)
# This site provides in-depth info about threads, threads-pooling, scheduling: http://msdn.microsoft.com/en-us/library/ms684841(VS.85).aspx [[Paul]]
# Here is another site that outlines THREAD designs and techniques: http://people.csail.mit.edu/rinard/osnotes/h2.html [[Paul]]
# [http://www.cosc.brocku.ca/Offerings/4P13/slides/threads.ppt Interesting presentation: really worth checking out] [[Paul]]
# KERNEL vs USERMODE http://www.wordiq.com/definition/Thread_(computer_science)--[[User:Praubic|Praubic]] 18:06, 10 October 2010 (UTC)
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 Scalability in linux]
# [http://hillside.net/plop/2007/papers/PLoP2007_Ahluwalia.pdf This has something to do with our question...]
# [http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx Scheduling Priorities (Windows)], Microsoft (23 September 2010) --[[User:Spanke|Shane]]
# [http://www.novell.com/coolsolutions/feature/14878.html Linux Scheduling Priorities Explained], Novell (11 October 2005) --[[User:Spanke|Shane]]
# [http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/ Inside the Linux 2.6 Completely Fair Scheduler], IBM (15 December 2009) --[[User:Spanke|Shane]]
#http://www.megaupload.com/?d=R4VMK3A1 (PDF Document on Multithreading) [[vG]]
# [http://www.linuxjournal.com/article/1363 what is multithreading?] [[vG]]
# [http://en.wikipedia.org/wiki/Thread_%28computer_science%29 type of threadings and multithreading in general] [[vG]]

COMP 3000 Essay 1 2010 Question 7

2010-10-14T19:43:54Z

Hirving: /* Answer */

=Question=

How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

=Answer=

A 'process' is defined to be "an address-space and a group of resources dedicated to running the program". On the other hand a 'thread' is an independent sequential unit of computation that executes within the context of a kernel supported entity like a 'process'. Threads are often classified by their “weight” (or overhead), which corresponds to the amount of context that must be saved when a thread is removed from the processor, and restored when a thread is reinstated on a processor that is a context switch. The context for a process usually includes the hardware register, kernel stack, user-level stack, interrupt vectors, page tables, and more. Threads require less system resources then concurrent cooperating processes and start much easier, therefore, there may exist millions of them in a single process. Loosely based on this there are two major types of threads: kernel and user-mode. Kernel threads are usually considered heavier and designs that involve them are not very scalable. User threads, on the other hand, are mapped to kernel threads and lightwieght. The ratio of the user threads to kernel threads is an important factor when designing scalable systems.

There are a few designs, mainly Fibers and UMS (User Mode Scheduling) which allow for very high scalability. UMS threads have their own context and resources. However, the ability to switch in the user mode makes them more efficient (depending on the application) than Thread Pools, which are yet another mechanism that allows for high scalability. Systems can support millions of threads within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at. [[vG]] && [[Paul]] && [[Shane]] && [[Gautam]]
----

== Scalable Threads: The Problems ==

One of the basic challenges is to create code which is stable and at the same time scalable. Furthermore, the challenge in making an existing code base scalable is the identification and elimination of bottlenecks once scaled. Ray Bryant and John Hawkes found the following bottlenecks when porting Linux to a 64-core NUMA system. Each of these bottle necks is an example of a type of bottleneck that can appear in any program.

When expensive operations are '''needlessly called''' one type of bottleneck appears. In Linux there can be some instances of misplaced information in the cache that can cause a "'''cache-coherency operation'''" to be called. This operation is expensive compared to what would happen if the information was in the 'right place'. Once misplaced information that causes this problem all the time is identified it can be moved to limit the problem. Anywhere expensive operations are called a needless number of times this bottleneck can appear (this problem is not inherent, but is a result of bad-design).

Another type of bottleneck is from '''starvation.''' One such bottleneck is the xtime_lock in Linux. Having locking reading prevented writing to the timer value, causing the kernel to waste CPU time to keep trying. This problem was solved by using a lockless-read. This problem would appear anywhere that a thread must keep trying to execute, but cannot, leading to wasted CPU cycles.

The next type of bottleneck is from '''course-grained''' operations. Granularity refers to the execution time of a code segment. Both examples eat alot of CPU time, where a finer-grained implementation would eat less. The closer a segment is to the speed of an atomic action the finer its granularity. One course-grained bottleneck was the dcache_lock. It ate up some time in normal use, but it was also called in the much more popular dnotify_parent() function. That was an unacceptable state of affairs. So the dcache_lock strategy was replaced with a finer-grained strategy from a later implementation of linux. Another big course-grained bottleneck in the system is the "Big Kernel Lock" (BKL) linux's kernel synchronization control. Waiting for the BKL took up as much as 70% of the CPU time on a system with only 28 cores. The preferred method, on Linux NUMA systems, was to limit the BKL's usage. The ext2 and ext3 file systems were replaced with a file system that uses finer-grained locking (XFS), reducing the impact of the bottleneck. Both those examples are the result of course granularity.

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.
--[[Rannath]] A few additions--[[Gautam]]

'''MAIN POINT 2 Paragraph draft''' --[[User:Praubic|Praubic]] 00:21, 14 October 2010 (UTC) still in progress and debating

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 which 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. 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. 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. 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 ==
--[[User:Gautam|Gautam]] 00:29, 14 October 2010 (UTC) 
'''(A) Kernel Threads and User Threads (1:1 vs M:N) '''
This is the most basic design choice. The 1:1 boasts of a slim clean library interface on top of the kernel functions. Although, the M:N would implement a complicated library, it would offer advantages in areas of signal handling. A general consensus was that the M:N design was not compatible with the Linux kernel due to such a high cost for implementation. This gave birth to the 1:1 model.

''' (B)Signal Handling '''
The kernel implements the POSIX signal handling for use with the multitude of signal masks. Since the signal will only be sent to a thread if it is unblocked, no unnecessary interruptions through signals occur. The kernel is also in a much better situation to judge which is the best thread to receive the signal. This only holds true if the 1-on-1 model is used.

''' (C)Synchronization '''
The implementation of the synchronization primitives such as mutexes, read-write locks, conditional variables, semaphores, and barriers requires some form of kernel support. Busy waiting is not an option since threads can have different priorities (beside wasting CPU cycles). The same argument rules out the exclusive use of sched yield. Signals were the only viable solution for the old implementation. Threads would block in the kernel until woken by a signal. This method has severe drawbacks in terms of speed and reliability caused by spurious wakeups and derogation of the quality of the signal handling in the application. Fortunately, new functionality was added to the kernel to implement all kinds of synchronization.

Explaining the four types of synchronization:

*Mutex locks uses only a thread thus giving access to only certain part of the code
*Using Read/Write synchronization one can gain exclusive write and read access to protected resource but to edit the content it must have the exclusive write lock. Exclusive write lock is only permitted when all the read locks are released
*Condition variable synchronization protects the thread until the condition becomes true
*Counting semaphores delivers access to multiple threads. It has a count which keeps tracks of the number of threads can have concurrent access to the data. Once the limit is reached other threads are blocked until the limit changes.
[[vG]]
''' (D)Memory Management '''
Thread memory management is an important design choice when attempting to create a large amount of threads in a single process, from creation to maintenance and deallocation. A thread's data structure is made up of a program counter, a stack and a control block. A control block of a thread is needed for thread management as it contains the state data of a thread. The optimization of this data structure can greatly increase performance in large number of threads.

The creation of a thread can take place before the process actually requires it to run and wait until a idle processor becomes available to run the thread. Thread overhead (the required memory, CPU time, and read/write time to initialize the thread) is a problem that can arise with this creation process, since it frontloads the process. Another problem with this creation process is that the thread must allocate the memory required for it's stack at creation because it is expensive to dynamically allocate the stack memory. A way to optimize this creation process for large amounts of threads is to copy the arguments of the thread into it's control block, this allows for the thread's stack to be allocated at the thread's startup (when the thread starts being used) and not when the thread is created. When the thread enters startup it can copy it's arguments out of it's control block and allocate it's memory. Thread creation is ruled by latency (the cost of thread management on the system) and throughput (the rate that the system can create, start, and finish threads), and, if thread memory management is done in a serial processing manner, these two factor combine to create a maximum rate of thread creation.

Locks are an important part of the performance of threads and there are multiple way of controlling and creating locks in order to create a large amount of threads. Single lock (having the data structures all be in one lock) has the advantage that once the processor has acquired the lock it can modify any of the stored data. Using the single lock method means only one lock is needed per thread, decreasing the thread overhead but this also limits the throughput of the system. Multiple lock (having each data structure have it's own lock) has the advantage of that each action on the data structure is it's own locking/unlocking operations. Multiple has greater thread overhead (because there are more locks) but the thread throughput is much higher allowing for fast creation of threads. Another downside of multiple lock systems are deadlocks, a deadlock happens when two different threads are waiting for data that the other task holds. Single and multiple lock systems are the inverse of each other and using both depending on the situation can greatly increase the performance of a system.

The deallocation of a thread can also be optimized for use in increasing the scalability of threads. Storing deallocted stacks and control blocks in a free list allows the process of allocation and deallocation to be a list operation, if they are not stored in a free list then the thread overhead would include finding the correct size of free memory to store the stack. [http://portal.acm.org/citation.cfm?id=75378] [[hirving]]

''' (E)Scheduling Priorities '''
A thread is an entity that can be scheduled according to its scheduling priority which is a number ranging from 0 to 31 for Windows and a Red-Black Tree used by the CFS (Completely Fair Scheduler) in Linux. All threads are executed in a time splice assigned to them in round robin fashion and lower priority threads wait until the ones above finish performing their tasks. Threads are composed of thread context which internally breaks down into set of machine registers, the kernel and user stack all linked to the address space of the process where the thread resides. A context switch occurs as the time splice elapses and an equal (or higher) priority thread becomes available and it is responsible for allowing high scalability if it is efficiently implemented. For example fibers which are executed entirely in userspace do not require a system call during a switch which highly increases efficiency.[http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx][http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/], Microsoft (23 September 2010) --[[User:Praubic|Praubic]] 18:24, 13 October 2010 (UTC)

== References ==

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-14T19:36:44Z

Hirving: /* Log */

== Log ==
'''Suggestion:''' Let us maintain our edits here instead of on littering the main page with our names. Also please do not edit without writing to the log so that we know who has done what and when.

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

Moved around some info for clarity. Everyone should post your interpretation of the question in simplest possible English so we`re on the same page (as someone, maybe me, seems to have the wrong idea about what we`re trying to talk about)
More moving for clarity. added an essay outline at bottom (feel free to change)
filled in the outline somewhat added questions to the outline for everyone to think on.--[[User:Rannath|Rannath]]

First Draft for essay. Please modify and add on. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

Edited Scheduling Priorities and rewrote some areas to provide a better paragraph structure. --[[User:Spanke|Shane]] 15:25, 13 October 2010 (UTC)

Added to the memory management section. --[[User:Hirving|Hirving]] 21:42, 13 October 2010 (UTC)

Edited Scalable Threads Problems. Also did a little re-arrangement. --[[User:Gautam|Gautam]] 01:03, 14 October 2010 (UTC)

Answered Essay Questions in Discussion. --[[User:Spanke|Shane]] 01:25, 13 October 2010 (UTC)

I posted Main point 2. It is nearing completion, --[[User:Praubic|Praubic]] 17:43, 14 October 2010 (UTC)

Minor edits in Scheduler part. --[[User:Gautam|Gautam]] 19:09, 14 October 2010 (UTC)

Added a paragraph about locks to memory section. --[[User:Hirving|Hirving]] 19:36, 14 October 2010 (UTC)

 <Add your future activities here>

== The Question ==
'''Original: '''
How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

'''Rannath: '''
The question seems to be about number and scalability of threads not the gross mechanics.

To be more clear: we can limit ourselves from the thread implementations to the thread scalability... ignore the stuff that required for all threads, unless its required for many threads. (I didn't find any implementations that required hardware)

I would also argue that since OSs have to run on multiple hardwares one cannot guarantee that unique/rare hardware bits will be there. While we can talk about hardware we should limit it to a mention at most. OR we could mention prospective hardware that could help out, but is not yet standard. It depends on whether we want to do "as it is" or "as it might be"

utility of such massively scalable thread implementations. I took this as: what functionality (of single strings) does one have to give up to make threads scalable.

'''Gautam: '''
I think the hardware is as relevant as the software. Not all things can be done in software and hardware support is an important factor in most of the solutions to many problems that OS face. My take.

'''Henry: '''
Since the question is about the system as a whole, I think the answer should include both software and hardware support for large amounts of threads. The questions revolves around how a system can handle millions of threads and what are the major factors that allow the system to do it. Also, the last part of the question seems to ask what this amount of threads allows a process to do.

'''Shane: '''
In response to the above's idea on the last part of the question, I would argue that it would enable fast execution because all threads that receive a cache miss would be picked up by the other threads so long as there was enough resources. Also the use of more threads would help synchronize the cache (through sharing) so that it would not miss. Of course this would be if they were assigned to the same task, you cannot sync threads running different applications it just wouldn't make sense. The only issue with this idea is the software must support this number.

'''vG: '''
We should talk about type of relationship models (1:1 N:M N:N and so on) also talk about the application vs hardware multi-threading within single processor.

'''Paul: '''
I discussed Main Point 2 and how UMS threading is stretched onto multiple cores. Design that involves multiple processors differs from single proc comps so hardware definitely plays significant role here.

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek <support.tamiltreasure@gmail.com>

Shane Panke <shanepanke@msn.com>

Henry Irving <sens.henry@gmail.com>

Paul Raubic <paul_raubic@hotmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: --[[User:Rannath|Rannath]]

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

== Facts We have ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far we have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere
# least number (none if at all possible) of context switches per-thread - ''5''
# use of a "thread pool" - ''3''
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space. --[[User:Rannath|Rannath]]

Multi-threading is a term used to describe:

* A facility provided by the operating system that enables an application to create threads of execution within a process
* Applications whose architecture takes advantage of the multi-threading provided by the operating system
[[vG]]
----
These are all related ideas.

Ok, since we are discussing design choices maybe we could also elaborate on the two major types of threads. Here, I already wrote a few lines, source can be found in citation section:

''Fibers (user mode threads) provide very quick and efficient switching because there is no need for a system call and kernel is oblivious to a switch - allows for millions of user mode threads. ISSUES: Blocking system calls disables all other fibers.
On the other hand managing threads through the kernel requires context switch (between user and kernel mode) on creation and removal of a thread therefore programs with prodigious number of threads would suffer huge performance hits.--[[User:Praubic|Praubic]] 18:05, 10 October 2010 (UTC)''

User-mode scheduling (UMS) is a light-weight mechanism that applications can use to schedule their own threads. The ability to switch between threads in user mode makes UMS more efficient than thread pools for short-duration work items that require few system calls. [[Paul]]

One implementation of UMS is: combination of N:N and N:M, where the N:N relationship reveals N false processors to the user-space so the user can deal with scheduling on their own. ''5'' -[[Rannath]]

----

I would scrap the first two below, at most mention them...

#time-division multiplexing
#threads vs processes
#I/O Scheduling -[[vG]]

Splitting this off because I don't think it's technically part of the answer 
Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]

----
Things that we '''need''' to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
This is a '''need''' section 4 below is not '''needed''' 
(A)Design Decisions
1. Type of threading (1:1 1:N M:N)
2. Signal handling - we might be able to leave this out as it seems some "light weight" threads use no signals
3. Synchronisation
4. Memory Handling
5. Scheduling Priorities (context switching and how it affects the CPU threading process)[[Paul]]
----

Things we might want also to cover in the essay (non-essentials here): --[[User:Rannath|Rannath]] 04:43, 10 October 2010 (UTC) 
(A)Design Decisions
1. Brief History of threading
2. examples of attempts at getting absurd numbers of threads (failures)
3. other types of threading, including heavy weight and processes
4. Examples of systems that require many threads such as mainframe servers or banking client processing.--[[User:Praubic|Praubic]] 17:34, 11 October 2010 (UTC)

Here is an example of a design: (the topic asks for key design choices here is one)

Capriccio is a specific design for scalable user level threads. They are distinct from most designs by being independent of event based mechanisms as well as kernel thread models. They are very good choice for internet servers and this implementations could easily support 100,000 threads. They are characterized by high scalability, efficient stack management and scheduling based on resource usage however the performance is not comparable to event-based systems.--[[User:Praubic|Praubic]] 13:32, 12 October 2010 (UTC)

(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Essay Outline ==

#Thesis is an answer to the question so... that's the first step, or the last step, we can always present our info and make our thesis match the info.
#List all questions and points we have about the topic

Questions:
# What makes threads non-scalable? List the problems
# What utility do some scalable implementations lack? Why?
# Just how scalable does a full utility implementation get?

Answers:
# Memory Usage, Context Switching. Consider using a thread pool.
# Signals, portability(maybe) both add overhead which would slow down threads
# If using thread pools, the scalability is then limited to the number of threads in the pool
----

Intro (fill in info)
# Thesis
# main topics

----

Body (made of many main points)

Main Point 1 -[[Rannath]] 
- efficient thread creation/destruction is more scalable 
-- NPTL's improvements over LinuxThreads- primarily due to lower overhead of creation/destruction ''1''

Main Point 2 -[[Rannath]] 
- UMS & user-space threads are more scalable - maybe 
-- context switches are costly ''From class'' 
-- blocking locks have lower latency when twinned with a user space scheduler ''8''

Ok for point 2 -> I posted a draft on the essay page but Im not certain as to whether i should talk about fibers since they are also functioning on user space but theyre not UMS. --[[User:Praubic|Praubic]] 00:18, 14 October 2010 (UTC)

Main Point 3 
- Certain bottleneck appear in scaled implementations, removing these improves scalability. 
-- "False cache-line sharing" ''14'' 
-- xtime lock to a lockless lock ''14''

Main Point 3.5 
Fine-Grain over course-grain 
-- "Big Kernel Lock" ''14'' 
-- dcache_lock ''14''

Link the Main points to the thesis

----

Conclusion
# restate info
# affirmation of thesis

Here is the first paragraph that I attempted. Please feel free to change or even delete it from here.

A thread is an independent task that executes in the same address space as other threads within a single process while sharing data synchronously. Threads require less system resources then concurrent cooperating processes and start much easier therefore there may exist millions of them in a single process. The two major types of threads are kernel and user-mode. Kernel threads are usually considered more heavy and designs that involve them are not very scalable User threads on the other hand are mapped to kernel threads by the threads library such as libpthreads. and there are a few designs that incorporate it mainly Fibers and UMS (User Mode Scheudling) which allow for very high scalability. UMS threads have their own context and resources however the ability to switch in the user mode makes them more efficient (depending on application) than Thread Pools which are yet another mechanism that allows for high scalability.
--[[User:Praubic|Praubic]] 19:04, 12 October 2010 (UTC)

we can add this for intro paragraph:

How is it possible for systems to supports millions of threads or more within a single process?

It is possible for systems to supports millions of threads or more within a single processor, it has the ability to switch execution resource between threads, thus making a concurrent execution. Concurrency is when multiple threads stays on the ques for switching but incapable of running at the same time but it has the ability to make it look like they are running at same time due to the speed they switch. [[vG]] You stated it is possible you did not state how, or rather did not make it clear. The below should be a better interpretation. --[[User:Spanke|Shane]]

Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at.

Added more == vG

Process is known as an instance of a program running in a computer which has its own resources such as address space, files, I/O devices and threads on the other hand thread is similar to a process but it but it does a single operation within the process. Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at. [[vG]]

----
I suggest that we start filling out the main points of the essay. We can discuss the intricacies as we go along. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

== Sources ==

# Short history of threads in Linux and new implementation of them. [http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ] [[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)
# This paper discusses the design choices [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf Native POSIX Threads] [[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)
# lightweight threads vs kernel threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf PicoThreads: Lightweight Threads in Java] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# [http://eigenclass.org/http://homeostasis.scs.carleton.ca/wiki/index.php?title=Talk:COMP_3000_Essay_1_2010_Question_7&action=edit&section=7hiki/lightweight-threads-with-lwt Eigenclass Comparing lightweight threads] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# A lightwight thread implementation for Unix [http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf Implementing light weight threads] --[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC) [[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC)
#Not in this group, but I thought that this paper was excellent: [http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf Qthreads: An API for Programming with Millions of Lightweight Threads]
# Difference between single and multi threading [http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process] [[vG]]
# [http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler] --[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)
# Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading] --[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)
# This site provides in-depth info about threads, threads-pooling, scheduling: http://msdn.microsoft.com/en-us/library/ms684841(VS.85).aspx [[Paul]]
# Here is another site that outlines THREAD designs and techniques: http://people.csail.mit.edu/rinard/osnotes/h2.html [[Paul]]
# [http://www.cosc.brocku.ca/Offerings/4P13/slides/threads.ppt Interesting presentation: really worth checking out] [[Paul]]
# KERNEL vs USERMODE http://www.wordiq.com/definition/Thread_(computer_science)--[[User:Praubic|Praubic]] 18:06, 10 October 2010 (UTC)
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 Scalability in linux]
# [http://hillside.net/plop/2007/papers/PLoP2007_Ahluwalia.pdf This has something to do with our question...]
# [http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx Scheduling Priorities (Windows)], Microsoft (23 September 2010) --[[User:Spanke|Shane]]
# [http://www.novell.com/coolsolutions/feature/14878.html Linux Scheduling Priorities Explained], Novell (11 October 2005) --[[User:Spanke|Shane]]
# [http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/ Inside the Linux 2.6 Completely Fair Scheduler], IBM (15 December 2009) --[[User:Spanke|Shane]]
#http://www.megaupload.com/?d=R4VMK3A1 (PDF Document on Multithreading) [[vG]]
# [http://www.linuxjournal.com/article/1363 what is multithreading?] [[vG]]
# [http://en.wikipedia.org/wiki/Thread_%28computer_science%29 type of threadings and multithreading in general] [[vG]]

COMP 3000 Essay 1 2010 Question 7

2010-10-14T19:35:18Z

Hirving: /* Design Choices */

=Question=

How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

=Answer=

A 'process' is defined to be "an address-space and a group of resources dedicated to running the program". On the other hand a 'thread' is an independent sequential unit of computation that executes within the context of a kernel supported entity like a 'process'. Threads are often classified by their “weight” , which corresponds to the amount of context that must be saved when a thread is removed from the processor, and restored when a thread is reinstated on a processor that is a context switch. The context for a process usually includes the hardware register, kernel stack, user-level stack, interrupt vectors, page tables,and more. Threads require less system resources then concurrent cooperating processes and start much easier therefore there may exist millions of them in a single process. Loosely based on this there are two major types of threads are kernel and user-mode. Kernel threads are usually considered more heavy and designs that involve them are not very scalable. User threads on the other hand are lightweight and are mapped to kernel threads. The ratio of the user threads to kernel threads is an important factor while designing scalable systems as will be seen below.

There are a few designs, mainly Fibers and UMS (User Mode Scheduling) which allow for very high scalability. UMS threads have their own context and resources. However, the ability to switch in the user mode makes them more efficient (depending on the application) than Thread Pools which are yet another mechanism that allows for high scalability. Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at. [[vG]] && [[Paul]] && [[Shane]] && [[Gautam]]
----

== Scalable Threads: The Problems ==

One of the basic challenges is to create code which is stable and at the same time scalable. Furthermore, the challenge in making an existing code base scalable is the identification and elimination of bottlenecks once scaled. Ray Bryant and John Hawkes found the following bottlenecks when porting Linux to a 64-core NUMA system. Each of these bottle necks is an example of a type of bottleneck that can appear in any program.

When expensive operations are '''needlessly called''' one type of bottleneck appears. In Linux there can be some instances of misplaced information in the cache that can cause a "'''cache-coherency operation'''" to be called. This operation is expensive compared to what would happen if the information was in the 'right place'. Once misplaced information that causes this problem all the time is identified it can be moved to limit the problem. Anywhere expensive operations are called a needless number of times this bottleneck can appear (this problem is not inherent, but is a result of bad-design).

Another type of bottleneck is from '''starvation.''' One such bottleneck is the xtime_lock in Linux. Having locking reading prevented writing to the timer value, causing the kernel to waste CPU time to keep trying. This problem was solved by using a lockless-read. This problem would appear anywhere that a thread must keep trying to execute, but cannot, leading to wasted CPU cycles.

The next type of bottleneck is from '''course-grained''' operations. Granularity refers to the execution time of a code segment. Both examples eat alot of CPU time, where a finer-grained implementation would eat less. The closer a segment is to the speed of an atomic action the finer its granularity. One course-grained bottleneck was the dcache_lock. It ate up some time in normal use, but it was also called in the much more popular dnotify_parent() function. That was an unacceptable state of affairs. So the dcache_lock strategy was replaced with a finer-grained strategy from a later implementation of linux. Another big course-grained bottleneck in the system is the "Big Kernel Lock" (BKL) linux's kernel synchronization control. Waiting for the BKL took up as much as 70% of the CPU time on a system with only 28 cores. The preferred method, on Linux NUMA systems, was to limit the BKL's usage. The ext2 and ext3 file systems were replaced with a file system that uses finer-grained locking (XFS), reducing the impact of the bottleneck. Both those examples are the result of course granularity.

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.
--[[Rannath]] A few additions--[[Gautam]]

'''MAIN POINT 2 Paragraph draft''' --[[User:Praubic|Praubic]] 00:21, 14 October 2010 (UTC) still in progress and debating

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 which 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. 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. 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. 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 ==
--[[User:Gautam|Gautam]] 00:29, 14 October 2010 (UTC) 
'''(A) Kernel Threads and User Threads (1:1 vs M:N) '''
This is the most basic design choice. The 1:1 boasts of a slim clean library interface on top of the kernel functions. Although, the M:N would implement a complicated library, it would offer advantages in areas of signal handling. A general consensus was that the M:N design was not compatible with the Linux kernel due to such a high cost for implementation. This gave birth to the 1:1 model.

''' (B)Signal Handling '''
The kernel implements the POSIX signal handling for use with the multitude of signal masks. Since the signal will only be sent to a thread if it is unblocked, no unnecessary interruptions through signals occur. The kernel is also in a much better situation to judge which is the best thread to receive the signal. This only holds true if the 1-on-1 model is used.

''' (C)Synchronization '''
The implementation of the synchronization primitives such as mutexes, read-write locks, conditional variables, semaphores, and barriers requires some form of kernel support. Busy waiting is not an option since threads can have different priorities (beside wasting CPU cycles). The same argument rules out the exclusive use of sched yield. Signals were the only viable solution for the old implementation. Threads would block in the kernel until woken by a signal. This method has severe drawbacks in terms of speed and reliability caused by spurious wakeups and derogation of the quality of the signal handling in the application. Fortunately, new functionality was added to the kernel to implement all kinds of synchronization.

Explaining the four types of synchronization:

*Mutex locks uses only a thread thus giving access to only certain part of the code
*Using Read/Write synchronization one can gain exclusive write and read access to protected resource but to edit the content it must have the exclusive write lock. Exclusive write lock is only permitted when all the read locks are released
*Condition variable synchronization protects the thread until the condition becomes true
*Counting semaphores delivers access to multiple threads. It has a count which keeps tracks of the number of threads can have concurrent access to the data. Once the limit is reached other threads are blocked until the limit changes.
[[vG]]
''' (D)Memory Management '''
Thread memory management is an important design choice when attempting to create a large amount of threads in a single process, from creation to maintenance and deallocation. A thread's data structure is made up of a program counter, a stack and a control block. A control block of a thread is needed for thread management as it contains the state data of a thread. The optimization of this data structure can greatly increase performance in large number of threads.

The creation of a thread can take place before the process actually requires it to run and wait until a idle processor becomes available to run the thread. Thread overhead (the required memory, CPU time, and read/write time to initialize the thread) is a problem that can arise with this creation process, since it frontloads the process. Another problem with this creation process is that the thread must allocate the memory required for it's stack at creation because it is expensive to dynamically allocate the stack memory. A way to optimize this creation process for large amounts of threads is to copy the arguments of the thread into it's control block, this allows for the thread's stack to be allocated at the thread's startup (when the thread starts being used) and not when the thread is created. When the thread enters startup it can copy it's arguments out of it's control block and allocate it's memory. Thread creation is ruled by latency (the cost of thread management on the system) and throughput (the rate that the system can create, start, and finish threads), and, if thread memory management is done in a serial processing manner, these two factor combine to create a maximum rate of thread creation.

Locks are an important part of the performance of threads and there are multiple way of controlling and creating locks in order to create a large amount of threads. Single lock (having the data structures all be in one lock) has the advantage that once the processor has acquired the lock it can modify any of the stored data. Using the single lock method means only one lock is needed per thread, decreasing the thread overhead but this also limits the throughput of the system. Multiple lock (having each data structure have it's own lock) has the advantage of that each action on the data structure is it's own locking/unlocking operations. Multiple has greater thread overhead (because there are more locks) but the thread throughput is much higher allowing for fast creation of threads. Another downside of multiple lock systems are deadlocks, a deadlock happens when two different threads are waiting for data that the other task holds. Single and multiple lock systems are the inverse of each other and using both depending on the situation can greatly increase the performance of a system.

The deallocation of a thread can also be optimized for use in increasing the scalability of threads. Storing deallocted stacks and control blocks in a free list allows the process of allocation and deallocation to be a list operation, if they are not stored in a free list then the thread overhead would include finding the correct size of free memory to store the stack. [http://portal.acm.org/citation.cfm?id=75378] [[hirving]]

''' (E)Scheduling Priorities '''
A thread is an entity that can be scheduled according to its scheduling priority which is a number ranging from 0 to 31 for Windows and a Red-Black Tree used by the CFS (Completely Fair Scheduler) in Linux. All threads are executed in a time splice assigned to them in round robin fashion and lower priority threads wait until the ones above finish performing their tasks. Threads are composed of thread context which internally breaks down into set of machine registers, the kernel and user stack all linked to the address space of the process where the thread resides. A context switch occurs as the time splice elapses and an equal (or higher) priority thread becomes available and it is responsible for allowing high scalability if it is efficiently implemented. For example fibers which are executed entirely in userspace do not require a system call during a switch which highly increases efficiency.[http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx][http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/], Microsoft (23 September 2010) --[[User:Praubic|Praubic]] 18:24, 13 October 2010 (UTC)

== References ==

COMP 3000 Essay 1 2010 Question 7

2010-10-14T19:17:31Z

Hirving: /* Design Choices */

=Question=

How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

=Answer=

Process is known as an instance of a program running in a computer which has its own resources such as address space, files, I/O devices and thread on the other hand is an independent task that executes in the same address space as other threads within a single process while sharing data synchronously and it can either execute the same code or a different code within the same application because it has its own state, run-time stack and execution context. Threads require less system resources then concurrent cooperating processes and start much easier therefore there may exist millions of them in a single process. The two major types of threads are kernel and user-mode. Kernel threads are usually considered more heavy and designs that involve them are not very scalable. User threads on the other hand, are mapped to kernel threads by the threads library such as libpthreads. There are a few designs that incorporate it, mainly Fibers and UMS (User Mode Scheduling) which allow for very high scalability. UMS threads have their own context and resources. However, the ability to switch in the user mode makes them more efficient (depending on the application) than Thread Pools which are yet another mechanism that allows for high scalability. Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at. [[vG]] && [[Paul]] && [[Shane]]

'''Taken the liberty to add Praubic's tentative first para. ''' and '''i have added my version to pauls and modified it [[vG]]'''

----

== Scalable Threads: The Problems ==

One of the basic challenges is to create code which is stable and at the same time scalable. Furthermore, the challenge in making an existing code base scalable is the identification and elimination of bottlenecks once scaled. Ray Bryant and John Hawkes found the following bottlenecks when porting Linux to a 64-core NUMA system. Each of these bottle necks is an example of a type of bottleneck that can appear in any program.

When expensive operations are '''needlessly called''' one type of bottleneck appears. In Linux there can be some instances of misplaced information in the cache that can cause a "'''cache-coherency operation'''" to be called. This operation is expensive compared to what would happen if the information was in the 'right place'. Once misplaced information that causes this problem all the time is identified it can be moved to limit the problem. Anywhere expensive operations are called a needless number of times this bottleneck can appear (this problem is not inherent, but is a result of bad-design).

Another type of bottleneck is from '''starvation.''' One such bottleneck is the xtime_lock in Linux. Having locking reading prevented writing to the timer value, causing the kernel to waste CPU time to keep trying. This problem was solved by using a lockless-read. This problem would appear anywhere that a thread must keep trying to execute, but cannot, leading to wasted CPU cycles.

The next type of bottleneck is from '''course-grained''' operations. Granularity refers to the execution time of a code segment. Both examples eat alot of CPU time, where a finer-grained implementation would eat less. The closer a segment is to the speed of an atomic action the finer its granularity. One course-grained bottleneck was the dcache_lock. It ate up some time in normal use, but it was also called in the much more popular dnotify_parent() function. That was an unacceptable state of affairs. So the dcache_lock strategy was replaced with a finer-grained strategy from a later implementation of linux. Another big course-grained bottleneck in the system is the "Big Kernel Lock" (BKL) linux's kernel synchronization control. Waiting for the BKL took up as much as 70% of the CPU time on a system with only 28 cores. The preferred method, on Linux NUMA systems, was to limit the BKL's usage. The ext2 and ext3 file systems were replaced with a file system that uses finer-grained locking (XFS), reducing the impact of the bottleneck. Both those examples are the result of course granularity.

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.
--[[Rannath]] A few additions--[[Gautam]]

'''MAIN POINT 2 Paragraph draft''' --[[User:Praubic|Praubic]] 00:21, 14 October 2010 (UTC) still in progress and debating

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 which 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. 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. 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. 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 ==
--[[User:Gautam|Gautam]] 00:29, 14 October 2010 (UTC) 
'''(A) Kernel Threads and User Threads (1:1 vs M:N) '''
This is the most basic design choice. The 1:1 boasts of a slim clean library interface on top of the kernel functions. Although, the M:N would implement a complicated library, it would offer advantages in areas of signal handling. A general consensus was that the M:N design was not compatible with the Linux kernel due to such a high cost for implementation. This gave birth to the 1:1 model.

''' (B)Signal Handling '''
The kernel implements the POSIX signal handling for use with the multitude of signal masks. Since the signal will only be sent to a thread if it is unblocked, no unnecessary interruptions through signals occur. The kernel is also in a much better situation to judge which is the best thread to receive the signal. This only holds true if the 1-on-1 model is used.

''' (C)Synchronization '''
The implementation of the synchronization primitives such as mutexes, read-write locks, conditional variables, semaphores, and barriers requires some form of kernel support. Busy waiting is not an option since threads can have different priorities (beside wasting CPU cycles). The same argument rules out the exclusive use of sched yield. Signals were the only viable solution for the old implementation. Threads would block in the kernel until woken by a signal. This method has severe drawbacks in terms of speed and reliability caused by spurious wakeups and derogation of the quality of the signal handling in the application. Fortunately, new functionality was added to the kernel to implement all kinds of synchronization.

Explaining the four types of synchronization:

*Mutex locks uses only a thread thus giving access to only certain part of the code
*Using Read/Write synchronization one can gain exclusive write and read access to protected resource but to edit the content it must have the exclusive write lock. Exclusive write lock is only permitted when all the read locks are released
*Condition variable synchronization protects the thread until the condition becomes true
*Counting semaphores delivers access to multiple threads. It has a count which keeps tracks of the number of threads can have concurrent access to the data. Once the limit is reached other threads are blocked until the limit changes.
[[vG]]
''' (D)Memory Management '''
Thread memory management is an important design choice when attempting to create a large amount of threads in a single process, from creation to maintenance and deallocation. A thread's data structure is made up of a program counter, a stack and a control block. A control block of a thread is needed for thread management as it contains the state data of a thread. The optimization of this data structure can greatly increase performance in large number of threads.

The creation of a thread can take place before the process actually requires it to run and wait until a idle processor becomes available to run the thread. Thread overhead (the required memory, CPU time, and read/write time to initialize the thread) is a problem that can arise with this creation process, since it frontloads the process. Another problem with this creation process is that the thread must allocate the memory required for it's stack at creation because it is expensive to dynamically allocate the stack memory. A way to optimize this creation process for large amounts of threads is to copy the arguments of the thread into it's control block, this allows for the thread's stack to be allocated at the thread's startup (when the thread starts being used) and not when the thread is created. When the thread enters startup it can copy it's arguments out of it's control block and allocate it's memory. Thread creation is ruled by latency (the cost of thread management on the system) and throughput (the rate that the system can create, start, and finish threads), and, if thread memory management is done in a serial processing manner, these two factor combine to create a maximum rate of thread creation.

The deallocation of a thread can also be optimized for use in increasing the scalability of threads. Storing deallocted stacks and control blocks in a free list allows the process of allocation and deallocation to be a list operation, if they are not stored in a free list then the thread overhead would include finding the correct size of free memory to store the stack. [http://portal.acm.org/citation.cfm?id=75378] [[hirving]]

''' (E)Scheduling Priorities '''
A thread is an entity that can be scheduled according to its scheduling priority which is a number ranging from 0 to 31 for Windows and a Red-Black Tree used by the CFS (Completely Fair Scheduler) in Linux. All threads are executed in a time splice assigned to them in round robin fashion and lower priority threads wait until the ones above finish performing their tasks. Threads are composed of thread context which internally breaks down into set of machine registers, the kernel and user stack all linked to the address space of the process where the thread resides. A context switch occurs as the time splice elapses and an equal (or higher) priority thread becomes available and it is responsible for allowing high scalability if it is efficiently implemented. For example fibers which are executed entirely in userspace do not require a system call during a switch which highly increases efficiency.[http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx][http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/], Microsoft (23 September 2010) --[[User:Praubic|Praubic]] 18:24, 13 October 2010 (UTC)

== References ==

COMP 3000 Essay 1 2010 Question 7

2010-10-14T12:31:51Z

Hirving: /* Design Choices */

=Question=

How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

=Answer=
A thread is an independent task that executes in the same address space as other threads within a single process while sharing data synchronously. Threads require less system resources then concurrent cooperating processes and start much easier therefore there may exist millions of them in a single process. The two major types of threads are kernel and user-mode. Kernel threads are usually considered more heavy and designs that involve them are not very scalable. User threads on the other hand, are mapped to kernel threads by the threads library such as libpthreads. There are a few designs that incorporate it, mainly Fibers and UMS (User Mode Scheduling) which allow for very high scalability. UMS threads have their own context and resources. However, the ability to switch in the user mode makes them more efficient (depending on the application) than Thread Pools which are yet another mechanism that allows for high scalability. 
'''Taken the liberty to add Praubic's tentative first para. No changes made as of yet.'''

I have the following... have your words or remove it if not needed:)

Systems can support millions within a single process by switching execution resources between threads, creating a concurrent execution. Concurrency is the result of multiple threads staying on the queues but is incapable of running them at the same time. It provides the impression that they are executing at the same time due to the speed they switch at.
[[vG]] Edited by : [[User:Spanke|Shane]]

----

== Scalable Threads: The Problems ==

One of the challenges in making an existing code base scalable is the identification and elimination of bottlenecks. When porting Linux to a 64-core NUMA system Ray Bryant and John Hawkes found the following bottlenecks (or just wrote a paper about them). Each of these bottle necks is an example of a type of bottleneck that can appear in any program.

When expensive operations are '''needlessly called''' one type of bottleneck appears. In Linux there can be some instances of misplaced information in the cache that can cause a "cache-coherency operation" to be called. This operation is expensive compared to what would happen if the information was in the 'right place'. Once misplaced information that causes this problem all the time is identified it can be moved to limit the problem. Anywhere where expensive operations are called a needless number of times this bottleneck can appear.

Another type of bottleneck is from '''starvation.''' One such bottleneck is the xtime_lock in Linux. Having locking reading prevented writing to the timer value, causing the kernel to waste CPU time to keep trying. This problem was solved by using a lockless-read. This problem would appear anywhere that a thread must keep trying to execute a thread that cannot execute.

The next type of bottleneck is from '''course-grained''' operations. Both example locks eat alot of CPU time, where a finer-grained implementation would eat less. Granularity refers to the execution time of a code segment. The closer a segment is to the speed of an atomic action the finer its granularity. One course-grained bottleneck was the dcache_lock. It ate up some time in normal use, but it was also called in the much more popular dnotify_parent() function. That was an unacceptable state of affairs. So the dcache_lock strategy was replaced with a finer-grained strategy from a later implementation of linux. Another big course-grained bottleneck in the system is the "Big Kernel Lock" (BKL) linux's kernel synchronization control. Waiting for the BKL took up as much as 70% of the CPU time on a system with only 28 cores. The preferred method, on Linux NUMA systems, was to limit the BKL's usage. The ext2 and ext3 file systems were replaced with a file system that uses finer-grained locking (XFS), reducing the impact of the bottleneck. Both those examples and others are the result of course granularity.

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, is was course-grained. While, the rest went into computing and recomputing information in the cache, a needless expensive operation. These problems were fixed by replacing the scheduler. That scheduler was then replaced by a more efficient scheduler [O(1) scheduler].

--[[Rannath]]

'''MAIN POINT 2 Paragraph draft''' --[[User:Praubic|Praubic]] 00:21, 14 October 2010 (UTC) still in progress and debating

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 which 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. This could turn out inefficient depending whether there are many related threads that could end up starving other processes.

Ok for point 2 -> I posted a draft on the essay page but Im not certain as to whether i should talk about fibers since they are also functioning on user space but theyre not UMS. --Praubic

== Design Choices ==
'''(A) Kernel Threads and User Threads (1:1 vs M:N) ''' --[[User:Gautam|Gautam]] 00:29, 14 October 2010 (UTC) 
This is the most basic design choice. The 1:1 boasts of a slim clean library interface on top of the kernel functions. Although, the M:N would implement a complicated library, it would offer advantages in areas of signal handling. A general consensus was that the M:N design was not compatible with the Linux kernel due to such a high cost for implementation. This gave birth to the 1:1 model.
''' (B)Signal Handling '''
The kernel implements the POSIX signal handling for use with the multitude of signal masks. Since the signal will only be sent to a thread if it is unblocked, no unnecessary interruptions through signals occur. The kernel is also in a much better situation to judge which is the best thread to receive the signal. This only holds true if the 1-on-1 model is used.

''' (C)Synchronization '''
The implementation of the synchronization primitives such as mutexes, read-write locks, conditional variables, semaphores, and barriers requires some form of kernel support. Busy waiting is not an option since threads can have different priorities (beside wasting CPU cycles). The same argument rules out the exclusive use of sched yield. Signals were the only viable solution for the old implementation. Threads would block in the kernel until woken by a signal. This method has severe drawbacks in terms of speed and reliability caused by spurious wakeups and derogation of the quality of the signal handling in the application. Fortunately, new functionality was added to the kernel to implement all kinds of synchronization.

Explaining the four types of synchronization:

*Mutex locks uses only a thread thus giving access to only certain part of the code
*Using Read/Write synchronization one can gain exclusive write and read access to protected resource but to edit the content it must have the exclusive write lock. Exclusive write lock is only permitted when all the read locks are released
*Condition variable synchronization protects the thread until the condition becomes true
*Counting semaphores delivers access to multiple threads. It has a count which keeps tracks of the number of threads can have concurrent access to the data. Once the limit is reached other threads are blocked until the limit changes.
[[vG]]
''' (D)Memory Management '''
Thread memory management is an important design choice when attempting to create a large amount of threads in a single process, from creation to maintenance and deallocation. A thread's data structure is made up of a program counter, a stack and a control block. A control block of a thread is needed for thread management as it contains the state data of a thread. The optimization of this data structure can greatly increase performance in large number of threads.

The creation of a thread can take place before the process actually requires it to run and wait until a idle processor becomes available to run the thread. Thread overhead (the required memory, CPU time, and read/write time to initialize the thread) is a problem that can arise with this creation process, since it frontloads the process. Another problem with this creation process is that the thread must allocate the memory required for it's stack at creation because it is expensive to dynamically allocate the stack memory. A way to optimize this creation process for large amounts of threads is to copy the arguments of the thread into it's control block, this allows for the thread's stack to be allocated at the thread's startup (when the thread starts being used) and not when the thread is created. When the thread enters startup it can copy it's arguments out of it's control block and allocate it's memory. Thread creation is ruled by latency (the cost of thread management on the system) and throughput (the rate that the system can create, start, and finish threads that are in contention), and, if thread memory management is done in a serial processing manner, these two factor combine to create a maximum rate of thread creation.

The deallocation of a thread can also be optimized for use in increasing the scalability of threads. Storing deallocted stacks and control blocks in a free list allows the process of allocation and deallocation to be a list operation, if they are not stored in a free list then the thread overhead would include finding the correct size of free memory to store the stack. [http://portal.acm.org/citation.cfm?id=75378] [[hirving]]
''' (E)Scheduling Priorities '''
A thread is an entity that can be scheduled according to its scheduling priority which is a number ranging from 0 to 31 for Windows and a Red-Black Tree used by the CFS (Completely Fair Scheduler) in Linux. All threads are executed in a time splice assigned to them in round robin fashion and lower priority threads wait until the ones above finish performing their tasks. Threads are composed of thread context which internally breaks down into set of machine registers, the kernel and user stack all linked to the address space of the process where the thread resides. A context switch occurs as the time splice elapses and an equal (or higher) priority thread becomes available and it is responsible for allowing high scalability if it is efficiently implemented. For example fibers which are executed entirely in userspace do not require a system call during a switch which highly increases efficiency. --[[User:Praubic|Praubic]] 18:24, 13 October 2010 (UTC)

== References ==

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-13T21:43:00Z

Hirving: /* Log */

== The Question ==
'''Original: '''
How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

'''Rannath: '''
The question seems to be about number and scalability of threads not the gross mechanics.

To be more clear: we can limit ourselves from the thread implementations to the thread scalability... ignore the stuff that required for all threads, unless its required for many threads. (I didn't find any implementations that required hardware)

I would also argue that since OSs have to run on multiple hardwares one cannot guarantee that unique/rare hardware bits will be there. While we can talk about hardware we should limit it to a mention at most. OR we could mention prospective hardware that could help out, but is not yet standard. It depends on whether we want to do "as it is" or "as it might be"

utility of such massively scalable thread implementations. I took this as: what functionality (of single strings) does one have to give up to make threads scalable.

'''Gautam: '''
I think the hardware is as relevant as the software. Not all things can be done in software and hardware support is an important factor in most of the solutions to many problems that OS face. My take.

'''Henry: '''
Since the question is about the system as a whole, I think the answer should include both software and hardware support for large amounts of threads. The questions revolves around how a system can handle millions of threads and what are the major factors that allow the system to do it. Also, the last part of the question seems to ask what this amount of threads allows a process to do.

'''Shane: '''
In response to the above's idea on the last part of the question, I would argue that it would enable fast execution because all threads that receive a cache miss would be picked up by the other threads so long as there was enough resources. Also the use of more threads would help synchronize the cache (through sharing) so that it would not miss. Of course this would be if they were assigned to the same task, you cannot sync threads running different applications it just wouldn't make sense. The only issue with this idea is the software must support this number.

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek <support.tamiltreasure@gmail.com>

Shane Panke <shanepanke@msn.com>

Henry Irving <sens.henry@gmail.com>

Paul Raubic <paul_raubic@hotmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: --[[User:Rannath|Rannath]]

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

== Log ==
Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

Moved around some info for clarity

everyone should post your interpretation of the question in simplest possible English so we`re on the same page (as someone, maybe me, seems to have the wrong idea about what we`re trying to talk about)

More moving for clarity
added an essay outline at bottom (feel free to change)
filled in the outline somewhat
added questions to the outline for everyone to think on.--[[User:Rannath|Rannath]]

First Draft for essay. Please modify and add on. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

Added to the memory management section. --[[User:Hirving|Hirving]] 21:42, 13 October 2010 (UTC)

 <Add your future activities here>

== Facts We have ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far we have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere
# least number (none if at all possible) of context switches per-thread - ''5''
# use of a "thread pool" - ''3''
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space. --[[User:Rannath|Rannath]]

----
These are all related ideas.

Ok, since we are discussing design choices maybe we could also elaborate on the two major types of threads. Here, I already wrote a few lines, source can be found in citation section:

''Fibers (user mode threads) provide very quick and efficient switching because there is no need for a system call and kernel is oblivious to a switch - allows for millions of user mode threads. ISSUES: Blocking system calls disables all other fibers.
On the other hand managing threads through the kernel requires context switch (between user and kernel mode) on creation and removal of a thread therefore programs with prodigious number of threads would suffer huge performance hits.--[[User:Praubic|Praubic]] 18:05, 10 October 2010 (UTC)''

User-mode scheduling (UMS) is a light-weight mechanism that applications can use to schedule their own threads. The ability to switch between threads in user mode makes UMS more efficient than thread pools for short-duration work items that require few system calls. [[Paul]]

One implementation of UMS is: combination of N:N and N:M, where the N:N relationship reveals N false processors to the user-space so the user can deal with scheduling on their own. ''5'' -[[Rannath]]

----

I would scrap the first two below, at most mention them...

#time-division multiplexing
#threads vs processes
#I/O Scheduling -[[vG]]

Splitting this off because I don't think it's technically part of the answer 
Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]

----
Things that we '''need''' to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
This is a '''need''' section 4 below is not '''needed''' 
(A)Design Decisions
1. Type of threading (1:1 1:N M:N)
2. Signal handling - we might be able to leave this out as it seems some "light weight" threads use no signals
3. Synchronisation
4. Memory Handling
5. Scheduling Priorities (context switching and how it affects the CPU threading process)[[Paul]]
----

Things we might want also to cover in the essay (non-essentials here): --[[User:Rannath|Rannath]] 04:43, 10 October 2010 (UTC) 
(A)Design Decisions
1. Brief History of threading
2. examples of attempts at getting absurd numbers of threads (failures)
3. other types of threading, including heavy weight and processes
4. Examples of systems that require many threads such as mainframe servers or banking client processing.--[[User:Praubic|Praubic]] 17:34, 11 October 2010 (UTC)

Here is an example of a design: (the topic asks for key design choices here is one)

Capriccio is a specific design for scalable user level threads. They are distinct from most designs by being independent of event based mechanisms as well as kernel thread models. They are very good choice for internet servers and this implementations could easily support 100,000 threads. They are characterized by high scalability, efficient stack management and scheduling based on resource usage however the performance is not comparable to event-based systems.--[[User:Praubic|Praubic]] 13:32, 12 October 2010 (UTC)

(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Essay Outline ==

#Thesis is an answer to the question so... that's the first step, or the last step, we can always present our info and make our thesis match the info.
#List all questions and points we have about the topic

Questions:
#What makes threads non-scalable? List the problems
#What utility do some scalable implementations lack? Why?
#Just how scalable does a full utility implementation get?

Answers:
#
# Signals, portability(maybe) both add overhead which would slow down threads
#
----

Intro (fill in info)
# Thesis
# main topics

----

Body (made of many main points)

Main Point 1 -[[Rannath]] 
- efficient thread creation/destruction is more scalable 
-- NPTL's improvements over LinuxThreads- primarily due to lower overhead of creation/destruction ''1''

Main Point 2 -[[Rannath]] 
- UMS & user-space threads are more scalable - maybe 
-- context switches are costly ''From class'' 
-- blocking locks have lower latency when twinned with a user space scheduler ''8''

Main Point 3 
- Certain bottleneck appear in scaled implementations, removing these improves scalability. 
-- "False cache-line sharing" ''14'' 
-- xtime lock to a lockless lock ''14''

Main Point 3.5 
Fine-Grain over course-grain 
-- "Big Kernel Lock" ''14'' 
-- dcache_lock ''14''

Link the Main points to the thesis

----

Conclusion
# restate info
# affirmation of thesis

Here is the first paragraph that I attempted. Please feel free to change or even delete it from here.

A thread is an independent task that executes in the same address space as other threads within a single process while sharing data synchronously. Threads require less system resources then concurrent cooperating processes and start much easier therefore there may exist millions of them in a single process. The two major types of threads are kernel and user-mode. Kernel threads are usually considered more heavy and designs that involve them are not very scalable User threads on the other hand are mapped to kernel threads by the threads library such as libpthreads. and there are a few designs that incorporate it mainly Fibers and UMS (User Mode Scheudling) which allow for very high scalability. UMS threads have their own context and resources however the ability to switch in the user mode makes them more efficient (depending on application) than Thread Pools which are yet another mechanism that allows for high scalability.
--[[User:Praubic|Praubic]] 19:04, 12 October 2010 (UTC)

----
I suggest that we start filling out the main points of the essay. We can discuss the intricacies as we go along. --[[User:Gautam|Gautam]] 02:46, 13 October 2010 (UTC)

== Sources ==

# Short history of threads in Linux and new implementation of them. [http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ] [[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)
# This paper discusses the design choices [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf Native POSIX Threads] [[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)
# lightweight threads vs kernel threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf PicoThreads: Lightweight Threads in Java] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# [http://eigenclass.org/http://homeostasis.scs.carleton.ca/wiki/index.php?title=Talk:COMP_3000_Essay_1_2010_Question_7&action=edit&section=7hiki/lightweight-threads-with-lwt Eigenclass Comparing lightweight threads] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# A lightwight thread implementation for Unix [http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf Implementing light weight threads] --[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC) [[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC)
#Not in this group, but I thought that this paper was excellent: [http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf Qthreads: An API for Programming with Millions of Lightweight Threads]
# Difference between single and multi threading [http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process] [[vG]]
# [http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler] --[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)
# Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading] --[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)
# This site provides in-depth info about threads, threads-pooling, scheduling: http://msdn.microsoft.com/en-us/library/ms684841(VS.85).aspx [[Paul]]
# Here is another site that outlines THREAD designs and techniques: http://people.csail.mit.edu/rinard/osnotes/h2.html [[Paul]]
# [http://www.cosc.brocku.ca/Offerings/4P13/slides/threads.ppt Interesting presentation: really worth checking out] [[Paul]]
# KERNEL vs USERMODE http://www.wordiq.com/definition/Thread_(computer_science)--[[User:Praubic|Praubic]] 18:06, 10 October 2010 (UTC)
# [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1.7621&rep=rep1&type=pdf#page=83 Scalability in linux]
# [http://hillside.net/plop/2007/papers/PLoP2007_Ahluwalia.pdf This has something to do with our question...]
# [http://msdn.microsoft.com/en-us/library/ms685100%28VS.85%29.aspx Scheduling Priorities (Windows)], Microsoft (23 September 2010) --[[User:Spanke|Shane]]
# [http://www.novell.com/coolsolutions/feature/14878.html Linux Scheduling Priorities Explained], Novell (11 October 2005) --[[User:Spanke|Shane]]
# [http://www.ibm.com/developerworks/linux/library/l-completely-fair-scheduler/ Inside the Linux 2.6 Completely Fair Scheduler], IBM (15 December 2009) --[[User:Spanke|Shane]]

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-13T21:42:48Z

Hirving: /* Log */

COMP 3000 Essay 1 2010 Question 7

2010-10-13T21:41:25Z

Hirving: /* Design Choices */

COMP 3000 Essay 1 2010 Question 7

2010-10-13T21:35:49Z

Hirving: /* Design Choices */

COMP 3000 Essay 1 2010 Question 7

2010-10-13T18:11:14Z

Hirving: /* Design Choices */

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-11T19:58:43Z

Hirving: /* Group 7 */

== The Question ==
'''Original: '''
How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

'''''For Paul: '''''
Please rephrase, you`re just restating the question.

'''Rannath: '''
The question seems to be about number and scalability of threads not the gross mechanics. I think we can safety limit ourselves to software-side only.

'''Paul: '''
Our topic contains 3 parts to it from what i see
# How is it possible for systems to supports millions of threads or more within a single process?
# What are the key design choices that make such systems work -
# and how do those choices affect the utility of such massively scalable thread implementations?
We need to find a way to split it between 5 people so everyone focuses primarily on one aspect.
If you guys don't mind Id like to discuss the format of our essay. [[Paul]]

'''Gautam: '''
I think the hardware is as relevant as the software. Not all things can be done in software and hardware support is an important factor in most of the solutions to many problems that OS face. My take.

'''Henry: '''
Since the question is about the system as a whole, I think the answer should include both software and hardware support for large amounts of threads. The questions revolves around how a system can handle millions of threads and what are the major factors that allow the system to do it. Also, the last part of the question seems to ask what this amount of threads allows a process to do.

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek <support.tamiltreasure@gmail.com>

Henry Irving <sens.henry@gmail.com>

Paul Raubic <paul_raubic@hotmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: --[[User:Rannath|Rannath]]

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

== Log ==
Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

Moved around some info for clarity

everyone should post your interpretation of the question in simplest possible English so we`re on the same page (as someone, maybe me, seems to have the wrong idea about what we`re trying to talk about)

More moving for clarity

added an essay outline at bottom (feel free to change)

filled in the outline somewhat

added questions to the outline for everyone to think on.--[[User:Rannath|Rannath]]

<Add your future activities here>

== Facts We have ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far we have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere
# least number (none if at all possible) of context switches per-thread - ''5''
# use of a "thread pool" - ''3''
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space. --[[User:Rannath|Rannath]]

Ok, since we are discussing design choices maybe we could also elaborate on the two major types of threads. Here, I already wrote a few lines, source can be found in citation section:

----
This is all one idea.

''Fibers (user mode threads) provide very quick and efficient switching because there is no need for a system call and kernel is oblivious to a switch - allows for millions of user mode threads. ISSUES: Blocking system calls disables all other fibers.
On the other hand managing threads through the kernel requires context switch (between user and kernel mode) on creation and removal of a thread therefore programs with prodigious number of threads would suffer huge performance hits.--[[User:Praubic|Praubic]] 18:05, 10 October 2010 (UTC)''

User-mode scheduling (UMS) is a light-weight mechanism that applications can use to schedule their own threads. The ability to switch between threads in user mode makes UMS more efficient than thread pools for short-duration work items that require few system calls. [[Paul]]

One implementation of UMS is: combination of N:N and N:M, where the N:N relationship reveals N false processors to the user-space so the user can deal with scheduling on their own. ''5'' -[[Rannath]]

----

#time-division multiplexing
#threads vs processes
#I/O Scheduling -[[vG]]

Splitting this off because I don't think it's technically part of the answer 
Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]

----
Things that we '''need''' to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
(A)Design Decisions
1. Type of threading (1:1 1:N M:N)
2. Signal handling - we might be able to leave this out as it seems some "light weight" threads use no signals
3. Synchronisation
4. Memory Handling
5. Scheduling Priorities (context switching and how it affects the CPU threading process)[[Paul]]
6. Examples of systems that require many threads such as mainframe servers or banking client processing.--[[User:Praubic|Praubic]] 17:34, 11 October 2010 (UTC)
----

----
Things we might want also to cover in the essay (non-essentials here): --[[User:Rannath|Rannath]] 04:43, 10 October 2010 (UTC) 
(A)Design Decisions
1. Brief History of threading
2. examples of attempts at getting absurd numbers of threads (failures)
3. other types of threading, including heavy weight and processes

(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Essay Outline ==

#Thesis is an answer to the question so... that's the first step, or the last step, we can always present our info and make our thesis match the info.
#List all questions and points we have about the topic

Questions:
#What makes threads non-scalable? List the problems
#What utility do some scalable implementations lack? Why?
#Just how scalable does a full utility implementation get?

Answers:
#
# Signals, portability(maybe) both add overhead which would slow down threads
#
----

Intro (fill in info)
# Thesis
# main topics

----

Body (made of many main points)

Main Point 1 -[[Rannath]] 
- efficient thread creation/destruction is more scalable 
-- NPTL's improvements over LinuxThreads- primarily due to lower overhead of creation/destruction ''1''

Main Point 2 -[[Rannath]] 
- UMS & user-space threads are more scalable 
-- context switches are costly ''From class'' 
-- blocking locks have lower latency when twinned with a user space scheduler ''8''

It is a good idea to avoid trying to create one (or even N) threads per client request. This approach is classically non-scalable and will definitely cause problems with memory usage or context switching. Using a thread pool approach instead and looking at the incoming requests as tasks for any thread in the pool to handle is more prefarable. The scalability of this approach is then limited by the ideal number of threads in the pool - usually this is related to the number of CPU cores. We want to try to have each thread use exactly 100% of the CPU on a single core - so in the ideal case we would have 1 thread per core, this will reduce context switching to zero. Depending on the nature of the tasks, this might not be possible, maybe the threads have to wait for external data, or read from disk or whatever so you may find that the number of threads is increased by some scaling factor.
--[[User:Praubic|Praubic]] 18:03, 11 October 2010 (UTC)

The question is how to support arbitrarily large numbers of threads, not if that's a good idea :P -[[Rannath]]

Link the Main points to the thesis

----

Conclusion
# restate info
# affirmation of thesis

== Sources ==

# Short history of threads in Linux and new implementation of them. [http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ] [[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)
# This paper discusses the design choices [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf Native POSIX Threads] [[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)
# lightweight threads vs kernel threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf PicoThreads: Lightweight Threads in Java] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# [http://eigenclass.org/hiki/lightweight-threads-with-lwt Eigenclass Comparing lightweight threads] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# A lightwight thread implementation for Unix [http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf Implementing light weight threads] --[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC) [[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC)
#Not in this group, but I thought that this paper was excellent: [http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf Qthreads: An API for Programming with Millions of Lightweight Threads]
# Difference between single and multi threading [http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process] [[vG]]
# [http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler] --[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)
# Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading] --[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)
# This site provides in-depth info about threads, threads-pooling, scheduling: http://msdn.microsoft.com/en-us/library/ms684841(VS.85).aspx [[Paul]]
# Here is another site that outlines THREAD designs and techniques: http://people.csail.mit.edu/rinard/osnotes/h2.html [[Paul]]
# [http://www.cosc.brocku.ca/Offerings/4P13/slides/threads.ppt Interesting presentation: really worth checking out] [[Paul]]
# KERNEL vs USERMODE http://www.wordiq.com/definition/Thread_(computer_science)--[[User:Praubic|Praubic]] 18:06, 10 October 2010 (UTC)

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-11T19:57:23Z

Hirving: /* The Question */

== The Question ==
'''Original: '''
How is it possible for systems to supports millions of threads or more within a single process? What are the key design choices that make such systems work - and how do those choices affect the utility of such massively scalable thread implementations?

'''''For Paul: '''''
Please rephrase, you`re just restating the question.

'''Rannath: '''
The question seems to be about number and scalability of threads not the gross mechanics. I think we can safety limit ourselves to software-side only.

'''Paul: '''
Our topic contains 3 parts to it from what i see
# How is it possible for systems to supports millions of threads or more within a single process?
# What are the key design choices that make such systems work -
# and how do those choices affect the utility of such massively scalable thread implementations?
We need to find a way to split it between 5 people so everyone focuses primarily on one aspect.
If you guys don't mind Id like to discuss the format of our essay. [[Paul]]

'''Gautam: '''
I think the hardware is as relevant as the software. Not all things can be done in software and hardware support is an important factor in most of the solutions to many problems that OS face. My take.

'''Henry: '''
Since the question is about the system as a whole, I think the answer should include both software and hardware support for large amounts of threads. The questions revolves around how a system can handle millions of threads and what are the major factors that allow the system to do it. Also, the last part of the question seems to ask what this amount of threads allows a process to do.

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek - support.tamiltreasure@gmail.com

Henry Irving <sens.henry@gmail.com>

Paul Raubic <paul_raubic@hotmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: --[[User:Rannath|Rannath]]

Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

== Log ==
Please maintain a log of your activities in the Log Section. So that we can keep track of the evolution of the essay. --[[User:Gautam|Gautam]]

Moved around some info for clarity

everyone should post your interpretation of the question in simplest possible English so we`re on the same page (as someone, maybe me, seems to have the wrong idea about what we`re trying to talk about)

More moving for clarity

added an essay outline at bottom (feel free to change)

filled in the outline somewhat

added questions to the outline for everyone to think on.--[[User:Rannath|Rannath]]

<Add your future activities here>

== Facts We have ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far we have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere
# least number (none if at all possible) of context switches per-thread - ''5''
# use of a "thread pool" - ''3''
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space. --[[User:Rannath|Rannath]]

Ok, since we are discussing design choices maybe we could also elaborate on the two major types of threads. Here, I already wrote a few lines, source can be found in citation section:

----
This is all one idea.

''Fibers (user mode threads) provide very quick and efficient switching because there is no need for a system call and kernel is oblivious to a switch - allows for millions of user mode threads. ISSUES: Blocking system calls disables all other fibers.
On the other hand managing threads through the kernel requires context switch (between user and kernel mode) on creation and removal of a thread therefore programs with prodigious number of threads would suffer huge performance hits.--[[User:Praubic|Praubic]] 18:05, 10 October 2010 (UTC)''

User-mode scheduling (UMS) is a light-weight mechanism that applications can use to schedule their own threads. The ability to switch between threads in user mode makes UMS more efficient than thread pools for short-duration work items that require few system calls. [[Paul]]

One implementation of UMS is: combination of N:N and N:M, where the N:N relationship reveals N false processors to the user-space so the user can deal with scheduling on their own. ''5'' -[[Rannath]]

----

#time-division multiplexing
#threads vs processes
#I/O Scheduling -[[vG]]

Splitting this off because I don't think it's technically part of the answer 
Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]

----
Things that we '''need''' to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
(A)Design Decisions
1. Type of threading (1:1 1:N M:N)
2. Signal handling - we might be able to leave this out as it seems some "light weight" threads use no signals
3. Synchronisation
4. Memory Handling
5. Scheduling Priorities (context switching and how it affects the CPU threading process)[[Paul]]
6. Examples of systems that require many threads such as mainframe servers or banking client processing.--[[User:Praubic|Praubic]] 17:34, 11 October 2010 (UTC)
----

----
Things we might want also to cover in the essay (non-essentials here): --[[User:Rannath|Rannath]] 04:43, 10 October 2010 (UTC) 
(A)Design Decisions
1. Brief History of threading
2. examples of attempts at getting absurd numbers of threads (failures)
3. other types of threading, including heavy weight and processes

(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Essay Outline ==

#Thesis is an answer to the question so... that's the first step, or the last step, we can always present our info and make our thesis match the info.
#List all questions and points we have about the topic

Questions:
#What makes threads non-scalable? List the problems
#What utility do some scalable implementations lack? Why?
#Just how scalable does a full utility implementation get?

Answers:
#
# Signals, portability(maybe) both add overhead which would slow down threads
#
----

Intro (fill in info)
# Thesis
# main topics

----

Body (made of many main points)

Main Point 1 -[[Rannath]] 
- efficient thread creation/destruction is more scalable 
-- NPTL's improvements over LinuxThreads- primarily due to lower overhead of creation/destruction ''1''

Main Point 2 -[[Rannath]] 
- UMS & user-space threads are more scalable 
-- context switches are costly ''From class'' 
-- blocking locks have lower latency when twinned with a user space scheduler ''8''

It is a good idea to avoid trying to create one (or even N) threads per client request. This approach is classically non-scalable and will definitely cause problems with memory usage or context switching. Using a thread pool approach instead and looking at the incoming requests as tasks for any thread in the pool to handle is more prefarable. The scalability of this approach is then limited by the ideal number of threads in the pool - usually this is related to the number of CPU cores. We want to try to have each thread use exactly 100% of the CPU on a single core - so in the ideal case we would have 1 thread per core, this will reduce context switching to zero. Depending on the nature of the tasks, this might not be possible, maybe the threads have to wait for external data, or read from disk or whatever so you may find that the number of threads is increased by some scaling factor.
--[[User:Praubic|Praubic]] 18:03, 11 October 2010 (UTC)

The question is how to support arbitrarily large numbers of threads, not if that's a good idea :P -[[Rannath]]

Link the Main points to the thesis

----

Conclusion
# restate info
# affirmation of thesis

== Sources ==

# Short history of threads in Linux and new implementation of them. [http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ] [[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)
# This paper discusses the design choices [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.93.6590&rep=rep1&type=pdf Native POSIX Threads] [[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)
# lightweight threads vs kernel threads [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf PicoThreads: Lightweight Threads in Java] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# [http://eigenclass.org/hiki/lightweight-threads-with-lwt Eigenclass Comparing lightweight threads] --[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)
# A lightwight thread implementation for Unix [http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf Implementing light weight threads] --[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC) [[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC)
#Not in this group, but I thought that this paper was excellent: [http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf Qthreads: An API for Programming with Millions of Lightweight Threads]
# Difference between single and multi threading [http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process] [[vG]]
# [http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler] --[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)
# Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading] --[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)
# This site provides in-depth info about threads, threads-pooling, scheduling: http://msdn.microsoft.com/en-us/library/ms684841(VS.85).aspx [[Paul]]
# Here is another site that outlines THREAD designs and techniques: http://people.csail.mit.edu/rinard/osnotes/h2.html [[Paul]]
# [http://www.cosc.brocku.ca/Offerings/4P13/slides/threads.ppt Interesting presentation: really worth checking out] [[Paul]]
# KERNEL vs USERMODE http://www.wordiq.com/definition/Thread_(computer_science)--[[User:Praubic|Praubic]] 18:06, 10 October 2010 (UTC)

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-07T21:24:45Z

Hirving: /* Sources */

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek - support.tamiltreasure@gmail.com

Henry Irving <sens.henry@gmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: -Rannath

== Essay Rough ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far I have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# least number (none if at all possible) of context switches per-thread - some linux implementation --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# use of a "thread pool" - java picothreads article --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
#Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space.--[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

----
Things that we need to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
(A)Design Decisions
1. Type of threading (1:1 M:N)
2. Signal handling
3. Synchronisation
4. Memory Handling
(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Sources ==

Short history of threads in Linux and new implementation of them.
[http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ]
[[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)

This paper discusses the design choices [http://people.redhat.com/drepper/nptl-design.pdf. Native POSIX Threads]
[[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)

A paper with low-footprint(lightweight) threads vs kernel threads (for Java :( )
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

A comparison of lightweight threads
http://eigenclass.org/hiki/lightweight-threads-with-lwt
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

A lightwight thread implementation for Unix
http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf
--[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC)

[[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC) Not in this group, but I thought that this paper was excellent: http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf

Difference between single and multi threading
http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process
[[vG]

[http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler]
--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)

Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading] --[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-07T21:24:02Z

Hirving: /* Sources */

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek - support.tamiltreasure@gmail.com

Henry Irving <sens.henry@gmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: -Rannath

== Essay Rough ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far I have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# least number (none if at all possible) of context switches per-thread - some linux implementation --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# use of a "thread pool" - java picothreads article --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
#Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space.--[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

----
Things that we need to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
(A)Design Decisions
1. Type of threading (1:1 M:N)
2. Signal handling
3. Synchronisation
4. Memory Handling
(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Sources ==

Short history of threads in Linux and new implementation of them.
[http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ]
[[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)

This paper discusses the design choices [http://people.redhat.com/drepper/nptl-design.pdf. Native POSIX Threads]
[[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)

A paper with low-footprint(lightweight) threads vs kernel threads (for Java :( )
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

A comparison of lightweight threads
http://eigenclass.org/hiki/lightweight-threads-with-lwt
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

A lightwight thread implementation for Unix
http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf
--[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC)

[[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC) Not in this group, but I thought that this paper was excellent: http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf

Difference between single and multi threading
http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process
[[vG]

[http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler]
--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)

Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading]--[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-07T21:21:53Z

Hirving: /* Sources */

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek - support.tamiltreasure@gmail.com

Henry Irving <sens.henry@gmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: -Rannath

== Essay Rough ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far I have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# least number (none if at all possible) of context switches per-thread - some linux implementation --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# use of a "thread pool" - java picothreads article --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
#Multithreading generally occurs by time-division multiplexing. It makes it possible for the processor to switch between different threads but it happens so fast that the user sees it as it is running at the same time. [[User:vG]]
The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space.--[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

----
Things that we need to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
(A)Design Decisions
1. Type of threading (1:1 M:N)
2. Signal handling
3. Synchronisation
4. Memory Handling
(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Sources ==

A Webpage. However found it really interesting.
[http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ]
[[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)

This paper discusses the design choices [http://people.redhat.com/drepper/nptl-design.pdf. Native POSIX Threads]
[[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)

A paper with low-footprint(lightweight) threads vs kernel threads (for Java :( )
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

A comparison of lightweight threads
http://eigenclass.org/hiki/lightweight-threads-with-lwt
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

A lightwight thread implementation for Unix
http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf
--[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC)

[[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC) Not in this group, but I thought that this paper was excellent: http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf

Difference between single and multi threading
http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process
[[vG]

[http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler]
--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)

Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading]--[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-07T20:05:09Z

Hirving: /* Essay Rough */

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek - support.tamiltreasure@gmail.com

Henry Irving <sens.henry@gmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: -Rannath

== Essay Rough ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far I have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# least number (none if at all possible) of context switches per-thread - some linux implementation --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# use of a "thread pool" - java picothreads article --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space.--[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

----
Things that we need to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
(A)Design Decisions
1. Type of threading (1:1 M:N)
2. Signal handling
3. Synchronisation
4. Memory Handling
(B)Kernel
1. Program Thread manipulation through system calls --[[User:Hirving|Hirving]] 20:05, 7 October 2010 (UTC)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Sources ==

A Webpage. However found it really interesting.
[http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ]
[[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)

This paper discusses the design choices [http://people.redhat.com/drepper/nptl-design.pdf. Native POSIX Threads]
[[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)

A paper with low-footprint(lightweight) threads vs kernel threads (for Java :( )
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

a comparison of lightweight threads
http://eigenclass.org/hiki/lightweight-threads-with-lwt
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

a lightwight thread implementation for Unix
http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf
--[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC)

[[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC) Not in this group, but I thought that this paper was excellent: http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf

Difference between single and multi threading
http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process
[[vG]

[http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler]
--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)

Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading]--[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-07T19:58:54Z

Hirving: /* Sources */

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek - support.tamiltreasure@gmail.com

Henry Irving <sens.henry@gmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: -Rannath

== Essay Rough ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far I have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# least number (none if at all possible) of context switches per-thread - some linux implementation --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# use of a "thread pool" - java picothreads article --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space.--[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

----
Things that we need to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
(A)Design Decisions
1. Type of threading (1:1 M:N)
2. Signal handling
3. Synchronisation
4. Memory Handling
(B)Kernel (?)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Sources ==

A Webpage. However found it really interesting.
[http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ]
[[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)

This paper discusses the design choices [http://people.redhat.com/drepper/nptl-design.pdf. Native POSIX Threads]
[[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)

A paper with low-footprint(lightweight) threads vs kernel threads (for Java :( )
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

a comparison of lightweight threads
http://eigenclass.org/hiki/lightweight-threads-with-lwt
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

a lightwight thread implementation for Unix
http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf
--[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC)

[[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC) Not in this group, but I thought that this paper was excellent: http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf

Difference between single and multi threading
http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process
[[vG]

[http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler]
--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)

Research Group working on Simultaneous Multithreading [http://www.cs.washington.edu/research/smt/ Simultaneous Multithreading]--[[User:Hirving|Hirving]] 19:58, 7 October 2010 (UTC)

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-07T19:55:56Z

Hirving: /* Essay Rough */

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek - support.tamiltreasure@gmail.com

Henry Irving <sens.henry@gmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: -Rannath

== Essay Rough ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far I have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# least number (none if at all possible) of context switches per-thread - some linux implementation --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# use of a "thread pool" - java picothreads article --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space.--[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

----
Things that we need to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
(A)Design Decisions
1. Type of threading (1:1 M:N)
2. Signal handling
3. Synchronisation
4. Memory Handling
(B)Kernel (?)

(C)Hardware --[[User:Hirving|Hirving]] 19:55, 7 October 2010 (UTC)
1. Simultaneous Multithreading
2. Multi-core processors

== Sources ==

A Webpage. However found it really interesting.
[http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ]
[[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)

This paper discusses the design choices [http://people.redhat.com/drepper/nptl-design.pdf. Native POSIX Threads]
[[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)

A paper with low-footprint(lightweight) threads vs kernel threads (for Java :( )
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

a comparison of lightweight threads
http://eigenclass.org/hiki/lightweight-threads-with-lwt
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

a lightwight thread implementation for Unix
http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf
--[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC)

[[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC) Not in this group, but I thought that this paper was excellent: http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf

Difference between single and multi threading
http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process
[[vG]

[http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler]
--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)

Talk:COMP 3000 Essay 1 2010 Question 7

2010-10-07T19:46:48Z

Hirving: /* Group 7 */

== Group 7 ==

Let us start out by listing down our names and email id (preffered).

Gautam Akiwate <gautam.akiwate@gmail.com>

Patrick Young(rannath) <rannath@gmail.com>

vG Vivek - support.tamiltreasure@gmail.com

Henry Irving <sens.henry@gmail.com>

== Guidelines ==

Raw info should have some indication of where you got it for citation.

Claim your info so we don't need to dig for who got what when we need clarification.

Feel free to provide info for or edit someone else's info, just keep their signature so we can discuss changes

sign changes (once) preferably without time stamps Ex: -Rannath

== Essay Rough ==
Start by placing the info here so we can sort through it. I'm going to go into full research/essay writing mode on Sunday if there isn't enough here.

So far I have:
Three design choices I've seen:
# Smallest possible footprint per-thread (being extremely light weight) - from everywhere --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# least number (none if at all possible) of context switches per-thread - some linux implementation --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)
# use of a "thread pool" - java picothreads article --[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

The idea is to reduce processor time and storage needed per-thread so you can have more in the same amount of space.--[[User:Rannath|Rannath]] 00:28, 7 October 2010 (UTC)

----
Things that we need to cover in the essay:--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC) 
(A)Design Decisions
1. Type of threading (1:1 M:N)
2. Signal handling
3. Synchronisation
4. Memory Handling
(B)Kernel (?)

== Sources ==

A Webpage. However found it really interesting.
[http://www.drdobbs.com/open-source/184406204;jsessionid=3MRSO5YMO1QVRQE1GHRSKHWATMY32JVN NPTL: The New Implementation of Threads for Linux ]
[[User:Gautam|Gautam]] 22:18, 5 October 2010 (UTC)

This paper discusses the design choices [http://people.redhat.com/drepper/nptl-design.pdf. Native POSIX Threads]
[[User:Gautam|Gautam]] 22:11, 5 October 2010 (UTC)

A paper with low-footprint(lightweight) threads vs kernel threads (for Java :( )
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.32.9043&rep=rep1&type=pdf
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

a comparison of lightweight threads
http://eigenclass.org/hiki/lightweight-threads-with-lwt
--[[User:Rannath|Rannath]] 00:23, 6 October 2010 (UTC)

a lightwight thread implementation for Unix
http://www.usenix.org/publications/library/proceedings/sa92/stein.pdf
--[[User:Rannath|Rannath]] 00:49, 6 October 2010 (UTC)

[[User:Gbint|Gbint]] 19:50, 5 October 2010 (UTC) Not in this group, but I thought that this paper was excellent: http://www.sandia.gov/~rcmurph/doc/qt_paper.pdf

Difference between single and multi threading
http://wiki.answers.com/Q/Single_threaded_Process_and_Multi-threaded_Process
[[vG]

[http://hdl.handle.net/1853/6804 Implementation of Scalable Blocking Locks using an Adaptative Thread Scheduler]
--[[User:Gautam|Gautam]] 19:35, 7 October 2010 (UTC)