带有测试和设置的信号灯（代码实现可能出错）

Question

[我一直在学习信号量，并且我正在研究信号量（http://faculty.salina.k-state.edu/tim/ossg/IPC_sync/ts.html）的网站实现，但是我不理解该实现，以节省访问该网站的任何人的代码，如下所示。

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

我假设的TS方法是TestandSet（），上面也显示了从同一网站复制的TS方法，我的问题是，如果出现3个进程，并调用带有初始化为1的信号量的acquire_semaphore，则该值信号量将变为-2，进程p2和p3将进入h队列，并且从未收到过唤醒的信号，这似乎不正确，所以我假设代码中有错误吗？我要解决此问题的假设是，释放信号量中的“ if（s.value> = 0）{”行应为“ if（s.value <= 0）{”，因为这将唤醒保留的下一个进程（h）排队。下面的表格显示了我手动处理3个名为p1，p2和p3的进程的代码。谢谢您的帮助。

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

Answer 1

第一：

acquire_semaphore(struct semaphore s)

被调用时，信号量由value提供，并且几乎可以肯定应该由reference提供。当通过value进行获取时，通过acquire进行的任何更改都不会反映在s中[请参见注1]。因此，无论获取如何，它都不会提供信号量获取语义。对未指定的队列类型（s-> m，s-> h）的引用最可能相同。

这是另一个经典：

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

编译器实际上将其理解为：

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

这似乎不正确，但是很多看起来不正确。所以，如果这什么都不做，那就是运气（也许是运气不好？）。除非指定您修复它，否则请忽略它。

[第二，似乎试图在WAIT＆SIGNAL之上实现信号量，这些信号量等同于信号量；很可能可以将其更正为：

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

并完成它。

[note]：合理地将信号量布置为：

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

这具有允许在信号量中使用复制语义的良好效果，因此，如果有人进行诸如重新分配包含信号量的结构之类的操作，它的行为将达到预期的效果。在此示例中未完成此操作，但请记住。