时间戳

首页 > 解决方案 > 带有测试和设置的信号量（代码实现可能的错误）

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

问题描述

我一直在学习信号量，并且正在查看信号量的网站实现（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 个进程并使用初始化为 1 的信号量调用 acquire_semaphore，那么信号量的值将变为 -2 并且进程 p2 和 p3 将进入 h 队列并且从未被通知唤醒，这似乎不正确所以我假设代码中有错误？我解决这个问题的假设是，发布信号量中的“if(s.value >= 0) {”行应该是“if(s.value <= 0) {”，因为这会唤醒保持中的下一个进程(h) 排队。我在下面显示了一个表格，我使用名为 p1、p2 和 p3 的 3 个进程手动处理代码。感谢您的任何帮助。

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

标签： coperating-systemmultiprocessingsemaphoretest-and-set

解决方案

第一的：

acquire_semaphore(struct semaphore s)

当它被调用时，信号量是由value提供的，而且几乎可以肯定应该是由reference提供的。当它是按值时，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);
}

并完成它。

[注意]：将信号量布局为：

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

这具有允许在信号量中复制语义的良好效果，因此如果有人执行诸如重新分配包含信号量的结构之类的操作，它的行为将符合预期。在本例中没有这样做，但最好记住。

推荐阅读