This question appears in Mumbai University > Parallel And Distributed System subject

Marks: 10 M

Year: Dec 2015

• A phantom read occurs when, in the course of a transaction, two identical queries are executed, and the collection of rows returned by the second query is different from the first.
• This can occur when range locks are not acquired on performing a SELECT ... WHERE operation.
• The phantom reads anomaly is a special case of Non-repeatable reads when Transaction 1 repeats a ranged SELECT ... WHERE query and, between both operations, Transaction 2 creates (i.e. INSERT) new rows (in the target table) which fulfill that WHERE clause.

• Note that Transaction 1 executed the same query twice. If the highest level of isolation were maintained, the same set of rows should be returned both times, and indeed that is what is mandated to occur in a database operating at the SQL SERIALIZABLE isolation level.
• However, at the lesser isolation levels, a different set of rows may be returned the second time.
• In the SERIALIZABLE isolation mode, Query 1 would result in all records with age in the range 10 to 30 being locked, thus Query 2 would block until the first transaction was committed. In REPEATABLE READ mode, the range would not be locked, allowing the record to be inserted and the second execution of Query 1 to include the new row in its results. Distributed Deadlock Detection Algorithm
  1. Chandy-Misra-Hass Detection Algorithm
  2. This is considered an edge-chasing, probe-based algorithm.
  3. It is also considered one of the best deadlock detection algorithms for distributed systems.
  4. If a process makes a request for a resource which fails or times out, the process generates a probe message and sends it to each of the processes holding one or more of its requested resources.
  5. Each probe message contains the following information:
• the id of the process that is blocked (the one that initiates the probe message);
• the id of the process is sending this particular version of the probe message; and
• the id of the process that should receive this probe message.
  • When a process receives a probe message, it checks to see if it is also waiting for resources.
  • If not, it is currently using the needed resource and will eventually finish and release the resource.
  • If it is waiting for resources, it passes on the probe message to all processes it knows to be holding resources it has itself requested.
  • The process first modifies the probe message, changing the sender and receiver ids.
  • If a process receives a probe message that it recognizes as having initiated, it knows there is a cycle in the system and thus, deadlock.
  • The following example is based on the same data used in the Silberschatz-Galvin algorithm example.
  • In this case P1 initiates the probe message, so that all the messages shown have P1 as the initiator.
  • When the probe message is received by process P3, it modifies it and sends it to two more processes.
  • Eventually, the probe message returns to process P1.Deadlock!

• The advantages of this algorithm include the following:
  • It is easy to implement
  • Each probe message is of fixed length.
  • There is very little computation.
  • There is very little overhead.
  • There is no need to construct a graph, nor to pass graph information to other sites.
  • This algorithm does not find false (phantom) deadlock.
  • There is no need for special data structures.