Добавлен: 29.10.2018
Просмотров: 48050
Скачиваний: 190
2.5. Классические задачи взаимодействия процессов
201
Решение, представленное в листинге 2.14, не вызывает взаимной блокировки и допу-
скает максимум параллелизма для произвольного числа философов. В нем использу-
ется массив state, в котором отслеживается, чем занимается философ: ест, размышляет
или пытается поесть (пытается взять вилки). Перейти в состояние приема пищи фило-
соф может, только если в этом состоянии не находится ни один из его соседей. Соседи
философа с номером i определяются макросами LEFT и RIGHT. Иными словами, если
i равен 2, то LEFT равен 1, а RIGHT равен 3.
Листинг 2.14. Решение задачи обедающих философов
#define N 5 /* количество философов */
#define LEFT (i+N−1) %N /* номер левого соседа для i-го философа */
#define RIGHT (i+1) %N /* номер правого соседа для i-го
философа */
#define THINKING 0 /* философ размышляет */
#define HUNGRY 1 /* философ пытается взять вилки */
#define EATING 2 /* философ ест спагетти */
typedef int semaphore; /* Семафоры — особый вид целочисленных
переменных */
int state[N]; /* массив для отслеживания состояния
каждого философа */
semaphore mutex = 1; /* Взаимное исключение входа в
критическую область */
semaphore s[N]; /* по одному семафору на каждого
философа */
void philosopher(int i) /* i – номер философа (от 0 до N−1) */
{
while (TRUE) { /* бесконечный цикл */
think(); /* философ размышляет */
take_forks(i); /* берет две вилки или блокируется */
eat(); /* ест спагетти */
put_forks(i); /* кладет обе вилки на стол */
}
}
void take_forks(int i) /* i – номер философа (от 0 до N−1) */
{
down(&mutex); /* вход в критическую область */
state[i] = HUNGRY; /* запись факта стремления философа
поесть */
test(i); /* попытка взять две вилки */
up(&mutex); /* выход из критической области */
down(&s[i]); /* блокирование, если вилки взять не
удалось */
}
void put_forks(i) /* i – номер философа (от 0 до N−1) */
{
down(&mutex); /* вход в критическую область */
state[i] = THINKING; /* философ наелся */
test(LEFT); /* проверка готовности к еде соседа
слева */
test(RIGHT); /* проверка готовности к еде соседа
202
Глава 2. Процессы и потоки
справа */
up(&mutex); /* выход из критической области */
}
void test(i) /* i – номер философа (от 0 до N−1) */
{
if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
state[i] = EATING;
up(&s[i]);
}
}
В программе используется массив семафоров, по одному семафору на каждого фило-
софа, поэтому голодный философ может блокироваться, если нужная ему вилка занята.
Обратите внимание на то, что каждый процесс в качестве своей основной программы
запускает процедуру philosopher, но остальные процедуры: take_forks, put_ forks и test —
это обычные процедуры, а не отдельные процессы.
2.5.2. Задача читателей и писателей
Задача обедающих философов хороша для моделирования процессов, которые сорев-
нуются за исключительный доступ к ограниченному количеству ресурсов, например
к устройствам ввода-вывода. Другая общеизвестная задача касается читателей и пи-
сателей (Courtois et al., 1971). В ней моделируется доступ к базе данных. Представим,
к примеру, систему бронирования авиабилетов, в которой есть множество соревную-
щихся процессов, желающих обратиться к ней для чтения и записи. Вполне допустимо
наличие нескольких процессов, одновременно считывающих информацию из базы
данных, но если один процесс обновляет базу данных (проводит операцию записи),
никакой другой процесс не может получить доступ к базе данных даже для чтения
информации. Вопрос в том, как создать программу для читателей и писателей? Одно
из решений показано в листинге 2.15.
В этом решении первый читатель для получения доступа к базе данных выполняет в от-
ношении семафора db операцию down. А все следующие читатели просто увеличивают
значение счетчика rc. Как только читатели прекращают свою работу, они уменьшают
значение счетчика, а последний из них выполняет в отношении семафора операцию
up, позволяя заблокированному писателю, если таковой имеется, приступить к работе.
В представленном здесь решении есть одна достойная упоминания недостаточно оче-
видная особенность. Допустим, что какой-то читатель уже использует базу данных
и тут появляется еще один читатель. Поскольку одновременная работа двух читателей
разрешена, второй читатель допускается к базе данных. По мере появления к ней могут
быть допущены и другие дополнительные читатели.
Теперь допустим, что появился писатель. Он может не получить доступа к базе данных,
поскольку писатели должны иметь к ней исключительный доступ, поэтому писатель
приостанавливает свою работу. Позже появляются и другие читатели. Доступ до-
полнительным читателям будет открыт до тех пор, пока будет активен хотя бы один
читатель. Вследствие этой стратегии, пока продолжается наплыв читателей, все они
будут получать доступ к базе по мере своего прибытия. Писатель будет приостановлен
до тех пор, пока не останется ни одного читателя. Если новый читатель будет прибы-
вать, скажем, каждые 2 с и каждый читатель затратит на свою работу по 5 с, писатель
доступа никогда не дождется.
2.6. Исследования, посвященные процессам и потокам
203
Чтобы предотвратить такую ситуацию, программу можно слегка изменить: когда пи-
сатель находится в состоянии ожидания, то вновь прибывающий читатель не получает
немедленного доступа, а приостанавливает свою работу и встает в очередь за писателем.
При этом писатель должен дождаться окончания работы тех читателей, которые были
активны при его прибытии, и не должен пережидать тех читателей, которые прибывают
после него. Недостаток этого решения заключается в снижении производительности
за счет меньших показателей параллельности в работе. Куртуа с соавторами (Courtois
et al., 1971) представили решение, дающее приоритет писателям. Подробности этого
решения можно узнать из их статьи.
Листинг 2.15. Решение задачи читателей и писателей
typedef int semaphore; /* напрягите свое воображение */
semaphore mutex = 1; /* управляет доступом к 'rc' */
semaphore db = 1; /* управляет доступом к базе данных */
int rc = 0; /* количество читающих или желающих
читать процессов */
void reader(void)
{
while (TRUE) { /* бесконечный цикл */
down(&mutex); /* получение исключительного доступа к ‘rc’ */
rc = rc + 1; /* теперь на одного читателя больше */
if (rc == 1) down(&db); /* если это первый читатель... */
up(&mutex); /* завершение исключительного доступа
к ‘rc’ */
read_data_base( ); /* доступ к данным */
down(&mutex); /* получение исключительного доступа к ‘rc’ */
rc = rc − 1; /* теперь на одного читателя меньше */
if (rc == 0) up(&db); /* если это последний читатель... */
up(&mutex); /* завершение исключительного доступа к ‘rc’
*/
use_data_read(); /* некритическая область */
}
}
void writer(void)
{
while (TRUE) { /* бесконечный цикл */
think_up_data( ); /* некритическая область */
down(&db); /* получение исключительного доступа */
write_data_base( ); /* обновление данных */
up(&db); /* завершение исключительного доступа */
}
}
2.6. Исследования, посвященные
процессам и потокам
В главе 1 мы рассмотрели ряд текущих исследований, посвященных структуре опера-
ционных систем. В этой и последующих главах рассмотрим более узконаправленные
исследования, начинающиеся с процессов. Со временем станет понятно, что некоторые
204
Глава 2. Процессы и потоки
предметы исследований лучше разработаны по сравнению с другими. Большинство ис-
следований обычно направлены на изучение новых тем и не относятся к темам, которые
исследуются уже не один десяток лет.
Понятие процесса являет собой пример довольно хорошо разработанной темы. Прак-
тически каждая система обладает неким понятием процесса как контейнера, предназна-
ченного для группировки взаимосвязанных ресурсов, таких как адресное пространство,
потоки, открытые файлы, права доступа к защищенным ресурсам и т. д. Группировка
осуществляется в различных системах немного по-разному, но эти различия носят чисто
технический характер. Основная идея уже практически не вызывает споров, и новых
исследований по теме процессов проводится совсем немного.
По сравнению с процессами потоки являются более новой идеей, но они тоже уже
довольно долго рассматриваются. Тем не менее время от времени все еще появляются
статьи, посвященные потокам, к примеру о кластеризации потоков на мультипроцес-
сорных системах (Tam et al., 2007) или о том, как хорошо современные операционные
системы вроде Linux масштабируются при наличии множества потоков и множества
ядер (Boyd-Wickizer, 2010).
Одна из конкретных областей исследований относится к записи и воспроизведению
выполнения процесса (Viennot et al., 2013). Воспроизведение позволяет разработчикам
выполнять обратное отслеживание трудно обнаруживаемых ошибок, а специалистам
по безопасности — расследовать инциденты.
Аналогичным образом многие современные исследования в сообществе разработчиков
операционных систем сфокусированы на вопросах безопасности. Многочисленные
инциденты показали, что пользователи нуждаются в более надежной защите от злоу-
мышленников (а иногда и от самих себя). Один из подходов заключается в отслежива-
нии и тщательном разграничении в операционной системе информационных потоков
(Giffin et al., 2012).
Планирование (как в однопроцессорной, так и в мультипроцессорной системе) по-
прежнему является темой, близкой и дорогой сердцу некоторых исследователей. Неко-
торые исследованные темы затрагивают энергосберегающее планирование на мобильных
устройствах (Yuan and Nahrstedt, 2006), планирование с учетом гиперпоточности (Bulpin
and Pratt, 2005) и планирование с известным смещением (Koufaty, 2010). С увеличением
количества вычислений на недостаточно мощных, ограниченных по электропитанию
смартфонах некоторые исследователи предлагают при любом удобном случае перено-
сить процесс на более мощный облачный сервер (Gordon et al., 2012). Однако немногие
современные системные разработчики бесцельно слоняются целыми днями, заламывая
руки из-за отсутствия подходящего алгоритма планирования потоков, поэтому данный
тип исследований больше проталкивается самими исследователями, чем вызывается
интенсивностью спроса. В целом процессы, потоки и планирование уже не являются,
как прежде, актуальными темами исследований. Времена активных исследований уже
прошли
1
, и исследователи переключились на такие темы, как управление электропита-
нием, виртуализация, облачные вычисления и безопасность.
1
Однако это совершенно не означает, что данные темы не смогут снова стать актуальными,
например из-за каких-либо значимых изобретений в аппаратном обеспечении, появления
новых структур процессоров или обнаружения каких-либо еще не рассматривавшихся
с должным уровнем детализации частных задач. — Примеч. ред.
Вопросы
205
2.7. Краткие выводы
Чтобы сгладить влияние прерываний, операционные системы предоставляют концеп-
туальную модель, состоящую из параллельно запускаемых последовательных процес-
сов. Процессы могут создаваться и уничтожаться в динамическом режиме. У каждого
процесса есть собственное адресное пространство.
Некоторым приложениям выгодно в рамках одного процесса иметь несколько потоков
управления. Эти потоки имеют независимое планирование, и каждый из них имеет
собственный стек, но все потоки, принадлежащие одному процессу, используют общее
адресное пространство. Потоки могут быть реализованы в пространстве пользователя
или в пространстве ядра.
Процессы могут взаимодействовать друг с другом, используя соответствующие при-
митивы, к которым относятся семафоры, мониторы или сообщения. Эти примитивы
используют, чтобы исключить одновременное пребывание двух процессов в их крити-
ческих областях, то есть для предотвращения ситуации, приводящей к хаосу. Процесс
может находиться в работающем, готовом к работе или заблокированном состоянии
и может изменять состояние, когда он сам или другие процессы задействуют один
из примитивов взаимодействия процессов. Взаимодействие потоков имеет сходный
характер.
Примитивы взаимодействия процессов могут использоваться для решения таких задач,
как «производитель — потребитель», «обедающие философы» и «читатель — писатель».
Но даже при использовании этих примитивов нужно соблюдать особую осторожность
во избежание ошибок и взаимных блокировок.
Было изучено множество алгоритмов планирования. Некоторые из них, например
алгоритм первоочередного выполнения самого короткого задания, используются
преимущественно в пакетных системах. Другие же получили распространение как
в пакетных, так и в интерактивных системах. В числе этих алгоритмов циклическое
и приоритетное планирование, многоуровневые очереди, гарантированное, лотерей-
ное и справедливое планирование. Некоторые системы проводят четкую грань между
механизмом и политикой планирования, что позволяет пользователям управлять
алгоритмом планирования.
Вопросы
1. На рис. 2.2 показаны три состояния процессов. Теоретически при трех состояниях
может быть шесть переходов, по два из каждого состояния. Но показаны только
четыре перехода. Возможны ли такие обстоятельства, при которых осуществимы
один или оба из пропущенных переходов?
2. Предположим, вам нужно разработать новую компьютерную архитектуру, кото-
рая вместо использования прерываний осуществляет аппаратное переключение
процессов. Какие сведения необходимы центральному процессору? Опишите
возможное устройство аппаратного переключения процессов.
3. На всех ныне существующих компьютерах хотя бы часть обработчиков прерыва-
ний написана на ассемблере. Почему?