6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 32.1.6 Why is time an issue? Now why should time be an issue? For any two events, a and b detine peter (nake-account 100) ither A occurs before B. a and b are simultaneous or A occurs define paul p。tex after B But let's look at that carefully. Suppose we create an account for withdraw) 25) Peter, that Paul shares. Now suppose thatthat Peter peter Bank paull eter 100 au dollars and Paul withdraws 25 dollars from this joint account that 90 -25 initially contains 100 dollars, leaving 65 in the account.Depending on the order of the two withdrawals, the sequence of balances in the account is either 100. then 90 then 65 or 100. then 75. then 65 In a computer implementation of the banking system, this 4 hanging sequence of balances could be modeled by successive signments to the variable balance Slide 32.1.7 In complex situations, however, such a view can be problematic. Why is time an issue? Suppose that Peter and Paul, and many other people besides, are accessing the same bank account through a network of banking ance ( balance anount)) machines distributed all over the world. The actual sequence of xuffieignt fund“) balances in the account will depend critically on the detailed (peter withdraW) 10 paul withdraw) 25 timing of the accesses and the details of the communication among [Peer the machines The size of the event matters in determining whether the outcome occurs correctly This indeterminacy in the order of events can pose serious nwva|u100-25=75 roblems in the design of concurrent systems. For instance Set balance 90 that the withdrawals made by peter and Paul set balanee 75 plemented as two separate processes sharing a common variable balance, each process specified by the withdraw procedure Consider the expression(set! 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 The timing diagram 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 The general phenomenon illustrated here is that several processes may share a common state variable. What makes this complicated is that more than one process 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 the balance in a way that depends on the balance he must be able to assume that, just before the moment of change, the balance is still what he thought it was 6.001 Notes: Section 32.26.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 32.1.6 Now why should time be an issue? For any two events, A and B, either A occurs before B, A and B are simultaneous, or A occurs after B. But let's look at that carefully. Suppose we create an account for Peter, that Paul shares. Now suppose that that Peter withdraws 10 dollars and Paul withdraws 25 dollars from this joint account that initially contains 100 dollars, leaving 65 in the account. Depending on the order of the two withdrawals, the sequence of balances in the account is either 100, then 90 then 65, or 100, then 75, then 65. In a computer implementation of the banking system, this changing sequence of balances could be modeled by successive assignments to the variable balance. Slide 32.1.7 In complex situations, however, such a view can be problematic. Suppose that Peter and Paul, and many 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. The size of the event matters in determining whether the outcome occurs correctly. 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 sharing a common variable balance, each process specified by the withdraw procedure: Consider the expression (set! 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. The timing diagram 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. The general phenomenon illustrated here is that several processes may share a common state variable. What makes this complicated is that more than one process 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 the balance in a way that depends on the balance, he must be able to assume that, just before the moment of change, the balance is still what he thought it was. 6.001 Notes: Section 32.2