江西师范大学计算机信息工程学院学生实验报告
专业_ 11级物联网班 姓名 _ 顾博君 学号_1108061001日期 2013.05.30
|
课程名称 |
操作系统 |
实验室名称 |
X4313 |
| 实验名称 |
存储管理分析 |
||
| 指导教师 |
朱明华 |
成绩 |
|
| 1、 实验目的： 用c语言模拟实现固定分区存储管理、可变分区存储管理、虚拟存储管理的空间分配
|
|||
| 2、 实验原理和内容 给出系统的分区及其大小起址和状态，把作业分配到各分区中 |
|||
| 3、 实验步骤 (1)分析问题，提出解决问题的算法 (2)编制程序 (3)程序调试 (4)记录实验结果，以及思考是否能够改善算法 |
|||
固定分区存储管理:
3
4 5 6
3
6 5 5
可变分区存储管理:
50
6
1 20 1
2 10 1
3 10 1
1 20 0
4 15 1
2 10 0
虚拟存储管理:
12
1 2 3 4 1 1 4 1 3 2 1 3
3
/**
* @author 顾博君
* @date 2013-5-18 begin
*/
#include <stdio.h>
#include <windows.h>
/**常量****************************/
#define TOTALSIZE_STATE 100
#define SIZE_OF_LIST 100
/**变量****************************/
int NumberOfMemory;//内存的数量
int SizeOfMemory[100];//内存的大小
int SizeOfAllMemory;//内存的总大小
int NumberOfMalloc;//需要申请的内存的数量
int SizeOfMalloc[100];//需要申请的内存的大小
int State[TOTALSIZE_STATE];//状态标志 0未分配，1已分配
/**结构体**************************/
typedef struct MyMemory {
int size;
int address;
struct MyMemory *next;
} MyMemory;
MyMemory systemMemory;//系统内存表
MyMemory freeMemory;//空闲区表
typedef struct WorkList {
int jobID;
int kind;
int sizeOfMemory;
} WorkList;
WorkList workList[SIZE_OF_LIST];//作业队列
int LenOfWorkList;
int numOfBlock;//系统分配的物理块数
/**函数****************************/
void showMenu();
void showMenu_dynamicStorageManagement();
int chooseView(int);
int chooseView_dynamicStorageManagement(int);
int showChoose();
void staticInput();
void dynamicInput();
void virtualInput();
void staticStorageManagement();//固定分区存储管理
void dynamicStorageManagement();//可变分区存储管理
void virtualStorageManagement();//虚拟存储管理
void firstAlgorithm();//最先分配算法
void bestAlgorithm();//最优分配算法
void worstAlgorithm();//最坏分配算法
void FIFOAlgorithm();//
void LRUAlgorithm();
void pause();
void print_list(char*,int,int*);
void initState();//初始化状态标志
void colorxy(int,int);
void printLine(int,char);
void print_block(int*);
MyMemory* listSort(MyMemory*,int);
/**
* 主函数
*/
int main() {
int c,t=1;
while(t) {
showMenu();//显示菜单
c=showChoose();//显示选择
t=chooseView(c);//根据用户指令选择界面
if(t==1)pause();//暂停
}
}
/**
* 显示主菜单
*/
void showMenu() {
printf("%30c*可变分区存储管理*\n\n",' ');
colorxy(0x0a,0x0a);
printf("========================\n");
printf(" 1.固定分区存储管理\n");
printf(" 2.可变分区存储管理\n");
printf(" 3.虚拟存储管理\n");
printf(" 4.退出\n");
printf("========================\n");
colorxy(0x07,0x07);
}
/**
* 显示可变分区存储管理菜单
*/
void showMenu_dynamicStorageManagement() {
printf("%30c*可变分区存储管理模拟*\n\n",' ');
colorxy(0x0b,0x0b);
printf("========================\n");
printf(" 1.最先分配算法\n");
printf(" 2.最优分配算法\n");
printf(" 3.最坏分配算法\n");
printf(" 4.返回\n");
printf("========================\n");
colorxy(0x07,0x07);
}
/**
* 显示虚拟存储管理菜单
*/
void showMenu_virtualStorageManagement() {
printf("%30c*虚拟存储管理模拟*\n\n",' ');
colorxy(0x0b,0x0b);
printf("========================\n");
printf(" 1.FIFO算法\n");
printf(" 2.LRU算法\n");
printf(" 3.返回\n");
printf("========================\n");
colorxy(0x07,0x07);
}
/**
* 显示选择
*/
int showChoose() {
int choose;
printf("请输入你的选择：");
scanf("%d",&choose);
return choose;
}
/**
* 根据主界面上的用户指令选择界面
*/
int chooseView(int choose) {
system("cls");
switch(choose) {
case 1:
staticInput();
staticStorageManagement();
break;
case 2:
dynamicStorageManagement();
return 2;
break;
case 3:
virtualStorageManagement();
return 2;
break;
case 4:
return 0;
default:
printf("你的输入有误！\n\n\n");
fflush(stdin);
pause();
return 2;
}
return 1;
}
/**
* 根据可变分区存储管理界面上的用户指令选择界面
*/
int chooseView_dynamicStorageManagement(int choose) {
system("cls");
switch(choose) {
case 1:
dynamicInput();
firstAlgorithm();
break;
case 2:
dynamicInput();
bestAlgorithm();
break;
case 3:
dynamicInput();
worstAlgorithm();
break;
case 4:
return 0;
default:
printf("你的输入有误！\n\n\n");
fflush(stdin);
return 2;
}
return 1;
}
/**
* 根据虚拟存储管理界面上的用户指令选择界面
*/
int chooseView_virtualStorageManagement(int choose) {
system("cls");
switch(choose) {
case 1:
virtualInput();
FIFOAlgorithm();
break;
case 2:
virtualInput();
LRUAlgorithm();
break;
case 3:
return 0;
default:
printf("你的输入有误！\n\n\n");
fflush(stdin);
return 2;
}
return 1;
}
/**
* 暂停
*/
void pause() {
system("pause");
system("cls");
}
//固定分区存储管理
void staticStorageManagement() {
int i,j,isAllo;
printf("staticStorageManagement\n");
printf("*************************************************************\n");
initState();//初始化状态标志
for(i=0; i<NumberOfMalloc; i++) {
isAllo=0;
printf("(作业%d ",i+1);
for(j=0; j<NumberOfMemory; j++) {
if(State[j]==0&&SizeOfMemory[j]>=SizeOfMalloc[i]) {
printf("大小：%d) 分配到 (内存%d 大小：%d)。\n",SizeOfMalloc[i],j+1,SizeOfMemory[j]);
State[j]=1;
isAllo=1;
break;
}
}
if(isAllo==0) {
printf("未分配到内存空间。\n");
}
}
printf("*************************************************************\n");
}
//可变分区存储管理
void dynamicStorageManagement() {
int c,t=1;
while(t) {
showMenu_dynamicStorageManagement();
c=showChoose();//显示选择
t=chooseView_dynamicStorageManagement(c);
if(t)pause();//暂停
}
}
/**
* 虚拟存储管理
*/
void virtualStorageManagement() {
int c,t=1;
while(t) {
showMenu_virtualStorageManagement();
c=showChoose();//显示选择
t=chooseView_virtualStorageManagement(c);
if(t)pause();//暂停
}
}
void staticInput() {
int i;
SizeOfAllMemory=0;
printf("请输入内存块数量：");
scanf("%d",&NumberOfMemory);
printf("请输入每块内存的大小：\n");
for(i=0; i<NumberOfMemory; i++) {
scanf("%d",&SizeOfMemory[i]);
SizeOfAllMemory+=SizeOfMemory[i];
}
print_list("内存块号",NumberOfMemory,SizeOfMemory);
printf("请输入你需要的内存数量：");
scanf("%d",&NumberOfMalloc);
printf("请输入每块内存的大小：\n");
for(i=0; i<NumberOfMalloc; i++) {
scanf("%d",SizeOfMalloc+i);
}
print_list("作业号",NumberOfMalloc,SizeOfMalloc);
pause();
}
void dynamicInput() {
int i;
MyMemory *t_free,*t_system;
//内存输入
t_free=(MyMemory*)malloc(sizeof(MyMemory));
printf("请输入内存块大小(int)：");
scanf("%d",&t_free->size);
t_free->address=0;
t_free->next=NULL;
freeMemory.next=t_free;
colorxy(0x0d,0x0d);
printLine(61,'*');///***********************************************************
printf("内存块的大小为：%d\n",t_free->size);
printLine(61,'*');///***********************************************************
colorxy(0x07,0x07);
//作业输入
printf("请输入作业队列：\n");
printf("请输入作业队列总长度(int)：");
scanf("%d",&LenOfWorkList);
printf("作业ID(int) 内存大小(int) 分配情况(1申请,0回收)(int)\n");
for(i=0; i<LenOfWorkList; i++) {
scanf("%d",&workList[i].jobID);
scanf("%d",&workList[i].sizeOfMemory);
scanf("%d",&workList[i].kind);
}
colorxy(0x0d,0x0d);
printLine(61,'*');///***********************************************************
for(i=0; i<LenOfWorkList; i++) {
printf("作业ID:%d 内存大小:%d 分配情况:",workList[i].jobID,workList[i].sizeOfMemory);
if(workList[i].kind!=0) {
colorxy(0x0b,0x0b);
printf("申请内存\n");
colorxy(0x0d,0x0d);
} else {
colorxy(0x0c,0x0c);
printf("释放内存\n");
colorxy(0x0d,0x0d);
}
}
printLine(61,'*');///***********************************************************
colorxy(0x07,0x07);
pause();
}
void virtualInput() {
int i;
//作业输入
printf("请输入作业队列：\n");
printf("请输入作业队列总长度(int)：");
scanf("%d",&LenOfWorkList);
printf("作业ID(int)\n");
for(i=0; i<LenOfWorkList; i++) {
scanf("%d",&workList[i].jobID);
}
colorxy(0x0d,0x0d);
printLine(61,'*');///***********************************************************
for(i=0; i<LenOfWorkList; i++) {
printf("作业ID:%d\n",workList[i].jobID);
}
printLine(61,'*');///***********************************************************
colorxy(0x07,0x07);
printf("系统分配的物理块数:");
scanf("%d",&numOfBlock);
pause();
}
void firstAlgorithm() {
int i;
int add=0;
int count=1;
MyMemory *t_free,*t_system;
MyMemory *freeM;
for(i=0; i<LenOfWorkList; i++) {
printf("firstAlgorithm\n");
colorxy(0x0d,0x0d);
printf("第%d次:\n",count++);
printLine(61,'*');///***********************************************************
printf("作业 %d ",workList[i].jobID);
freeM=freeMemory.next;
if(workList[i].kind!=0) {
colorxy(0x0b,0x0b);
printf("申请内存:");
colorxy(0x0d,0x0d);
while(freeM) {
if(freeM->size>=workList[i].sizeOfMemory) {
freeM->size=freeM->size-workList[i].sizeOfMemory;
t_system=(MyMemory*)malloc(sizeof(MyMemory));
t_system->size=workList[i].sizeOfMemory;
t_system->next=NULL;
t_system->address=add;
freeM->address=t_system->address;
t_system->next=systemMemory.next;
systemMemory.next=t_system;
add+=freeM->size;
break;
} else {
freeM=freeM->next;
}
}
} else {
colorxy(0x0c,0x0c);
printf("释放内存:");
colorxy(0x0d,0x0d);
t_free=(MyMemory*)malloc(sizeof(MyMemory));
t_free->size=workList[i].sizeOfMemory;
t_free->next=freeMemory.next;
freeMemory.next=t_free;
}
printf("%d\n",workList[i].sizeOfMemory);
freeM=freeMemory.next;
printLine(61,'-');///--------------------------------------------------
while(freeM) {
printf("剩余可用内存：%d\n",freeM->size);
freeM=freeM->next;
}
printLine(61,'*');///***********************************************************
colorxy(0x07,0x07);
if(i!=LenOfWorkList-1)
pause();
}
}
void bestAlgorithm() {
int i;
int add=0;
int count=1;
MyMemory *t_free,*t_system;
MyMemory *freeM;
for(i=0; i<LenOfWorkList; i++) {
printf("bestAlgorithm\n");
colorxy(0x0d,0x0d);
printf("第%d次:\n",count++);
printLine(61,'*');///***********************************************************
printf("作业 %d ",workList[i].jobID);
freeM=freeMemory.next;
if(workList[i].kind!=0) {
colorxy(0x0b,0x0b);
printf("申请内存:");
colorxy(0x0d,0x0d);
while(freeM) {
if(freeM->size>=workList[i].sizeOfMemory) {
freeM->size=freeM->size-workList[i].sizeOfMemory;
t_system=(MyMemory*)malloc(sizeof(MyMemory));
t_system->size=workList[i].sizeOfMemory;
t_system->next=NULL;
t_system->address=add;
freeM->address=t_system->address;
t_system->next=systemMemory.next;
systemMemory.next=t_system;
add+=freeM->size;
break;
} else {
freeM=freeM->next;
}
}
} else {
colorxy(0x0c,0x0c);
printf("释放内存:");
colorxy(0x0d,0x0d);
t_free=(MyMemory*)malloc(sizeof(MyMemory));
t_free->size=workList[i].sizeOfMemory;
t_free->next=freeMemory.next;
freeMemory.next=t_free;
}
printf("%d\n",workList[i].sizeOfMemory);
freeMemory.next=listSort(freeMemory.next,1);
freeM=freeMemory.next;
printLine(61,'-');///--------------------------------------------------
while(freeM) {
printf("剩余可用内存：%d\n",freeM->size);
freeM=freeM->next;
}
printLine(61,'*');///***********************************************************
colorxy(0x07,0x07);
if(i!=LenOfWorkList-1)
pause();
}
}
void worstAlgorithm() {
int i;
int add=0;
int count=1;
MyMemory *t_free,*t_system;
MyMemory *freeM;
for(i=0; i<LenOfWorkList; i++) {
printf("worstAlgorithm\n");
colorxy(0x0d,0x0d);
printf("第%d次:\n",count++);
printLine(61,'*');///***********************************************************
printf("作业 %d ",workList[i].jobID);
freeM=freeMemory.next;
if(workList[i].kind!=0) {
colorxy(0x0b,0x0b);
printf("申请内存:");
colorxy(0x0d,0x0d);
while(freeM) {
if(freeM->size>=workList[i].sizeOfMemory) {
freeM->size=freeM->size-workList[i].sizeOfMemory;
t_system=(MyMemory*)malloc(sizeof(MyMemory));
t_system->size=workList[i].sizeOfMemory;
t_system->next=NULL;
t_system->address=add;
freeM->address=t_system->address;
t_system->next=systemMemory.next;
systemMemory.next=t_system;
add+=freeM->size;
break;
} else {
freeM=freeM->next;
}
}
} else {
colorxy(0x0c,0x0c);
printf("释放内存:");
colorxy(0x0d,0x0d);
t_free=(MyMemory*)malloc(sizeof(MyMemory));
t_free->size=workList[i].sizeOfMemory;
t_free->next=freeMemory.next;
freeMemory.next=t_free;
}
printf("%d\n",workList[i].sizeOfMemory);
freeMemory.next=listSort(freeMemory.next,0);
freeM=freeMemory.next;
printLine(61,'-');///--------------------------------------------------
while(freeM) {
printf("剩余可用内存：%d\n",freeM->size);
freeM=freeM->next;
}
printLine(61,'*');///***********************************************************
colorxy(0x07,0x07);
if(i!=LenOfWorkList-1)
pause();
}
}
void FIFOAlgorithm() {
int i,j;
int Flag_find;//找到标记
int count_less=0;//缺页中断次数
int block[100];
printf("fifo\n");
for(i=0; i<100; i++)block[i]=-1;
for(i=0; i<LenOfWorkList; i++) {
for(Flag_find=j=0; j<numOfBlock; j++) {
if(workList[i].jobID==block[j]) {
Flag_find=1;
break;
}
}
if(Flag_find){
print_block(block);
printf("\n");
}else{
for(j=numOfBlock;j>0;j--){
block[j]=block[j-1];
}
block[0]=workList[i].jobID;
print_block(block);
printf("*\n");
count_less++;
}
}
printf("缺页中断次数：%d\n",count_less);
printf("缺页中断率：%.2f%%\n",(float)count_less/LenOfWorkList*100);
}
void LRUAlgorithm() {
int i,j;
int Flag_find;//找到标记
int count_less=0;//缺页中断次数
int block[100];
printf("LRU\n");
for(i=0; i<100; i++)block[i]=-1;
for(i=0; i<LenOfWorkList; i++) {
for(Flag_find=j=0; j<numOfBlock; j++) {
if(workList[i].jobID==block[j]) {
Flag_find=1;
break;
}
}
if(Flag_find){
for(;j>0;j--){
block[j]=block[j-1];
}
block[0]=workList[i].jobID;
print_block(block);
printf("\n");
}else{
for(j=numOfBlock;j>0;j--){
block[j]=block[j-1];
}
block[0]=workList[i].jobID;
print_block(block);
printf("*\n");
count_less++;
}
}
printf("缺页中断次数：%d\n",count_less);
printf("缺页中断率：%.2f%%\n",(float)count_less/LenOfWorkList*100);
}
/**
* 打印列表
*/
void print_list(char *str,int num,int *s) {
int i;
printf("*************************************************************\n");
for(i=0; i<num; i++) {
printf("%s:%d 大小:%d\n",str,i+1,s[i]);
}
printf("*************************************************************\n");
}
/**
* 打印物理块
*/
void print_block(int *block){
int i;
for(i=0;i<numOfBlock;i++){
if(block[i]==-1)
printf("%3c ",'-');
else
printf("%3d ",block[i]);
}
}
/**
* 打印横线
*/
void printLine(int n,char c) {
int i;
for(i=0; i<n; i++)
printf("%c",c);
if(n!=80)
printf("\n");
}
/**
* 初始化状态标志
*/
void initState() {
int i;
for(i=0; i<TOTALSIZE_STATE; i++) {
State[i]=0;
}
}
/**
* 改变文字颜色
*/
void colorxy(int x, int y) {
HANDLE hOut;
hOut = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hOut, x|y);
}
/**
* 单链表排序
* @param head
* @param i 1升序排序 0降序排序
*/
MyMemory* listSort(MyMemory* head,int i) {
MyMemory *t,*p,*pre;
pre=head;
if(!pre)return NULL;
p=pre->next;
pre->next=NULL;
for(; p; ) {
t=p;
p=p->next;
if(i) {
for(pre=head; pre->next&&t->size>pre->next->size; pre=pre->next);
if(pre==head&&pre->size>t->size) {
t->next=head;
head=t;
} else {
t->next=pre->next;
pre->next=t;
}
} else {
for(pre=head; pre->next&&t->size<pre->next->size; pre=pre->next);
if(pre==head&&pre->size<t->size) {
t->next=head;
head=t;
} else {
t->next=pre->next;
pre->next=t;
}
}
}
return head;
}