Shadow Paging is an alternative technique for recovery to overcome the disadvantages of log-based recovery techniques. The main idea behind the shadow paging is to keep two page tables in database, one is used for current operations and other is used in case of recovery.
Database is partitioned into fixed length blocks called pages. For memory management, adopt any paging technique.
1. Page Table
To keep record of each page in database, maintain a page table. Total number of entries in page table is equal to the number of pages in database. Each entry in page table contains a pointer to the physical location of pages.
The two page tables in Shadow Paging are :
- Shadow page table : This table cannot be changed during any transaction.
- Current page table : This table may be changed during transaction.
Both page tables are identical at the start of transaction. Suppose a transaction Ti performs a write operation on data item V, that resides in page j. The write operation procedure is as follows :
- If jth page is in main memory then Ok otherwise first transfer it from secondary memory to main memory by instruction input (V).
- Suppose page is used first time then :
- System first finds a free page on disk and delete its entry from free page list.
- Then modify the current page table so that it points to the page found in step 2(a).
- Modify the contents of page or assign new value to V.
After performing all the above operations, the following steps are needed to commit Ti.
- Modified pages are transferred from main memory to disk.
- Save current page table on disk.
- Change current page table into shadow page table (by changing the physical address).
Shadow page table must be stored in non-volatile or stable storage because it is used at the time of recovery. Suppose the system crashed and you have to recover it. After every successful completion of transaction, current page table is converted into shadow page table. So, shadow page table has to be searched. For making the search simple, store shadow page table on fixed location of stable storage. No redo operations need to be invoked. Shadow page table and Current page table are shown in Figure 10.6 after write operation on page 409.
Disadvantages : The major disadvantages of shadow paging are
- Data fregmentation due to fixed sized pages.
- Wastage of memory space.
- Extra overhead at the time of commit (by transferring of page tables)
- It provides no concurrency.
SOLVED PROBLEMS
Problem 1. Consider the case of deferred database modifications and assume that, after a crash, the log contains the following records:
<T1 starts>
<T1, A, 500> op1
<T2 starts>
<T1, B, 400> op2
<T2, A, 200> op3
<T1 commits>
<T3 starts>
<T3, A, 800> op4
<T4 starts>
<T4, B, 900> op5
<T3 commits>
- Which transactions (T1 – T4) will be redone during recovery?
- For each operation (op1 – op5) state whether that operation will be redone, undone, or neither, during recovery.
- What will be the value of data item ‘A’ after the recovery algorithm has finished?
Solution.
- Redo T1 and T3, since the log contains both < T1 starts >, < T1 commits > and < T3 starts >, < T3 commits >.
- Redo OP1, OP2 and OP4
Nothing needs to be done to OP3 and OP5
- After recovery, A will be 800
Problem 2. Consider the case of immediate database modifications and assume that, after a crash, the log contains the following records:
<T1 starts>
<T1, A, 400, 500> op1
<T1, B, 300, 400> op2
<T1 commits>
<T2 starts>
<T2, C, 100, 200> op3
<T3 starts>
<T3, D, 700, 800> op4
<T3 commits>
<T4 starts>
<T4, E, 800, 900> op5
- Which transactions (T1 – T4) will be redone during recovery?
- For each operation (op1 – op5) state whether that operation will be redone, undone, or neither, during
- What will be the value of data item ‘A’ and ‘E’ after the recovery algorithm has finished?
Solution.
- Redo T1 and T3, since the log contains both < T1 starts >, < T1 commits > and < T3 starts >, < T3 commits > .
- Redo OP1, OP2 and OP4; Undo OP3 and OP5
- After recovery, A will be 500, E will be 800
Problem 3. After a systems failure, the undo-redo recovery log has the following entries:
An entry <T, X, u, v> means that transaction T has updated the value of X from u (the old value) to v (the new value). <CkPT(…)> denotes the beginning of a checkpoint and lists the currently active transactions. <END CkPT> is written to disk once all dirty pages of the active transactions have been flushed to disk. The redo phase preceeds the undo phase during the recovery.
- Which are the transactions whose actions the recovery manager needs to redo?
- Which are the transactions whose actions the recovery manager needs to undo?
- Indicate the actions of the recovery manager on all the elements, separately during the Redo and the Undo phase.
Solution.
- T2, T5
- T3, T4, T6
Source: Gupta Satinder Bal, Mittal Aditya (2017), Introduction to Basic Database Management System, 2nd Edition-University Science Press (2017)