磁盘调度算法文档

1、精选优质文档-倾情为你奉上精选优质文档-倾情为你奉上专心-专注-专业专心-专注-专业精选优质文档-倾情为你奉上专心-专注-专业操作系统原理及应用课程设计报告磁盘调度算法 学院（系）： 计算机科学与工程学院 班 级： 37-5 学号 学生姓名： 时间： 从 2013 年 12 月16日 到 2013 年12月20日1、课程设计的目的本课程设计是学生学习完操作系统原理及应用课程后，进行的一次全面的综合训练，通过课程设计，让学生更好地掌握操作系统的原理及实现方法,加深对操作系统基础理论和重要算法的理解，加强学生的动手能力。2、课程设计的内容及要求编程序实现下述磁盘调度算法,并求出每种算法的平均寻道长

2、度：要求设计主界面以灵活选择某算法，且以下算法都要实现1、先来先服务算法（FCFS）2、最短寻道时间优先算法（SSTF）3、扫描算法（SCAN）4、循环扫描算法（CSCAN）3、实现原理磁盘是可供多个进程共享的设备，当有多个进程都要求访问磁盘时，应采用一种最佳调度算法，以使各进程对磁盘的平均访问时间最小。由于在访问磁盘的时间中，主要是寻道时间，因此，磁盘调度的目标是使磁盘的平均寻道时间最少。目前常用的磁盘调度算法有先来先服务、最短寻道时间优先、扫描和循环扫描等算法。其中，平均寻道长度（L）为所有磁道所需移动距离之和除以总的所需访问的磁道数（N），即：L=（M1+M2+Mi+MN）/N其中Mi为

3、磁头从上一各磁道到这个磁道所需移动的距离。4、算法1.先来先服务算法（FCFS）这是一种最简单的磁盘调度算法。它根据进程请求访问磁盘的先后次序进行调度。此算法只考虑访问者提出访问请求的先后次序，按照先后次序依次访问磁道号。移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。2.短寻道时间优先算法（SSTF）该算法选择这样的进程，其要求访问的磁道与当前磁头所在的磁道距离最近，以使每次的寻道时间最短，而不管访问者到来的先后次序。实现时可以先对磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，选择离自己最近的访问，每比较一次，当

4、前磁道号也跟着变化，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当数组里的最大值小于当前磁道号时，就逆序访问，此时移动距离的和就等于当前磁道号减去数组中最小数；当数组中最小的数大于当前磁道号时，就正序访问，此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。3.扫描算法（SCAN）SCAN 算法又称电梯调度算法。该算法先考虑磁头的移动方向，再考虑距离近的访问。所以可以对即将访问的磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，当磁头移动方向向磁道号增加的方向移动时，就先依次访问比当前磁道号大的数，再逆向访问比自己小的

5、数；当磁头移动方向是向磁道号减小的方向时就先访问比自己的小的，然后逆向访问比自己大的，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当数组里的最大值小于当前磁道号时，两种方向都是逆序对磁道号访问，此时移动距离的和就等于当前磁道号减去数组中最小数；当数组中最小的数大于当前磁道号时，两种方向都是正序对磁道号访问，此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所有移动距离之和除以磁道被访问的次数。4.循环扫描算法（CSCAN）CSCAN算法是在SCAN算法的基础上规定磁头单向移动，即扫描时要么向磁道号增加的方向的访问，要么向磁道号减小的方向访问。所以可以对即将访问的

6、磁道号进行从小到大排序保存在数组里，然后与当前磁道号比较，当磁头移动方向向磁道号增加的方向移动时，就先依次访问比当前磁道号大的数，再返回磁道最里面朝增加的方向访问比自己小的数；当磁头移动方向是向磁道号减小的方向时就先访问比自己的小的，然后返回到磁道最外层访问比自己大的，移动距离等于上一个被访问的磁道号减去当前访问的磁道号的绝对值。但当向磁道号增加的方向时，数组里的最大值小于当前磁道号或数组中最小的数大于当前磁道号时，都是正序访问；而当向磁道号减小的方向时，数组里的最大值小于当前磁道号或数组中最小的数大于当前磁道号时，都是逆序访问；此时移动距离的和等于数组中最大值减当前磁道号，平均寻道长度等于所

7、有移动距离之和除以磁道被访问的次数。5、程序中使用的数据结构及使用的变量说明和作用int cidao = new int1000;/将被访问的磁道号存入cidao数组int sum = 0;/求移动距离之和double avg = 0;/求平均寻道时间string str = txtnum.Text.Split(,);/从txtnum里面获取访问的磁道号int now = Convert.ToInt32(txtnow.Text);/获取当前的磁道号for (int i = 0; i str.Length; i+)/将获取的磁道号存入磁道号数组cidaoi = Convert.ToInt32(s

8、tri);private void btnFCFS_Click(object sender, EventArgs e)先来先服务FCFS算法private void btnSSTF_Click(object sender, EventArgs e)最短寻道时间优先SSTFprivate void btnSCANhigh_Click(object sender, EventArgs e)从里向外扫描private void btnSCANlow_Click(object sender, EventArgs e)从外向里扫描private void btnCSCANhigh_Click(objec

9、t sender, EventArgs e)从里向外循环扫描private void btnCSCANlow_Click(object sender, EventArgs e)从外向里循环扫描private void btnexit_Click(object sender, EventArgs e)退出窗体private void txtnum_KeyDown(object sender, KeyEventArgs e)快捷键Tab选择输入框关键算法实现流程图先来先服务FCFS算法：最短寻道时间算法：扫描算法：向磁道号增加的方向：从磁道号减小的方向：循环扫描算法： 从磁道号增加的方向：从磁道号

10、减小的方向：实现代码 / / 先来先服务FCFS / / / private void btnFCFS_Click(object sender, EventArgs e) txtresult.Clear();/清除显示 int cidao = new int1000;/被访问的磁道号数组 int sum = 0;/移动距离之和 double avg = 0;/平均寻道时间 string str = txtnum.Text.Split(,);/从txtnum里面获取访问的磁道号 int now = Convert.ToInt32(txtnow.Text);/当前的磁道号 for (int i =

11、 0; i str.Length; i+) /将获取的磁道号存入磁道号数组 cidaoi = Convert.ToInt32(stri); sum += Math.Abs(now - cidao0);/当前的磁道号减去磁道号数组中的第一个值取绝对值 for (int i = 0; i str.Length; i+) /输出FCFS磁盘调度结果 txtresult.Text = txtresult.Text + cidaoi + ,; for (int i = 0, j = 1; j str.Length; i+, j+) /累计总的移动距离 sum += Math.Abs(cidaoj - c

12、idaoi); avg = (double)sum / str.Length;/平均寻道长度 lblsum.Text = 总移动距离： + sum.ToString();/在Label中显示总移动距离 lblavg.Text = 平均寻道长度： + avg.ToString(0.00);/在Label中显示平均寻道时间 / / 最短寻道时间优先SSTF / / / private void btnSSTF_Click(object sender, EventArgs e) txtresult.Clear();/清除显示 int cidao = new int1000;/被访问的磁道号数组 in

13、t sum = 0;/移动距离之和 double avg = 0;/平均寻道时间 int temp;/中间变量 int k = 1; int m, n; string str = txtnum.Text.Split(,);/从txtnum里面获取访问的磁道号 int now = Convert.ToInt32(txtnow.Text);/当前的磁道号 for (int i = 0; i str.Length; i+) /将获取的磁道号存入磁道号数组 cidaoi = Convert.ToInt32(stri); /对磁道号进行从小到大排列 for (int i = 0; i str.Lengt

14、h; i+) for (int j = i + 1; j cidaoj) temp = cidaoi; cidaoi = cidaoj; cidaoj = temp; /数组的最后一个小于当前磁道号，则数组逆序输出，此时的移动距离之和等于当前磁道号减去最小的磁道号 if (cidaostr.Length - 1 = 0; i-) txtresult.Text = txtresult.Text + cidaoi + ,; sum = now - cidao0;/移动距离之和 /数组的第一个数大于当前磁道号，正序输出，此时的移动距离之和等于最大的磁道号减去当前磁道号 else if (cidao0

15、 = now) for (int i = 0; i str.Length; i+) txtresult.Text = txtresult.Text + cidaoi + ,; sum = cidaostr.Length - 1 - now;/移动距离之和 /当前磁道号的大小介于数组的最大值与最小值之间 else /k的初始值为，从数组的第二个数开始逐一与当前磁道号比较 while (cidaok = 0) & (n str.Length) /当前位置的前一个磁道号离当前磁道号近 if (now - cidaom) = (cidaon - now) txtresult.Text = txtres

16、ult.Text + cidaom + ,;/输出 sum += now - cidaom;/移动距离之和 now = cidaom;/当前磁道号改变 m = m - 1;/与数组的前半部分比较 /当前位置的后一个磁道号离当前磁道号近 else txtresult.Text = txtresult.Text + cidaon + ,; ;/输出 sum += cidaon - now;/移动距离之和 now = cidaon;/当前磁道号改变 n = n + 1;/与数组的后半部分比较 /数组的第一个数比当前磁道号大 if (m = -1) for (int j = n; j = 0; j-)

17、/输出 txtresult.Text = txtresult.Text + cidaoj + ,; sum += cidaostr.Length - 1 - cidao0;/移动距离之和 avg = (double)sum / str.Length;/平均寻道长度 lblsum.Text = 总移动距离： + sum.ToString();/在Label中显示总移动距离 lblavg.Text = 平均寻道长度： + avg.ToString(0.00);/在Label中显示平均寻道时间 / / 磁道号增加的方向扫描 / / / private void btnSCANhigh_Click(o

18、bject sender, EventArgs e) txtresult.Clear();/清除显示 int cidao = new int1000;/被访问的磁道号数组 int sum = 0;/移动距离之和 double avg = 0;/平均寻道时间 int temp;/中间变量 int k = 1; int m, n; string str = txtnum.Text.Split(,);/从txtnum里面获取访问的磁道号 int now = Convert.ToInt32(txtnow.Text);/当前的磁道号 for (int i = 0; i str.Length; i+) /

19、将获取的磁道号存入磁道号数组 cidaoi = Convert.ToInt32(stri); /对磁道号进行从小到大排列 for (int i = 0; i str.Length; i+) for (int j = i + 1; j cidaoj) temp = cidaoi; cidaoi = cidaoj; cidaoj = temp; /数组的最后一个小于当前磁道号，则数组逆序输出，此时的移动距离之和等于当前磁道号减去最小的磁道号 if (cidaostr.Length - 1 = 0; i-) txtresult.Text = txtresult.Text + cidaoi + ,;

20、/移动距离之和 sum = now - cidao0; /数组的第一个数大于当前磁道号，正序输出，此时的移动距离之和等于最大的磁道号减去当前磁道号 else if (cidao0 = now) for (int i = 0; i str.Length; i+) txtresult.Text = txtresult.Text + cidaoi + ,; sum = cidaostr.Length - 1 - now;/移动距离之和 /当前磁道号的大小介于数组的最大值与最小值之间 else /k的初始值为，从数组的第二个数开始逐一与当前磁道号比较 while (cidaok now) k+; /k

21、+1比当前磁道号大的时候 m = k - 1; n = k; for (int j = n; j = 0; j-) txtresult.Text = txtresult.Text + cidaoj + ,; /sum = cidaostr.Length - 1 - cidao0; sum =2 * cidaostr.Length - 1 - now - cidao0; avg = (double)sum / str.Length;/平均寻道长度 lblsum.Text = 总移动距离： + sum.ToString();/在Label中显示总移动距离 lblavg.Text = 平均寻道长度：

22、 + avg.ToString(0.00);/在Label中显示平均寻道时间 / / 磁道号减小的方向扫描 / / / private void btnSCANlow_Click(object sender, EventArgs e) txtresult.Clear();/清除显示 int cidao = new int1000;/被访问的磁道号数组 int sum = 0;/移动距离之和 double avg = 0;/平均寻道时间 int temp;/中间变量 int k = 1; int m, n; string str = txtnum.Text.Split(,);/从txtnum里面

23、获取访问的磁道号 int now = Convert.ToInt32(txtnow.Text);/当前的磁道号 for (int i = 0; i str.Length; i+) /将获取的磁道号存入磁道号数组 cidaoi = Convert.ToInt32(stri); /对磁道号进行从小到大排列 for (int i = 0; i str.Length; i+) for (int j = i + 1; j cidaoj) temp = cidaoi; cidaoi = cidaoj; cidaoj = temp; /数组的最后一个小于当前磁道号，则数组逆序输出，此时的移动距离之和等于当前

24、磁道号减去最小的磁道号 if (cidaostr.Length - 1 = 0; i-) txtresult.Text = txtresult.Text + cidaoi + ,; sum = now - cidao0;/移动距离之和 /数组的第一个数大于当前磁道号，正序输出，此时的移动距离之和等于最大的磁道号减去当前磁道号 else if (cidao0 = now) for (int i = 0; i str.Length; i+) txtresult.Text = txtresult.Text + cidaoi + ,; sum = cidaostr.Length - 1 - now;/

25、移动距离之和 /当前磁道号的大小介于数组的最大值与最小值之间 else /k的初始值为，从数组的第二个数开始逐一与当前磁道号比较 while (cidaok = 0; j-)/比当前磁道号小的磁道数组的左边输出 txtresult.Text = txtresult.Text + cidaoj + ,; /sum = now - cidao0; for (int j = n; j str.Length; j+)/比当前磁道号大的磁道数组的右边输出 txtresult.Text = txtresult.Text + cidaoj + ,; /sum = cidaostr.Length - 1 -

26、cidao0; sum = now - cidao0 + cidaostr.Length - 1 - cidao0; avg = (double)sum / str.Length;/平均寻道长度 lblsum.Text = 总移动距离： + sum.ToString();/在Label中显示总移动距离 lblavg.Text = 平均寻道长度： + avg.ToString(0.00);/在Label中显示平均寻道时间 / / 磁道号增加的方向循环扫描 / / / private void btnCSCANhigh_Click(object sender, EventArgs e) txtre

27、sult.Clear();/清除显示 int cidao = new int1000;/被访问的磁道号数组 int sum = 0;/移动距离之和 double avg = 0;/平均寻道时间 int temp;/中间变量 int k = 1; int m, n; string str = txtnum.Text.Split(,);/从txtnum里面获取访问的磁道号 int now = Convert.ToInt32(txtnow.Text);/当前的磁道号 for (int i = 0; i str.Length; i+) /将获取的磁道号存入磁道号数组 cidaoi = Convert.

28、ToInt32(stri); /对磁道号进行从小到大排列 for (int i = 0; i str.Length; i+) for (int j = i + 1; j cidaoj) temp = cidaoi; cidaoi = cidaoj; cidaoj = temp; /数组的最后一个小于当前磁道号，则数组正序输出，此时的移动距离之和等于最大的磁道号减去当前磁道号 if (cidaostr.Length - 1 = now) for (int i = 0; i = now) for (int i = 0; i str.Length; i+) txtresult.Text = txtr

29、esult.Text + cidaoi + ,; sum = cidaostr.Length - 1 - now;/移动距离之和 /当前磁道号的大小介于数组的最大值与最小值之间 else /k的初始值为，从数组的第二个数开始逐一与当前磁道号比较 while (cidaok now) k+; /k+1比当前磁道号大的时候 m = k - 1; n = k; for (int j = n; j str.Length; j+)/输出 txtresult.Text = txtresult.Text + cidaoj + ,; /sum = cidaostr.Length - 1 - now;cidao

30、str.Length - 1 - cidao0 + cidaon - cidao0; for (int j = 0; j n; j+) txtresult.Text = txtresult.Text + cidaoj + ,; /sum = cidaostr.Length - 1 - cidao0 + cidaon-1 - cidao0; sum = cidaon-1 + 2 * (cidaostr.Length - 1 - cidao0) - now; avg = (double)sum / str.Length;/平均寻道长度 lblsum.Text = 总移动距离： + sum.ToSt

31、ring();/在Label中显示总移动距离 lblavg.Text = 平均寻道长度： + avg.ToString(0.00);/在Label中显示平均寻道时间 / / 磁道号减小的方向循环扫描 / / / private void btnCSCANlow_Click(object sender, EventArgs e) txtresult.Clear();/清除显示 int cidao = new int1000;/被访问的磁道号数组 int sum = 0;/移动距离之和 double avg = 0;/平均寻道时间 int temp;/中间变量 int k = 1; int m,

32、n; string str = txtnum.Text.Split(,);/从txtnum里面获取访问的磁道号 int now = Convert.ToInt32(txtnow.Text);/当前的磁道号 for (int i = 0; i str.Length; i+) /将获取的磁道号存入磁道号数组 cidaoi = Convert.ToInt32(stri); /对磁道号进行从小到大排列 for (int i = 0; i str.Length; i+) for (int j = i + 1; j cidaoj) temp = cidaoi; cidaoi = cidaoj; cidao

33、j = temp; /数组的最后一个小于当前磁道号，则数组逆序输出，此时的移动距离之和等于当前磁道号减去最小的磁道号 if (cidaostr.Length - 1 = 0; i-) txtresult.Text = txtresult.Text + cidaoi + ,; sum = now - cidao0;/移动距离之和 /数组的第一个数大于当前磁道号，逆序输出，此时的移动距离之和等于当前磁道号减去最小的磁道号 else if (cidao0 = now) for (int i = str.Length - 1; i = 0; i-) txtresult.Text = txtresult

34、.Text + cidaoi + ,; sum = cidaostr.Length - 1 - now;/移动距离之和 /当前磁道号的大小介于数组的最大值与最小值之间 else /k的初始值为，从数组的第二个数开始逐一与当前磁道号比较 while (cidaok = 0; j-)/输出 txtresult.Text = txtresult.Text + cidaoj + ,; for (int j = str.Length-1; j = n; j-) txtresult.Text = txtresult.Text + cidaoj + ,; sum = now - cidaon + 2 * (

35、cidaostr.Length - 1 - cidao0); avg = (double)sum / str.Length;/平均寻道长度 lblsum.Text = 总移动距离： + sum.ToString();/在Label中显示总移动距离 lblavg.Text = 平均寻道长度： + avg.ToString(0.00);/在Label中显示平均寻道时间 / / 退出 / / / private void btnexit_Click(object sender, EventArgs e) Application.Exit(); / / 快捷键Tab选择输入框 / / / privat

36、e void txtnum_KeyDown(object sender, KeyEventArgs e) if (e.KeyCode = Keys.Return) this.txtnum.Focus(); 8、软件运行环境及限制Microsoft Visual Studio 2005 C# Windows应用程序9、结果输出及分析编译并运行程序，弹出来磁盘调度算法窗体，输入当前磁道号和写一个被访问的磁道号（磁道号间用逗号隔开），然后可以根据提供的空间选择不同的算法实现对输入的磁道号的访问；按照教材196页的例题输入相应的数据；2、点击先来先服务(FCFS)按钮实现算法，显示结果如下：此算法按照请求访问的先后顺序访问磁道号，所以输出结果和输入结果的顺序一致，平均寻道长度为访问的磁道号之间的移动距离之和除以被访问的磁道数。3、点击最短寻道时间优先(SSTF)按钮实现算法，显示结果如下：此算法首先按照距离当前磁道号最近的先访问，然后以才被访问的磁道号为基准，又找离其最近的访问，以此类推。平均寻道长度为访问的磁道号之间的移动距离之和除以被访问的磁道数。4、点击磁道增加的方向扫描(SCAN)按钮实现算法，显示结果如下：此算法首先按照请求访问的磁道号从小到大排序，然后以当前磁道号为基准，向磁