This is an old revision of the document!
−Table of Contents
Вопросы к проверке знаний
1. Уровни абстракции технологий
Расположите в порядке увеличения степени абстракции технологии высокопроизводительных вычислений:
- OS Threads, SSE/MMX, C++11 Threads/Java Threads, TBB/Fork-Join framework
- SSE/MMX, OS Threads, TBB/Fork-Join framework, C++11 Threads/Java Threads
- SSE/MMX, OS Threads, C++11 Threads/Java Threads, TBB/Fork-Join framework
- OS Threads, TBB/Fork-Join framework, C++11 Threads/Java Threads, SSE/MMX
2. Закон Амдала
Что показывает закон Амдала:
- Прирост производительности в зависимости от доли последовательного кода и числа вычислительных элементов
- Прирост производительности в зависимости от числа вычислительных элементов и используемой технологии распараллеливания
- Число вычислительных элементов, необходимое для достижения заданного уровня роста производительности
- Долю последовательного кода, производительность которого невозможно повысить
3. Завершение потоков
Как называются функции, внутри которых, в зависимости от используемой технологии, происходит проверка на необходимость завершения работы потока и по результатам проверки возможно выкидывание исключений или завершение потока с применением стека зарегистрированных функций:
- Функции завершения потока
- join-функции
- Cancellation / interruption points
- Signal handlers
4. Spin mutex
Чем отличается spin mutex от обычного mutex:
- Остаётся всегда в user space
- Остаётся всегда в kernel space
- Ничем не отличается
- Позволяет читателям производить операции параллельно
5. Wait/notify
В каком состоянии находится примитив синхронизации (mutex) в приведённом коде на 1, 3 и 4 строках:
0: boost::unique_lock<boost::mutex> lock(mutex); 1: 2: while (messageQueue.empty()) 3: conditionVariable.wait(lock); 4:
- Во всех строках захвачен
- Во всех строках освобождён
- Захвачен в 1 и 4 строках, в 3 на время вызова wait освобождается
- Захвачен в 1 строке, в 3 и 4 освобождён
6. Ранжирование алгоритмов
Расположите алгоритмы синхронизации в порядке увеличения потенциальной производительности в жёсткой конкурентной среде:
- Грубая, тонкая, оптимистичная, неблокирующая
- Тонкая, грубая, оптимистичная, неблокирующая
- Неблокирующая, оптимистичная, грубая, тонкая
- Грубая, тонкая, неблокирующая, оптимистичная
7. Выбор алгоритма
Отметьте вид алгоритмов синхронизации, обычно реализуемый на CAS-операциях и позволяющий добиться максимальной независимости исполнения потоков, гарантируя общий прогресс системы:
- Грубая
- Тонкая
- Оптимистичная
- Неблокирующая
8. Wait-free алгоритм
Выберите корректное определение wait-free класса алгоритмов:
- Любой поток ожидает, пока хотя бы один другой поток не выполнил свою операцию
- Любой поток может выполнить свои функции за конечное число шагов, если ни один другой поток не находится в критической секции
- Система в целом продвигается вперед не зависимо ни от чего
- Любой поток может выполнить свои функции за конечное число шагов, не зависимо ни от чего
9. Определение типа ошибки
Какая ошибка потенциально может возникнуть в приведённом коде:
void f() { first_mutex.lock(); second_mutex.lock(); ... } void g() { second_mutex.lock(); first_mutex.lock(); ... }
- Гонка данных (Data Race)
- Взаимная блокировка (Deadlock)
- Проблема ABA
- Инверсия приоритетов
10. Реализация lock-free алгоритмов
Почему lock-free алгоритмы легче реализовать на языке со сборщиком мусора, нежели на нативных языках, например C++:
- Невозможна инверсия приоритетов
- Наличие существующих базовых контейнеров в java.util.concurrent
- Невозможна проблема ABA
- Наличие CAS-операций
Консенсус
Какое консенснусное число CAS-операций:
- 1
- 2
- 2N-2 (где N-число ячеек памяти, доступных для CAS)
- Бесконечность