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.