DBMS Notes

mobiprep (6).png

Database Management System

mobiprep (6).png

Data Modeling

mobiprep (6).png

Database Architecture

mobiprep (6).png

Relational Model

mobiprep (6).png

Relational Algebra

mobiprep (6).png

Entity Relationship Model

mobiprep (6).png

Functional Dependencies

mobiprep (6).png

Normalization

mobiprep (6).png

Transaction And Concurrency Control

mobiprep (6).png

Deadlock

mobiprep (6).png

Files and Storage

mobiprep (6).png

Indexing

Heading

Q

1

Define Deadlock.

LRM_EXPORT_207556595493866_20190724_1939

Ans

Deadlock is a condition in which a group of processes are waiting for the resources held by some other process, while holding a resource which is required by the other process. Under such condition, none of the processes can proceed further in execution. Hence, these processes are blocked.

LRM_EXPORT_207556595493866_20190724_1939

Q

2

What are the different methods of recovery from Deadlock?

LRM_EXPORT_207556595493866_20190724_1939

Ans

Once the deadlock is detected, the system must be recovered from deadlock.
The following are the three methods of data recovery after deadlock:
1. Preemption:
By preemption, the resources held by a process are taken back to avoid deadlock. The resources taken are given to another process that is waiting for that resource. By doing so, the ‘Hold and Wait’ condition is eliminated and the system can recover from deadlock.
2. Kill the Process:
Another method of removing deadlock is by killing the processes one by one. After killing each process, the existence of deadlock is checked. If the deadlock still exists, this process is continued. The processes are killed until the system is free from deadlock.
3. Rollback
The different states of the process are recorded by the Operating System. When a deadlock occurs, the processes are rolled back to their previous states. If the system is free from the deadlock in any of the previous states of a process, then, the process is rolled back to that particular state. In this way, the system can be freed from deadlock.


LRM_EXPORT_207556595493866_20190724_1939

Q

3

Give a real world scenario of Deadlock

LRM_EXPORT_207556595493866_20190724_1939

Ans

Consider a bridge which can allow only one vehicle to pass across it at a time (The width of the bridge is narrow). When two vehicles try to cross the bridge from opposite directions, a deadlock occurs. Neither of the two vehicles can move further. Here, we consider the bridge as the resource and the vehicles as processes.

LRM_EXPORT_207556595493866_20190724_1939

Q

4

What are the necessary conditions for Deadlock to occur?

LRM_EXPORT_207556595493866_20190724_1939

Ans

For a deadlock to occur in a system when all the following conditions hold:
1. Mutual exclusion
Mutual exclusion is a condition in which only one process can hold a resource at a time.
2. Hold and Wait
A process holds a resource until it gets another resource.
3. No pre-emption
A process does not give-up a resource before it has completed execution.
4. Circular wait
Circular wait condition occurs when a group of processes are waiting for the resources held by each other in a circular fashion.

LRM_EXPORT_207556595493866_20190724_1939

Q

5

How can we prevent Deadlock?

LRM_EXPORT_207556595493866_20190724_1939

Ans

Deadlock can be prevented by making one of the below four conditions False.
i. Mutual Exclusion
ii. Hold and Wait
iii. No pre-emption
iv. Circular Wait
a. Mutual Exclusion
The mutual exclusion condition can be violated if a resource is used by more than one process at a time. But, removing the mutual exclusion condition is impossible as it might lead to un-sharable resources.
b. Hold and Wait
Hold and wait condition can be prevented by preventing a process from holding a resource or by preventing the process from waiting for a resource. Such a condition can be achieved by the allocation of necessary resources before the execution of a process.
c. No pre-emption
Pre-emption can be achieved by stopping a process while execution and taking away the resource held by that process. But, this is not an advisable approach.
d. Circular Wait
Circular wait can be avoided by assigning a number to each resource and each process. A process should not be able to request a resource with a number less than itself. This ensures the prevention of the circular wait condition.

LRM_EXPORT_207556595493866_20190724_1939

Q

6

What is the Deadlock avoidence?

LRM_EXPORT_207556595493866_20190724_1939

Ans

Deadlock avoidance is different from deadlock prevention. In deadlock avoidance, our aim is to avoid unsafe states. Deadlock avoidance methods allocate resources to the processes only if the system remains in the safe state. Safe state refers to the condition in which deadlock cannot occur. The most commonly used deadlock avoidance algorithm is the ‘Banker’s Algorithm’

LRM_EXPORT_207556595493866_20190724_1939

Q

7

What is Wait-For-Graph?

LRM_EXPORT_207556595493866_20190724_1939

Ans

Wait-for-graph method is used for deadlock detection. This method involves the transaction graph. A transaction graph is drawn by considering the transactions and their lock on the resource. If a cycle is detected in the graph, then deadlock is said to exist in the system. Else, there is no deadlock.
Example:In the above transaction graph, a cycle exists. Hence, the system is in deadlock.

LRM_EXPORT_207556595493866_20190724_1939

Q

8

Discuss the drawback of Deadloack avoidance algorithm?

LRM_EXPORT_207556595493866_20190724_1939

Ans

The following are the disadvantages of deadlock avoidance algorithm:
a. The deadlock avoidance algorithms are not efficient because they cause unwanted delays while trying to avoid the unsafe states.
b. It is applicable to only limited number of resources and processes.
c. It does not completely prevent deadlock. So, deadlock might occur.

LRM_EXPORT_207556595493866_20190724_1939

Q

9

Explain Banker's algorithm in detail with data structure

LRM_EXPORT_207556595493866_20190724_1939

Ans

The Banker’s algorithm is a deadlock avoidance algorithm which checks for safe state. It simulates the resource allocation before actually allocating the resources to the processes. Hence, it detects the possible un-safe states and avoids deadlock.
Need matrix:
The need matrix shows the resources which are needed by the processes, but still are not allocated.
Safety Algorithm:
The safety algorithm is used to find whether the given system is safe or not.
Let Work and Finish be vectors of length ‘m’ and ‘n’ respectively.
Initialize: Work = Available
Finish[i] = false; for i=1, 2, 3, 4….n

2) Find an i such that both
a) Finish[i] = false
b) Need i<= Work
if no such i exists goto step (4)
3) Work = Work + Allocation[i]
Finish[i] = true
goto step (2)
4) if Finish [i] = true for all i then the system is in a safe state
Resource Request Algorithm
1) If Request i &lt;= Need,
iGoto step (2); otherwise, raise an error
2) If Request i &lt;= Available Goto step (3);
otherwise, P i must wait
3) Have the system pretend to have allocated the requested resources to process
P,by modifying the state as follows:
Available = Available – Request i
Allocation i = Allocation i + Request i
Need i = Need i – Request i

Need Matrix:
Need [i, j] = Max [i, j] – Allocation [i, j]
By applying the safety algorithm, we find that the system is safe

LRM_EXPORT_207556595493866_20190724_1939