.. _ts:

Test and Set Instruction
----------------------------------------------

**Test_and_Set** is a special assembly language instruction that does two
operations autonomously.  That is, the instruction can not be interrupted in
the middle and it is not necessary to disable interrupts.  *Test_and_Set* (TS)
is a privileged instruction requiring supervisory mode permissions. (See
:ref:`mode`).  The action of *Test_and_Set* is described with the following
pseudo-code::

    boolean Test_and_Set( boolean memory[m] )
    { [
        if( memory[m] )        // lock denied
            return True;
        else {                 // lock granted
            memory[m] = True;
            return False;
        }
      ]
    }

.. centered:: TS(m): [Reg_i = memory[m]; memory[m] = TRUE;]

.. figure:: ts.png
   :align: center

   The Autonomous Two Step TS Instruction 


Implementing Semaphores with Test and Set
----------------------------------------------

::

    struct semaphore {
        int value = <initial value>;
        boolean mutex = FALSE;
        boolean hold = TRUE;
        queue m, h;
    };

    shared struct semaphore s;

    /* P() */
    acquire_semaphore(struct semaphore s) {  
        while(TS(s.mutex)) WAIT(s.m);    /* wait for intertal mutex */
        s.value--;
        if(s.value < 0) {
            s.mutex = FALSE;
            SIGNAL(s.m);
            while(TS(s.hold)) WAIT(s.h); /* wait - too many out */
        }
        else
            s.mutex = FALSE;
            SIGNAL(s.m);
    }

    /* V() */
    release_semaphore(struct semaphore s) {
        while(TS(s.mutex)) WAIT(s.m);   /* wait for intertal mutex */
        s.value++;
        if(s.value >= 0) {
            s.hold = FALSE;
            SIGNAL(s.h);
        }
        s.mutex = FALSE;
        SIGNAL(s.m);
    }