Алгоритмы планирования
Планирование включает в себя решение задач
Определение момента времени для смены выполняемого процесса
Выбор процессов на выполнение из очереди готовых
Переключение контекстов
Рис.2.
2 Группы алгоритмов планирования
1
группа. Бесприоритетные
(на основе квантования)
линейные циклические
могут выбираться:
- в порядке очереди
- случайно.
ВЫТЕСНЯЮЩАЯ МНОГОЗАДАЧНОСТЬ.
2 группа. Приоритетные.
С фиксированными приоритетами С динамическими приоритетами
- относительные приоритеты; приоритет зависит от:
- абсолютные -//-; - t ожидания;
- адаптивные алгоритмы обслуживания. - t обслуживания.
Алгоритмы основанные на квантовании меняют выполняющийся процесс при его совершении, ошибке, переходе в состояние ожидания или завершение ему отведённого кванта времени. Кванты могут быть одинаковыми для всех процессов или различными (фиксированными или динамическими).
Приоритетные алгоритмы могут снимать процесс с выполнения при появлении более приоритетной заявки (абсолютный приоритет). Относительный приоритет влияет только на порядок выбора из очереди. Приоритет может назначаться директивно или вычисляться ОС по заданным правилам, может быть фиксированным или динамическим.
Потоки (Thread)
Поток - часть процесса, способная выполняться квазипараллельно с другими потоками того же процесса. Каждая нить (поток) имеет свой собственный программный счётчик, стек, регистры потоков и состояний. В рамках процессов потоки разделяют: адресное пространство, глобальные переменные, открытые файлы, таймеры, семафоры и статистическую информацию.
Рис.3
Организация
вычислительных процессов с помощью
потоков.
Потоки могут быть реализованы статически, когда их количество и задачи определяются на этапе написания программы или динамически по ходу выполнения. Завершаются потоки по своей инициативе или извне. Многопоточная обработка может быть реализована в пользовательском пространстве или в пространстве ядра.
Средства взаимодействия и синхронизация процессов
Взаимодействие процессов
Категории обмена информацией:
Сигнальная – передаётся минимальное количество данных, используется для извещения о наступлении события. Степень воздействия на поведение процессов получателя минимальна.
Канальные средства – взаимодействие происходит через линии связи, предоставленные ОС, объём данных зависит от пропускной способности линии связи. Степень воздействия на получателя прямо пропорциональна количеству передаваемой информации.
Разделяемая память – область адресного пространства, выделенная ОС для совместного использования. Самый быстрый способ в системе.
При установлении связи различают разные способы адресации:
Прямая - взаимодействующие процессы непосредственно обращаются друг к другу, явно указывая имена или номера. Может быть симметричной, если оба указаны имена адресатов. Ассиметричная – один из процессов явно указывает имя партнёра, второй рассматривает в этом качестве любой процесс системы.
Непрямая адресация – данные помещаются в промежуточный объект хранения, имеющий свой адрес
Количество процессов, которые может быть одновременно ассоциирован с конкретным средством связи, называется валентностью этого средства связи. При прямой адресации валентность будет 2, для непрямой может быть больше.
Связь может быть однонаправленной или симплексной, двунаправленной или дуплексной, полудуплексной – поочерёдная передача данных в разных направлениях.
Рис.4.
Синхронизация
процессов при одновременном доступе к
общим разделяемым ресурсам
Часть программы, в которой осуществляется доступ к разделяемому ресурсу называется критической секцией.
Для исключения эффекта гонок, по отношению к ресурсу, необходимо, чтобы в каждый момент времени в критической секции, связанной с этим ресурсом находился только один процесс (взаимное исключение). С каждым ресурсом связывается двоичная переменная, принимающая значение 1, если ресурс свободен и 0, если занят.
Рис. 5. Алгоритм работы критической секции.
Высокоуровневым средством синхронизации процессов являются семафоры.
Лекция 3. 200912