基于 Java 实现银行家算法【100011124】

# 实现银行家算法 ## 摘 要 操作系统实验的实验目的是为了了解处理器调度，存储空间的分配与回收，进程与程序的区别以及死锁的避免。 实验内容主要包括： 选择一个调度算法，实现处理器调度。 主存储器空间的分配和回收。 模拟磁盘空闲空间的表示方法，以及模拟实现磁盘空间的分配和回收。 利用 fork()系统调用创建进程。 ## 实验目的和意义 ### 实验目的 本实验分为五个小实验，实验一的目的是模拟在单处理器环境下的处理器调度，加深了解处理器调度的工作。实验二的目的是理解在不同的存储管理方式下应怎样进行存储空间的分配和回收。实验三的目的是掌握磁盘存储空间的分配和回收算法。实验四的目的是了解进程的创建过程，进一步理解进程的概念，明确进程和程序的区别。实验五的目的是了解死锁的避免，掌握银行家算法。 ### 实验意义 通过完成本实验，深入了解操作系统的处理器调度，存储调度，进程线程调度，从而了解操作系统对各类资源的分配方式以及是如何利用各类算法提高系统对资源的利用率。 本实验有两个选题，我选择了第一题：设计一个按优先数调度算法实现处理器调度的程序。 实验原理 每个进程用一个 PCB 来代表，PCB 有进程名；要求运行时间：假设进程需要运行的单位时间数；优先数：赋予进程的优先数，调度时总是选取优先数大的进程先执行；状态：就绪和结束，用 R 表示就绪，用 E 表示结束。初始状态都为就绪状态。 实验方案 采用 Java 来完成本实验，设计了四个类分别为 Service, Main, PCB 及 PCBCreator. Main 类为输入输出相关的类。PCB 类定义了每个进程的数据结构，包含进程名，要求运行时间，优先级及状态，并且包含一个将进程信息打印出来的方法。PCBCreator 类是用来创建 PCB 对象的类。 Service 类包含一个用来表示就绪队列的存储 PCB 对象的链表，包含一个进程运行的方法，每次运行将就绪队列的第一个进程的优先级和要求运行时间减 1，再判断该进程的要求运行时间是否为 0，为零则从就绪队列删除。运行一次后调用排序方法根据优先级进行排序。 结果 随机使用一组数据进行测试，创建了如图 2.3.1 的进程，运行结果如图 2.3.2。 进程运行时是遵循优先级高的先运行。可以看出，实验代码完成了要求。  图 2.3.1  图 2.3.2 ## 概述 本实验有两个选题，我选择了第一题：可变分区管理方式下采用首次适应算法实现主存分配和回收。 ### 实验原理 按作业需要的主存空间大小来分割分区的。当要装入一个作业时，根据作业需要的主存容量查看是否有足够的空闲空间，若有，则按需分配，否则，作业无法装入。 空闲分区说明表格式：分区号——表示是第几个空闲分区；起始地址——指出空闲区的起始地址；长度——一个连续空闲区的长度。 采用首次适应算法分配回收内存。 ### 实验方案 采用 Java 来完成本实验，设计了三个类分别为 Memory, Main 及 Partition. Main 类为输入输出相关的类。Partition 类定义了每个分区的数据结构，包含分区起始地址，分区长度以及分区状态。 Memory 类包含两个链表，分别用来存放已使用的分区和空闲分区，包含申请，回收，显示内存状态，以及另外三个辅助的方法。申请方法从空闲分区的链表中遍历，第一个分区长度大于申请长度的用于分配主存，分配时新建一个 Partition 对象，将原空闲分区的起始地址及长度修改继续作空闲分区，新对象作为被分配的空间加入已分配空间的链表。加入后再调用排序方法，按照起始地址的顺序进行排序。 回收方法将要回收的 Partition 对象的状态修改修改为未分配，再从已分配链表里移除，加入空闲分区链表。再调用排序方法，按照起始地址的顺序进行排序。最后调用空闲分区拼接方法，将相邻的空间分区拼接。 ### 结果 随机使用一组数据进行测试，运行结果如图 3.3。 申请，回收都能正常进行，特殊情况需要拼接的也能正常完成。可以看出，代码完成了实验要求。  图 3.3 ## 概述 本实验有三个选题，我选择了第二题：用位示图管理磁盘存储空间。 ### 实验原理 为了提高磁盘存储空间的利用率，可在磁盘上组织成链接文件、索引文件，这类文件可以把逻辑记录存放在不连续的存储空间。为了表示哪些磁盘空间已被占用，哪些磁盘空间是空闲的，可用位示图来指出。位示图由若干字节构成，每一位与磁盘上的一块对应，“1”状态表示相应块已占用，“0”状态表示该块为空闲。 申请一块磁盘空间时，由分配程序查位示图，找出一个为“0”的位，计算出这一位对应块的磁盘物理地址，且把该位置成占用状态“1”。假设现在有一个盘组共 8 个柱面，每个柱面有 2 个磁道（盘面），每个磁道分成 4 个物理记录。那么，当在位示图中找到某一字节的某一位为“0”时，这个空闲块对应的磁盘物理地址为：柱面号=字节号 磁道号= 位数 / 4 物理记录号= 位数 % 4 归还一块磁盘空间时，由回收程序根据归还的磁盘物理地址计算出归还块在位示图中的对应位，把该位置成“0”。按照（2）中假设的盘组，归还块在位示图中的位置计算如下：字节号=柱面号 位数=磁道号 4+ 物理记录号 ### 实验方案 采用 Java 来完成本实验，设计了三个类分别为 Map, Main 及 Service. Main 类为输入输出相关的类。Map 类定义了位视图的数据结构，包含总字节数，总位数以及用来表示位示图的二维数组。 Service 类包含显示位示图，申请，回收三个方法，申请时遍历位示图，计算剩余空间，如果满足条件，可分配；同时利用公式将物理地址计算处理出来，将分配的空间对应的物理地址打印出来。 回收方法利用公式计算出在位示图中的坐标，将该位置 0。 ### 结果 随机使用一组数据进行测试，运行结果如图 4.3.1 及 4.3.2。 申请，回收都能正常操作，可见代码完成了实验要求。   图 4.3.1  图 4.3.2 ## 概述 利用 fork()系统调用创建进程。 ### 实验原理 可用 fork()系统调用来创建一个新进程。 系统调用格式：pid=fork() fork()返回值意义如下： =0：若返回值为 0，表示当前进程是子进程。 0：若返回值大于0，表示当前进程是父进程，返回值为子进程的pid值。 -1：若返回值小于 0，表示进程创建失败。 如果 fork()调用成功，它向父进程返回子进程的 pid，并向子进程返回 0，即 fork()被调用了一次，但返回了两次。此时 OS 在内存中建立�