Construction Of DFA

 

Construction Of DFA-

 

Type-01 Problems-

 

In Type-01 problems -  ending with a particular substring.

 

Steps to construct DFA-

 

Step-01:

 

• Determine the minimum number of states required in the DFA.
• Draw those states.

 

Use the following rule to determine the minimum number of states-

 

RULE Calculate the length of substring. All strings ending with ‘n’ length substring will always require minimum (n+1) states in the DFA.

 

Step-02:

 

• Decide the strings for which DFA will be constructed.
• The method for deciding the strings has been discussed in this Video.

 

Step-03:

 

• Construct a DFA for the strings decided in Step-02.

 

Remember the following rule while constructing the DFA-

 

RULE While constructing a DFA, Always prefer to use the existing path. Create a new path only when there exists no path to go with.

 

Step-04:

 

• Send all the left possible combinations to the starting state.
• Do not send the left possible combinations over the dead state.

 

 Bankers Algorithm:

• Banker’s Algorithm is a deadlock avoidance strategy.
• It is called so because it is used in banking systems to decide whether a loan can be granted or not.

 Banker’s Algorithm requires-
               Whenever a new process is created, it specifies the maximum number of instances of each resource type that it exactly needs.

DataStructures used in bankers alogorithm

Available:

• It is a 1-d array of size ‘m’ indicating the number of available resources of each type. 

• Available[j] = k means there are ‘k’ instances of resource type Rj 

Max: 

• It is a 2-d array of size ‘n*m’ that defines the maximum demand of each process in a system.

• Max[i,j] = k means process Pi may request at most ‘k’ instances of resource type Rj.

Allocation: 

• It is a 2-d array of size ‘n*m’ that defines the number of resources of each type currently allocated to each process. 

• Allocation [i, j] = k means process Pi is currently allocated ‘k’ instances of resource type Rj.

 Need: 

• It is a 2-d array of size ‘n*m’ that indicates the remaining resource need of each process. 

• Need [i, j] = k means process Pi currently need ‘k’ instances of resource type Rj for its execution. 

• Need [i,j] = Max [i, j] – Allocation [i, j]

Problems on Bankers algorithm:

1Q.A single processor system has three resource types X, Y and Z, which are shared by three processes. There are 5 units of each resource type. Consider the following scenario, where the column alloc denotes the number of units of each resource type allocated to each process, and the column request denotes the number of units of each resource type requested by a process in order to complete execution. Which of these processes will finish LAST?

1. P0
2. P1
3. P2
4. None of the above since the system is in a deadlock

Deadlocks In Operating system for Gate CSE

 DeadLocks

A Deadlock is a situation where each of the computer processes waits for a resource which is being assigned to some other process. In this situation, none of the process gets executed since the resource it needs is held by some other process which is also waiting for some other resource to be released.

Example for deadlock:

There are following 4 necessary conditions for the occurrence of deadlock-

1. Mutual Exclusion
2. Hold and Wait
3. No preemption
4. Circular wait
   
   

1. Mutual Exclusion

• There must exist at least one resource in the system which can be used by only one process at a time.
• If there exists no such resource, then deadlock will never occur.
• Printer is an example of a resource that can be used by only one process at a time

2. Hold and wait

• There must exist a process which holds some resource and waits for another resource held by some other process.

3. No preemption

• Once the resource has been allocated to the process, it can not be preempted.
• It means resource can not be snatched forcefully from one process and given to the other process.
• The process must release the resource voluntarily by itself.

4. circular wait

• All the processes must wait for the resource in a cyclic manner where the last process waits for the resource held by the first process.

NOTE

• All these 4 conditions must hold simultaneously for the occurrence of deadlock.
• If any of these conditions fail, then the system can be ensured deadlock free.

Deadlock Handling Strategies

1. Deadlock Prevention
2. Deadlock Avoidance
3. Deadlock Detection and Recovery
4. Deadlock Ignorance

Formulas on Deadlock:

Maximum Number Of Units That Ensures Deadlock-

Maximum number of units of resource R that ensures deadlock

= (x₁-1) + (x₂-1) + (x₃-1) + …. + (x_n-1)

= ( x₁ + x₂ + x₃ + …. + x_n ) – n

= ∑x_i – n

= Sum of max needs of all n processes – n

Minimum Number Of Units That Ensures No Deadlock-

Minimum number of units of resource R that ensures no deadlock

= One more than maximum number of units of resource R that ensures deadlock

= (∑x_i – n) + 1

 

Problems on no. of resources required
1Q. A system is having 3 user processes each requiring 2 units of resource R. The minimum number of units of R such that no deadlock will occur-

 Ans: 4

2Q. A system is having 8 user processes each requiring 3 units of resource R. The minimum number of units of R such that no deadlock will occur _____.

Ans: 17

Problems on no. of processes required

3Q. If there are 6 units of resource R in the system and each process in the system requires 3 units of resource R, then how many processes can be present at maximum so that no deadlock will occur?

Ans: 

• Process P1 holds 2 units of resource R
• Process P2 holds 2 units of resource R
• Process P3 holds 2 units of resource R

 

Therefore,

• Minimum number of processes that ensures deadlock = 3
• Maximum number of processes that ensures no deadlock = 3 – 1 = 2

4Q. If there are 100 units of resource R in the system and each process in the system requires 4 units of resource R, then how many processes can be present at maximum so that no deadlock will occur?

Ans: 

• Process P1 holds 3 units of resource R
• Process P2 holds 3 units of resource R
• Process P3 holds 3 units of resource R and so on.
• Process P33 holds 3 units of resource R
• Process P34 holds 1 unit of resource R

 

Thus,

• Minimum number of processes that ensures deadlock = 34
• Maximum number of processes that ensures no deadlock = 34 – 1 = 33

Next article: Bankers algorithm