gottlieb@cmcl2.UUCP (Allan Gottlieb) (01/02/84)
I would not classify it as a BUG to say that the buddy system is good for segment allocation. Please note that good is not great. The obvious method of allocating next higher power of two yields segments 3/4 filled and when about 90-95% of the memory is allocated memory requests start failing for lack of memory. Being limited to only 2/3 of the memory purchased is certainly not good, but the buddy system is very fast. As pointed out, some speed can be traded in for better memory utilization. Instead of using all the one bits, one could look at only the first two or three. Considering the relative cost of central I would give the buddy system a B- or (fair to) good rating. Note however that the bulk of the message was about parallelizing memory allocation. As stated, we know how to do this for the buddy system. To be sure we can parallelized allocating fixed size pages (NOT demand paging) as well but are concerned about loading large page tables on context switches. I am unaware of fully parallel algorithms (i.e. algorithms without critical sections) for first fit (with the Knuth "rover" modification). Allan Gottlieb GOTTLIEB @ NYU floyd!cmcl2!gottlieb