4.2.3. 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 CPU Execution 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;
    }
  ]
}

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

The Autonomous Two Step TS Instruction

4.2.4. 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 internal 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 internal mutex */
    s.value++;
    if(s.value >= 0) {
        s.hold = FALSE;
        SIGNAL(s.h);
    }
    s.mutex = FALSE;
    SIGNAL(s.m);
}