1. Bibliographic Information

1.1. Title

The central topic of this paper is Concurrency Control Algorithms for Real-Time Database Systems.

1.2. Authors

The author of this dissertation is Juhnyoung Lee. His affiliation is the University of Virginia, where this work was submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy (Computer Science). The dissertation advisor and committee chairman was Professor Sang Son. Other committee members included Professor Jorg Liebeherr, Professor Bill Wulf, Professor Stephen Strickland, and Professor Jim French.

1.3. Journal/Conference

This work is a doctoral dissertation submitted to the Faculty of the School of Engineering and Applied Science, University of Virginia. As a dissertation, it is an academic publication but not a peer-reviewed journal or conference paper in the traditional sense, although it represents original research contributing to the field. Dissertations are typically foundational works that may lead to multiple journal or conference publications.

1.4. Publication Year

The dissertation was published in January 1994. The microfilm copy was prepared and inspected by the school, with a UTC publication timestamp of 1989-09-01T00:00:00.000Z, which likely refers to an internal processing or cataloging date for the microfilm rather than the final defense and acceptance date of the dissertation itself, which is explicitly stated as January 1994.

1.5. Abstract

This dissertation investigates and proposes concurrency control algorithms for real-time database systems (RTDBSs). The primary objective is to develop algorithms that not only maintain data consistency but also effectively meet transaction timing constraints, aiming to minimize the percentage and average lateness of deadline-missing transactions.

The research is conducted in three phases:

1. Modeling and Performance Study: The author first develops a model for an RTDBS and evaluates the performance of various concurrency control protocol classes under different operating conditions. This phase aims to understand protocol characteristics, their performance impact, and validate the RTDBS model by reconfirming previous studies.

2. New Optimistic Concurrency Control (OCC) Algorithm: Focusing on optimistic techniques, the study investigates their behavior in firm-deadline environments where tardy transactions are discarded. A new optimistic concurrency control algorithm is presented, demonstrated to outperform existing ones across a broad range of operating conditions, making it a strong candidate for a basic concurrency control mechanism in RTDBSs.

3. Deadline-Cognizant Optimistic Protocols: This phase addresses how to integrate deadline information into optimistic protocols to enhance real-time performance. A new priority-cognizant conflict resolution scheme is introduced, which is shown to significantly improve performance over priority-insensitive algorithms and surpass previously proposed priority-based conflict resolution schemes across various operating ranges.

   Throughout these phases, performance evaluation results are reported using a detailed simulation model developed in the first phase. Additionally, the dissertation explores semantic-based concurrency control to boost transaction concurrency and meet timing constraints, proposing an object-oriented data model for RTDBS and a semantic-based concurrency control mechanism that leverages the studied protocols alongside general-purpose methods.

1.6. Original Source Link

The original source link provided is /files/papers/694639bc7a7e7809d937f3dd/paper.pdf. This appears to be a local or internal file path rather than a public web link. It is likely the PDF of the dissertation.

2. Executive Summary

2.1. Background & Motivation

The core problem addressed by this dissertation is the effective management of data consistency and timing constraints in Real-Time Database Systems (RTDBSs).

• Problem Importance: RTDBSs are crucial for a wide range of applications, including program stock trading, telephone switching, network management, automated factory management, and command and control systems. These systems require timely access to data and timely responses, often dealing with temporal data whose validity decays over time. The correctness of RTDBS operations depends not only on logical computations but also on the time at which results are delivered. This distinguishes them fundamentally from conventional database systems, which primarily focus on throughput and average response time without explicit timing requirements.

• Challenges and Gaps:

  1. Impedance Mismatch: Traditional database systems and real-time systems have different assumptions and objectives. Simply integrating concepts from one into the other is not feasible; new approaches are needed for data and transaction management.
  2. Predictability vs. Speed: Real-time computing is about predictability (meeting timing constraints deterministically), not just speed. Fast computing that performs the wrong activity is not useful.
  3. Hard Deadlines Intractability: While hard deadlines (where missing a deadline can lead to catastrophe) are critical, guaranteeing them in dynamic database environments is extremely difficult. It requires static planning, pre-knowledge of resource/data requirements, and worst-case execution times, which are often unavailable or impractical in typical database systems. This limits the functionality and applicability of transactions.
  4. Soft/Firm Deadlines Focus: A majority of real-world real-time applications involve soft or firm deadlines (where value might decrease after a deadline but doesn't cause catastrophe). Most existing research and the practical need are in this area, motivating a focus on optimizing performance for these types of deadlines.
  5. Concurrency Control Adaptation: Traditional concurrency control methods (like Two-Phase Locking or Optimistic Concurrency Control) are designed for logical consistency (e.g., serializability) but are not inherently time-cognizant. They need to be tailored to explicitly incorporate timing constraints to maximize deadline adherence.

• Paper's Innovative Idea/Entry Point: The dissertation aims to bridge the gap between data consistency and timing constraints by investigating and proposing novel concurrency control algorithms specifically designed for soft and firm deadline RTDBSs. It focuses on adapting optimistic concurrency control techniques, which are generally well-suited for high concurrency, to be deadline-cognizant and minimize deadline misses and tardy times. Furthermore, it explores semantic-based concurrency control to increase concurrency beyond traditional strict serializability for RTDBSs.

2.2. Main Contributions / Findings

The primary contributions and key findings of this dissertation are structured around its three research phases and an additional investigation:

1. Comprehensive Performance Study of Concurrency Control:

   • Developed a robust real-time database system model for simulation.
   • Conducted extensive performance studies of various concurrency control protocol classes (locking vs. optimistic) under different conditions (soft/firm deadlines, finite/infinite resources).
   • Validated the model by reproducing and reconfirming results from previous studies, providing a solid foundation for subsequent research.

2. Novel Optimistic Concurrency Control (OCC) Algorithm:

   • Identified unnecessary restarts as a performance bottleneck in traditional OCC under deadline environments.
   • Proposed a new optimistic concurrency control algorithm designed to reduce these unnecessary restarts.
   • Demonstrated through simulation that this new algorithm significantly outperforms previous OCC approaches over a wide range of operating conditions, offering a promising baseline for RTDBS concurrency control.

3. Deadline-Cognizant Conflict Resolution for OCC:

   • Addressed the critical problem of incorporating deadline information into optimistic protocols.
   • Developed a new priority-cognizant conflict resolution scheme (e.g., Feasible Sacrifice). This scheme makes intelligent decisions during transaction validation, potentially sacrificing lower-priority or less-likely-to-meet-deadline transactions to enable higher-priority ones to complete.
   • Showed that this priority-cognizant approach provides considerable performance improvement over priority-insensitive algorithms and outperforms existing priority-based conflict resolution schemes across a wide operating range, effectively minimizing miss percentage and average lateness.

4. Exploration of Semantic-Based Concurrency Control:

   • Investigated semantic-based concurrency control as a means to further increase transaction concurrency and meet timing constraints, moving beyond strict serializability when appropriate.

   • Proposed an object-oriented data model specifically tailored for real-time database systems.

   • Presented a semantic-based concurrency control mechanism that leverages the previously studied real-time concurrency control protocols and general-purpose methods for compatibility relations. This opens avenues for higher concurrency by exploiting application-specific semantics.

     In summary, the dissertation provides validated insights into real-time concurrency control, proposes specific enhanced optimistic concurrency control algorithms and conflict resolution schemes that are deadline-aware, and lays groundwork for semantic-based approaches to improve RTDBS performance.

3. Prerequisite Knowledge & Related Work

3.1. Foundational Concepts

To understand this dissertation, a reader should be familiar with fundamental concepts from both database systems and real-time systems.

• Real-Time Database Systems (RTDBSs):

  • Concept: RTDBSs are database systems designed to handle data with explicit timing constraints in addition to traditional data consistency requirements. They are critical for applications where the correctness of a computation depends not only on the logical result but also on the time it is delivered.
  • Distinction from Conventional DBs: Unlike conventional databases that aim for high throughput or low average response time, RTDBSs prioritize meeting individual transaction deadlines.
  • Embedded Systems: Often, RTDBSs are part of embedded computer systems that interact with a physical environment via sensors and actuators, requiring timely processing of environmental data.

• Timing Constraints and Deadlines:

  • Concept: A timing constraint specifies when a transaction or task must complete. A deadline is the specific point in time by which a transaction must finish.
  • Value Function Model: The dissertation refers to the value function model to categorize deadlines. This model assigns a "value" or "importance" to a transaction's completion as a function of its completion time.
    • Hard Deadline: Missing a hard deadline results in a catastrophic failure or a large negative value. All transactions with hard deadlines must meet them. The dissertation argues that supporting hard deadlines dynamically is often infeasible due to lack of pre-execution information (resource needs, worst-case execution time).
    • Soft Deadline: Missing a soft deadline reduces the value of the transaction, but it still has some positive value even if completed after its deadline. The value typically drops to zero at some point past the deadline.
    • Firm Deadline: A special case of a soft deadline where the value of the transaction drops immediately to zero if its deadline is missed. Tardy transactions (those that miss their firm deadline) are typically aborted or discarded because their results are no longer useful.
  • Temporal Consistency: Beyond logical consistency, RTDBSs must maintain temporal consistency, ensuring that the data in the database accurately reflects the current state of the real-world environment it models within acceptable time limits.

• Transactions:

  • Concept: A transaction in a database system is a logical unit of work that accesses and potentially modifies data. It must be atomic, consistent, isolated, and durable (ACID properties).
  • ACID Properties (briefly):
    • Atomicity: Either all operations within a transaction complete successfully, or none do.
    • Consistency: A transaction transforms the database from one consistent state to another.
    • Isolation: The concurrent execution of multiple transactions appears as if they were executed sequentially.
    • Durability: Once a transaction commits, its changes are permanent.

• Concurrency Control:

  • Concept: Concurrency control mechanisms ensure that multiple transactions running simultaneously do not interfere with each other and maintain the logical consistency of the database.
  • Data Conflicts: Conflicts arise when transactions try to access the same data items in incompatible ways (e.g., one tries to write while another reads, or both try to write).
  • Serializability: The most widely accepted correctness criterion for concurrency control. It ensures that the final state of the database after concurrent execution is the same as if the transactions had executed in some serial (one after another) order. This prevents anomalies like lost updates or inconsistent retrievals (explained in Appendix A.1.1).

• Microfilm/Xerographic Copies: These terms refer to older reproduction technologies for documents like dissertations.

  • Microfilm: A roll or sheet of photographic film containing miniature images of document pages. It was a common method for archiving and distributing academic papers before digital formats.
  • Xerographic Copies: Photocopies made from microfilm. The abstract notes that photographs reproduce acceptably on positive microfilm or microfiche but lack clarity on xerographic copies made from the microfilm. This highlights a technical limitation of the reproduction method for the physical dissertation copy.

3.2. Previous Works

The dissertation extensively reviews concurrency control techniques, primarily categorizing them into locking, timestamp ordering, and optimistic approaches.

• Traditional Approaches to Concurrency Control (Appendix A.2):

  • Two-Phase Locking (2PL):

    • Concept: A widely used locking protocol. Transactions acquire locks on data items before accessing them. Locks are held in two phases:
      1. Growing Phase: A transaction can acquire new locks but cannot release any.
      2. Shrinking Phase: A transaction can release existing locks but cannot acquire new ones.
    • Types of Locks:
      • Shared Lock (S-lock): Allows multiple transactions to read a data item concurrently.
      • Exclusive Lock (X-lock): Grants exclusive access, allowing only one transaction to write (and read) a data item.
    • Conflict Resolution: If a transaction requests a lock that conflicts with an existing lock, it must wait. This can lead to deadlocks (a situation where two or more transactions are waiting indefinitely for each other to release locks).
    • Real-time Adaptation: In real-time systems, 2PL can suffer from priority inversion, where a high-priority transaction waits for a low-priority one to release a lock, potentially missing its deadline. Various priority-based 2PL variants (e.g., 2PL-HP - High Priority) have been proposed to address this by allowing high-priority transactions to abort conflicting low-priority ones.

  • Timestamp Ordering (TO):

    • Concept: Each transaction is assigned a unique timestamp at its initiation. This timestamp defines its serialization order.
    • Conflict Resolution: Operations are executed based on timestamps. If a transaction attempts an operation that would violate the timestamp order, it is aborted and restarted with a new (later) timestamp.
    • Variants:
      • Basic TO: Strict adherence to timestamp order; can lead to many aborts.
      • Multiversion Timestamp Ordering (MVTO): To reduce aborts, the database maintains multiple versions of data items. A read operation can access an older, consistent version, avoiding conflicts with ongoing writes, as long as the version's timestamp is appropriate for the reading transaction. Writes still create new versions and can cause aborts.

  • Optimistic Concurrency Control (OCC):

    • Concept: Based on the assumption that conflicts are rare. Transactions execute optimistically without acquiring locks during their read phase. They perform all modifications on private copies of data.
    • Phases:
      1. Read Phase: Transaction reads data items and writes any updates to a private workspace.
      2. Validation Phase: Before committing, the transaction checks for conflicts with other concurrently executing transactions. If no conflicts are detected, it proceeds.
      3. Write Phase: If validation is successful, changes from the private workspace are made permanent in the database.
    • Conflict Resolution: If a conflict is detected during validation, the transaction (or a conflicting one) is aborted and restarted.
    • Advantages: High concurrency in low-contention environments, no deadlocks.
    • Disadvantages: High restart overhead in high-contention environments, potential for livelock (a transaction repeatedly gets aborted and restarted).
    • Real-time Adaptation: Optimistic protocols are often favored in RTDBS due to their potential for high concurrency and the absence of blocking (which can exacerbate priority inversion). However, validation must be deadline-aware to ensure high-priority transactions are favored.

3.3. Technological Evolution

The evolution of database systems from conventional to real-time involves several key shifts:

1. From Batch to Interactive to Real-Time: Early databases focused on batch processing, then evolved to support interactive transactions. The demand for systems responding to real-world events in a timely manner led to the emergence of real-time systems.
2. From Logical Consistency to Timing Constraints: The primary concern of conventional databases (e.g., SQL databases) is logical consistency (ensuring data integrity and correctness, typically via ACID properties and serializability). Real-time systems added the crucial dimension of timing constraints (deadlines, periodicity).
3. The "Impedance Mismatch": Initial attempts to simply combine database management systems with real-time schedulers failed. Traditional database concurrency control algorithms (like 2PL) can cause priority inversion (a high-priority task waiting for a low-priority task) or unpredictable delays due to data blocking or restarts. Traditional real-time scheduling (e.g., Earliest Deadline First - EDF) often assumes tasks are independent or that resource conflicts are simple to resolve. Integrating these required new approaches that make concurrency control time-cognizant.
4. Focus on Soft/Firm Deadlines: Given the difficulty of guaranteeing hard deadlines in dynamic database environments, the field largely shifted its focus to soft and firm deadlines, where the goal is to maximize deadline adherence rather than guaranteeing all deadlines. This dissertation fits squarely into this evolution, aiming to improve performance for these practical real-time scenarios.

3.4. Differentiation Analysis

This dissertation differentiates itself from prior work in real-time concurrency control through several innovations:

1. Systematic Performance Analysis: Unlike many studies that might focus on a single protocol, this work systematically evaluates and compares different concurrency control protocol classes (locking vs. optimistic) under a variety of realistic RTDBS conditions (soft vs. firm deadlines, finite vs. infinite resources). This comprehensive benchmarking provides a validated foundation.

2. Novel OCC Algorithm for Reduced Restarts: The paper specifically identifies and addresses the problem of unnecessary restarts in existing optimistic concurrency control (OCC) algorithms. It proposes a new OCC algorithm that modifies the validation phase and serialization order adjustment to minimize these restarts, particularly crucial in firm-deadline environments where tardy transactions are discarded, making restarts costly. This is a direct improvement over the core mechanism of OCC.

3. Advanced Deadline-Cognizant Conflict Resolution: The key innovation lies in moving beyond simple priority inheritance or priority abort schemes to more sophisticated deadline-cognizant conflict resolution policies for optimistic protocols. The Feasible Sacrifice approach, for instance, is not just about aborting a lower-priority transaction, but making an informed decision about which transaction to abort (or restart) based on its likelihood of meeting its deadline and its impact on other transactions. This adaptive and predictive element is a significant step beyond existing priority-based schemes (like No Sacrifice, Always Sacrifice, Conservative Sacrifice, Unavoidable Sacrifice) which might be too rigid or too aggressive.

4. Integration of Semantic Information: While not the primary focus of the core concurrency control chapters, the dissertation also explores semantic-based concurrency control within an object-oriented data model. This is a departure from purely syntactic (data item-level) conflict detection and aims to exploit application-specific semantics to allow higher concurrency than strict serializability permits, without compromising logical correctness. This forward-looking aspect broadens the scope beyond purely algorithmic improvements.

   In essence, the dissertation moves beyond merely applying traditional concurrency control with priorities to real-time systems. It proposes specific algorithmic enhancements to optimistic concurrency control and introduces more intelligent, deadline-aware conflict resolution strategies that consider the actual feasibility of transactions, rather than just their static priority.

4. Methodology

This dissertation conducts its research in three primary phases, followed by an investigation into semantic-based concurrency control. The methodology revolves around designing, implementing, and simulating various concurrency control algorithms within a real-time database system (RTDBS) model.

4.1. Principles

The core principles guiding this research are:

1. Time-Cognizant Design: All proposed algorithms and modifications explicitly consider timing constraints (deadlines) of transactions, rather than solely focusing on logical consistency or average performance metrics.
2. Simulation-Based Evaluation: Due to the complexity of real-time systems and the difficulty of conducting controlled experiments on live systems, a detailed simulation model is used for performance evaluation. This allows for reproducible results under a wide range of operating conditions.
3. Optimistic Approach Preference: The research leans towards optimistic concurrency control (OCC) as a promising candidate for RTDBSs due to its inherent non-blocking nature in the read phase, which can reduce priority inversion issues common in locking protocols. The challenge then becomes optimizing its validation and conflict resolution phases to be deadline-aware.
4. Minimizing Deadline Misses: The primary performance objective is to minimize the miss percentage and average lateness of transactions, especially for soft and firm deadline systems.

4.2. Core Methodology In-depth (Layer by Layer)

4.2.1. Phase 1: Performance of Concurrency Control Algorithms (Chapter 2)

This phase establishes the baseline understanding of different concurrency control (CC) algorithms in an RTDBS context.

4.2.1.1. Concurrency Control Algorithms Under Study

The dissertation primarily focuses on two major classes of CC algorithms:

• A Locking Algorithm (Section 2.2.1):

  • Algorithm: Two-Phase Locking with High Priority (2PL-HP). This is a strict 2PL protocol enhanced with a priority mechanism.
  • Mechanism: When a transaction (T) requests a lock on a data item and the item is already locked by another transaction (T_c) in a conflicting mode, T has to wait. However, 2PL-HP incorporates priority:
    • If T has a higher priority than T_c, T_c is aborted (restarted), and its locks are released, allowing T to acquire the lock.
    • If T has a lower or equal priority to T_c, T waits for T_c to release the lock. This waiting is a form of priority inversion if T_c is lower priority.
  • Lock Management: Locks are requested before accessing data items. For writes, an exclusive lock is required. For reads, a shared lock is required. The strict aspect means all exclusive locks are held until the transaction commits.

• An Optimistic Concurrency Control Algorithm (Section 2.2.2):

  • Algorithm: Optimistic Concurrency Control with High Priority (OCC-HP). This is a basic OCC protocol adapted for real-time environments.
  • Mechanism: Transactions execute in three phases:
    1. Read Phase: A transaction reads data items and stores all writes into a private workspace without acquiring any locks.
    2. Validation Phase: When a transaction (T_v) is ready to commit, it enters the validation phase. It checks for conflicts with other active transactions.
       • T_v is validated against all transactions (T_a) that have completed their validation phase and committed since T_v started its read phase.
       • T_v is also validated against all transactions (T_r) currently in their read phase.
       • Specifically, T_v's read set (set of items read) and write set (set of items written) are checked against other transactions' read/write sets.
       • OCC-HP handles conflicts based on priority: If T_v conflicts with an active transaction T_c, and T_v has a higher priority than T_c, T_c is aborted. If T_v has lower or equal priority, T_v is aborted.
    3. Write Phase: If validation is successful, T_v's updates from its private workspace are permanently written to the database.

• Qualitative Analysis (Section 2.2.3):

  • 2PL-HP: Can suffer from priority inversion when a high-priority transaction waits for a lower-priority one. It can also lead to deadlocks if not properly handled (though 2PL-HP often uses priority abort to resolve this).
  • OCC-HP: Generally avoids priority inversion during the read phase because no locks are held. However, validation becomes a critical bottleneck. High contention can lead to many restarts, potentially causing livelock for low-priority transactions. The cost of restart is significant because all work done is discarded.

• Implementation Issues (Section 2.2.4):

  • Timestamp Assignment: Transactions are assigned timestamps upon creation, typically based on their deadlines (e.g., Earliest Deadline First - EDF). A transaction with an earlier deadline gets a higher priority (smaller timestamp).
  • Data Structures: Read set and write set are maintained for each transaction. A Commit_history is used to record information about committed transactions for OCC validation.

4.2.1.2. RTDBS Model (Section 2.3)

The simulation model represents a multi-processor, shared-memory RTDBS.

• Soft Deadline vs. Firm Deadline (Section 2.3.1):

  • Soft Deadline: Transactions that miss their deadline are still allowed to complete, and their results are accepted. The performance metric average tardy time (or average lateness) is relevant here.
  • Firm Deadline: Transactions that miss their deadline are immediately aborted and discarded because their results are no longer useful. For these systems, miss percentage is the primary performance metric.

• Resource Availability (Section 2.3.2):

  • Finite Resources: A limited number of CPUs and disks are available, leading to resource contention.
  • Infinite Resources: Assumes CPU and disk resources are unlimited, isolating data contention as the primary performance factor. This simplifies analysis to understand the pure impact of concurrency control.

4.2.1.3. Experimental Environment (Section 2.4)

The simulation model is built using CSIM, a process-oriented simulation language.

• Simulation Model (Section 2.4.1):

  • Components:
    • Transaction Generator: Creates transactions with random arrival times and assigns deadlines.
    • Transaction Manager (TM): Manages the lifecycle of transactions, including priority assignment (EDF or Value-EDF for soft deadline), and restart logic.
    • Concurrency Control Manager (CCM): Implements the chosen concurrency control protocol (2PL-HP or OCC-HP).
    • Resource Manager (RM): Manages CPU and disk resources.
    • Database: A collection of data items.
  • Transaction Flow: Transactions arrive, go through CPU processing (for logic), I/O (for data access), and interact with CCM for locking/validation.

• Parameter Setting (Section 2.4.2): The simulation uses various parameters for system resources and workload:

  The following are the results from Table 2.1 of the original paper:

  System Resource Parameters	Setting
  Number of CPUs	8
  Number of Disks	8
  CPU Speed	10 MIPS
  I/O Speed (Disk Access Time)	20 ms
  DB Size (Number of Data Items)	1000
  Page Size	4 KB

  The following are the results from Table 2.2 of the original paper:

  Workload Parameters	Setting
  Transaction Arrival Rate ($\lambda$)	10 to 100 transactions/second
  Transaction Size (Number of Operations)	10
  Write Probability ($P_W$)	0.25, 0.5, 0.75
  Deadline Factor ($D_F$)	2.0, 4.0, 6.0, 8.0, 10.0
  Restart Penalty Factor ($R_F$)	2.0
  Data Access Skew	Uniform
  Restart Probability	0

  • Transaction Arrival Rate ($\lambda$): Rate at which new transactions enter the system.
  • Transaction Size: Number of operations (read/write) per transaction.
  • Write Probability ($P_W$): The likelihood that an operation is a write operation, influencing data contention.
  • Deadline Factor ($D_F$): Controls how tight deadlines are. A transaction's deadline is calculated as: $ \text{Deadline} = \text{Arrival Time} + D_F \times \text{Execution Time} $ where Execution Time is the estimated total time for CPU and I/O operations without any contention. A smaller $D_F$ means tighter deadlines.
  • Restart Penalty Factor ($R_F$): Multiplier for the cost of restarting a transaction. When a transaction is restarted, its deadline is adjusted to reflect the wasted time.
  • Data Access Skew: How evenly data items are accessed (uniform means all items equally likely).

• Performance Metrics (Section 2.4.3):

  • Miss Percentage: The percentage of transactions that fail to commit by their deadline.
    • Conceptual Definition: This metric quantifies the effectiveness of the system in meeting timing constraints. A lower miss percentage indicates better real-time performance. It is particularly crucial for firm-deadline systems where tardy transactions are useless.
    • Mathematical Formula: $ \text{Miss Percentage} = \frac{\text{Number of transactions missing deadline}}{\text{Total number of transactions attempted}} \times 100% $
    • Symbol Explanation:
      • Number of transactions missing deadline: Count of transactions whose completion time is later than their assigned deadline.
      • Total number of transactions attempted: Total count of transactions that entered the system, including those that committed, aborted, or are still running.
  • Average Tardy Time: For soft-deadline systems, this measures the average amount of time by which transactions miss their deadline.
    • Conceptual Definition: This metric provides insight into the degree of lateness for transactions that fail to meet their timing constraints. A lower average tardy time indicates that even when deadlines are missed, they are not missed by a large margin. It's relevant when late results still have some value.
    • Mathematical Formula: $ \text{Average Tardy Time} = \frac{\sum_{i=1}^{N_{miss}} (\text{Completion Time}_i - \text{Deadline}_i)}{\text{Number of transactions missing deadline}} $
    • Symbol Explanation:
      • $N_{miss}$: Total number of transactions that missed their deadline.
      • $\text{Completion Time}_i$: The time at which transaction $i$ finished execution.
      • $\text{Deadline}_i$: The assigned deadline for transaction $i$.
  • Throughput: The number of transactions committed per second.
    • Conceptual Definition: This traditional database metric measures the efficiency of the system in processing and successfully completing transactions. Higher throughput generally means more work is being done. In real-time systems, it must be considered alongside deadline adherence.
    • Mathematical Formula: $ \text{Throughput} = \frac{\text{Number of committed transactions}}{\text{Total simulation time}} $
    • Symbol Explanation:
      • Number of committed transactions: The count of transactions that successfully completed and had their changes made permanent.
      • Total simulation time: The total duration for which the simulation was run.
  • Average Response Time: The average time from transaction arrival to completion.
    • Conceptual Definition: This metric quantifies the average total time a transaction spends in the system from its arrival until its successful completion. It includes waiting for resources, data, and execution time.
    • Mathematical Formula: $ \text{Average Response Time} = \frac{\sum_{i=1}^{N_{commit}} (\text{Completion Time}_i - \text{Arrival Time}i)}{N{commit}} $
    • Symbol Explanation:
      • $N_{commit}$: Total number of committed transactions.
      • $\text{Completion Time}_i$: The time at which transaction $i$ finished execution.
      • $\text{Arrival Time}_i$: The time at which transaction $i$ entered the system.
  • Restart Count: The average number of times a transaction is restarted due to concurrency control conflicts.
    • Conceptual Definition: This metric directly reflects the overhead caused by conflict resolution, particularly in optimistic concurrency control where aborts and restarts are the primary mechanism. A high restart count indicates significant wasted work.
    • Mathematical Formula: $ \text{Restart Count} = \frac{\text{Total number of transaction restarts}}{\text{Total number of committed transactions}} $
    • Symbol Explanation:
      • Total number of transaction restarts: The cumulative count of all times transactions were aborted and re-initiated.
      • Total number of committed transactions: The count of transactions that successfully completed.
  • Data Blocking Time: The average time a transaction spends waiting for a lock due to data conflicts.
    • Conceptual Definition: This metric is specific to locking-based concurrency control and quantifies the amount of time transactions are stalled due to data contention. It directly impacts response time and can indicate priority inversion issues.
    • Mathematical Formula: (Not explicitly provided in the paper, but commonly defined as) $ \text{Data Blocking Time} = \frac{\sum_{i=1}^{N_{blocked}} \text{Wait Time}i}{N{blocked}} $
    • Symbol Explanation:
      • $N_{blocked}$: Number of times a transaction was blocked.
      • $\text{Wait Time}_i$: The duration for which a transaction was blocked during the $i$-th blocking instance. (Or, alternatively, sum of wait times for all transactions, divided by number of transactions).

4.2.2. Phase 2: Dynamic Adjustment of Serialization Order (Chapter 3)

This phase focuses on improving optimistic concurrency control by dynamically adjusting the serialization order to reduce unnecessary restarts.

4.2.2.1. Optimistic Concurrency Control Principles (Section 3.2.1)

Reiterates the three phases of OCC: Read Phase, Validation Phase, and Write Phase. The key is that validation determines if a transaction can commit without violating serializability.

4.2.2.2. Unnecessary Restarts (Section 3.2.2)

• Problem: Traditional OCC protocols (like OCC-HP) make decisions about restarts based on a fixed serialization order (e.g., determined by timestamp at arrival). If an active transaction T_a conflicts with a validating transaction T_v, and T_v has an earlier serialization order (higher priority), T_a is typically aborted. However, T_a might have already completed a significant amount of work or might be a high-priority transaction itself that could still meet its deadline. Aborting it might be "unnecessary" if an alternative serialization order could be found or if T_v is likely to miss its deadline anyway.

4.2.2.3. A New Optimistic Concurrency Control Algorithm (Section 3.3)

The proposed algorithm, called Dynamic Adjustment of Serialization Order (DASO-OCC), aims to avoid unnecessary restarts by allowing a validating transaction to yield to a younger, conflicting active transaction if that transaction has a higher priority or is more likely to meet its deadline. This effectively allows for a dynamic adjustment of the serialization order.

• Validation Phase (Section 3.3.1):

  • When a transaction T_v (validating transaction) reaches its validation phase, it checks for conflicts with committed transactions and active transactions.
  • Against Committed Transactions (T_c): T_v validates against all T_c that committed while T_v was in its read phase. If T_v reads an item written by T_c or T_v writes an item read by T_c, and T_c's commit time is before T_v's start time, there is no conflict. Otherwise, if T_v has an older serialization order (earlier timestamp) than T_c, and there's an actual conflict (e.g., T_v's write set intersects T_c's read set), T_v must be aborted to maintain serializability.
  • Against Active Transactions (T_a): This is where DASO-OCC differentiates.
    • Conflict Detection: T_v checks its write set against T_a's read set, and T_v's read set against T_a's write set.
    • Priority and Serialization Order Comparison:
      • If T_v has a higher priority (earlier deadline) than T_a, and they conflict, T_a is aborted (standard OCC-HP behavior).
      • If T_v has a lower or equal priority than T_a, this is where DASO-OCC introduces its dynamic adjustment. Instead of immediately aborting T_v (as OCC-HP would), DASO-OCC tries to preserve T_v if possible by letting T_a commit first, effectively letting T_a have an earlier serialization order than T_v, even if T_v arrived earlier.
    • Yielding Mechanism: If T_v's serialization order (defined by its timestamp) is earlier than T_a's, but T_a has a higher priority or is more critical, T_v can yield.
      • T_v sets a yielding flag and waits. This implies T_a can commit first.
      • When T_a later validates, it will see T_v's yielding flag. If T_a successfully validates, T_v might need to restart from the beginning, but with a potentially improved serialization order (later timestamp) that avoids repeated conflicts with T_a.
      • If T_a is aborted for other reasons, T_v might then be able to proceed with its original validation.
    • The algorithm dynamically calculates a wait_for_commit_time (WFC) for T_v. T_v will wait for conflicting transactions that have higher priority (or meet certain criteria) to commit. If these transactions don't commit by WFC, T_v then proceeds with its own validation, potentially aborting them. The objective is to maximize the chance of committing high-priority transactions.

• Read Phase (Section 3.3.2): Standard OCC read phase. Transaction reads data, stores updates in a private workspace.

• Write Phase (Section 3.3.3): Standard OCC write phase. If validation is successful, changes are made permanent.

• Correctness (Section 3.3.4): The algorithm maintains serializability by ensuring that for any two conflicting transactions T_i and T_j, if T_i's commit time is before T_j's commit time, then T_i's serialization order is also before T_j's. This is achieved through the careful handling of timestamps and restarts during the validation phase. The yield mechanism effectively allows an earlier-timestamped transaction (T_v) to commit after a later-timestamped transaction (T_a) if T_v yields, thus dynamically adjusting their effective serialization order without violating serializability for the final committed state.

• Discussion (Section 3.3.5): The DASO-OCC algorithm introduces a new tradeoff: allowing validating transactions to wait (yield) instead of immediately aborting. This waiting can reduce restarts but might increase response time for the waiting transaction. The goal is to make this wait decision intelligent based on priorities and expected deadlines.

4.2.3. Phase 3: Design of Real-Time Optimistic Concurrency Control (Chapter 4)

This phase focuses on deadline-cognizant conflict resolution within optimistic protocols, building on the OCC-HP framework but introducing more sophisticated sacrifice policies.

4.2.3.1. The Choice of Optimistic Protocol (Section 4.2)

The dissertation re-affirms the choice of optimistic protocols for RTDBS due to their non-blocking nature in the read phase, which minimizes priority inversion compared to locking. The challenge is that restarts are costly, so conflict resolution must be intelligent.

4.2.3.2. Deadline-Cognizant Conflict Resolution Policies (Section 4.3)

These policies are variations on how a validating transaction (T_v) resolves conflicts with an active transaction (T_a) in the read phase. The policies decide which transaction, if any, should be sacrificed (aborted).

• No Sacrifice (NS) (Section 4.3.1):

  • Mechanism: If T_v conflicts with T_a:
    • If T_v has higher priority than T_a, T_a is aborted.
    • If T_v has lower or equal priority than T_a, T_v is aborted.
  • Characteristic: This is the standard OCC-HP behavior. It's priority-sensitive but makes immediate decisions without further analysis of deadline feasibility.

• Always Sacrifice (AS) (Section 4.3.2):

  • Mechanism: If T_v conflicts with T_a:
    • If T_v has higher priority than T_a, T_a is aborted.
    • If T_v has lower or equal priority than T_a, T_v is still aborted.
  • Characteristic: This policy always sacrifices the lower priority transaction, which is T_v if its priority is lower. It's aggressive in favoring higher priority transactions, potentially leading to livelock for low-priority transactions.

• Conservative Sacrifice (CS) (Section 4.3.3):

  • Mechanism: If T_v conflicts with T_a:
    • If T_v has higher priority than T_a, T_a is aborted.
    • If T_v has lower or equal priority than T_a, T_v is aborted.
  • Characteristic: This seems to be identical to No Sacrifice based on the description, implying a default behavior for lower priority. It might imply a more cautious approach where a transaction is only sacrificed if it must be. The paper's text here seems to be an oversight or a repetition of NS. Self-correction: Given the context, CS might imply that T_v aborts only if it's strictly necessary to preserve an active higher priority transaction, but the description doesn't elaborate further distinguishing it from NS.

• Unavoidable Sacrifice (US) (Section 4.3.4):

  • Mechanism: If T_v conflicts with T_a:
    • If T_v has higher priority than T_a, T_a is aborted.
    • If T_v has lower or equal priority than T_a, T_v is aborted.
  • Characteristic: Again, the description is identical to No Sacrifice. This suggests that these terms NS, AS, CS, US might refer to specific algorithms from prior work that the author is comparing against, rather than distinct new policies introduced in this section. The actual distinction is subtle and likely involves how "sacrifice" is defined in context of other system state or transaction properties beyond simple priority. Self-correction: The names NS, AS, CS, US, Adaptive Sacrifice are referenced in related work (Hari90b, Hari91b), so they are indeed existing baseline policies for comparison.

• Adaptive Sacrifice (ADS) (Section 4.3.5):

  • Mechanism: If T_v conflicts with T_a:
    • If T_v has higher priority than T_a, T_a is aborted.
    • If T_v has lower or equal priority than T_a:
      • T_v is aborted if it is unlikely to meet its deadline, or if T_a is likely to miss its deadline without T_v's sacrifice.
      • T_v is committed (and T_a is potentially aborted) if T_v is likely to meet its deadline and T_a is unlikely to meet its deadline even with T_v's sacrifice.
  • Characteristic: This policy attempts to make a more intelligent decision by considering the slack or remaining execution time relative to the deadline for both transactions. It tries to save transactions that have a higher chance of meeting their deadline.

4.2.3.3. Our Approach (Section 4.4)

The dissertation proposes a new approach called Feasible Sacrifice (FS) for deadline-cognizant conflict resolution.

• Feasible Sacrifice (FS) (Section 4.4.1):

  • Principle: When a validating transaction (T_v) conflicts with an active transaction (T_a) in its read phase, the decision to sacrifice (abort) one of them is based on whether either transaction (or both) can realistically meet its deadline if allowed to proceed.
  • Mechanism:
    1. Direct Priority Check: If T_v has higher priority than T_a, T_a is aborted.
    2. Feasibility Check for Lower Priority T_v: If T_v has lower or equal priority than T_a, instead of immediately aborting T_v (as in NS/AS), FS performs a feasibility check.
       • It estimates the remaining execution time for both T_v and T_a.
       • It calculates the slack time for each: Deadline - Current Time - Remaining Execution Time.
       • If T_v is found to be feasible (i.e., has positive slack, indicating it can meet its deadline) and T_a is infeasible (i.e., has negative slack, indicating it cannot meet its deadline even if T_v is aborted), then T_a is aborted, and T_v is allowed to commit. This is a crucial difference: a lower-priority T_v can abort a higher-priority T_a if T_a is already doomed to miss its deadline, preventing wasted work.
       • Otherwise, if T_v is infeasible or T_a is feasible (or both), T_v is aborted. The logic is that if T_v cannot meet its deadline, it should be aborted, or if T_a can meet its deadline, it should be favored.

• Predictable Transaction Execution (Section 4.4.2):

  • Feasible Sacrifice relies on predicting transaction execution time and slack. The paper discusses how to estimate this.
  • Slack Calculation: $ \text{Slack}(T) = \text{T.deadline} - \text{current_time} - \text{remaining_exec_time}(T) $
    • Symbol Explanation:
      • $\text{Slack}(T)$: The amount of time transaction $T$ has left before its deadline, beyond its estimated remaining execution time. A positive slack means it can likely meet its deadline.
      • $\text{T.deadline}$: The deadline assigned to transaction $T$.
      • $\text{current\_time}$: The current time in the simulation.
      • $\text{remaining\_exec\_time}(T)$: The estimated CPU and I/O time required for $T$ to complete its remaining operations.
  • Feasible Transaction: A transaction $T$ is considered feasible if its $\text{Slack}(T) > 0$.
  • The predictive nature of FS helps in making more informed decisions about sacrificing transactions, reducing unnecessary restarts and maximizing the number of completed transactions that meet their deadlines.

4.2.4. Semantic-Based Concurrency Control (Chapter 5)

This chapter explores an alternative paradigm to traditional syntactic concurrency control by leveraging application semantics to achieve higher concurrency.

4.2.4.1. An Object-Oriented Data Model for RTDBS (Section 5.2)

• Basic Concepts: An object-oriented approach is chosen because it allows for richer data modeling and encapsulation of methods, which can be leveraged for semantic-based concurrency control.

• Object Model (Section 5.2.2): Data is organized into objects, each with its own state (attributes) and behavior (methods). Classes define the structure and behavior of objects.

• Relationship Model (Section 5.2.3): Defines how objects are related to each other (e.g., aggregation, inheritance, association).

• Transaction Model (Section 5.2.4): Transactions in this model operate by invoking methods on objects. Each method invocation can be considered a sub-transaction.

• Example (Section 5.2.5): A real-time database schema example is provided (Figure 5.1), illustrating classes like Control-Objects, Sensor-Objects, Actuator-Objects, and their relationships.

  

  Figure 5.1 An Object-Oriented Real-Time Database Schema This figure visually represents a hierarchical structure for an object-oriented real-time database, including Control-Objects, Sensor-Objects, and Actuator-Objects, with relationships indicating their interactions within the system.

4.2.4.2. Design Issues (Section 5.3)

• Compatibility Relation (Section 5.3.1): Instead of simple read/write conflicts, method invocations are classified as compatible or incompatible based on their semantics. For example, two increment operations on a counter might be compatible even if they both modify the same data.
• Concurrency Control Algorithms (Section 5.3.2): Traditional CC algorithms need to be adapted to operate on method-level compatibility rather than data-item-level conflicts.
• Inter-Object Data Consistency (Section 5.3.3): Maintaining consistency across related objects becomes crucial when allowing finer-grained concurrency.

4.2.4.3. Our Approach (Section 5.5)

• Compatibility Relation by Affected-Set (Section 5.5.1):

  • Principle: The compatibility of two methods is determined by their affected-sets. An affected-set for a method is the set of data items that the method reads or writes.
  • Mechanism: Two methods $M_1$ and $M_2$ are compatible if, for any data item $X$ in their respective affected-sets:
    • If $X$ is read by $M_1$ and read by $M_2$, they are compatible.
    • If $X$ is written by $M_1$ and read by $M_2$, they are compatible if the semantic dependencies allow.
    • If $X$ is written by $M_1$ and written by $M_2$, they are compatible if the semantic dependencies allow.
  • This generalizes the read/write conflict matrix. It allows for non-serializable but semantically correct executions, e.g., allowing two deposit operations on an account to commute.

• Real-Time Concurrency Control Algorithms (Section 5.5.2): The semantic-based compatibility information can be integrated into the optimistic and locking protocols developed in previous chapters. For example, during validation in OCC, instead of checking for raw read/write set intersections, the system would check for semantic incompatibility between method invocations. This can reduce the number of detected conflicts and thus restarts, leading to higher concurrency and better deadline adherence.

  The overall methodology combines theoretical design of algorithms with extensive simulation to validate their practical performance in real-time database systems under various constraints, moving from general performance analysis to specific algorithmic enhancements and finally to more abstract semantic approaches.

5. Experimental Setup

The experimental setup described in the dissertation relies heavily on a simulation model to evaluate the performance of the proposed concurrency control algorithms for real-time database systems (RTDBSs).

5.1. Datasets

Instead of using traditional datasets, the paper utilizes a simulated database and transaction workload.

• Simulated Database:

  • Scale: The database consists of 1000 data items. Each data item represents a page of 4KB size.
  • Characteristics: The data items are accessed uniformly, meaning there is no data access skew towards specific popular items, which simplifies the analysis of concurrency control overhead.
  • Domain: The simulation is general-purpose and not tied to a specific application domain, allowing for broader applicability of the findings.

• Simulated Transaction Workload:

  • Source: Transactions are generated by a Transaction Generator component of the simulation model.
  • Arrival Pattern: Transactions arrive at the system according to a Poisson distribution, with a configurable Transaction Arrival Rate ($\lambda$) ranging from 10 to 100 transactions/second.
  • Transaction Size: Each transaction executes 10 operations (read or write).
  • Write Probability ($P_W$): The probability that any given operation is a write operation is varied (0.25, 0.5, 0.75). A higher write probability generally leads to higher data contention.
  • Deadlines: Each transaction is assigned a deadline based on its arrival time, an estimated execution time (without contention), and a Deadline Factor ($D_F$). $ \text{Deadline} = \text{Arrival Time} + D_F \times \text{Execution Time} $ The Deadline Factor ($D_F$) is varied (2.0, 4.0, 6.0, 8.0, 10.0) to simulate different tightness of deadlines, with smaller values indicating tighter deadlines.
  • Restart Penalty Factor ($R_F$): When a transaction is restarted, its deadline is adjusted to reflect the time lost, multiplied by $R_F = 2.0$. This simulates the real cost of restarting transactions.
  • Data Access: Each operation accesses a random data item from the 1000 available items.

• Resource Configuration:

  • The System Resource Parameters for finite resource experiments include 8 CPUs and 8 Disks.
  • CPU Speed is 10 MIPS (Millions of Instructions Per Second).
  • I/O Speed (Disk Access Time) is 20 ms.
  • For infinite resource experiments, CPU and disk resources are assumed to be unlimited, to isolate the effects of data contention.

5.2. Evaluation Metrics

The dissertation uses several performance metrics to evaluate the concurrency control algorithms:

1. Miss Percentage:

   • Conceptual Definition: This metric quantifies the effectiveness of the system in meeting timing constraints. A lower miss percentage indicates better real-time performance. It is particularly crucial for firm-deadline systems where tardy transactions are useless.
   • Mathematical Formula: $ \text{Miss Percentage} = \frac{\text{Number of transactions missing deadline}}{\text{Total number of transactions attempted}} \times 100% $
   • Symbol Explanation:
     • Number of transactions missing deadline: Count of transactions whose completion time is later than their assigned deadline.
     • Total number of transactions attempted: Total count of transactions that entered the system, including those that committed, aborted, or are still running.

2. Average Tardy Time:

   • Conceptual Definition: For soft-deadline systems, this measures the average amount of time by which transactions miss their deadline. A lower average tardy time indicates that even when deadlines are missed, they are not missed by a large margin. It's relevant when late results still have some value.
   • Mathematical Formula: $ \text{Average Tardy Time} = \frac{\sum_{i=1}^{N_{miss}} (\text{Completion Time}_i - \text{Deadline}_i)}{\text{Number of transactions missing deadline}} $
   • Symbol Explanation:
     • $N_{miss}$: Total number of transactions that missed their deadline.
     • $\text{Completion Time}_i$: The time at which transaction $i$ finished execution.
     • $\text{Deadline}_i$: The assigned deadline for transaction $i$.

3. Throughput:

   • Conceptual Definition: This traditional database metric measures the efficiency of the system in processing and successfully completing transactions. Higher throughput generally means more work is being done. In real-time systems, it must be considered alongside deadline adherence.
   • Mathematical Formula: $ \text{Throughput} = \frac{\text{Number of committed transactions}}{\text{Total simulation time}} $
   • Symbol Explanation:
     • Number of committed transactions: The count of transactions that successfully completed and had their changes made permanent.
     • Total simulation time: The total duration for which the simulation was run.

4. Average Response Time:

   • Conceptual Definition: This metric quantifies the average total time a transaction spends in the system from its arrival until its successful completion. It includes waiting for resources, data, and execution time.
   • Mathematical Formula: $ \text{Average Response Time} = \frac{\sum_{i=1}^{N_{commit}} (\text{Completion Time}_i - \text{Arrival Time}i)}{N{commit}} $
   • Symbol Explanation:
     • $N_{commit}$: Total number of committed transactions.
     • $\text{Completion Time}_i$: The time at which transaction $i$ finished execution.
     • $\text{Arrival Time}_i$: The time at which transaction $i$ entered the system.

5. Restart Count:

   • Conceptual Definition: This metric directly reflects the overhead caused by conflict resolution, particularly in optimistic concurrency control where aborts and restarts are the primary mechanism. A high restart count indicates significant wasted work.
   • Mathematical Formula: $ \text{Restart Count} = \frac{\text{Total number of transaction restarts}}{\text{Total number of committed transactions}} $
   • Symbol Explanation:
     • Total number of transaction restarts: The cumulative count of all times transactions were aborted and re-initiated.
     • Total number of committed transactions: The count of transactions that successfully completed.

6. Data Blocking Time:

   • Conceptual Definition: This metric is specific to locking-based concurrency control and quantifies the average amount of time a transaction spends stalled due to data contention (waiting for a lock). It directly impacts response time and can indicate priority inversion issues.
   • Mathematical Formula: (As per common definition, not explicitly given in paper) $ \text{Data Blocking Time} = \frac{\sum_{i=1}^{N_{blocked}} \text{Wait Time}i}{N{blocked}} $
   • Symbol Explanation:
     • $N_{blocked}$: Number of times a transaction was blocked.
     • $\text{Wait Time}_i$: The duration for which a transaction was blocked during the $i$-th blocking instance.

5.3. Baselines

The paper compares its proposed algorithms against several baseline concurrency control (CC) algorithms:

• For general CC performance (Chapter 2):

  • Two-Phase Locking with High Priority (2PL-HP): A traditional locking-based protocol that incorporates priority for conflict resolution.
  • Optimistic Concurrency Control with High Priority (OCC-HP): A basic optimistic protocol that uses priority for validation conflicts.

• For novel Optimistic CC (Chapter 3):

  • OCC-HP: The standard optimistic protocol with priority is used as a baseline to demonstrate the improvements of DASO-OCC (Dynamic Adjustment of Serialization Order Optimistic Concurrency Control).

• For Deadline-Cognizant Conflict Resolution (Chapter 4):

  • Existing priority-based conflict resolution schemes for optimistic concurrency control are used as baselines, including:

    • No Sacrifice (NS)
    • Always Sacrifice (AS)
    • Conservative Sacrifice (CS)
    • Unavoidable Sacrifice (US)
    • Adaptive Sacrifice (ADS)

  • These baselines represent different strategies for aborting transactions during validation based on their priorities and, in some cases, estimated slack. The proposed Feasible Sacrifice (FS) is compared against these.

    These baselines are representative as they cover both major concurrency control paradigms (locking and optimistic) and include several established priority-cognizant variants for real-time systems.

6. Results & Analysis

The results are presented across different experimental setups, varying deadline types (soft vs. firm), resource availability (finite vs. infinite), and workload characteristics (arrival rate, write probability, deadline factor).

6.1. Core Results Analysis

6.1.1. Experiment 1: Soft Deadline and Finite Resources (Section 2.5.1)

• Figure 2.3 Miss Percentage, Finite Resource, Soft Deadline:

  

  This figure plots the Miss Percentage for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under soft deadline and finite resource conditions.

  • Analysis: At low arrival rates (low contention), both 2PL-HP and OCC-HP have similar, low miss percentages. As the arrival rate increases, OCC-HP generally shows a lower miss percentage than 2PL-HP. This indicates that OCC-HP is more effective at meeting deadlines under moderate to high load in soft-deadline environments with finite resources. This is likely due to OCC's non-blocking nature in the read phase, reducing priority inversion compared to 2PL's blocking.

• Figure 2.4 Average Tardy Time, Finite Resource, Soft Deadline:

  

  This figure plots the Average Tardy Time for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under soft deadline and finite resource conditions.

  • Analysis: Similar to miss percentage, OCC-HP generally exhibits lower average tardy time than 2PL-HP at higher arrival rates. This reinforces the finding that OCC-HP not only misses fewer deadlines but also misses them by a smaller margin when it does.

• Figure 2.5 Throughput, Finite Resource, Soft Deadline:

  

  This figure plots the Throughput for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under soft deadline and finite resource conditions.

  • Analysis: OCC-HP consistently achieves higher throughput than 2PL-HP, especially at higher arrival rates. This suggests that the non-blocking nature of OCC allows more transactions to progress, leading to a higher rate of completed transactions.

• Figure 2.6 Average Response Time, Finite Resource, Soft Deadline:

  

  This figure plots the Average Response Time for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under soft deadline and finite resource conditions.

  • Analysis: OCC-HP generally has lower average response time than 2PL-HP. The ability to process transactions without waiting for locks during the read phase in OCC contributes to faster completion times on average.

6.1.2. Experiment 2: Soft Deadline and Infinite Resources (Section 2.5.2)

• Figure 2.7 Miss Percentage, Infinite Resource, Soft Deadline:

  

  This figure plots the Miss Percentage for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under soft deadline and infinite resource conditions.

  • Analysis: With infinite resources (eliminating resource contention), OCC-HP shows a more pronounced advantage over 2PL-HP in terms of miss percentage. This highlights that data contention (handled by CC mechanisms) is the primary factor differentiating their performance, and OCC-HP handles it more effectively in this scenario.

• Figure 2.8 Average Tardy Time, Infinite Resource, Soft Deadline:

  

  This figure plots the Average Tardy Time for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under soft deadline and infinite resource conditions.

  • Analysis: Similar to miss percentage, OCC-HP maintains a lower average tardy time in the infinite resource scenario, further emphasizing its efficiency in handling data contention.

• Figure 2.9 Throughput, Infinite Resource, Soft Deadline:

  

  This figure plots the Throughput for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under soft deadline and infinite resource conditions.

  • Analysis: OCC-HP consistently delivers higher throughput, especially at high arrival rates. This confirms that with resource contention removed, OCC-HP's ability to minimize data blocking and priority inversion allows for more transaction completions.

• Figure 2.10 Data Blocking Time, Infinite Resource, Soft Deadline:

  

  This figure plots the Data Blocking Time for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under soft deadline and infinite resource conditions.

  • Analysis: OCC-HP has virtually zero data blocking time (as expected, since it doesn't use locks in the read phase), whereas 2PL-HP shows significant and increasing data blocking time with higher arrival rates. This directly explains 2PL-HP's poorer performance.

• Figure 2.11 Miss Percentage, Soft Deadline:

  

  This figure compares Miss Percentage between finite and infinite resource scenarios for both 2PL-HP and OCC-HP under soft deadline conditions.

  • Analysis: This figure aggregates insights, showing that OCC-HP generally performs better than 2PL-HP in soft-deadline systems, both with and without resource contention. The performance difference is more pronounced when resource contention is eliminated, isolating the impact of data contention on which OCC-HP excels.

6.1.3. Experiment 3: Firm Deadline and Finite Resources (Section 2.5.3)

• Figure 2.12 Miss Percentage, Finite Resource, Firm Deadline:

  

  This figure plots the Miss Percentage for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under firm deadline and finite resource conditions.

  • Analysis: For firm deadlines (where tardy transactions are aborted), OCC-HP still generally outperforms 2PL-HP in terms of miss percentage at higher arrival rates. However, the miss percentages are significantly higher overall compared to soft deadlines, as any missed deadline counts as an aborted transaction.

• Figure 2.13 Restart Count, Finite Resource, Firm Deadline:

  

  This figure plots the Restart Count for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under firm deadline and finite resource conditions.

  • Analysis: OCC-HP shows a higher restart count than 2PL-HP at higher arrival rates. This is a critical trade-off: OCC avoids data blocking but pays the price in restarts. While OCC-HP has a lower miss percentage, its higher restart count indicates wasted work, which is a target for improvement in subsequent chapters.

6.1.4. Experiment 4: Firm Deadline and Infinite Resources (Section 2.5.4)

• Figure 2.14 Miss Percentage, Infinite Resource, Firm Deadline:

  

  This figure plots the Miss Percentage for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under firm deadline and infinite resource conditions.

  • Analysis: With infinite resources, OCC-HP maintains its advantage in miss percentage over 2PL-HP for firm-deadline systems, similar to the soft-deadline case. This again points to data contention as the key differentiator.

• Figure 2.15 Restart Count, Infinite Resource, Firm Deadline:

  

  This figure plots the Restart Count for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under firm deadline and infinite resource conditions.

  • Analysis: OCC-HP still incurs a significantly higher restart count than 2PL-HP when resource contention is removed. This confirms that the problem of high restarts in OCC is primarily due to data contention and its validation strategy, not resource contention.

• Figure 2.16 Data Blocking Time, Infinite Resource, Firm Deadline:

  

  This figure plots the Data Blocking Time for 2PL-HP and OCC-HP algorithms against Transaction Arrival Rate under firm deadline and infinite resource conditions.

  • Analysis: As expected, OCC-HP shows minimal data blocking time, while 2PL-HP exhibits substantial data blocking, reinforcing the inherent differences in their conflict resolution mechanisms.

• Figure 2.17 Miss Percentage, Firm Deadline:

  

  This figure compares Miss Percentage between finite and infinite resource scenarios for both 2PL-HP and OCC-HP under firm deadline conditions.

  • Analysis: Similar to soft deadlines, OCC-HP generally performs better than 2PL-HP for firm deadlines, with a more pronounced difference under infinite resources. However, the firm deadline context highlights the restart cost of OCC, motivating the need for DASO-OCC and Feasible Sacrifice.

6.1.5. Dynamic Adjustment of Serialization Order (Chapter 3)

• Figure 3.1 Miss Percentage, Finite Resource, Write Probability = 0.25:

  

  This figure compares Miss Percentage for OCC-HP and DASO-OCC under finite resources and $P_W = 0.25$.

  • Analysis: DASO-OCC consistently achieves a lower miss percentage than OCC-HP, especially at higher arrival rates. This demonstrates the effectiveness of dynamically adjusting the serialization order to reduce unnecessary restarts and allow more transactions to meet their deadlines.

• Figure 3.2 Restart Count, Finite Resource:

  

  This figure compares Restart Count for OCC-HP and DASO-OCC under finite resources.

  • Analysis: DASO-OCC significantly reduces the restart count compared to OCC-HP. This is the direct mechanism by which DASO-OCC improves miss percentage: by making more intelligent decisions during validation and allowing transactions to yield or be reordered, it avoids aborting transactions that could still complete.

• Figure 3.3 Miss Percentage, Finite Resource, Write Probability = 0.75:

  

  This figure compares Miss Percentage for OCC-HP and DASO-OCC under finite resources and $P_W = 0.75$ (high contention).

  • Analysis: With very high write probability (meaning high data contention), DASO-OCC still maintains a lower miss percentage than OCC-HP, though the absolute miss percentages are higher for both algorithms due to increased contention. This shows the robustness of DASO-OCC even in demanding environments.

• Figure 3.4 Restart Count, Finite Resource, Write Probability = 0.75:

  

  This figure compares Restart Count for OCC-HP and DASO-OCC under finite resources and $P_W = 0.75$.

  • Analysis: The reduction in restart count by DASO-OCC is even more dramatic under high write probability. This suggests that unnecessary restarts are a bigger problem in high-contention scenarios, and DASO-OCC's mechanism is particularly effective there.

• Figure 3.5 Miss Percentage, Infinite Resource, Write Probability = 0.5:

  

  This figure compares Miss Percentage for OCC-HP and DASO-OCC under infinite resources and $P_W = 0.5$.

  • Analysis: The performance gains of DASO-OCC over OCC-HP are maintained under infinite resources, indicating that its improvements are primarily related to data contention and concurrency control logic, rather than resource contention.

• Figure 3.6 Restart Count, Infinite Resource, Write Probability = 0.5:

  

  This figure compares Restart Count for OCC-HP and DASO-OCC under infinite resources and $P_W = 0.5$.

  • Analysis: DASO-OCC significantly reduces restart counts even when resource contention is not a factor, further confirming its effectiveness in optimizing concurrency control decisions.

6.1.6. Design of Real-Time Optimistic Concurrency Control (Chapter 4)

This section evaluates the Feasible Sacrifice (FS) policy against other deadline-cognizant conflict resolution schemes.

• Figure 4.2 Miss Percentage, Finite Resource, Write Probability = 0.25:

  

  This figure compares Miss Percentage for various OCC conflict resolution policies (NS, AS, CS, US, ADS, FS) under finite resources and $P_W = 0.25$.

  • Analysis: The proposed Feasible Sacrifice (FS) policy consistently achieves the lowest miss percentage across all arrival rates. Adaptive Sacrifice (ADS) is the second best. The more aggressive policies (AS) initially perform well but degrade quickly, while simpler policies (NS, CS, US) perform worse. This demonstrates that intelligent, predictive sacrifice decisions based on transaction feasibility are superior.

• Figure 4.3 Miss Percentage, Infinite Resource, Write Probability = 0.5:

  

  This figure compares Miss Percentage for various OCC conflict resolution policies under infinite resources and $P_W = 0.5$.

  • Analysis: Even with infinite resources, FS maintains its lead, indicating its robust performance in handling data contention and making optimal conflict resolution decisions independent of resource contention. ADS remains the second best.

• Figure 4.4 Miss Percentage, Finite Resource, Write Probability = 0.75:

  

  This figure compares Miss Percentage for various OCC conflict resolution policies under finite resources and $P_W = 0.75$ (high contention).

  • Analysis: Under high write probability, FS's advantage becomes even more pronounced, especially at high arrival rates. This highlights its effectiveness in environments with significant data conflicts, where making correct sacrifice decisions is crucial to minimize wasted work and meet deadlines.

• Figure 4.5 Miss Percentage, Infinite Resource, Write Probability = 1.0:

  

  This figure compares Miss Percentage for various OCC conflict resolution policies under infinite resources and $P_W = 1.0$ (extremely high contention).

  • Analysis: With all operations being writes and infinite resources, FS continues to outperform other policies, though the absolute miss percentages are very high due to extreme data contention. This further validates FS's robust decision-making under severe conflict conditions.

• Figure 4.6 Miss Percentage, Finite Resource, Arrival Rate = 20 tran/sec:

  

  This figure compares Miss Percentage for various OCC conflict resolution policies against Write Probability under finite resources and $Arrival Rate = 20 tran/sec$.

  • Analysis: At a fixed, moderate arrival rate, FS consistently shows the lowest miss percentage across varying write probabilities. Its performance degrades less severely than other policies as write probability increases.

• Figure 4.7 Miss Percentage, Infinite Resource, Arrival Rate = 40 tran/sec:

  

  This figure compares Miss Percentage for various OCC conflict resolution policies against Write Probability under infinite resources and $Arrival Rate = 40 tran/sec$.

  • Analysis: Similar to Figure 4.6, FS maintains its superior performance across write probabilities even with infinite resources, confirming its effectiveness in optimizing conflict resolution decisions.

6.2. Data Presentation (Tables)

The paper provides its parameters in tables, which were transcribed in the Experimental Setup section. No other result tables are present in the provided content. All results are presented graphically.

6.3. Ablation Studies / Parameter Analysis

While the paper doesn't explicitly frame experiments as "ablation studies," it implicitly performs several types of parameter analysis:

• Resource Availability: Comparing finite vs. infinite resources (Experiments 1 vs. 2, and 3 vs. 4) helps isolate the impact of data contention versus resource contention on CC algorithm performance. For example, the enhanced performance of OCC-HP over 2PL-HP is more pronounced with infinite resources, suggesting its strength lies in managing data conflicts.

• Deadline Type: Comparing soft vs. firm deadlines (Experiments 1 & 2 vs. 3 & 4) shows how the system behaves when tardy transactions are tolerated versus discarded. Firm deadline scenarios typically lead to higher miss percentages but highlight the criticality of restart count for OCC.

• Contention Level: Varying Transaction Arrival Rate ($\lambda$) and Write Probability ($P_W$) across experiments allows for evaluating algorithm robustness under different data contention levels. For instance, DASO-OCC and Feasible Sacrifice demonstrate greater improvements under higher contention, indicating their value in stress-testing scenarios.

• Deadline Tightness: The Deadline Factor ($D_F$) is a parameter (Table 2.2), although the results figures primarily vary arrival rate and write probability. This parameter would show how algorithm performance changes when deadlines are very tight versus loose.

  These variations allow the author to understand the conditions under which each algorithm performs best and to highlight the specific advantages of the proposed methods (DASO-OCC and Feasible Sacrifice) in optimizing for real-time constraints under varying resource and data contention scenarios. The consistent outperformance of the proposed algorithms across these diverse conditions strongly validates their effectiveness.

7. Conclusion & Reflections

7.1. Conclusion Summary

This dissertation provides a comprehensive investigation into concurrency control algorithms for real-time database systems (RTDBSs), focusing on soft and firm deadline environments. The key findings and contributions are:

1. Systematic Performance Analysis: The research established a robust RTDBS simulation model and conducted thorough performance comparisons of locking (2PL-HP) and optimistic (OCC-HP) concurrency control protocols. It was consistently found that OCC-HP generally outperforms 2PL-HP in terms of miss percentage, average tardy time, throughput, and average response time, especially under moderate to high contention and when resource contention is not the dominant factor. This validated the choice of optimistic concurrency control as a promising direction for RTDBS.

2. Novel Optimistic Concurrency Control Algorithm (DASO-OCC): The dissertation introduced Dynamic Adjustment of Serialization Order Optimistic Concurrency Control (DASO-OCC). This algorithm intelligently reduces unnecessary restarts in optimistic protocols by allowing for dynamic adjustment of the serialization order during the validation phase. Simulation results demonstrated that DASO-OCC significantly lowers miss percentage and restart count compared to OCC-HP across various operating conditions, making it a more efficient base mechanism for RTDBSs.

3. Advanced Deadline-Cognizant Conflict Resolution (Feasible Sacrifice): Building on the strengths of optimistic protocols, the research proposed Feasible Sacrifice (FS), a new priority-cognizant conflict resolution scheme. FS makes intelligent decisions about sacrificing (aborting) transactions based not just on static priorities, but on the feasibility of transactions meeting their deadlines. It was shown that FS consistently achieves the lowest miss percentage compared to existing priority-based conflict resolution schemes (e.g., NS, AS, CS, US, ADS), particularly under high data contention.

4. Exploration of Semantic-Based Concurrency Control: The dissertation also explored semantic-based concurrency control within an object-oriented data model for RTDBS. By defining compatibility relations based on method semantics and affected-sets, it laid the groundwork for achieving higher concurrency than traditional serializability-based methods, further enhancing the ability to meet timing constraints.

   Overall, the dissertation successfully identifies limitations in existing concurrency control approaches for RTDBS, proposes innovative optimistic concurrency control algorithms that are highly deadline-aware, and provides a strong foundation for future research in semantic-based approaches.

7.2. Limitations & Future Work

The author explicitly identifies future research directions at the end of the dissertation:

1. More Realistic Performance Evaluation Models: The current simulation model uses a generic RTDBS. Future work could incorporate more realistic aspects such as:

   • Modeling hot spots in the database (non-uniform data access patterns).
   • Considering varying transaction sizes and access patterns.
   • Integrating main-memory database architectures, which are becoming prevalent in real-time systems.

2. Further Refinements to Optimistic Protocols:

   • Dynamic Adaptation: Investigating how the parameters and behavior of DASO-OCC and Feasible Sacrifice can be dynamically tuned at runtime based on current system load and contention levels.
   • Hybrid Approaches: Exploring hybrid concurrency control protocols that combine elements of locking and optimistic approaches to leverage the strengths of both, especially in mixed workload environments (e.g., some transactions requiring strict guarantees, others more flexible).

3. Advanced Semantic-Based Concurrency Control:

   • Detailed Implementation: Developing a more detailed implementation and evaluation of the semantic-based concurrency control mechanism proposed in Chapter 5. This would involve defining a comprehensive set of compatibility relations for various object methods and rigorously testing their impact on performance and correctness.
   • Integration with Real-Time Scheduling: How semantic-based concurrency control interacts with real-time scheduling policies at a deeper level (e.g., priority assignment, resource allocation).

4. Handling Hard Real-Time Transactions: Despite the dissertation's focus on soft and firm deadlines, the author acknowledges that supporting hard deadlines remains a challenge. Future work could explore restricted environments or specialized approaches (e.g., static analysis, resource reservation) to provide guarantees for critical hard real-time transactions within a database context.

7.3. Personal Insights & Critique

This dissertation offers a rigorous and insightful deep dive into a critical area of real-time systems.

• Strengths and Inspirations:

  • Rigorous Foundation: The initial comprehensive performance study (Chapter 2) of 2PL-HP and OCC-HP is a strong foundation. Validating the simulation model by reconfirming previous results adds credibility to the subsequent novel contributions. This systematic approach is a valuable lesson for any research.
  • Practical Relevance of Soft/Firm Deadlines: The pragmatic focus on soft and firm deadlines is highly relevant to real-world applications, acknowledging the inherent difficulties of strictly hard real-time guarantees in dynamic database environments. This grounds the research in practical applicability.
  • Targeted Innovation in OCC: The identification of unnecessary restarts as a key problem in OCC and the subsequent development of DASO-OCC and Feasible Sacrifice demonstrate keen analytical ability. These solutions are not just incremental changes but address core inefficiencies in existing optimistic protocols by introducing more intelligent, deadline-aware decision-making. The Feasible Sacrifice policy, in particular, showcases a sophisticated understanding of real-time constraints by prioritizing not just static priority but also the actual likelihood of meeting a deadline.
  • Forward-Looking Semantic Approaches: The inclusion of semantic-based concurrency control indicates a broader vision beyond traditional approaches. This concept is highly valuable for domains where application-specific knowledge can relax strict serializability without sacrificing correctness, potentially unlocking significantly higher concurrency. This idea could be applied in various modern distributed systems, not just RTDBS.

• Potential Issues, Unverified Assumptions, or Areas for Improvement:

  • Predicting Execution Time: The Feasible Sacrifice algorithm heavily relies on estimating remaining execution time and slack. In real-world, complex database systems, accurately predicting execution time can be extremely challenging due to variable I/O latencies, CPU caching, operating system interference, and dynamic data access patterns. The simulation assumes relatively predictable execution times. The robustness of FS in environments with highly unpredictable execution times would be an important area for further investigation.

  • Overhead of Feasibility Checks: While FS makes smarter decisions, the additional computation required for slack calculation and feasibility checks during the validation phase could introduce its own overhead. The dissertation shows performance benefits, implying this overhead is outweighed, but its magnitude in extremely high-contention or very tight deadline scenarios would be worth detailed analysis.

  • Homogeneous Workload Assumption: The simulation often assumes a uniform data access pattern and fixed transaction size. Real-world workloads are often heterogeneous, with hot spots and varying transaction complexities. The performance of these algorithms might differ significantly under such conditions.

  • Interplay with OS Scheduling: The simulation abstracts away many operating system scheduling details. The interaction between the database's priority-driven concurrency control and the underlying operating system scheduler could introduce complexities (e.g., a high-priority database transaction being descheduled by the OS).

  • Generalizability of Semantic-Based CC: While promising, the semantic-based concurrency control remains at a conceptual level in this dissertation. Its practical implementation requires significant effort in defining affected-sets and compatibility relations for diverse application methods, which can be application-specific and complex to manage.

    This dissertation represents a substantial contribution to the understanding and advancement of concurrency control in real-time database systems, particularly for the widely applicable soft and firm deadline paradigms. The proposed DASO-OCC and Feasible Sacrifice algorithms offer practical improvements, and the exploration of semantic-based approaches points towards exciting future directions for achieving even higher performance in complex real-time environments.