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

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()，上面也显示了从同一个网站复制的，我的问题是，如果出现 3 个进程并调用 acquire_semaphore，信号量初始化为一个值为 1 那么信号量的值将变为 -2 并且进程 p2 和 p3 将进入 h 队列并且永远不会被唤醒，这似乎不正确所以我假设代码中有错误？我假设要解决这个问题，释放信号量中的行 "if(s.value >= 0) {" 应该是 "if(s.value <= 0) {"，因为这会唤醒保持 (h) 队列中的下一个进程。下面显示了 table 我使用 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]。因此，无论 acquire 做什么，它都不提供信号量获取语义。这同样很可能适用于对未指定队列类型（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);
}

并完成它。

[注]: 合理布局信号量为：

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

它具有允许信号量中的复制语义的良好效果，因此如果有人做了类似重新分配包含信号量的结构的操作，它会按预期运行。此示例中未执行此操作，但最好记住。

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

Semaphores with test and set (code implementation possible mistake)

c

operating-system

semaphore

test-and-set

multiprocessing