Operating Systems: Concurrent and Distributed Software Design

21.8. An algorithm for recovery

An algorithm for the recovery procedure is as follows.

The recovery manager keeps:

• an UNDO LIST which initially contains all the transactions listed as active in the checkpoint record;

• a REDO LIST which is initially empty.

It searches forwards from the checkpoint record to the end of the log (that is, the most recently written record at the time of failure):

• if it finds a START TRANSACTION record it adds that transaction to the UNDO LIST;

• if it finds a COMMIT record it moves that transaction from the UNDO LIST to the REDO LIST.

It then works backwards through the log from its end,

• UNDOing transactions on the UNDO LIST.

Finally, it works forwards again from the checkpoint record to the end of the log,

• REDOing transactions ...