精华内容
下载资源
问答
  • opt算法流程图
    千次阅读
    2020-11-25 09:31:02

    1.实验内容
    0-1背包问题:若有物品n个,每个物品的价值Value,用vi表示,每个物品的重量weight用wi表示,其中vi和wi均为非负数。设背包的总容量为W,且W为非负数。现需要考虑的问题是:如何选择装入背包的物品,使装入背包的物品总价值最大。

    【动态规划解步骤】
    第一步,刻画问题的最优解子结构。可以将背包问题的求解过程看作是进行一系列的决策过程,即决定哪些物品应该放入背包,哪些物品不放入背包。如果一个问题的最优解包含了物品n,即xn=1,那么其余x1,x2,…,x(n-1)一定构成子问题1,2,…,n-1在容量W-wn时的最优解。如果这个最优解不包含物品n,即xn=0,那么其余x1,x2,…,x(n-1)一定构成子问题1,2,…,n-1在容量W时的最优解。

    第二步,递归定义最优解的值,根据上述分析的最优解的结构递归地定义问题最优解。设G[i,w]表示背包容量为w时,i个物品导致的最优解的总价值,得到下式。显然要求G[n,w]:
    在这里插入图片描述

    2.算法流程图及说明
    在这里插入图片描述

    3.核心代码解释

    /*
    c[i][w]表示背包容量为w时,i个物品导致的最优解的总价值,大小为(n+1)*(w+1)
    v[i]表示第i个物品的价值,大小为n
    w[i]表示第i个物品的重量,大小为n
    */
    #include <iostream>
    using namespace std;
    void Dny(int n, int W, int c[][18], int* v, int* wei)//构建最优解子结构
    {
    	memset(*c, 0, (W + 1) * sizeof(int));
    	for (int i = 1; i <= n; i++)//构建最优子结构从装入一个物品开始
    	{
    		c[i][0] = 0;
    		for (int w = 1; w <= W; w++)
    		{
    			if (wei[i - 1] > w)	//此处比较是关键,当当前第一个物品重量大于当前背包容量时,最优子结构等于上一所装数量的最优解
    			{
    				c[i][w] = c[i - 1][w];
    			}
    			else//否则可以装入
    			{
    				int temp = c[i - 1][w - wei[i - 1]] + v[i - 1];	//注意wei和v数组中的第i个应该为wei[i-1]和v[i-1]
    				if (c[i - 1][w] > temp)//如果上一个最优子结构大于当前价值,则不装,否则装入。
    				{
    					c[i][w] = c[i - 1][w];
    				}
    				else
    					c[i][w] = temp;//写入当前最优解
    			}
    		}
    	}
    }
    
    void assign(int c[][18], int* x, int* wei, int n, int W)
    {
    	int w = W;
    	for (int i = n; i >= 2; i--)
    	{
    		if (c[i][w] == c[i - 1][w])
    		{
    			x[i - 1] = 0;
    		}
    		else
    		{
    			x[i - 1] = 1;
    			w = w - wei[i - 1];
    		}
    	}
    	if (c[1][w] == 0)
    		x[0] = 0;
    	else
    		x[0] = 1;
    }
    
    int main()
    {
    	int n = 5;
    	int W = 17;
    	int w[] = { 3, 4, 7, 8, 9 };
    	int v[] = { 4, 5, 10, 11, 13 };
    	int c[6][18] = { 0 };
    	Dny(n, W, c, v, w);
    	cout << c[5][17] << endl;
    	int x[5];
    	assign(c, x, w, n, W);
    	cout << "Here is the assignment!" << endl;
    	for (int i = 0; i < n; i++)
    		cout << x[i] << endl;
    	for (i = 0; i <= n; i++)
    	{
    		for (int j = 0; j <=W; j++)
    			cout << c[i][j] << "   ";
    		cout << endl;
    	}
    	return 0;
    }
    

    }
    4.测试数据及截图
    测试jietu
    主要是写出这个函数在这里插入图片描述程序中表示出来:

    if (wei[i - 1] > w)	
    	c[i][w] = c[i - 1][w];
    else
    	int temp = c[i - 1][w - wei[i - 1]] + v[i - 1];
    

    然后构建表格!当运行到装下一个物品的时候,判断上一个物品是放着还是取出!

    更多相关内容
  • 前提:设置三个内存块 1、FIFO页面置换算法 第一种: 第二种: 2、LRU页面置换算法 第一种: 第二种:

    前提:

    1.设置三个内存块;
    2. * 指的是缺页;
    3. / 指的是命中。

    1、先进先出页面置换算法(FIFO)

    总是淘汰在内存中停留时间最长的一页,,即先进入内存的一页,先被替换出。

    第一种:
    在这里插入图片描述
    第二种:
    在这里插入图片描述

    2、最近最久未使用页面置换算法(LRU)

    选择在最近一段时间里没有被使用过的页面,将其淘汰,也就是被其他页面替换。

    第一种:

    在这里插入图片描述
    第二种:

    在这里插入图片描述

    3、最佳置换算法(OPT)

    选择在将来不被使用,或者在最远的将来才被使用的老页面,也就是选择该页面后面较远才出现,甚至不出现的页面,将其淘汰,即被替换。

    第一种:
    在这里插入图片描述
    第二种:
    在这里插入图片描述

    一开始,我也搞不明白这两种表格有什么不同,还以为其中的一种是错的,后来才发现两种都是正确的,只不过略有不同。

    区别:
    第一种表格,例如数字2被替换出去,那么新进来的数字1 将被安排在刚刚被替换出去的数字2的原位置;
    第二种表格,例如数字2被替换出去,那么新进来的数字1依旧始终被安排在最上面第一个内存块,即内存块a,后面内存块中的数字依次向下移动,数字2的空位置在移动过程中被占据。

    展开全文
  • OPT算法:最佳淘汰算法,选择永不使用或在未来最长时间内不再被访问的页面予以替换。 CLOCK算法:根据页面内存是否被访问来决定是否置换该页面。 改进版CLOCK算法:在之前的CLOCK算法上面除了使用

    ▶▶▶完整代码在最后!!!

    FIFO算法:先进先出调度算法,该算法总是淘汰最先进入内存的页面,即选择在内存中驻留时间最久的页面予以淘汰。
    LRU算法:最近最少使用算法,根据数据的历史访问记录来进行淘汰数据,其核心思想是“如果数据最近被访问过,那么将来被访问的几率也更高”。选择最近最久未使用的页面予以淘汰。
    OPT算法:最佳淘汰算法,选择永不使用或在未来最长时间内不再被访问的页面予以替换。
    CLOCK算法:根据页面内存是否被访问来决定是否置换该页面。
    改进版CLOCK算法:在之前的CLOCK算法上面除了使用位,还增加了一个修改位,进行判断。
    LFU算法:最近最少使用算法,如果一个数据在最近一段时间很少被访问到,那么可以认为在将来它被访问的可能性也很小。因此,当空间满时,最小频率访问的数据最先被淘汰,也就是每次淘汰那些使用次数最少的数据。

    系统最后的界面图:

    在这里插入图片描述

    系统设计流程图:

    FIFO算法流程图:
    在这里插入图片描述

    LRU算法流程图:
    在这里插入图片描述

    OPT算法流程图:
    在这里插入图片描述

    CLOCK算法流程图:
    在这里插入图片描述

    改进版CLOCK算法流程图:
    在这里插入图片描述

    LFU算法流程图:
    在这里插入图片描述

    算法分析(举例):

    页面顺序为0 1 5 4 1 7 3 2 6 7

    FIFO算法分析过程:
    在这里插入图片描述

    LRU算法分析过程:
    在这里插入图片描述

    OPT算法分析过程:
    在这里插入图片描述

    CLOCK算法分析过程:
    在这里插入图片描述

    改进版CLOCK算法分析过程:(修改位是随机产生的)
    在这里插入图片描述

    LFU算法分析过程:
    在这里插入图片描述

    #include <stdlib.h>
    #include <string.h>
    #include <stdlib.h>
    #include <time.h>
    #include <unistd.h>
    #include <stdio.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <memory.h>
    
    #define MAX_SEQ_LEN 50   /*页面序列的最大长度*/
    int blockNum;   /*分配给进程的内存块数量*/
    int pageNum;   /*进程页面数,决定随机生成的页面序列中页面号的最大值*/
    int pageSequenceLen;   /*实际页面序列长度*/
    int pageSequence[MAX_SEQ_LEN];  /*页面序列数组*/
    int *memBlocks;    /*为进程分配的内存块,动态数组,存放页号*/
    int *isPageLoaded;  /*页面状态数组,动态数组,1表示已经在内存块中,0表示不在内存块中*/
    int *useSite;  /*CLOCK算法的使用位,标记页号的状态*/
    int *reviseSite; /*改进CLOCK算法的修改位*/
    int oldPageIndex=0;  /*被置换的页索引*/
    int pageFaultTimes=0;  /*缺页次数统计*/
    float effectiveTime=0;  /*有效访问时间  有效访问时间=(1-pageFaultTimes)*内存访问时间+pageFaultTimes*页错误处理时间  /本例中 内存访问时间=100ns ; 页错误处理时间=20ms */
    char choice1; /*用来存储是否开始(y/n)*/
    int choice2=-1;/*用来存储选择的排序到序号*/
    
    void FIFO(){
    	printf("---------------------FIFO Replacement---------------------\n");
    	int i,j,k, n;
    	oldPageIndex = 0;
    	pageFaultTimes = 0;
    	effectiveTime=0;
    	memBlocks = (int *)malloc(blockNum * sizeof(int));  //初始化内存块中的页面号,全部初始化设置为-1
    	memset(memBlocks, -1, blockNum*sizeof(int));        //-1表示该内存块未装入任何页面
    
    	isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
    	memset(isPageLoaded, 0, pageNum*sizeof(int));
    
    	printf("页\t\t物理块\n");
    	for (i=0; i<pageSequenceLen; i++) {
    		printf("%2d\t-->\t", pageSequence[i]);
    		if (0 == isPageLoaded[pageSequence[i]]) {
    			pageFaultTimes++;
    			for (j=0; j<blockNum; j++) {	//找空闲块
    				if (memBlocks[j]==-1) break;
    				}
    			if (j<blockNum) {		//有空闲块
    				memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
    				isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
    				}
    			else {		//没有空闲块,页面置换
    				isPageLoaded[memBlocks[oldPageIndex]] = 0; //将被置换出去的页面状态修改为未装入
    				memBlocks[oldPageIndex] = pageSequence[i]; //将当前页号写入内存块
    				oldPageIndex = (oldPageIndex + 1) % blockNum;  //将最先进入的索引修改为下一个索引
    				isPageLoaded[pageSequence[i]] = 1;   //将当前页面状态修改为1
    				}
    
    			for (j=0; j<blockNum; j++)    //显示内存块数组中的页号
    				if (memBlocks[j] != -1)
    					printf("%d ", memBlocks[j]);
    			printf("\n");
    			}
    		else printf("\n");
    	}
    	srand((unsigned)time(NULL));
    	effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
    	printf("缺页次数为:%d,缺页率为:%.3f,有效访问时间:%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
    		
    }
    
    void LRU(){
    	printf("---------------------LRU Replacement---------------------\n");
    	int i,j,k, n,m,h;
    	oldPageIndex = 0;
    	pageFaultTimes = 0;
    	memBlocks = (int *)malloc(blockNum * sizeof(int));  //初始化内存块中的页面号,全部初始化设置为-1
    	memset(memBlocks, -1, blockNum*sizeof(int));        //-1表示该内存块未装入任何页面
    
    	isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
    	memset(isPageLoaded, 0, pageNum*sizeof(int));
    	printf("页\t\t物理块\n");
    	for (i=0; i<pageSequenceLen; i++) {
    		h=0;
    		printf("%2d\t-->\t", pageSequence[i]);
    		if (isPageLoaded[pageSequence[i]] == 0){
    			pageFaultTimes++;
    			for (j=0; j<blockNum; j++) {	//找空闲块
    				if (memBlocks[j]==-1) break;
    				}
    			if (j<blockNum) {		//有空闲块
    				memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
    				isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
    			}
    			else {
    				int a[blockNum],p;
    				for(p=0;p<blockNum;p++)
    					a[p]=0;
    				for(k=i-1;k>=0;k--){
    					for(m=0;m<j;m++)
    						if(pageSequence[k]==memBlocks[m] && a[m]==0){
    							h=m;
    							a[m]=1;
    						}
    				}
    				isPageLoaded[memBlocks[h]] = 0;
    				memBlocks[h] = pageSequence[i];
    				isPageLoaded[pageSequence[i]] = 1;
    			}
    			for (j=0; j<blockNum; j++)    //显示内存块数组中的页号
    				if (memBlocks[j] != -1)
    					printf("%d ", memBlocks[j]);
    			printf("\n");
    		}
    		else printf("\n");
    	}
    	srand((unsigned)time(NULL));
            effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
            printf("缺页次数为:%d,缺页率为:%.3f,有效访问时间:%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
    }
    
    void OPT(){
            printf("---------------------OPT Replacement---------------------\n");
    	int i,j,k, n,m,h;
            oldPageIndex = 0;
            pageFaultTimes = 0;
            effectiveTime=0;
            memBlocks = (int *)malloc(blockNum * sizeof(int));  //初始化内存块中的页面号,全部初始化设置为-1
            memset(memBlocks, -1, blockNum*sizeof(int));        //-1表示该内存块未装入任何页面
    
            isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
            memset(isPageLoaded, 0, pageNum*sizeof(int));
    	printf("页\t\t物理块\n");
    	for (i=0; i<pageSequenceLen; i++) {
                    h=0;
                    int count=0;
                    printf("%2d\t-->\t", pageSequence[i]);
                    if (isPageLoaded[pageSequence[i]] == 0){
                            pageFaultTimes++;
                            for (j=0; j<blockNum; j++) {    //找空闲块
                                    if (memBlocks[j]==-1) break;
                                    }
                            if (j<blockNum) {               //有空闲块
                                    memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
                                    isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
                            }
                            else {
                                    int a[blockNum],p;
                                    for(p=0;p<blockNum;p++)
                                            a[p]=0;
                                    for(k=i+1;k<pageSequenceLen;k++){
                                            for(m=0;m<j;m++)
                                            	if(pageSequence[k]==memBlocks[m] && a[m]==0){
                                                    	h=m;
                                                    	a[m]=1;
    							count++;
                                            	}
                                    }
    				if(count<blockNum)
    					for(p=0;p<blockNum;p++){
    						if(a[p]==0){
    							h=p;
    							break;
    					}
    				}
                                    isPageLoaded[memBlocks[h]] = 0;
                                    memBlocks[h] = pageSequence[i];
                                    isPageLoaded[pageSequence[i]] = 1;
                            }
                            for (j=0; j<blockNum; j++)    //显示内存块数组中的页号
                                    if (memBlocks[j] != -1)
                                            printf("%d ", memBlocks[j]);
                            printf("\n");
                    }
                    else printf("\n");
            }
            srand((unsigned)time(NULL));
            effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
            printf("缺页次数为:%d,缺页率为:%.3f,有效访问时间:%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
    }
    
    void CLOCK(){
    	printf("---------------------CLOCK Replacement---------------------\n");
            int i,j,k, n,m,h;
            oldPageIndex = 0;
            pageFaultTimes = 0;
            memBlocks = (int *)malloc(blockNum * sizeof(int));  //初始化内存块中的页面号,全部初始化设置为-1
            memset(memBlocks, -1, blockNum*sizeof(int));        //-1表示该内存块未装入任何页面
    
            isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
            memset(isPageLoaded, 0, pageNum*sizeof(int));
    	
    	useSite = (int *)malloc(blockNum * sizeof(int));//初始化页面使用位数组,初始化未装入
    	memset(useSite, 0, blockNum*sizeof(int));
    		
    	int *pageSite;//标记页号在内存块中的位置
    	pageSite = (int *)malloc(pageNum * sizeof(int));//初始化页面使用位数组,初始化未装入
    	memset(pageSite, 0, pageNum*sizeof(int));
    
            printf("页\t\t物理块\n");
    	
    	for (i=0; i<pageSequenceLen; i++) {
                    printf("%2d\t-->\t", pageSequence[i]);
                    if (isPageLoaded[pageSequence[i]] == 0){
                            pageFaultTimes++;
                            for (j=0; j<blockNum; j++) {    //找空闲块
                                    if (memBlocks[j]==-1) break;
                                    }
                            if (j<blockNum) {               //有空闲块
                                    memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
                                    isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
    				useSite[j] = 1;
    				pageSite[pageSequence[i]] = j;
                            }
                            else {
    				int flag=0;
    				while(flag==0){
    					if(useSite[oldPageIndex] == 0){
                                    		isPageLoaded[memBlocks[oldPageIndex]] = 0; //将被置换出去的页面状态修改为未装入
                                    		memBlocks[oldPageIndex] = pageSequence[i]; //将当前页号写入内存块
    						pageSite[pageSequence[i]] = oldPageIndex;
    						useSite[oldPageIndex] = 1;
                                    		oldPageIndex = (oldPageIndex + 1) % blockNum;  //将最先进入的索引修改为下一个索引
                                    		isPageLoaded[pageSequence[i]] = 1;   //将当前页面状态修改为1
    						flag=1;
    					}
    					else{
    						useSite[oldPageIndex] = 0;
                                            	oldPageIndex = (oldPageIndex + 1) % blockNum;
    					}
    				}
                            }
                            for (j=0; j<blockNum; j++)    //显示内存块数组中的页号
                                    if (memBlocks[j] != -1)
                                            printf("%d ", memBlocks[j]);
                            printf("\n");
                    }
                    else{
    			useSite[pageSite[pageSequence[i]]] = 1;
    			printf("\n");
    		}
            }
            srand((unsigned)time(NULL));
            effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
            printf("缺页次数为:%d,缺页率为:%.3f,有效访问时间:%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
    }
    
    void improvedCLOCK(){
    	printf("---------------------改进版CLOCK Replacement---------------------\n");
    	int i,j,k, n,m,h;
            oldPageIndex = 0;
            pageFaultTimes = 0;
            memBlocks = (int *)malloc(blockNum * sizeof(int));  //初始化内存块中的页面号,全部初始化设置为-1
            memset(memBlocks, -1, blockNum*sizeof(int));        //-1表示该内存块未装入任何页面
    
            isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
            memset(isPageLoaded, 0, pageNum*sizeof(int));
    
            useSite = (int *)malloc(blockNum * sizeof(int));//初始化页面使用位数组,初始化未装入
            memset(useSite, 0, blockNum*sizeof(int));
    	
    	reviseSite = (int *)malloc(pageSequenceLen * sizeof(int));//初始化页面使用位数组,初始化未装入
            memset(reviseSite, 0, pageSequenceLen*sizeof(int));
    
    	int *reviseSites;//内存块中的修改位
            reviseSites = (int *)malloc(blockNum * sizeof(int));//
            memset(reviseSites, 0, blockNum*sizeof(int));
    
    	int *pageSite;//标记页号在内存块中的位置
            pageSite = (int *)malloc(pageNum * sizeof(int));
            memset(pageSite, 0, pageNum*sizeof(int));
    
    
    	for (i=0; i<pageSequenceLen; i++) { 
    		printf("%d ", pageSequence[i]);
    	}
    	printf("\n");
    	n=2;
    	for (i=0; i<pageSequenceLen; i++) {
             	reviseSite[i] = rand()%n;
    		printf("%d ", reviseSite[i]);       
            }
    	printf("\n");
    	     
    	printf("页\t\t物理块\n");
    	for (i=0; i<pageSequenceLen; i++) {
                    printf("%2d\t-->\t", pageSequence[i]);
                    if (isPageLoaded[pageSequence[i]] == 0){
                            pageFaultTimes++;
                            for (j=0; j<blockNum; j++) {    //找空闲块
                                    if (memBlocks[j]==-1) break;
                                    }
                            if (j<blockNum) {               //有空闲块
                                    memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
                                    isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
                                    useSite[j] = 1;
    				reviseSites[j] = reviseSite[i];
                                    pageSite[pageSequence[i]] = j;
                            }
                            else {
    				int flag=0;
    				while(flag==0){
    					int count=0;
    					while((useSite[oldPageIndex]!=0 || reviseSites[oldPageIndex]!=0) && count<blockNum){ 
    						count++;
    						oldPageIndex = (oldPageIndex + 1) % blockNum;
    					}
    					if(count<blockNum){
    						isPageLoaded[memBlocks[oldPageIndex]] = 0;
    						memBlocks[oldPageIndex] = pageSequence[i];
    						reviseSites[oldPageIndex] = reviseSite[i];
                                            	useSite[oldPageIndex] = 1;
                                                    pageSite[pageSequence[i]] = oldPageIndex;
                                            	oldPageIndex = (oldPageIndex + 1) % blockNum;
                                            	isPageLoaded[pageSequence[i]] = 1;
    						flag=1;
    					}
    					else{
    						int count1=0;
    						while((useSite[oldPageIndex]!=0 || reviseSites[oldPageIndex]!=1) && count1<blockNum){
                                            		count1++;
    							useSite[oldPageIndex] = 0;
                                            		oldPageIndex = (oldPageIndex + 1) % blockNum;
                                    		}
    						if(count1<blockNum){
    							isPageLoaded[memBlocks[oldPageIndex]] = 0;
                                            		memBlocks[oldPageIndex] = pageSequence[i];
                                            		reviseSites[oldPageIndex] = reviseSite[i];
                                           	 		useSite[oldPageIndex] = 1;
                                                    	pageSite[pageSequence[i]] = oldPageIndex;
                                            		oldPageIndex = (oldPageIndex + 1) % blockNum;
                                            		isPageLoaded[pageSequence[i]] = 1;
    							flag=1;
    						}
    					}
    				}
                            }
                            for (j=0; j<blockNum; j++)    //显示内存块数组中的页号
                                    if (memBlocks[j] != -1)
                                            printf("%d ", memBlocks[j]);
                            printf("\n");
                    }
    		else{
                            useSite[pageSite[pageSequence[i]]] = 1;
    			reviseSites[pageSite[pageSequence[i]]] = reviseSite[i];
    			printf("\n");
    		}
            }
            srand((unsigned)time(NULL));
            effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
            printf("缺页次数为:%d,缺页率为:%.3f,有效访问时间:%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
    }
    
    void LFU(){
    	printf("---------------------LFU Replacement---------------------\n");
    	int i,j,k, n;
            oldPageIndex = 0;
            pageFaultTimes = 0;
            effectiveTime=0;
            memBlocks = (int *)malloc(blockNum * sizeof(int));  //初始化内存块中的页面号,全部初始化设置为-1
            memset(memBlocks, -1, blockNum*sizeof(int));        //-1表示该内存块未装入任何页面
    
            isPageLoaded = (int *)malloc(pageNum * sizeof(int));//初始化页面状态数组,初始化未装入
            memset(isPageLoaded, 0, pageNum*sizeof(int));
    	
    	int *pagenumber;//各个页面出现的次数统计
    	pagenumber = (int *)malloc(pageNum * sizeof(int));
    	memset(pagenumber, 0, pageNum*sizeof(int));
    
    	int *blocktime;//标记各个页面出现的先后顺序
            blocktime = (int *)malloc(blockNum * sizeof(int));
            memset(blocktime, 0, blockNum*sizeof(int));
    
            printf("页\t\t物理块\n");
            for (i=0; i<pageSequenceLen; i++) {
                    printf("%2d\t-->\t", pageSequence[i]);
                    if (isPageLoaded[pageSequence[i]] == 0) {
                            pageFaultTimes++;
                            for (j=0; j<blockNum; j++) {    //找空闲块
                                    if (memBlocks[j]==-1) break;
                                    }
                            if (j<blockNum) {               //有空闲块
                                    memBlocks[j] = pageSequence[i]; //将当前页面序列的页号写入空闲内存块
                                    isPageLoaded[pageSequence[i]] = 1; //将页号对应的页面状态修改为已装入
    				pagenumber[pageSequence[i]]++;
    				blocktime[j] = j;
                                    }
                            else {          //没有空闲块,页面置换
    				oldPageIndex = 0;
    				for(j=1;j<blockNum;j++){
    					if(pagenumber[memBlocks[oldPageIndex]]>pagenumber[memBlocks[j]])
    						oldPageIndex=j;
    					else if(pagenumber[memBlocks[oldPageIndex]] == pagenumber[memBlocks[j]] && blocktime[oldPageIndex]<blocktime[j])
    						oldPageIndex = j;
    				}
                                    isPageLoaded[memBlocks[oldPageIndex]] = 0; //将被置换出去的页面状态修改为未装入
                                    memBlocks[oldPageIndex] = pageSequence[i]; //将当前页号写入内存块
                                    isPageLoaded[pageSequence[i]] = 1;   //将当前页面状态修改为1
    				pagenumber[pageSequence[i]]++;
    				for(j=0;j<blockNum;j++){
    					if(blocktime[j]>blocktime[oldPageIndex])
    						blocktime[j]--;
    				}
    				blocktime[oldPageIndex] = blockNum-1;
    			}
    
                            for (j=0; j<blockNum; j++)    //显示内存块数组中的页号
                                    if (memBlocks[j] != -1)
                                            printf("%d ", memBlocks[j]);
                            printf("\n");
                            }
                    else{
    			pagenumber[pageSequence[i]]++;
    			printf("\n");
    		}
            }
            srand((unsigned)time(NULL));
            effectiveTime=((1-pageFaultTimes*1.0/pageSequenceLen)*100+ pageFaultTimes*1.0/pageSequenceLen*20*1000000)/1000;
            printf("缺页次数为:%d,缺页率为:%.3f,有效访问时间:%.3fus\n", pageFaultTimes,pageFaultTimes*1.0/pageSequenceLen, effectiveTime);
    
    }
    
    int main(int argc,char **argv)
    {
    	printf("本例中 内存访问时间=100ns   页错误处理时间=20ms\n");
    	int i,n;
    	printf("Begin? (Y or N): ");
    	choice1 = getchar();
    	while (choice1=='Y' || choice1=='y') {
    		printf("输入分配给该进程的内存块数:");
    		scanf("%d", &blockNum);
    		printf("输入该进程的页面总数:");
    		scanf("%d", &pageNum);
    		printf("输入该进程访问的页面序列长度:");
    		scanf("%d", &pageSequenceLen);
    		getchar();
    		//srand((int)time(0));	
    //		pageSequence[0]=0;pageSequence[1]=1;pageSequence[2]=5;pageSequence[3]=4;pageSequence[4]=1;
    //		pageSequence[5]=7;pageSequence[6]=3;pageSequence[7]=2;pageSequence[8]=6;pageSequence[9]=7;
    		for (i=0; i<pageSequenceLen; i++) {   //随机生成页面序列
    			n=rand()%pageNum;
    			pageSequence[i] = n;
    			printf("%d ", pageSequence[i]);
    		}		
    		printf("\n请选择需要使用到算法:\n");
    		printf("1.FIFO\n2.LRU\n3.OPT\n4.CLOCK\n5.改进版CLOCK\n6.LFU\n0.exit\n");
    		printf("选择算法序号:");
    		scanf("%d",&choice2);
    		while(choice2){
    			switch(choice2){
    				case 1: FIFO();  	  break;
    				case 2: LRU();   	  break;
    				case 3: OPT();   	  break;
    				case 4: CLOCK(); 	  break;
    				case 5: improvedCLOCK();  break;
    				case 6: LFU();		  break;            
    				defalut: break;
    			}
                    	printf("请选择需要使用到算法:\n");
                    	printf("1.FIFO\n2.LRU\n3.OPT\n4.CLOCK\n5.改进版CLOCK\n6.LFU\n0.exit\n");
    	                printf("选择算法序号:");
    			scanf("%d",&choice2);
    		}
    		printf("Begin? (Y or N): ");
    		getchar();
    		choice1 = getchar();
    	}
    }
    
    
    展开全文
  • 该工程具体是在codeblock上面实现了操作系统课程上讲解的页面置换算法,包括先进先出(FIFO)、最佳置换算法OPT)、最久最近未使用算法(LRU)。 具体实现功能有: 1、建立相应的数据结构 2、在屏幕上显示页面...
  • 包括了操作系统页面置换算法,其中有OPT,FIFO,LRU,CLOCK,改进型的CLOCK算法
  • 2-opt全邻域搜索求解TSP思路以及matlab实现 算法流程图 matlab程序编写实现 主程序如下: %% 2-opt 全邻域搜索求解TSP实现 %% 2-opt全邻域搜索算法求解tsp问题 data = initData(); % 存放城市之间距离的矩阵 ...

    一. 旅行商问题描述

    一位商人要到若干城市去推销商品,已知城市个数和各城市间的路程(或者旅费),要求找到一条从城市1出发,经过所有城市且每个城市只能访问一次,最后回到城市1的路线,使总的路程(或者旅费)最小
    结点数为 N N N的TSP问题,其路径组合数量为 ( N − 1 ) ! (N-1)! (N1)!

    二. 邻域搜索算法

    1. 邻域的概念

    在这里插入图片描述
    字面意思理解,如上面的表格所示,如果红色表格代表解,那么它旁边的绿色部分表格就是它的邻域。
    对应到旅行商问题中,假如有七个城市,那么它的一个解可以如下表示:
    1 → 2 → 3 → 4 → 5 → 6 → 7 1\to2\to3\to4\to5\to6\to7 1234567
    即:
    在这里插入图片描述
    则2opt(两点互换产生的邻域)有:
    在这里插入图片描述
    等等

    2. 2-opt全邻域搜索求解TSP思路以及matlab实现

    算法流程图

    在这里插入图片描述
    matlab程序编写实现
    主程序如下:

    %% 2-opt 全邻域搜索求解TSP实现
    
    %% 2-opt全邻域搜索算法求解tsp问题
    
    data = initData();                                          % 存放城市之间距离的矩阵
    
    cityQty = size(data,1);                                     % 城市总数
    otherCities = 2:cityQty;                                    
    
    % 随机产生初始解
    randCities = otherCities(randperm(cityQty - 1));
    xnew = [1 randCities];                                      % 产生xnew
    fitxnew = routeDistance(data,xnew);                         % 计算xnew解的路线长度
    xbest = xnew;                                               % 让xbest = xnew     
    fitxbest = fitxnew;                                         % 让fitxbest = fitxnew
    
    % 循环计算
    isStop = 0;
    while isStop < 4                                            % 设置迭代次数
        % 使用2-opt方式产生xnew的全部邻域解
        neighbors = neighborBy2opt(xnew);                       % 产生xnew的邻域解
        
        % 计算neighbors中每个解的值,并获得最小解
        neighborRows = size(neighbors,1);
        fitnesses = zeros(neighborRows,1);
        for i = 1:neighborRows
            fitnesses(i) = routeDistance(data,neighbors(i,:));  % 计算每个邻域解的路线长度
        end
        [~, idx] = sortrows(fitnesses);                         % 对邻域解进行升序排列
        xnow = neighbors(idx(1),:);                             % 把最短路线长度的解赋给xnow
        fitnow = fitnesses(idx(1));                             % xnow的路线长度
        
        % 进行解的更新和终止循环判断
        if fitnow < fitxbest                                    % 如果xnow优于xbest时将xnow赋给xbest
            xbest = xnow;
            fitxbest = fitnow;
            isStop = 0;
        else                                                    % 如果xnow不优于xbest,进行下一次的迭代
            isStop = isStop + 1;
        end
        xnew = xnow;                                            % 将xnow赋给xnew
        
        % 解随机移动下
        segCities = circshift(otherCities,randperm(cityQty,1)-1);
        newIdx = [1 segCities];
        xnew = xnew(newIdx);
        
    end
    
    % 输出结果
    disp('------------------最短路径------------------');
    disp(optX);
    disp('------------------最短路径长度------------------');
    disp(optFit);
    
    

    用到的函数:
    initData:初始化数据,各个城市之间的距离

    function distData = initData()
        distData = [0 15 19 30 6 11 18 14 24
                    15 0 34 44 14 23 29 4 38
                    19 34 0 16 22 15 19 32 9
                    30 44 16 0 35 30 18 44 7
                    6 14 22 35 0 9 24 11 28
                    11 23 15 30 9 0 24 20 23
                    18 29 19 18 24 24 0 30 15
                    14 4 32 44 11 20 30 0 37
                    24 38 9 7 28 23 15 37 0];
    end
    
    

    routeDistance:计算解的路线长度

    function routeDist = routeDistance(cityDist, route)
    % 根据城市间的距离计算总路径
        qty = max(size(route));
        sumDist = 0;
        for i = 1 ; qty-1
            sumDist = sumDist + cityDist(route(i),route(i+1));
        end
        sumDist = sumDist + cityDist(route(qty),route(1));
        routeDist = sumDist;
    end
    

    neighborBy2opt:产生一个解的全部邻域解集(采用2opt方式产生)

    function routes = neighborBy2opt( route )
        % 根据一条路径route,采用2opt方式产生其全部邻域解集
        cityQty = max(size(route));
        if cityQty <= 3
            disp('cityQty is too small in neighborBy2opt.....');
        end
        pos = 2 : cityQty;
        changePos = nchoosek(pos, 2);
        rows = size(changePos, 1);
        routes = zeros(rows, cityQty);
        % 依次对两个点进行位置互换,形成新的解
        for i  = 1 : rows
            city1 = route(changePos(i,1));
            city2 = route(changePos(i,2));
            midRoute = route;
            midRoute(changePos(i,1)) = city2;
            midRoute(changePos(i,2)) = city1;
            routes(i,:) = midRoute;
        end
    end
    
    
    

    程序运行结果
    在这里插入图片描述

    展开全文
  • 第一个输入的为页面数,不是内存中页面,失踪的页面,内存中的页面在宏定义中设置 第二个输入的是页面执行的顺序,以0结束
  • 实验题目:OPT算法实验实验内容:已知页面访问序列,采用OPT页面置换算法,求缺页次数、页面置换次数和缺页率。实验目的:通过模拟实现请求页式存储管理的几种基本页面置换算法,了解虚拟存储技术的特点,掌握虚拟...
  • 【JAVA操作系统——页面置换算法】LRU&OPT
  • 最佳置换OPT页面置换算法的源代码,以及可执行程序。
  • 一分钟学会页面置换算法OPT、FIFO、LRU、NUR】

    千次阅读 多人点赞 2020-03-26 19:26:04
    最佳置换(OPT)算法:选择的被淘汰页面,将是以后永不使用的,或许是在最长(未来)时间内不再被访问的页面;采用最佳置换算法可保证获得最低的缺页率。但是由于无法预知哪一个页面是未来最长时间内不再被访问的,因而...
  • 页面置换算法(FIFO,LRU,OPT

    千次阅读 2018-01-19 20:41:48
    1.先进先出置换算法(FIFO):...2.最佳置换算法OPT)(理想置换算法):从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的,或者是在
  • 文章目录1、最佳淘汰算法(Optimal)举例代码流程图2、先进先出的算法(FIFO)举例代码流程图3、最近最久未使用算法(LRU)举例代码流程图4、简单时钟(钟表)算法(CLOCK)举例代码流程图 1、最佳淘汰算法OPT)  ...
  • 页面淘汰算法模拟实现与比较实验报告.zip
  • 页面置换算法.doc

    2020-03-23 22:48:13
    深入掌握内存调度算法的概念原理和实现方法,编写程序实现: (1) 先进先出页面置换算法(FIFO) ...操作系统页面置换算法课程设计,完整的课设结构,有详细的流程图、Java源码,还有调试截图!!!
  • 实用标准文案精彩文档操作系统实验报告页面置换算法模拟——OFT、FIFO和LRU算法班级:2013级软件工程1班学号:X X X姓名:萧氏一郎数据结构说明:Memery[10]物理块中的页码Page[100]页面号引用串Temp[100][10]辅助...
  • 包含五种基本算法,有算法的文字介绍,算法流程图,C语言代码。 本实验的程序设计基本上按照实验内容进行,用C语言编写程序。首先用srand( )和rand( )函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,...
  • (1)最佳淘汰算法OPT) (2)先进先出的算法(FIFO) (3)最近最久未使用算法(LRU)) 三、实验原理 1、虚拟存储系统 UNIX中,为了提高内存利用率,提供了内外存进程对换机制;内存空间的分配和回收均以页为...
  • 页面置换:在地址映射过程中,若在页面中发现所要访问的页面不再内存中,则产生缺页中断(page fault)。当发生缺页中断时操作系统必须在内存选择一个...opt算法需要知道操作系统将来的事件,显然不可能实现,只作为一...
  • 图像分割与提取——分水岭算法

    千次阅读 2022-04-01 15:55:32
    6、利用函数connectedComponents对原始图像O进行修正 7、使用分水岭函数完成对图像的分割 三、代码实例 # 分水岭算法流程:输入图像、灰度、二值、距离变换、寻找种子、生成Marker、分水岭变换、输出图像 def ...
  • A3C的算法原理和算法流程

    千次阅读 多人点赞 2020-03-22 04:52:55
    在强化学习(十四) Actor-Critic中,我们讨论了Actor-Critic的算法流程,但是由于普通的Actor-Critic算法难以收敛,需要一些其他的优化。而Asynchronous Advantage Actor-critic(以下简称A3C)就是其中比较好的优化...
  • OPT页面置换算法1

    千次阅读 2019-06-09 17:31:47
    OPT页面置换算法1 OPT简单/简陋/算法实现 对于页面置换计数有待改进 当要调入一页而必须淘汰旧页时,应该淘汰以后不再访问的页,或距现在最长时间后要访问的页面。它所产生的缺页数最少,然而,却需要预测程序的页面...
  • 页面置换算法(FIFO&LRU)

    万次阅读 多人点赞 2020-12-27 11:23:43
    页面置换算法 实验目的 1.通过模拟实现几种基本页面置换的算法,了解虚拟存储技术的特点。 2.通过置换算法的模拟和比较,进一步了解它们的优缺点。 3.锻炼知识的运用能力和实践能力 实验要求 编写程序实现:先进先出...
  • 【操作系统】页面置换算法(最佳置换算法)(C语言实现) #####(编码水平较菜,写博客也只是为了个人知识的总结和督促自己学习,如果有错误,希望可以指出) 1.页面置换算法: 在地址映射过程中,若在页面中发现所...
  • 页面置换算法( 详解 )

    2022-07-22 08:07:16
    进程运行时,若其访问的页面不在内存而需将其调入,但内存已无空闲空间时,就需要从内存中调出一页程序或数据,送入磁盘的对换区,其中选择调出页面的算法就称为页面置换算法。好的页面置换算法应有较低的页面更换...
  • opencv图像处理基础总结,基于分水岭算法的图像分割,介绍了分水岭算法的原理、距离变换、opencv有关函数的用法,基于距离的分水岭分割的流程,python代码实现分水岭算法的图像分割
  • R-CNN:Rich feature hierarchies for accurate object detection and ... SPP-Net : Spatial Pyramid Pooling in Deep Convolutional Networks for Visual Recognition) 传统CNN和SPP-Net流程对比如下所示(引自...
  • 计算机操作系统实验之页面置换算法(C语言)

    万次阅读 多人点赞 2019-12-08 17:25:19
    在进程运行过程中,如果它需要访问的页面不在内存,需要把它调入内存,但是内存已满时,需要把内存中的某页数据送到磁盘的对换区中。而选择哪个页面,则由固定的算法来决定,称为页面置换算法
  • 一、缺页异常(缺页中断) 当 CPU 访问的⻚⾯不在物理内存时,便会产⽣⼀个...缺⻚中断的处理流程,如下: 在 CPU ⾥访问⼀条 Load M 指令,然后 CPU 会去找 M 所对应的⻚表项。 如果该⻚表项的状态位是「有效的」.

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,227
精华内容 4,090
关键字:

opt算法流程图