Главная страница
Навигация по странице:

  • Цель работы

  • Задания к практической работе

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

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

  • ПР №2 Взаимные блокировки потоков и их обнаружение. Взаимные блокировки потоков и их обнаружение


    Скачать 26.58 Kb.
    НазваниеВзаимные блокировки потоков и их обнаружение
    Дата14.05.2023
    Размер26.58 Kb.
    Формат файлаdocx
    Имя файлаПР №2 Взаимные блокировки потоков и их обнаружение.docx
    ТипПрактическая работа
    #1128044

    Практическая работа №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
    2) если такой процесс найден, это значит, что он может завершиться и освободить занятые ресурсы. Найденный процесс отмечается, i–я строка матрицы C прибавляется к вектору A, то есть Aj=Aj+cij, где j=1, 2, ... m, и осуществляется возвращение к шагу 1;

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

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

    Задания к практической работе

    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) построить граф ресурсов и процессов, позволяющий установить процессы, которые попали в тупиковую ситуацию.

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







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

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

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

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

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

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

    а) Т < 10;

    б) 10
    в) 20
    г) T>30.

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

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

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

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

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

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

    - выводы по каждому заданию.
    Контрольные вопросы

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

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

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

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

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

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

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

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

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

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


    написать администратору сайта