6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 32.2.1 The above example typifies the subtle bugs that can creep into Correct behavior of concurrent programs concurrent programs. The root of this complexity lies in the REQUIRE assignments to variables that are shared among the different ations that change any shared state variables can occur at the same time processes. We already know that we must be careful in writing That a concurrent system produces the same result as if programs that use set!, because the results of a computation the processes had run sequentially in some order depend on the order in which the assignments occur With concurrent processes 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. If several sut changes might be made concurrently(as with two depositors accessing a joint account)we need some way to ensure that our 4 stem 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 a less stringent restriction on concurrency would ensure that a concurrent system produces the same result as if the processes had run sequentially in some order Slide 32.2.2 Correct behavior of concurrent programs There are two important aspects to this requirement. First, it does REQUIRE not require the processes to actually run sequentially, but only to That no two operations that change any shared state produce results that are the same as if they had run sequentially That a concurrent system produces the same result as if For our previous example, the designer of the bank account system the processes had run sequentially in some orde fely allow Paul's deposit and Peter,s withdrawal to happen by to areer e sa es ey a urena. concurrently, because the net result will be the same as if the two sequentially operations had happened sequentially. Second, there may be more -There may be more than one"correct" result as a han one possible correct result produced by a concurrent progra because we require only that the result be the same as for some sequential order Slide 32. 2.3 Let's look at this a bit more carefully Parallel execution To make the above mechanism more concrete, suppose that we (define x 10) have extended Scheme to include a procedure called parallel (define p3 (Lambda ((set! x (*xx))) execute this procedure takes a set of procedures of no ( define p4(1 anda()《set!K件x1)))) arguments as input. It then creates a separate process for each such procedure( think of this as a separate evaluator, with its own environment) and applies such procedure within that process. All these processes(or evaluators)then run concurrently As an example of how this is used, consider the example shown here This creates two concurrent processes: Pl, which sets x to x times 4 x and p2. which increments x6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 32.2.1 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. We already know that we must be careful in writing programs that use set!, because the results of a computation depend on the order in which the assignments occur. With concurrent processes 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. 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. A less stringent restriction on concurrency would ensure that a concurrent system produces the same result as if the processes had run sequentially in some order. Slide 32.2.2 There are two important aspects to this requirement. First, it does not require the processes to actually run sequentially, but only to produce results that are the same as if they had run sequentially. For our previous example, 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. Slide 32.2.3 Let's look at this a bit more carefully. To make the above mechanism more concrete, suppose that we have extended Scheme to include a procedure called parallel￾execute: this procedure takes a set of procedures of no arguments as input. It then creates a separate process for each such procedure (think of this as a separate evaluator, with its own environment) and applies such procedure within that process. All these processes (or evaluators) then run concurrently. As an example of how this is used, consider the example shown here. This creates two concurrent processes: P1, which sets x to x times x, and P2, which increments x