implement a queue as shared memory

I am trying to figure out how to implement a queue using shared memory.
I want to do this so 2 threads can access this queue, but with mutual
exclusion.

say I wanted a queue of max size 5 integers

int seg_id = shmget(IPC_PRIVATE, 20480, S_IRUSR | S_WRUSR);  //this
gets my shared memory

but how do I make this shared memory a queue? could I do this:

queue<int> *shared_queue;

shared_queue = (int *) shmat(seg_id, NULL, 0);

would this work? would this allow me to still use the common queue
functions like pop, push, front?

am I way off on this?

Leshanster

<leshanster@gmail.com> wrote in message
news:1113507714.525015.246700@o13g2000cwo.googlegroups.com...

>I am trying to figure out how to implement a queue using shared memory.
> I want to do this so 2 threads can access this queue, but with mutual
> exclusion.

If you mean 2 threads in the same process, they already share all their
memory.

> say I wanted a queue of max size 5 integers
>
> int seg_id = shmget(IPC_PRIVATE, 20480, S_IRUSR | S_WRUSR);  //this
> gets my shared memory
>
> but how do I make this shared memory a queue? could I do this:
>
> queue<int> *shared_queue;
>
> shared_queue = (int *) shmat(seg_id, NULL, 0);
>
> would this work? would this allow me to still use the common queue
> functions like pop, push, front?
>
> am I way off on this?

That certainly won't work. If you want to implement a queue that can be
shared by different processes, you'll have to code it along with the
necessary synchronization. If you want to implement a queue that can be
shared by threads in a process, you can just use the queue class, but you'll
need to wrap it in appropriate locks (pthread_mutex_* functions).

DS

what I am trying to do (first with threads which isn't going to work,
so I am going to have to throw away that idea), is I want to have 2
processes access shared memory.  But I want the shared memory to be a
FIFO queue of size 5.

//this would get the space needed for 5 integers
int seg_id = shmget(IPC_PRIVATE, 20480, S_IRUSR | S_WRUSR);

^ but with that, how do I turn that memory space into a queue?

"leshanster" <leshanster@gmail.com> wrote in message
news:1113511372.710173.163330@o13g2000cwo.googlegroups.com...
> what I am trying to do (first with threads which isn't going to work,
> so I am going to have to throw away that idea), is I want to have 2
> processes access shared memory.  But I want the shared memory to be a
> FIFO queue of size 5.
>
> //this would get the space needed for 5 integers
> int seg_id = shmget(IPC_PRIVATE, 20480, S_IRUSR | S_WRUSR);
>
> ^ but with that, how do I turn that memory space into a queue?

You have to write a queue class that understands shared memory and
synchronization. What do you plan to use for synchronization? Semaphores?

By the way, it's *much* easier with threads.

DS

> I want to have 2
> processes access shared memory.  But I want the shared memory to be a
> FIFO queue of size 5.

You could alternatively use a pipe (man pipe) or inter-process message
queue (man msgget, msgsend).

Using shared memory, the shared region may exist at different addresses
in the different processes.  So you can't use pointers.  This almost
certainly means that you can't use the C++ STL queue classes, or
probably any C++.  Stick to a simple struct like this:

typedef struct {
int in_pos;
int out_pos;
base_type data[5];
} queue;

Declare this as volatile.

Next you need to worry about locking.  In the case of a fifo, I think
that it is sufficient to use atomic assignment when changing in_pos and
out_pos.  The GNU libc documentation says:

In practice, you can assume that `int' and other integer types no
longer than `int' are atomic.  You can also assume that pointer types
are atomic; that is very convenient.  Both of these assumptions are
true on all of the machines that the GNU C library supports and on
all
POSIX systems we know of.

If you don't believe them, or need a more complex data structure, a
more heavyweight lock would be needed.

Then write push(), pop(), full(), empty() etc. in the obvious way.

--Phil.

leshanster wrote:
> what I am trying to do (first with threads which isn't going to work,
> so I am going to have to throw away that idea), is I want to have 2
> processes access shared memory.  But I want the shared memory to be a
> FIFO queue of size 5.

you can still use thread, in this way you will not have to use a shared
memory, you can directly use a global variable to implement queue(using
linked list), take care that you use "mutex" to avoid race conditions.
>
> //this would get the space needed for 5 integers
> int seg_id = shmget(IPC_PRIVATE, 20480, S_IRUSR | S_WRUSR);
>
> ^ but with that, how do I turn that memory space into a queue?

Is there a way then I could just the shared memory as an integer array?

Something like:

int* front;

front = tshmat(shmid, 0, 0);

then could I just use

front[0] = 3;

Would this work?

"leshanster" <leshanster@gmail.com> writes:

> Is there a way then I could just the shared memory as an integer array?
>
> Something like:
>
> int* front;
>
> front = tshmat(shmid, 0, 0);
>
> then could I just use
>
> front[0] = 3;
>
> Would this work?

You've not been reading what David and Darius have written, have you?


You must distinguish threads and processes.

Threads in a process use all the same memory. If you only have threads
in one process, you don't need shared memory.  A simple global
variable will do.


If you have several processes, each process has its own memory, then
you need shared memory to communicate between these processes.


In both cases, while you'll be able to read and write the memory, your
file abstract data type won't work if you don't synchronize accesses.

Let's take the case of threads, with the following queue:

#define qsize (5)
typedef struct {
int head;
int length;
int data[qsize];
} queue_t;

void queue_init(queue_t* q){
q->head=0;
q->length=0; }

void enqueue(queue_t* q,int value){
if(q->length<qsize){
q->data[(q->head+q->length)%qsize]=value;
q->length++; }
else{
error("queue is full"); }}

int dequeue(queue_t* q){
if(q->length==0){
error("queue is empty"); }
else{
int result=q->data[q->head];
q->head++;
q->length--;
return(result); }}

queue_t* q=shmat(id,0,0);

Now, imagine q->head==0 and q->length==0, and thread 1 runs:

enqueue(q,1);

that is, it executes:

if(q->length<qsize){

and:

q->data[(q->head+q->length)%qsize]=value;

Now, q->head=0, q->length=0, and q->data[0]=1

Imagine now the OS decides to switch to thread 2, and thread 2 runs:

enqueue(q,2);

that is, it executes:

if(q->length<qsize){

and:

q->data[(q->head+q->length)%qsize]=value;
q->length++; }

Now, q->head=0, q->length=1, q->data[0]=2. If thread 2 continues with:

int v=dequeue(q);

it gets v=2 instead of v=1, and q->head=1, q->length=0

If now the OS decides to give back the processor to thread 1, it resumes:

q->length++; }

and now q->head=1, q->length=1 and q->data[1]= whatever garbage there
was there.  and if thread 1 continues with:

int w=dequeue(q);

it gets w=garbage instead of v=2, and q->head=2, q->length=0;




When we say that you need to consider synchronisation, it means that
you must ensure that when you start an enqueue or a dequeue operation,
not matter what arrives, no other thread (or processes) will be able
to modify the same queue until the enqueue or dequeue operation is
finished.  Access to these operations must be mutually exclusive, that
is, no two threads (or processes) must be able yo access these
operations at the same time.  Hence the need to use mutex in the case
of threads, or semaphores in the case of processes.


So, go read:

man pthread_mutex_init
man pthread_mutex_lock
man pthread_mutex_unlock
man semget
man semop

and come back after.

--

__Pascal Bourguignon__                     http://www.informatimago.com/

> Let's take the case of threads,

Leshanster's question is about processes using shared memory, not
threads.

> when you start an enqueue or a dequeue operation,
> not matter what arrives, no other thread (or processes) will be able
> to modify the same queue until the enqueue or dequeue operation is
> finished.

Why not?  If I have a queue that contains "A B C D", and I am in the
process of removing "A" from the front, why shouldn't another thread
simultaneously be adding "E" to the end?  Storing input and output
positions, rather than head and length as you suggest, makes this
possible.

--Phil.

>> when you start an enqueue or a dequeue operation, 
> Why not?  If I have a queue that contains "A B C D", and I am in the
> process of removing "A" from the front, why shouldn't another thread
> simultaneously be adding "E" to the end?

I should of course say that locking is necessary when there is more
than one process or thread trying to write to the queue and/or more
than one trying to read.  The common case is where exactly one process
is reading and exactly one is writing; it is in this case that locking
can be reduced to atomic operations on the position counters.  Sorry
for pressing "post" too quickly.

--Phil.