LOOK磁盘调度算法解析和代码实现详解

2021年3月12日13:10:02 发表评论 3,276 次浏览

先决条件:磁盘调度算法

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

LOOK磁盘调度算法

LOOK是的高级版本

SCAN(电梯)磁盘调度算法

与层次结构中的任何其他算法相比, 其寻找时间略长

(FCFS-> SRTF-> SCAN-> C-SCAN-> LOOK)

。 LOOK算法的服务请求与SCAN算法相似, 同时它还"向前看", 就好像在同一方向上需要维护更多的磁道一样。如果在移动方向上没有待处理的请求, 则磁头反转方向, 并开始在相反的方向上处理请求。

与SCAN相比, LOOK算法具有更好的性能的主要原因在于, 在该算法中, 磁头不允许移动到磁盘末端。

算法:

  1. 让Request数组表示一个数组, 该数组存储已按其到达时间的升序请求的音轨的索引。 "磁头"是磁盘磁头的位置。
  2. 给出了头部移动的初始方向, 并且该方向在同一方向上起作用。
  3. 头在头移动的方向上一一服务所有请求。
  4. 磁头继续沿相同方向移动, 直到该方向上的所有请求都未完成。
  5. 沿该方向移动时, 计算磁道与磁头的绝对距离。
  6. 以此距离增加总寻道数。
  7. 当前服务的轨道位置现在变为新的头位置。
  8. 进行第5步, 直到我们最终朝这个方向提出要求。
  9. 如果到达此方向不需要处理任何请求的地方, 请反转方向, 然后转到步骤3, 直到未处理请求数组中的所有轨道。

例子:

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

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

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

LOOK磁盘调度算法1

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

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

实现

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

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

#include <bits/stdc++.h>
using namespace std;
  
// Code by Vikram Chaurasia
  
// C++ program to demonstrate
// SCAN Disk Scheduling algorithm
  
int size = 8;
int disk_size = 200;
  
void LOOK(int arr[], int head, string direction)
{
     int seek_count = 0;
     int distance, cur_track;
     vector<int> left, right;
     vector<int> seek_sequence;
  
     // appending values which are
     // currently at left and right
     // direction from the head.
     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
     // for servicing tracks in the
     // correct sequence.
     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 side 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;
             }
             // reversing the direction
             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;
             }
             // reversing the direction
             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 = "right";
  
     cout << "Initial position of head: "
          << head << endl;
  
     LOOK(arr, head, direction);
  
     return 0;
}

输出如下:

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

木子山

发表评论

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