Programming Forums > Application Development > C

secrecy230 · May 19th, 2008, 9:22 AM

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, 11:27 AM

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:

 c Syntax (Toggle Plain Text) 
typedef struct lnode {
    void *data;
    struct lnode *next;
 
    int used_;
} lnode;
 
#define LIST_MAX 5000
 
static lnode sharedmem[LIST_MAX];
 
static lnode *allocator( void ) {
    int i;
 
    for ( i = 0; i < LIST_MAX; i++ ) {
        if ( ! sharedmem[i].used_ ) {
            sharedmem[i].used_ = 1;
            return &(sharedmem[i]);
        }
    }
 
    return NULL;
}
 
static lnode *make_lnode( void *data, lnode *next ) {
    lnode *n = allocator();
 
    n->data = data;
    n->next = next;
 
    return n;
}
typedef struct lnode {
    void *data;
    struct lnode *next;

    int used_;
} lnode;

#define LIST_MAX 5000

static lnode sharedmem[LIST_MAX];

static lnode *allocator( void ) {
    int i;

    for ( i = 0; i < LIST_MAX; i++ ) {
        if ( ! sharedmem[i].used_ ) {
            sharedmem[i].used_ = 1;
            return &(sharedmem[i]);
        }
    }

    return NULL;
}

static lnode *make_lnode( void *data, lnode *next ) {
    lnode *n = allocator();

    n->data = data;
    n->next = next;

    return n;
}

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, 1:50 PM

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, 2:58 AM

I think you were joking but you can implement a queue a variety of ways lol.

mbd · May 21st, 2008, 9:34 AM

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, 11:50 AM

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, 11:24 AM

fall back son, what language would you want to do this in?

Sane · May 22nd, 2008, 3:27 PM

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

(Toggle Plain Text)

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, 8:22 PM

Quote:

Originally Posted by Fall Back Son

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, 1:03 AM

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.

May 19th, 2008, 9:22 AM	#1
secrecy230 Newbie Join Date: May 2005 Posts: 11 Rep Power: 0	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!

May 19th, 2008, 11:27 AM	#2
Jessehk The Oblivious One Join Date: May 2005 Location: Ontario, Canada Posts: 644 Rep Power: 4	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: c Syntax (Toggle Plain Text) typedef struct lnode { void data; struct lnode next; int used_; } lnode; #define LIST_MAX 5000 static lnode sharedmem[LIST_MAX]; static lnode allocator( void ) { int i; for ( i = 0; i < LIST_MAX; i++ ) { if ( ! sharedmem[i].used_ ) { sharedmem[i].used_ = 1; return &(sharedmem[i]); } } return NULL; } static lnode make_lnode( void data, lnode next ) { lnode n = allocator(); n->data = data; n->next = next; return n; } typedef struct lnode { void data; struct lnode next; int used_; } lnode; #define LIST_MAX 5000 static lnode sharedmem[LIST_MAX]; static lnode allocator( void ) { int i; for ( i = 0; i < LIST_MAX; i++ ) { if ( ! sharedmem[i].used_ ) { sharedmem[i].used_ = 1; return &(sharedmem[i]); } } return NULL; } static lnode make_lnode( void data, lnode next ) { lnode n = allocator(); n->data = data; n->next = next; return n; } 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. __________________ Dr. Zoidberg: [ecstatic] I'm going to a movie... with FRIENDS!

May 19th, 2008, 1:50 PM	#3
mbd Programmer Join Date: Nov 2007 Posts: 86 Rep Power: 1	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.

May 21st, 2008, 2:58 AM	#4
Fall Back Son Professional Programmer Join Date: Oct 2006 Posts: 265 Rep Power: 2	Re: Implement a queue using share memory? I think you were joking but you can implement a queue a variety of ways lol.

May 21st, 2008, 9:34 AM	#5
mbd Programmer Join Date: Nov 2007 Posts: 86 Rep Power: 1	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.

May 21st, 2008, 11:50 AM	#6
Fall Back Son Professional Programmer Join Date: Oct 2006 Posts: 265 Rep Power: 2	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.

May 22nd, 2008, 11:24 AM	#7
mbd Programmer Join Date: Nov 2007 Posts: 86 Rep Power: 1	Re: Implement a queue using share memory? fall back son, what language would you want to do this in?

May 22nd, 2008, 3:27 PM	#8
Sane Programming Guru Join Date: Apr 2005 Location: Waterloo, Ontario Posts: 1,888 Rep Power: 5	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 (Toggle Plain Text) 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) 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? __________________ Waterloo's Canadian Computing Competition (CCC) - Stage 2 Problems, Solutions, and Test Data

May 25th, 2008, 1:03 AM	#10
Game_Ender Professional Programmer Join Date: May 2006 Location: Maryland, USA Posts: 306 Rep Power: 3	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. __________________ Robotics @ Maryland AUV Team - Software Lead

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
an efficient way to store/lookup memory addresses?	rgba	Software Design and Algorithms	8	Feb 13th, 2008 1:54 AM
Hexadecimal Memory Address Question	357mag	C++	1	Jul 8th, 2007 9:19 PM
queue - shared memory	programmingnoob	C++	4	Mar 26th, 2007 8:19 PM
Heap vs. Stack memory	Eric the Red	C++	11	Oct 24th, 2006 6:18 PM
Queue again	zman2245	C++	3	Sep 9th, 2005 1:07 PM

Programming Forums > Application Development > C

Implement a queue using share memory?