P Sendlink = О

P Callerq

Р Sendlink = О

Р Sendlink

P Calierq

Рис. 2.19. Очереди процессов, ожидающих отправления сообщения процессу О

Если ни одного подходящего отправителя не найдено, делается проверка флага pJnt blocked, который означает, что ранее было заблокировано прерывание для данного получателя. Если это так, создается новое сообщение (так как сообщения от HARDWARE не имеют содержимого и всегда относятся к типу HARD INT, копировать буфер в этом случае не нужно).

Если заблокированного прерывания не обнаружено, адрес приемного буфера сохраняется в таблице процессов, а сам процесс переводится в состояние ожидания путем установки бита RECEIVING. Вызов unready исключает данный процесс из очереди готовых к запуску процессов. Перед вызовом unready делается проверка, не установлены ли у него другие флаги в p flags. У процесса могут иметься текущие сигналы, и если это так, ему нужна возможность обработать их.

Предпоследнее выражение в mini rec связано с тем, как обрабатываются генерируемые ядром сигналы SIGINT, SIGQUIT и SIGALARM. Когда генерируется один из этих сигналов, менеджеру памяти посылается сообщение, если он ждет уведомления от ANY. Если менеджер памяти такого сообщения не ждет, сигнал запоминается в ядре до тех пор, пока ММ не попытается получить сообщение от ANY. В коде делается проверка этого условия и при необходимости вызывается inform.

2.6.9. Планирование процессов в MINIX

в MINIX применяется многоуровневый алгоритм планирования, структура которого близка к показанной на рис. 2.20. На этом рисунке мы видим задачи ввода/вывода на уровне 2, сервера на уровне 3 и пользовательские процессы на уровне 4. У планировщика есть три очереди готовых к работе процессов, по одной на каждый слой, как показано на рисунке. Массив rdy head содержит по одному элементу на каждую из очередей, в котором хранится указатель на начало соответствующей очереди. Аналогично, массив rdy tail хранит указатели на конец каждой из очередей. Оба этих массива описаны в proc.h при помощи макроса EXTERN.

Каждый раз, когда приостановленный процесс вновь приходит в состояние готовности, он помещается в хвост соответствующей очереди. Эффективное добавление элемента в хвост списка обеспечивает массив rdy taiL А когда выпол-

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

Rdy head

Rdy tail

Рис. 2.20. Три очереди планировщика, no одной на каждый уровень приоритета

Алгоритм диспетчеризации с описанной выше структурой очередей прост. Берется непустая очередь с наивысшим приоритетом, в которой выбирается первый процесс. Если же все очереди пусты, выбирается подпрограмма бездействия. На рис. 2.20 наибольший приоритет у очереди TASK Q. Код планировщика находится в файле ргос.с. Очередь выбирается в функции pick proc, основная задача которой - установить значение proc ptr. Если над очередями производятся какие-либо действия, которые могут повлиять на выбор следующего готового процесса, то pick proc необходимо вызвать снова. Эта функция вызывается каждый раз, когда блокируется один процесс, с целью поставить на выполнение следующий.

Сама функция pick proc по простоте сродни алгоритму. Сначала проверяется каждая из очередей: в первую очередь TASK Q, и при наличии в ней процесса устанавливается значение proc ptr, и функция немедленно завершается. Далее проверяется очередь SERVER Q, и, опять же, если она не пуста, устанавливается proc ptr и функция завершается. Затем, если в очереди USER Q имеются готовые процессы, устанавливается значение переменной bilLptr, чтобы обозначить, что за процессорное время, которое будет отдано процессу, отвечает именно он. Если ни в одной из очередей нет готовых к работе процессов, следующая строка перекладывает учет времени на процесс IDLE, который и выбирается на выполнение планировщиком. Выбранный процесс не исключается из очереди.

Для управления очередями служат процедуры ready и unready, первая из них предназначена для постановки процесса в его очередь, а вторая убирает процесс из очереди готовых к запуску. Как мы видели, ready вызывается из mini send и из mini rec. Кроме того, ready можно было бы использовать в функции interrupt, но по соображениям производительности код ready встроен в pick proc. Функция ready модифицирует одну из трех очередей, добавляя новый процесс в хвост очереди.

Функция unready также управляет очередями. В обычной ситуации она удаляет процесс из хвоста очереди, так как, чтобы попасть в состояние блокировки, процесс должен выполняться. В этом случае unready перед тем, как завершиться, вызывает pick proc. Процесс может попасть в состояние блокировки и в результате сигнала. Тогда, если процесс не найден в хвосте очереди, он ищется во всей цепочке USER Q.

Хотя большая часть действий по планированию процессов происходит, когда процесс блокируется или приходит в готовность, планирование необходимо и тогда, когда задача таймера сообщает, что квант времени текущего процесса истек. В данном случае задача таймера вызывает функцию sched, которая перемещает процесс из начала очереди USER Q в конец. Благодаря такому алгоритму пользовательские процессы выполняются по кругу (алгоритм циклического планирования). Файловая система, менеджер памяти и задачи ввода/вывода никогда не перемещаются в конец очереди. Им оказывается доверие, и блокируются они тогда, когда завершают свою работу.

В ргос.с есть еще несколько процедур, необходимых для планирования. Пять из них: lock mini send, lock pick proc, lock ready, lock unready и lock sched устанавливают значение переменной-семафора switching перед вызовом соответствующей функции, а затем освобождают семафор после завершения функции. Последняя функция в файле, unhold, упоминалась при обсуждении .restart в mpx386.s. Она просматривает очередь задержанных прерываний, вызывая для каждого из них interrupt, чтобы все прерывания были преобразованы в сообщения, до того как какой-либо из процессов запустится.

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

2.6.10. Аппаратно-зависимая поддержка в ядре

в системе есть несколько функций на С, которые очень существенно зависят от аппаратной платформы. Чтобы способствовать переносу MINIX на разные платформы, такие функции вьщелены в отдельные файлы: ехсерпоп.с, i8259.c и protectc, а не помещены в том же файле, в котором они используются.

Файл exception.с содержит обработчик исключений, функцию exception, которая вызывается из ассемблерной программы обработки исключений в mpx386.s (вызывается как .exception). Когда исключение исходит от пользователя, оно преобразуется в сигнал, так как ошибки в пользовательских программах ожидаемы. Но когда исключение исходит от операционной системы, это признак того, что произошло нечто действительно серьезное. Такое исключение приводит к сообщению о сбое ядра (kernel panic). Сообщение, которое при этом будет выведено на экран, или сигнал, который будет послан приложению, задаются массивом ex data. Третье поле задает минимальный номер модели процессора, поддерживающего данное прерывание, поскольку круг прерываний в ранних моделях процессоров Intel более узок. Этот массив является интересным индикатором развития семейства процессоров Intel, на которых реализована MINIX.