操作系统模拟算法实验指导..docVIP

操作系统模拟算法 实验指导 邓维 郑利华 唐建清 编 软件教研室 二○一二年四月 目 录 实验一 处理机管理 1 1.1 实验内容 1 1.2 实验目的 1 1.3 实验题目 1 1.3.1 设计一个按先来先服务调度的算法 1 1.3.2 设计一个按优先级调度的算法 2 1.3.3 设计一个按时间片轮转法调度的算法 2 1.4 按时间片轮转法进行CPU调度的实例 3 1.5 实验要求 11 实验二 死锁的避免 12 2.1 实验内容 12 2.2 实验目的 12 2.3 实验题目 12 用银行家算法和随机算法实现资源分配 12 2.4 资源分配算法的示例 16 2.5 实验要求 25 实验三 主存空间的分配与回收 26 3.1 实验内容 26 3.2 实验目的 26 3.3 实验目的 26 3.3.1 采用可变式分区管理，使用首次或最佳适应算法实现 主存的分配与回收 26 3.3.2 采用可变式分区管理，使用空闲区链实现 主存的分配与回收 29 3.3.3 采用分页管理，使用位示图实现主存的分配与回收 31 3.3.4 采用分页管理，使用主存分块表实现主存的 分配与回收算法 33 3.4程序实例 33 3.4.1 采用可变式分区管理方式，空闲区采用分区说明表时， 使用首次适应算法实现主存的分配与回收 33 3.4.2 采用存储分块表实现主存的分配与回收的示例。 39 3.5 实验要求 48 附录： 实验报告范例 49 实验一 处理机管理 1.1 实验内容 处理机管理是操作系统中非常重要的部分。为深入理解进程管理部分的功能，设计几个调度算法，模拟实现处理机的调度。 1.2 实验目的 在多道程序或多任务系统中，系统同时处于就绪态的进程有若干个。也就是说能运行的进程数远远大于处理机个数。为了使系统中的各个进程能有条不紊的运行，必须选择某种调度策略，以选择一进程占用处理机。要求学生设计一个模拟单处理机调度的方法，以巩固和加深处理机调度的概念。 1.3 实验题目 本实验有3个题目，学生可以选择其中的一题进行实验。 1.3.1 设计一个按先来先服务调度的算法 提示 （1）假设系统中有5个进程，每个进程有一个进程控制块(PCB)来标识。进程控制块内容如图1-1所示。 进程名 链接指针 到达时间 估计运行时间 进程状态 图1-1进程控制块 进程名即进程标识。 链接指针：按照进程到达系统的时间将处于就绪状态的进程连接成一个就绪队列。指针指出下一个到达进程的进程控制块首地址。最后一个进程的链接指针为NULL。 估计运行时间：可由设计者任意指定一个时间值。 到达时间：进程创建时的系统时间或由用户指定。调度时，总是选择到达时间最早的进程。 进程状态：为简单起见，这里假定进程有两种状态：就绪和完成。并假设进程一创建处于就绪状态，用R表示。 当一个进程运行结束时，就将其置成完成态，用C表示。 （2）设置一个队首指针head，用来指出最先进入系统的进程。各就绪进程通过链接指针连在一起。 （3）处理机调度时总是选择队首指针指向的进程投入运行。由于本实验是模拟实验，所以对被选中进程并不实际启动运行，而只是执行： 估计运行时间减1 用这个操作来模拟进程的一次运行，而且省去进程的现场保护和现场恢复工作。 （4）在所设计的程序中应有显示或打印的语句，能显示或打印正运行进程的进程名，已运行时间、还剩时间、就绪队列中的进程等。所以进程运行完成时，给出个进程的周转时间和平均周转时间。 实验的具体要求见本实验1.5节实验要求。 1.3.2 设计一个按优先级调度的算法 提示 进程名 链接指针 进程的优先级 估计运行时间 进程状态 图1-2 进程控制块 （1）进程控制块与1.3.1节题目的进程结构类似，具体表示如图1-2所示。其中进程的优先数由用户自己指定或程序任意设定，且优先数越低，优先级越高。调度时，总是选择优先级最高的进程运行。其他说明同1.3.1。 （2）为了调度方便，设计一个指针指向5个进程排成的就绪队列的第一个进程。另外再设一个当前运行进程指针，指向当前运行的进程。 （3）处理机调度时，总是选择队列中优先级别最高的进程运行。为了采用动态优先级调度，进程每运行一次，其优先级就减1。由于本实验是模拟实验，所以对被选中进程并不实际启动运行，而只是执行：优先数加1和估计运行时间减1，用这两个操作来模拟进程的一次运行。 （4）进程运行一次后，若剩余的运行时间不为0，且其优先级低于就绪队列的进程的优先级，则选择一个高优先级进程抢占CPU；若剩余时间为0，则把它的状态改为完成状态（C），并撤出就绪队列。 （5）若就绪队列不空，则重复上述的（3）和（4）直到进程成为完成状态。 （6）在所设计的程序中应有显示或打印语句，以显示或打印每次