磁盘调度算法（先来先服务/最短寻道优先）
#include
#include
#include
void FCFS(int a[],int m,int now);//先来先服务
void SSTF(int a[],int n,int now);//最短寻道时间优先
void choose(int a[],int n);//选择排序
void FCFS(int a[],int m,int now){ //先来先服务算法实现
int i,b,sum=0;
printf("\n磁盘调度序列:\n\n");
printf(" （从%d磁道开始）\n",now);
printf("-----------------------\n");
printf("下一个访问| 移动距离\n");
for(i=0;i b=abs(a[i]-now); //每次移动距离 now=a[i]; sum=sum+b; printf("-->%d\t %d\n",a[i],b); } double d=sum*1.0/m; printf("\n平均寻道长度：%.2f\n\n",d); } void SSTF(int a[],int n,int now) //最短寻道时间优先算法实现{ int i,k,sum=0,b; choose(a,n); //对磁道序列进行排序 printf("\n\n"); printf("磁盘调度序列：\n\n"); printf(" （从%d磁道开始）\n",now); printf("-----------------------\n"); printf("下一个访问| 移动距离\n"); if(a[0]>=now){ //当前磁道号小于请求磁道号的最小值for(i=0;i b=a[i]-now; sum+=b; now=a[i]; printf("-->%d\t %d\n",now,b); } } else if(a[n-1]<=now){ //当前磁道号大于请求磁道号的最大值for(i=0;i b=now-a[n-i-1]; sum+=b; now=a[n-i-1]; printf("-->%d\t %d\n",now,b); } } else if(a[0] if(a[i]>=now){ k=i;break;}//选择第一个比当前磁道号大的磁道号 int right=k; int left=k-1; while(left>=0&&right if(now-a[left]<=a[right]-now){ //当前磁道号与大于它的近 b=now-a[left]; sum+=b; now=a[left]; printf("-->%d\t %d\n",now,b); left--; } else{ //当前磁道号与小于它的近 b=a[right]-now; sum+=b; now=a[right]; printf("-->%d\t %d\n",now,b); right++; } } if(left<0){ //磁道序列左边最小的磁道号已经访问，转向右边没有访问的 for(int j=right;j b=a[j]-now; sum+=b; now=a[j]; printf("-->%d\t %d\n",now,b); } } else if(right==n){//磁道序列右边最大的磁道号已经访问，转向左边没有访问的for(int j=left;j>=0;j--){ b=now-a[j]; sum+=b; now=a[j]; printf("-->%d\t %d\n",now,b); } } } double d=sum*1.0/n; printf("平均寻道长度：%.2f\n\n",d); } void choose(int a[],int n) //选择排序实现 { int i,k,index,temp; for(k=0;k index=k; for(i=k+1;i if(a[i] index=i; } temp=a[index]; a[index]=a[k]; a[k]=temp; } printf("排序之后的磁道序列：\n"); for(i=0;i printf("%d ",a[i]); } void main() //主函数 { int i,m,h,now,b,sum=0,a[20]; printf(" ---------输入磁盘调度的基本信息----------\n"); printf(" 1.磁道请求总数2.磁道请求序列3.当前磁道号\n"); printf(" -----------------------------------------\n"); printf("1.需要访问的磁道总数："); scanf(" %d",&m); printf("\n2.需要访问的磁道序列：\n"); for(i=0;i scanf("%d",&a[i]); printf("\n3.输入当前磁道号: "); scanf("%d",&now); do{ printf("\n -------------磁盘调度算法------------\n\n"); printf(" * 1.先来先服务（FCFS）*\n\n"); printf(" * 2.最短寻道时间优先（SSTF）*\n\n"); printf(" * 0.退出系统*\n\n"); printf(" -------------------------------------\n"); printf("请选择算法序号(0-2)：\n"); scanf("%d",&h); switch(h){ case 1: FCFS(a,m,now);break; case 2: SSTF(a,m,now);break; case 0: exit(0);break; default:break; } }while(h>=0); } 青岛理工大学 操作系统课程设计报告 院（系）：计算机工程学院 专业：计算机科学与技术专业 学生姓名: 班级：＿＿学号: 题目：短作业优先调度算法的进程调度程序＿ 起迄日期:＿＿＿＿＿＿＿＿ 设计地点: 指导教师: 2011—2012年度第 1 学期 完成日期: 2012 年 1 月日 一、课程设计目的 进行操作系统课程设计主要是在学习操作系统课程的基础上，在完成操作系统各部分实验的基础上，对操作系统的整体进行一个模拟，通过实践加深对各个部分的管理功能的认识，还能进一步分析各个部分之间的联系，最后达到对完整系统的理解。同时，可以提高运用操作系统知识解决实际问题的能力；锻炼实际的编程能力、开发软件的能力；还能提高调查研究、查阅技术文献、资料以及编写软件设计文档的能力。 二、课程设计内容与要求 设计目的：在多道程序和多任务系统中，系统内同时处于就绪状态的进程可能有若干个，且进程之间也存在着同步与互斥的关系，要求采用指定的调度策略，使系统中的进程有条不紊地工作，通过观察诸进程的运行过程，以巩固和加深处理机调度的概念。 2、设计要求（多道、单处理机）： 1)每一个进程有一个PCB，其内容可以根据具体情况设定。 2)可以在界面设定的互斥资源（包括两种：输入设备与输出设备）的数目 3)进程数、进入内存时间、要求服务时间可以在界面上进行设定 4)进程之间存在一定的同步与互斥关系，可以通过界面进行设定，其表示方法如下： 进程的服务时间由三段组成：I2C10O5（表示进程的服务时间由2个时间片的输入，10个时间片的计算，5个时间片的输出） 进程间的同步关系用一个段表示：W2，表示该进程先要等待P2进程执行结束后才可以运行 因此，进程间的同步与互斥关系、服务时间可以统一用四段表示为：I2C10O5W2 5)可以在运行中显示各进程的状态：就绪、阻塞、执行 6)采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相 应的阻塞队列 7)具有一定的数据容错性 三、系统分析与设计 1、系统分析 本系统主要是采用短作业优先算法进程的进程调度过程。短作业优先调度算法，是指对短作业或短进程优先调度的算法。他们可以分别用于作业调度和进程调度，短作业优先的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将他们调入内存运行。而短进程优先调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给他，，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再度重新调度。本程序采用了非抢占式短作业优先调度。而非抢占式这种方式，一旦把处理机分配给某进程后，便让该进程一直执行，直至该进程完成或发生某事件而被阻塞时，才再把处理机分配给其它进程，决不允许某进程抢占已经分配出去的处理机。这种调度方式的优点是实现简单，系统开销小，适用于大多数的批处理系统环境。但它难以满足紧急任务的要求——立即执行，因而可能造成难以预料的后果。因此，在要求比较严格的实时系统中，不宜采用这种调度方式本系统的主要是在满足要求多道单处理机的情况下进行短作业的优先调度。 本系统在测试时输入了五个进程，按实验要求如I2C10O5（表示进程的服务时间由2个时间片的输入，10个时间片的计算，5个时间片的输出，5个时间片的计算组成）的方式输入，各进程的信息如下：（0 0 1 1 1 ）（1 2 1 2 2 ）（2 4 1 1 1 ） ●假定一个阅览室最多可容纳100人，读者进入和离开阅览室时都必须在阅览室门口的 一个登记表上进行登记，而且每次只允许一人进行登记操作，请用记录型信号量机制实现上述问题的同步。 定义信号量sum,mutex，初值分别为100，1。（3分）则第i个读者的活动描述为：procedure P i(i=1,2,3……) begin wait(sum); wait(mutex); 登记； signal(mutex); 进入阅览室； 阅读; wait(mutex); 登记； signal(mutex); 离开阅览室； signal(sum); end ●请用信号量解决以下的“过独木桥”问题：同一方向的行人可连续过桥，当某一方向 有人过桥时，另一方向的行人必须等待；当某一方向无人过桥时，另一方向的行人可以过桥。 将独木桥的两个方向分别标记为A和B；并用整形变量countA和countB分别表示A、B 方向上已在独木桥上的行人数，初值为0；再设置三个初值都1的互斥信号量：SA用来实现对countA的互斥访问，SB用来实现对countB的互斥访问，mutex用来实现两个方向的行人对独木桥的互斥使用。则具体描述如下： Var SA,SB,mutex:semaphore:=1,1,1; CountA,countB:integer:=0,0: begin parbegin process A: begin wait(SA); if(countA=0) then wait(mutex); countA:=countA+1; signal(SA); 过独木桥； wait(SA); countA:=countA-1; if (countA=0) then signal(mutex); signa(SA); end process B: begin wait(SB); 6. 算法题（共32个题目） 200348. 在信号量机制中，若P（S）操作是可中断的，则会有什么问题？ 此题答案为：答： P（S）的操作如下： Begin S.Value:= S.Value-1; ① If S.Value<0 Then ② Begin Insert(*,S.L); Block(*) ③ End End. 若P（S）可中断的，例如进程A在执行了语句①之后从CPU上退 下了，假定此时S.Value＝0；这时换另一进程B，B又将S.Value 的值减1使之为－1，在执行语句③时，B被阻塞；然后又换回A执行，由于A的"断点"是语句①之后，当它执行语句②时，由于这时S.Value已经是－1，故进程继续执行而被阻塞。这就出现了错误： 本来A操作P（S）操作后，S.Value＝0，是不应该被阻塞的，现在却被阻塞了。 200350. 何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？ ＃define true; # define false; Int flag[2]; flag[1]=flag[2]=false; enter-crtsec(i) int i; { While(flag[1-i]) flag[i]=true; } feave-crtsec(i) Int i; { flag[i]=false; } process I; … Enter-crtsec(i); In critical section; Leave-crtsec(i); 此题答案为：答：一次仅允许一个进程使用的资源称为临界资源，在进程中对临界资源访问的程序段称为临界区。 从概念上讲，系统中各进程在逻辑上是独立的，它们可以按各自的速度向前推进。但由于它们共享某些临界资源，因而产生了临界区问题。对于具有临界区问题的并发进程，它们之间必须互斥，以保证不会同时进入临界区。 这种算法不是安全的。因为，在进入临界区的enter-crtsec（）不是一个原语操作，如果两个进程同时执行完其循环（此前两个flag均为false），则这两个进程可同时进入临界区。 200353. 某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票少于20名购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题： （1）用P、V操作管理这些并发进程时，应怎样定义信号量？写出信号量的初值以及信号量各种取值的含义。 （2）根据所定义的信号量，把应执行的P、V操作填入下述程序中，以保证进程能够正确地并发执行。 Cobegin PROCESS Pi(i=1,2,…) Begin 进入售票厅； 购票； 退出； End; 操作系统磁盘调度算法 实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 目录 1．课程设计目的 编写目的 本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。 2．课程设计内容 设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。 1、先来先服务算法（FCFS） 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进 程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。 2、最短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。 3、扫描算法（SCAN） 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到 《操作系统》实验报告 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E31314037 一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务（FCFS）调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法 高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = （等待时间 + 要求服务时间）/要求服务时间 三、实验内容 源程序： #include 操作系统期末考试（A） 一、单项选择题（在每小题的四个备选答案中，只有一个是正确的，将其写在题干的括号中。每小题2分，共20分） 1、文件系统的主要组成部分是（） A、文件控制块及文件 B、I/O文件及块设备文件 C、系统文件及用户文件 D、文件及管理文件的软件 2、实现进程互斥可采用的方法（） A、中断 B、查询 C、开锁和关锁 D、按键处理 3、某页式管理系统中，地址寄存器的低9位表示页地址，则页面大小为（） A、1024字节 B、512字节 C、1024K D、512K 4、串联文件适合于（）存取 A、直接 B、顺序 C、索引 D、随机 5、进程的同步与互斥是由于程序的（）引起的 A、顺序执行 B、长短不同 C、信号量 D、并发执行 6、信号量的值（） A、总是为正 B、总是为负 C、总是为0 D、可以为负整数 7、多道程序的实质是（） A、程序的顺序执行 B、程序的并发执行 C、多个处理机同时执行 D、用户程序和系统程序交叉执行 8、虚拟存储器最基本的特征是（） A、从逻辑上扩充存容量 B、提高存利用率 C、驻留性 D、固定性 9、飞机定票系统是一个（） A、实时系统 B、批处理系统 C、通用系统 D、分时系统 10、操作系统中，被调度和分派资源的基本单位，并可独立执行的实体是（） A、线程 B、程序 C、进程 D、指令 二、名词解释（每小题3分，共15分） 1.死锁: 2.原子操作: 3.临界区: 4.虚拟存储器: 5.文件系统: 三、判断改错题（判断正误，并改正错误，每小题2分，共20分） 1、通道是通过通道程序来对I/O设备进行控制的。（） 2、请求页式管理系统中，既可以减少外零头，又可以减少零头。（） 3、操作系统中系统调用越多，系统功能就越强，用户使用越复杂。（） 4、一个进程可以挂起自已，也可以激活自已。（） 5、虚拟存储器的最大容量是由磁盘空间决定的。（） 6、单级文件目录可以解决文件的重名问题。（） 7、进程调度只有一种方式：剥夺方式。（） 8、程序的顺度执行具有顺序性，封闭性和不可再现性。（） 9、并行是指两个或多个事件在同一时间间隔发生，而并发性是指两个或多个事件在同 一时刻发生。（） 10、进程控制一般都由操作系统核来实现。（） 四、简答题（每小题5分，共25分） 1、简述死锁产生的原因及必要条件。 2、什么是多道程序技术，它带来了什么好处？ 《操作系统原理》 课程设计报告书 题目：磁盘调度 专业：网络工程 学号： 学生姓名： 指导教师： 完成日期： 目录 第一章课程设计目的 (1) 1.1 编写目的 (1) 第二章课程设计内容 (2) 2.1 设计内容 (2) 2.1.1、先来先服务算法（FCFS） (2) 2.1.2、最短寻道时间优先算法（SSTF） (2) 2.1.3、扫描算法（SCAN ） (3) 2.1.4、循环扫描算法（CSCAN ） (3) 第三章系统概要设计 (4) 3.1 模块调度关系图 (4) 3.2 模块程序流程图 (4) 3.2.1 FCFS 算法 (5) 3.2.2 SSTF 算法 (6) 3.2.3 SCAN 算法 (7) 3.2.4 CSCAN 算法 (8) 第四章程序实现 (9) 4.1 主函数的代码实现 (9) 4.2.FCFS 算法的代码实现 (11) 4.3 SSTF 算法的代码实现 ...................................................... 13 4.4 SCAN 算法的代码实现..................................................... 15 4.5 CSCAN 算法的代码实现.................................................... 17 第五章测试数据和结果 (20) 第六章总结 (23) 第一章课程设计目的 1.1 编写目的 本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解 课程设计 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期： 目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13) 摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。 一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列 《操作系统》实验一实验报告 【实验题目】：先来先服务FCFS和短作业优先SJF进程调度算法【实验目的】 通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。 【实验内容】 问题描述： 设计程序模拟进程的先来先服务FCFS和短作业优先SJF调度过程。假设有n个进程分别在T1, …,T n时刻到达系统，它们需要的服务时间分别为S1, … ,S n。分别采用先来先服务FCFS和短作业优先SJF 进程调度算法进行调度，计算每个进程的完成时间，周转时间和带权周转时间，并且统计n个进程的平均周转时间和平均带权周转时间。 程序要求如下： 1）进程个数n；每个进程的到达时间T1, …,T n和服务时间S1, … ,S n；选择算法1-FCFS，2-SJF。 2）要求采用先来先服务FCFS和短作业优先SJF分别调度进程运行，计算每个进程的周转时间，带权周转时间，并且计算所有进程的平均周转时间，带权平均周转时间； 3）输出：要求模拟整个调度过程，输出每个时刻的进程运行状态，如“时刻3：进程B开始运行”等等； 4）输出：要求输出计算出来的每个进程的周转时间，带权周转时间， 所有进程的平均周转时间，带权平均周转时间。【实验过程】 #include 人和以吟实验报告学院（系）名称：计算机与通信工程学院 【实验过程记录(源程序、测试用例、测试结果及心得体会等) 】 #include 题目先来先服务FCFS和短作业优先SJF进程调度算法 姓名： 学号： 专业： 学院： 指导教师：林若宁 二零一八年十一月 一、实验目的 模拟单处理器系统的进程调度，分别采用短作业优先和先来先服务的进程调度算法作为进程设计算法，以加深对进程的概念及进程调度算法的理解． 二、实验内容 1. 短作业优先调度算法原理 短作业优先调度算法，是指对短作业或断进程优先调度的算法。它们可以分别可以用于作业调度和进程调度。短作业优先调度算法，是从后备队列中选择一个或若干个运行时间最短的作业，将它们调入内存运行。短进程优先调度算法，是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机时再重新调度。 2. 先来先服务调度算法原理 先来先服务(FCFS)调度算法是一种最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，每次调度都是从后备作业队列中选择一个或多个最先进入该队列的作业，将它们调入内存，为它们分配资源、创建进程，然后放入就绪队列。在进程调度中采用FCFS算法时，则每次调度是从就绪队列中选择一个最先进入该队列的进程，为之分配处理机，使之投入运行。该进程一直运行到完成或发生某事件而阻塞后才放弃处理机。 三、程序设计 1.概要设计 程序包括主函数、FCFS算法函数、SJF算法函数、输出函数；主函数流程：输入文件中的数据—显示各进程数据—选择算法—调用相应算法的函数—输出结果 2.算法流程 SJF算法流程图： 3.详细设计 （1）定义一个结构体 typedef struct PCB { char job_id[10]; //作业ID float Arr_time; //到达时刻 float Fun_time; //估计运行时间 float Wait_time; //等待时间 float Start_time; //开始时刻 float Fin_time; //完成时刻 float Tur_time; //周转时间 float WTur_time; //带权周转时间 int Order; //优先标记 }list; （2）先来先服务算法函数 void fcfs(list *p,int count) //先来先服务算法 { list temp; //临时结构体变量int i; int j; 短作业（进程）优先调度算法 1.短作业（进程）优先调度算法SJ（P）F，是指对短作业或 短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。SJ(P)F 调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。该算法对长作业不利，完全未考虑作业的紧迫程度。 2.流程图 3.代码 #include<> #include<> #include<> struct sjf{ char name[10]; float arrivetime; float servicetime; float starttime; float finishtime; float zztime; float dqzztime; }; sjf a[100]; void input(sjf *p,int N) { int i; printf("intput the process's name & arrivetime & servicetime:\nfor exmple: a 0 100\n"); for(i=0;i<=N-1;i++) { printf("input the %dth process's information:\n",i+1); scanf("%s%f%f",&p[i].name,&p[i].arrivetime,&p[i].servicetim e); 实验一进程调度 一、实验目的 编写并调试一个模拟的进程调度程序，以加深对进程的概念及进程调度算法的理解． 二、实验内容 1.采用“短进程优先”调度算法对五个进程进行调度。每个进程有一个进 程控制块（ PCB）表示。进程控制块可以包含如下信息：进程名、到达 时间、需要运行时间、已用CPU时间、进程状态等等。 2.每个进程的状态可以是就绪 W（Wait）、运行R（Run）、或完成F（Finish） 三种状态之一。每进行一次调度程序都打印一次运行进程、就绪队列、 以及各个进程的 PCB，以便进行检查。重复以上过程，直到所要进程都 完成为止。 三、实现思路 主函数-输入函数-短作业优先调度函数-输出函数。 这是一条最基础的思路。输入函数使用文本导入完成数据输入，输出函数输出调度结果，主函数完成各子函数连接，最主要的是短作业优先的调度函数。我想到的方法就是排序，不断选择需要运行时间最短的作业，接着进行数据输入计算输出等，遍历全部数据并完成调度。 四、主要的数据结构 struct Process_struct{ char name[MaxNum]; //进程名称 int arrivetime; //到达时间 int servertime; //开始运行时间 int finishtime; //运行结束时间 int runtime; //运行时间 int runflag; //调度标志 int order; //运行次序 double weightwholetime; //周转时间 double averagewt_FCFS,averagewt_SJF; //平均周转时间 double averagewwt_FCFS,averagewwt_SJF; //平均带权周转时间 }pro[MaxNum]; 五、算法流程图 六、运行与测试 用书上数据对程序进行测试，结果如下： 计算机操作系统经典题库及答案 一填空： 1．操作系统为用户提供三种类型的使用接口，它们是(命令方式)和(系统调用)和图形用户界面。 2．主存储器与外围设备之间的数据传送控制方式有程序直接控制、(中断驱动方式)、(DMA方式)和通道控制方式。 3．在响应比最高者优先的作业调度算法中，当各个作业等待时间相同时，(运行时间短)的作业将得到优先调度；当各个作业要求运行的时间相同时，(等待时间长)的作业得到优先调度。 4．当一个进程独占处理器顺序执行时，具有两个特性：(封闭性)和可再现性。5．程序经编译或汇编以后形成目标程序，其指令的顺序都是以零作为参考地址，这些地址称为(逻辑地址)。 6．文件的逻辑结构分(流式文件)和记录式文件二种。 7．进程由程度、数据和(FCB)组成。 8．对信号量S的操作只能通过(原语)操作进行，对应每一个信号量设置了一个等待队列。 9．操作系统是运行在计算机(裸机)系统上的最基本的系统软件。 10．虚拟设备是指采用(SPOOLING)技术，将某个独享设备改进为供多个用户使用的的共享设备。 11．文件系统中，用于文件的描述和控制并与文件一一对应的是(文件控制块)。12．段式管理中，以段为单位，每段分配一个(连续区)。由于各段长度(不同)，所以这些存储区的大小不一，而且同一进程的各段之间不要求连续。 13．逻辑设备表（LUT）的主要功能是实现(设备独立性)。 14在采用请求分页式存储管理的系统中，地址变换过程可能会因为(缺页)和(越界)等原因而产生中断。 16. 段的共享是通过（共享段）表实现的。 17．文件的物理结构分为顺序文件、（索引文件）和（索引顺序文件）。 18．所谓（设备控制器），是一块能控制一台或多台外围设备与CPU并行工作的 操作系统 实验报告 哈尔滨工程大学 计算机科学与技术学院 第六讲磁盘调度算法 一、实验概述 1. 实验名称 磁盘调度算法 2. 实验目的 （1）通过学习EOS 实现磁盘调度算法的机制，掌握磁盘调度算法执行的条件和时机； （2）观察 EOS 实现的FCFS、SSTF和 SCAN磁盘调度算法，了解常用的磁盘调度算法； （3）编写 CSCAN和 N-Step-SCAN磁盘调度算法，加深对各种扫描算法的理解。 3. 实验类型 验证性+设计性实验 4. 实验内容 （1）验证先来先服务（FCFS）磁盘调度算法； （2）验证最短寻道时间优先（SSTF）磁盘调度算法； （3）验证SSTF算法造成的线程“饥饿”现象； （4）验证扫描（SCAN）磁盘调度算法； （5）改写SCAN算法。 二、实验环境 在OS Lab实验环境的基础上，利用EOS操作系统，由汇编语言及C语言编写代码，对需要的项目进行生成、调试、查看和修改，并通过EOS应用程序使内核从源代码变为可以在虚拟机上使用。 三、实验过程 1. 设计思路和流程图 （1）改写SCAN算法 在已有 SCAN 算法源代码的基础上进行改写，要求不再使用双重循环，而是只遍历一次请求队列中的请求，就可以选中下一个要处理的请求。算法流程图如下图所示。 图 3.1.1 SCAN算法IopDiskSchedule函数流程图（2）编写循环扫描（CSCAN）磁盘调度算法 在已经完成的SCAN算法源代码的基础上进行改写，不再使用全局变量ScanInside 确定磁头移动的方向，而是规定磁头只能从外向内移动。当磁头移动到最内的被访问磁道时，磁头立即移动到最外的被访问磁道，即将最大磁道号紧接着最小磁道号构成循环，进行扫描。算法流程图如下图所示。 短作业优先调度算法 学院计算机科学与技术 专业 学号 学生姓名 指导教师姓名 2014-3-18目录 九参考文献……………………………………………………………………………………………………… 实验题目 采用短作业优先算法的进程调度程序 课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 具有一定的数据容错性 主要数据结构及其说明 算法的简要说明：短作业（进程）优先调度算法SJ（P）F，是指对短作业或短进程优先调度的算法。它们可以分别用于作业调度和进程调度。短作业优先（SJF）的调度算法是从后备队列中选择一个或若干个估计运行时间最短的作业，将它们调入内存运行。而短进程（SPF）调度算法则是从就绪队列中选出一个估计运行时间最短的进程，将处理机分配给它，使它立即执行并一直执行到完成，或发生某事件而被阻塞放弃处理机再重新调度。优点是SJ(P)F调度算法能有效地降低作业（进程）的平均等待时间，提高系统吞吐量。缺点是该算法对长作业不利；完全未考虑作业的紧迫程度，因而不能保证紧迫性作业（进程）长期不被调度；由于作业（进程）的长短只是根据用户所提供的估计执行时间而定的，而用户又可能会有意或无意地缩短其作业的估计运行时间，致使该算法不一定能真正做到短作业游戏那调度。 该程序定义了一个进程数据块(struct spf)，该数据块有进程名(name)、到达时间(arrivetime)、服务时间(servicetime)、开始执行时间(starttime)、完成时间 (finishtime)、周转时间(zztime)、带权周转时间(dqzztime)。用到的公式有：完成时间=到达时间+服务时间；周转时间=完成时间-到达时间；带权周转时间=周转时间/服务时间；(第一次执行的进程的完成时间=该进程的到达时间；下一个进程的开始执行时间=上一个进程的完成时间)。运行进程的顺序需要对进程的到达时间和服务时间进行比较。如果某一进程是从0时刻到达的，那么首先执行该进程；之后就比较进程的服务时间，谁的服务时间短就先执行谁（如果服务时间相同则看它们的到达时间，到达时间短的先执行）；如果到达时间和服务时间相同，则按先来先服务算法执行。 习题：1.进程同步，信号量机制实现 设有6个程序s1,…,s6，它们在并发系统中执行时如图所示的制约关系，试用wait和signal原语来实现它们之间的同步。（10分） begin parbegin beginS1;signal(a);signal(b);signal(c);end; beginwait(a);S2;signal(d);end; beginwait(b);S3;signal(f);end; beginwait(c);S4;signal(g);end; beginwait(d);S5;signal(e);end; beginwait(e);wait(f);wait(g);S6;end; parend end 2.进程同步，信号量机制实现。详见上课讲的例题 3.有如下进程，后一个依次比前一个晚一个时间单位到达， （1）画出下列调度算法下的调度时间图：FCFS、抢占式\非抢占式SPF、抢占式\非抢占式HPF、HRRN和RR（q=1,q=2） （2）对于上述每种算法，各个作业的周转时间是多少？平均周转时间是多少？ （3）对于上述每种算法，各个作业的带权周转时间和平均带权周转时间各是多少？ 相应比=【(等待时间=现在时刻减去到达时间)+服务时间】/服务时间 4.作出页式存储管理系统中地址变换机构图。已知某作业页表如下： 02 15 29 38 试借助地址变换机构图求出逻辑地址对应的物理地址（1页为1024字节） (1)2968（2）4599（3）0FCCH 解：分析逻辑地址除以页面大小=商是页号：余数是页内地址偏移 根据页号查找页表中的页号判断是（缺页中断，越界中断...） 磁盘调度算法 学生姓名: 学生学号: 专业班级: 指导老师： 2013年6月20日 1、实验目的： 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。 2、问题描述： 设计程序模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN 和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。 3、需求分析 通过这次实验，加深对磁盘调度算法的理解，进一步掌握先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的实现方法。 通过已知开始磁道数、访问磁道总数、磁道号访问序列、访问方向及访问方式得到访问序列及移动距离和平均移动距离！ (1)输入的形式； int TrackOrder[MaxNumber];//被访问的磁道号序列 int direction;//寻道方向 int Num;//访问的磁道号数目 int start;// (2)输出的形式； int MoveDistance[MaxNumber]={0};//移动距离 double AverageDistance=0;//平均寻道长度 移动的序列！ (3)程序所能达到的功能； 模拟先来先服务FCFS、最短寻道时间优先SSTF、SCAN和循环SCAN算法的工作过程。假设有n个磁道号所组成的磁道访问序列，给定开始磁道号m和磁头移动的方向（正向或者反向），分别利用不同的磁盘调度算法访问磁道序列，给出每一次访问的磁头移动距离，计算每种算法的平均寻道长度。 (4)测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。 开始磁道号：100 磁道号方向：内（0）和外（1） 磁道号数目：9 页面序列：55 58 39 18 90 160 150 38 184 4、概要设计 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 O S短作业优先调度算 法C语言 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期： 目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (14) 摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。 一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 ●操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既 动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 ●进一步巩固和复习操作系统的基础知识。 ●培养学生结构化程序、模块化程序设计的方法和能力。 ●提高学生调试程序的技巧和软件设计的能力。 ●提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 一、某系统对主存采用页式管理，供用户使用的主存区域共640K字节，被分成160块，块号为0,1,2……159。现有一作业的地址空间共占4页，其页号为0,1,2,,3，被分配到主存的第2，4，1，5块中，回答： (1)作业每一页的长度为多少字节？ 4K (2)写出该作业被装入主存时，其对应的页表。 逻辑页号主存块号 0 2 1 4 2 1 3 5 (3)把该作业的每一页在主存中的起始地址(用16进制表示)填在下表中 页号起始地址 1 2 3 二、两个并发进程的程序如下： begin N:integer; N:=1; cobegin process A begin L1:N:=N+1; go to L1; end; process B begin L2:print(N); N:=0; go to L2; end; coend; end; 请回答： (1)指出这两个并发进程的临界区。 进程A的临界区：N:=N+1 进程B的临界区: N:=0 (2)指出它们并发执行时可能出现的“与时间有关的错误”。 进程B执行了print（N）后被中断；在执行N：＝0之前插入了进程A执行N：＝N+1，则出现“与时间有关的错误”。 (3)用PV操作进行管理，写出使它们能正确并发执行的程序。 begin N:=integer； N：＝1； s:＝semaphore；s:=1 cobegin process A begin L1:p（s）； n:=N+1； V（s）； go to L1； end； process B begin L2：p（s）； end； Print（N）； coend； N：＝0； end； V（s）； go to L2 三．桌子有一个盘子，每次只能放入一个水果，爸爸专向盘中放苹果，妈妈专向盘中放桔子，女儿专等吃盘中的苹果，儿子专等吃盘中的桔子，试用P，V操作写出他们能正确同步的并发过程。答案： 解：设公用信号量S=1表示盘子，私用信号量S1=0表示苹果，私用信号量S2=0表示桔子。他们能正确同步的并发过程如下： 爸爸P1 妈妈P2 女儿P3 儿子P4 P(S) P(S) P(S1) P(S2) 放苹果放桔子取苹果取桔子 V(S1) V(S2) V(S) V(S) 四.假定一个阅览室可供50个人同时阅读。读者进入和离开阅览室时都必须在阅览室入口处的一个登记表上登记，阅览室有50个座位，规定每次只允许一个人登记或注销登记。 要求：（1）用PV操作描述读者进程的实现算法（可用流程图表示，登记、注销可用自然语言描述）； （2）指出算法中所用信号量的名称、作用及初值。短作业优先调度算法
操作系统经典习题+解释
计算机操作系统算法题(最全)
操作系统磁盘调度算法实验报告
作业调度算法(先来先服务算法,短作业算法)
操作系统精彩试题及问题详解
操作系统磁盘调度算法实验报告
操作系统短作业优先调度算法
先来先服务和短作业优先调度算法
天津理工大学操作系统实验3：磁盘调度算法的实现
操作系统实验-FCFS和短作业优先SJF调度算法模拟
短作业优先算法
短作业优先调度
计算机操作系统经典题库及答案
操作系统实验 磁盘调度算法
短作业优先调度算法 (1)
操作系统经典习题
磁盘调度算法实验报告 (2)
OS短作业优先调度算法C语言知识分享
操作系统原理计算题及答案
相关主题
文本预览