Programming Forums

Programming Forums (http://www.programmingforums.org/forumindex.php)
-   C (http://www.programmingforums.org/forum60.html)
-   -   Implement a queue using share memory? (http://www.programmingforums.org/showthread.php?t=15845)

secrecy230 May 19th, 2008 10:22 AM
Implement a queue using share memory?
 
I know how to build a queue in C.
However,what does it mean to "Implement a queue using shared memory?"
How to do it? and can someone provide me a start please?

thanks in advance!

Jessehk May 19th, 2008 12:27 PM
Re: Implement a queue using share memory?
 
I'm not entirely sure, but it might mean that instead of allocating memory on the heap for every node in the queue, that you instead allocate a "pool" of memory for the whole structure and assign memory from there.

For example, if you were writing a linked-list (can you implement a queue with a linked-list? I don't know too much about computer science-y stuff ;)) you might be able to do something like this:

:
  1. typedef struct lnode {
  2.     void *data;
  3.     struct lnode *next;
  4.  
  5.     int used_;
  6. } lnode;
  7.  
  8. #define LIST_MAX 5000
  9.  
  10. static lnode sharedmem[LIST_MAX];
  11.  
  12. static lnode *allocator( void ) {
  13.     int i;
  14.  
  15.     for ( i = 0; i < LIST_MAX; i++ ) {
  16.         if ( ! sharedmem[i].used_ ) {
  17.             sharedmem[i].used_ = 1;
  18.             return &(sharedmem[i]);
  19.         }
  20.     }
  21.  
  22.     return NULL;
  23. }
  24.  
  25. static lnode *make_lnode( void *data, lnode *next ) {
  26.     lnode *n = allocator();
  27.  
  28.     n->data = data;
  29.     n->next = next;
  30.  
  31.     return n;
  32. }

Alternatively, you could malloc() a block of memory within the structure of the ADT and keep a memory index.

EDIT: on second thought, look near the bottom of this page.

mbd May 19th, 2008 2:50 PM
Re: Implement a queue using share memory?
 
you need to google for "producer consumer problem" or "bounded buffer". you should find what you are looking for.

Fall Back Son May 21st, 2008 3:58 AM
Re: Implement a queue using share memory?
 
I think you were joking but you can implement a queue a variety of ways lol.

mbd May 21st, 2008 10:34 AM
Re: Implement a queue using share memory?
 
if you think i am joking, then you are mistaken. obviously you can implement a queue in many ways. however if you are using memory shared between threads, you must provide protection for that shared resource. this is a classic comp sci problem which is probably what he is currently studying.

Fall Back Son May 21st, 2008 12:50 PM
Re: Implement a queue using share memory?
 
No, I was talking to Jessehk or whatever his name is. I realize what the problem entails. I also don't understand why anyone would want you to do this in C, and I'm interested to know what kind of practical applications (In C) might use this.

mbd May 22nd, 2008 12:24 PM
Re: Implement a queue using share memory?
 
fall back son, what language would you want to do this in?

Sane May 22nd, 2008 4:27 PM
Re: Implement a queue using share memory?
 
Of course you'd want to use C!

C is the language for implementing queues and/or linked lists, since it's basically the only commonly used language that doesn't already support lists or queues.

Let's look at TIOBE's list of the most popular programming languages as of May 2008.

Source: http://www.tiobe.com/index.php/conte...pci/index.html
:
1  Java            (Built-in support for queues)
2  C
3  Visual Basic    (Would not use this language)
4  PHP            (Would not use this language)
5  C++            (Built-in support for queues)
6  Perl            (Built-in support for queues)
7  Python          (Built-in support for queues)

Sure you could make your own queue in Java. But it's always more effective to demonstrate something in a language that does not have support for it.

That leaves C.

So as mbd asked, what language would you use?

Jessehk May 22nd, 2008 9:22 PM
Re: Implement a queue using share memory?
 
Quote:
Originally Posted by Fall Back Son (Post 145426)
No, I was talking to Jessehk or whatever his name is.
In the time you wrote that sentence, you could have scrolled up three posts and checked for yourself. Congratulations.

Game_Ender May 25th, 2008 2:03 AM
Re: Implement a queue using share memory?
 
I think everyone missed the mark here. "shared memory"most commonly means memory shared between processes, not threads. In this case a queue with shared memory could be used to create an interprocess message passing system. You still need to use some kind of semaphore or mutex mapped into shared memory in order to synchronize access to the queue between multiple processes.

You should first learn how to implement a queue, then learn the API for shared memory on your particular OS. Jessehk's code should be able to help you with some of it.


All times are GMT -5. The time now is 4:08 AM.

Powered by vBulletin® Version 3.7.0, Copyright ©2000 - 2008, Jelsoft Enterprises Ltd.
Copyright ©2007 DaniWeb® LLC