处理机调度程序-操作系统课程设计报告

华北航空航天工程研究所操作系统课程设计报告课程设计主题：处理器调度器作者所在系：计算机与遥感信息技术研究所作者专业：网络工程作者类别：B12522作者姓：梁爽作者的学术编号：教员姓名：刘丽媛完成时间：2015年1月5日华北航空航天工程学院教务办公室系统课程设计任务书主题名称处理器调度程序完成时间2015.1.5教师刘丽媛标题助教学生姓名梁爽班级B12522总体设计要求和技术要点处理器调度器：选择一种调度算法来实现处理器调度。设计要求：主界面可以灵活选择算法，应实现以下算法：1.时间片旋转法2.短作业优先级算法3.动态优先级算法执行时，在主界面选择算法(由函数实现)，输入进程数、运行时间、优先级数(由随机函数生成)，执行并在进入子页面后显示结果。工作内容和时间表时间：本课程设计为两周，即第18周和第19周，共40小时。它分四个阶段完成：1.分析和设计阶段：定义设计需求，找出实现方法。这一阶段在第一天完成。2.代码调试阶段：根据设计分析方案编写代码，然后调试代码，实现课题所需的功能。该阶段在第2-8天完成。3.总结报告阶段：总结设计工作，撰写课程设计报告。这一阶段在第8-9天完成。4.评估阶段：该阶段将在第10天完成。地点：计算机与遥感信息技术研究所实验室课程设计结果1.对应于设计内容的软件程序2.课程设计报告摘要自从1946年第一台真正的数字电子计算机ENIAC诞生以来，计算机经历了四个阶段：1854-1890，1890-20世纪早期，20世纪中期和20世纪晚期-现在。每个阶段的发展都见证了质和量的快速进步。然而，计算机的发展只代表硬件的升级。对于软件来说，操作系统的发展更加引人注目。操作系统是一个管理计算机硬件和软件资源的程序。它也是计算机系统的核心和基石。操作系统是控制其他程序操作、管理系统资源并为用户提供操作界面的系统软件的集合。操作系统的基本任务包括管理和配置内存、确定系统资源的供应和需求优先级、控制输入和输出设备、操作网络和管理文件系统。操作系统的类型非常多样，安装在不同机器上的操作系统从简单到复杂，从移动电话的嵌入式系统到超级计算机的大规模操作系统。目前，DOS、OS/2、UNIX、XENIX、LINUX、Windows、Netware等都是微机上常见的操作系统。操作系统的不断改进对提高计算机的整体性能起着至关重要的作用。操作系统必须提到其要求的所有方面的效率问题，因此计算机系统的处理器调度变得特别重要。处理器调度的效率甚至可能成为提高计算机处理速度的瓶颈。处理器调度是为了合理分配系统资源，因此，改进处理器的调度算法就显得尤为重要。关键词：操作系统处理器调度系统资源内容第一章螺纹理论11.1处理器调度功能11.2处理器调度性能标准1第2章系统需求分析32.1时间片循环调度算法32.2短作业优先级调度算法32.3动态优先级调度算法3第三章系统总体设计43.1系统功能设计43.2时间片旋转方法的设计43.3短作业优先级算法设计43.4动态优先级算法设计4第4章系统实施64.1时间片旋转方法6的实施4.2短作业优先级算法的实现94.3动态优先级算法12的实现第5章系统使用说明14第六章课程设计概述156.1主要问题和解决方案156.2课程设计经验156.3自我评估15参考文献16第一章在多道程序设计系统中，内存中运行着多个程序，它们争夺处理器这一重要资源。处理器调度是根据一定的算法从就绪队列中选择一个进程，并分配给它运行，从而实现进程的并发执行。1.1处理器调度功能一般来说，当占用处理器的进程由于某些请求不能得到满足而不得不放弃CPU以进入等待状态时，或者当时间片到达时，系统不得不将CPU分配给就绪队列中的另一个进程，这将导致处理器进行调度。此外，进程的正常结束、中断处理等。也可能导致处理器的调度。因此，处理器调度是操作系统核心的重要组成部分。其主要功能如下：(1)记住过程状态，如过程名称、指令计数器、程序状态寄存器、所有通用寄存器和其他字段信息，并将这些信息记录在相应的过程控制块中。(2)根据某个算法，决定哪个进程可以获得处理器以及需要多长时间。(3)收回处理器，即当正在执行的进程由于时间不够或某些原因而无法再次执行时，保存进程的场景并收回处理器。处理器调度最重要的功能之一是根据某种算法从就绪队列中选择一个进程来占用CPU。显然，算法是处理器调度的关键。1.2处理器调度性能标准处理器调度有许多独立的调度算法，不同的调度算法有不同的特点。因此，在介绍一个算法之前，首先介绍衡量一个算法的基本标准。有几个因素可以衡量和比较调度算法的性能：(1)中央处理器利用率。中央处理器是计算机系统中最重要的资源，因此中央处理器应该尽可能地保持忙碌，以最大限度地提高资源的利用率。(2)吞吐量。CPU运行时表示系统处于工作状态，工作负载由单位时间内完成的作业数来描述，这称为吞吐量。(3)周转时间。指从作业提交到作业完成所用的时间，包括作业等待、在就绪队列中排队、在处理器上运行和输入/输出操作的总和。(4)等待时间。处理器调度算法实际上并不影响作业执行或输入/输出操作的时间，而只影响作业在就绪队列中等待的时间。因此，为了衡量调度算法的优点和缺点，等待时间通常被简单地研究。(5)响应时间。指从作业提交到系统响应所用的时间。在交互式系统中，工作的周转时间不一定是最好的衡量标准，所以经常使用另一种衡量标准，即响应时间。从用户的角度来看，响应时间应该更快更好，但这通常是以系统资源利用率为代价的。第2章系统需求分析FCFS比较有利于长作业SJF比较有利于短作业，而优先级调度算法仅有利于特定类型的作业。相比之下，它可以充分满足不同类型工作的需求，更好地实现公平和资源利用之间的平衡。对于交互式作业，因为它们通常很短，所以这些作业在第一个队列指定的时间片内完成，这可以使用户满意。对于短批处理作业，可以通过在开始时在第一个队列中执行一个时间片来完成，这与交互式作业相同。否则，它通常只需要在第二个队列中执行一个时间片，在第三个队列中执行一个时间片，并且它的周转时间仍然相对较短。对于长批处理作业，它们在第一到第n个队列中依次执行，而不用担心长期处理。2.1时间片轮换调度算法时间片循环调度算法的基本思想是为就绪队列中的每个进程分配一个时间片，时间片的长度q一般在10 ms到1100 ms之间。就绪队列被视为一个环形结构，调度器根据时间片长度q依次调度就绪队列中的每个进程，使得每个进程都有机会获得相同的时间长度来占用处理器运行。时间片轮换调度算法是分时系统中一种简单有效的调度策略。分时系统有许多终端。最终用户在他们各自的终端设备上同时使用计算机。如果一个终端用户的程序长时间占用处理器，那么其他终端用户的请求就不能立即得到响应。一般来说，在最终用户提出请求后，他对自己能在几秒钟内得到响应感到满意。通过采用时间片旋转算法，系统可以立即响应各种终端用户的请求。如果时间片太大，时间片循环调度算法的性能在很大程度上取决于时间片长度q的值。然后递归算法退化为先进先出算法。另一方面，如果时间片太小，则处理器频繁地在进程之间切换，处理器时间开销变得非常大，并且提供给用户程序的时间将大大减少。2.2短作业优先级调度算法(SJF)根据估计的运行时间，每个进程被安排在一个队列中(运行时间最短的进程被估计放在队列的最前面)。每次运行都将把头进程投入运行，直到运行结束，并将该进程连接到队列的末尾以供完成。然后，下一对将投入运行，直到所有过程完成。2.3动态优先级调度算法流程的动态优先级通常根据以下原则确定：根据进程占用CPU的时间长度。根据就绪进程等待CPU的时间长度。16第三章系统总体设计3.1系统功能设计该系统实现了处理器调度。整个系统分为三个模块：时间片旋转算法、短作业优先级算法和动态优先级算法。如图3-1所示。处理器调度程序时间片旋转法短作业优先级算法动态优先级算法图3-1系统功能模块图3.2时间片旋转方法的设计所有进程按照先来先服务的规则排列在队列中，CPU分配给就绪队列中的第一个进程，并指定其执行时间(称为第二次作为时间片)。当时间片用完但没有执行时，进程被剥夺执行，并连接到完成队列的末尾。然后，下一个流程将投入运行，直到所有操作完成。时间片循环调度算法如图3-2所示。3.3短作业优先级算法的设计SJF，最短工作优先(SJF)也被称为短流程优先(SPN)；这是对FCFS算法的改进。它的目标是减少平均周转时间。根据估计的运行时间，每个进程被安排在一个队列中(运行时间最短的进程被估计放在队列的最前面)。每次运行都将把头进程投入运行，直到运行结束，并将该进程连接到队列的末尾以供完成。然后，下一对将投入运行，直到所有过程完成。3.4动态优先级算法设计动态优先级基于时间片旋转。所有进程按照先来先服务的规则排列在队列中，CPU分配给就绪队列中的第一个进程，并指定其执行时间(称为第二次作为时间片)。当时间片用完但没有执行时，进程被剥夺执行，并连接到完成队列的末尾。然后，下一个流程将投入运行，直到所有操作完成。每个流程的优先级是50服务时间。数字越小，优先级越高，数字越大，优先级越低。优先级随着等待时间的增加而增加(数量减少)。YN开始目标初始化印刷电路板输入进程被插入到队列中队列是空的分配时间片运行进程在队列末尾插入进程。运行时间已达到所需的运行时间。完成图3-2时间片旋转方法第四章系统实现4.1时间片旋转方法的实现根据FCFS原则将系统中所有准备好的进程排列成一个队列。然后轮流执行这个过程。执行过程如图4-1所示。图4-1时间片旋转方法时间片旋转代码如下：typedef结构节点char名称20；/*流程名称*/int prio/*流程优先级*/整数；/* CPU分配的时间片*/int cputime/*中央处理器执行时间*/int needtime/*流程执行所需的时间*/充电状态；/*进程状态，W就绪状态，R exeint计数；/*记录执行的次数*/结构节点*下一步；/*链表指针*/多氯联苯；印刷电路板*就绪=空，*运行=空，*完成=空；void Clear()就绪=空；运行=空；完成=空；void GetFirst() /*取得第一个就绪队列节点*/运行=就绪；如果（准备好了！=空)运行状态=R；ready=ready-next；运行-下一个=空；无效输出()/*输出队列信息*/多氯联苯；p=准备就绪；printf(进程名t优先级t轮数tcpu时间t需要时间t进程状态t计数器 n )；同时(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-下一个；p=完成；同时(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-