First-Come, First-Served (FCFS)

Простейшим алгоритмом планирования является алгоритм, который принято обозначать аббревиатурой FCFS по первым буквам его английского названия – First-Come, First-Served (первым пришел, первым обслужен). Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он, а точнее, ссылка на его PCB помещается в конец этой очереди. Выбор нового процесса для исполнения осуществляется из начала очереди с удалением оттуда ссылки на его PCB. Очередь подобного типа имеет в программировании специальное наименование – FIFO¹⁾, сокращение от First In, First Out (первым вошел, первым вышел).

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

 

Таблица 3.1.
Процесс	p0	p1	p2
Продолжительность очередного CPU burst

Преимуществом алгоритма FCFS является легкость его реализации, но в то же время он имеет и много недостатков. Рассмотрим следующий пример. Пусть в состоянии готовность находятся три процесса p₀, p₁ и p₂, для которых известны времена их очередных CPU burst. Эти времена приведены в таблице 3.1. в некоторых условных единицах. Для простоты будем полагать, что вся деятельность процессов ограничивается использованием только одного промежутка CPU burst, что процессы не совершают операций ввода-вывода и что время переключения контекста так мало, что им можно пренебречь.

Вопрос 11.

Round Robin (RR)

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

Рис. 3.4. Процессы на карусели

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

Вопрос 11.

Shortest-Job-First (SJF)

При рассмотрении алгоритмов FCFS и RR мы видели, насколько существенным для них является порядок расположения процессов в очереди процессов, готовых к исполнению. Если короткие задачи расположены в очереди ближе к ее началу, то общая производительность этих алгоритмов значительно возрастает. Если бы мы знали время следующих CPU burst для процессов, находящихся в состоянии готовность, то могли бы выбрать для исполнения не процесс из начала очереди, а процесс с минимальной длительностью CPU burst. Если же таких процессов два или больше, то для выбора одного из них можно использовать уже известный нам алгоритм FCFS. Квантование времени при этом не применяется. Описанный алгоритм получил название "кратчайшая работа первой" или Shortest Job First (SJF).

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

 

Вопрос 12.

Многоуровневые очереди в планировании процессов (без обратной связи и с обратной связью)

(Multilevel Queue)

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

Этим очередям приписываются фиксированные приоритеты.

Например, приоритет очереди системных процессов устанавливается выше, чем приоритет очередей пользовательских процессов.

А приоритет очереди процессов, запущенных студентами, ниже, чем для очереди процессов, запущенных преподавателями.

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

Внутри этих очередей для планирования могут применяться самые разные алгоритмы.

Так, например, для больших счетных процессов, не требующих взаимодействия с пользователем (фоновых процессов), может использоваться алгоритм FCFS, а для интерактивных процессов – алгоритм RR.

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

Многоуровневые очереди с обратной связью (Multilevel Feedback Queue)

Дальнейшим развитием алгоритма многоуровневых очередей является добавление к нему механизма обратной связи.

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

Для простоты рассмотрим ситуацию, когда процессы в состоянии готовность организованы в 4 очереди, как на рисунке

Рис. Схема миграции процессов в многоуровневых очередях планирования с обратной связью. Вытеснение процессов более приоритетными процессами и завершение процессов на схеме не показано

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

Процессы в очереди 1 не могут исполняться, если в очереди 0 есть хотя бы один процесс.

Процессы в очереди 2 не будут выбраны для выполнения, пока есть хоть один процесс в очередях 0 и 1.

И наконец, процесс в очереди 3 может получить процессор в свое распоряжение только тогда, когда очереди 0, 1 и 2 пусты.

Если при работе процесса появляется другой процесс в какой-либо более приоритетной очереди, исполняющийся процесс вытесняется новым.

Планирование процессов внутри очередей 0–2 осуществляется с использованием алгоритма RR, планирование процессов в очереди 3 основывается на алгоритме FCFS.

Родившийся процесс поступает в очередь 0. При выборе на исполнение он получает в свое распоряжение квант времени размером 8 единиц. Если продолжительность его CPU burst меньше этого кванта времени, процесс остается в очереди 0. В противном случае он переходит в очередь 1.

Для процессов из очереди 1 квант времени имеет величину 16. Если процесс не укладывается в это время, он переходит в очередь 2. Если укладывается – остается в очереди 1.

В очереди 2 величина кванта времени составляет 32 единицы. Если для непрерывной работы процесса и этого мало, процесс поступает в очередь 3, для которой квантование времени не применяется и, при отсутствии готовых процессов в других очередях, может исполняться до окончания своего CPU burst.

Чем больше значение продолжительности CPU burst, тем в менее приоритетную очередь попадает процесс, но тем на большее процессорное время он может рассчитывать.

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

Миграция процессов в обратном направлении может осуществляться по различным принципам.

Например, после завершения ожидания ввода с клавиатуры процессы из очередей 1, 2 и 3 могут помещаться в очередь 0, после завершения дисковых операций ввода-вывода процессы из очередей 2 и 3 могут помещаться в очередь 1, а после завершения ожидания всех других событий – из очереди 3 в очередь 2.

Перемещение процессов из очередей с низкими приоритетами в очереди с высокими приоритетами позволяет более полно учитывать изменение поведения процессов с течением времени.

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

Они наиболее трудны в реализации, но в то же время обладают наибольшей гибкостью.

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

· Количество очередей для процессов, находящихся в состоянии готовность.

· Алгоритм планирования, действующий между очередями.

· Алгоритмы планирования, действующие внутри очередей.

· Правила помещения родившегося процесса в одну из очередей.

· Правила перевода процессов из одной очереди в другую.

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

Вопрос 12.

Взаимодействие между процессами (англ. Inter-Process Communication, сокращенно англ. IPC) - набор средств обмена сообщениями процессами.

Средства IPC могут использоваться для взаимодействия процессов:

· которые выполняются на одном компьютере (для многомашинных систем - под управлением одной операционной системы), также известные как собственно IPC;

· которые выполняются на разных компьютерах (для многомашинных систем - под управлением отдельных операционных систем), также известные как средства межмашинного взаимодействия;

· для обеспечения взаимодействия процесса с самим собой - например, для синхронизации или обмена данными между различными нитями одного процесса.

 

Взаимодействие процессов внутри одной машины

Для взаимодействия процессов, выполняемых на одном компьютере (под управлением одной операционной системы) используют (механизмы взаимодействия обеспечиваются ядром операционной системы, в которой выполняются процессы):

· сигналы - асинхронные (неожиданные) сообщения, не передают данные между процессами, а извещают о событии (чрезвычайной ситуации), на которую процесс должен отреагировать выполнением предустановленной действия (функции или команды в зависимости от использованных средств программирования);

· неименованные и именованные каналы (англ. pipes) передачи данных как синхронных (ожидаемых) сообщений; отправки сообщения происходит подобно операции записи в файл, получения - подобно чтения данных из файла, если канал пуст - процесс, который ожидает данные приостанавливается до поступления данных в канал.

· очереди сообщений - пакеты данных, передаваемые между процессами с увидомленням получателя о поступлении пакета;

· сегменты делимой памяти - средство, позволяющее нескольким процессам совместно использовать (разделять) фрагмент оперативной памяти с целью обмена данными; отправка данных происходит путем записи в память, получения - чтением из памяти.

 

Взаимодействие процессов, выполняемых на разных машинах

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

· прямое использование сокетов - технология, требующая программирования на низком уровне и реализации протокола передачи данных;

· RPC (Remote Procedure Call), удаленный вызов процедур - технология, обеспечивающая взаимодействие между процессами подобно вызова функций, данные в одну сторону передаются как аргументы функций (удаленных процедур), в другом - как результаты выполнения функций (удаленных процедур).

· CORBA - технология, предусматривающая возможность взаимодействия между процессами как между объектами CORBA, является дальнейшим развитием технологии RPC.

Также существуют и другие технологии, которые в основном являются модификациями существующих: XML-RPC, SOAP и т.п.. Кроме того, сокеты могут использоваться также для взаимодействия процессов в пределах одной машины, так например работает x.Org.

 

Вопрос 12.

ПОТОКИ (нити)

Потоки в операционных системах нужны для двух вещей – для параллелизма и одновременности.

Параллелизм – это физически одновременное выполнение для достижения наибольшей производительности(например, между двумя ядрами).

Одновременность – логическое и/или физическое одновременное выполнение (есть один ЦП, на нем одновременно выполняется несколько программ – многозадачная ОС).

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

Потоки – другой способ достичь параллелизма. Потоки работают внутри одного процесса. Все потоки процесса имеют одно адресное пространство и те же ресурсы ОС. У потоков есть свой стек и свое состояние ЦП.

 

Многопоточность полезна для:

· обработки одновременных событий

· построение параллельных программ.

Поддержка многопоточности – разделение понятие процесса от минимального потока управления.

· Для параллельного потока выполнения не нужно создавать новые процессы.

· Работает быстрее, меньше требования к памяти.

Раньше: «Процесс»= адресное пространство + ресурсы ОС+ подразумевался единственный поток

Раньше: «Процесс»= адресное пространство + ресурсы ОС+ все потоки принадлежат процессу

Какие бывают потоки?

 

Вопрос 13.

 

Тупики

Гонки