Memory allocation to avoid memory waste

When it comes to memory allocation, we have to mention continuous allocation.This method, which allocates a contiguous memory space for a user program, was widely used in the OS in the 1960s and 1970s and is still used today.Continuous allocation can be further divided into single continuous allocation, fixed allocation, dynamic partition allocation and dynamic relocation allocation.

Single continuous allocation is the simplest storage management method, which can only be used in single-user, single-task OS.It divides the memory into the system area and the user area. The system area is only provided for the OS. Except for the system area, all the memory space is the user area.

Fixed partition allocation, which is the simplest storage management in a multiprogramming environment.Dividing memory into fixed-size regions, each containing only one job, allows several jobs to run concurrently.When you have a free partition, you can select one from the standby queue to load that partition.

Fixed partition allocation has two ways to partition: partition size is equal, but due to lack of flexibility, programs too small will waste memory, too large will not run.However, it can be used when controlling multiple identical objects.Partition size is different, the partition will be divided into a number of smaller partition, the right amount of medium partition and a small number of large partition, according to the size of the program to allocate the appropriate partition.

In order to facilitate memory allocation, we usually queue partitions by size and establish a partition usage table for them. The table item reports the initial address, size and state of each partition.Fixed partitions were the earliest form of multiprogram storage management, and although they are now obsolete, they are still used in some systems that control multiple objects of the same type.

Dynamic partition allocation, this is according to the actual needs of the process, dynamic allocation of memory space.It mainly involves three problems: the data structure used in partition allocation, partition allocation algorithm and partition allocation and recovery.

The data structure in partition allocation is mainly used to describe the situation of free partition and allocated partition and provide basis for allocation.Common data structure has two forms: free partition table, used to record every free partition on the whole, each free partition occupies a table table;The free partition chain, also to facilitate the use of free partitions, adds forward and backward Pointers at the beginning and end of each partition.

Partition allocation algorithm, a new crime into memory, according to a certain allocation algorithm, from the free partition table or free partition chain to choose a free partition to the job.There are roughly five allocation algorithms.

For the first time, the free partition chain is linked in the order of address increasing, and the memory is allocated from the beginning. As long as a free area is found to meet the requirements of job size, it will be allocated, and the remaining free partition will remain in the free chain.Because this algorithm tends to make use of the free partition of the low address part, the low address part will be divided continuously, leaving many idle partitions that are difficult to use.

Loop first adaptive algorithm, based on the first adaptive algorithm, not every time from the chain start to find, but from the last found free partition next free partition to start to find.You need to set the start lookup pointer to indicate the free partition of the next start query, and use the loop lookup method.This algorithm reduces the overhead of finding free partitions, but it lacks large free partitions.

The optimal adaptive algorithm can always allocate the minimum free partition that meets the requirements to the job.In order to implement this algorithm, free partitions need to be formed into a chain of free partitions in order from small to large.However, the remainder of each partition is always minimal, leaving a lot of small free space that is difficult to exploit.

The worst fit algorithm scans the entire free partition table, always picking the largest free partition for the job, and requires the free areas to be sorted from large to small.The advantage is that the remaining free area is not too small, the probability of generating debris is the minimum, and the search efficiency is the highest.The downside is that the memory lacks large free partitions.

The above four algorithms are called sequential search, while the following algorithm is called classified search.

According to the fast adaptive algorithm, the idle partition is first classified according to the size of capacity, and a linked list of idle partitions is set up for each category.At the same time in memory set up a management index table, each table entry corresponds to a free partition type.And the classification of free partition is based on the commonly used space size of the process partition, convenient allocation of free partition.The advantage of this algorithm is high efficiency, and will not produce partition partition, can retain large partition, will not produce memory fragmentation.The disadvantage is that the algorithm is complex and the system overhead is large.In addition, the allocation of this algorithm is based on process, and a partition belongs to a process. In the allocated partition, there is more or less waste.The finer the idle partition, the worse the waste.

Partition allocation and recovery, the system USES some allocation algorithm from the free partition table to find the required size of the partition, load the free partition of the job occupied space, the rest of the small part is no longer cut, on the contrary, it will be divided out.When the memory is released after the completion of the job or process, the system finds the corresponding insertion point from the free area list according to the first address of the recycling area and merges it with the adjacent free area.