?
Solved

Executing statements atomically

Posted on 2005-03-15
22
Medium Priority
?
331 Views
Last Modified: 2012-06-21
Hi ,
I want to ensure that two statements in my c++ program be executed atomically.. The other thread in the program should not continue running before both these statements are executed. Is there any way to do this in c++.

Regards,
A
0
Comment
Question by:Archiskulkarni
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 5
  • 3
  • +4
22 Comments
 
LVL 30

Expert Comment

by:Axter
ID: 13542650
Hi Archiskulkarni,
You can add these two statements in the top of your main() function to make sure they get executed first.

David Maisonave :-)
Cheers!
0
 

Author Comment

by:Archiskulkarni
ID: 13542808
No, these 2 statements are in the middle of the code and I want to ensure that the thread executing these statements should not give control to the other thread unless both these statements are executed.
0
 
LVL 30

Expert Comment

by:Axter
ID: 13542832
>>No, these 2 statements are in the middle of the code and I want to ensure that the thread executing these statements should not give control to the other thread unless both these statements are executed.

Then you can in a seperate function that can be called by both main() and youre sperate code?

If this doesn't answer your question, then please post your code, so that we can give a better answer.

We need to see your code for a more detailed answer.
0
What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

 
LVL 12

Expert Comment

by:andrewjb
ID: 13542991
Generally the problem is that you're trying to protect some resource (variable/class/memory location) from being accessed by two threads at once.

e.g.

a = GetValueFromSomeWhere()
SetValueBack( a + 1 )

Do this in two threads at once, and you might end up running the first statement in both threads first, then the second (and hence only incrementing the target resource once, not twice.

In this case, you'd use something like a mutex, which means thread2 will get blocked whilst thread1 does the two lines, and vice-versa.

i.e.

GetMutex()
a = GetValueFromSomewhere()
SetValueBack( a + 1 )
ReleaseMutex();

Most O/S offer various mutex/semaphore etc. and other locking mechanisms.


If you can't tweak your problem to look like this, then I can't personally think of a way other than temporarily stalling the second thread. Can't remember the exact call, but something like

SuspendThread( Thread2ID)
... do atomic statements
RestartThreaD( Thread2ID )


0
 
LVL 9

Expert Comment

by:rcarlan
ID: 13543597
Robust and effective concurrent programming is much more difficult than it may appear. I'm not trying to use big words ro to start a polemic. It's just a reality of the current programming technologies which generally rely on the exclusive acquisition of locks. It's too error prone and more often than not leads to deadlocks.

While it is theoretically possible to achieve what you want, finding and implementing a robust solution (that meets the criteria under all circumstances, present and future, and does not lock, in the current code nor after who knows how many maintenance cycles) may prove to be a rather difficult exercise. The solution will be very much dependent on current implementation details and it may be very difficult to safeguard against future changes.

Because I do not know enough about your specifics (i.e. how many threads and what exactly are they doing), I can only provide some generic pointers:

If you want to serialize access to a section of the code (i.e. ensure only one thread at a time may enter), use a critical section.

If you want to serialize access to a shared resource (i.e. ensure only one thread at a time may access it), use semaphores - they are lighter than mutexes but are limited to controlling threads belonging to the same process. Use mutexes if you want to serialize threads belonging to different processes.

If what you have is two threads (not more) and you have a piece of code that is executed by only one of these threads, and you want this piece of code to be executed "atomically", you can indeed consider the approach suggested by andrewjb. Assuming you are writing a Windows program, you can do the following:

// code executed by Thread1 only
HANDLE hThread2 = GetOtherThreadHandle();   // the handle of the 'other' thread - from somewhere (even global variable)

SuspendThread(hThread2);       // when running on an NT kernel (NT, W2K, XP, W2003),
                                               // there are certain permissions required to be able to suspend another thread
                                               // (it should generally be OK if the thread belongs to the same process)

// execute atomic code (needs careful consideration, see comments below)

ResumeThread(hThread2);


First of all, the solution doesn't scale. It may work with two threads, but it would be very difficult to extend it to something more generic. This may not be an issue for your specific case - I don't know.

Secondly, the 'atomic' code must not acquire any kind of exclusive locks to synchronisation objects (semaphores, mutexes, etc) that may also be used by the other thread. This may sound trivial and easy, but it's actually very difficult to police in large-scale applications that go through many maintenance cycles. For example, if as part of the atomic code you are calling a function or a method, you've opened the door to potential deadlocks - if not now, with the current code, then in the future.

0
 
LVL 22

Expert Comment

by:grg99
ID: 13544134
IIRC from my old OS class, there's no way to do this without access to some machine-dependent test-and-set operation, which you won't find built-into C or C++.  


You need access to some system-supplied API that does this.  In Windows, it's the mutex or semaphore operations.

0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 13545063
The simplest would be to wait in your thread til the two statements are executed. You need a global bool variable or a bool variable that is passed to the thread and could be access both by main and by the thread:

1. Using a global variable

main.cpp

bool g_statementsWereExecuted = false;

int main()
{
    ...
     _beginthread(threadProc, NULL, NULL);
     ....
     statement1();
     statement2();
     g_statementsWereExecuted = true;
     ...

     return 0;  
}

thread.cpp

extern bool g_statementsWereExecuted;

unsigned long threadProc(void* pParam)
{
     while (!g_statementsWereExecuted)
     {
          Sleep(1);  // to give other threads a chance
     }
     doWhatEverHasToBeDone();
     return 0;
}


2. Using a parameter to thread


main.cpp

struct ThreadParam
{
    ...
    bool statementsWereExecuted;
    ThreadParam() : statementsWereExecuted(false) {}
};

int main()
{
    ...
    ThreadParam pParam = new ThreadParam;
   
     _beginthread(threadProc, NULL, pParam);
     ....
     statement1();
     statement2();
     pParam->statementsWereExecuted = true;
     ...

     return 0;  
}

thread.cpp


unsigned long threadProc(void* pParam)
{
     ThreadParam p = (ThreadParam*) pParam;
     while (!p->statementsWereExecuted)
     {
          Sleep(1);  // to give other threads a chance
     }
     doWhatEverHasToBeDone();
     return 0;
}

Note, of course you could use a Mutex, CriticalSection, Semaphore, Event, WaitForSingleEvent(..), ...  to prevent the thread from being executed before the two statements. However, it isn't much faster and much more complex than the few lines above. You also should know that if you are using a mutex you have to lock it *before* you are creating the thread.

Regards, Alex
0
 
LVL 22

Expert Comment

by:grg99
ID: 13545306
Ah, nice try Mr. A, but you're assuming you have a-priory knowledge and control that ensures the other stuff isnt running beforehand.  In most cases you don't know this.    If I remember my Dijkstra stuff right, you can't keep two tasks from entering the same region without having a test-and-set primitive.  And I think this was actually proven.  Or at least nobody has been able to come up with a counter-example in the last 29 years.



0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 13545774
>>>> Ah, nice try Mr. A, ...

Sorry, I didn't understand a word of what you are saying. Did you reflect to my code above or is it another comment you are referring to?

Regards, Alex
0
 
LVL 22

Expert Comment

by:grg99
ID: 13546178
Yours I think.

You're assuming you can hold off running one thread.  In general, the threads are going to be already running at at arbitray locations in their code.  

A Dr. Djikstra is the guy that invented semaphores, just to solve this problem.  He showed IIRC that you can't interlock two separate threads with simple variables.  You need some primitive instruction that can set a flag and test it in the same atomic cycle.  That's why any multi-task capable CPU made after then has a test and set instruction, or extra hardware to effectively do the same.
.


0
 
LVL 30

Expert Comment

by:Axter
ID: 13546245
Since the use is not adding any feedback here, and IMHO, all we're doing is guess work, I'll unsubscribe.
Good Luck!
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 13546559
>>>> You're assuming you can hold off running one thread.

Yes, the Sleep loop function definitively will wait til the bool flag turns to true. That is, because main thread and worker thread share the same address space and the bool flag is initialized to false *before* the worker thread was invoked. The bool flag is set to true after the statements of interest were executed. This setting definitively will cause the worker thread to break the while loop and go on. That isn't a guess but proven practice.

Regards, Alex
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 13547915
Note, I did not say that bool flags could/should be used to replace a mutex. That isn't impossible but not efficient as you have to implement a lot of waits to make sure that a bool flag could have been recognized by a concurrently running thread. But for the simple case where only one thread is allowed to write to a resource and all others only read, you can use bool flags like traffic lights. If the writing thread wants exclusive access to the resource it sets a lock flag. Then, it checks a read flag for any other thread and goes on if all read flags were set to unlocked. Threads that want to read from the resource are setting their own read flag indicating that they currently were reading the resource. After setting the read flag it checks the lock flag of the writing thread was set. If yes it resets the own read flag and polls til the lock flag was released. If not locked it reads the resource and resets the own read flag after read. Let's check the crucial test case:  thread 1 wants to write to the resource, thread 2 wants to read the resource nearly same time.

case 1:

     t1 sets write flag
     t2 sets read flag t2
     t2 doesn't recognize write flag as the read operation was same time as the write operation
     t1 checks read flag t2
     t1 recognizes read flag t1
     t1 polls til read flag t1 was reset
     t1 checks all further read flags

Note, we assumed t2 doesn't recognize write flag because of running same time. Because of that, t1 *must* recognize the read flag t2 as only of these two threads could be late to recognize a previously set flag.

case 2:

     t2 sets read flag t2
     t1 sets write flag
     t2 recognizes write flag
     t2 resets read flag t2
     t2 polls til write flag is reset
     t1 regognizes read flag t2 as unlocked
     t1 writes to resource
     
You see, that the case is safe even if t1 wouldn't recognize that t2 has reset the read flag t2. If so, it would poll a short time and finally recognize that read flag 2 is unlocked.

case 3:

    t2 sets read flag t2
    t1 sets write flag
    t2 doesn't recognize write flag
    t1 doesn't recognize read flag

That case could not happen as only one of these threads could be late.

Hope, it was understandable.

Regards, Alex


0
 
LVL 22

Expert Comment

by:grg99
ID: 13548521
Goody, I agree in a few simple cases you can use a pair of plain old boolean flags to interlock access.  May save CPU time, but then again if there's a system API that can block and schedule tasks efficiently, it can avoid a lot of looping and checking.


But the original question (remember that? :))  was to interlock two arbitrary statements, not just the special case of one writer and several readers.

maybe if ( YOO HOO ) the Original Poster can explain in a bit more detail what they want to interlock we can fine-tune our recommendations.

Regards,


grg99





 
0
 
LVL 9

Expert Comment

by:jhshukla
ID: 13550635
Here is a solution without semaphores taken straight from my OS txtbk. This works only for 2 threads. For more than 2 threads, complexity rockets.

bool flag[2] = {false, false};
int turn;

Thread0 {
  flag[0] = true; //post a request
  turn = 1; //this allows other thread to run. if other thread overwrites, it is blocked and this runs
  while(turn == 1 && flag[1] == true); //while(allow_other & other_running) I will wait.
  //critical
  flag[0] = false; //I am not running anymore, let the other thread run
}

Thread1 {
  flag[1] = true;
  turn = 0;
  while(turn == 0 && flag[0] == true);
  //critical
  flag[1] = false;
}
0
 

Author Comment

by:Archiskulkarni
ID: 13552504
Hi All,
Thanx for your suggestions.. well, the actual problem is like this..

I have a parser, which parses a stream progressively. Now, I want to run the parser code in a separate thread. Whenever the parser parses a chunk of data, it should inform the second thread that it has parsed a portion of data. Then the second thread should use that data parsed by the first thread. After that it should again invoke the first thread to parse the next chunk of data.. so on and the cycle continues till the stream is parsed completely..
So I guess this situation resembles the common Producer-consumer problem (correct me if I am wrong).. Can this be achieved with a single semaphore.. and wait on the value of this semaphore in the 2 threads.

something like
Thread1
parse()
set Semaphore()
wait till semaphore becomes false.

Thread2
While(not done with parsing)
{
         wait till semaphore becomes true.
         use parsed data().
         resetSemaphore()
}

p.s. - Sorry for all the confusion caused by initial explanation of the problem.. Actually I was trying it differently and I explained only that portion of the problem, so it was not clear.. Hope things are clear now.

Regards,
A
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 13553118
>>>> But the original question (remember that? :))  ...

If you would read the original question you easily could see that the case is much easier than the one writer and several readers scenario.

>>>> while(turn == 1 && flag[1] == true);

That statement brings CPU up to 100% (or 50% on hyper-threading).


>>>> So I guess this situation resembles the common Producer-consumer problem

You also could see it  as a problem of a shared resource - here the data already parsed - that shouldn't be changed (by Thread1) while another thread (Thread 2) was reading the data.

So, the simplest way is to lock the resource by a Mutex (or CriticalSection if you are on Windows platform).

struct ParsedData
{
    string data;
    string parsed;
    bool   modified;
    Mutex mutex;
};

Thread 1:

   // get thread parameter
   ParsedData* ppd = (ParsedData*)pParam;

   ....

   mutex.lock();
   ppd->parsed = getParsedData();
   ppd->modified = true;
   ppd->mutex.unlock();
   
   ...

Thread 2:
   
    ParsedData pd;
    startThread(threadProc, NULL, &pd);

    while (true)
    {

         if (pd.modified)
         {
              pd.mutex.lock();   // wait til thread 1 has unlocked
              string s = pd.parsed;
              pd.modified = false;
              pd.mutex.unlock();

              doSomethingWithString(s);
         }
         else
              Sleep(1);
         
    }  


Regards, Alex
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 200 total points
ID: 13553200
FYI:
A Semaphore is used if a limited number of threads could use a resource. The Semaphore has a counter that was decremented if a thread uses the resource. If the counter is 0 the resource was locked.

If the initial count is 1, a Semaphore does the same as a Mutex.

Regards, Alex
0
 
LVL 22

Assisted Solution

by:grg99
grg99 earned 200 total points
ID: 13554736
Aha, interesting, you really have "coroutines" here.

As others have suggested, in this simplest of all cases, you can interlock them with a boolean variable or two, or an access counter.   No need for some high-falootin test-and-set gadget.




0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generat…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses

800 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question