A Fixed Optimum Cell-Size for Records of Various Lengths

This paper discusses a problem arising when messages of unpredictable lengths must be stored in and removed from a computer memory upon demand. Storage space for a data message must be allocated while the message is arriving and before its length is know~ to the computer. Difficulties occur both in assigning storage space and in keeping track of the locations of messages. One convenient plan is to divide the memory into addressaMe cells of fixed size, each containing several machine words. All the cells used for one message form a list structure. Small cells waste space by requiring the use of many control words to link the cells of each list. If cells are very large, the last cell used by a message is likely to contain much empty space. The problem treated here is that of finding C, the cell size Omt minimizes the mean (with respect to message lengths) amount of space wasted per message.