操作系统-内存管理-最佳适应算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了操作系统-内存管理-最佳适应算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6762字，纯文字阅读大概需要10分钟。

内容图文

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <time.h>
using namespace std;
struct node{
    //status表示当前节点的状态 0:空闲 1:占用
    //free_space表示当前节点的空余空间
    //*str表示当前存储字符串的首地址
    //index表示当前第几块空闲区，充当地址的作用 
    int free_space,status,index;
    char *str;
    node *next;
};
node *p,*s[15];
int piece;//记录当前系统中有几块空闲区 
void priority_sort(node *s[],int size);
void display(node *s[],int size);
void init_s(node *p){
	cout<<"重新初始化s数组"<<endl; 
	node *temp = p;
	piece = 0;
	while(temp != NULL){
		if(temp->status == 0){
			s[piece++] = temp;
		//	cout<<"第"<<piece<<"块剩余空间"<<temp->free_space<<endl;
		}
		temp = temp->next;
	}
	/*
	temp = p;
	cout<<"链表"<<endl;
	while(temp != NULL){
			cout<<temp->index<<" "<<temp->status<<endl;
		temp = temp->next;
	}
	
	cout<<"s数组"<<endl;
	for(int i=0;i<piece;i++){
		cout<<s[i]->index<<" "<<s[i]->free_space<<endl;
	} 
	*/
	cout<<"更新s数组后空闲区块数:"<<piece<<endl;
}
node *init(node *p){
    p = (node *)malloc(sizeof(node));
    node *first = p;
    srand((unsigned)time(NULL));
    for(int i=0;i<10;i++){
    	//cout<<(rand()%10)<<endl;
    	int temp = rand()%10+1;
    	first->index = i;
        first->str = (char *)malloc(sizeof(char));
        first->free_space = temp;
        first->status = 0;
        first->next = (node *)malloc(sizeof(node));
        s[i] = first;
    	piece++;
		if(i != 9)
			first = first->next;
	}
    first->next = NULL;
    cout<<"当前系统中有"<<piece<<"块空闲区"<<endl; 
    //display(s,piece);
    priority_sort(s,piece);
    cout<<"按照剩余空间升序排列后"<<endl; 
    display(s,piece);
    return p;
}
void display(node *ss[],int size){
	for(int i=0;i<size;i++) 
		cout<<"第"<<i<<"块空闲空间:"<<ss[i]->free_space<<"     链表起始地址:"<<s[i]->index<<endl;
}
void priority_sort(node *s[],int size){
	for(int i=0;i<size;i++)
		for(int j=i+1;j<size;j++)
			if(s[j]->free_space < s[i]->free_space)
				swap(s[i],s[j]);
}
void findMinNode(node *ss[],int size,char *str){
    //printf("%d\n",strlen(temp));
    int len = strlen(str);
    bool flag = false;
    node *temp1 = p;
	/*
	cout<<"插入前链表状态"<<endl;
	while(temp1 != NULL){
		cout<<"链表下标"<<temp1->index<<endl;
		temp1 = temp1->next;
	}
	*/
    for(int i=0;i<size;i++){
    	if(ss[i]->free_space == len){
            ss[i]->str = str;
            //cout<<"ss[i]->str "<<ss[i]->str<<endl;
            ss[i]->free_space = 0;
            ss[i]->status = 1;
            flag = true;
            break;
        }
        if(ss[i]->free_space > len){
        	node *tail;
			tail = (node *)malloc(sizeof(node));
			tail->str = (char *)malloc(sizeof(char));
			tail->status = 0;
			tail->free_space = ss[i]->free_space-len;
			tail->index = ss[i]->index+1;
			node *t = ss[i]->next;
			int tt = tail->index+1;
			while(t != NULL){
				t->index = tt++;
				t = t->next;
			}
			tail->next = ss[i]->next; 
			ss[i]->next = tail;
        	ss[i]->str = str;
        	//cout<<"ss[i]->str "<<ss[i]->str<<endl;
        	ss[i]->free_space = 0;
        	ss[i]->status = 1;
        	flag = true;
        	size++;
        	break;
		}
	}
	/*
	cout<<"插入后链表状态"<<endl;
	temp1 = p; 
	while(temp1 != NULL){
		cout<<"链表下标"<<temp1->index<<" 字符串"<<temp1->str<<endl;
		temp1 = temp1->next;
	}
	*/
    if(flag){
    	cout<<"成功插入字符串:"<<str;
		cout<<"剩余空闲区:"<<size-1<<"块"<<endl;
	}
	else
		cout<<"没有空闲区能装入字符串:"<<str<<endl; 
	init_s(p);
	/*
	cout<<"s数组"<<piece<<endl;
	for(int i=0;i<piece;i++){
		cout<<s[i]->index<<" "<<s[i]->free_space<<endl;
	}
	*/
    priority_sort(ss,piece);
}
void del(node *pp,int index){
	node *temp = p,*top = NULL,*tail = NULL,*mid; 
	//temp是找到要是释放的节点 
	while(temp != NULL){
		if(temp->index == index - 1)
			top = temp;
		if(temp->index == index)
			mid = temp; 
		if(temp->index == index + 1)
			tail = temp;
		temp = temp->next;
	}
	int len = strlen(mid->str);
	node *temp1 = p;
	/*
	cout<<"释放前链表状态"<<endl;
	while(temp1 != NULL){
		cout<<"链表下标"<<temp1->index<<"    剩余空间"<<temp1->free_space<<endl;
		temp1 = temp1->next;
	}
	
	if(top != NULL)
		cout<<"top找到了"<<endl;
	if(tail != NULL)
		cout<<"tail找到了"<<endl;
	*/
	if(top != NULL && tail != NULL){
		cout<<"top and tail are not NULL"<<endl;
		//如果上下两块都没有被使用三块合并
		if(top->status == 0 && tail->status == 0){
			cout<<"!top->status && !tail->status"<<endl;
			int next_index = top->index+1;
			top->next = tail->next;
			top->free_space = len + top->free_space + tail->free_space;
			free(mid);
			free(tail);
			node *temp1 = top->next;
			while(temp1 != NULL){
				temp1->index = next_index++;
				temp1 = temp1->next; 
			}
		}
		//如果下一块没有被使用和下一块合并 
		else if(top->status == 0){
			cout<<"!top->status"<<endl;
			int next_index = top->index+1;
			top->next = mid->next;
			top->free_space = len + top->free_space ;
			free(mid);
			node *temp1 = top->next;
			while(temp1 != NULL){
				temp1->index = next_index++;
				temp1 = temp1->next; 
			}
		}
		//如果上一块没有被使用和上一块合并 
		else if(tail->status == 0){
			cout<<"!tail->status"<<endl;
			int next_index = mid->index+1;
			mid->next = tail->next;
			mid->free_space = len + tail->free_space ;
			free(tail);
			node *temp1 = mid->next;
			while(temp1 != NULL){
				temp1->index = next_index++;
				temp1 = temp1->next; 
			}
		}
		//如果上下都被使用则插入到对位 
		else{
			cout<<"插入队尾"<<endl;
			top->next = mid->next;
			node *temp1 = mid->next; 
			while(temp1->next !=NULL){
				temp1 = temp1->next; 
			}
			temp1->next = mid;
			mid->index = temp1->index+1;
			mid->next = NULL;
			mid->free_space = len;
			mid->status = 0; 
		}
	}
	//如果被释放的是链表中最后一块 
	else if(top !=NULL){
			cout<<"top is not NULL"<<endl;
			if(!top->status){
				cout<<"!top->status"<<endl;
				int next_index = top->index+1;
				top->next = mid->next;
				top->free_space = len + top->free_space ;
				free(mid);
				node *temp1 = top->next;
				while(temp1 != NULL){
					temp1->index = next_index++;
					temp1 = temp1->next; 
				}
			}else{
				cout<<"插入队尾"<<endl;
				int next_index = mid->index;
				node *temp1 = mid->next; 
				while(temp1 != NULL){
					temp1->index = next_index++;
					temp1 = temp1->next; 
				}
				temp1->next = mid;
				mid->index = temp1->index+1;
				mid->next = NULL;
				mid->free_space = len;
			}
	}
	//如果被释放的是链表中第一块
	else if(tail != NULL){
		cout<<"tail is not NULL"<<endl;
			if(!tail->status){
				cout<<"!tail->status"<<endl;
				int next_index = mid->index+1;
				mid->next = tail->next;
				mid->free_space = len  + tail->free_space ;
				mid->status = 0;
				free(tail);
				node *temp1 = mid->next;
				while(temp1 != NULL){
					temp1->index = next_index++;
					temp1 = temp1->next; 
				}
			}else{
				cout<<"插入队尾"<<endl;
				node *temp1 = mid->next; 
				while(temp1->next != NULL){
					temp1 = temp1->next; 
				}
				temp1->next = mid;
				mid->index = temp1->index+1;
				mid->next = NULL;
				mid->free_space = len;
			}
	} 
	
	cout<<"释放后链表状态"<<endl;
	temp1 = p; 
	while(temp1 != NULL){
		cout<<"链表下标"<<temp1->index<<"   剩余空间"<<temp1->free_space<<endl;
		temp1 = temp1->next;
	}
	
	init_s(p);
	priority_sort(s,piece);
}
int main(){
    //printf("char类型内存中占字节数：%d\n",sizeof(char));
    //printf("字符串str内存中占字节数：%d\n",sizeof(str));
    printf("\t\t\t\t实验五 基本存储管理\n");
    printf("\t\t\t\t   最佳适应算法\n");
    p = init(p);
    char temp[10];
    while(1){
        gets(temp);
        if(temp[0] == '!')
            break;
        findMinNode(s,piece,temp);
        display(s,piece);
    }
    while(1){
        cout<<"输出你要释放那条数据"<<endl;
        gets(temp);
        node *t = p;
        bool flag = false;
        
        node *temp1 = p;
        while(temp1 != NULL){
        	if(strcmp(temp1->str,temp) == 0){
        		flag = true;
        		del(p,temp1->index); 
        		break;
			}
			temp1 = temp1->next;
		}
		display(s,piece);
        if(flag)
            cout<<"找到了,释放了该数据"<<endl;
        else
            cout<<"没找到"<<endl;
        getchar();
    }
    return 0;
}

内容总结

以上是互联网集市为您收集整理的操作系统-内存管理-最佳适应算法全部内容，希望文章能够帮你解决操作系统-内存管理-最佳适应算法所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/933333.html

来源：【匿名】

【上一篇】进程调度算法总结【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【操作系统-内存管理-最佳适应算法】教程文章相关的互联网学习教程文章

一.先来先服务调度算法先来先服务的调度算法（FCFS）是一种最简单的调度算法，该算法既可以用于作业调度，也可以用于进程调度。当在作业调度中采用该算法时，每次都是从后备作业队列选择一个或多个最先进入该队列的作业，将他们调入内存，为他们分配内存，为他们分配资源，创建进程，然后放入就绪队列中。在进程中采用FCFS算法时，则每次调度室从就绪队列中选择一个最先进入该队列的进程，位置分配处理机，使之投入运行。该进程一...

操作系统复习——页面置换算法【图】

1.　　FIFO 先进先出页面置换算法：　　　优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。　　　看下实例:　　　缺页次数15次，缺页率：15/202.　　LRU最近最久未使用置换算法　　　当需要淘汰一个页面时，总是选择在最近一段时间内最久不用的页面予以淘汰。　　　缺页次：12次，缺页率：12/20 3.　　CLOCK时钟置换算法　　　为每页设置一位访问位，再将内存中的所有页面都通过链接指针链接成一个循环队列。当某页...

使用Java模拟操作系统高优先级算法【代码】

最近做操作系统的课程设计，网上看到一些动态调度的算法都是基于C写的，下午闲来无事，用Java写了一个高优先级调度的算法玩玩，这个算法首先有这几条要注意优先级是否可以为负的，答案是肯定的，如果有一个线程阻塞了另外一个线程一直去运行就可能一直减去，让优先级变成负数了阻塞的时机：可以说阻塞的时机特别的重要，一旦到达时间需要线程进行阻塞的状态就要立刻将状态改变掉，让它产生调度恢复成就绪状态的问题：因为是有可能是...

操作系统磁道调度算法（C++实现）【代码】【图】

磁盘调度在多道程序设计的计算机系统中，各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快，因此我们有必要为每个磁盘设备建立一个等待队列，常用的磁盘调度算法有以下四种：先来先服务算法（FCFS），最短寻道时间优先算法（SSTF），扫描算法（SCAN），循环扫描算法（CSCAN）代码变量声明：1 vector<int> TrackOrder; //磁道初始序列在函数中简写为 t2 vector<int>...

操作系统之页面置换算法（最佳置换OPT，先进先出FIFO，最近最久未使用LRU）【代码】【图】

最近学习操作系统时，实验要求实现常见的三种页面置换算法，博主按照书上要求试着编写，实现了案例，并记录在博客随记中，以便后续自己复习并也给需要的同学分享参考一下!水平有限，若有错，请悄悄告诉博主！博主好立即改正。最佳置换算法（optimal replacement，OPT）是从内存中选择今后不再访问的页面或者在最长一段时间后才需要访问的页面进行淘汰。如下例子： 1 #include <iostream>2 #include <stdio.h>3 #include <stdlib.h...

短作业优先算法_操作系统_c语言实现【代码】【图】

PTA题目注:在PTA上面提交时务必把scanf_s改成scanf,(编译器用的是vs2019). 主函数 int main() {int n; //进程数量scanf_s("%d", &n);struct pcb p[100];input(p,n);sort(p,n);sjf(p, n);output(p,n);return 0; }核心算法 void sjf(struct pcb* p, int n) {int finishedcount = 0; //记录已经完成的进程数 int unfinishedposition = 0; // 记录未完成的进程的位置 double nowtime = 0; //现在时间for...

超硬核！学霸把操作系统经典算法给敲完了！要知行合一

上期的笔记，浏览快1万了，既然关注的人很多，那就发出来承诺过的算法全模拟，希望帮到你们。上期的操作系统学霸笔记，考试复习面试全靠它一、模拟进程调度功能 data.h #ifndef _Data_h_ #define _Data_h_#include <stdio.h> #include <stdlib.h> #include <string.h>#define ElemType PCB #define Status int #define OK 1 #define ERROR 0 #define TimeSlice 1 #define Infinity 10 //INT_MAX#define NAME_MAXSIZE 20 typedef...

操作系统之调度算法

操作系统管理了系统的有限资源，当有多个进程(或多个进程发出的请求)要使用这些资源时，因为资源的有限性，必须按照一定的原则选择进程(请求)来占用资源。这就是调度。目的是控制资源使用者的数量,选取资源使用者许可占用资源或占用资源。这时就可以根据不同的调度的方法来进行处理进程。 FCFS(First-Come，First-Served) 先来先服务调度算法：在进程调度中，FCFS就是从就绪队列的队首选择最先到达就绪队列的进度，为该进程分配CPU...

操作系统课程设计之银行家算法【代码】【图】

操作系统课程设计之银行家算法背景银行家算法（Banker’s Algorithm）是一个避免死锁（Deadlock）的著名算法，是由艾兹格迪杰斯特拉在1965年为T.H.E系统设计的一种避免死锁产生的算法。它以银行借贷系统的分配策略为基础，判断并保证系统的安全运行。在银行中，客户申请贷款的数量是有限的，每个客户在第一次申请贷款时要声明完成该项目所需的最大资金量，在满足所有贷款要求时，客户应及时归还。银行家在客户申请的贷款数量不超...

操作系统中的『银行家算法（避免死锁）』

银行家算法中的数据结构需求矩阵Need。这也是一个n*m的矩阵，用以表示每一个进程尚需的各类资源数。如果Need[i,j]=K,则表示进程 i 还需要 Rj 类资源K个，方能完成其任务。上述三个矩阵间存在下述关系：Need[i,j]=Max[i,j]-Allocation[i,j] 银行家算法的步骤（判断是否为安全状态）设Request i是进程Pi的请求向量，如果Requesti [j]=K，表示进程Pi需要K个Rj类型的资源。当Pi发出资源请求后，系统按下述步骤进行检查：计算Need矩...

操作系统，最先适应分配算法代码【代码】

以下代码如有疑问，请联系博主，最佳适应算法与最差适应算法只需添加简单的排序即可完成（本代码中未添加） #include <windows.h> #include <conio.h> #include <stdlib.h> #include <stdio.h> #include <io.h> #include <string.h>#define MAX_THREAD 3typedef struct freearea { //表示空闲区域的数据结构struct freearea *next; //指向下一个结点的指针int start_address; ...

操作系统 - 相关标签

操作系统安装操作系统概念操作系统课程设计操作系统内核操作系统实验操作系统原理

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 操作系统-内存管理-最佳适应算法

操作系统-内存管理-最佳适应算法

内容导读

内容图文

内容总结

内容备注

内容手机端

【操作系统-内存管理-最佳适应算法】教程文章相关的互联网学习教程文章

操作系统中常见的调度算法

操作系统复习——页面置换算法【图】

使用Java模拟操作系统高优先级算法【代码】

操作系统磁道调度算法（C++实现）【代码】【图】

操作系统之页面置换算法（最佳置换OPT，先进先出FIFO，最近最久未使用LRU）【代码】【图】

短作业优先算法_操作系统_c语言实现【代码】【图】

超硬核！学霸把操作系统经典算法给敲完了！要知行合一

操作系统之调度算法

操作系统课程设计之银行家算法【代码】【图】

操作系统中的『银行家算法（避免死锁）』

操作系统，最先适应分配算法代码【代码】

操作系统-银行家算法(Java实现)【代码】【图】

最不常用置换算法LFT 最久未使用置换算法LRU 操作系统 C语言链表实现【代码】

操作系统之调度算法【图】

操作系统(5) 死锁的概念死锁产生的必要条件死锁的处理策略预防死锁避免死锁死锁的检测和解除银行家算法【图】

操作系统 - 相关标签

算法 - 相关标签

内存 - 相关标签

算法 - 最新教程

算法 - 最热教程