Multhithreading> Circular buffer

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • thiago777
    New Member
    • May 2007
    • 89

    #1

    Multhithreading> Circular buffer

    I have four methods(threads ) in my application that must work syncronized sharing an 8 element circular buffer array. Each method should work in the data only after its previous thread had completed its task, in the following order:

    1st.: Reads data from file and place in one free element of the array;
    2nd.:Read data produced by thread 1, change and save;
    3rd.: Read data produced by thread 2, change and save;
    4th.: Get processed data from 3rd thread, write to disk and free element of the array so that thread 1 can now write there again.

    Is it possible that all threads access and manipulate the data concurrently without causing monitor overhead?

    What is the best way to achieve this so that they all could work together but in the correct order / syncronized? any tips/examples?

    thank you.
  • TRScheel
    Recognized Expert Contributor
    • Apr 2007
    • 638

    #2
    I dont think multithreading in that fashion is the correct way to go about it if they must do something synchronized. I would instead do something like:

    Thread 1 - Works on index 1 of array, does step 1 - 4 itself
    Thread 2 - Works on index 2 of array, does step 1 - 4 itself
    Thread n - Works on index n of array, does step 1 - 4 itself

    Then watch to make sure you dont get a million threads started.

    Comment

    • Plater
      Recognized Expert Expert
      • Apr 2007
      • 7872

      #3
      If the next thread shouldn't be doing anything until it's previous thread is completed.....w hy are you using threads at all?
      Seems kinda silly if you have to have the thread wait to begin with.

      Comment

      • TRScheel
        Recognized Expert Contributor
        • Apr 2007
        • 638

        #4
        Originally posted by Plater
        If the next thread shouldn't be doing anything until it's previous thread is completed.....w hy are you using threads at all?
        Seems kinda silly if you have to have the thread wait to begin with.
        Ya that was my point

        Comment

        • thiago777
          New Member
          • May 2007
          • 89

          #5
          **Sorry for the big post!**

          I think if I explain the situation maybe it will be more clear for you.

          In my single-threaded application these are the tasks to be performed:

          1. Read data from a file and store it in memory (eg. buffer)
          2. Process all data read
          3. Save data processed and start all over again.

          I make the steps above in a loop because I would'nt be able to allocate so much memory since its not possible to guess the size of the file and how much RAM is available on the computer.

          Considering I make loops of 256MB for example, take a look at the problem:

          1. Program is reading data from file (let us call it IO) and storing in RAM (the program's buffer) - Processor is idle;
          2. Program is processing data read - now IO (which is slow -normally a HD) is idle;
          3. Program is saving processed data back to file (IO) - Processor is idle again.

          and this is repeated until the whole file is processed. Now that you can see what I want to achieve (get the most of the processing power of the hardware at full-time), let me show why Im trying the multithreading the way I said in the first post:

          This is an example code from my book of using Circular Buffers (it should be easy to understand if your familiar with threads) :

          The Interface IBuffer:

          Code:
          'IBuffer.vb
          Public Interface IBuffer
                Property Buffer() as Integer 'Property to access the buffer
          End Interface 'IBuffer
          The main controller:

          Code:
          ' A circular shared buffer for the producer/consumer relationship.
          Imports System.Threading
          
          ' implement the an array of shared integers with synchronization
          Public Class CircularBuffer
             Implements IBuffer
             ' each array element is a buffer
             Private buffers As Integer() = {-1, -1, -1}
          
             ' occupiedBufferCount maintains count of occupied buffers
             Private occupiedBufferCount As Integer = 0
          
             ' variable that maintain read and write buffer locations
             Private readLocation As Integer = 0
             Private writeLocation As Integer = 0
          
             ' property Buffer
             Public Property Buffer() As Integer Implements IBuffer.Buffer
                Get
                   ' lock this object while getting value from buffers array
                   SyncLock (Me)
                      ' if there is no data to read, place invoking thread
                      ' in WaitSleepJoin state
                      If occupiedBufferCount = 0 Then
                         Console.Write(vbCrLf & "All buffers empty. " & _
                            Thread.CurrentThread.Name & " waits.")
                         Monitor.Wait(Me) ' enter the WaitSleepJoin state
                      End If
          
                      ' obtain value at current readLocation
                      Dim readValue As Integer = buffers(readLocation)
          
                      Console.Write(vbCrLf & Thread.CurrentThread.Name & _
                          " reads " & buffers(readLocation) & " ")
          
                      ' just consumed a value, so decrement
                      ' number of occupied buffers
                      occupiedBufferCount -= 1
          
                      ' update readLocation for future read operation, then
                      ' add current state to output
                      readLocation = (readLocation + 1) Mod buffers.Length
                      CreateStateOutput()
          
                      ' return waiting thread (if there is one) to Running state
                      Monitor.Pulse(Me)
          
                      Return readValue
                   End SyncLock
                End Get
                Set(ByVal value As Integer)
                   ' lock this object while setting value in buffers array
                   SyncLock (Me)
                      ' if there are no empty locations, place invoking thread
                      ' in WaitSleepJoin state
                      If occupiedBufferCount = buffers.Length Then
                         Console.Write(vbCrLf & "All buffers full. " & _
                            Thread.CurrentThread.Name & " waits.")
                         Monitor.Wait(Me) ' enter the WaitSleepJoin state
                      End If
          
                      ' place value in writeLocation of buffers
                      buffers(writeLocation) = value
          
                      Console.Write(vbCrLf & Thread.CurrentThread.Name & _
                         " writes " & buffers(writeLocation) & " ")
          
                      ' just produced a value, so increment
                      ' number of occupied buffers
                      occupiedBufferCount += 1
          
                      ' update writeLocation for future write operation,
                      ' then add current state to output
                      writeLocation = (writeLocation + 1) Mod buffers.Length
                      CreateStateOutput()
          
                      ' return waiting thread (if there is one) to Running state
                      Monitor.Pulse(Me)
                   End SyncLock
                End Set
             End Property ' Buffer
          
             ' create state output
             Public Sub CreateStateOutput()
                ' display first line of state information
                Console.Write("(buffers occupied: " & _
                   occupiedBufferCount & ")" & vbCrLf & "buffers: ")
          
                For i As Integer = 0 To (buffers.Length - 1)
                   Console.Write(" " & String.Format("{0,2}", buffers(i)) & "  ")
                Next (i)
          
                Console.WriteLine()
          
                ' display second line of state information
                Console.Write("         ")
          
                For i As Integer = 0 To (buffers.Length - 1)
                   Console.Write("---- ")
                Next (i)
          
                Console.WriteLine()
          
                ' display third line of state information
                Console.Write("         ")
          
                ' display readLocation (R) and writeLocation (W) indicators
                ' below appropriate buffer locations
                For i As Integer = 0 To (buffers.Length - 1)
                   If i = writeLocation And writeLocation = readLocation Then
                      Console.Write(" WR  ")
                   ElseIf i = writeLocation Then
                      Console.Write(" W   ")
                   ElseIf i = readLocation Then
                      Console.Write("  R  ")
                   Else
                      Console.Write("     ")
                   End If
                Next (i)
          
                Console.WriteLine()
             End Sub ' CreateStateOutput
          End Class ' CircularBuffer
          Here is the consumer class:

          Code:
          ' Fig. 15.6: Consumer.vb
          ' Consumer consumes ten integer values from the shared buffer.
          Imports System.Threading
          
          ' class Consumer's Consume method controls a thread that
          ' loops ten times and reads a value from sharedLocation
          Public Class Consumer
             Private sharedLocation As IBuffer
             Private randomSleepTime As Random
          
             ' constructor
             Public Sub New(ByVal sharedBuffer As IBuffer, ByVal random As Random)
                sharedLocation = sharedBuffer
                randomSleepTime = random
             End Sub ' New
          
             ' read sharedLocation's value ten times
             Public Sub Consume()
                Dim sum As Integer = 0
          
                ' sleep for random interval upto 3000 milliseconds then
                ' add sharedLocation's Buffer property value to sum
                For count As Integer = 1 To 10
                   Thread.Sleep(randomSleepTime.Next(1, 3001))
                   sum += sharedLocation.Buffer ' consume
                Next count
          
                Console.WriteLine(Thread.CurrentThread.Name & _
                   " read values totaling: " & sum & "." & vbCrLf & _
                   "Terminating " & Thread.CurrentThread.Name & ".")
             End Sub ' Consume
          End Class ' Consumer
          The producer:

          Code:
          ' Fig. 15.5: Producer.vb
          ' Producer produces ten integer values in the shared buffer.
          Imports System.Threading
          
          ' class Producer's Produce method controls a thread that
          ' stores values from 1 to 10 in sharedLocation
          Public Class Producer
             Private sharedLocation As IBuffer
             Private randomSleepTime As Random
          
             ' constructor
             Public Sub New(ByVal sharedBuffer As IBuffer, ByVal random As Random)
                sharedLocation = sharedBuffer
                randomSleepTime = random
             End Sub ' New
          
             ' store values 1-10 in object sharedLocation
             Public Sub Produce()
                ' sleep for random interval upto 3000 milliseconds
                ' then set sharedLocation's Buffer property
                For count As Integer = 1 To 10
                   Thread.Sleep(randomSleepTime.Next(1, 3001))
                   sharedLocation.Buffer = count
                Next count
          
                Console.WriteLine(Thread.CurrentThread.Name & " done producing." & _
                   vbCrLf & "Terminating " & Thread.CurrentThread.Name & ".")
             End Sub ' Produce
          End Class ' Producer
          And finally, he starts the threads:

          Code:
          ' Fig. 15.10: SynchronizedBufferTest.vb
          ' Showing multiple threads modifying a shared object with synchronization.
          Imports System.Threading
          
          ' this module creates producer and consumer threads
          Module SynchronizedBufferTest
             ' create producer and consumer threads and start them
             Sub Main()
                ' create shared object used by threads
                Dim sharedBuffer As New SynchronizedBuffer
          
                ' Random object used by each thread
                Dim random As New Random
          
                ' output column heads and initial buffer state
                Console.WriteLine("{0,-35}{1,-9}{2}" & vbCrLf, _
                   "Operation", "Buffer", "Occupied Count")
                sharedBuffer.DisplayState("Initial state")
          
                ' create Producer and Consumer objects
                Dim producer As New Producer(sharedBuffer, random)
                Dim consumer As New Consumer(sharedBuffer, random)
          
                ' create threads for producer and consumer and set
                ' delegates for each thread
                Dim producerThread As New Thread(New ThreadStart( _
                   AddressOf producer.Produce))
                producerThread.Name = "Producer"
          
                Dim consumerThread As New Thread(New ThreadStart( _
                   AddressOf consumer.Consume))
                consumerThread.Name = "Consumer"
          
                ' start each thread
                producerThread.Start()
                consumerThread.Start()
             End Sub ' Main
          End Module ' SynchronizedBufferTest
          The problem with the code above is that its for only one producer and one consumer. But in the case of this application I mention, as you might have noticed, there is one thread that works in the first step as a "consumer", reading the data and then "producing" saving data back to buffer, before it can be sent to the next thread which will read it (consume) and save to file; Therefore its a "consumer" and "producer" at the same time.

          What I have made so far is create more variables to take control of them, but the code is getting kind of messy and hard to debug.

          But, if I make it this way:

          Thread 1 - Works on index 1 of array, does step 1 - 4 itself
          Thread 2 - Works on index 2 of array, does step 1 - 4 itself
          Thread n - Works on index n of array, does step 1 - 4 itself
          then the circular buffer idea ( that is to have memory available until the other thread is not done its job, so that it is not waiting ) , I believe, is gone.

          From the book (due the fact that you cant know how and when a thread will execute):

          Even when using a circular buffer, its possible that a producer thread could fill the (whole) buffer. This would force the producer thread to wait until a consumer consumes a value to free an element in the buffer. Similarly, if the buffer is empty, the consumer thread must wait until the producer produces another value. The key to using a circular buffer is to optimize the buffer size to minimize the amount of thread wait time.
          that should answer this question:

          If the next thread shouldn't be doing anything until it's previous thread is completed.....w hy are you using threads at all?
          again, because I'm trying to implement circular buffers so that threads don't have to wait.

          Hope this cleared things up. I need a good way to control all the threads in a synchronized way. Ideas/suggestions?

          Comment

          • Plater
            Recognized Expert Expert
            • Apr 2007
            • 7872

            #6
            So you want a FIFO-y thing?
            You want the HD to keep building up a buffer for you to process on and then be writing it back?
            That makes more sense now. But, alas, I've never been very good with that.

            Comment

            • thiago777
              New Member
              • May 2007
              • 89

              #7
              Originally posted by Plater
              So you want a FIFO-y thing?
              You want the HD to keep building up a buffer for you to process on and then be writing it back?
              That makes more sense now. But, alas, I've never been very good with that.
              The file could be anywhere (like HD, flash-memory,etc) with write access. The buffer is on the RAM (its my working variable).

              Comment

              • Plater
                Recognized Expert Expert
                • Apr 2007
                • 7872

                #8
                So I was thinking. You might be able to do this with two linked lists that can be accessed between multiple threads (you will have to handle the thread-safing on your own I think)

                Have you reading thread (the one that reads from hd/cd/flashdisk/whatever) continuously reading and pushing chunks of data onto the end of LinkListA.

                Have your processins thread start at the start of LinkListA, popfront (or whatever they call it) and process the chunks of data, putting them at the end of LinkListB.

                Then your writer thread will be reading from the start of LinkedListB and writing back to your media (harddrive/whatver)

                Reader -> <ListA> -> Processor -> <ListB> -> Writer


                So reader pushes data onto end of ListA and processor pulls data off from the begining of ListA and pushes it onto the end of ListB where Writer pulls data off from the begining.

                Comment

                • thiago777
                  New Member
                  • May 2007
                  • 89

                  #9
                  Hum.. sounds to be a good idea. What you suppose is, as far as I understood, to make one buffer for each processing step, correct?
                  do you think this way making the process thread-safe will be easier?

                  Comment

                  • Plater
                    Recognized Expert Expert
                    • Apr 2007
                    • 7872

                    #10
                    Originally posted by thiago777
                    do you think this way making the process thread-safe will be easier?
                    Don't know, I am only theorizing.

                    Comment

                    Working...