Билеты (Graur) (Экзамен), страница 10

pid_t wait(int *status);

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

Возвращаемым значением wait() будет идентификатор завершенного процесса, а через параметр status будет возвращена информация о причине завершения процесса (путем вызова _exit() либо прерван сигналом) и коде возврата. Если процесс не интересуется это информацией, он может передать в качестве аргумента вызову wait() NULL-указатель.

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

Жизненный цикл процессов

Рис. 3 Жизненный цикл процесса.

Формирование процессов 0 и 1

Рассмотрим подробнее, что происходит в момент начальной загрузки OC UNIX. Начальная загрузка – это загрузка ядра системы в основную память и ее запуск. Нулевой блок каждой файловой системы предназначен для записи короткой программы, выполняющей начальную загрузку. Начальная загрузка выполняется в несколько этапов.

1.Аппаратный загрузчик читает нулевой блок системного устройства.

2.После чтения этой программы она выполняется, т.е. ищется и считывается в память файл /unix, расположенный в корневом каталоге и который содержит код ядра системы.

3.Запускается на исполнение этот файл.

В самом начале ядром выполняются определенные действия по инициализации системы, а именно, устанавливаются системные часы (для генерации прерываний), формируется диспетчер памяти, формируются значения некоторых структур данных (наборы буферов блоков, буфера индексных дескрипторов) и ряд других. По окончании этих действий происходит инициализация процесса с номером "0". По понятным причинам для этого невозможно использовать методы порождения процессов, изложенные выше, т.е. с использованием функций fork() и exec(). При инициализации этого процесса резервируется память под его контекст и формируется нулевая запись в таблице процессов. Основными отличиями нулевого процесса являются следующие моменты

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

2. Он существует в течении всего времени работы системы (чисто системный процесс) и считается, что он активен, когда работает ядро ОС.

Далее ядро копирует "0" процесс и создает "1" процесс. Алгоритм создания этого процесса напоминает стандартную процедуру, хотя и носит упрощенный характер. Сначала процесс "1" представляет собой полную копию процесса "0" , т.е. у него нет области кода. Далее происходит увеличение его размера и во вновь созданную кодовую область копируется программа, реализующая системный вызов exec() , необходимый для выполнения программы /etc/init. На этом завершается подготовка первых двух процессов. Первый из них представляет собой структуру данных, при помощи которой ядро организует мультипрограммный режим и управление процессами. Второй – это уже подобие реального процесса. Далее ОС переходит к выполнению программ диспетчера. Диспетчер наделен обычными функциями и на первом этапе у него нет выбора – он запускает exec() , который заменит команды процесса "1" кодом, содержащимся в файле /etc/init. Получившийся процесс, называемый init, призван настраивать структуры процессов системы. Далее он подключает интерпретатор команд к системной консоли. Так возникает однопользовательский режим, так как консоль регистрируется с корневыми привилегиями и доступ по каким-либо другим линиям связи невозможен. При выходе из однопользовательского режима init создает многопользовательскую среду. С этой целью init организует процесс getty для каждого активного канала связи, т.е. каждого терминала Это программа ожидает входа кого-либо по каналу связи. Далее, используя системный вызов exec(), getty передает управление программе login, проверяющей пароль. Во время работы ОС процесс init ожидает завершения одного из порожденных им процессов, после чего он активизируется и создает новую программу getty для соответствующего терминала. Таким образом процесс init поддерживает многопользовательскую структуру во время функционирования системы. Схема описанного “круговорота” представлена на Error: Reference source not found

БИЛЕТ 25

Основные задачи планирования

• Планирование очереди процессов на начало обработки

• Планирование распределения времени ЦП между процессами

• Планирование свопинга

• Планирование обработки прерываний

• Планирование очереди запросов на обмен

Планирование распределения времени ЦП между процессами

Квант времени – непрерывный период процессорного времени.

Приоритет процесса – числовое значение, показывающее степень привилегированности процесса при использовании ресурсов ВС (в частности, времени ЦП).

Для грамотного планирования надо решить две задачи:

– определить величину кванта

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

Если величина кванта не ограничена – невытесняющая стратегия планирования времени ЦП (применяется в пакетных системах). Никто принудительно не скидывает процесс с ЦП. Разработчики берут на себя функции диспетчера. Например, программа что-то долго считает => сама периодически снимает себя с ЦП, что могли выполнится задачи требующие меньшее количество времени для выполнения и не могущие долго ждать.

Вытесняющая стратегия - величина кванта ограничена.

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

Рассмотрим, как решается проблема с определения кванта времени.

8.3.1 Кванты постоянной длины.

•Время ожидания кванта процессом ~ q(n-1)

•Параметры: длина очереди и величина кванта.

•Дисциплина обслуживания очереди, например, FIFO.

•Переключение процессов – операция, требующая времени.

Проблема: как определить длину кванта. Слишком маленький – не хватит времени на переключение, большой - некоторые успеют выполниться полностью.

8.3.2 Кванты переменной длины

Величина кванта может меняться со временем

• Вначале «большой» квант q=A,на следующем шаге q=A-t, q=A-2t,…, до q=B (B<A). Преимущество для коротких задач.

• Вначале q=B, далее q=B+t,…, до q=A. Уменьшение накладных расходов на переключение задач, когда несколько задач выполняют длительные вычисления.

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

БИЛЕТ 26 Стратегии планирования времени ЦП. Алгоритмы, основанные на приоритетах.

Алгоритмы, основанные на приоритетах

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

8.4.1 Планирование по наивысшему приоритету (highest priority first - HPF).

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

Возможно два варианта:

- относительный приоритет (ожидание исчерпания кванта у текущего процесса)

- абсолютный приоритет (немедленная смена текущего процесса)

Задача выбора/постановки процесса с наивысшим приоритетом зависит от организации очереди (упорядочена/неупорядочена).

Возможно наличие очередей с одинаковым приоритетом.

Пример использования стратегии HPF.

Выбор самого короткого задания (shortest job first - SJF).

 

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

 Этот вариант

удобен для “коротких” процессов.

8.4.2 Класс подходов, использующих линейно возрастающий приоритет.

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

Из выбора A и В - разные правила планирования:

- Если 0<A<=B обслуживание очереди по дисциплине FIFO

- Если 0>B>=A обслуживание очереди по дисциплине LIFO

8.4.3 Нелинейные функции изменения приоритета

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

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

8.5 Разновидности круговорота.

Простой круговорот (RR – round robin) не использует никакой статистической или динамической информации о приоритетах. (см. рисунок выше)

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

«Эгоистический» круговорот. Если параметры A и B : 0<=B<A.

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

Приоритет выполняемых процессов увеличивается с коэффициентом B<A, следовательно, ожидающие процессы их догонят.

При B=0 «эгоистический» круговорот практически сводится к простому.

8.6 Очереди с обратной связью (feedback – FB).

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

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

«-» Работа с несколькими очередями – издержки.

«+» Удобны для коротких заданий: не требуется предварительная информация о времени выполнения процессов.

БИЛЕТ 27

Смешанные алгоритмы планирования

На практике концепции квантования и приоритетов часто используются совместно.

К примеру, в основе – концепция квантования, а определение кванта и/или дисциплина обслуживания очередей базируется на приоритетах.

БИЛЕТ 28 . Планирование свопинга в ОС UNIX.

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

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

В вычислении приоритета P_PRI используются две изменяемые составляющие - P_NICE и P_CPU. P_NICE - это пользовательская составляющая приоритета. Его начальное значение полагается равным системной константе NZERO, в процессе выполнения процесса P_NICE может модифицироваться системным вызовом nice(). Аргументом этого системного вызова является добавка к текущему значению (для обычного – непривилегированного - процесса эти добавки представляют собой неотрицательные числа). Значение P_NICE наследуется при порождении процессов, и таким образом, значение приоритета не может быть понижено при наследовании. Заметим, что изменяться P_NICE может только в сторону увеличения значения (до некоторого предельного значения), таким образом пользователь может снижать приоритет своих процессов.