|Notice: Exam Form BE IV/II & BAR V/II (Back) for 2076 Magh
|Routine: BE IV/II & BAR V/II - 2076 Magh
|Result: BCE I/II exam held on 2076 Bhadra
|Result: All (except BCE & BEI) I/II exam held on 2076 Bhadra
|Notice: Exam Center for Barrier Exam (2076 Poush), 1st Part
|Electronics and Communication(BEX)
- Transaction is a single logical unit of operation which on collection performs some meaningful actions.
- The system should ensure proper execution of transactions
- Either the entire transaction executes or none of them executes
- The system also manages concurrent execution of transactions
- Each transaction access and possible updates various data items.
- Either the entire transaction completes or none of it completes
- Transaction is indivisible
- Execution of transaction must preserve database consistency
- If a transaction runs from a consistent database state. The database must be in consistent state after the end of transaction
- A transaction should not appear its effects on other concurrent transactions
- Each transaction must operate properly without interference from concurrent operations.
- For a pair of Ti and Tj it appears to Ti that either Tj finished execution before Ti started or Tj started execution after T: templates.
- The changes made to the database by a transaction must be persistent even if the system fails or crashes
- Active state : the transaction is executing in the state
- Partially commited: the final statement has been executed.
- Commited : the transaction is completely successfully.
- Failed: Normal execution can not be proceed.
- Aborted:Transaction is rolled back and database is restored
- The system allows multiple transactions to run concurrently
- It increase cpu and data utilization increasing throughputs.
- It reduces the average response time of transaction
- Concurrency control scheme must be formulated to control interaction among transactions to prevent database consistency
- Schedule is the sequence of instructions that specify chronological order in which instructions of concurred transactions are executed.
- It must preserve the consistency of the database.
Example of Schedule
Consider the given figure:
- A schedule is serial if for every transaction participating in the schedule , all operations of a transaction executed consecutively in the schedule
- A schedule is serializable if it is not serial but is equivalent to some serial schedule of same transactions
- Two schedules are result equivalent if they produce the same final state of the database
Forms of Schedule Equivalence
1) Conflict serializablity
- To actions Ai and Aj executed on same data object by Ti and Tj conflicts if either one of them is write operation
- If Ai and Aj are consecutive non conflicting actions belonging to Ti and Tj we can swap Ai an Aj without changing result
- If schedule S can be transformed to S by a series of Swap m, S and S’ are conflict equivalent
- A schedule S is conflict serializable , if it is conflict equivalent to a serial schedule.
Test for conflict serializability
- For each transaction Ti in schedule S create a node labeled T: in the precedence graph
- For each case in S where Tj executes write(X) , create edge (Ti – Tj )
- For each case in S where where Tj executes write(X) after Ti – Tj )
- S is serializable if graph has no cycle.
- The two schedules S2 and S2 are view equivalent if:
- For each data item Q if transaction T: reads initial value of Q in S1 then tranactions Ti must read initial value of B in S2
- For each data item Q If ti reads Q after Tj writes Q in S1 then T1 must read B after Ti writes Q in S2
- For each data item Q, if Ti writes final value of Q in S1 , then Ti must writes final value of Q in S2
- A schedule is view serializable if it is view equivalent to a serial schedule.
T1 : r1(Q) , w1(Q)
T2 : w2 (Q)
T3: w3 (Q)
Schedule S: r1(Q) , w2(Q) ,W1(Q) ,w3(Q)
Let s be serial schedule : s’ : r1(q), w2(q), w1(q), w3(q)
T1 reads initial value of Q in S and s’
T3 writes final value of Q in S and S’
S is view serializable.
- A schedule is recoverable if a transaction Tj reads a data item previously written by Transaction Ti then Ti should commit before Tj commits.
- Cascading rollback is a mechanism that performs a series of transaction rollbacks if a single transaction fails
- Cascade less schedule is the schedule in which for each pair of transactions Ti and Tj such that Tj reads data item previously written by Ti , Tj must commit before Tj reads.
Lock Based Protocols
- It is a protocol that ensures that when one transaction is accessing a data item , no other transaction can modify that data item with the use of locks
- A lock based protocol is a set of rules followed by all the transactions while requesting and releasing locks
- The transaction holding the lock on that item can only access that data item.
- Locks can be in two modes. The transaction holding shared mode lock (lock-s) can only read data item. - The transaction holding exclusive mode lock (lock-x) can both read and write data item
Lock compatibility Matrix
- Transaction request concurrency control manager for locks.
- A transaction may be granted a lock an item if request lock is compatible with locks already held on the item by other transactions.
- Any no of transactions can hold shared locks on an item
- If lack us not granted , the requesting transaction must wait
Two phase locking Protocol
Phase 1 : Growing phase
- Transaction may obtain locks
- Transaction may not release locks.
Phase 2 : Shrinking phase
- Transaction may release locks
- Transaction may not obtain locks.
- It results in deadlock
- It may cause cascading rollback (Use strict two phase locking )
- Rigorous two phase locking (holds all locks until commit)
- It is a mechanism for upgrading a shared lock to exclusive lock and downgrading an exclusive lock to a shared lock.
- Upgrade takes place in growing phase
- Downgrade takes place in shrinking phase.
- It assures serializability
Implementation of lock conversion
- Lock manager replies to a lock request by sending lock grant message
- In case of deadlock it sends msg asking for rollback
- The requesting transaction waits until its request is answered
- It maintains data structure called lock table
- Lock table is in memory hash table indexed on name of data being locked
- Lock table also records type of lock granted or requested
- New requests added to the end of queue
- If transaction aborts , all of its requests are deleted
Deadlock Handling and Prevention
Deadlock is the condition in which all transactions in a set are holding locks to some data items and waiting for locks to other data items being currently held by other transactions of some set
1. Ensure no cyclic waits
- All locks should be acquired together before execution
- Ordering requests for locks
2. No wait
- Wait-die scheme/rollback (T: waits only if it has time stamp smaller than that of Tj otherwise rolled back
- Wound wait scheme
- Timeout based scheme
- Deadlock can be described as a wait for graph G- (V,E)
- V is for all transactions
- E is edges showing Ti- Tj
- If ti – Tj is in E , there is directed edge from Ti to Tj Implying that Ti is waiting for Tj to release the lock.
- The system is in deadlock if wait-for graph has a cycle.