.Q
8. Предположим, есть реализация dequeue в виде двусвязного списка (то
есть есть указатели на предыдущий и следующий элементы). А
возможна ли реализация, где для связи узлов используется только
одно слово вместо двух (то есть мы хотим сэкономить одно слово
размера sizeof(struct node *))?
.A
Полагаю, речь идёт о циклическом буфере или контейнере где есть указатель на начало и указатель на конец, элементы включают указатель только на следующий элемент. Проход односторонний, с конца в начало.
.Q
9. Предположим, что в многопоточной программе в одном потоке
выполняется код
a = 3;
b = 1;
а в другом потоке
if (b == 1)
sum += a;
(оба потока видят одни и те же а и b, блокировок нет). Если
условие выполнится, то на сколько увеличится sum?
Здравствуйте, Alexander Pazdnikov, Вы писали:
AP>Здравствуйте, Коллеги.
AP>Прошу поправить мои ответы на несколько тестовых вопросов.
AP>Спасибо.
AP>.Q AP>1. Является ли язык C строгим подмножеством языка C++?
AP>.A AP>По-моему, нет. AP>По крайней мере, усиленный контроль типов в C++ требует от большинства программ на С доработки.
действующие стандарты С11 и С++11 имеют различные синтаксические конструкции.
могу ошибаться, но уже как минимум начиная с С99/С++98 С не является подмножеством С++
AP>.Q AP>4. Каков размер следующей структуры? Почему?
AP> struct S AP> { AP> int i; AP> void *v; AP> char c; AP> long l; AP> };
AP>.A AP>зависит от разрядности процессора и от принятого выравнивания адресов.
AP>ARM — (sizeof(int) = 4, sizeof(void *) = 4, alignment = 4) — 16 байт AP>x86 (sizeof(int) = 4, sizeof(void *) = 4, alignment = 4) — 16 байт AP>x86_64 (sizeof(int) = 4, sizeof(void *) = 8, alignment = 4) — 20 байт AP>ia64 (sizeof(int) = 8, sizeof(void *) = 8, alignment = 8) — 32 байт
sizeof(S), который не меньше суммы sizeof ее членов. выравнивание не указано, и компилятор может использовать любое выравнивание.
btw, в своем ответе Вы забыли про alignment=1
AP>.Q AP>8. Предположим, есть реализация dequeue в виде двусвязного списка (то AP> есть есть указатели на предыдущий и следующий элементы). А AP> возможна ли реализация, где для связи узлов используется только AP> одно слово вместо двух (то есть мы хотим сэкономить одно слово AP> размера sizeof(struct node *))? AP>.A AP>Полагаю, речь идёт о циклическом буфере или контейнере где есть указатель на начало и указатель на конец, элементы включают указатель только на следующий элемент. Проход односторонний, с конца в начало.
тогда это не double-ended queue, раз мы не можем удалять элементы с конца за О(1)
AP>.Q AP>9. Предположим, что в многопоточной программе в одном потоке AP> выполняется код
AP> a = 3; AP> b = 1;
AP> а в другом потоке
AP> if (b == 1) AP> sum += a;
AP> (оба потока видят одни и те же а и b, блокировок нет). Если AP> условие выполнится, то на сколько увеличится sum?
AP>.A AP>либо на 3, либо на 6.
для начала надо определить исходные значения a и b.
поток #2 может выполниться до потока #1,
либо сначала выполнится b = 1; потом поток #2, потом a = 3;
откуда взялось 6 я не понял, может вы имели ввиду что код выполняется в цикле? так и надо писать %)
Здравствуйте, Abyx, Вы писали:
A>sizeof(S), который не меньше суммы sizeof ее членов. выравнивание не указано, и компилятор может использовать любое выравнивание. A>btw, в своем ответе Вы забыли про alignment=1
спасибо, а на практике это 8-битные процы, аля atmega, z80, i8080?
A>тогда это не double-ended queue, раз мы не можем удалять элементы с конца за О(1)
В концах можем удалять и добавлять элементы за O(1), для этого есть указатели head и tail.
A>откуда взялось 6 я не понял, может вы имели ввиду что код выполняется в цикле? так и надо писать %)
Имел в виду, что при проходе обоих потоков через этот код, sum суммарно увеличится либо на 3, либо на 6. Зависит от переключения контекста в другой поток при выполнении sum += a.
полагаю, что b == 1 и a == 3 в обоих потоках при любом раскладе.
Здравствуйте, Alexander Pazdnikov, Вы писали:
AP>.Q AP>8. Предположим, есть реализация dequeue в виде двусвязного списка (то AP> есть есть указатели на предыдущий и следующий элементы). А AP> возможна ли реализация, где для связи узлов используется только AP> одно слово вместо двух (то есть мы хотим сэкономить одно слово AP> размера sizeof(struct node *))? AP>.A AP>Полагаю, речь идёт о циклическом буфере или контейнере где есть указатель на начало и указатель на конец, элементы включают указатель только на следующий элемент. Проход односторонний, с конца в начало.
Похоже, спрашивается про XOR-связный список.
AP>.Q AP>9. Предположим, что в многопоточной программе в одном потоке AP> выполняется код
AP> a = 3; AP> b = 1;
AP> а в другом потоке
AP> if (b == 1) AP> sum += a;
AP> (оба потока видят одни и те же а и b, блокировок нет). Если AP> условие выполнится, то на сколько увеличится sum?
AP>.A AP>либо на 3, либо на 6.
Здравствуйте, Alexander Pazdnikov, Вы писали:
AP>Здравствуйте, Abyx, Вы писали:
A>>sizeof(S), который не меньше суммы sizeof ее членов. выравнивание не указано, и компилятор может использовать любое выравнивание. A>>btw, в своем ответе Вы забыли про alignment=1 AP>спасибо, а на практике это 8-битные процы, аля atmega, z80, i8080?
на практике это #pragma pack(1) и например передача структур по сети
A>>тогда это не double-ended queue, раз мы не можем удалять элементы с конца за О(1)
AP>В концах можем удалять и добавлять элементы за O(1), для этого есть указатели head и tail.
как удалить с конца если мы не знаем предыдущий элемент?
A>>откуда взялось 6 я не понял, может вы имели ввиду что код выполняется в цикле? так и надо писать %)
AP>Имел в виду, что при проходе обоих потоков через этот код, sum суммарно увеличится либо на 3, либо на 6. Зависит от переключения контекста в другой поток при выполнении sum += a. AP>полагаю, что b == 1 и a == 3 в обоих потоках при любом раскладе.
Вы имеете ввиду такой код?
int sum = 0;
int a, b;
void thread_fn()
{
a = 3;
b = 1;
if (b == 1)
sum += a;
}
int main()
{
thread t1(thread_fn);
thread t2(thread_fn);
t1.join();
t2.join();
return sum;
}
так sum всегда будет 6, в любом потоке перед if a и b будут 3 и 1
Здравствуйте, Abyx, Вы писали:
A>>>sizeof(S), который не меньше суммы sizeof ее членов. выравнивание не указано, и компилятор может использовать любое выравнивание. A>>>btw, в своем ответе Вы забыли про alignment=1 AP>>спасибо, а на практике это 8-битные процы, аля atmega, z80, i8080? A>на практике это #pragma pack(1) и например передача структур по сети
или опции компилятора
A>Вы имеете ввиду такой код? A>
A>int sum = 0;
A>int a, b;
A>void thread_fn()
A>{
A> a = 3;
A> b = 1;
A> if (b == 1)
A> sum += a;
A>}
A>int main()
A>{
A> thread t1(thread_fn);
A> thread t2(thread_fn);
A> t1.join();
A> t2.join();
A> return sum;
A>}
A>
A>так sum всегда будет 6, в любом потоке перед if a и b будут 3 и 1
Даже при выполнении этих ниток на двух разных процессорах?
Здравствуйте, Abyx, Вы писали:
A>>>тогда это не double-ended queue, раз мы не можем удалять элементы с конца за О(1)
AP>>В концах можем удалять и добавлять элементы за O(1), для этого есть указатели head и tail. A>как удалить с конца если мы не знаем предыдущий элемент?
Здравствуйте, Abyx, Вы писали: A>на практике это #pragma pack(1) и например передача структур по сети
Плюс можно добавить, что доступ к данным с адресом, не выровненным по машинному слову, либо менее эффективен (как у x86), либо падает в рантайме (некоторые микроконтроллеры, плюс было ещё что-то из процессоров старой школы наподобие Alpha)
Здравствуйте, Mr.Delphist, Вы писали:
MD>Здравствуйте, Abyx, Вы писали: A>>на практике это #pragma pack(1) и например передача структур по сети
MD>Плюс можно добавить, что доступ к данным с адресом, не выровненным по машинному слову [...] либо падает в рантайме (некоторые микроконтроллеры, плюс было ещё что-то из процессоров старой школы наподобие Alpha)
у arm тоже падает, если используется инструкция требующая выравнивание
Здравствуйте, Alexander Pazdnikov, Вы писали:
AP>то же не могу понять, зачем if и присваивания?
За барьерами. В самом общем случае С++ не гарантирует, что при оптимизации будет сохранено наблюдаемое поведение, если смотреть из другой нити. Например, компилятор может переупорядочить эти присваивания.
Мало того, их может переупорядочить не только оптимизатор компилятора, но и процессор тоже.
В общем то, что из другой нити уже видно, что b == 1 не гарантирует, что из неё же уже видно, что а == 3...
Все эмоциональные формулировки не соотвествуют действительному положению вещей и приведены мной исключительно "ради красного словца". За корректными формулировками и неискажённым изложением идей, следует обращаться к их автором или воспользоваться поиском
