先进先出置换算法实现请求分页存储管理(C语言)

Myth丶恋晨 2023-02-11 12:27 20阅读 0赞

## 要求 ##

*  作业共有320条指令，假设每个页面存放10条指令，它的地址空间为32页，初始状态所有页都未调入内存。
 *  分配给作业的内存块数为4。
 *  如果访问的指令在内存，则显示其物理地址，转入下一条指令，否则发生缺页，此时记录缺页次数，将相应页调入内存；
 *  如果4个内存块均已占用，需进行页面置换，最后显示其物理地址，并转入下一条指令。
 *  在所有320条指令执行完毕后，计算并显示作业运行过程中发生的缺页率。
 *  作业中指令的访问次序按下述原则生成：  
    1、在\[0，319\]之间随机选取一条起始指令，序号为m ；  
    2、顺序执行下一条指令，即序号为m+1的指令；  
    3、通过随机数，跳转到前地址部分\[0，m-1\]中的某条指令处，其序号为m1;  
    4、顺序执行下一条指令，即序号为m1+1的指令；  
    5、通过随机数，跳转到后地址部分\[m1+2,319\]中的某条指令处，其序号为m2；  
    6、顺序执行下一条指令，即序号为m2+1的指令；  
    重复跳转到前地址部分、顺序执行、跳转到后地址部分、顺序执行的过程，直至执行320条指令。

## 流程图 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70]

## 源代码 ##

#include <stdio.h>
    #include <stdlib.h>
    #include <time.h>
    #define totalCmdNum 320 // 指令总数
    #define BlockNum 4 // 内存块总数
    
    // 内存块结构体
    typedef struct { 
    	int id;			// 物理地址
    	int page;		// 页号(默认为-1)
    	int keepTime;	// 在内存中驻留的时间
    } Block;
    
    int cmdNum = 0;					// 指令执行次数
    int curCmd;						// 当前正在执行的指令
    int isExecute[totalCmdNum];		// 判断每条指令是否执行的标志数组
    double lostPage = 0;			// 缺页次数
    Block *blocks[BlockNum];		// 内存块指针数组
    
    // 初始化
    void init() { 
    	// 初始化标志数组
    	for (int i = 0; i < totalCmdNum; i++) { 
    		// 0代表未执行
    		isExecute[i] = 0;
    	}
    	// 设置随机数种子
    	srand(time(NULL));
    	// 初始化内存块数组
    	for (int i = 0; i < BlockNum; i++) { 
    		// 分配空间
    		blocks[i] = (Block *)malloc(sizeof(Block));
    		blocks[i]->id = i + 1;		// 物理地址
    		blocks[i]->page = -1;		// -1 代表此页还未分配 
    		blocks[i]->keepTime = 0;	// 内存驻留时间
    	}
    }
    
    // 产生指令
    int genCmd() { 
    	cmdNum++;			// 累计指令条数
    	if (cmdNum == 1) { 
    		curCmd = rand() % totalCmdNum;
    	}
    	if (cmdNum == 2) { 
    		curCmd++;		// 顺序执行下一条指令
    	}
    
    	if (cmdNum >= 3) { 
    		switch ((cmdNum - 2) % 4) { 
    		case 1:			// 前地址部分
    			curCmd = rand() % (curCmd - 2);
    			break;
    		case 2:
    		case 0:
    			curCmd++;	// 顺序执行下一条指令
    			break;
    		case 3:			// 后地址部分
    			curCmd = curCmd + 1 + rand() % (totalCmdNum - curCmd);
    			break;
    		}
    	}
    	isExecute[curCmd] = 1;		// 1代表该指令已被执行(可以重复执行)
    	return curCmd;
    }
    
    // 判断所有指令是否全部执行了一遍
    int isFinish() { 
    	int flag = 1;
    	// 遍历所有指令执行情况
    	for (int i = 0; i < totalCmdNum; i++) { 
    		if (isExecute[i] == 0) { 
    			flag = 0;
    			break;
    		}
    	}
    	return flag;
    }
    
    // 作业调度
    void dispatchJob() { 
    	int page = genCmd() / 10;		// 根据指令号计算页号
    
    	int i = 0;
    	for (; i < BlockNum; i++) { 
    		// 如果访问的指令在内存中，则显示其物理地址
    		if (blocks[i]->page == page) { 
    			printf("指令%3d在内存块%d中\n", curCmd, blocks[i]->id);
    			break;
    		}
    	}
    
    	// 如果访问的指令不在内存中
    	if (i >= BlockNum) { 
    		i = 0;
    		for (; i < BlockNum; i++) { 			// 寻找未分配的内存块
    			if (blocks[i]->page == -1) { 		
    				blocks[i]->page = page;
    				//printf("内存块未分配\n");
    				printf("指令%3d在内存块%d中\n", curCmd, blocks[i]->id);
    				break;
    			}
    		}
    	}
    
    	// 如果所有内存块都已被分配
    	if (i >= BlockNum) { 
    		int oldestBlock = 0;	// 最先被分配的内存块
    		int maxKeepTime = blocks[0]->keepTime;		// 最长内存驻留时间
    		i = 1;
    		for (; i < BlockNum; i++) { 
    			if (blocks[i]->keepTime > maxKeepTime) { 
    				oldestBlock = blocks[i]->id;
    				maxKeepTime = blocks[i]->keepTime;
    			}
    		}
    		blocks[oldestBlock]->page = page;
    		blocks[oldestBlock]->keepTime = 0;
    		lostPage++;		// 累计缺页次数
    		//printf("缺页了\n");
    		printf("指令%3d在内存块%d中\n", curCmd, blocks[oldestBlock]->id);
    	}
    
    	i = 0;
    	for (; i < BlockNum; i++) { 
    		if (blocks[i]->page != -1) { 
    			blocks[i]->keepTime++;		// 累计驻留时间
    		}
    	}
    }
    
    int main() { 
    	init();					// 初始化
    	while (1) { 
    		dispatchJob();		// 作业调度
    		if (isFinish()) { 	// 判断作业是否运行完成
    			break;
    		}
    	}
    
    	printf("\n共执行指令%d条\n", cmdNum);
    	printf("缺页率约为:%.1lf%%\n", (lostPage / cmdNum)*100);
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200523191127778.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM4OTAyODQ0,size_16,color_FFFFFF,t_70