Serializability theory in transaction management is a concept that ensures even when multiple transactions are executed concurrently in a database, the final result will appear as if they were executed one after another in a sequential order, preventing data inconsistencies and maintaining a database integrity; essentially, it guarantees that the outcome of concurrent transactions is the same as if they were executed serially (one at a time).
Key points about serializability theory:
1. Concurrency Control: Database management systems (DBMS) use concurrency control mechanisms to achieve serializability by managing the order in which transactions access shared data, ensuring no conflicts arise between concurrent transactions.
2. Schedules and Histories: A “schedule” represents the order in which operations (reads and writes) of multiple transactions are executed, and a “history” is a particular sequence of operations within a schedule.
3. Serial Schedule: A schedule where transactions are executed one after another, without any interleaving of operations, is called a serial schedule.
4. Conflict Serializability: A widely used concept where a schedule is considered serializable if it can be transformed into a serial schedule by swapping non-conflicting operations between transactions.
5. Checking Serializability: To determine if a schedule is serializable, algorithms analyze the “conflict graph” which represents dependencies between transactions based on read/write operations on shared data. Deadlock management is an important aspect of ensuring smooth transaction processing and resource allocation in database systems. The strategies and challenges for managing deadlocks differ between
centralized and distributed systems due to their distinct architectures and environments.
Deadlock Management in Centralized Systems:
1. Detection:
o Wait-for Graph (WFG): A centralized system can use a wait-for graph to detect
deadlocks. Nodes in the graph represent transactions, and edges represent waiting
relationships. A cycle in the graph indicates a deadlock.
o Resource Allocation Graph (RAG): Another approach is to use a resource allocation
graph, where nodes represent both transactions and resources, and edges represent
allocation and request relationships. A cycle in this graph also indicates a deadlock.
2. Prevention:
o Timestamp Ordering: Transactions are assigned timestamps, and a transaction can only wait for other transactions with earlier timestamps. This prevents circular wait
conditions.
o Resource Ordering: Resources are assigned unique orderings, and transactions request resources in a specific order to prevent circular waits.
3. Avoidance:
o Banker’s Algorithm: This algorithm checks whether granting a resource request will keep the system in a safe state. If not, the request is denied to avoid deadlock.
4. Recovery:
o Transaction Rollback: If a deadlock is detected, one or more transactions are rolled back (aborted) to break the deadlock cycle. The transactions can be restarted later.
Deadlock Management in Distributed Systems:
1. Detection:
o Distributed Wait-for Graph (DWFG): Each node in the distributed system maintains its own local wait-for graph. Periodically, nodes communicate and merge their local graphs to detect cycles, indicating deadlocks.
o Global Wait-for Graph (GWFG): A coordinator node collects wait-for information from all nodes to construct a global wait-for graph. Cycles in this graph indicate deadlocks.
2. Prevention:
o Timestamp Ordering: Similar to centralized systems, transactions are assigned
timestamps, and they can only wait for transactions with earlier timestamps to prevent
circular waits.
o Timeout Mechanism: Transactions are assigned timeouts. If a transaction waits for a
resource beyond its timeout period, it is aborted, thus preventing deadlocks.
3. Avoidance:
o Path-Pushing Algorithm: Each node maintains information about possible deadlock
paths. When a transaction requests a resource, the system checks if the request will lead to a deadlock based on these paths.
o Wait-Die and Wound-Wait Schemes: These are priority-based schemes where older
transactions are given priority over younger transactions to avoid deadlocks.
4. Recovery:
o Transaction Rollback: Similar to centralized systems, transactions involved in a deadlock are rolled back to break the deadlock cycle. In distributed systems, choosing which transactions to roll back can be more complex due to the need to coordinate across multiple nodes.
Comparision summary:
| Aspect | Centralized Systems | Distributed Systems |
|---|---|---|
| Detection | Uses simple graphs to track waiting transactions | Uses global or distributed graphs to find deadlocks |
| Prevention | Follows a fixed order for transactions | Uses timestamps or time limits to prevent waiting loops |
| Avoidance | Checks if a transaction is safe before running | Uses special rules to control waiting |
| Recovery | Cancels (rolls back) blocked transactions | Cancels transactions across multiple locations |
Thus, serializability ensures that concurrent transactions produce the same result as if executed one by one, maintaining database integrity. Effective deadlock management in both centralized and distributed systems is crucial for smooth transaction processing and resource allocation.