Chris Clack

Programming Languages and Systems

List of Publications

Citations

Automatic Memory Management for Real-Time Embedded Systems

• There is a growing interest in the use of high-level languages such as Java to program real-time embedded systems; one compelling reason is the ability to load new code dynamically and have it link in with existing code on the device.
• However, much of Java's power and flexibility comes from its automatic memory management (automatic memory allocation and garbage collection)...and the underlying technology is not yet up to the job!
  • Incremental copying collectors are capable of providing fast response but require up to 100% memory overheads - this increases the size, power consumption and cost of the end product.
  • Reference counting collectors require at least one word overhead per allocated block of memory, cannot (or can only with difficulty) reclaim cyclic structures, and suffer fragmentation.
  • Incremental mark-sweep collectors are fast but suffer fragmentation.
• But does fragmentation really occur in real programs?
  • Yes! Johnstone and Wilson have shown that, for a collection of common programs (Espresso, GCC, Ghostscript, Grobner, Hyper, LRUsim, P2C and Perl), the average fragmentation depends critically on the allocation policy being used and can be as bad as nearly 2,000% ! - see ftp://ftp.dcs.gla.ac.uk/pub/drastic/gc/wilson.ps
• But the best policies give an average fragmentation of about 1%, so is it really a problem?
  • It is if you're running an embedded application that absolutely cannot, must not, run out of memory. Or for exampe if your product is an operating system for a consumer embedded product where consumers will not tolerate "out of memory" errors. In these cases, you must consider the worst-case fragmentation and ensure that the memory footprint is big enough that the program will not abort due to lack of memory!
• So why not just run a defragger?
  • Because defraggers are slow and often require additional memory, so the overall memory footprint is not as low as it should be.
• So which memory allocation policy gives the smallest "worst-case" fragmentation?
  • Probably best-fit.
• But isn't best-fit unbearably slow?
  • Not any longer! A new allocator (and associated collector) provides best-fit allocation of variable-sized memory blocks an order of magnitude faster (in the worst-case) than the previous best-performing best-fit algorithm, and with equivalent speed (in the best-case) to dlmalloc (one of the best-performing best-case best-fit allocators currently available).
  • A patent for the new technique has just been filed - hence nothing has been published yet. However, if you want to know more, email me.

• Priority queues are used in a wide variety of applications (for example, process scheduling, processing data from multiple sensors, in network routers to prioritise real-time media flows and to provide differentiated services).
• Hard real-time systems require guaranteed worst-case behaviour. Typically, priority queues exhibit one of the following two kinds of worst-case behaviour (where n is the number of items currently in the queue):
  • O(1) insert and O(n) deletemin (or O(n) insert and O(1) deletemin);
  • O(log n) insert and O(log n) deletemin.
• A number of novel variants of the priority queue have been developed which exhibit differing worst-case behaviour (see below). Thus, the best behaviour can be selected for a given application.
  • insertion and deletion both O(log max) where max is the biggest value;
  • insertion and deletion both O(log range) where range is the difference between the biggest and smallest value;
  • insertion and deletion both O(log diff) where diff is the number of different cell values.
• Worst-case insertion and deletion may be significantly faster than for conventional priority queues, for example in situations where there are many duplicates and where values are tightly clustered.