Why would we want to make a function recursive whe

问题:

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

If you want to call functions recursively, which lock the same mutex, then they either have to use one recursive mutex, or
have to unlock and lock the same non-recursive mutex again and again (beware of concurrent threads!), or
have to somehow annotate which mutexes they already locked (simulating recursive ownership/mutexes).

Can in any case this be a "sensible" design decision to make function recursive which already has a mutex lock?

回答1:

In addition to paxdiablo's exmaple using an actual recursive funciotn, don't forget that using a mutex recursively doesn't necessarily mean that the functions involved are recursive. I've found use for recursive mutexes for dealing with a situation where you have complex operations which need to be atomic with respect to some data structure, with those complex operations rely on more fundamental operations that still need to use the mutex since the fundamental operations can be used on their own as well. An example might be something like the following (note that the code is illustrative only - it doesn't use proper error handling or transactional techniques that might really be necessary when dealing with accounts and logs):

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

To do something more or less equivalent without recursive mutexes means that the code would need to take care not to reacquire the mutex if it already held it. One option is to add some sort of flag (or thread ID) to the data structure to indicate if the mutex is already held. In this case, you're essentially implementing recursive mutexes - a trickier bit of work than it might seem at first to get right. An alternative is to pass a flag indicating you already acquired the mutex to functions as a parameter (easier to implement and get right) or simply have even more fundamental operations that assume the mutex is already acquired and call those from the higher level functions that take on the responsibility of acquiring the mutex:

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

回答2:

Well, one possibility is that the resource you're using lends itself naturally to recursive algorithms.

Think of searching a binary tree, while preventing everyone else from using (especially modifying) the tree out with a mutex.

If you use a recursive mutex, you can simply have one function search() that you pass the root node in to. It then recursively calls itself as per a normal binary tree search but the first thing it does in that function is to lock the mutex (while this looks like Python, that's really just because Python is an ideal basis for pseudo-code):

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

The alternative is to separate the mutex lock and search into two separate functions like search() (public) and search_while_locked() (most likely private):

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

While that sort of defeats the elegance of the recursive solution, I actually prefer it since it reduces the amount of work that needs to be done (however small that work is, it's still work).

And languages that lend themselves easily to public/private functions can encapsulate the details well. The user of your class has no knowledge (or need of knowledge) as to how you do things within your class, they just call the public API.

Your own functions, however, have access to all the non-public stuff as well as full knowledge as to what locks need to be in place for certain operations.

---

Another possibility is very much related to that but without being recursive.

Think of any useful operation you may want users to perform on your data which requires that no-one else be using it during that time. So far, you have just the classic case for a non-recursive mutex. For example, clearing all of the entries out of a queue:

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

Now let's say you find that rather useful and want to call it from your destructor, which already locks the mutex:

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

Obviously, with a non-recursive mutex, that's going to lock up on the first line of clearQueue after your destructor calls it, which may be one reason why you'd want a recursive mutex.

You could use the afore-mentioned method of providing a locking public function and a non-locking private one:

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

However, if there are a substantial number of these public/private function pairs, it may get a little messy.