Home > Archive > Unix Programming > May 2004 > Mutex Question
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
|
|
| Nurdz2000 2004-05-13, 7:40 am |
| Consider the following scenario of mutex request for locks:-
Thread#1 Thread#2
pthread_mutex_lock <Sleeping>
<Cirtical Section> <Got an async event>
....... pthread_mutex_lock
........ <waiting for the lock>
pthread_mutex_unlock
pthread_mutex_lock
Now my question is
In the Thread#1 unlocks and immediately requests for the same lock
again due to some condition. In such a case is there any possibilty
that Thread#1 gets back the lock again before the Thread#2 that was
actually waiting for the lock.
Thanks in advance
-Nurdz
| |
| David Schwartz 2004-05-13, 7:40 am |
|
"Nurdz2000" <nurdz2000@yahoo.com> wrote in message
news:750fd72.0405130233.c65541d@posting.google.com...
> Consider the following scenario of mutex request for locks:-
>
> Thread#1 Thread#2
> pthread_mutex_lock <Sleeping>
> <Cirtical Section> <Got an async event>
> ...... pthread_mutex_lock
> ....... <waiting for the lock>
> pthread_mutex_unlock
> pthread_mutex_lock
>
> Now my question is
> In the Thread#1 unlocks and immediately requests for the same lock
> again due to some condition. In such a case is there any possibilty
> that Thread#1 gets back the lock again before the Thread#2 that was
> actually waiting for the lock.
Absolutely. In fact, one would hope this would be the case. It would be
very, very bad if two threads contending for the same mutex kept switching
back and forth each time one of them made the slightest bit of progress. Far
better for one thread to make lots of progress and then the other to make
lots of progress.
Generally, unless a thread cannot make forward progress, it will be
allowed to continue to use up its timeslice.
DS
| |
| Darko M. 2004-05-13, 2:33 pm |
| "David Schwartz" <davids@webmaster.com> wrote in message news:<c7vj9g$pfs$1@nntp.webmaster.com>...
> "Nurdz2000" <nurdz2000@yahoo.com> wrote in message
> news:750fd72.0405130233.c65541d@posting.google.com...
>
>
> Absolutely. In fact, one would hope this would be the case. It would be
> very, very bad if two threads contending for the same mutex kept switching
> back and forth each time one of them made the slightest bit of progress. Far
> better for one thread to make lots of progress and then the other to make
> lots of progress.
I wouldn't agree. If that'd be a rule, than almost no use of
multithreading. I think it depends of the implementation of the
scheduler and thread library. It may actually appear to be randomly,
but the situation is that the other thread has already been waiting
for the lock, so it should have the priority.
Generally, I don't know inner structure of the pthread library, but
what I do know is that the situation with semaphores in IPC is as I
think it's about mutexes, too. Namely, the process sleeps until the
semaphore gets enough resources, and then it automatically takes them
over. I think this should be the general rule.
> Generally, unless a thread cannot make forward progress, it will be
> allowed to continue to use up its timeslice.
>
> DS
| |
| David Schwartz 2004-05-13, 2:33 pm |
| "Darko M." <mdanko@tesla.rcub.bg.ac.yu> wrote in message
news:ef663480.0405130927.67d4e189@posting.google.com...
> "David Schwartz" <davids@webmaster.com> wrote in message
> news:<c7vj9g$pfs$1@nntp.webmaster.com>...
[color=darkred]
[color=darkred]
> I wouldn't agree. If that'd be a rule, than almost no use of
> multithreading.
Huh?
> I think it depends of the implementation of the
> scheduler and thread library. It may actually appear to be randomly,
> but the situation is that the other thread has already been waiting
> for the lock, so it should have the priority.
No. How long you have waited for a lock has nothing to do with priority.
> Generally, I don't know inner structure of the pthread library, but
> what I do know is that the situation with semaphores in IPC is as I
> think it's about mutexes, too. Namely, the process sleeps until the
> semaphore gets enough resources, and then it automatically takes them
> over. I think this should be the general rule.
This would mean that two threads contending for the same lock on a
single CPU system would require one context switch for each lock/unlock of
the mutex. That would be a total and utter disaster. A thread should be
allowed to run out its timeslice unless it needs a resource that another
thread holds. Exceptions can be made in special cases, for example where it
may be expected that interactivity would suffer.
[color=darkred]
Consider two threads each trying to add 1,000 entries to a linked list.
Each tightly loops around a function to add an entry to the linked list,
which internally locks and releases a mutex. My way, each thread would add,
say, 50 entries very rapidly until its timeslice ran out. Each mutex
lock/unlock would be nearly a nop, except at the very beginning when one
thread had to block or occasionally when a thread gets switched while it
holds the mutex. Your way, each thread would add one entry and then there
would be a task switch. The system would be performance limited by the rate
at which it could accomplish task switches.
"Fairness" is irrelevent here. You won't hurt a thread's feelings or
cause it to file a union grievance if you treat it unfairly. The programmer
has total control over what the thread does once it gets the mutex.
DS
| |
| Søren Hansen 2004-05-13, 4:32 pm |
| Den Thu, 13 May 2004 10:48:29 -0700. skrev David Schwartz:
> Consider two threads each trying to add 1,000 entries to a linked list.
> Each tightly loops around a function to add an entry to the linked list,
> which internally locks and releases a mutex. My way, each thread would add,
> say, 50 entries very rapidly until its timeslice ran out. Each mutex
> lock/unlock would be nearly a nop, except at the very beginning when one
> thread had to block or occasionally when a thread gets switched while it
> holds the mutex. Your way, each thread would add one entry and then there
> would be a task switch. The system would be performance limited by the rate
> at which it could accomplish task switches.
I don't know how it actually works in real life implementations, but your
scenario holds a serious flaw, too! The only way for thread 2 to gain the
mutex is for it to be active at a point where the mutex is free. So, if
thread one goes through an algorithm, where the - for us - interesting
parts are:
while(1) {
mutex_lock();
.....
mutex_unlock();
}
So, for thread 2 to to get the mutex, the scheduler would have to make a
context switch at the exact picosecond (or whatever unit of time applies),
between the mutex_unlock() and the mutex_lock() of thread 1. Otherwise,
every time thread 2 is due to run, it'll still be blocking and would never
run.
If this is how things work, i wouldn't know who to point my blame finger
at: the kernel scheduler programmer or the programmer of thread 1..
| |
| Eric Sosman 2004-05-13, 4:32 pm |
| S=F8ren Hansen wrote:
> Den Thu, 13 May 2004 10:48:29 -0700. skrev David Schwartz:
>=20
ist.=20[color=darkred]
,=20[color=darkred]
add,=20[color=darkred]
e=20[color=darkred]
t=20[color=darkred]
re=20[color=darkred]
rate=20[color=darkred]
>=20
>=20
> I don't know how it actually works in real life implementations, but yo=
ur
> scenario holds a serious flaw, too! The only way for thread 2 to gain t=
he
> mutex is for it to be active at a point where the mutex is free. So, if=
> thread one goes through an algorithm, where the - for us - interesting
> parts are:
>=20
> while(1) {
> mutex_lock();
> ....
> mutex_unlock();
> }
>=20
> So, for thread 2 to to get the mutex, the scheduler would have to make =
a
> context switch at the exact picosecond (or whatever unit of time applie=
s),
> between the mutex_unlock() and the mutex_lock() of thread 1. Otherwise,=
> every time thread 2 is due to run, it'll still be blocking and would ne=
ver
> run.
> If this is how things work, i wouldn't know who to point my blame finge=
r
> at: the kernel scheduler programmer or the programmer of thread 1..
Presumably the "...." includes some kind of access to
shared data objects (if it didn't, the mutex wouldn't be
needed). So the question arises: What, exactly, is Thread 1
doing with these shared objects? Some possibilities:
- Thread 1 is a "producer," inserting packets or job
tickets or some kind of "stuff" into a queue or something
of the sort. If so, the queue will eventually become
full and Thread 1 will need to wait for other threads to
remove some items before it can insert another one. When
this happens, Thread 1 will do a cond_wait() or something
similar, and the other threads will get their chance.
- Thread 1 is a "consumer," pulling job tickets off of a
queue and processing them. Eventually the queue will
become empty, at which point Thread 1 will have to wait
until producer threads generate more work.
- Thread 1 is both a "producer" and a "consumer," and since
it's doing all the work so rapidly that no other thread
can intervene, that's perfectly all right: all the work
is getting done, and getting done quickly. What more
can one ask?
- Thread 1 is a time-waster, just locking an unlocking a
mutex for no good reason. Or Thread 1 is doing something
useful, but needlessly holds the mutex throughout each
entire operation instead of only for those moments when
it needs access to the shared data. In cases like these,
I'd certainly point the finger at the programmer!
Mutexes do not guarantee "fairness," in part because "fair" is
a notion that differs from one application to another. If you want
to enforce some particular kind of fairness, you must program it
explicitly, with something like
while (1) {
mutex_lock();
join_queue_at_rear();
while (! at_front_of_queue())
cond_wait();
exit_queue_at_front();
.... /* as above */
mutex_unlock();
}
That wasn't so hard, now, was it?
--=20
Eric.Sosman@sun.com
| |
| Alexey 'kaa' Kiritchun 2004-05-13, 5:32 pm |
| Søren Hansen wrote:
> I don't know how it actually works in real life implementations, but your
> scenario holds a serious flaw, too! The only way for thread 2 to gain the
> mutex is for it to be active at a point where the mutex is free. So, if
> thread one goes through an algorithm, where the - for us - interesting
> parts are:
>
> while(1) {
> mutex_lock();
> .....
> mutex_unlock();
> }
>
> So, for thread 2 to to get the mutex, the scheduler would have to make a
> context switch at the exact picosecond (or whatever unit of time applies),
> between the mutex_unlock() and the mutex_lock() of thread 1. Otherwise,
> every time thread 2 is due to run, it'll still be blocking and would never
> run.
If mutex operations can cause threads resheduling (and they should),
then this will not happen: spinnig thread will get to run full
timeslice, then be scheduled away.
A simple test proves it (linux 2.4.18, glibc 2.2.5)
#include <pthread.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <signal.h>
pthread_mutex_t m = PTHREAD_MUTEX_INITIALIZER;
void *th(void *arg)
{
struct timespec t = {0, 1};
/* linux has HZ=100 by default, so will sleep at leasr 10 ms */
puts("Entered thread");
while(1) {
pthread_mutex_lock( &m );
nanosleep(&t, NULL);
pthread_mutex_unlock( &m );
}
return NULL;
}
int main()
{
pthread_t x;
pthread_mutex_init( &m, NULL );
alarm( 7 );
pthread_create( &x, NULL, th, NULL);
while( sleep(2) == 0 ) {
pthread_mutex_lock( &m );
puts("OK");
pthread_mutex_unlock( &m );
}
/* don't need to exit: will be killed by SIGALRM */
}
--
Alexey 'Kaa the Snake' Kiritchun
mailto:kaa@nightmail.ru
| |
| subnet 2004-05-14, 3:31 am |
| Eric Sosman <Eric.Sosman@sun.com> wrote in message news:<40A3D2DE.7050700@sun.com>...
> Mutexes do not guarantee "fairness," in part because "fair" is
> a notion that differs from one application to another. If you want
> to enforce some particular kind of fairness, you must program it
> explicitly, with something like
>
> while (1) {
> mutex_lock();
> join_queue_at_rear();
> while (! at_front_of_queue())
> cond_wait();
> exit_queue_at_front();
> .... /* as above */
> mutex_unlock();
> }
Forgive my ignorance, but won't going to sleep with the mutex acquired
prevent any other thread from getting it? Or did you assume that
cond_wait() releases the lock?
Thanks
>
> That wasn't so hard, now, was it?
| |
| Casper H.S. Dik 2004-05-14, 6:31 am |
| sunglo@katamail.com (subnet) writes:
>Eric Sosman <Eric.Sosman@sun.com> wrote in message news:<40A3D2DE.7050700@sun.com>...
[color=darkred]
>Forgive my ignorance, but won't going to sleep with the mutex acquired
>prevent any other thread from getting it? Or did you assume that
>cond_wait() releases the lock?
cond_wait is always passed a condition variable and a mutex; during
the call the mutex is unlocked.
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
| |
| Nurdz2000 2004-05-14, 10:32 am |
| But if the thread is allowed to run-out its timeslice, and it has the
lock when its pre-empted from the CPU till its next time slice, and
this locking/unlocking happens in a loop. Then there are scenarios
where every time its pre-empted out of the CPU the lock is always with
the thread#1 and the thread#2 will be starved for the mutex resource.
Does the OS make sures that when lots of locking/unlocking are taking
place then no thread/process is starved?
But I agree to the fact that if the context switch takes place on
every lock/unlock its a big performance degradation in the system. But
starving the order process for the mutex would not help much.
-Nurdz
"David Schwartz" <davids@webmaster.com> wrote in message news:<c80cde$8i2$1@nntp.webmaster.com>...
> "Darko M." <mdanko@tesla.rcub.bg.ac.yu> wrote in message
> news:ef663480.0405130927.67d4e189@posting.google.com...
>
>
>
>
>
> Huh?
>
>
> No. How long you have waited for a lock has nothing to do with priority.
>
>
> This would mean that two threads contending for the same lock on a
> single CPU system would require one context switch for each lock/unlock of
> the mutex. That would be a total and utter disaster. A thread should be
> allowed to run out its timeslice unless it needs a resource that another
> thread holds. Exceptions can be made in special cases, for example where it
> may be expected that interactivity would suffer.
>
>
> Consider two threads each trying to add 1,000 entries to a linked list.
> Each tightly loops around a function to add an entry to the linked list,
> which internally locks and releases a mutex. My way, each thread would add,
> say, 50 entries very rapidly until its timeslice ran out. Each mutex
> lock/unlock would be nearly a nop, except at the very beginning when one
> thread had to block or occasionally when a thread gets switched while it
> holds the mutex. Your way, each thread would add one entry and then there
> would be a task switch. The system would be performance limited by the rate
> at which it could accomplish task switches.
>
> "Fairness" is irrelevent here. You won't hurt a thread's feelings or
> cause it to file a union grievance if you treat it unfairly. The programmer
> has total control over what the thread does once it gets the mutex.
>
> DS
| |
| Casper H.S. Dik 2004-05-14, 10:32 am |
| nurdz2000@yahoo.com (Nurdz2000) writes:
>But if the thread is allowed to run-out its timeslice, and it has the
>lock when its pre-empted from the CPU till its next time slice, and
>this locking/unlocking happens in a loop. Then there are scenarios
>where every time its pre-empted out of the CPU the lock is always with
>the thread#1 and the thread#2 will be starved for the mutex resource.
>Does the OS make sures that when lots of locking/unlocking are taking
>place then no thread/process is starved?
No; but an algorithm which depends on the "fairness" of the OS or
other help from the OS is fundamentally broken.
>But I agree to the fact that if the context switch takes place on
>every lock/unlock its a big performance degradation in the system. But
>starving the order process for the mutex would not help much.
It's not a problem if the algorithm and locking mechanism have been
properly thought out; in this particular case it is certain they
have not.
Casper
--
Expressed in this posting are my opinions. They are in no way related
to opinions held by my employer, Sun Microsystems.
Statements on Sun products included here are not gospel and may
be fiction rather than truth.
| |
| David Schwartz 2004-05-14, 4:31 pm |
|
"Nurdz2000" <nurdz2000@yahoo.com> wrote in message
news:750fd72.0405140519.27affed0@posting.google.com...
> But if the thread is allowed to run-out its timeslice, and it has the
> lock when its pre-empted from the CPU till its next time slice, and
> this locking/unlocking happens in a loop. Then there are scenarios
> where every time its pre-empted out of the CPU the lock is always with
> the thread#1 and the thread#2 will be starved for the mutex resource.
> Does the OS make sures that when lots of locking/unlocking are taking
> place then no thread/process is starved?
> But I agree to the fact that if the context switch takes place on
> every lock/unlock its a big performance degradation in the system. But
> starving the order process for the mutex would not help much.
You are asking the OS to do the impossible. If two threads each always
want the mutex, then there is an infinite amount of work to do. Any finite
amount of work can be fairly divided, but an infinite quantity cannot be.
Mutexes do not guarantee anything but mutual exclusion. If you have
other requirements, use a synchronization primitive that meets them.
DS
|
|
|
|
|