Главная / Программирование / Теория и практика многопоточного программирования

Теория и практика многопоточного программирования - ответы на тесты Интуит

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

Смотрите также:

Суперкомпьютерные технологии

Отличие монитора от Mutex заключается в:

(1) Постоянном контроле потоком состояния замка

(2) Возможности отпустить блокировку, находясь внутри критической секции

(3) Возможности одновременно исполнять 2 потока в критической секции

Каким образом закон Мура повлиял на архитектуру ЭВМ?

(1) Процессоры периодически удваивали разрядность

(2) Кардинально увеличилось число разъёмов под процессоры на материнских платах

(3) Процессоры получили многоядерную архитектуру

(4) Частота работы процессора каждые два года удваивается

Примитивы синхронизации обеспечивают:

(1) Синхронность исполнения команд на 2 и более процессорах

(2) Коммуникацию между потоками

(3) Синхронизацию часов для различных потоков

Как в модели детерминированного конечного автомата можно интерпретировать запись значения переменной?

(1) Как состояние автомата

(2) Как переход в автомате

(3) Как изменение самого автомата

Результатом протокола консенсуса является:

(1) Значение из числа допустимых значений типа данных

(2) Значение из числа переданных в вызов метода протокола

(3) Значение из числа переданных в вызов метода протокола, или значение по умолчанию

Для синхронизации доступа к разделяемому счётчику невозможно использовать:

(1) Крупнозернистую синхронизацию

(2) Мелкозернистую синхронизацию

(3) Ленивую синхронизацию

Какой тип памяти является самым быстрым для чтения-записи из процессора?

(1) HDD

(2) SSD

(3) Cache

(4) RAM

Можно ли ввести критерий корректности для программы-генератора случайных чисел?

(1) Да

(2) Нет

Алгоритм, приведённый ниже, относится к типу:


					for (int i = 0; i < N; i++) {
						lock.lock();
						array[i].proceed();
						lock.unlock();
						}

(1) Блокирующих

(2) Неблокирующих

(3) Свободных от ожидания

Начальное состояние протокола консенсуса:

(1) Всегда бивалентно

(2) Всегда унивалентно

(3) Всегда критическое

Операция изменения элемента в множестве занимает 3 микросекунды. Операция взятия замка является идеальной (константное время) и занимает 4 микросекунды. Оправдано ли использование оптимистичной синхронизации?

(1) Да

(2) Нет

(3) Недостаточно информации

Какие типы параллельных систем можно отнести к комбинированным по отношению к доступу к памяти?

(1) 2x Intel Core i7

(2) GPGPU

(3) OpenMP-MPI

(4) PThreads

Для фиксации приоритета потока можно использовать циклическую систему времени?

(1) Да

(2) Нет

Является ли построенное выражение противоречивым:


						write[A](flag[A]=true)  read[A](flag(B)==false) 
						 write[B](flag[B]=true)  read[B](flag(A)==false)

(1) Да

(2) Нет

Атомарный регистр имеет число консенсуса (целое число):

Ленивый подход к синхронизации - это:

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

(2) Отказ от использования операций над разделяемыми данными

(3) Блокирование малых частей разделяемого объекта, а не всего объекта целиком

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

(1) Load Balancing

(2) GRID

(3) OpenMP

(4) MPI

Подграф А доминирует надо подграфом Б:

(1) Если каждая вершина А доминирует над всеми вершинами Б

(2) Если значения в вершинах А больше любого значения Б

(3) Если каждая вершина А доминирует над хотя бы одной вершиной из Б

Всегда ли метод входа в критическую секцию завершается за конечное число шагов?

(1) Да

(2) Нет

Тип атомарного RMW регистра определяется:

(1) Функцией модификации значения

(2) Ёмкостью инкапсулированной переменной

(3) Количеством процессорных тактов, расходуемых на запись

Множество - это структура:

(1) Поддерживающая вставку и извлечение объекта по ключу

(2) Поддерживающая неуникальные значения

(3) Всегда с детерминированным поведением

Какие из принципов относятся к принципам архитектуры фон Неймана?

(1) принцип синхронности

(2) принцип локальности

(3) принцип двоичного кодирования

(4) принцип однородности памяти

Гонка данных:

(1) Нарушает заложенную в программу логику

(2) Блокирует исполнение потока

(3) Приводит к стабильному воспроизведению ошибки

Утверждение соответствует тотальной последовательной спецификации:

(1) Собака, если ей кинуть палочку, обязательно её принесёт.

(2) Если в банке лежит больше одной конфеты, операция по извлечению одной конфеты закончится успешно.

(3) Довольный кот, если его погладить, будет урчать.

Детерминированный объект - это:

(1) Объект с детерминированным поведением методов для всех состояний объекта и всех входных параметров

(2) Объект, занимающий в памяти фиксированный объём памяти

(3) Объект, предсказуемо работающий только в однопоточной программе

Натуральный параллелизм опирается на принцип:

(1) Дешёвая память, дорогое время

(2) Дешёвое время, дорогая память

(3) Быстрое чтение, медленная запись

(4) Быстрая запись, медленное чтение

Шина - это:

(1) средство коммуникации устройств в архитектуре PC

(2) способ подключения периферийных устройств к портам

(3) микросхема в процессоре

Более подвержены проблеме ABA:

(1) Управляемые языки

(2) Неуправляемые языки

Упорядоченная согласованность гарантирует порядок исполнения методов:

(1) По времени

(2) В порядке вызова в рамках одного потока

(3) В порядке вызова в рамках всей системы

Отличие частично корректного консенсуса от полностью корректного:

(1) В возможности существования сценариев, не приводящих к решению

(2) В возможности существовании сценариев, приводящих к различным решениям в разных потоках

(3) В возможности существования сценариев, возвращающих значение по умолчанию

Для очереди с приоритетом, реализованной на связном списке, можно достигнуть скорости чтения:

(1) O(1)

(2) O(N)

(3) O(logN)

В системах с общей памятью всегда один общий кэш?

(1) Да

(2) Нет

Спор за блокировку приводит:

(1) К остановке программы

(2) Нарушению порядка исполнения

(3) Плохому масштабированию программы

Линеаризуемый регистр иначе называется:

(1) Атомарным

(2) Константой

(3) Регулярным

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

(1) 1

(2) Меньше половины

(3) Все, кроме одного

Алгоритм Bakery Lock не является корректным выбором для использования в замках, потому что:

(1) Он подвержен ABA проблеме

(2) Он подвержен deadlock-проблеме

(3) Он основан на предположении упорядоченной согласованности, не выполняющемся на современных архитектурах

К промахам кэша приводят:

(1) Множественные разыменования в ООП

(2) Частое чтение одной переменной разными ядрами

(3) Частая запись значения в одну переменную

Возможна ли ситуация взаимной блокировки в неожидающем алгоритме?

(1) Да

(2) Нет

Подыстория H|X системы по объекту X может содержать вызовы методов объекта Y?

(1) Да

(2) Нет

Реализация универсального объекта предполагает:

(1) Создание блокирующей реализации разделяемого объекта

(2) Создание неблокирующей реализации разделяемого объекта

Элементами и характеристиками процесса, но не потока, являются:

(1) Контекст

(2) Идентификатор, доступный во всей ОС

(3) Глобальные переменные

Атомарные операции занимают ровно один процессорный такт?

(1) Да

(2) Нет

Порядок исполнения программы:

(1) Может быть изменён компилятором

(2) Задаётся программистом

(3) Не детерминирован

Порядок исполнения программы в важных местах можно зафиксировать?

(1) Да

(2) Нет

Замки чтения-записи при установке reader-замка запрещают:

(1) Всем потокам читать из заблокированного объекта

(2) Всем потокам изменять заблокированный объект

(3) Не запрещают действий над объектами

Какое эвристическое правило фактически предсказало увеличение разрядности процессоров?

(1) Закон больших чисел

(2) Правило Паркинсона

(3) Закон Мура

(4) Второй закон Мерфи

Примитивы синхронизации индивидуальны для различных языков?

(1) Да

(2) Нет

Может ли существовать модель программы с пустым множеством конечных состояний?

(1) Да

(2) Нет

Консенсус может быть реализован при помощи критических секций?

(1) Да

(2) Нет

Какая проблема возникает при использовании крупнозернистой синхронизации с большими массивами данных?

(1) Гонка данных (race condition)

(2) ABA проблема

(3) Борьба за замок (lock contention)

Укажите верное утверждение.

(1) Для распараллеливания алгоритма существующей последовательной программы часто достаточно запустить её на многоядерном процессоре

(2) Для распараллеливания алгоритма существующей последовательной программы часто достаточно запустить несколько её экземпляров

(3) Использование кэша процессора приводит к замедлению работы программ, поэтому его необходимо отключать

(4) Использование кэша процессора может приводить к существенному ускорению программы

Для программ существует формальное математическое определение корректности?

(1) Да

(2) Нет

Алгоритм, приведённый ниже, относится к типу:


						int oldValue = -1;
						while(oldValue != r.compareAndSet(oldValue, myValue)) oldValue = r.get();
						proceed();

(1) Блокирующих

(2) Неблокирующих

(3) Свободных от ожидания

Может ли существовать неблокирующий протокол консенсуса без критических состояний?

(1) Да

(2) Нет

Операция изменения элемента в множестве занимает 3 микросекунды. Операция взятия замка является идеальной (константное время) и занимает 4 микросекунды. Время исправления коллизии колеблется от 10 до 50 микросекунд. Вероятность коллизии при изменении составляет 1%. Оправдано ли использование оптимистичной синхронизации?

(1) Да

(2) Нет

(3) Недостаточно информации

Характеристикой GRID-системы является:

(1) Исполнение в системах с общей памятью

(2) Низкая устойчивость к ошибкам

(3) Исполнение распределённых программ

Использование системных часов всегда решает проблему вычисления приоритета?

(1) Да

(2) Нет

Могут ли в критической секции находиться одновременно два потока?

(1) Да

(2) Нет

Очередь имеет число консенсуса минимум (целое число):

Можно ли комбинировать ленивый подход и мелкозернистую синхронизацию?

(1) Да

(2) Нет

Критично ли для кластерных вычислений выпадение одного из узлов в ходе вычислений?

(1) Да

(2) Нет

Если "" – доминирование, и ad, ae, bc, bd, то:

(1) {a,b}{c,d}

(2) {a,b}{d}

(3) {c,d}{a}

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

(1) Неожидающее свойство

(2) Честность

(3) Детерминированность

Какое число консенсуса имеет тривиальный RMW регистр?

Пул - это структура:

(1) Поддерживающая вставку и извлечение объекта по ключу

(2) Поддерживающая неуникальные значения

(3) Всегда с детерминированным поведением

Принцип однородности в архитектуре фон Неймана - это:

(1) принцип одинаковой важности компонентов компьютера

(2) принцип равноправия процессов

(3) принцип неразличимости данных и кода

Гонка данных – это:

(1) Конкурентный доступ на чтение к одной переменной

(2) Конкурентный доступ к переменной, в котором хотя бы один поток изменяет её значение

(3) Рассинхронизация потоков

Формальное описание метода, которое учитывает все возможные состояния объекта, можно назвать:

(1) Глобальным

(2) Дескриптивным

(3) Тотальным

Универсальный объект:

(1) Это полиморфный объект, который можно использовать как любой другой объект

(2) Это объект, с помощью которого можно конструировать неожидающие реализации любого разделяемого объекта

(3) Это любой объект, разделяемый между потоками

Хэш-таблица с открытой адресацией по одному ключу хранит:

(1) 1 элемент

(2) Много элементов

Механизм асинхронной передачи данных из медленных источников - это:

(1) cache coherence

(2) DMA

(3) NUMA

В управляемых языках невозможно воспроизвести ситуацию ABA?

(1) Да

(2) Нет

Регистры, обладающие свойством упорядоченной согласованности, называются:

(1) Безопасными

(2) Регулярными

(3) Атомарными

Корректный поток таков, что:

(1) Корректно обрабатывает все исключительные ситуации

(2) Всегда доходит до точки возврата

(3) Не прерывается и прочитывает все направленные ему сообщения

Для множества, реализованного на связном списке, скорости чтения составляет:

(1) O(1)

(2) O(N)

(3) O(logN)

Когерентность кэша – это задача в системах типа:

(1) NUMA

(2) SMP

(3) DMA

Возможен ли в неожидающей реализации алгоритма спор за блокировку?

(1) Да

(2) Нет

Допустима ли для атомарного регистра такая ситуация:


				writeStart[A](R=2)writeEnd[A](R=2)writeStart[A](R=3)
				read[B](R==3)read[B](R==2)writeEnd[A](R=3)

(1) Да

(2) Нет

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

(1) 1

(2) Половина или больше

(3) Все, кроме одного

В идеальной реализации замка время обращения к замку T зависит от числа потоков N как:

(1) T = kN

(2) T = const

(3) T = log(N)

Управляя квотой на использование кэша, можно влиять на скорость программы:

(1) Использование кэша не регулируется

(2) Да

(3) Нет

Что общего у проблемы "взаимная блокировка" и "имитация деятельности"?

(1) Обе проблемы возникают из-за вечных циклов

(2) Обе проблемы разрешаются увеличением времени ожидания

(3) Обе проблемы приводят к прекращению прогресса в исполнении программы

. Подыстория H|A системы по потоку A может содержать вызовы методов объектов, созданных в других потоках?

(1) Да

(2) Нет

Отсутствие конфликтов при доступе к полям разделяемого объекта при использовании универсального объекта обеспечивается:

(1) Созданием копии объекта для каждого потока

(2) Использованием критических секций

(3) Использованием семафоров

Процесс может содержать:

(1) Один поток

(2) Много потоков

(3) Это синонимы

Промежуточное состояние атомарной операции можно просмотреть из параллельного потока?

(1) Да

(2) Нет

Сложение двух переменных в оперативной памяти является атомарной операцией?

(1) Да

(2) Нет

Выключение оптимизации компилятора гарантирует заданный порядок исполнения программы?

(1) Да

(2) Нет

При помощи семафора невозможно организовать эксклюзивный доступ к объекту?

(1) Да

(2) Нет

Какова характеристика зависимости количества транзисторов в процессоре от времени в соответствии с законом Мура?

(1) Линейная

(2) Логарифмическая

(3) Геометрическая

(4) Экспоненциальная

Примитивы синхронизации являются собственностью потока?

(1) Да

(2) Нет

Модель программы, в которой при возникновении определённого события для определённого состояния может с некоторой вероятностью произойти один из множества переходов, называется:

(1) Детерминированный конечный автомат

(2) Недетерминированный конечный автомат

(3) Сеть Петри

Два объекта с числом консенсуса 8 могут решить задачу консенсуса для (целое число) потоков:

Сколько замков нужно, чтобы обслужить конкурентный доступ к атомарному регистру в 4-поточной программе (целое число)?

Укажите верное утверждение.

(1) Доступ к переменной в кэше гораздо быстрее, чем к её значению в оперативной памяти

(2) Запись переменной на диск можно осуществить за один процессорный такт

(3) Доступ к оперативной памяти гораздо быстрее, чем к её закэшированному значению

Для определения корректности программы достаточно статического анализа кода?

(1) Да

(2) Нет

Алгоритм, приведённый ниже, относится к типу:


					int oldValue = -1;
					if (oldValue != r.compareAndSet(oldValue, myValue)) {
					//someone was faster
					foo();
						} else {
					//that’s my turn!
					bar();

(1) Блокирующих

(2) Неблокирующих

(3) Свободных от ожидания

Верно ли, что всегда решением консенсуса является значение потока, сделавшего первый ход?

(1) Да

(2) Нет

Операция изменения элемента в множестве занимает 3 микросекунды. Операция взятия замка является идеальной (константное время) и занимает 4 микросекунды. Время исправления коллизии колеблется от 500 до 1000 микросекунд. Вероятность коллизии при изменении составляет 1%. Оправдано ли использование оптимистичной синхронизации?

(1) Да

(2) Нет

(3) Недостаточно информации

Программу, написанную с использованием OpenMP, можно запустить:

(1) На распределённой системе

(2) На графической плате

(3) На многоядерной системе

(4) На двухпроцессорной системе

Время и временные отметки – это синонимы с точки зрения программы?

(1) Да

(2) Нет

Могут ли два потока одновременно выполнять метода входа в критическую секцию?

(1) Да

(2) Нет

Common2 RMW регистр имеет число консенсуса строго равное (целое число):

Какой из этих примеров соответствует принципу ленивой синхронизации?

(1) Сборка мусора

(2) Дефрагментация диска

(3) Использование разреженных матриц

(4) Использование хэш-таблиц

Критично ли для вычисления на GRID выпадение одного из узлов в ходе вычислений?

(1) Да

(2) Нет

Доминирование на графе – транзитивное отношение?

(1) Да

(2) Нет

При честной реализации замка, в каком порядке могут войти потоки в критическую секцию?


					doorway1[A]doorway1[B]doorway2[A]doorway2[B]doorway1[С] doorway2[С]waiting[С]waiting[B]waiting[A]

(1) A,B, C

(2) A, C, B

(3) B, A, C

Какое число консенсуса имеет конструкция "sticky byte":

(1) 1

(2) 2

(3) бесконечность

Примером пула является:

(1) Хэш-таблица

(2) Стэк

(3) Очередь

(4) Связный список

Принцип архитектуры фон Неймана, описывающий самостоятельное управление программой своим исполнением, называется:

(1) принцип программного управления

(2) принцип автономности

(3) принцип нелинейности

Плавающие ошибки в программе могут быть обусловлены:

(1) гонкой данных

(2) недостаточной производительностью процессора

(3) несвоевременным переключением контекста

Чем отличается сигнатура метода от последовательной спецификации?

(1) В сигнатуре можно опускать имена переменных

(2) Последовательная спецификация рассматривается только в последовательных системах

(3) Последовательная спецификация включает в себя сигнатуру и описывает ожидаемое поведение метода

Класс является универсальным в системе из 3 потоков, если его число консенсуса больше, либо равно (целое число):

Верно ли утверждение, что в структурах с натуральным параллелизмом не нужно задумываться о синхронизации доступа?

(1) Да

(2) Нет

Программа, часто использующая оперативную память:

(1) Будет предельно производительной, из-за отсутствия обращений к жёсткому диску

(2) Будет медленнее программы, использующей кэш из-за эксплуатации шины

Проблема ABA – это:

(1) Последствия некорректного именования переменных

(2) Следствие гонки данных

(3) Проблема использования указателей для идентификации объекта

Допустима ли для регулярного регистра такая ситуация:


					writeStart[A](R=2)writeEnd[A](R=2)writeStart[A](R=3)
					read[B](R==3)read[B](R==2)writeEnd[A](R=3)

(1) Да

(2) Нет

Решающее исполнение предполагает:

(1) Преодоление решающего состояния

(2) Завершения хотя бы одного потока

(3) Завершение всех потоков

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

(1) O(1)

(2) O(N)

(3) O(logN)

В системах типа NUMA доступ к памяти соседнего ядра:

(1) невозможен

(2) медленнее, чем к локальной

(3) такой же, как к локальной

Если программа на 2 ядрах исполняется за 8 секунд, в на 4 ядрах за 6, то наиболее вероятной причиной этому может быть:

(1) Спор за блокировку

(2) Гонка данных

(3) Переполнение стэка

Укажите верное утверждение:

(1) Точка линеаризации фиксирует изменение состояние объекта, видимое для других потоков

(2) Линеаризуемый регистр имеет неизменяемое значение

(3) Точка линеаризации совпадает с завершением метода

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

(1) 1

(2) Половина или больше

(3) Все, кроме одного

Проблема, которую решает подход Local Spinning называется:

(1) Инвалидация кэша

(2) Выравнивание данных

(3) ABA-проблема

Использование локально расположенных данных может дать прирост производительности программы?

(1) Да

(2) Нет

Каким образом можно избежать взаимной блокировки?

(1) Используя Spinlock вместо Mutex

(2) Используя компиляцию без оптимизации

(3) Используя примитивы синхронизации с принудительным прерыванием ожидания

История, у которой вызовов на один меньше, чем возвратов, может быть:

(1) Последовательной

(2) Завершённой

(3) Легальной

Одинаковая линеаризация вызовов методов разделяемого объекта универсальным объектом осуществляется при помощи:

(1) Разделяемого атомарного регистра

(2) Разделяемого стэка

(3) Очереди заявок на исполнение метода

Процесс отличается от программы:

(1) наличием приоритета

(2) наличием имени

(3) это одно и то же

Операция копирования данных из оперативной памяти в регистр является атомарной?

(1) Да

(2) Нет

Перестановка операций в программе всегда приводит к некорректному исполнению?

(1) Да

(2) Нет

Сколько типов барьеров памяти можно выделить (целое число)?