操作系统课程设计报告-基于时间片的轮转调度算法

PAGE58淮阴工学院操作系统课程设计报告选题名称:基于时间片的高优先级调度模拟实现系（院）: 经济管理学院 专业: 信息管理与信息系统 班级:信管1091姓名:赵洁学号：1091807127姓名:杨娟学号：1091807123姓名:俞庆燕学号：1091807124姓名:方晨学号：1091807105指导教师:陈礼青邱军林学年学期: 2011~2012 学年第一学期 2012 年1 月设计任务书课题名称基于时间片的高优先级调度模拟实现设计目的理解进程调度相关理论。掌握时间片调度原理。掌握高优先级调度原理。实验环境硬件：PC机，奔腾IV以上CPU，512MB以上内存，80G以上硬盘。软件：Windows2000/XP、MicrosoftVisualC++6.0。任务要求搜集基于时间片的高优先级调度模拟实现可能涉及到的知识和相关资料。应用MicrosoftVisualC++6.0集成开发环境，设计并实现一个基于时间片的高优先级调度模拟程序。确保基于时间片的高优先级调度模拟程序能正确运行。参加答辩，撰写课程设计报告。工作进度计划序号起止日期工作内容12012.1.1课题任务下达，查阅文献资料22012.1.2～2012.1.3课题总体设计、素材搜集与处理32012.1.4～2012.1.7课题详细设计、调试、完善设计42012.1.8答辩，撰写报告指导教师（签章）：年月日摘要操作系统（OperatingSystem，简称OS）是计算机系统的重要组成部分，是一个重要的系统软件，它负责管理计算机系统的硬、软件资源和整个计算机的工作流程，协调系统部件之间,系统与用户之间、用户与用户之间的关系。随着操作系统的新技术的不断出现功能不断增加。操作系统作为一个标准的套装软件必须满足尽可能多用户的需要，于是系统不断膨胀，功能不断增加，并逐渐形成从开发工具到系统工具再到应用软件的一个平台环境。更能满足用户的需求。随着计算机技术的不断发展，人们对于计算机系统性能的要求也越来越高，对于操作系统所使用的算法也在不断地发展。OS对调度分配实质是一种资源分配，因而调度算法要根据不同的系统资源分配策略所规定的来分配算法。对于不同的系统目标，又必须采用不同的调度算法。有的算法适合长作业，有的适合短作业，有的适合作业调度，有的适合进程调度。本课程设计所讨论的基于优先级的时间片调度算法是在诸多的调度算法中具有明显有点的调度算法。该算法涉及到高优先级调度算法、时间片轮转算法、多级反馈队列调度算法。本课题基于MicrosoftVisualC++6.0平台，对算法作出具体的解释。关键词：操作系统，调度算法，优先级，时间片目录43301引言 5TOC\o"1-2"\h\z\u233811.1课题设计背景 5251641.2目的和意义 6173161.3调度算法发展过程 6234061.4使用的到的开发工具 9284302需求分析 11143102.1需求背景 11215412.2课程设计任务 14218222.3课程设计要求 15250582.4课程设计思想 1561043概要设计 16325763.1课程设计所用方法及其原理 1657283.2主要的数据结构 17280113.3课题设计的流程图 18178424详细设计 19196024.1设计进程控制块 19207424.2进程调度 21245444.3优先级 22267194.3.1优先级简介 22211654.3.2优先权调度算法的类型 22244644.4时间片轮转算法 2640824.5多级反馈队列调度算法 2926485调试与操作说明 3416545.1调试过程中遇到的问题及解决方案 34262065.2测试结果 3718259总结 4118259致谢 4318259参考文献 4418259附录 451引言1.1课题设计背景计算机自从1946年第一台真正意义上的数字电子计算机ENIAC(ElectronicNumericalIntegratorAndComputer)的诞生以来，已经经历了1854年－1890年、1890年－20世纪早期、20世纪中期、20世纪晚期－现在四个阶段，每一个阶段的发展都发生了质与量的突飞猛进。然而，计算机的发展只是代表了硬件的提升，对于软件，操作系统的发展更加引人注目。操作系统（OperatingSystem，简称OS）是管理电脑硬件与软件资源的程序，同时也是计算机系统的内核与基石。操作系统是控制其他程序运行，管理系统资源并为用户提供操作界面的系统软件的集合。操作系统身负诸如管理与配置内存、决定系统资源供需的优先次序、控制输入与输出设备、操作网络与管理文件系统等基本事务。操作系统的型态非常多样，不同机器安装的OS可从简单到复杂，可从手机的嵌入式系统到超级电脑的大型操作系统。目前微机上常见的操作系统有DOS、OS/2、UNIX、XENIX、LINUX、Windows、Netware等。操作系统的不断提升对于计算机整体性能的提高有着至关重要的作用。操作系统对于各个方面的要求都不得不提到效率的问题，计算机系统的处理机调度便变得尤为重要。处理机调度的效率甚至可能成为提高计算机处理速度的瓶颈。处理机调度就是对系统的资源做出合理的分配，因而，提高处理机的调度算法也变得尤为重要。1.2目的和意义在多道程序设计系统中，内存中有多道程序运行，他们相互争夺处理机这一重要的资源。处理机调度就是从就绪队列中，按照一定的算法选择一个进程并将处理机分配给它运行，以实现进程并发地执行。一般情况下，当占用处理机的进程因为某种请求得不到满足而不得不放弃CPU进入等待状态时，或者当时间片到，系统不得不将CPU分配给就绪队列中另一进程的时候，都要引起处理机调度。除此之外，进程正常结束、中断处理等也可能引起处理机的调度。因此，处理机调度是操作系统核心的重要组成部分，它的主要功能如下：记住进程的状态，如进程名称、指令计数器、程序状态寄存器以及所有通用寄存器等现场信息，将这些信息记录在相应的进程控制块中；根据一定的算法，决定哪个进程能获得处理机，以及占用多长时间；收回处理机，即正在执行的进程因为时间片用完或因为某种原因不能再执行的时候，保存该进程的现场，并收回处理机。1.3调度算法发展过程调度算法[1]是根据系统的资源分配策略所规定的资源分配算法。对于不同的的系统和系统目标，通常采用不同的调度算法，例如，在批处理系统中，为了照顾为数众多的段作业，应采用短作业优先的调度算法；又如在分时系统中，为了保证系统具有合理的响应时间，应当采用轮转法进行调度。目前存在的多种调度算法中，有的算法适用于作业调度，有的算法适用于进程调度；但也有些调度算法既可以用于作业调度，也可以用于进程调度。各种调度算法都有其具有的优点和缺点。因此，在这里便要对一种结合了多种算法的具有极强的适应性的调度算法—基于优先级的时间片调度算法作研究。1）FCFS（Firstcomefirstserve)，或者称为FIFO算法，先来先处理。这个算法的优点是简单，实现容易，并且似乎公平；缺点在于短的任务有可能变的非常慢，因为其前面的任务占用很长时间，造成了平均响应时间非常慢。

2）时间片轮询算法，这是对FIFO算法的改进，目的是改善短程序（运行时间短）的响应时间，其方法就是周期性地进行进程切换。这个算法的关键点在于时间片的选择，时间片过大，那么轮转就越接近FIFO，如果太小，进程切换的开销大于执行程序的开销，从而降低了系统效率。因此选择合适的时间片就非常重要。选择时间片的两个需要考虑的因素：一次进程切换所使用的系统消耗以及我们能接受的整个系统消耗、系统运行的进程数。时间片轮询看上起非常公平，并且响应时间非常好，然而时间片轮转并不能保证系统的响应时间总是比FIFO短，这很大程度上取决于时间片大小的选择，以及这个大小与进程运行时间的相互关系。

3）STCF算法（Shorttimetocompletefirst)，顾名思义就是短任务优先算法。这种算法的核心就是所有的程序都有一个优先级，短任务的优先级比长任务的高，而OS总是安排优先级高的进程运行。STCF又分为两类：非抢占式和抢占式。非抢占式STCF就是让已经在CPU上运行的程序执行到结束或者阻塞，然后在所有的就绪进程中选择执行时间最短的来执行；而抢占式STCF就不是这样，在每进来一个新的进程时，就对所有进程（包括正在CPU上执行的进程）进行检查，谁的执行时间短，就运行谁。STCF总是能提供最优的响应时间，然而它也有缺点，第一可能造成长任务的程序无法得到CPU时间而饥饿，因为OS总是优先执行短任务；其次，关键问题在于我们怎么知道程序的运行时间，怎么预测某个进程需要的执行时间？通常有两个办法：使用启发式方法估算（例如根据程序大小估算），或者将程序执行一遍后记录其所用的CPU时间，在以后的执行过程中就可以根据这个测量数据来进行STCF调度。

4）优先级调度，STCF遇到的问题是长任务的程序可能饥饿，那么优先级调度算法可以通过给长任务的进程更高的优先级来解决这个问题；优先级调度遇到的问题可能是短任务的进程饥饿，这个可以通过动态调整优先级来解决。实际上动态调整优先级（称为权值）+时间片轮询的策略正是linux的进程调度策略之一的SCHED_OTHER分时调度策略,它的调度过程如下：

（1）创建任务指定采用分时调度策略，并指定优先级nice值(-20~19)。

（2）将根据每个任务的nice值确定在cpu上的执行时间(counter)。

（3）如果没有等待资源，则将该任务加入到就绪队列中。

（4）调度程序遍历就绪队列中的任务，通过对每个任务动态优先级的计算(counter+20-nice)结果，选择计算结果最大的一个去运行，当这个时间片用完后(counter减至0)或者主动放弃cpu时，该任务将被放在就绪队列末尾(时间片用完)或等待队列(因等待资源而放弃cpu)中。（5）此时调度程序重复上面计算过程，转到第4步。

（6）当调度程序发现所有就绪任务计算所得的权值都为不大于0时，重复第2步。linux还有两个实时进程的调度策略：FIFO和RR,实时进程会立即抢占非实时进程。

5）显然，没有什么调度算法是毫无缺点的，因此现代OS通常都会采用混合调度算法。例如将不同的进程分为几个大类，每个大类有不同的优先级，不同大类的进程的调度取决于大类的优先级，同一个大类的进程采用时间片轮询来保证公平性。

6）其他调度算法，保证调度算法保证每个进程享用的CPU时间完全一样；彩票调度算法是一种概率调度算法，通过给进程“发彩票”的多少，来赋予不同进程不同的调用时间，彩票调度算法的优点是非常灵活，如果你给短任务发更多“彩票”，那么就类似STCF调度，如果给每个进程一样多的“彩票”，那么就类似保证调度；用户公平调度算法，是按照每个用户，而不是按照每个进程来进行公平分配CPU时间，这是为了防止贪婪用户启用了过多进程导致系统效率降低甚至停顿。

7）实时系统的调度算法，实时系统需要考虑每个具体任务的响应时间必须符合要求，在截止时间前完成。

（1）EDF调度算法，就是最早截止任务优先（Earliestdeadlinefirst)算法，也就是让最早截止的任务先做。当新的任务过来时，如果它的截止时间更靠前，那么就让新任务抢占正在执行的任务。EDF算法其实是贪心算法的一种体现。如果一组任务可以被调度（也就是所有任务的截止时间在理论上都可以得到满足），那么EDF可以满足。如果一批任务不能全部满足（全部在各自的截止时间前完成），那EDF满足的任务数最多，这就是它最优的体现。EDF其实就是抢占式的STCF，只不过将程序的执行时间换成了截止时间。EDF的缺点在于需要对每个任务的截止时间做计算并动态调整优先级，并且抢占任务也需要消耗系统资源。因此它的实际效果比理论效果差一点。

（2）RMS调度算法，EDF是动态调度算法，而RMS（ratemonotonicscheduling)算法是一种静态最优算法；该算法在进行调度前先计算出所有任务的优先级，然后按照计算出来的优先级进行调度，任务执行中间既不接收新任务，也不进行优先级调整或者CPU抢占。因此它的优点是系统消耗小，缺点就是不灵活了。对于RMS算法，关键点在于判断一个任务组是否能被调度，这里有一个定律，如果一个系统的所有任务的CPU利用率都低于ln2，那么这些任务的截止时间均可以得到满足，ln2约等于0.693147，也就是此时系统还剩下有30%的CPU时间。这个证明是Liu和Kayland在1973年给出的。1.4使用到的开发工具在本次课程设计中，我们选择了C++语言作为我们所使用的开发语言，开发工具则选用了MicrosoftVisualC++6.0。MFC借助C++的优势为Windows开发开辟了一片新天地，同时也借助ApplicationWizzard使开发者摆脱离了那些每次都必写基本代码，借助ClassWizard和消息映射使开发者摆脱了定义消息处理时那种混乱和冗长的代码段。更重要的是利用C++的封装功能使开发者摆脱Windows中各种句柄的困扰，只需要面对C++中的对象，这样一来使开发更接近开发语言而远离系统。正因为MFC是建立在C++的基础上，所以我强调C/C++语言基础对开发的重要性。利用C++的封装性开发者可以更容易理解和操作各种窗口对象；利用C++的派生性开发者可以减少开发自定义窗口的时间和创造出可重用的代码；利用虚拟性可以在必要时更好的控制窗口的活动。而且C++本身所具备的超越C语言的特性都可以使开发者编写出更易用，更灵活的代码。MicrosoftVisualC++6.0[2]：VisualC++6.0，简称VC或者VC6.0，是微软推出的一款C++编译器，将“高级语言”翻译为“机器语言（低级语言）”的程序。VisualC++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出VisualC++1.0后，随着其新版本的不断问世，VisualC++已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了VisualC++.NET(VisualC++7.0)，但它的应用有很大的局限性，只适用于Windows2000、WindowsXP和WindowsNT4.0。所以实际中，更多的是以VisualC++6.0为平台。1.4.1特色三级标题也不要缩进；下同。三级标题也不要缩进；下同。VisualC++6.0由Microsoft开发,它不仅是一个C++编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrateddevelopmentenvironment，IDE）。VisualC++6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。这些组件通过一个名为DeveloperStudio的组件集成为和谐的开发环境。Microsoft的主力软件产品。VisualC++是一个功能强大的可视化软件开发工具。自1993年Microsoft公司推出VisualC++1.0后，随着其新版本的不断问世，VisualC++已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了VisualC++.NET(VisualC++7.0)，但它的应用的很大的局限性，只适用于Windows2000,WindowsXP和WindowsNT4.0。所以实际中，更多的是以VisualC++6.0为平台。VisualC++6.0以拥有“语法高亮”，自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创建预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。1.4.2缺点由于C++是由C语言发展起来的，也支持C语言的编译。6.0版本是使用最多的版本，很经典。最大的缺点是对于模版的支持比较差。现在最新补丁为SP6，推荐安装，否则易出现编译时假死状态。仅支持Windows操作系统。目前发现与windows7兼容性不好，安装成功后可能会出现无法打开cpp文件的现象。现在的最新版C++编译器集合在MicrosoftVisualStudio2010软件里面，包含C++，Visualbasic，C#，J#，.net。等,其中，VC开发环境的版本已经升级至MicrosoftVisualC++2010，对C++的支持更加全面稳定，建议电脑性能好的可以使用此版本。目前微软公司已经停止对VC++6.0系列产品的维护，继而转向.NET平台环境，新的MS2008、MS2010等将更符合新世纪通用开发需求。不要随便加空行！！2需求分析2.1需求背景无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。众所周知，现在的操作系统都是多任务的操作系统，实际上并不是真正同时运行多个进程，只不过是进程在频繁切换，而这种切换用户基本上感觉不到，进程调度就是操作系统来完成的。当以下情况出现时需要操作系统来调度进程：时间片到，即每个进程所分配的时间片用完后，要跳转到调度程序；占用CPU的当前运行进程提出I/O操作，发起对内核的系统调用时，在系统调用结束后,跳转到调度程序；当前运行进程对所有内核系统调用的结束时都要跳转到调度程序，根据当前的调度信息来决定下一个可以占用CPU的进程。然而进程调度的实现需要一系列的算法。如短作业优先调度算法，但该算法仅照顾了短作业而忽略了长进程，而且如果并未指明进程的长度，则短进程优先和基于进程长度的抢占式调度算法都将无法使用。在早期的时间片轮转算法[3]中，系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。时间片的大小从几ms到几百ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列的队首进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。但该算法存在未考虑优先级的不足。而基于时间片的高优先级调度算法则不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要。本次试验就是依据该算法的原理进行设计的。首先设置多个就绪队列并为各个队列赋予不同的优先级，第一个队列的优先级最高，依次降低；当新进程进入内存后将其放入第一队列的队尾，然后再按先来先服务的原则排队等待调度；仅当第一个队列为空闲时，调度程序才调度第二队列中的进程运行。根据分析，得到如下结果：（1）系统组成系统由虚拟内核(VKernel)、命令解释程序(Commander)、用户程序（Application）、编译器（Compiler）四部分组成。VKernel首先运行，并常驻内存。Kernel启动后，创建Commander进程。根据用户请求创建多个Application进程。Kernel负责维护6个数据结构，包括时间(Time),处理器状态(CPUstate),进程表(PCBTable),就绪队列(ReadyState),等待队列(BlockedState),运行进程（RunningState）。Time是系统时间片。CPUstate应包括程序计数器PC,累加器A、B,状态寄存器F的值。PCBTable的每一项是一个进程的进程控制块(PCB)。Commander程序、Application程序是用下列CPU虚拟指令书写的程序：#include<stdio.h>/*定义头文件（本程序自带的）*#include<stdlib.h>#include<string.h>#include<math.h>typedefstructnode/*进程节点信息*/{charname[20];/*进程的名字*/intprio;/*进程的优先级*/intround;/*分配CPU的时间片*/intcputime;/*CPU执行时间*/intneedtime;/*进程执行所需要的时间*/charstate;/*进程的状态，W--就绪态，R--执行态，F--完成态*/intcount;/*记录执行的次数*/structnode*next;/*链表指针*/}PCB;typedefstructQueue/*多级就绪队列节点信息*/{PCB*LinkPCB;/*就绪队列中的进程队列指针*/intprio;/*本就绪队列的优先级*/intround;/*本就绪队列所分配的时间片*/structQueue*next;/*指向下一个就绪队列的链表指针*/}ReadyQueue;PCB*run=NULL,*finish=NULL;/*定义三个队列，就绪队列，执行队列和完成队列*/ReadyQueue*Head=NULL;/*定义第一个就绪队列*/intnum;/*进程个数*/intReadyNum;/*就绪队列个数*/voidOutput();/*进程信息输出函数*/voidInsertFinish(PCB*in);/*将进程插入到完成队列尾部*/voidInsertPrio(ReadyQueue*in);/*创建就绪队列，规定优先数越小，优先级越低*/voidPrioCreate();/*创建就绪队列输入函数*/voidGetFirst(ReadyQueue*queue);/*取得某一个就绪队列中的队头进程*/voidInsertLast(PCB*in,ReadyQueue*queue);/*将进程插入到就绪队列尾部*/voidProcessCreate();/*进程创建函数*/voidRoundRun(ReadyQueue*timechip);/*时间片轮转调度算法*/voidMultiDispatch();/*多级调度算法，每次执行一个时间片*/（2）命令解释程序命令解释程序从标准输入重复读入用户命令,然后以消息形式发送给内核。命令解释程序处理的命令由设计者定义并实现。（3）编译器编译器把虚拟指令和虚拟系统调用编译为可执行字节码。可执行字节码由内核解释执行。2.2课程设计任务1）设计进程控制块；2）设计优先级对应的时间片；3）实现高优先级非抢占式调度算法；4）实现时间片轮转调度算法；5）实现基于高优先级的时间片轮转算法。2.2.1课题目的三级标题也不要缩进；下同。三级标题也不要缩进；下同。1)理解进程调度相关理论；2)掌握时间片调度原理；3)掌握高优先级调度原理。2.2.2课题内容1)设计进程控制块；2)设计多个进程队列；3)设计多个进程；4)动态生成时间片、执行时间和优先级；5)设计基于时间片的多优先级调度算法；2.2.3测试要求要求输出进程名以及与其对应的优先级、轮数、CPU时间、需要时间、进程状态、计数器，可执行文件的输出格式如下：进程名优先级轮数CPU时间需要时间进程状态计数器Jc22802W0Jc11801R02.3课程设计要求1)编写程序完成课题内容；2)在课程设计报告中画出基于时间片的高优先级调度函数流程图；3)撰写课程设计报告，并参加答辩。2.4课程设计思想FCFS、SJF和优先级调度算法仅对某一类作业有利，相比之下，它能全面满足不同类型作业的需求，较好实现公平性与资源利用率之间的平衡。对交互型作业，由于通常较短，这些作业在第一队列规定的时间片内完成，可使用户感到满意；对短批作业，开始时在第一队列中执行一个时间片就可完成，便可与交互型作业一样获得快速晌应，否则通常也仅需在第二、第三队列中各执行一个时间片即可完成，其周转时间仍较短；对长批作业，它们依次在第一至第n个队列中轮番执行，不必担心长时间得不到处理。

不要随便加空行！！！3概要设计3.1课程设计所用方法及其原理3.1.1优先级优先级[4]体现了进程的重要程度或紧迫程度，在大多数现代操作系统中，都采用了优先级调度策略。优先级从小到大（如0-127），0优先级最低，127最高。在本实验中，要求优先级为0-8。3.1.2基于时间片调度 将所有的就绪进程按照先来先服务[5]的原则，排成一个队列，每次调度时，将CPU分配给队首进程，并令其执行一个时间片。当时间片用完时，由一个计时器发出时钟中断请求，调度程序把此进程终止，把该进程放到队尾。 在调度过程中，需要通过时间函数检测进程的执行时间，当该进程执行时间≥时间片大小时，进行调度。3.1.3高优先级调度 优先级高的进程优先得到cpu，等该进程执行完毕后，另外的进程才能执行。3.1.4基于时间片的高优先级调度 时间片和优先级调度仔细检查缩进！的结合，在系统中，每个优先级对应一个就绪队列，在每个就绪队列内，采用时间片调度。当高优先级进程队列调度完成后，才能转入更低优先级的就绪队列调度。仔细检查缩进！不要随便加空行！！！3.2主要的数据结构表3.1PCB的数据结构字段名类型宽度别名name字符型10进出名prio数值型1进程的优先级round日期时间型8分配CPU的时间片needtime日期时间型8进程执行所需要的时间state字符型10进程的状态count数值型10记录执行的次数next指针型100链表指针不要随便加空行！！！3.3课题设计的流程图图3.1主要数据流程图4详细设计4.1设计进程控制块为了描述和控制进程的运行，系统为每个进程定义了一个数据结构，即进程控制块【6】他的作用是使一个在多道程序环境下不能独立运行的程序（含数据），成为一个能独立运行的基本单位，一个能与其它进程并发执行的进程。在进程的整个生命周期中，系统总是通过PCB而不是任何别的什么而感知到该进程的存在的。PCB是进程存在的唯一标志。4.1.1进程控制块的内容1）进程标识符[7]：进程标识符用于惟一的标识一个进程。一个进程通常有两种标识符：内部标识符和外部标识符。内部标识符指在所有的操作系统中，都为每一个进程赋予了一个惟一的标识符，他通常是一个进程的符号。设置内部标识符主要是为了方便系统使用。外部标识符是由创建者提供，通常是由字母、数字组成，往往是由用户（进程）在访问该进程时使用。为了描述进程的家族关系，还应设置父进程标识和子进程标识。此外，还可设置用户标识，以指示拥有该进程的用户。2）处理机状态[8]：主要是由处理机的各种寄存器中的内容组成。处理机在运行时，许多信息都放在寄存器中。当处理机被中断时，所有这些信息都必须保存在PCB中，以便在该进程重新执行时，能从断电继续执行。这些寄存器包括：（1）通用寄存器，又称为用户可视寄存器，它们是用户进程可以访问的，用于在暂存信息，在大多数处理机中，有8~32个通用寄存器，在RISC结构的计算机中科超过100个；（2）指令计数器，其中存放访问的下一条指令的地址；（3）程序状态字PSW，其中含有状态信息，如条形码、执行方式中断屏蔽标志等。（4）用户栈指针，指每个用户进程都有一个或若干个与之相关的系统栈，用于存放过过程和系统调用参数及调用地址，栈指针指向该栈的栈顶。3）进程调度信息[9]：在PCB中还存放一些与进程调度和进程对换有关的信息，包括：（1）进程状态，指明进程的当前状态，作为进程调度和兑换的依据；（2）进程优先级，用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机；（3）进程调度所需的其它信息，他们与所采用的进程调度算法有关，比如，进程已等待CPU的时间总和、进程已执行的时间总和等；（4）事件，指进程由执行状态改为阻塞状态所等待发生的事件，即阻塞原因。4）进程控制信息：进程控制信息包括程序和数据地址的地址，只进程的程序和数据所在的内存或外存底（首）址，以便再调度到该进程执行时，能从CPU中找到其程序和数据；进程同步和通信机制，指实现进程同步和进程通信时必须的机制，如信息队列指针、信号量等，他们可能全部或的放在PCB中；资源清单，即一张列出了除CPU以外的、进程所需的全部资源即已经分配到该进程的资源清单；链接指针，它给出了本进程（PCB）所在队列中的下一个进程的PCB的首地址。4.1.2进程名字name、进程的优先级prio、分配CPU的时间片round、进程执行所需要的时间needtime、进程的状态state、记录执行的次数count、链表指针next。4.1.3进程控制块的格式进程名指针要求运行时间已运行时间状态图4.1进程控制块格式其中，进程名——作为进程的标识，如Q1、Q2等。指针——进程按顺序排成循环链队列，用指针指出下一个进程的进程控制块的首地址，最后一个进程的指针指出第一个进程的进程控制块首地址。要求运行时间——假设进程需要运行的单位时间数。已运行时间——假设进程已经运行的单位时间数，初始值为“0”。状态——有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“W”表示。当一个进程运行结束后，它的状态为“结束”，用“F”表示，当进程运行时，它的状态为“执行”，用“R”表示。4.2进程的三种基本状态1）就绪（ready）状态分配到除CPU以外所有必要的资源以后，只要在获得CPU，便可立即执行，进程这时的状态称为就绪状态。在一个系统中处于就绪状态的进程可能有多个，通常将它们排成一个队列，称为就绪队列。2）执行状态进程已获得CPU，其程序正在执行。在单机处理系统中，只有一个进程处于执行状态；在多处理机系统中，则有多个进程处于执行状态。3）阻塞状态正在执行的进程由于发生某个时间而暂时无法继续执行时，便放弃处理机而处于暂停状态，亦即进程的执行受到阻塞，把这种暂停状态称为阻塞状态，有时也称为等待状态或者封锁状态。致使进程阻塞的典型事件有：强求I/O，申请缓存空间等。通常将这种处于阻塞状态的进程也排成一个队列。有的系统则根据阻塞原因的不同而把处于阻塞状态的进程拍成多个队列。处于就绪状态的进程，在调度程序为之分配的了处理机之后，该进程便可执行，相应的，它就由就绪状态转变为执行状态。正在执行的进程也成为当前进程，如果因分配给它的时间片已完而被暂停执行时，该进程便由执行状态又回复到就绪状态；如果因发生某件事而使进程的执行受阻（例如，进程请求访问某临界资源，而该资源正在被其他进程访问时），使之无法继续执行，该进程将由执行状态转变为阻塞状态。如图，表示了进程三种基本状态以及各状态之间的转换关系。4.3优先级4.3.1优先级简介是指在进程创建时先确定一个初始优先数，以后在进程运行中随着进程特性的改变不断修改优先数，这样，由于开始优先数很低而得不到CPU的进程，就能因为等待时间的增长而优先数变为最高而得到CPU运行。4.3.2优先权调度算法的类型1）非抢占式优先权算法：在这种方式下，系统一旦把处理机分配给就绪队列中优先权最高的进程后，该进程便一直执行下去，直至完成；或因发生某事件使该进程放弃处理机时，系统方可再将处理机重新分配给另一优先权最高的进程。这种调度算法主要用于批处理系统中；也可某些对实时性要求不严的实时系统中。2）抢占式优先权调度算法：系统同样把处理机分配给优先权最高的进程,使之执行。但在其执行期间,只要又出现了另一个其优先权更高的进程,进程调度程序就立即停止当前进程(原优先权最高的进程)的执行,重新将处理机分配给新到的优先权最高的进程。这种抢占式的优先权调度算法,能更好地满足紧迫作业的要求,常用于要求比较严格的实时系统中,以及对性能要求较高的批处理和分时系统中。4.3.3优先权的类型1）静态优先权[10]：静态优先权是在创建进程时确定的，且在进程的整个运行期间保持不变。一般地，优先权是利用某一范围内的一个整数来表示的，例如,0~7，又把该整数称为优先数。只是具体用法各异:有的系统用“0”表示最高优先权,当数值愈大时,其优先权愈低；而有的系统恰恰相反。确定进程优先权的依据有三个方面:（1）进程类型(系统进程/用户进程)（2）进程对资源的需求(需求量的大小)（3）用户要求(用户进程紧迫程度)2)动态优先权:动态优先权是指在创建进程时所赋予的优先权，可以随进程的推进或随其等待时间的增加而改变的，以便获得更好的调度性能。例如，我们可以规定,在就绪队列中的进程，随其等待时间的增长，其优先权以速率a提高。若所有的进程都具有相同的优先权初值，则显然是最先进入就绪队列的进程，将因其动态优先权变得最高而优先获得处理机，此即FCFS算法。4.3.4优先权的变化规律由于等待时间与服务时间之和，就是系统对该作业的响应时间,故该优先权又相当于响应比RP。4.3.5优先级的算法1)设定系统中有五个进程，每一个进程用一个进程控制块（PCB）表示，进程队列采用链表数据结构。2)进程控制块包含如下信息：进程名、优先数、需要运行时间、已用CPU时间、进程状态等等等。3)在每次运行设计的处理调度程序之前，由终端输入五个进程的“优先数”和“要求运行时间”。4)进程的优先数及需要的运行时间人为地指定.进程的运行时间以时间片为单位进行计算。5)采用优先权调度算法，将五个进程按给定的优先数从大到小连成就绪队列。用头指针指出队列首进程，队列采用链表结构。6)处理机调度总是选队列首进程运行。采用动态优先数办法，进程每运行一次优先数“1”，同时将已运行时间加“1”。7)进程运行一次后，若要求运行时间不等于已运行时间，则再将它加入就绪队列；否则将其状态置为“结束”,且退出就绪队列。8)“就绪”状态的进程队列不为空，则重复上面6，7步骤，直到所有进程都成为“结束”状态。9)在设计的程序中有输入语句，输入5个进程的“优先数”和“要求运行时间”，也有显示或打印语句，能显示或打印每次被选中进程的进程名、运行一次后队列的变化，以及结束进程的进程名。10)最后，为五个进程任意确定一组“优先数”和“要求运行时间”，运行并调试所设计的程序，显示或打印出逐次被选中进程的进程名及其进程控制块的动态变化过程。4.3.6最高优先级优先调度算法流程图开始开始初始化PCB，输入进程信息各进程按优先数从高到低排列就绪队列是否为空结束运行进程已占用CPU时间已达到所需的运行时间使运行进程的优先数减1，把运行进程插入就绪队列进程完成，撤销该进程时间片到，运行进程已占用了CPU时间+1N已达到未达到就绪队列首进程投入运行图4.3最高优先级优先调度算法流程图4.4时间片轮转算法4.4.1时间片轮转法的基本原理系统将所有的就绪进程按先来先服务的原则排成一个队列，每次调度时，把CPU分配给队首进程，并令其执行一个时间片。此实验中时间片的单位定义为100ms。当执行的时间片用完时，由一个计时器发出时钟中断请求，调度程序便据此信号来停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中的对手进程，同时也让它执行一个时间片。这样就可以保证就绪队列中的所有进程在一给定的时间内均能获得一时间片的处理机执行时间。换言之，系统能在给定的时间内响应所有用户的请求。4.4.2时间片轮转算法描述1）设系统有10个进程，每个进程用一个进程控制块PCB来代表。2）为每个进程任意确定一个要求运行时间。3）按照进程输入的先后顺序排成一个队列。再设一个队首指针指向第一个到达进程的首址。4）执行处理机调度时，开始选择队首的第一个进程运行。另外，再设一个当前运行进程的指针，指向当前正在运行的进程。5）考虑到代码的可重用性，轮转法调度程序和最高优先级优先调度是调用同一个模快进行输出注:由于轮转法调度程序和最高优先级优先调度是调用同一个模快进行输出,所以在时间轮转法调度算法的进程中,依然显示上述所定义的优先级数。6）进程运行一次后，以后的调度则将当前指针依此下移一个位置，指向下一个进程，即调整当前运行指针指向该进程的链接指针所指进程，以指示应运行进程。同时还应采用计数器来判断该进程的要求运行时间是否等于已运行时间。若不等，则等待下一轮的运行，但此时该进程应插到代执行队列的尾部，否则将该进程的状态置为完成态F，并退出执行队列进入完成队列。7）若就绪队列不空，则重复上述的5）和6）步骤直到所有的进程都运行完为止。8）在所设计的调度程序中，包含显示或打印语句。显示或打印每次选中的进程的名称、所需运行的时间、轮数、cpu时间、运行一次后进程所处的状态以及计数器的变化情况。4.4.31）在开始页面用户可输入进程名，给出时间片的大小和每个进程的服务时间。2）每运行一次，给进程的服务时间减去一个时间片大小排到队尾，显示一个时间片后的新队列。3）直到所有的进程都服务完。4.4.4时间片的工作流程时间片轮转的原则是系统将所有的就绪进程按照先来先服务的原则排成一个队列，每次调度时，把CPU分配对手进程，并令其执行一个时间片，当执行完时，有一个计时器发出时钟中断请求，该进程停止，并被送到就绪队列的末尾，然后再把处理机分配就绪队列的队列进程，同时也让它执行一个时间片。根据时间片轮转调度算法并结合本实验，分析进程运行情况，得到如下图所示的时间轴：不要随便加空行！！！01234567891112141618200123456789111214161820A1B1C1D1E1F1C2G1H1D2I1A0B0C0D0E0F0G0H0I0J0222426283032343537394143J1E2F2G2H2I2J2E3F3G3H3I3J3G4H4I4J4I5J545464850525355图4.4进程运行情况不要随便加空行！！！4.4.5时间片轮转调度流程图YYN开始初始化PCB，输入进程信息各进程按输入顺序插入到队列就绪队列是否为空结束分配时间片，运行首进程计数器计数，运行时间逐渐增加，所需时间逐渐减少运行进程已占用CPU时间已达到所需的运行时间已达到进程完成，撤销该进程并将插到完成队列把运行进程插入到队尾未达到图4.5时间片轮转法调度算法流程图4.5多级反馈队列调度算法多级反馈队列调度算法是一种CPU处理机调度算法，UNIX操作系统采取的便是这种调度算法。多级反馈队列调度算法不必事先知道各种进程所需的执行时间，而且还可以满足各类进程的需要，因而它是目前被公认的一种较好的进程调度算法。4.5.1多级反馈队列调度算法原理1）设有Ｋ个队列，其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一样的。一般来说，第一个队列的优先级最高，第二个队列次之，其余各队列的优先级逐个降低。2）对于某个特定的队列来说，里面是遵循时间片轮转法。也就是说，位于队列Ｋ中有N个作业，它们的运行时间是通过Ｋ这个队列所设定的时间片来确定的（为了便于理解，我们也可以认为特定队列中的作业的优先级是按照FCFS来调度的）。3）各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。例如，第二个队列的时间片要比第一个队列的时间片要长一倍，……，最后一个队列(优先级最低的队列)的时间片一般很大。下图是多级反馈队列算法的示意。图4.6多级反馈队列调度算法4.5.2多级反馈队列调度算法描述1）设置多个就绪队列，并给队列赋予不同的优先级数，第一个最高，依次递减。2）赋予各个队列中进程执行时间片的大小，优先级越高的队列，时间片越小。3）当一个新进程进入内存后，首先将其放入一个对列末尾，如果在一个时间片结束时尚未完成，将其转入第二队列末尾。4）当一个进程从一个对列移至第n个队列后，便在第n个队列中采用时间片轮转执行完。5）仅当时间片空闲时，才调度第二个队列中的进程。(1~i-1)空闲时，才调度i，如果处理机正在第i队列中运行，又有新进程进入优先权较高的队列，则新进程抢占处理机，将正在运行的进程放入第i队列队尾，将处理机分给新进程。4.5.3多级反馈队列调度算法的性能多级反馈队列调度算法具有较好的性能，能很好地满足各种类型用户的需要。1）终端型作业用户。由于终端型作业用户所提交的作业大多数属于交互型作业，作业通常较小，系统只要能使这些作业在第一队列所规定的时间片内完成，便可使终端型作业用户都感到满意。2）短批处理作业用户。对于很短的批处理型作业，开始时像终端型作业一样，如果仅在第一对列中执行一个时间片即可完成，便可获得与终端型作业一样的响应时间。对于稍长的作业，通常也只需在第二队列和第三队列各执行一个时间片即可完成，其周转时间仍然较短。3）长批处理作业用户。对于长作业它将依次在第1,2，…，k个队列中运行，然后再按轮转方式运行，用户不必担心其作业长期得不到处理。4.5.4多级反馈队列调度算法的运作1)现在有10个作业JC1，JC2，JC3，JC4，JC5，JC6，JC7，JC8，JC9，JC10，分别用A，B，C，D，E，F，G，H，I，J表示，分别在0,1,2,3,4,5,6,7,8,9时刻到达，所需要的CPU时间片分别为1,2,3,4,5,6,7,8,9,10。（1）时刻0：A到达。运行1个时间片，完成执行，调入完成队列，此时B到达。（2）时刻1：B到达。运行了1个时间片后，C到达。（3）时刻2：C到达。由于时间片仍然由B掌控，于是等待。B在运行了1个时间片后，已经完成2个时间片的限制，加入完成队列队尾，现在处理机分配给C。（4）时刻3：D到达。由于时间片仍然由C掌控，于是等待。C在运行了1个时间片后，E到达。（5）时刻4：E到达。由于时间片仍然由C掌控，于是等待。C在运行了1个时间片后，时间片用完，置于等待，处理机分配给D，F到达。（6）时刻5：F到达。由于时间片由D掌控，于是等待。D在运行了1个时间片后，G到达。（7）时刻6：G到达。由于时间片由D掌控，于是等待。D在运行了1个时间片后，时间片用完，置于等待，处理机分配给E，H到达。（8）时刻7：H到达。由于时间片由E掌控，于是等待。E在运行了1个时间片后，I到达。（9）时刻8：I到达。由于时间片由E掌控，于是等待。E在运行了1个时间片后，时间片用完，置于等待，处理机分配给F，J到达。（10）时刻9：J到达。由于时间片由F掌控，于是等待。F在运行了2个时间片后，时间片用完，置于等待，处理机分配给C。（11）时刻11。C运行了1个时间片后，完成执行，调入完成队列队尾，处理机分配给G。（12）时刻12。G运行了2个时间片后，时间片用完，于是等待，处理机分配给H。（13）时刻14。H运行了2个时间片后，时间片用完，于是等待，处理机分配给D。（14）时刻16。D运行了2个时间片后，完成执行，调入完成队列队尾，处理机分配给I。（15）时刻18。I运行了2个时间片后，时间片用完，于是等待，处理机分配给J。（16）时刻20。J运行了2个时间片后，时间片用完，于是等待，处理机分配给E。（17）时刻22。E运行了2个时间片后，时间片用完，于是等待，处理机分配给F。（18）时刻24。F运行了2个时间片后，时间片用完，于是等待，处理机分配给G。(19)时刻26。G运行了2个时间片后，时间片用完，于是等待，处理机分配给H。(20)时刻28。H运行了2个时间片后，时间片用完，于是等待，处理机分配给I。(21)时刻30。I运行了2个时间片后，时间片用完，于是等待，处理机分配给J。(22)时刻32。J运行了2个时间片后，时间片用完，于是等待，处理机分配给E。(23)时刻34。E运行了1个时间片后，执行完成，调入完成队列队尾，处理机分配给F。(24)时刻35。F运行了2个时间片后，执行完成，调入完成队列队尾，处理机分配给G。(25)时刻37。G运行了2个时间片后，时间片用完，于是等待，处理机分配给H。(26)时刻39。H运行了2个时间片后，时间片用完，于是等待，处理机分配给I。(27)时刻41。I运行了2个时间片后，时间片用完，于是等待，处理机分配给J。(28)时刻43。J运行了2个时间片后，时间片用完，于是等待，处理机分配给G。(29)时刻45。G运行了1个时间片后，执行完成，调入完成队列队尾，处理机分配给H。(30)时刻46。H运行了2个时间片后，执行完成，调入完成队列队尾，处理机分配给I。(31)时刻48。I运行了2个时间片后，时间片用完，于是等待，处理机分配给J。(32)时刻50。J运行了2个时间片后，时间片用完，于是等待，处理机分配给I。(33)时刻52。I运行了1个时间片后，执行完成，调入完成队列队尾，处理机分配给J。(34)时刻53。J运行了2个时间片后，执行完成，调入完成队列队尾，算法完毕。进程运行情况如下图序号字体不对。序号字体不对。图4.7进程运行情况5调试与操作说明5.1调试过程中遇到的问题及解决方案1）一开始执行的结果都是左对齐，无法居中显示，如下图显示图5.1进程运行结果一原因：经检查程序发现语句printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);设置有错误。解决方案：将代码改为printf("%3s\t%5d\t%3d\t%4d\t%4d\t\t%4c\t\t%3d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);结果如下图所示：图5.2进程运行结果二2）调试程序发现进程所需时间≤8，一旦大于8优先级值则出现负值，如下图所示：图5.3进程运行结果三原因：原代码语句tmp->prio=8-tmp->round使用减法运算解决方案：改为tmp->prio=tmp->round%9，此时输入下图数据，运行成功。图5.4进程运行结果四5.2测试结果1)将所编写完成的代码进行编译，检测代码是否存在错误，若存在错误则进行代码的修改；否则执行编译操作，编译完成后即可点击执行按钮，弹出可执行对话框。根据对话框所提示内容进行输写。2）结合本实验的要求，输入就绪队列的个数为5，输入就绪队列的CPU时间片分别为2、4、8、16、32，输入,进程个数为5，进程名与所需时间依次为（jc1、1)、(jc2、2）、（jc3、3）、（jc4、4）、（jc5、5)，点击回车键，则出现执行结果，如下图所示：图5-5进程运行结果五3）再次输入进程个数为5，出现如图所示的调式结果：图5-6进程运行结果六图5-7进程运行结果七图5-8进程运行结果八图5-9进程运行结果九图5-10进程运行结果十图5-11进程运行结果十一4）调试完成，按任意一个键则退出可执行对话框。总 结因在早期的时间片轮转法中，系统将所有的就绪进程按照先来先服务的原则排成一个队列，每次调度是，把CPU分配给队首进程，并令其执行一个时间片。当执行的时间片用完时，调度程序停止该进程的执行，并将它送往就绪队列的末尾；然后，再把处理机分配给就绪队列中新的队首进程，同时也让它执行一个时间片。在时间片轮转算法中，时间片的大小对系统性能有很大的影响。如果选择很小的时间片将有利于短作业，因为它能较快地完成，但会频繁的发生中断、进程上下文的切换，从而增加系统的开销；反之，如果选择太长时间片，使得每个进程都能在一个时间片内完成，所以，一般定为时间片略大于一次典型地交互所需要的时间。在完成时间片轮转算法的实现过程中，我们遇到了一些问题，比如怎样运用循环队列，如何设计结构体等等，也积极配合并思考进行解决。整体来说，我们的算法虽然实现了体现进程动态运行变化的过程，但是相对而言比较简单。实验中，我们小组不断讨论对算法进行优化，使得运行结果看起来更容易理解，也达到了处理机调度的功能。做实验让我们对于时间片轮转的思想理解的更加透彻，巩固了理论知识的学习。实验心得体会：首先，我们认为这次课程设计是对学习《操作系统》的一次综合考察，锻炼我们综合分析问题、解决问题的能力。初次得到课程设计的题目时，为程序本身的简单而窃喜过；实验过程中也出现了一些难题需要解决，为此去苦苦探索过。课程设计期间，我们完全投入进去了，就像是在做一个相当重要的项目一样的感觉。曾经跑过图书馆几次，只是为了一种新的想法得到实现，也曾多次登录网站浏览网页，为了弥补一些知识上的纰漏，为此曾洒下了真实的汗水。当我们的想法得到实现，又学会了新的知识的时候，心中满是欣喜，或许这是实践出真知的真实验证，有付出就有回报的真实写照吧。其次，我们感受了真诚的友谊。在实验中，遇到的问题是多方面的，而且有那么一部分是以前学过的C语言问题，但是已经忘却或是以前没有真正的理解过。但是你会发现就在你的身边，会有那么一批人在背后热心的帮助你，让你身处困境却感到无限希望。这好像是人生的一种历程，风风雨雨中我们一起走过，然后为了一些坑坑洼洼彼此真诚的帮助过和无私的付出过。团队的协作和彼此心的交流让我们彼此丰厚起来，这也是我们成长中必不可失的重要部分。最后，我们认识到了自己的不足。平心而论，以前真的没有认真的学习过，即使是在听课，可是后来却没有对学习中出现的问题而仔细分析过。得过且过，迷失了我前进的方向，而现在却又重新敞开了。不论是以后的学习还是工作，我想这都是很重要的，我们需要不断进步的动力。总的说来知识上的收获很是重要，精神上的丰收也是更加可喜的，让我知道了学无止境的道理。我们每一个人永远不能满足于现有的成就，人生就像在爬山，一座山峰的后面还有更高的山峰在等着你。挫折是一份财富，经历是一份拥有。这次课程设计必将成为我人生旅途上一个非常美好的回忆。控制在一页。控制在一页。致谢充实的课程设计活动在大家的辛勤忙碌中结束了，它给我们不仅带来了丰硕的实验成果，而且使我们对操作系统这门课程的认识又更近了一步；时间是检验认识真理性的唯一标准，在通过我们亲身实践的过程中，我们感受到了巨大的成就感以及获得了对于课本中的知识更加感性的认识。在此，我们必须要向对我们前进道路提供指引明灯的人致以最诚挚的感谢。首先，要感谢的是两位指导老师，陈礼青老师和邱军林老师。我们很难想象，没有灯塔指引的我们在茫茫的计算机知识的海洋中如何找到方向。陈礼青老师是一位治学非常严谨的老师，对我们的要求较为严格，而且对我们在程序的选择，修改中起到了至关重要的作用。对于我们在课程设计中遇到的各种问题，陈老师总是对我们不清楚的甚至是纠缠不清的问题作出解答，是我们不至于深陷自我桎梏的泥潭。同样，邱军林老师也是一位极其耐心和负责任的老师，而且对于数据库的深刻认识在我们纠正错误方面做出了不可磨灭的贡献，而且在最后的课程设计的答辩过程中，邱老师和陈老师都对我们系统的改进做出了一些建议。对于我们课程设计程序的改善大有裨益。两位老师严谨的治学态度以及对学生耐心负责的态度对我们以后工作生活起着深远的影响。淮阴工学院为我们的课程设计提供了极好地平台，这个平台就是基础。对于学习操作系统的我们，我们自然而然的认识到操作系统对于计算机的重要意义，没有操作系统的一台计算机对于我们是没有任何用处的。所以，感谢淮阴工学院培养出来的良好的学习氛围和坚实的硬件基础，对我们的前进起着推波助澜的强大作用。当然，我们是一个团体在战斗，团体的团结让我们在操作系统课程设计中付出的努力开花结果。团结就是力量，大家在课程设计中各显其能，使得每个人都在争论与交流中得到提高，这些才能使得课程设计这条大船平稳的前行，每一位都是好样的！最后，要向在幕后默默支持和培养我们的父母致以最诚挚的感谢，感恩的话已经言尽，一言以蔽之，我们也会在你们的付出中奋勇前行！参考文献汤小丹，梁红兵，哲凤屏，汤子瀛.计算机操作系统.西安电子科技大学出版社，2007.2.孟庆昌.操作系统教程.北京：电子工业出版社，2004.陈向群，杨芙清.操作系统教程.2版.北京：北京大学出版社，2006.GaryNutt著.操作系统现代观点.孟祥由，晏益慧，译.北京：机械工业出版社，2004.屠祁，屠立德，等.操作系统基础.3版。北京：清华大学出版社，2000.哲凤屏，汤子瀛，杨成忠.计算机操作系统.台湾：儒林图书公司,1994.黄祥喜.计算机操作系统实验教程.广州：中山大学出版社，1994.李勇，刘恩林.计算机体系结构.长沙：国防科技大学出版社，1987.王鹏，尤晋元，等，译.操作系统设计与实现.北京：电子工业出版社，1998.张尧学，史美林.计算机操作系统教程.北京：清华大学出版社，2000.附 录#include<stdio.h>#include<stdlib.h>#include<string.h>typedefstructnode/*进程节点信息*/{charname[20];/*进程的名字*/intprio;/*进程的优先级*/intround;/*分配CPU的时间片*/intcputime;/*CPU执行时间*/intneedtime;/*进程执行所需要的时间*/charstate;/*进程的状态，W--就绪态，R--执行态，F--完成态*/intcount;/*记录执行的次数*/structnode*next;/*链表指针*/}PCB;typedefstructQueue/*多级就绪队列节点信息*/{PCB*LinkPCB;/*就绪队列中的进程队列指针*/intprio;/*本就绪队列的优先级*/intround;/*本就绪队列所分配的时间片*/structQueue*next;/*指向下一个就绪队列的链表指针*/}ReadyQueue;PCB*run=NULL,*finish=NULL;/*定义三个队列，就绪队列，执行队列和完成队列*/ReadyQueue*Head=NULL;/*定义第一个就绪队列*/intnum;/*进程个数*/intReadyNum;/*就绪队列个数*/voidOutput();/*进程信息输出函数*/voidInsertFinish(PCB*in);/*将进程插入到完成队列尾部*/voidInsertPrio(ReadyQueue*in);/*创建就绪队列，规定优先数越小，优先级越低*/voidPrioCreate();/*创建就绪队列输入函数*/voidGetFirst(ReadyQueue*queue);/*取得某一个就绪队列中的队头进程*/voidInsertLast(PCB*in,ReadyQueue*queue);/*将进程插入到就绪队列尾部*/voidProcessCreate();/*进程创建函数*/voidRoundRun(ReadyQueue*timechip);/*时间片轮转调度算法*/voidMultiDispatch();/*多级调度算法，每次执行一个时间片*/intmain(void){PrioCreate();/*创建就绪队列*/ProcessCreate();/*创建就绪进程队列*/MultiDispatch();/*算法开始*/Output();/*输出最终的调度序列*/return0;}voidOutput()/*进程信息输出函数*/{ReadyQueue*print=Head;PCB*p;printf("进程名\t优先级\t轮数\tcpu时间\t需要时间\t进程状态\t计数器\n");while(print){if(print->LinkPCB!=NULL){p=print->LinkPCB;while(p){printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);p=p->next;}}print=print->next;}p=finish;while(p!=NULL){printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);p=p->next;}p=run;while(p!=NULL){printf("%s\t%d\t%d\t%d\t%d\t\t%c\t\t%d\n",p->name,p->prio,p->round,p->cputime,p->needtime,p->state,p->count);p=p->next;}}voidInsertFinish(PCB*in)/*将进程插入到完成队列尾部*/{PCB*fst;fst=finish;if(finish==NULL){in->next=finish;finish=in;}else{while(fst->next!=NULL){fst=fst->next;}in->next=fst->next;fst->next=in;}}voidInsertPrio(ReadyQueue*in)/*创建就绪队列，规定优先数越小，优先级越低*/{ReadyQueue*fst,*nxt;fst=nxt=Head;if(Head==NULL)/*如果没有队列，则为第一个元素*/{in->next=Head;Head=in;}else/*查到合适的位置进行插入*/{if(in->prio>=fst->prio)/*比第一个还要大，则插入到队头*/{in->next=Head;Head=in;}else{while(fst->next!=NULL)/*移动指针查找第一个别它小的元素的位置进行插入*