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;]
![../_images/ts.png](../_images/ts.png)
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 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);
}