Checkpoints & Shadow Paging

Duration: 12 min

This video lesson is available to enrolled students.

Return to /learn/DSSSB-TGT-COMPUTER-SCIENCE-COMPLETE-COURSE/data-base-management-system/database-recovery/advanced-recovery-algorithms/asset-checkpoints-shadow-paging after enrolling

Inside: a video lesson and guided study material.

Module outline

  1. About Course: About the Course
  2. Section A: General Awareness: Polity, Physics, Biology, Chemistry, Static General Knowledge, History, Geography, Indian Economy, GK- Current Affairs, Evolution of Indian Banking (Banking & Financial Awareness), Environment
  3. Section A: General Intelligence & Reasoning ability: Series (Number and Letter Series) (Numerical Relations and Reasoning), Coding Decoding, Data Sufficiency, Non Verbal Reasoning (Spatial Aptitude) (Spatial Reasoning) (Visual Reasoning), Analytical Reasoning (Counting Figures Reasoning), Blood Relations, Syllogisms, Deductive and Inductive Reasoning (Logical Deduction and Induction) (Prepositional Reasoning), Seating Arrangements, Directions (Direction Test), Puzzle Solving (Puzzles), Calendar, Clock, Cubes & Dices, Selection Decision Table (Decision Making), Logical Sequence Of Words, Crypt Arithmetic, Venn Diagram, Data Arrangement, Inequality, Analogy, Ranking, Order and Sequence, TCS NQT Advanced Reasoning Ability
  4. Section A: Arithmetical & Numerical Ability: Ratio and Proportion (Ratios), Divisibility Rules, Data Interpretation, Mixture and Alligation, Permutation and Combination, Logarithm, Number System, HCF LCM, Sequence and Series (Series), Speed Time and Distance, Percentage, Average, Profit and Loss, Simple Interest and Compound Interest, Time and Work, Pipe and Cistern, Mensuration and Geometry, Powers and Exponents (Surds and Indices), Algebra, Probability, Mental Ability, Age Problems, Partnership, Statistics, Arithmetic, Speed Mathematics and Basic Mathematics, Miscellaneous
  5. Section A: English Language & Comprehension: Vocabulary, Subject Verb Agreement (Verb Noun Agreement), Adjectives, Tenses, Comprehension / Reading Comprehension / Unseen Passages (Critical Reasoning) (Paragraph Questions), Articles, Sentence Construction, Preposition, Direct and Indirect Speech, Sentence Completion (Fill in the blanks), Sentence Re-arrangements (Para Jumbles) (Narrative Sequencing), Modals, Active Passive Voice (Voice), Sentence Correction (Error Correction), Adverb, Conjunction, Cloze Test (Cloze Passage)
  6. Section A: Hindi Language & Comprehension: भाषा, लिपि, ध्वनि, वर्ण, अक्षर, स्वर, व्यंजन, मात्रा और संयुक्ताक्षर, वर्तनी, वर्ण-विन्यास, अनुस्वार, अनुनासिक, चंद्रबिंदु और ‘र’ के रूप, शब्द, पद और शब्द-भेद, संज्ञा और सर्वनाम, विशेषण और क्रिया, लिंग, वचन, पुरुष और कारक, काल, वाच्य, वाक्य और वाक्य-भेद, संधि, समास, विलोम शब्द, पर्यायवाची शब्द, सामान्य अशुद्धियाँ, अनेक शब्दों के लिए एक शब्द, मुहावरे और लोकोक्तियाँ, अपठित गद्यांश और अपठित पद्यांश, Multi-Topic Content (Cross-Concept Material), वर्णमाला
  7. Section B: Programming, Data Structures, OOP & Java: 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, Java, OOPS with C++, Language Design, Intro to Compilers, Visual Basics, Syntax Analysis: Bottom-Up, Object Oriented Technology
  8. Section B: Computer Networks, TCP/IP & Network Security: Introduction to CN, Data Communication, DLL: Flow Control, DLL: Access Control, DLL: Error Control, Data Link Layer - Ethernet, Net Layer: IPv4 & Proto, Net Layer: IP Addressing, Transport Layer Services, TL: Congestion & UDP, Application Layer, Hardware basics, Network Access Technologies, Network Security, Society, Law & Ethics, Mobile Computing, Net Layer:Routing Protocol, Cyber Safety and Security
  9. Section B: Teaching Methodology: Child Development, Concept of Pedagogy, Theories, Inclusive Education, Experiential Pedagogy, Assessment & Evaluation, Curriculum Framework & Reforms, National Education Policy (NEP) 2020, Psychology, Teaching-Learning Process, Personality Development, Teaching Methods & Strategies, Learning and Motivation, Learners & Learning Process, Factors Affecting Teaching, Methods of Teaching, Nature, Objectives & Characteristics of Teaching, Teaching-Learning Aids & ICT Integration, Classroom Management & Communication, Evaluation, Assessment & Measurement, Curriculum & School Environment, Inclusive Education & Special Needs, Professional Development & Ethics
  10. Section B: Digital Electronics / Boolean Logic: Digital Systems & Boolean Basics, Logic Gates & Hardware, Boolean Expression, Boolean Minimization, Combinational Circuit, Sequential Circuits, Number System, Number Representation, Analog-Digital Conversion
  11. Section B: Operating Systems & Linux: Introduction to OS, Process Management, CPU Scheduling, Process Synchronization, Threads & Process Creation, Deadlock, Memory Management, Virtual Memory, File Management, Disc Scheduling, Unix OS, Linux OS, Distributed Systems, Windows OS
  12. Section B: Data Base Management System: Basics of DBMS, ER Diagram, Relational Model & Functional Dependencies, Keys & Integrity Constraints, Normalization (1NF - BCNF), Decomposition Properties & 4NF, Relational Algebra, SQL, File Organization & Indexing, Transaction Management, Concurrency Control, Database Security & Authorization, Database Recovery, Data Warehousing & Mining
  13. Section B: Internet & Web Technologies: Website, Browser & Services, Internet Fundamentals, Web Design & Development, Protocols & Services, Web Publishing & Hosting, Server Side & Security, HTML Basics, CSS, Emerging Technologies, JavaScript-Basics, .Net Programming, Electronic Data Interchange and E-Commerce, XML
  14. Section B: Computer Fundamentals, IT Basics & Architecture: Basics of COA, Cache Memory Organization, Input Output Organisation, Register Transfer and Microoperations, Control Unit Design, Programming the Basic Computer, Terms & Abbreviations, MS Office Applications, Instr Formats & Modes, Floating Point Rep, Artificial Intelligence, साइबर सुरक्षा / Cyber Safety and Security, कंप्यूटर सॉफ़्टवेयर / Computer Software, ऑपरेटिंग सिस्टम / Operating System, वर्ड प्रोसेसिंग (MS Word) / Word Processing (MS Word), कंप्यूटर नेटवर्क / Computer Networks, प्रेज़ेंटेशन (MS PowerPoint) / Presentation Software (MS PowerPoint)
  15. Section B: Python Language: Introduction to Python, Tokens, Variables, Data Types, I/O, Operators & Expressions, Control Flow & Looping, Collections & Strings, Functions & Modules, File Handling & Data Analysis
  16. Section B: Software Engineering: Fundamentals of Software Engineering, Software Requirements and Quality Assurance, Software Design, Estimation and Metrics, Software Testing, Software Maintenance and Configuration Management, extras, Fundamentals of Systems and Information Systems
  17. Section B: Design & Analysis of Algorithms: Algorithm Analysis, Time Complexity Analysis, Sorting Algorithms, Greedy Algorithms, Dynamic Programming, Minimum Spanning Trees, Shortest Path Algos, Advanced Algorithms
  18. Section B: Mathematics: Linear Algebra, Calculus, Trigonometry, Vectors, Set Theory, Functions, Relations, Propositional and Predicate Logic, Research Process Steps, Graph Theory, Number System & Place Value, Factors, Multiples, Divisibility, HCF & LCM, Mensuration — Perimeter, Area, Surface Area, Volume, Data Handling, Graphs & Probability, Coordinates & Graphs, Higher Mathematics — Trigonometry, Quadratics, Polynomials, Progressions, Statistics, Logarithms, समतल क्षेत्रमिति / Plane Mensuration, प्रतिचयन / Sampling
  19. Section B: Computer Graphics, Multimedia & Mobile Computing: Basics of Computer Graphics, 2-D Geometrical Transforms and Viewing, 3-D Object Representation, Geometric Transformations and Viewing, Multimedia
  20. Section B: Emerging Trends: Emerging Tech Trends, Knowledge Representation, Natural Language Processing, Marketing and Consumer Studies
  21. DSSSB Previous Year Paper:
  22. Business Studies and Management: Business Communication, Business Organization and Management, Financial Accounting, Business Economics, Management Information System (MIS), Knowledge Management & New Economy
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

  1. 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. 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.

  3. 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.

  4. 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.

Loading lesson…