SICP Exercise 3.48 deadlock avoidance
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't happen. This is where the next test comes in.
Test 3: Two threads run serialized-exchange in parallel with opposite account orders. However, there is a 1 second delay after any mutex is acquired so as to increase the chances of a deadlock. The idea is for a thread to acquire mutex 1 and delay before acquiring the mutex 2. This gives the other thread a chance to acquire mutex 2 thereby creating a deadlock. This is the reason the sleep command needs to be in 'make-serializer' immediately after the mutex is acquired. This sleep command is commented out while running tests 1 and 2. Sure enough, when we run test 3 we encounter a deadlock situation (See test results.)
Test 4: Two threads run serialized-exchange-da in parallel with opposite account orders. The suffice 'da' stands for deadlock avoidance. The 1 second delay after the mutex is acquired is still there. This new procedure avoids the deadlock using the technique described in the question. Accounts are acquired in the same order. See results below. There is no deadlock.
So why does this technique work? The reason is that we have added another level of serialization here. The first level of serialization is to make concurrent processes execute a procedure serially. This works well when there is only resource to serialize over. But when we have two or more resources and they need to be acquired together by each thread but are acquired in different orders by different threads, we get deadlocks. To overcome this situation, we essentially 'serialize the serialization' so that threads acquire a set of resources in the same order. In other words, we make the threads 'line-up' with each other by acquiring resources in the same order. This ensures that all threads also release resources in the same order (which will be the reverse of the order in which the resources were acquired.)
We can also look at this as a 'pipeline' of resources that each thread acquires from beginning to end and releases from end to beginning. So in effect, the threads will get serialized over the entire set of resources as if it is one big resource.
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't happen. This is where the next test comes in.
Test 3: Two threads run serialized-exchange in parallel with opposite account orders. However, there is a 1 second delay after any mutex is acquired so as to increase the chances of a deadlock. The idea is for a thread to acquire mutex 1 and delay before acquiring the mutex 2. This gives the other thread a chance to acquire mutex 2 thereby creating a deadlock. This is the reason the sleep command needs to be in 'make-serializer' immediately after the mutex is acquired. This sleep command is commented out while running tests 1 and 2. Sure enough, when we run test 3 we encounter a deadlock situation (See test results.)
Test 4: Two threads run serialized-exchange-da in parallel with opposite account orders. The suffice 'da' stands for deadlock avoidance. The 1 second delay after the mutex is acquired is still there. This new procedure avoids the deadlock using the technique described in the question. Accounts are acquired in the same order. See results below. There is no deadlock.
So why does this technique work? The reason is that we have added another level of serialization here. The first level of serialization is to make concurrent processes execute a procedure serially. This works well when there is only resource to serialize over. But when we have two or more resources and they need to be acquired together by each thread but are acquired in different orders by different threads, we get deadlocks. To overcome this situation, we essentially 'serialize the serialization' so that threads acquire a set of resources in the same order. In other words, we make the threads 'line-up' with each other by acquiring resources in the same order. This ensures that all threads also release resources in the same order (which will be the reverse of the order in which the resources were acquired.)
We can also look at this as a 'pipeline' of resources that each thread acquires from beginning to end and releases from end to beginning. So in effect, the threads will get serialized over the entire set of resources as if it is one big resource.
Comments
Post a Comment