Взаимные блокировки потоков и их обнаружение
жүктеу/скачать 26,38 Kb.
|
ПР №2 Взаимные блокировки потоков и их обнаружение
- Бұл бет үшін навигация:
- Общие сведения
|
Практическая работа №2 Тема: Взаимные блокировки потоков и их обнаружение Цель работы: получить практические навыки обнаружения взаимоблокировок потоков. Общие сведения Потоки возникли в операционных системах как средство распараллеливания вычислений, хотя эта задача в рамках одного приложения может быть решена и традиционными способами. Каждый процесс всегда состоит, по крайней мере, из одного потока выполнения, и только если имеется внутренний параллелизм, программист может «расщепить» один поток на несколько параллельных. Потребность в потоках возникла еще в однопроцессорных вычислительных системах, поскольку они позволяли организовать вычисления более эффективно. Для использования достоинств многопроцессорных систем с общей памятью потоки уже просто необходимы, так как позволяют не только реально ускорить выполнение тех задач, которые допускают их естественное распараллеливание, но и загрузить процессорные элементы работой, с тем, чтобы они не простаивали. Желательно свести к минимуму взаимодействие потоков между собой, ибо ускорение от одновременного выполнения параллельных потоков может быть сведено к минимуму из-за задержек синхронизации и обмена данными. Каждый поток выполняется строго последовательно и имеет свой собственный программный счетчик и стек. Потоки, как и процессы, могут порождать потоки-потомки, поскольку любой процесс состоит, по крайней мере, из одного потока. Подобно традиционным процессам (однопоточным), каждый поток может находиться в одном из активных состояний. Пока один поток заблокирован (или просто находится в очереди готовых к исполнению задач), другой поток того же процесса может выполняться. Например, потоки разделяют процессорное время так же, как это делают обычные процессы, в соответствии с различными вариантами диспетчеризации. Использование потоков связано не только со стремлением повысить производительность системы за счет параллельных вычислений, но и с целью создания более читабельных, логичных программ. Введение нескольких потоков выполнения упрощает программирование. Тем не менее, проблемой многопоточных программ является возможность взаимной блокировки потоков. Взаимная блокировка может произойти в том случае, если каждый из двух потоков ждет освобождения ресурса, заблокированного другим потоком. Рассмотрим возможность обнаружения взаимоблокировок при наличии нескольких разделяемых ресурсов каждого типа. Пусть имеется множество процессов Р={Р1, Р2, …, Рn} и множество ресурсов Е={Е1, Е2, …, Еm}, где n и m - количество процессов и ресурсов соответственно. В любой момент времени некоторые ресурсы могут быть заняты и, соответственно, недоступны. Пусть вектор А=(А1, А2, …, Аm) – вектор доступных ресурсов. Причем выполняется соотношение Аj<=Еj, где j=1, 2, …, m. Кроме того, рассматриваются две матрицы: 1) С={сij}, i=1, 2, …n; j=1, 2, ..., m – матрица текущего распределения ресурсов, где сij – количество ресурсов j-того класса, которые занимает процесс Pi; 2) R={rij}, i=1,2,...n; j=1,2,...,m – матрица требуемых (запрашиваемых) ресурсов, где rij – количество ресурсов j–того класса, которые хочет получить процесс Pi. Справедливо m соотношений по ресурсам: , где j=1,2,...,m. (5.1) Алгоритм обнаружения взаимоблокировок основан на сравнении векторов доступных и требуемых ресурсов. В исходном состоянии все процессы не отмечены. По мере реализации алгоритма на процессы будет ставиться отметка, что они могут закончить свою работу, следовательно, не находятся в тупике. После завершения алгоритма любой немаркированный процесс находится в тупиковой ситуации. Алгоритм обнаружения тупиков состоит из следующих шагов: 1) ищется процесс Pi, для которого i-строка матрицы R меньше вектора A, то есть Ri<=A, или rij 3) если таких процессов не существует, работа алгоритма заканчивается, а неотмеченные процессы попадают в тупик. Изложенный алгоритм можно использовать для решения задач обнаружения тупиковых ситуаций и заблокированных процессов в системе с множественными ресурсами. жүктеу/скачать 26,38 Kb. Достарыңызбен бөлісу:
|