下载文档原格式
3用C语言模拟实现可变式分区存储管理可变式分区存储管理是一种动态分配内存空间的方式，它能够根据进程的内存需求来动态地分配和回收内存空间，提高内存的利用率。
在C语言中，我们可以使用指针和数据结构来模拟实现可变式分区存储管理。
1.使用结构体来表示内存块首先，我们可以定义一个结构体来表示每个内存块的属性，包括起始地址、大小、以及是否被占用等信息。
```cstruct Blockint start_address;int size;int is_allocated; // 0代表未分配，1代表已分配};```2.初始化内存空间接下来，我们可以定义一个数组来表示整个内存空间，该数组的每个元素都是一个 Block 结构体，表示一个内存块。
在程序开始时，我们可以初始化一个 Block 数组，表示整个内存空间的初始状态。
```c#define TOTAL_SIZE 1024 // 内存总大小struct Block memory[TOTAL_SIZE];void init_memormemory[0].start_address = 0;memory[0].size = TOTAL_SIZE;memory[0].is_allocated = 0;```3.分配内存空间当进程需要分配内存空间时，可变式分区存储管理会选择一个合适的内存块来分配给该进程。
我们可以定义一个函数来实现分配内存的过程。
```cint allocate_memory(int size)int i;for (i = 0; i < TOTAL_SIZE; i++)if (!memory[i].is_allocated && memory[i].size >= size)//找到未分配且大小足够的内存块memory[i].is_allocated = 1;memory[i].size -= size;return memory[i].start_address;}}//没有找到合适的内存块return -1;```4.回收内存空间当进程释放已分配的内存空间时，我们需要回收这部分内存，使其变为未分配状态。
动态分区分配方式的模拟动态分区分配方式是计算机中内存管理的一种重要方式。
在动态分区分配方式中，内存空间被分割为多个不同大小的分区，每个分区可以被进程占用。
当一个进程需要内存时，系统会为其分配一个适当大小的分区，进程结束后，该分区将会被释放出来供其他进程使用。
为了更好地理解动态分区分配方式的原理和实际运作，可以通过模拟的方法来观察和分析。
下面是一个简单的动态分区分配方式的模拟过程：假设我们有一块容量为6400KB的内存，要模拟分配4个进程的情况。
这4个进程的内存需求分别是1000KB，2000KB，500KB和300KB。
首先，我们可以将内存划分为几个分区，每个分区的大小根据需要进行调整。
可以设置整块内存为一块分区（大小为6400KB），或者划分成多个较小的分区。
由于这里有4个进程需要分配内存，我们可以为它们设置4个分区，分别为P1，P2，P3和P41.初始状态：内存：[6400KB]（未分配）进程：P1，P2，P3，P4（空）2.分配P1：内存：[1000KB]（P1）、[5400KB]（未分配）进程：P1，P2，P3，P4P1占用了1000KB的内存，剩余空间为5400KB。
3.分配P2：内存：[1000KB]（P1）、[2000KB]（P2）、[3400KB]（未分配）进程：P1，P2，P3，P4P2占用了2000KB的内存，剩余空间为3400KB。
4.分配P3：内存：[1000KB]（P1）、[2000KB]（P2）、[500KB]（P3）、[2900KB]（未分配）进程：P1，P2，P3，P4P3占用了500KB的内存，剩余空间为2900KB。
5.分配P4：内存：[1000KB]（P1）、[2000KB]（P2）、[500KB]（P3）、[300KB]（P4）、[2600KB]（未分配）进程：P1，P2，P3，P4P4占用了300KB的内存，剩余空间为2600KB。
在模拟的过程中，我们可以看到进程在内存中的分配情况和未分配内存的变化。
#include<stdio.h>#include<conio.h>#include<stdlib.h> /* 头文件*/#define VERGE 512 /* 定义内存大小*/typedef struct using{ /* 被占用内存空间大小*/ int num;int from,to;int content;struct using *next;}Use;typedef struct free{ /* 内存空闲区大小*/int from,to;int content;struct free *next;}Free;Use *Umemory;Free *Fmemory;int Unum=0,Fnum=1;void addProcess(int content);void freeProcess(int num);void displayFree();void displayUsing(); /* 所使用子函数*/void main( ){ /* 主函数*/int i;Fnum=1;Fmemory=(Free *)malloc(sizeof(Free));Fmemory->from=0;Fmemory->to=VERGE;Fmemory->content=Fmemory->to-Fmemory->from; Fmemory->next=NULL;Umemory=NULL;while(!kbhit()){ /* 按下键盘任意键结束操作*/i=rand()%2+1;if(Unum-Umemory->num==0||Umemory==NULL)i=2;if(i==1){ /* 释放内存*/i=rand()%(Unum-Umemory->num)+Umemory->num;freeProcess(i);}else{ /* 添加进程*/i=rand()%VERGE;addProcess(i);}displayFree(); /* 显示内存使用情况*/displayUsing(); } }void addProcess(int content){ /* 添加进程*/int i,left=0;Free *p,*minc,*p1,*info;Use *t,*new;p=Fmemory;while(p!=NULL){left+=p->content;p=p->next;}if(content<=0||content>left){printf("add content:%d,left:%d,error\n",content,left);return;}printf("add process:%d\n",content);p=Fmemory;p1=NULL;minc=NULL;while(p!=NULL){if(content<=p->content){minc=p;info=p1;break;}else {p1=info;p=p->next;}}while(p!=NULL){if(p->content<minc->content&&p->content>content){minc=p; info=p1;}else {p1=p;p=p->next;} } /*在剩余空闲区中查找第一个能满足的最小空闲块if(minc!=NULL){if(Umemory==NULL){Umemory=(Use *)malloc(sizeof(Use));Umemory->num=Unum++;Umemory->from=minc->from;Umemory->to=Umemory->from+content;Umemory->content=content;Umemory->next=NULL; }else{ t=Umemory;while(t->next!=NULL)t=t->next;new=(Use *)malloc(sizeof(Use));new->num=Unum++;new->from=minc->from;new->to=new->from+content;new->content=content;new->next=NULL;t->next=new; }minc->from=minc->from+content;minc->content=minc->to-minc->from;if(minc->content==NULL){if(info!=NULL)info->next=minc->next;else Fmemory=minc->next; } } }void freeProcess(int num){ /* 释放内存*/Use *p,*p1;Free *t,*t1,*new;if(num<0||num>=Unum){printf("free: %d error\n",num);return;}p=Umemory;p1=NULL;while(p->num!=num&&p!=NULL){p1=p;p=p->next;}if(p==NULL){printf("free:%d error\n",num);return;}printf("free process:%d,%d,%d,%d\n",num,p->from,p->to,p->content); if(p1!=NULL)p1->next=p->next;else Umemory=Umemory->next;t=Fmemory;t1=NULL;while(t->from<p->to){t1=t;t=t->next;}if(t==Fmemory){if(p->to!=Fmemory->from){t=Fmemory;Fmemory=(Free *)malloc(sizeof(Free));Fmemory->from=p->from;Fmemory->to=p->to;Fmemory->content=p->content;Fmemory->next=t;}else{Fmemory->from=p->from;Fmemory->content=Fmemory->to-Fmemory->from;}}else{if(t1->to==p->from){t1->to=p->to;t1->content=t1->to-t1->from;if(t1->to==t->from){t1->to=t->to;t1->content=t1->to-t1->from;t1->next=t->next;free(t);}}else if(t->from==p->to){t->from=p->from;t->content=t->to-t->from; }else{new=(Free *)malloc(sizeof(Free));new->from=p->from;new->to=p->to;new->content=new->to-new->from;new->next=t;t1->next=new; }} /*合并空闲区*/ free(p);}void displayFree(){ /* 显示空闲区情况*/Free *p;p=Fmemory;if(p!=NULL)printf("The Free Memory:\n");while(p!=NULL){printf("%-3d %-3d %-3d\n",p->from,p->to,p->content);p=p->next; }}void displayUsing(){ /* 显示占用内存情况*/Use *p;p=Umemory;if(p!=NULL)printf("The Using Memory:\n");while(p!=NULL){printf("%-3d%-3d%-3d %-3d\n",p->num,p->from,p->to,p->content); p=p->next; }}。
实验五动态分区分配算法的模拟为了更好地理解动态分区分配算法的工作原理，我们可以进行一次模拟实验。
在实验中，我们将模拟一个内存分区，并使用动态分区分配算法来管理这些分区。
首先，让我们定义一个内存大小为1000字节的分区。
我们假设这个内存中包含几个已分配的分区和几个空闲的分区。
我们使用首次适应算法来进行分区的首次适应分配。
首先，我们将整个内存空间标记为空闲状态，并创建一个初始的空闲链表。
我们假设初始时只有一个空闲分区，大小为1000字节，起始地址为0。
现在，假设有一个进程请求分配一个250字节大小的内存空间。
我们首先检查空闲链表，找到一个大小大于等于250字节的空闲分区。
在这种情况下，我们发现第一个空闲分区的大小是1000字节，所以我们将它拆分成250字节的已分配分区和750字节的空闲分区。
我们在已分配分区上标记一个进程编号，并将空闲分区加入空闲链表。
接下来，假设我们的进程需要申请500字节的内存空间。
在这种情况下，我们需要查找一个大小大于等于500字节的空闲分区。
我们发现第一个可用的空闲分区大小是750字节，我们将它拆分为已分配的500字节和剩余的250字节的空闲分区。
然后，我们假设有进程释放了先前分配的250字节的内存空间。
当一个进程释放分配的内存空间时，我们需要合并相邻的空闲分区。
在这种情况下，释放的分区位于地址0，大小为250字节，并且其下一个分区是地址500，大小为500字节的空闲分区。
因此，我们将这两个分区合并为一个大小为750字节的空闲分区。
接下来，我们假设另一个进程将请求600字节的内存空间。
根据首次适应算法，我们将在第一个满足条件的空闲分区进行分配。
在这种情况下，我们将分配200字节的空闲分区和分配400字节的空闲分区拆分为600字节的已分配分区和空闲分区。
最后，假设一个进程请求200字节的内存空间。
根据首次适应算法，我们在第一个满足条件的空闲分区进行分配。
在这种情况下，我们将250字节的空闲分区拆分为200字节的已分配分区和50字节的空闲分区。
实验五动态分区分配算法的模拟一、实验目的1、加深操作系统内存管理过程的理解2、掌握内存分配算法的基本应用二、实验任务请同学们用C/C++实现一个完整的（可变）动态分区管理器，包括分配，回收，分区碎片整理等。
希望同学们实现如下功能：n 初始化功能：内存状态设置为初始状态。
n 分配功能：要求至少使用两种算法，用户可以选择使用。
n 回收功能：n 空闲块的合并：即紧凑功能，用以消除碎片。
当做碎片整理时，需要跟踪分配的空间，修改其引用以保证引用的正确性。
n 显示当前内存的使用状态，可以使用表格或图形。
三、实验指导1．基本思想动态分区是指系统不预先划分固定分区，而是在装入程序的时候划分内存区域，使得为程序分配的分区大小恰好等于该程序的需求量，且分区的个数是动态的。
显然动态分区有较大的灵活性，较之固定分区能获得好的内存利用率。
2．数据结构动态分区管理可以用两种数据结构实现，一种是已分配区表和空闲区表，也就是用预先定义好的系统空间来存放空间分配信息。
另一种也是最常用的就是空闲链表，由于对分区的操作是动态的，所以很难估计数据结构所占用的空间，而且空闲区表会占用宝贵的系统空间，所以提出了空闲链表的概念。
其特点是用于管理分区的信息动态生成并和该分区在物理地址上相邻。
这样由于可以简单用两个空闲块之间的距离定位已分配空间，不仅节约了系统空间，而且不必维持已分配空间的信息。
本实验是要做一个模拟程序，来模拟动态分区算法的分配和回收过程，并不是真正的去分配和回收内存。
基本的模拟方法有两种：1、先从内存中申请一块存储区，对这块存储区进行模拟的分配和回收活动。
2、不申请存储区，自己定义一块虚拟的存储区，对这块存储区进行模拟的分配和回收活动，分配和回收仅仅是对数据结构的修改而已。
程序代码：#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]){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;}void 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();}。
动态分区分配算法c语言代码动态分区分配算法是操作系统管理内存时不可或缺的一部分。
它能够动态地将物理内存划分成多个分区，并向进程提供所需的内存空间。
因此，使用动态分区分配算法，可以提高操作系统的内存利用率，优化内存管理。
动态分区分配算法的实现非常复杂，但是通过c语言，可以精确地描述出这一算法。
一般而言，动态分区分配算法需要考虑以下几个方面：1. 内部碎片问题：由于分配内存时分配的大小和分区大小并不总是完全匹配，会产生未使用的部分。
动态分区分配算法需要减少这种情况的发生。
2. 外部碎片问题：在进程运行结束后，会留下未使用的内存。
这些未使用的内存小于内存分区大小，被称为外部碎片。
动态分区分配算法需要将这些未使用的小块内存合并起来，以供分配。
在c语言中，动态分区分配算法的实现方式可以借助链表的数据结构，来实现对内存空间的分配与释放。
一个内存分区对应的链表节点，包含了分区的起始地址，分区的大小以及该分区的状态（是否被分配或是否为空）等信息。
下面是一个简单的动态分区分配算法的示例代码。
在这个代码中，初始化时，将整个可用内存视为一个空闲分区，并创建分配内存时使用的节点。
分配内存时，会遍历空闲分区链表，找到第一个大小足够的分区并将其分配。
释放内存时，遍历已分配分区链表，找到需要释放的分区，并将其状态更改为未分配，并将其添加到空闲分区链表中。
```include <stdio.h>include <stdlib.h>include <stdbool.h>// 内存分区结构体typedef struct partition {int size; // 分区大小bool allocated; // 是否被分配struct partition* next; // 下一个分区节点} partition_t;// 全局链表头节点指针partition_t* head;// 初始化函数void initialize(int size) {head = (partition_t*)malloc(sizeof(partition_t));head->size = size;head->allocated = false;head->next = NULL;}// 分配函数void* allocate(int size) {partition_t* current = head;while (current != NULL) {if (current->size >= size && !current->allocated) {if (current->size == size) {current->allocated = true;} else {partition_t* new_part =(partition_t*)malloc(sizeof(partition_t));new_part->size = size;new_part->allocated = true;new_part->next = current->next;current->size -= size;current->next = new_part; }return (void*)(current + 1); }current = current->next;}printf("Memory allocation failed\n"); return NULL;}// 释放函数void free_memory(void* ptr) {partition_t* current = head;partition_t* prev = head;while (current != NULL) {if ((void*)(current + 1) == ptr) { current->allocated = false;// 尝试合并空闲分区节点if (prev != head && !prev->allocated) {prev->size += current->size;prev->next = current->next;free(current);current = prev;}if (current->next != NULL && !current->next->allocated) {current->size += current->next->size;partition_t* temp = current->next;current->next = current->next->next;free(temp);}return;}prev = current;current = current->next;}printf("Memory free failed\n");}int main() {// 初始化内存initialize(1000);// 分配内存int* p = (int*)allocate(sizeof(int));if (p != NULL) {*p = 10;}// 释放内存free_memory(p);return 0;}```在实际应用中，动态分区分配算法可能会使用更加复杂的内存分配方式，例如“首次适应算法”、“最佳适应算法”、“最坏适应算法”等。
计算机操作系统实验报告姓名：班级：学号：题目：动态分区分配方式的模拟实习内容简要描述本次实验要完成两部分内容：一是用C语言实现对采用首次适应算法和最佳适应算法的动态分区分配过程ALLOCo和回收过程FREE（）,其中空闲分区由空闲分区链来管理，进行分配时，系统优先使用空闲区底端空间。
二是假设初始状态下，可用内存空间为640KBO按照题目要求的作业顺序，以及各个作业分配和回收的内存空间。
分别采用首次适应法和最佳适应法，对内存进行分配和回收，要求每次分配和回收后显示空闲内存分区链的情况。
实验分析算法介绍本次实验通过用C语言进行编程并调试、运行，形象地表现出动态分区的分配方式，直观地展现了首次适应算法和最佳适应算法对内存的释放和回收方式之间的区别。
加深了我们对两种算法优缺点的理解，帮助我们了解一些数据结构和分配算法，进一步加深我们对动态分区存储器管理方式及其实现过程的理解。
主要的问题在于，如何解决两种算法对内存的释放和回收空间的表示。
动态分区分配：又称为可变分区分配，这种分配方式并不事先先将主存划分成一块块的分区，而是在作业进入主存时，根据作业的大小动态地建立分区。
并使分区的大小正好适应作业的需要。
因此系统中分区的大小是可变的，分区的数目也是可变的。
分区分配算法：（两者的空闲块链接方式不冋）①首次适应法：为作业选择分区时总是按地址从高到低搜索，只要找到可以容纳该作业的空白块，就把该空白块分配给该作业。
特点：优先利用内存中底地址部分的空闲分区（将所有空闲区，按其地址递增的顺序链接）②最佳适应算法：接到内存申请时，在空闲块表中找到一个不小于请求的最小空块进行分配；为作业选择分区时总是寻找其大小最接近于作业所要求的存储区域。
特点：用最小空间满足要求（将所有空闲区，按其大小递增的顺序联接成空闲区链）结果分析(思考题解答；错误原因分析)间的分配和回收。
思考题解答：1、首次适应算法分配时从表头指针开始查找可利用空间表，将找到的第一个大小不小于“请求”的空闲块的一部分分配给用户。
编写程序实现动态分区存储管理方式的主存分配与回收 c语言以下是一个简单的 C 语言程序示例，实现了动态分区存储管理方式的主存分配与回收：```c#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 1000typedef struct {int size;int address;} MemoryBlock;void allocateMemory(MemoryBlock *blockList, int size) {MemoryBlock *newBlock = (MemoryBlock *)malloc(sizeof(MemoryBlock));if (newBlock == NULL) {printf("内存分配失败\n");exit(1);}newBlock->size = size;newBlock->address = (blockList->address + size) % MAX_SIZE;blockList->address += size;newBlock->next = blockList->next;blockList->next = newBlock;}void freeMemory(MemoryBlock *blockList) {if (blockList->next == NULL) {printf("没有可释放的内存块\n");return;}MemoryBlock *current = blockList->next;blockList->next = current->next;free(current);}int main() {MemoryBlock *blockList = (MemoryBlock *)malloc(sizeof(MemoryBlock));if (blockList == NULL) {printf("内存分配失败\n");exit(1);}blockList->address = 0;blockList->next = NULL;// 内存分配allocateMemory(blockList, 100);allocateMemory(blockList, 200);allocateMemory(blockList, 300);// 输出分配的内存地址MemoryBlock *current = blockList->next;while (current != NULL) {printf("分配的内存大小: %d, 地址: %d\n", current->size, current->address);current = current->next;}// 内存回收freeMemory(blockList);// 输出剩余的内存地址current = blockList->next;while (current != NULL) {printf("剩余的内存大小: %d, 地址: %d\n", current->size,current->address);current = current->next;}freeblockList;return 0;}```上述程序中，我们定义了一个`MemoryBlock`结构体来表示内存块的信息，包括大小和地址。
动态分区分配方式模拟动态分区分配方式的核心思想是将内存划分为若干个不同大小的分区，每个分区可以用来存放一个进程或作为一部分进程的存储区域。
当一个进程需要分配内存时，系统会根据进程的需要选择一个合适大小的空闲分区分配给该进程。
当进程执行完毕后，系统会回收其占用的内存分区，再次将其标记为空闲分区。
首次适应算法（First Fit）是最简单的动态分区分配算法之一、它从内存的起始位置开始，寻找第一个满足进程需要的空闲分区，然后将该分区分配给进程。
首次适应算法的优点是实现简单，且内存利用率较高。
然而，它也有一些缺点，比如容易产生碎片，导致内存的利用率下降。
最佳适应算法（Best Fit）是根据进程需要的内存大小，选择最小的满足条件的空闲分区进行分配。
最佳适应算法可以最大限度地减少碎片的产生，提高内存的利用率。
但是，最佳适应算法的缺点是实现较为复杂，同时由于选择最小的分区进行分配，会导致大量的碎片出现。
最坏适应算法（Worst Fit）与最佳适应算法相反，它选择最大的满足进程需要的空闲分区进行分配。
最坏适应算法的优点是可以减少大型进程的外部碎片，但由于选择最大的分区进行分配，会导致更多的碎片产生。
为了更好地理解动态分区分配方式，我们可以通过一个简单的模拟实例来进行说明。
假设有一块内存大小为1MB，现有以下三个请求需要进行内存分配：1.进程A需要200KB的内存；2.进程B需要400KB的内存；3.进程C需要600KB的内存。
首次适应算法：首先，进程A需要200KB的内存，首次适应算法从内存起始位置开始寻找空闲分区，找到一个大小符合要求的空闲分区，将其分配给进程A。
然后，进程B需要400KB的内存，首次适应算法会从上次分配的位置开始，找到一个大小满足要求的空闲分区，并将其分配给进程B。
最后，进程C需要600KB的内存，首次适应算法会继续从上次分配的位置开始，但发现没有足够的空闲分区，分配失败。
最佳适应算法：最佳适应算法需要对所有空闲分区进行排序，按照分区大小的升序排列。
课程设计课程设计名称：操作系统课程设计专业班级：学生姓名：学号：指导教师：课程设计时间：6月13日-——6月17日计算机科学专业课程设计任务书学生姓名马飞扬专业班级学号题目动态分区分配方式的模拟1课题性质其它课题来源自拟课题指导教师同组姓名主要内容1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。
其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。
2）假设初始状态如下，可用的内存空间为640KB，并有下列的请求序列；作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请50KB；作业6释放60 KB请采用首次适应算法进行内存块的分配和回收，同时显示内存块分配和回收后空闲内存分区链的情况。
任务要求了解动态分区分配中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。
参考文献任满杰等《操作系统原理实用教程》电子工业出版社 2006汤子瀛《计算机操作系统》（修订版）西安电子科技大学出版社 2001张尧学史美林《计算机操作系统教程》实验指导清华大学出版社 2000 罗宇等《操作系统课程设计》机械工业出版社2005审查意见指导教师签字：教研室主任签字：年月日说明：本表由指导教师填写，由教研室主任审核后下达给选题学生，装订在设计（论文）首页1：需求分析（1）用C语言实现采用首次适应算法的动态分区分配过程alloc()和回收过程free()。
其中，空闲分区通过空闲分区链表来管理，在进行内存分配时，系统优先使用空闲区低端的空间。
（2）假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：作业1申请130KB；作业2申请60KB；作业3申请100KB；作业2释放60KB；作业4申请200 KB；作业3释放100 KB；作业1释放130 KB；作业5申请140 KB；作业6申请60 KB；作业7申请50KB；作业6释放60 KB。
编写程序模拟实现内存的动态分区法存储管理。
内存空闲区使用自由链管理，采用最坏适应算法从自由链中寻找空闲区进行分配，内存回收时要与相邻空闲区的合并。
初始状态信息：假定系统的内存共640K，初始状态为操作系统本身占用64K。
将要申请内存的作业信息（存储在document/job.txt文件中），当前时间是0。
输入：用户打开document/job.txt文件，输入作业信息。
处理：模拟时间逐歩增加，每次加1.采用先来先服务算法调度作业，模拟作业运行，用最坏适应算法进行内存的分配。
且进行内存的回收，注意与空闲分区的合并。
直到所以作业运行完成程序结束。
输出：把当前时间为0，为1，为2......的内存分配状况和作业信息写入文件document/information.txt。
设计思路4.1 结点定义//空闲区结点描述typedef struct FreeNode{int length; // 分区长度int address; // 分区起始地址}FreeNode,*PFreeNode;//空闲区自由链表的描述typedef struct FreeLink{FreeNode freeNode;struct FreeLink * next;}FreeLink,*PFreeLink;//内存占用区链表描述typedef struct BusyNode{char name[20];//标明此块内存被哪个进程所占用int length; // 分区长度int address; // 分区起始地址}BusyNode,*PBusyNode;//内存占用区忙碌链表的描述typedef struct BusyLink{BusyNode busyNode;struct BusyLink * next;}BusyLink,*PBusyLink;//作业控制块的结点描述typedef struct JCBNode{char name[20]; //作业名称int length; //作业申请的内存大小int start_time; //作业申请内存的时间，即到达后备作业队列的时间int use_time; //作业占用内存的时间，随着该作业的运行逐渐减小，int state; //作业内存分配描述：//0表示未申请内存，此时作业在后备队列//1表示申请内存成功，作业进入就绪队列//2表示申请内存失败,此时作业插入到后备队列队尾//3表示该作业占用cpu，正在运行//4表示作业运行完成，释放占用的内存}JCBNode,*PJCBNode;//作业队列的描述,用带头结点的循环链表实现typedef struct JCBQueue{JCBNode jcbNode;struct JCBQueue* next;}JCBQueue,*PJCBQueue;4.2 全局变量定义//全局变量#define ALL_MEMORY 640 //系统总内存#define OS_MEMORY 64 //操作系统占用的内存#define SIZE 2 //门限值PFreeLink freeLink; //空闲区自由链表PBusyLink busyLink; //内存占用区链表PJCBQueue jcbQueue; //外存中待分配内存的作业队列PJCBQueue readyQueue; //已分配内存的就绪队列PJCBQueue finishQueue; //已完成的作业队列PJCBNode currentJCB; //当前正在执行的进程(作业)int current_time; //当前时间4.3 算法流程图（已上传，在此没贴出）1.程序总算法流程图如下：此流程图描述了作业从外存进入内存，再到进程完毕的过程。
【操作系统】分区分配算法（⾸次适应算法、最佳适应算法）（C语⾔实现）【操作系统】分区分配算法（⾸次适应算法、最佳适应算法）（C语⾔实现）（编码⽔平较菜，写博客也只是为了个⼈知识的总结和督促⾃⼰学习，如果有错误，希望可以指出）今天测试，发现⼀点问题：1.最佳插⼊算法：对于插⼊的时候忘记修改temp.next.front的指向2.回收头节点的时候现在多了⼀种判断。
判断头节点的下⼀个是否为空。
对如果不为空⽽且后⾯的空闲的话，做出了处理。
原来则没有这⼀情况。
1.动态分区分配算法：为了实现动态分区分配，通常将系统中的空闲分区链接成⼀个链。
所谓顺序查找是指依次搜索空闲分区链上的空闲分区，去寻找⼀个⼤⼩能满⾜要求的分区。
--------计算机操作系统（第四版）2.动态分区算法主要包括四种：（1）.⾸次适应算法（first fit，FF）：要求，空闲分区链以地址递增的顺序链接。
每次从链⾸开始，直到找到第⼀个能满⾜要求的空闲分区为⽌。
简单来说，就是，每次都从第⼀个开始顺序查找，找到⼀块区域可以满⾜要求的。
优点：优先利⽤内存中低址部分的空闲分区，从⽽保留了⾼址部分的⼤空闲区，这为以后到达的⼤作业分配⼤的内存空间创造了条件。
缺点：低址部分不断被划分，会留下许多难以利⽤的，很⼩的空闲分区，称为碎⽚。
⽽每次查找⼜都是从低址部分开始的，这⽆疑⼜会增加查找可⽤空闲分区时的开销。
（2）.循环⾸次适应算法（next fit，NF）：与FF算法区别就是，不是每次都从⾸次开始，⽽是从上次找到的空闲分区的下⼀个空闲分区开始。
（第⼀次查找的话也是从⾸页开始）。
特点：能使内存中的空闲区分布得较均匀。
(3）.最佳适应算法（best，BF）：将所有空闲分区按照空闲分区容量⼤⼩从⼩到⼤的顺序连接起来，形成⼀个空闲分区链。
即，每次都是找空间容量不但可以满⾜要求的空闲区，⽽且该空闲分区的容量还要最接近要求的容量⼤⼩。
优点：每次分配给⽂件的都是最合适该⽂件⼤⼩的分区。
存储管理动态分区分配算法的模拟一(题目: 存储管理--- 动态分区分配算法的模拟二(任务: 设计主界面以灵活选择某算法，且以下算法都要实现:首次适应算法、循环首次适应算法、最佳适应算法;。
三(思想: 对任务进行构思和设想。
(1) 首次适应算法:FF算法要求空闲分区链以地址递增的次序链接。
在分配内存时，从链首开始顺巡查找，直到找到一个大小能够满足要求的空闲分区为止; 然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲区间仍留在空闲链中。
若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。
该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区。
这给为以后到达的大作业分配大的内存空间创造了条件。
(2) 循环首次适应算法该算法是由首次适应算法演变而成的。
在为进程分配内存空间时，不再是每次都从链首开始查找，而是从上次找到的空闲分区的下一个空闲分区开始查找，直至找到一个能满足要求的空闲分区，从中划出一块的请求大小相等的内存空间分配给作业。
为实现该算法，应设置一起始查找指针，用于指示下一次起始查询的空闲分区，并采用循环查找方式，即如果最后一个( 链尾)空闲分区的大小仍不能满足要求，则返回到第一个空闲分区，比较大小是否满足，找到后，应调整起始查询指针。
(3) 最佳适应算法是将最小的空闲分区分配给作业，避免"大材小用"。
为了加速寻找，该算法要求将所有的空闲分区按照某容量以从小到大的顺序形成一空闲分区链。
这样，第一次找到的能满足要求的空闲区，必然是最佳的。
(4) 内存回收:将释放作业所在内存块的状态改为空闲状态，删除其作业名，设置为空。
并判断该空闲块是否与其他空闲块相连，若释放的内存空间与空闲块相连时，则合并为同一个空闲块，同时修改分区大小及起始地址。
四(目的: 在构思中提出要达到的目的。
(1) 按照首次适应算法对内存进行分配，得到(2) 按照循环首次适应算法对内存(3) 按照最佳适应算法对内存进行分配(4) 在作业完成时，释放作业所在内存块，使其能够再次被利用五(方案: 对构思的细化，提出粗略的方案。
实验三使用动态分区分配方式的模拟1、实验目的了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。
2、实验内容(1) 用C语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程alloc( )和回收过程free( )。
其中，空闲分区通过空闲分区链来管理：在进行内存分配时，系统优先使用空闲区低端的空间。
(2) 假设初始状态下，可用的内存空间为640KB，并有下列的请求序列：•作业1申请130KB。
•作业2申请60KB。
•作业3申请100KB。
•作业2释放60KB。
•作业4申请200KB。
•作业3释放100KB。
•作业1释放130KB。
•作业5申请140KB。
•作业6申请60KB。
•作业7申请50KB。
•作业6释放60KB。
请分别采用首次适应算法和最佳适应算法，对内存块进行分配和回收，要求每次分配和回收后显示出空闲分区链的情况。
程序代码——C语言实现#include<stdio.h>#include<stdlib.h>struct node //空闲分区链结点的定义{node *before;node *after;int size;int address;int state;};node L;struct usenode{usenode *next;int num;int add;int size;}U,*n;void Init() //空闲分区链的初始化{node *p;p=(node *)malloc(sizeof(node));p->before=&L;p->after=NULL;p->size=640;p->address=0;p->state=0;L.after=p;L.before=NULL;L.size=0;U.next=NULL;n=&U;}node *search(int a){node *p=L.after;if(p==NULL){printf("没有空闲的区域!");p=NULL;return p;}else{while(p!=NULL && a>p->size)p=p->after;if(p==NULL){printf("没有找到合适的空闲空间!");p=NULL;return p;}elsereturn p;}}void recovery(int a,int b) //内存回收算法{node *c,*s,*r=L.after;node *d=L.after,*e;usenode *k=U.next,*h=&U;while(k!=NULL && a!=k->num){h=k;k=k->next;}if(k==NULL)printf("没有找到这样的作业!");else{h->next=k->next;if(h->next==NULL)n=h;}while(r!=NULL) //若回收得到的空闲块的前方有空闲块合并此空闲块{if(k->add==r->address+r->size){r->size=r->size+k->size;break;}elser=r->after;}if(r==NULL) //若回收得到的空闲块的后面有空闲块合并此空闲块{r=L.after;while(r!=NULL){if(k->add+k->size==r->address){r->address=k->add;r->size=r->size+k->size;break;}elser=r->after;}}while(d!=NULL) //保证空闲链表中没有相邻的空闲空间{if(d->after!=NULL)e=d->after;elsebreak;if(d->address+d->size==e->address){d->after=e->after;while(e->after!=NULL)e->after->before=d;d->size=d->size+e->size;free(e);break;}elsed=d->after;}if(r==NULL){r=L.after;c=(node *)malloc(sizeof(node));c->size=b;c->address=k->add;if(L.after==NULL){c->after=L.after;c->before=&L;L.after=c;}else{r=L.after;while(r!=NULL){if(r->address>c->address){c->after=r;c->before=r->before;r->before->after=c;r->before=c;free(k);return;}elser=r->after;}}}free(k);}void alloc(int a ,int b) //分配内存算法{node *p,*q=L.after;usenode *m;p=search(b);if(p==NULL)return;m=(usenode *)malloc(sizeof(usenode));//生成一个被占用链表的结点,并插入到该链表的尾部m->add=p->address;m->size=b;m->num=a;m->next=n->next;n->next=m;n=m; //保证n始终指向被占用链表的尾部，方便以后新生成结点的插入if(p->size>b) //如果申请空间的大小小于找到空闲空间的大小的处理{p->size=p->size-b;p->address=p->address+b;}else //如果申请空间的大小等于找到空闲空间的大小的处理{p->before->after=p->after;if(p->after!=NULL)p->after->before=p->before;free(p);}}void sort() //对空闲链表进行排序{int max;node *p,*q,*r,*s;node a;p=L.after;while(p!=NULL) //让指针q指向链表的最后一个结点{q=p;p=p->after;}if(L.after->after==NULL)return;else{while(p!=q){s=r=p=L.after;max=r->size;while(s!=q->after){if(s->size>max){max=s->size;r=s;s=s->after;}elses=s->after;}a.size=q->size;a.address=q->address;q->size=r->size;q->address=r->address;r->size=a.size;r->address=a.address;if(q->before->before==&L)return;elseq=q->before;}}}void Print(){node *p=L.after;usenode *q=U.next;int i=1;printf("\n空闲区域列表:\n");printf("FREEID address size\n");while(p!=NULL){printf("%-10d",i);printf("%-10d",p->address);printf("%d\n",p->size);p=p->after;i++;}if(q==NULL)return;else{printf("\n已分配区域列表:\n");printf("WORKID address size\n");while(q!=NULL){printf("%-10d",q->num);printf("%-10d",q->add);printf("%d\n",q->size);q=q->next;}}}void firstfit() //首次适应算法{int a,b,i;Init();Print();while(1){printf("\n1、申请空间\n");printf("2、释放空间\n");printf("3、退出首次适应算法\n");printf("请输入你的选择:");scanf("%d",&i);switch(i){case 1:{printf("请输入申请空间的作业号:");scanf("%d",&a);printf("请输入申请空间的大小:");scanf("%d",&b);alloc(a,b);Print();break;}case 2:{printf("请输入释放空间的作业号:");scanf("%d",&a);printf("请输入释放空间的大小:");scanf("%d",&b);recovery(a,b);Print();break;}case 3:printf("\n");return;}}}void bestfit(){int a,b,i;Init();Print();while(1){printf("\n1、申请空间\n");printf("2、释放空间\n");printf("3、退出最佳适应算法\n");printf("请输入你的选择:");scanf("%d",&i);switch(i){case 1:{printf("请输入申请空间的作业号:");scanf("%d",&a);printf("请输入申请空间的大小:");scanf("%d",&b);alloc(a,b);sort();Print();break;}case 2:{printf("请输入释放空间的作业号:");scanf("%d",&a);printf("请输入释放空间的大小:");scanf("%d",&b);recovery(a,b);sort();Print();break;}case 3:printf("\n");return;}}}void main(){int i;while(1){printf("1、首次适应算法\n");printf("2、最佳适应算法\n");printf("3、退出\n");printf("请输入你的选择:");scanf("%d",&i);switch(i){case 1:firstfit();break;case 2:bestfit();break;case 3:return;}}}运行结果①开始界面②首次适应算法③最佳适应算法程序代码——C++语言实现//*************************************************************** //******** 动态分区分配方式的模拟 *********//***************************************************************#include<iostream.h>#include<stdlib.h>#define Free 0 //空闲状态#define Busy 1 //已用状态#define OK 1 //完成#define ERROR 0 //出错#define MAX_length 640 //最大内存空间为640KBtypedef int Status;typedef struct freearea//定义一个空闲区说明表结构{int ID; //分区号long size; //分区大小long address; //分区地址int state; //状态}ElemType;//---------- 线性表的双向链表存储结构 ------------typedef struct DuLNode //double linked list{ElemType data;struct DuLNode *prior; //前趋指针struct DuLNode *next; //后继指针}DuLNode,*DuLinkList;DuLinkList block_first; //头结点DuLinkList block_last; //尾结点Status alloc(int);//内存分配Status free(int); //内存回收Status First_fit(int,int);//首次适应算法Status Best_fit(int,int); //最佳适应算法void show();//查看分配Status Initblock();//开创空间表Status Initblock()//开创带头结点的内存空间链表{block_first=(DuLinkList)malloc(sizeof(DuLNode));block_last=(DuLinkList)malloc(sizeof(DuLNode));block_first->prior=NULL;block_first->next=block_last;block_last->prior=block_first;block_last->next=NULL;block_last->data.address=0;block_last->data.size=MAX_length;block_last->data.ID=0;block_last->data.state=Free;return OK;}//----------------------- 分配主存 ------------------------- Status alloc(int ch){int ID,request;cout<<"请输入作业(分区号)：";cin>>ID;cout<<"请输入需要分配的主存大小(单位:KB)：";cin>>request;if(request<0 ||request==0){cout<<"分配大小不合适，请重试！"<<endl;return ERROR;}if(ch==2) //选择最佳适应算法{if(Best_fit(ID,request)==OK) cout<<"分配成功！"<<endl; else cout<<"内存不足，分配失败！"<<endl;return OK;}else //默认首次适应算法{if(First_fit(ID,request)==OK) cout<<"分配成功！"<<endl; else cout<<"内存不足，分配失败！"<<endl;return OK;}}//------------------ 首次适应算法 -----------------------Status First_fit(int ID,int request)//传入作业名及申请量{//为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;while(p){if(p->data.state==Free && p->data.size==request){//有大小恰好合适的空闲块p->data.state=Busy;p->data.ID=ID;return OK;break;}if(p->data.state==Free && p->data.size>request){//有空闲块能满足需求且有剩余"temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.size; p->data.size-=request;return OK;break;}p=p->next;}return ERROR;}//-------------------- 最佳适应算法 ------------------------ Status Best_fit(int ID,int request){int ch; //记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); temp->data.ID=ID;temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; //记录最佳插入位置while(p) //初始化最小空间和最佳位置{if(p->data.state==Free &&(p->data.size>request || p->data.size==request) ){q=p;ch=p->data.size-request;break;}p=p->next;}while(p){if(p->data.state==Free && p->data.size==request){//空闲块大小恰好合适p->data.ID=ID;p->data.state=Busy;return OK;break;}if(p->data.state==Free && p->data.size>request){//空闲块大于分配需求if(p->data.size-request<ch)//剩余空间比初值还小{ch=p->data.size-request;//更新剩余最小值q=p;//更新最佳位置指向}}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else{//找到了最佳位置并实现分配temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.size=ch;return OK;}}//----------------------- 主存回收 --------------------Status free(int ID){DuLNode *p=block_first;while(p){if(p->data.ID==ID){p->data.state=Free;p->data.ID=Free;if(p->prior->data.state==Free)//与前面的空闲块相连{p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;}if(p->next->data.state==Free)//与后面的空闲块相连{p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;}break;}p=p->next;}return OK;}//--------------- 显示主存分配情况 ------------------void show(){cout<<"+++++++++++++++++++++++++++++++++++++++\n"; cout<<"+++ 主存分配情况 +++\n";cout<<"+++++++++++++++++++++++++++++++++++++++\n"; DuLNode *p=block_first->next;while(p){cout<<"分区号：";if(p->data.ID==Free) cout<<"Free"<<endl;else cout<<p->data.ID<<endl;cout<<"起始地址："<<p->data.address<<endl;cout<<"分区大小："<<p->data.size<<" KB"<<endl;cout<<"状态：";if(p->data.state==Free) cout<<"空闲"<<endl;else cout<<"已分配"<<endl;cout<<"——————————————"<<endl;p=p->next;}}//----------------------- 主函数---------------------------void main(){int ch;//算法选择标记cout<<" 动态分区分配方式的模拟 \n";cout<<"************************************\n";cout<<"** 1)首次适应算法 2)最佳适应算法 **\n";cout<<"************************************\n";cout<<"请选择分配算法：";cin>>ch;Initblock(); //开创空间表int choice; //操作选择标记while(1){cout<<"********************************************\n"; cout<<"** 1: 分配内存 2: 回收内存 **\n";cout<<"** 3: 查看分配 0: 退出 **\n";cout<<"********************************************\n"; cout<<"请输入您的操作：";cin>>choice;if(choice==1) alloc(ch); // 分配内存else if(choice==2) // 内存回收{int ID;cout<<"请输入您要释放的分区号：";cin>>ID;free(ID);}else if(choice==3) show();//显示主存else if(choice==0) break; //退出else //输入操作有误{cout<<"输入有误，请重试！"<<endl; continue;}}}。
