Explain briefly Deadlock Avoidance and Detection?

Deadlocks are a serious issue that needs to be avoided since it can cause the whole system to hang or crash.

What is Deadlock Avoidance?

- Avoiding a deadlock is possible only if certain information regarding the processes is available with the operating system.
- This information has to be made available to the OS just before the resources are allocated to the processes.
- These are the processes that are to be consumed by the process in its lifetime.
- For every resource request made by the process, any potential threats are checked by the system i.e., whether granting the request of the process will send it in to an unsafe zone or not.
- If it is so then there are possibilities that the system could enter a deadlock.
- Therefore, only those requests are granted by the process that will ensure a safe state of the process.
- It is important for the system to determine whether the next level of the process will be safe or unsafe.
- There are 3 things that the operating system must know at any before or after the execution of the process:
1. The currently available resources.
2. The resources currently allocated to the processes.
3. Resources to be required and released in the future by these processes.

- It is possible that a process might be in an unsafe state but still may not cause a deadlock.
- By the notion of the safe and unsafe state of the process we refer to the system’s ability of entering in to a deadlock.
An example will make it clearer:
- Consider a resource A requested by a process which would make the process state unsafe.
- At the same time it releases another resource say B preventing the circular wait of the resources.
- In such a situation, the system is said to be in an unsafe state though not necessarily in a deadlock.
- There are various algorithms that have been designed for deadlock avoidance and one such is the banker’s algorithm.
- To use this algorithm knowledge about the resource usage limit is required in advance.
-  It is impossible for most of the systems to know what a process will request for in advance.
- This only implies that the deadlock avoidance is also not possible here.
- There are other two algorithms for achieving this task namely wound/ wait and wait/ die algorithms.
- Each of them makes use of a symmetry breaking technique.

What is Deadlock Detection?

- Deadlocks are free to occur under the implementation of this concept.
- Then through the state of the system, the occurrence of the deadlock is confirmed and subsequently mended.
- Here, the resource allocation activities are tracked along with the process states by certain algorithms.
- After this, the algorithm is used for removing the deadlock.
- Deadlock detection is quite easy since the OS scheduler knows about the resources that have been locked by the processes.
- Model checking is one of the techniques used for deadlock detection.
- In this a finite state model is created up on which a progress analysis of the process is carried out and all the terminal sets of the model are found.
- Each of these stands for a deadlock.
- Correction of the deadlock can be done by any of the below mentioned methods after the deadlock has been detected:
1. Process termination: This is about aborting one or more of the processes that cause the deadlock thus ensuring a certain and speedy removal of the deadlock. But this method might prove to be a little expensive because of the loss of the partial computations.
2. Resource preemption: This is about a successive preemption of the allocated resources until the breakdown of the deadlock.

What are the various Desk Scheduling methods?

About Disk Scheduling

The I/O system has got the following layers:

1. User processes: The functions of this layer including making I/O calls, formatting the I/O and spooling.
2. Device independent software: Functions are naming, blocking, protection, allocating and buffering.
3. Device drivers: Functions include setting up the device registers and checking their status.
4. Interrupt handlers: These perform the function of waking up the I/O drivers up on the completion of the I/O.
5. Hardware: Performing the I/O operations.

- Disk drives can be pictured as large 1 – D array consisting of logical blocks that are smallest unit of transfer.  

- These blocks are mapped in to the disk sectors in a sequential manner. 

- Mapping is done in the same manner. 

- The responsibility of using the hardware efficiently is the duty of the operating system for the disk drives for increasing the speed of access and bandwidth of the disk. 

Algorithms for Scheduling Disk Requests

There are several algorithms existing for the scheduling of the disk requests:

Ø  SSTF: 

- In this method the request having the minimum seek time is selected from the present head position. 

- This method is a modification of the SJF (shortest job first) scheduling and therefore contains some possibility of process starvation.

Ø  SCAN: 

- From one end of the disk, the disk arm starts and continues in the direction of the other end, serving to the requests till the opposite end. 

- At this end the head is reversed and the process continues. 

- This is sometimes called as the elevator algorithm.

Ø  C – SCAN: 

- A better algorithm then the previous one. 

- This one offers a more uniform waiting time than the previous one. 

- The movement of the head is from one end to another while it services the requests encountered along the way. 

- However, the difference is that when it comes to the other it straightaway goes to the beginning without heeding to any of the requests in the way and then again starts. 

- The cylinders are treated as the circular list wrapped around last and the first cylinder.

Ø  C – Look: 

- This is a modified version of the C – SCAN. 

- Here the arm or the head travels only up to the last request rather than going till the far end. 

- Then immediately the direction is reversed and the process continues.

- For disk scheduling it is important that the method be selected as per the requirements only. 

- The first one is the most commonly used and appeals to the needs naturally. 

- For a system where often there is a heavy load on the disk, the SCAN and C- SCAN methods can help. 

- The number as well as the kind of requests affects the performance in a number of ways.

- On the other hand, the file – allocation method influences the requests for the disk services. 

- These algorithms have to be written as an individual module of the OS so that if required it can be replaced with a different one easily. 

- As a default algorithm, the LOOK or the SSTF is the most reasonable choice. 

Ways to attach to a disk

There are two ways of attaching the disk:

Ø  Network attached: This attachment is made via a network. This is called the network attached storage. All such connected storage devices together form the storage area network.

Ø  Host attached: This attachment is made via the I/O port.

All these disk scheduling methods are for the optimization of the secondary storage access and for making the whole system efficient. 

What are different types of schedulers and their workings?

Scheduling is an important part of the working of operating systems. 

- The scheduler is the component that provides access to the resources to the processes, threads and data flows. 

- These resources may include time of the processor and the communications bandwidth. 

- Scheduling is necessary for effectively balancing the load of the system and achieving the target of QoS or quality of service. 

- Scheduling is also necessary for the systems that do multitasking and multiplexing on a single processor since they need to divide the CPU time between many processes. 

- In multiplexing, it is required for timing the simultaneous transmission of the multiple flows.

Important things about Scheduler

There are 3 things which most concern the scheduler:

1. Throughput
2. Latency inclusive of the response time and the turnaround time
3. Waiting time or the fairness time

- But when practically implemented, conflicts arise between these goals for example between latency and throughput. 

- It is the scheduler that can make a compromise between any two goals. 

- Based on the user’s requirements and the objectives it is decided to which goal the preference has to be given. 

- In systems such as the embedded systems and robotics that operate in real time environment, it has to be ensured by the scheduler that the processes are capable of meeting the deadlines. 

- This is a very critical factor in maintaining the stability of the system. 

- The administrative back end is used for managing the scheduled tasks that are then sent to the mobile devices.  

Types of Schedulers

There are 3 different types of schedulers available which we discuss below:

Long term Schedulers or Admission Schedulers: 

- The purpose of this type of scheduler is to decide about the processes and jobs to be admitted or added to the ready queue. 

- When a program makes an attempt for executing a process, it is the responsibility of the long – term scheduler to delay or authorize the request for admitting the process to the ready queue. 

- Thus, what all processes will be executed by the system is dictated by this scheduler. 

- It also dictates about the degree of the concurrency and handling of the CPU intensive and I/O intensive processes. 

- Modern operating systems use this for making sure that there is enough time for the processes to finish of their tasks. 

- Modern GUIs would be of very less use if there was no real time scheduling. 

- The long term queue resides in the secondary memory.

Medium term Schedulers: 

- This scheduler serves the purpose of removing the processes from the physical memory and placing them in the virtual memory and even vice versa. 

- This process is called swapping out and swapping in. 

- A process that has been inactive for some time might be swapped by the scheduler. 

- It may also swap a process with frequent page faulting, low priority or more amount of memory etc. 

- This is necessary since this makes the space available for other processes.

Short term Schedulers: 

- These schedulers are more commonly known as the CPU schedulers.

- It decides which one out of all the processes will be executed after the clock interrupt, a system call, an I/O interrupt, hardware interrupt and so on. 

- Thus, we can say that the frequency of the short term schedulers of making decisions is much higher than that of the long term and medium term schedulers since after every time slice these schedulers have to decide.

- There is one more component that is involved in CPU scheduling but is not counted under schedulers. It is called dispatcher. 

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 cache memory?

Cache memory is a certain memory aid for computers that speeds them up very well. 

- In cache memory, the storage of the data is transparent so as to make the processing of the future requests faster. 

- A cache might store in it the values that have already computed or duplicate of some values stored somewhere else in the memory. 

- Whenever some data is requested, it is first looked up in the cache memory. - If the data is found here, it is returned to the processor and this is called a ‘cache hit’. 

- In this case the time taken for accessing the data is reduced. 

- This access is thus faster than that of the main memory. 

- Another case is of cache miss when the required data is not found in the cache.

- Then again the data has to be fetched or computed from its original source or the storage location which is slow as obvious. 

- The overall performance of the system increases in proportion with the number of requests that can be served from the cache memory.

- In order to maintain the cost efficiency as well as efficiency in data usage, the size of the cache is kept relatively small as compared to the main memory. 

- However, the caches have proven themselves from time to time because of their ability to recognize the patterns of access in the applications having some locality of reference. 

- Temporal locality is exhibited by the references if the data that was previously requested is requested once again.

- These references apart from temporal locality also exhibit spatial locality if the storage location of the requested data is close to the data that was previously requested.

How is cache implemented?

- The cache is implemented as a memory block by the hardware and as a place of temporary storage. 

- Here, only that data is stored which is likely to be accessed again and again. 

- Caches are not only used by hard drives and CPUs but also by the web servers and browsers. 

- Pools of entries together make up the cache. 

- Each entry has a datum associated with and a copy of it is stored in the backing store. 

- Each entry is also tagged for the specification of the datum’s identity in the backing store.

- When a datum is required to be accessed by a cache client (it might be an operating system, CPU or web browser.) that it thinks might be available in the backing store, the cache is first checked. 

- If the desired entry is found, it is returned for the use. This is cache hit.

- Similarly, a web browser might look in its local cache available at the disk to see if it has the contents of a web page. 

- In this case the URL serves as the searching tag and the contents are the datum. 

- The rate of successful cache accesses is known as the hit rate of the cache.

- In case of a cache miss, the datum not cached is copied in to the cache so as to prevent future cache misses. 

- For making space for this datum, some already existing datum in the cache is removed. 

- Which datum is to be removed is determined by using the replacement algorithms. 

What are different types of design patterns?

The Composite View Design Pattern
- The context of composite view pattern is that it allows the development of the view more manageable through the creation of a template to handle common page elements for a view.
- The problem comes in modifying and managing the layout of multiple views.
- The solution is to use this pattern when a view is composed of multiple atomic sub-views. Each component of the template may be included into the whole and the layout of the page may be managed independently of the content.
- A benefit of using this pattern is that interface designer can prototype the layout of the page, plugging in static content on each component.
- The drawback is that there is a runtime overhead associated with it.

The Front Controller Design Pattern
- It provides a centralized controller for managing requests.
- The problem is that the system needs a centralized access point for presentation-tier request handling to support the integration of system data retrieval, view management, and navigation.
- The solution to the above problem is that a controller is used as an initial point of contact for handling a request. It centralizes decision-making controls.

Data Access Object Design Pattern
- It separates resource's client interface from its data access mechanisms.It allows data access mechanism to change independently of the code that uses the data.
- The problem is that data will be coming from different persistent storage mechanism and access mechanism varies based on the type of storage.
- The solution to the above problem is to use the Data Access Object to abstract and encapsulate all access to the data source. It implements the access mechanism required to work with the data source.