6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 32. 4.1 Finally, how do we actually implement serializers? The mostImplementing serializers common method is to implement serializers in terms of a more .We can implement primitive synchronization mechanism called a mutex. A mutex synchronization method, called a mutex. A mutex acts like is an object that supports two operations the mutex can be Once one process has acquired the mutex(or run the acquired, and the mutex can be released Once a mutex has been flag up the flagpole), no other process can acquire the acquired, no other acquire operations on that mutex may proceed mutex until it has been released (or the flag has been run down the flagpole) until the mutex is released Thus only one of the procedures produced by have to wait for ti ex to be released so tha A simple Scheme Mutex In our implementation, each serializer has an associated mutex (define (make-serializer Given a procedure p, the serializer returns a procedure that let ((mutex (make-mutex) acquires the mutex, runs p, and then releases the mutex. This (define (serialized-p. Args) ensures that only one of the procedures produced by the serializer (mutex ' acqui can be running at once, which is precisely the serialization (let ((val (apply p args))) property that we need to guarantee tex releas serialized-p))) Slide 32.43 The mutex is a mutable object(here we'll use a one-element list, A simple Scheme Mutex which we'll refer to as a cell)that can hold the value true or false.(define(make-mutex When the value is false, the mutex is available to be acquired 1立st普))) When the value is true, the mutex is unavailable, and any process (define (the-mutex m that attempts to acquire the mutex must wait. Rif (test-and-set! cell) Our mutex constructor make-mutex begins by initializing the the-mute cell contents to false. To acquire the mutex, we test the cell. If the clear! Cell)))) mutex is available, we set the cell contents to true and proceed the-mmutex)) Otherwise, we wait in a loop, attempting to acquire over and over (define (clear! cell again, until we find that the mutex is available. To release the mutex. we set the cell contents to false Slide 32.4. 4 mplementing test-and-set Test-and-set! tests the cell and returns the result of the test (define (test-and-set! Cell) In addition, if the test was false test-and-set! sets the ce (Ef (car cell) contents to true before returning false. We can express this cell (begin (set-car! Cell #t) behavior with the procedure shown 排f))) However, this implementation of test-and-set! does not suffice as it stands. There is a crucial subtlety here, which is the This operation must be performed atomically. directly in the hardware! essential place where concurrency control enters the system: The test-and-set! operation must be performed atomically. That is, we must guarantee that, once a process has tested the cell and found it to be false, the cell contents will actually be set to true before any other process can test the cell. If we do not make this guarantee, then the mutex can fail The actual implementation of test-and-set depends on the details of how our system runs concurrent6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 32.4.1 Finally, how do we actually implement serializers? The most common method is to implement serializers in terms of a more primitive synchronization mechanism called a mutex. A mutex is an object that supports two operations: the mutex can be acquired, and the mutex can be released. Once a mutex has been acquired, no other acquire operations on that mutex may proceed until the mutex is released. Slide 32.4.2 In our implementation, each serializer has an associated mutex. Given a procedure p, the serializer returns a procedure that acquires the mutex, runs p, and then releases the mutex. This ensures that only one of the procedures produced by the serializer can be running at once, which is precisely the serialization property that we need to guarantee. Slide 32.4.3 The mutex is a mutable object (here we'll use a one-element list, which we'll refer to as a cell) that can hold the value true or false. When the value is false, the mutex is available to be acquired. When the value is true, the mutex is unavailable, and any process that attempts to acquire the mutex must wait. Our mutex constructor make-mutex begins by initializing the cell contents to false. To acquire the mutex, we test the cell. If the mutex is available, we set the cell contents to true and proceed. Otherwise, we wait in a loop, attempting to acquire over and over again, until we find that the mutex is available. To release the mutex, we set the cell contents to false. Slide 32.4.4 Test-and-set! tests the cell and returns the result of the test. In addition, if the test was false, test-and-set! sets the cell contents to true before returning false. We can express this behavior with the procedure shown. However, this implementation of test-and-set! does not suffice as it stands. There is a crucial subtlety here, which is the essential place where concurrency control enters the system: The test-and-set! operation must be performed atomically. That is, we must guarantee that, once a process has tested the cell and found it to be false, the cell contents will actually be set to true before any other process can test the cell. If we do not make this guarantee, then the mutex can fail. The actual implementation of test-and-set! depends on the details of how our system runs concurrent