Рубрики

LOOK Алгоритм планирования дисков

GATE CS, Операционные системы

Предварительное условие: Алгоритмы планирования дисков

Учитывая массив номеров дорожек диска и начальное положение головки, наша задача состоит в том, чтобы найти общее количество операций поиска, выполненных для доступа ко всем запрошенным дорожкам, если используется алгоритм планирования диска. Также напишите программу для поиска последовательности поиска с использованием алгоритма планирования диска.

Посмотрите алгоритм планирования диска:
LOOK — это усовершенствованная версия алгоритма планирования диска SCAN (элеватора), которая дает немного лучшее время поиска, чем любой другой алгоритм в иерархии. Алгоритм LOOK обслуживает запрос аналогично алгоритму SCAN, в то же время он также «смотрит» вперед, как будто есть больше дорожек, которые необходимо обслуживать в том же направлении. Если нет ожидающих запросов в направлении движения, головка меняет направление и начинает обслуживать запросы в противоположном направлении.

Основная причина лучшей производительности алгоритма LOOK по сравнению со SCAN состоит в том, что в этом алгоритме головке не разрешается перемещаться до конца диска.

Алгоритм:

  1. Массив Let 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.

Поэтому общее количество запросов рассчитывается как:

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

Реализация:
Реализация алгоритма LOOK приведена ниже.

Примечание: переменная расстояния используется для хранения абсолютного расстояния между головой и текущей позицией трека. disk_size — это размер диска. Векторы left и right хранят все треки запроса слева и справа от начальной позиции головы соответственно.

#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

Рекомендуемые посты:

LOOK Алгоритм планирования дисков

0.00 (0%) 0 votes