Лабораторная работа. Взаимные блокировки потоков и их обнаружение

 

Цель работы: получить практические навыки обнаружения взаимоблокировок потоков.

 

Общие сведения

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

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

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

Пусть имеется множество процессов Р={Р₁, Р₂, …, Р_n} и множество ресурсов Е={Е₁, Е₂, …, Е_m}, где n и m - количество процессов и ресурсов соответственно. В любой момент времени некоторые ресурсы могут быть заняты и, соответственно, недоступны.

Пусть вектор А=(А₁, А₂, …, А_m) – вектор доступных ресурсов. Причем выполняется соотношение А _j <=Е _j, где j=1, 2, …, m.

Кроме того, рассматриваются две матрицы:

1) С={с _ij }, i =1, 2, …n; j =1,2,...,m – матрица текущего распределения ресурсов, где с_ij – количество ресурсов j-того класса, которые занимает процесс P_i;

2) R={r _ij }, i =1,2,...n; j =1,2,...,m – матрица требуемых (запрашиваемых) ресурсов, где r_ij – количество ресурсов j–того класса, которые хочет получить процесс P_i.

Справедливо m соотношений по ресурсам:

, где j =1,2,...,m. (5.1)

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

Алгоритм обнаружения тупиков состоит из следующих шагов:

1) ищется процесс P_i, для которого i -строка матрицы R меньше вектора A, то есть R_i<=A, или r_ij<A_j, где j =1, 2,..., m;

2) если такой процесс найден, это значит, что он может завершиться и освободить занятые ресурсы. Найденный процесс отмечается, i –я строка матрицы C прибавляется к вектору A, то есть A _j =A _j +c _ij, где j =1,2,...m, и осуществляется возвращение к шагу 1;

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

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

 

Задания к лабораторной работе

5.2.1 Обнаружение взаимоблокировок при наличии неразделяемых ресурсов. Рассматривается простой вариант для случая, когда в системе существует только один ресурс каждого типа.

Пусть система состоит из семи процессов – A, B, C, D, E, F, G и шести ресурсов - R, S, T, V, W, U. В некоторый момент времени система соответствует следующему списку:

а) процесс А занимает ресурс R и хочет получить ресурс S;

б) процесс В ничего не использует, но хочет получить ресурс Т;

в) процесс С ничего не использует, но хочет получить ресурс S;

г) процесс D занимает ресурс U и хочет получить ресурсы S и T;

д) процесс Е занимает ресурс Т и хочет получить ресурс V;

е) процесс F занимает ресурс W и хочет получить ресурс S;

ж) процесс G занимает ресурс V и хочет получить ресурс U.

Требуется:

1) определить заблокирована ли эта система и если да, то какие процессы в этом участвуют;

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

3) распределить ресурсы по процессам в соответствии с приведенным списком;

4) построить граф ресурсов и процессов, позволяющий установить процессы, которые попали в тупиковую ситуацию.

 

5.2.2 В системе есть 5 процессов (A, B, C, D, E) и 4 ресурса (p1, p2, p3, p4), которые можно предоставить процессам. Текущее распределение ресурсов и максимальное их количество, необходимое процессам, приводится в таблице 5.1. Заполнить столбцы «требуется» и «доступно». Определить оптимальный вариант распределения существующих ресурсов. Возможно ли возникновение в системе тупиковой ситуации?

 

Таблица 5.1 – Распределение ресурсов и их количество

процесс	Предоставлено р1, р2, р3, р4	Максимальные требования	Требуется р1, р2, р3, р4	Доступно р1, р2, р3, р4
А	0 0 1 3	1 0 1 5		1 1 0 2
В	1 3 0 0	2 6 5 0
С	0 0 3 1	2 6 5 6
D	2 3 4 1	4 3 5 6
Е	0 3 3 1	0 5 5 1

 

5.2.3 Требуется сравнить считывание файла через однопоточный и многопоточный файловые серверы. Получение запроса, его диспетчеризация и обработка занимают 15 миллисекунд при условии наличия данных в блочном кэше. В каждом третьем случае требуется обращение к диску, занимающее 75 миллисекунд, в течение которых поток находится в состоянии ожидания. Сколько запросов в секунду обработает однопоточный сервер? А многопоточный?

 

5.2.4 Запуска ожидают пять задач. Предполагаемое время их выполнения составляет 9, 6, 3, 5 и х мс. В каком порядке их следует запустить, что минимизировать среднее время отклика? (Ответ должен зависеть от х).

 

5.2.5 В гибкую систему реального времени поступают четыре периодических сигнала в периодами 50, 100, 200 и 250 мс. На обработку каждого сигнала требуется 35, 20, 10 и х мс времени центрального процессора. Требуется определить максимальное значение х, при котором система остается поддающейся планированию.

 

5.2.6 Пользовательский процесс формирует строку из 70 символов для вывода на принтер, затрачивая на это 5 мс. Объем буфера равен одной строке. Страница текста содержит 50 строк. Принтер способен печатать 10 страниц в минуту. Будет ли приостанавливаться пользовательский процесс? Если да, то насколько? Улучшит ли ситуацию двойная буферизация?

 

5.2.7 Информация от модема поступает со скоростью 50 Кбит/с, размещаясь в двух переключаемых системных буферах, каждый из которых имеет емкость в 1 Кбайт. Перемещение данных из буфера в пользовательский процесс занимает 7 мс. Пользовательский процесс затрачивает 50 мс на обработку одного блока данных. Возможны ли при этих условиях потери данных, поступающих от модема?

 

5.2.8 Известно, что программа А выполняется в монопольном режиме за 10 минут, а программа В – за 20 минут, то есть при последовательном выполнении они требуют 30 мин. Если Т – время выполнения обеих этих задач в режиме мультипрограммирования, то какое из неравенств справедливо? Поясните ответ схемой.

а) Т < 10;

б) 10< T <20;

в) 20< T <30;

г) T >30.

 

Требования к отчету

Отчет по работе выполняется на бумажном носителе и должен содержать:

- задание к работе;

- описание тех или иных действий, выполненных для получения результата;

- листинги программ с комментариями;

- снимки экрана с результатами работы;

- выводы по каждому заданию.

 

5.4 Контрольные вопросы

5.4.1 Что такое «поток»?

5.4.2 В чем разница между потоком и процессом?

5.4.3 В каких случаях возникает взаимоблокировка?

5.4.4 На чем основан алгоритм обнаружения взаимоблокировок?

5.4.5 Какие виды планировщиков Вам известны?

5.4.6 Какие состояния возможны для активных процессов?

5.4.7 Приведите пример пассивных процессов?

5.4.8 Что понимается под мультипрограммированием?

5.4.9 Что понимается под планированием вычислительных процессов?

5.4.10 Что определяет стратегия планирования?