Существуют два метода синхронизации взаимодействующих процессов: метод взаимных исключений и барьерная синхронизация, способам и средствам реализации которой посвящена работа [7]. В этой статье отчасти показаны методы реализации взаимных исключений, к которым относят блокирующие переменные, мьютексы, семафоры, мониторы. Наиболее общим из них является семафор, т.к. битовый семафор заменяет собой и блокирующую переменную, и мьютекс. Более того, семафоры используются для входа в монитор и обеспечения взаимоисключения внутри монитора. Поэтому в дальнейшем будем все средства синхронизации называть семафором [2, 5]. Семафоры используются для координации использования одиночных или фиксированного множества общих ресурсов (ОР) несколькими процессами. Проблема заключается в том, что взаимодействующие процессы такого рода приводят к столкновению транзакций, поскольку они вступают в конфликт друг с другом, что в свою очередь приводит к потерям производительности операционной системы (ОС) в целом. Наиболее явно это проявляется в параллельных системах, когда взаимодействующие процессы реализуются в независимых процессорах (ЦП), которые могут потребовать одновременно ОР.
Если ОР требуется слишком большому числу ЦП, то они ставятся в очередь к семафору. По мере освобождения ОР запросы удовлетворяются традиционно по принципу: первым пришел – первым обслужен (FIFO). Там, где разрешена параллельная обработка и имеется единица ОР, некоторый процесс может держать его продолжительное время. В это время другие процессы будут ожидать окончания этого процесса, причем быстро исполняющиеся процессы скоро «застрянут» в более медленных [7].
Аналитическая модель n-процессорной системы с одиночным ОР для оценки потерь производительности из-за конфликтов за доступ к семафору, при использовании концепции планирования типа FIFO, изображена на рис. 1а [3, 6]. Математическая модель представлена в виде разомкнутой стохастической сети массового обслуживания (РСеМО), состоящей из n (S1,…,Sn) одноканальных систем массового обслуживания (СМО), моделирующих ЦП, и одноканальной СМО (Sn+1), которая моделирует семафор. Причем СМО S0 выступает в качестве внешнего источника запросов (заявок на выполнение процессов), которые могут формироваться, например, терминалами пользователей, а также в качестве поглотителя обслуженных заявок [4].
Пусть на вход n-процессорной системы поступает поток запросов на выполнение процессов с интенсивностью λ0 = 1/T, где T – средняя длительность интервала между поступающими на вход запросами. Поток запросов распределяется предварительным планировщиком по ЦП с вероятностями р01,…,роn (см. граф вероятностей передач стохастической сети, изображенной на рис. б). Каждый ЦП содержит собственный планировщик, формирующий очередь запросов Оi. Будем считать, что время выполнения запроса vi в каждом ЦП распределено по экспоненциальному закону.
Схема аналитической модели n-процессорной системы (а) и её граф передач (б)
Предположим для упрощения, что потоки запросов на выполнение процессов на входе многопроцессорной системы распределяются равновероятно по ЦП, т.е. р01=…= роn = 1/n (см. рис. б). Причем i-й ЦП (СМО S1,…,Sn), обслужив очередную заявку, передает её на обслуживание в семафор (СМО Sn+1) с вероятностями p1, n+1 =,…,= pn,n+1 (т.е. каждый ЦП формирует потоки запросов семафора с одинаковой интенсивностью). Заявки, получившие обслуживание в семафоре, с равной вероятностью возвращаются на продолжение обслуживания в ЦП, следовательно, pn+1,1 =…= pn+1,n = 1/n. Предположим также, что вероятность получения заявкой полного обслуживания в i-м ЦП (вероятность выхода заявки из сети) составляет pi0, а вероятность, что заявка останется на обслуживании в СМО Si, составляет pij, где i,j = 1,…,n.
Пусть среднее время обслуживания i-го процесса в семафоре сравнимо со временем обслуживания его в ЦП, и конкретные значения ti могут отличаться в среднем не более чем в 2–3 раза. Для конкретности примем, что среднее время обслуживания в ЦП составляет vi = 1 единицу (i = 1,…,n) времени, а среднее значение в семафоре
единиц времени.
Будем считать, что в среднем на одну реализацию некоторого процесса приходится 1000 циклов обращения к семафору. Тогда вероятность того, что заявка покинет вычислительную систему (процесс полностью выполнился) составит pi0 = 0,001. Вероятность же того, что заявка останется на обслуживании в вычислительной системе составит (1 – pi0) = 0,999.
Время ожидания заявки в сети
Tw = α1tw1 + α2tw2 + ... + αntwn + αn+1 twn+1,
где αi = λi / λ0 – коэффициент передачи сети (i = 1, ..., n + 1); twi – время ожидания в i-й СМО [1]. Интенсивности потоков заявок определятся системой уравнений:
,
где pji – вероятность передачи из СМО Sj в СМО Si; i, j = 0, 1, ..., n + 1.
В статье показано, что планирование на основе приоритетов дает выигрыш по времени ожидания в очереди к семафору почти в 2 раза, чем при использовании стратегии на основе FIFO. Полученные модели позволяют произвести количественные оценки времени ожидания процессов, обращающихся к общему ресурсу через посредство семафора. Модели могут быть использованы при проектировании параллельных ОС, где критичным является время выполнения процессов.
Работа выполнена при финансовой поддержке РФФИ (Проект № 16–07–00012 А).