操作系统-动态分区式存贮区管理

2018-01-12 11:06:02来源:网络收集作者:咖啡不加糖人点击

分享

阿里云爆款(一)、程序功能:模拟动态分区式存贮区管理
(二)、设计思路:

1、设计一个动态分区式存贮区管理程序,支持不同的放置策略。如首次、最佳、最坏。


2、分区描述器中为 :flag/size/next;


3、自由主存队列按链表组织,主存大小假设为maxsize(单位为节=rd的大小)。


4、作业申请n节,实际分配的分区大小应为n+1节。
其中一节作为分区描述器,其他n节提供给作业。


5、已分配区放在高地址处。


6、合并时应考虑四种情况:


假设回收区为r,上邻为f1(f1需搜索自由主存队列),下邻为f2(f2可直接计算)


A) f1空闲,f2已分配;


B) f1已分配,f2空闲;


C) f1空闲,f2空闲;


D) f1已分配,f2已分配;


(三)、数据结构
1、PCB类(进程控制器):

私有数据成员


类型

名称

注释


int

begin

进程开始的首地址


int

size

进程占用的大小


string

name

进程名


函数


声明

注释


PCB(string n="无'",int s=0,int b=0)

构造函数


ostream& operator<<(ostream&os, PCB&P)

重定义输出函数


注:PCB类是manage类的友元类。


2、block类(分区描述器):

私有数据成员


类型

名称

注释


int

m_size

分区的大小


bool

m_falg

判断该分区是否被占用


block*

next

下一个分区的地址


函数


函数声明

注释


block(bool flag = false… …)

构造函数


ostream& operator<<(ostream&os, block&P)

重定义输出函数


注:block类是manage类的友元类。


3、manage类

私有数据成员


类型

名称

注释


block*

first;

分区链表首地址


vector

lib;

未结束的所有进程


函数 


声明

注释


manage()

构造函数


void first_time();

首次适应算法


void best();

最佳适应算法


void worst();

最坏适应算法


void free();

内存回收


void show();

显示内存分配情况


 


(四)、算法设计
1、首次适应算法

首次适应算法是将程序放入到主存中,按地址查找到第一个能装入它的空闲区。在首次适应算法中,空闲区是按其位置的顺序链接在一起,即每一个后继空闲去的起始地址总比他前者大。当要分配一个分区时,总是从低地址空闲区开始查寻,直到找到第一个足以满足该程序要求的空闲区为止。


代码:


void manage::first_time() {
cout << "输入进程名和大小:";
string name; int size,addr(0);
cin >> name >> size;
block* p(first);
while (p != nullptr) {//寻找块
addr +=(p->m_size+1);//计算地址
if (p->m_flag == false) {//当前块未被占用
if (p->m_size > size) {//当前块的大小大于进程申请的大小
p->m_size -= (size + 1);//从当前块中减去进程申请的大小
block* temp=new block(true,size,p->m_next);//新建一个进程块
p->m_next = temp;//添加到当前块的后面
addr -= (size + 1);//重新计算当前块的地址
break;
}
else if (p->m_size == size) {//当前块的大小刚好够进程申请的大小
p->m_flag = true;//直接更改当前块的状态为已占用,不用分裂块
addr -= (size + 1);//重新计算地址
break;
}
else p = p->m_next;//当前块的大小不满足进程申请的大小,先后继续寻找。
}
else p = p->m_next;//当前块已被占用,先后继续寻找
}
if (p == nullptr)cout << "分配失败" << endl;//未找到符合条件的块,分配失败
else {//找到符合条件的块,该进程存入lib进程库中
PCB temp(name, size, addr);
lib.push_back(temp);
}
}


2、最佳适应算法

最佳适应算法是将程序放入主存中与他所需大小最接近的空闲区中,在最佳适应算法中,空闲区队列是按空闲区大小递增顺序链接在一起的。在进行分配时总是从最小的空闲区开始查寻,因而找到的第一个能满足要求的空闲区便是最佳的一个。即从所要求的大小来看,该区和气候的所有空闲区相比它是最接近的。
代码:


void manage::best() {
cout << "输入进程名和大小:";
string name; int size, addr1(0),addr2(0);
cin >> name >> size;
block *p(first),*q(nullptr);
int Error(512);
while (p != nullptr) {
addr1 += (p->m_size + 1);
if (p->m_flag == false) {//当前块未被占用
if (p->m_size > size) {//当前块的大小满足进程请求的大小
if (p->m_size - size < Error) {//当前块更合适该进程
Error = p->m_size - size;//计算偏差
q = p;//保存当前块的地址
addr2 = addr1 - size - 1;
p = p->m_next;//指针后移
}
else p = p->m_next;//和之前的块相比,之前的块更合适该进程
}
else if (p->m_size == size) {//当前块的大小刚好等于进程申请的大小
q = p;//已找到最合适的块,保存当前块的信息并退出
addr2 = addr1 - size - 1;
Error = 0;
break;
}
else p = p->m_next;//当前块的大小小于进程请求的大小,继续先后搜索
}
else p = p->m_next;//当前块已经被占用,继续先后搜索
}
if (Error == 512)cout << "分配失败" << endl;
else {
if (Error == 0)q->m_flag = true;
else {
q->m_size -= (size + 1);//从当前块中减去进程申请的大小
block* temp = new block(true, size, q->m_next);//新建一个进程块
q->m_next = temp;//添加到当前块的后面
}
PCB temp(name, size, addr2);
lib.push_back(temp);
}
}


3、最坏适应算法

最坏适应算法就是将程序放入主存中最不适合它的空闲区,即最大的空闲区内。在最坏适应算法中,空闲区是按大小递减顺序连接到一起的,因此,其队列指针总是指向最大空闲区,在进行分配时,总是从最大空闲区开始查寻。


代码:


void manage::worst() {
cout << "输入进程名和大小:";
string name; int size, addr1(0), addr2(0);
cin >> name >> size;
block *p(first), *q(nullptr);
int Error(0);
while (p != nullptr) {
addr1 += (p->m_size + 1);
if (p->m_flag == false) {//当前块未被占用
if (p->m_size >= size) {//当前块的大小满足进程请求的大小
if (p->m_size - size >= Error) {//当前块比之前块更大
Error = p->m_size - size;//计算偏差
q = p;//保存当前块的地址
addr2 = addr1 - size - 1;
p = p->m_next;//指针后移
}
else p = p->m_next;//和之前的块相比,之前的块更合适该进程
}
else p = p->m_next;//当前块的大小小于进程请求的大小,继续先后搜索
}
else p = p->m_next;//当前块已经被占用,继续先后搜索
}
if (Error == 0)cout << "分配失败" << endl;
else {
q->m_size -= (size + 1);//从当前块中减去进程申请的大小
block* temp = new block(true, size, q->m_next);//新建一个进程块
q->m_next = temp;//添加到当前块的后面
PCB temp1(name, size, addr2);
lib.push_back(temp1);
}
}


4、内存回收

在内存回收时应考虑四种情况:


假设回收区为r,上邻为f1(f1需搜索自由主存队列),下邻为f2(f2可直接计算)


A) f1空闲,f2已分配:r和f1合并


B) f1已分配,f2空闲:r和f2合并


C) f1空闲,f2空闲:r和f1、f2合并


D) f1已分配,f2已分配:r不和任何分区合并


代码:


void manage::free() {
cout << "输入回收进程的名称:";
string name;
cin >> name;
//在lib库中查找是否存在该进程
vector::iterator it = lib.begin();
while (it != lib.end()){
if (it->name == name)
break;
else it++;
}
//该进程不存在,直接提示并退出函数
if (it == lib.end()) {
cout << "该进程不存在" << endl;
return;
}
//进程存在
else {
int addr(0); block *p(first);
while (p != nullptr) {//查找该进程所占用的内存块
if (it->begin == addr)break;//查找到该进程
addr += (p->m_size + 1);
p = p->m_next;
}
if (p == nullptr)cout << "未在内存中查找到该进程" << endl;
else {
p->m_flag = false;//该内存块的状态更改为未占用//所回收的内存块后面存在空闲的内存块
if (p->m_next != nullptr&&p->m_next->m_flag==false) {
p->m_size += p->m_next->m_size;//该内存块的大小增加为为俩内存大小之和
block *temp(p->m_next);
p->m_next = p->m_next->m_next;//更改指针指向
delete temp;//释放后一指针的空间
}
lib.erase(it);//进程库中删除当前进程
//所回收的内存块前面存在空闲的内存块
block *q(first);
//寻找到所回收的内存块前面的内存块
while (q != nullptr) {
//所回收的内存块前面存在空闲的内存块
if (q->m_next==p&&q->m_flag == false) {
q->m_size += (p->m_size + 1);
q->m_next = p->m_next;
delete p;
break;
}
q = q->m_next;
}
}
}
}


(五)、程序运行情况
1、测试数据:初始值大小为512(分区描述器占一位,实际大小为511);
2、测试结果:
(1)、首次适应算法
操作系统-动态分区式存贮区管理操作系统-动态分区式存贮区管理

 


(2)、最佳适应算法

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台