Барьеры

Некоторые приложения делятся на фазы, и существует правило, что процесс не может перейти в следующую фазу, пока к этому не готовы все остальные процессы. Этого можно добиться, разместив в конце каждой фазы барьер. Когда процесс доходит до барьера, он блокируется, пока все процессы не дойдут до барьера. Приведем пример, допустим, у нас есть четыре процесса, приближающиеся к барьеру. Это означает, что они заняты вычислениями и еще не дошли до конца фазы. Через некоторое время первый процесс завершает вычисления, предусмотренные в этой фазе. Он выполняет примитив barrier, чаще всего вызывая библиотечную процедуру. Затем процесс приостанавливается. Через некоторое время второй и третий процессы заканчивают первую фазу и выполняют примитив barrier. Наконец, когда последний процесс достигает барьера, все процессы переходят в следующую фазу.

Сокеты

Сокет – это программный интерфейс для обеспечения обмена данными между процессами.

Сокеты подобны почтовым ящикам и телефонным розеткам в том смысле, что они образуют пользовательский интерфейс с сетью, как почтовые ящики формируют интерфейс с почтовой системой, а телефонные ро­зетки позволяют абоненту подключить телефон и соединиться с телефонной сис­темой.

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

Каждый сокет поддерживает определенный тип работы в сети, указываемый при создании сокета. Наиболее распространенными типами сокетов являются:

1. Надежный, ориентированный на соединение “байтовый поток”.

2. Надежный, ориентированный на соединение “поток пакетов”.

3. Ненадежная передача пакетов.

Первый тип сокетов позволяет двум процессам на различных машинах устано­вить между собой эквивалент «трубы» (канала между процессами на одной машине). Байты подаются в канал с одного конца и в том же порядке выходят с другого. Такая система гарантирует, что все посланные байты прибудут на другой конец канала и прибудут именно в том порядке, в котором были отправлены.

Второй тип сокетов отличается от первого тем, что он сохраняет границы меж­ду пакетами. Если отправитель пять раз отдельно обращается к системному вызо­ву write, каждый раз отправляя по 512 байт, а получатель запрашивает 2560 байт по сокету типа 1, он получит все 2560 байт сразу. При использовании сокета типа 2 ему будут выданы только первые 512 байт. Чтобы получить остальные байты, получателю придется выполнить системный вызов read еще четыре раза.

Третий тип сокетов предоставляет пользователю доступ к «голой» сети. Этот тип сокета особенно полезен для приложений реального времени и ситуаций, в которых пользователь хочет реализовать специальную схему обработки ошибок. Сеть может терять пакеты или доставлять их в неверном порядке. В отличие от сокетов первых двух типов, сокет типа 3 не предоставляет никаких гарантий доставки. Преиму­щество этого режима заключается в более высокой производительности, которая в некоторых ситуациях оказывается важнее надежности.

При создании сокета один из параметров указывает протокол, используемый для него. Для надежных байтовых потоков используется протокол ТСР (Transmission control protocol — протокол управления передачей). Для ненадежной передачи пакетов обычно применяется протокол UDP (User data protocol— пользовательский протокол данных).

Прежде чем сокет может быть использован для работы в сети, с ним должен быть связан адрес. Этот адрес может принадлежать к одному из нескольких про­странств адресов. Наиболее распространенным пространством является простран­ство адресов Интернета, использующее 32-разрядные числа для идентификации конечных адресатов в протоколе IPv4 и 128-разрядные числа в протоколе IPv6.

Как только сокеты созданы на компьютере-источнике и компьютере-приемни­ке, между ними может быть установлено соединение (для ориентированной на соединение связи). Одна сторона обращается к системному вызову listen, указы­вая в качестве параметра локальный сокет. При этом системный вызов создает буфер и блокируется до тех пор, пока не прибудут данные. Другая сторона обра­щается к системному вызову connect, задавая в параметрах дескриптор файла для локального сокета и адрес удаленного сокета. Если удаленный компьютер прини­мает вызов, тогда система устанавливает соединение между двумя сокетами.

Функции установленного соединения аналогичны функциям канала. Процесс может читать из канала и писать в него, используя дескриптор файла для локаль­ного сокета. Когда соединение более не нужно, оно может быть закрыто обычным способом, при помощи системного вызова close.

Планирование

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

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

Алгоритм планирования – алгоритм, используемый планировщиком.

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

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

большую часть времени работает один процесс.

время процессора не представляет собой дефицитный ресурс.

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

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

С увеличением скорости процессоров про­цессы все больше зависят от устройств ввода-вывода. Поэтому пла­нирование процессов с ограниченными возможностями ввода-вывода имеет большее значение.

Самым важным в планировании является выбор момента при­нятия решений. Существует ряд ситуаций, в которых необходимо пла­нирование:

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

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

— при блокировке на операции ввода-вывода, семафоре и т.д., причем причина блокировки влияет на выбор процесса для запуска;

— при прерывании ввода-вывода.

Если аппаратный таймер выполняет периодические прерыва­ния, то решения планировщика могут приниматься при каждом пре­рывании.

Существует два вида алгоритмов планирования:

Неприоритетное планирование — это алгоритм планирования без переключения, при котором выбирается процесс и ему позволяется работать до его блокировки или пока сам процесс не освободит процессор.

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

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

В зависимости от операционной системы можно выделить раз­личные алгоритмы планирования. Можно выделить три вида среды:

— системы пакетной обработки;

— интерактивные системы;

— системы реального времени.

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

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

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

Можно выделить ряд задач, возникающих при планировании в различных средах:

1. Характерные для всех систем:

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

Задача контроля за выполнением принятой политики.

Задача поддержания загруженности всех частей системы.

2. Характерные для систем пакетной обработки данных:

Задача обеспечения максимальной пропускной способности (максимальное количество задач в час).

Задача минимизации времени, затрачиваемого на ожидание обслу­живания и обработку задания (оборотного времени).

Задача поддержания загруженности процессора.

3. Характерные для интерактивных систем:

Минимизация время отклика (быстрая реакция на запросы).

Задача достижения соразмерности, т.е. выполнение пожеланий пользователя.

4. Характерные для систем реального времени:

Задача окончания работы к сроку, т.е. предотвращение потери данных.

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

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

Алгоритмы, используемые в системах пакетной обработки:1) «первым пришел — первым обслужен» Процессам предоставляется доступ к процессору в том порядке, в котором они его запрашивают. Чаще всего формируется единая очередь ждущих процессов. Как только появляется первая задача, она немедленно запускается и работает столько, сколько необходимо. Остальные задачи ставятся в конец очереди. Когда текущий процесс блокируется, запускается следующий в очереди, а когда блокировка снимается, процесс попадает в конец очереди. В этом алгоритме все процессы в состоянии готовности контролируются одним связным списком. Чтобы выбрать процесс для запуска, нужно всего лишь взять первый элемент списка и удалить его. Появление нового процесса приводит к помещению его в конец списка.2) «Кратчайшая задача — первая» алгоритм предполагающий, что временные отрезки работы известны заранее. Если в очереди есть несколько одинаково важных задач, планировщик выбирает первой самую короткую задачу. 3) Наименьшее оставшееся время выполнения. Планировщик каждый раз выбирает процесс с наименьшим оставшимся временем выполнения. В этом случае также необходимо заранее знать время выполнения задач. Когда поступает новая задача, ее полное время выполнения сравнивается с оставшимся временем выполнения текущей задачи. Если время выполнения новой задачи меньше, текущий процесс приостанавливается и управление передается новой задаче. Эта схема позволяет быстро обслуживать короткие запросы.4) Трехуровневое планирование. По мере поступления в систему новые задачи сначала помещаются в очередь, хранящуюся на диске. Впускной планировщик выбирает задание и передает его системе. Остальные задания остаются в очереди. Как только задание попало в систему, для него будет создан соответствующий процесс, и он может тут же вступить в борьбу за доступ к процессору. Возможна ситуация, когда процессов слишком много и они все в памяти не помещаются, тогда некоторые из них будут выгружены на диск. Второй уровень планирования определяет, какие процессы можно хранить в памяти, а какие на диске. Этим занимается планировщик памяти. Для оптимизации эффективности системы планировщик памяти должен решить, сколько и каких процессов может одновременно находиться в памяти. Количество процессов, одновременно находящихся в памяти, называется степенью многозадачности. Третий уровень планирования отвечает за доступ процессов, находящихся в состоянии готовности, к процессору.

Планирование в интерактивных системах

1) Циклическое планирование. Каждому процессу предоставляется некоторый интервал времени процессора, так называемый квант времени.Если к концу кванта времени процесс все еще работает, он прерывается, а управление передается другому процессу. Если процесс блокируется или прекращает работу раньше, переход управления происходит в этот момент. Реализация циклического планирования проста. Планировщику нужно всего лишь поддерживать список процессов в состоянии готовности согласно рис. а. Когда процесс исчерпал свой лимит времени, он отправляется в конец списка(рис. б).

Интересным моментом этого алгоритма является длина кванта. слишком малый квант приведет к частому переключению процессов и небольшой эффективности, но слишком большой квант может привести к медленному реагированию на короткие интерактивные запросы. Значение кванта около 20-50 мс часто является разумным компромиссом.

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

3) Несколько очередей. Процессам класса с высшим приоритетом выделяется один квант, процессам следующего класса — два кванта, следующего — четыре кванта и т. д. Когда процесс использовал все отведенное ему время, он перемещается на класс ниже.4 ) «Самый короткий процесс — следующий» Если рассматривать выполнение каждой команды как отдельную задачу, можно минимизировать общее среднее время отклика, запуская первой самую короткую задачу. Проблема состоит в том, чтобы понять, какой из ожидающих процессов самый короткий. Один из методов основывается на оценке длины процесса, базирующейся на предыдущем поведении процесса. При этом запускается процесс, у которого оцененное время самое маленькое. 5) Гарантированное планирование. Система должна отслеживать распределение процессора между процессами с момента создания каждого процесса. Затем система рассчитывает количество ресурсов процессора, на которое процесс имеет право, Теперь можно сосчитать отношение времени, предоставленного процессу, к времени, на которое он имеет право. Полученное значение 0,5 означает, что процессу выделили только половину положенного, а 2,0 означает, что процессу досталось в два раза больше, чем положено. Затем запускается процесс, у которого это отношение наименьшее, пока оно не станет больше, чем у его ближайшего соседа.6 ) Лотерейное планировани е. Когда планировщику необходимо принять решение, выбирается случайным образом лотерейный билет, и его обладатель получает доступ к ресурсу. билетов. лотерейное планирование обладает высокой отзывчивостью. Взаимодействующие процессы могут при необходимости обмениваться билетами. 7) Справедливое планирование. каждому пользователю достается некоторая доля процессора, и планировщик выбирает процесс в соответствии с этим фактом. Если каждому из пользователей было обещано по 50 % процессора, то им достанется по 50 % процессора, независимоот количества процессов.

Планирование в системах реального времени

Планирование в реальном времени – планирование нескольких конкурирующих процессов, у некоторых (или у всех) из них есть жесткие сроки выполнения работ.

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

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

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

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

Алгоритмы реального времени могут быть статическими или динамическими.

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

Условия выполнения статического Алгоритма RMS:

1.Каждый периодичесий процесс должен быть завершен за время его периода.

2. Ни один процесс не должен зависеть от любого другого процесса.

3. каждому процессу требуется одинакового процессорное время на каждом интревале

4. у непериодических процессов нет жестких сроков.

5. прерывание процесса происходит мгновенно, без накладных расходов

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