[HT]实验指导书及格式.doc

HT实验指导书及格式 实验1处理器调度 一、实验内容按优先数调度算法实现处理器调度。 二、实验目的在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。 当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。 本实验模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。 三、实验原理设计一个按优先数调度算法实现处理器调度的程序。 (1)假定系统有五个进程，每一个进程用一个进程控制块PCB来代表，进程控制块的格式为进程名指针要求运行时间优先数状态其中，进程名作为进程的标识，假设五个进程的进程名分别为P1，P2，P3，P4，P5。 指针按优先数的大小把五个进程连成队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程中的指针为“0”。 要求运行时间假设进程需要运行的单位时间数。 优先数赋予进程的优先数，调度时总是选取优先数大的进程先执行。 状态可假设有两种状态，“就绪”状态和“结束”状态。 五个进程的初始状态都为“就绪”，用“R”表示，当一个进程运行结束后，它的状态为“结束”，用“E”表示。 (2)在每次运行你所设计的处理器调度程序之前，为每个进程任意确定它的“优先数”和“要求运行时间”。 (3)为了调度方便，把五个进程按给定的优先数从大到小连成队列。 用一单元指出队首进程，用指针指出队列的连接情况。 例队首标志K2K1P1K2P2K3P3K4P4K5P50K4K5K3K12312415342R R RRR PCB1PCB2PCB3PCB4PCB5 (4)处理器调度总是选队首进程运行。 采用动态改变优先数的办法，进程每运行一次优先数就减“1”。 由于本实验是模拟处理器调度，所以，对被选中的进程并不实际的启动运行，而是执行优先数-1要求运行时间-1来模拟进程的一次运行。 提醒注意的是在实际的系统中，当一个进程被选中运行时，必须恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行结束。 在这里省去了这些工作。 (5)进程运行一次后，若要求运行时间0，则再将它加入队列（按优先数大小插入，且置队首标志）；若要求运行时间=0，则把它的状态修改成“结束”（E），且退出队列。 (6)若“就绪”状态的进程队列不为空，则重复上面 （4）和 （5）的步骤，直到所有进程都成为“结束”状态。 (7)在所设计的程序中应有显示或打印语句，能显示或打印每次被选中进程的进程名以及运行一次后进程队列的变化。 (8)为五个进程任意确定一组“优先数”和“要求运行时间”，启动所设计的处理器调度程序，显示或打印逐次被选中进程的进程名以及进程控制块的动态变化过程。 四、实验报告 (1)画出算法流程图。 (2)程序中使用的数据结构及符号说明。 (3)打印一份源程序并附上注释。 (4)打印程序运行时的初值和运行结果，要求如下进程控制块的初始状态。 打印每次被选中进程的进程名以及运行一次后进程队列的变化。 实验2银行家算法的实现 一、实验内容银行家算法的实现。 二、实验目的银行家算法是一种最有代表性的避免死锁的算法。 在避免死锁方法中允许进程动态地申请资源，但系统在进行资源分配之前，应先计算此次分配资源的安全性，若分配不会导致系统进入不安全状态，则分配，否则等待。 通过编写一个模拟动态资源分配的银行家算法程序，帮助学生进一步深入理解死锁、产生死锁的必要条件、安全状态等重要概念，并掌握避免死锁的具体实施方法。 三、实验原理3. 1、银行家算法中的数据结构1）可利用资源向量Available是个含有m个元素的数组，其中的每一个元素代表一类可利用的资源数目。 如果Availablej=K，则表示系统中现有Rj类资源K个。 2）最大需求矩阵Max这是一个nm的矩阵，它定义了系统中n个进程中的每一个进程对m类资源的最大需求。 如果Maxi,j=K，则表示进程i需要Rj类资源的最大数目为K。 3）分配矩阵Allocation这也是一个nm的矩阵，它定义了系统中每一类资源当前已分配给每一进程的资源数。 如果Allocationi,j=K，则表示进程i当前已分得Rj类资源的数目为K。 4）需求矩阵Need。 这也是一个nm的矩阵，用以表示每一个进程尚需的各类资源数。 如果Needi,j=K，则表示进程i还需要Rj类资源K个，方能完成其任务。 Needi,j=Maxi,j-Allocationi,j3. 2、银行家算法设Requesti是进程Pi的请求向量，如果Requestij=K，表示进程Pi需要K个Rj类型的资源。 当Pi发出资源请求后，系统按下述步骤进行检查 (1)如果RequestijNeedi,j，便转向步骤 (2)；否则认为出错，因为它所需要的资源数已超过它所宣布最大值。 (2)如果RequestijAvailablej，便转向步骤 (3)；否则，表示尚无足够资源，Pi须等待。 (3)系统试探着把资源分配给进程Pi，并修改下面数据结构中的数值Availablej=Availablej-Requestij;Allocationi,j=Allocationi,j+Requestij;Needi,j=Needi,j-Requestij;系统执行安全性算法，检查此次资源分配后，系统是否处于安全状态。 若安全，才正式将资源分配给进程Pi，以完成本次分配；否则，将本次的试探分配作废，恢复原来的资源分配状态，让进程Pi等待。 3. 3、安全性算法1）设置两个向量工作向量Work:它表示系统可提供给进程继续运行所需的各类资源数目，它含有m个元素，在执行安全算法开始时，Work=Available;工作向量Finish:它表示系统是否有足够的资源分配给进程，使之运行完成。 开始时先做Finishi=false;当有足够资源分配给进程时，再令Finishi=true。 2）从进程集合中找到一个能满足下述条件的进程Finishi=false;Needi,jWorkj；若找到，执行 (3)，否则，执行 (4)3）当进程Pi获得资源后，可顺利执行，直至完成，并释放出分配给它的资源，故应执行Workj=Worki+Allocationi,j;Finishi=true;go tostep2;4）如果所有进程的Finishi=true都满足，则表示系统处于安全状态；否则，系统处于不安全状态 四、实验报告 (1)系统资源名称、系统资源数量、进程数量、各进程对资源的最大需求、各进程已申请到资源数等信息初始值不可以在程序中指定固定值，要在程序运行后人工输入。 (2)程序中使用的数据结构及符号说明。 (3)打印一份源程序，必须要有注释。 (4)打印程序运行过程中相关数据值。 05k10k14k26k32k512k实验3主存储器空间的分配和回收 一、实验内容主存储器空间的分配和回收。 二、实验目的一个好的计算机系统不仅要有一个足够容量的、存取速度高的、稳定可靠的主存储器，而且要能合理地分配和使用这些存储空间。 当用户提出申请存储器空间时，存储管理必须根据申请者的要求，按一定的策略分析主存空间的使用情况，找出足够的空闲区域分配给申请者。 当作业撤离或主动归还主存资源时，则存储管理要收回作业占用的主存空间或归还部分主存空间。 主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。 三、实验原理模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。 (1)可变分区方式是按作业需要的主存空间大小来分割分区的。 当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。 随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。 例如操作系统作业1作业3空闲区作业2空闲区为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下起址14K长度12K状态未分配第一栏第二栏32K96K未分配?其中，起址指出一个空闲区的主存起始地址。 长度指出从起始地址开始的一个连续空闲的长度。 状态有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区。 (2)当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。 有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分一部分分给作业占用；另一部分又成为一个较小的空闲区。 为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。 为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。 (3)采用最先适应算法（顺序分配算法）分配主存空间。 按照作业的需要量，查空闲区说明表，顺序查看登记栏，找到第一个能满足要求的空闲区。 当空闲区大于需要量时，一部分用来装入作业，另一部分仍为空闲区登记在空闲区说明表中。 由于本实验是模拟主存的分配，所以把主存区分配给作业后并不实际启动装入程序装入作业，而用输出“分配情况”来代替。 (4)当一个作业执行结束撤离时，作业所占的区域应该归还，归还的区域如果与其它空闲区相邻，则应合成一个较大的空闲区，登记在空闲区说明表中。 (5)请按最先适应算法设计主存分配和回收的程序。 假设初始时主存中没有作业，现按下面序列进行内存的申请与释放作业1申请300K，作业2申请100K，作业1释放300K，作业3申请150K，作业4申请30K，作业5申请40K，作业6申请60K，作业4释放30K。 请你为它们进行主存分配和回收，把空闲区说明表的初值以及每次分配或回收后的变化显示出来或打印出来。 四、实验报告 (1)画出最先适应分配算法流程图、归还主存时的回收算法流程图。 (2)程序中使用的数据结构及符号说明。 (3)打印一份源程序并附上注释。 (4)打印程序运行时的初值和运行结果，要求如下依次打印空闲区说明表的初始状态；打印每次作业申请或释放空间后主存分区的情况。 (5)如果在要申请一个100K的作业空间，能否满足？实验4驱动调度 一、实验内容模拟电梯调度算法，实现对磁盘的驱动调度。 二、实验目的磁盘是一种高速、大量旋转型、可直接存取的存储设备。 它作为计算机系统的辅助存储器，负担着繁重的输入输出任务，在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请示等待处理。 系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求，这就叫驱动调度，使用的算法称驱动调度算法。 驱动调度能降低为若干个输入输出请求服务所须的总时间，从而提高系统效率。 本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。 三、实验原理模拟电梯调度算法，对磁盘调度。 磁盘是要供多个进程共享的存储设备，但一个磁盘每个时刻只能为一个进程服务。 当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。 当有多个进程提出输入输出请求处于等待状态，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。 当存取臂仅需移到一个方向最远的所请求的柱面后,如果没有访问请求了,存取臂就改变方向。 假设磁盘有200个磁道，用C语言随机函数随机生成一个磁道请求序列（不少于15个）放入模拟的磁盘请求队列中，假定当前磁头在100号磁道上，并向磁道号增加的方向上移动。 请给出按电梯调度算法进行磁盘调度时满足请求的次序,并计算出它们的平均寻道长度。 四、实验报告 (1)画出算法流程图。 (2)程序中使用的数据结构及符号说明。 (3)打印一份源程序并附上注释。 (4)打印程序运行时的初值和运行结果。 操作系统实验报告实验.姓名学