OSDev.org

The Place to Start for Operating System Developers
It is currently Tue Dec 11, 2018 10:57 pm

All times are UTC - 6 hours




Post new topic Reply to topic  [ 14 posts ] 
Author Message
 Post subject: See if i can generate race condition, is my approach ok?
PostPosted: Thu Dec 06, 2018 4:09 pm 
Offline
Member
Member

Joined: Wed Nov 18, 2015 3:04 pm
Posts: 337
Location: San Jose San Francisco Bay Area
I posted on cplusplus but decided to put here for better response. Idea is to create race condition, done in C. main() will fire of two threads (can be changed to arbitrary by setting CONFIG_THREAD_COUNT). Each thread will run hello() in which it loops X thousands of times to read SUM variable wrote to file, add RAND() to SUM and write the RAND() as well as SUM+RAND() to file. Therefore each thread's loop will create thousands of file in current directory: file-<threadID>-<loopNo> which I merge into single file "cat file-* > file.all.log.

Instead of scouring through thousands of lines for error, race-check.py little utility will read the merged file one-by-one, parse and do the addition again and compare the result. (code below).

If I may see result looks promising:
With mutex line disabled, expected the possibility of race condition. with 2 threads and 20,000 loops, python found two addition that makes no sense:

Code:
[root@dev]# cat race.found.log
RACE!: ['75330', '2', '75877']
RACE!: ['103486', '2', '104581']
RACE!: ['34712', '3', '35232']
RACE!: ['105220', '5', '105751']


checked the surrounding line with addition 75530+2

Quote:
[root@dev]# egrep -ir "75330:2" file.all.log -A 2 -B 2
threadNo. 0:75321:4:75325
threadNo. 0:75325:5:75330
threadNo. 0:75330:2:75877
threadNo. 0:75877:2:75879
threadNo. 0:75879:4:75883


I then reduced the CONFIG_THREAD_COUNT to 1 effectively making a single-threaded or no concurrency, main() will launch only 1 thread and do not bother with SUM, therefore only only one instance of hello() will sequentially add it thousands of times and yes, with the result, race-check.py did not find any inconsistency.

As a next step, I am applying the mutex inside the hello and see how it goes which I haven't tried.

Code:
#include <list>
#include <mutex>
#include <algorithm>
#include <thread>
#include <iostream>
#include <fstream>
#include <sstream>
#include <unistd.h>

using namespace std;

std::mutex mutex_sum;
int sum = 0;

void hello(int pId, int pStat[])
{
    int pNum;
    int i;

    std::cout << pId << ": Hello CONCURRENT WORLD " << endl;

    for (int i = 0; i < 1000000; i++ ) {
        pNum  = rand() % 4 + 2;

        cout << pId << ": " << ", loop: " << i << endl;
        // read + sum + read and write to file.

        ofstream myfile;
        ostringstream oss;
        oss << "file-" << pId << "-" << i;
        myfile.open(oss.str());
        myfile << "threadNo. " << pId << ":" << sum;
        sum += pNum;
        myfile << ":" << pNum << ":" << sum << endl;
        pStat[pId]  = 1;
        myfile.close();
    }
    std::cout << pId << ": Done sleeping exiting now..." << endl;
}

int main()
{
    // Declare, initialize variables.

    int i;
    const int CONFIG_THREAD_COUNT = 2;
    int stat[CONFIG_THREAD_COUNT];
    int sum = 0;

    // launch threads.

    for ( i = 0; i < CONFIG_THREAD_COUNT; i ++ ) {
        stat[i] = 0;
        std::thread t(hello, i, stat);
        t.detach();
    }
    cout << "Checking thread status-s..." << endl;

     while (sum != CONFIG_THREAD_COUNT)  {
        sum = 0;

        for (i = 0; i < CONFIG_THREAD_COUNT; i++) {
            cout << stat[i] << ", ";
            sum += stat[i];
        }

        cout << "main(): sum: " << sum << ". waiting for all threads to finish..." << endl;
        usleep(2 * 1000000);
    }

    return 0;
}


race-check.py:

Code:
fp = open("file.all.log")
fpOut = open("race.found.log", 'w')

if not fp:
    print "Failed to open."

line = fp.readline().strip()

counter = 0

while line:
    print line
    operands= line.split(":")[1:4]
    print "operands: ", operands

    if int(operands[0]) + int(operands[1]) != int(operands[2]):
        fpOut.write("RACE!: " + str(operands) + "\n")
        counter += 1

    line = fp.readline().strip()

if counter == 0:
    fpOut.write("No race condition found.")
    print "No race condition found."
else:
    print "At least one race condition found: ", counter

fp.close()
fpOut.close()

_________________
key takeaway after spending yrs on sw industry: big issue small because everyone jumps on it and fixes it. small issue is big since everyone ignores and it causes catastrophy later. #devilisinthedetails


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Thu Dec 06, 2018 10:12 pm 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 84
Nothing in your code actually locks the mutex. You need to take the lock after opening myfile at the latest, and release it after the last access to sum at the earliest.

What is the point of this exercise?


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Fri Dec 07, 2018 3:56 pm 
Offline
Member
Member

Joined: Wed Nov 18, 2015 3:04 pm
Posts: 337
Location: San Jose San Francisco Bay Area
nullplan wrote:
Nothing in your code actually locks the mutex. You need to take the lock after opening myfile at the latest, and release it after the last access to sum at the earliest.

What is the point of this exercise?

you have a wandering eye?

_________________
key takeaway after spending yrs on sw industry: big issue small because everyone jumps on it and fixes it. small issue is big since everyone ignores and it causes catastrophy later. #devilisinthedetails


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Fri Dec 07, 2018 4:26 pm 
Offline
Member
Member

Joined: Mon Feb 02, 2015 7:11 pm
Posts: 265
ggodw000 wrote:
you have a wandering eye?


Do you?

_________________
https://github.com/kiznit/rainbow-os


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sat Dec 08, 2018 2:33 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 84
ggodw000 wrote:
you have a wandering eye?


I am unfamiliar with that idiom. What did you mean to say?


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sat Dec 08, 2018 8:58 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1371
Location: Athens, GA, USA
TBH, that question (why you would deliberately create a race condition, something which mutual exclusion primitives are intended to help avoid by allowing only one process access at a time) was the first thing that came to mind for me, too. I'd ignored the thread up until now because the title didn't even make sense to me.

I assume that there is some reason why you would intentionally set up a race condition, but I am at a loss as to why. The only thing I can think of is that you are trying to learn how to detect them, but even that makes no sense - unlike, say, a deadlock condition, it is always possible to prevent a race condition through any of the mutual exclusion approaches in common use. Race conditions come about because of failure to use them when needed, or using them incorrectly, not because of an inherent limitation in mutual exclusion.

I suppose it could be just to see what a race condition's effects are, but that doesn't make much sense to me - the well known examples should be sufficient to demonstrate that.

So yeah, I'm just as confused as nullplan on this.

Your post does seem to allude to the possibility that this was for testing the detection code, which you were using to debug a program you know has a race condition which you couldn't pin down. However, you never stated this outright in the post, and the title implies that the race condition itself is the goal, which would seem pretty bizarre.

The confusion in this thread seems to involve an XY problem. Please, ggodw000, could you tell us what you are actually trying to accomplish?

nullplan wrote:
ggodw000 wrote:
you have a wandering eye?


I am unfamiliar with that idiom. What did you mean to say?


I know the idiom as it is used in English, but in this context it makes no sense :?: ; it usually refers to romantic infidelity (i.e., someone who keeps looking at attractive individuals other than their current partner, with the implication that they are doing more than just looking). Perhaps ggodw000 thinks that nullplan is going to cheat on their significant other with a hot piece of software? :twisted:

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Last edited by Schol-R-LEA on Sat Dec 08, 2018 10:30 am, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sat Dec 08, 2018 10:23 am 
Offline
Member
Member

Joined: Wed Aug 30, 2017 8:24 am
Posts: 84
Schol-R-LEA wrote:
I know the idiom as it is used in English, but in this context it makes no sense :?: ; it usually refers to romantic infidelity (i.e., someone who keeps looking at attractive individuals other than their current partner, with the implication that they are doing more than just looking). Perhaps ggodw000 thinks that nullplan is going to cheat on their significant other with a hot piece of software? :twisted:


Nah, gcc's the only girl for me! (Except for all the others).

NP: Die Ärzte - Alles für dich (look it up!)


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sat Dec 08, 2018 10:32 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1371
Location: Athens, GA, USA
nullplan wrote:
NP: Die Ärzte - Alles für dich (look it up!)



Yeah, girlfriend, I'm all for the D too... wait, we were talking programming, that must mean something else... :twisted:

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Last edited by Schol-R-LEA on Sat Dec 08, 2018 2:49 pm, edited 1 time in total.

Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sat Dec 08, 2018 2:29 pm 
Offline
Member
Member

Joined: Wed Nov 18, 2015 3:04 pm
Posts: 337
Location: San Jose San Francisco Bay Area
Schol-R-LEA wrote:
TBH, that question (why you would deliberately create a race condition, something which mutual exclusion primitives are intended to help avoid by allowing only one process access at a time) was the first thing that came to mind for me, too. I'd ignored the thread up until now because the title didn't even make sense to me.

I assume that there is some reason why you would intentionally set up a race condition, but I am at a loss as to why. The only thing I can think of is that you are trying to learn how to detect them, but even that makes no sense - unlike, say, a deadlock condition, it is always possible to prevent a race condition through any of the mutual exclusion approaches in common use. Race conditions come about because of failure to use them when needed, or using them incorrectly, not because of an inherent limitation in mutual exclusion.

I suppose it could be just to see what a race condition's effects are, but that doesn't make much sense to me - the well known examples should be sufficient to demonstrate that.

So yeah, I'm just as confused as nullplan on this.

Your post does seem to allude to the possibility that this was for testing the detection code, which you were using to debug a program you know has a race condition which you couldn't pin down. However, you never stated this outright in the post, and the title implies that the race condition itself is the goal, which would seem pretty bizarre.

The confusion in this thread seems to involve an XY problem. Please, ggodw000, could you tell us what you are actually trying to accomplish?

nullplan wrote:
ggodw000 wrote:
you have a wandering eye?


I am unfamiliar with that idiom. What did you mean to say?


I know the idiom as it is used in English, but in this context it makes no sense :?: ; it usually refers to romantic infidelity (i.e., someone who keeps looking at attractive individuals other than their current partner, with the implication that they are doing more than just looking). Perhaps ggodw000 thinks that nullplan is going to cheat on their significant other with a hot piece of software? :twisted:


Scrol-l-lea, I am going through intro to concurrent programming and yes deliberately create race condition to see if my understanding is right with this most simple example and with that, I deliberately chose not to use any mutex.
Two experiments so far I have done so far consistent answer so far but I wanted to have it scrutinzed:
- 2 threads repeatedly (looping) trying to write over shared variable. This found some inconsistency which I described well in my OP.
- 1 thread repeatedly trying to write over "shared" variable. This found no consistency which I also described why I think so in my OP.
No once my effort is scrutinzed and makes no sense, or just plain wrong, I'd rather to know why and how I got wrong.

_________________
key takeaway after spending yrs on sw industry: big issue small because everyone jumps on it and fixes it. small issue is big since everyone ignores and it causes catastrophy later. #devilisinthedetails


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sun Dec 09, 2018 10:47 am 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1371
Location: Athens, GA, USA
OK, that gives us a lot more context for the problem. Though, when you say going through intro to concurrent programming', are you referring to a class, to a specific textbook (such as this one) or video lecture series, or just the topic in general?

Sorry to keep interrogating you, but the more we know about what you are working from, the better (well, up to a point, anyway).

As for the plan... well, there is a classic and significantly simpler test, but it may prove to be too simple, namely the 'interleaved prints' test. This is simply the test of having two threads trying to print to the screen at the same time - the shared resource is the console. One should print something such as 'a' or "Hello,", while the other prints 'b' or "World!\n" - in other words, something where a break in the ordering would be obvious. With proper synchronization, they would print something like:

abababababababab...

or

Hello, World!
Hello, World!
Hello, World!
Hello, World!
...


Whereas a sync failure might give something like

ababababbabaaaabaababb...

or

Hello, World!
Hello, World!
Hello, World!
World! Hello, World!
Hello, World!
Hello, World!
Hello, Hello, World!
...
...

The advantages of this are a) a synchronization error is visually distinctive and easily found by eyeball inspection even in a large sample, and b) the printing routines themselves are large enough, run long enough, and ther running times are variable enough that they tend to introduce a desynchronization fairly quickly.

I don't know if this is the sort of test you were looking for, and whether you had tried it yourself or not yet (most textbooks use this example).

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sun Dec 09, 2018 2:33 pm 
Offline
Member
Member

Joined: Wed Nov 18, 2015 3:04 pm
Posts: 337
Location: San Jose San Francisco Bay Area
ok, so if you studied the code, and see since each thread will independently write to different file and even each loop within thread will create another file, whatever output, be it a screen or file has no problem.
the shared resource in this case is sum variable which two threads are competing to update.
now it is adding lot of numbers through each loop, the end result will eventually be the same even though it is a race condition, it is a benign race condition if one is only interested in the final result not the intermediate. that is why i decided to output the intermediate result to file which is a sum before and after addition during each loop hopefully to detect race condition.

The book i am studying from is C++ concurrence in action by Anthony Williams but this example I completely made up by contemplation.

_________________
key takeaway after spending yrs on sw industry: big issue small because everyone jumps on it and fixes it. small issue is big since everyone ignores and it causes catastrophy later. #devilisinthedetails


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sun Dec 09, 2018 2:41 pm 
Offline
Member
Member

Joined: Wed Jul 25, 2018 2:47 pm
Posts: 37
Location: Pizzaland, Southern Europe
ggodw000 wrote:
[...] now it is adding lot of numbers through each loop, the end result will eventually be the same even though it is a race condition, it is a benign race condition if one is only interested in the final result not the intermediate. [...]


That is not necessarily the case. To perform accumulations, a thread needs to read the value of the shared variable, sum the amount, and then substitute the shared variable. This creates the possibility that the end result is not going to be correct:

Code:
V := 0 // shared variable

Thread code:
  tmp := V + 1
  V <- tmp

Thread A:
  tmp := V + 1 = 0 + 1 = 1
  [Thread A is suspended]

Thread B:
  tmp := V + 1 = 0 + 1 = 1 // V has not been updated yet
  V <- 1
  [Thread B is suspended]

Thread A:
  V <- tmp // tmp is still 1, the result is not correct


This can be mitigated by using atomic operations, which are basically implicit mutexes


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sun Dec 09, 2018 3:35 pm 
Offline
Member
Member
User avatar

Joined: Fri Oct 27, 2006 9:42 am
Posts: 1371
Location: Athens, GA, USA
I'm still not sure why you want to create a race condition deliberately, though. I don't see what it teaches you, since the whole point in studying them in concurrent programming is to learn how to prevent them.

Race conditions are easy enough to create by accident, and I'm not sure if an exercise in creating them on purpose would give you any real knowledge that isn't inherent simply in knowing that race conditions exist at all. Since different circumstances lead to very different outcomes, there is also no general approach to mitigating or eliminating them which can be found from such a study, either.

So again: what are you trying to accomplish with this?

_________________
Rev. First Speaker Schol-R-LEA;2 LCF ELF JAM POEE KoR KCO PPWMTF
μή εἶναι βασιλικήν ἀτραπόν ἐπί γεωμετρίαν
Lisp programmers tend to seem very odd to outsiders, just like anyone else who has had a religious experience they can't quite explain to others.


Top
 Profile  
 
 Post subject: Re: See if i can generate race condition, is my approach ok?
PostPosted: Sun Dec 09, 2018 7:01 pm 
Offline
Member
Member

Joined: Wed Nov 18, 2015 3:04 pm
Posts: 337
Location: San Jose San Francisco Bay Area
Schol-R-LEA wrote:
I'm still not sure why you want to create a race condition deliberately, though. I don't see what it teaches you, since the whole point in studying them in concurrent programming is to learn how to prevent them.

Race conditions are easy enough to create by accident, and I'm not sure if an exercise in creating them on purpose would give you any real knowledge that isn't inherent simply in knowing that race conditions exist at all. Since different circumstances lead to very different outcomes, there is also no general approach to mitigating or eliminating them which can be found from such a study, either.

So again: what are you trying to accomplish with this?

I think it is fun to create one and doing so reinforces your understanding.

_________________
key takeaway after spending yrs on sw industry: big issue small because everyone jumps on it and fixes it. small issue is big since everyone ignores and it causes catastrophy later. #devilisinthedetails


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 14 posts ] 

All times are UTC - 6 hours


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group