2011-gre-cs-practice-book.pdf/Q47 — различия между версиями

Материал из DISCOPAL
Перейти к: навигация, поиск
 
(не показано 8 промежуточных версий 2 участников)
Строка 1: Строка 1:
 
== Вопрос: Q47-08c765 ==
 
== Вопрос: Q47-08c765 ==
  
 +
Рассмотрим следующие 2 многопоточные задачи, в которых операции присваивания исполняются атомарно. Изначально, переменные с разделяемым состоянием x и y равны 0.
 +
 +
* Задача 1
 
<code-c>
 
<code-c>
−
i = 0;
+
x = 1
−
j = 0;
+
a = y
−
k = 0;
+
</code-c>
  
−
while (i < 10 and j < 10)
+
* Задача 2
−
{
+
<code-c>
−
    if (A[i] > B[j])
+
y = 1
−
    {
+
b = x
−
        C[k] = A[i];
+
−
        k = k + 1;
+
−
        i = i + 1;
+
−
    }
+
−
    else
+
−
    {
+
−
        C[k] = B[j];
+
−
        k = k + 1;
+
−
        j = j + 1;
+
−
    }
+
−
}
+
 
</code-c>
 
</code-c>
  
 +
В конце выполнения обеих многопоточных задач значения переменных a и b проверяются.
 +
Какие из следующих утверждений должны быть истинными?
  
−
 
+
;I: a == 0 → b == 1
−
Какие из следующих утверждений могут служить инвариантом цикла для указанного выше цикла while?
+
;II: b == 0 → a == 1
−
 
+
;III: a == 1 → b == 1
−
* I. i < 10 или j < 10
+
−
* II. i < 11 и j < 11
+
−
* III. k = i + j
+
  
 
=== Ответы ===
 
=== Ответы ===
−
* (A) Только I
+
* Только I
−
* (B) I и II
+
* Только II
−
* (C) I и III
+
* Только III
−
* (D) II и III 
+
* Правильный ответ: (D) I и II
−
* Правильный ответ: (E) I, II и III
+
* I, II и III
  
 
=== Объяснение ===
 
=== Объяснение ===
 +
{{cstest-source|2011-gre-cs-practice-book.pdf|38|47}}
  
−
{{cstest-source|2011-gre-cs-practice-book.pdf|37|46}}
+
Разберём каждый случай:
−
 
+
;I.: a == 0 → b == 1
−
Разберём каждое из утверждений
+
* Если a == 0, то задача 1 выполнилась полностью раньше задачи 2.
−
 
+
* Следовательно, b == 1 и это утверждение верно.
−
* I: i < 10 или j < 10
+
;II: b == 0 → a == 1
−
 
+
* Если b == 0, то задача 2 выполнилась полностью раньше задачи 1.
−
Из того, что i<10 и j<10, автоматически следует более слабое утверждение i<10 или j<10.
+
* Следовательно, a == 1 и это утверждение верно.
−
Пока цикл ещё не прерван, утверждение «i<10 или j<10» будет верно всегда. Следовательно, I действительно является инвариантом.
+
;III: a == 1 → b == 1
−
 
+
* В данном случае мы не можем гарантировать, что b == 1.
−
* II: i < 11 и j < 11
+
* Оно может быть равно как 1, так и 0.
−
 
+
−
Внутри цикла мы имеем i <= 9 и j <= 9. Отсюда немедленно следует, что i < 11 и j < 11. Следовательно, II также является инвариантом.
+
−
 
+
−
* III: k = i + j
+
  
−
Перед входом в цикл имеем k = i + j = 0. В то же время либо инкрементируется i, либо j. Таким образом, соотношение сохраняется при переходе между итерациями и утверждение III является инвариантом.
+
{{question-ok|[[Участник:StasFomin|StasFomin]] 10:10, 9 января 2025 (UTC)}}
  
−
{{question-ok|}}
+
[[Категория:Параллельные вычисления]]
−
{{reserve-task|[[Участник:Nikitashapovalov|Nikitashapovalov]] 20:53, 8 января 2025 (UTC)}}
+

Текущая версия на 10:10, 9 января 2025

Вопрос: Q47-08c765

Рассмотрим следующие 2 многопоточные задачи, в которых операции присваивания исполняются атомарно. Изначально, переменные с разделяемым состоянием x и y равны 0.

  • Задача 1
x = 1
a = y
  • Задача 2
y = 1
b = x

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

I
a == 0 → b == 1
II
b == 0 → a == 1
III
a == 1 → b == 1

Ответы

  • Только I
  • Только II
  • Только III
  • Правильный ответ: (D) I и II
  • I, II и III

Объяснение

Исходники — вопрос 47 на 38 странице книги «2011-gre-cs-practice-book.pdf»

Разберём каждый случай:

I.
a == 0 → b == 1
  • Если a == 0, то задача 1 выполнилась полностью раньше задачи 2.
  • Следовательно, b == 1 и это утверждение верно.
II
b == 0 → a == 1
  • Если b == 0, то задача 2 выполнилась полностью раньше задачи 1.
  • Следовательно, a == 1 и это утверждение верно.
III
a == 1 → b == 1
  • В данном случае мы не можем гарантировать, что b == 1.
  • Оно может быть равно как 1, так и 0.
Источник — «https://discopal.ispras.ru/index.php?title=2011-gre-cs-practice-book.pdf/Q47&oldid=35587»