操作系统实验--SSTF磁盘调度算法

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

磁盘调度在多道程序设计的计算机系统中,各个进程可能会不断提出不同的对磁盘进行读/写操作的请求。由于有时候这些进程的发送请求的速度比磁盘响应的还要快,因此我们有必要为每个磁盘设备建立一个等待队列,最短寻道时间优先算法(Shortest Seek Time First-SSTF)常用的磁盘调度算法之一。 

SSTF算法选择调度处理的磁道是与当前磁头所在磁道距离最近的磁道,以使每次的寻找时间最短。当然,总是选择最小寻找时间并不能保证平均寻找时间最小,但是能提供比FCFS算法更好的性能。这种算法会产生“饥饿”现象。

1、算法思想:优先选择距当前磁头最近的访问请求进行服务,主要考虑寻道优先。

2、优点:改善了磁盘平均服务时间。

3、缺点:造成某些访问请求长期等待得不到服务。

对于给定的磁头所在的当前磁道号和请求访问的磁道号队列(FIFO),试设计一个解此问题的算法,计算磁道访问序列和平均寻道长度(保留两位小数),并分析算法的正确性与计算复杂性。

Input

 

多组输入。输入数据的第一行是正整数n(0 < n < 500),表示磁头所在的当前磁道号;第2 行是正整数m(8 n 20),表示请求访问的磁道号队列长度;第三行有m个正整数ai(0 < a­I < 500),表示请求访问队列的m个磁道号。

Output

 

输出m+1行,前m行每行有两个整数,分别表示磁道号和移动的磁道数,第m+1行表示计算出的平均寻道长度(保留两位小数)。

Sample Input

100 9
350
180
22
365
30
120
185
60
200

Sample Output

120 20
180 60
185 5
200 15
60 140
30 30
22 8
350 328
365 15
69.00

Hint

 

Source

Xie Yinbao