5

I'm acquiring some resources in increasing order. Which version is better? I was told that #2 leads to starvation of threads wanting higher numbered resources. Is this true? If so, how and why?

a[] sorted array

1.

for(int i = 1; i < N; ++i) {
  lock(mutex)
  while(!resource_available[a[i]]) {
    pthread_cond_wait(&cond_w[a[i]], &mutex);
  }
  resource_available[a[i]] = 0;
  unlock(mutex)
}

2.

lock(mutex)
for(int i = 1; i < N; ++i) {
  while(!resource_available[a[i]]) {
    pthread_cond_wait(&cond_w[a[i]], &mutex);
  }
  resource_available[a[i]] = 0;
}
unlock(mutex)

EDIT: It turns out that order in which you release resources makes the difference, not above constructs. If you release them in order you received them starvation happens, if in opposite then probably not.

niteria
  • 1,375
  • 1
  • 9
  • 14

3 Answers3

3

Both are going to be virtually equivalent, since in example 1 the thread will almost always reacquire the mutex without sleeping immediately after unlocking it, since there's only two expressions evaluated in between.

caf
  • 233,326
  • 40
  • 323
  • 462
  • Can you somehow explain why nobody would starve in #2? – niteria Jan 24 '11 at 01:16
  • @niteria: Proving a negative is notoriously difficult. It would depend on what the threads do other than this loop - do they spend any significant time *not* holding any of the resources? I can say, however, that the two loops you have given are equivalent - unlocking a mutex does *not* imply yielding, and mutex waiters are not queued. – caf Jan 24 '11 at 01:41
  • You're right, problem was with order of releasing the resources. Do you know why opposite order helps? – niteria Jan 24 '11 at 15:16
2

It would cause more starvation when resources are always available and pthread_cond_wait doesn't need run. In that case you'd have the mutex the entire loop. So if N is very large then by locking outside the entire loop you could be starving other threads that need the mutex.

Its generally a good idea to lock the smallest region nescesarry to avoid starvation of other threads and deadlocks.

Consider too when someone comes along to maintain this loop. Its going to be very easy to glob a few extra if statements/function calls in the body of the for loop and create more starvation. The maintainer might easily miss the locking in the code. You're best off preventing this by creating a function in charge of acquiring resource i. This function would be responsible for all locking, eliminating any chance the calling code could extend the size of the critical section.

 // blocks till resource resourceNum is obtained
 void acquire_resource(int resourceNum)
 {
     lock(mutex)
     while(!resource_available[a[i]]) {
       pthread_cond_wait(&cond_w[a[i]], &mutex);
     }
     unlock(mutex)
 }

 for(int i = 1; i < N; ++i) {
     acquire_resource(i);
 }
Doug T.
  • 64,223
  • 27
  • 138
  • 202
  • But either pthread_cond_wait releases mutex or thread successfully aquires all resources and then releases mutex. I don't see how starvation happens. – niteria Jan 23 '11 at 23:25
  • But N is finite (in my case under 100) and in case where all resources are available it finishes in finite time, so thread waiting for mutex finally gets it. So starvation doesn't happen. – niteria Jan 23 '11 at 23:38
  • N may be finite, but you are leaving the door open to maintainers of your code to extend the size of your critical section by adding more code in the loop. See my edit -- by wrapping the lock in a function call you help maintainers avoid this by clearly delineating the responsibility of two pieces of code. One which blocks until a resource is acquired, and a second which tries to acquire all N resources. – Doug T. Jan 23 '11 at 23:41
  • The question is if starvation can happen in #2. Code won't be maintained, so don't worry about that. – niteria Jan 23 '11 at 23:49
0

I would have the locking and unlocking in the resource_available function, and then only lock right before wait - unlock right after it.

Peyman
  • 447
  • 3
  • 7