Что такое оптимистическое и пессимистическое блокирование. В каких случаях какое предпочтительнее. Какие еще виды блокирования вы знаете.

 

In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.

The main categories of concurrency control mechanisms are:

 

· Optimistic - Delay the checking of whether a transaction meets the isolation and other integrity rules (e.g., serializability and recoverability) until its end, without blocking any of its (read, write) operations ("...and be optimistic about the rules being met..."), and then abort a transaction to prevent the violation, if the desired rules are to be violated upon its commit. An aborted transaction is immediately restarted and re-executed, which incurs an obvious overhead (versus executing it to the end only once). If not too many transactions are aborted, then being optimistic is usually a good strategy.

· Pessimistic -Block an operation of a transaction, if it may cause violation of the rules, until the possibility of violation disappears. Blocking operations is typically involved with performance reduction.

· Semi-optimistic - Block operations in some situations, if they may cause violation of some rules, and do not block in other situations while delaying rules checking (if needed) to transaction's end, as done with optimistic.

 

Different categories provide different performance, i.e., different average transaction completion rates (throughput), depending on transaction types mix, computing level of parallelism, and other factors. If selection and knowledge about trade-offs are available, then category and method should be chosen to provide the highest performance.

 

The mutual blocking between two transactions (where each one blocks the other) or more results in a deadlock, where the transactions involved are stalled and cannot reach completion. Most non-optimistic mechanisms (with blocking) are prone to deadlocks which are resolved by an intentional abort of a stalled transaction (which releases the other transactions in that deadlock), and its immediate restart and re-execution. The likelihood of a deadlock is typically low.

 

Both blocking, deadlocks, and aborts result in performance reduction, and hence the trade-offs between the categories.

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

 

Что такое программная транзакционная память (STM)? Какие качества имеют программы, которые ее используют?

Вступление. Транзакционная память (transactional memory, TM) – это новая программная конструкция, обеспечивающая высокоуровневую абстракцию для написания параллельных программ. TM можно реализовывать полностью программным образом (STM) или с использованием специальной аппаратной поддержки (HTM).

Система STM может распознать конфликт при первом обращении транзакции к объекту (early detection, раннее выявление) или в то время, когда транзакция пытается выполнить операцию фиксации (late detection, отложенное выявление).

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

Основная часть. Программная реализация транзакционного принципа обмена данными с оперативной памятью - называется программная транзакционная память (STM);

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

 

Расшифруйте аббревиатуру ACID в применении к системному программированию и кратко охарактеризуйте значение каждого из слов. Какая из букв аббревиатуры не применима, когда речь идет о программной транзакционной памяти (STM)?

Вступление. Транзакция – это некоторая форма выполнения программ, перенятая от сообщества баз данных [8]. Параллельно исполняемые запросы конфликтуют, когда они читают и изменяют некоторый элемент базы данных, и возникающий конфликт может привести к ошибочному результату, который не мог бы получиться при последовательном выполнении этих запросов. Транзакции гарантируют, что все запросы произведут тот же самый результат, как если бы они выполнялись последовательно в некотором порядке (serially, «сериально»; это свойство называют «сериализуемостью» (serializability)). Декомпозиция семантики транзакции приводит к четырем требованиям, обычно называемым свойствами ACID: атомарность (atomicity), согласованность (consistency), изоляция (isolation) и долговечность (durability)

ACID (atomicity, consistency, isolation, durability).

 

В информатике, акроним ACID описывает требования к транзакционной системе (например, к СУБД), обеспечивающие наиболее надёжную и предсказуемую её работу. Требования ACID были в основном сформулированы в конце 70-х годов Джимом Греем

Лингвистические корни STM.NET берут свое начало из самых разных областей, но концептуальная идея STM гениально проста и знакома: вместо того чтобы заставлять разработчиков придумывать средства распараллеливания (блокировки и все такое), дать им возможность помечать, какие части кода должны выполняться с теми или иными характеристиками дружественности к параллельной обработке, и разрешить инструментальным средствам языка (компилятору или интерпретатору) при необходимости самостоятельно управлять блокировками. Другими словами, разработчики подобно администраторам и пользователям баз данных помечают код атрибутами транзакционной семантики в стиле ACID и оставляют все черную работу по управлению блокировками нижележащей среде.

Хотя STM.NET может показаться всего лишь еще одной попыткой управления параллельной обработкой, она отражает нечто более глубокое — поиск путей переноса всех четырех характеристик ACID -транзакций баз данных в модель программирования, размещенную в памяти. Помимо управления блокировками в интересах программиста, модель STM также обеспечивает атомарность (atomicity), согласованность (consistency), изоляцию (isolation) и надежность (durability), которые сами по себе могут значительно упростить программирование независимо от наличия нескольких потоков выполнения.

 

Атомарность заявляет, что база данных изменений должны следовать принципу "все или ничего". Каждая операция называется "атомной". Если одна часть сделки не удается, вся сделка не удается. Очень важно, что система управления базами данных сохраняет атомный характер операций, несмотря на любую операционную систему или аппаратный сбой.

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

Изоляция требует, чтобы несколько изменений, совершенных в то же время, не влияли на исполнение друг друга. Например, если Джо запросил транзакции с базой данных в то же время, что Мария запросила различные сделки, и операции должны функционировать на базе данных, независимо. База данных должна либо выполнять весь запрос Джо перед выполнением запроса Марии или наоборот. Это предохраняет запрос Джо от чтения промежуточных данных, полученных в качестве побочного эффекта части запроса Марии, которая в конечном итоге не будет фиксироваться в базе данных. Обратите внимание, что изоляция собственности не обеспечивает исполнения, только того, что не конфликтует друг с другом.

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

 

Не применима буква “I”(изоляция), т.к. при STM - транзакции выполняются таким образом, как будто текущая транзакция это единственная операция над текущими данными, а при ACID - несколько изменений, совершенных в то же время, не влияют на исполнение друг друга.

22. Что такое конвейер (PIPE)? Что такое именованный конвейер? Охарактеризуйте их. Как эти объекты можно использовать для взаимодействия программ (приведите несколько примеров)?

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

В программировании именованный канал или именованный конвейер (англ. named pipe) — расширение понятия конвейера в Unix и подобных ОС, один из методов межпроцессного взаимодействия. Это понятие также существует и в Microsoft Windows, хотя там его семантика существенно отличается. Традиционный канал — «безымянен», потому что существует анонимно и только во время выполнения процесса. Именованный канал — существует в системе и после завершения процесса. Он должен быть «отсоединён» или удалён когда уже не используется. Процессы обычно подсоединяются к каналу для осуществления взаимодействия между процессами.

Именованные каналы в Unix

Вместо традиционного, безымянного конвейера оболочки (англ. shell pipeline), именованный канал создаётся явно с помощью mknod или mkfifo, и два различных процесса могут обратиться к нему по имени.

Например, можно создать канал и настроить gzip на сжатие того, что туда попадает:

mkfifo pipe

gzip -9 -c < pipe > out

Параллельно, в другом процессе можно выполнить:

cat file > pipe

что приведёт к сжатию передаваемых данных gzip-ом.

 

Конвейер (pipe) - перенаправление ввода-вывода в Linux

В UNIX-подобных операционных системах пользователю открывается огромный простор для перенаправления ввода-вывода команд.
Простым примером перенаправления является pipe (конвейер). Обозначается он символом “|”. Используется pipe следующим образом:
команда 1 | команда 2 | команда 3...
При таком вызове все данные, которые при обычном запуске команды 1 выводились бы на экран будут поступать на стандартный ввод команды 2, как будто бы мы вводим эти данные с клавиатуры.
Поясню на примере. Введите команду "ls -l /" (Без кавычек). Вы увидите как на экран будет выведено содержимое корневого каталога. Теперь давайте перенаправим вывод этой команды на ввод другой команды: grep, которая ищет во входных данных некоторое сочетание символов. Например, используем такую команду: "ls -l / | grep tmp". Объясню поподробнее что это значит: команда ls -l / Выведет содержимое корневого каталога (как мы убедились выше). Дальше данные поступают команде grep tmp, которая произведет поиск по входным данным (полученным из 1 команды). После чего команда grep выведет то, что нашла на экран (разумеется, это дело опять можно перенаправить).
Что очень важно отметить, команды исполняются одновременно, то есть все, что поступает на вывод в первой программе немедленно поступает на вход второй, не дожидаясь завершения 1.
Если проводить ассоциации с реальным миром, то можно представить pipe в виде длинной трубы, распооженной вертикально (что-то мне подсказывает, что разработчики системы преставляли себе это именно также, потому и выбрали такое название и символ |). В эту трубу некто (команда 1) сверху кидает яблоки (данные). Второй некто (команда 2) достает из трубы эти яблоки. Ширина трубы не позволяет яблакам менять порядок, то есть в каком порядке они были отправлены командой 1, в таком порядке они будут приняты командой 2. Скорости работы команд также могут различаться. В случае, если второй некто замешкается, яблоки будут оставаться в трубе, дожидаясь обработки. Если замешкается первый, то второй будет ждать поступления данных.

 

 

23. Объясните разницу между взаимодействием программ с помощью разделяемой памяти и обмена сообщениями. Опишите преимущества и недостатки обоих вариантов. В каких случаях предпочтительно использование каждого из них? (приведите несколько примеров)