15. Многопоточные программы, стандарт posix.

Многопоточность — свойство платформы (например, операционной системы, виртуальной машины и т. д.) или приложения, состоящее в том, что процесс, порождённый в операционной системе, может состоять из нескольких потоков, выполняющихся «параллельно», то есть без предписанного порядка во времени. При выполнении некоторых задач такое разделение может достичь более эффективного использования ресурсов вычислительной машины.

Определение

POSIX – стандарт системы UNIX, который определяет минимальный интерфейс системных вызовов, который должны поддерживать совместимые с ним системы UNIX (и не только).

Задачи POSIX:

• Содействовать облегчению переноса кода прикладных программ на иные платформы.

• Способствовать определению и унификации интерфейсов заранее при проектировании, а не в процессе их реализации.

• Сохранять по возможности и учитывать все главные, созданные ранее и используемые прикладные программы.

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

• Развивать стандарты в направлении обеспечения коммуникационных сетей, распределенной обработки данных и защиты информации.

• Рекомендовать ограничение использования бинарного (объектного) кода для приложений в простых системах.

Состав

• Основные определения (англ. Base definitions) — список основных определений и соглашений, используемых в спецификациях, и список заголовочных файлов языка Си, которые должны быть предоставлены соответствующей стандарту системой.

• Оболочка и утилиты (англ. Shell and utilities) — описание утилит и командной оболочки sh, стандарты регулярных выражений.

• Системные интерфейсы (англ. System interfaces) — список системных вызовов языка Си.

• Обоснование (англ. Rationale) — объяснение принципов, используемых в стандарте.

16. Синхронизация потоков.

Для синхронизации потоков применяются семафоры, мьютексы и критические секции.

Семафор

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

Мьютекс

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

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

Критическая секция

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

17. Семафоры, алгоритм Дейкстры.

Определение

Семафор — объект, ограничивающий количество потоков, которые могут войти в заданный участок кода. Определение введено Эдсгером Дейкстрой в 1962 или 1963 году. Семафоры используются для синхронизации и защиты передачи данных через разделяемую память, а также для синхронизации работы процессов и потоков.

Это объект, над которым можно выполнять действия:

1. Инициализация семафора (задать начальное значение счётчика);

2. Захват семафора (ждать, пока счётчик станет больше 0, после этого уменьшить счётчик на единицу);

3. Освобождение семафора (увеличить счётчик на единицу).

Применение семафоров:

1. запрет одновременного выполнения заданных участков кода (критические секции);

2. поочерёдный доступ к критическому ресурсу (важному ресурсу, для которого невозможен (или нежелателен) одновременный доступ);

3. синхронизация процессов и потоков (например, можно инициировать обработку события отпусканием семафора).

Проблемы семафоров:

1. можно написать программу с «утечкой семафора», вызвав enter() и забыв вызвать leave(). Реже встречаются ошибки, когда дважды вызывается leave();

2. семафоры чреваты взаимной блокировкой потоков.

Алгоритм Дейкстры

Алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его используют протоколы маршрутизации OSPF и IS-IS.

Формальное определение

Дан взвешенный ориентированный граф без дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины графа до всех остальных вершин этого графа.