算法设计:如何实现FCFS磁盘调度算法?

2021年3月23日14:58:33 发表评论 947 次浏览

本文概述

先决条件: 磁盘调度算法

给定一系列磁盘磁道编号和初始磁头位置, 我们的任务是查找为访问所有请求的磁道而执行的查找操作总数先来先服务(FCFS)使用磁盘调度算法

先来先服务(FCFS)

FCFS是最简单的

磁盘调度算法

。顾名思义, 该算法按请求到达磁盘队列的顺序来接受请求。该算法看起来非常公平, 没有饥饿(所有请求都按顺序处理), 但是通常它不能提供最快的服务。

算法:

  1. 让Request数组表示一个数组, 该数组存储已按其到达时间的升序请求的音轨的索引。 "磁头"是磁盘磁头的位置。
  2. 让我们一一按照默认顺序获取轨迹, 并计算轨迹到头部的绝对距离。
  3. 以此距离增加总寻道数。
  4. 当前服务的轨道位置现在变为新的头位置。
  5. 转到步骤2, 直到未维修请求数组中的所有轨道。

例子:

Input: 
Request sequence = {176, 79, 34, 60, 92, 11, 41, 114}
Initial head position = 50

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

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

FCFS磁盘调度算法1

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

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

实现

实施

FCFS

在下面给出。请注意, 距离用于存储磁头和当前磁道位置之间的绝对距离。

C ++

// C++ program to demonstrate
// FCFS Disk Scheduling algorithm
  
#include <bits/stdc++.h>
using namespace std;
  
int size = 8;
  
void FCFS( int arr[], int head)
{
     int seek_count = 0;
     int distance, cur_track;
  
     for ( int i = 0; i < size; i++) {
         cur_track = arr[i];
  
         // calculate absolute distance
         distance = abs (cur_track - head);
  
         // increase the total count
         seek_count += distance;
  
         // accessed track is now new head
         head = cur_track;
     }
  
     cout << "Total number of seek operations = "
          << seek_count << endl;
  
     // Seek sequence would be the same
     // as request array sequence
     cout << "Seek Sequence is" << endl;
  
     for ( int i = 0; i < size; i++) {
         cout << arr[i] << endl;
     }
}
  
// Driver code
int main()
{
  
     // request array
     int arr[size] = { 176, 79, 34, 60, 92, 11, 41, 114 };
     int head = 50;
  
     FCFS(arr, head);
  
     return 0;
}

Java

// Java program to demonstrate
// FCFS Disk Scheduling algorithm
class GFG
{
static int size = 8 ;
  
static void FCFS( int arr[], int head)
{
     int seek_count = 0 ;
     int distance, cur_track;
  
     for ( int i = 0 ; i < size; i++) 
     {
         cur_track = arr[i];
  
         // 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;
     }
  
     System.out.println( "Total number of " + 
                        "seek operations = " + 
                         seek_count);
  
     // Seek sequence would be the same
     // as request array sequence
     System.out.println( "Seek Sequence is" );
  
     for ( int i = 0 ; i < size; i++)
     {
         System.out.println(arr[i]);
     }
}
  
// Driver code
public static void main(String[] args) 
{
     // request array
     int arr[] = { 176 , 79 , 34 , 60 , 92 , 11 , 41 , 114 };
     int head = 50 ;
  
     FCFS(arr, head);
}
}
  
// This code is contributed by 29AjayKumar

Python3

# Python program to demonstrate
# FCFS Disk Scheduling algorithm
  
size = 8 ;
  
def FCFS(arr, head):
  
     seek_count = 0 ;
     distance, cur_track = 0 , 0 ;
  
     for i in range (size):
         cur_track = arr[i];
  
         # calculate absolute distance
         distance = abs (cur_track - head);
  
         # increase the total count
         seek_count + = distance;
  
         # accessed track is now new head
         head = cur_track;
      
     print ( "Total number of seek operations = " , seek_count);
  
     # Seek sequence would be the same
     # as request array sequence
     print ( "Seek Sequence is" );
  
     for i in range (size):
         print (arr[i]);
      
# Driver code
if __name__ = = '__main__' :
  
     # request array
     arr = [ 176 , 79 , 34 , 60 , 92 , 11 , 41 , 114 ];
     head = 50 ;
  
     FCFS(arr, head);
  
# This code contributed by Rajput-Ji

C#

// C# program to demonstrate
// FCFS Disk Scheduling algorithm
using System;
  
class GFG
{
static int size = 8;
  
static void FCFS( int []arr, int head)
{
     int seek_count = 0;
     int distance, cur_track;
  
     for ( int i = 0; i < size; i++) 
     {
         cur_track = arr[i];
  
         // 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;
     }
  
     Console.WriteLine( "Total number of " + 
                     "seek operations = " + 
                               seek_count);
  
     // Seek sequence would be the same
     // as request array sequence
     Console.WriteLine( "Seek Sequence is" );
  
     for ( int i = 0; i < size; i++)
     {
         Console.WriteLine(arr[i]);
     }
}
  
// Driver code
public static void Main(String[] args) 
{
     // request array
     int []arr = { 176, 79, 34, 60, 92, 11, 41, 114 };
     int head = 50;
  
     FCFS(arr, head);
}
}
  
// This code is contributed by PrinciRaj1992

输出如下:

Total number of seek operations = 510
Seek Sequence is
176
79
34
60
92
11
41
114

木子山

发表评论

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