Art of Multiprocessor Programming - Revision history

Scott: /* Introduction */

2014-01-31T21:11:58Z

Introduction

← Older revision		Revision as of 21:11, 31 January 2014
Line 14:		Line 14:
	* '''Amdahl's law''': we have n concurrent processors, and fraction p of the job can be executed in parallel. Then the speedup S of moving from 1 processor to n processors is		* '''Amdahl's law''': we have n concurrent processors, and fraction p of the job can be executed in parallel. Then the speedup S of moving from 1 processor to n processors is

	S = 1/(1-p+p/n)		<math>S = \frac{1}{1-p+p/n}</math>

Scott: /* Some Terms */

2012-04-02T22:29:23Z

Some Terms

← Older revision		Revision as of 22:29, 2 April 2012
Line 1:		Line 1:
	Maurice Herlihy and Nir Shavit		Maurice Herlihy and Nir Shavit

	== ~~Some Terms~~ ==		== Introduction ==
	* A '''safety property''' states that some "bad thing" never happens. For example, a traffic light never displays green in all directions, even if the power fails.		* A '''safety property''' states that some "bad thing" never happens. For example, a traffic light never displays green in all directions, even if the power fails.
	* A '''liveness property''' states that a particular good thing will happen. For example, a red traffic light will eventually turn green.		* A '''liveness property''' states that a particular good thing will happen. For example, a red traffic light will eventually turn green.
Line 12:		Line 12:
	* In a '''producer-consumer''' problem, the producer will only produce a resource when it is needed, and only when no one is busy consuming; the consumer will consume only when the resource is present, and only when no one is producing.		* In a '''producer-consumer''' problem, the producer will only produce a resource when it is needed, and only when no one is busy consuming; the consumer will consume only when the resource is present, and only when no one is producing.
	* In the '''readers-writers''' problem, the reader must be able to read from several locations without interrupting any of the writers from writing.		* In the '''readers-writers''' problem, the reader must be able to read from several locations without interrupting any of the writers from writing.
			* '''Amdahl's law''': we have n concurrent processors, and fraction p of the job can be executed in parallel. Then the speedup S of moving from 1 processor to n processors is

			S = 1/(1-p+p/n)

Scott at 22:26, 2 April 2012

2012-04-02T22:26:27Z

← Older revision		Revision as of 22:26, 2 April 2012
Line 11:		Line 11:
	* An example of persistent communication is that of '''interrupts'''. Thread A interrupts thread B by setting a bit at a location periodically checked by B. Sooner or later, B notices the bit has been set and reacts. After reacting, B typically resets the bit (A cannot reset the bit).		* An example of persistent communication is that of '''interrupts'''. Thread A interrupts thread B by setting a bit at a location periodically checked by B. Sooner or later, B notices the bit has been set and reacts. After reacting, B typically resets the bit (A cannot reset the bit).
	* In a '''producer-consumer''' problem, the producer will only produce a resource when it is needed, and only when no one is busy consuming; the consumer will consume only when the resource is present, and only when no one is producing.		* In a '''producer-consumer''' problem, the producer will only produce a resource when it is needed, and only when no one is busy consuming; the consumer will consume only when the resource is present, and only when no one is producing.
			* In the '''readers-writers''' problem, the reader must be able to read from several locations without interrupting any of the writers from writing.

Scott: /* Some Terms */

2012-04-02T22:24:26Z

Some Terms

← Older revision		Revision as of 22:24, 2 April 2012
Line 10:		Line 10:
	* '''Persistent''' communication allows the sender and receiver to participate at different times. Posting letters, sending email, or leaving notes under rocks are all examples of persistent communication.		* '''Persistent''' communication allows the sender and receiver to participate at different times. Posting letters, sending email, or leaving notes under rocks are all examples of persistent communication.
	* An example of persistent communication is that of '''interrupts'''. Thread A interrupts thread B by setting a bit at a location periodically checked by B. Sooner or later, B notices the bit has been set and reacts. After reacting, B typically resets the bit (A cannot reset the bit).		* An example of persistent communication is that of '''interrupts'''. Thread A interrupts thread B by setting a bit at a location periodically checked by B. Sooner or later, B notices the bit has been set and reacts. After reacting, B typically resets the bit (A cannot reset the bit).
			* In a '''producer-consumer''' problem, the producer will only produce a resource when it is needed, and only when no one is busy consuming; the consumer will consume only when the resource is present, and only when no one is producing.

Scott: /* Some Terms */

2012-04-02T22:19:49Z

Some Terms

← Older revision		Revision as of 22:19, 2 April 2012
Line 4:		Line 4:
	* A '''safety property''' states that some "bad thing" never happens. For example, a traffic light never displays green in all directions, even if the power fails.		* A '''safety property''' states that some "bad thing" never happens. For example, a traffic light never displays green in all directions, even if the power fails.
	* A '''liveness property''' states that a particular good thing will happen. For example, a red traffic light will eventually turn green.		* A '''liveness property''' states that a particular good thing will happen. For example, a red traffic light will eventually turn green.
	* The problem of making sure that only one thread at a time can execute a particular block of code is called the		* The problem of making sure that only one thread at a time can execute a particular block of code is called the '''mutual exclusion''' problem.
	'''mutual exclusion''' problem.
	* The property of '''deadlock-freedom''' ensures that at least one thread will eventually gain access to some resource.		* The property of '''deadlock-freedom''' ensures that at least one thread will eventually gain access to some resource.
	* The property of '''starvation-freedom''' ensures that every thread will eventually gain access to some resource.		* The property of '''starvation-freedom''' ensures that every thread will eventually gain access to some resource.

Scott: /* Some Terms */

2012-04-02T22:19:38Z

Some Terms

← Older revision		Revision as of 22:19, 2 April 2012
Line 2:		Line 2:

	== Some Terms ==		== Some Terms ==
	* A '''safety property''' states that some "bad thing" never happens. For example, a traffic light never displays green in all		* A '''safety property''' states that some "bad thing" never happens. For example, a traffic light never displays green in all directions, even if the power fails.
	directions, even if the power fails.
	* A '''liveness property''' states that a particular good thing will happen. For example, a red traffic light will eventually turn green.		* A '''liveness property''' states that a particular good thing will happen. For example, a red traffic light will eventually turn green.
	* The problem of making sure that only one thread at a time can execute a particular block of code is called the		* The problem of making sure that only one thread at a time can execute a particular block of code is called the
Line 9:		Line 8:
	* The property of '''deadlock-freedom''' ensures that at least one thread will eventually gain access to some resource.		* The property of '''deadlock-freedom''' ensures that at least one thread will eventually gain access to some resource.
	* The property of '''starvation-freedom''' ensures that every thread will eventually gain access to some resource.		* The property of '''starvation-freedom''' ensures that every thread will eventually gain access to some resource.
	* '''Transient''' communication requires both parties to participate at the same time.		* '''Transient''' communication requires both parties to participate at the same time. Shouting, gestures, or cell phone calls are examples of transient communication.
	Shouting, gestures, or cell phone calls are examples of transient ~~commun-~~		* '''Persistent''' communication allows the sender and receiver to participate at different times. Posting letters, sending email, or leaving notes under rocks are all examples of persistent communication.
	~~ication~~.
	* '''Persistent''' communication allows the sender and receiver to participate at ~~dif-~~
	~~ferent~~ times. Posting letters, sending email, or leaving notes under rocks are all
	examples of persistent communication.
	* An example of persistent communication is that of '''interrupts'''. Thread A interrupts thread B by setting a bit at a location periodically checked by B. Sooner or later, B notices the bit has been set and reacts. After reacting, B typically resets the bit (A cannot reset the bit).		* An example of persistent communication is that of '''interrupts'''. Thread A interrupts thread B by setting a bit at a location periodically checked by B. Sooner or later, B notices the bit has been set and reacts. After reacting, B typically resets the bit (A cannot reset the bit).

Scott: Created page with 'Maurice Herlihy and Nir Shavit == Some Terms == * A '''safety property''' states that some "bad thing" never happens. For example, a traffic light never displays green in all di…'

2012-04-02T22:18:58Z

Created page with 'Maurice Herlihy and Nir Shavit == Some Terms == * A '''safety property''' states that some "bad thing" never happens. For example, a traffic light never displays green in all di…'

New page

Maurice Herlihy and Nir Shavit

== Some Terms ==
* A '''safety property''' states that some "bad thing" never happens. For example, a traffic light never displays green in all
directions, even if the power fails.
* A '''liveness property''' states that a particular good thing will happen. For example, a red traffic light will eventually turn green.
* The problem of making sure that only one thread at a time can execute a particular block of code is called the
'''mutual exclusion''' problem.
* The property of '''deadlock-freedom''' ensures that at least one thread will eventually gain access to some resource.
* The property of '''starvation-freedom''' ensures that every thread will eventually gain access to some resource.
* '''Transient''' communication requires both parties to participate at the same time.
Shouting, gestures, or cell phone calls are examples of transient commun-
ication.
* '''Persistent''' communication allows the sender and receiver to participate at dif-
ferent times. Posting letters, sending email, or leaving notes under rocks are all
examples of persistent communication.
* An example of persistent communication is that of '''interrupts'''. Thread A interrupts thread B by setting a bit at a location periodically checked by B. Sooner or later, B notices the bit has been set and reacts. After reacting, B typically resets the bit (A cannot reset the bit).