GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

No menu could be recovered. Follow the blue links in the page.

This view

  • Original page
  • New address

GeezerVison is showing sicp.sourceacademy.org — 3.4.1 The Nature of Time in Concurrent Systems - SICP Comparison Edition

SICP — Scheme/JS Structure and Interpretation of Computer Programs — Comparison Edition
 
Foreword
Foreword to Structure and Interpretation of Computer Programs, 1984
Preface
Prefaces to Structure and Interpretation of Computer Programs, 1996 & 1984
Acknowledgments
➤ ▼ 1 Building Abstractions with Procedures Functions
➤ ▼ 1.1 The Elements of Programming
1.1.1 Expressions
1.1.2 Naming and the Environment
1.1.3 Evaluating Combinations Operator Combinations
1.1.4 Compound Procedures Functions
1.1.5 The Substitution Model for Procedure Function Application
1.1.6 Conditional Expressions and Predicates
1.1.7 Example: Square Roots by Newton's Method
1.1.8 Procedures Functions as Black-Box Abstractions
➤ ▼ 1.2 Procedures Functions and the Processes They Generate
1.2.1 Linear Recursion and Iteration
1.2.2 Tree Recursion
1.2.3 Orders of Growth
1.2.4 Exponentiation
1.2.5 Greatest Common Divisors
1.2.6 Example: Testing for Primality
➤ ▼ 1.3 Formulating Abstractions with Higher-Order Procedures Functions
1.3.1 Procedures Functions as Arguments
1.3.2 Constructing Procedures using Lambda Constructing Functions using Lambda Expressions
1.3.3 Procedures Functions as General Methods
1.3.4 Procedures Functions as Returned Values
➤ ▼ 2 Building Abstractions with Data
➤ ▼ 2.1 Introduction to Data Abstraction
2.1.1 Example: Arithmetic Operations for Rational Numbers
2.1.2 Abstraction Barriers
2.1.3 What Is Meant by Data?
2.1.4 Extended Exercise: Interval Arithmetic
➤ ▼ 2.2 Hierarchical Data and the Closure Property
2.2.1 Representing Sequences
2.2.2 Hierarchical Structures
2.2.3 Sequences as Conventional Interfaces
2.2.4 Example: A Picture Language
➤ ▼ 2.3 Symbolic Data
2.3.1 Quotation Strings
2.3.2 Example: Symbolic Differentiation
2.3.3 Example: Representing Sets
2.3.4 Example: Huffman Encoding Trees
➤ ▼ 2.4 Multiple Representations for Abstract Data
2.4.1 Representations for Complex Numbers
2.4.2 Tagged data
2.4.3 Data-Directed Programming and Additivity
➤ ▼ 2.5 Systems with Generic Operations
2.5.1 Generic Arithmetic Operations
2.5.2 Combining Data of Different Types
2.5.3 Example: Symbolic Algebra
➤ ▼ 3 Modularity, Objects, and State
➤ ▼ 3.1 Assignment and Local State
3.1.1 Local State Variables
3.1.2 The Benefits of Introducing Assignment
3.1.3 The Costs of Introducing Assignment
➤ ▼ 3.2 The Environment Model of Evaluation
3.2.1 The Rules for Evaluation
3.2.2 Applying Simple Procedures Functions
3.2.3 Frames as the Repository of Local State
3.2.4 Internal Definitions Declarations
3.2.5 CSE Machine
➤ ▼ 3.3 Modeling with Mutable Data
3.3.1 Mutable List Structure
3.3.2 Representing Queues
3.3.3 Representing Tables
3.3.4 A Simulator for Digital Circuits
3.3.5 Propagation of Constraints
➤ ▼ 3.4 Concurrency: Time Is of the Essence
3.4.1 The Nature of Time in Concurrent Systems
3.4.2 Mechanisms for Controlling Concurrency
➤ ▼ 3.5 Streams
3.5.1 Streams Are Delayed Lists
3.5.2 Infinite Streams
3.5.3 Exploiting the Stream Paradigm
3.5.4 Streams and Delayed Evaluation
3.5.5 Modularity of Functional Programs and Modularity of Objects
➤ ▼ 4 Metalinguistic Abstraction
➤ ▼ 4.1 The Metacircular Evaluator
4.1.1 The Core of the Evaluator
4.1.2 Representing Expressions Components
4.1.3 Evaluator Data Structures
4.1.4 Running the Evaluator as a Program
4.1.5 Data as Programs
4.1.6 Internal Definitions Declarations
4.1.7 Separating Syntactic Analysis from Execution
➤ ▼ 4.2 Variations on a Scheme: Lazy Evaluation
4.2.1 Normal Order and Applicative Order
4.2.2 An Interpreter with Lazy Evaluation
4.2.3 Streams as Lazy Lists
➤ ▼ 4.3 Variations on a Scheme: Nondeterministic Computing
4.3.1 Amb and Search Search and amb
4.3.2 Examples of Nondeterministic Programs
4.3.3 Implementing the Amb amb Evaluator
➤ ▼ 4.4 Logic Programming
4.4.1 Deductive Information Retrieval
4.4.2 How the Query System Works
4.4.3 Is Logic Programming Mathematical Logic?
4.4.4 Implementing the Query System
➤ ▼ 5 Computing with Register Machines
➤ ▼ 5.1 Designing Register Machines
5.1.1 A Language for Describing Register Machines
5.1.2 Abstraction in Machine Design
5.1.3 Subroutines
5.1.4 Using a Stack to Implement Recursion
5.1.5 Instruction Summary
➤ ▼ 5.2 A Register-Machine Simulator
5.2.1 The Machine Model
5.2.2 The Assembler
5.2.3 Generating Execution Procedures for Instructions Instructions and Their Execution Functions
5.2.4 Monitoring Machine Performance
➤ ▼ 5.3 Storage Allocation and Garbage Collection
5.3.1 Memory as Vectors
5.3.2 Maintaining the Illusion of Infinite Memory
➤ ▼ 5.4 The Explicit-Control Evaluator
5.4.1 The Core of the Explicit-Control Evaluator The Dispatcher and Basic Evaluation
5.4.2 Sequence Evaluation and Tail Recursion Evaluating Function Applications
5.4.3 Conditionals, Assignments and Definitions Blocks, Assignments, and Declarations
5.4.4 Running the Evaluator
➤ ▼ 5.5 Compilation
5.5.1 Structure of the Compiler
5.5.2 Compiling Expressions Components
5.5.3 Compiling Combinations Applications and Return Statements
5.5.4 Combining Instruction Sequences
5.5.5 An Example of Compiled Code
5.5.6 Lexical Addressing
5.5.7 Interfacing Compiled Code to the Evaluator
References
About the SICP JS Project
Permalink copied!
3.4.1 The Nature of Time in Concurrent Systems

On the surface, time seems straightforward. It is an ordering imposed on events.[1] For any events $A$ and $B$, either $A$ occurs before $B$, $A$ and $B$ are simultaneous, or $A$ occurs after $B$. For instance, returning to the bank account example, suppose that Peter withdraws $10 and Paul withdraws $25 from a joint account that initially contains $100, leaving $65 in the account. Depending on the order of the two withdrawals, the sequence of balances in the account is either $\$100 \rightarrow \$90 \rightarrow\$65$ or $\$100 \rightarrow \$75 \rightarrow\$65$. In a computer implementation of the banking system, this changing sequence of balances could be modeled by successive assignments to a variable balance.

In complex situations, however, such a view can be problematic. Suppose that Peter and Paul, and other people besides, are accessing the same bank account through a network of banking machines distributed all over the world. The actual sequence of balances in the account will depend critically on the detailed timing of the accesses and the details of the communication among the machines.

This indeterminacy in the order of events can pose serious problems in the design of concurrent systems. For instance, suppose that the withdrawals made by Peter and Paul are implemented as two separate processes threads sharing a common variable balance, each process thread specified by the procedure function given in section 3.1.1:

Original JavaScript
(define (withdraw amount) (if (>= balance amount) (begin (set! balance (- balance amount)) balance) "Insufficient funds")) function withdraw(amount) { if (balance >= amount) { balance = balance - amount; return balance; } else { return "Insufficient funds"; } }
If the two processes threads operate independently, then Peter might test the balance and attempt to withdraw a legitimate amount. However, Paul might withdraw some funds in between the time that Peter checks the balance and the time Peter completes the withdrawal, thus invalidating Peter's test.

Things can be worse still. Consider the expression statement

Original JavaScript
(set! balance (- balance amount)) balance = balance - amount;
executed as part of each withdrawal process. This consists of three steps: (1) accessing the value of the balance variable; (2) computing the new balance; (3) setting balance to this new value. If Peter and Paul's withdrawals execute this statement concurrently, then the two withdrawals might interleave the order in which they access balance and set it to the new value.

Original JavaScript
Figure 3.52 Timing diagram showing how interleaving the order of events in two banking withdrawals can lead to an incorrect final balance.
Figure 3.53 Timing diagram showing how interleaving the order of events in two banking withdrawals can lead to an incorrect final balance.

The timing diagram in figure 3.52 figure 3.53 depicts an order of events where balance starts at 100, Peter withdraws 10, Paul withdraws 25, and yet the final value of balance is 75. As shown in the diagram, the reason for this anomaly is that Paul's assignment of 75 to balance is made under the assumption that the value of balance to be decremented is 100. That assumption, however, became invalid when Peter changed balance to 90. This is a catastrophic failure for the banking system, because the total amount of money in the system is not conserved. Before the transactions, the total amount of money was $100. Afterwards, Peter has $10, Paul has $25, and the bank has $75.[2]

The general phenomenon illustrated here is that several processes threads may share a common state variable. What makes this complicated is that more than one process thread may be trying to manipulate the shared state at the same time. For the bank account example, during each transaction, each customer should be able to act as if the other customers did not exist. When a customer changes customers change the balance in a way that depends on the balance, he they must be able to assume that, just before the moment of change, the balance is still what he they thought it was.

Correct behavior of concurrent programs

The above example typifies the subtle bugs that can creep into concurrent programs. The root of this complexity lies in the assignments to variables that are shared among the different processes threads. We already know that we must be careful in writing programs that use set!, assignment, because the results of a computation depend on the order in which the assignments occur.[3] With concurrent processes threads we must be especially careful about assignments, because we may not be able to control the order of the assignments made by the different processes threads. If several such changes might be made concurrently (as with two depositors accessing a joint account) we need some way to ensure that our system behaves correctly. For example, in the case of withdrawals from a joint bank account, we must ensure that money is conserved. To make concurrent programs behave correctly, we may have to place some restrictions on concurrent execution.

One possible restriction on concurrency would stipulate that no two operations that change any shared state variables can occur at the same time. This is an extremely stringent requirement. For distributed banking, it would require the system designer to ensure that only one transaction could proceed at a time. This would be both inefficient and overly conservative. Figure 3.54 shows Peter and Paul sharing a bank account, where Paul has a private account as well. The diagram illustrates two withdrawals from the shared account (one by Peter and one by Paul) and a deposit to Paul's private account.[4] The two withdrawals from the shared account must not be concurrent (since both access and update the same account), and Paul's deposit and withdrawal must not be concurrent (since both access and update the amount in Paul's wallet). But there should be no problem permitting Paul's deposit to his private account to proceed concurrently with Peter's withdrawal from the shared account.

Figure 3.54 Concurrent deposits and withdrawals from a joint account in Bank1 and a private account in Bank2.

A less stringent restriction on concurrency would ensure that a concurrent system produces the same result as if the processes threads had run sequentially in some order. There are two important aspects to this requirement. First, it does not require the processes threads to actually run sequentially, but only to produce results that are the same as if they had run sequentially. For the example in figure 3.54, the designer of the bank account system can safely allow Paul's deposit and Peter's withdrawal to happen concurrently, because the net result will be the same as if the two operations had happened sequentially. Second, there may be more than one possible correct result produced by a concurrent program, because we require only that the result be the same as for some sequential order. For example, suppose that Peter and Paul's joint account starts out with $100, and Peter deposits $40 while Paul concurrently withdraws half the money in the account. Then sequential execution could result in the account balance being either $70 or $90 (see exercise 3.38).[5]

There are still weaker requirements for correct execution of concurrent programs. A program for simulating diffusion (say, the flow of heat in an object) might consist of a large number of processes, threads, each one representing a small volume of space, that update their values concurrently. Each process thread repeatedly changes its value to the average of its own value and its neighbors' values. This algorithm converges to the right answer independent of the order in which the operations are done; there is no need for any restrictions on concurrent use of the shared values.

Exercise 3.38 Suppose that Peter, Paul, and Mary share a joint bank account that initially contains $100. Concurrently, Peter deposits $10, Paul withdraws $20, and Mary withdraws half the money in the account, by executing the following commands:
Original JavaScript
Peter: (set! balance (+ balance 10))
Paul: (set! balance (- balance 20))
Mary: (set! balance (- balance (/ balance 2)))
Peter: balance = balance + 10
Paul: balance = balance - 20
Mary: balance = balance - (balance / 2)
  1. List all the different possible values for balance balance after these three transactions have been completed, assuming that the banking system forces the three processes threads to run sequentially in some order.
  2. What are some other values that could be produced if the system allows the processes threads to be interleaved? Draw timing diagrams like the one in figure 3.53 to explain how these values can occur.
There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

[1] To quote some graffiti seen on a building wall in Cambridge, Massachusetts: Time is a device that was invented to keep everything from happening at once.
[2] An even worse failure for this system could occur if the two set! operations assignments attempt to change the balance simultaneously, in which case the actual data appearing in memory might end up being a random combination of the information being written by the two processes threads. Most computers have interlocks on the primitive memory-write operations, which protect against such simultaneous access. Even this seemingly simple kind of protection, however, raises implementation challenges in the design of multiprocessing computers, where elaborate cache-coherence protocols are required to ensure that the various processors will maintain a consistent view of memory contents, despite the fact that data may be replicated (cached) among the different processors to increase the speed of memory access.
[3] The factorial program in section 3.1.3 illustrates this for a single sequential process thread.
[4] The columns show the contents of Peter's wallet, the joint account (in Bank1), Paul's wallet, and Paul's private account (in Bank2), before and after each withdrawal (W) and deposit (D). Peter withdraws $10 from Bank1; Paul deposits $5 in Bank2, then withdraws $25 from Bank1.
[5] A more formal way to express this idea is to say that concurrent programs are inherently nondeterministic. That is, they are described not by single-valued functions, but by functions whose results are sets of possible values. In section 4.3 we will study a language for expressing nondeterministic computations.
< Previous
Next >
3.4.1   The Nature of Time in Concurrent Systems
You are visitor 01402639 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.