操作系统原理实验-动态分区分配方式的模拟

文章目录

• • 1.实验目的
  • 2.实验内容和要求
  • 3.主要仪器设备
  • 4.实验原理
  • 5.预备知识
  • 5.源程序
  • 7.实验步骤与调试
  • 8.实验结果与分析

1.实验目的

了解动态分区分配方式中使用的数据结构和分配算法，进一步加深对动态分区存储管理方式及其实现过程的理解。

2.实验内容和要求

1．用C或其他语言分别实现采用首次适应算法和最佳适应算法的动态分区分配过程和回收过程。
2．设置初始状态，每次分配和回收后显示出空闲内存分区链的情况。

3.主要仪器设备

仪器： PC机
实验环境： Ubuntu16.04
编程语言：C++

4.实验原理

程序执行流程图

5.预备知识

1. 动态分区分配
   动态分区分配是指，在处理作业的过程中，建立分区，依据用户请求的大小分配分区。在分区回收的过程中会涉及到一个空间利用效率相关的放置策略，即选择空闲区的策略。

2. 首次适应算法(First Fit)
   该算法从空闲分区链首开始查找，直至找到一个能满足其大小要求的空闲分区为止。然后再按照作业的大小，从该分区中划出一块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。
   优点：该算法倾向于使用内存中低地址部分的空闲区，在高地址部分的空闲区很少被利用，从而保留了高地址部分的大空闲区。显然为以后到达的大作业分配大的内存空间创造了条件。
   缺点：低地址部分不断被划分，留下许多难以利用、很小的空闲区，而每次查找又都从低地址部分开始，会增加查找的开销。

3. 最佳适应算法(Best Fit)
   该算法总是把既能满足要求，又是最小的空闲分区分配给作业。为了加速查找，该算法要求将所有的空闲区按其大小排序后，以递增的顺序形成一个空白链。这样每次找到的第一个满足要求的空闲区，必然是最优的。孤立地看，该算法似乎是最优的，但是事实上并不一定。因为每次分配后的剩余的空间一定是最小的，在存储器中将留下许多难以利用的小空闲区。同时每次分配后必须重新排序，这也带来了一定的开销。
   优点：每次分配给文件的都是最合适该文件大小的分区。
   缺点：内存中留下许多难以利用的小的空闲区。

5.源程序

#include
#include
using namespace std;
enum State{Free,Busy
};
#define OK 1
#define ERROR 0
#define max_length 640
int flag;
typedef bool Status;typedef struct Free_area{long size;long address;State state;
}ElemType;typedef struct DuLNode{ElemType data;struct DuLNode *prior;struct DuLNode *next;
}DuLNode,*DuLinkList;DuLinkList block_first;
DuLinkList block_last;
Status alloc(int);
Status free(int);
Status First_fit(int);
Status Best_fit(int);
void show();Status Initblock();
Status Initblock(){block_first = (DuLinkList)malloc(sizeof(DuLNode));block_last = (DuLinkList)malloc(sizeof(DuLNode));block_first->prior = NULL;block_first->next = block_last;block_last->prior = block_first;block_last->next = NULL;block_last->data.address = 0;block_last->data.size = max_length;block_last->data.state = Free;return OK;
}
Status alloc(int ch){int request = 0;cout << "Enter the size(KB) of main memory to be allocated:\n";cin >> request;if(request<=0){cout << "allocate error!Please enter again.\n"<next;elsereturn ERROR;}p->data.state = Free;/*merge with the previous free block*/if(p->prior != block_first && p->prior->data.state == Free){p->prior->data.size += p->data.size;p->prior->next = p->next;p->next->prior = p->prior;p = p->prior;}/*merge with the following free block*/if(p->next != block_last && p->next->data.state ==Free){p->data.size +=p->next->data.size;p->next->next->prior = p;p->next = p->next->next;}/*merge with the last free block*/if(p->next == block_last && p->next->data.state == Free){p->data.size += p->next->data.size;p->next=NULL;}return OK;
}
Status First_fit(int request){DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));temp->data.size = request;temp->data.state = Busy;DuLNode *p = block_first->next;while(p){if(p->data.state == Free && p->data.size == request){p->data.state = Busy;return OK;break;}if(p->data.state == Free && p->data.size>request){//temp->prior = p->prior;temp->next = p;temp->data.address = p->data.address;p->prior->next = temp;p->prior = temp;p->data.address = temp->data.address + temp->data.size;p->data.size -= request;return OK;break;	}p = p->next;}return ERROR;
}Status Best_fit(int request){int min_size;DuLinkList temp = (DuLinkList)malloc(sizeof(DuLNode));temp->data.size = request;temp->data.state = Busy;DuLNode *p = block_first->next;DuLNode *q = NULL;//record the best insert positionwhile(p)//initialize the min_size and the best positon{if(p->data.state == Free && (p->data.size)>=request){if(q==NULL){q=p;min_size = p->data.size - request;	}else if(q->data.size > p->data.size){q=p;min_size = p->data.size - request;}}p = p->next;}if(q==NULL){return ERROR;}else if(q->data.size == request){q->data.state = Busy;return OK;}else{temp->prior = q->prior;temp->next = q;temp->data.address = q->data.address;q->prior->next = temp;q->prior = temp;q->data.address = q->data.address+request;q->data.size = min_size; return OK;}
}void show()
{int flag=0;cout << "\nMain memory allocation:\n";cout << "++++++++++++++++++++++++++++++++++++++++++++++\n\n";DuLNode *p = block_first->next;cout << "block_id\t start_address\t block_size\t block_state\n\n";while(p){cout << "  " << flag++ << "\t\t";cout << "  " << p->data.address << "\t\t";cout << "  " << p->data.size << "KB\t\t";if(p->data.state == Free)cout << "free\n\n";elsecout << "busy\n\n";p = p->next;		}cout << "++++++++++++++++++++++++++++++++++++++++++++++\n\n";
}int main()
{int ch;// algorithm choicecout << "Please enter the memory allocation algorithm used:\n";cout << "1.First Fit\n2.Best Fit\n";cin >> ch;while(ch<1||ch>2){cout << "input error,please enter again!" <> ch;}Initblock();int choice;//operation choice while(1){show();cout << "\n 1.allocate\n 2.free\n 3.exit\n";cin >> choice;if(1==choice)alloc(ch);else if(2==choice){int flag;cout << "Please enter the block id which you want to free."<> flag;free(flag);}else if(3==choice){break;}else{cout<<"wrong input!Please do it again."<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！