基于二叉排序树的最佳适应算法

Best Fit Algorithm Based on Binary Sort Tree

当前操作系统在管理内存时,常采用最佳适应算法对空闲内存块进行分配,但该算法存在效率不高、时空消耗大的缺点,对此提出基于二叉排序树的最佳适应算法,改变原有的最佳适应算法中把所有空闲分区按容量大小顺序连接成空闲分区链的特点,而把所有空闲分区组建成一颗二叉排序树,进程发出请求时,根据二叉排序树的性质依次查找满足条件的空闲分区,并在分配后重组二叉排序树,保证二叉排序树的结构不被破坏,改善现有的最佳适应算法在查找过程中的效率问题.

The best fit algorithm is frequently used in the free memory block distribution when OS administrates the memory of computer. However, faults in efficiency and consumption of time-space are abvious. Therefore, the best fit algorithm based on the Binary Sort Tree is proposed to avoid the defects, which change all free memory block into Binary Sort Tree instead of chain table from small to big, the Operating Systme will inquire the Binary Sort Tree according to its character to get a free memory block when a process needs a new one. And then, the recombination will be finished after block distribution to protect the structure against destory and promots the efficiency during the memory block inquirment.