SCAN（电梯）磁盘调度算法解析和实现

2021年3月9日15:53:33 发表评论 1,450 次浏览

本文概述

先决条件

磁盘调度算法。

给定一个磁盘磁道编号和初始磁头位置的数组, 如果使用了SCAN磁盘调度算法, 我们的任务是查找为访问所有请求的磁道而执行的查找操作的总数。

SCAN(电梯)算法

在SCAN磁盘调度算法中, 磁头从磁盘的一端开始, 朝磁盘的另一端移动, 一个接一个地处理请求, 然后到达另一端。然后, 磁头的方向反转, 并且随着磁头不断来回扫描以访问磁盘, 该过程继续进行。因此, 此算法可以用作电梯, 因此也称为

电梯算法

。结果, 中端的请求得到了更多的服务, 那些到达磁盘臂后面的请求将不得不等待。

SCAN(电梯)算法的优点 

  1. 该算法简单易懂。
  2. SCAN算法没有饥饿感。
  3. 该算法优于FCFS调度算法。

SCAN(电梯)算法的缺点

  1. 实施更复杂的算法。
  2. 该算法是不公平的, 因为它会导致磁头刚访问的气缸的等待时间较长。
  3. 这样会导致磁头移动到磁盘末端, 这样到达手臂位置之前的请求将立即得到服务, 但是到达手臂位置后面的其他一些请求将不得不等待请求完成。

算法-

  1. 让Request数组表示一个数组, 该数组存储已按其到达时间的升序请求的音轨的索引。 "磁头"是磁盘磁头的位置。
  2. 让方向代表头部向左还是向右移动。
  3. 在头部移动的方向上, 所有人都一一追踪。
  4. 计算磁头到磁头的绝对距离。
  5. 以此距离增加总寻道数。
  6. 当前服务的轨道位置现在变为新的头位置。
  7. 转到步骤3, 直到到达磁盘的一端。
  8. 如果我们到达磁盘末端, 请反转方向, 然后继续执行步骤2, 直到请求阵列中的所有磁道都未送达为止。

例子：

Input: 
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50
Direction = left (We are moving from right to left)

Output:
Total number of seek operations = 226
Seek Sequence is
41
34
11
0
60
79
92
114
176

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

SCAN（电梯）磁盘调度算法1

因此, 总寻道数计算如下：

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

实现

下面给出了SCAN的实现。请注意, 距离用于存储磁头和当前轨道位置之间的绝对距离。 disk_size是磁盘的大小。左向量和右向量分别将所有请求轨迹存储在初始头部位置的左侧和右侧。

C ++

// C++ program to demonstrate
// SCAN Disk Scheduling algorithm
 
#include <bits/stdc++.h>
using namespace std;
 
int size = 8;
int disk_size = 200;
 
void SCAN( int arr[], int head, string direction)
{
     int seek_count = 0;
     int distance, cur_track;
     vector< int > left, right;
     vector< int > seek_sequence;
 
     // appending end values
     // which has to be visited
     // before reversing the direction
     if (direction == "left" )
         left.push_back(0);
     else if (direction == "right" )
         right.push_back(disk_size - 1);
 
     for ( int i = 0; i < size; i++) {
         if (arr[i] < head)
             left.push_back(arr[i]);
         if (arr[i] > head)
             right.push_back(arr[i]);
     }
 
     // sorting left and right vectors
     std::sort(left.begin(), left.end());
     std::sort(right.begin(), right.end());
 
     // run the while loop two times.
     // one by one scanning right
     // and left of the head
     int run = 2;
     while (run--) {
         if (direction == "left" ) {
             for ( int i = left.size() - 1; i >= 0; i--) {
                 cur_track = left[i];
 
                 // appending current track to seek sequence
                 seek_sequence.push_back(cur_track);
 
                 // calculate absolute distance
                 distance = abs (cur_track - head);
 
                 // increase the total count
                 seek_count += distance;
 
                 // accessed track is now the new head
                 head = cur_track;
             }
             direction = "right" ;
         }
         else if (direction == "right" ) {
             for ( int i = 0; i < right.size(); i++) {
                 cur_track = right[i];
                 // appending current track to seek sequence
                 seek_sequence.push_back(cur_track);
 
                 // calculate absolute distance
                 distance = abs (cur_track - head);
 
                 // increase the total count
                 seek_count += distance;
 
                 // accessed track is now new head
                 head = cur_track;
             }
             direction = "left" ;
         }
     }
 
     cout << "Total number of seek operations = "
          << seek_count << endl;
 
     cout << "Seek Sequence is" << endl;
 
     for ( int i = 0; i < seek_sequence.size(); i++) {
         cout << seek_sequence[i] << endl;
     }
}
 
// Driver code
int main()
{
 
     // request array
     int arr[size] = { 176, 79, 34, 60, 92, 11, 41, 114 };
     int head = 50;
     string direction = "left" ;
 
     SCAN(arr, head, direction);
 
     return 0;
}

Java

// Java program to demonstrate
// SCAN Disk Scheduling algorithm
import java.util.*;
 
class GFG
{
 
static int size = 8 ;
static int disk_size = 200 ;
 
static void SCAN( int arr[], int head, String direction)
{
     int seek_count = 0 ;
     int distance, cur_track;
     Vector<Integer> left = new Vector<Integer>(), right = new Vector<Integer>();
     Vector<Integer> seek_sequence = new Vector<Integer>();
 
     // appending end values
     // which has to be visited
     // before reversing the direction
     if (direction == "left" )
         left.add( 0 );
     else if (direction == "right" )
         right.add(disk_size - 1 );
 
     for ( int i = 0 ; i < size; i++)
     {
         if (arr[i] < head)
             left.add(arr[i]);
         if (arr[i] > head)
             right.add(arr[i]);
     }
 
     // sorting left and right vectors
     Collections.sort(left);
     Collections.sort(right);
 
     // run the while loop two times.
     // one by one scanning right
     // and left of the head
     int run = 2 ;
     while (run-- > 0 )
     {
         if (direction == "left" )
         {
             for ( int i = left.size() - 1 ; i >= 0 ; i--)
             {
                 cur_track = left.get(i);
 
                 // appending current track to seek sequence
                 seek_sequence.add(cur_track);
 
                 // calculate absolute distance
                 distance = Math.abs(cur_track - head);
 
                 // increase the total count
                 seek_count += distance;
 
                 // accessed track is now the new head
                 head = cur_track;
             }
             direction = "right" ;
         }
         else if (direction == "right" )
         {
             for ( int i = 0 ; i < right.size(); i++)
             {
                 cur_track = right.get(i);
                 
                 // appending current track to seek sequence
                 seek_sequence.add(cur_track);
 
                 // calculate absolute distance
                 distance = Math.abs(cur_track - head);
 
                 // increase the total count
                 seek_count += distance;
 
                 // accessed track is now new head
                 head = cur_track;
             }
             direction = "left" ;
         }
     }
 
     System.out.print( "Total number of seek operations = "
                         + seek_count + "\n" );
 
     System.out.print( "Seek Sequence is" + "\n" );
 
     for ( int i = 0 ; i < seek_sequence.size(); i++)
     {
         System.out.print(seek_sequence.get(i) + "\n" );
     }
}
 
// Driver code
public static void main(String[] args)
{
 
     // request array
     int arr[] = { 176 , 79 , 34 , 60 , 92 , 11 , 41 , 114 };
     int head = 50 ;
     String direction = "left" ;
 
     SCAN(arr, head, direction);
}
}
 
// This code is contributed by 29AjayKumar

C#

// C# program to demonstrate
// SCAN Disk Scheduling algorithm
using System;
using System.Collections.Generic;
 
class GFG
{
 
static int size = 8;
static int disk_size = 200;
 
static void SCAN( int []arr, int head, String direction)
{
     int seek_count = 0;
     int distance, cur_track;
     List< int > left = new List< int >(), right = new List< int >();
     List< int > seek_sequence = new List< int >();
 
     // appending end values
     // which has to be visited
     // before reversing the direction
     if (direction == "left" )
         left.Add(0);
     else if (direction == "right" )
         right.Add(disk_size - 1);
 
     for ( int i = 0; i < size; i++)
     {
         if (arr[i] < head)
             left.Add(arr[i]);
         if (arr[i] > head)
             right.Add(arr[i]);
     }
 
     // sorting left and right vectors
     left.Sort();
     right.Sort();
 
     // run the while loop two times.
     // one by one scanning right
     // and left of the head
     int run = 2;
     while (run-- >0)
     {
         if (direction == "left" )
         {
             for ( int i = left.Count - 1; i >= 0; i--)
             {
                 cur_track = left[i];
 
                 // appending current track to seek sequence
                 seek_sequence.Add(cur_track);
 
                 // calculate absolute distance
                 distance = Math.Abs(cur_track - head);
 
                 // increase the total count
                 seek_count += distance;
 
                 // accessed track is now the new head
                 head = cur_track;
             }
             direction = "right" ;
         }
         else if (direction == "right" )
         {
             for ( int i = 0; i < right.Count; i++)
             {
                 cur_track = right[i];
                 
                 // appending current track to seek sequence
                 seek_sequence.Add(cur_track);
 
                 // calculate absolute distance
                 distance = Math.Abs(cur_track - head);
 
                 // increase the total count
                 seek_count += distance;
 
                 // accessed track is now new head
                 head = cur_track;
             }
             direction = "left" ;
         }
     }
 
     Console.Write( "Total number of seek operations = "
                         + seek_count + "\n" );
     Console.Write( "Seek Sequence is" + "\n" );
     for ( int i = 0; i < seek_sequence.Count; i++)
     {
         Console.Write(seek_sequence[i] + "\n" );
     }
}
 
// Driver code
public static void Main(String[] args)
{
 
     // request array
     int []arr = { 176, 79, 34, 60, 92, 11, 41, 114 };
     int head = 50;
     String direction = "left" ;
 
     SCAN(arr, head, direction);
}
}
 
// This code is contributed by 29AjayKumar

输出如下：

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

发表评论

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