精华内容
下载资源
问答
  • 用高级语言编写调试一个内存连续分配中动态分区分配模拟程序,以加深对进程的概念及进程调度算法的理解. 二、实验指导 设计程序模拟内存动态分区分配流程,要求实现三项功能:分配内存、回收内存、显示内存使用...

    动态分区分配算法
    一、实验目的
    用高级语言编写和调试一个内存连续分配中动态分区分配模拟程序,以加深对进程的概念及进程调度算法的理解.
    二、实验指导
    设计程序模拟内存动态分区分配流程,要求实现三项功能:分配内存、回收内存、显示内存使用情况
    内存连续分配动态分区分配流程图如下
    在这里插入图片描述

    回收分区时应考虑分区合并的情况,三种情况,如下图
    在这里插入图片描述

    #include<bits/stdc++.h>
    using namespace std;
    struct PCB
    {
    	string name;
    	int begin;
    	int num;
    	bool status;
    };
    vector<PCB> RAM;
    void menu()
    {
    	printf("1. 分配内存\n");
    	printf("2. 回收内存\n");
    	printf("3. 显示内存使用情况\n");
    	printf("4. 退出\n");
    	printf("\n请输入选择: ");
    }
    void init()
    {
    	RAM.push_back({"空闲",0,1024,false});
    }
    
    void output()
    {
    	printf("\n\t分区号\t作业名\t起始地址\t分区大小\t状态\n");
    	for(int i=0; i<RAM.size(); i++)
    	{
    		cout<<"\t"<<i<<"\t"<<RAM[i].name<<"\t"<<RAM[i].begin<<"\t\t"<<RAM[i].num<<"\t\t"<<RAM[i].status<<endl;
    	}
    	printf("\n\n");
    }
    void Distribution()
    {
    	string name;
    	int num;
    	printf("作业名(字符串): ");
    	cin>>name;
    	printf("作业占内存大小:");
    	scanf("%d",&num);
    	//开始分区,从开始找,状态为0并且分区大小
    	int f = 0;
    	for(int i = 0; i < RAM.size() ; i++)
    	{
    		if(RAM[i].status == false && RAM[i].num>=num)
    		{
    			PCB p = {name,RAM[i].begin,num,true};
    			RAM[i].begin = p.num + p.begin;
    			RAM[i].num = RAM[i].num - num;
    			RAM.insert(RAM.begin()+i,p);
    			f = 1;
    			break;
    		}
    	}
    	output();
    	if(f == 0) //没找到
    		printf("\t请求失败!空间不够!\n\n");
    	else
    		printf("\t请求成功!\n\n");
    }
    
    void Recover()
    {
    	string name;
    	printf("输入要回收分区的作业名(字符串): ");
    	cin>> name;
    	for(int i=0; i<RAM.size(); i++)
    	{
    		if(RAM[i].name == name) //找到要回收的作业
    		{
    			if(i == 0) // 如果第一个单独
    			{
    				if(RAM[i+1].status == true)
    				{
    					RAM[i].name = "空闲";
    					RAM[i].status = false;
    					break;
    				}
    				else
    				{
    					RAM[i].status = false;
    					RAM[i].name = "空闲";
    					RAM[i].num += RAM[i+1].num;
    					RAM.erase(RAM.begin()+1);
    					break;
    				}
    			}
    			if(RAM[i-1].status == true && RAM[i+1].status == true) //左右都为 1 ,直接回收
    			{
    				RAM[i].name = "空闲";
    				RAM[i].status = false;
    				break;
    			}
    			else if(RAM[i-1].status == false && RAM[i+1].status == true)
    			{
    				RAM[i-1].num += RAM[i].num;
    				RAM.erase(RAM.begin()+i);
    				break;
    			}
    			else if(RAM[i-1].status == true && RAM[i+1].status == false)
    			{
    				RAM[i].name = "空闲";
    				RAM[i].status = false;
    				RAM[i].num += RAM[i+1].num;
    				RAM.erase(RAM.begin()+i+1);
    				break;
    
    			}
    			else if(RAM[i-1].status == false && RAM[i+1].status == false)
    			{
    				//
    				RAM[i-1].status = false;
    				RAM[i-1].num += (RAM[i].num+RAM[i+1].num);
    				RAM.erase(RAM.begin()+i);
    				RAM.erase(RAM.begin()+i);
    			}
    		}
    	}
    	output();
    //	for(int i=0; i<RAM.size(); i++)
    //	{
    //		cout<<"\t"<<RAM[i].name<<"\t"<<RAM[i].begin<<"\t"<<RAM[i].num<<"\t"<<RAM[i].status<<endl;
    //	}
    }
    int main()
    {
    	int n;
    	init();
    	while(1)
    	{
    		menu();
    
    		scanf("%d",&n);
    		switch (n)
    		{
    			case 1:
    				Distribution();
    				break;
    			case 2:
    				Recover();
    				break;
    			case 3:
    				output();
    				break;
    			case 4:
    				exit(0);
    				break;
    
    		}
    	}
    }
    
    展开全文
  • 七、操作系统——动态分区分配算法(详解)

    千次阅读 多人点赞 2020-05-20 17:45:48
    动态分区分配算法:在动态分区分配方式中,当很多个空闲分区都能满足需求时,应该选择哪个分区进行分配? 二、首次适应算法(First Fit) 算法思想:每次都从低地址开始查找,找到第一个能满足大小的空闲分区。 ...

    一、引入

    动态分区分配算法:在动态分区分配方式中,当很多个空闲分区都能满足需求时,应该选择哪个分区进行分配?
    在这里插入图片描述

    二、首次适应算法(First Fit)

    算法思想:每次都从低地址开始查找,找到第一个能满足大小的空闲分区。
    如何实现空闲分区以地址递增的次序排列。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
    在这里插入图片描述
    在这里插入图片描述

    三、最佳适应算法(Best Fit)

    算法思想:由于动态分区分配是一种连续分配方式,为各进程分配的空间必须是连续的一整片区域。因此为了保证当“大进程”到来时能有连续的大片空间,可以尽可能多地留下大片的空闲区,即优先使用更小的空闲区
    如何实现:空闲分区按容量递增次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
    在这里插入图片描述
    在这里插入图片描述
    缺点:每次都选最小的分区进行分配,会留下越来越多的、很小的、难以利用的内存块。因此这种方法会产生很多的外部碎片

    四、最坏适应算法(Worst Fit)

    又称最大适应算法(Largest Fit)
    算法思想:为了解决最佳适应算法的问题——即留下太多难以利用的小碎片,可以在每次分配时优先使用最大的连续空闲区,这样分配后剩余的空闲区就不会太小,更方便使用。
    如何实现空闲分区按容量递减次序链接。每次分配内存时顺序查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    重新排序:空闲分区按容量递减次序链接
    在这里插入图片描述
    缺点:每次都选最大的分区进行分配,虽然可以让分配后留下的空闲区更大,更可用,但是这种方式会导致较大的连续空闲区被迅速用完。如果之后有“大进程”到达,就没有内存分区可用了

    五、邻近适应算法(Next Fit)

    算法思想:首次适应算法每次都从链头开始查找的。这可能会导致低地址部分出现很多小的空闲分区,而每次分配查找时,都要经过这些分区,因此也增加了查找的开销。如果每次都从上次查找结束的位置开始检索,就能解决上述问题。
    如何实现空闲分区以地址递增的顺序排列(可排成一个循环链表)。每次分配内存时从上次查找结束的位置开始查找空闲分区链(或空闲分区表),找到大小能满足要求的第一个空闲分区。
    在这里插入图片描述
    在这里插入图片描述
    注意:
    对于邻近适应算法首次适应算法,我们是按照地址顺序递增的次序来进行排列的。所以,即使内存空闲区的大小发生了比较大的变化,也不需要对整个链表进行重新排序。这也是这两种算法的算法开销小的原因。而最佳适应算法和最坏适应算法,在回收分区后可能经常需要对空闲分区队列重新排序,因此算法开销大
    在这里插入图片描述

    首次适应算法 VS 邻近适应算法:

    首次适应算法每次都要从头查找,每次都需要检索低地址的小分区。但是这种规则也决定了当低地址部分有更小的分区可以满足需求时,会更有可能用到低地址部分的小分区,也会更有可能把高地址部分的大分区保留下来(最佳适应算法的优点)
    邻近适应算法的规则可能会导致无论低地址、高地址部分的空闲分区都有相同的概率被使用,也就导致了高地址部分的大分区更可能被使用,划分为小分区,最后导致无大分区可用(最佳适应算法的缺点)
    综合来看,四种算法中,首次适应算法的效果反而更好

    六、总结

    在这里插入图片描述

    展开全文
  • 【hive创建动态分区】hive使用动态...因为hive是批处理系统,所以hive提供了一个动态分区功能,其可以基于查询参数的位置去推断分区的名称,从而建立分区。 1.创建一个单一字段分区表 create table dpartition(i...

    【hive创建动态分区】hive使用动态分区插入数据详解

    往hive分区表中插入数据时,如果需要创建的分区很多,比如以表中某个字段进行分区存储,则需要复制粘贴修改很多sql去执行,效率低。因为hive是批处理系统,所以hive提供了一个动态分区功能,其可以基于查询参数的位置去推断分区的名称,从而建立分区。

       1.创建一个单一字段分区表

    create table dpartition(id int ,name string )partitioned by(ct string );

       2.往表里装载数据,并且动态建立分区,以city建立动态分区

    hive.exec.dynamici.partition=true; #开启动态分区,默认是false

    set hive.exec.dynamic.partition.mode=nonstrict; #开启允许所有分区都是动态的,否则必须要有静态分区才能使用。

    insert overwrite table dpartition partition(ct) select id ,name,city from mytest_tmp2_p;

    要点:因为dpartition表中只有两个字段,所以当我们查询了三个字段时(多了city字段),所以系统默认以最后一个字段city为分区名,因为分区表的

    分区字段默认也是该表中的字段,且依次排在表中字段的最后面。所以分区需要分区的字段只能放在后面,不能把顺序弄错。如果我们查询了四个字段的话,则会报

    错,因为该表加上分区字段也才三个。要注意系统是根据查询字段的位置推断分区名的,而不是字段名称。

    hive>--查看可知,hive已经完成了以city字段为分区字段,实现了动态分区。

    show partitions dpartition;

    注意:使用,insert...select 往表中导入数据时,查询的字段个数必须和目标的字段个数相同,不能多,也不能少,否则会报错。但是如果字段的类型不一致的话,则会使用null值填充,不会报错。而使用load data形式往hive表中装载数据时,则不会检查。如果字段多了则会丢弃,少了则会null值填充。同样如果字段类型不一致,也是使用null值填充。

    3.多个分区字段时,实现半自动分区(部分字段静态分区,注意静态分区字段要在动态前面)

    ​​​​创建一个只有一个字段,两个分区字段的分区表

    create table ds_parttion(id int ) partitioned by (state string ,ct string );

    4.往该分区表半动态分区插入数据

    set hive.exec.dynamici.partition=true;

    set hive.exec.dynamic.partition.mode=nonstrict;

    insert overwrite table ds_parttion

    partition(state='china',ct) #state分区为静态,ct为动态分区,以查询的city字段为分区名

    select id ,city from  mytest_tmp2_p; 

    5.多个分区字段时,全部实现动态分区插入数据

    set hive.exec.dynamici.partition=true;

    set hive.exec.dynamic.partition.mode=nonstrict;

    insert overwrite table ds_parttion partition(state,ct) select id ,country,city from mytest_tmp2_p;

    注意:字段的个数和顺序不能弄错。

    6.动态分区表的属性

      使用动态分区表必须配置的参数 :

        set hive.exec.dynamic.partition =true(默认false),表示开启动态分区功能

        set hive.exec.dynamic.partition.mode = nonstrict(默认strict),表示允许所有分区都是动态的,否则必须有静态分区字段

     动态分区相关的调优参数: 

    1. set  hive.exec.max.dynamic.partitions.pernode=100 (默认100,一般可以设置大一点,比如1000)
    2. #表示每个maper或reducer可以允许创建的最大动态分区个数,默认是100,超出则会报错。
    3. set hive.exec.max.dynamic.partitions =1000(默认值) 
    4. #表示一个动态分区语句可以创建的最大动态分区个数,超出报错
    5. set hive.exec.max.created.files =10000(默认)
    6. #全局可以创建的最大文件个数,超出报错。

    参考:https://blog.csdn.net/qq_26442553/article/details/80382174                   https://blog.csdn.net/sunwukong_hadoop/article/details/81334556

    展开全文
  • 【操作系统 - 4】动态分区分配算法

    万次阅读 多人点赞 2017-03-18 19:58:23
    【操作系统 - 4】动态分区分配算法:学习至此,发现很多学了但很久没用的知识,久而久之,慢慢遗忘。等哪天还需要的话,却发现已经忘得差不多了,即使整理了文档(word等),还是得从头再学一遍。读研第一学期,发现...

    操作系统系列

      学习至此,发现很多学了但很久没用的知识,久而久之,慢慢遗忘。等哪天还需要的话,却发现已经忘得差不多了,即使整理了文档(word等),还是得从头再学一遍。读研第一学期,发现很多东西都可以从博客上学习到,也有不少博主呕心沥血整理了挺多有用的博文。于是,本人借此契机,也慢慢开始整理一些博文,不断改进完善中。整理博文(IT)有如下目的:

    • 首要目的:记录“求学生涯”的所学所悟,不断修改,不断更新!(有读者的互动)
    • 其次目的:在这“开源”的时代,整理并分享所学所悟是一种互利的行为!

    博文系列:操作系统课程所学相关算法

    分享目的:希望大家能纠正本人的不足,继续完善程序,共同进步。

    6个实验相关代码的下载地址:http://download.csdn.net/detail/houchaoqun_xmu/9865648

    -------------------------------

    动态分区分配算法

    一、概念介绍和案例解析

      动态分区分配是根据进程的实际需要,动态地为之分配内存空间。在实现可变分区分配时,将涉及到分区分配中所用的数据结构分区分配算法分区的分配与回收操作这样三个问题。
    • 分区分配中的数据结构:
      为了实现分区分配,系统中必须配置相应的数据结构,用来描述空闲分区和已分配分区的情况,为分配提供依据。常用的数据结构有以下两种形式: 
    (1) 空闲分区表。在系统中设置一张空闲分区表,用于记录每个空闲分区的情况。每个空闲分区占一个表目,表目中包括分区序号、分区始址及分区的大小等数据项。
    (2) 空闲分区链。为了实现对空闲分区的分配和链接,在每个分区的起始部分,设置一些用于控制分区分配的信息,以及用于链接各分区所用的前向指针;在分区尾部则设置一后向指针,通过前、后向链接指针,可将所有的空闲分区链接成一个双向链,如下图所示:
      为了检索方便,在分区尾部重复设置状态位和分区大小表目。当分区被分配出去以后,把状态位由“0”改为“1”,此时,前、后向指针已无意义。
    • 分区分配算法:
    1) 首次适应算法(First Fit)
      我们以空闲分区链为例来说明采用FF算法时的分配情况。FF算法要求空闲分区链以地址递增的次序链接。
      -- 在分配内存时,从链首开始顺序查找,直至找到一个大小能满足要求的空闲分区为止;
      -- 然后再按照作业的大小,从该分区中划出一块内存空间分配给请求者,余下的空闲分区仍留在空闲链中。
      -- 若从链首直至链尾都不能找到一个能满足要求的分区,则此次内存分配失败,返回。
      首次适应算法倾向于优先利用内存中低址部分的空闲分区,从而保留了高址部分的大空闲区。这给为以后到达的大作业分配大的内存空间创造了条件。其缺点是低址部分不断被划分,会留下许多难以利用的、很小的空闲分区,而每次查找又都是从低址部分开始,这无疑会增加查找可用空闲分区时的开销。
    2) 循环首次适应算法(Next Fit)
      该算法是由首次适应算法演变而成的。在为进程分配内存空间时,不再是每次都从链首开始查找,而是从上次找到的空闲分区的下一个空闲分区开始查找,直至找到一个能满足要求的空闲分区,从中划出一块与请求大小相等的内存空间分配给作业。
      为实现该算法,应设置一起始查寻指针,用于指示下一次起始查寻的空闲分区,并采用循环查找方式,即如果最后一个(链尾)空闲分区的大小仍不能满足要求,则应返回到第一个空闲分区,比较其大小是否满足要求。找到后,应调整起始查寻指针。
      该算法能使内存中的空闲分区分布得更均匀,从而减少了查找空闲分区时的开销,但这样会缺乏大的空闲分区。 
    3) 最佳适应算法(Best Fit)
      所谓“最佳”是指每次为作业分配内存时,总是把能满足要求、又是最小的空闲分区分配给作业,避免“大材小用”。为了加速寻找,该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样,第一次找到的能满足要求的空闲区,必然是最佳的。
      孤立地看,最佳适应算法似乎是最佳的,然而在宏观上却不一定。因为每次分配后所切割下来的剩余部分总是最小的,这样,在存储器中会留下许多难以利用的小空闲区。 
    4) 最坏适应算法(Worst Fit)
      最坏适应分配算法要扫描整个空闲分区表或链表,总是挑选一个最大的空闲区分割给作业使用,其优点是可使剩下的空闲区不至于太小,产生碎片的几率最小,对中、小作业有利,同时最坏适应分配算法查找效率很高。该算法要求将所有的空闲分区按其容量以从大到小的顺序形成一空闲分区链,查找时只要看第一个分区能否满足作业要求。
      但是该算法的缺点也是明显的,它会使存储器中缺乏大的空闲分区。最坏适应算法与前面所述的首次适应算法、循环首次适应算法、最佳适应算法一起,也称为顺序搜索法。 
    5) 快速适应算法(Quick Fit)
      该算法又称为分类搜索法,是将空闲分区根据其容量大小进行分类,对于每一类具有相同容量的所有空闲分区,单独设立一个空闲分区链表,这样,系统中存在多个空闲分区链表,同时在内存中设立一张管理索引表,该表的每一个表项对应了一种空闲分区类型,并记录了该类型空闲分区链表表头的指针。
      空闲分区的分类是根据进程常用的空间大小进行划分,如2 KB、4 KB、8 KB等,对于其它大小的分区,如7 KB这样的空闲区,既可以放在8 KB的链表中,也可以放在一个特殊的空闲区链表中。 
      该算法的优点是查找效率高,仅需要根据进程的长度,寻找到能容纳它的最小空闲区链表,并取下第一块进行分配即可。另外该算法在进行空闲分区分配时,不会对任何分区产生分割,所以能保留大的分区,满足对大空间的需求,也不会产生内存碎片。
      该算法的缺点是在分区归还主存时算法复杂,系统开销较大。
      此外,该算法在分配空闲分区时是以进程为单位,一个分区只属于一个进程,因此在为进程所分配的一个分区中,或多或少地存在一定的浪费。空闲分区划分越细,浪费则越严重,整体上会造成可观的存储空间浪费,这是典型的以空间换时间的作法。 

    • 分区分配操作:
    3.分区分配操作
      1) 分配内存
      系统应利用某种分配算法,从空闲分区链(表)中找到所需大小的分区。
      设请求的分区大小为u.size,表中每个空闲分区的大小可表示为m.size。若m.size-u.size≤size(size是事先规定的不再切割的剩余分区的大小),说明多余部分太小,可不再切割,将整个分区分配给请求者;
      否则(即多余部分超过size),从该分区中按请求的大小划分出一块内存空间分配出去,余下的部分仍留在空闲分区链(表)中。然后,将分配区的首址返回给调用者。
    2) 回收内存
      当进程运行完毕释放内存时,系统根据回收区的首址,从空闲区链(表)中找到相应的插入点,此时可能出现以下四种情况之一:
      (1) 回收区与插入点的前一个空闲分区F1相邻接,见图4-8(a)。此时应将回收区与插入点的前一分区合并,不必为回收分区分配新表项,而只需修改其前一分区F1的大小,大小为两者之和。
      (2) 回收分区与插入点的后一空闲分区F2相邻接,见图4-8(b)。此时也可将两分区合并,形成新的空闲分区,但用回收区的首址作为新空闲区的首址,大小为两者之和。 
      (3) 回收区同时与插入点的前、后两个分区邻接,见图4-8(c)。此时将三个分区合并,使用F1的表项和F1的首址,取消F2的表项,大小为三者之和。
      (4) 回收区既不与F1邻接,又不与F2邻接。这时应为回收区单独建立一新表项,填写回收区的首址和大小,并根据其首址插入到空闲链中的适当位置。 

      

    二、实验介绍

    • 问题描述:
      设计程序模拟四种动态分区分配算法:首次适应算法循环首次适应算法最佳适应算法最坏适应算法的工作过程。假设内存中空闲分区个数为n,空闲分区大小分别为P1, … ,Pn,在动态分区分配过程中需要分配的进程个数为m(m≤n),它们需要的分区大小分别为S1, … ,Sm,分别利用四种动态分区分配算法将m个进程放入n个空闲分区,给出进程在空闲分区中的分配情况。
    • 程序要求:
    1)利用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法四种动态分区分配算法模拟分区分配过程。
    2)模拟四种算法的分区分配过程,给出每种算法进程在空闲分区中的分配情况。
    3)输入:空闲分区个数n,空闲分区大小P1, … ,Pn,进程个数m,进程需要的分区大小S1, … ,Sm,算法选择1-首次适应算法,2-循环首次适应算法,3-最佳适应算法,4-最坏适应算法。
    4)输出:最终内存空闲分区的分配情况。

    三、程序设计和程序开发

    • 算法思想:
      本程序采用空闲分区表的方式实现,借助数组以及相应的数据结构实现了“首次适应算法”,“循环首次适应算法”,“最佳适应算法”,“最坏适应算法”,其中“最佳适应算法”和“最坏适应算法”需要对分区进行排序,故需要相应的数据结构来保证排序后所对应的分区序列号保持与原分区一致。
      本程序的排序采用冒泡算法,根据排序算法的选择的不同,因其稳定性的不同,会有细微的差别,但不影响算法的实现。
    • 核心算法:
    void FirstFit()
    {
    	cout<<"***********首次适应算法***********"<<endl;
    	initial();
    
    	int i,j;
    	for (i = 0;i<ProcessNum;i++)   //逐个遍历每个进程
    	{
    		for (j = 0;j<PartitionNum;j++)   //每次都从分区的首地址开始查找
    		{
    			if (LeftProcessNeed[i] <= LeftFreePartition[j] && LeftFreePartition!=0)  //当系统内存分区足够大的时候,即分配给进程资源
    			{
    				LeftFreePartition[j] -= LeftProcessNeed[i];   //扣除分配给进程的资源
    				LeftProcessNeed[i] = 0;  //当且仅当系统内存分区足够时才执行,即当前进程大小置0
    
    				NameProcessToPartition[i][j] = ProcessName[i];  //存储各个进程所在的分区位置
    
    				break;   //!!!很重要,一个进程分区完后,应该立即break,进行下一个进程的判断
    			}
    		}
    	}
    
    	display();
    	
    }

    void NextFit()
    {
    	cout<<"***********循环首次适应算法***********"<<endl;
    	initial();
    	int i,nextPoint = 0;
    	bool isWhile;
    	for (i = 0;i<ProcessNum;i++)
    	{
    		isWhile = true;
    		while(isWhile)     //每次都从当前分区的下一个分区开始查找
    		{
    			if (LeftFreePartition[nextPoint] >= LeftProcessNeed[i])
    			{
    				LeftFreePartition[nextPoint] -= LeftProcessNeed[i];
    				LeftProcessNeed[i] = 0;
    				NameProcessToPartition[i][nextPoint] = ProcessName[i];
    				nextPoint++;
    				if (nextPoint > PartitionNum - 1)
    				{
    					nextPoint = 0;  //当j遍历到分区末尾的时候,返回首位置
    				}
    				isWhile = false;
    			}
    			else
    				nextPoint++;
    		}
    	}
    	display();
    }

    void BestFit()
    {
    	//思想:利用冒泡排序对分区大小进行排序,但不改变原分区的位置
    	//创建一个结构体,包括分区大小和所对应的id,排序过程中,每改变顺序一次,id随着改变
    	//关键:每次分配完一个进程的内存大小后,都要重新排序
    	cout<<"***********最佳适应算法***********"<<endl;
    	initial();
    	int i,j,temp,tempID;
    
    	sortNeed best[MAXNUMBER];
    	for (i = 0;i<PartitionNum;i++)
    	{
    		//初始化结构体
    		best[i].partitionSize = FreePartition[i];
    		best[i].id = i;
    	}
    
    	//int count2 = 0;
    
    	for (i = 0;i<ProcessNum;i++)
    	{
    		for (int s = PartitionNum - 1;s > 0;s--)   //冒泡排序(每次分配完一个进程后,都需要重新排序)
    		{
    			for (int t = 0;t < s;t++)
    			{
    				if (best[s].partitionSize < best[t].partitionSize)
    				{
    					temp = best[s].partitionSize;
    					best[s].partitionSize = best[t].partitionSize;
    					best[t].partitionSize = temp;
    
    					tempID = best[s].id;
    					best[s].id = best[t].id;
    					best[t].id = tempID;
    				}
    			}
    		}
    
    		for (j = 0;j<PartitionNum;j++)
    		{
    			if (LeftProcessNeed[i] <= best[j].partitionSize)
    			{
    				best[j].partitionSize -= LeftProcessNeed[i];
    				LeftProcessNeed[i] = 0;			
    
    				NameProcessToPartition[i][best[j].id] = ProcessName[i];
    				//count2++;
    				break;
    			}
    		}
    		LeftFreePartition[best[j].id] = best[j].partitionSize;
    	}
    	//cout<<count2<<endl;
    
    	display();
    }

    void WorstFit()
    {
    	cout<<"***********最坏适应算法***********"<<endl;
    	initial();
    	int i,j,s,t,tempSize,tempID;
    	sortNeed Worst[MAXNUMBER];
    
    	for (i = 0;i<PartitionNum;i++)
    	{
    		Worst[i].partitionSize = FreePartition[i];
    		Worst[i].id = i;
    	}
    
    	for (i = 0;i<ProcessNum;i++)
    	{
    		for (s = PartitionNum - 1;s>0;s--)
    		{
    			for (t = 0; t<s;t++)
    			{
    				if (Worst[s].partitionSize > Worst[t].partitionSize)
    				{
    					tempSize = Worst[s].partitionSize;
    					Worst[s].partitionSize = Worst[t].partitionSize;
    					Worst[t].partitionSize = tempSize;
    
    					tempID = Worst[s].id;
    					Worst[s].id = Worst[t].id;
    					Worst[t].id = tempID;
    				}
    			}
    		}
    
    		for (j = 0;j<PartitionNum;j++)
    		{
    			if (LeftProcessNeed[i] <= Worst[j].partitionSize)
    			{
    				Worst[j].partitionSize -= LeftProcessNeed[i];
    				LeftProcessNeed[j] = 0;
    
    				NameProcessToPartition[i][Worst[j].id] = ProcessName[i];
    				break;
    			}
    		}
    		LeftFreePartition[Worst[j].id] = Worst[j].partitionSize;
    	}
    
    	display();
    
    }

    四、实验结果分析

    • 测试数据:
    9
    16 16 8 32 64 32 8 16 64
    
    
    6
    A B C D E F
    7 18 9 20 35 8
    • 实验结果:

    五、实验源码

    // 操作系统_实验四(动态分区分配算法).cpp : 定义控制台应用程序的入口点。
    //
    
    #include <iostream>
    #include <fstream>
    #include <iomanip>
    using namespace std;
    
    #define MAXNUMBER 100
    static int PartitionNum;  //内存中空闲分区的个数
    static int ProcessNum; //需要分配的进程个数
    static int FreePartition[MAXNUMBER];  //空闲分区对应的内存
    static int ProcessNeed[MAXNUMBER];  //需要分配的进程大小
    
    static int LeftFreePartition[MAXNUMBER];
    static int LeftProcessNeed[MAXNUMBER];
    
    static char ProcessName[MAXNUMBER];
    static char NameProcessToPartition[MAXNUMBER][MAXNUMBER];
    
    typedef struct
    {
    	int partitionSize;
    	int id;
    }sortNeed;
    
    void readDataFunction();
    void display();
    void FirstFit();
    void NextFit();
    void BestFit();
    void WorstFit();
    void selectAlgorithm(int chooceAlgorithm);
    void display();
    
    void readDataFunction()
    {
    	ifstream readData;
    	readData.open("data.txt");
    
    	readData>>PartitionNum;
    	for (int i=0;i<PartitionNum;i++)
    	{
    		readData>>FreePartition[i];
    	}
    
    	readData>>ProcessNum;
    	for (int i=0;i<ProcessNum;i++)
    	{
    		readData>>ProcessName[i];
    	}
    	for (int i=0;i<ProcessNum;i++)
    	{
    		readData>>ProcessNeed[i];
    	}
    }
    
    void initial()
    {
    	readDataFunction();   //读取原始数据
    	for (int i=0;i<ProcessNum;i++)
    	{	
    		for (int j =0;j<PartitionNum;j++)
    		{
    			NameProcessToPartition[i][j] =NULL;
    			LeftFreePartition[j] = FreePartition[j];
    		}
    	}
    	for (int i = 0;i<ProcessNum;i++)
    	{
    		LeftProcessNeed[i] = ProcessNeed[i];
    	}
    }
    
    
    void FirstFit()
    {
    	cout<<"***********首次适应算法***********"<<endl;
    	initial();
    
    	int i,j;
    	for (i = 0;i<ProcessNum;i++)   //逐个遍历每个进程
    	{
    		for (j = 0;j<PartitionNum;j++)   //每次都从分区的首地址开始查找
    		{
    			if (LeftProcessNeed[i] <= LeftFreePartition[j] && LeftFreePartition!=0)  //当系统内存分区足够大的时候,即分配给进程资源
    			{
    				LeftFreePartition[j] -= LeftProcessNeed[i];   //扣除分配给进程的资源
    				LeftProcessNeed[i] = 0;  //当且仅当系统内存分区足够时才执行,即当前进程大小置0
    
    				NameProcessToPartition[i][j] = ProcessName[i];  //存储各个进程所在的分区位置
    
    				break;   //!!!很重要,一个进程分区完后,应该立即break,进行下一个进程的判断
    			}
    		}
    	}
    
    	display();
    	
    }
    
    void NextFit()
    {
    	cout<<"***********循环首次适应算法***********"<<endl;
    	initial();
    	int i,nextPoint = 0;
    	bool isWhile;
    	for (i = 0;i<ProcessNum;i++)
    	{
    		isWhile = true;
    		while(isWhile)     //每次都从当前分区的下一个分区开始查找
    		{
    			if (LeftFreePartition[nextPoint] >= LeftProcessNeed[i])
    			{
    				LeftFreePartition[nextPoint] -= LeftProcessNeed[i];
    				LeftProcessNeed[i] = 0;
    				NameProcessToPartition[i][nextPoint] = ProcessName[i];
    				nextPoint++;
    				if (nextPoint > PartitionNum - 1)
    				{
    					nextPoint = 0;  //当j遍历到分区末尾的时候,返回首位置
    				}
    				isWhile = false;
    			}
    			else
    				nextPoint++;
    		}
    	}
    	display();
    }
    
    void BestFit()
    {
    	//思想:利用冒泡排序对分区大小进行排序,但不改变原分区的位置
    	//创建一个结构体,包括分区大小和所对应的id,排序过程中,每改变顺序一次,id随着改变
    	//关键:每次分配完一个进程的内存大小后,都要重新排序
    	cout<<"***********最佳适应算法***********"<<endl;
    	initial();
    	int i,j,temp,tempID;
    
    	sortNeed best[MAXNUMBER];
    	for (i = 0;i<PartitionNum;i++)
    	{
    		//初始化结构体
    		best[i].partitionSize = FreePartition[i];
    		best[i].id = i;
    	}
    
    	//int count2 = 0;
    
    	for (i = 0;i<ProcessNum;i++)
    	{
    		for (int s = PartitionNum - 1;s > 0;s--)   //冒泡排序(每次分配完一个进程后,都需要重新排序)
    		{
    			for (int t = 0;t < s;t++)
    			{
    				if (best[s].partitionSize < best[t].partitionSize)
    				{
    					temp = best[s].partitionSize;
    					best[s].partitionSize = best[t].partitionSize;
    					best[t].partitionSize = temp;
    
    					tempID = best[s].id;
    					best[s].id = best[t].id;
    					best[t].id = tempID;
    				}
    			}
    		}
    
    		for (j = 0;j<PartitionNum;j++)
    		{
    			if (LeftProcessNeed[i] <= best[j].partitionSize)
    			{
    				best[j].partitionSize -= LeftProcessNeed[i];
    				LeftProcessNeed[i] = 0;			
    
    				NameProcessToPartition[i][best[j].id] = ProcessName[i];
    				//count2++;
    				break;
    			}
    		}
    		LeftFreePartition[best[j].id] = best[j].partitionSize;
    	}
    	//cout<<count2<<endl;
    
    	display();
    }
    
    void WorstFit()
    {
    	cout<<"***********最坏适应算法***********"<<endl;
    	initial();
    	int i,j,s,t,tempSize,tempID;
    	sortNeed Worst[MAXNUMBER];
    
    	for (i = 0;i<PartitionNum;i++)
    	{
    		Worst[i].partitionSize = FreePartition[i];
    		Worst[i].id = i;
    	}
    
    	for (i = 0;i<ProcessNum;i++)
    	{
    		for (s = PartitionNum - 1;s>0;s--)
    		{
    			for (t = 0; t<s;t++)
    			{
    				if (Worst[s].partitionSize > Worst[t].partitionSize)
    				{
    					tempSize = Worst[s].partitionSize;
    					Worst[s].partitionSize = Worst[t].partitionSize;
    					Worst[t].partitionSize = tempSize;
    
    					tempID = Worst[s].id;
    					Worst[s].id = Worst[t].id;
    					Worst[t].id = tempID;
    				}
    			}
    		}
    
    		for (j = 0;j<PartitionNum;j++)
    		{
    			if (LeftProcessNeed[i] <= Worst[j].partitionSize)
    			{
    				Worst[j].partitionSize -= LeftProcessNeed[i];
    				LeftProcessNeed[j] = 0;
    
    				NameProcessToPartition[i][Worst[j].id] = ProcessName[i];
    				break;
    			}
    		}
    		LeftFreePartition[Worst[j].id] = Worst[j].partitionSize;
    	}
    
    	display();
    
    }
    
    void selectAlgorithm(int chooseAlgorithm)
    {
    	switch(chooseAlgorithm)
    	{
    		case 0:break;
    		case 1:FirstFit();break;
    		case 2:NextFit();break;
    		case 3:BestFit();break;
    		case 4:WorstFit();break;
    		default:cout<<"请输入正确的序号:"<<endl;
    	}
    }
    
    void display()
    {
    	int i;
    	cout<<"需要分配内存的进程名:"<<setw(10);
    	for (i = 0;i<ProcessNum;i++)
    	{
    		cout<<ProcessName[i]<<setw(6);
    	}
    	cout<<endl;
    	cout<<"需要分配内存的进程分区大小:"<<setw(4);
    	for (i = 0;i<ProcessNum;i++)
    	{
    		cout<<ProcessNeed[i]<<setw(6);
    	}
    	cout<<endl;
    	cout<<"分配结果:"<<endl;
    
    	cout<<"分区序号:";
    	for (i = 0;i<PartitionNum;i++)
    	{
    		cout<<"分区"<<i+1<<" ";
    	}
    	cout<<endl<<"分区大小:";
    	for (i = 0;i<PartitionNum;i++)
    	{  
    		cout<<FreePartition[i]<<"     ";
    	}
    	cout<<endl<<"剩余大小:";
    	for (i = 0;i<PartitionNum;i++)
    	{
    		cout<<LeftFreePartition[i]<<"     ";
    	}
    	cout<<endl<<"分配进程情况:"<<endl;
    	for (i = 0;i<PartitionNum;i++)
    	{
    		for (int j = 0;j<ProcessNum;j++)
    		{
    			if (NameProcessToPartition[j][i]!=NULL)
    			{
    				cout<<NameProcessToPartition[j][i]<<": (分区"<<i+1<<")"<<endl;
    			}		
    		}	
    	}
    	cout<<endl<<"********结束**********"<<endl;
    }
    
    int main()
    {
    	int chooseAlgorithm = 5;	
    	while(chooseAlgorithm)
    	{
    		cout<<"请选择实现的算法:"<<endl;
    		cout<<"*****  1 - 首次适应算法     *****"<<endl;
    		cout<<"*****  2 - 循环首次适应算法 *****"<<endl;
    		cout<<"*****  3 - 最佳适应算法     *****"<<endl;
    		cout<<"*****  4 - 最坏适应算法     *****"<<endl;
    		cout<<"*****  0 - 结束             *****"<<endl;
    
    		cout<<"chooseAlgorithm = ";
    		cin>>chooseAlgorithm;
    		selectAlgorithm(chooseAlgorithm);
    	}
    	system("pause");
    	return 0;
    }
    


    展开全文
  • 操作系统动态分区分配算法

    万次阅读 多人点赞 2018-12-11 10:15:27
    目的:陆续整理近一年的学习收获 ...在实现可变分区分配时,将涉及到分区分配中所用的数据结构、分区分配算法和分区的分配与回收操作这样三个问题。    首次适应算法(First Fit):  算法...
  • 主要在于静态分区需要手动指定,而动态分区是基于查询参数的位置去推断分区的名称,从而建立分区。总的来说就是,静态分区的列是在编译时期通过用户传递来决定的;动态分区只有在SQL执行时才能确定。 下面举例详细...
  • hive使用动态分区插入数据详解

    万次阅读 多人点赞 2018-05-20 15:21:57
    因为hive是批处理系统,所以hive提供了一个动态分区功能,其可以基于查询参数的位置去推断分区的名称,从而建立分区。 1.创建一个单一字段分区表hive&gt; create table dpartition(id int ,name string ...
  • 系统分区、引导分区启动分区这三个术语则是针对磁盘分区类型划分的。   一、主分区、扩展分区逻辑分区 1、概念 MBR下的硬盘分区有三种,主磁盘分区、扩展磁盘分区、逻辑分区。(ps:现在的GPT分区至少可以...
  • 操作系统动态分区分配算法

    千次阅读 2017-05-20 17:46:38
    动态分区存储管理方式中,主要的操作时分配内存回收内存。 分配内存:请求的分区大小为u.size,空闲分区的大小用m.size表示,如果m.size - u.size size(这里的size表示系统规定的不在切割的剩余分区的大小),即是...
  • 动态分区分配

    千次阅读 2017-10-08 10:31:45
    动态分区分配 动态分区分配是根据进程的实际需要,动态的为之分配内存的空间。总体是按照算法规则找到分配的空闲分区,然后从该分区中再按照作业的大小划出一块内存空间分给作业,该分区余下的空闲分区当做一个新的...
  • Linux文件系统下的分区和挂载

    千次阅读 2018-01-11 14:22:27
    为什么要分区? 方便OS管理,提高系统管理效率大大减少寻找文件所花费的...在传统的磁盘管理中,将一个硬盘分为两大类分区:主分区和扩展分区。主分区是能够安装操作系统,能够进行计算机启动的分区,这样的分区可以
  • 系统动态分区导致无法删除合并

    千次阅读 2012-02-28 23:12:36
    今天给一个朋友维修电脑的时候发现,硬盘所有分区都变成了动态分区,而不是我们常见的主分区和逻辑分区。无从下手,考虑重新安装Win7。 重装的时候,居然发现分区居然无法调整,不能删除,不能合并,郁闷啊。插入XP...
  • 文章目录分区目的分区的创建1....-分为静态分区和动态分区 分区的创建 Hive创建分区时,是通过partitioned by关键字进行创建,要注意的是这个关键字定义的列是表中正式的列,不能与表中其他列名重复
  • 操作系统-动态分区式存贮区管理

    千次阅读 2018-01-11 20:10:45
    (绝对原创,请勿抄袭)(一)、程序功能:模拟动态分区式存贮区管理(二)、设计思路:1、设计一个动态分区式存贮区管理程序,支持不同的放置策略。如首次、最佳、最坏。2、分区描述器中为:flag/size/next;3、自由主存...
  • 计算机操作系统实验三:动态分区分配方式的模拟

    千次阅读 多人点赞 2019-04-24 09:50:23
    了解动态分区分配方式中的数据结构分配算法,并进一步加深对动态分区存储管理方式及其实现过程的理解 2、实验内容 用C语言分别实现采用首次适应算法最佳适应算法的动态分区分配过程回收过程。其中,空闲分区...
  • Hive动态分区详解

    千次阅读 2020-10-06 19:01:47
    因为hive是批处理系统,所以hive提供了一个动态分区功能,其可以基于查询参数的位置去推断分区的名称,从而建立分区。 1、创建一个单一字段分区表 hive> create table dpartition(id int ,name string ) ...
  • 动态分区分配算法

    万次阅读 多人点赞 2016-12-08 17:11:46
    动态分区分配算法 一.顺序搜索的动态分区分配算法 1.首次适应算法(First Fit)  算法思想:将空闲分区链以地址递增的顺序连接;在进行内存分配时,从链首开始顺序查找,直到找到一块分区的大小可以满足需求时,...
  • 安装Ubuntu Linux系统时硬盘分区最合理的方法

    万次阅读 多人点赞 2017-08-13 15:36:20
    无论是安装Windows还是Linux操作系统,硬盘分区都是整个系统安装过程中最为棘手的环节,网上的一些...在讲硬盘分区之前,我先来普及一下硬盘的相关分类,硬盘一般分为IDE硬盘、SCSI硬盘SATA硬盘三种,在Linux系统...
  • 操作系统动态分区分配与回收—C语言实现

    千次阅读 多人点赞 2019-12-13 22:29:49
    这篇文章用来记录操作系统实验之 动态分区分配与回收。 不想从网上copy代码,打算自己从头到尾写一下,没想到却花了我整整两个晚上的时间,好在终于写完了… 动态分区分配采用的算法是最佳适应(best fit, BF)...
  • 操作系统中ESPMSR分区

    万次阅读 2019-03-12 15:48:40
    一:ESP即EFI系统分区: 1.全称EFI System Partition,简写为ESP。msr分区本身没有做任何工作,是保留分区。ESP虽然是一个FAT16或者FAT32格式的物理分区,但是其分区标识是EF(十六进制)而非常规的OE或OC。 因此,该...
  • 电脑需要安装含Linux的双系统,但是参照了亲测UEFI启动模式的电脑安装Win10Ubuntu双系统,但是参照教程时对安装双系统知识掌握不全面,导致重新安装了多次Ubuntu,也即给Ubuntu划分了多次的磁盘分区。 最严重的...
  • 系统移植丨使用傲梅分区助手EasyBCD迁移系统

    万次阅读 多人点赞 2018-12-04 09:00:54
    系统移植丨使用傲梅分区助手EasyBCD迁移系统盘 现在已经有越来越多的网友开始升级使用Windows 10系统,不过对于该系统而言机械硬盘其实比较吃力。 而速度更快的固态硬盘价格相对来说已经越来越便宜,所以大家也...
  • 基于顺序搜索的动态分区分配算法首次适应算法(FF)空闲分区排成一个链,从链首开始查找,知道找到一个大小能满足的要求的分区为止。循环首次适应NF不是每次都是从链首查找,而是从上次找到的空闲分区开始查找,找到...
  • 前几天无意中在扩展磁盘的时候,将磁盘转换为了动态硬盘,然后找个各种方法... 磁盘管理,将黄色的动态分区直接删除卷,再创建一个简单卷,格式化,这个卷还是一个动态 分区,接着来: win + r 输入 cmd 进入管理员...
  • 动态分区分配及可重定位分区分配

    千次阅读 2020-03-23 22:40:39
    动态分区分配及可重定位分区分配 分区大小不固定 分区分配的数据结构 二维表格(连续存储结构) 空闲分区表记录空闲分区的大小,位置状态 已分配区表记录已占用分区的大小,位置状态 双向循环链表(离散...
  • Linux系统分区和挂载

    千次阅读 2016-04-19 19:16:57
    Linux系统分区和挂载linux系统分区Linux分区Windows有很大的区别。在Linux中,没有图形化的分区界面,因此,我们无法看到Windows下C盘、D盘这样的磁盘分区界面。 1. 硬盘分区 硬盘分区的目的:提高管理效率。如果...
  • 原文地址:操作系统实验:动态分区分配方式作者:依然 1. 实验目的: 了解动态分区分配方式中使用的数据结构分配算法,进一步加深对动态分区存储管理方式及其实现过程的理解。提高学生设计实验、发现问题、分析...
  • 内存管理之固定分区和动态分区详解

    万次阅读 多人点赞 2013-05-21 08:30:49
    下面先介绍一个概念: 页:一个固定长度的数据块,存储在二级存储器中(如磁盘)。数据页可以临时复制入内存的页框中。 段:一个变长的数据块,存储在二级存储... 操作系统存储至少要分成两级:内存外存。内存提供

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 561,424
精华内容 224,569
关键字:

动态分区和系统分区