Что обозначает аббревиатура fcfs в программировании

4.2.5 Стратегии планирования

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

Простейшая стратегия «первым пришел, первым обслужен» — FCFS (First Come, First Served) назначает всем процессам одинаковые приоритеты и всегда выбирает для выполнения процесс, который находится в очереди дольше всех. По существу процессы помещаются в низ («хвост») очереди и берутся из ее вершины («головы»). Структура списка готовности, опирающаяся на планирование FCFS и связанный список, представлена на рис. 2.

Рисунок 2 – Стратегия First Come, First Served

Здесь fqp — указатель очереди процесса, а pcbp — указатель контекста процесса.

Очередь подобного типа имеет в программировании специальное наименование FIFO — сокращение от First In, First Out (первым вошел, первым вышел).

Надо отметить, что аббревиатура FCFS используется для этой стратегии планирования вместо стандартной аббревиатуры FIFO для механизмов подобного типа для того, чтобы подчеркнуть, что организация готовых процессов в очередь FIFO возможна и при других стратегиях планирования (например, для Round Robin).

Указатель первого элемента показывает, какой процесс находится в вершине очереди, а указатель последнего элемента — процесс в низу очереди. Указатель последнего элемента необходим для того, чтобы в очередь можно было помещать новые процессы без просмотра всего списка. В примере предполагается, что каждый процесс имеет ID (идентификатор), который совпадает с позицией в массиве, содержащем связанный список (как в FAT). Предполагается также, что очередь состоит из процессов 3, 6, 2, 8 и 5. Следовательно, указатель первого элемента содержит 3, указатель последнего элемента содержит 5, а процессы 2, 3, 5, 6 и 8 находятся в состоянии готовности. Остальные элементы в таблице процессов либо заняты выполняемыми, либо заблокированными процессами, либо в данное время не используются. Если число 0 применяется для указания конца списка, его нельзя употреблять в качестве ID процесса.

Стратегия FCFS осуществляет невытесняющее планирование.

Модификацией стратегии FCFS является стратегия, получивший название Round Robin(Round Robin – вид детской карусели в США) или сокращенно RR. По сути дела это та же самая стратегия, только реализованная в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически — процессы «сидят на карусели». Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 — 100 миллисекунд. Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение для исполнения (рис. 3).

Рисунок 3 – Стратегия Round Robin

Реализуют такую стратегию так же, как и предыдущую, с помощью организации процессов, находящихся в состоянии «готовность», в очередь FIFO. Планировщик выбирает для очередного исполнения процесс, расположенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени. При выполнении процесса возможны два варианта:

• время непрерывного использования процессора, требующееся процессу, (остаток текущего CPU burst) меньше или равно продолжительности кванта времени. Тогда процесс по своей воле освобождает процессор до истечения кванта времени, на исполнение выбирается новый процесс из начала очереди и таймер начинает отсчет кванта заново;
• продолжительность остатка текущего CPU burst процесса больше, чем квант времени. Тогда по истечении этого кванта процесс прерывается таймером и помещается в конец очереди процессов готовых к исполнению, а процессор выделяется для использования процессу, находящемуся в ее начале.

Round Robin (RR)

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin (Round Robin — это вид детской карусели в США) или сокращенно RR. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования.

Можно представить себе все множество готовых процессов организованным циклически — процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10-100 миллисекунд (см. рис. 3.4). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

Реализуется такой алгоритм так же, как и предыдущий, с помощью организации процессов, находящихся в состоянии готовность, в очередь FIFO. Планировщик выбирает для очередного исполнения процесс, рас-

положенный в начале очереди, и устанавливает таймер для генерации прерывания по истечении определенного кванта времени.

При выполнении процесса возможны два варианта:

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

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

Рассмотрим предыдущий пример с порядком процессов ро, pi, рг и величиной кванта времени, равной 4. Выполнение этих процессов иллюстрируется таблицей 3.2. Обозначение «И» используется в ней для процесса, находящегося в состоянии исполнение, обозначение «Г» — для процессов в состоянии готовность, пустые ячейки соответствуют завершившимся процессам. Состояния процессов показаны на протяжении соответствующей единицы времени, т. е. колонка с номером 1 соответствует промежутку времени от 0 до 1.

Первым для исполнения выбирается процесс ро- Продолжительность его CPU burst больше, чем величина кванта времени, и поэтому процесс исполняется до истечения кванта, т. е. в течение 4 единиц времени. После этого он помещается в конец очереди готовых к исполнению процессов, которая принимает вид pi, рг, ро- Следующим начинает выполняться процесс рь Время его исполнения совпадает с величиной выделенного кванта, поэтому процесс работает до своего завершения. Теперь очередь процессов всостоянии готовность состоит из двух процессов — рг и ро. Процессор выделяется процессу рг. Он завершается до истечения отпущенного ему процессорного времени, и очередные кванты отмеряются процессу ро — единственному не закончившему к этому моменту свою работу. Время ожидания для процесса ро (количество символов «Г» в соответствующей строке) составляет 5 единиц времени, для процесса Р1 — 4 единицы времени, для процесса рг — 8 единиц времени. Таким образом, среднее время ожидания для этого алгоритма получается равным (5 + 4 + 8)/3 = 5,6 (6) единицам времени. Полное время выполнения для процесса ро (количество непустых столбцов в соответствующей строке) составляет 18 единиц времени, для процесса Р1 — 8 единиц, для процесса рг — 9 единиц. Среднее полное время выполнения оказывается равным (18 + 8 + 9)/3 = 11,6 (6) единицам времени.

Легко увидеть, что среднее время ожидания и среднее полное время выполнения для обратного порядка процессов не отличаются от соответствующих времен для алгоритма РСРБ и составляют 2 и 6 единиц времени соответственно.

На производительность алгоритма ЯЯ сильно влияет величина кванта времени. Рассмотрим тот же самый пример с порядком процессов ро, Рь рг для величины кванта времени, равной 1 (см. табл. 3.3). Время ожидания для процесса ро составит 5 единиц времени, для процесса р| — тоже 5 единиц, для процесса рг — 2 единицы. В этом случае среднее время ожидания получается равным (5 + 5 + 2)/3 = 4 единицам времени. Среднее полное время исполнения составит (18 + 9 + 3)/3 = 10 единиц времени.

При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS. При очень малых величинах создается иллюзия того, что каждый из п процессов работает на собственном виртуальном процессоре с производительностью ~ 1/п от производительности реального процессора. Правда, это справедливо лишь при теоретическом анализе при условии пренебрежения временами переключения контекста процессов. В реальных условиях при слишком малой величине кванта времени и, соответственно, слишком частом переключении контекста накладные расходы на переключение резко снижают производительность системы.

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 цилиндре. Тогда положение головок будет меняться следующим образом:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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.

17) алгоритм планирования FCFS

Что такое метод «первым пришел, первым обслужен»?

First Come First Serve (FCFS) – это алгоритм планирования операционной системы, который автоматически выполняет запросы и процессы в очереди в порядке их поступления. Это самый простой и простой алгоритм планирования процессора. В алгоритме этого типа процессы, которые сначала запрашивают ЦП, сначала получают распределение ЦП. Это управляется с помощью очереди FIFO. Полной формой FCFS является First Come First Serve.

Когда процесс входит в готовую очередь, его PCB (блок управления процессом) связывается с хвостом очереди и, когда ЦП становится свободным, его следует назначить процессу в начале очереди.

Из этого руководства по операционной системе вы узнаете:

• Что такое метод «первым пришел, первым обслужен»?
• Характеристики метода FCFS
• Пример планирования FCFS
• Как работает FCFS? Расчет среднего времени ожидания
• Преимущества FCFS
• Недостатки FCFS

Характеристики метода FCFS

• Он поддерживает алгоритм упреждающего и упреждающего планирования.
• Задания всегда выполняются в порядке поступления.
• Это легко реализовать и использовать.
• Этот метод имеет низкую производительность, и общее время ожидания довольно велико.

Пример планирования FCFS

Реальный пример метода FCFS – покупка билета в кино на кассе. В этом алгоритме планирования человек обслуживается согласно порядку очереди. Человек, который прибывает первым в очереди, сначала покупает билет, а затем следующий. Это будет продолжаться до тех пор, пока последний человек в очереди не купит билет. Используя этот алгоритм, процесс ЦП работает аналогичным образом.

Как работает FCFS? Расчет среднего времени ожидания

Вот пример пяти процессов, прибывающих в разное время. Каждый процесс имеет разное время посылки.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Используя алгоритм планирования FCFS, эти процессы обрабатываются следующим образом.

Шаг 0) Процесс начинается с P4, который имеет время прибытия 0

Шаг 1) В момент времени = 1 приходит P3. P4 все еще выполняется. Следовательно, P3 хранится в очереди.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Шаг 2) В момент времени = 2 прибывает P1, который сохраняется в очереди.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Шаг 3) В момент времени = 3 процесс P4 завершает свое выполнение.

Шаг 4) В момент времени = 4, P3, который является первым в очереди, начинает выполнение.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Шаг 5) В момент времени = 5 приходит P2, и он сохраняется в очереди.

Обработать	Время взрыва	Время прибытия
P1	6	2
P2	3	5
P3	8	1
P4	3	0
P5	4	4

Шаг 6) В момент 11 P3 завершает свое выполнение.

Шаг 7) В момент времени = 11, P1 начинает выполнение. Он имеет время пакета 6. Он завершает выполнение через интервал времени 17

Шаг 8) В момент времени = 17, P5 начинает выполнение. Он имеет время пакета 4. Он завершает выполнение в момент времени = 21

Шаг 9) В момент времени = 21 P2 начинает выполнение. Он имеет время пакета 2. Он завершает выполнение через интервал времени 23

Шаг 10) Рассчитаем среднее время ожидания для приведенного выше примера.

Waiting time = Start time - Arrival time

Среднее время ожидания

Преимущества FCFS

Вот преимущества и преимущества использования алгоритма планирования FCFS:

• Простейшая форма алгоритма планирования процессора
• Легко программировать
• Первым прибыл – первым обслужен Эквивалент в русском языке: поздний гость гложет и кость

Недостатки FCFS

Вот минусы / недостатки использования алгоритма планирования FCFS:

• Это непланирующий алгоритм планирования ЦП, поэтому после выделения процесса ЦП он никогда не освободит ЦП, пока не завершит выполнение.
• Среднее время ожидания высокое.
• Короткие процессы, которые находятся в конце очереди, должны ждать завершения длинного процесса на фронте.
• Не идеальная техника для систем с разделением времени.
• Из-за своей простоты FCFS не очень эффективна.

Резюме:

• Определение: FCFS – это алгоритм планирования операционной системы, который автоматически выполняет запросы и процессы, поставленные в очередь, в порядке их поступления
• Поддерживает не вытесняющее и упреждающее планирование
• алгоритм.
• FCFS расшифровывается как First Come First Serve
• Реальный пример метода FCFS – покупка билета в кино на кассе.
• Это самая простая форма алгоритма планирования процессора
• Это непланирующий алгоритм планирования ЦП, поэтому после выделения процесса ЦП он никогда не освободит ЦП, пока не завершит выполнение.