On Thu, May 15, 2003 at 11:15:53PM +0200, Paul Bijnens wrote:
> On Thu May 15 2003 14:49, Eric Siegerman wrote:
> >     Intended usage:
> > taper_algo LARGESTFIT
> > second_taper_algo SMALLEST
> 
> It could also be implemented as a second optional directive of taper_algo
> like:
>   taper_algo LARGESTFIT SMALLEST

Yah.  I've been thinking that it might turn into another kind of
custom block like tapetype and dumptype.  Something like:
        algorithm algo1 {
                algo 1 stuff
        }
        algorithm algo2 {
                algo 2 stuff
        }

        taper_algorithms algo1 algo2

or, semantically equivalent and in some sense cleaner, but less
Amanda-like:
        taper_algorithms {
                {
                        algo 1 stuff
                }
                {
                        algo 2 stuff
                }
        }

The idea is that, every time the taper becomes available, driver
runs through the algorithm blocks in turn until one yields up a
DLE.

Making each algorithm a block instead of a simple keyword starts
by providing a place to stash parameters, as in my "SLOP n MB"
suggestion.  But given the syntax, it lets one factor out and
orthogonalize the algorithms themselves.

Here are some examples.  for clarity, I'll use CAPS for the
primitives, and lower-case for the derived combinations; but I'm
NOT suggesting casting this distinction in stone.  Don't try to
read this as a sensible list that someone might use; they're just
isolated algorithm blocks.

Some basic primitives are FIRST, LAST, LARGEST, SMALLEST, which
mean the same as the current taper_algo's; I'll invent more as I
go along.

        #
        # Factor FIRSTFIT and LARGESTFIT primitives out of
        # existence.  The argument to MAX_SIZE can be either an
        # absolute size (i.e. of the dump to select) or a
        # percentage of (estimated) remaining tape.
        #
        algorithm first_fit {
                FIRST
                MAX_SIZE 100%
                SLOP 0
        }

        algorithm largest_fit {
                LARGEST
                MAX_SIZE 100%
                SLOP 0
        }

        #
        # A sloppy version...
        #
        algorithm sloppy_largest_fit {
                LARGEST
                MAX_SIZE 100%
                SLOP .5 GB
        }

        #
        # This one implements the fancy version of SLOP that only
        # gambles on small-enough dumps
        #
        algorithm sloppy {
                LARGEST
                MAX_SIZE 1 GB
                SLOP .2 GB      # 2% of a 10-GB tape
        }

        #
        # The SLEEP primitive is special:
        #   - after the sleep period, the list of algo's is rerun
        #     from the top
        #   - if the dumps have all finished, the algorithm falls
        #     through (without selecting a dump); that gives the
        #     following blocks a chance to clean up whatever's
        #     still in the holding disk
        #
        # Unless of course one wants to make an explicit CONTINUE
        # primitive instead -- gee, isn't this fun?
        #
        algorithm snooze {
                SLEEP 10 MIN
        }

There'd also have to be a NEXT_TAPE primitive, of course, but now
one has lots of flexibility as to how or even if it comes into
play.

Putting it all together:  I mentioned before about waiting for
all the dumps to finish before starting to write to tape (to give
LARGESTFIT the info it needs to optimally fill tapes).  Here's a
version that starts as soon as it knows it can (almost) fill a
tape.  It's suboptimal, but its suboptimality is bounded and
tunable, unlike that of the current LARGESTFIT.  Assume a 10-GB
tape drive.  To keep things simple, there're no sloppy algorithms
in this one.  And I'm switching to the other syntax just to get a
feel for it :-)

        taper_algorithms {
                #
                # If some subset of the tape-ready dumps totals
                # between 9.5 and 10 GB, tape 'em all.  It's that
                # old exponential knapsack algorithm, so don't
                # try it with too many DLE's :-)
                #
                # (Within the selected set, it's probably ok to
                # hard-code a LARGEST ordering, to minimize the
                # risk should there be less room left than we
                # thought there was)
                #
                {
                        DUMP_SET
                        SLOP 0
                        MIN_SIZE 9.5 GB
                        MAX_SIZE 100%
                }

                #
                # If we don't have such a subset, wait until one appears,
                # polling at 10-minute intervals.
                # But once the dumps are finished, fall through.
                #
                {
                        SLEEP 10 MIN
                }

                #
                # Standard largest-fit for whatever's left
                #
                {
                        LARGEST
                        MAX_SIZE 100%
                        SLOP 0
                }
        }

I wonder if this would do well enough, without being exponential?
The idea is to keep LARGESTFIT from using up all of the small
dumps at once, but only as needed to fill up the tape.  Replacing
only the first block in the preceding example:
                {
                        LARGEST
                        MAX_SIZE 100%
                        MIN_SIZE 50%    # likewise, % of remaining tape
                        SLOP 0
                }

Yet another scheme I'll never find time to implement.  *sigh*

--

|  | /\
|-_|/  >   Eric Siegerman, Toronto, Ont.        erics AT telepres DOT com
|  |  /
My Wine works.  However it crashes about half the time on startup.
Apparently their simulation of windoze API is getting too accurate.  :)
        - Kyle Sallee