用银行家算法实现资源分配课程设计.docx

实验一: 资源分配仿真(8学时)
实验内容
模拟资源分配算法,了解死锁的产生和预防方法。
实验目的
在课程已经学****了死锁的4个必要条件的基础上,为了了解系统的资源分配情况,假定系统中任一资源在每一时刻只能由一个进程使用,任何进程不能抢占其它进程正在占有的资源,当进程得不到资源时,必须等待。因此,只要资源分配策略能保证不出现循环等待,系统就不会发生死锁。
要求学生编写和调试系统动态分配资源的仿真程序,观察死锁产生的条件,再采用适当的算法,有效地防止和避免死锁发生。
实验题目
用银行家算法实现资源分配
要求:
设计3~4个并发进程共享10个同类资源的系统,各进程动态地申请和释放资源;
用银行家算法和随机分配算法分别设计资源分配程序,观察系统的运行情况;
确定一组进程依次申请的资源数序列,运行上述程序,显示各进程依次申请的资源情况。
提示:
银行家分配算法的原则是:系统掌握每个进程对资源的最大需求量,当进程要求申请资源时,系统就测试该进程还需要资源的最大量。如果系统中现存的资源数大于或等于该进程还需要的最大量时,则满足进程的当前申请。这样可以保证至少有一个进程能得到全部资源而执行到结束。然后归还它占用的全部资源,供其它进程使用。银行家算法破坏了产生死锁的环路等待条件,即不可能产生循环等待,从而可以避免死锁的发生。
把各进程需要和已占用资源的情况记录在进程控制块中。假定进程控制块PCB的格式如下:
其中,状态有:就绪、等待和完成。当进城处于等待态时,表示系统不能满足进程的当前申请。“资源需求量”表示进程在执行过程中总共要申请的资源量。“已占资源量”表示进程目前已经得到但还未归还的资源量。因此,进程在以后还需要的剩余资源量等于资源需要总量减去已占资源量。显然每个进程的资源需求总量不应超过系统拥有的资源总量。
由于银行家算法可以避免死锁,为了观察死锁现象的发生,要求采用两个算法:银行家算法和随机算法。随机算法的分配原则是:当进程申请资源时,如果系统现存资源数能够满足进程当前申请量,就把资源分配给进程;否则,让其等待。这样,随机算法可能引起死锁。
资源分配仿真程序的总流程见图1:
随机分配算法流程图见图2:
银行家算法流程如图3:
实验报告:
1、程序中使用数据结构和符号说明;
2、给出程序流程;
3、显示程序运行的初始状态和运行结果;
4、附程序实现的核心代码(编程语言不限);
5、收获体会及改进意见。
实验二: 可变分区主存空间的分配与回收仿真(8学时)
实验内容
仿真可变分区主存空间的分配与回收
实验目的
主存中央处理机能直接存取指令和数据的存储器。能否合理而有效地使用它,在很大程度上将影响整个计算机系统的性能。本实验主要让大家熟悉主存的分配与回收。所谓分配,就是解决多道作业如何共享主存空间的问题;当作业运行完成时,如何回收作业所占的主存空间。主存的分配与回收的实现是与主存储器的管理方式相关的。通过本实验,帮助学生理解在不同的存储管理方式下如何实现主存空间的分配与回收。
实验题目
采用可变式分区管理时,采用首次或最佳适应算法实现主存的分配与回收。
提示:
可变式分区管理是指在处理进程的过程中建立分区,使分区大小正好适合作业的需要,并且分区的个数是可以调整的。当要装入一个进程时,根据进程需要的主存量,查看是否有足够的空闲空间,若有,则按需求量分割一部分给进程;若无,则进行“紧凑”;否则,作业等待。随着进程的装入、完成,主存空间被分割成许多大大小小的分区,有的分区被进程占用,有的分区空闲。
为了说明哪些分区是空闲,可以装入新进程,必须有一张空闲区说
明表或者空白存储块链(+2)
其中:起始地址指出空闲区的主存起始地址
长度指出空闲区大小
状态:未分配——该栏目是有效空闲区
空表目——没有登记信息
由于分区个数补丁,所以空闲区说明表中应有足够的空表目项。否则造成溢出,无法登记。
当有一个新进程要求装入主存时,必须查空闲区说明表,从中找出一个足够大的空闲区。有时找到的空闲区可能大于作业的需求量,这时应该将空闲区一分为二。一个分给进程,另一个仍作为空闲区留在空闲区表中。为了尽量减少由于分割造成的碎片,尽可能分配低地址部分的空闲区,将较大空闲区留在高地址端,以利于大作业的装入。为此在空闲区表中,按空闲区地址从高到低登记。为了方便查找,要不断调整表格,让“空表目”栏目留在表的后部。
当一个进程执行完成时,进程所占用的分区应该归还给系统。在归还时要考虑相邻空闲区合并的问题(使用边界标识法+2)。

请按首次或最佳适应算法设计主存的分配和回收程序,以提示1中给出的分区说明表作为当前主存的初始值。学生自己仿真一个进程的申请队列及进程