Exercises M1 and M2

M1: Semaphores that busy-wait can be implemented with shared variables and a TSL (test and set lock) instruction, which atomically sets a variable to 1 and returns the old value of that variable. Show how to implement the semaphore wait(), to work with the following signal() procedure. A semaphore here is a record consisting of two shared variables: S.val for the semaphore value, and S.lock, for mutual exclusion; both values are initially 0.

                     signal(S) {
                        while(TSL(S.lock)) ;
                        S.val = S.val + 1 ;     
                        S.lock = 0 ;
                        }

M2: Professor Basil Fawlty has discovered the "Fawlty Exclusion Algorithm," a purported solution to the two-process mutual exclusion problem. The code is as follows. Initially, flag0 = 0, flag1 = 0, and turn = 0.

        Process P0:  while (alive) {
                        flag0 = 1 ;   
                        turn  = 1 ;
                        if ( turn==1 ) while ( flag1 ) ;
                        critical_section() ;
                        flag0 = 0 ;
                        }

        Process P1:  while (alive) {
                        flag1 = 1 ;   
                        turn  = 0 ;
                        if ( turn==0 ) while ( flag0 ) ;
                        critical_section() ;
                        flag1 = 0 ;
                        }

If you think the Fawlty algorithm is correct, give a short justification. If you think the algorithm is not correct, then explain which condition for a good critical section solution fails, and give a trace to show what goes wrong.