#include
#include
#include
#include
typedefstruct_proc
{
char name[100]; /*定义进程名称*/
int team; /*定义柱面号*/
int ci; /*定义磁道面号*/
int rec; /*定义记录号*/
struct_proc *prior;
struct_proc *next;
}PRO;
PRO *g_head = NULL, *g_curr = NULL, *local;
int record = 0; //初始柱面号
int yi = 1; //初始方向
int rec0 = 0; //初始记录号
void init()
{
PRO *p; /*初始化链表（初始I/O表）*/ g_head = (PRO*)malloc(sizeof(PRO));
g_head->next = NULL;
g_head->prior = NULL;
p = (PRO*)malloc(sizeof(PRO));
strcpy_s(p->name, "P1");
p->team = 100;
p->ci = 10;
p->rec = 1;
p->next = NULL;
p->prior = g_head;
g_head->next = p;
g_curr = g_head->next;
p = (PRO*)malloc(sizeof(PRO));
strcpy_s(p->name, "P2");
p->team = 50;
p->ci = 10;
p->rec = 5;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
g_curr = p;
p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P3");
p->team = 40;
p->ci = 10;
p->rec = 4;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
g_curr = p;
p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P4");
p->team = 60;
p->ci = 20;
p->rec = 6;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
g_curr = p;
p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P5");
p->team = 50;
p->ci = 20;
p->rec = 6;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
g_curr = p;
p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P6");
p->team = 60;
p->ci = 20;
p->rec = 6;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
g_curr = p;
p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P7");
p->team = 50;
p->ci = 2;
p->rec = 6;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
g_curr = p;
p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P8");
p->team = 50;
p->ci = 5;
p->rec = 6;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
g_curr = p;
p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P9");
p->team = 50;
p->ci = 100;
p->rec = 6;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
g_curr = p;
p = (PRO*)malloc(sizeof(PRO)); strcpy_s(p->name, "P10");
p->team = 60;
p->ci = 10;
p->rec = 10;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
local = (PRO*)malloc(sizeof(PRO)); /*选中进程*/
strcpy_s(local->name, "P0");
local->team = 50;
local->ci = 50;
local->rec = 50;
local->next = NULL;
local->prior = NULL;
}
void PrintInit() /*打印I/O表*/
{
PRO *t = g_head->next;
printf("-------------------------------------\n");
printf(" 请求I/O表\n");
printf(" 进程名柱面号磁道号记录号\n");
while (t != NULL)
{
printf("%4s %8d %8d %5d\n", t->name, t->team, t->ci, t->rec);
t = t->next;
}
}
void acceptreq() /*接受请求函数*/
{
PRO *p;
p = (PRO*)malloc(sizeof(PRO));
printf("please input the information of the new process\n");
printf("进程名:");
scanf_s("%s", p->name,20);
printf("柱面号(0-199):");
scanf_s("%d", &p->team); /*输入请求进程信息*/ printf("磁道号(0-20):");
scanf_s("%d", &p->ci);
printf("记录号(0-7):");
scanf_s("%d", &p->rec);
getchar();
g_curr = g_head; /*将此节点链入I/O请求表*/ while (g_curr->next != NULL)
g_curr = g_curr->next;
p->next = NULL;
p->prior = g_curr;
g_curr->next = p;
g_curr = g_head->next;
PrintInit(); /*将新的I/O请求表输出*/
}
void SCAN() /*驱动调度函数*/
{
PRO *out = 0;
int deng = 0;
int deng1 = 0;
int min = g_head->next->team;//大于里最小的
int max = g_head->next->team;//小于里最大的
for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next)
{
if (g_curr->team == record)//找到是否有同一个柱面号的进程，deng=1
{
min = g_curr->rec;
out = g_curr;
deng = 1;
break;
}
}
switch (deng)
{
case 1://找出同一个柱面号里最小的记录号
for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next)
{
if (g_curr->team == record&&abs(g_curr->rec - rec0) <= abs(min - rec0))
{
min = g_curr->rec;
out = g_curr;
}
}
break;
case 0:
switch (yi)//不属于同一个柱面号里。分向里和向外方向
{
case 1://向外（大）方向
for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next)
{
if (g_curr->team > record)//找到第一个大于它的柱面号的进程
{
min = g_curr->team;
deng1 = 1;//存在大于的柱面号
break;
}
}
switch (deng1)
{
case 1://存在
for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next)
{
if (min >= g_curr->team&&g_curr->team>record)//找到大于它的柱面号的最小的柱面号
{
min = g_curr->team;
out = g_curr;
}
}
break;
case 0://不存在
yi = 0;//反方向,即向外（小）方向
for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next)
{
if (max <= g_curr->team)//找柱面号比它小的第一个进程
{
min = g_curr->team;
out = g_curr;
}
}
break;
}
break;
case 0:
for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next)
{
if (g_curr->team < record)//找到第一个小于它的柱面号deng1=1
{
max = g_curr->team;
deng1 = 1;
break;
}
}
switch (deng1)
{
case 1:
for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next)
{
if (max <= g_curr->team&&g_curr->team { max = g_curr->team; out = g_curr; } } break; case 0: yi = 1;//向反方向，即向内（大）方向 for (g_curr = g_head->next; g_curr != NULL; g_curr = g_curr->next) { if (min >= g_curr->team) { min = g_curr->team; out = g_curr; } } break; } break; } break; } strcpy_s(local->name, out->name); local->team = out->team; local->ci = out->ci; local->rec = out->rec; printf("被选中进程:\n"); printf(" 进程名柱面号磁道号记录号\n"); printf("%4s %8d %8d %5d\n", out->name, out->team, out->ci, out->rec); switch (yi) { case 1: printf("current direction is UP\n"); printf("-------------------------------------\n"); break; case 0: printf("current direction is DOWN\n"); printf("-------------------------------------\n"); break; } record = local->team; rec0 = local->rec; if (out->next == NULL) /*将选中的进程从I/O请求表中删除*/ { out->prior->next = NULL; free(out); } else { out->prior->next = out->next; out->next->prior = out->prior; free(out); } } void acceptnum() /*通过输入0~1选择‘驱动调度’或是‘接受请求’*/ { float num; char c = 'y'; do { printf("please input a number between 0 and 1\n"); printf("num<=0.5:接受请求 num>0.5:驱动调度\n"); printf("num:"); scanf_s("%f", &num); getchar(); while((num<0 || num>1)) /*过滤不合法数据注意：本程序其他输入数据可能未过滤*/ { printf("ERROR!!!! Input again please!\nnum:\n"); scanf_s("%f", &num); getchar(); } if (num>0.5) /*驱动调度*/ { if (g_head->next == NULL) printf("请求I/O表 is empty!!!\n"); /*请求表为空无需调度*/ else { printf("-------------------------------\n"); printf("驱动调度\n"); PrintInit(); SCAN(); /*调用函数进行调度*/ } } else/*接受请求*/ { printf("-------------------------------\n"); printf("接受请求\n"); PrintInit(); acceptreq(); } printf("是否继续(y/n):"); /*输入n离开本程序*/ c = getchar(); } while (c == 'y' || c == 'Y'); } int main() /*主程序*/ { init(); PrintInit(); acceptnum(); return 0; } 操作系统实验报告实验3 磁盘调度算法 报告日期：2016-6-17 姓名： 学号： 班级： 任课教师： 实验3 磁盘调度算法 一、实验内容 模拟电梯调度算法，实现对磁盘的驱动调度。 二、实验目的 磁盘是一种高速、大量旋转型、可直接存取的存储设备。它作为计算机系统的辅助存储器，负担着繁重的输入输出任务，在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请示等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求，这就叫驱动调度，使用的算法称驱动调度算法。驱动调度能降低为若干个输入输出请求服务所须的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。 三、实验原理 模拟电梯调度算法，对磁盘调度。 磁盘是要供多个进程共享的存储设备，但一个磁盘每个时刻只能为一个进程服务。当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出请求处于等待状态，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。当存取臂仅需移到一个方向最远的所请求的柱面后,如果没有访问请求了,存取臂就改变方向。 假设磁盘有200个磁道，用C语言随机函数随机生成一个磁道请求序列（不少于15个）放入模拟的磁盘请求队列中，假定当前磁头在100号磁道上，并向磁道号增加的方向上移动。请给出按电梯调度算法进行磁盘调度时满足请求的次序,并计算出它们的平均寻道长度。 四、实验过程 1.画出算法流程图。 2．源代码 #include 《操作系统原理》 课程设计报告书 题目：磁盘调度 专业：网络工程 学号： 学生姓名： 指导教师： 完成日期： 目录 第一章课程设计目的 (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编写目的 本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解 1 第二章课程设计内容 2.1设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。 2.1.1、先来先服务算法（FCFS） 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。 2.1.2、最短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。 2 学生实习报告 课程名称_ 数据结构与数据处理应用训练 题目名称多级反馈队列调度算法的实现 学生学院计算机与计算科学 专业班级 学号 学生姓名 指导教师 2012年 2月 16 日 多级反馈队列调度算法的实现 【摘要】 多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程（任务）得到响应又能使短进程（任务）迅速完成。UNIX操作系统便采取这种算法，而本次试验就是试用C语言模拟某多级反馈队列调度算法。本次试验中前三级就绪队列采用时间片轮转法，时间片大小分别为2、4和8，最后一级就绪队列采用FIFO调度，将任务进入多级队列进行模拟，任务从优先级高的队列到优先级地的队列的顺序逐一进入，还用了算法支持抢占式，最后完成模拟，得到各个任务先后完成的顺序，还有得到各个任务的响应时间、离开时间、周转时间。 【关键词】队列优先级任务时间 1 内容与要求 【内容】 多级反馈队列调度算法是操作系统中CPU处理机调度算法之一，该算法既能使高优先级的进程（任务）得到响应又能使短进程（任务）迅速完成。UNIX操作系统便采取这种算法，本次试验就是试用C语言模拟某多级反馈队列调度算法，通过输入任务号、到达时间、运行时间，求出任务完成的先后顺序以及各个任务 的响应时间、离开时间、周转时间。 【要求】 多级反馈队列调度算法描述： 1、该调度算法设置四级就绪队列：前三级就绪队列采用时间片轮转法，时间片大小分别为 2、4和8；最后一级就绪队列采用FIFO调度。 2、任务在进入待调度的队列等待时，首先进入优先级最高的队列等待。 3、首先调度优先级高的队列中的任务。若高优先级中队列中已没有调度的任务，则调度次优先级队列中的任务，依次类推。 4、对于同一个队列中的各个任务，按照队列指定调度方法调度。每次任务调度执行后，若没有完成任务，就被降到下一个低优先级队列中。 5、在低优先级的队列中的任务在运行时，又有新到达的任务，CPU马上分配给新到达的任务。（注：与原来的题目不同，原题是在低优先级的队列中的任务在运行时，又有新到达的任务时，要在运行完这个时间片后，CPU马上分配给新到达的任务，而本题不需要在运行完这个时间片，即正在进行的任务立刻停止，CPU 马上分配给新到达的任务） 6、为方便实现，时间以1为单位，用整数数据表示；且每个时间点，最多只有一个任务请求服务（即输入）。 2 总体设计 算法总体思路： 这是建立在一个时间轴上的，即时刻，一个一个时刻（时间点）进行。 2.1.1 主函数思路： 操作系统磁盘调度算法 实验报告 Company number：【0089WT-8898YT-W8CCB-BUUT-202108】 目录 1．课程设计目的 编写目的 本课程设计的目的是通过磁盘调度算法设计一个磁盘调度模拟系统，从而使磁盘调度算法更加形象化，容易使人理解，使磁盘调度的特点更简单明了，能使使用者加深对先来先服务算法、最短寻道时间优先算法、扫描算法以及循环扫描算法等磁盘调度算法的理解。 2．课程设计内容 设计内容 系统主界面可以灵活选择某种算法，算法包括：先来先服务算法（FCFS）、最短寻道时间优先算法（SSTF）、扫描算法（SCAN）、循环扫描算法（CSCAN）。 1、先来先服务算法（FCFS） 这是一种比较简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法的优点是公平、简单，且每个进 程的请求都能依次得到处理，不会出现某一进程的请求长期得不到满足的情况。此算法由于未对寻道进行优化，在对磁盘的访问请求比较多的情况下，此算法将降低设备服务的吞吐量，致使平均寻道时间可能较长，但各进程得到服务的响应时间的变化幅度较小。 2、最短寻道时间优先算法（SSTF） 该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，该算法可以得到比较好的吞吐量，但却不能保证平均寻道时间最短。其缺点是对用户的服务请求的响应机会不是均等的，因而导致响应时间的变化幅度很大。在服务请求很多的情况下，对内外边缘磁道的请求将会无限期的被延迟，有些请求的响应时间将不可预期。 3、扫描算法（SCAN） 扫描算法不仅考虑到欲访问的磁道与当前磁道的距离，更优先考虑的是磁头的当前移动方向。例如，当磁头正在自里向外移动时，扫描算法所选择的下一个访问对象应是其欲访问的磁道既在当前磁道之外，又是距离最近的。这样自里向外地访问，直到 作业6磁盘驱动调度 1磁盘共有100各柱面，若干个等待访问磁盘者依次要访问的柱面为20 , 44, 40, 4, 80, 12, 76。假设每移动一个柱面需要3ms时间，移动臂当前位于36号柱面，试问对以下 几种磁盘请求调度算法而言，满足以上请求序列，磁头将分别如何移动？并计算为完成 上述各次访问总共花费的寻找时间。 ①先来先服务算法（FCFS）。 ②最短寻找时间优先算法（SSTF）。 ③扫描算法（SCAN）。 ④循环扫描算法（CSCAN）。 1.解 ①先来先服务算法，磁头移动示意图： 0 4 12 20 36 40 44 先来先服务算法磁头的移动顺序为：20，44，40，4，80，12，76。 花费的寻找时间为：（16+24+4+36+76+68+64）*3=864（ms） ②最短寻找时间优先算法，磁头移动示意图： 0 4 12 20 36 40 44 76 80 99 最短寻找时间优先算法磁头的移动顺序为：40，44，20，12，4，76，80 花费的寻找时间为：(4+4+24+8+8+72+4)*3=372 ( ms) 76 80 99 ③扫描（电梯调度）算法，磁头移动示意图: 电梯调度算法磁头移动的顺序为：40, 44, 76, 80, 20, 12, 4 花费的寻找时间为：（44+76）*3=360（ms） ④循环扫描算法（CSCAN,磁头移动示意图： 循环扫描算法磁头移动的顺序为：40, 44, 76, 80, 4, 12, 20 花费的寻找时间为：（44+76+16）*3=408（ms） 【下载本文档，可以自由复制内容或自由编辑修改内容，更多精彩文章，期待你的好评和关注，我将一如既往为您服务】 2008年2月 February 2008 —28— 计 算 机 工 程Computer Engineering 第34卷 第4期 Vol.34 No.4 ·博士论文· 文章编号：1000—3428(2008)04—0028—03 文献标识码：A 中图分类号：TP391 一种新的加权公平队列调度算法 尹德斌，谢剑英 (上海交通大学自动化系，上海 200240) 摘 要：传统公平队列调度算法(WFQ 、WRR 等)普遍存在基于数据包的权重参数计算问题，由此产生的高复杂度使其难以获得广泛应用。该文提出一种新的加权公平队列调度算法，使用服务概率和随机数实现加权公平调度，显著降低了算法的复杂度。同时使用自适应服务概率计算解决了数据包变长度带来的不公平性。通过队列管理技术有效地提高了交换机的缓冲区利用率，并减小了排队延迟抖动。仿真结果证明了算法的有效性和实用性。 关键词: 队列调度；加权公平排队；自适应队列管理；分组交换网络 New Weighted Fair Queue Scheduling Algorithm YIN De-bin, XIE Jian-ying (Department of Automation, Shanghai Jiaotong University, Shanghai 200240) 【Abstract 】Traditional weighted fair queue algorithms have the main drawback: the calculation of the weight parameters according to each packet.The paper proposes a new weighted fair queueing algorithm(SPFQ), which uses service probability to schedule packets and a random number to decide which packet to be served next. In addition, a novel adaptive service probability parameter calculation method is used to solve the unfair problem induced by the variable packet length and an adaptive queue management technology to improve the utilization of the server's queue buffer and reduce the delay burstiness. Simulation results demonstrate the validity and practicability of SPFQ. 【Key words 】queue scheduling; weighted fair queueing; adaptive queue management; packet switching network 1 概述 队列调度是当前互联网技术领域的一个研究热点。其中，加权公平队列调度算法由于能够根据各业务流的权重进行区分服务而受到广大研究者的广泛关注[1-9]。其中最著名的是加权公平WFQ [1]和加权轮询WRR [6]两类算法。WFQ 及其改进算法[3,5,7]都基于通用处理机共享模型[2]，使用虚时间(virtual time)进行数据包转发。WFQ 算法在业务流受漏斗约束的情况下可以提供精确的带宽保证和最大时延上限，并且数据包的转发不受其他业务流特性影响。但是它的计算复杂度太高。WRR [2,6]是另一类复杂度相对较低的常用加权队列调度算法；各业务流在一次轮询中所允许发送的数据包个数由队列权重决定。DRR [4]引入了差额计数器(dificit conter)，记录由数据包长度不同引起的服务量差。轮询类算法复杂度较低，但无法提供确定的带宽保证和时延上限。 国内的研究者近年来也提出了许多队列调度算法。文 献[8]针对SS 和BF 两种业务流，提出了一种对数自适应调度算法，但该算法对类内各业务流之间如何调度并没有说明，且不能提供公平服务和隔离特性。文献[9]提出了一种用于区分服务网络的虚时钟核心无状态队列调度算法，各数据包自身携带虚时钟状态信息，中心服务器根据虚时钟进行转发，但需要根据虚时钟将入队列数据包插入到转发队列中，这无疑是一项沉重的计算负担。另外，该算法并未考虑虚时钟清零问题。本文提出了一种新的加权队列调度算法SPFQ 。由于采用了指数移动平均算法和阀值触发的平均数据包长度更新，使得服务概率计算频度大大降低，从而显著降低了算法的复杂度。 2 SPFQ 队列调度算法 2.1 SPFQ 的基本原理 SPFQ 算法依据各业务流的平均数据包长度将它们的权重转换成归一化服务概率，通过该参数实现加权服务。为了降低算法的复杂度，系统采用事件触发方式计算队列的平均长度。在算法实现中，使用单独模块计算服务概率，以减轻调度器的负荷。 2.2 SPFQ 的结构 数据包分类器图1 SPFQ 算法结构 基金项目：国家自然科学基金资助项目(60572157)；国家“863”计划基金资助项目(2003AA123310) 作者简介：尹德斌(1978－)，男，博士，主研方向：包交换网络的队列调度和管理；谢剑英，教授、博士生导师 收稿日期：2007-03-10 E-mail ：yin_db@https://www.doczj.com/doc/116663540.html, 课程设计 采用短作业优先调度算法调度程序 学号： 姓名： 专业： 指导老师： 日期： 目录 一、实验题目 (3) 二、课程设计的目的 (3) 三、设计内容 (3) 四、设计要求 (3) 五、主要数据结构及其说明 (4) 六、程序运行结果 (5) 七、流程图 (7) 八、源程序文件 (9) 九、实验体会 (13) 十、参考文献 (13) 摘要 在多道程序环境下，主存中有着多个进程，其数目往往多于处理机数目。这就要求系统能按某种算法，动态地把处理机分配给就绪队列中的一个进程，使之执行。分配处理机的任务是由处理机调度程序完成的。由于处理机是最重要的计算机资源，提高处理机的利用率及改善系统性能（吞吐量、响应时间），在很大程度上取决于处理机调度性能的好坏，因而，处理机调度便成为操作系统设计的中心问题之一。 在多道程序系统中，一个作业被提交后必须经过处理机调度后，方能获得处理机执行。对于批量型作业而言，通常需要经历作业调度和进程调度两个过程后方能获得处理机。作业调度是对成批进入系统的用户作业，根据作业控制块的信息，按一定的策略选取若干个作业使它们可以去获得处理器运行的一项工作。而对每个用户来说总希望自己的作业的周转时间是最小的，短作业优先（SJF）便是其中一种调度方法。本次课程设计主要是模拟短作业优先(SJF)调度算法。 一、实验题目 采用短作业优先算法的的进程调度程序 二、课程设计的目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合一起，独立分析和解决实际问题的机会。 进一步巩固和复习操作系统的基础知识。 培养学生结构化程序、模块化程序设计的方法和能力。 提高学生调试程序的技巧和软件设计的能力。 提高学生分析问题、解决问题以及综合利用C语言进行程序设计的能力。 三、设计内容 设计并实现一个采用短作业优先算的进程调度算法演示程序 四、设计要求 1. 每一个进程有一个PCB，其内容可以根据具体情况设定。 2. 进程数、进入内存时间、要求服务时间、优先级等均可以在界面上设定 3. 可读取样例数据（要求存放在外部文件中）进行进程数、进入内存时间、时间片长度、进程优先级的初始化 4. 可以在运行中显示各进程的状态：就绪、执行（由于不要求设置互斥资源与进程间同步关系，故只有两种状态） 5. 采用可视化界面，可在进程调度过程中随时暂停调度，查看当前进程的状态以及相应的阻塞队列 湖南工业大学 课程设计 资料袋 计算机与通信学院学院（系、部）20 08 ~ 20 09 学年第一学期课程名称操作系统指导教师职称讲师 学生姓名专业班级学号06408100139 题目磁盘调度算法的实现与分析 成绩起止日期2008 年12 月24 日～2009 年01 月06日 目录清单 序号材料名称资料数量备注 1 课程设计任务书 1 2 课程设计说明书 1 3 课程设计图纸 1 9 张4 5 6 湖南工业大学 课程设计任务书 2008 —2009 学年第1 学期 计算机与通信学院学院（系、部）专业班级 课程名称：操作系统 设计题目：磁盘调度算法的实现与分析 完成期限：自2008 年12 月24 日至2009 年01 月06 日共 2 周 内容及任务一、设计的主要技术参数 二、设计任务 1.先来先服务算法(FCFS) 2.最短寻道时间优先算法(SSTF) 3.扫描算法(SCAN) 4.循环扫描算法(CSCAN) 三、设计工作量 通过两周的时间进行设计、编码、测试、运行、书写实验报告。 进度安排 起止日期工作内容 2008-12-24至2008-12-27数据结构设计 2008-12-28至2008-12-30编写代码 2008-12-31至2009-01-01调试运行、修改 2009-01-02至2009-01-06得出最终程序、撰写实验报告 主要参考资料[1] 袁庆龙，候文义．Ni-P合金镀层组织形貌及显微硬度研究［Ｊ］．太原理工 大学学报，2001，32(1)：51-53. [2] 刘国钧，王连成．图书馆史研究［Ｍ］．北京：高等教育出版社，1979：15-18， 31 [3] 孙品一．高校学报编辑工作现代化特征［Ｃ］．中国高等学校自然科学学报研究会．科技编辑学论文集(2)．北京：北京师范大学出版社，1998：10-22 指导教师（签字）：年月日 系（教研室）主任（签字）：年月日 #include void input() {int i; printf("请输入进程数："); scanf("%d",&J); for(i=0;i 人和以吟实验报告学院（系）名称：计算机与通信工程学院 【实验过程记录(源程序、测试用例、测试结果及心得体会等) 】 #include 负载调度算法 负载均衡（Load Balance），又称为负载分担，就是将负载（工作任务）进行平衡、分摊到多个操作单元上进行执行，例如Web服务器、FTP服务器、企业关键应用服务器和其它关键任务服务器等，从而共同完成工作任务。负载均衡建立在现有网络结构之上，它提供了一种廉价又有效的方法来扩展网络设备和服务器的带宽、增加吞吐量、加强网络数据处理能力、提高网络的灵活性和可用性。 在调度器的实现技术中，IP负载均衡技术是效率最高的。在已有的IP负载均衡技术中有通过网络地址转换（Network Address Translation）将一组服务器构成一个高性能的、高可用的虚拟服务器，称之为VS/NAT技术。在分析VS/NAT 的缺点和网络服务的非对称性的基础上，提出通过IP隧道实现虚拟服务器的方法VS/TUN，和通过直接路由实现虚拟服务器的方法VS/DR，它们可以极大地提高系统的伸缩性。 在内核中的连接调度算法上，IPVS实现了以下几种调度算法： 1 轮叫调度 1.1 轮叫调度含义 轮叫调度（Round Robin Scheduling）算法就是以轮叫的方式依次将请求调度不同的服务器，即每次调度执行i = (i + 1) mod n，并选出第i台服务器。算法的优点是其简洁性，它无需记录当前所有连接的状态，所以它是一种无状态调度。 轮叫是基站为终端分配带宽的一种处理流程，这种分配可以是针对单个终端或是一组终端的。为单个终端和一组终端连接分配带宽，实际上是定义带宽请求竞争机制，这种分配不是使用一个单独的消息，而是上行链路映射消息中包含的一系列分配机制。 1.2 轮叫调度算法流程 轮询调度算法的原理是每一次把来自用户的请求轮流分配给内部中的服务器，从1开始，直到N（内部服务器个数），然后重新开始循环。在系统实现时，我们引入了一个额外条件，即当服务器的权值为零时，表示该服务器不可用而不被调度。这样做的目的是将服务器切出服务（如屏蔽服务器故障和系统维护），同时与其他加权算法保持一致。所以，算法要作相应的改动，它的算法流程如下：假设有一组服务器S = {S0, S1, …, Sn-1}，一个指示变量i表示上一次选择的服务器，W(Si)表示服务器Si的权值。变量i被初始化为n-1，其中n > 0。 j = i; do { j = (j + 1) mod n; 操作系统实验 （第三次） 一、实验内容 模拟电梯调度算法，实现对磁盘的驱动调度。 二、实验目的 磁盘是一种高速、大容量、旋转型、可直接存取的存储设备。它作为计算机系统的辅 助存储器，担负着繁重的输入输出任务、在多道程序设计系统中，往往同时会有若干个要求访问磁盘的输入输出请求等待处理。系统可采用一种策略，尽可能按最佳次序执行要求访问磁盘的诸输入输出请求。这就叫驱动调度，使用的算法称为驱动调度算法。驱动调度能降低为若干个输入输出请求服务所需的总时间，从而提高系统效率。本实验要求学生模拟设计一个驱动调度程序，观察驱动调度程序的动态运行过程。通过实验使学生理解和掌握驱动调度的职能。 三、实验题目 模拟电梯调度算法，对磁盘进行移臂和旋转调度。 [提示]： （1）磁盘是可供多个进程共享的存储设备，但一个磁盘每时刻只能为一个进程服务。 当有进程在访问某个磁盘时，其他想访问该磁盘的进程必须等待，直到磁盘一次工作结束。当有多个进程提出输入输出要求而处于等待状态时，可用电梯调度算法从若干个等待访问者中选择一个进程，让它访问磁盘。选择访问者的工作由“驱动调度”进程来完成。 由于磁盘与处理器是可以并行工作的、所以当磁盘在作为一个进程服务时，占有处理 器的另一进程可以提出使用磁盘的要求，也就是说，系统能动态地接收新的输入输出请求。为了模拟这种情况，在本实验中设置了一个“接收请求”进程。 “驱动调度”进程和“接收请求”进程能否占有处理器运行，取决于磁盘的结束中断信 号和处理器调度策略。在实验中可用随机数来模拟确定这两个进程的运行顺序，以代替中断四、处理和处理器调度选择的过程。因而，程序的结构可参考图3—1 2015年10月21日 实验一 进程调度 1.实验目的： 通过对进程调度算法的模拟，进一步理解进程的基本概念，加深对进程运行状态和进程调度过程、调度算法的理解。 2.实验内容： （1）用C 语言（或其它语言，如Java ）实现对N 个进程采用某种进程调度算法（如先来先服务调度、短作业优先调度、优先权调度、时间片轮转调度、多级反馈队列调度）的调度。 （2）为了清楚地观察每个进程的调度过程，程序应将每个进程的被调度情况显示出来。 （3）分析程序运行的结果，谈一下自己的收获。 3.设计实现： 1）流程图 主流程图： choice!=1&&choice!=2 c hoice==2 c hoice==1 Y N 开 始 初始化参数 输入函数 输入chioce FCFS SJF 输入有误，请重新输入！ 是否继续？ 结束 输入函数流程图： 请输入进程个数：Num N Y i=0 N i=0 N 先来先服务流程图： i=0 N Y N Y 开始 Num>0&&Num<=100 i 短作业优先算法流程图： i =0 N i = 0 开始 计算第一次NowTime 和第一个进程的完成时间 输出 i 在多道程序环境下，主存中有着多个进程，其数目往往多过于处理机数目。这就要求系统能按某种算法，动态的把处理机分配给就绪队列中的一个进程，使之执行。 在OS中的调度的实质是一种资源分配，因而调度算法是指：根据系统的资源分配策略所规定的资源分配算法。对于不同的系统和系统目标，通常采用不同的调度算法，目前存在的多种调度算法中，有的算法适用于作业电镀，有的算法适用于进程调度；但也有些调度算法即可用于作业调度，也可用于进程调度。 多级反馈队列调度算法是一种CPU处理机调度算法，它不必事先知道各种进程所需的执行时间，而且还可以满足各种类型进程的需要，因而它是目前被公认的一种较好的进程调度算法。 多级反馈队列调度算法的思想 设置多个就绪队列，并为各个队列赋予不同的优先级和不同长度的时间片；第一个队列的优先级最高，进程所执行时间片最小。 新创建的进程挂到第一优先级的队列后，然后按FCFS 原则排队等待调度。当轮到其执行时，如它能在时间片内完成，便撤离系统；如果不能完成，便被挂入第二级队列后，……； 仅当第一级队列空闲时，调度程序才调度第二级队列中的进程运行，依次类推……；新进程可抢占低级进程的处理机。 多级(假设为N级)反馈队列调度算法可以如下原理： 1、设有N个队列（Q1,Q2....QN），其中各个队列对于处理机的优先级是不一样的，也就是说位于各个队列中的作业(进程)的优先级也是不一 样的。一般来说，优先级Priority(Q1) > Priority(Q2) > ... > Priority(QN)。怎么讲，位于Q1中的任何一个作业(进程)都要比Q2中的任何一个作业(进程)相对于CPU的优先级要高（也就是说，Q1中的作业一定要比Q2中的作业先被处理机调度），依次类推其它的队列。 2、对于某个特定的队列来说，里面是遵循时间片轮转法。也就是说，位于队列Q2中有N个作业，它们的运行时间是通过Q2这个队列所设定的时间片来确定的（为了便于理解，我们也可以认为特定队列中的作业的优先级是按照FCFS来调度的）。 3、各个队列的时间片是一样的吗？不一样，这就是该算法设计的精妙之处。各个队列的时间片是随着优先级的增加而减少的，也就是说，优先级越高的队列中它的时间片就越短。同时，为了便于那些超大作业的完成，最后一个队列QN(优先级最低的队列)的时间片一般很大(不需要考虑这个 问题)。 多级反馈队列调度算法描述： 1、进程在进入待调度的队列等待时，首先进入优先级最高的Q1等待。 2、首先调度优先级高的队列中的进程。若高优先级中队列中已没有调度的进程，则调度次优先级队列中的进程。例如：Q1,Q2,Q3三个队列，只有在Q1中没有进程等待时才去调度Q2，同理，只有Q1,Q2都为空时才会去调度Q3。 3、对于同一个队列中的各个进程，按照时间片轮转法调度。比如Q1 队列的时间片为N，那么Q1中的作业在经历了N个时间片后若还没有完成，则进入Q2队列等待，若Q2的时间片用完后作业还不能完成，一直进入下一级队列，直至完成。 4、在低优先级的队列中的进程在运行时，又有新到达的作业，那么在运行完这个时间片后，CPU马上分配给新到达的作业（抢占式）。 我们来看一下该算法是如何运作的： 假设系统中有3个反馈队列Q1,Q2,Q3，时间片分别为2，4，8。 现在有3个作业J1,J2,J3分别在时间 0 ，1，3时刻到达。而它们所需要的CPU时间分别是3，2，1个时间片。 1、时刻0 J1到达。于是进入到队列1 ，运行1个时间片，时间片还未到，此时J2到达。 2、时刻1 J2到达。由于时间片仍然由J1掌控，于是等待。 J1在运行了1个时间片后，已经完成了在Q1中的 2个时间片的限制，于是J1置于Q2等待被调度。现在处理机分配给 J2。 3、时刻2 J1进入Q2等待调度，J2获得CPU开始运行。 4、时刻3 J3到达，由于J2的时间片未到，故J3在Q1等待调度，J1也在Q2等待调度。 操作系统 实验报告 哈尔滨工程大学 计算机科学与技术学院 第六讲磁盘调度算法 一、实验概述 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 目录 一、课设简介 (3) 1. 课程设计题目 (3) 2. 课程设计目的 (3) 3. 课程设计的内容 (3) 4. 课程设计要求 (3) 二、原理分析 (4) 1. 先来先服务算法介绍与分析 (4) 2. 短作业优先算法介绍与分析 (4) 3. 高响应比优先调度算法介绍与分析 (4) 4. 流程图 (5) 三、主要功能模块 (7) 1. 先来先服务算法实现代码 (7) 2. 短作业优先算法实现代码 (8) 3. 高响应比优先调度算法实现代码 (8) 四、测试与运行结果 (9) 1. 主界面 (9) 2. 先来先服务算法测试 (10) 3. 短作业优先算法测试 (11) 4. 高响应比优先调度算法测试 (13) 五、总结 (16) 六、参考文献 (16) 七、附录 (16) 一、课设简介 1.课程设计题目 经典调度算法的实现 2.课程设计目的 操作系统课程设计是计算机专业重要的教学环节，它为学生提供了一个既动手又动脑，将课本上的理论知识和实际有机的结合起来，独立分析和解决实际问题的机会。 ●进一步巩固和复习操作系统的基础知识。 ●培养学生结构化程序、模块化程序设计的方法和能力。 ●提高学生调试程序的技巧和软件设计的能力。 ●提高学生分析问题、解决问题以及综合利用 C 语言进行程序设计的能力。 3.课程设计的内容 实现以下几种调度算法 1 FCFS 2 SJF 3 高响应比优先调度算法。 4.课程设计要求 1．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 2．对系统进行功能模块分析、画出总流程图和各模块流程图。 3．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单。 4．通过命令行相应选项能直接进入某个相应菜单选项的功能模块。 5．所有程序需调试通过。 磁盘调度算法 -电脑资料 2019-01-01 磁盘优点 容量很大每位的价格非常低当关掉电源后存储信息不丢失 物理特性 磁盘表面覆盖着磁性物质，信息记录在磁表面上， 。固定头磁盘的每个磁道单独有一个磁头，这样就能使得计算机可以很快地从一个磁道转换到另一个磁道。但是这需要大量的头，设备成本很高。更通用的方式是每个盘面只有一个头，让它从一道移向另一道。这种动头设备需要硬件设备移动头。 磁盘一般用于文件存储，设计原则是：成本低、容量大、速度高。扩大存储容量：a.增加每英寸磁道数目; b. 双面记录。 存取盘块中的信息一般要有三部分时间：系统首先要把磁头移到相应的道上或柱面上，这个时间叫做寻道时间;一旦磁头到达指定磁道，必须等待所需要的扇区转到读/写头下，这个延迟时间叫做旋转延迟时间;最后，信息实际在磁盘和内存之间进行传送也要花费时间，这部分时间叫做传送时间。一次磁盘服务的总时间就是这三者之和。 要使磁盘服务尽可能地快，操作系统要提供合适的调度算法，改善磁盘服务的平均时间。 进程需要和磁盘交换信息时必须要操作系统发出系统调用，对磁盘的请求一般要有下述几部分内容： 1. 输入和输出; 2. 磁盘地址（驱动器、柱面、面号、扇区）; 3. 内存地址; 4. 传送长度。 磁盘调度算法 1、先来先服务调度（FCFS） FCFS 算法是优先为最先到达的请求服务。例如，有如下请求磁盘服务队列，要访问的磁道数分别是： 98，183，37，122，14，124，65，67 排在前面的是先到达的请求，假设磁头目前停留在53磁道上，按照先来先服务的算法，接下来磁头的移动顺序依次是： 53—>98—>183—>37—>122—>14—>124—>65—>67 这个过程总共移动了（98-53）+（183-98）+（183-37）+（122-37）+（122-14）+（124-14）+（124-65）+（67-65）=640个磁道 这种调度法产生的磁头移动服务太大，磁头频繁的大幅度移动，容易产生机械振动和误差，对使用寿命有损害。所以，要设计好的算法来减少磁头移动幅度，减少服务时间，改善磁盘的吞吐量。 2、最短寻道时间优先法（SSTF） ??优先服务接近于磁头当前位置的请求。SSTF从本质上将是SJF（最短作业优先算法）调度的形式。使用SSTF调度算法，上面那个请求队列的执行顺序是： ??53—>65—>67—>37—>14—>98—>122—>124—>183 总共移动了236个磁道，比FCFS的三分之一多一点，明显改善了磁盘服务， 《》()。 ??但是这种算法并不是最优的。例如，若把磁头从53道移动到37道（尽管不是靠的最近的），然后移动到14，接下去是65，67，98，122，124，183，总共移动了208个磁道<236。 ??SSTF也可能导致某些请求长期得不到服务（即“饥饿”问题）。如果当前磁头附近总会不断的到来新的请求，那么距离磁头远的请求将会一直等待下去。 3、扫描法（SCAN） 由于请求服务的队列具有动态性质，总会有新的请求到达，因此可采用扫描算法。读/写磁头从磁盘的一端出发，向另一端移动，遇到所需的磁道时就 磁盘调度算法 学生姓名: 学生学号: 专业班级: 指导老师： 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、概要设计 说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。操作系统实验报告—磁盘调度算法
操作系统磁盘调度算法实验报告
多级反馈队列调度算法的实现
操作系统磁盘调度算法实验报告
作业6--磁盘驱动调度-答案
加权公平队列调度算法
操作系统短作业优先调度算法
磁盘调度算法
多级反馈队列调度算法
天津理工大学操作系统实验3：磁盘调度算法的实现
负载均衡调度算法
模拟电梯调度算法,实现对磁盘的驱动调度。
调度算法
操作系统论文-----多级反馈队列调度算法
操作系统实验 磁盘调度算法
经典调度算法的实现
磁盘调度算法-电脑资料.
磁盘调度算法实验报告 (2)
相关主题
文本预览