BJFU_操作系统实验_实验1：进程调度/ 实验2：生产者与消费者/ 实验3：存储管理

迈不过友情╰ 2022-12-29 01:49 255阅读 0赞

### 文章目录 ###

*   *   *  操作系统实验
         *  操作系统实验1
         *   *  实验题目：实验1 进程调度
             *  一、实验目的
             *  二、实验内容
             *  三、实验要求
         *  操作系统实验2
         *   *  实验题目：实验2 生产者与消费者
             *  一、实验目的
             *  二、实验内容
             *  三、实验要求
             *  四、实验原理
         *  操作系统实验3
         *   *  实验题目：实验3 存储管理
             *  一、实验目的
             *  二、实验内容
             *  三、实验要求
             *  四、实验说明

### 操作系统实验 ###

### 操作系统实验1 ###

#### 实验题目：实验1 进程调度 ####

#### 一、实验目的 ####

（1）掌握处理机调度及其实现。  
（2）掌握进程状态及其状态转换。  
（3） 掌握进程控制块PCB及其作用。

#### 二、实验内容 ####

进程调度模拟程序：假设有10个进程需要在CPU上执行，三选一：  
先进先出调度算法；0  
基于优先数的调度算法；1  
最短执行时间调度算法 2  
确定这10个进程在CPU上的执行过程。要求每次进程调度时在屏幕上显示：  
当前执行进程；  
就绪队列；  
等待队列

#### 三、实验要求 ####

（1）创建10个进程的PCB，每个PCB包括：进程名、进程状态、优先级（110）、需要在处理机上执行的时间（150ms）、队列指针等。  
（2）初始化10个PCB（产生随机数0或1，分别表示进程处于就绪态或等待态）；rand()%2, rand()%10+1, rand()%50+1。  
（3）根据调度算法选择一个就绪进程在CPU上执行。  
（4）在进程执行过程中，产生随机数0或1，该随机数为1时，将等待队列中的第一个PCB加入就绪队列的对尾。  
（5）在进程执行过程中，产生一个随机数，表示执行进程能在处理机上执行的时间，如果随机时间(1~20ms)大于总需要的时间，则执行完成。如果小于，则从总时间中减去执行时间。  
（6）如果执行进程没有执行完成。则产生随机数0或1，当该随机数为0时，将执行进程加入就绪队列对尾；否则，将执行进程加入等待队列对尾。  
（7）一直到就绪队列为空，程序执行结束。

#include<cstring>
    #include<string>
    #include<stdlib.h>
    #include<iostream>
    using namespace std; 
    typedef struct PCB
    {
        
    	char name;			//进程名
        int priority;		//优先级
        int arrtime;		//到达时间
        int needtime;		//需要运行时间
        int usedtime;		//已用时间
        char state;			//进程状态
    	struct PCB* next;	//队列指针
    }PCB,*pcb;
    pcb Tprocess=new PCB;	//就绪队列的头指针	
    pcb Trear=Tprocess;		//就绪队列的尾指针			
    pcb Wprocess=new PCB;	//等待队列的头指针
    pcb Wrear=Wprocess;		//就绪队列的尾指针			
    void input()			//创建进程 3种 
    {
        
    	cout<<"***************************先来先服务调度算法******************************"<<endl;
    	cout<<"一共创建10个进程"<<endl;
    	for(int i=0;i<10;i++)
    	{
        
    		pcb p=new PCB;			//新的进程 
    		p->name=char(i+65);
    		p->priorityrand()%10+1;	//优先级 先来先服务这个优先级不考虑 
    		//优先级不考虑 
    		p->arrtime=rand()%30+1;//同时到达的…… 
    		p->needtime=rand()%50+1;//需要在处理机上执行的时间（1~50ms）
    		p->usedtime=0;			//已用时间
    		if(rand()%2==0)			//插到等待队列
    		{
        
    			p->state='T'; 
    			Trear->next=p;
    			p->next=NULL;
    			Trear=Trear->next;
    		}   
    		else					//插到就绪队列
    		{
        
    			p->state='W';
    			Wrear->next=p;
    			p->next=NULL;
    			Wrear=Wrear->next;
    		}
    		cout<<"第"<<i+1<<"个进程:"<<"\t进程名:"<<p->name<<"\t达到时间:"<<p->arrtime<<"\t还需时间:"<<p->needtime<<"\t进程状态:"<<p->state<<endl;
    	}
    }
    void display()//显示调度进程时显示就绪队列与等待队列
    {
        
    	cout<<endl<<"********************************"<<endl;
    	cout<<"        就绪队列        "<<endl;
    	pcb fd=Tprocess->next;
    	while(fd)
    	{
        
    		cout<<"进程名,已用时间,还需时间,状态"<<endl;
    		cout<<fd->name<<"\t "<<fd->usedtime<<"\t "<<fd->needtime<<"\t "<<fd->state<<endl;
    		fd=fd->next;
    	}
    	cout<<"        等待队列        "<<endl;
    	fd=Wprocess->next;
    	while(fd)
    	{
        
    		cout<<"进程名,已用时间,还需时间,状态"<<endl;
    		cout<<fd->name<<"\t "<<fd->usedtime<<"\t "<<fd->needtime<<"\t "<<fd->state<<endl;
    		fd=fd->next;
    	}
    	cout<<"********************************"<<endl;
    	cout<<endl;
    }
    void Sort_T()//先来先服务，如果同时到则先输入的进程先执行
    {
        
    	pcb H=Tprocess;
    	int n=0;
    	while(H->next)
    	{
        
    		n++;
    		H=H->next;
    	}
    	cout<<"N="<<n<<endl; 
    	for(int i=0;i<n;i++)
    	{
        
    		H=Tprocess->next;
    		for(int j=0;j<=n-1-i;j++)
            {
        
            	while(H->next)
    			{
        
    	            if(H->arrtime>H->next->arrtime)
    	            {
        
    					/*
    					pcb temp=H;
    	                H=H->next;
    	                H->next=temp;
    	                */
    	                char tname=H->name;			//进程名
    				    H->name=H->next->name;
    				    H->next->name=tname;
    				//	int tpriority;		//优先级
    				   
    				    int tarrtime=H->arrtime;		//到达时间
    				    H->arrtime=H->next->arrtime;
    				    H->next->arrtime=tarrtime;
    				
    				    int tneedtime=H->needtime;		//到达时间	//需要运行时间
    				    H->needtime=H->next->needtime;
    				    H->next->needtime=tneedtime;
    				
    				    int tusedtime=H->usedtime;		//已用时间
    				    H->usedtime=H->next->usedtime;
    				    H->next->usedtime=tusedtime;
    				
    				
    				    char tstate=H->state;			//进程状态
    					H->state=H->next->state;
    				    H->next->state=tstate;
    	            }
    	            H=H->next;
    			} 
    
    	    }
    	}
    	pcb p=Tprocess->next;			//新的进程 
    	while(p)
    	{
        
    		cout<<"进程名:"<<p->name<<"\t达到时间:"<<p->arrtime<<"\t还需时间:"<<p->needtime<<"\t进程状态:"<<p->state<<endl;
    		p=p->next;
    	}	
    }
    int main() 
    {
        
    	input();						//创建进程
    	Sort_T();						//对就绪队列排序,先到达的排在前面
    	int num=0;
    	while(Tprocess->next)			//直到就绪队列为空，程序执行结束
    	{
        
    		num++;
    		cout<<endl<<"这是第"<<num<<"次进程调度"<<endl;
    		display();					//显示就绪队列与等待队列
    		pcb head=Tprocess->next;	//指向就绪队列的队头元素
    		head->state='R';			//正在运行
    		Tprocess->next=Tprocess->next->next;//更新队头元素
    		if(!Tprocess->next)			//更新后发现就绪队列为空，这时要更新尾指针
    			Trear=Tprocess;
    		int choice;	
    		int runtime=rand()%20+1;	//随机运行时间
    		cout<<"当前时刻正在运行的进程:"<<endl;
    		cout<<"进程名:"<<head->name<<"\t已用时间:"<<head->usedtime<<"\t还需时间:"<<head->needtime<<"\t随机运行时间:"<<runtime<<endl;
    		if(Wprocess->next)			//等待队列不为空
    		{
        	
    			pcb p=Wprocess->next;		//指向等待队列的队头元素
    			choice=rand()%2;
    			if(choice==1)				//将等待队列中的第一个PCB加入就绪队列的队尾
    			{
        
    				cout<<"在进程执行过程中，将等待队列的队头元素插入就绪队列的队尾"<<endl;
    				p->state='T';		//状态修改为T，就绪
    				Wprocess->next=Wprocess->next->next;//更新等待队列的队头元素
    				if(!Wprocess->next)
    					Wrear=Wprocess;
    				Trear->next=p;		//插入到就绪队列的队尾，指针后移
    				p->next=NULL;		//处理指针
    				Trear=Trear->next;	//尾指针后移
    			}   
    		}
    		else
    			Wrear=Wprocess;
    		if(runtime>=head->needtime)	//当随机时间大于等于还需时间
    		{
        
    			cout<<"该进程运行完:"<<endl;	
    			head->usedtime=head->usedtime+head->needtime;
    			head->needtime=0;
    			head->state ='F';		
    		}
    		else
    		{
        
    			head->usedtime=head->usedtime+runtime;
    			head->needtime=head->needtime-runtime;
    			choice=rand()%2;
    			if(choice==0)		
    			{
        
    				cout<<"该进程未运行完，将该进程插入就绪队列的队尾:"<<endl;
    				head->state='T'; 
    				Trear->next=head;
    				head->next=NULL;
    				Trear=Trear->next;
    			}   
    			else		
    			{
        
    				cout<<"该进程未运行完，将该进程插入等待队列的队尾:"<<endl;
    				head->state='W';
    				Wrear->next=head;
    				head->next=NULL;
    				Wrear=Wrear->next;
    			}
    		}
    		cout<<"进程名:"<<head->name<<"\t已用时间:"<<head->usedtime<<"\t还需时间:"<<head->needtime<<"\t进程状态:"<<head->state<<endl;
    	}
    	display();
    	cout<<"就绪队列为空，程序执行结束"<<endl;
    	return 0;
    }

### 操作系统实验2 ###

#### 实验题目：实验2 生产者与消费者 ####

#### 一、实验目的 ####

通过实验模拟生产者与消费者之间的关系，了解并掌握他们之间的关系及其原理。由此增加对进程同步的问题的了解。

#### 二、实验内容 ####

1由用户指定要产生的进程及其类别，存入进入就绪队列。  
2调度程序从就绪队列中提取一个就绪进程运行。如果申请的资源被阻塞则进入相应的等待队列，调度程序调度就绪队列中的下一个进程。进程运行结束时，会检查对应的等待队列，激活队列中的进程进入就绪队列。运行结束的进程进入over链表。重复这一过程直至就绪队列为空。  
3程序询问是否要继续？如果要转直1开始执行，否则退出程序。

#### 三、实验要求 ####

每个进程有一个进程控制块（PCB）表示。进程控制块可以包含如下信息：进程类型标号、进程系统号、进程状态、进程产品（字符）、进程链指针等等。  
系统开辟了一个缓冲区，大小由buffersize指定。  
程序中有三个链队列，一个链表。一个就绪队列（ready），两个等待队列：生产者等待队列（producer）；消费者等待队列（consumer）。一个链表（over），用于收集已经运行结束的进程  
本程序通过函数模拟信号量的原子操作。

#### 四、实验原理 ####

生产者不断的向缓冲池中写入数据，消费者不断的从缓冲区中读取数据。生产者和消费者对缓冲池的操作是互斥的，即当前只能由一个进程对这个缓冲池进行操作。生产者生产时要判断当前缓冲池是否已满，当缓冲池满时，不能再写入，消费者消费时要判断当前缓冲池是否已空，当缓冲池空时，不能再读取。

#include <iostream>
    using namespace std;
    #define buffersize 3
    typedef struct PCB  
    {
         
    	 int flag;					//进程类型标号 flag=0生产者，flag=1消费者
    	 int id;					//进程系统号
    	 char state;				//进程状态 T就绪 W等待 F完成
    	 char product;				//进程产品名
    	 struct PCB *next;			//进程链指针
    }PCB,*pcb;
    char buffer[buffersize];		//缓冲区:填进程id
    int in=0;						//放入缓冲区指针
    int out=0;						//取走缓冲区指针
    int productnum=0;                //产品数
    int full=0;						//信号量full
    int empty=buffersize;			//信号量empty
    int mutex=1;					//互斥信号量，确保唯一操作
    pcb p;							//存储每次的就绪队头进程
    pcb ready,readytail;			//就绪队列，头尾指针	
    pcb producer,producertail;		//生产者等待队列，头尾指针
    pcb consumer,consumertail;		//消费者等待队列，头尾指针	
    pcb over,overtail;				//完成队列，头尾指针
    void Create();					//创建进程
    void InitList(pcb &head);		//创建链队列
    void Display(pcb processhead);	//输出进程
    pcb Pop(pcb &head,pcb &tail);	//队头进程出队
    void Push(pcb p,pcb &tail);		//进程入队尾
    int P(int &s);					//P操作
    int V(int &s);					//V操作
    void Wakeconsumer();			//唤醒生产者			
    void Wakeproducer();			//唤醒消费者
    int main()
    {
         
    	int yes=1;					//用来询问进程是否继续进行
    	while(yes)
    	{
        
    		Create();										//创建进程
    		while(ready->next!=NULL)						//就绪队列不为空
    		{
        
    			p=Pop(ready,readytail);						//就绪队头出进程
    			if(p->flag==0)								//生产者进程
    			{
        
    				if(P(empty)>=0&&P(mutex)>=0)			//P操作申请临界资源，继续执行本进程，或者等待		
    				{
        					
    					buffer[in]=p->id;					//缓冲区:填写id号码
    					productnum++;						//缓冲区产品数目加1
    					in++;								//放入缓冲区指针加1
    					in=in%buffersize;
    					Push(p,overtail);					//完成队尾入进程		
    					p->state='F';						//修改进程状态
    					cout<<"生产者进程"<<p->id<<"申请资源成功，放入产品后，产品总数为"<<productnum<<",进入over队列"<<endl;
    					V(mutex);
    					V(full);							//V操作
    					Wakeconsumer();						//唤醒消费者
    				}
    				else									//本进程等待
    				{
        
    					cout<<"生产者进程"<<p->id<<"申请资源，不可放产品，进入等待队列"<<endl;
    					Push(p,producertail);				//生产者队尾入进程
    					p->state='W';						//修改进程状态
    				}
    			}
    			else										//消费者进程
    			{
        
    				if(P(full)>=0&&P(mutex)>=0)							//P操作，继续执行本进程，否则本进程等待
    				{
        	 
    					int goods;
    					goods=buffer[out];					//缓冲区:填产品名字
    					productnum--;						//缓冲区产品数目减1		
    					out++;								//取走缓冲区指针加1
    					out=out%buffersize;
    					Push(p,overtail);					//完成队尾入进程
    					p->state='F';						//修改进程状态
    					cout<<"消费者进程"<<p->id<<"申请资源成功，取走产品后，产品总数为"<<productnum<<",进入over队列"<<endl;
    					V(mutex);
    					V(empty);							//V操作
    					Wakeproducer();						//唤醒生产者
    				}
    				else									//本进程等待
    				{
        
    					cout<<"消费者进程"<<p->id<<"申请资源，不可取产品，进入等待队列"<<endl;
    					Push(p,consumertail);				//消费者队尾入进程
    					p->state='W';						//修改进程状态
    				}		
    			}
    			//每此调出一个进程，输出缓冲区和四个链队列的进程信息，以便跟踪
    			cout<<"缓冲区信息如下"<<"放入缓冲区指针:"<<in<<"，取走缓冲区指针:"<<out<<"缓冲区产品数目"<<productnum<<endl;
    			cout<<"第1队列：就绪"<<endl;
    			Display(ready);
    			cout<<"第2队列：生产者等待"<<endl;
    			Display(producer);
    			cout<<"第3队列：消费者等待"<<endl;
    			Display(consumer);
    			cout<<"第4队列：完成"<<endl;
    			Display(over);		
    		}	
    		cout<<"程序是否要继续，继续输入1，否则输入0"<<endl;
    		cin>>yes;
    	}		
    	return 0;
    }
    void InitList(pcb &head)		//创建链队列
    {
        
    	head=new PCB;				//分配内存
    	head->next=NULL;			//处理指针域			
    }
    void Display(pcb processhead)	//显示队列中的所有进程
    {
        
    	if(processhead->next)
    	{
        
    		pcb p=processhead->next;
    		while(p)
    		{
        	
    			cout<<"进程"<<p->id<<"\t\t进程类型:"<<p->flag<<"\t进程号:"<<p->id<<"\t进程状态"<<p->state<<endl;//输出进程信息
    			p=p->next;
    		}
    	 cout<<"****************************"<<endl;
    	}
    	else
    	{
        
    		cout<<"队列为空"<<endl;
    		cout<<"****************************"<<endl;
    	}
    }
    void Push(pcb p,pcb &tail)		//进程入队尾
    {
        
    	tail->next=p;				//进程入队尾
    	p->next=NULL;				//处理指针域
    	tail=tail->next;			//更新尾指针
    }
    pcb Pop(pcb &head,pcb &tail)	//队头出进程
    {
        
    	pcb p=head->next;			//队头出进程
    	head->next=head->next->next;//更新头指针	
    	if(head->next==NULL)		//判断是否更新尾指针
    		tail=head;
    	return p;					//返回队头进程
    }
    void Create()					//创建进程
    {
        
    	cout<<"创建4个队列"<<endl;
    	InitList(ready);			//就绪队列
    	readytail=ready;			//尾指针			
    	InitList(producer);			//生产者等待队列
    	producertail=producer;		//尾指针			
    	InitList(consumer);			//消费者等待队列
    	consumertail=consumer;		//尾指针	
    	InitList(over);				//完成队列
    	overtail=over;				//尾指针
    	cout<<"创建20个进程"<<endl;
    	for(int i=0;i<20;i++)
    	{
        
    		pcb p=new PCB;			//分配内存 
    		p->id=i+1;				//进程号
    		p->state='T';
    		if(rand()%2==0)			
    			p->flag=0;			//0为生产者
    		else				
    			p->flag=1;			//1为消费者
    		cout<<"第"<<i+1<<"个进程:"<<"\t进程类型:"<<p->flag<<"\t进程号:"<<p->id<<"\t进程状态"<<p->state<<endl;//输出进程信息	
    		p->next=NULL;			//处理尾指针	
    		Push(p,readytail);		
    	
    	}
    	cout<<endl<<"**********就绪队列**********"<<endl;
    	Display(ready);
    }
    int P(int &s)					//P操作
    {
        	
    	if(s>=1)
    	{
        
    		s=s-1;
    		return s;
    	}
    	else
    		return -1;
    }
    int V(int &s)					//V操作
    {
        
    	s=s+1;
    	return s;
    }
    void Wakeconsumer()						//唤醒消费者
    {
        				
    	if(consumer->next!=NULL)			//队列不空才能唤醒
    	{
        	
    		p=Pop(consumer,consumertail);	//等待队头出进程
    		Push(p,readytail);				//就绪队尾入进程
    		p->state='T';
    		cout<<"唤醒消费者进程"<<p->id<<"，插入就绪队尾"<<endl;
    	}
    	else
    		cout<<"消费者等待队列为空，没有可唤醒对象"<<endl;
    }
    void Wakeproducer()						//唤醒消费者
    {
        				
    	if(producer->next!=NULL)			//队列不空才能唤醒
    	{
        
    		p=Pop(producer,producertail);	//等待队头出进程
    		Push(p,readytail);				//消费者队尾入进程
    		p->state='T';
    		cout<<"唤醒生产者进程"<<p->id<<"，插入就绪队尾"<<endl;
    	}
    	else
    		cout<<"生产者等待队列为空，没有可唤醒对象"<<endl;
    }

### 操作系统实验3 ###

#### 实验题目：实验3 存储管理 ####

#### 一、实验目的 ####

1．了解可变分区管理方式下如何进行主存的分配；  
2．了解可变分区管理方式下如何进行主存空间的回收。  
3．了解可变分区的调度算法分配策略。

#### 二、实验内容 ####

可变分区调度算法有：最先适应分配算法，最优适应分配算法，最坏适应算法。用户提出内存空间的申请；系统根据申请者的要求，按照一定的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者；当程序执行完毕或主动归还内存资源时，系统要收回它所占用的内存空间或它归还的部分内存空间。  
根据可变分区的主存分配思想，首先设计记录主存使用情况的数据表格，用来记录空闲区和作业占用的区域，即“已分配区表”和“空闲区表”。然后在数据表格上进行主存的分配，其主存分配算法选择一种算法。程序中可选择进行主存分配或主存回收，若是主存分配，输入作业名和所需主存空间大小；若是回收，输入回收作业的作业名，以循环进行主存分配和回收。  
当要装入一个作业时，从空闲区表中查找标志为“未分配”的空闲区，从中找一个能容纳该作业的空闲区。如果找到的空闲区正好等于该作业的长度，则把该分区全部分配给该作业。这时应该把该空闲区登记栏中的标志改为“空”，同时在已分配区表中找到一个标志为“空”的栏目登记新装入作业所占用分区的起始地址、长度和作业名。如果找到的空闲区大于作业长度，则把空闲区分成两部分，一部分用来装入作业，另一部分仍然为空闲区，这时只要修改空闲区的长度，且把新装入的作业登记到已分配区表中。本实验中采用首次适应算法、循环首次适应算法、最坏适应算法中的一种为作业分配主存。  
动态分区方式下回收主存空间时应该检查是否有与归还区相邻的空闲区域。若有，则应该合并成一个空闲区。一个归还区可能有上邻空闲区，也可能有下邻空闲区，或者既有上邻空闲区又有下邻空闲区，或者既无上邻空闲区也无下邻空闲区。  
在实现回收时，首先将作业归还的区域在已分配表中找到，将该栏目的状态变为“空”，然后检查空闲区表中标志为“未分配”栏目，查找是否又相邻空闲区；最后合并空闲区，修改空闲区表。

#### 三、实验要求 ####

由于动态分区的大小是由作业需求量决定的，故分区的长度是预先不固定的，且分区的个数也随主存分配和回收变动。总之，所有分区情况随时可能发生变化，数据表格的设计必须和这个特点相适应。由于分区长度不同，因此设计的表格应该包括分区在主存中的起始地址和长度。由于分配时，空闲区有时会变成两个分区：空闲区和已分分区，回收主存分区时，可能会合并空闲区，这样如果整个主存采用一张表格记录已分分区和空闲区，就会使表格操作繁琐。主存分配时查找空闲区进行分配，然后填写已分配区表，主要操作在空闲区；某个作业执行完后，将该分区变成空闲区，并将其与相邻的空闲区合并，主要操作也在空闲区。由此可见，主存的分配与回收主要时对空闲区的操作。这样为了便于对主存空间的分配与回收，就建立两张分区表记录主存的使用情况：“已分配区表”记录作业占用分区，“空闲区表”记录空闲区。  
这两张表的实现方法一般由两种：链表形式、顺序表形式。在本实验中，可以采用任意一种形式。如果采用顺序表形式，用数组模拟。由于顺序表的长度必须提前固定，所以无论是“已分配区表”还是“空闲区表”都必须事先确定长度。它们的长度必须是系统可能的最大项数，系统运行过程中才不会出错，因此在多数情况下，无论是“已分配表区”还是“空闲区表”都是空闲栏目。已分配区表中除了分区起始地址、长度外，也至少还有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个作业占用分区的登记项，内容为该作业的作业名；空闲区表除了分区起始地址、长度外，也要有一项“标志”，如果是空闲栏目，内容为“空”，如果为某个空闲区的登记项，内容为“未分配”。在实际系统中，这两个表格的内容可能还要多，实验中仅仅使用上述必须的数据。为此，“已分配区表”和“空闲区表”在实验中有如下的结构定义。  
已分配区表的定义：  
\#define n 10 //假定系统允许的最大作业数量为n  
Struct  
\{  
float address; //已分分区起始地址  
float length; //已分分区长度，单位为字节  
int flag; //已分配表区登记栏标志，用0表示空栏目，  
\}used\_table\[n\]; //已分配区表  
空闲区表的定义：  
\#define m 10 //假定系统允许的空闲区表最大为m  
Struct  
\{  
float address; //空闲区起始地址  
float length; //空闲区长度，单位为字节  
int flag; //空闲区表登记栏目用0表示空栏目，1表示未分配  
\}free\_table\[m\]; //空闲区表

#### 四、实验说明 ####

假设内存空间为L=1M，步骤如下：  
初始化：把内存分配为L/512,L/256,L/128，L/64，L/32，L/16，L/8，L/4，L/2,剩下的内存，这样共有10个块。把这10个块的信息填写到空闲表中。  
建立作业队列，10个作业，作业需求内存大小为随机，但是不能超过L，需求0~L/4之间，作业里有一个FLAg参数，表示当前作业请求有没有满足。  
第一步：对作业队列中的每个作业，根据不同的算法，在空闲表里面找到一个内存块，进行分配。如果找到了，则把这个内存块从空闲表移到已分配表。  
第二步：对第一轮分配到的每一个作业，产生一个随机数（0或1），如果为1，则把分配到的内存进行回收，从已分配表转移到空闲表，看看左右的邻居，能不能进行合成一个大块。  
第三步：对第一步没有分配到内存的作业进行分配。  
第四步：与第二步相同。  
第五步：与第三步相同。  
最后全部作业分配了空间为止。  
作业有个FLAG参数，0表示没有分配到内存，1表示已分配到内存，2表示作业已经结束，内存已回收。  
第一步到第五步的操作，就是交替进行一轮分配、一轮回收。对队列中没有分配到内存的作业进行分配，对队列中分配到内存的作业进行随机回收。

#define minisize 100
    #include <iostream>
    #include <iomanip>
    using namespace std;
    #define n 10						//假定系统允许的最大作业数量为n
    #define m 10						//假定系统允许的空闲区表最大为m
    struct								//已分配区表的定义：
    {
        
    	 float address;					//已分分区起始地址
    	 float length;					//已分分区长度，单位为字节
    	 int flag;						//已分配表区登记栏标志，用0表示空栏目
    }used_table[n];						//已分配区表 
    struct								//空闲区表的定义：
    {
        
    	float address;					//空闲区起始地址
    	float length;					//空闲区长度，单位为字节
    	int flag;						//空闲区表登记栏目用0表示空栏目，1表示未分配
    }free_table[m];						//空闲区表
    struct								//作业队列的定义：
    {
        
    	int name;						//作业名
    	float length;					//作业大小
    	int flag;						//0未分配,1已分配,2已完成
    }job[10];
    //全局变量
    int L=1024;							//总内存
    //自定义函数
    void First_fit();					//最先适应算法
    void Init_table();					//初始化已分配区表和空闲表
    void Init_job();					//初始化作业队列
    int Distribute(int,float);			//分配内存，考虑切割，修改已分配区表和空闲表信息
    void Reclaim(int);					//回收内存，考虑合并，修改已分配区表和空闲表信息
    void Display();						//显示空闲区表与已分配区表信息
    void Display_job();					//显示作业队列信息 
    //主函数
    int main()
    {
        
    	First_fit();					//最先适应算法
    	return 0;
    }
    void First_fit()					//最先适应算法				
    {
        
    	Init_table();					//初始化两表
    	Init_job();						//初始化作业队列
    	Display();						//输出两表
    	Display_job();					//输出作业队列
    	cout<<endl;
    	int i,num=10;					//记录未分配作业数目
    	while(num>0)					//一轮分配一轮回收，直到作业分配完
    	{
        
    		cout<<"开始一轮分配"<<endl<<endl;
    		for(i=0;i<10;i++)			//第一步：对每一个未分配作业进行分配
    		{
        
    			if(job[i].flag==0)		//找到一个未分配
    			{
        
    				cout<<"找到未分配作业"<<job[i].name<<"大小为"<<job[i].length<<endl;
    				if(Distribute(job[i].name,job[i].length)==1)//分配切割，修改2个表和1个队列信息
    				{
        
    					cout<<"成功分配"<<endl;
    					//分配（包含可能的切割，2表信息修改）
    					//改作业标志
    					job[i].flag=1;					//已分配
    					num--;							//未分配作业数减1	
    					Display();						//输出两表
    					Display_job();					//输出作业队列
    				}
    				else
    				{
        
    					cout<<"该作业暂无空间分配"<<endl;
    					Display();						//输出两表
    					Display_job();					//输出作业队列
    				}
    			}
    		}
    		if(num==0)
    		{
        	
    			cout<<"全部作业都分配了空间，程序结束"<<endl;
    			break;
    		}
    		cout<<"开始一轮回收"<<endl<<endl;
    		int choice;
    		for(i=0;i<10;i++)					//第二步：对每一个已分配作业随机回收
    		{
        
    			if(job[i].flag==1)				//已分配
    			{
        
    			
    				choice=rand()%2;
    				cout<<"产生的随机数为"<<choice<<endl;
    				if(choice==1)				//随机
    				{
        
    					cout<<"回收作业"<<job[i].name<<endl;
    					Reclaim(job[i].name);	//回收合并（修改2表信息）回收不可能失败
    					job[i].flag=3;			//已完成
    					cout<<"作业已经完成"<<endl;
    					Display();				//输出两表
    					Display_job();			//输出作业队列
    				}
    				else
    				{
        
    					cout<<"暂不回收作业"<<job[i].name<<endl;
    					Display();				//输出两表
    					Display_job();			//输出作业队列		
    				}
    			}
    		}
    	}
    }
    void Init_table()							//初始化两表			
    {
        	
    	int i;
    	for(i=0;i<n;i++)
    		used_table[i].flag=0;				//已分配区：0空表格目，非0(作业名)已分配
    	free_table[0].address=0;			    //空闲区大小依次为2,2,4,8,16，……，512(后面可以循环分配 前面两个需要手动)
    	free_table[0].length=L/512;
    	free_table[0].flag=1;
    	free_table[1].address=L/512;      
    	free_table[1].length=L/512;
    	free_table[1].flag=1;
    	for(i=2;i<m;i++)
    	{
        
    		free_table[i].address=free_table[i-1].address+free_table[i-1].length;	//起址
    		free_table[i].length=free_table[i-1].length*2;							//大小
    		free_table[i].flag=1;													//状态
    	}
    	cout<<"空闲区与已分配区初始化完成"<<endl;
    }
    void Init_job()																	//初始化作业
    {
        
    	for(int i=0;i<10;i++)
    	{
        
    		job[i].name=i+11;														//作业名：11~20
    		job[i].length=rand()%(L/4)+1;											//大小：在1~L/4
    		job[i].flag=0;															//状态：0未分配，1已分配，2已结束
    	}
    	cout<<"作业循环队列初始化完成"<<endl;
    }
    void Display()																	//输出两表
    {
        
    	cout<<endl<<"================================"<<endl;
    	cout<<"空闲区表(起址由低向高排序)"<<endl;
    	cout<<"================================"<<endl;
    	cout<<"序号"<<"\t起址"<<"\t大小"<<"\t标志"<<endl;;
    	cout<<"================================"<<endl;
    	for(int i=0;i<m;i++)
    	{
        
    		if(free_table[i].flag==1)												//2种状态
    			cout<<i+1<<"\t"<<free_table[i].address<<"\t"<<free_table[i].length<<"\t空闲"<<endl;
    		else
    			cout<<i+1<<"\t--\t--\t空栏目"<<endl;
    	}	
    	cout<<"================================"<<endl<<endl;
    	cout<<endl<<"================================"<<endl;
    	cout<<"已分配区表(不用排序)"<<endl;
    	cout<<"================================"<<endl;
    	cout<<"序号"<<"\t起址"<<"\t大小"<<"\t标志"<<endl;;
    	cout<<"================================"<<endl;
    	for(int j=0;j<n;j++)
    	{
        
    		if(used_table[j].flag==0)												//2种状态
    			cout<<j+1<<"\t--\t--\t空栏目"<<endl;
    		else
    			cout<<j+1<<"\t"<<used_table[j].address<<"\t"<<used_table[j].length<<"\t"<<"已分配"<<endl;
    	}
    	cout<<"================================"<<endl<<endl;
    }
    void Display_job()																//输出作业队列
    {
        
    	cout<<endl<<"========================="<<endl;
    	cout<<"作业队列"<<endl;
    	cout<<"========================="<<endl;
    	cout<<"作业名"<<"\t大小"<<"\t标志"<<endl;;
    	cout<<"========================="<<endl;
    	for(int i=0;i<10;i++)
    	{
        
    		cout<<job[i].name<<"\t"<<job[i].length;
    		if(job[i].flag==0)														//3种状态
    			cout<<"\t未分配"<<endl;
    		else if(job[i].flag==1)
    			cout<<"\t已分配"<<endl;
    		else 
    			cout<<"\t已结束"<<endl;
    	}
    	cout<<"========================="<<endl<<endl;
    }
    int Distribute(int name,float len)	//分配切割，修改2表信息
    {
        
    	int find=0;						//0：分配失败，1：分配成功
    	int i=0,j;
    	for(i=0;i<m;i++)				//从低地址开始找
    	{
        
    		if(free_table[i].length<len)//小于
    		{
        //继续找下一个
    		}
    		else if(free_table[i].length==len)//等于
    		{
        
    			cout<<"地址由低到高，找到首个不小于作业的空间，其大小为"<<free_table[i].length<<"，等于作业大小，不用分割"<<endl;
    			//已分配区
    			for(j=0;j<n;j++)
    			{
        
    				if(used_table[j].flag==0)//空表目
    				{
        		
    					//已分配区 改起址 大小 标志 
    					used_table[j].address=free_table[i].address;//改起址
    					cout<<"已分配的地址"<<used_table[j].address<<endl;
    					used_table[j].length=len;					//改大小
    					used_table[j].flag=name;					//改标志
    					break;
    				}	
    			}
    			//空闲区 
    			for(j=i;j<=m-2;j++)
    				free_table[j]=free_table[j+1];	//改位置
    			free_table[m-1].flag=0;				//改标志
    			find=1;								//分配完成
    			break;
    		}
    		else //大于
    		{
        
    			cout<<"地址由低到高，找到首个不小于作业的空间，其大小为"<<free_table[i].length<<"，大于作业，要分割"<<endl;
    			//已分配区
    			for(j=0;j<n;j++)
    			{
        
    				if(used_table[j].flag==0)		//空表目
    				{
        		
    					//已分配区 改起址 大小 标志 
    					used_table[j].address=free_table[i].address;//改起址
    					used_table[j].length=len;					//改大小
    					used_table[j].flag=name;					//改标志
    					break;
    				}	
    			}
    			//空闲区
    			free_table[i].address+=len;	//改地址
    			free_table[i].length-=len;	//改大小
    			find=1;						//分配完成
    			break;	
    		}
    	}
    	return find;		
    }
    void Reclaim(int name)					//回收合并，修改2表信息				 
    {
        			
    	int i,j,key=-1;						//判断空闲区是否有空表目
    	int key2;							//没有空表时记下存有作业信息的那个已分配区
    	for(i=0;i<n;i++)
    	{
        
    		if(used_table[i].flag==name)	//找到了作业信息
    		{
        
    			key2=i;
    			//修改空闲区信息
    			for(j=0;j<m;j++)
    			{
        
    				//找空表目 修改起址 大小 标志 排序 然后合并 一个接一个合并 
    				if(free_table[j].flag==0)	
    				{
        
    					free_table[j].address=used_table[i].address;//改起址
    					free_table[j].length=used_table[i].length;	//改大小
    					free_table[j].flag=1;						//改标志
    					key=j;										//记录该栏目位置
    					break;										//只要找到首个空表目
    				}
    			}
    			//修改已分配区信息
    			used_table[i].flag=0;//空表目
    			break;
    		}
    	}
    	if(key!=-1)
    	{
        
    		cout<<"回收块已经存入空闲区"<<endl;
    		for(i=0;i<m;i++)					//找上空闲区
    		{
        
    			if(free_table[i].flag==1)		//空闲
    			{
        
    				if(free_table[i].address+free_table[i].length==free_table[key].address)
    				{
        
    					cout<<"找到上邻空闲区，现在合并"<<endl;
    					//只要改长度 空闲区少1 迁移
    					free_table[i].length+=free_table[key].length;
    					for(j=key;j<=m-2;j++)//空闲区少1
    						free_table[j]=free_table[j+1];
    					free_table[m-1].flag=0;//空表目
    					key=i;					//回收的块号
    					break;					//合并完成
    				}		
    			}
    			else	
    			{
        
    				cout<<"不存在上邻空闲区"<<endl;
    				break;						
    			}
    		}
    	}
    	else//没有空栏目
    	{
        
    		cout<<"此时空闲区没有空栏目，只能直接合并"<<endl;
    		for(i=0;i<m;i++)				//找上空闲区
    		{
        
    			if(free_table[i].flag==1)	//空闲
    			{
        
    				if(free_table[i].address+free_table[i].length==used_table[key2].address)
    				{
        
    					cout<<"找到上邻空闲区，现在合并"<<endl;
    					//只改长度 还是满的空闲区
    					free_table[i].length+=used_table[key2].length;
    					key=i;
    					break;
    				}		
    			}
    			else
    			{
        
    				cout<<"不存在上邻空闲区"<<endl;
    				break;
    			}
    		}
    	}
    	if(key!=-1)							//已存入
    	{
        
    		cout<<"回收块已经存入空闲区"<<endl;
    		for(i=0;i<m;i++)				//找下空闲区
    		{
        
    			if(free_table[i].flag==1)	//空闲
    			{
        
    				if(free_table[key].address+free_table[key].length==free_table[i].address)
    				{
        
    					cout<<"找到下邻空闲区，现在合并"<<endl;
    					//只要改长度 空闲区少1 迁移
    					free_table[key].length+=free_table[i].length;
    					for(j=i;j<=m-2;j++)				//空闲区少1
    						free_table[j]=free_table[j+1];
    					free_table[m-1].flag=0;			//空表目
    					break;							//合并完成
    				}		
    			}
    			else
    			{
        
    				cout<<"不存在下邻空闲区"<<endl;
    				break;
    			}	
    		}
    	}
    	else
    	{
        
    		for(i=0;i<m;i++)							//找下空闲区
    		{
        
    			if(free_table[i].flag==1)				//空闲
    			{
        
    				if(used_table[key2].address+used_table[key2].length==free_table[i].address)
    				{
        
    					cout<<"找到下邻空闲区，现在合并"<<endl;
    					//只改长度 还是满的空闲区
    					free_table[i].length+=used_table[key2].length;
    					key=i;
    					break;							//合并完成
    				}		
    			}
    			else
    			{
        
    				cout<<"不存在下邻空闲区"<<endl;
    				break;	
    			}
    		}		
    	}
    	for(j=0;j<m;j++)
    	{
        
    		if(free_table[j].flag&&free_table[j+1].flag)//都空闲则比较
    		{
        
    			if(free_table[j].address>free_table[j+1].address)
    			{
        
    				int add=free_table[j].address;
    				free_table[j].address=free_table[j+1].address;
    				free_table[j+1].address=add;
    				int len=free_table[j].length;
    				free_table[j].length=free_table[j+1].length;
    				free_table[j+1].length=len;
    			}			
    		}
    		else
    			break;							//到空表目排序结束
    	}
    }