Any implementation of acquire and release should provide the desired operation for even for the most pathological sequences and timings of events. An incorrect implementation may be manifest in a variety of ways, including deadlock of multiple tasks, calls to acquire never returning, semaphore values becoming inconsistent, etc.

Suppose further that the operating system is intended to run on both uniprocessor and multiprocessor platforms, so mutual exclusion must be supported in some way other than disabling interrupts. This problem explores two alternative implementations.

1. Most instruction sets include special instructions that can be used for synchronization. Example instructions include test-and-set and other read-modify-write operations. In general, suitable instructions combine a read of a memory location with a modification to that location as an atomic or indivisible operation.

   Identify one instruction implemented in any processor in the x86 family that could be used for synchronization. (Feel free to use any documentation you have access to, online or otherwise.) Describe how you could use this instruction to implement efficient acquire and release routines.

2. Suppose you are targeting a CPU with no special instructions for synchronization. The following code has been proposed as a software implementation of acquire and release:

   struct semaphore
   {
       int val[NUMPROCS];    /* 1 entry for each processor */
       int lastid;           /* ID of last processor to get semaphore */
   };
   
   int procid;               /* processor ID, unique per processor */
   
   void init(struct semaphore *sem)
   {                         /* called once at beginning of execution */
       int i;
       for (i = 0; i < NUMPROCS; i++)
           sem->val[i] = 0;
       sem->lastid = 0;
   }
   
   void acquire(struct semaphore *sem)
   {
       /* assume procid holds ID of processor running this code */
       int i, j, first;
     loop:
       first = sem->lastid;
       sem->val[procid] = 1;
     forloop:
       for (i = first; i < NUMPROCS; i++)
       {
           if (i == procid)
   	{
   	    sem->val[i] = 2;
   	    for (j = 0; j < NUMPROCS; j++)
   	        if (sem->val[j] == 2 && j != procid)
   		    goto loop;
   	    sem->lastid = procid;
   	    return;      /* success!  */
   	}
   	else if (sem->val[i])
   	    goto loop;
       }
       first = 0;
       goto forloop;
   }
   
   void release(struct semaphore *sem)
   {
       sem->lastid = (procid+1) % NUMPROCS;    /* reset to next processor */
       sem->val[procid] = 0;
   }
   

   Does this implementation of acquire and release actually work? If not, show a situation in which it malfunctions. If it does work, describe the approach taken by the algorithm to guarantee mutual exclusion.