What is meant by Deadlock? List the necessary conditions for arising deadlocks?

Consider two competing processes or actions in a situation where both of them wait for each other to be done and so neither of them ever finish. Such a situation is called a deadlock. 

- When the number of competing processes is exactly two, then it is said to be a ‘deadly embrace’. 

- The two involved competing actions tend to move towards some sort of tragedy which might be mutual extinction or mutual death. 

"In operating systems a situation occurs where two threads or processes enter the waiting state at the same time because of the resource that they both want is being used by some other process that also in waiting state for some resource being held by another process in waiting state and so on". 

- It so happens that the process is then unable to change its state since the resources it requires are being used by the other processes which is then keeping the process in waiting state indefinitely. 

- The system is now in a deadlock. 

- Systems such as the distributed systems, parallel computing systems, multi-processing systems face the problem of being in a deadlock quite often. 

- This is so because here the hardware and software locks are purposed for handling the resources that are shared and implementing the process synchronization. 

- Deadlocks may also occur in telecommunication systems because of the corrupt signals and their loss rather than resource contention. 

- A deadlock situation can be compared to problems such as that of the catch-22 or chicken or egg problem. 

- A deadlock can also occur in a circular chain pattern. 

- For example, consider a computer having 3 processes and corresponding 3 CD drives i.e., one held by each process. 

- Now all the three processes would be in a deadlock if they all request another drive.

Conditions for a Deadlock to arise

There are certain conditions that should be there for a deadlock to arise:

1. Mutual exclusion: There has to be at least one resource that cannot be shared. So that only one process would use at any given time.
2. Resource holding (or hold and wait): There should be at least one resource held by a process that in turn should be request more resources that are being held by other processes.
3. No preemption: Once the resources have been allocated, they should not de-allocated by the operating system. The condition is that the process holding the resource must release it voluntarily.
4. Circular wait: A circular chain of processes must be formed as explained in the earlier example.

"These 4 conditions for deadlock are collectively called the ‘Coffman conditions’. If any of these conditions is not met, a deadlock can’t occur".

- Handling a deadlock is an important capability of the operating systems. 

- However, there are many modern operating systems that still cannot avoid deadlocks. 

- On occurrence of a deadlock many non-standard approaches are followed by different operating systems for handling it. 

- Many of these approaches try to avoid at least one of the Coffman conditions (generally the 4^th one). 

- Below we discuss some of the approaches:

1. Ignoring deadlock
2. Detection
3. Prevention
4. Avoidance

- There is a second kind of deadlocks called the ‘distributed deadlock’ and it is common where concurrency control is used or we can say in the distributed systems. 

What is a Safe State and what is its use in deadlock avoidance?

Safe state plays a great role in avoiding the deadlocks. In this article we discuss in detail the concept of this safe state.
When do we call a state safe?
It is when even if the system allocates resources to all the processes and no deadlock occurs. This allocation is to the maximum limits and can be done in any preferred order. To put it down more formally, we can say that a system is considered to be in a safe state only if a safe sequence exists. This would become clearer from the following example:

Consider the following sequence of processes:

- Now this sequence is considered to be a safe one for the current state of the allocation if the resource requests made by each of the processes Pi can be satisfied by resources that are currently available including the resources held by some another process that precedes Pi.
- In this case, if the resources required by the Pi are not presently available, then it can wait till the preceding process completes its executions and releases the resources.
- Once it finishes, the resources it held, now can be utilized by the Pi for completing the task assigned to it and then it also releases back the resources to be used by succeeding processes.
- It then finally terminates.
- If there exists no sequence like this, then the system is said to be in an unsafe state.
- A deadlock cannot occur in a safe state and so this state cannot be called a deadlocked one. 
- But on the other side, a state is unsafe if it has a deadlock.
- However, it is not necessary that the reason for all states being unsafe is the deadlock.
- An unsafe state can however lead to a deadlock. 
- It is in the safe states, that the operating system is capable of avoiding the deadlocks.
- When the operating system falls in an unsafe state, it is no more in a position to prevent the requests of the processes that would cause a deadlock to occur.
- It is the behavior of the processes by which the unsafe states of the system are controlled.
- Another major difference between the safe and the unsafe states is that in a safe state it is guaranteed by the operating system that the execution of the processes will be completed in expected time but in the case of unsafe states it gives no such guarantee.
- If the concept of the safe state is predefined, then algorithms can be designed that would make sure that no deadlocks occur.
- The idea behind these algorithms would be to ensure the following things:
1. The system does not come out of the safe state.
2. The system is kept in a safe state initially.
3. The system must be able to determine if a resource requested by a process can be allocated immediately to it or it requires waiting.
4. The system grants the request of the process if and only if after finishing it, the system would still be in a safe state.

- One disadvantage of such algorithms is low resource utilization. It is because the process would still have to wait for the resource even if it is available.
- A deadlock occurs when two or more processes that are competing with one another to wait for each other to finish and neither of them do so.
- The deadlock which involves only two processes is called a deadly embrace.
- This may also occur if one process is waiting for the other to finish which in turn is waiting for some other process to finish and so on.

What is meant by concurrency testing?

INTRODUCTION TO CONCURRENT TESTING

1. Concurrency testing employs many users at a time and therefore it is considered to be a type of multi- user testing.

2. Concurrency testing was invented in order to determine what happens if many users are accessing the same data base records, modules or application code.

3. Other than this, concurrency testing also identifies the use of single threaded code, dead locking, locking semaphores and locking and it is also effective in measuring the level of these aspects.

4. While carrying out the concurrency testing several users perform same kind of task on the same application and that too at the same time.

5. The application serves too many users at a time.

TOOLS FOR PERFORMING CONCURRENT TESTING
Several tools are available for performing concurrency testing but we would recommend you loadRunner since it helps you create concurrency at a point you wish.

- All you need to do is create a test scenario after you have recorded and improved your scripts using the virtual user generator.

- You can decide and add how many users you want your scripts to support.

- You should input the number of users in the controller component of this testing tool.

- There are several ways to add user like gradual ramp- up or spike, stepped etc.

- You can choose for yourself which way you want the users to be added.

- This is the most effective way to create concurrency.

- Apart from the multi user testing, the concurrency testing tests one application over the other one.

LEVELS OF CONCURRENCY TESTING
Two levels of concurrency testing have been developed so far and they have been discussed below:

# 1st Level:
- This involves concurrency tsting of one application being executed on the top of another application.

- We can illustrate this by a simple example; you receive an incoming call while playing some game on your cell phone. The game will go to paused state. This is the simplest example we can give.

# 2nd Level:
- This involves concurrency testing of one application being executed on the top of other two applications.

- This can also be illustrated with a similar example, you receive an incoming call while playing games and while you are on the call you receive an SMS. The game is paused.

- Apart from just testing the multi user capacity of the software, concurrency is also responsible for finding out the bugs like dead lock, live lock, data race and data corruption.

- These bugs usually occur when the parallel processing is implemented in the application.

- If you are also using the user scenario apart from the test scenario your concurrency testing will yield much better results.

- Some applications make use of more than one module where some accept parallel processing and other are sequential.

- Identifying the type of modules can help you in writing effective test cases against them which in turn will reflect in your testing.

This is the internet era. Almost everyone is using web and web applications all over the world. Such a huge number of users require great stress handling capacity for the servers. If the servers are not able to take the load they often slip in to the position of the dead lock.

Concurrency testing is a way to ensure that such kinds of situations do not occur. Therefore concurrency testing is important. Performance is the basic aspect that is tested most in the concurrency testing.

Number of users using the application at a time equals to the number of hits per second. With the growing number of internet users world wide more and more security is needed over the web. Concurrency testing is one such measure which has helped to a great extent for improving the cyber standards.

What are common programming bugs every tester should know?

A programming bug as we all know is common or “one in all” term for a flaw, error or mistake in a software system or program. A bug is known for producing unexpected result always or results in the abnormal behavior of the software system or program.

CAUSES OF BUGS
- Root causes of the bugs are the faults or mistakes introduced in to the program’s source code or design and structure or its implementation.
- A program or a piece of program too much affected with bugs is commonly termed as a “buggy” program or code.
- They can be introduced unknowingly in the software system or program during the coding, specification, data entry, designing and documentation.
- Bugs can also arise due to complex interactions between the components of a complex computer program or system.
- This happens because the software programmers or developers have to combine a great length of code and therefore, they may not be able to track minor bugs.
- The discovered bugs are also documented and such documents or reports are called bug reports or trouble reports.

HOW BUGS INFECT A PROGRAM ACTUALLY?
- A single bug can trigger a number of faults or errors within the program which can affect the program in many ways.
- The degree of affecting depends on the nature of the bug.
- It can either affect the program very badly causing it to rash or hang or it may have only a subtle affect on the system.
- There are some bugs that are not detected in the entire software testing process.
- Some bug may cause a chain effect which can be described as one bug causing an error and that error causing some other errors and so on.
- Some bugs may even shut down the whole software system or application.
- Bugs can have serious impacts.
- Bugs can destroy a whole machine.
- Bugs are after all mistakes of human programmers.

TYPES OF BUGS
Bugs are of many types. There are certain types of common bugs that every programmer should be introduced with.

First we are listing some security vulnerabilities:
- Improper encoding
- SQL injection
- Improper validation
- Race conditions
- Memory leaks
- Cross site scripting
- Errors in transmission of sensitive data
- Information leak
- Controlling of critical data
- Improper authorization
- Security checks on the client side and
- Improper initialization

SOME COMMON BUGS ARE:

1. Memory leaks
- This bug is catastrophic in nature.
- It is most common in languages like C++ and C i.e., the languages which do not have automatic garbage collection feature.
- Here the rate of consumption of memory is higher as compared to rate of de- allocating memory which is zero.
- In such a situation the executing program comes to a halt because there is no availability of free memory.

2. Freeing the resource which has already been freed
- This bug is quite frequent in occurrence.
- Usually it happens that the resources are freed after allocation but here already freed resource is freed which causes an error.

3. De-referencing of NULL operator
- This bug is caused due to an improper or missing initialization.
- It an also be caused due to incorrect use of reference variables.

4. References
- Sometimes unexpected or unclear references are created during the execution which may lead to the problem of de- allocation.

5. Deadlocks
- These bugs though rare are catastrophic and are caused when two or more threads are mutually locked by each other or those threads get entangled.

6. Race conditions
- These are frequent and occur when the same resource or result is being tried to be accessed by two threads.
- The two threads are said to be racing.

Project Scheduling - Different ways for tracking the schedule.

A proper project schedule is very important for a successful project delivery. The project schedule is a road map for a software project manager. A project schedule needs to be properly developed. A proper project schedule defines the tasks and milestones that are tracked and controlled as project proceeds. This tracking needs to be accomplished nicely and there are different methods and ways to do so...

- Timely project meetings regarding the status of the project are held and it should be ensured that each team member should report the progress achieved and the problems that are faced.
- There are different reviews that are conducted throughout the software engineering process. It becomes necessary to evaluate the results of all these reviews in order to accomplish proper tracking.
- To accomplish proper tracking, for each task of the project, the actual start date and the planned start date should be compared.
- To accomplish tracking, one should determine whether the formal project milestones are achieved by the scheduled date.
- To accomplish tracking, progress should be assessed quantitatively.

The best indication of progress is the completion and successful review of a defined software work product.
The control administers the project resources, cope with problems and direct the project staff. Control is light if the project is on schedule and within budget. The control is exercised to reconcile the problems if they occur.

In case the problem is identified and diagnosed:
- staff is redeployed
- additional resources should be focused on problem area.

A severe deadline can be managed by time-boxing technique. It chooses an incremental software paradigm and a schedule is derived for each incremental delivery. This technique is done when the product may not be deliverable by a pre-defined deadline.

Deadlock - algorithms

BANKER’S ALGORITHM

Consider an example:

There are four customers: A, B, C and D, which are analogous to four processes.
The credit unit is like the resource
The banker himself is the OS
Assume each credit unit = Rs. 1000.

Not all customers need their maximum credit immediately. Hence only 10 credit units are reserved.
Process Current Max. Free = 10
A 0 6 B 0 5 C 0 4 D 0 7

How does the Algorithm Work?

When a new process (customer) enters the system, it (he) must declare the maximum number of instances of each resource type (credit units) that it (he) may need. This number may not exceed the total number of resources (credit units) in the system. When a user (customer) requests a set of resources (credit unit), the system must determine whether the allocation of these resources will leave the system in a safe state. If it will,
the resources are allocated; otherwise, the process must wait until some other process releases enough resources. Consider current allocation to various processes is as shown below.
Process Current Max. Free = 2
A 1 6 B 1 5 C 2 4 D 4 7
Would the System be in a Safe State?
‘C’ requests 2 additional units and gets them. It then runs to completion and frees all the resources it has.
Process Current Max. Free = 4
A 1 6 B 1 5 C 0 - D 4 7
Now either ‘B’ or ‘D’ can request and run to completion. Assume ‘B’ requests 4 additional units and gets them. It then runs to completion and frees all its resources. Process Current Max. Free = 5
A 1 6 B 0 - C 0 - D 4 7
Now ‘D’ runs and requests 3 additional resources and gets them. It then runs to completion and releases all its resources.Process Current Max. Free = 9
A 1 6 B 0 - C 0 - D 0 -
Finally ‘A’ runs and requests 5 additional resources and gets them. It then runs to completion and releases all its resources. Process Current Max. Free = 10
A 0 - B 0 - C 0 - D 0 -
Here is the complete banker’s algorithm:

Several data structures must be maintained to implement banker’s algorithm. Let n be the number of processes and m be the number of resource types. The data structures needed are:
• Available : A vector of length m indicates number of available resources of each type. If Available[j] = k, there are k instances of resource type Rj available.
• Max : A n*m matrix defines the maximum demand of each process. If Max[i,j]=k, then Pi may request at most k instances of resource type Rj.
• Allocation : An n*m matrix defines the number of resources of each type currently allocated to each process. If Allocation[i,j]=k, then process Pi is currently allocated k instances of resource type rj.
• Need : An n*m matrix indicates the remaining resource need of each process. If Need[i,j]=k, then Pi may need k more instances of resource type Rj to complete its task. Need[i,j]=Max[I,j] – Allocation[I,j].

After defining the data structures, algorithm moves into two phases :
• Safety Algorithm
• Resource Request Algorithm


SAFETY ALGORITHM

The safety algorithm is for finding out whether or not a system is in a safe state. It is described below:

1. Let work and finish be vectors of length m and n
respectively. Initialize work = Available and Finish[I] = false for all I = 1, 2, …, n.
2. Find an I such that both
• Finish[I] = false
• Needi <= work
If no such I exists, go to step 4.
3. Work = work + allocationi
finish[I] = true
go to step 2

4. If finish[I] = true for all I, then the system is in a safe state. This algorithm may require an order of m * n2 operations to decide whether a state is safe.

RESOURCE – REQUEST ALGORITHM

Having determined that the system is safe, this algorithm grants the requested resources to the process. Let Request i be the request vector for process Pi. If Request[j] = k, then process Pi wants k instances of resource type Rj. When this request is made, the following actions are taken:

1. If request I <= need I, then go to step 2. Otherwise raise an error condition because the process has exceeded its maximum claim.
2. If request I <= available, go to step 3. Otherwise, Pi must wait since the resources are not available.
3. Have the system pretend to have allocated the requested resources to process Pi by modifying the state as follows:
a. Available = available – request I
b. Allocation = allocation + request I
c. Need I = Need I – request I
4. Call the Safety algorithm. If the state is safe, then transaction is completed and process Pi is allocated the resources. If the new state is unsafe, then Pi must wait and the old resource allocation state is restored.

Deadlock situation

A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does. In the computing world deadlock refers to a specific condition when two or more processes are each waiting for another to release a resource, or more than two processes are waiting for resources in a circular chain.

Under the normal mode of operation, a process may utilize a resource in the following sequence:

Request – when a process needs some resource, it requests for it. Process has to wait if resource is busy.
Use – The process should operate on the resource.
Release – After using, process should release the resource.

Conditions In Which Deadlock Can Arise

• Hold and Wait : As the name suggests, a process is holding a resource and also waiting for some other resources that are held by other process.
• No Preemption : A resource can be released only voluntarily by the process holding it, after that process has completed the task.
• Mutual Exclusion : It means only one process can use the resource at a time. If some other process requests that resource, the requesting process has to wait until the resource is released.
• Circular Condition : There must exist a state of waiting processes in which process P0 is waiting for a resource that is held by P1, P1 waiting for resource held by P2, Pn-1 waiting for resource held by Pn an Pn is waiting for resource held by P0.