Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Лекция 5
Содержание
- 1. Лекция 5
- 2. Цели и средства синхронизацииПотребность в синхронизации потоков
- 3. Моменты прерывания потоков, время нахождения их в
- 4. Необходимость синхронизации и гонкиПренебрежение вопросами синхронизации в
- 5. Программа, ведущая базу данных, оформлена как единый
- 6. 1. Считать из файла базы данных в
- 7. Слайд 7
- 8. Предположим, что в некоторый момент поток А
- 9. Предположим также, что потоку В также потребовалось
- 10. Когда в очередной раз управление будет передано
- 11. Таким образом, в базе данных будут зафиксированы
- 12. Слайд 12
- 13. Ситуации, подобные той, когда два или более
- 14. Критическая секция — это часть программы, результат
- 15. В предыдущем примере такими критическими данными являлись
- 16. Операционная система использует разные способы реализации взаимного
- 17. Для синхронизации потоков одного процесса могут использоваться
- 18. Перед входом в критическую секцию поток проверяет,
- 19. Слайд 19
- 20. Недостаток: в течение времени, когда один поток
- 21. Для устранения этого недостатка во многих ОС
- 22. Поток после выхода из критической секции должен
- 23. Слайд 23
- 24. Таким образом исключается непроизводительная потеря процессорного времени
- 25. Семафоры Обобщением блокирующих переменных являются так называемые
- 26. Для работы с семафорами вводятся два примитива,
- 27. P(S): уменьшение S на 1, если это
- 28. В частном случае, когда семафор S может
- 29. Рассмотрим использование семафоров на примере взаимодействия двух
- 30. Для правильной совместной работы поток-писатель должен приостанавливаться,
- 31. Слайд 31
- 32. Поток-писатель прежде всего выполняет операцию Р(е), с
- 33. Поток-читатель действует аналогичным образом, с той разницей,
- 34. Использование двоичной переменной не позволяет организовать доступ
- 35. Семафор может использоваться и в качестве блокирующей
- 36. Слайд 36
- 37. ТупикиПриведенный выше пример позволяет также проиллюстрировать еще
- 38. Пусть поток-писатель начинает свою работу с проверки
- 39. Но поток-читатель не сможет этого сделать, так
- 40. Слайд 40
- 41. Предположим, что после того, как ОС назначила
- 42. Управление снова получил поток А, который в
- 43. В зависимости от соотношения скоростей потоков они
- 44. Слайд 44
- 45. Слайд 45
- 46. Слайд 46
- 47. В рассмотренных примерах тупик был образован двумя
- 48. Слайд 48
- 49. Невозможность потоков завершить начатую работу из-за возникновения
- 50. И наконец, если тупик диагностирован, то нужны
- 51. Другой, более гибкий подход к предотвращению тупиков
- 52. Скачать презентанцию
Цели и средства синхронизацииПотребность в синхронизации потоков возникает только в мультипрограммной операционной системе и связана с совместным использованием аппаратных и информационных ресурсов вычислительной системы. Синхронизация необходима при обмене данными между потоками,
Слайды и текст этой презентации
Слайд 3Моменты прерывания потоков, время нахождения их в очередях к разделяемым
ресурсам, порядок выбора потоков для выполнения — все эти события
являются случайными. Любое взаимодействие процессов или потоков связано с их синхронизацией, которая заключается в согласовании их скоростей путем приостановки потока до наступления некоторого события и последующей его активизации при наступлении этого события.
Слайд 4Необходимость синхронизации и гонки
Пренебрежение вопросами синхронизации в многопоточной системе может
привести к неправильному решению задачи или даже к краху системы.
Рассмотрим
задачу ведения базы данных клиентов некоторого предприятия. Каждому клиенту отводится отдельная запись в базе данных, в которой среди прочих полей имеются поля “Заказ” и “Оплата”. 
Слайд 5Программа, ведущая базу данных, оформлена как единый процесс, имеющий несколько
потоков, в том числе поток А, который заносит в базу
данных информацию о заказах, поступивших от клиентов, и поток В, который фиксирует в базе данных сведения об оплате клиентами выставленных счетов.Оба эти потока совместно работают над общим файлом базы данных, используя однотипные алгоритмы, включающие три шага.
Слайд 61. Считать из файла базы данных в буфер запись о
клиенте с заданным идентификатором.
2. Внести новое значение в поле Заказ
(для потока А) или Оплата (для потока В).3. Вернуть модифицированную запись в файл базы данных.
Обозначим соответствующие шаги для потока А как A1, A2 и A3, а для потока В как B1, B2 и ВЗ.
Слайд 8Предположим, что в некоторый момент поток А обновляет поле Заказ
записи о клиенте N. Для этого он считывает эту запись
в свой буфер (шаг А1), модифицирует значение поля Заказ (шаг А2), но внести запись в базу данных (шаг A3) не успевает, так как его выполнение прерывается, например, вследствие завершения кванта времени.
Слайд 9Предположим также, что потоку В также потребовалось внести сведения об
оплате относительно того же клиента N. Когда подходит очередь потока
В, он успевает считать запись в свой буфер (шаг В1) и выполнить обновление поля Оплата (шаг В2), а затем прерывается. Заметим, что в буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение.
Слайд 10Когда в очередной раз управление будет передано потоку А, то
он, продолжая свою работу, запишет запись о клиенте N с
модифицированным полем Заказ в базу данных (шаг A3). После прерывания потока А и активизации потока В последний запишет в базу данных поверх только что обновленной записи о клиенте N свой вариант записи, в которой обновлено значение поля Оплата.
Слайд 11Таким образом, в базе данных будут зафиксированы сведения о том,
что клиент N произвел оплату, но информация о его заказе
окажется потерянной.
Слайд 13Ситуации, подобные той, когда два или более потоков обрабатывают разделяемые
данные и конечный результат зависит от соотношения скоростей потоков, называются
гонками.
Слайд 14Критическая секция — это часть программы, результат выполнения которой может
непредсказуемо меняться, если переменные, относящиеся к этой части программы, изменяются
другими потоками в то время, когда выполнение этой части еще не завершено. Критическая секция всегда определяется по отношению к определенным критическим данным, при несогласованном изменении которых могут возникнуть нежелательные эффекты.
Слайд 15В предыдущем примере такими критическими данными являлись записи файла базы
данных. Во всех потоках, работающих с критическими данными, должна быть
определена критическая секция.Чтобы исключить эффект гонок по отношению к критическим данным, необходимо обеспечить, чтобы в каждый момент времени в критической секции, связанной с этими данными, находился только один поток. Этот прием называют взаимным исключением.
Слайд 16Операционная система использует разные способы реализации взаимного исключения.
Самый простой и
неэффективный способ : операционная система позволяет потоку запрещать любые прерывания
на время его нахождения в критической секции. Однако этот способ практически не применяется, так как опасно доверять управление системой пользовательскому потоку — он может надолго занять процессор, а при крахе потока в критической секции крах потерпит вся система, потому что прерывания никогда не будут разрешены.
Слайд 17Для синхронизации потоков одного процесса могут использоваться глобальные блокирующие переменные.
Каждому набору критических данных ставится в соответствие двоичная переменная, которой
поток присваивает значение 0, когда он входит в критическую секцию, и значение 1, когда он ее покидает. Рассмотрим фрагмент алгоритма потока, использующего для реализации взаимного исключения доступа к критическим данным D блокирующую переменную F(D).
Слайд 18Перед входом в критическую секцию поток проверяет, не работает ли
уже какой-нибудь поток с данными D. Если переменная F(D) установлена
в 0, то данные заняты и проверка циклически повторяется. Если же данные свободны (F(D) = 1), то значение переменной F(D) устанавливается в 0 и поток входит в критическую секцию. После того как поток выполнит все действия с данными D, значение переменной F(D) снова устанавливается равным 1.
Слайд 20Недостаток: в течение времени, когда один поток находится в критической
секции, другой поток, которому требуется тот же ресурс, получив доступ
к процессору, будет непрерывно опрашивать блокирующую переменную, бесполезно тратя выделяемое ему процессорное время.
Слайд 21Для устранения этого недостатка во многих ОС предусматриваются специальные системные
вызовы для работы с критическими секциями. Перед тем как начать
изменение критических данных, поток выполняет системный вызов EnterCriticalSection(). Если системный вызов определил, что ресурс занят (F(D) = 0), он в отличие от предыдущего случая не выполняет циклический опрос, а переводит поток в состояние ожидания (D) и делает отметку о том, что данный поток должен быть активизирован, когда соответствующий ресурс освободится.
Слайд 22Поток после выхода из критической секции должен выполнить системную функцию
LeaveCriticaiSection(), в результате чего блокирующая переменная принимает значение, соответствующее свободному
состоянию ресурса (F(D) = 1), а операционная система просматривает очередь ожидающих этот ресурс потоков и переводит первый поток из очереди в состояние готовности.
Слайд 24Таким образом исключается непроизводительная потеря процессорного времени на циклическую проверку
освобождения занятого ресурса.
Однако в тех случаях, когда объем работы
в критической секции небольшой и существует высокая вероятность в очень скором доступе к разделяемому ресурсу, более предпочтительным может оказаться использование блокирующих переменных.
Слайд 25Семафоры
Обобщением блокирующих переменных являются так называемые семафоры Дийкстры. Вместо
двоичных переменных Дийкстра предложил использовать переменные, которые могут принимать целые
неотрицательные значения- семафоры.
Слайд 26Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р
и V. Пусть переменная S представляет собой семафор. Тогда действия
V(S) и P(S) определяются следующим образом:V(S): переменная S увеличивается на 1 единым действием. К переменной S нет доступа другим потокам во время выполнения этой операции.
Слайд 27P(S): уменьшение S на 1, если это возможно. Если S=0
и невозможно уменьшить S, оставаясь в области целых неотрицательных значений,
то в этом случае поток, вызывающий операцию Р, ждет, пока это уменьшение станет возможным.Никакие прерывания во время выполнения примитивов V и Р недопустимы.
Слайд 28В частном случае, когда семафор S может принимать только значения
0 и 1, он превращается в блокирующую переменную, которую по
этой причине часто называют двоичным семафором.
Слайд 29Рассмотрим использование семафоров на примере взаимодействия двух выполняющихся в режиме
мультипрограммирования потоков, один из которых пишет данные в буферный пул,
а другой считывает их из буферного пула.Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. В общем случае поток-писатель и поток-читатель могут иметь различные скорости и обращаться к буферному пулу с переменой интенсивностью.
Слайд 30Для правильной совместной работы поток-писатель должен приостанавливаться, когда все буферы
оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера.
Напротив, поток-читатель должен приостанавливаться, когда все буферы пусты, и активизироваться при появлении хотя бы одной записи.
Введем два семафора: е — число пустых буферов, и f — число заполненных буферов, причем в исходном состоянии е = N, a f = 0.
Слайд 32Поток-писатель прежде всего выполняет операцию Р(е), с помощью которой он
проверяет, имеются ли в буферном пуле незаполненные буферы. Eсли семафор
е=0 (то есть свободных буферов в данный момент нет), то поток-писатель переходит в состояние ожидания. Если е>0, то он уменьшает число свободных буферов, записывает данные в очередной свободный буфер и после этого наращивает число занятых буферов операцией V(f), т.е. устанавливая f+1.
Слайд 33Поток-читатель действует аналогичным образом, с той разницей, что он начинает
работу с проверки наличия заполненных буферов, а после чтения данных
наращивает количество свободных буферов.В данном случае предпочтительнее использовать семафоры вместо блокирующих переменных. Действительно, критическим ресурсом здесь является буферный пул, представленный как набор идентичных ресурсов — отдельных буферов, а значит, с буферным пулом могут работать сразу несколько потоков, и именно столько, сколько буферов в нем содержится.
Слайд 34Использование двоичной переменной не позволяет организовать доступ к критическому ресурсу
более чем одному потоку. Семафор же решает задачу синхронизации более
гибко, допуская к разделяемому пулу ресурсов заданное количество потоков. Так, в нашем примере с буферным пулом могут работать максимум N потоков, часть из которых может быть «писателями», а часть — «читателями».
Слайд 35Семафор может использоваться и в качестве блокирующей переменной. В рассмотренном
выше примере, для того чтобы исключить коллизии при работе с
разделяемой областью памяти, будем считать, что запись в буфер и считывание из буфера являются критическими секциями. Взаимное исключение будем обеспечивать с помощью двоичного семафора b .
Слайд 37Тупики
Приведенный выше пример позволяет также проиллюстрировать еще одну проблему синхронизации
— взаимные блокировки, называемые также тупиками. Покажем, что если переставить
местами операции Р(е) и Р(b) в потоке-писателе, то при некотором стечении обстоятельств эти два потока могут взаимно блокировать друг друга.
Слайд 38Пусть поток-писатель начинает свою работу с проверки доступности критической секции
— операции Р(b) и пусть он первым войдет в критическую
секцию. Выполняя операцию Р(е), он может обнаружить отсутствие свободных буферов и перейти в состояние ожидания. Из этого состояния его может вывести только поток-читатель, который возьмет очередную запись из буфера.
Слайд 39Но поток-читатель не сможет этого сделать, так как для этого
ему потребуется войти в критическую секцию, вход в которую заблокирован
потоком-писателем. Таким образом, ни один из этих потоков не может завершить начатую работу и возникнет тупиковая ситуация, которая не может разрешиться без внешнего воздействия.
Слайд 41Предположим, что после того, как ОС назначила порт потоку А
и установила связанную с этим ресурсом блокирующую переменную, поток А
был прерван. Управление получил поток В, который сначала выполнил запрос на получение принтера, затем при выполнении следующей команды был заблокирован, так как порт оказался уже занятым потоком А.
Слайд 42Управление снова получил поток А, который в соответствии со своей
программой сделал попытку занять принтер и был заблокирован, поскольку тот
уже выделен потоку В. В таком положении потоки А и В могут находиться сколь угодно долго.
Слайд 43В зависимости от соотношения скоростей потоков они могут либо взаимно
блокировать друг друга (рис. 4.22, б), либо образовывать очереди к
разделяемым ресурсам (рис. 4.22, в), либо совершенно независимо использовать разделяемые ресурсы (рис. 4.22, г).
Слайд 47В рассмотренных примерах тупик был образован двумя потоками, но взаимно
блокировать друг друга может и большее число потоков. На рис.
показано такое распределение ресурсов Ri между несколькими потоками Tj, которое привело к возникновению взаимных блокировок.
Слайд 49Невозможность потоков завершить начатую работу из-за возникновения взаимных блокировок снижает
производительность вычислительной системы. Поэтому проблеме предотвращения тупиков уделяется большое внимание.
На тот случай, когда взаимная блокировка все же возникает, система должна предоставить администратору-оператору средства, с помощью которых он смог бы распознать тупик, отличить его от обычной блокировки из-за временной недоступности ресурсов.
Слайд 50И наконец, если тупик диагностирован, то нужны средства для снятия
взаимных блокировок и восстановления нормального вычислительного процесса.
Тупики могут быть предотвращены
на стадии написания программ, то есть программы должны быть написаны таким образом, чтобы тупик не мог возникнуть при любом соотношении взаимных скоростей потоков. 
Слайд 51Другой, более гибкий подход к предотвращению тупиков заключается в том,
что ОС каждый раз при запуске задач анализирует их потребности
в ресурсах и определяет, может ли в данной мультипрограммной смеси возникнуть тупик. Если да, то запуск новой задачи временно откладывается. ОС может также использовать определенные правила при назначении ресурсов потокам, например, ресурсы могут выделяться операционной системой в определенной последовательности, общей для всех потоков.
