动态分区分配
 
动态分区分配是根据进程的实际需要，动态的为之分配内存的空间。总体是按照算法规则找到分配的空闲分区，然后从该分区中再按照作业的大小划出一块内存空间分给作业，该分区余下的空闲分区当做一个新的空闲分区留在空闲链中。
 
当作业按照算法规则分配好了后，等作业运行完毕释放内存，系统根据回收区的首址，从空闲区链表中找到相应的插入点，此时可能出现以下4种情况之一：
 
回收区与插入点的前一个空闲分区F1相邻接，此时将两个分区合并；
 
回收区与插入点的后一个空闲分区F2相邻接，此时将两个分区合并；
 
回收区与插入点的前，后两个空闲分区相邻接，此时将三个分区合并；
 
回收区既不与F1相邻接，又不与F2相邻接，此时应为回收区单独建立一个新表项。
 
 
 
1)首次适应算法
 
首次适应算法，要求空闲分区链以地址递增的次序链接，在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止，然后再按照作业的大小，从该分区中划出一块内存空间分给请求者，余下的空闲分区仍停留在空闲链中。
 
 
 
2)循环首次适应算法
 
该算法是由首次适应算法演变而成的。在为进程分配内存空间时，不再每次从链首开始查找，而是从上次找到的空闲分区开始查找，直至找到一个能满足需求的空闲分区，并从中划出一块来分给作业。该算法能使空闲中的内存分区分布得更加均匀，但将会缺乏大的空闲分区。
 
 
3)最佳适应算法
 
该算法总是把既能满足需求又是最小的空闲分区分配给作业。
 
为了加速查找，该算法需要将所有的空闲区按其大小从小到大进行排序后，当有作业要分配的时候，查找满足其内存需求，同时又是最小的空闲块，然后分配给作业。
 
这样每次找到的第一个满足需求的空闲区，必然是最优的。但该算法容易由于每次是查找到满足作业的最小空闲块，然后从该分区中再按照作业的大小划出一块内存空间分给作业，该分区余下的空闲分区当做一个新的空闲分区留在空闲链中，由于在没分配前该分区（满足作业的最小空闲块）大小一般不会超过该作业太多，就容易会出现在存储器中将留下许多难以利用的小空闲区，同时每次分配后必须重新排序，这也带来了一定的开销。
 
4)最差适应算法
 
最差适应算法中，该算法需要将所有的空闲区按其大小从大到小进行排序，分配时直接从空闲区链的第一个空闲分区中分配（不能满足需要则不分配）。非常显然，如果第一个空闲分区不能满足，那么再没有空闲分区能满足需要。
 
这种分配方法初看起来不太合理，但他也有非常强的直观吸引力：在大空闲区中放入程式后，剩下的空闲区常常也非常大，于是还能装下一个较大的新程式。
 

 
 
例题：
 
在动态分区分配方案中，某一作业完成后，系统收回其主存空间，并与相邻空闲区合并，为此需要修改空闲区表，造成空闲区数减1的情况是()
 
 
 
 
无上邻空闲区，也无下邻空闲区
 
 
有上邻空闲区，但无下邻空闲区
 
 
有下邻空闲区，但无下邻空闲区
 
 
有上邻空闲区，也有下邻空闲区
 
 

 解答：D
 

  
 
有上邻空闲区，但无下邻空闲区.只修改上邻空闲区长度（为收回的空闲区长度与原上邻区长度之和），空闲区数不变 
无上邻空闲区，但有下邻空闲区.改记录这个下邻空闲区记录的地址为收回空闲区的地址，长度为下邻空闲区的长度和收回空闲区的长度，空闲区数不变 
有上邻空闲区，也有下邻空闲区.改记录上邻区记录的长度（为上邻区长度、下邻区长度和收回区长度之和），再把下邻区记录的标志位改为空，即空闲区数-1。 
无上邻空闲区，也无下邻空闲区.那么找一个标志位为空的记录，记下该回收区的起始地址和长度，且改写相应的标志位为未分配，表明该登记栏中指示了一个空闲区。空闲区数+1。
 
 

 

基于顺序搜索的动态分区分配方法
        首次适应法（FF）：要求空闲分区按首址递增的次序组织空闲分区表（队列）。 
               注意：每次分配和回收后空闲分区表或空闲 分区队列都要按首址递增的次序排序。
        下次适应法(NF)（循环首次适应算法）：按分区的先后次序，从上次分配的分区起查找（到最后分区时再回到开头），找到符合要求的第一个分区。

        最佳适应法(BF) ：要求按空闲区大小递增的次序组成空闲分区表（队列）。
               注意：分配和回收后要对空闲区表(队列)重新排序
             优点：
               在系统中若存在一个与申请分区大小相等的空闲区，必定会被选中，而首次适应法则不一定。

            若系统中不存在与申请分区大小相等的空闲区，则选中的空闲区是满足要求的最小空闲区，而不致于毁掉较大的空闲区。
            缺点：
                空闲区的大小一般与申请分区大小不相等，因此将其一分为二，留下来的空闲区一般情况下是很小的，以致无法使用。随着时间的推移，系统中的小空闲区会越来越多，从而造成存储区的大量浪费

        最坏适应法(WF)：要求空闲区按大小递减的顺序组织空闲区表（或队列）
例：有作业序列：作业A要求18K；作业B要求25K，作业C要求30K。系统中空闲区按三种算法组成的空闲区队列：



经分析：最佳适应法对这个作业序列是合适的，而其它两种对该作业序列是不合适的。

C语言实现动态分区分配
 
代码重复度还是很高的，存在简化的空间。
 
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>  
#include<conio.h>
#include<string.h>
#include<stdlib.h> 

#define LEN sizeof(Qu)
int m = 0;

typedef struct fenqu
{
	int num; //分区序号    
	long begin; //起始地址    
	long size;   //分区大小    
	int status;   //分区状态 
	struct fenqu* next;
}Qu;

Qu* tin = NULL;//悬停指针

Qu* creat()//初始化
{
	Qu* p1;
	Qu* h = NULL;
	h = (Qu*)malloc(LEN);
	if (h) {
		p1 = (Qu*)malloc(LEN);
		if (p1) {
			printf("用户空闲分区：");
			scanf_s("%d", &p1->size);
			p1->num = m++;
			p1->status = 0;
			p1->begin = 30;
			h->next = p1;
			p1->next = NULL;
			return h;
		}
	}
}
Qu* cr() {//分配内存
	Qu* h, * n, * u;
	h = n = u = NULL;
	n = h = (Qu*)malloc(LEN);
	if (h) {
		printf("分配大小：");
		scanf_s("%d", &h->size);
		h->num = m++;
		h->status = 1;
		h->begin = 0;
		h->next = NULL;
		return h;
	}
}
void xs(Qu* h) {//显示

	Qu* tou = h->next;
	printf("区号\t起始地址   大小\t状态(0为空闲)\n");
	while (tou)
	{
		printf("%d\t%d\t   %d\t%d\n", tou->num, tou->begin, tou->size, tou->status);
		tou = tou->next;
	}
}
void Sort1(Qu* l) { //采用头插法
	Qu* p = l->next, * pre;
	Qu* r = p->next;
	p->next = NULL;
	p = r;
	while (p != NULL) {
		r = p->next;
		pre = l;
		while (pre->next != NULL && pre->next->size < p->size) {
			pre = pre->next;
		}
		p->next = pre->next;
		pre->next = p;
		p = r;
	}
}
void Sort2(Qu* l) { //采用头插法
	Qu* p = l->next, * pre;
	Qu* r = p->next;
	p->next = NULL;
	p = r;
	while (p != NULL) {
		r = p->next;
		pre = l;
		while (pre->next != NULL && pre->next->size > p->size) {
			pre = pre->next;
		}
		p->next = pre->next;
		pre->next = p;
		p = r;
	}
}
Qu* shouci(Qu* h, Qu* x) {//首次算法
	Qu* p, * n; //* u;
	n = h;
	p = h->next;
	int kk = 0;
	while (p)
	{
		if (p->size > x->size && p->status == 0) {
			x->begin = p->begin;
			p->begin = x->begin + x->size;
			p->size = p->size - x->size;
			n->next = x;
			x->next = p;
			kk = 1;
			return p;
			break;
		}
		if (p->size = x->size && p->status == 0) {//刚好相等不用划分
			p->status = 1;
			free(x);
			kk = 1;
			return p;
			break;
		}
		n = p;
		p = p->next;
	}
	if (kk == 0)printf("没有足够空间！\n");
}
Qu* xhshouc(Qu* tou, Qu* h, Qu* x) {//循环首次
	Qu* p, * n, * u;
	int ll = 0;
	u = tou;
	n = tou->next;
	while (n) {
		if (n == h) {
			break;
		}
		u = n;
		n = n->next;
	}
	p = h;
	int kk = 0;
	while (p)
	{
		if (p->size > x->size&& p->status == 0) {
			x->begin = p->begin;
			p->begin = x->begin + x->size;
			p->size = p->size - x->size;
			u->next = x;
			x->next = p;
			kk = 1;
			return p;
			break;
		}
		if (p->size = x->size && p->status == 0) {
			p->status = 1;
			free(x);
			kk = 1;
			return p;
			break;
		}
		p = p->next;
		ll++;
		if (p == NULL)p = tou;
		if (ll > m)break;
	}
	if (kk == 0)printf("没有足够空间！\n");
}
Qu* zuijia(Qu* h, Qu* x) {//最佳
	Sort1(h);
	Qu* p, * n;
	p = h->next;
	n = h;
	int kk = 0;
	while (p)
	{
		if (p->size > x->size&& p->status == 0) {
			x->begin = p->begin;
			p->begin = x->begin + x->size;
			p->size = p->size - x->size;
			n->next = x;
			x->next = p;
			kk = 1;
			return p;
			break;
		}
		if (p->size = x->size&& p->status == 0) {
			p->status = 1;
			free(x);
			kk = 1;
			return p;
			break;
		}
		n = p;
		p = p->next;
	}
	if (kk == 0)printf("没有足够空间！\n");
}
Qu* zuicha(Qu* h, Qu* x) {//最差
	Sort2(h);
	Qu* p, * n;
	p = h->next;
	n = h;
	int kk = 0;
	while (p)
	{
		if (p->size > x->size&& p->status == 0) {
			x->begin = p->begin;
			p->begin = x->begin + x->size;
			p->size = p->size - x->size;
			n->next = x;
			x->next = p;
			kk = 1;
			return p;
			break;
		}
		if (p->size = x->size && p->status == 0) {
			p->status = 1;
			free(x);
			kk = 1;
			return p;
			break;
		}
		n = p;
		p = p->next;
	}
	if (kk == 0)printf("没有足够空间！\n");
}
void huishou(Qu *h) {//回收1
	Qu* p = h->next;
	Qu* n, * u;
	n = h;
	int a;
	int kk = 0;
	printf("要回收的区号：");
	scanf_s("%d",&a);
	while (p)
	{
		if (p->num == a) {
			//n->next = p->next;
			//free(p);
			//m--;
			p->status = 0;
			kk = 1;
			break;
		}
		n = p;
		p = p->next;
	}
	if (kk == 0)printf("找不到该分区！\n");
}
void hs(Qu* h) {//回收2
	Qu* p = h->next;
	Qu* n, * u;
	n = h;
	
	while (p)
	{
		if (p->next) {
			if (p->status == 0 && p->next->status == 0) {
				p->next->begin = p->begin;
				p->next->size = p->next->size + p->size;
				p->next->num = p->num;
				n->next = p->next;
				free(p);
				p = n;
			}
		}
		n = p;
		p = p->next;
	}
}
void ff(Qu* h, Qu* x) {//方法
	Qu* head = h;
	int xuanze;
	int kk = 1;
	while (1)
	{
		printf("1.首\t2.循环首    3.最佳\t4.最差\n");
		scanf_s("%d", &xuanze);
		switch (xuanze)
		{
		case 1:
			tin = shouci(head, x);
			break;
		case 2:
			if (tin) {
				xhshouc(head, tin, x);
			}
			else
			{
				tin = shouci(head, x);
			}
			break;
		case 3:
			tin=zuijia(head, x);
			break;
		case 4:
			tin = zuicha(head, x);
			break;
		default:
			printf("重新选择！\n");
			kk = 0;
			break;
		}
		if (kk == 1)break;
	}
}
void main()
{
	Qu* n, * u, * x;
	Qu* head = NULL;
	int xuanze = 0;
	n = u = x = NULL;
	head = creat();
	while (1)
	{
		printf("1.分配内存\t2.回收内存\t0.退出\n");
		scanf_s("%d", &xuanze);
		if (xuanze == 0)break;
		switch (xuanze)
		{
		case 1:
			x = cr();
			ff(head, x);
			break;
		case 2:
			huishou(head);
			hs(head);
			break;
		case 3:
			xs(head);
			break;
		default:
			printf("重新选择！\n");
			xs(head);
			break;
		}
		xs(head);
	}
}```

 
动态分区分配算法的模拟
 
四类算法
首次适应算法(FF)
循环首次适应算法(NF)
最佳适应算法(BF)
最坏适应算法(WF)
  
四类算法流程图
首次适应算法(FF)
循环首次适应算法(NF)
最佳适应算法(BF)
最坏适应算法(WF)
  
源代码
类
代码
Partiton.cs
Program.cs
Setting.cs
Way.cs
Work.cs
  
  
算法截图
主函数截图
 

 
四类算法
 
首次适应算法(FF)
 
在首次适应算法中，是从已建立好的数组中顺序查找，直至找到第-一个大小能满足要求的空闲分区为止，然后再按照作业大小，从该分区中划出一块内存空间分配给请求者，余下的空间令开辟一块新的地址， 大小为原来的大小减去作业大小，若查找结束都不能找到一个满足要求的分区，则此次内存分配失败。
 
循环首次适应算法(NF)
 
该算法是由首次适应算法演变而成，在为进程分配内存空间时，不再是每次都从第一个空间开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到第一个能满足要求的空闲分区，从中划出一块与请求大小相等的内存空间分配给作业。
 
最佳适应算法(BF)
 
最佳适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最小的空闲分区分配给作业。
 
最坏适应算法(WF)
 
最坏适应分配算法是每次为作业分配内存时，扫描整个数组，总是把能满足条件的，又是最大的空闲分区分配给作业。
 
四类算法流程图
 
首次适应算法(FF)
 
 
循环首次适应算法(NF)
 
 
最佳适应算法(BF)
 
 
最坏适应算法(WF)
 
 
源代码
 
类
 
 
代码
 
Partiton.cs
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 内存动态分配
{
    class  Partition
    {
       public String id;
       public int size;
    public Partition() { }
    public Partition(String id,int size)
    {
        this.id = id;
        this.size = size;
    }
     
    }

}

 
Program.cs
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 内存动态分配
{
    class Program
    {
        static void Main(string[] args)
        {
            Setting S=new Setting();
            S.setting();
        }
    }
}


 
Setting.cs
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 内存动态分配
{
    class Setting
    {
        public  void setting()
        {
            int n, m,size;
            string name,id;
            Console.WriteLine("请输入作业个数");
            n = int.Parse(Console.ReadLine());
            Work []work = new Work[n];
            for (int i = 0; i < work.Length; i++)
            {
                work[i] = new Work();
                Console.WriteLine("请输入第{0}个作业的名字和大小", i+1);
                name = Console.ReadLine();
                size = int.Parse(Console.ReadLine());
                work[i].name = name;
                work[i].size =size ;
            }

            Console.WriteLine("请输入空闲分区个数");
            m = int.Parse(Console.ReadLine());
            Partition []freepartition = new Partition[m];
            for(int i=0;i<freepartition.Length;i++)
            {
                freepartition[i] = new Partition();
                Console.WriteLine("请输入第{0}个空闲分区的名字和大小", i + 1);
                id=Console.ReadLine();
                size=int.Parse(Console.ReadLine());
                freepartition[i].id = id;
                
                freepartition[i].size = size;
            }
            Way way = new Way();
            int num;
            Console.WriteLine("========================");
            way.show();
            Console.WriteLine("请输入你想使用算法的序号");
            num = int.Parse(Console.ReadLine());
            while(num!=0)
            {
                switch(n)
                {
                    case 1:way.FirstPartition(freepartition,work);break;
                    case 2: way.CycleFirstPartition(freepartition, work); break;
                    case 3: way.BestPartition(freepartition, work); break;
                    case 4: way.WorstPartition(freepartition, work); break;
                    case 0:Environment.Exit(0);break;
                }
                Console.WriteLine("");
                way.show();
                Console.WriteLine("请输入你想使用算法的序号");
                num = int.Parse(Console.ReadLine());
                
            }
        }
    }

}

 
Way.cs
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 内存动态分配
{

    class Way
    {
        String WorkName;
        String PartitionName;

        public void show()
        {
            Console.WriteLine("1.首次适应算法");
            Console.WriteLine("2.循环首次适应算法");
            Console.WriteLine("3.最佳适应算法");
            Console.WriteLine("4.最坏适应算法");
            Console.WriteLine("0.退出");
        }
        public void FirstPartition(Partition[] freepartition, Work[] works)//首次适应算法
        {
            int i, j;
            Partition[] firstpartition = freepartition;
            for ( i = 0; i < works.Length; i++)
                for ( j = 0; j < firstpartition.Length; j++)
                {
                    if (works[i].size > firstpartition[j].size)
                    {
                        continue;
                    }
                    else
                    {
                        firstpartition[j].size -= works[i].size;
                        PartitionName = firstpartition[j].id;
                        WorkName = works[i].name;
                        Console.WriteLine("作业" + WorkName + "在" + PartitionName + "分区中");
                        break;
                    }
                }
            Console.WriteLine("分配之后剩余的情况:");
            for ( i = 0; i < firstpartition.Length; i++)
            {
                Console.Write(firstpartition[i].size + "         ");
            }
        }

        public void CycleFirstPartition(Partition[] freepartition, Work[] works)//循环首次适应算法
        {
            int j = 1;
            Partition[] Cyclefirstfartition = freepartition;
            for (int i = 0; i < works.Length; i++)
            {
                j = j - 1;
                while (j < Cyclefirstfartition.Length )
                {
                    if (works[i].size > Cyclefirstfartition[j].size)
                        j++;
                    else
                    {
                        Cyclefirstfartition[j].size -= works[i].size;
                        PartitionName = Cyclefirstfartition[j].id;
                        WorkName = works[i].name;
                        Console.WriteLine("作业" + WorkName + "在" + PartitionName + "分区中");
                        break;
                    }
                 }
            }
            Console.WriteLine("分配之后剩余的情况:");
            for (int i = 0; i < Cyclefirstfartition.Length; i++)
            {
                Console.Write(Cyclefirstfartition[i].size + "         ");
            }
        }

        public void BestPartition(Partition[] freepartition, Work[] works)//最佳适应算法
        {
            int i, j, k;
            Partition[] Bestpartition = freepartition;
            for( i=0;i<works.Length;i++)
            {
                 k = 0;
                for(j=0;j<Bestpartition.Length;j++)
                {
                    if(Bestpartition[j].size>=works[i].size)
                    {
                        k = j;
                        break;
                    }
                }
                for(int n=0;n<Bestpartition.Length;n++)
                {
                    if(Bestpartition[n].size<Bestpartition[k].size&&Bestpartition[n].size>=works[i].size)
                    {
                        k = n;
                    }
                }
                Bestpartition[k].size -= works[i].size;
                PartitionName = Bestpartition[k].id;
                WorkName = works[i].name;
                Console.WriteLine("作业" + WorkName + "在" + PartitionName + "分区中");
            }
            Console.WriteLine("分配之后剩余的情况:");
            for ( i = 0; i < Bestpartition.Length; i++)
            {
                Console.Write(Bestpartition[i].size + "         ");
            }
        }

        public void WorstPartition(Partition[]freepartition,Work[]works)
        {
            int i, j, k;
            Partition[] Worstpartition = freepartition;
            for( i=0;i<works.Length;i++)
            {
                 k = 0;
                for( j=0;j<Worstpartition.Length;j++)
                {
                    if(Worstpartition[j].size>=Worstpartition[k].size)
                    {
                        k = j;
                    }
                }
                Worstpartition[k].size -= works[i].size;
                PartitionName = Worstpartition[k].id;
                WorkName = works[i].name;
                Console.WriteLine("作业" + WorkName + "在" + PartitionName + "分区中");  
            }
            Console.WriteLine("分配之后剩余的情况:");
            for ( i = 0; i < Worstpartition.Length; i++)
            {
                Console.Write(Worstpartition[i].size + "         ");
            }
        }//最坏适应算法
    }
}

 
Work.cs
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace 内存动态分配
{
    class Work
    {
        public String name;
        public int size;
        public Work() { }
         public Work(String name,int size)
        {
           this.name = name;
            this.size = size;
        }
    }
}

 
算法截图
 
//（算法中内存可能会出现问题，建议使用时每次选择一项算法，然后重新执行）
 
主函数截图