Checkpoints & Shadow Paging
Duration: 12 min
This video lesson is available to enrolled students.
Inside: a video lesson and guided study material.
Module outline
- About Course: About the Course
- Paper 1 | Quantitative Aptitude: Percentage Ratio and Proportion (Ratios) Powers and Exponents (Surds and Indices) Logarithm Sequence and Series (Series) Mensuration and Geometry Data Interpretation Average Arithmetic Simplification and Approximation Algebra Sequences and Series Profit, Loss and Discount Percentages Number System Ratio and Proportion Averages, Mixtures and Alligation Permutations and Combinations Time and Work Vocabulary Subject-Verb Agreement Sentence Completion Geometry Reading Comprehension Powers, Surds and Logarithms Trigonometry Mensuration Speed, Time and Distance Patterns in Two-Dimensional Figures Probability Measurement and Quantity Take-Off Transformation of Shapes Three-Dimensional Patterns and Visualization Statistics Mathematical Operations Data Sufficiency Constraint Puzzles Data Interpretation Mixture and Alligation Speed Time and Distance HCF LCM Algebra Profit and Loss Venn Diagram
- Paper 1 | Logical Reasoning: Non Verbal Reasoning (Spatial Aptitude) (Spatial Reasoning) (Visual Reasoning) Series (Number and Letter Series) (Numerical Relations and Reasoning) Deductive and Inductive Reasoning (Logical Deduction and Induction) (Prepositional Reasoning) Analogy Cubes & Dices Syllogisms Numerical Reasoning Assembling and Grouping of Shapes Coding and Decoding Cubes and Dice Series Completion Alphabet and Word Tests Analogy and Classification Direction Sense Logical Deduction and Induction Order, Ranking and Sequence Critical Reasoning Syllogisms and Venn Diagrams Narrative Sequencing Project Monitoring, Resources and Safety Simple Interest and Compound Interest Coding Decoding Seating Arrangements
- Paper 1 | English Language: Vocabulary Noun Pronoun Verb Adjectives Adverb Preposition Conjunction Articles Tenses Subject Verb Agreement (Verb Noun Agreement) Modals Sentence Correction (Error Correction) Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions) Sentence Re-arrangements (Para Jumbles) (Narrative Sequencing) Prepositions and Conjunctions Idioms and Phrases Verb Forms and Verb Patterns Sentence Basics, Nouns and Pronouns Adjectives and Adverbs Articles and Determiners Modals, Conditionals and Subjunctive Sentence Structure and Correction Voice and Reported Speech Tenses Vocabulary
- Paper 1 | Unit Tests:
- Paper 1 | Full-Length Mock Tests:
- Paper 2 | Engineering Mathematics: Set Theory Relations Functions Graph Theory Group Theory Propositional and Predicate Logic Linear Algebra Calculus Permutation and Combination Probability Statistics Signal Space and Optimum Detection Probability Statistics Combinatorics
- Paper 2 | Digital Logic: Digital Systems & Boolean Basics Logic Gates & Hardware Boolean Expression Boolean Minimization Combinational Circuit Sequential Circuits Number System Number Representation Registers and Counters Boolean Algebra and Logic Gates Microprocessors and Microcontrollers Logic Families and CMOS Logic Microprocessors Logic Gates and Boolean Algebra Number Systems and Codes Minimization of Boolean Functions Timing, Hazards and Testing Logic Families Combinational Logic Design Arithmetic Circuits Semiconductor Memories and Programmable Logic Devices Combinational Logic Circuits Sequential Circuits and State Machines Latches and Flip-Flops Finite State Machines Minimization of Boolean Functions Arithmetic Circuits Registers and Counters Latches and Flip-Flops Number Systems and Codes
- Paper 2 | Computer Architecture: Basics of COA Floating Point Rep Cache Memory Organization Input Output Organisation Pipelining Instr Formats & Modes Control Unit Design Semiconductor Memories and Programmable Logic Processor Organization and Instructions Memory Hierarchy and Input/Output
- Paper 2 | Programming and Data Structures: C Fundamentals Control Flow Functions Arrays & Pointers Storage Classes, Structures & Enums DMA, Macros, Scoping & File Handling Introduction to DS Array Stack Queue Linked List Tree Graphs Hashing
- Paper 2 | Algorithms: Algorithm Analysis Time Complexity Analysis Sorting Algorithms Greedy Algorithms Dynamic Programming Minimum Spanning Trees Shortest Path Algos
- Paper 2 | Theory Of Computation/Automata Theory: Introduction to TOC Deterministic FA (DFA) Non-Deterministic FA Regular Expressions Grammar Regular Language Properties Moore & Mealy Machines Pushdown Automata & CFG Turing Machines Complexity Theory
- Paper 2 | Compiler Design: Intro to Compilers Lexical Analysis Grammar & CFG Syntax Analysis: Top-Down Syntax Analysis: Bottom-Up Semantic Analysis & SDT Intermediate Code Gen Code Optimization Run Time Environment
- Paper 2 | Operating System: Introduction to OS Process Management CPU Scheduling Process Synchronization Threads & Process Creation Deadlock Memory Management Virtual Memory Disc Scheduling File Management
- Paper 2 | DataBase Management System/DBMS: Basics of DBMS ER Diagram Relational Model & Functional Dependencies Keys & Integrity Constraints Normalization (1NF - BCNF) Decomposition Properties & 4NF File Organization & Indexing Relational Algebra SQL Relational Calculus Transaction Management Concurrency Control Database Recovery
- Paper 2 | Computer Networks: Introduction to CN DLL: Access Control DLL: Flow Control DLL: Error Control DLL: Framing Data Link Layer - Ethernet Net Layer: IPv4 & Proto Net Layer: IP Addressing Net Layer:Routing Protocol Transport Layer Services TL: Congestion & UDP Application Layer Hardware Basics
- Paper 2 | CS/IT Sectional Mock Tests:
- Complete Paper Full Mock Test:
AI summary & chapters
AI Summary
An AI-generated summary of this video lecture.
This educational video provides a comprehensive overview of database recovery techniques, focusing on checkpoints and shadow paging. The lecture begins by explaining the inefficiency of redoing or undoing all transactions from a log after a system failure, especially when the log is long. To address this, it introduces checkpoints as a mechanism to periodically save the state of the database, reducing recovery time. The video then transitions to shadow paging, an alternative to log-based recovery. It explains that shadow paging uses two page tables: a current page table and a shadow page table. The current page table is used for all data accesses during a transaction, while the shadow page table is stored in nonvolatile storage. The core idea is that when a page is written for the first time, a copy is made to an unused page, and the current page table is updated to point to this copy. The video uses diagrams to illustrate the process of a transaction beginning, where the current page table is copied to the shadow page table, and the shadow page table is saved. It also shows how to recover from a failure by discarding the current page table and making the shadow page table the new current one. Finally, the video discusses the advantages and disadvantages of shadow paging, noting that it eliminates the overhead of writing log records and makes recovery trivial, but it suffers from data fragmentation and requires expensive garbage collection. A potential optimization is mentioned: using a B+ tree structure for the page table to only copy the paths to updated leaf nodes, rather than the entire table.
Chapters
0:00 – 2:00 00:00-02:00
The video begins with a slide titled 'Checkpoints'. It explains that redoing or undoing all transactions from a log can be very slow, especially if the system has been running for a long time, as it may require redoing transactions that have already been committed. To streamline the recovery process, the video introduces the concept of periodically performing checkpoints. The steps for a checkpoint are listed: 1) Output all log records currently in main memory to stable storage. 2) Output all modified buffer blocks to the disk. 3) Write a log record <checkpoint> to stable storage, along with a list L of all transactions active at the time of the checkpoint. The slide also notes that all updates are stopped during the checkpointing process.
2:00 – 5:00 02:00-05:00
The video transitions to a new topic, 'Shadow Paging', which is presented as an alternative to log-based recovery. The slide explains that in this technique, the database is considered to be made up of fixed-size disk blocks or pages. The core idea is to maintain two page tables during a transaction's lifetime: the current page table and the shadow page table. The current page table is used for all data item accesses, while the shadow page table is stored in nonvolatile storage. This allows the state of the database prior to transaction execution to be recovered. The slide concludes by stating that this technique provides atomicity and durability.
5:00 – 10:00 05:00-10:00
This segment details the mechanics of shadow paging. The first slide explains that at the start, both the current and shadow page tables are identical, and only the current page table is used for data access. When a page is written for the first time, a copy of that page is made to an unused page, the current page table is updated to point to this copy, and the update is performed on the copy. A diagram titled 'Sample Page Table' illustrates this, showing a page table with pointers to pages on disk, and a 'free page' pointer. The next slide, 'Example of Shadow Paging', shows a visual representation of the two page tables. It demonstrates that when a transaction modifies a page, the current page table is updated to point to a new copy of that page, while the shadow page table remains unchanged, preserving the pre-transaction state.
10:00 – 11:32 10:00-11:32
The final segment covers the commit and recovery process. A flowchart shows that when a transaction begins, the current page table is copied to the shadow page table, which is then saved. To recover from a failure, the current page table is discarded, and the shadow page table becomes the new current page table. The slide on committing a transaction outlines three steps: flush modified pages to disk, output the current page table to disk, and make the current page table the new shadow page table by updating a pointer. The video concludes with a slide on the advantages and disadvantages. Advantages include no overhead for writing log records and trivial recovery. Disadvantages include data fragmentation and expensive garbage collection, which can be mitigated by using a B+ tree structure for the page table.
The video presents a logical progression from a common recovery problem to a specific solution. It starts by identifying the performance bottleneck of log-based recovery, which is the need to process a potentially massive log after a crash. The solution, checkpoints, is introduced as a way to create a 'snapshot' of the database state, reducing the amount of work needed for recovery. The video then pivots to a fundamentally different approach: shadow paging. This technique avoids the log entirely by using a copy-on-write strategy with two page tables. The core concept is that the shadow page table acts as a persistent, unmodified backup of the database state before a transaction started. This allows for a simple and fast recovery by simply discarding the current, potentially corrupted, state and reverting to the shadow state. The video effectively contrasts the two methods, highlighting the trade-offs: checkpoints are a modification of the log-based approach, while shadow paging is a complete alternative that offers faster recovery at the cost of increased storage overhead and complexity in managing data fragmentation.

