Глава_1 (1085730), страница 10

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 10)

}}

void customer(void)

/* Вход в критическую область */

down(&mutex);

if (waiting < CHAIRS) {

waiting = waiting -1;

up(&customers);rs);

up(&mutex);

down(&barbers);

get_haircut (); } } else {

up(&mutex);

} }

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

Если свободный стул есть, посетитель увеличивает значение целочисленной переменной waiting. Затем он выполняет процедуру up на семафоре customers, тем

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

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

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

^{Планирование}

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

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

Введение в планирование

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

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

Во-вторых, компьютеры стали настолько быстрее, что время процессора прак­тически перестало быть дефицитным ресурсом. Большинство программ для пер­сонального компьютера ограничены скоростью, с которой пользователь вводит входные данные (с клавиатуры или с помощью мыши), а не скоростью процессо­ра. Даже процедуры компиляции, основные потребители процессорного времени прошлого, теперь занимают всего несколько секунд. Если одновременно запуще­ны две программы, например текстовый редактор и электронная таблица, и то вряд ли имеет значение, которая из них была первой, поскольку пользователь, вероят­но, ждет окончания работы обеих. Таким образом, на простых персональных ком­пьютерах планирование не играет существенной роли. Разумеется, существуют приложения, занимающие практически весь процессор: визуализация одного часа видеозаписи может потребовать обрабатывающих мощностей промышленного уровня для всех 108 000 кадров формата NTSC (90 000 кадров формата PAL), но подобные приложения являются скорее исключением из правила.

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

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

Поведение процесса

Практически все процессы чередуют периоды вычислений с операциями (диско­выми) ввода-вывода, как показано на рис. 2.20. Обычно процессор некоторое время работает без остановки, затем происходит системный вызов на чтение из файла или запись в файл. После выполнения системного вызова процессор опять считает, пока ему не понадобятся новые данные или не потребуется записать полученные данные и т. д. Заметьте, что некоторые операции ввода-вывода считаются вычис­лениями. Например, когда процессор копирует биты в видео-ОЗУ, чтобы перери­совать экран, он вычисляет, а не выполняет операцию ввода-вывода, поскольку задействован процессор. С этой точки зрения операция ввода-вывода выполняется в случае, если процесс входит в состояние блокировки, ожидая окончания работы внешнего устройства. Важно отметить, что некоторые процессы, как на рис. 2.20, а, большую часть времени заняты вычислениями, а другие, как на рис. 2.20, б, большую часть време­ни ожидают ввода-вывода. Первые называются ограниченными возможностями процессора, вторые — ограниченными возможностями устройств ввода-вывода.

а

Длинный пакет Ожидание ввода-вывода

Короткий пакет

б

В ремя

Рис. 2.20. Периоды использования процессора, чередующиеся с ожиданием ввода-вывода:

процесс, ограниченный возможностями процессора (а); процесс, ограниченный

возможностями устройств ввода-вывода (б)

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

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

Когда планировать?

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

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

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

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

Характеристики

Список файлов книги