1

https://stackoverflow.com/a/5524120/462608

如果你想递归调用函数来锁定同一个互斥锁，那么它们要么必须使用一个递归互斥锁，要么
必须一次又一次地解锁和锁定同一个非递归互斥锁（当心并发线程！），或者
必须以某种方式注释它们已经锁定的互斥锁（模拟递归所有权/互斥锁）。

无论如何，这是一个“明智的”设计决定，使已经具有互斥锁的函数递归？

4

2 回答 2

2

嗯，一种可能性是您使用的资源自然适合递归算法。

考虑搜索二叉树，同时防止其他人使用（尤其是修改）带有互斥锁的树。

如果您使用递归互斥锁，您可以简单地拥有一个search()将根节点传递给的函数。然后它按照正常的二叉树搜索递归地调用自己，但它在该函数中做的第一件事是锁定互斥锁（虽然这看起来像 Python，但这实际上只是因为 Python 是伪代码的理想基础）：

def search (haystack, mutex, needle):
    lock mutex recursively

    if haystack == NULL:
        unlock mutex and return NULL

    if haystack.payload == needle:
        unlock mutex and return haystack

    if haystack.payload > needle:
        found = search (haystack.left, mutex, needle)
    else:
        found = search (haystack.right, mutex, needle)

    unlock mutex and return found

另一种方法是将互斥锁和搜索分离为两个单独的函数，例如search()（公共）和search_while_locked()（很可能是私有）：

def private search_while_locked (haystack, needle):
    if haystack == NULL:
        return NULL

    if haystack.payload == needle:
        return haystack

    if haystack.payload > needle:
        return search_while_locked (haystack.left, needle)

    return search_while_locked (haystack.right, needle)

def search (haystack, mutex, needle):
    lock mutex non-recursively

    found = search_while_locked (haystack.right, needle)

    unlock mutex and return found

虽然这会破坏递归解决方案的优雅，但我实际上更喜欢它，因为它减少了需要完成的工作量（无论工作量多么小，它仍然有效）。

易于使用公共/私有功能的语言可以很好地封装细节。您班级的用户对您如何在班级内做事一无所知（或需要知识），他们只是调用公共 API。

但是，您自己的函数可以访问所有非公开内容，并且完全了解某些操作需要哪些锁。

另一种可能性与此非常相关，但不是递归的。

想一想您可能希望用户对您的数据执行的任何有用的操作，这些操作要求在此期间没有其他人使用它。到目前为止，您已经有了非递归互斥锁的经典案例。例如，清除队列中的所有条目：

def clearQueue():
    lock mutex
    while myQueue.first <> null:
        myQueue.pop()
    unlock mutex

现在假设您发现它非常有用并想从您的析构函数中调用它，该析构函数已经锁定了互斥锁：

def destructor():
    lock mutex
    clearQueue()
    doSomethingElseNeedingLock()
    unlock mutex

显然，对于非递归互斥锁，它会clearQueue在你的析构函数调用它之后锁定在第一行，这可能是你想要一个递归互斥锁的一个原因。

您可以使用上述提供锁定公共函数和非锁定私有函数的方法：

def clearQueueLocked():
    while myQueue.first <> null:
        myQueue.pop()

def clearQueue():
    lock mutex
    clearQueueLocked():
    unlock mutex

def destructor():
    lock mutex
    clearQueueLocked():
    doSomethingElseNeedingLock()
    unlock mutex and return

但是，如果这些公共/私有函数对的数量很大，它可能会变得有点混乱。

于 2012-05-11T07:05:30.313 回答
1

除了使用实际递归函数的 paxdiablo 示例之外，不要忘记递归使用互斥锁并不一定意味着所涉及的函数是递归的。我发现递归互斥锁可用于处理复杂操作的情况，这些操作需要对某些数据结构是原子的，这些复杂操作依赖于更基本的操作，这些操作仍然需要使用互斥锁，因为基本操作也可以单独使用。一个示例可能类似于以下内容（请注意，代码只是说明性的 - 它没有使用在处理帐户和日志时可能真正需要的正确错误处理或事务技术）：

struct account
{
    mutex mux;

    int balance;

    // other important stuff...

    FILE* transaction_log;
};

void write_timestamp( FILE*);


// "fundamental" operation to write to transaction log
void log_info( struct account* account, char* logmsg)
{
    mutex_acquire( &account->mux);

    write_timestamp( account->transaction_log);
    fputs( logmsg, account->transaction_log);

    mutex_release( &account->mux);
}


// "composed" operation that uses the fundamental operation.
//  This relies on the mutex being recursive
void update_balance( struct account* account, int amount)
{
    mutex_acquire( &account->mux);

    int new_balance = account->balance + amount;

    char msg[MAX_MSG_LEN];
    snprintf( msg, sizeof(msg), "update_balance: %d, %d, %d", account->balance, amount, new_balance);

    // the following call will acquire the mutex recursively
    log_info( account, msg);

    account->balance = new_balance;

    mutex_release( &account->mux);
}

在没有递归互斥锁的情况下做或多或少等效的事情意味着代码需要注意不要重新获取已经持有的互斥锁。一种选择是在数据结构中添加某种标志（或线程 ID）以指示互斥锁是否已被持有。在这种情况下，您实际上是在实现递归互斥锁 - 一项比起初看起来要正确的工作更棘手。另一种方法是传递一个标志，表明您已经获得了互斥锁作为参数（更容易实现和正确），或者只是有更基本的操作，假设互斥锁已经获得，并从更高级别的函数调用那些关于获取互斥锁的责任：

// "fundamental" operation to write to transaction log
//  this version assumes that the lock is already held
static
void log_info_nolock( struct account* account, char* log msg)
{
    write_timestamp( account->transaction_log);
    fputs( logmsg, account->transaction_log);
}


// "public" version of the log_info() function that
//      acquires the  mutex
void log_info( struct account* account, char* logmsg)
{
    mutex_acquire( &account->mux);
    log_info_nolock( account, logmsg);    
    mutex_release( &account->mux);
}


// "composed operation that uses the fundamental operation
//      since this function acquires the mutex, it much call the
//      "nolock" version of the log_info() function
void update_balance( int amount)
{
    mutex_acquire( &account->mux);

    int new_balance = account->balance + amount;

    char msg[MAX_MSG_LEN];
    snprintf( msg, sizeof(msg), "update_balance: %d, %d, %d", account->balance, amount, new_balance);

    // the following call assumes the lock is already acquired
    log_info_nolock( account, msg);

    account->balance = new_balance;

    mutex_release( &account->mux);
}
于 2012-05-12T08:15:31.930 回答