Semaphores with test and set (code implementation possible mistake)

Question

I have been learning about semaphores and I was looking at a website implementation of semaphores (http://faculty.salina.k-state.edu/tim/ossg/IPC_sync/ts.html), however, I don't understand the implementation, to save anyone going to the website the code is shown below.

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);
}

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

The TS method I have assumed is TestandSet(), which is also shown above copied from the same website, my issue is that if 3 processes come along and call acquire_semaphore with a semaphore initialized at a value of 1 then the value of the semaphore will become -2 and the processes p2 and p3 will go into the h queue and never been signalled to wake, this doesn't seem correct so I am assuming there is a mistake in the code? My assumption to fix this would be that the line "if(s.value >= 0) {" in release semaphore should be "if(s.value <= 0) {" since this would then wake the next process in the held (h) queue. I have a shown below a table of me working through the code by hand with 3 processes named p1,p2 and p3. Thank you for any help.

Action            | Value | Mutex | Hold | m  | h       | Comments
init              | 1     | FALSE | TRUE | [] | []      | 
P1 aquire lock    | 0     | FALSE | TRUE | [] | []      | P1 now has the semaphore
P2 aquire lock    | -1    | FALSE | TRUE | [] | [P2]    | P2 added to the h queue
P3 aquire lock    | -2    | FALSE | TRUE | [] | [P2,P3] | p3 added to the h queue
P1 release lock   | -1    | FALSE | TRUE | [] | [P2,P3] | lock released but since s.value is <= 0 signal not set to wake s.h queue

mevets · Accepted Answer · 2020-04-26T22:44:19.970

First:

acquire_semaphore(struct semaphore s)

When this is called, the semaphore is provided by value, and almost certainly should be by reference. When it is by value, any changes made by acquire are not reflected in s at all [ see note 1 ]. So, whatever acquire does, it does not provide semaphore acquisition semantics. The same most likely applies to references to the unspecified queue types (s->m, s->h).

This is another classic:

}
else
    s.mutex = FALSE;
    SIGNAL(s.m);

Which is actually understood by the compiler as:

} else {
    s.mutex = FALSE;
}
SIGNAL(s.m);

Which doesn't seem right, but a lot doesn't seem right. So, if this does anything at all, it is by luck (maybe bad luck?). Ignore it unless you are assigned to fix it.

Secondly, it appears to attempt to implement semaphores on top of WAIT & SIGNAL, which are equivalent to a semaphore; It is quite likely it could be corrected to be:

struct semaphore {
    queue s;
};
acquire_semaphore(struct semaphore *s) {
    WAIT(&s->s);
}
release_semaphore(struct semaphore *s) {
    SIGNAL(&s->s);
}

and be done with it.

[note]: It is reasonable to layout a semaphore as:

struct semaphore {
     struct _semaphore *p;
};
struct _semaphore {
     /* actual bits to make a semaphore here */
};

Which has the nice effect of permitting copy semantics in the semaphore, so if somebody does something like reallocate a structure containing a semaphore, it behaves as expected. This isn't being done in this example, but it is good to remember.

Semaphores with test and set (code implementation possible mistake)

1 Answers1