Soma-notes - User contributions [en]

Talk:COMP 3000 Essay 2 2010 Question 5

2010-11-27T19:04:09Z

Afranco2:

Maybe we can all add our names below so we know who's still in this course? --[[User:Myagi|Myagi]] 12:38, 14 November 2010 (UTC)

Group members:

* Michael Yagi
* Nicolas Lessard
* Julie Powers
* Derek Langlois
* Dustin Martin

Jeffrey Francom contacted me earlier so I know he is also still in the course. <strike>Now we are only waiting on Dustin Martin.</strike> Everyone has been accounted for. [[User:J powers|J powers]] 18:07, 15 November 2010 (UTC)

Just kicking things off. Feel free to make suggestions or change anything. --[[User:Myagi|Myagi]] 11:36, 17 November 2010 (UTC)

Edited and filled out the critique section. Edited a little bit here and there. --[[User:Afranco2|Afranco2]] 17:41, 22 November 2010 (UTC)

Moved stuff to the front page and cleaned up references. Still waiting for people to expand if possible. Also, spellcheck ;) --[[User:Myagi|Myagi]] 10:37, 24 November 2010 (UTC)

Expanded --[[User:Afranco2|Afranco2]] 19:04, 27 November 2010 (UTC)

==Essay==
===Paper===
<blockquote>The paper's title, authors, and their affiliations. Include a link to the paper and any particularly helpful supplementary information.</blockquote>
* Title: [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]
* Authors: Jingyue Wu, Heming Cui, Junfeng Yang
* Affiliations: Computer Science Department, Columbia University
* Supplementary Information: [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 Video], [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf Slides]

===Background Concepts===
<blockquote>Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.</blockquote>

-------------
A race condition is a system flaw that “occurs when two threads access a shared variable at the same time." Race conditions can be very complex, time consuming and expensive to fix. Unfortunately, the most challenging part of race condition is not fixing it, but rather find it. Race conditions are notorious for being extremely difficult to find, isolate and recreate. To help ease this process, the authors of this paper, Jingyue Wu, Heming Cui, Junfeng Yang, propose the adoption of LOOM.

LOOM is a system which dynamically locates and corrects areas which may be susceptible to race condition errors. The power of LOOM rests in its ability to operate on live applications in real time. This is possible thanks to its evacuation algorithm which injects execution filters to fix race conditions at runtime. Execution filters, otherwise known as request filtering, allow you to inspect the request before and after the main logic is executed. By leveraging execution filters as the means for correcting race conditions, LOOM is able to operate with very little performance overhead and is a highly scalable as the number of application threads increases.

The authors tested LOOM on existing real world race conditions found in common applications. The tests found that all tested race conditions were solved, with little performance overhead, in a scalable and easy to implement manor.
-------------

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

* Race Condition: "A race condition occurs when two threads access a shared variable at the same time." [http://support.microsoft.com/kb/317723 Race Condition]
* Execution Filters: Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.
* Hot Patches: "Hot patching provides a mechanism to update system files without rebooting or stopping services and processes."[http://technet.microsoft.com/en-us/library/cc781109%28WS.10%29.aspx Hot Patching]
* Hybrid Instrumentation Engine: "Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information." [http://msdn.microsoft.com/en-us/library/aa983649%28VS.71%29.aspx Instrumentation] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.
* Lock: A lock is a way of limiting access to a common resource when using multiple threads. Lock and unlock methods are usually called at the beginning and end of a target method, respectively. "Mutual exclusion locks (mutexes) are a common method of serializing thread execution. Mutual exclusion locks synchronize threads, usually by ensuring that only one thread at a time executes a critical section of code. Mutex locks can also preserve single-threaded code." [http://www.cs.cf.ac.uk/Dave/C/node31.html#SECTION003110000000000000000 Mutex Locks]
* Mutex: Unable to be both true at the same time.
* Semaphore: "A semaphore is a protected variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel programming environment." [http://en.wikipedia.org/wiki/Semaphore_%28programming%29 Semaphore]

===Research problem===
<blockquote>What is the research problem being addressed by the paper? How does this problem relate to past related work?</blockquote>
====Problem being addressed====
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
====Past related work====
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.
===Contribution===
<blockquote>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?)</blockquote>
====Current solution expressed====
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

-------------
====Why is it any better than what came before?====
Previously, the two standard ways of fixing deployed race conditions were system updates and hot patches. LOOM is a superior choice to both these options for a number of reasons.

Unlike LOOM, the system update approach requires that the system be rebooted before the fix can be implemented. With desktop applications, this can sometimes be considered acceptable. However, server applications often do not have the luxury of being able to reboot because requests are coming from external sources and are expected to be processed.

While hot patches do not require a system reboot, they do have their own specific vulnerabilities. Namely, it is very difficult to apply a patch that corrects the error, or errors, but leaves the rest of the system unaffected. Often when correcting a race condition via a hot patch, others can appear. The main concern with hot patches however, is that their development is a time consuming process. A process which until developed and deployed, leaves the race condition vulnerable and exposed. The paper chronicles a real world Mozilla race condition whose hot patch took nearly 8 years of development to correct, all the while the vulnerability was exposed to all Mozilla users.

Flaws common to both the system update and hot patch approach are they very difficult to properly development, slow to implement, and result in potential unsafe ad hoc solutions that are not scalable. Conversely, LOOM is easy to use, fast to implement, highly flexible, scalable, and safe to use.
-------------

===Critique===
<blockquote>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.</blockquote>
====Good====
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up thier topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnessicary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delievered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explination) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

====Not-So-Good====
One of the problems with this paper is that although many of the examples are simplified in order to expediate the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunatly, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

===References===
<blockquote>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.</blockquote>

COMP 3000 Essay 2 2010 Question 5

2010-11-27T19:03:20Z

Afranco2: /* Related work */

==Paper==
'''Title:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]

'''Authors:''' Jingyue Wu, Heming Cui, Junfeng Yang

'''Affiliations:''' Computer Science Department, Columbia University

'''Supplementary Information:''' Video available [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 here] as well as [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf slides]

==Background Concepts==
A race condition is a system flaw that “occurs when two threads access a shared variable at the same time." Race conditions can be very complex, time consuming and expensive to fix. Unfortunately, the most challenging part of race condition is not fixing it, but rather find it. Race conditions are notorious for being extremely difficult to find, isolate and recreate. To help ease this process, the authors of this paper, Jingyue Wu, Heming Cui, Junfeng Yang, propose the adoption of LOOM.

LOOM is a system which dynamically locates and corrects areas which may be susceptible to race condition errors. The power of LOOM rests in its ability to operate on live applications in real time. This is possible thanks to its evacuation algorithm which injects execution filters to fix race conditions at runtime. Execution filters, otherwise known as request filtering, allow you to inspect the request before and after the main logic is executed. By leveraging execution filters as the means for correcting race conditions, LOOM is able to operate with very little performance overhead and is a highly scalable as the number of application threads increases.

The authors tested LOOM on existing real world race conditions found in common applications. The tests found that all tested race conditions were solved, with little performance overhead, in a scalable and easy to implement manor.

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

'''Deadlock:''' Deadlocks usually occur within the context of two threads. One thread tries to lock a variable that the other thread has already locked and vice versa. The result of this is that each thread is waiting for each others thread to release the variable. Thus a deadlock occurs and nothing can happen.

'''Evacuation''' The process of proactively pausing and changing states of code sections so that those sections can be filtered for proper processing

'''Execution Filters:''' Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.

'''Function Quiescence''' The process of pausing and altering states, in order to avoid race conditions and overlapping between code segments.

'''Hot Patches:''' "Hot patching provides a mechanism to update system files without rebooting or stopping services and processes."[[#References | [1]]]

'''Hybrid Instrumentation Engine:''' "Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information." [[#References | [2]]] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.

'''Lock:''' A lock is a way of limiting access to a common resource when using multiple threads. Lock and unlock methods are usually called at the beginning and end of a target method, respectively. "Mutual exclusion locks (mutexes) are a common method of serializing thread execution. Mutual exclusion locks synchronize threads, usually by ensuring that only one thread at a time executes a critical section of code. Mutex locks can also preserve single-threaded code." [[#References | [3]]]

'''Mutex:''' Unable to be both true at the same time.

'''Race Condition:''' "A race condition occurs when two threads access a shared variable at the same time." [[#References | [4]]]

'''Semaphore:''' Semaphores are basically a special type of flag and generalize a down and up state(sleep or wakeup). The down operation checks to see if the value is greater than 0 and if so, decrements the value and uses up one stored wakeup. If the value is 0, the process is put to sleep. These steps are all done in a single indivisible atomic action. It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has been completed or blocked. Semaphores are an essential part of solving synchronization problems. [[#References | [5]]]

==Research problem==
===Problem being addressed===
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
===Related work===
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.

Using a QUIESCE function to "temporarily suspend...incoming messages on an IUCV path"[[#References | [6]]] These paths can later be reactivated and run as normal. This is not an efficient for of fixing a race condition because it only delays the problem in an attempt to avoid conflict. Although this does allow for a certain extent of safety it does not come near the reliability and flexibility of LOOM. Speed, reliability, flexibility and ease of use are all areas in which LOOM is demonstrated as being better than a QUIESCE function.

==Contribution==
===Current solution expressed===
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

Through multiple tests LOOM proves its worth. Overhead is tested in a comparison of LOOM during normal runtime. The effects of LOOM on Apache and MySQL are minimal, (~1.83% and ~4% respectively) making it an obvious choice as a runtime fix for race errors. To test scalability the team discovered that on 32 server threads, the over head was still under 3% and 12% respectively. Reliability is one of the strongest facets of the LOOM system. It fixed all of the race condition errors that it was tested against, proving that it has immense power as a reliable form of fix. To assure reliability LOOM was paired against a conventional restart-based software update. In this test the software update was clearly slower, requiring time to reset itself, where LOOM running a live update had almost no effect on the throughput. Lastly the timeliness of LOOM was demonstrated using a simple example, showing a LOOM based fix in 368ms whereas the function quiescence fix took the max test time (1 hour) and still did not finish.

==Critique==
===Good===
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up their topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnecessary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delivered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explanation) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

===Not-So-Good===
One of the problems with this paper is that although many of the examples are simplified in order to expedite the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunately, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

==References==
[1] Introduction to Hotpatching. [http://technet.microsoft.com/en-us/library/cc781109%28WS.10%29.aspx http://technet.microsoft.com/en-us/library/cc781109(WS.10).aspx].

[2] Introduction to Instrumentation and Tracing. [http://msdn.microsoft.com/en-us/library/aa983649%28VS.71%29.aspx http://msdn.microsoft.com/en-us/library/aa983649(VS.71).aspx]

[3] A. D. Marshall. Further Threads Programming:Synchronization. Cardiff University, 1999 [http://www.cs.cf.ac.uk/Dave/C/node31.html#SECTION003110000000000000000 HTML]

[4] Description of race conditions and deadlocks. [http://support.microsoft.com/kb/317723 http://support.microsoft.com/kb/317723]

[5] A. S. Tanenbaum. Modern Operating Systems (3rd Edition), page 128, 2008

[6] QUIESCE Function. IBM [http://publib.boulder.ibm.com/infocenter/zvm/v5r3/index.jsp?topic=/com.ibm.zvm.v53.hcpb4/hcse5b21270.htm]

COMP 3000 Essay 2 2010 Question 5

2010-11-27T19:02:19Z

Afranco2: /* References */

==Paper==
'''Title:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]

'''Authors:''' Jingyue Wu, Heming Cui, Junfeng Yang

'''Affiliations:''' Computer Science Department, Columbia University

'''Supplementary Information:''' Video available [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 here] as well as [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf slides]

==Background Concepts==
A race condition is a system flaw that “occurs when two threads access a shared variable at the same time." Race conditions can be very complex, time consuming and expensive to fix. Unfortunately, the most challenging part of race condition is not fixing it, but rather find it. Race conditions are notorious for being extremely difficult to find, isolate and recreate. To help ease this process, the authors of this paper, Jingyue Wu, Heming Cui, Junfeng Yang, propose the adoption of LOOM.

LOOM is a system which dynamically locates and corrects areas which may be susceptible to race condition errors. The power of LOOM rests in its ability to operate on live applications in real time. This is possible thanks to its evacuation algorithm which injects execution filters to fix race conditions at runtime. Execution filters, otherwise known as request filtering, allow you to inspect the request before and after the main logic is executed. By leveraging execution filters as the means for correcting race conditions, LOOM is able to operate with very little performance overhead and is a highly scalable as the number of application threads increases.

The authors tested LOOM on existing real world race conditions found in common applications. The tests found that all tested race conditions were solved, with little performance overhead, in a scalable and easy to implement manor.

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

'''Deadlock:''' Deadlocks usually occur within the context of two threads. One thread tries to lock a variable that the other thread has already locked and vice versa. The result of this is that each thread is waiting for each others thread to release the variable. Thus a deadlock occurs and nothing can happen.

'''Evacuation''' The process of proactively pausing and changing states of code sections so that those sections can be filtered for proper processing

'''Execution Filters:''' Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.

'''Function Quiescence''' The process of pausing and altering states, in order to avoid race conditions and overlapping between code segments.

'''Hot Patches:''' "Hot patching provides a mechanism to update system files without rebooting or stopping services and processes."[[#References | [1]]]

'''Hybrid Instrumentation Engine:''' "Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information." [[#References | [2]]] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.

'''Lock:''' A lock is a way of limiting access to a common resource when using multiple threads. Lock and unlock methods are usually called at the beginning and end of a target method, respectively. "Mutual exclusion locks (mutexes) are a common method of serializing thread execution. Mutual exclusion locks synchronize threads, usually by ensuring that only one thread at a time executes a critical section of code. Mutex locks can also preserve single-threaded code." [[#References | [3]]]

'''Mutex:''' Unable to be both true at the same time.

'''Race Condition:''' "A race condition occurs when two threads access a shared variable at the same time." [[#References | [4]]]

'''Semaphore:''' Semaphores are basically a special type of flag and generalize a down and up state(sleep or wakeup). The down operation checks to see if the value is greater than 0 and if so, decrements the value and uses up one stored wakeup. If the value is 0, the process is put to sleep. These steps are all done in a single indivisible atomic action. It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has been completed or blocked. Semaphores are an essential part of solving synchronization problems. [[#References | [5]]]

==Research problem==
===Problem being addressed===
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
===Related work===
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.

Using a QUIESCE function to "temporarily suspend...incoming messages on an IUCV path" These paths can later be reactivated and run as normal. This is not an efficient for of fixing a race condition because it only delays the problem in an attempt to avoid conflict. Although this does allow for a certain extent of safety it does not come near the reliability and flexibility of LOOM. Speed, reliability, flexibility and ease of use are all areas in which LOOM is demonstrated as being better than a QUIESCE function.

==Contribution==
===Current solution expressed===
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

Through multiple tests LOOM proves its worth. Overhead is tested in a comparison of LOOM during normal runtime. The effects of LOOM on Apache and MySQL are minimal, (~1.83% and ~4% respectively) making it an obvious choice as a runtime fix for race errors. To test scalability the team discovered that on 32 server threads, the over head was still under 3% and 12% respectively. Reliability is one of the strongest facets of the LOOM system. It fixed all of the race condition errors that it was tested against, proving that it has immense power as a reliable form of fix. To assure reliability LOOM was paired against a conventional restart-based software update. In this test the software update was clearly slower, requiring time to reset itself, where LOOM running a live update had almost no effect on the throughput. Lastly the timeliness of LOOM was demonstrated using a simple example, showing a LOOM based fix in 368ms whereas the function quiescence fix took the max test time (1 hour) and still did not finish.

==Critique==
===Good===
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up their topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnecessary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delivered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explanation) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

===Not-So-Good===
One of the problems with this paper is that although many of the examples are simplified in order to expedite the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunately, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

==References==
[1] Introduction to Hotpatching. [http://technet.microsoft.com/en-us/library/cc781109%28WS.10%29.aspx http://technet.microsoft.com/en-us/library/cc781109(WS.10).aspx].

[2] Introduction to Instrumentation and Tracing. [http://msdn.microsoft.com/en-us/library/aa983649%28VS.71%29.aspx http://msdn.microsoft.com/en-us/library/aa983649(VS.71).aspx]

[3] A. D. Marshall. Further Threads Programming:Synchronization. Cardiff University, 1999 [http://www.cs.cf.ac.uk/Dave/C/node31.html#SECTION003110000000000000000 HTML]

[4] Description of race conditions and deadlocks. [http://support.microsoft.com/kb/317723 http://support.microsoft.com/kb/317723]

[5] A. S. Tanenbaum. Modern Operating Systems (3rd Edition), page 128, 2008

[6] QUIESCE Function. IBM [http://publib.boulder.ibm.com/infocenter/zvm/v5r3/index.jsp?topic=/com.ibm.zvm.v53.hcpb4/hcse5b21270.htm]

COMP 3000 Essay 2 2010 Question 5

2010-11-27T19:01:01Z

Afranco2: /* Current solution expressed */

==Paper==
'''Title:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]

'''Authors:''' Jingyue Wu, Heming Cui, Junfeng Yang

'''Affiliations:''' Computer Science Department, Columbia University

'''Supplementary Information:''' Video available [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 here] as well as [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf slides]

==Background Concepts==
A race condition is a system flaw that “occurs when two threads access a shared variable at the same time." Race conditions can be very complex, time consuming and expensive to fix. Unfortunately, the most challenging part of race condition is not fixing it, but rather find it. Race conditions are notorious for being extremely difficult to find, isolate and recreate. To help ease this process, the authors of this paper, Jingyue Wu, Heming Cui, Junfeng Yang, propose the adoption of LOOM.

LOOM is a system which dynamically locates and corrects areas which may be susceptible to race condition errors. The power of LOOM rests in its ability to operate on live applications in real time. This is possible thanks to its evacuation algorithm which injects execution filters to fix race conditions at runtime. Execution filters, otherwise known as request filtering, allow you to inspect the request before and after the main logic is executed. By leveraging execution filters as the means for correcting race conditions, LOOM is able to operate with very little performance overhead and is a highly scalable as the number of application threads increases.

The authors tested LOOM on existing real world race conditions found in common applications. The tests found that all tested race conditions were solved, with little performance overhead, in a scalable and easy to implement manor.

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

'''Deadlock:''' Deadlocks usually occur within the context of two threads. One thread tries to lock a variable that the other thread has already locked and vice versa. The result of this is that each thread is waiting for each others thread to release the variable. Thus a deadlock occurs and nothing can happen.

'''Evacuation''' The process of proactively pausing and changing states of code sections so that those sections can be filtered for proper processing

'''Execution Filters:''' Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.

'''Function Quiescence''' The process of pausing and altering states, in order to avoid race conditions and overlapping between code segments.

'''Hot Patches:''' "Hot patching provides a mechanism to update system files without rebooting or stopping services and processes."[[#References | [1]]]

'''Hybrid Instrumentation Engine:''' "Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information." [[#References | [2]]] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.

'''Lock:''' A lock is a way of limiting access to a common resource when using multiple threads. Lock and unlock methods are usually called at the beginning and end of a target method, respectively. "Mutual exclusion locks (mutexes) are a common method of serializing thread execution. Mutual exclusion locks synchronize threads, usually by ensuring that only one thread at a time executes a critical section of code. Mutex locks can also preserve single-threaded code." [[#References | [3]]]

'''Mutex:''' Unable to be both true at the same time.

'''Race Condition:''' "A race condition occurs when two threads access a shared variable at the same time." [[#References | [4]]]

'''Semaphore:''' Semaphores are basically a special type of flag and generalize a down and up state(sleep or wakeup). The down operation checks to see if the value is greater than 0 and if so, decrements the value and uses up one stored wakeup. If the value is 0, the process is put to sleep. These steps are all done in a single indivisible atomic action. It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has been completed or blocked. Semaphores are an essential part of solving synchronization problems. [[#References | [5]]]

==Research problem==
===Problem being addressed===
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
===Related work===
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.

Using a QUIESCE function to "temporarily suspend...incoming messages on an IUCV path" These paths can later be reactivated and run as normal. This is not an efficient for of fixing a race condition because it only delays the problem in an attempt to avoid conflict. Although this does allow for a certain extent of safety it does not come near the reliability and flexibility of LOOM. Speed, reliability, flexibility and ease of use are all areas in which LOOM is demonstrated as being better than a QUIESCE function.

==Contribution==
===Current solution expressed===
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

Through multiple tests LOOM proves its worth. Overhead is tested in a comparison of LOOM during normal runtime. The effects of LOOM on Apache and MySQL are minimal, (~1.83% and ~4% respectively) making it an obvious choice as a runtime fix for race errors. To test scalability the team discovered that on 32 server threads, the over head was still under 3% and 12% respectively. Reliability is one of the strongest facets of the LOOM system. It fixed all of the race condition errors that it was tested against, proving that it has immense power as a reliable form of fix. To assure reliability LOOM was paired against a conventional restart-based software update. In this test the software update was clearly slower, requiring time to reset itself, where LOOM running a live update had almost no effect on the throughput. Lastly the timeliness of LOOM was demonstrated using a simple example, showing a LOOM based fix in 368ms whereas the function quiescence fix took the max test time (1 hour) and still did not finish.

==Critique==
===Good===
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up their topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnecessary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delivered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explanation) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

===Not-So-Good===
One of the problems with this paper is that although many of the examples are simplified in order to expedite the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunately, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

==References==
[1] Introduction to Hotpatching. [http://technet.microsoft.com/en-us/library/cc781109%28WS.10%29.aspx http://technet.microsoft.com/en-us/library/cc781109(WS.10).aspx].

[2] Introduction to Instrumentation and Tracing. [http://msdn.microsoft.com/en-us/library/aa983649%28VS.71%29.aspx http://msdn.microsoft.com/en-us/library/aa983649(VS.71).aspx]

[3] A. D. Marshall. Further Threads Programming:Synchronization. Cardiff University, 1999 [http://www.cs.cf.ac.uk/Dave/C/node31.html#SECTION003110000000000000000 HTML]

[4] Description of race conditions and deadlocks. [http://support.microsoft.com/kb/317723 http://support.microsoft.com/kb/317723]

[5] A. S. Tanenbaum. Modern Operating Systems (3rd Edition), page 128, 2008

COMP 3000 Essay 2 2010 Question 5

2010-11-27T18:33:26Z

Afranco2: /* Background Concepts */

==Paper==
'''Title:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]

'''Authors:''' Jingyue Wu, Heming Cui, Junfeng Yang

'''Affiliations:''' Computer Science Department, Columbia University

'''Supplementary Information:''' Video available [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 here] as well as [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf slides]

==Background Concepts==
A race condition is a system flaw that “occurs when two threads access a shared variable at the same time." Race conditions can be very complex, time consuming and expensive to fix. Unfortunately, the most challenging part of race condition is not fixing it, but rather find it. Race conditions are notorious for being extremely difficult to find, isolate and recreate. To help ease this process, the authors of this paper, Jingyue Wu, Heming Cui, Junfeng Yang, propose the adoption of LOOM.

LOOM is a system which dynamically locates and corrects areas which may be susceptible to race condition errors. The power of LOOM rests in its ability to operate on live applications in real time. This is possible thanks to its evacuation algorithm which injects execution filters to fix race conditions at runtime. Execution filters, otherwise known as request filtering, allow you to inspect the request before and after the main logic is executed. By leveraging execution filters as the means for correcting race conditions, LOOM is able to operate with very little performance overhead and is a highly scalable as the number of application threads increases.

The authors tested LOOM on existing real world race conditions found in common applications. The tests found that all tested race conditions were solved, with little performance overhead, in a scalable and easy to implement manor.

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

'''Deadlock:''' Deadlocks usually occur within the context of two threads. One thread tries to lock a variable that the other thread has already locked and vice versa. The result of this is that each thread is waiting for each others thread to release the variable. Thus a deadlock occurs and nothing can happen.

'''Evacuation''' The process of proactively pausing and changing states of code sections so that those sections can be filtered for proper processing

'''Execution Filters:''' Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.

'''Function Quiescence''' The process of pausing and altering states, in order to avoid race conditions and overlapping between code segments.

'''Hot Patches:''' "Hot patching provides a mechanism to update system files without rebooting or stopping services and processes."[[#References | [1]]]

'''Hybrid Instrumentation Engine:''' "Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information." [[#References | [2]]] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.

'''Lock:''' A lock is a way of limiting access to a common resource when using multiple threads. Lock and unlock methods are usually called at the beginning and end of a target method, respectively. "Mutual exclusion locks (mutexes) are a common method of serializing thread execution. Mutual exclusion locks synchronize threads, usually by ensuring that only one thread at a time executes a critical section of code. Mutex locks can also preserve single-threaded code." [[#References | [3]]]

'''Mutex:''' Unable to be both true at the same time.

'''Race Condition:''' "A race condition occurs when two threads access a shared variable at the same time." [[#References | [4]]]

'''Semaphore:''' Semaphores are basically a special type of flag and generalize a down and up state(sleep or wakeup). The down operation checks to see if the value is greater than 0 and if so, decrements the value and uses up one stored wakeup. If the value is 0, the process is put to sleep. These steps are all done in a single indivisible atomic action. It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has been completed or blocked. Semaphores are an essential part of solving synchronization problems. [[#References | [5]]]

==Research problem==
===Problem being addressed===
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
===Related work===
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.

Using a QUIESCE function to "temporarily suspend...incoming messages on an IUCV path" These paths can later be reactivated and run as normal. This is not an efficient for of fixing a race condition because it only delays the problem in an attempt to avoid conflict. Although this does allow for a certain extent of safety it does not come near the reliability and flexibility of LOOM. Speed, reliability, flexibility and ease of use are all areas in which LOOM is demonstrated as being better than a QUIESCE function.

==Contribution==
===Current solution expressed===
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

==Critique==
===Good===
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up their topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnecessary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delivered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explanation) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

===Not-So-Good===
One of the problems with this paper is that although many of the examples are simplified in order to expedite the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunately, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

==References==
[1] Introduction to Hotpatching. [http://technet.microsoft.com/en-us/library/cc781109%28WS.10%29.aspx http://technet.microsoft.com/en-us/library/cc781109(WS.10).aspx].

[2] Introduction to Instrumentation and Tracing. [http://msdn.microsoft.com/en-us/library/aa983649%28VS.71%29.aspx http://msdn.microsoft.com/en-us/library/aa983649(VS.71).aspx]

[3] A. D. Marshall. Further Threads Programming:Synchronization. Cardiff University, 1999 [http://www.cs.cf.ac.uk/Dave/C/node31.html#SECTION003110000000000000000 HTML]

[4] Description of race conditions and deadlocks. [http://support.microsoft.com/kb/317723 http://support.microsoft.com/kb/317723]

[5] A. S. Tanenbaum. Modern Operating Systems (3rd Edition), page 128, 2008

COMP 3000 Essay 2 2010 Question 5

2010-11-27T18:31:29Z

Afranco2: /* Related work */

==Paper==
'''Title:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]

'''Authors:''' Jingyue Wu, Heming Cui, Junfeng Yang

'''Affiliations:''' Computer Science Department, Columbia University

'''Supplementary Information:''' Video available [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 here] as well as [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf slides]

==Background Concepts==
A race condition is a system flaw that “occurs when two threads access a shared variable at the same time." Race conditions can be very complex, time consuming and expensive to fix. Unfortunately, the most challenging part of race condition is not fixing it, but rather find it. Race conditions are notorious for being extremely difficult to find, isolate and recreate. To help ease this process, the authors of this paper, Jingyue Wu, Heming Cui, Junfeng Yang, propose the adoption of LOOM.

LOOM is a system which dynamically locates and corrects areas which may be susceptible to race condition errors. The power of LOOM rests in its ability to operate on live applications in real time. This is possible thanks to its evacuation algorithm which injects execution filters to fix race conditions at runtime. Execution filters, otherwise known as request filtering, allow you to inspect the request before and after the main logic is executed. By leveraging execution filters as the means for correcting race conditions, LOOM is able to operate with very little performance overhead and is a highly scalable as the number of application threads increases.

The authors tested LOOM on existing real world race conditions found in common applications. The tests found that all tested race conditions were solved, with little performance overhead, in a scalable and easy to implement manor.

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

'''Deadlock:''' Deadlocks usually occur within the context of two threads. One thread tries to lock a variable that the other thread has already locked and vice versa. The result of this is that each thread is waiting for each others thread to release the variable. Thus a deadlock occurs and nothing can happen.

'''Evacuation''' The process of proactively pausing and changing states of code sections so that those sections can be filtered for proper processing

'''Execution Filters:''' Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.

'''Hot Patches:''' "Hot patching provides a mechanism to update system files without rebooting or stopping services and processes."[[#References | [1]]]

'''Hybrid Instrumentation Engine:''' "Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information." [[#References | [2]]] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.

'''Lock:''' A lock is a way of limiting access to a common resource when using multiple threads. Lock and unlock methods are usually called at the beginning and end of a target method, respectively. "Mutual exclusion locks (mutexes) are a common method of serializing thread execution. Mutual exclusion locks synchronize threads, usually by ensuring that only one thread at a time executes a critical section of code. Mutex locks can also preserve single-threaded code." [[#References | [3]]]

'''Mutex:''' Unable to be both true at the same time.

'''Race Condition:''' "A race condition occurs when two threads access a shared variable at the same time." [[#References | [4]]]

'''Semaphore:''' Semaphores are basically a special type of flag and generalize a down and up state(sleep or wakeup). The down operation checks to see if the value is greater than 0 and if so, decrements the value and uses up one stored wakeup. If the value is 0, the process is put to sleep. These steps are all done in a single indivisible atomic action. It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has been completed or blocked. Semaphores are an essential part of solving synchronization problems. [[#References | [5]]]

==Research problem==
===Problem being addressed===
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
===Related work===
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.

Using a QUIESCE function to "temporarily suspend...incoming messages on an IUCV path" These paths can later be reactivated and run as normal. This is not an efficient for of fixing a race condition because it only delays the problem in an attempt to avoid conflict. Although this does allow for a certain extent of safety it does not come near the reliability and flexibility of LOOM. Speed, reliability, flexibility and ease of use are all areas in which LOOM is demonstrated as being better than a QUIESCE function.

==Contribution==
===Current solution expressed===
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

==Critique==
===Good===
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up their topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnecessary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delivered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explanation) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

===Not-So-Good===
One of the problems with this paper is that although many of the examples are simplified in order to expedite the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunately, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

==References==
[1] Introduction to Hotpatching. [http://technet.microsoft.com/en-us/library/cc781109%28WS.10%29.aspx http://technet.microsoft.com/en-us/library/cc781109(WS.10).aspx].

[2] Introduction to Instrumentation and Tracing. [http://msdn.microsoft.com/en-us/library/aa983649%28VS.71%29.aspx http://msdn.microsoft.com/en-us/library/aa983649(VS.71).aspx]

[3] A. D. Marshall. Further Threads Programming:Synchronization. Cardiff University, 1999 [http://www.cs.cf.ac.uk/Dave/C/node31.html#SECTION003110000000000000000 HTML]

[4] Description of race conditions and deadlocks. [http://support.microsoft.com/kb/317723 http://support.microsoft.com/kb/317723]

[5] A. S. Tanenbaum. Modern Operating Systems (3rd Edition), page 128, 2008

COMP 3000 Essay 2 2010 Question 5

2010-11-27T18:23:03Z

Afranco2: /* Background Concepts */

==Paper==
'''Title:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]

'''Authors:''' Jingyue Wu, Heming Cui, Junfeng Yang

'''Affiliations:''' Computer Science Department, Columbia University

'''Supplementary Information:''' Video available [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 here] as well as [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf slides]

==Background Concepts==
A race condition is a system flaw that “occurs when two threads access a shared variable at the same time." Race conditions can be very complex, time consuming and expensive to fix. Unfortunately, the most challenging part of race condition is not fixing it, but rather find it. Race conditions are notorious for being extremely difficult to find, isolate and recreate. To help ease this process, the authors of this paper, Jingyue Wu, Heming Cui, Junfeng Yang, propose the adoption of LOOM.

LOOM is a system which dynamically locates and corrects areas which may be susceptible to race condition errors. The power of LOOM rests in its ability to operate on live applications in real time. This is possible thanks to its evacuation algorithm which injects execution filters to fix race conditions at runtime. Execution filters, otherwise known as request filtering, allow you to inspect the request before and after the main logic is executed. By leveraging execution filters as the means for correcting race conditions, LOOM is able to operate with very little performance overhead and is a highly scalable as the number of application threads increases.

The authors tested LOOM on existing real world race conditions found in common applications. The tests found that all tested race conditions were solved, with little performance overhead, in a scalable and easy to implement manor.

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

'''Deadlock:''' Deadlocks usually occur within the context of two threads. One thread tries to lock a variable that the other thread has already locked and vice versa. The result of this is that each thread is waiting for each others thread to release the variable. Thus a deadlock occurs and nothing can happen.

'''Evacuation''' The process of proactively pausing and changing states of code sections so that those sections can be filtered for proper processing

'''Execution Filters:''' Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.

'''Hot Patches:''' "Hot patching provides a mechanism to update system files without rebooting or stopping services and processes."[[#References | [1]]]

'''Hybrid Instrumentation Engine:''' "Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information." [[#References | [2]]] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.

'''Lock:''' A lock is a way of limiting access to a common resource when using multiple threads. Lock and unlock methods are usually called at the beginning and end of a target method, respectively. "Mutual exclusion locks (mutexes) are a common method of serializing thread execution. Mutual exclusion locks synchronize threads, usually by ensuring that only one thread at a time executes a critical section of code. Mutex locks can also preserve single-threaded code." [[#References | [3]]]

'''Mutex:''' Unable to be both true at the same time.

'''Race Condition:''' "A race condition occurs when two threads access a shared variable at the same time." [[#References | [4]]]

'''Semaphore:''' Semaphores are basically a special type of flag and generalize a down and up state(sleep or wakeup). The down operation checks to see if the value is greater than 0 and if so, decrements the value and uses up one stored wakeup. If the value is 0, the process is put to sleep. These steps are all done in a single indivisible atomic action. It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has been completed or blocked. Semaphores are an essential part of solving synchronization problems. [[#References | [5]]]

==Research problem==
===Problem being addressed===
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
===Related work===
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.

==Contribution==
===Current solution expressed===
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

==Critique==
===Good===
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up their topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnecessary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delivered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explanation) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

===Not-So-Good===
One of the problems with this paper is that although many of the examples are simplified in order to expedite the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunately, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

==References==
[1] Introduction to Hotpatching. [http://technet.microsoft.com/en-us/library/cc781109%28WS.10%29.aspx http://technet.microsoft.com/en-us/library/cc781109(WS.10).aspx].

[2] Introduction to Instrumentation and Tracing. [http://msdn.microsoft.com/en-us/library/aa983649%28VS.71%29.aspx http://msdn.microsoft.com/en-us/library/aa983649(VS.71).aspx]

[3] A. D. Marshall. Further Threads Programming:Synchronization. Cardiff University, 1999 [http://www.cs.cf.ac.uk/Dave/C/node31.html#SECTION003110000000000000000 HTML]

[4] Description of race conditions and deadlocks. [http://support.microsoft.com/kb/317723 http://support.microsoft.com/kb/317723]

[5] A. S. Tanenbaum. Modern Operating Systems (3rd Edition), page 128, 2008

COMP 3000 Essay 2 2010 Question 5

2010-11-27T18:22:37Z

Afranco2: /* Background Concepts */

==Paper==
'''Title:''' [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]

'''Authors:''' Jingyue Wu, Heming Cui, Junfeng Yang

'''Affiliations:''' Computer Science Department, Columbia University

'''Supplementary Information:''' Video available [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 here] as well as [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf slides]

==Background Concepts==
A race condition is a system flaw that “occurs when two threads access a shared variable at the same time." Race conditions can be very complex, time consuming and expensive to fix. Unfortunately, the most challenging part of race condition is not fixing it, but rather find it. Race conditions are notorious for being extremely difficult to find, isolate and recreate. To help ease this process, the authors of this paper, Jingyue Wu, Heming Cui, Junfeng Yang, propose the adoption of LOOM.

LOOM is a system which dynamically locates and corrects areas which may be susceptible to race condition errors. The power of LOOM rests in its ability to operate on live applications in real time. This is possible thanks to its evacuation algorithm which injects execution filters to fix race conditions at runtime. Execution filters, otherwise known as request filtering, allow you to inspect the request before and after the main logic is executed. By leveraging execution filters as the means for correcting race conditions, LOOM is able to operate with very little performance overhead and is a highly scalable as the number of application threads increases.

The authors tested LOOM on existing real world race conditions found in common applications. The tests found that all tested race conditions were solved, with little performance overhead, in a scalable and easy to implement manor.

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

'''Deadlock:''' Deadlocks usually occur within the context of two threads. One thread tries to lock a variable that the other thread has already locked and vice versa. The result of this is that each thread is waiting for each others thread to release the variable. Thus a deadlock occurs and nothing can happen.

'''Execution Filters:''' Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.

'''Evacuation''' The process of proactively pausing and changing states of code sections so that those sections can be filtered for proper processing

'''Hot Patches:''' "Hot patching provides a mechanism to update system files without rebooting or stopping services and processes."[[#References | [1]]]

'''Hybrid Instrumentation Engine:''' "Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information." [[#References | [2]]] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.

'''Lock:''' A lock is a way of limiting access to a common resource when using multiple threads. Lock and unlock methods are usually called at the beginning and end of a target method, respectively. "Mutual exclusion locks (mutexes) are a common method of serializing thread execution. Mutual exclusion locks synchronize threads, usually by ensuring that only one thread at a time executes a critical section of code. Mutex locks can also preserve single-threaded code." [[#References | [3]]]

'''Mutex:''' Unable to be both true at the same time.

'''Race Condition:''' "A race condition occurs when two threads access a shared variable at the same time." [[#References | [4]]]

'''Semaphore:''' Semaphores are basically a special type of flag and generalize a down and up state(sleep or wakeup). The down operation checks to see if the value is greater than 0 and if so, decrements the value and uses up one stored wakeup. If the value is 0, the process is put to sleep. These steps are all done in a single indivisible atomic action. It is guaranteed that once a semaphore operation has started, no other process can access the semaphore until the operation has been completed or blocked. Semaphores are an essential part of solving synchronization problems. [[#References | [5]]]

==Research problem==
===Problem being addressed===
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
===Related work===
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.

==Contribution==
===Current solution expressed===
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

==Critique==
===Good===
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up their topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnecessary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delivered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explanation) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

===Not-So-Good===
One of the problems with this paper is that although many of the examples are simplified in order to expedite the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunately, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

==References==
[1] Introduction to Hotpatching. [http://technet.microsoft.com/en-us/library/cc781109%28WS.10%29.aspx http://technet.microsoft.com/en-us/library/cc781109(WS.10).aspx].

[2] Introduction to Instrumentation and Tracing. [http://msdn.microsoft.com/en-us/library/aa983649%28VS.71%29.aspx http://msdn.microsoft.com/en-us/library/aa983649(VS.71).aspx]

[3] A. D. Marshall. Further Threads Programming:Synchronization. Cardiff University, 1999 [http://www.cs.cf.ac.uk/Dave/C/node31.html#SECTION003110000000000000000 HTML]

[4] Description of race conditions and deadlocks. [http://support.microsoft.com/kb/317723 http://support.microsoft.com/kb/317723]

[5] A. S. Tanenbaum. Modern Operating Systems (3rd Edition), page 128, 2008

Talk:COMP 3000 Essay 2 2010 Question 5

2010-11-23T00:49:20Z

Afranco2: /* Background Concepts */

Maybe we can all add our names below so we know who's still in this course? --[[User:Myagi|Myagi]] 12:38, 14 November 2010 (UTC)

Group members:

* Michael Yagi
* Nicolas Lessard
* Julie Powers
* Derek Langlois
* Dustin Martin

Jeffrey Francom contacted me earlier so I know he is also still in the course. <strike>Now we are only waiting on Dustin Martin.</strike> Everyone has been accounted for. [[User:J powers|J powers]] 18:07, 15 November 2010 (UTC)

Just kicking things off. Feel free to make suggestions or change anything. --[[User:Myagi|Myagi]] 11:36, 17 November 2010 (UTC)

Edited and filled out the critique section. Edited a little bit here and there. --[[User:Afranco2|Afranco2]] 17:41, 22 November 2010 (UTC)

==Essay==
===Paper===
<blockquote>The paper's title, authors, and their affiliations. Include a link to the paper and any particularly helpful supplementary information.</blockquote>
* Title: [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]
* Authors: Jingyue Wu, Heming Cui, Junfeng Yang
* Affiliations: Computer Science Department, Columbia University
* Supplementary Information: [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 Video], [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf Slides]

===Background Concepts===
<blockquote>Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.</blockquote>

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

* Race Condition: "A race condition occurs when two threads access a shared variable at the same time." [http://support.microsoft.com/kb/317723 Race Condition]
* Execution Filters: Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.
* Hot Patches: "Hot patching is the application of patches without shutting down and restarting the system or the program concerned. This addresses problems related to unavailability of service provided by the system or the program. A patch that can be applied in this way is called a hot patch. [http://en.wikipedia.org/wiki/Patch_%28computing%29#Hot_patching Hot Patching]
* Hybrid Instrumentation Engine: Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information. [http://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 Instrumentation] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.
* Lock: "In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies." [http://en.wikipedia.org/wiki/Lock_%28computer_science%29 Lock]
* Mutex: Mutually Exclusive; Unable to be both true at the same time.

===Research problem===
<blockquote>What is the research problem being addressed by the paper? How does this problem relate to past related work?</blockquote>
====Problem being addressed====
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
====Past related work====
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.
===Contribution===
<blockquote>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?)</blockquote>
====Current solution expressed====
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

===Critique===
<blockquote>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.</blockquote>
====Good====
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up thier topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnessicary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delievered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explination) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

====Not-So-Good====
One of the problems with this paper is that although many of the examples are simplified in order to expediate the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunatly, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

===References===
<blockquote>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.</blockquote>

Talk:COMP 3000 Essay 2 2010 Question 5

2010-11-22T17:41:14Z

Afranco2:

Maybe we can all add our names below so we know who's still in this course? --[[User:Myagi|Myagi]] 12:38, 14 November 2010 (UTC)

Group members:

* Michael Yagi
* Nicolas Lessard
* Julie Powers
* Derek Langlois

Jeffrey Francom contacted me earlier so I know he is also still in the course. <strike>Now we are only waiting on Dustin Martin.</strike> Everyone has been accounted for. [[User:J powers|J powers]] 18:07, 15 November 2010 (UTC)

Just kicking things off. Feel free to make suggestions or change anything. --[[User:Myagi|Myagi]] 11:36, 17 November 2010 (UTC)

Edited and filled out the critique section. Edited a little bit here and there. --[[User:Afranco2|Afranco2]] 17:41, 22 November 2010 (UTC)

==Essay==
===Paper===
<blockquote>The paper's title, authors, and their affiliations. Include a link to the paper and any particularly helpful supplementary information.</blockquote>
* Title: [http://www.usenix.org/events/osdi10/tech/full_papers/Wu.pdf Bypassing Races in Live Applications with Execution Filters]
* Authors: Jingyue Wu, Heming Cui, Junfeng Yang
* Affiliations: Computer Science Department, Columbia University
* Supplementary Information: [http://homeostasis.scs.carleton.ca/osdi/video/wu.mp4 Video], [http://homeostasis.scs.carleton.ca/osdi/slides/wu.pdf Slides]

===Background Concepts===
<blockquote>Explain briefly the background concepts and ideas that your fellow classmates will need to know first in order to understand your assigned paper.</blockquote>

This paper consists of multiple terms which must be familiar to the reader in order to assist in reading the Bypassing Races in Live Applications with Execution Filters paper. These terms are listed and explained below:

* Execution Filters: Otherwise known as request filtering. Request filters allow you to inspect the request before and after the main logic is executed. These are mutual exclusion filters in the context of this paper.
* Hot Patches: "Hot patching is the application of patches without shutting down and restarting the system or the program concerned. This addresses problems related to unavailability of service provided by the system or the program. A patch that can be applied in this way is called a hot patch. [http://en.wikipedia.org/wiki/Patch_%28computing%29#Hot_patching Hot Patching]
* Hybrid Instrumentation Engine: Instrumentation refers to an ability to monitor or measure the level of a product's performance, to diagnose errors and writing trace information. [http://en.wikipedia.org/wiki/Instrumentation_%28computer_programming%29 Instrumentation] Instrument programs can have low runtime overhead, but instrumentation has to be done at compile time. Dynamic instrumentation can update programs at runtime but incur high overhead. A hybrid instrumentation is an implementation of combined static and dynamic instrumentation.
* Lock: "In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies." [http://en.wikipedia.org/wiki/Lock_%28computer_science%29 Lock]
* Mutex: Mutually Exclusive; Unable to be both true at the same time.

===Research problem===
<blockquote>What is the research problem being addressed by the paper? How does this problem relate to past related work?</blockquote>
====Problem being addressed====
With the rise of multiple core systems, multithreaded programs are often prone to race conditions. Races are hard to detect, test and debug. Due to the immaturity of current race detectors, this paper explains a new approach to race detection and work arounds through the use of LOOM.
====Past related work====
Two common solutions to fixing deployed races are software updates and hot patches. Software updates require restarts whereas hot patches applies patches to live systems. However, relying on conventional patches can lead to new errors and could be unsafe, due to a multithreaded applications complexity. Releasing a reliable patch takes time, but developers often resort to more efficient fixes rather than placing proper locks in the application due to performance or work pressure.
===Contribution===
<blockquote>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?)</blockquote>
====Current solution expressed====
Compared to traditional solutions, LOOM differs in its approach to race fixes. It is designed to quickly develop safe, optimized, temporary workarounds while a concrete solution is developed. LOOM is also very easy to use. LOOM is compiled with a developers application as a plugin and kept separate from the source code. The plugin will inject the LOOM update into the application binary.

Mutual exclusion filters are written by the developer and synced with the source code to filter out any racy threads. The code declaration used is easy to understand and can be inserted in a code region that need to be mutually exclusive. The developer does not need to deal with low level operations such as lock, unlock and semaphore operations. Users can then download the filter and apply it to the application while it is still live.

LOOM is flexible in that developers can make trade-offs in performance and reliability in their application in conjunction with LOOM. These can include making two code regions mutually exclusive even when accessing different objects or with extreme measures, making them run in single threaded mode.

An evacuation algorithm is used for safety as to not introduce new errors. A critical region is marked using static analysis. All threads in the critical region are then evacuated. After the evacuation is executed, the execution filter is installed and then the threads are resumed after a live update pause is done at a safe location.

LOOM's hybrid instrumentation engine is used to reduce its overhead. The engine statically changes an applications binary to anticipate dynamic updates.

Evaluation of LOOM was based on overhead, scalability, reliability, availability and timeliness. These were demonstrated using Apache and MySQL in conjunction with the multithreaded ApacheBench and SysBench, respectively.

===Critique===
<blockquote>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.</blockquote>
====Good====
The authors of this essay are efficient at delivering the information surrounding their thesis both in staying focused on the main thesis as well as backing up thier topics with relevant examples and data. This helps to keep the thesis paramount throughout the paper. Examples throughout the paper, particularly the MySQL example ensure that the use of execution filters is clear to the reader. All of the examples are well documented and some (ex. Figure 2) are simplified as to not confuse the reader with too much unnessicary information. References throughout the writing backup the reliability of the paper and let the user keep track of the sources to properly check information and sources.

The whole essay flows well and the information is delievered in a well put together order, allowing the reader to learn enough about LOOM (or any of the sub-topics involved in the explination) before being informed about the next relative subject. The paper ends with a conclusion that does a good job of wrapping up the whole paper in a clear and concise manner.

====Not-So-Good====
One of the problems with this paper is that although many of the examples are simplified in order to expediate the understanding of the user, some are a little oversimplified. For example, Figure 9 is a graphic that attempts to represent the evacuation process in a visual manner. Unfortunatly, this ends up making the problem seem almost trivial and does little more than water down the information.

The writers are also a little bit one sided (with understandable reason) on the topic. Although they do admit the limitations of LOOM, they do not spend much time discussing any problems later. There is a large amount of play-up for LOOM without much discussion of the possible problems with it, such as the clients running LOOM may decide not to fix the race conditions and rather just let the program continue to run with LOOM as a permanent fix. This may cause further errors in the long term life of the program.

===References===
<blockquote>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.</blockquote>

Talk:COMP 3000 Essay 2 2010 Question 5

2010-11-22T17:39:08Z

Afranco2: /* Background Concepts */

Talk:COMP 3000 Essay 2 2010 Question 5

2010-11-22T17:29:05Z

Afranco2: /* Not-So-Good */

2010-10-09T18:51:35Z

Afranco2:

=Question=

What is the history of POSIX Threads (pthreads)? Consider - does this history explain why UNIX was so late to implement support for multithreaded processes?

=Answer=

Hey guys, i'm just gunna get this started by posting a few links for everyone to get going. This will help explain a general idea of what they are and the history of them. Please add some more links or anything else you think would be helpful!

http://en.wikipedia.org/wiki/POSIX_Threads
https://computing.llnl.gov/tutorials/pthreads/
http://sourceware.org/pthreads-win32/

-[[User:tmalone|tmalone]]

I found this, might not help, but it might:--[[User:Rannath|Rannath]] 02:09, 6 October 2010 (UTC)

I'm not sure about the rest of you, but most of what I am able to find has to do with information on things that fall under POSIX, not actually about POSIX-afranco2

POSIX Threads, or pthreads, is a thread that is commonly used in UNIX systems but it also seen in some Microsoft Windows systems. A thread is a unit of process that executes segments of code within applications. When a process gets called from the system, the thread will execute the code for the process. POSIX stands for Portable Operating System Interface (for UNIX) and has been used by many independent sellers of hardware. There has always been issues such that developers could not create a reliable protable pthread application. For the use of multi-threading, its implementation arrived fairly late because the systems could not support it. Data mapping onto Linux gave birth to several problems due to the fact that POSIX and UNIX were implemented so differently.

-[[User:tmalone|tmalone]]

http://www.faqs.org/faqs/os-research/part1/section-10.html

Might be of some use as well --[[User:Lmundt|Lmundt]] 14:48, 7 October 2010 (UTC)
https://computing.llnl.gov/tutorials/pthreads/

Edited version from what -tmalone has written.

POSIX Threads is also called pthreads. It’s a Portable Operating System interface is mainly for Unix but it’s also distributed to some Microsoft Windows OS. A Thread is a unit of process that resigns inside a process and executes when a system call has been executed. Threads have same global and all the threads share memory, threads also contain their personal private data. Pthread has become commonly used a way of adding concurrency to an application. The history of POSIX Threads is that many hardware sellers executed their own versions of threads. These developments differed from one another, creating difficulties for programmers to implement portable thread applications. POSIX threading has always been an issue on Linux. UNIX was so late to implement support for multithreaded process because it does not map that well onto linux; this is due to the significant differences in relationship between POSIX and UNIX.

-Npatel1

Just a reorganized version of the above, with more history edited into the middle. See the discussion page for organization notes:

POSIX Threads is also called pthreads. It’s a Portable Operating System interface is mainly for Unix but it’s also distributed to some Microsoft Windows OS. A Thread is a unit of process that resigns inside a process and executes when a system call has been executed. Threads have same global and all the threads share memory, threads also contain their personal private data. Pthread has become commonly used a way of adding concurrency to an application.

The history of POSIX Threads is that many hardware sellers executed their own versions of threads. These developments differed from one another, creating difficulties for programmers to implement portable thread applications. UNIX traditionally had a system running only a single thread under a process. These processes could not share memory and interacted using 'pipes'. Once developers started wanting to be able to run multiple threads under one process, IEEE began to form together the POSIX standards. In 1988 POSIX.1 was ratified and was accepted as the international standard in 1990. From there the POSIX standards grew to more than 20 individual standards, encapsulating a large area of different groups.

POSIX threading has always been an issue on Linux. UNIX was so late to implement support for multithreaded process because it does not map that well onto linux; this is due to the significant differences in relationship between POSIX and UNIX.
-afranco2

2010-10-08T20:51:16Z

Afranco2: /* Sources */

COMP 3000 Essay 1 2010 Question 8

2010-10-08T20:49:10Z

Afranco2: /* Answer */

COMP 3000 Essay 1 2010 Question 8

2010-10-08T20:47:49Z

Afranco2: /* Answer */

Talk:COMP 3000 Essay 1 2010 Question 8

2010-10-08T20:31:10Z

Afranco2:

Talk:COMP 3000 Essay 1 2010 Question 8

2010-10-08T20:20:00Z

Afranco2: /* Sources */

Talk:COMP 3000 Essay 1 2010 Question 8

2010-10-08T20:19:47Z

Afranco2: /* Sources */