天津理工大学操作系统实验二

实验报告学院（系）名称：​计算机与通信工程学院姓名卢洪利学号20146049专业计算机科学与技术班级2014级4班实验项目实验二：存储器的分配与回收算法实现课程名称操作系统课程代码0668036实验时间2016年11月28日第5～8节2016年12月1日第1～4节2016年12月15日第1～4节实验地点软件实验室7-220软件实验室7-220软件实验室7-220批改意见成绩教师签字：第1页共7页实验环境：●操作系统：Fedora25withLinux4.8.12-300.fc25.x86_64●编程语言：Python3.5.2●开发环境：PyCharm2016.3实验内容​：1.模拟操作系统的主存分配，运用可变分区的存储管理算法设计主存分配和回收程序，并不实际启动装入作业。2.采用最先适应法、最佳适应法、最坏适应法分配主存空间。3.当一个新作业要求装入主存时，必须查空闲区表，从中找出一个足够大的空闲区。若找到的空闲区大于作业需要量，这是应把它分成二部分，一部分为占用区，加一部分又成为一个空闲区。4.当一个作业撤离时，归还的区域如果与其他空闲区相邻，则应合并成一个较大的空闲区，登在空闲区表中。5.运行所设计的程序，输出有关数据结构表项的变化和内存的当前状态。实验要求：1．详细描述实验设计思想、程序结构及各模块设计思路；2．详细描述程序所用数据结构及算法；3．明确给出测试用例和实验结果；4．为增加程序可读性，在程序中进行适当注释说明；5．认真进行实验总结，包括：设计中遇到的问题、解决方法与收获等；6．实验报告撰写要求结构清晰、描述准确逻辑性强；7．实验过程中，同学之间可以进行讨论互相提高，但绝对禁止抄袭。实验过程：1.设计思想程序设计了两个类：MemoryTable和MemoryBlock。其中MemoryBlock是模拟的内存块，包括空间（size）和地址（address）两个属性以及操作它们的方法；MemoryTable是一个对Pythonlist数据类型的封装，用来存储多个MemoryBlock，实现空闲区表。已经分配的MemoryBlock因为除了还回给空闲表外不需要进行其他操作，直接使用了原生list进行存储。2.测试用例以下测试用例借用了Python的random模块由系统随机生成，程序中__main__函数为测试函数空闲块：No.0(addr:0,size:25)No.1(addr:25,size:47)进程：Process1need:16Process2need:12第2页共7页3.运行结果/usr/bin/python3.5/home/ward/PycharmProjects/os2/main.pyNo.0(addr:0,size:25)No.1(addr:25,size:47)============================================Process1need:16Allocatedsize:16Allocatedaddress:9No.0(addr:0,size:9)No.1(addr:25,size:47)============================================Process2need:12Allocatedsize:12Allocatedaddress:60No.0(addr:0,size:9)No.1(addr:25,size:35)============================================Finally:No.0(addr:0,size:25)No.1(addr:25,size:47)Processfinishedwithexitcode04.实验总结分配内存时，大多空闲块都需要切割，而归还时需要合并，切割与合并都需要注意空闲表的边界和对空闲块操作前后的空间（size）和地址（address）变化。另外，切割后需要分配哪一块需要在与归还时对应。上面提到的注意点容易出现访问越界、归还时产生碎片、归还后地址冲突、分配失败等问题。5.附录（源代码）：注：Python代码中由​包围或由#开头的行为注释信息#coding=utf-8importrandomclassMemoryBlock:Classofmemoryblock__size=0__address=0def__init__(self):self.__size=0self.__address=0def__init__(self,size,address):self.__size=sizeself.__address=addressdefset_size(self,size):self.__size=sizedefset_address(self,address):self.__address=address第3页共7页defget_size(self):returnself.__sizedefget_address(self):returnself.__addressdefadd_size(self,size):self.__size+=sizeclassMemoryTable:Memorytable,containsallmemoryblocksBasedonPythonList__list=[]defadd(self,obj):#Appendatendself.__list.append(obj)defblock_at(self,id):returnself.__list[id]defget_count(self):returnlen(self.__list)defmax(self):max_no=0forcntinrange(1,len(self.__list)):ifself.__list[cnt]self.__list[max]:max_no=cntreturnself.__list[max_no]defgive_back(self,obj):ifobj.get_address()self.__list[len(self.__list)-1].get_address():self.__list[len(self.__list)-1].add_size(obj.get_size())else:forcntinrange(0,self.get_count()):ifself.get_count()==1:self.__list[0].add_size(obj.get_size())elifobj.get_address()self.__list[cnt].get_address():ifobj.get_address()self.__list[cnt+1].get_address():self.__list[cnt].add_size(obj.get_size())returndeffirst_fit(self,size):forcntinrange(0,self.get_count()):ifself.block_at(cnt).get_size()=size:temp_return=self.block_at(cnt)delself.__list[cnt]第4页共7页iftemp_return.get_size()==size:returntemp_returnelse:Whenthefreeblockfoundistoobigdivideitintotwoblocksonetooccupied(occupied_block)andtheother(back_block)goingbacktotableback_block=MemoryBlock(temp_return.get_size()-size,temp_return.get_address())occupied_block=MemoryBlock(size,back_block.get_size()+back_block.get_address())self.__list.insert(cnt,back_block)returnoccupied_blockreturnNonedefbest_fit(self,size):min=abs(self.__list[0].get_size()-size)min_no=-1forcntinrange(0,self.get_count()):ifself.__list[cnt].get_size()-sizemin:ifself.__list[cnt].get_size()-size0:min=abs(self.__list[cnt].get_size()-size)min_no=cntifmin_no==-1:returnNonetemp_return=self.__list[min_no]cnt=min_nodelself.__list[cnt]iftemp_return.get_size()==size:returntemp_returnelse:back_block=MemoryBlock(temp_return.get_size()-size,temp_return.get_address())occupied_block=MemoryBlock(size,back_block.get_size()+back_block.get_address())self.__list.insert(cnt,back_block)returnoccupied_blockdefworst_fit(self,size):temp_return=self.max()iftemp_return.get_size()size:returnNonecnt=self.__list.index(temp_return)delself.__list[cnt]iftemp_return.get_size()==size:returntemp_returnelse:back_block=MemoryBlock(temp_return.get_size()-size,temp_return.get_address())occupied_block=MemoryBlock(size,back_block.get_size()+back_block.get_address())self.__list.insert(cnt,back_block)第5页共7页returnoccupied_blockdefshow_detail(self):Showdetailsaboutallblocksforcntinrange(0,len(self.__list)):print(No.+str(cnt)+(addr:+str(self.__list[cnt].get_address())+,size:+str(self.__list[cnt].get_size())+))classPROCESS:Processclass__need_size=0def__init__(self,size):self.__need_size=sizedefget_size(self):returnself.__need_sizedefset_size(self,size):self.__need_size=sizeThebeginningoftime,mainfunctionif__name__==__main__:temp_size=0temp_address=0#Freememoryblocktablefree_table=MemoryTable()#Allocatedmemoryblocktablealloc_table=[]Generatetwomemoryblocks.Everyonehasarandomsize.temp_size=random.randint(1,50)te