6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 32.3.3 For correct behavior, we must arrange for the exchange Locking out access to shared state variables procedure to lock out any other concurrent accesses to the [detine (make-acceumt-with-serializer balance) accounts during the entire time of the exchange if d> balance (begin tset Balance(- balance amount)) One way we can accomplish this is by using both account Insuffieient fundal serializers to serialize the entire exchange procedure. To do this ance (+ b we will arrange for access to an account's serializer Note that we 41mt((ba1anE-都x主a1(mk一x1a1主x})) are deliberately breaking the modularity of the bank-account object by exposing the serializer. This version of make (eg? H balance) h ((q?目1a1主eE)ba1an日一er1a1i) account is identical to the original version, except that a else (errer wunknuvn request n))) serializer is provided to protect the balance variable, and the serializer is exported via message passing Serialized access to shared variables We can use this to do serialized deposits and withdrawals (define (deposit account amount However. unlike our earlier serialized account. it is now the responsibility of each user of bank-account objects to explicitly ( d (account ]deposit))) ((s d) amount))) manage the serialization. For example, we might create a deposit procedure that gets access to the balance through the serializer, hus ensuring that it only gains access if no one else is using it et ((serializer (acctl se (serializer(acct ' se D) Exporting the serializer in this way gives us enough flexibility to ((serializer (serializer acct original exchange procedure with the serializers for both acct))) accounts as shown Slide 32.3.5 Even with the serialization technique discussed above, account Deadlocks exchanging still has a problem. Imagine that Peter attempts to ppose Peter attempts to exchange al with a2 exchange al with a2 while Paul concurrently attempts to exchange. And Paul attempts to exchange a2 with a1 a2 with al. Suppose that Peter,s process reaches the point where it has entered a serialized procedure protecting al and, just after that,I time that Pallo or gets the serializer for a1 at the same Paul's process enters a serialized procedure protecting a2. Now Now Peter is stalled waiting for the serializer from a 2, but Paul is holding it. Peter cannot proceed(to enter a serialized procedure protecting a2 ) And Paul is similarly waiting for the serializer from at, but until Paul exits the serialized procedure protecting a2. Similarly Peter is holding it, Paul cannot proceed until Peter exits the serialized procedure This'deadly embrace"is called a deadlock. protecting al. Each process is stalled forever, waiting for the other This situation is called a deadlock Deadlock is always a danger in 4 systems that provide concurrent access to multiple shared One way to avoid the deadlock in this situation is to give each account a unique identification number and rewrite exchange so that a process will always attempt to enter a procedure protecting the lowest-numbered account first Although this method works well for the exchange problem, there are other situations that require more sophisticated deadlock-avoidance techniques, or where deadlock cannot be avoided at all 6.001 Notes: Section 32. 46.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 32.3.3 For correct behavior, we must arrange for the exchange procedure to lock out any other concurrent accesses to the accounts during the entire time of the exchange. One way we can accomplish this is by using both accounts' serializers to serialize the entire exchange procedure. To do this, we will arrange for access to an account's serializer. Note that we are deliberately breaking the modularity of the bank-account object by exposing the serializer. This version of make￾account is identical to the original version, except that a serializer is provided to protect the balance variable, and the serializer is exported via message passing. Slide 32.3.4 We can use this to do serialized deposits and withdrawals. However, unlike our earlier serialized account, it is now the responsibility of each user of bank-account objects to explicitly manage the serialization. For example, we might create a deposit procedure that gets access to the balance through the serializer, thus ensuring that it only gains access if no one else is using it. Exporting the serializer in this way gives us enough flexibility to implement a serialized exchange program. We simply serialize the original exchange procedure with the serializers for both accounts, as shown. Slide 32.3.5 Even with the serialization technique discussed above, account exchanging still has a problem. Imagine that Peter attempts to exchange a1 with a2 while Paul concurrently attempts to exchange a2 with a1. Suppose that Peter's process reaches the point where it has entered a serialized procedure protecting a1 and, just after that, Paul's process enters a serialized procedure protecting a2. Now Peter cannot proceed (to enter a serialized procedure protecting a2) until Paul exits the serialized procedure protecting a2. Similarly, Paul cannot proceed until Peter exits the serialized procedure protecting a1. Each process is stalled forever, waiting for the other. This situation is called a deadlock. Deadlock is always a danger in systems that provide concurrent access to multiple shared resources. One way to avoid the deadlock in this situation is to give each account a unique identification number and rewrite exchange so that a process will always attempt to enter a procedure protecting the lowest-numbered account first. Although this method works well for the exchange problem, there are other situations that require more sophisticated deadlock-avoidance techniques, or where deadlock cannot be avoided at all. 6.001 Notes: Section 32.4