>>>On Wed, Nov 20, 2002 at 01:47:50PM -0600, Deb Baddorf wrote: >>>> What kind of optimiaztion does amanda use while flushing >>>> dumps to tape? >>>> >>>There is no optimazation, first in, first out. >>>That's a need feature. >>> >>>Jean-Louis
Here's a basic algorithm (in pseudo-code).
Is this useful to somebody who is already working on this code?
Or should I attempt to fit it into the actual taper code myself?
Deb Baddorf
=============================
This *should* handle both the FLUSH case (all data is available from
the start) and the on-going AMDUMP case (data is added as we go).
I may notice more errors but I think I got them all.
To "grok" the basic algorithm (ridiculously simple) ignore
or white out the "SPIN" paragraphs which wait for more data to
arrive.
===========================================
stuff = collection of items to be put into knapsack.
Dumpfiles in this case (includes tarfiles too)
Stuff is probably a doubly(?) linked list. Operations required:
status = insert(item)
status = remove(ptr) or maybe remove(item)
ptr = get_largest()
#boolean = is_empty()
boolean = has_data() #opposite sense to is_empty()
boolean = more_coming() #somebody elsewhere needs to tell us when no more dumps are coming down the pipe
item
number = size(item)
ptr = get_next_smaller() # return item next smaller than self
(maybe should be a function of the COLLECTION instead of the item, for project OO code)
next_ptr #if you use a doubly linked list
prev_ptr #if you use a doubly linked list
string = get_name(item) ?? for the index, or some such. Maybe for error message when dump won't fit.
knapsack #(or, tape!)
number = size_remaining()
status = add(item) # responsible to DELETE from holding disk after successful & from COLLECTION above
make_full() # decree it "full" when no available items can fit in the remaining space
boolean = has_space() # is not yet full
bunch-o-knapsacks #(or, how many tapes are available?)
ptr = gimme_one()
boolean = is_more()
==========================================
PACK_ALL_STUFF #i.e. start taping
{
mystuff = new stuff() # filled somewhere else, or here, but before algorithm below
allsacks = new bunch-o-knapsacks() #number comes from RUNTAPES parameter
yada yada yada
maybe twiddle thumbs till significant data arrives, if holding disk allows
while ( allsacks.is_more() # stop when we run out of sacks (tapes)
or (not mystuff.has_data() # or when we run out of data
and not mystuff.more_coming() ) ) # and know that no more is coming
{
this_sack = allsacks.gimme_one()
while ( not mystuff.has_data() ) #wait for some data to arrive
{spin
check "more coming" in case a client dies
}
while ( mystuff.has_data() and #there is still data waiting to be taped
this_sack.has_space() ) #the sack (tape) has room left
{
#remember, in "timed" version, a bigger one may be added during any pass
#so, we start with biggest each time and add the first that will fit
fill_sack (this_sack, mystuff.get_largest())
while ( not mystuff.has_data() ) #wait for some more data to arrive
{spin
check "more coming" in case a client dies
}
}
}
}
==========================================
fill_sack(sackptr, item_ptr)
{
if (item_ptr is NULL) #there are no more smaller items
{
sackptr.make_full() #decree sack (tape) to be full, so we can move on to another
return
}
isize=item_ptr.size(); ssize=sackptr.size_remaining(); #store for possible error msg
#or assign to variable IN the if statement, but too messy to do in psuedo-code here!
if ( item_ptr.size() <= sackptr.size_remaining() ) #if item fits, according to sack specs,
{ # put it in the sack
status = sackptr.add(item_ptr) # add MUST delete from holding disk, if it finishes successfully
# add MUST also adjust sack's size_remaining value
# it writes the INDEX, and does other bookkeeping too
# Also removes ITEM from "stuff" list of available dumps to flush
if ( not status) # failed -- tape size must've been slightly wrong. That's life.
{
sackptr.make_full() # we've already written to EOT so can't try another size item
write message "Sack(tape) wasn't as big as " isize + ssize.
write message "May want to correct sack specs (tapesize)"
}
}
else #find next smaller item and try that one
{
fill_sack (sackptr, item_ptr.get_next_smaller())
}
}
