13.2.4.2. Алгоритм First Come First Served (fcfs)

Простейшим алгоритмом, к которому мы уже должны были привыкнуть, является алгоритм First Come First Served (FCFS) – первым пришел, первым обслужен. Все запросы организуются в очередь FIFO и обслуживаются в порядке поступления. Алгоритм прост в реализации, но может приводить к достаточно большим общим временам обслуживания запросов. Рассмотрим пример. Пусть у нас на диске из 100 цилиндров (от 0 до 99) есть следующая очередь запросов: 23, 67, 55, 14, 31, 7, 84, 10 и головки в начальный момент находятся на 63 цилиндре. Тогда положение головок будет меняться следующим образом:

63->23->67->55->14->31->7->84->10

и всего головки переместятся на 329 цилиндров. Неэффективность алгоритма хорошо иллюстрируется двумя последними перемещениями с 7 цилиндра через весь диск на 84 цилиндр и, затем опять через весь диск на цилиндр 10. Простая замена порядка двух последних перемещений (7->10->84) позволила бы существенно сократить общее время обслуживания запросов. Поэтому давайте перейдем к рассмотрению другого алгоритма.

13.2.4.3. Алгоритм Short Seek Time First (sstf).

Как мы видели, достаточно разумным является первоочередное обслуживание запросов, данные для которых лежат рядом с текущей позицией головок, а уж затем далеко отстоящих. Алгоритм Short Seek Time First (SSTF) – короткое время поиска первым - как раз и исходит из этой позиции. Для очередного обслуживания будем выбирать запрос, данные для которого лежат наиболее близко к текущему положению магнитных головок. Естественно, что при наличии равноудаленных запросов, решение о выборе между ними может приниматься из различных соображений, например по алгоритму FCFS. Для предыдущего примера алгоритм даст следующую последовательность положений головок:

63->67->55->31->23->14->10->7->84

и всего головки переместятся на 141 цилиндр. Заметим, что наш алгоритм похож на алгоритм SJF планирования процессов, если за аналог оценки времени очередного CPU burst процесса выбирать расстояние между текущим положением головки и положением, необходимым для удовлетворения запроса. И точно так же, как алгоритм SJF, он может приводить к длительному откладыванию выполнения какого-либо запроса. Необходимо вспомнить, что запросы в очереди могут появляться в любой момент времени. Если у нас все запросы, кроме одного, постоянного группируются в области с большими номерами цилиндров, то этот один запрос может находиться в очереди неопределенно долго.

Точный алгоритм SJF являлся оптимальным для заданного набора процессов с заданными временами CPU burst. Легко видеть, что алгоритм SSTF не является оптимальным. Если мы перенесем обслуживание запроса 67 цилиндра в промежуток между запросами 7 и 84 цилиндров, мы уменьшим общее время обслуживания. Это наблюдение приводит нас к идее целого семейства других алгоритмов – алгоритмов сканирования.

13.2.4.4. Алгоритмы сканирования (scan, c-scan, look, c-look)

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

63->55->31->23->14->10->7->0->67->84

и всего головки переместятся на 147 цилиндров.

Если мы знаем, что обслужили последний попутный запрос в направлении движения головок, то мы можем не доходить до края диска, а сразу изменить направление движения на обратное:

63->55->31->23->14->10->7->67->84

и всего головки переместятся на 133 цилиндра. Полученная модификация алгоритма SCAN получила название LOOK.

Допустим, что к моменту изменения направления движения головки в алгоритме SCAN, т.е. когда головка достигла одного из краев диска, у этого края накопилось большое количество новых запросов, на обслуживание которых будет потрачено достаточно большое время (не забываем, что надо не только перемещать головку, но еще и передавать прочитанные данные!). Тогда запросы, относящиеся к другому краю диска и поступившие раньше, будут ждать обслуживания несправедливо долгое время. Для сокращения времени ожидания запросов применяется другая модификация алгоритма SCAN – циклическое сканирование. Когда головка достигает одного из краев диска, она без чтения попутных запросов (иногда существенно быстрее, чем при выполнении обычного поиска цилиндра) перемещается на другой край, откуда вновь начинает свое движение. Для этого алгоритма, получившего название C-SCAN, последовательность перемещений будет выглядеть так:

63->55->31->23->14->10->7->0->99->84->67

По аналогии с алгоритмом LOOK для алгоритма SCAN можно предложить и алгоритм C-LOOK для алгоритма C-SCAN:

63->55->31->23->14->10->7->84->67

Существуют и другие разновидности алгоритмов сканирования, и совсем другие алгоритмы, но мы на этом закончим наше рассмотрение, ибо было сказано: “И еще раз говорю: никто не обнимет необъятного”.

Рекомендуемая литература

1. Bach M.J.. The design of the UNIX Operating System.- Prentice-Hall, 1986

2. Department of Defense. Trusted Computer System Evaluation Criteria. DoD 5200.28?STD. 1993.

3. Department of Trade and Industry. Information Technology Security Evaluation Criteria (ITSEC). Harmonized Criteria of France - Germany - the Netherlands - the United Kingdom. London. 1991.

4. "i486™ Microprocessor", Intel Corporation, 1989.

5. Linnaeus, Karl, "Systema naturae", 13 ed., t. 1-3, Lugduni, 1789-96;

6. Ritchie D.M. "The Evolution of the Unix Time-sharing System", AT&T Bell Laboratories Technical Journal 63 No. 6 Part 2, October 1984, pp. 1577-93.

7. Security Architecture for Open Systems Interconnection for CCITT Applications. Recommendations X.800. CCITT. Geneva. 1991.

8. Silberschatz A., P.B.Galvin, Operating System Concepts. - John Willey & Sons, 1997.

9. Solomon D.A., Russinovich M.E.. Inside Microsoft Windows 2000. Microsoft Press, 2000.

10. Stevens R. W, "Unix Network Programming", Prentice Hall, Inc., 1990, First edition.

11. Stevens R. W, "Unix Network Programming", Prentice Hall, Inc., volume 1-2, 1998, Second edition.

12. Tanenbaum A.S.. Modern Operating Systems. - Prentice Hall, 1992

13. Ахо В., Хопкрофт Д., Ульман Д. Структуры данных и алгоритмы. "Вильямс". 2001.

14. Беляков М.И., Рабовер Ю.И., Фридман А.Л. "Мобильная операционная система", М., Радио и связь, 1991.

15. Блэк. У. Интернет: протоколы безопасности. Учебный курс. "Питер", 2001.

16. Брамм П., Брамм Д. "Микропроцессор 80386 и его применение", М., Мир, 1990.

17. Гостехкомиссия России. Руководящий документ. Автоматизированные системы. Защита от несанкционированного доступа к информации. Классификация автоматизированных систем и требования по защите информации. М., 1992.

18. Гостехкомиссия России. Руководящий документ. Временное положение по организации разработки, изготовления и эксплуатации программных и технических средств защиты информации от НСД в автоматизированных системах и средствах вычислительной техники. М., 1992.

19. Гостехкомиссия России. Руководящий документ. Защита от несанкционированного доступа к информации. Термины и определения. М., 1992.

20. Гостехкомиссия России. Руководящий документ. Концепция защиты СВТ и АС от НСД к информации. М., 1992.

21. Гостехкомиссия России. Руководящий документ. Средства вычислительной техники. Защита от несанкционированного доступа к информации. Показатели защищенности от НСД к информации. М., 1992.

22. Дейтел Г. Введение в операционные системы. М.: Мир. 1987.

23. Дунаев С. Unix. System V. Release 4.2. М.: Диалог МИФИ. 1996.

24. Кастер Хелен. Основы Windows NT и NTFS. М.: Русская редакция. 1996.

25. Казаринов Ю.М., Номоконов В.М., Подклетнов Г.С., Филиппов Ф.М. "Микропроцессорный комплекс К1810", М.,Высшая школа, 1990.

26. Керниган Б. В, Пайк Р. UNIX - универсальная среда программирования. М.:Финансы и статистика. 1992.

27. Коффрон Дж. "Технические средства микропроцессорных систем", М., Мир, 1983.

28. Кузнецов С.Д.. Операционная система UNIX. -http://www.citforum.ru/operating_systems/unix/contents.shtml

29. Олифер В.Г., Олифер Н.А.. Новые технологии и оборудование IP-сетей.-<БХВ-Санкт-Питербург>.2000.

30. Олифер В.Г., Олифер Н.А.. Сетевые операционные системы. - Издательский дом <Питер>, 2001.

31. Снейдер Й. "Эффективное программирование TCP/IP", Питер, 2001

32. Робачевский Андрей. Операционная система UNIX. - BHV, 1999.

33. Цикритис Д.,Бернстайн Ф.. Операционные системы. М.: Мир. 1977.