[ros-kernel] RE: I can boot ReactOS with 8 Mb!!

[Waldo Alvarez Cañizares]

What they say looks great, but beware that it is a comercial product. I'm not saying they are doing it but a little tweak of the truth could mean huge amounts of $ for them. I'm researching strategies to reduce fragmentation (I have putted people to search for them too) Now the no lock-free operation is very attractive (beware that it won't cause to much speed improvement) Any Idea???. Also there are things that do not apply to the nonpaged pool like the swapping and for bookeeping I already fixed that. I'm watching for other possible solutions to the fragmentation problem but maybe a suballocator or sorting the requested blocks in bins sorted by size could be good. I have taken a look at other oses
 
Linux - binomial buddy system (exchanges external fragmentation by internal fragmentation)
        - bins of blocks sorted by size for realtime (by Doug Lea)
 
Minix - first fit (with linked lists :P, Tanenbaum wants to keep it simple)
 
Some I would like to know of
 
*BSD - ?? I do not have the sources
MacOS/MacOSX - ??
 
Wanna dig? The sources are huge ad take time to download.
 
In Modern Operating Systems Tanenbaum limits to say best fi tends to leave tiny useless blocks, FirstFit Tend to leave greater blocks WorstFit is a bad choice.
 
Also I was thinking that it could be a chance for us to do a similar product as LeapHeap and get the code  for ROS tested.
 
Best Regards
Waldo Alvarez

________________________________

From: ros-kernel-bounces at reactos.com on behalf of Robert K.
Sent: Fri 1/30/2004 1:11 PM
To: ReactOS Kernel List
Subject: Re: [ros-kernel] RE: I can boot ReactOS with 8 Mb!!



Is there still a heap missing?
I thought there's one around gnu (c-)libs

KJK::Hyperion schrieb:

> At 20.46 29/01/2004, you wrote:
>
>> I wonder if anyone has thought of a 'small object' bitmap based
>> allocator for these small things.  It would probably save hordes of
>> memory.
>
>
> FYI, I stumbled upon an interesting allocator:
>
> <http://www.leapheap.com/>
>
> The implementation is proprietary, not sure about the algorithms. It's
> entirely lock-free and, according to them, handles small-block
> allocation even better than the small-block algorithm by Microsoft
> (Microsoft's big block allocation synchronizes on a single mutex, so
> comparisons don't even make sense). Even if we won't be able to use the
> algorithm, this is the competition to beat
>
>> Some things in the reactos kernel even allocate chains of 16 byte or
>> less chunks. my idea would be keep a list of pages, each of which
>> would have a bitmap of 8-byte cells, and the cell data afterward. 
>> That way, a low-overhead allocator could be embedded in the current
>> pool allocator.
>
>
> My bread-and-butter idea, for what it's worth, was to keep a pool of
> lookaside lists for small (small enough for the padding overhead to be
> neglectable), 2^n block sizes - 1, 2, 4, 8, 16, 32, etc. bytes - to
> force ill-behaving drivers into using lookaside lists when appropriate.
> You calculate ceil(log2(allocation size)) and use it as an index in the
> array of preallocated lookaside lists. If the size exceeds the maximum
> available to this allocator, the normal pool allocator is used
> _______________________________________________
> Ros-kernel mailing list
> Ros-kernel at reactos.com
> http://reactos.com/mailman/listinfo/ros-kernel


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/ms-tnef
Size: 7100 bytes
Desc: not available
Url : http://reactos.com:8080/pipermail/ros-kernel/attachments/20040204/9b9f5fbf/attachment.bin