操作系统实验报告 时间片轮转调度算法

“网络协议分析”实验4

实验名称：用Ethereal研究DNS和HTTP协议

实验目的：通过对捕获分组的分析和研究，加深对DNS协议和HTTP协议的工作原理和实现过程的理解。

实验环境：连网PC机，Ethereal网络协议分析软件

实验步骤：

1．安装Ethereal网络协议分析器。

2．打开Ethereal软件菜单中的Help->Contents，可学习Ethereal的使用方法。

3．开始捕获分组之前，清空客户端Web浏览器的高速缓存和DNS的高速缓存（命令为：ipconfig /flushdns）。（想一想，为什么？）

4．在Capture->Option里选择网卡类型；取消捕获分组的“混杂模式”；设置捕获过滤器为：“host 本机IP”，这样Ethereal就会只捕获从本机发出的和

发往本机的分组。

5．点击Start启动协议分析器，用Ethereal捕获从本机发出和发往本机的分组。

6．在Web浏览器中输入URL（如https://www.wendangku.net/doc/a04975215.html,, https://www.wendangku.net/doc/a04975215.html,等，网页较简单）。网页显示出来后，过一会儿停止捕获。将跟踪文件保存在一

个文件中。

实验结果分析：

1．在跟踪列表框中找出请求网页时发出的DNS查询报文和回答报文，找出发起TCP连接的三次握手报文，找出HTTP请求报文和响应报文。

2．在协议框中找出各层协议，观察各层协议，并对照教材中DNS查询/回答报文结构和HTTP请求/响应报文结构对这些应用层报文进行分析，找出报文中各字段相应的内容，解释其含义和用途。

3．你的主机所用的DNS服务器的IP地址是多少？你的浏览器与DNS服务器之间使用传输层的什么协议进行通信？

202.196.0.1

DNS请求报文和应答报文的ID号一样吗？是什么？

一样，0xc4a6

你所请求网站的规范名是什么？

https://www.wendangku.net/doc/a04975215.html,

DNS服务器对你的域名解析请求在应答中给出了几个可用的IP地址？都是什么？

2个，202.196.0.16，202.196.0.17

和DNS服务器通信时，你的客户机使用的端口号是多少？DNS服务器使用的端口号是多少？

64384，53

你所请求Web服务器的IP地址是什么？其域名有几个层次（参看教材127页）？

202.196.0.16 4个

如果请求一个存在/不存在的网页，Web服务器分别会应答什么？

……等等。请自己在所获取的分组中找到尽可能多的信息。

4．点击statistic下的summary，查看跟踪记录的统计概要。

实验要求：

1．实验完毕，提交实验报告（请在报告名中注上学号、姓名及实验序号）。报告中请写明实验步骤、实验结果分析以及实验总结。

2．不来的同学，上机实验成绩扣除一半。

插入排序算法实验报告

算法设计与分析基础 实验报告 应用数学学院 二零一六年六月

实验一插入排序算法 一、实验性质设计 二、实验学时14学时 三、实验目的 1、掌握插入排序的方法和原理。 2、掌握java语言实现该算法的一般流程。 四、实验内容 1、数组的输入。 2、输入、输出的异常处理。 3、插入排序的算法流程。 4、运行结果的输出。 五、实验报告 Ⅰ、算法原理 从左到右扫描有序的子数组，直到遇到一个大于（或小于）等于A[n-1]的元素，然后就把A[n-1]插在该元素的前面（或后面）。 插入排序基于递归思想。 Ⅱ、书中源代码 算法InsertionSort（A[0..n-1]） //用插入排序对给定数组A[0..n-1]排序 //输入：n个可排序元素构成的一个数组A[0..n-1] //输出：非降序排列的数组A[0..n-1] for i ←1 to n-1 do v ← A[i] j ← i-1 while j ≥0and A[j] > v do A[j+1] ← A[j] j ← j-1 A[j+1] ← v

Ⅲ、Java算法代码： import java.util.*; public class Charu { public static void main(String[] args) { int n = 5; int a[] = new int[n]; int s = a.length; int i = 0, j = 0, v = 0; System.out.println("请输入若干个数字："); Scanner sc = new Scanner(System.in); try { while (i < s) { a[i] = sc.nextInt(); i++; } for (i = 1; i = 0 && a[j] > v) { a[j + 1] = a[j]; j--; } a[j + 1] = v; } System.out.println("插入排序结果显示："); for (i = 0; i < s; i++) { System.out.println(a[i]); } } catch (Exception es) { System.out.println(es); } } } Ⅳ、运行结果显示：

进程调度算法实验报告

操作系统实验报告（二） 实验题目：进程调度算法 实验环境：C++ 实验目的：编程模拟实现几种常见的进程调度算法，通过对几组进程分别使用不同的调度算法，计算进程的平均周转时间和平均带权周转时间，比较 各种算法的性能优劣。 实验内容：编程实现如下算法： 1.先来先服务算法； 2.短进程优先算法； 3.时间片轮转调度算法。 设计分析： 程序流程图： 1.先来先服务算法 开始 初始化PCB，输入进程信息 各进程按先来先到的顺序进入就绪队列 结束 就绪队列？ 运行 运行进程所需CPU时间 取消该进程 2.短进程优先算法

3.时间片轮转调度算法 实验代码： 1.先来先服务算法 #include #define n 20 typedef struct { int id; //进程名

int atime; //进程到达时间 int runtime; //进程运行时间 }fcs; void main() { int amount,i,j,diao,huan; fcs f[n]; cout<<"请输入进程个数:"<>amount; for(i=0;i>f[i].id; cin>>f[i].atime; cin>>f[i].runtime; } for(i=0;if[j+1].atime) {diao=f[j].atime; f[j].atime=f[j+1].atime; f[j+1].atime=diao; huan=f[j].id; f[j].id=f[j+1].id; f[j+1].id=huan; } } } for(i=0;i #define n 5 #define num 5 #define max 65535 typedef struct pro { int PRO_ID; int arrive_time;

时间片轮转调度算法资料

《操作系统》课程实验报告实验名称：时间片轮转调度算法 班级：**************** 学号：************* 姓名：************** 指导老师：*************** 成绩：

一、实验目的： 1、测试数据可以随即输入或从文件中读入。 2、必须要考虑到进程的到达时间 3、最终能够计算每一个进程的周转时间的带权周转时间。 4、时间片大小可以不为1，但至少实现时间片大小为1的RR调度。 二、实验内容： 模拟实现时间片轮转调度算法，具体如下： 设置进程体：进程名，进程的到达时间，服务时间，，进程状态（W——等待,R ——运行,F——完成），进程间的链接指针 进程初始化：由用户输入进程名、服务时间进行初始化，同时，初始化进程的状态为W。 显示函数：在进程调度前、调度中和调度后进行显示。 排序函数：对就绪状态的进程按照进入就绪队列的时间排序，新到达的进行应优先于刚刚执行过的进程进入就绪队列的队尾。 调度函数：每次从就绪队列队首调度优一个进程执行，状态变化。并在执行一个时间片后化，服务时间变化，状态变化。当服务时间为0时，状态 变为F。 删除函数：撤销状态为F的进行。 三、实验代码 #include #include #include typedefstruct PCB2 { char name[10];//进程名 int runtime;//要求运行时间 intfrist;//定义优先数 char zhuangtai; //定义状态，R为就绪，F为完成 }; structshijian {//定义时间片的结构体 char name; //定义进程名 intdaodatime;// 到达时间 intfuwutime; //服务时间 intshengyutime;//剩余时间 char *state;//所处状态 structshijian *next; }; structshijian *time() { inta,i;

《数据结构》实验报告——排序.docx

《数据结构》实验报告排序实验题目： 输入十个数，从插入排序，快速排序，选择排序三类算法中各选一种编程实现。 实验所使用的数据结构内容及编程思路： 1. 插入排序：直接插入排序的基本操作是，将一个记录到已排好序的有序表中，从而得到一个新的，记录增一得有序表。 一般情况下，第i 趟直接插入排序的操作为：在含有i-1 个记录的有序子序列r[1..i-1 ]中插入一个记录r[i ]后，变成含有i 个记录的有序子序列r[1..i ]；并且，和顺序查找类似，为了在查找插入位置的过程中避免数组下标出界，在r [0]处设置哨兵。在自i-1 起往前搜索的过程中，可以同时后移记录。整个排序过程为进行n-1 趟插入，即：先将序列中的第一个记录看成是一个有序的子序列，然后从第2 个记录起逐个进行插入，直至整个序列变成按关键字非递减有序序列为止。 2. 快速排序：基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序的序列为{L.r[s] ,L.r[s+1],…L.r[t]}, 首先任意选取一个记录 （通常可选第一个记录L.r[s]）作为枢轴（或支点）（PiVOt ）,然后按下述原则重新排列其余记录：将所有关键字较它小的记录都安置在它的位置之前，将所有关键字较大的记录都安置在它的位置之后。由此可以该“枢轴”记录最后所罗的位置i 作为界线，将序列{L.r[s] ，… ，L.r[t]} 分割成两个子序列{L.r[i+1],L.[i+2], …,L.r[t]}。这个过程称为一趟快速排序，或一次划分。 一趟快速排序的具体做法是：附设两个指针lOw 和high ，他们的初值分别为lOw 和high ，设枢轴记录的关键字为PiVOtkey ，则首先从high 所指位置起向前搜索找到第一个关键字小于PiVOtkey 的记录和枢轴记录互相交换，然后从lOw 所指位置起向后搜索，找到第一个关键字大于PiVOtkey 的记录和枢轴记录互相 交换，重复这两不直至low=high 为止。 具体实现上述算法是，每交换一对记录需进行3 次记录移动(赋值)的操作。而实际上，

先来先服务FCFS和短作业优先SJF进程调度算法_实验报告材料

先来先服务FCFS和短作业优先SJF进程调度算法 1、实验目的 通过这次实验，加深对进程概念的理解，进一步掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。 2、需求分析 (1) 输入的形式和输入值的范围 输入值：进程个数Num 范围：0

说明本程序中用到的所有抽象数据类型的定义、主程序的流程以及各程序模块之间的层次(调用)关系。 4、详细设计 5、调试分析 (1)调试过程中遇到的问题以及解决方法，设计与实现的回顾讨论和分析 ○1开始的时候没有判断进程是否到达，导致短进程优先算法运行结果错误，后来加上了判断语句后就解决了改问题。 ○2 基本完成的设计所要实现的功能，总的来说，FCFS编写容易，SJF 需要先找到已经到达的进程，再从已经到达的进程里找到进程服务时间最短的进程，再进行计算。 (2)算法的改进设想 改进：即使用户输入的进程到达时间没有先后顺序也能准确的计算出结果。（就是再加个循环，判断各个进程的到达时间先后，组成一个有序的序列） (3)经验和体会 通过本次实验，深入理解了先来先服务和短进程优先进程调度算法的思想，培养了自己的动手能力，通过实践加深了记忆。 6、用户使用说明 （1）输入进程个数Num

处理器调度(设计一个按时间片轮转法实现处理器调度的程序)

实验一处理器调度 一、实验容 选择一个调度算法，实现处理器调度。 二、实验目的 在采用多道程序设计的系统中，往往有若干个进程同时处于就绪状态。当就绪进程个数大于处理器数时，就必须依照某种策略来决定哪些进程优先占用处理器。本实习模拟在单处理器情况下的处理器调度，帮助学生加深了解处理器调度的工作。 三、实验题目 设计一个按时间片轮转法实现处理器调度的程序。 [提示]： (1)假定系统有五个进程，每一个进程用一个进程控制块PCB来代表。进程控制块的 格式为： 其中，Q1，Q2，Q3，Q4，Q5。 指针——进程按顺序排成循环队列，用指针指出下一个进程的进程控制块的首地址最后一个进程的指针指出第一个进程的进程控制块首地址。 要求运行时间——假设进程需要运行的单位时间数。 已运行时间——假设进程已经运行的单位时间数，初始值为“0”。 状态——有两种状态，“就绪”和“结束”，初始状态都为“就绪”，用“R”表示。 当一个进程运行结束后，它的状态为“结束”，用“E”表示。 (2) 每次运行所设计的处理器调度程序前，为每个进程任意确定它的“要求运行时间”。 (3) 把五个进程按顺序排成循环队列，用指针指出队列连接情况。另用一标志单元记录轮到运行的进程。例如，当前轮到P2执行，则有： 标志单元 K1 K2 K 3 K4 K5

(4)处理器调度总是选择标志单元指示的进程运行。由于本实习是模拟处理器调度的 功能，所以，对被选中的进程并不实际的启动运行，而是执行： 已运行时间+1 来模拟进程的一次运行，表示进程已经运行过一个单位的时间。 请同学注意：在实际的系统中，当一个进程被选中运行时，必须置上该进程可以运行的时间片值，以及恢复进程的现场，让它占有处理器运行，直到出现等待事件或运行满一个时间片。在这时省去了这些工作，仅用“已运行时间+1”来表示进程已 经运行满一个时间片。 (5)进程运行一次后，应把该进程的进程控制块中的指针值送到标志单元，以指示下一 个轮到运行的进程。同时，应判断该进程的要求运行时间与已运行时间，若该进程的要求运行时间 已运行时间，则表示它尚未执行结束，应待到下一轮时再运行。若该进程的要求运行时间=已运行时间，则表示它已经执行结束，应指导它的状态修改成“结束”（E）且退出队列。此时，应把该进程的进程控制块中的指针值送到前 面一个进程的指针位置。 (6)若“就绪”状态的进程队列不为空，则重复上面的（4）和（5）的步骤，直到所有 的进程都成为“结束”状态。 (7)在所设计的程序中应有显示或打印语句，能显示或打印每次选中进程的进程名以及 运行一次后进程队列的变化。 (8)为五个进程任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示 或打印逐次被选中的进程名以及进程控制块的动态变化过程。 四. 所用数据结构及符号说明 typedef struct PNode//PCB { struct PNode *next; //定义指向下一个节点的指针 char name[10]; //定义进程名，并分配空间 int All_time; //定义总运行时间 int Runed_Time; //定义已运行时间 char state; //定义进程状态Ready/End } *Proc; //指向该PCB的指针 int ProcNum; //总进程数

算法排序问题实验报告

《排序问题求解》实验报告 一、算法的基本思想 1、直接插入排序算法思想 直接插入排序的基本思想是将一个记录插入到已排好序的序列中，从而得到一个新的，记录数增1 的有序序列。 直接插入排序算法的伪代码称为InsertionSort，它的参数是一个数组A[1..n]，包含了n 个待排序的数。用伪代码表示直接插入排序算法如下： InsertionSort (A) for i←2 to n do key←A[i] //key 表示待插入数 //Insert A[i] into the sorted sequence A[1..i-1] j←i-1 while j>0 and A[j]>key do A[j+1]←A[j] j←j-1 A[j+1]←key 2、快速排序算法思想 快速排序算法的基本思想是，通过一趟排序将待排序序列分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可对这两部分记录继续进行排序，以达到整个序列有序。 假设待排序序列为数组A[1..n]，首先选取第一个数A[0]，作为枢轴（pivot），然后按照下述原则重新排列其余数：将所有比A[0]大的数都排在它的位置之前，将所有比A[0] 小的数都排在它的位置之后，由此以A[0]最后所在的位置i 作为分界线，将数组A[1..n]分成两个子数组A[1..i-1]和A[i+1..n]。这个过程称作一趟快速排序。通过递归调用快速排序，对子数组A[1..i-1]和A[i+1..n]排序。 一趟快速排序算法的伪代码称为Partition,它的参数是一个数组A[1..n]和两个指针low、high,设枢轴为pivotkey，则首先从high 所指位置起向前搜索，找到第一个小于pivotkey 的数，并将其移到低端，然后从low 所指位置起向后搜索，找到第一个大于pivotkey 的数，并将其移到高端，重复这两步直至low=high。最后，将枢轴移到正确的位置上。用伪代码表示一趟快速排序算法如下： Partition ( A, low, high) A[0]←A[low] //用数组的第一个记录做枢轴记录 privotkey←A[low] //枢轴记录关键字 while low=privotkey do high←high-1 A[low]←A[high] //将比枢轴记录小的记录移到低端 while low

作业调度实验报告

作业调度实验报告 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT

实验二作业调度 一.实验题目 1、编写并调试一个单道处理系统的作业等待模拟程序。 作业调度算法：分别采用先来先服务（FCFS），最短作业优先（SJF）、响应比高者优先（HRN）的调度算法。 （1）先来先服务算法：按照作业提交给系统的先后顺序来挑选作业，先提交的先被挑选。 （2）最短作业优先算法：是以进入系统的作业所提出的“执行时间”为标准，总是优先选取执行时间最短的作业。 （3）响应比高者优先算法：是在每次调度前都要计算所有被选作业（在后备队列中）的响应比，然后选择响应比最高的作业执行。 2、编写并调度一个多道程序系统的作业调度模拟程序。 作业调度算法：采用基于先来先服务的调度算法。可以参考课本中的方法进行设计。 对于多道程序系统，要假定系统中具有的各种资源及数量、调度作业时必须考虑到每个作业的资源要求。 二.实验目的： 本实验要求用高级语言（C语言实验环境）编写和调试一个或多个作业调度的模拟程序，了解作业调度在操作系统中的作用，以加深对作业调度算法的理解三 .实验过程 <一>单道处理系统作业调度 1)单道处理程序作业调度实验的源程序: 执行程序: 2)实验分析：

1、由于在单道批处理系统中，作业一投入运行，它就占有计算机的一切资源直到作业完成为止，因此调度作业时不必考虑它所需要的资源是否得到满足，它所占用的 CPU 时限等因素。 2、每个作业由一个作业控制块JCB 表示，JCB 可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W 。 3、对每种调度算法都要求打印每个作业开始运行时刻、完成时刻、周转时间、带权周转时间，以及这组作业的平均周转时间及带权平均周转时间。 3)流程图: 二.最短作业优先算法 三.高响应比算法 图一.先来先服务流程图 4)源程序: #include <> #include <> #include <> #define getpch(type) (type*)malloc(sizeof(type)) #define NULL 0 int n; float T1=0,T2=0; int times=0; struct jcb .\n",p->name); free(p); .wait...",time); if(times>1000) 代替 代替

时间片轮转调度算法

#include #include #include #include /*进程控制块数据结构*/ typedef struct node { char name[10];/*进程名*/ int prio; /*进程优先级*/ int round; /*循环轮转法进程每次轮转的时间片*/ int cputime; /*进程累计消耗的CUP时间*/ int needtime; /*进程到完成还需要的CUP时间*/ int count; /*循环轮转法一个时间片内进程运行时间*/ char state; /*进程的状态：'R':运行,'W'：等待,'F'：结束*/ struct node *next;/*指向下一个进程的链指针*/ }PCB; PCB *finish,*ready,*tail,*run;/*指向三个队列的队首的指针， finish为完成队列头指针， ready为就绪队列头指针， tail为就绪队列的队尾指针， run为当前运行进程头指针*/ int N;/*定义进程的数目*/ void firstin(void); //调度就绪队列的第一个进程投入运行； void print1(char a); //打印表头行信息 void print2(char chose,PCB *p); //打印每一行的状态信息 void print(char chose); //打印每执行一次算法后所有的进程的状态信息 void insert_prio(PCB *q); //在优先数算法中,将尚未完成的PCB按优先数顺序插入到就绪队列中； void prior_init(char chose); //进程优先级法初始化将进程按优先级插入到就绪队列里 void priority(char chose); //进程优先级算法总函数 void insert_rr(PCB *q); //在轮转法中，将执行了一个时间片单位（为2），但尚未完成的进程的PCB，插到就绪队列的队尾； void roundrun_init(char chose); //循环轮转法初始化将就绪队列保存为FIFO队列 void roundrun(char chose); //循环轮转法总算法 void main()//主函数 {

各种排序实验报告

【一】需求分析 课程题目是排序算法的实现，课程设计一共要设计八种排序算法。这八种算法共包括：堆排序，归并排序，希尔排序，冒泡排序，快速排序，基数排序，折半插入排序，直接插入排序。 为了运行时的方便，将八种排序方法进行编号，其中1为堆排序，2为归并排序，3为希尔排序，4为冒泡排序，5为快速排序，6为基数排序，7为折半插入排序8为直接插入排序。 【二】概要设计 1.堆排序 ⑴算法思想：堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占有一个存储空间。将序列所存储的元素A[N]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的元素均不大于(或不小于)其左右孩子(若存在)结点的元素。算法的平均时间复杂度为O(N log N)。 ⑵程序实现及核心代码的注释： for(j=2*i+1; j<=m; j=j*2+1) { if(j=su[j]) break; su[i]=su[j]; i=j; } su[i]=temp; } void dpx() //堆排序 { int i,temp; cout<<"排序之前的数组为："<=0; i--) { head(i,N); } for(i=N-1; i>0; i--) {

temp=su[i]; su[i]=su[0]; su[0]=temp; head(0,i-1); } cout<<"排序之后的数组为："<

时间片轮转算法

一、实验目的 （1）在单处理器情况下按时间片轮转算法实现处理器调度，输出运行动态变化过程。 （2）通过算法的实现加深了解处理器调度的工作。 二、实验内容 输入实现处理器调度的几个进程信息，任意确定一组“要求运行时间”，启动所设计的处理器调度程序，显示逐次被选中进程的进程名以及进程控制块的动态变化过程。 三、实验步骤 1、任务分析： 时间片轮转的主要思想就是按顺序为每一个进程一次只分配一个时间片的时间。算法要完成的功能就是将各个进程按照时间片轮转运行的动态过程显示出来。时间片轮转算法的主要实现过程是首先为每一个进程创建一个进程控制块，定义数据结构，说明进程控制块所包含的内容，有进程名、进程所需运行时间、已运行时间和进程的状态以及指针的信息。实现的过程即运用指针指向某一个进程，判断当前的进程是否是就绪状态“r”，如果是，则为该进程分配一个时间片，同时，已运行时间加一且要求运行的时间减一，如此循环执行，当某一个进程的所需要运行的时间减少至0时，则将该进程的状态设置为“e”。然后，将指针指向下一个未运行完成的进程，重复判断，直至所有的进程都运行结束。 2、概要设计： （1）所用数据结构及符号说明 typedef struct PCB{ char name[10]; //进程名 struct PCB *next; //循环链指针 int need_time; //要求运行时间 int worked_time; //已运行时间，初始为0 char condition; //进程状态，只有“就绪”和“结束”两种状态 int flag; //进程结束标志，用于输出 }PCB; PCB *front,*rear; //循环链队列的头指针和尾指针 int N; //N为进程数 （2）主程序的流程图：

操作系统实验报告-作业调度

作业调度 一、实验目的 1、对作业调度的相关内容作进一步的理解。 2、明白作业调度的主要任务。 3、通过编程掌握作业调度的主要算法。 二、实验内容及要求 1、对于给定的一组作业, 给出其到达时间和运行时间，例如下表所示： 2、分别用先来先服务算法、短作业优先和响应比高者优先三种算法给出作业的调度顺序。 3、计算每一种算法的平均周转时间及平均带权周转时间并比较不同算法的优劣。

测试数据 workA={'作业名':'A','到达时间':0,'服务时间':6} workB={'作业名':'B','到达时间':2,'服务时间':50} workC={'作业名':'C','到达时间':5,'服务时间':20} workD={'作业名':'D','到达时间':5,'服务时间':10} workE={'作业名':'E','到达时间':12,'服务时间':40} workF={'作业名':'F','到达时间':15,'服务时间':8} 运行结果 先来先服务算法 调度顺序:['A', 'B', 'C', 'D', 'E', 'F'] 周转时间: 带权周转时间:

短作业优先算法 调度顺序:['A', 'D', 'F', 'C', 'E', 'B'] 周转时间: 带权周转时间:1. 响应比高者优先算法 调度顺序:['A', 'D', 'F', 'E', 'C', 'B'] 周转时间: 带权周转时间: 五、代码 #encoding=gbk workA={'作业名':'A','到达时间':0,'服务时间':6,'结束时间':0,'周转时间':0,'带权周转时间':0} workB={'作业名':'B','到达时间':2,'服务时间':50} workC={'作业名':'C','到达时间':5,'服务时间':20} workD={'作业名':'D','到达时间':5,'服务时间':10} workE={'作业名':'E','到达时间':12,'服务时间':40} workF={'作业名':'F','到达时间':15,'服务时间':8} list1=[workB,workA,workC,workD,workE,workF] list2=[workB,workA,workC,workD,workE,workF] list3=[workB,workA,workC,workD,workE,workF] #先来先服务算法 def fcfs(list): resultlist = sorted(list, key=lambda s: s['到达时间']) return resultlist #短作业优先算法 def sjf(list): time=0 resultlist=[] for work1 in list: time+=work1['服务时间'] listdd=[] ctime=0 for i in range(time): for work2 in list: if work2['到达时间']<=ctime: (work2) if len(listdd)!=0: li = sorted(listdd, key=lambda s: s['服务时间']) (li[0]) (li[0]) ctime+=li[0]['服务时间'] listdd=[]

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

武汉理工大学华夏学院课程设计报告书 课程名称：操作系统原理 题目：时间片轮转进程调度模拟算法的实现系名：信息工程系 专业班级：计算机1132班 姓名：李杰 学号： 10210413209 指导教师: 司晓梅 2015年 6 月 26日

武汉理工大学华夏学院信息工程系 课程设计任务书 课程名称：操作系统原理课程设计指导教师：司晓梅 班级名称：计算机1131-2 开课系、教研室：自动化与计算机 一、课程设计目的与任务 操作系统课程设计是《操作系统原理》课程的后续实践课程，旨在通过一周的实践训练， 加深学生对理论课程中操作系统概念，原理和方法的理解，加强学生综合运用操作系统原理、 Linux系统、C语言程序设计技术进行实际问题处理的能力，进一步提高学生进行分析问题 和解决问题的能力，包含系统分析、系统设计、系统实现和系统测试的能力。 学生将在指导老师的指导下，完成从需求分析，系统设计，编码到测试的全过程。 二、课程设计的内容与基本要求 1、课程设计题目 时间片轮转进程调度模拟算法的实现 2、课程设计内容 用c/c++语言实现时间片轮转的进程调度模拟算法。要求： 1．至少要有5个以上进程 2．进程被调度占有CPU后，打印出该进程正在运行的相关信息 提示: 时间片轮转调度算法中，进程调度程序总是选择就绪队列中的第一个进程，也就是说按照先来先服务原则调度，但一旦进程占用处理机则仅使用一个时间片。在使用完一个时间片后，进程还没有完成其运行，它必须释放出处理机给下一个就绪的进程，而被抢占的进程返回到就绪队列的末尾重新排队等待再次运行。 1）进程运行时，只打印出相关提示信息，同时将它已经运行的时间片加1就可以了。 2）为进程设计出PCB结构。PCB结构所包含的内容，有进程名、进程所需运行时间、已运行时间和进程的状态以及指针的信息等。 3、设计报告撰写格式要求： 1设计题目与要求 2 设计思想 3系统结构 4 数据结构的说明和模块的算法流程图 5 使用说明书（即用户手册）：内容包含如何登录、退出、读、写等操作说明 6 运行结果和结果分析（其中包括实验的检查结果、程序的运行情况）

算法排序问题实验报告

《排序问题求解》实验报告 一、算法得基本思想 1、直接插入排序算法思想 直接插入排序得基本思想就是将一个记录插入到已排好序得序列中,从而得到一个新得, 记录数增 1 得有序序列。 直接插入排序算法得伪代码称为InsertｉonＳorｔ，它得参数就是一个数组A[1、、n］,包含了n 个待排序得数。用伪代码表示直接插入排序算法如下: IｎsｅrtｉonＳｏｒt (Ａ) for i←2 tｏn ｄo ｋeｙ←Ａ[i］／/key 表示待插入数 //Ｉnsｅrt A［i] ｉnto ｔhｅsｏrteｄｓequence A［1、、i-１］ j←i-1 wｈｉｌe j＞0 ａnｄＡ[j]＞key do A[j＋１］←A［j］ j←j-1 Ａ[j+1］←keｙ 2、快速排序算法思想 快速排序算法得基本思想就是，通过一趟排序将待排序序列分割成独立得两部分，其中一 部分记录得关键字均比另一部分记录得关键字小,则可对这两部分记录继续进行排序,以达 到整个序列有序。 假设待排序序列为数组A[１、、n]，首先选取第一个数Ａ[0],作为枢轴(ｐｉvｏt)，然后按照下述原则重新排列其余数:将所有比Ａ[0]大得数都排在它得位置之前,将所有比 A[０]小得数都排在它得位置之后,由此以A[0]最后所在得位置i 作为分界线,将数组 A[1、、n]分成两个子数组Ａ［1、、i－1］与Ａ[ｉ+1、、n］。这个过程称作一趟快速排序。通过递归调用快速排序,对子数组A[1、、ｉ-1]与A[i＋1、、n]排序。 一趟快速排序算法得伪代码称为Paｒtｉtion，它得参数就是一个数组A[１、、n］与两个指针ｌoｗ、high,设枢轴为ｐｉvotｋeｙ，则首先从higｈ所指位置起向前搜索,找到第一个小于ｐivｏtｋey得数,并将其移到低端,然后从low 所指位置起向后搜索,找到第一个大于pivotkey 得数,并将其移到高端，重复这两步直至low=ｈigh。最后,将枢轴移到正确得位置上。用伪代码表示一趟快速排序算法如下: Partiｔｉｏn ( Ａ，low，higｈ) A[０］←A[low] ／／用数组得第一个记录做枢轴记录 priｖotkey←Ａ[low] //枢轴记录关键字 wｈile lｏw<ｈigh //从表得两端交替地向中间扫描 whｉle low＝pｒivotｋey do ｈｉｇh←higｈ-1 A［loｗ]←Ａ[high] //将比枢轴记录小得记录移到低端 ｗｈile low<ｈigh &＆A[ｌow］＜＝pivｏｔkｅｙ)dｏlow←lｏw+１ A[hｉｇｈ]←A[ｌoｗ] ／/将比枢轴记录大得记录移到高端

作业调度算法(先来先服务算法,短作业算法)

《操作系统》实验报告 题目：作业调度算法 班级：网络工程 姓名：朱锦涛 学号：E31314037

一、实验目的 用代码实现页面调度算法，即先来先服务（FCFS）调度算法、短作业优先算法、高响应比优先调度算法。通过代码的具体实现，加深对算法的核心的理解。 二、实验原理 1.先来先服务（FCFS）调度算法 FCFS是最简单的调度算法，该算法既可用于作业调度，也可用于进程调度。当在作业调度中采用该算法时，系统将按照作业到达的先后次序来进行调度，或者说它是优先考虑在系统中等待时间最长的作业，而不管该作业所需执行的时间的长短，从后备作业队列中选择几个最先进入该队列的作业，将它们调入内存，为它们分配资源和创建进程。然后把它放入就绪队列。 2.短作业优先算法 SJF算法是以作业的长短来计算优先级，作业越短，其优先级越高。作业的长短是以作业所要求的运行时间来衡量的。SJF算法可以分别用于作业和进程调度。在把短作业优先调度算法用于作业调度时，它将从外存的作业后备队列中选择若干个估计运行时间最短的作业，优先将它们调入内存。 3、高响应比优先调度算法

高响应比优先调度算法则是既考虑了作业的等待时间，又考虑了作业的运行时间的算法，因此既照顾了短作业，又不致使长作业等待的时间过长，从而改善了处理机调度的性能。 如果我们引入一个动态优先级，即优先级是可以改变的令它随等待的时间的延长而增加，这将使长作业的优先级在等待期间不断地增加，等到足够的时间后，必然有机会获得处理机。该优先级的变化规律可以描述为： 优先权 = （等待时间 + 要求服务时间）/要求服务时间 三、实验内容 源程序： #include #include #include struct work { i nt id; i nt arrive_time;

时间片轮转调度算法实验报告

xx大学操作系统实验报告 姓名：学号：班级： 实验日期： 实验名称：时间片轮转RR进程调度算法 实验二时间片轮转RR进程调度算法 1.实验目的：通过这次实验，理解时间片轮转RR进程调度算法的运行原理，进一步 掌握进程状态的转变、进程调度的策略及对系统性能的评价方法。 2.需求分析 (1) 输入的形式和输入值的范围； 输入：进程个数n 范围：0

(4) 测试数据，包括正确的输入及其输出结果和含有错误的输入及其输出结果。正确输入： 错误输入：

2、概要设计 所有抽象数据类型的定义： static int MaxNum=100 int ArrivalTime //到达时间 int ServiceTime //服务时间 int FinishedTime //结束时间 int WholeTime //周转时间 double WeightWholeTime //带权周转时间double AverageWT //平均周转时间double AverageWWT //平均带权周转时间主程序的流程: 变量初始化

排序算法实验报告

实验课程：算法分析与设计 实验名称：几种排序算法的平均性能比较（验证型实验） 实验目标： （1）几种排序算法在平均情况下哪一个更快。 （2）加深对时间复杂度概念的理解。 实验任务： （1）实现几种排序算法（selectionsort, insertionsort,bottomupsort,quicksort, 堆排序）。对于快速分类，SPLIT中的划分元素采用三者A(low)，A(high)，A((low+high)/2)中其值居中者。（2）随机产生20组数据（比如n=5000i，1≤i≤20）。数据均属于范围（0，105）内的整数。对于同一组数据，运行以上几种排序算法，并记录各自的运行时间（以毫秒为单位）。（3）根据实验数据及其结果来比较这几种分类算法的平均时间和比较次数，并得出结论。 实验设备及环境： PC；C/C++等编程语言。 实验主要步骤： (1)明确实验目标和具体任务； (2)理解实验所涉及的几个分类算法； (3)编写程序实现上述分类算法； (4)设计实验数据并运行程序、记录运行的结果； (5)根据实验数据及其结果得出结论； (6)实验后的心得体会。 一:问题分析（包括问题描述、建模、算法的基本思想及程序实现的技巧等）：1:随机生成n个0到100000的随机数用来排序的算法如下. for(int n=1000;n<20000;n+=1000) { int a[]=new int[n]; for(int i=0;i

FCFS和SJF进程调度算法实验报告

FCFS和SJF进程调度算法实验报告 【实验题目】：编写程序，实现FCFS和SJF算法，模拟作 业调度过程，加深对作业调度的理解。 【实验内容】 实现FCFS和SJF调度算法。 –数据结构设计（JCB，后备作业队列） –算法实现与模拟（排序、调度） –输出调度结果，展示调度过程并解释 【实验要求】 1. 设计作业控制块(JCB)的数据结构 –应包含实验必须的数据项，如作业ID、需要的服务时间、进入系 统时间、完成时间，以及实验者认为有必要的其他数据项。 2. 实现排序算法（将作业排队） –策略1：按“进入系统时间”对作业队列排序(FCFS) –策略2：按“需要的服务时间”对作业队列排序（SJF） 3. 实现调度过程模拟 （1）每个作业用一个JCB表示，如果模拟FCFS，按策略1将作业排队，如果模拟SJF，按策略2将作业排队（2）选择队首的作业，将其从后备队列移出 （3）（作业运行过程，在本实验中，无需实现，可认为后备队列的 作业一但被调度程序选出，就顺利运行完毕，可以进入第4步） （4）计算选中作业的周转时间 （5）进行下一次调度（去往第2步） 4.实现结果输出 –输出作业状态表，展示调度过程 ?初始作业状态（未调度时） ?每次调度后的作业状态 设计作业控制块(JCB)的数据结构 每个作业由一个作业控制块JCB表示，JCB可以包含如下信息：作业名、提交时间、所需的运行时间、所需的资源、作业状态、链指针等等。具体结构如下：typedef struct jcb{ char name[10]; /* 作业名*/ char state; /* 作业状态*/ int ts; /* 提交时间*/ float super; /* 优先权*/ int tb; /* 开始运行时间*/ int tc; /* 完成时间*/ float ti; /* 周转时间*/ float wi; /* 带权周转时间*/ int ntime; /* 作业所需运行时间*/ char resource[10]; /* 所需资源*/ struct jcb *next; /* 结构体指针*/ } JCB; JCB *p,*tail=NULL,*head=NULL; 作业的状态可以是等待W(Wait)、运行R(Run)和完成F(Finish)三种状态之一。每个作业的最初状态总是等待W。，组成一个后备队列等待，总是首先调度等待队列中队首的作业。