Art of Multiprocessor Programming: Difference between revisions
Jump to navigation
Jump to search
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…' |
|||
| 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 | * '''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 | |||
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). | ||
Revision as of 22:19, 2 April 2012
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 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).