Сделай Сам Свою Работу на 5

Синхронизации процессов и потоков

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

Во многих ОС эти средства называются Inter Process Communication (IPC). Вып потока в мульти прог среде всегда имеет асинхронный характер.

Очень сложно с полной определённостью сказать на каком этапе выполнения будет находиться процесс в определённый момент времени. Так как исходные данные в разные моменты запуска задачи могут быть разными. То и время вып отдельных этапов и задачи в целом является весьма неопределённой величиной. Ещё более не определённым является время выполнения программы в мульти программной системе.

Моменты прерывания потоков, время нахождения их в очереди(к разным ресурсам), порядок выбора потоков для выполнения – все эти события являются результатом стечения многих обстоятельств и могут быть интерпретированы как случайные.

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

Таким образом потоки в общем случае протекают независимо или асинхронно друг от друга это утверждение справедливо как по утверждению к потоком одного процесса(вып одну общ задачу) так и по отнош потоков разных процессов каждый из которых выполняет собственную задачу.

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

Синхронизация лежит в основе любого взаимодействия потоков, не важно, связанно ли это с взаимодействием ресурсов или обменом данными.

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



Пример: задача состоит в ведении базы данных клиентов некоторого предприятия. Каждому клиенту отводиться своя строка в базе данных в которой имеются поля заказ и оплата, программа ведущая базу данных оформлена как единый процесс имеющий несколько потоков в том числе поток: а) заносит инф о заказах поступивших от клиентов и поток б) фиксирует в базе данных сведения об оплате выставленных счетов. Оба потока совместно работают над файлом базы данных используя при этом однотипный алгоритм:

Этапы алгоритма

1) Считать из файла базу данных в буфер, запись о клиенте с заданным идентификатором.

2) Для потока а) внести новое значение в поле заказ, а для потока б) внести новое значение в поле оплаты.

3) Вернуть модифицированную запись в файл оплаты.

Обозначим соответствующие шаги для потока а1, а2, … б1, б2 … предположим что в некоторый момент поток а) обновляет поле заказ записи о клиенте «Н» для этого он считывает запись в свой буфер шаг а1, модифицирует значение в поле заказ шаг а2 но внести изменение в базу данных шаг а3 не успевает. Так как его выполнение прерывается в следствии завершения кванта времени.

Так же предположим что потоку б) требовалось внести данные о клиенте «Н» когда приходит очередь потока б) он успевает считать запись в свой буфер шаг б1, выполнить обновление поля оплата шаг б2, и прерывается при этом заметим что в буфере у потока б) находиться запись о клиенте «Н» в котором поле заказ имеет все ещё имеет низменное значение. Когда в очередной раз управление будет передано значение в поток а) он запишет в запись о клиенте «Н» модифицированное значение. После заверш а) и активизации б) в базу данных поверх обновленной записи о клиенте «Н» будет записана обновленное значение в поле оплата но старое значение в поле заказ шаг б3 выполниться но снова измениться поле заказ.

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

Проблемы при синхронизации:

1) Гонки

2) Критическая секция – часть программы результат выполнения которой может не предсказуемо меняться если переменные относящиеся к этой части программы изменяются другими потоками в то время когда выполнение этой части программы ещё не завершено. Она всегда определяется по отношению к определённым критическим данным при не согласованном изменении которых могут возникать проблемные ситуации. В предыдущем примере такие данные являлись записи файла базы данных, во всех потоках работающие с базами данных должна быть определена критическая секция. При этом в разных потоках критическая секция состоит из разных наборов последовательности команд, что бы исключить эффект гонок по отношению к критическим данным необходимо обеспечить что бы в каждый момент времени в критической секции связанной с этими данными находился лишь один поток при этом не важно находиться ли этот поток в активном или приостановленном состоянии этот приём называет взаимоисключением. ОС использует различные способы реализации взаимоисключения для потоков одного процесса и при взаимодействии нескольких потоков.

3) Блокирующие переменные для синхронизации потоков одного процесса возможно использование глобальных блокирующих переменных. С этими переменными которым все потоки процесса имеют прямой доступ, необходимо работать не обращаясь к системным вызовам ОС. Каждому набору критических данных ставится в соответствии двоичная переменная которой поток присваивает значение ноль когда он входит в критическую секцию и значение 1 когда он ее покидает.

a. Необходимо определить занята ли переменная или нет if(!free){ d = 0; вып крит ситуации; d = 1} else {return first} – единая не делимая операция т.е. взаимодействуют как единое целое.

b. Данный фрагмент алгоритма показывает поток использующий для реализации взаимного исключения доступ к критическим данным “D” в блокирующею переменную f(d). Пред входом в критическую секцию поток проверяет не работает ли уже какой ни будь поток с данными D если переменная f(d) == NULL , то данные заняты и цикл повторяется если же f(d) == 1, f(d) = 0 и поток входит в критическую секцию. После того как поток выполнит свою секцию значения f(d) = 1. Блокир переменные могут использоваться не только при доступе к разделённым данным, но и при доступе к разделённым ресурсам любого вида.

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

d. Для избежания данных ситуаций системы команд многих ПК предусмотрена единая не делимая команда анализа и присвоения значения логической переменной.

4) Семафоры – обощением блокирующих переменных являются так называние семафоры дийкстры (Dijkstro) – предложил использовать переменные которые могут принимать целые не отрицательные значения, такие переменные получили название семафоров. Для работы с семафорами вводятся два примитива «P» «V» пусть переменная «S» представляет собой семафор тогда действие P(s) and V(s) определяется следующим действием V(s) – увеличение переменной S на единицу единым действием при этом выборка наращивания и запоминания не могут быть прерваны. К переменной S не доступа другим потокам во время выполнения этой операции. P(s) – уменьшение S на единицу если это возможно if(5*0) то уменьшить S области целых не отриц чисел невозможно, то поток P ожидает пока это станет возможным успешная проверка и уменьшение так же является не делимой. Прерывание во время примитивов P and S невозможно. В случае если семафор принимает 0 или 1 то он становиться простой блокирующей переменной которой часто называют двоичным семафором. Операция P заключает в себя потенциальную возможность перехода потока который ее выполняет состояние ожидания в то время как операция V может активизировать другой поток приостановленный операцией P.

Рассмотрим семафоры на примере взаимодействия двух вып потоков один из которых пишет данных в группы другой считывает их из буфера. При этом буфер состоит из N частей так называемый буферный пул, в общем случае поток read и записи могут иметь разные скорости и обращаться к беферному пулу с перемннной интенсивностью. В различные периоды скорость записи может перевышать скорость чтения и наоборот.

Для правильной работы поток записи должен приостанавливаться когда все буферы в пуле и активизироваться при освобождении хотя бы одного буфера. Поток читатель наоборот должен приостанавливаться когда все буферы пусты и активизироваться при пойвлении хотя бы одной записи.

Введём два семафорам

Е – число пустых буферов

Ф – число заполненные

В начале Е = N

Ф = 0;

Тогда работа потоков с общим буферным пулом может быть описана:

Поток писатель должен прежде всего вып операцию P(E)(--) через которую он проверяет имеется ли в пуле незаполненные буферы. Если семафор Е = 0, свободных буферов в данный момент нет, то поток писатель переходит в момент ожидания. Если же значение Е является положительное число то происходит уменьшение числа свободных буферов на единицу, записывает данные в очередной свободный буфер и после этого наращивает число занятых буферов операцией V(Ф) (++), поток читатель действует аналогично с разницей в том что начинает работу с проверки заполненных буферов и наращивает количество свободных буферов. Критическим ресурсом является буферный пул представленный набором идентичных ресурсов, а значит с буферным пулом могут работать сразу несколько потоков (именно столько, сколько содержится буферов в пуле). В данной ситуации использовании двоичного семафора не позволяет организовать доступ к критическому ресурсу более чем одному потоку. Семафор же в свою очередь позволяет решить данную задачу синхронизации более гибко допуская при этом к разделённому пулу ресурсов заданное количество потоков. Таким образом с буферным пулом могут работать максимум N потоков часть из которых могут мыть писателе а другие читателями.

5) Тупики

Для того что бы разрешить коллизий с разделяемой областью памяти будем считать что запись в буфер и считывание из буфер будут являться критическими секциями. В данном случае можно проиллюстрировать еще одну проблему синхронизации – взаимной блокировки называемой так же дедлоками(Deadblok), тупиками, clinch.

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

Firt А - запрашивается принтер, а затем порт

Б – запрашивает устройства в обратном порядке.

Предположим что когда ОС назначила принтер к потоку А и установила связанной с этим ресурсом связную переменную поток А был прерван управление получил поток Б который сначала выполняет запрос на получение доступа к порту, а затем при выполнении следующей команды оказался заблокирован так как принтер уже занят потоком А управление снова получил поток А который в соответствии со своей задачей предпринял попытку занять порт и был заблокирован, поскольку порт уже занял поток Б. в таком положении потоки А и Б могут находиться вечно.

Тупиковые ситуации необходимо отделять от очередей. Очередь представляет собой адекватное явлении при использовании совместных ресурсов. Ресурс не доступен в данный момент но через определённое количество времени освободиться. При возникновении тупиков существует потребность потока сразу в нескольких ресурсах, при этом возникает так называемая не разрешимая ситуация.

Бесконечная блокировка

Поток А заблокирован А не вып переход к А так бесконечно
Поток Б переход к Б заблокирован Б не вып так бесконечно

 

Взаимная блокировка

Но при этом выполняется несколько обращений, авто переход управления

Поток А А1 блокируется выполнен А2 блокирован … выполнен  
Поток Б переход к Б1 блокирован Б1 переход к Б2 …  

 

Очереди с разделёнными ресурсами

Если блокируется первый ресурс то управление к А2 если все блокируется то тогда переход к Б.

6) Голодание пусть существуют 3 потока А, Б, В им необходим один ресурс но при передаче управления происходит п1 передаёт п3 и наоборот, при этом блокировки п2 не происходит, но происходит голодание п2.

Д/з Управление памятью, страничная, динамичная, сегментная и т.п. см. СиАОД

Кеширование способы кеширования.

Лекция 9

 



©2015- 2017 stydopedia.ru Все материалы защищены законодательством РФ.