# TAOCP Vol 1, Section 2.5, Exercise 27. MMIX version. # Algorithms R and S pg. 443, buddy system reservation and liberation. Conversion from MIX by Ladislav Sladecek sladecek@users.sourceforge.net ** FILES README this file buddy_book.mms The MMIX code (just the procedures printed in the book) buddy_run.mms Complete runnable MMIX code with main(). buddy_test.pl A perl wrapper which generates a random scenario of allocations, compiles buddy_run.mms, and runs it. ** HOWTO run this Tested on RedHat Linux 7.2; should work on most other systems. perl buddy_test.pl (Read the source of buddy_test.pl for explanation of arguments.) Use xterm with at least 114 chars of width. ** DISCUSSION 1) The mix version can allocate blocks of any length beginning from a single word. This is because a single mix word can contain two links (LINKF and LINKB) and a field for KVAL. In mmix, we need 19 bytes for this. Therefore the smallest block size is 32 bytes. 2) The mix version dies (JMP OVERFLOW) when the memory is exhausted. This mmix code returns zero. This is needed for testing. 3) The mix version assumes that the memory pool starts at location zero. The mmix pool starts at PoolSegment. 4) The mix code for the algorithm S on page 612 (answer to Exercise 28) stores TAG in the sign field of the first word of the block. This is OK for empty blocks. But, in my view, this will not work for reserved blocks because the user can store any value here. If this value is negative, the algorithm will combine this block with its buddy. Hence, the mmix version uses a separate array of bits for this. Ladislav Sladecek