Solved

Single writer , multiple reader in Real Time code

Posted on 2009-05-03
10
1,625 Views
Last Modified: 2013-11-25
Dear experts,

In real time programming, it is common that we need to have concurrency procedure that enable only 1 single writer OR multiple concurrent reader to one shared variable / memory at one time.
Is there anyone can share common high level design (in terms of how to handle the concurrency , locking, queuing) for this (not specific to any language)? Or any references?

Thanks so much.
0
Comment
Question by:isuhendro
  • 3
  • 3
  • 2
  • +2
10 Comments
 
LVL 86

Expert Comment

by:CEHJ
ID: 24290279
There are high level concepts such as mutexes, locking, semaphores etc but in java, look at the java.util.concurrent package classes
0
 
LVL 40

Assisted Solution

by:evilrix
evilrix earned 50 total points
ID: 24290473
I don't know if it helps but I wrote the code example below for another question but it does exhibit the qualities you discuss. It is an example of (a simple) solution to a producer/consumer pattern. The producer (the main thread and single writer) writes requests to a queue (your shared variable) and the threads in the thread pool (the multiple readers) read and process the requests. The code using mutual exclusion (mutex) to ensure the variable is only being access/modified by one thread at a time. A single event is used to signal the thread pool to dispatch a thread to process a newly queue request. Additionally, another even is used to signal the thread pool to terminate.

Since the code exhibits the requirements you discussed I figured I'd post it so you could take a look and see how there constructs have been used to help implement this solution. The same principles can, obviously, been applied to your more specific requirement.

I hope this helps.
include <windows.h>

#include <process.h>

 

#include <deque>

#include <vector>

#include <string>

#include <iostream>

#include <sstream>

 

// Typedefs just to aid readability

typedef std::deque<std::string> string_queue_t;

typedef std::vector<HANDLE> handle_vector_t;

 

// Thread data

struct thread_data

{

        string_queue_t string_queue;

        HANDLE mtx;

        HANDLE evts[2]; // 0 Quit, 1 Process

};

 

// A thread

void thread_proc(void * pv)

{

        // If we have no thread data terminate

        if(0 == pv) return;

 

        // Get the thread data

        thread_data & td = *reinterpret_cast<thread_data *>(pv);

 

        bool bQuit = 0;

        while(!bQuit)

        {

                // Wait for either a job or signal to quit

                DWORD result = WaitForMultipleObjects(2, td.evts, false, INFINITE);

 

                // Get exclusive access to the queue

                WaitForSingleObject(td.mtx, INFINITE);

 

                // Take a copy of the job in the queue

                // NB. working with a copy means we can free up access to the queue immediately

                std::string s;

                if(td.string_queue.size() > 0)

                {

                        s = td.string_queue.front();

                        td.string_queue.pop_front();

                }

                else

                {

                        // The queue is empty so if we were signaled to quit then we can do so now

                        bQuit = ((result - WAIT_OBJECT_0) == 0);

                }

 

                // Release exclusinve lock on queue

                ReleaseMutex(td.mtx);

 

                // Process what we got out of the queue

                // NB. Since this is a copy the queue has been released from exclusive access

                if(!s.empty())

                {

                        // This output is thread safe but may end up mixing with other threads

                        // that's ok it's just for example purposes.

                        std::cout << "tid: " << GetCurrentThreadId() << " - " << s << std::endl;

                }

        }

}

 

 

int main()

{

        // Create out cross-thread object

        thread_data td;

 

        // Mutex to sync access to the queue

        td.mtx = CreateMutex(0, false, 0);

 

        // Event used to signal threads to terminate

        td.evts[0] = CreateEvent(0, true, false, 0);

 

        // Event used to signal the thread pool a job is ready

        td.evts[1] = CreateEvent(0, false, false, 0);

 

        // A vector that will represent the thread pool

        handle_vector_t handle_vector;

 

        // Create thread pool

        for(int i = 0 ; i < 10 ; ++i)

        {

                HANDLE handle = reinterpret_cast<HANDLE>(_beginthread(thread_proc, 0, &td));

                if(handle > 0)

                {

                        handle_vector.push_back(handle);

                }

        }

 

        // Queue jobs for processing by thread pool

        for(int j = 0 ; j < 9999 ; ++j)

        {

                std::stringstream ss;

                ss << "data " << j;

 

                // Add to queue

                WaitForSingleObject(td.mtx, INFINITE);

                td.string_queue.push_back(ss.str());

                ReleaseMutex(td.mtx);

 

                // Signal the thread pool

                SetEvent(td.evts[1]);

        }

 

        // Signal threads to terminate when there are no more jobs

        SetEvent(td.evts[0]);

 

        // wait for threads to terminate

        WaitForMultipleObjects(3, &handle_vector[0], true, INFINITE);

}

Open in new window

0
 

Author Comment

by:isuhendro
ID: 24292399
hi CEHJ, thanks for your advice.

However, I need specific information about multiple read & single writer. Let's say i have 3 threads of reader, and 1 thread of writer, I would like that whenever writer in action then no other thread would be able to perform. But whenever one reader in action, it could be that all of them (3 reader) do the reading at the same time.

Hi evilrixD, thank you for sharing the code.

If I don't understand wrongly your code is producer and consumer scenario.. however i could not see the fact that producer is prohibit to produce message when consumer is reading, or consumer is allowed to consume message whenever other consumer is in action.

I think the code required would need a conditioned variable to signify the current mode is R/W. However i am still confused the fact that we need to have multiple reader, against the fact that R/W cannot be run together.

Thanks..
0
 
LVL 92

Accepted Solution

by:
objects earned 75 total points
ID: 24292463
0
 
LVL 92

Expert Comment

by:objects
ID: 24292472
0
How your wiki can always stay up-to-date

Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
- Increase transparency
- Onboard new hires faster
- Access from mobile/offline

 

Author Comment

by:isuhendro
ID: 24292691
hi Objects, thanks for the good out of the box answer.

i just found from the web a good and sounds of working algorithm here ,
the key is reader will only try to acquire "lock" if and only if it is the "first" active reader. the rest of the reader can do "reading" activity without any "lock"

http://www-cse.ucsd.edu/classes/fa02/cse120/lectures/sema.pdf
// number of readers

int readcount = 0;

// mutual exclusion to readcount

Semaphore mutex = 1;

// exclusive writer or reading

Semaphore w_or_r = 1;
 

writer {

  wait(w_or_r); // lock out readers

  Write;

  signal(w_or_r); // up for grabs

}
 

reader {

  wait(mutex); // lock readcount

  readcount += 1; // one more reader

  if (readcount == 1)

    wait(w_or_r); // synch w/ writers

  signal(mutex); // unlock readcount

  Read;

  wait(mutex); // lock readcount

  readcount -= 1; // one less reader

  if (readcount == 0)

    signal(w_or_r); // up for grabs

  signal(mutex); // unlock readcount}

}

Open in new window

0
 
LVL 92

Expert Comment

by:objects
ID: 24292697
0
 
LVL 40

Expert Comment

by:evilrix
ID: 24293400
>> i could not see the fact that producer is prohibit to produce message when consumer is reading, or consumer is allowed to consume message whenever other consumer is in action.

Protection is provided via the mutex. See both the producer and consumer try to take ownership of the mutex (lines 38 and 103). Only one thread will gain ownership and the other will block until ownership is released by the other thread. This is a typical mechanism used to provide mutual exclusion semantics. You would avoid using a variable for a number of reasons...

1. Unless the variable is volatile changes in one thread may not be apparent in the others (due to CPU caching and compiler optimization)

2. Unless the variable type can be read/written/tested in one instruction you have the strong possibility of a race condition.

3. Even if you could fulfil the requires of 2 you'd have to "busy wait" (ie. keep spinning in code until your thread could move on), where as a Mutex (being a kernal object) uses up no CPU time whilst blocking.

http://en.wikipedia.org/wiki/Mutual_exclusion
http://en.wikipedia.org/wiki/Race_condition
http://en.wikipedia.org/wiki/Busy_waiting

>> However i am still confused the fact that we need to have multiple reader, against the fact that R/W cannot be run together.
The idea is it takes a fraction of the time to add to the queue than it does to process jobs in the queue. So, if might take 10ms to add a new job and dispatch a thread but then that thread might spend 20 seconds processing the job. Meanwhile, the producing can keep adding jobs and dispatching new threads until all the threads in the pool are busy, at which point the jobs will just stake queued until a thread is free to process it. Of course, if you only want one thread in your thread pool then you can just set up the main process to only create a thread pool of 1 thread.

0
 

Author Closing Comment

by:isuhendro
ID: 31577341
Thanks!
0
 

Expert Comment

by:RufusVS
ID: 24379625
0

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
countHi challenge 25 86
java set up 1 48
for i loop in grovy 1 34
eclipse compiler vs Installed JREs option 3 42
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
In this post we will learn how to connect and configure Android Device (Smartphone etc.) with Android Studio. After that we will run a simple Hello World Program.
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

743 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

Need Help in Real-Time?

Connect with top rated Experts

10 Experts available now in Live!

Get 1:1 Help Now