Skip to content
  • Categories
  • Recent
  • Tags
  • Popular
  • World
  • Users
  • Groups
Skins
  • Light
  • Cerulean
  • Cosmo
  • Flatly
  • Journal
  • Litera
  • Lumen
  • Lux
  • Materia
  • Minty
  • Morph
  • Pulse
  • Sandstone
  • Simplex
  • Sketchy
  • Spacelab
  • United
  • Yeti
  • Zephyr
  • Dark
  • Cyborg
  • Darkly
  • Quartz
  • Slate
  • Solar
  • Superhero
  • Vapor

  • Default (No Skin)
  • No Skin
Collapse
Code Project
  1. Home
  2. General Programming
  3. Algorithms
  4. Threading problem

Threading problem

Scheduled Pinned Locked Moved Algorithms
comdebugginghelpquestion
11 Posts 4 Posters 0 Views 1 Watching
  • Oldest to Newest
  • Newest to Oldest
  • Most Votes
Reply
  • Reply as topic
Log in to reply
This topic has been deleted. Only users with topic management privileges can see it.
  • A Anthony Mushrow

    I'm a little tired of staring at these few lines and not seeing the problem. Take this code:

    volatile int WorkingBuff = 0;
    volatile int NextBuff = 1;
    volatile int RenderBuff = 1;

    //Thread A
    void stuff()
    {
    NextBuff = WorkingBuff;
    int usedId = 0;
    do
    {
    usedId = RenderBuff;
    for(int i=0; i<3; i++)
    {
    if(i != NextBuff && i != usedId)
    WorkingBuff = i;
    }
    } while(RenderBuff != usedId);
    }

    //Thread B
    void render()
    {
    RenderBuff = NextBuff;
    //do stuff with RenderBuff
    }

    Could anybody point out the situation where WorkingBuff and RenderBuff have the same value? I'm just not seeing it.

    My current favourite phrase: I've seen better!

    -SK Genius

    Source Indexing and Symbol Servers

    A Offline
    A Offline
    Alan Balkany
    wrote on last edited by
    #2

    1. NextBuff = WorkingBuff; in Thread A. 2. Thread A is blocked and Thread B starts. 3. RenderBuff = NextBuff; in Thread B.

    A 1 Reply Last reply
    0
    • A Alan Balkany

      1. NextBuff = WorkingBuff; in Thread A. 2. Thread A is blocked and Thread B starts. 3. RenderBuff = NextBuff; in Thread B.

      A Offline
      A Offline
      Anthony Mushrow
      wrote on last edited by
      #3

      Sorry, I should have elaborated a bit. I mean after the do-while loop had run. I'm having a problem it seems, where I'm trying to render with stuff I'm in the middle of updating.

      My current favourite phrase: I've seen better!

      -SK Genius

      Source Indexing and Symbol Servers

      A 1 Reply Last reply
      0
      • A Anthony Mushrow

        Sorry, I should have elaborated a bit. I mean after the do-while loop had run. I'm having a problem it seems, where I'm trying to render with stuff I'm in the middle of updating.

        My current favourite phrase: I've seen better!

        -SK Genius

        Source Indexing and Symbol Servers

        A Offline
        A Offline
        Alan Balkany
        wrote on last edited by
        #4

        You could use lock () around the places you absolutely don't want to execute concurrently. This would remove all the uncertainty and make your code more reliable.

        A 1 Reply Last reply
        0
        • A Alan Balkany

          You could use lock () around the places you absolutely don't want to execute concurrently. This would remove all the uncertainty and make your code more reliable.

          A Offline
          A Offline
          Anthony Mushrow
          wrote on last edited by
          #5

          True, but I was aiming for a lock-free solution as they are surprisingly expensive.

          My current favourite phrase: I've seen better!

          -SK Genius

          Source Indexing and Symbol Servers

          A 1 Reply Last reply
          0
          • A Anthony Mushrow

            I'm a little tired of staring at these few lines and not seeing the problem. Take this code:

            volatile int WorkingBuff = 0;
            volatile int NextBuff = 1;
            volatile int RenderBuff = 1;

            //Thread A
            void stuff()
            {
            NextBuff = WorkingBuff;
            int usedId = 0;
            do
            {
            usedId = RenderBuff;
            for(int i=0; i<3; i++)
            {
            if(i != NextBuff && i != usedId)
            WorkingBuff = i;
            }
            } while(RenderBuff != usedId);
            }

            //Thread B
            void render()
            {
            RenderBuff = NextBuff;
            //do stuff with RenderBuff
            }

            Could anybody point out the situation where WorkingBuff and RenderBuff have the same value? I'm just not seeing it.

            My current favourite phrase: I've seen better!

            -SK Genius

            Source Indexing and Symbol Servers

            L Offline
            L Offline
            Luc Pattyn
            wrote on last edited by
            #6

            when you have a producer, a consumer, and a number (at least 2) of equivalent buffers, I find it most easy to have two queues, one holding "empty" buffers (emptied by the consumer, to be filled by the producer), one holding "full" buffers (filled by the producer, to be processed by the consumer). That is an approach that is simple to understand; it works well, it doesn't create new objects once initialized, and it doesn't really need locking, except the Queue.Dequeue operation should wait for a buffer being returned. In pseudo-code:

            // init
            emptyQ=CreateQueue();
            fullQ=CreateQueue();
            for(N times) emptyQ.Queue(new Buffer());

            // producer
            forever {
            buf=emptyQ.Dequeue(); // blocking
            ...fill buf
            fullQ.Queue(buf);
            }

            // consumer
            forever {
            buf=fullQ.Dequeue(); // blocking
            ... process buf
            emptyQ.Queue(buf);
            }

            :)

            Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum

            Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.

            A 1 Reply Last reply
            0
            • A Anthony Mushrow

              True, but I was aiming for a lock-free solution as they are surprisingly expensive.

              My current favourite phrase: I've seen better!

              -SK Genius

              Source Indexing and Symbol Servers

              A Offline
              A Offline
              Alan Balkany
              wrote on last edited by
              #7

              It's surprisingly complex for such a short fragment because of the possible interactions between threads, and the shuffling of values among four variables. Maybe it could be rewritten in a simpler way. A useful step in analyzing code like this is identifying invariant conditions, that are guaranteed to always be true at some point in the code. But it looks like the variable shuffling makes this impossible.

              A 1 Reply Last reply
              0
              • L Luc Pattyn

                when you have a producer, a consumer, and a number (at least 2) of equivalent buffers, I find it most easy to have two queues, one holding "empty" buffers (emptied by the consumer, to be filled by the producer), one holding "full" buffers (filled by the producer, to be processed by the consumer). That is an approach that is simple to understand; it works well, it doesn't create new objects once initialized, and it doesn't really need locking, except the Queue.Dequeue operation should wait for a buffer being returned. In pseudo-code:

                // init
                emptyQ=CreateQueue();
                fullQ=CreateQueue();
                for(N times) emptyQ.Queue(new Buffer());

                // producer
                forever {
                buf=emptyQ.Dequeue(); // blocking
                ...fill buf
                fullQ.Queue(buf);
                }

                // consumer
                forever {
                buf=fullQ.Dequeue(); // blocking
                ... process buf
                emptyQ.Queue(buf);
                }

                :)

                Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum

                Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.

                A Offline
                A Offline
                Anthony Mushrow
                wrote on last edited by
                #8

                Good call, I might be able to fit that in. With the change that the consumer won't release a buffer until it has new one to render so it would be holding 2 buffers at times, so the minimum number of required buffers becomes 3.

                My current favourite phrase: I've seen better!

                -SK Genius

                Source Indexing and Symbol Servers

                1 Reply Last reply
                0
                • A Alan Balkany

                  It's surprisingly complex for such a short fragment because of the possible interactions between threads, and the shuffling of values among four variables. Maybe it could be rewritten in a simpler way. A useful step in analyzing code like this is identifying invariant conditions, that are guaranteed to always be true at some point in the code. But it looks like the variable shuffling makes this impossible.

                  A Offline
                  A Offline
                  Anthony Mushrow
                  wrote on last edited by
                  #9

                  Yeah, I've temporarily gone with a lock which solves the problem for now. Then I'm going to try Luc's suggestion of using a couple of queues. I already have a lock-free queue that's working elsewhere which I should be able to use, since there would only be one producer for each queue (a limitation for lock-free queues it would seem).

                  My current favourite phrase: I've seen better!

                  -SK Genius

                  Source Indexing and Symbol Servers

                  L J 2 Replies Last reply
                  0
                  • A Anthony Mushrow

                    Yeah, I've temporarily gone with a lock which solves the problem for now. Then I'm going to try Luc's suggestion of using a couple of queues. I already have a lock-free queue that's working elsewhere which I should be able to use, since there would only be one producer for each queue (a limitation for lock-free queues it would seem).

                    My current favourite phrase: I've seen better!

                    -SK Genius

                    Source Indexing and Symbol Servers

                    L Offline
                    L Offline
                    Luc Pattyn
                    wrote on last edited by
                    #10

                    SK Genius wrote:

                    there would only be one producer ... a limitation for lock-free queues it would seem

                    a limitation for lock-free whatevers I would say. :-D

                    Luc Pattyn [Forum Guidelines] [My Articles] Nil Volentibus Arduum

                    Please use <PRE> tags for code snippets, they preserve indentation, improve readability, and make me actually look at the code.

                    1 Reply Last reply
                    0
                    • A Anthony Mushrow

                      Yeah, I've temporarily gone with a lock which solves the problem for now. Then I'm going to try Luc's suggestion of using a couple of queues. I already have a lock-free queue that's working elsewhere which I should be able to use, since there would only be one producer for each queue (a limitation for lock-free queues it would seem).

                      My current favourite phrase: I've seen better!

                      -SK Genius

                      Source Indexing and Symbol Servers

                      J Offline
                      J Offline
                      JesperMadsen123
                      wrote on last edited by
                      #11

                      I am sure you can find a solution for adding more producers, if you are good at lock-free algorithms. This page suggest that it is not impossible. http://www.1024cores.net/home/lock-free-algorithms/queues

                      1 Reply Last reply
                      0
                      Reply
                      • Reply as topic
                      Log in to reply
                      • Oldest to Newest
                      • Newest to Oldest
                      • Most Votes


                      • Login

                      • Don't have an account? Register

                      • Login or register to search.
                      • First post
                        Last post
                      0
                      • Categories
                      • Recent
                      • Tags
                      • Popular
                      • World
                      • Users
                      • Groups