[openbeos] Re: Threading and File Descriptors
- From: "Alexander G. M. Smith" <agmsmith@xxxxxxxxxx>
- To: openbeos@xxxxxxxxxxxxx
- Date: Sat, 17 Aug 2002 11:55:10 EDT (-0400)
> Think about it - skip lists with 2-10 (or more) pointers per node? Where a
> node is a single socket/file handle?
The related kernel data (such as the data structure which tracks an open file -
reference count, vnode, read/write position and whatnot) would presumably be
part of that node. You usually wouldn't have a socket or file handle as the
data portion of the node, it would be the actual socket implementation data
structure etc.
Trees may be better than skip lists. AVL balanced trees have 2 child pointers,
plus a height and the key (call it 3 words total, height only needs a byte and
the key can by a 3 byte integer - 16 million file handles possible before it
wraps around), and the actual payload data. Vs skip lists with a height (a
byte), the key, and two pointers in every other node, three for every fourth
node, four for every eighth node etc.
> Maybe 50 pages at a time for VM... Or even:
> struct vmPages {
> page *pages[50];
> a100Pages *somePages;
> a1000Pages *lotsOfPages;
> }
Keep this up and you'll reinvent balanced trees :-). I'd put up with the O(log
n) speed hit and keep it simpler that way.
Incidentally, AmigaDOS used doubly linked lists for its kernel structures.
Rather than passing around file handles, it used the address of the list node
itself as the file handle, so no searches were required to find open files etc.
You got the unlimited space advantage of lists and speed actually better than
that of arrays. When closing the file, the list node was removed from the list
efficiently because of the double links. Traversing the whole list was rarely
needed for most operations (but expensive when it was).
> Gigabyte areas would require a whole different way of looking at things. What
> is optimal for 16k areas is not going to work for 2 gig areas. I am not sure
> if I want to try to conquer all of that with a first release, but it is
> definately something coming up in the future (and not too far off).
The general strategy of getting it working first, even if it isn't perfect, is
good. Even Microsoft uses it with great success.
- Alex
Other related posts:
