算法设计:C-LOOK磁盘调度算法指南

2021年3月13日16:12:44 发表评论 1,100 次浏览

先决条件: 磁盘调度算法

给定一系列磁盘磁道编号和初始磁头位置, 我们的任务是查找为访问所有请求的磁道而执行的查找操作总数C语言使用磁盘调度算法。另外, 编写一个程序以使用以下命令查找寻道顺序C语言磁盘调度算法。

C-LOOK(循环查找)磁盘调度算法:

C语言

是两者的增强版本

扫描

以及

磁盘调度算法。该算法还使用了像C-SCAN算法那样将轨迹包裹为圆柱体的想法, 但是查找时间比C-SCAN算法要好。我们知道, 使用C-SCAN可以避免饥饿, 并为所有请求提供更统一的服务, C-LOOK也是如此。

在这种算法中, 头服务仅在一个方向(左或右)上进行请求, 直到该方向上的所有请求均未得到服务, 然后再跳回到另一方向上最远的请求, 并为其余请求提供服务, 从而提供更好的统一性维修以及避免浪费寻找时间直到磁盘末端。

算法-

  1. 令Request数组代表一个数组, 该数组存储按其到达时间和头是磁盘头的位置。
  2. 给出了磁头移动的初始方向, 并且它以相同的方向运行。
  3. 头部在其移动方向上一一处理所有请求。
  4. 磁头继续沿相同方向移动, 直到已满足该方向上的所有请求。
  5. 沿该方向移动时, 计算磁道与磁头的绝对距离。
  6. 以此距离增加总寻道数。
  7. 当前服务的轨道位置现在变为新的头位置。
  8. 转到第5步, 直到我们达到此方向的最后一个请求。
  9. 如果我们在当前方向上到达最后一个请求, 则反转方向, 并朝该方向移动磁头, 直到我们到达需要在该方向上进行服务的最后一个请求, 而无需服务中间请求。
  10. 反转方向, 然后转到步骤3, 直到未满足所有请求。

例子:

输入:请求顺序= {176、79、34、60、92、11、41、114}初始磁头位置= 50方向=右(从左向右移动)输出:磁头的初始位置:50搜索操作总数= 156搜索顺序为60 79 92 114 176 11 34 41

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

C-LOOK磁盘调度算法1

因此, 总搜寻次数=(60 – 50)+(79 – 60)+(92 – 79)+(114 – 92)+(176 – 114)+(176 – 11)+(34 – 11)+( 41 – 34)= 321

实现

下面给出了C-LOOK算法的实现。

注意

距离变量用于存储磁头到当前轨道位置之间的绝对距离, disk_size是磁盘的大小。左向量和右向量分别将所有请求轨迹存储在初始头部位置的左侧和右侧。

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
int size = 8;
int disk_size = 200;
  
// Function to perform C-LOOK on the request
// array starting from the given head
void CLOOK( int arr[], int head)
{
     int seek_count = 0;
     int distance, cur_track;
     vector< int > left, right;
     vector< int > seek_sequence;
  
     // Tracks on the left of the
     // head will be serviced when
     // once the head comes back
     // to the beggining (left end)
     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());
  
     // First service the requests
     // on the right side of the
     // head
     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;
     }
  
     // Once reached the right end
     // jump to the last track that
     // is needed to be serviced in
     // left direction
     seek_count += abs (head - left[0]);
     head = left[0];
  
     // Now service the requests again
     // which are left
     for ( int i = 0; i < left.size(); 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;
     }
  
     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;
  
     cout << "Initial position of head: " << head << endl;
  
     CLOOK(arr, head);
  
     return 0;
}

输出如下:

Initial position of head: 50
Total number of seek operations = 321
Seek Sequence is
60
79
92
114
176
11
34
41

木子山

发表评论

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