Can't find what you are looking for ?

Sunday, September 6, 2009

Learn software terms: How is shadow paging performed ?

Shadow paging is an alternative to log-based recovery techniques, which has both advantages and disadvantages. It may require fewer disk accesses, but it is hard to extend paging to allow multiple concurrent transactions. The paging is very similar to paging schemes used by the operating system for memory management.

How Shadow Paging is performed ?
- To commit a transaction :
* Flush all modified pages in main memory to disk.
* Output current page table to disk.
* Make the current page table the new shadow page table, as follows:
1. Keep a pointer to the shadow page table at a fixed (known) location on disk.
2. To make the current page table the new shadow page table, simply update the pointer to point to current page table on disk.
- Once pointer to shadow page table has been written, transaction is committed.
- No recovery is needed after a crash: New transactions can start right away, using the shadow page table.
- Pages not pointed to from current/shadow page table should be freed (garbage collected).

Advantages of shadow-paging technique:
- No overhead of writing log records.
- Recovery is trivial.

Disadvantages of shadow-page technique:
- Commit overhead : The commit of a single transaction using shadow paging requires multiple blocks to be output -- the current page table, the actual data and the disk address of the current page table. Log-based schemes need to output only the log records.
- Data fragmentation : Shadow paging causes database pages to change locations (therefore, no longer contiguous.
- Garbage collection : Each time that a transaction commits, the database pages containing the old version of data changed by the transactions must become inaccessible. Such pages are considered to be garbage since they are not part of the free space and do not contain any usable information. Periodically it is necessary to find all of the garbage pages and add them to the list of free pages. This process is called garbage collection and imposes additional overhead and complexity on the system.

No comments: