Tanenbaum (модели конситентности) (1162628), страница 5
Текст из файла (страница 5)
6.2. Модели непрстивсречивссп~, оривнтнрсваиньж на денные 347 + С переменной синхронизации не ыпжет быль произведена ни одна операция до полного и повсеместного завершения предшествующих ей операций записи. + С элементами данных не может быть произведена ни одна операция до полного эанершения всех операций с переменнымн синхроннюции. Первый пункт гласит, что все процессы могут наблюдать за нсеми операциями над переменными синхронизации, которые с точки зрения этих процессов проиююдят а одинаковом порядке.
Другими словами, если процесс Р< вызывает операцию зугсьпю1 хе<5) ) в то же самое время, когда процесс Р2 вызывает операцию зуэсэгсп1ге<52), результат будет точно таким же как если бм операция эуасэгсо1 те <5) ) была вызвана раньше операции аувсэгсп1 ге<52), или наоборот. Второй пункт указывает на то, что синхронизация очищает конвейер. Она уг коряет выполнение всех операций пения, которые в этот момент происжщят„ частично завершены или завершены в некоторых локальных копиях, и привоюп их к повсемеспюму эавершениш. Когда синхронизалия заканчивается, гарантировано зааанчиваются все преашеспювавшие ей операции записи.
Производя синхронизацию после изыенения совместно используемых данных, процесс перегюсит новые значения во все локальные копии хранилища. Третий пункт поясняет, что при доступе к элементам данных (как для записи, так и для чтения) все прдлшествующне синхрсниатции должны быль завершены. Производя перел чтением ссвмество всиольэуемых данных сиюцюннэацию, процесс может бып уверен, что получит самые есвежиеь значения.
.В отличие от предыдущих ьюделей непротиворечивости, слабая непротиворечивость реализует непротиворечивость групп операций, а ие гпдельных операций чтения и записи. Зта модель наиболее широко иглюльзуегсл, если отдельные процсяуры доступа к общим лавнмм Репки, а бсльгпая часть операций доступа собрана в грушке (много операцяй за коРоткий срок, а пегом ничего в течениедолгого времени). Другое важное отличие от предыдущих моделей непротиворечивости заклю жется в том, что теперь мы ограничены только временем шждержавия непротиворсчижкти, в то время как ранее мы были ограничены фермой непротиворечивости. На самом деле мы можем сказать, что в случае слабой непротиворечивости соблюдается последовательная непротиворечивость между труппами операций, вне между отлельными операциями.
Для выделения этих групп используются переменные синхронизации. В идее о лопустнмосги сущеспювания в памяти неверных значений нет ничего ножко. Множество компиляюров еплутуют» таким же образом. Для примера рассмотрим фрагмент программы из листинга 6.1, где все переменные инициализируются соответствующими значениями. Оптимизирующий компилятор может производить вычисление переменных а и Ь в регистрах, времшпю сохраняя там результат и ие обновляя эти переменные в памяти. Только вызов функции 1 заставляет компилятор помесппь текущие значшцш а и Ь обратно в память, поскольку ( должна ими пользоваться.
Зто типичный пример оцтимнзация компилятора. 348 Глава 6. Непротиворечивость и лнкация Листинг 6.1. Хранение в регистрах некоторьк переменных гпд а. Ь, с, б. е. х. ю О оедеиеннне (лс *р, *о: // уназатени (ог /(тов р. глг "О): О протОтип функции // а хранится в регистре О Ь гом // будет испмьзоаано оовднев О (Ьдег иаюяьяовано позднее !/ р нсяучаег адрес а О о яснучаег адрес Ь О вызов функции а х*х; Ь-у*у с-а*а*агЬ*Ь+а*Ьг б-а*а*с: р - да: О - ЗЬг е 1(р, О); РИ ФР)» Рг(х)Ь 3 Ртг)Я(к)в Чйх)Ь 3 Пх)Ь З Н(к)Ь Н(х)в З Рэг е б Рис.б.тп.
Допустимая нрн сявбой ив о рот иваром вост н последммтагьноояь событий (а). Недопустимая нрн оливой нвлрогнварвчнзссти оосивдгяагвяьнооть событий (б) Ситуация иа рис. 6. (О, б иная. Здесь процесс Р2 сикхронизирован. Зто означает актуальносп, его локальной копии хранилигца данных. Когда он будет считывать значение л, он получит значение 6. Получение а. квк видно из рисунка, при слабой непротиворечивости невозможно. 6.2.6.Свободнвянепротиворечивость Слабая иштротиворечнвость имеет проблему следующего рода: когда осуществ- ляется доступ к переменкой синхроиюации, хранилище данных не знает, то ли зто проиожжит потому, что процесс закончил запись совместно ислользусмых В данном глуше неправильные значения в памяти доиустнмы, потому что компилятор знает, что делает (а программу ие волнует, по вначения в измяти н» актуальны).
Ясно, что если будет создан второй процесс, который может читать из памяти без ограничений, вта схеме перестанет работать. Твк, вацример, еслц в ходе присвоения значения б второй процесс считает а, Ь и с, он получит щютиворечивые данные (старые значения а и Ь н новое значение с). Для предупреждения лаоса можно представить себе специальную защиту, при которой компилятор сначала должен счипавать специальный бит (флаг), сигнализирующнй, что память не актуальна. Если доступ к а хочет получить другой процесс„ему придется ожидать установки флага: Таким образом, мы получим по пи абсолютную непроппюрсчивость, обеспечинвгдмую программной синхроннэапией и тем, что все стороны выполняют нравнлв. Обсудим теперь относиюльно менее отвлмгенную ситуацию. На рис. 6.)0, о мы видим, что процесс Р1 осуществляет две записи значений элементов данных, после чего синхронизируется (показано буквой 5). Если Р2 н РУ к этому моменту етое не были синхронизированы.
мы не можем дать никаких гн)жнпг й по поводу того, что они увидят. Таким образом, ша последовшельность о/бытий допусткмк 6.2. Ьщдвли непротиворечивости, ориентированные ивдмщые 349 данных, то лн наоборот качал чтение данных. Соответственно, оно может предпринять действия, иеобхсднмме в обоих случаях, например. убедиться, что завершены (то есть расщкктранены иа все копии) все локально инициированные оперыгип заииси и что учщны вге операции записи с друпгх копий.
Если хранилище должно распознавать разницу между ююдом в критическую область и выхгщом из нее, может потребоваться более эффективная реализация. Для предоставления этой информации необходимо два типа пщюмеипых пэи двв типа операций синхронизации, а ие спин. Свободная яелрсэшесрьчпеосщь (щ(еаю соязи~ясу) предссщвляет вти два типа «165$ Операция эахеажа (асдибч) используется для сообщения хранилищу данных о входе в критическую область, а операция оаюбеждеьпя (гейию) говор!и о тоьь что критическая область была покинута. Зтн операции могут быль реализованы одним из двух способов: во-первых, обычнымн операциями наа специальнмми переменными; во-вторых, специальными операциями.
В любом случае программист отвечает за вставку в программу соответпкуюшего дополнительного кола, реалпзуюшвго, например, вызов библиотечных процелур ассв! ге и ге!вазе или процедур епсег сщг!сщ ген!ги и !вате сгуг!сз! го)зов. В случае свободной непротнворечнщктн, кроме того, независимо от критических областей пожно использовать барьеры. Бщммр (Ьапмт) — що механизм синхронизации, который предваряет любой процесс в начале фазы программм под номером и+1 Ио того, как все процессы окончат фазу и. Когда процесс подойдет к барьеру, он должен дождатьея, пока к нему ие еподтянутсяь и все остальные процессы.
Когда последний из процессов подойдет к барьеру, все совместно используемые данные синхрониэируются, и процессы продолжают свою работу. Отправщцие от барьера выполняется по захвату, а приход к бэрыру— по освобождению. Вдобавок к этим операциям снихронипщии также возможны чщние и вались совместно используемых данных. Захват и освобожление не могут применяться ко всем данным хранилища Они могут охранять только отдельные совместно используеьцяе данные, в зтОм случае только эти Ланные оотаются цепротиворечивыми.
Совместно используемме даннме, сохраняющие свою нещютиворечивость, называются заи1пп!еюпьчи (ргщегзегг). Хранилище данных со свободной иепротнворечгпюстью щ(жщируец 'гго прн захвате процесса хранилище сделает так, что все локальные копии эавщщенных данных при необходимости бузят актуэлнзированы и'стаиуг непротиворечивыми относительно сгюих удаленных копиЕ Когда проюайлет освобождение, измененные защищенные данные будут распространены на другие локальные копии хранилища. Захват петарантирует, что лохальиме изменения булут немедленно раэоезыны другим локальным копнам. Сгкиветственио, освобождение ие обязательно приведет к импорту изменений из друпп копий.
На рис. 6.11 показана допустимак для свободной нещютиворечивостк последовательность событий. Процесс Р! производит ваюит, дважды изменяет элемент данных. а затем ироиэводит освобождение. Процесс Ру производит захват и считывает элемент данных. Он га)интировэно получает значение, которое элемент даивмх имел в момент освобождения, а именно Ь (кроые случая,.когда за- ЗВО Глава б.
Ыеппотиворвчивость н репликеция хват Р2 происходит раньше, чем захват Р1). Если захват произошел до того, как процесс Р1 произвел освобождение, захват будет ожидать совершения оаюбшкдения. Поскольку процесс РУ ие сможет осуществить захват до ггення совместно используемых данных, хранилище данных не будет обязано выдать ему текущее значение х. н этому процессу будет эоэзрашегю значение и пз: П(х)а Пие. 6.11. дсотс ни и» пссэелсазтмы петь сапитиа при свсеодиой иепретивсречииютн Чтобы прояснить свободную иепротшюречизость, давайте кратко определим ее возможную реализацию (несложиую) э контексте реплнцирупчой базы данных Произвола птхзат, процесс посылает сообщение центральному менеджеру синхронизации, эапрашиюя захват отделыюй блокировки.
В отсутствии других желающих запрос удовлетворяется и происхцаит захват. Затем следует произвольная послеповательиость локальных операций чтения и записи. Ни одна из этих операций ею расщкютраняется на другие копии базы, В процессе осэсбшкдения модифьщироэаниые данные рассмлаэжся другим копиям, которые использукп эти даннме. После того как каждая копия подтзерзит получение этих дапщах, центрвьиый менеджер синхронизаций уэеаомляепя о произошедшем освобождении. Таким образом, произвольное число операций чтения и эаписз совместно используемых данных сопровождается фиксированными дополнительными затратами Захваты и освобождения при разных блокирспках проис- холят независимо друг от друга.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
