Sign in to follow this  
Narf the Mouse

Getting a feel for threading - Perplexing problem

Recommended Posts

To get a feel for threading, I decided to make a simple action/display set-up - One thread would count, the other would display the count. The main thread would wait until a key was pressed, then end. It works almost perfectly - For some reason, it pauses every few seconds. I'm wondering why. Thanks for any and all help.
        static void Main(string[] args)
        {
            System.Threading.Thread threadCount = new System.Threading.Thread(Count);
            System.Threading.Thread threadDisplay = new System.Threading.Thread(Display);
            threadCount.IsBackground = true;
            threadDisplay.IsBackground = true;
            threadDisplay.Start();
            threadCount.Start();
            

            Console.ReadKey(true);
        }


        static int n = 0;


        static void Count()
        {
            while (1 == 1)
                n = n + 1;
        }


        static void Display()
        {
            while (1 == 1)
                Console.WriteLine(n);
        }

Share this post


Link to post
Share on other sites
WriteLine and 'n=n+1' are not guaranteed to be atomic operations. So what happens is the following:
load n from memory into register a
push 1 into register b
add a to b
write result into memory of n

These are technically 4 operations, and WriteLine can execute many times in between. Even if such operation is implemented atomically, there is no synchronization between two threads, meaning they each run independently.

Due to too many reasons, WriteLine can execute hundreds, even thousands of times while the above code is executing, seeing no change at all. On multiple cores, without n being volatile, each core might not write the value back into memory/cache for other core to be able to use it.

And on single core or HT machines, each of the busy loops can dominate the CPU time, starving the other thread.

At minimum, n must be declared as volatile, and adding a Thread.sleep(0 or 1) into the busy loops would help balance the load.

This type of constructs are generally undesirable though, there are considerably better ways to communicate between threads.

Share this post


Link to post
Share on other sites
Ah - So first, store a copy for WriteLine of the last thing it wrote and only execute if n != copy?

Thanks - What would be a good tutorial on those constructs?

Also, .Net's Console is very slow - Count executes a lot more than Display.

Edit: Adding Thread.Sleep(1); to Display appears to have fixed the problem.

Share this post


Link to post
Share on other sites
Quote:
Original post by Narf the Mouse

Edit: Adding Thread.Sleep(1); to Display appears to have fixed the problem.


Unless you declare the shared variable volatile, you haven't solved anything, just hid the problem on your CPU on your CLR for this test. It is the count() that is problematic.

You need to add sleep to both threads, or it will likely break on single core or HT CPUs, where increment thread will take over all the CPU. Run your test, set processor affinity to single core, and the problem will likely manifest itself.

Share this post


Link to post
Share on other sites
you realy shoud look after the voilatile and atomic solution you will definetly need it later

"You need to add sleep to both threads, or it will likely break on single core or HT CPUs"


why ?

unless you give it a higher priority it will use its timeslice and get to the and of the quee

Share this post


Link to post
Share on other sites
#include <intrin.h>
#pragma intrinsic(_InterlockedIncrement)
volatile long n;
DWORD WINAPI ThreadProc(LPVOID lpParameter)
{
while(1)
{
if(lpParameter)
{
wchar_t str[1000];
wsprintf(&str[0], L"Num: %d \n", n);
OutputDebugString(&str[0]);
}
else
{
_InterlockedIncrement(&n);
}
};
return 0;
};


int WINAPI WinMain(HINSTANCE hInst, HINSTANCE, LPSTR, int)
{
CreateThread(0, 0, &ThreadProc, 0, 0, 0);
CreateThread(0, 0, &ThreadProc, (void*)1, 0, 0);

Share this post


Link to post
Share on other sites
Quote:
Original post by Discard_One
#include <intrin.h>
#pragma intrinsic(_InterlockedIncrement)
volatile long n;


What exactly does locked increment do here that isn't covered by volatile already (note the OP has C# code)?

Given there is a one reader+writer and one passive observer, what additional safety would interlocked operations bring? Observer cannot read inconsistent value, and there is no synchronization.

Quote:
why ?

unless you give it a higher priority it will use its timeslice and get to the and of the quee


Because busy wait loops don't work well with the scheduler - original example is effectively a spin-wait. It will not break, but is very likely to cause scheduling degradation.

Same caution must be taken when designing lock-less algorithms with multiple readers and/or multiple writers. This is much less of a concern these days due to prevalence of multi-core.

Share this post


Link to post
Share on other sites
Quote:

isn't covered by volatile already (note the OP has C# code)

Unless I read the article wrong, C# "volatile" only insures that all threads reading get the latest value, and any write will instantly become the correct value in memory.(memory being the cache)

This confirms
So,
n = n + 1
running in two threads A could read "5". B then reads "5". A increments and stores "6". B increments and stores "6". When n should have been "7".
Volatile is not a replacement for lock.
the interlockincrment insures that n takes the value of 7 in the above example.

BUT as you said, there is only one writer. and one reader.
So, really the only problem is that the writer can update n several times before the reader reads n. But, that might not be a problem, so there might not be a need to actually lock increment.

Share this post


Link to post
Share on other sites
here nothing

but if he looks it up he will find the other interloked funcs


EDIT:

we have just 1 thread incrementing in my example but yeh if an other comes to it we coud get problems


EDIT2:

by the way i expect increment to by faster then x += 1 , x++ or similair

Share this post


Link to post
Share on other sites
Quote:
Original post by KulSeran

running in two threads A could read "5". B then reads "5". A increments and stores "6". B increments and stores "6". When n should have been "7".
Volatile is not a replacement for lock.
the interlockincrment insures that n takes the value of 7 in the above example.


Read the original example again. n is only modified by a single thread. It is also read from another thread.

The value that WriteLine reads may be delayed, but the way this code works, there is no concept about what this delay means. As such, it is impossible to argue what exactly the correct value should be, except that value printed by WriteLine will always be valid (it will not be corrupted, or decrement - it will be consistent with regard to algorithm, overflow excluded).

This is not reader/writer concurrency, it is reader+writer in one threads, along with independent observer.

Volatile in this case should only make sure that n isn't stuck in one core's cache, or purely in register, or something even odder.


A real world example is this:
volatile bool running = true;

// in a separate thread
while (running) {
//
}


When running is set to false, thread is signaled to exit at its discretion. It is not possible to order thread to stop now, or to wait until it stops (as far as our code is involved, join() is separate concept).

Using InterlockedXXX in above case would not make code any safer or more reliable. Volatile however is needed. Either way, this type of cross-thread communication is potentially fragile, which is why explicit message passing or safely shared structures are preferred, or all the edge cases of sharing must be taken into account (perhaps sharing a buffer of vertices or similar).

Share this post


Link to post
Share on other sites
It's meant to simulate (At a very basic, very simple level) update logic and display logic (Although that may be obvious)

I intend to introduce, over time, additional complexity, until such a point as I understand it well enough to use it in a non-test environment.

Share this post


Link to post
Share on other sites
Unfortunately your solution for 1 small data type doesn't scale beyond that 1 small data type. As soon as you need to start reading multiple bits of information then you run the risk of things having changed while you do that, meaning the information you end up with is incoherent. That's why you shouldn't generally play around with trying to read variables atomically and instead use the safe and proven methods to provide mutual exclusion (preferably via the higher level constructs provided by your language).

Share this post


Link to post
Share on other sites
Well, that's what learning is about - Knowing what works and what doesn't. And I learn by doing.

That being said, here's the current state of the code. Feel free to comment on what I did right and, of course, what I did wrong.

Thanks for any and all help.


static void Main(string[] args)
{
System.Threading.Thread threadCount = new System.Threading.Thread(Count);
System.Threading.Thread threadDisplay = new System.Threading.Thread(Display);
threadCount.IsBackground = true;
threadDisplay.IsBackground = true;
threadDisplay.Start();
threadCount.Start();

Console.ReadKey(true);
shouldStop = true;
}


volatile static bool shouldStop = false;
static Vector2 n = Vector2.Zero;
static Vector2 n2 = Vector2.One;
volatile static State state = State.Neutral;


static void Count()
{
while (!shouldStop)
{

if (state == State.Neutral)
{
state = State.Counting;
n += n2;
state = State.Neutral;
}
System.Threading.Thread.Sleep(0);
}
}


static Vector2 copy = n;
static void Display()
{
while (!shouldStop)
{
if (n != copy &&
state == State.Neutral)
{
state = State.Reading;
Console.WriteLine(n);
copy = n;
state = State.Neutral;
}
else
System.Threading.Thread.Sleep(0);
}
}


enum State
{
Neutral,
Counting,
Reading,
}

Share this post


Link to post
Share on other sites
Quote:
Original post by Narf the Mouse
Well, that's what learning is about - Knowing what works and what doesn't. And I learn by doing.

Unfortunately you can't learn correct concurrency by doing, because it's possible to write incorrect code that appears to work, indefinitely. Until it breaks. It's not science, it's mathematics - you need to learn the principles, not experiment and watch the observations.

Your code is full of race conditions, because it's not safe to do the if-checks on a state and then change the state in the way you're doing it. Example:

- counting thread passes the if (state == State.Neutral) check.
- context switch happens.
- display thread passes the if (state == State.Neutral) check.
- display thread calls Console.WriteLine(n) - n is written
- context switch happens.
- counting thread sets state => State.Counting;
- counting thread increments n to be n+n2
- context switch happens
- display thread stores n+n2 in the copy instead of the value it just wrote to the console
...
- display thread will fail to ever display the value n+n2 and will wait for counting thread to move to next value.

In short you can't do the compare and set in 2 operations. The hardware provides mechanisms to do this atomically, and your language probably provides classes that expose this functionality, in the form of semaphores, locks, mutexes, critical sections, condition variables, monitors, rendezvous, whatever.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this