LinuxQuestions.org
Support LQ: Use code LQ3 and save $3 on Domain Registration
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Reply
 
LinkBack Search this Thread
Old 03-07-2012, 01:34 PM   #1
TheIndependentAquarius
Senior Member
 
Registered: Dec 2008
Posts: 4,598
Blog Entries: 29

Rep: Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880
[pthread] It is necessary to lock the mutex BEFORE using the condition variable?


Is the following reasoning correct? If not, then please correct it.

Quote:
Situation with the condition variables in action is as follows:

{
If <condition is false> then
`pthread_cond_wait (&demoConditionVariable)` // Threads should wait if the condition is false.

Write to shared `x` file.
}

Now, suppose three threads are waiting on that condition variable for the condition to be true. The function `pthread_cond_wait ()` will let the waiting threads activate only when it receives a signal (for activation).

The condition may get set to true (due to some run time logic).

A fourth thread (not waiting on this condition variable) may see the condition to be true, skip the waiting part, and attempt to grab the access to the shared file.

Meanwhile the function `pthread_cond_wait ()` may receive the signal and wake up the sleeping threads.
This may lead to a race condition between the fourth thread and the newly activated threads for getting write access to the shared file!
 
Old 03-07-2012, 02:29 PM   #2
orgcandman
Member
 
Registered: May 2002
Location: dracut MA
Distribution: Ubuntu; PNE-LE; LFS (no book)
Posts: 594

Rep: Reputation: 102Reputation: 102
The short answer is 'no'. The less short answer is 'like many things, it depends'.

The long answer, though is filled with considerations about requirements.

Do you _need_ to keep in sync on shared 'x'? If so, you'll need some synchronization primitive around it, although where that goes, what it is, and how you use it are all dependent on the access scheme you decide on (look into lock free data structures if you want some more information on synchronization without using pthread mutexes).

If you don't really require the synchronization, you don't need to use a sync primitive. If you do require sync, you do need one. It's as simple as that. If your condition needs to have a synchronized "test-and-set" - you need a synchronized test and set.
 
Old 03-07-2012, 02:55 PM   #3
jlinkels
Senior Member
 
Registered: Oct 2003
Location: Bonaire
Distribution: Debian Lenny/Squeeze/Wheezy/Sid
Posts: 3,982

Rep: Reputation: 477Reputation: 477Reputation: 477Reputation: 477Reputation: 477
Is it correct that you ask is this:

- 3 threads are in wait state, waiting until the condition becomes true
- thread #4 doesn't wait, but does check the condition and accesses the file if the condition is true.

Well, in that case, thread 4 must invalidate the condition before writing.

If, in the mean time thread 1-3 already started, thread 4 will not be able to invalidate the condition, and hence will wait until it can.

Maybe the error in reasoning you make is that you forget that you must not just wait until a condition becomes true, you must also set a mutex before you access a shared resource. The good news is that testing and setting a mutex is atomic, it is not possible that you test a mutex, get a valid return value, and get interrupted before you can set the mutex by another task.

Maybe this helps:
https://computing.llnl.gov/tutorials...#MutexOverview

jlinkels

Last edited by jlinkels; 03-07-2012 at 02:58 PM.
 
Old 03-08-2012, 12:13 AM   #4
TheIndependentAquarius
Senior Member
 
Registered: Dec 2008
Posts: 4,598
Blog Entries: 29

Original Poster
Rep: Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880
Quote:
Originally Posted by jlinkels View Post
Well, in that case, thread 4 must invalidate the condition before writing.
by invalidate you mean that the condition should be set to true before writing?
I also meant the same.

Quote:
Originally Posted by jlinkels View Post
If, in the mean time thread 1-3 already started, thread 4 will not be able to invalidate the condition, and hence will wait until it can.
yeah that's fine, but I stated that if the condition becomes true, and before the 3 threads could wake, the 4th one starting acting.

Quote:
Originally Posted by jlinkels View Post
Maybe the error in reasoning you make is that you forget that you must not just wait until a condition becomes true, you must also set a mutex before you access a shared resource.
Perhaps I didn't mention here that there is a mutex before the condition variable and therefore it includes the shared file.

The only place where there is no mutex is the point from where we "send" the signal.
When a thread enters the critical region, and gets to the point of wait API (starts waiting), the wait aPI again unlocks the mutex.

So, the fourth thread gets in the critical region, condition becomes true, so the 4th thread doesn't wait and straightway starts writing to the shared x. Now, the signal is sent to the wait API and the wait API frees the 3 sleeping threads. Now, there is a race condition between 3 threads and the 4th one.

Is all this correct?
 
Old 03-08-2012, 08:51 AM   #5
orgcandman
Member
 
Registered: May 2002
Location: dracut MA
Distribution: Ubuntu; PNE-LE; LFS (no book)
Posts: 594

Rep: Reputation: 102Reputation: 102
Quote:
Originally Posted by jlinkels View Post
Maybe the error in reasoning you make is that you forget that you must not just wait until a condition becomes true, you must also set a mutex before you access a shared resource.
This is an example of a poor statement. If we must set mutexes before accessing shared resources, our software would be plagued with inefficiencies. Additionally, we don't need to do this for global variables - so the statement is false anyway. Also, if only one thread ever will write to the variable, there is no need to put locks. Ping-pong table anyone?

Mutexes are NOT multi-threading.
 
Old 03-08-2012, 08:57 AM   #6
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 1,456

Rep: Reputation: 445Reputation: 445Reputation: 445Reputation: 445Reputation: 445
I don't really understand your code, but I can tell it is wrong. Either don't use synchronisation at all, or use it correctly:

Code:
if (condition) {
    wait_for_semaphore/mutex/whatever;
    peform-critical-action;
    release_semaphore/mutex/whatever;
}
 
Old 03-08-2012, 09:36 AM   #7
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,051

Rep: Reputation: 953Reputation: 953Reputation: 953Reputation: 953Reputation: 953Reputation: 953Reputation: 953Reputation: 953
Agreed.

You cannot "know if a condition is true-or-false" if the variable that you are testing is designed to be protected by a mutex: you do not know whether the value is stable... you are "racing" on that variable.

Having said that ... sometimes, for efficiency's sake (i.e. to minimize the number of trips through "atomic" mutex code...) you do elect to accept a certain amount of racing. Kind of like the person who zips past a line of patiently-waiting traffic on the highway and darts on ahead. Sure, such a thing might royally piss-off you or me, but a computer's case might be different.

There are two different purposes for mutual-exclusion:
  1. To guarantee the data-integrity of a shared data structure (or the atomic increment/decrement of an integer variable when an alternative atomic "compare-and-swap" primitive cannot instead be used). These uses are not optional: you must use mutual-exclusion here.
  2. To provide for "fair waiting-in-line," i.e. to avoid "busy waiting." As above, you can decide to let the cars zip past the line if they find that they can, and wait in line only if they find that they can't. Your design decision.

In the second case, I use mutual exclusion primitives to allow a process to wait until "it might have something to do." (That is to say, to cause it to wait when it "definitely does not have anything to do.") The process then wakes up, sees if it has anything to do, and if so does everything that it does have to do, and then it goes to sleep again. What are the odds that it'll instantly wake-up (because of some signal that had been posted in the past while it was working through its list), check and find that this time it has nothing more to do? Very likely... and, who cares. We don't care about that. But what we do care about is indefinite postponement: where the process does have work to do but is sleeping on the job. So, don't worry if it wakes up a little bit too often; do worry that it does not wake up often enough, and that it does not gobble up CPU time in the act of doing nothing.

Last edited by sundialsvcs; 03-08-2012 at 09:42 AM.
 
Old 03-08-2012, 12:12 PM   #8
jlinkels
Senior Member
 
Registered: Oct 2003
Location: Bonaire
Distribution: Debian Lenny/Squeeze/Wheezy/Sid
Posts: 3,982

Rep: Reputation: 477Reputation: 477Reputation: 477Reputation: 477Reputation: 477
Quote:
Originally Posted by orgcandman View Post
If we must set mutexes before accessing shared resources, our software would be plagued with inefficiencies.
This is exactly what mutexes are for. See the post by NevemTeve.


Quote:
Originally Posted by orgcandman View Post
Mutexes are NOT multi-threading.
I don't understand what you mean by this. No idea whether mutexes are multithreading. But they are extremely useful in a multithreaded environmoment. And mutexes have to be used because using system calls to test & set mutexes their atomic access is guaranteed, as is waiting (putting a thread to sleep and waking it up again) automatically until a mutex reaches it desired state.

jlinkels
 
Old 03-08-2012, 01:46 PM   #9
jlinkels
Senior Member
 
Registered: Oct 2003
Location: Bonaire
Distribution: Debian Lenny/Squeeze/Wheezy/Sid
Posts: 3,982

Rep: Reputation: 477Reputation: 477Reputation: 477Reputation: 477Reputation: 477
Quote:
Originally Posted by Anisha Kaul View Post
by invalidate you mean that the condition should be set to true before writing?
I also meant the same.
No, invalidate means set to False. Valid = true, Invalid = False, invalidate = the action setting to False

Quote:
Originally Posted by Anisha Kaul View Post
Perhaps I didn't mention here that there is a mutex before the condition variable and therefore it includes the shared file.
Threads are a difficult kind of breed, and you have to be very careful in what you do. There are people who want to avoid using threads at all. (http://www.stanford.edu/class/cs240/...d-usenix96.pdf)

I have the idea you are mixing up conditions, wait-for conditions amd mutexes. You should not do that, instead, you should programming threads as straigthforward as possible. That means:

- use mutexes around accessing a shared resources, e.g. variables, files, records etc.
- use a wait conditions if you want to wait for something to happen before you can proceed.

You can mix the two: use a wait condition while waiting for some flag to set or unset while you access a shared resource. That is usually incorrect and can lead to the most difficult, unpredictable and random errors.

If more than one thread can access a resourrce, and the resource is being accessed and correctly protected by a mutex, the next task will sleep until the mutex becomes available again. So you don't have to wait for a condition.

If you have designed your program such that a race condition can be raised if some task doesn't wait and proceeds directly processing, your design is flawed.

jlinkels

Last edited by jlinkels; 03-08-2012 at 01:48 PM.
 
Old 03-09-2012, 02:37 PM   #10
orgcandman
Member
 
Registered: May 2002
Location: dracut MA
Distribution: Ubuntu; PNE-LE; LFS (no book)
Posts: 594

Rep: Reputation: 102Reputation: 102
Quote:
Originally Posted by jlinkels View Post
This is exactly what mutexes are for. See the post by NevemTeve.
Mutexes are for creating critical sections. That you can use a critical section as one of many mechanisms for 'guaranteed' synchronization doesn't mean that they are:
1) The only way
2) The most efficient way.

Again, look at things like tcmalloc that provide guaranteed, synchronized, thread-safe access to shared data structures without using mutexes.

Quote:
If more than one thread can access a resourrce, and the resource is being accessed and correctly protected by a mutex, the next task will sleep until the mutex becomes available again. So you don't have to wait for a condition.
This is why mutexes are not multi-threading. Mutexes STOP all semblance of parallel processing, and all threads sleep while 1 executes. In this case, why not use 1 context of execution?

Quote:
I don't understand what you mean by this. No idea whether mutexes are multithreading. But they are extremely useful in a multithreaded environmoment. And mutexes have to be used because using system calls to test & set mutexes their atomic access is guaranteed, as is waiting (putting a thread to sleep and waking it up again) automatically until a mutex reaches it desired state.
Mutexes aren't the only way. Atomic test-and-set exists, and is far faster than the overhead of a system call. Especially since the rules around which threads wake up (and when) are lenient (meaning the kernel is under no obligation not to try waking up other threads which could just wait on the same mutex, making your software far more inefficient). I'm not just saying this as some random conjecture to troll. I've implemented lock-free queues which are hundreds of times faster and more efficient than mutex based queues and brought systems processing 10k packets per second at 70% cpu utilization to 50k packets per second at 2% peak utilization. These queues allow for multiple threads to push and pop at the same time without using mutexes. The accesses are guaranteed, as well (ie: no race conditions which result in broken variable state). These are not even NEW ideas (parallel programming groups have had these algorithms in their back pockets for years, if not decades).

This all comes with a caveat that you need to know the design of the system, end-to-end. So in the generic, must code to all platforms and all permutations of memory model, then I'll concede that mutexes are the only way to do test-and-sets. Even then, for open-source, one can rely on gcc's compare and exchange intrinsics. Even Microsoft includes InterlockedExchange.

I've come from enough projects where people over-use mutex and break performance requirements that I try and get people to think about what they need the mutex to protect rather than the blanket statement of "oh, it's shared, so mutex it."

Last edited by orgcandman; 03-09-2012 at 02:38 PM.
 
Old 03-10-2012, 11:58 AM   #11
jlinkels
Senior Member
 
Registered: Oct 2003
Location: Bonaire
Distribution: Debian Lenny/Squeeze/Wheezy/Sid
Posts: 3,982

Rep: Reputation: 477Reputation: 477Reputation: 477Reputation: 477Reputation: 477
Quote:
Originally Posted by orgcandman View Post
Mutexes are for creating critical sections. That you can use a critical section as one of many mechanisms for 'guaranteed' synchronization doesn't mean that they are:
1) The only way
2) The most efficient way.
(1) Partially correct and (2) correct.
The mutex functions in the pthread library are not the only way. But a mutex mechanism as such by locking access to a certain resource before actually accessing is fundamental for multitasking/multithreadinf operating systems. This has been discussed by Edsger Dijkstra in 1964 and is still valid. There are various ways to implement the mechanism, varying from very down to the bytes to high level abstraction. Since the pthread library comes with overhead, it does not necessarily mean it is the most efficient in execution time. There is always a trade-off in execution time versus abstraction.
Quote:
Originally Posted by orgcandman View Post
This is why mutexes are not multi-threading. Mutexes STOP all semblance of parallel processing, and all threads sleep while 1 executes. In this case, why not use 1 context of execution?
Ok, I have 2 threads. They want to share access to one single resource. One thread is actually accessing the resource. If the other thread is not set to wait, can you explain to me what exactly should happen with the second task in between? If you want to access the same resource exclusively, you have to wait until it comes available. If this means that a whole thread or task is being blocked, while that is undesirable, then you have designed your code incorrectly.

According to some, one context of execution is better than using threads at all. But that is not the discussion.

Quote:
Originally Posted by orgcandman View Post
Mutexes aren't the only way. Atomic test-and-set exists, and is far faster than the overhead of a system call. Especially since the rules around which threads wake up (and when) are lenient (meaning the kernel is under no obligation not to try waking up other threads which could just wait on the same mutex, making your software far more inefficient). I'm not just saying this as some random conjecture to troll. I've implemented lock-free queues which are hundreds of times faster and more efficient than mutex based queues and brought systems processing 10k packets per second at 70% cpu utilization to 50k packets per second at 2% peak utilization. These queues allow for multiple threads to push and pop at the same time without using mutexes. The accesses are guaranteed, as well (ie: no race conditions which result in broken variable state). These are not even NEW ideas (parallel programming groups have had these algorithms in their back pockets for years, if not decades).
If you have multiple threads and you want to access the resources without risk of corruption and there is no intrinsic underlying mechanism to guarantee that, I don't see how you can do that without blocking one thread while the other accesses the resource. You can't have the cake and eat it. I do agree however that by smart programming in one way of the other much optimization can be gained.

Quote:
Originally Posted by orgcandman View Post
I've come from enough projects where people over-use mutex and break performance requirements that I try and get people to think about what they need the mutex to protect rather than the blanket statement of "oh, it's shared, so mutex it."
True. Simply said: there is no substitute for competence.

jlinkels

Last edited by jlinkels; 03-10-2012 at 11:59 AM.
 
Old 03-11-2012, 10:49 AM   #12
NevemTeve
Senior Member
 
Registered: Oct 2011
Location: Budapest
Distribution: Debian/GNU/Linux, AIX
Posts: 1,456

Rep: Reputation: 445Reputation: 445Reputation: 445Reputation: 445Reputation: 445
Well, the OP mentioned shared files, so the serialization cannot be substitued with 'TS', 'CS' or 'CMPXCHG' instructions, but it is true that in some cases they can be very useful.
 
Old 03-12-2012, 10:59 AM   #13
orgcandman
Member
 
Registered: May 2002
Location: dracut MA
Distribution: Ubuntu; PNE-LE; LFS (no book)
Posts: 594

Rep: Reputation: 102Reputation: 102
We've hijacked Anish's thread for long enough, so I'm only going to post one more time to this.

Quote:
Originally Posted by jlinkels View Post
(1) Partially correct
Not partially correct - correct. ll/sc are not mutual exclusion, in the strict sense, and provide the synchronization you are looking for. The ll/sc primitives can be emulated on most architectures, if they're not natively supported.

Quote:
But a mutex mechanism as such by locking access to a certain resource before actually accessing is fundamental for multitasking/multithreadinf operating systems.
No. The only thing they require is a synchronization mechanism. The mutex paradigm is ONE mechanism for synchronization, but it isn't the only one.

Quote:
Ok, I have 2 threads. They want to share access to one single resource. One thread is actually accessing the resource. If the other thread is not set to wait, can you explain to me what exactly should happen with the second task in between?
I'm not going to answer this only because it's so abstract and vague that there is no way for me to say what the other task is doing, what it could be doing, what the shared resource is, etc. For instance, I could say "The second task is also accessing, since the shared resource was a simple counter and the gcc intrinsic __sync_add_and_fetch() takes care of calling the 'lock; xaddl...' instructions which invoke low-level cache synchronization primitives within the core." And if I did, you might respond with "oh, the shared resource was an rb-tree" and the only response that I could possible have is "well, then they must use a mutex or binary+ownership semaphore because there is no known lock-free implementation of rb-tree." The use of mutex vs some other synchronization (or NO synchronization, even) is heavily tied to requirements and design.

Quote:
If you want to access the same resource exclusively, you have to wait until it comes available. If this means that a whole thread or task is being blocked, while that is undesirable, then you have designed your code incorrectly.

According to some, one context of execution is better than using threads at all. But that is not the discussion.
I don't want for my code anything but to satisfy the functional and performance requirements it has. If my code requires a critical section, I'll use one. If it doesn't, I won't use one.

Quote:
If you have multiple threads and you want to access the resources without risk of corruption and there is no intrinsic underlying mechanism to guarantee that, I don't see how you can do that without blocking one thread while the other accesses the resource. You can't have the cake and eat it.
Given those restrictions, it is true. However, many times those types of systems implement mutex as an interrupt disable. Additionally, MOST processors (mips, ppc, arm, intel) provide these mechanisms. Since most people code on these systems, it is important to then expose people to the concepts.

Quote:
True. Simply said: there is no substitute for competence.
Always.
 
Old 03-13-2012, 09:05 AM   #14
sundialsvcs
Guru
 
Registered: Feb 2004
Location: SE Tennessee, USA
Distribution: Gentoo, LFS
Posts: 5,051

Rep: Reputation: 953Reputation: 953Reputation: 953Reputation: 953Reputation: 953Reputation: 953Reputation: 953Reputation: 953
The notion that orgcandman is referring to is based on the fact that the actual probability of interference with any particular queue-operation is very slight indeed ... "slight" enough to be dealt with using what is basically a busy-wait loop. The approach is taken in a well understood edge case in which so many queue operations are performed per-second that the overhead of system calls is undesirable and only "slightly" necessary.

Microprocessors do implement "atomic" memory operations, e.g. the LOCK prefix of the x86 architecture, and libraries expose subroutines which employ them.

The concept and the implementation are quite similar to, but not exactly like, that of a "spin lock."

In the old IBM mainframe architectures, these instructions were called compare and swap, and I mention that because I think the name is quite descriptive. In one, atomic operation, compare the value in a memory-location to what is expected, and if so, replace it with something else (otherwise don't). The instruction is executed in such a way that even on a multi-CPU system the instruction ... which IIRC is non-privileged ... will execute correctly on any of them. The notion of using this to maintain a shared queue is so straightforward that many programming textbooks include it ... yet, at one time, IBM actually patented it.

Last edited by sundialsvcs; 03-13-2012 at 12:06 PM.
 
Old 06-16-2012, 05:50 AM   #15
TheIndependentAquarius
Senior Member
 
Registered: Dec 2008
Posts: 4,598
Blog Entries: 29

Original Poster
Rep: Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880Reputation: 880
This is my understanding now:

It is necessary to lock the mutex variable 'before' attempting.
to make the threads wait.

Example scenario:
- Thread A wants to do something once a variable `count` is
non-zero in `functionA`.
- Thread B will signal when it increments the variable `count`
(which will set variable `count` to something other than zero)
in `functionB`.

Since one mutex variable cannot be locked by more than one
thread at a time, it is a possibility that `ThreadB` might increment
the `count` variable and send the signal /before/ the `ThreadA`
waits on the particular condition variable.

So, now `ThreadA` unaware of the fact that the signal has already
been sent will wait on the condition variable for ever and ever.

A `pthread_cond_signal ()` doesn't 'persist' - if there are no
threads waiting on the condition variable declared by `pthread_cond_t`,
the signal gets lost and cannot be recovered.

So, the mutex lock when acquired by `ThreadA`, will prevent
`ThreadB` from incrementing the `count` variable (and sending the
signal) until `ThreadA` waits on the condition variable (which will
then automatically release the lock for `threadB` to access).


Quote:
Originally Posted by Anisha Kaul View Post
by invalidate you mean that the condition should be set to true before writing?
I must be day dreaming when I wrote this, BTW.
 
  


Reply

Tags
c++, condition-variables, pthreads


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Trackbacks are Off
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
[SOLVED] pthread threads and mutex naaman Programming 1 02-07-2011 02:50 AM
Pthread mutex doubt rajesh1978 Programming 2 09-17-2010 09:34 AM
Difference between condition variable and mutex linux_ujjwal Linux - General 4 05-10-2005 03:17 AM
How does pthread_mutex_lock() lock mutex in pthread icoming Programming 0 12-04-2004 08:54 AM
pthread mutex issue gauge73 Programming 6 04-20-2004 05:29 PM


All times are GMT -5. The time now is 04:07 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration