精华内容
下载资源
问答
  • 分配算法 首次适应算法 最佳适应算法 循环首次适应算法 有流程图 源代码
  • 操作系统 循环首次适应算法 首次适应算法 最佳适应算法 回收内存 分配内存设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。 对分区的管理法可以是下面三种算法: 首次适应算法 循环首次...
  • 实验目的 学会主存空间分配与回收的基本方法首次适应算法和循环首次适应算法 实验原理 理解在连续分区动态的存储管理方式下如何实现贮存空间的分配与回收 采用可变式分区管理使用最佳适应算法实现主存空间的分配与...
  • 操作系统中利用最佳适应算法 最坏适应算法 循环首次适应算法 首次适应算法实现动态内存的分配和回收内存
  • 操作系统实验四主存空间的分配与回收首次适应算法和循环首次适应算法
  • 存储管理实验(3个) 首次适应算法,循环首次适应算法,最佳适应算法
  • #include using namespace std; int FreePartition[100];//空闲分区块数组 ...int FirstPartition[100];...//循环首次适应算法数组 int BestPartition[100];//最佳适应算法数组 int WorstPartiti
    #include<iostream>
    using namespace std;
    
    
    int FreePartition[100];//空闲分区块数组
    int FirstPartition[100];//首次适应算法数组
    int CycleFirstPartition[100];//循环首次适应算法数组
    int BestPartition[100];//最佳适应算法数组
    int WorstPartition[100];//最坏适应算法数组
    int ProcessNeed[100];//每个作业的大小
    int PartitionNum,ProcessNum;//分区块数,作业数
    
    
    //首次适应算法
    void First()
    {
    int i,j;
    char str;
    for(i=0;i<PartitionNum;i++)
    {
    FirstPartition[i]=FreePartition[i];
    }
    for(i=0;i<ProcessNum;i++)//找出第一块满足作业的分区
    for(j=0;j<PartitionNum;j++)
    {
    if(ProcessNeed[i]>FirstPartition[j])
    continue;
    else
    {
    FirstPartition[j]-=ProcessNeed[i];//找到后把分区大小减去作业的大小
                    str='A'+i;
    cout<<"作业"<<str<<"在第"<<j+1<<"块分区中"<<endl;
    break;
    }
    }
    cout<<endl;
    cout<<"分配之后剩余情况:"<<endl;
        for(i=0;i<PartitionNum;i++)
    cout<<FirstPartition[i]<<" ";
    cout<<endl<<endl;
    }
    
    
    //循环首次适应算法
    void CycleFirst()
    {
    int i,j=1;
    char str;
    for(i=0;i<PartitionNum;i++)
    {
    CycleFirstPartition[i]=FreePartition[i];
    }
    for(i=0;i<ProcessNum;i++)
    //for(j=0;j<PartitionNum;j++)
    {
    j=j-1;
    while(j<PartitionNum)
    {
    if(ProcessNeed[i]>CycleFirstPartition[j])
    //continue;
    j++;
    else
    {
    CycleFirstPartition[j]-=ProcessNeed[i];
    str='A'+i;
    cout<<"作业"<<str<<"在第"<<j+1<<"块分区中"<<endl;
    break;
    }
    //j++;
    //cout<<j<<" ";
    if(j==PartitionNum && i!=ProcessNum)
    {
    i=-1;
    }
    }
    }
    cout<<endl;
    cout<<"分配之后剩余情况:"<<endl;
    for(i=0;i<PartitionNum;i++)
    cout<<CycleFirstPartition[i]<<" ";
    cout<<endl<<endl;
    
    
    }
    
    
    //最佳适应算法
    void Best()
    {
    int i,j,k;
    char str;
        for(i=0;i<PartitionNum;i++)
    {
    BestPartition[i]=FreePartition[i];
    }
    for(i=0;i<ProcessNum;i++)
    {
    k=0;
    for(j=0;j<PartitionNum;j++)
    {
    //cout<<BestPartition[j]<<"   "<<ProcessNeed[i]<<endl;
    if(BestPartition[j]>=ProcessNeed[i])
    {
    k=j;
    break;
    }
    }
     for(int n=0;n<PartitionNum;n++)
     {
        if(BestPartition[n]<BestPartition[k] && BestPartition[n]>=ProcessNeed[i])//找最佳的
       k=n;
     }
    BestPartition[k]-=ProcessNeed[i];
    str='A'+i;
    cout<<"作业"<<str<<"在第"<<j+1<<"块分区中"<<endl;
    }
    cout<<endl;
    cout<<"分配之后剩余情况:"<<endl;
    for(i=0;i<PartitionNum;i++)
    cout<<BestPartition[i]<<" ";
    cout<<endl<<endl;
    
    
    }
    
    
    //最坏适应算法
    void Worst()
    {
    int i,j,k;
    char str;
    for(i=0;i<PartitionNum;i++)
    {
    WorstPartition[i]=FreePartition[i];
    }
    for(i=0;i<ProcessNum;i++)
    {
    k=0;
    for(j=0;j<PartitionNum;j++)
    {
    if(WorstPartition[j]>WorstPartition[k])//找到最大的分区
      k=j;
    }
    WorstPartition[k]-=ProcessNeed[i];
    str='A'+i;
    cout<<"作业"<<str<<"在第"<<j+1<<"块分区中"<<endl;
    }
    cout<<endl;
    cout<<"分配之后剩余情况:"<<endl;
    for(i=0;i<PartitionNum;i++)
    cout<<WorstPartition[i]<<" ";
    cout<<endl<<endl;
    }
    
    
    int main()
    {
    int i;
    cout<<"输入分区块数:"<<endl;
    cin>>PartitionNum;
    cout<<"输入每个分区的大小:"<<endl;
    for(i=0;i<PartitionNum;i++)
    cin>>FreePartition[i];
    cout<<"输入作业数:"<<endl;
    cin>>ProcessNum;
    cout<<"输入每个作业的大小:"<<endl;
    for(i=0;i<ProcessNum;i++)
    cin>>ProcessNeed[i];
    cout<<"------------首次适应算法-----------------"<<endl;
    First();
    cout<<"------------循环首次适应算法-------------"<<endl;
        CycleFirst();
    cout<<"------------最佳适应算法-----------------"<<endl;
    Best();
    cout<<"------------最坏适应算法-----------------"<<endl;
    Worst();
    return 0;
    }
    

    展开全文
  • 循环首次适应算法

    千次阅读 2015-07-12 13:47:09
    #include #include #include #include #include #define NULL 0 #define int ElemType #define LEN sizeof(struct MainM) #define minsize 8 int main_mem[1024]; int n; strct MainM ... int si
    #include <stdio.h>
    #include <graphics.h>
    #include <conio.h>
    #include <stdlib.h>
    #include <malloc.h>
    #define NULL 0
    #define int ElemType
    #define LEN sizeof(struct MainM)
    #define minsize 8
    int main_mem[1024];
    int n;
    strct MainM
    {
    	ElemType num;
    	int size;
    	int beign;
    	struct MainM *next,*pre;
    }*start, *node;
    void mem_made()
    {
    	int use_start=random(1023);
    	int use_end=random(96);
    	int i;
    	while(use_start+use_end<1023)
    		{
    			for(i=use_start;i<=use_start+use_end;i++)
    			{
    				man_mem[i]=1;
    			}
    			use_start=random(1023);
    			use_end=random(96);
    		}
    }
    
    void create(void)
    {
    	int i=0;
    	start=(struct MainM*)malloc(LEN);
    	node=start;
    	for(;i<1023;)
    		{
    			if(main_mem[i]==1)
    			{
    				i++;
    				contiune;
    			}
    			else if(main_mem[i]==0)
    			{
    				node->next=(struct MainM*)malloc(LEN);
    				node->next-pre=node;
    				node->begin=i;
    				node->size=1;
    				while((main_mem[++i]==0)&&(i<=1023))
    				{
    					node->size++;
    				}
    				node=node->next;
    			}
    		}
    	node->pre-next=start;
    	start-pre=node-pre;
    	node=start;
    }
    
    int scan(int m)
    {
    	int i=0;
    	int n=0;
    	struct MainM *p;
    	p=node;
    	do
    	{
    		if(m>node->size)
    			node =node->next;
    		else if(m<=node->size)
    		{
    			if(node->size-m<minsize)
    				{
    					for(i=node->begin;i<=((node->begin)+node->size-1):i++)
    					{
    						main_mem[i]=1;
    					}
    					if(start==node)
    					{
    						start=node->next;
    						node->pre->next=start;
    						start->pre=node->pre;
    					}
    					else
    					{
    						node->pre->next=node->next;
    						node->next->pre=node->pre;
    					}
    					node=node->next;
    					p=node;
    					return 1;
    				}
    				else
    				{
    					for(i=node->begin;i<=((node->begin)+m-1)i++)
    					{
    						main_mem[i]=1;
    						node->begin+=m;
    						node->size=m;
    						if(node->size==0)
    						{
    							if(start==node)
    							{
    								start=node->next;
    								node->pre->next=start;
    								start->pre=node->pre;
    							}
    							else
    							{
    								node->pre->next=node->next;
    								node->next->pre=node->pre;
    							}
    						}
    						
    					}
    				node=node->next;
    				p=node;
    				return 1;
    				}
    		}
    	}while(node!=p);
    	return 0;
    }
    
    void print()
    {
    	struct MainM *d;
    	d=start;
    	printf("B:");
    	do
    	{
    		printf("%d\t",d->begin);
    		d=d->next;
    	}while(d!=start);
    	d=start;
    	printf("\nS:");
    	do
    	{
    		printf("%d\t",d->size);
    	}while(d!=start);
    }
    
    void printline()
    {
    	struct MainM *f;
    	f=node;
    	setcolor(7);
    	setlinestyle(8,4,3);
    	line((f->begin)*0.6+10,425,(f-begin)*0.6+10,440);
    	line((f->begin)*0.6+7,436,(f-begin)*0.6+10,440);
    	line((f->begin)*0.6+13,436,(f-begin)*0.6+10,440);
    }
    
    int main(int argc,char *argv[])
    {
    	int i=0;
    	int m=DETECT,d=0;
    	int con=0;
    	initgraph(&m,&d,"C:\\TURBOC2\\BGI");
    	_graphetmem(1024);
    	clrscr();
    	mem_made();
    	create();
    	while(1)
    	{
    		clrscr();
    		cleardevice();
    		setbkcolor(1);
    		setlinestyle(0,0,0);
    		for(i=0;i<1024;i++)
    			{
    				if(main_mem[i]==0)
    				{
    					setcolor(2);
    				}
    				else if(main_mem[i]==1)
    				{
    					setcolor(4);
    				}
    				rectangle(1*0.6+10,400,i*0.6+10.5,420);
    			}
    		for(i=0;i<1024;i++)
    			{
    				if(main_mem[i]==0)
    				{
    					setcolor(2);
    				}
    				else
    					setcolor(0);
    				rectangle(1*0.6+10,440,i*0.6+10.5,460);
    			}
    		printline();
    		for(i=0;i<=1023;i++)
    		{
    			printf("%d",main_mem[i]);
    		}
    		printf("\n********************************************************************************");
    		printf("\nPlease input the requests:\n");
    		scanf("%d",&n);
    		con=scan(n);
    		if(con)
    		{
    			printf("Success!!");
    		}
    		else
    		{
    			printf("Nospace to use!Just wait!!");
    		}
    		getch();
    	}
    	return 0;
    }

    展开全文
  • 模拟动态分区的分配以及回收 ,首次适应算法,循环首次适应算法以及最佳适应算法。
  • #include<stdio.h> #define getpch(type) (type)malloc(sizeof(type) struct LNode { int size; int start; int end; struct LNode *next; struct LNode *front; }*L; /*L 为头指针 */ typedef struct LNode LN;...
  • c的循环首次适应算法

    2011-03-28 03:13:47
    操作系统 循环首次适应算法 回收内存 分配内存设计一个可变式分区分配的存储管理方案。并模拟实现分区的分配和回收过程。
  • 首次适应算法(FF)和循环首次适应算法(NF)原文:https://blog.csdn.net/acm_yuuji/article/details/50410483FF和NF算法都是基于顺序搜索的动态分区分配算法,在内存中检索一块分区分配给作业。如果空间大小合适则分配...

    首次适应算法(FF)和循环首次适应算法(NF)

    FF和NF算法都是基于顺序搜索的动态分区分配算法,在内存中检索一块分区分配给作业。如果空间大小合适则分配,如果找不到空间则等待。

    FF算法按地址递增从头扫描空闲分区,如果找到空闲分区大小>=作业大小则分配。如果扫描完空闲分区表都没有找到分区,则分配失败。

    NF算法和FF算法类似,但是NF算法每次分配都会记录下位置,下次分配的时候从记录的位置开始,循环扫描一遍空闲分区。


    注:回收分区的算法写的和书上不太一样,书上是分配过后把分区从空闲分区链中移除,我是直接分配然后状态为设置为false,所以可能不太一样。








    [cpp]  view plain  copy
    1. //公共模块,负责定义结构体,初始化,显示结果,回收  
    2. //BlockJob.h  
    3. #ifndef BLOCKJOB_H_  
    4. #define BLOCKJOB_H_  
    5.   
    6. #include <vector>  
    7.   
    8. const int MINSIZE = 10;     //最小不可分割分区大小  
    9.   
    10.                             //空闲分区  
    11. typedef struct block  
    12. {  
    13.     int start;  //开始地址  
    14.     int size;   //大小  
    15.     bool state; //分区状态 true:空闲 false:占用  
    16. }block;  
    17.   
    18. //作业  
    19. typedef struct job  
    20. {  
    21.     int size;   //作业大小  
    22.     int start;  //分配的分区首址  
    23.     int BlockSize;  //分配空闲分区的大小(可能大于作业大小)  
    24. };  
    25.   
    26. //初始化空闲分区与作业  
    27. void init(std::vector<block> &BlockList, std::vector<job> &JobList);  
    28.   
    29. //显示结果  
    30. void show(std::vector<block> &BlockList, std::vector<job> &JobList);  
    31.   
    32. //回收分区  
    33. void recycle(std::vector<block> &BlockList, std::vector<job> &JobList);  
    34.   
    35. #endif  
    36.   
    37. //BlockJob.cpp  
    38. #include "BlockJob.h"  
    39. #include <iostream>  
    40. #include <iomanip>  
    41.   
    42. //初始化空闲分区与作业  
    43. void init(std::vector<block> &BlockList, std::vector<job> &JobList)  
    44. {  
    45.     std::cout << "输入空闲分区数: ";  
    46.     int num;  
    47.     std::cin >> num;  
    48.   
    49.     std::cout << "输入空闲分区的起始地址与大小: \n";  
    50.     block temp;  
    51.     for (int i = 0; i < num; ++i)  
    52.     {  
    53.         std::cin >> temp.start >> temp.size;  
    54.         temp.state = true;  
    55.         BlockList.push_back(temp);  
    56.     }  
    57.   
    58.     std::cout << "输入作业数: ";  
    59.     std::cin >> num;  
    60.     std::cout << "输入作业的大小: \n";  
    61.     job tempj;  
    62.     for (int i = 0; i < num; ++i)  
    63.     {  
    64.         std::cin >> tempj.size;  
    65.         tempj.BlockSize = 0;  
    66.         tempj.start = 0;  
    67.         JobList.push_back(tempj);  
    68.     }  
    69. }  
    70.   
    71. //显示结果  
    72. void show(std::vector<block> &BlockList, std::vector<job> &JobList)  
    73. {  
    74.     using std::setw;  
    75.     std::cout.setf(std::ios_base::left);  
    76.   
    77.     std::cout << "空闲分区表: \n";  
    78.     std::cout << setw(10) << "分区号" << setw(10) << "分区大小" << setw(10) << "分区始址" << setw(10) << "状态" << std::endl;  
    79.     int num = 0;  
    80.     for (std::vector<block>::iterator it = BlockList.begin(); it != BlockList.end(); ++it, ++num)  
    81.         std::cout << setw(10) << num << setw(10) << (*it).size << setw(10) << (*it).start << setw(10) << (((*it).state == true) ? "空闲" : "占用") << std::endl;  
    82.   
    83.     std::cout << "作业信息: \n";  
    84.     std::cout << setw(10) << "作业号" << setw(10) << "作业大小" << setw(10) << "分区大小" << setw(10) << "分区始址" << std::endl;  
    85.     num = 0;  
    86.     for (std::vector<job>::iterator it = JobList.begin(); it != JobList.end(); ++it, ++num)  
    87.         std::cout << setw(10) << num << setw(10) << (*it).size << setw(10) << (*it).BlockSize << setw(10) << (*it).start << std::endl;  
    88. }  
    89.   
    90. //回收分区  
    91. void recycle(std::vector<block> &BlockList, std::vector<job> &JobList)  
    92. {  
    93.     std::cout << "输入回收分区的首址: ";  
    94.     int start;  
    95.     std::cin >> start;  
    96.   
    97.     for (std::vector<block>::iterator it = BlockList.begin(); it != BlockList.end(); ++it)  
    98.     {  
    99.         //找到要回收的分区  
    100.         if (start == (*it).start)  
    101.         {  
    102.             //与前一个分区邻接  
    103.             if (it != BlockList.begin() && (*(it - 1)).start + (*(it - 1)).size == (*it).start)  
    104.             {  
    105.                 //与后一个分区邻接  
    106.                 if (it != BlockList.end() - 1 && (*it).start + (*it).size == (*(it + 1)).start)  
    107.                 {  
    108.                     //将前一块分区,要回收的分区,后一块分区合并  
    109.                     (*(it - 1)).size += (*it).size + (*(it + 1)).size;  
    110.                     (*(it - 1)).state = true;  
    111.                     BlockList.erase(it);  
    112.                     BlockList.erase(it);  
    113.                 }  
    114.                 else    //不与后一个分区邻接  
    115.                 {  
    116.                     //将此分区与前一个分区合并  
    117.                     (*(it - 1)).size += (*it).size;  
    118.                     (*(it - 1)).state = true;  
    119.                     BlockList.erase(it);  
    120.                 }  
    121.             }  
    122.             else if(it != BlockList.end()-1 && (*it).start +(*it).size == (*(it+1)).start)  //不与前一个分区邻接,与后一个分区邻接  
    123.             {  
    124.                 //将此分区与后一个分区合并  
    125.                 (*it).size += (*(it + 1)).size;  
    126.                 (*it).state = true;  
    127.                 BlockList.erase(it + 1);  
    128.             }  
    129.             else    //都不邻接  
    130.             {  
    131.                 (*it).state = true;  
    132.             }  
    133.             break;  
    134.         }  
    135.     }  
    136.   
    137.     for (std::vector<job>::iterator it = JobList.begin(); it != JobList.end(); ++it)  
    138.     {  
    139.         if ((*it).start == start)  
    140.         {  
    141.             (*it).BlockSize = (*it).start = 0;  
    142.             break;  
    143.         }  
    144.     }  
    145. }  


    [cpp]  view plain  copy
    1. //FF.cpp  
    2. #include "BlockJob.h"  
    3.   
    4. //FF算法  
    5. void FF(std::vector<block> &BlockList, std::vector<job> &JobList);  
    6.   
    7. int main()  
    8. {  
    9.     std::vector<block> BlockList;  
    10.     std::vector<job> JobList;  
    11.   
    12.     //初始化空闲分区与作业  
    13.     init(BlockList, JobList);  
    14.   
    15.     //FF算法  
    16.     FF(BlockList, JobList);  
    17.   
    18.     //显示结果  
    19.     show(BlockList, JobList);  
    20.   
    21.     //回收分区  
    22.     recycle(BlockList, JobList);  
    23.   
    24.     //显示结果  
    25.     show(BlockList, JobList);  
    26.   
    27.     return 0;  
    28. }  
    29.   
    30. //FF算法  
    31. void FF(std::vector<block> &BlockList, std::vector<job> &JobList)  
    32. {  
    33.     for (std::vector<job>::iterator ItJob = JobList.begin(); ItJob != JobList.end(); ++ItJob)  
    34.     {  
    35.         for (std::vector<block>::iterator ItBlock = BlockList.begin(); ItBlock != BlockList.end(); ++ItBlock)  
    36.         {  
    37.             //分区未被使用且能够装下作业  
    38.             if ((*ItBlock).state && (*ItBlock).size >= (*ItJob).size)  
    39.             {  
    40.                 if ((*ItBlock).size - (*ItJob).size > MINSIZE)   //剩余空间还可以继续分配  
    41.                 {  
    42.                     (*ItBlock).state = false;  
    43.   
    44.                     //修改作业信息,分配空间  
    45.                     (*ItJob).start = (*ItBlock).start;  
    46.                     (*ItJob).BlockSize = (*ItJob).size;  
    47.   
    48.                     //添加新表项  
    49.                     block NewBlock;  
    50.                     NewBlock.start = (*ItBlock).start + (*ItJob).size;  
    51.                     NewBlock.size = (*ItBlock).size - (*ItJob).size;  
    52.                     NewBlock.state = true;  
    53.                     (*ItBlock).size = (*ItJob).size;  
    54.                     BlockList.insert(ItBlock + 1, NewBlock);  
    55.   
    56.                 }  
    57.                 else        //剩余空间不可分配,全部分配给此作业  
    58.                 {  
    59.                     (*ItBlock).state = false;  
    60.   
    61.                     //修改作业信息,分配空间  
    62.                     (*ItJob).start = (*ItBlock).start;  
    63.                     (*ItJob).BlockSize = (*ItBlock).size;  
    64.                 }  
    65.   
    66.                 break;  
    67.             }  
    68.         }  
    69.     }  
    70. }  


    [cpp]  view plain  copy
    1. //NF.cpp  
    2. #include "BlockJob.h"  
    3.   
    4. //NF算法  
    5. void NF(std::vector<block> &BlockList, std::vector<job> &JobList);  
    6.   
    7. int main()  
    8. {  
    9.     std::vector<block> BlockList;  
    10.     std::vector<job> JobList;  
    11.   
    12.     //初始化空闲分区与作业  
    13.     init(BlockList, JobList);  
    14.   
    15.     //NF算法  
    16.     NF(BlockList, JobList);  
    17.   
    18.     //显示结果  
    19.     show(BlockList, JobList);  
    20.   
    21.     //回收分区  
    22.     recycle(BlockList, JobList);  
    23.   
    24.     //显示结果  
    25.     show(BlockList, JobList);  
    26.   
    27.     return 0;  
    28. }  
    29.   
    30. //NF算法  
    31. void NF(std::vector<block> &BlockList, std::vector<job> &JobList)  
    32. {  
    33.     int pos = 0;        //上一次查找的位置  
    34.   
    35.     for (std::vector<job>::iterator ItJob = JobList.begin(); ItJob != JobList.end(); ++ItJob)  
    36.     {  
    37.         std::vector<block>::iterator ItBlock = BlockList.begin() + pos;  
    38.         do {  
    39.             //分区未被使用且能够装下作业  
    40.             if ((*ItBlock).state && (*ItBlock).size >= (*ItJob).size)  
    41.             {  
    42.                 pos = &(*ItBlock) - &BlockList[0];  //记录此次分配位置  
    43.                 if ((*ItBlock).size - (*ItJob).size > MINSIZE)   //剩余空间还可以继续分配  
    44.                 {  
    45.                     (*ItBlock).state = false;  
    46.   
    47.                     //修改作业信息,分配空间  
    48.                     (*ItJob).start = (*ItBlock).start;  
    49.                     (*ItJob).BlockSize = (*ItJob).size;  
    50.   
    51.                     //添加新表项  
    52.                     block NewBlock;  
    53.                     NewBlock.start = (*ItBlock).start + (*ItJob).size;  
    54.                     NewBlock.size = (*ItBlock).size - (*ItJob).size;  
    55.                     NewBlock.state = true;  
    56.                     (*ItBlock).size = (*ItJob).size;  
    57.                     BlockList.insert(ItBlock + 1, NewBlock);  
    58.   
    59.                 }  
    60.                 else        //剩余空间不可分配,全部分配给此作业  
    61.                 {  
    62.                     (*ItBlock).state = false;  
    63.   
    64.                     //修改作业信息,分配空间  
    65.                     (*ItJob).start = (*ItBlock).start;  
    66.                     (*ItJob).BlockSize = (*ItBlock).size;  
    67.                 }  
    68.   
    69.                 break;  
    70.             }  
    71.   
    72.             ++ItBlock;  
    73.             if (ItBlock == BlockList.end())  
    74.                 ItBlock = BlockList.begin();  
    75.         } while (pos != &(*ItBlock) - &BlockList[0]);  
    76.     }  
    77. }  

    展开全文
  • 1.首次适应算法(FF):将所有空闲分区按照地址递增的次序链接,在申请内存分配时,从链首开始查找,将满足需求的第一个空闲分区分配给作业。 void FirstFit() { cout << "***********首次适应算法***********...

    动态分区分配是根据进程的实际需要,动态地址为之分配内存空间,在分配时按照一定的分配算法,从空闲分区表或空闲分区链中选出一分区分配给该作业

    • 1.首次适应算法(FF):将所有空闲分区按照地址递增的次序链接,在申请内存分配时,从链首开始查找,将满足需求的第一个空闲分区分配给作业。

    • 2.循环首次适应算法(NF):将所有空闲分区按照地址递增的次序链接,在申请内存分配时,总是从上次找到的空闲分区的下一个空闲分区开始查找,将满足需求的第一个空闲分区分配给作业

    • 3.最坏适应算法(WF):将所有的空闲分区按照从大到小的顺序形成空闲分区链,在申请内存分配时,总是把满足需求的、最大的空闲分区分配给作业。

    • 4.最佳适应算法(BF): 将所有空闲分区按照从小到大的顺序形成空闲分区链,在申请内存分配时,总是把满足需求的、最小的空闲分区分配给作业。

    源码

    #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 input();
    void display();
    void FirstFit();
    void NextFit();
    void BestFit();
    void WorstFit();
    void selectAlgorithm(int chooceAlgorithm);
    void display();
    
    
    void readDataFunction()
    {
    	cout<<"请输入空闲分区数"<<endl;
    	cin >> PartitionNum;
    		cout << "请输入空闲分区大小" << endl;
    	for (int i = 0; i<PartitionNum; i++)
    	{
    		cin >> FreePartition[i];
    	}
    	cout<<"请输入进程个数"<<endl;
    	cin >> ProcessNum;
    		cout<<"请输入进程名称"<<endl;
    	for (int i = 0; i<ProcessNum; i++)
    	{
    		cin >> ProcessName[i];
    	}
    		cout<<"请输入进程需要分配大小"<<endl;
    	for (int i = 0; i<ProcessNum; i++)
    	{
    		cin >> ProcessNeed[i];
    	}
    }
    
    void input()
    {
    	int chooseAlgorithm = 5;
    	do
    	{
    	//readDataFunction();
    	cout << "请选择实现的算法:" << endl;
    	cout << "*****  1 - 首次适应算法     *****" << endl;
    	cout << "*****  2 - 循环首次适应算法 *****" << endl;
    	cout << "*****  3 - 最佳适应算法     *****" << endl;
    	cout << "*****  4 - 最坏适应算法     *****" << endl;
    	cout << "*****  0 - 结束             *****" << endl;
    		cout << "chooseAlgorithm = ";
    		cin >> chooseAlgorithm;
    		selectAlgorithm(chooseAlgorithm);
    	//display();
    	} while (chooseAlgorithm);
    }
    
    void initial()
    {
    	readDataFunction();   //读取原始数据
    	for (int i = 0; i<PartitionNum; i++)
    	{
    		LeftFreePartition[i] = FreePartition[i];
    		for (int j = 0; j<ProcessNum; j++)
    		{
    			NameProcessToPartition[i][j] = NULL;
    		}
    	}
    	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;
    	}
    
    	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];
    				break;
    			}
    		}
    		LeftFreePartition[best[j].id] = best[j].partitionSize;
    	}
    
    	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<<"  ";
    	}
    	cout << endl << "********结束**********" << endl;
    }
    
    int main()
    {
    	input();
    	return 0;
    }
    
    展开全文
  • 操作系统中的实验,用C语言实现循环首次适应算法的功能
  • 操作系统课程设计 循环首次适应算法的动态分区分配方式模拟(c++实现)报告+源代码打包文件
  • 本算法为循环首次适应算法。 算法:由用户进行初始化,即输入分区的总数及各分区的大小,然后在这个基础上再进行后面的操作。在分配函数中,在本实验中设置一个定位指针,当为作业分配内存空间时,不是从空间分区表...
  • 操作系统“循环首次适应算法”源代码~~~~~~~~~~~~~~~
  • NF 循环首次适应算法 (java)

    千次阅读 2019-12-24 20:08:44
    2. 邻近适应 (循环首次适应)NF 从上一次 查找结束的位置 开始查找 运行结果 -----java 代码 ---- ... * NF 循环首次适应算法 * @author ymj * @Date: 2019/12/24 16:18 */ public class NF { ...
  • 动态分区分配-循环首次适应算法+最佳适应算法

    万次阅读 多人点赞 2016-05-30 14:53:16
    分配算法采用最佳适应算法(内存空闲区按照尺寸大小从小到大的排列)和循环首次适应算法,实现内存的分配与回收。 #include #include #include #include #include using namespace std; int pos,n,Size; //
  • 编译原理与操作系统——循环首次适应算法 (C语言)
  • 操作系统-循环首次适应算法

    万次阅读 2017-11-27 20:30:18
    循环首次适应算法介绍 每次为进程分配空间的时候,从上一次刚分配过的空闲区的下一块开始寻找,比如,初始化的内存空闲区是用户输入的max大小,没有进行回收之前之前必定是只有最后一块是空闲的,但是经过回收之后...
  • 循环首次适应算法 #include<iostream> using namespace std; #include<vector> #include<string> #include<stdlib.h> string bai="○"; string hei="●"; class process { public: int ...
  • 循环首次适应算法(Next Fit): 该算法是首次适应算法的变种。在分配内存空间时,不再每次从表头(链首)开始查找,而是从上次找到空闲区的下一个空闲开始查找,直到找到第一个能满足要求的的空闲区为止,并从中划出...
  • printf("\t1:首次适应算法\n"); printf("\t3:最佳适应算法\n"); printf("\t4:最佳适应算法\n"); printf("\t0:退出\n"); printf("\t输入您要的选项:\n"); scanf("%d",&m); } }
  • } } void NextFit() { cout ***********循环首次适应算法***********" ; initial(); int i, nextPoint = 0; bool isWhile; for (i = 0; i { isWhile = true; while (isWhile) { if (LeftFreePartition[nextPoint] >...
  • 湖南师范大学 信息科学与工程学院 操作系统课程实验报告 ...参照教材P137-P140的内容,编写一个C程序,用char *malloc(unsigned size)函数向系统申请一次内存空间(如size=1000,单位为字节),用循环首次适应算法
  • } } } //循环首次适应算法 public static void firstAdapt(int length, ArrayList<Area> area) { System.out.println("循环首次适应算法的分配————————————————...
  • System.out.print("请选择分配算法:"); Scanner in = new Scanner(System.in); int xuanze = in.nextInt(); switch (xuanze){ case 1: fristFit(size);break; case 2: nextFit(size);break; case 3: bestFit(size);...
  • 一、首次适应算法(First Fit):该算法从空闲分区链首开始查找,直至找到一个能满足其大小要求的空闲分区为止。然后再按 照作业的大小,从该分区中划出一块内存分配给请求者,余下的空闲分区仍留在空闲分区链 中。 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,937
精华内容 3,174
关键字:

循环首次适应算法