如何实现SSTF磁盘调度算法程序？

2021年3月19日18:39:45 发表评论 893 次浏览

本文概述

先决条件–

磁盘调度算法

给定一系列磁盘磁道编号和初始磁头位置, 我们的任务是查找为访问所有请求的磁道而执行的查找操作总数

最短搜寻时间优先(SSTF)

是使用磁盘调度算法的。

最短搜寻时间优先(SSTF)–

基本思想是, 应首先维修更靠近当前磁盘磁头位置的轨道, 以便

最小化搜寻操作

.

最短搜寻时间优先(SSTF)的优势–

  1. 性能优于FCFS调度算法。
  2. 它提供了更好的吞吐量。
  3. 此算法用于批处理系统, 在该系统中, 吞吐量更为重要。
  4. 它的平均响应时间和等待时间更少。

最短搜索时间优先(SSTF)的缺点–

  1. 对于某些请求, 可能会出现饥饿, 因为它容易达到请求且忽略了遥远的过程。
  2. 由于响应时间差异很大, 因此缺乏可预测性。
  3. 切换方向会使事情变慢。

算法–

  1. 让Request数组表示一个数组, 该数组存储已请求的曲目的索引。 "磁头"是磁盘磁头的位置。
  2. 找到请求数组中所有磁迹到头部的正距离。
  3. 从请求的阵列中找到一条尚未被访问/维修且距头部最小距离的轨道。
  4. 以此距离增加总寻道数。
  5. 当前服务的轨道位置现在变为新的头位置。
  6. 转到步骤2, 直到未维修请求数组中的所有轨道。

示例–

请求顺序= {176, 79, 34, 60, 92, 11, 41, 114}

初始头部位置= 50

下表显示了使用SSTF服务请求的曲目的顺序。

SSTF磁盘调度算法程序1

因此, 总寻道数计算为：

= (50-41)+(41-34)+(34-11)+(60-11)+(79-60)+(92-79)+(114-92)+(176-114)
= 204

实施–

SSTF的实现如下。请注意, 我们已使节点类具有2个成员。 "距离"用于存储头部和轨道位置之间的距离。 " accessed"是一个布尔变量, 它指示磁盘磁头之前是否已经访问过/维护过磁道。

Java

class node {
      
     // represent difference between 
     // head position and track number
     int distance = 0 ; 
      
     // true if track has been accessed
     boolean accessed = false ; 
}
  
public class SSTF {
      
     // Calculates difference of each 
     // track number with the head position
     public static void calculateDifference( int queue[], int head, node diff[])
                                          
     {
         for ( int i = 0 ; i < diff.length; i++)
             diff[i].distance = Math.abs(queue[i] - head);
     }
  
     // find unaccessed track 
     // which is at minimum distance from head
     public static int findMin(node diff[])
     {
         int index = - 1 , minimum = Integer.MAX_VALUE;
  
         for ( int i = 0 ; i < diff.length; i++) {
             if (!diff[i].accessed && minimum > diff[i].distance) {
                  
                 minimum = diff[i].distance;
                 index = i;
             }
         }
         return index;
     }
  
     public static void shortestSeekTimeFirst( int request[], int head)
                                                       
     {
         if (request.length == 0 )
             return ;
              
         // create array of objects of class node    
         node diff[] = new node[request.length]; 
          
         // initialize array
         for ( int i = 0 ; i < diff.length; i++) 
          
             diff[i] = new node();
          
         // count total number of seek operation    
         int seek_count = 0 ; 
          
         // stores sequence in which disk access is done
         int [] seek_sequence = new int [request.length + 1 ]; 
          
         for ( int i = 0 ; i < request.length; i++) {
              
             seek_sequence[i] = head;
             calculateDifference(request, head, diff);
              
             int index = findMin(diff);
              
             diff[index].accessed = true ;
              
             // increase the total count
             seek_count += diff[index].distance; 
              
             // accessed track is now new head
             head = request[index]; 
         }
          
         // for last accessed track
         seek_sequence[seek_sequence.length - 1 ] = head; 
          
         System.out.println( "Total number of seek operations = " 
                                                      + seek_count);
                                                       
         System.out.println( "Seek Sequence is" );
          
         // print the sequence
         for ( int i = 0 ; i < seek_sequence.length; i++) 
             System.out.println(seek_sequence[i]);
     }
  
     public static void main(String[] args)
     {
         // request array
         int arr[] = { 176 , 79 , 34 , 60 , 92 , 11 , 41 , 114 }; 
         shortestSeekTimeFirst(arr, 50 );
     }
}

Python3

# Python3 program for implementation of 
# SSTF disk scheduling 
  
# Calculates difference of each 
# track number with the head position
def calculateDifference(queue, head, diff):
     for i in range ( len (diff)):
         diff[i][ 0 ] = abs (queue[i] - head) 
      
# find unaccessed track which is 
# at minimum distance from head 
def findMin(diff): 
  
     index = - 1
     minimum = 999999999
  
     for i in range ( len (diff)):
         if ( not diff[i][ 1 ] and 
                 minimum > diff[i][ 0 ]):
             minimum = diff[i][ 0 ]
             index = i
     return index 
      
def shortestSeekTimeFirst(request, head):             
         if ( len (request) = = 0 ): 
             return
          
         l = len (request) 
         diff = [ 0 ] * l
          
         # initialize array 
         for i in range (l):
             diff[i] = [ 0 , 0 ]
          
         # count total number of seek operation     
         seek_count = 0
          
         # stores sequence in which disk 
         # access is done 
         seek_sequence = [ 0 ] * (l + 1 ) 
          
         for i in range (l): 
             seek_sequence[i] = head 
             calculateDifference(request, head, diff) 
             index = findMin(diff) 
              
             diff[index][ 1 ] = True
              
             # increase the total count 
             seek_count + = diff[index][ 0 ] 
              
             # accessed track is now new head 
             head = request[index] 
      
         # for last accessed track 
         seek_sequence[ len (seek_sequence) - 1 ] = head 
          
         print ( "Total number of seek operations =" , seek_count) 
                                                          
         print ( "Seek Sequence is" ) 
          
         # print the sequence 
         for i in range (l + 1 ):
             print (seek_sequence[i]) 
      
# Driver code 
if __name__ = = "__main__" :
      
     # request array 
     proc = [ 176 , 79 , 34 , 60 , 92 , 11 , 41 , 114 ]
     shortestSeekTimeFirst(proc, 50 )
      
# This code is contributed by
# Shubham Singh(SHUBHAMSINGH10)

C#

// C# program for implementation of FCFS 
// scheduling 
using System;
      
public class node
{
      
     // represent difference between 
     // head position and track number
     public int distance = 0; 
      
     // true if track has been accessed
     public Boolean accessed = false ; 
}
  
public class SSTF 
{
      
     // Calculates difference of each 
     // track number with the head position
     public static void calculateDifference( int []queue, int head, node []diff)
                                          
     {
         for ( int i = 0; i < diff.Length; i++)
             diff[i].distance = Math.Abs(queue[i] - head);
     }
  
     // find unaccessed track 
     // which is at minimum distance from head
     public static int findMin(node []diff)
     {
         int index = -1, minimum = int .MaxValue;
  
         for ( int i = 0; i < diff.Length; i++)
         {
             if (!diff[i].accessed && minimum > diff[i].distance)
             {
                  
                 minimum = diff[i].distance;
                 index = i;
             }
         }
         return index;
     }
  
     public static void shortestSeekTimeFirst( int []request, int head)
     {
         if (request.Length == 0)
             return ;
              
         // create array of objects of class node 
         node []diff = new node[request.Length]; 
          
         // initialize array
         for ( int i = 0; i < diff.Length; i++) 
          
             diff[i] = new node();
          
         // count total number of seek operation 
         int seek_count = 0; 
          
         // stores sequence in which disk access is done
         int [] seek_sequence = new int [request.Length + 1]; 
          
         for ( int i = 0; i < request.Length; i++)
         {
              
             seek_sequence[i] = head;
             calculateDifference(request, head, diff);
              
             int index = findMin(diff);
              
             diff[index].accessed = true ;
              
             // increase the total count
             seek_count += diff[index].distance; 
              
             // accessed track is now new head
             head = request[index]; 
         }
          
         // for last accessed track
         seek_sequence[seek_sequence.Length - 1] = head; 
          
         Console.WriteLine( "Total number of seek operations = "
                                                     + seek_count);
                                                      
         Console.WriteLine( "Seek Sequence is" );
          
         // print the sequence
         for ( int i = 0; i < seek_sequence.Length; i++) 
             Console.WriteLine(seek_sequence[i]);
     }
  
     // Driver code
     public static void Main(String[] args)
     {
         // request array
         int []arr = { 176, 79, 34, 60, 92, 11, 41, 114 }; 
         shortestSeekTimeFirst(arr, 50);
     }
}
  
// This code contributed by Rajput-Ji

输出如下：

Total number of seek operations = 204
Seek Sequence is
50
41
34
11
60
79
92
114
176
木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: