wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> shared memory queues
        
(Message started by: cuckoo on Jul 24^th, 2007, 10:43pm)

Title: shared memory queues
Post by cuckoo on Jul 24^th, 2007, 10:43pm

Give a good data structure for having n queues (n not fixed) in a finite memory segment. You can have some data-structure separate for each queue. Try to use at least 90% of the memory space.

Any good ideas?

Title: Re: shared memory queues
Post by towr on Jul 25^th, 2007, 12:44am

You could use an list/tree/heap of linked lists.
Of course that'd waste a lot of space on pointers if the elements you store are small.

Title: Re: shared memory queues
Post by sk on Sep 3^rd, 2007, 7:45pm

u can use a circular queue with n heads and tails.

queue full condition is checked if the tail hits the next head.
tail[i] hits head[i+1%n];
whenever a new queue has to be created, the space between the last tail and the first head can be divided into 2 segments and the new queue head can be assigned to lasttail + (lasttail - firsthead)/2 % n.

Maybe some math can be adjusted here to determine which is the best alocation.
-----

other alternative
as towr suggested list of queues, or trees

Title: Re: shared memory queues
Post by gotit on Sep 4^th, 2007, 1:34am

I don't quiet get the reason behind using a list/tree/heap of linked list, as towr has said. Are we using the list/tree/heap to assign some kind of priority to the queues?

Title: Re: shared memory queues
Post by towr on Sep 4^th, 2007, 4:44am

on 09/04/07 at 01:34:28, gotit wrote:

I don't quiet get the reason behind using a list/tree/heap of linked list, as towr has said. Are we using the list/tree/heap to assign some kind of priority to the queues?

Or some kind of sorting.
It really depends on why we want n different queues in the first place.

In any case we need a datastructure to tie the n queues together in some way, and since n is not fixed, we need a variable datastructure to do this. Lists, trees and heaps then come to mind.