第一篇:北工《操作系统》作业考核试题参考答案
北京理工大学远程教育学院2019-2020学年第二学期 《操作系统》期末试卷(A卷)应用题(每题20分,共100分)1.试说明操作系统与硬件、其他系统软件以及用户之间的关系。
2.常见的进程调度算法包括先来先服务算法、短作业优先调度算法、高优先权优先调度算法和基于时间片的轮转调度算法,请简述这几个算法的调度思想。
3.操作系统的主要任务是什么?请论述其基本功能。
4.请论述基本分页系统中将逻辑地址L转化为物理地址的过程。
5.某工厂有一个可以存放设备的仓库,总共有8个位置可以存放8台设备。生产部门生产的每一台设备都必须入库。销售部门可以从仓库提出设备供应客户。设备的出库和入库都必须借助运输工具。现在只有一套运输工具,每次只能运输一台设备,系统共使用三个信号量,S代表互斥信号量,表示运输工具;
S1和S2均为同步信号量,S1表示仓库中可以存放设备的空闲位置,S2表示仓库中已经被设备占用了的位置。请设计一个能协调工作的自动调度管理系统,并利用记录型信号量写出解决此问题的程序代码,请注明信号量的初值。
(93)北京理工大学远程教育学院2019-2020学年第二学期 《操作系统》期末试卷(A卷)答题纸
第二篇:福师《民法》作业考核参考试题答案
《民法》期末考试A卷
姓名:专业:
学号:学习中心:
成绩:
一、简答题(34分)
1、简述抵押权的概念及含义。(6分)
2、简述租赁合同的效力。(6分)
3、简述遗嘱的有效要件。(6分)
4、简述意思自治原则的含义及主要体现。(8分)
5、简述宣告失踪的概念、条件及法律后果。(8分)
二、论述题(42分)
1、试述实现留置权的条件及程序。(10分)
2、试述建筑物区分所有权的概念及客体。(10分)
3、何为同时履行抗辩权?其构成要件有哪些?(12分)
4、试述保证的主要特征。(10分)
三、案例分析题(24分)
杨某(男)与马某(女)于1990年登记结婚。后因感情恶化,于2001年11月经协商,双方到婚姻登记机关办理了离婚登记,并对夫妻共同财产进行了分割。2005年12月3日,马某得知,杨某曾于2001年8月以10万元购买一套房屋,在办理离婚手续时并没有告知马某,致使这一本属夫妻共同财产的房屋为杨某独自占有,因而于2006年1月向人民法院起诉,要求重新分割这部分财产。杨某辩称:当初离婚时,双方已经就夫妻共同财产进行了分割,现在已经四年多,诉讼时效已过,马某再来请求分割财产,没有法律依据。
根据本案案情,回答下列问题,并说明理由:
1、马某能否请求再次分割夫妻共同财产?(8分)
2、本案中,马某请求权的诉讼时效从何时起算?是否已超过诉讼时效?(8分)
3、人民法院应当如何处理这一案件?(8分)
第三篇:内审员考核试题答案
实验室资质认定评审准则
内审员考核试题答案
单位:
姓名
得分
一 判断题(共20分,每题2分)计量认证和审查认可均属于资质评定
(√)
资质评定的执行主体是第三方
(×)
资质评定是自愿行为
(×)
实验室应建立以过程为基础的管理体系
(√)
实验室应通过实施纠正措施、预防措施等持续改进其管理体系
(√)
实验室的监督员就是内审员
(×)
实验室的授权签字人必须是技术主管
(×)
为保证独立性,实验室不允许将其工作的一部分分包出去
(×)
校准证书必须给出测量不确定度,而检测报告则不用给出
测量不确定度
(×)
10由于计量检定机构是国家法定的,所以其提供的检定结果
肯定正确可靠,实验室没有必要再进行检查确认
(×)二 填空题(共20分,每空2分)实验室选择检测/校准方法时,应优先考虑-------A--------------A国家、行业标准、地方标准 B 客户指定的方法C 实验室自己制定的方法 D 非标准方法实验室资质认定评审准则主要依据-------D-----------------标准制定
A ISO9001 B GB/T15481-2000 C GB/T15481-1995 D ISO/IEC17025:2005 实验室应对从事抽样、检测和/或校准、签发检测/校准报告以及操作设备等工作的人员进行-------C----------------A 培训考核
B 长期教育
C 资格确认并持证上岗
D 适当监督对文件进行控制的目的是为了------A------------A 确保文件现行有效
B 可以检索
C 方便查阅
D 接受审核 进行合同评审的时机是--------B----------A 合同签订以后
B合同签订以前
C按客户要求
D内审之前 实验室应具有检测/校准样品的-------B-----------A标识
B标识系统
C唯一性标识
D永久性标识 实验室报告和证书应当-------D-----------A 简单明确
B用中英文两种文字编写
C统一一致
D保证数据和结果准确、客观、真实 实验室所用检测/校准仪器的量值应溯源到-----A------------A 国家基准
B 当地计量部门
C
CNAS
D 国际标准化组织 实验室在以下情况时应监控、记录环境条件-------D-----------A 相关的规范、方法和程序有要求
B对结果的质量有影响
C当物品需要存放或在规定的环境条件下
D以上都需要
实验室的职责是-------D-----------
A 从事检测或校准B满足客户的需求C满足法定管理机构或认可组织的需求D以上都是
三 简答题(共40分,每题4分)实验室管理体系文件包括哪些内容?
① 质量手册② 程序文件③作业指导书④记录计划表格
纠正和纠正措施有何区别?
纠正是对已经产生的不符合的处置和补救,纠正措施是针对已经产生的不符合的根本原因,为防止类似的不符合再次发生而采取的措施。
3没有相关的技术规范或者标准时,实验室应如何制定抽样计划?
实验室应根据适当的统计方法制定抽样计划
内审员和监督员有什么区别?
① 资格不同②数量不同③任务不同④执行任务的时机不同⑤对象不通
什么情况下允许对检测/校准方法的偏离?
须有相关技术单位验证其可靠性或经有关主管部门核准后,由实验室负责人批准和客户接受,并将该方法偏离进行文件规定。
为什么记录要包含足够的信息?
保证检测(校准)工作能够再现 实验室发现所用仪器有缺陷时应采取什么措施?
应立即停止使用,并加以明显标识,如可能应将其储存在规定的地方直至修复;修复的仪器设备必须经检定、校准等方式证明其功能指标已恢复。实验室应检查这种缺陷对过去进行的检测和/或校准所造成的影响。
期间核查与校准有何不同?
①目的不同②对象不同③方法不同④结果不同 有损实验室判断独立性和检测/校准诚信度的活动可能包括哪些?
以实验室的名义①产品(工程)评优②监制、监销产品或监理工程③推荐产品④不经客户同意向媒体公布检测结果等 监控检测/校准有效性的措施可包括哪些内容?
a)定期使用有证标准物质(参考物质)进行监控和/或使用次级标准物质(参考物质)开展内部质量控制;
b)参加实验室间的比对或能力验证; c)使用相同或不同方法进行重复检测或校准; d)对存留样品进行再检测或再校准; e)分析一个样品不同特性结果的相关性。
四 场景题(共20分,每题5分)评审员发现实验室正在使用的一台仪器有某单位出具的校准证书,问仪器设备管理员该仪器是否满足使用要求?仪器设备管理员回答说有校准证书当然能行了。回答正确吗?
不符合《评审准则》第4.5条 评审员在审核时询问实验室技术主管是否实施了质量监控?实验室技术主管回答实施了,并取出质量监控的记录。评审员又问质量监控的结果如何?实验室技术主管回答:我们也不知道应如何判断结果,所以就没判断,你看我们做的还行把?。该情况是否符合评审准则规定?
不符合《评审准则》第5.7.2条 评审员在某实验室审核时发现2005内部审核只检查了7个要素。问质量主管其它要素为什么没审核?质量主管回答这7个要素对我们来说比较重要,其它要素与我们基本没有关系,所以就不用审了。这样做正确吗?
不符合《评审准则》第4.10.条 评审员在某实验室审核时发现没有2005管理评审计划,问实验室主任为什么没有?
实验室主任回答管理评审已经作了很多次了,每次讨论的内容都差不多,所以不用编计划了。回答正确吗?
不符合《评审准则》第4.11条
第四篇:GRO考核试题答案
GRO考核试题
一、填空(每空1分,共30分)
1.酒店的客房分布在3—9楼,共有14种房型,其中3楼为艺术楼层,5、6、7楼为高级楼层,8楼为绿色无烟楼层,9楼为豪华楼层,总统套房位于9楼的988。
2.酒店餐饮包括中餐厅1个,西餐厅1个,特色中餐包房(16)个,韩餐厅1个。酒店以(鲁菜)为主。宴会包房位于酒店的2楼,共有包间16个,其中6人包房(2)个,8人包房(5)个,10人包房(5)个,12人包房(3)个,16-20人包房(1)个。
3、酒店的健身房位于酒店的3楼,免费为客人提供服务,营业时间为(8:30-21:30).棋牌室也位于3层,提供24小时服务,收费标准为每小时(50)元,(500)元/天,(6小时后按全天算)
4、多功能厅衣帽间内线电话:8089,V2V3内线:8085,音控室内线:8087
5、酒店大库办公室电话:8100 电脑房:8123,前台电话(任一个)812,礼宾电话8121, 客房中心电话(任一个)8600,餐饮预订电话(任一个)8188,工程部电话8008,监控室电话8111。
二、英文翻译(每题6分 共30分)
1、请问您有预订吗?
Do you have a reservation??
2、请问您怎么来支付押金呢?
How would you like to pay your deposit?
3、我们的早餐位于酒店二楼,开餐时间是上午的6:30---9:30.Our breakfast start from 6:30 to 9:30 on the second floor
4、请稍等(打电话)。Hold on , please
5、请问有什么可以帮您?
What can I do for you?
三、简答题(每题10分,共40分)
1、酒店企业文化是什么?
我们尊重市场,尊总顾客,尊重团队,统一目标,统一追求,统一理念,用信仰武装头脑,用毅力刻画意志,用行动实践诺言。
2、如果客人在客休区抽烟,你应该如何制止?
端着烟灰缸过去礼貌的跟客人说:大堂是公共区域,这里是无烟区,是禁止吸烟的。请您谅解一下,麻烦您把烟熄灭吧。我给您倒杯热水。谢谢您的配合。谢谢。
3、简要概述一下如何介绍一个SK房间?
先生/小姐,您面前的这个衣柜是酒店专门为出差的商务人士设计的,时尚方便,顺手打开衣橱,这里面为您准备了各种材质的衣架(手势跟上),方便您晾挂不同的衣服。柜子的旁边酒店还专门为您准备了电熨斗,烫衣板,当然酒店还可以为您提供洗衣服务,这是洗衣袋和洗衣单(手势),接着下面这个是电子保险柜,您的贵重物品可以放在里面,密码您可以
自己设定,按#号开启。衣柜的旁边为您配置了酒水吧台,茶叶,咖啡等都是免费供您使用的,吧台下面的柜子中的冰箱里还为您提供了酒水,软饮,点心等,旁边的消费菜单您可以自己填写,非常方便。为了方便您的娱乐生活,您的房间接入了卫星数字电视,电视节目非常的丰富,平板的高清频显示频也非常方便您的观看(顺手打开电视),前面是酒店专门为您打造方便您使用的写字台,办公用的便筏纸,信封,笔等一应俱全,旁边还为您接入了高速的宽带插口(IP地址是自动获取的),国际国内直拨电话,为了方便你的使用,我们在您的房间里配备了三部电话,分别在写字台,床头柜,和洗手间内。在靠近床头的床头柜上酒店还为你准备了便筏,铅笔,台灯,保健用品等方便您的居住。酒店的床上用品都是按照国际四星级酒店标准配备的,非常的舒适,保证您健康的睡眠。酒店的卫生间也是聘请名师专门设计,干湿分开的,方便您的使用!尊敬的先生小姐,您的房间已经给您介绍完毕,您看还有其他需要给您介绍的吗?我是酒店的宾客关系主任某某,这是我的名片(双手递上),很高兴能为您提供服务!希望您下榻愉快!后退三步鞠躬和客人道别!
4、常用房型简称考核(请在英文简称后写下他们的汉语称谓)SK
DK
ST
DT
ES
高级大床
豪华大床
高级标准间
豪华标准间
艺术套房
AK
AES
SD
AS
AC
艺术大床房
艺术豪华套
高级单人间
艺术套房
艺术标准间
第五篇:北邮操作系统第二次实验[模版]
北京邮电大学操作系统实验实验报告
班号:2011211314姓名:oneseven学号:
实验日期: 2013.12.16 实验名称: 操作系统实验
一、实验目的
通过模拟实现内存分配的伙伴算法和请求页式存储管理的几种基本页面置换算法,了解存储技术的特点。掌握虚拟存储请求页式存储管理中几种基本页面置换算法的基本思想和实现过程,并比较它们的效率。
二、实验内容
1.实现一个内存管理的伙伴算法,实现内存块申请时的分配和释放后的回收。
实验准备
用随机函数仿真进程进行内存申请,并且以较为随机的次序进行释放。对其碎片进行统计,当申请分配内存失败时区分实际空间不足和由于碎片而不能满足。
2.设计一个虚拟存储区和内存工作区,并使用下述算法计算访问命中率。
1)最佳置换算法(Optimal)
2)先进先出法(Fisrt In First Out)
3)最近最久未使用(Least Recently Used)4)最不经常使用法(Least Frequently Used)
其中,命中率=1-页面失效次数/页地址流长度。试对上述算法的性能加以较各:页面个数和命中率间的关系;同样情况下的命中率比较。
实验准备
本实验中主要的流程:首先用srand()和rand()函数定义和产生指令序列,然后将指令序列变换成相应的页地址流,并针对不同的算法计算出相应的命中率。
实验可先从一个具体的例子出发。
(1)通过随机数产生一个指令序列,共2048条指令。指令的地址按下述原则生成: A:50%的指令是顺序执行的
B:25%的指令是均匀分布在前地址部分 C:25%的指令是均匀分布在后地址部分 具体的实施方法是:
A:在[0,1023]的指令地址之间随机选取一起点m B:顺序执行一条指令,即执行地址为m+1的指令
C:在前地址[0,m+1]中随机选取一条指令并执行,该指令的地址为m’ D:顺序执行一条指令,其地址为m’+1 E:在后地址[m’+2,2047]中随机选取一条指令并执行 F:重复步骤A-E,直到2048次指令(2)将指令序列变换为页地址流 设:页面大小为4K;
用户内存容量4页到32页; 用户虚存容量为32K。
在用户虚存中,按每K存放64条指令排列虚存地址,即2048条指令在虚存中的存放方式为:
第 0 条-第 63 条指令为第0页(对应虚存地址为[0,63])第64条-第127条指令为第1页(对应虚存地址为[64,127])
………………………………
-1- 第1984条-第2047条指令为第31页(对应虚存地址为[1984,2047])按以上方式,用户指令可组成32页。
以此为基础,给出较为一般的情形:仿真内存容量和虚存容量参数变化时的情形。
3.实现内存的slab分配器:
其基本思想是:一次向内核获取整数页,slab根据数据结构的大小进行划分为一个个小的数据结构,当需要时直接从该链表上摘取一个返回应用程序,当应用程序释放时,而非真正释放,只需要该空间放回到链表中,当分散的一页多块又聚集一页时,又会拼成一页,同时判断slab空闲的页数,如果空闲页超过一定的页数,就会向系统释放一定的页数。一个slab分配器只能管理一个指定大小的数据结构分配。
三、项目要求及分析
3.1实现一个内存管理的伙伴算法,实现内存块申请时的分配和释放后的回收。假设系统的可利用内存空间容量为2m个字(地址从0到2m-1),则在开始运行时,整个内存区是一个大小为2m的空闲块,在运行了一段时间之后,被分隔成若干占用块和空闲块。为了在分配时查找方便起见,我们将所有大小相同的空闲块建于一张子表中。每个子表是一个双重链表,这样的链表可能有m+1个,将这m+1个表头指针用向量结构组织成一个表,这就是伙伴系统中的可利用空间表,如图所示:
分配算法:
当用户提出大小为n的内存请求时,首先在可利用表上寻找结点大小与n相匹配的子表,若此子表非空,则将子表中任意一个结点分配之即可;若此子表为空,则需从结点更大的非空子表中去查找,直至找到一个空闲块,则将其中一部分分配给用户,而将剩余部分插入相应的子表中。
若2k-1 < n ≤ 2k-1,又第k+1个子表不空,则只要删除此链表中第一个结点并分配给用户即可;若 2k-2 < n ≤ 2k-1-1,此时由于结点大小为2k-1 的子表为空,则需从结点大小为2k 的子表中取出一块,将其中一半分配给用户,剩余的一半作为一个新结点插入在结点大小为2k-1的子表中,若2k-i-1 < n ≤ 2k-i-1(i为小于是的整数),并且所有结点小于2k的子表均为空,则同样需从结点大小为2k的子表中取出一块,将其中2k-i的一小部分分配给用户,剩余部分分割成若干个结点分别插入在结点大小为2k-1、2k-
2、…、2k-i的子表中。回收算法:
在用户释放不再使用的占用块时,系统需将这新的空闲块插入到可利用空间表中去。这里,同样有一个地址相邻的空闲块归并成大块的问题。但是在伙伴系统中仅考虑互为“伙伴”的两个空闲块的归并。
何谓“伙伴”?如前所述,在分配时经常需要将一个大的空闲块分裂成两个大小相等的存
-2- 储区,这两个由同一大块分裂出来的小块就称之“互为伙伴”。例如:假设p为大小为pow(2,k)的空闲块的初始地址,且p MOD pow(2,k+1)=0,则初始地址为p和p+pow(2,k)的两个空闲块互为伙伴。在伙伴系统中回收空闲块时,只当其伙伴为空闲块时才归并成大块。也就是说,若有两个空闲块,即使大小相同且地址相邻,但不是由同一大块分裂出来的,也不归并在一起。
由此,在回收空闲块时,应首先判别其伙伴是否为空闲块,若否,则只要将释放的空闲块简单插入在相应子表中即可;若是,则需在相应子表中找到其伙伴并删除之,然后再判别合并后的空闲块的伙伴是否是空闲块。依此重复,直到归并所得空闲块的伙伴不是空闲块时,再插入到相应的子表中去。
3.2.设计一个虚拟存储区和内存工作区,并使用下述算法计算访问命中率。
页式虚拟存储器实现的一个难点是设计页面调度(置换)算法,即将新页面调入内存时,如果内存中所有的物理页都已经分配出去,就要按某种策略来废弃某个页面,将其所占据的物理页释放出来,供新页面使用。页面替换算法主要用于如下几个地方:
(1)虚拟存储器中,主存页面(或程序段)的替换。
(2)Cache中的块替换。
(3)虚拟存储器的快慢表中,快表的替换。
(4)虚拟存储器中,用户基地址寄存器的替换。
在虚拟存储器中常用的页面替换算法有如下几种:
(1)最优替换算法,即OPT算法(OPTimal replacement algorithm)。上面介绍的几种页面替换算法主要是以主存储器中页面调度情况的历史信息为依据的,它假设将来主存储器中的页面调度情况与过去一段时间内主存储器中的页面调度情况是相同的。显然,这种假设不总是正确的。最好的算法应该是选择将来最久不被访问的页面作为被替换的页面,这种替换算法的命中率一定是最高的,它就是最优替换算法。
要实现OPT算法,唯一的办法是让程序先执行一遍,记录下实际的页地址流情况。根据这个页地址流才能找出当前要被替换的页面。显然,这样做是不现实的。因此,OPT算法只是一种理想化的算法,然而,它也是一种很有用的算法。实际上,经常把这种算法用来作为评价其它页面替换算法好坏的标准。在其它条件相同的情况下,哪一种页面替换算法的命中率与OPT算法最接近,那么,它就是一种比较好的页面替换算法。(2)先进先出算法,即FIFO算法(First-In First-Out algorithm)。这种算法选择最先调入主存储器的页面作为被替换的页面。它的优点是比较容易实现,能够利用主存储器中页面调度情况的历史信息,但是,没有反映程序的局部性。因为最先调入主存的页面,很可能也是经常要使用的页面。
(3)最久没有使用算法,即LRU算法(Least Recently Used algorithm)。这种算法把近期最久没有被访问过的页面作为被替换的页面。它把LFU算法中要记录数量上的“多”与“少”简化成判断“有”与“无”,因此,实现起来比较容易。
(4)近期最少使用算法,即LFU算法(Least Frequently Used algorithm)。这种算法选择近期最少访问的页面作为被替换的页面。显然,这是一种非常合理的算法,因为到目前为止最少使用的页面,很可能也是将来最少访问的页面。该算法既充分利用了主存中页面调度情况的历史信息,又正确反映了程序的局部性。但是,这种算法实现起来非常困难,它要为每个页面设置一个很长的计数器,并且要选择一个固定的时钟为每个计数器定时计数。在选择被替换页面时,要从所有计数器中找出一个计数值最大的计数器。因此,通常采用如下一种相 -3- 对比较简单的方法。
3.3实现内存的slab分配器
slab描述符和空闲对象管理部分成为 slab的管理部分,也可以称为slab头
slab的头可以放在slab自身,也可以放在 slab 之外。如果slab头放在了slab 之外,那么用户申请obj时,需要首先访问 slab头,slab头提供未使用free obj的指针
然后再访问这个free obj的地址。完成这项工作需要访问2个页块。会带来效率上的损失。slab头始终位于slab 也存在问题,比如一个页面只有4K,objsize = 2K,那么slab 头在slab 上,就意味着,这个4K的页面只能够分配一个obj。造成了内存的浪费。
如果 页数太少,存放的 obj个数少,那么 增加管理开销,同时 内存使用率低,如果页数太多对伙伴内存系统不好,所以需要一定的策略妥协。
这个妥协过程是有calculate_slab_order 这个函数来实现的。从 0阶(即一页)到kmalloc的最高阶 KMALLOC_MAX_ORDER,挨个尝试,由cache_estimate这个函数计算 如果选用order 阶,那么能分配 多少个 obj(num),剩余空间是多少(remainder)。所谓剩余空间,就是除去slab头(如果有的话),除去 obj*num,剩下的边角料空间是多少。需要分成两种情况去计算,分成两种情况的原因,很快就能看到 A)slab头不在slab上,即 flag & CFLGS_OFF_SLAB == 1的时候 这种情况比较简单,由于管理数据完全不在slab 上,size_tslab_size = PAGE_SIZE < 换句话,slab头的大小取决于obj的个数,obj的个数取决于 slab头的大小,四、具体实现 4.1实现一个内存管理的伙伴算法,实现内存块申请时的分配和释放后的回收。 程序: #include #define MIN_MOMORY_SIZE 536870912 //随机产生的最小内存空间 #define WORKTIME 1500 //系统工作时间 #define MAX_REQ_SIZE 268435456 //申请空闲内存分配的最大容量:256M #define MIN_DUE 30 //使用内存块的最短时间 #define MAX_DUE 90 //使用内存块的最长时间 #define OCCUPY_INTERVAL 60 //每次分配的最大间隔 #define USED 1 //内存块被使用 #define UNUSED 0 //内存块未被使用 //内存块链表结点结构 typedefstructbuddy_node { int flag; //标记空间是否被使用 -4- int base; //本块儿内存的基地址 int occupy; //实际使用空间大小 int fragment; //碎片大小 intduetime; //使用时间 structbuddy_node *nextPtr; //指向下一个结点 } Buddy, *BuddyPtr; IndexTable table[INDEX_SIZE];//使用哈希表管理伙伴系统 int ready = 0; //需要分配内存的时刻 intavailSpace; //可分配空间大小 inttotalFragment = 0; //总碎片大小 //函数:添加结点(形参为内存块结点的信息) void insert_node(inti, intinbase, int f, intocc, int frag, int d){ BuddyPtrnewnodePtr = NULL, prePtr = NULL, curPtr = NULL; newnodePtr =(BuddyPtr)malloc(sizeof(Buddy));//分配结点 newnodePtr->base = inbase;newnodePtr->flag = f;newnodePtr->occupy = occ;newnodePtr->fragment = frag;newnodePtr->duetime = d;newnodePtr->nextPtr = NULL; if(table[i].headPtr == NULL) table[i].headPtr = newnodePtr; else { curPtr = table[i].headPtr;prePtr = NULL; //按地址顺序插入内存块 while(curPtr&&curPtr->base } if(prePtr == NULL){ //插在最前 newnodePtr->nextPtr = curPtr; table[i].headPtr = newnodePtr; } else if(curPtr == NULL){ //插在最后 prePtr->nextPtr = newnodePtr; } else { //插在中间 prePtr->nextPtr = newnodePtr;newnodePtr->nextPtr = curPtr; -5- } } } //函数:删除结点 intdelete_node(inti, BuddyPtrdelPtr){ BuddyPtrprePtr = NULL, curPtr = NULL;intbasehold = delPtr->base; curPtr = table[i].headPtr; while(curPtr!= delPtr){ //寻找要删除的结点的位置 prePtr = curPtr;curPtr = curPtr->nextPtr; } if(prePtr == NULL) //要删除的结点在最前 table[i].headPtr = curPtr->nextPtr; else //要删除的结点不在链表的最前 prePtr->nextPtr = curPtr->nextPtr; free(curPtr); //释放结点 return basehold; //返回删除的内存块结点的基地址 } //函数:伙伴系统的分配算法 void buddy_allocate(inttime_slice){ inti, j, size, due;int state = 0; //分配状态:0为未分配,1为已分配 intinbase, basehold;BuddyPtrcurPtr = NULL; if(ready == time_slice){ //到达分配内存的时刻 printf(“Time %d:”, time_slice); size = 1 + rand()% MAX_REQ_SIZE; //申请使用内存的大小 due = MIN_DUE + rand()%(MAX_DUEsize;curPtr->duetime = due + ready; //修改可系统分配空间和碎片大小 availSpace-= table[i].nodesize;totalFragment += curPtr->fragment; state = 1;//标记已分配 break; } //空闲块的大小刚大于申请大小的2倍 else { basehold = delete_node(i, curPtr);//删除较大的空闲块并保留其基地址 inbase = basehold + table[i].nodesize; j = i; //分割空闲块 do { j--;inbase-= table[j].nodesize; //设置要添加内存块结点的基地址 insert_node(j, inbase, UNUSED, 0, 0, 0);//添加较小的空闲块 printf(“A block cut takes placen”); } while(table[j].nodesize / size > 1); //分配 insert_node(j, basehold, USED, size, table[j].nodesizesize; state = 1;//标记已分配 } } //块被占用,查看下一结点 else curPtr = curPtr->nextPtr; } } } printf(“Allocated %d,Fragment %d,Due %dn”, size, totalFragment, ready+due); -7- } else if((availSpace< size)&&((availSpace + totalFragment)>= size))printf(“Allocation failed because of fragment!n”); else printf(“Allocation failed because of no enough unused space!n”); ready +=(1 + rand()% OCCUPY_INTERVAL);//下次需要分配内存的时刻 } } //函数:伙伴系统的回收算法 void buddy_retrieve(inttime_slice){ inti, basehold, dif;int f = 0;intModnext=0;BuddyPtrcurPtr = NULL, todelPtr = NULL; //依次查找,并回收需要回收的块 for(i = 0;i< INDEX_SIZE;i ++){ if(table[i].headPtr){ curPtr = table[i].headPtr; while(curPtr){ if((curPtr->flag == USED)&&(curPtr->duetime == time_slice)){//需要回收 //修改可系统分配空间和碎片大小 availSpace += table[i].nodesize;totalFragment-= curPtr->fragment; //回收为空闲块 curPtr->flag = UNUSED;curPtr->occupy = 0;curPtr->fragment = 0;curPtr->duetime = 0;printf(“Time %d:Retrieve %d,Fragment %dn”, time_slice, table[i].nodesize, totalFragment); } curPtr = curPtr->nextPtr; } } } //合并空闲块 for(i = 0;i< INDEX_SIZE;i ++){ if(table[i].headPtr){ -8- curPtr = table[i].headPtr; while(curPtr&&curPtr->nextPtr){ //将地址连续且都为空闲的块合并后加入下一级的链表中 if(curPtr->flag == UNUSED &&(curPtr->nextPtr)->flag == UNUSED){ dif =(curPtr->nextPtr)->base-curPtr->base; Modnext =((int)(curPtr->nextPtr->base))%(2*table[i].nodesize); if((dif == table[i].nodesize)&&(Modnext==0)){ //删除两个结点 todelPtr = curPtr;curPtr = curPtr->nextPtr;basehold = delete_node(i, todelPtr);todelPtr = curPtr;curPtr = curPtr->nextPtr;delete_node(i, todelPtr);insert_node(i+1, basehold, UNUSED, 0, 0, 0);//添加合并后的结点 printf(“Two blocks mergen”); } else curPtr = curPtr->nextPtr; } else curPtr = curPtr->nextPtr; } } } } //函数:伙伴系统的处理过程 void buddy_system(void){ inttime_slice = 0; //在每个时间片内使用分配算法和回收算法 for(;time_slice< WORKTIME;time_slice ++){ buddy_allocate(time_slice); //分配算法 buddy_retrieve(time_slice); //回收算法 } } int main(intargc, char *argv[]){ intmemory_size; -9- ini_index(); //初始化哈希索引表 srand(time(NULL)); //设置随机数种子 //随机产生需要管理的内存大小:512M ~ 1G memory_size = MIN_MOMORY_SIZE + rand()% MIN_MOMORY_SIZE;printf(“The size of memory is:%dn”, memory_size); int_system(memory_size); //初始化伙伴系统 buddy_system(); //伙伴系统的处理过程 printf(“Time %d:System execution stops and the spaces are all freed.n”, WORKTIME); free_system(); //释放所有结点 system(“pause”); return 0;} 4.2.设计一个虚拟存储区和内存工作区,并使用下述算法计算访问命中率。程序: #include //虚页长 #define clear_period 50 //清零周期 typedefstruct { intpn; //页号 intpfn; // 面号 int counter; // 一个周期内访问该页面的次数 int time; // time为访问时间 }pl_type;pl_typepl[total_vp];//页面结构数组 structpfc_struct{ //页面控制结构 intpn,pfn;structpfc_struct *next;};typedefstructpfc_structpfc_type; -10- pfc_typepfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;intdiseffect,a[total_instruction];int page[total_instruction], offset[total_instruction];/* Name: void Lprintf(void) Achieve: 格式控制 */ void Lprintf(void){ inti,j;printf(“|”); for(i = 1;i<=6;i++) { for(j = 1;j<=9;j++)printf(“-”); if(i!=6)printf(“+”); } printf(“|n”); } /* Name: void initialize(inttotal_pf) Achieve:初始化相关数据结构 */ void initialize(inttotal_pf){ inti;diseffect=0; for(i=0;i { pl[i].pn=i;pl[i].pfn=INVALID; //置页面控制结构中的页号,页面为空 pl[i].counter=0;pl[i].time=-1;//页面控制结构中的访问次数为0,时间为-1 } for(i=1;i { pfc[i-1 ].next=&pfc[i];pfc[i-1].pfn=i-1;//建立pfc[i-1]和pfc[i]之间的连接 } pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1; freepf_head=&pfc[0]; //页面队列的头指针为pfc[0] } /* -11- Name:void FIFO(inttotal_pf) Achieve:先进先出法(Fisrt In First Out)*/ void FIFO(inttotal_pf){ inti,j;pfc_type *p;//中间变量 initialize(total_pf);//初始化相关页面控制用数据结构 busypf_head=busypf_tail=NULL;//忙页面队列头,队列尾链接 for(i=0;i if(pl[page[i]].pfn==INVALID) //页面失效 { diseffect+=1;//失效次数 if(freepf_head==NULL)//无空闲页面 { p=busypf_head->next; pl[busypf_head->pn].pfn=INVALID; freepf_head=busypf_head;//释放忙页面队列的第一个页面 freepf_head->next=NULL;//表明还是缺页*/ busypf_head=p; } p=freepf_head->next; freepf_head->pn=page[i]; pl[page[i]].pfn=freepf_head->pfn; freepf_head->next=NULL;//使busy的尾为null if(busypf_tail==NULL) { busypf_tail=busypf_head=freepf_head; } else { busypf_tail->next=freepf_head; busypf_tail=freepf_head; } freepf_head=p; } } printf(“%6.3f”,1-(float)diseffect/320);} /* Name: void LRU(inttotal_pf) Achieve: 最近最久未使用(Least Recently Used)*/ -12- void LRU(inttotal_pf){ intmin,minj,i,j,present_time;//minj为最小值下标 initialize(total_pf);present_time=0;for(i=0;i if(pl[page[i]].pfn==INVALID)//页面失效 { diseffect++; if(freepf_head==NULL)//无空闲页面 { min=32767;//设置最大值 for(j=0;j { if(min>pl[j].time&&pl[j].pfn!=INVALID) { min=pl[j].time; minj=j; } } freepf_head=&pfc[pl[minj].pfn]; //空出一个单元 pl[minj].pfn=INVALID; pl[minj].time=0; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效 pl[page[i]].time=present_time; freepf_head=freepf_head->next;//减少一个free 页面 } else { pl[page[i]].time=present_time;//命中则增加该单元的访问次数 present_time++; } } printf(“%6.3f”,1-(float)diseffect/320);} /* Name:void OPT(inttotal_pf) Achieve:最佳置换算法(Optimal)*/ void OPT(inttotal_pf){ -13- inti,j, max,maxpage,d,dist[total_vp];pfc_type *t;initialize(total_pf);for(i=0;i if(pl[page[i]].pfn==INVALID) /*页面失效*/ { diseffect++; if(freepf_head==NULL) /*无空闲页面*/ { for(j=0;j { if(pl[j].pfn!=INVALID) dist[j]=32767; else dist[j]=0; } for(j=0;j { if((pl[j].pfn!=INVALID)&&(dist[j]==32767)) { dist[j]=j; } } max=0; for(j=0;j if(max { max=dist[j]; maxpage=j; } freepf_head=&pfc[pl[maxpage].pfn]; freepf_head->next=NULL; pl[maxpage].pfn=INVALID; } pl[page[i]].pfn=freepf_head->pfn; freepf_head=freepf_head->next; } } printf(“%6.3f”,1-(float)diseffect/320);} /* Name: vodi LFU(inttotal_pf) Achieve:最不经常使用法(Least Frequently Used) -14- */ void LFU(inttotal_pf) { inti,j,min,minpage;pfc_type *t;initialize(total_pf);for(i=0;i if(pl[page[i]].pfn==INVALID)//页面失效 { diseffect++; if(freepf_head==NULL)//无空闲页面 { min=32767; //获取counter的使用用频率最小的内存 for(j=0;j { if(min>pl[j].counter&&pl[j].pfn!=INVALID) { min=pl[j].counter; minpage=j; } } freepf_head=&pfc[pl[minpage].pfn]; pl[minpage].pfn=INVALID; pl[minpage].counter=0; freepf_head->next=NULL; } pl[page[i]].pfn=freepf_head->pfn;//有空闲页面,改为有效 pl[page[i]].counter++; freepf_head=freepf_head->next;//减少一个free 页面 } else { pl[page[i]].counter; pl[page[i]].counter=pl[page[i]].counter+1; } } printf(“%6.3f”,1-(float)diseffect/320);} int main(int){ intS,i; -15- srand((int)getpid()); for(i=0;i { S=(int)rand()%320; a[i]=S; //任选一指令访问点 a[i+1]=a[i]+1;//顺序执行一条指令 a[i+2]=(int)rand()%a[i+1];//执行前地址指令m' a[i+3]=a[i+2]+1;//顺序执行一条指令 a[i+4]=(int)rand()%(319-a[i+2]-1)+a[i+2]+2;//执行后地址指令 } for(i=0;i { page[i]=a[i]/10; offset[i]=a[i]%10;} printf(“FrametOPTtFIFOtLRUtLFU n”);for(i=4;i<=32;i++)//用户内存工作区从4个页面到32个页面 { printf(“%dt”,i);OPT(i);printf(“t”); FIFO(i);printf(“t”); LRU(i); printf(“t”); LFU(i); printf(“n”);} system(“pause”);return 0;} 4.3 实现内存的slab分配器 程序: #include -17- } 五、调试运行结果 -18- 5.1 实现一个内存管理的伙伴算法 5.2设计一个虚拟存储区和内存工作区,并使用下述算法计算访问命中率。 -19- 5.3 实现内存的slab分配器 六、所遇问题及解决方法 1.在写第一个程序的时候,对树的合并在之前的学习中,有比较多的学习,数据结构中此程序有详细的介绍,因此在编写这个程序的时候,比较顺利的完成了要求。但要求中需要产生一些随机的数据,重新对随机仿真函数进行回顾,最后较为顺利的完成了程序。2.第二个程序,要求随机产生一些数据,对srand()和rand()函数定义和产生指令序列,在进一步的学习中,完成了这些函数,仿真内存容量和虚存容量参数变化时的情形,对此不太熟悉,四个算法对要求较高,在完成算法的学习后,完成了程序。 3.第三个程序因不太理解其要求,上网搜寻了一些代码,但对其最后的结果依然没有得出,为此询问了同学,但不知是否正确。 -20-