Compressed memory systems and methods that reduce problems of memory overflow and data loss. A compression engine compresses blocks of data for storage in a compressed memory. A compression monitor monitors the achieved compression ratio and provides a software trap when the achieved compression ratio falls below a minimum. After the trap is provided software monitors the fill state of the compressed memory. If the compressed memory is approaching full, the software changes the block size to improve the compression ratio.