Re: LBAcache devel BUGFIX and improved release

Hi, are you sure this is a priority queue type problem?
By the way:
- the percentage display still shows wrong numbers. What the heck???
- if you are almost out of DOS memory, the .com version will not notice
  and you will get in troubles when you spend more than you have
- I remember that "use least used if have to discard one" is no good:
  When the cache is full, the newest sectors will always be discarded too
  soon, as they have no time to "earn importance" before new request for
  new cache slots come in. So yes, a queue would be an idea, but this is
  not optimal either: How to find the priority?
  Possible solutions: Have a minimum age per slot, younger slots may not
  be discarded. Hard to measure the age here.
  Do indeed a queue, by allocating the buffers in a circular way, possibly
  skipping over "too important" entries (but in the course eating up their
  importance value, so that they will not settle at "max importance" and
  block the cache for more useful sectors).

Bonus ideas:
- How about a "freeze" option: Would mark all currently stored entries as
  undiscardable. Could for example be triggered after a locate /d+ /s which
  will read all directory sectors once.
- I think I should add a "default after timeout" to MetaKern, correct?
- I think I should provide a nice 512 byte program / screensaver / game with
  MetaKern, for those who have only one DOS version installed, to fill the
  other then free menu item :-). Suggestions for that?

Eric


>      I suggest, for you will be useful book Jon Bentley "Programmin Pearls",
> 2nd ed. There in chapter 14 described queues with priorities, implemented
> with help of heap ("heap" as in "heapsort"). Some info you may find on the
> site <http://netlib.bell-labs.com/cm/cs/pearls/>. He also makes short
> introfuction into hashing, but for hashing better look in Knuth's excelent
> book "Art of Computer Programming", 2nd ed., vol 3, "Sorting and Searching",
> chapter 6.4.
> 
>      There heapsort alwys gives fixed (relative small) time O(n*log n), but
> with correct implemenation hashing will be much-much better - O(1)!

I once had a quick look at Linux' caching algorithm, you can really add a
big pile of complexity to that kind of calculations if you want to :-). If
somebody knows a "halfway sane but simple" algorithm, please give me a hint.
By the way, my hashing is just "sector number xor (drive shift ...)" and then
modulo sector size. I do not see why a simple modulo should not be okay for
my simple needs. But who knows?

Eric