SICP

Exercise 3.51.    In order to take a closer look at delayed evaluation, we will use the following procedure, which simply returns its argument after printing it: (define (show x)   (display-line x)   x) What does the interpreter print in response to evaluating each expression in the following sequence? 59 (define x (stream-map show (stream-enumerate-interval 0 10))) (stream-ref x 5) (stream-ref x 7) SOLUTION The code and tests are here . Note: I spent a lot of time tracing through the logic to see what really happens here. The delayed evaluation of items in streams combined with new streams being produced in procedure stream-map makes it really confusing.  Also, note that in Racket, both the car part and the cdr part of the stream are delayed evaluations until the point of need.

Exercise 3.50.   Complete the following definition, which generalizes  stream-map  to allow procedures that take multiple arguments, analogous to  map  in section  2.2.3 , footnote  12 . (define (stream-map proc . argstreams)   (if (< ?? > (car argstreams))       the-empty-stream       (< ?? >        (apply proc (map < ?? > argstreams))        (apply stream-map               (cons proc (map < ?? > argstreams)))))) SOLUTION The code and tests are here .

Exercise 3.49.   Give a scenario where the deadlock-avoidance mechanism described above does not work. (Hint: In the exchange problem, each process knows in advance which accounts it will need to get access to. Consider a situation where a process must get access to some shared resources before it can know which additional shared resources it will require.) EXPLANATION Consider the case where we have two bank branches in different locations and an account can be accessed  at each branch. For fast local access, we allow withdrawals and deposits at each location and design  a way to keep the account balance at both locations synchronized. Concurrent processes can access and change  the balance in either location. In order to keep the balance the same in both locations, we write a procedure  similar to 'synchronized-exchange' but which first updates the local balance and then the remote balance. This  procedure acquires a lock on the local account first and then the remote

Exercise 3.48.    Explain in detail why the deadlock-avoidance method described above, (i.e., the accounts are numbered, and each process attempts to acquire the smaller-numbered account first) avoids deadlock in the exchange problem. Rewrite  serialized-exchange  to incorporate this idea. (You will also need to modify  make-account  so that each account is created with a number, which can be accessed by sending an appropriate message.) SOLUTION The code and tests are here . Explanation: I run four tests here: Test 1: Main thread runs serialized-exchange. There is no concurrency. So it just works. Test 2: Two threads run serialized-exchange in parallel with opposite account orders. In this case  the first thread almost always acquires both the accounts before the 2nd thread tries to acquire account 2.  So again, thread 1 is able to complete the exchange and thread 2 starts its work only after that. So  even though a deadlock is theoretically possible, practically it doesn

Exercise 3.47.    A semaphore (of size  n ) is a generalization of a mutex. Like a mutex, a semaphore supports acquire and release operations, but it is more general in that up to  n  processes can acquire it concurrently. Additional processes that attempt to acquire the semaphore must wait for release operations. Give implementations of semaphores a. in terms of mutexes b. in terms of atomic  test-and-set!  operations. SOLUTION The code is here . While implementing in terms of atomic test and set operations, the semaphore logic is similar to that of the mutex but instead of the binary (true or false) cell that the mutex uses,  the semaphore uses a number with a maximum possible value of 'size'. When the semaphore is acquired, the number is incremented (up to a max of 'size') and when the semaphore is released, the number is decremented.

Exercise 3.47.    A semaphore (of size  n ) is a generalization of a mutex. Like a mutex, a semaphore supports acquire and release operations, but it is more general in that up to  n  processes can acquire it concurrently. Additional processes that attempt to acquire the semaphore must wait for release operations. Give implementations of semaphores a. in terms of mutexes b. in terms of atomic  test-and-set!  operations. SOLUTION The code is here . The make-semaphore procedure object manages within its local state, a set of mutexes in two lists: a free list and an acquired list. (See code documentation for details of the implementation.) Instead of a serializer, which does not make sense for a semaphore, I have implemented a concurrency limiter that internally maintains the semaphore. The test shown in the program tries to run ten threads simultaneously with a concurrency-limit of 3. The test results reflect this fact. Only 3 threads are able to run at a time.

Exercise 3.46.   Suppose that we implement  test-and-set!  using an ordinary procedure as shown in the text, without attempting to make the operation atomic. Draw a timing diagram like the one in figure  3.29  to demonstrate how the mutex implementation can fail by allowing two processes to acquire the mutex at the same time. SOLUTION

Exercise 3.45.   Louis Reasoner thinks our bank-account system is unnecessarily complex and error-prone now that deposits and withdrawals aren't automatically serialized. He suggests that  make-account-and-serializer  should have exported the serializer (for use by such procedures as  serialized-exchange ) in addition to (rather than instead of) using it to serialize accounts and deposits as  make-account  did. He proposes to redefine accounts as follows: (define (make-account-and-serializer balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (let ((balance-serializer (make-serializer)))     (define (dispatch m)       (cond ((eq? m 'withdraw) (balance-serializer withdraw))             ((eq? m 'deposit) (balance-serializer deposit))             ((eq? m 'balance)

Exercise 3.44.    Consider the problem of transferring an amount from one account to another. Ben Bitdiddle claims that this can be accomplished with the following procedure, even if there are multiple people concurrently transferring money among multiple accounts, using any account mechanism that serializes deposit and withdrawal transactions, for example, the version of  make-account  in the text above. (define (transfer from-account to-account amount)   ((from-account 'withdraw) amount)   ((to-account 'deposit) amount)) Louis Reasoner claims that there is a problem here, and that we need to use a more sophisticated method, such as the one required for dealing with the exchange problem. Is Louis right? If not, what is the essential difference between the transfer problem and the exchange problem? (You should assume that the balance in  from-account  is at least  amount .) SOLUTION Louis Reasoner is wrong. Ben Bitdiddle is right: Even if there are multiple people conc

Exercise 3.43.   Suppose that the balances in three accounts start out as $10, $20, and $30, and that multiple processes run, exchanging the balances in the accounts. Argue that if the processes are run sequentially, after any number of concurrent exchanges, the account balances should be $10, $20, and $30 in some order. Draw a timing diagram like the one in figure  3.29  to show how this condition can be violated if the exchanges are implemented using the first version of the account-exchange program in this section. On the other hand, argue that even with this  exchange  program, the sum of the balances in the accounts will be preserved. Draw a timing diagram to show how even this condition would be violated if we did not serialize the transactions on individual accounts. SOLUTION Part 1: Suppose that the balances start out as $10, $20 and $30 and the processes run sequentially  and they execute the first version (i.e. the non-serialized version) of the exchange procedure ----

Exercise 3.42.   Ben Bitdiddle suggests that it's a waste of time to create a new serialized procedure in response to every  withdraw  and  deposit  message. He says that  make-account  could be changed so that the calls to  protected  are done outside the  dispatch procedure. That is, an account would return the same serialized procedure (which was created at the same time as the account) each time it is asked for a withdrawal procedure. (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)   (let ((protected (make-serializer)))     (let ((protected-withdraw (protected withdraw))           (protected-deposit (protected deposit)))       (define (dispatch m)         (cond ((eq? m 'withdraw) protected-withdraw)               ((eq? m 'deposit) protec

Exercise 3.41.   Ben Bitdiddle worries that it would be better to implement the bank account as follows (where the commented line has been changed): (define (make-account balance)   (define (withdraw amount)     (if (>= balance amount)         (begin (set! balance (- balance amount))                balance)         "Insufficient funds"))   (define (deposit amount)     (set! balance (+ balance amount))     balance)    ;; continued on next page   (let ((protected (make-serializer)))     (define (dispatch m)       (cond ((eq? m 'withdraw) (protected withdraw))             ((eq? m 'deposit) (protected deposit))             ((eq? m 'balance)              ((protected (lambda () balance))))  ; serialized             (else (error "Unknown request -- MAKE-ACCOUNT"                          m))))     dispatch)) because allowing unserialized access to the bank balance can result in anomalous behavior. Do you agree? Is there any scenario that demonstrates Ben