Skip to main content

What is a deadlock?The reason for the deadlock? What are the necessary conditions for deadlock? How to remove the deadlock? What is the difference between paging and segmentation?

 What is a deadlock?

Deadlock refers to a stalemate caused by multiple processes competing for resources during operation. When the processes are in this stalemate, if there is no external force, they will not be able to move forward.

 

The reason for the deadlock?

Because there are some inalienable resources in the system, and when two or more processes occupy their own resources and request each other's resources, each process will not be able to move forward, which is a deadlock.

 A. Competing resources

For example: there is only one printer in the system that can be used by process A. Assuming that A has occupied the printer, if B continues to request the printer to print, it will be blocked. 

The resources in the system can be divided into two categories:

  1. Deprivable resources: After a process obtains such resources, the resources can be deprived by other processes or systems. Both CPU and main memory are deprived resources;
  2. Inalienable resources. When the system allocates such resources to a process, it cannot be forcibly taken back. It can only be released after the process is used up, such as tape drives, printers, etc.

B. Improper sequence of progress

For example: Process A and Process B are waiting for each other's data.

 

What are the necessary conditions for deadlock?

  1.  Mutually exclusive conditions: the process requires exclusive control of the allocated resources, that is, a certain resource is occupied by only one process within a period of time.
  2. Request and hold conditions: When the process is blocked by requesting resources, hold on to the acquired resources.
  3. Non-deprivation conditions: the resources acquired by the process cannot be deprived before they are used up, and can only be released by themselves when they are used up.
  4. Loop waiting condition: When a deadlock occurs, there must be a process-resource circular chain.

 

The basic method to solve the deadlock?

  1. Prevent deadlock
  2. Avoid deadlock
  3. Detect deadlock
  4. Relieve the deadlock

 

How to prevent deadlock?

  1.  Destruction of request conditions: All resources are allocated at once so that there will be no more requests;
  2. Please keep the conditions for destruction: as long as one resource is not allocated, no other resources are allocated to this process:
  3. Destruction of inalienable conditions: When a process obtains some resources but cannot obtain other resources, the occupied resources are released;
  4. Break the loop waiting condition: the system assigns a number to each type of resource, and each process requests the resource in the order of increasing number, and the release is the opposite.

How to avoid deadlock?

Banker's algorithm

When a process applies for resources for the first time, it is necessary to test the maximum demand for resources of the process. If the existing resources of the system can meet its maximum demand, the resources will be allocated according to the current application amount, otherwise the allocation will be postponed.

When a process continues to apply for resources during execution, first test whether the sum of the number of resources occupied by the process and the number of resources applied for this time exceeds the maximum demand for resources of the process. If it exceeds, refuse to allocate resources. If it is not exceeded, then test whether the existing resources of the system can meet the maximum amount of resources still needed for the process, if it is satisfied, the resources will be allocated according to the current application amount, otherwise the allocation will also be postponed. 

Security sequence

It means that the system can allocate the resources needed by each process Pi according to a certain process advancement sequence (P1, P2, P3, ..., Pn), until the maximum demand for resources of each process is satisfied, so that each The processes can be completed sequentially. This sequence of advancement is called a security sequence [the core of the banker's algorithm is to find a security sequence]. 

System security status

If the system can find a safe sequence, it is said to be in a safe state, otherwise, it is said to be in an unsafe state.

 

How to remove the deadlock?

  1.  Resource deprivation: Suspend some deadlocked processes, seize its resources, and allocate these resources to other deadlocked processes (but it should prevent the suspended process from not getting resources for a long time);
  2. Revocation process: Forcibly revoke some or even all deadlock processes and deprive these processes of resources (the principle of revocation can be carried out according to the priority of the process and the cost of the revocation process);
  3. Process rollback: Let one or more processes rollback enough to avoid deadlock. When the process rolls back, voluntarily release resources instead of being deprived. The system is required to maintain historical information of the process and set a restore point.


What is a buffer overflow? What's the harm?

The buffer is the memory for temporarily storing output or input data. Buffer overflow means that when the computer fills the buffer with data, the capacity of the buffer itself is exceeded, and the overflowed data is overlaid on the legal data. The main reason for buffer overflow is that the program did not carefully check whether the user input is reasonable. In the computer, the harm caused by buffer overflow mainly has the following two points: program crash causes denial of service and jump and executes a piece of malicious code.

 

What is the difference between paging and segmentation?

  1. Segment is the logical unit of information, which is divided according to the needs of users, so the segment is visible to users; Page is the physical unit of information, which is divided for the convenience of managing main memory, and is transparent to users;
  2. The size of the segment is not fixed, it is determined by the function it completes; the page size is fixed, determined by the system;
  3. Segments provide users with a two-dimensional address space; pages provide users with a one-dimensional address space;
  4. A segment is a logical unit of information, which is convenient for storage protection and information sharing, and page protection and sharing are restricted.

Labels:

Comments

Post a Comment

Popular posts from this blog

Defination of the essential properties of operating systems

Define the essential properties of the following types of operating sys-tems:  Batch  Interactive  Time sharing  Real time  Network  Parallel  Distributed  Clustered  Handheld ANSWERS: a. Batch processing:-   Jobs with similar needs are batched together and run through the computer as a group by an operator or automatic job sequencer. Performance is increased by attempting to keep CPU and I/O devices busy at all times through buffering, off-line operation, spooling, and multi-programming. Batch is good for executing large jobs that need little interaction; it can be submitted and picked up later. b. Interactive System:-   This system is composed of many short transactions where the results of the next transaction may be unpredictable. Response time needs to be short (seconds) since the user submits and waits for the result. c. Time sharing:-   This systems uses CPU scheduling and multipro-gramming to provide economical interactive use of a system. The CPU switches rapidl
Post a Comment
Read more

What is a Fair lock in multithreading?

  Photo by  João Jesus  from  Pexels In Java, there is a class ReentrantLock that is used for implementing Fair lock. This class accepts optional parameter fairness.  When fairness is set to true, the RenentrantLock will give access to the longest waiting thread.  The most popular use of Fair lock is in avoiding thread starvation.  Since longest waiting threads are always given priority in case of contention, no thread can starve.  The downside of Fair lock is the low throughput of the program.  Since low priority or slow threads are getting locks multiple times, it leads to slower execution of a program. The only exception to a Fair lock is tryLock() method of ReentrantLock.  This method does not honor the value of the fairness parameter.
Post a Comment
Read more

How do clustered systems differ from multiprocessor systems? What is required for two machines belonging to a cluster to cooperate to provide a highly available service?

 How do clustered systems differ from multiprocessor systems? What is required for two machines belonging to a cluster to cooperate to provide a highly available service? Answer: Clustered systems are typically constructed by combining multiple computers into a single system to perform a computational task distributed across the cluster. Multiprocessor systems on the other hand could be a single physical entity comprising of multiple CPUs. A clustered system is less tightly coupled than a multiprocessor system. Clustered systems communicate using messages, while processors in a multiprocessor system could communicate using shared memory. In order for two machines to provide a highly available service, the state on the two machines should be replicated and should be consistently updated. When one of the machines fails, the other could then take‐over the functionality of the failed machine. Some computer systems do not provide a privileged mode of operation in hardware. Is it possible t
Post a Comment
Read more