Implementation of Atomic operations

1. Dekker's Algorithm

• needs atomic read and writes to main memory
• Hard to implement if more than two transactions are involved
• Use busy waiting

2. Spin- Lock

• Need hardware support – should be able lock bus (communication channel between CPU and memory + any other devices) for two memory cycles (one for reading and one for writing). During this time no other devices’ access is allowed to this memory location.
• use busy waiting
• Algorithm does not depend on the number of processes
• Efficient if the lock contentions are low

Deadlock

In deadlock situation, each member of the deadlock processes is waiting for another member to release the resources it wants

• Solution:

1. Have enough resources so that no waiting occurs
2. Linearly order the resources and request of resources should follow this order.
3. Periodically check the resource dependency graph for cycles
4. Allow a transaction to wait ofr certain maximum time on a lock and force it to rollback

Probability of Deadlocks

• Assumption
  1. number of transactions n+1 = n where n is large
  2. each transaction access r locks exclusively
  3. Total number of records in the database = R
  4. On average each transaction is holding r/2 locks approximately

  5. Average number of locks taken by the other n transactions = n*(r/2)

     
     
     
     
     Capture.PNG