Efficient allocation algorithms for flash file systems

Embedded systems have been developing rapidly, and flash memory technology has become an essential building block because of its shock-resistance, low power consumption, and non-volatile nature. Since flash memory is a write-once and bulk-erase medium, an intelligent allocation algorithm is essential to providing applications efficient storage service. In this paper, we propose three allocation algorithms - a first come first serve (FCFS) method, a first re-arrival first serve (FRFS) method, and an online first re-arrival first serve (OFRFS) method. Both FCFS and OFRFS are online allocation mechanisms which make allocation decision as the requests arrive. The FRFS method, which serves as an offline mechanism, is developed as the standard of performance comparison. The capability of the proposed mechanisms is demonstrated by a series of experiments and simulations. The experimental results indicate that FRFS provide superior performance when the data access pattern is analyzed in advance, and the online OFRFS method provides good performance by run-time estimation of access patterns.