实现模拟进程调度的算法时间片轮转及短进程优先

操作系统课程设计报告时间：2011-12-262012-1-6地点：信息技术实验中心计算机科学与技术或软件工程专业xxx级xxx班xx号xxxxxxxx目录一 课程设计的目的和意义二 进程调度算法模拟1 设计目的2 设计要求3 时间片轮转算法模拟4 先来先效劳算法模拟三 主存空间的回收与分配1 设计目的2 设计要求3 模拟算法的实现四 模拟DOS文件的建立和使用1 设计目的2 设计要求3 模拟算法的实现五 磁盘调度1 设计目的2 设计要求3 模拟算法的实现六 总结一、课程设计的目的和意义本次操作系统课程设计的主要任务是进行系统级的程序设计。本课程设计是操作系统原理课程的延伸。通过该课程设计，使学生更好地掌握操作系统各局部结构、实现机理和各种典型算法，加深对操作系统的设计和实现思路的理解，培养学生的系统设计和动手能力，学会分析和编写程序。课程设计的实施将使学生在以下几个方面有所收获：1加深对操作系统原理的理解，提高综合运用所学知识的能力；2培养学生自主查阅参考资料的习惯，增强独立思考和解决问题的能力；3通过课程设计，培养严谨的科学态度和协作精神。二、进程调度算法模拟1、设计目的1要求学生设计并实现模拟进程调度的算法：时间片轮转及短进程优先。2理解进程控制块的结构。3理解进程运行的并发性。4掌握进程调度算法。2、设计要求在多道程序运行环境下，进程数目一般多于处理机数目，使得进程要通过竞争来使用处理机。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之运行，分配处理机的任务是由进程调度程序完成的。一个进程被创立后，系统为了便于对进程进行管理，将系统中的所有进程按其状态，将其组织成不同的进程队列。于是系统中有运行进程队列、就绪队列和各种事件的进程等待队列。进程调度的功能就是从就绪队列中挑选一个进程到处理机上运行。进程调度的算法有多种，常用的有优先级调度算法、先来先效劳算法、时间片轮转算法。3、时间片轮转算法模拟1时间片算法概述时间片轮转调度是一种最古老，最简单，最公平且使用最广的算法。每个进程被分配一个时间段，称作它的时间片，即该进程允许运行的时间。如果在时间片结束时进程还在运行，那么CPU将被剥夺并分配给另一个进程。如果进程在时间片结束前阻塞或结束，那么CPU当即进行切换。调度程序所要做的就是维护一张就绪进程列表，当进程用完它的时间片后，它被移到队列的末尾。2时间片算法流程图图1-1 时间片算法流程图3时间片算法模拟设计要求 进程的调度采用时间片轮转算法。 设计三个链队列，分别用来表示运行队列、就绪队列和完成队列。 用户输入进程标识符以及进程所需的时间申请空间存放进程 PCB信息。 输出的格式和上面的运行结果分析中的格式相同。时间片轮转调度，具体做法是调度程序每次把 CPU 分配给就绪队列首进程使用一个时间片。当这个时间片结束时，就强迫一个进程让出处理器，让它排列到就绪队列的尾部，等候下一轮调度。实现这种调度要使用一个间隔时钟。当一个进程开始运行时，就将时间片的值置入间隔时钟内，当发生间隔时钟中断时，就说明该进程连续运行的时间已超过一个规定的时间片。此时，中断处理程序就通知处理器调度进行处理器的切换工作。4算法模拟程序的关键代码while (!threads.isEmpty() if (threads.get(0).getPCB().getTimed() = threads.get(0).getPCB().getTimePian() threads.get(0).run();finished.add(threads.get(0);threads.remove(0);else threads.get(0).run();MyThread thread = threads.get(0);threads.remove(0);threads.add(thread);public void run() System.out.println(执行的进程是：);if (this.getPCB().getTimed() = this.getPCB().getTimePian()System.out.println(进程名= + this.getPCB().getPName() + ，剩余执行时间=0);this.getPCB().setTimed(0);else System.out.println(进程名= + this.getPCB().getPName() + ，剩余执行时间= + (this.getPCB().getTimed()-this.getPCB().getTimePian();System.out.println(已经运行了一个时间片);this.getPCB().setTimed(this.getPCB().getTimed() - this.getPCB().getTimePian();System.out.println(*); 4、先来先效劳算法模拟1先来先效劳算法概述2先来先效劳算法流程图3先来先效劳算法模拟程序关键代码4程序运行结果图三、主存空间的分配与回收1、设计目的 主存是中央处理器能直接存取指令和数据的存储器，能否合理地利用主存，在很大程度上将影响到整个计算机系统的性能。主存分配是指在多道作业和多进程环境下，如何共享主存空间。主存回收是指当作业执行完毕或进程运行结束后将主存空间归还给系统。主存分配与回收的实现是与主存储器的管理方式有关。本次设计主要是为了帮助学生深入理解主存空间的分配与回收的几种算法。1掌握最先适应分配算法2掌握循环首次适应分配算法3掌握最坏适应分配算法2、设计要求用户提出内存空间请求，系统根据申请者要求，按照最先适应分配算法的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者，当程序执行完毕时，系统要收回它所占用的内存空间。建立空闲数据文件，空闲区数据文件包括假设干行，每行有两个字段：起始地址、内存块大小均为整数，各字段以逗号隔开。下面是一个空闲区数据文件的例如：0，10 10，08 18，10 28，06 34，10 44，09 读取空闲区数据文件，建立空闲区表并在屏幕上显示空闲内存状态，空闲区表记录了可供分配的空闲内存的起始地址和大小，用标志位指出该分区是否是未分配的空闲区。接收用户的内存申请，格式为：作业名、申请空间的大小。按照内存分配算法中的一种方法选择一个空闲区，分割并分配，修改空闲区表，填写内存已分配区表起始地址、长度、标志位，其中标志位的一个作用是指出该区域分配给哪个作业。进程结束后回收内存。空闲区表的结构如下：typedef struct node int start; int length; char tag20; job; 本次设计要求完成如下算法：1设计一个内存分配回收的程序使用最先适应分配算法2设计一个内存分配回收的程序使用循环首次适应分配算法3设计一个内存分配回收的程序使用最坏适应分配算法用户提出内存空间请求，系统根据申请者要求，选择上述算法的一种分配策略分析内存空间的使用情况，找出适宜的空闲区，分给申请者，当进程执行完毕时，系统收回它所占用的内存空间。3、模拟算法的实现3.1最先适应分配算法1算法概述最先适应分配算法是指从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表空闲区链中的空闲分区要按大小从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保存大的空闲区，但造成许多小的空闲区2算法流程图3算法模拟程序关键代码4程序运行结果3.2循环首次适应分配算法1算法概述该算法是首次适应算法的变种。在分配内存空间时，不再每次从表头链首开始查找，而是从上次找到空闲区的下一个空闲开始查找，直到找到第一个能满足要求的的空闲区为止，并从中划出一块与请求大小相等的内存空间分配给作业。该算法能使内存中的空闲区分布得较均匀2算法流程图3算法模拟程序关键代码4程序运行结果3.3最坏适应分配算法1算法概述最坏适应分配算法要扫描整个空闲分区或链表，总是挑选一个最大的空闲分区分割给作业使用。该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，查找时只要看第一个分区能否满足作业要求。 优点：可使剩下的空闲分区不至于太小，产生碎片的几率最小，对中、小作业有利，同时该算法查找效率很高。 缺点：会使存储器中缺乏大的空闲分区。 最坏适应算法与首次适应算法、循环首次适应算法、最正确适应算法一起，也称为顺序搜索法。2算法流程图3算法模拟程序关键代码4程序运行结果四、模拟DOS文件的建立和使用1、设计目的磁盘文件是磁盘上存储的重要信息，通过本实验模拟DOS文件的建立和使用情况，理解磁盘文件的物理结构。文件管理是操作系统中重要的内容之一，不同的文件系统提供了不同的物理结构，通过实验，深入理解文件的物理结构与存取方法之间的关系，以便更好的掌握文件系统的概念。2、设计要求1拟设计DOS操作系统中磁盘文件的存储结构DOS操作系统对磁盘文件的管理采用链接结构，将所有的链接指针集中在一起，存放在文件分配表FAT中。连接文件的第一个物理块号登记在文件目录中。其设计思想是：假定磁盘上共有N个物理块可供使用，当要存放文件时，从FAT表中寻找其值为0的项，用其对应的物理块存放文件信息，并把文件占有的各物理块用链接指针登记在FAT表中，再把文件的第一个物理块号登记在文件目录中。文件目录及FAT表如下图: 在DOS中FAT表的前两项用来记录磁盘的类型。而从第2项开始记录磁盘的分配情况和文件各物理块的链接情况。在FAT表中第三项的值如果为0，表示对应的第三块空闲。由图还知道文件A的各记录依次存放在第2、第4、第15、第16、第50等六个物理块中。第50块中的指针为FFF，表示文件A的结束。文件B的各记录依次存放在第7、第10、第20等三个物理块中。第20块中的指针为FFF。假定磁盘存储空间共有100个物理块，设计一个文件分配表。为了简单，文件分配表可用一个数组定义，其中每一个元素与一个物理块对应。当第 i 个元素为 0 时，表示第 i 块空闲；当第 i 个元素既不为 0 也不为 FFF 时，其值表示该文件的下一个物理块号。另外，再设一个空闲块总数变量记录系统还有的空闲块数。为了简单，假定一个物理块指存放一个逻辑记录，要求设计一个程序，把文件的逻辑记录结构转换成 DOS 的链接结构。当用户要求将已在主存的文件保存在磁盘上时，给出文件名及文件的记录个数，系统应能在磁盘上正确地保存文件。或当用户要求给指定文件增加记录时，也应正确的实现，并插在指定记录之后。为了正确地执行模拟程序，可用键盘模拟输入用户的要求。输入格式为：write(文件名，记录个数) 或insert(文件名，逻辑记录号) 2拟设计便于直接存取的索引文件结构为了便于用户直接存取文件的各个逻辑记录，在 MS-DOS 中通过文件目录，再沿着链查找FAT表，便可直接找到指定逻辑记录对应的物理块。在小型机或更高级的文件系统中，直接存取文件的方法是为每个文件建立一个索引表，指出各逻辑记录与物理块的对应关系。最简单的形式是一个逻辑记录对应一个物理块。文件目录与索引表的关系如下图。通常索引表按照逻辑记录顺序建立，这样既有利于顺序存储，又有利于直接存储。为了标识哪些记录已经建立，哪些记录还没建立，故在索引表中增设一个标志位。写文件或插入一个记录的过程是寻找一个空闲物理块，然后将其填入索引表对应项中。其建立过程同第一题，即 write文件名，记录号和 insert文件名，记录号。要求用位示图描绘出磁盘的使用情况，并要求模拟程序执行过程的每一步都能显示文件目录、位示图、索引表。3.模拟算法的实现1算法流程图2算法模拟程序关键代码3程序运行结果五、磁盘调度1、设计目的1要求学生设计一个模拟磁盘调度的程序2理解磁盘调度过程中的三个时间段3理解磁盘调度的三种算法2、实验原理共享设备的典型代表为磁盘，磁盘的物理块的地址由柱面号、磁道号、扇区号来指定，完成磁盘某一个物理块的访问要经过三个阶段：寻道时间Ts、旋转延迟 Tw 和读写时间 Trw。寻道时间 Ts 是磁头从当前磁道移动到目标磁道所需要的时间；旋转延迟 Tw 是当磁头停留在目标磁道后，目标物理块从当前位置旋转到磁头位置的时间；读写时间 Trw 是目标物理块内容与内存中对应交换的时间。磁盘调度的原那么是公平和高吞吐量，衡量指标有访问时间 T 和平均访问时间 Ta：T=Ts+Tw+Trw Ta=Tsa+Twa+Trwa 寻道时间和旋转延迟成为调度算法的主要考虑因素。减少访问时间就是要减少寻道时间和旋转延迟。3、设计要求1设计并实现一个函数，完成先来先效劳的磁盘调度功能2设计并实现一个函数完成最短寻道时间优先的磁盘调度功能。3设计并实现一个函数完成CSCAN的磁盘调度功能。4、算法模拟4.1 先来先效劳算法1算法概述最简单的移臂调度算法是“先来先效劳调度算法，这个算法实际上不考虑访问者要求访问的物理位置，而只是考虑访问者提出访问请求的先后次序。采用先来先效劳算法决定等待访问者执行输入输出操作的次序时，移动臂来回地移动。先来先效劳算法花费的寻找时间较长，所以执行输入输出操作的总时间也很长。2算法流程图图3模拟程序关键代码public void fcfs(List list,int num,String name) int distance = 0; int danqian = num; for(int i=0;i=list.get(i) distance = distance+danqian-list.get(i); danqian = list.get(i); else distance = distance+list.get(i)-danqian; danqian = list.get(i); System.out.println(name+算法访问磁道序列为：); for(int j=0;jlist.size();j+) System.out.print(list.get(j)+ ); double dis = (double)distance; double averige = dis/list.size(); System.out.println(); System.out.println(总寻道长度为：+distance); System.out.println(平均寻道长度为：+averige); System.out.println(*);4模拟程序运行结果图4.2 最短寻道时间优先算法1算法概述最短寻找时间优先调度算法总是从等待访问者中挑选寻找时间最短的那个请求先执行的，而不管访问者到来的先后次序。采用最短寻找时间优先算法决定等待访问者执行操作的次序时，与先来先效劳、算法比拟，大幅度地减少了寻找时间，因而缩短了为各访问者请求效劳的平均时间，也就提高了系统效率。但最短查找时间优先SSTF调度，FCFS会引起读写头在盘面上的大范围移动，SSTF查找距离磁头最短也就是查找时间最短的请求作为下一次效劳的对象。SSTF查找模式有高度局部化的倾向，会推迟一些请求的效劳，甚至引起无限拖延又称饥饿。2算法流程图图3模拟程序关键代码public void sstf(List list,int num) int x = num; List sort = new ArrayList(); while(!list.isEmpty() int sign = 0; int cidao = list.get(0); int cha = Math.abs(num-list.get(0); for(int i=0;ilist.size();i+) if(Math.abs(num-list.get(i)=cha) cidao = list.get(i); sign = i; cha = Math.abs(num-list.get(i); sort.add(cidao); num = cidao; list.remove(sign); this.fcfs(sort, x,最短寻道时间优先);4模拟程序运行结果图4.3 循环扫描算法1算法概述循环扫描算法是对扫描算法的改良。如果对磁道的访问请求是均匀分布的，当磁头到达磁盘的一端，并反向运动时落在磁头之后的访问请求相对较少。这是由于这些磁道刚被处理，而磁盘另一端的请求密度相当高，且这些访问请求等待的时间较长，为了解决这种情况，循环扫描算法规定磁头单向移动。例如，只自里向外移动，当磁头移到最外的被访问磁道时，磁头立即返回到最里的欲访磁道，即将最小磁道号紧接着最大磁道号构成循环，进行扫描。2算法流程图图3模拟程序关键代码public void cscan(List list,int num) List intoout = new ArrayList();List outtoin = new ArrayList();for(int j=0;jlist.size();j+) for(int i=0;ilist.get(i+1) int temp = list.get(i);list.set(i, list.get(i+1);list.set(i+1, temp);for(int i=0;i=num) intoout.add(list.get(i);for(int i=0;ilist.size();i+) if(list.get(i)=0;i-) if(list.get(i)=0;i-) if(list.get(i)num) outtoin.add(list.get(i);this.fcfs(intoout, num,循环扫描(由内到外);this.fcfs(outtoin, num,循环扫描(由外到内);4模拟程序运行结果图