Company : Microsoft
Asked in : Technical Interviews
1) What is basic difference between 32 bit and 64 bit operating system?
A) The terms are just refer to ways a CPU handles information. The main difference is 64 bit version handles large amount of RAM more effectively than a 32 bit. 4GB RAM is maximum usable memory the 32 bit version can handle and 64 bit, more than 4GB.
2) What is deadlock? What are the conditions of deadlock? Can you write a code to show deadlock. What is the Bankers Algorithm?
A) Operating system is a resources allocator that can be allocated to one process at time. Now resources allocated to a process are not preemptable; this means that once a resource has been allocated to a process, there is no simple mechanism by which the system can take the resource back from the process unless the process voluntarily gives it up or the system administrator kills the process. This can lead to a situation called deadlock.
Lets take an example. Suppose a process P1 requires some resource R2 which is acquired by some other process P2 and P2 requires resource R1 which is already acquired by P1.Hence none of the process acquired the required resource as both the respective process are in waiting condition and hence deadlock occurs.
Lets consider a real life example also. Imagine you have a sibling and both of you want to bat while playing cricket. Say you have bat and your sibling has ball. Now both are not willing to compromise and hence both cannot play cricket because alone bat or alone ball won't help and this situation is called deadlock.
Lets move onto the next subquestion. The conditions of deadlock are as follows:
Mutual exclusion - Each resource is either currently allocated to exactly one process or it is available. (Two processes cannot simultaneously control the same resource or be in their critical section).
Hold and Wait - processes currently holding resources can request new resources
No preemption - Once a process holds a resource, it cannot be taken away by another process or the kernel.
Circular wait - Each process is waiting to obtain a resource which is held by another process.
Lets now move on to the next subquestion asked. The interviewer wants us to write a code on deadlock. We can show it in Java by locking two Java threads as shown in fig:
In above case, Thread- has A but need B to complete processing and Similarly Thread-2 has resource B but need A first.
Let write above scenario in java code:
package thread;
public class ResolveDeadLockTest {
public static void main(String[] args) {
ResolveDeadLockTest test = new ResolveDeadLockTest();
final A a = test.new A();
final B b = test.new B();
// Thread-1
Runnable block1 = new Runnable() {
public void run() {
synchronized (a) {
try {
// Adding delay so that both threads can start trying to
// lock resources
Thread.sleep(100);
} catch (InterruptedException e) {
e.printStackTrace();
}
// Thread-1 have A but need B also
synchronized (b) {
System.out.println("In block 1");
}
}
}
};
// Thread-2
Runnable block2 = new Runnable() {
public void run() {
synchronized (b) {
// Thread-2 have B but need A also
synchronized (a) {
System.out.println("In block 2");
}
}
}
};
new Thread(block1).start();
new Thread(block2).start();
}
// Resource A
private class A {
private int i = 10;
public int getI() {
return i;
}
public void setI(int i) {
this.i = i;
}
}
// Resource B
private class B {
private int i = 20;
public int getI() {
return i;
}
public void setI(int i) {
this.i = i;
}
}
}
This will result in a deadlock.
Next subquestion is Banker's Algorithm.
The banker’s algorithm is a resource allocation and deadlock avoidance algorithm that tests for safety by simulating the allocation for predetermined maximum possible amounts of all resources, then makes an “s-state” check to test for possible activities, before deciding whether allocation should be allowed to continue.
Following Data structures are used to implement the Banker’s Algorithm:
Let ‘n’ be the number of processes in the system and ‘m’ be the number of resources types.
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 allocated ‘k’ instances of resource type Rj
Need [ i, j ] = Max [ i, j ] – Allocation [ i, j ]
Allocationi specifies the resources currently allocated to process Pi and Needi specifies the additional resources that process Pi may still request to complete its task.
Banker’s algorithm consist of Safety algorithm and Resource request algorithm
Safety Algorithm
Resource-Request Algorithm
Let Requesti be the request array for process Pi. Requesti [j] = k means process Pi wants k instances of resource type Rj. When a request for resources is made by process Pi, the following actions are taken:
Example:
Considering a system with five processes P0 through P4 and three resources types A, B, C. Resource type A has 10 instances, B has 5 instances and type C has 7 instances. Suppose at time t0 following snapshot of the system has been taken:
Question1. What will be the content of the Need matrix?
Need [i, j] = Max [i, j] – Allocation [i, j]
So, the content of Need Matrix is:
Question2. Is the system in safe state? If Yes, then what is the safe sequence?
Applying the Safety algorithm on the given system,
Question3. What will happen if process P1 requests one additional instance of resource type A and two instances of resource type C?
We must determine whether this new system state is safe. To do so, we again execute Safety algorithm on the above data structures.
Hence the new system state is safe, so we can immediately grant the request for process P1 .
Comments
Post a Comment