А билеты вообще есть как таковые?

Да, это очень волнующий вопрос!

Билетов нет, есть задачи. На экзамене вытягиваешь 2 задачи, решаешь их, а потом объясняешь. Условия задач выложены в интернете, но как их решать там не написано.

Где-нибудь есть решение этих задач????

http://www.cmc-msu.ru/files/8/8-raspr-os-answers.rar
Тут есть решения, но говорят что из них больше половины неправильные.
Там местами вообще такая чушь написана...

Лично моё резюме: там есть часть правильных решений, часть неправильных. Просто те, который решены неправильно замаскированы под правильно решённые, поэтому их очень тяжело найти... Но там есть неправильно решённые задачи, та же 2.3 например.

Идея правильная но эти задачи можно решать по-разному:2-1,2-4.
Непойму:2-2
Неверно:2-3,3-1 - 3-4

Решу сам, обязательно напишу...

2Castor
Если такой умный, то объясни пожалуйста дураку, какой смысл в семафорах несут операции P(access), P(wait), V(access), V(wait), или что тоже самое P(empty), P(full), V(empty), V(full). Никак не могу понять что это значит...

Не надо нервничать, расскажу в меру моего понимания:
P(access),V(access) - захват семафора, отвечающего за целостность выполнения функций (в начале функции захватывается, в конце освобождается). Как видишь, он везде стоит - вот чтобы выполнения функций не накладывались, функция сама - КС.
P(wait),V(wait) - собственно блокировка процессов, в случае когда их нужно блокировать (считающий семафор s=0)
P(full),P(empty) - бредовая реализация, но на мой взгляд, это просто характеризует пустая очередь или она полная. Надо не забывать, что семафор, как пишет Крюков, это всего лишь целочисленная неотрицательная переменная, управляемая двумя функциями пэ и вы. Так что это просто говорит, в этот момент очередь пуста а в этот полная...

да кстати, а почему "что тоже самое" совсем разные семафоры из совсем разных мест в лекциях...

а почему 2-3 неверно? По-моему, все логично.

2-3 неверно потому, что во-первых там не L1, а L1-2 (заметь время последовательного вычисления (L1-2)(L2-2) ). Каждое вхождение L2 тоже должно быть в форме L2-2.
У меня вообще ответ такой, он тоже логичный, но его то я хоть могу обосновать:
((L1-2)divN)(N+L2-2)+((L1-2)modN==0?0:(L1-2)modN+L2-2)
оно верно для всех возможных случаев

как ы вообще понимаете как эта релаксация работает - ума не приложу

То, что в задаче 3-1 получается не 8*(Тс+Тв*Т) а 6 я поняла.
Но как тоже самое получить в задачах 3-2 и 3-3?? В лекциях так сказано. А что еще значит фраза: "если все процессы выдали ее одновременно"? Кого ее? И куда выдали???

а почему собственно 6(Тс + N * Nb)???
мне почему-то кажется что 6*Tc + (N+5) * Тb. В самом деле - чтобы передать из левого нижнего в правый верхний нужно раскачать 6 узлов , когда правый верхний получает первый байт сообщения, левый нижний выдает шестой байт сообщения. И этому шестому нужно еще пять перегонов пройти.

Это ты про какую задачу?

Тут возник вопрос - а передча только полными сообщениями идет? :) или по байтам? Т.е. передача строки длины L это неделимая операция длиной Ts+N*Tb или получив первый байт сообщения можно уже дальше передавать?

про 3.1

По моему либо ты либо я не понимаем как работает эта матрица. Я считаю по итерациям. Для того, чтобы разослать бродкаст от (0.0) всем, необходимо 6 итераций. В рассылке участвуют все (по лекциям). На первой итерации (0.0) передает сообщение (0.1). Это 1-я итерация и занимает она времени 100+N. 2-я итерация: здесь уже сообщение отсылают одновременно (0.0) и (0.1) так как оба обладают этой информацией. Это еще 100 + N. Для того чтобы все получили сообщение нужно еще 4 итерации. Т.е. еще 400 + 4*N.

Ходили бы на консультацию - лектор сказал седня, что операции посылки и приема неделимы. То есть если мы посылаем 100байт, то приемник не может получив пару байт начать их дальнейшую передачу

Если это не так, то как работает broadcast?

И вообще, чего вы паритесь? Там важен лишь порядок так как Ts >> Tb
Скажете 6Ts - это и будет ответ, какая разница есть ли там мизернео слагаемое 6Tb или 21Tb?

Просто работает: мы передаем соседям столько то байт, они их передают дальше итп

По лекциям - неделимая.

Дело в том что в первой задаче мы передаем N байт. И если сообщение большое, то имеет значение 6 или 21 N.

это и не важно, там 6(Ts+N*Tb)
Что совершенно очевидно

И потом - про задачи 3.2 и 3.3. - в лекциях написано точное время в ответе - 6*(Ts + Tb). Это же не спроста. И мне не понятно как можно получить это выполняя операцию рассылки или сбора информации.

А что значит фраза "если все процессы выдали ее одновременно"?

Ну про задачу 3.1 мне вроде бы все понятно. Мне не понятны 3.2 и 3.3. Как там получить 6(Ts+Tb)?

Очень просто - мы начинаем собирать по байту (или посылать) с каждого. Очевидно, что искомое время будет равно времени, затраченному самым отдаленным байтом. Потому что остальные все равно успеют дойти за это время.

Нет. Не очевидно. По крайней мере мне.
Предположим для определенности что мы рассылаем байты. Нам нужно отправить 15 байт. Каждому процессу - свой байт. Если бы рассылали один и тот же байт - было бы очевидно. А так - первый процесс должен все 15 байт отправить. И как это уложить именно в 6Ts мне не понятно.

На первой итерации, скажем, он посылает по одному выходу 8, по другому 7 байт, далее они распределяются схожим образом. В любом случае, самый дальний байт на каждом шаге будет прилижаться к цели и дойдет последним

Я так тоже пробовала посчитать. Ровно 6 у меня не получается.

Там и не должно быть ровно, может будет другой коэффициент перед Tb, но я их никогда не считаю. Для меня главное - порядок, то есть Ts

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

Блин, меня смущает то, что в 3-х вариантах лекций у лектора сказано что получается РОВНО такое число. И для меня совершенно не важно, важно ли это для тебя. Для меня важно, важно ли это для принимающих экзамен? В том числе для лектора.

И что все таки значит фраза "если все процессоры выдали ее одновременно"?

Информацию они выдали скорее всего, или команды рассылки либо сбора

А так париться из-за того, что там важно для лектора на 4ом курсе, имхо - кошмар. Мы уже достаточно взрослые для этого =)))

Бред какой-то... какую информацию они могли выдать одновременно при бродкасте?

А при бродкасте это просто так осталось. Copy, paste, знаешь ли

ну может быть ты себе хорошо представляешь как работает эта матрица, а я не очень. Поэтому мне многие вопросы принципиальными кажутся. И еще - я вообще себе плохо представляю как со 100% точностью можно сказать время в задачах 3.2 и 3.3 если мы не знаем точного алгоритма рассылки, а только его предполагаем.

Как у тебя все просто :)

Сразу видно, что ты не была на консультации. Объясняю ВСЕМ и популярно: еще до консультации я понял, что бессмысленно решать эти задачи или смотреть чужие решения по одной очень простой причине. Правильных ответов НЕТ. Есть куча разных решений и соотвтественно ответов. Главная задача - мотивировать свою точку зрения, доказать на экзамене ее логичность и состоятельность, что можно так, а можно и так.
И лекто сегодня это подтвердил, сказав: ваша задача найти ОДНО ИЗ решений, не занимайтесь поиском оптимального, просто скажиет какие есть методы оптимизации (конвейер, разделение итп)

А еще такой вопрос, может ли одновременно процесс получать информации и в это же время отправлять? (отправлять другую информацию, а не ту, что получает).

может, конечно. Прием у нас мгновенный

Некто рулит. Подпишусь под каждым словом поста 20:50. Задачи - это просто повод поболтать на тему.

Круто. Время передаче ох... а прием мгновеный?
Ну ладно, это немного проясняет ситуацию.

2=Е
Точно, они совершенно бредовые с той точки зрения, что надо сидеть и высчитывать сколько там времени занимает пересылочка байтиков. Асперам на это насрать с высокой колокольни. Главное понимать как оно работает

Ну в том что задачи - только повод поболтать на тему, это и так ясно.

2Александра
Ну а нахрена тогда весь этот флуд?!
Посмотри лучше задачки на тему 6, чтобы у тебя сразу желание отпало про них ваще думать. Там даже приблизительного решения сложно придумать.

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

2=Е
Я как раз про это написал =)
Хотелось бы все-таки понять что там пересылается =)))

Ну и что ты предлагаешь? На все забить и лечь спать? Вообще ничего не ботать? Если ты такой умный и готов все эти задачи решать и беседовать на экзамене на все темы, я тогда не очень понимаю что ты вообще делаешь в этой теме и нафига весь этот флуд читаешь.

Слушайте, давайте флудить про РОСы в более удобном форуме? Скажем http://www.forum.b.gz.ru/

2Александра
Есть кое-какие непонятные моменты. Скажем, как работает алгортм неделимый широковещательный, или реализиация post, wait через семафоры

Упс! Просто http://forum.b.gz.ru/

Ну для тебя это непонятные моменты, а для меня другие. Хотя впрочем и эти тоже.

Сначала мне тоже было непонятно, потом я часок провозился с задачкой одной, придумал для себя удобную модель, попадающую под эмпирические наблюдения( читай ответы) и ей полностью удовлетворился =) Как в физике - ничег не знаем, что-то придумываем, чтобы с миром не конфликтовало и юзаем :)

Мля, опять придется подписаться под постом некто 21:02.
На счет консистентностей - думаю матрицы тут ваще не причем. Ключевое слово шина, далее RTFM.

2=Е
А я тебя не знаю?

2Некто
хз, причем взаимно.

А что из себя представляют модели консистентности PRAM и Процессорная?

Адинец? LOL =)

PRAM: все операции одного процессора выполняются в порядке записи, остальные параллельно.
Процессорная: ПРАМ + когерентность памяти (что это такое никто не знает, но это никму и не нужно)

Я ща застрелюсь, меня приняли за адинца...
Кстати не факт, что это никому не нужно. Такой дополнительный вопрос (чем отличается процессорная и прам консистентности ПО СУТИ?!) вполне реально получить от какого-нибудь злобного аспера. И когерентностью памяти тут не отмажешься.

Ну, про Адинца это так, по приколу...
А про отличие процессорной от ПРАМ даже в Таненбауме нет, откуда это все взято. Крюков сам придумал процессорную, потому что она то же самое, что ПРАМ у Таненбаума

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

Разве же не бред?

И еще объясните мне в чем глубинный смысл параграфа: реализация DSM через разделяемые переменные

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

Короче мля, харэ тут разводить треп по стремным темам, а то у асперов будет богатая почва для имения.

Если бы я был аспером, я бы просто распечатал все непонятки из этой ветки и глумился бы потом на экзаме, гы.

Если бы ты был ботанским аспером, а нормальные асперы щас пеффко пьют

Если бы я был ботанским аспером, я бы все заботал. А так я распечатал бы ветку и пошел бы пить пеффко.

:))) теперь моя очередь подписываться под постом 21:57 :)

так ты бы был злобным аспером! А они должны быть добрыми

Ну чего, ребята? Рассказывайте, как сегодня прошёл экзамен!?!?

Итак, рассказываю.
Крюков - #%(&*$&*%@
Если вас взял то пишите пропало сразу.
Взял парочку человек, включая Адинца. Последнему, естественно отл, остальным не очень хорошо. На просьбы не портить зачетку пошел навстречу - не ставил в ведомость, а просто велел прийти со следующей группой.
Асперы - халява все поголовно, в том плане, что понимания вполне достаточно. Прогоняют по всему курсу, дают дополнительные задачи.
Ставят 3 очень редко. При мне поставили чуваку, который не знал, что такое алгоритмы выбора координатора

ЗЫ: у меня отл

Маза в том, чтобы вызываться сразу асперам, как только Крюков кого-нибудь взял. Пусть и не полностью подготовленным, это не важно...

А по курсу гоняют по определениям и алгоритмам? И доп. задачи идут из билетов?

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

Гм... А много народу Крюков взял? Или не очень? Асперы, значит, берут если попросишься...?

Да кстати, а как относятся к тому, что не решил задачку (не до конца, какие-то ошибки или недоработки)? Например, слабая консистентность - хрен знает как её реализовать. Реализуешь по-своему - один ответ, по-другому - другой. Как там с этим дела?

>> А много народу Крюков взял? Или не очень?
Сколько и все. По желанию только Адинец был.
>> Асперы, значит, берут если попросишься?
После того как начинают брать по спику, шанс напроситься к асперам падает, но я все равно сумел.
>> Да кстати, а как относятся к тому, что не решил задачку
Одну задачку я решил неверно, он дал мне время переделать, мы с ним обсудили возможные пути решения и согласились, что так будет лучше )

А тама берут по списку или по желанию?
По желанию можно пойти отвечать?

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

И так и так.

Некоторые берут тех, кто хочет, а некоторые только по зачеткам. А некоторых Крюков вытягивает и отдает асперам:)

Люди, а в 3.2 же получается 8*(Ts+Tb), тк в (0.0) за раз можно прислать только 2 байта

Нет! 6*(Ts+Tb) т.к. в первый ход мы из угловой вершины отсылаем сразу большую часть сообщения (не по одному и не по двум байтам за такт, а больше) По этому нам не нужно делать еще две лишни подготовки к посылке, которые дают число 8Ts вместо шести. (с) http://waves.h12.ru/

Но если не один байт за такт, то у Тb появляется множитель?

Народ! Может кто-нить предложить нормальное решение этой задачи и его объяснить? А то в решениях бред какой-то...

Имеется команда TSL и команда объявления прерывания указанному процессору. Опираясь на них, реализуйте на мультипроцессоре P-операцию и V-операцию для двоичного семафора. Активное ожидание освобождения семафора не допускается.

Решение там абсолютно правильное этой задачи :)

Надо просто начать писать самому и через 3 минуты всё станет ясно.

В паре мест там можно подругому, но решение верное.

Да я в него врубиться просто не могу

2Light
Нет, ничего не появляется, т.к. время 606 покрывает собой все времена доставки осталных сообщений. К сожалению форум не поддерживает вставку картинок, так что я тут нарисовал решение в том виде, в котором виу его я и положил сюда:
http://waves.h12.ru/study/ros_ideas3_3.html
Может там конечно идея и неверна, но помоему так получается.

Я поддерживаю рисунок Валентино, очень красиво... Только непонятно почему именно по одному каналу в начале шлётся 1 а по другому 14, почему не 7 и 8... Я бы лично для симметрии послал 7 и 8... ;-)

Valentin, мне кажется Вы что-то путаете

Попробуйте решить задачу: за какое время можно передать 15 байт по двум каналам, если по одному каналу одновременно может проходить один байт?

если расскажете, как это сделать за 6Tb, буду благодарна

Согласна, что можно сэкономить на стартах, если есть возможность соединять сообщения!!!!!!
но 8Tb, на мой взгляд, нельзя сократить

Имхо, рисунок лажа... Из того что говорил Лектор на консультации можно сделать вывод что шлется с самого начала по одному байту... Т.е. на первом шаге 1 байт вправо и один вниз - это 101, затем, из (0,0) продолжают слаться байты пока они там есть, а все остальные в то же время пихают полученное дальше. Таким образом когда правый нижний получит первый посланный байт (пройдет 606) все уже всё получат...

Да, рисунок имеет моло отношения к решаемой задаче
хотя в задаче 3.3 ответ 606

могу поделиться своими ответами
3.1 Считаем, что длина сообщеия меньше времени старта, поэтому, когда второй сможет начать передачу, то он уже получит от первого все сообщение надо шесть времен старта, пять передач по одному байту, одна передача N/2 байт (к (3,3) можно передавать сообщение по двум каналам)

3.2 выше обсуждались причины, по которым ответ 6Ts+8Tb или 8(Ts+Tb)

3.3 6(Ts+Tb)
Схема:
_ _ _
|_ _ _
|_ _ _
|_ _ _

а че такое адинец? фамилия?

3.4 4*4: 6(Ts+NTb) N-длина числа в байтах
8*8: 14(Ts+NTb)

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

если режим без буферизации, то надо еще передать пять байт и L/2 байт

с буферизацией: 3LTb если просто разбить сообщение на две части и посылать по двум параллельным каналам
(13/7)LTb если максимально использовать параллелизм
(делее: к чему мы пришли, обсуждая с аспером на экзамене решение задачи)
Последовал вопрос: можно ли улучшить эту оценку? оценку можно улучшить, если использовать конвейер, но есть нижний предел, обусловленный числом стартов (попросили вывести формулу в общем виде)

3.6 а или б не влияет на решение здачи , далее аналогично 3.5

да, Адинец - это фамилия
http://ru.thespoke.net/MyBlog/adinetz/MyBlog.aspx

4.1 вторая по красоте задача
дерево:
______________0______________
_________1/________8________
_______2/__5____9/____12____
______3/4_6/7_10/11_13/14__
_________________________15_

посылаем 15 сообщений с запросом на вход в критическую секцию: 15(Ts+TbLq)
получается 11 пересылок маркера с запросом:
11(Ts+Tb(Lm+Lq))
и 15 пересылок маркера без запроса:
15(Ts+TbLm)

упс, дерево получилось не правильное 15 должно выходить из 14

> за какое время можно передать 15 байт по двум каналам, если по одному каналу одновременно может проходить один байт?
По двум каналам можно передать 15 байт за Ts+8Tb, ведь так? Если так, то не вижу причин по которым в моем варианте за 606 не проидут все до места назначения. Рисунки могут быть разными, суть не изменится.

А в твоем решении:
3.3 6(Ts+Tb)
Схема:
_ _ _
|_ _ _
|_ _ _
|_ _ _
по сколько байт за одну сессию посылает процесс (0,0)?

4.6 32Ts+16LsTb+16LkTb Ls- длина пересылаемого списка, Lk - длина сообщение с номером координатора

еще совет: на parallel.ru в курсе Крюкова задач немного больше, чем на сайте кафедры СП

Задача для интересующихся

P1 W(x)1________S__R(x)?_R(y)?
p2 W(y)2_W(x)2______S____R(x)?_R(y)?
P3 W(y)1____________S____R(x)?_R(y)?

Что на месте знаков вопросов в случае слабой консистентности?

Valentin,
:(
по твое картинке получается шесть времен старта в любом случае
В задаче 3.3 мы должны всем передать один и тотже байт эта задача разбиралась на лекции ответ 606

из моей переписки с лектором:

1. Передача по шине: пусть некоторый процесс хочет передать по шине несколько сообщений подряд. Сколько раз надо стартовать (достаточно ли одного времени старта)?
*******************************
Каждое сообщение отрабатывается самостоятельно, захват шины происходит на апаратном уровне при посылке сообщения - время старта входит во время передачи каждого сообщения

2. Передача в транспьютерной матрице: пусть есть три процессора: 1__2__3 . Нам надо передать первому по 1 байту от второго и от третьего, второй и третий стартуют одновременно: второй передает байт первому, третий – второму. Можно ли передать от второго первому байт, пришедший от третьего, дополнительно не стартуя?
******************************
Аналогично, каждая посылка требует старта

2Liya. Ответ очевидно зависит от порядка в котором были произведены записи в переменные. Однозначного ответа нет. Переберать возможные в лом =)

Да, 6 времен старта и 6 передач на самый дольний путь, и все=606, я что, спорю?

2Liya: у тя в натуре какие-то кривые ответы получаются. При чем по кривости они подозрительно похожи на кривые решения в доке.
Например, в задаче 3.4 - откуда такие цифры? Я считал, что смысл этой задачи в том, чтобы сначала собрать 16 чисел в одном транспьютере, а потом разослать максимум обратно.
Очевидно оптимально собирать все числа например вот тут, а не в углу:
0 0 0 0
0 х 0 0
0 0 0 0
0 0 0 0
Тогда такие ответы как у тебя не получатся.

лектор дал более конкретный ответ:
> Какие значения будут на месте знаков вопрса в следующем примере?
> P1 W(x)1________S__R(x)2_R(y)1 [если синхронизация p2 сработала раньше,
чем синхронизация p3] или 2
> p2 W(y)2_W(x)2______S____R(x)1_R(y)1 [если синхронизация p2 сработала
раньше, чем синхронизация p3] или 2
> P3 W(y)1____________S____R(x)1_R(y) 2[если синхронизация p2 сработала
раньше, чем синхронизация p3] или 1

до меня долго доходило, почему так

По 4.1 - ваще ересь. При чем тут дерево?! У нас топология СПД - шина!! Т.е. мы можем сразу посылать нужные данные напрямую, без промежуточных звеньев. Иначе это не шина, а какой-то бред. В конце концов на хрена мы тогда ботали курс Сетей, если нам говорят, что чтобы передать от одного участника на шине к другому, нужно для этого передать сообщение еще 10 промежуточным участникам.

=Е,
у этой задачки в моем рейтинге третье место
смысл в том, что для определения максимума не надо собирать все числа в одном месте свое решение если интересно напишу завтра с утра а то мне в 6 30 на работу вставать удачи

Ребята, спасибо вам за переписку. Пока читал 2 типа задач понял. Вы, главное, не останавливайтесь!

2Liya. Лектор не адекватен. Считаю бессмысленным обсуждать его ответы, мы все видели как он хорошо объясняет на консультации.
А по поводу слабой консистенции, копи паст твоего скана из Таненбаума:
"В ходе синхронизации ВСЕ локальные записи процесса Р распространяются на остальные копии, а ВСЕ операции записи других процессов – на копию данных процесса Р."
Как я понимаю, в это задаче не важно чья синхронизация произошла раньше, т.к. все равно все будет решать последовательность записи значений в переменные x и y разными процессами. В любом случае при каждой синхронизации ВСЕ процессоры становятся согласованными. По крайней мере так я понял тезис таненбаума.

00:27
Хе-хе
там сказано используя некоторый алгорим
очевидно , что такая шина не самое оптимальное железо для его реализации все до утра

Ну вот, наша очаровательная брюнетка сботвила спать =( Придется последовать ее примеру...

нет со слабой консистентностью све немножко хитрее

2Liya: "Уходя уходи" =Р
"используя некоторый алгорим" - и что? Какой смысл тогда писать, что топология - шина, если мы не используем ее специфику?
"нет со слабой консистентностью све немножко хитрее" - надо будет ответить так асперу.

3.4 решена как в доке так и у Liya правильно, я ее сегодня сдавал, там вся фишка что на четвертом такте, за счет пересылки во внутреннем квадрате информации в обе стороны, сразу на 4х процах формируется максимум, а потом еще за 2 такта он отсылается назад. итого получаем ответ. Задачу можно решить графически несколькими способами и получить такой же ответ как сmc-msu

В слабой консистентности главное не забыть для чего нужны синхропеременные, мы сегодня(вчера уже:)) на эту тему с аспером долго базарили...

2Valentin&Liya: По 3.4 - круто, да. Пошел делать upgrade мозгам.

Слышь ты, слышь ты! 4.1 - ответы конечно хорошие, но в моей интерпретации неверные. Дело в том, что сообщение ЗАПРОС передаётся между процессами в топологии дерево, как и сообщение МАРКЕР. В этом и заключается древовидный маркерный алгоритм. Было бы странно, если бы сообщения ЗАПРОС и МАРКЕР летали бы напрямую, тогда зачем дерево, зачем указатели на направление, где находится МАРКЕР и почему очередь у каждого процесса только для четырёх процессов (3-х соседей и себя самого). Так что ответ брюнетки я считаю не верным...
p.s. Валентин, я с тобой, у тебя всё правильно...

00:51
Полностью согласен.

начну с задачи 4.1
в задаче важно понять что в один момет по шине может проходить только одно сообщение и вход выход и работа в критеческой секции происходит мгновенно по условию задачи очередь запросов будет формироваться следующим образом: 15 запросов соседям т.к. мы в начальный момент знаем напрвление маркера
следующим запросом в очереди уже будет запрос на передачу маркера от 0 к 1 передаем маркер и запрос на маркер от 0 к 1 пока будет передаваться запрос уже будет сформировано собщение передачи меркера от 1 к 2 и т.д. Я и Валентина Глазкова считаем данный ответ правильным

2Liya: Ты сама себе противоречишь:
"в один момет по шине может проходить только одно сообщение".
А потом ты пишешь:
"передаем маркер и запрос на маркер от 0 к 1 пока будет передаваться запрос уже будет сформировано собщение передачи меркера от 1 к 2 и т.д."
Объясни плз по нормальному последовательность сообщений хотя бы для 3х первых процов.

2Castor: У меня встречный вопрос - а зачем тогда топология шина? Я согласен, что в предложенном мной варианте дерево не имеет никакого смысла, когда сообщения посылаются напрямую. Но если они посылаются не на прямую, то получается ЗАПРЕДЕЛЬНО неэффективный алгоритм.
В таком случае последовательность действий будет примерно такая:
1. Все 15 процессов ПО ОЧЕДЕЛИ посылают запрос своим соседям в направлении процесса 0.
2. У процесса 0 оказывается 2 запроса в очедели - от процесса 1 и от процесса 2 (пусть в корне процесс 0, в первом ярусе процессы 1 и 2, и т.д.).
3. Процесс 0 посылает СНАЧАЛА сообщение с маркером процессу 1.

4. Затем процесс 0 посылает сообщение с запросом опять же процессу 1 (кто ваще сказал, что сообщения можно объединять?! Если действовать строго по алгоритму, то там ясно написано, что сначала процесс отсылает маркер, а потом думает че делать дальше).
5. После этого опять происходит форвардинг запросов от остальных процессов в сторону процесса 1. Опять же ПО ОЧЕРЕДИ, т.к. доступ последовательный.
И т.д. посторяются эти шаги. При этом происходит обход дерева слева направо (т.е. сначала доходим до самого левого листа, поднимаемся выше, доходим до второго слева листа и т.д.). При этом получаются ЖУТКИЕ накладные расходы, т.к. все происходит по очедери. Я щас конечно посчитаю, но думаю там будет идти счет на сотни сообщений, а никак не на такие скромные числа как в ответе.

согласна до 5 шага
5. никакого форвардинга не происходит для один направление маркера изменилось

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

Про нахрждение максимума еще актуально?

Liya, про максимум проехали, thx.
Не понимаю, почему не происходит форвардинга запросов. Запросы должны в конечном итоге оказаться у владельца маркера, иначе он не будет знать куда дальше его посылать (у него в очереди должы быть запросы).
Копи-паст из алгоритма:
А) Пришло сообщение «МАРКЕР»
М1. Взять 1-ый запрос из очереди и послать маркер его автору (концептуально, возможно себе);
М2. Поменять значение указателя в сторону маркера;
М3. Исключить запрос из очереди;
М4. Если в очереди остались запросы, то послать сообщение «ЗАПРОС» в сторону маркера.
Б) Пришло сообщение «ЗАПРОС».
1. Поместить запрос в очередь
2. Если нет маркера, то послать сообщение «ЗАПРОС» в сторону маркера, иначе (если есть маркер) - перейти на пункт М1.

Т.к. процессы получают доступ к шине последовательно, то каждый процесс, получив запрос, и если у него нет маркера, должен отправить его далее по направлению к маркеру. Отсюда и форвардинг.

=E 00:21,
ты не прав, смысл в том, что на каждом процессоре своя копия данных и нет единых часов
если мы будем знать последовапельность в которой были проведены записи в каждую переменную то получим последовательную консистентность а не слабую

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

Народ, если не влом: может быть обсудим задачки 6-3 - 6-7, давайте обсудим теоретические реализации этих алгоритмов с полным размножением... Какие там предложения. Особенно интересует 6-4,6-5.

2Liya: Я не сказал, что мы ЗНАЕМ эту последовательность записи. Конечно же, мы ее НЕ знаем, иначе, как ты правильно заметила, это была бы последовательная консистентность. Именно поэтому мы не можем дать однозначного ответ, так как мы НЕ знаем этой последовательности записей. Единственный момент, относительно которого мы можем сказать хоть что-то – это синхронизация, которая происходит во всех процессорах одновременно. То, что было до нее – совершенно не понятно в каком порядке происходило.
Ты сказала, что в слабой консистенции есть какая-то хитрость. Поясни плз.

2Castor: Фсе, я ни хрена не прав. В 4.1 форвардинга действительно нет, я не правильно понял алгоритм. У меня получилось 27 маркерных сообщений и 12 запросов (не считая изначальных 15).

2Liya: Не понятно как в 3.2 ты умудрилась уместить все в 8*Tb. Понятно, что будет 6*Ts, но я так и не смог получить 8*Tb. У меня получается минимум 9*Tb. Ты уверена в ответе, или ты опять не расписывала каждый ход, а сделала прикидку?

Мля, лектор подстроил аварию на электростанции, чтобы мы не успели разрюхать все задачи, вот отстой =((

2Castor:
А 6.4 -то чего? Там все довольно просто.

Я так и знал, я тут уже 4 часа зайти сюда не могу. Не, в 4.1 у тя не получится 12 и 27 и 15. Завтра встретимся, ты мне раскажешь как ты умудрился так получить... ;-)

2Castor: 6.3-6.7 обсуждать без мазы, потому что каждый придумывает свой алгоритм или понимает алгоритм из дока в меру собственной тупости. Если у тебя есть папские реализации алгоритмов - предлагай.

По поводу 4.1 - завтра не встретимся, поэтому выкладываю свое решение (расписал каждый шаг на листочке, без всяких обобщений и догадок):
Сначала происходит посылка запросов всеми процессами в сторону процесса 0: 15*(Ts+R*Tb)
После этого последовательность сообщений такова:
0–MR–1–MR–3–MR–7–MR–15–M–7–M–3–MR–8–M–3 –M–1–MR–4–MR–9–M–4–MR–10–M–4–M–1–M–0–M–2–MR –5–MR–11–M–5–MR–12–M–5–M–2–M–6–MR–13–M–6–M–14
MR – значит посылаем 2 сообщения, сначала маркер, а потом запрос.
Всего в этой цепочке сообщений с маркером 27, т.е.: 27*(Ts+M*Tb)
Всего в этой цепочке сообщений с запросом 12, т.е.: 12*(Ts+R*Tb)
В итоге: (15+12)*(Ts+R*Tb) + 27*(Ts+M*Tb) = 54*Ts + (27R+27M)*Tb

А теперь пусть многоуважаемая Liya или ты покажешь где в этой последовательности косяк и почему.

Вид дерева (для определенности):
0
/
1 2
/ /
3 4 5 6
...
и т.д.
Последняя висюлька под номером 15 - самая крайняя левая.

Слышь ты! Слышь ты! Косяк??? А почему ты считаешь, что посылка запроса в сторону процесса 0? Через некоторое время маркер уйдёт в процесс 1, и потом дальше. Считай ещё время будет тратится на доставку сообщения ЗАПРОС к процессу, содержащему МАРКЕР, а он будет далеко не 0. Что на это скажешь, Ява?

Сначала передача ЗАПРОСА будет так: 1-0 3-1 4-1 5-2 6-2, а не сразу все взяли и за 15(Ts+ATb) передали, это так только в сказке бывает...

Мда. Нет слов, RTFM. Liya, спасай положение, на тебя вся надежда!
Когда мы оправляем первые 15 запросов, то нам больше не надо никуда перенаправлять запросы. Я тоже думал, что нужно форвардить запросы в сторону процесса с маркером, но оказалось, что не нужно. Нарисуй себе на листочке дерево и действуй по алгоритму. А если хочешь сказать что-ньть умное - говори КОНКРЕТНО, что "в цепочке не верно 3е сообщение МR, потому что...".

2Castor: Сникерсни мля.
Я и говорю что не сразу все передали. Если бы сразу все, то было бы (Ts+R*Tb).
А так это будет в последовательности номеров машин за 15 шагов:
1-0, 2-0, 3-1, 4-1, 5-2, 6-2 и т.д.

ХАМЛО!!!! Так бы сразу... Ну тогда согласен, убедил... А как я тебя хотел запутать, а... ;-)

Да меня теперь хрен запутаешь, я сам кого хочешь запутаю =Е

Ты вообще конечно очень хитрый... Но по алгоритму вроде как ещё будут сообщения: смотри

Б) Пришло сообщение «ЗАПРОС».
1. Поместить запрос в очередь
2. Если нет маркера, то послать сообщение «ЗАПРОС» в сторону маркера, иначе (если есть маркер) - перейти на пункт М1.

Т.е. вначале 15(Ts+ATb) все посылают ЗАРОСЫ - всё, что с маркером - согласен, а вот дальше эти запросы идут по пункту 2 - ПОСЛАТЬ СООБЩЕНИЕ "ЗАПРОС" В СТОРОНУ МАРКЕРА... ВОПРОСЫ ЕСТЬ!?!?

Тебя? Запутать? Да поссать ночью и то проще... Расскажи мне про отношение лектора к студентам 4-го курса с точки зрения банальной эрудиции и общечеловеческой позиции? Если правильно ответишь, то возьму слова обратно... ;-)

2Castor: Про "поссать ночью" тебе определенно видней.
По сути: "дальше" запросы никуда не идут. Пример: когда процесс 2 в самом начале отправил запрос процессу 0, ему затем пришли еще 2 запрос (от процессов 5 и 6). Какой смысл ему еще раз отправлять запрос в сторону, если он уже и так один отправил и рано или поздно к нему вернется очередь? Имхо он ничего не будет отправлять, а будет в тихую складировать эти запросы себе в очередь. Т.е. в итоге процесс 2 отправил запрос в сторону процесса 0, а у себя в очереди стало [2,5,6], т.е. когда к нему попадет маркер, он сначала выполнит КС, затем переправит маркер процессу 5 (и отправит туда же запрос), после того как к нему вернется маркер от процесса 5, он отправит его процессу 6, его очередь на этом опустеет и фсе закончицца. Доходчиво?
Если ты хочешь сказать, что КАЖДЫЙ раз будет снова посылаться запрос, то сам решай в таком бредовом раскладе задачу - это не логично (более того, бессмысленно) и с диким оверхедом.

2Castor: Про "поссать ночью" тебе определенно видней.

По сути: "дальше" запросы никуда не идут. Пример: когда процесс 2 в самом начале отправил запрос процессу 0, ему затем пришли еще 2 запроса (от процессов 5 и 6). Какой смысл ему еще раз отправлять запрос в сторону процесса 0, если он уже и так один отправил и рано или поздно к нему вернется маркер? Имхо он ничего не будет отправлять, а будет втихую складировать эти запросы себе в очередь. Т.е. в итоге процесс 2 отправил запрос в сторону процесса 0, а у себя в очереди стало [2,5,6], т.е. когда к нему попадет маркер, он сначала выполнит КС, затем переправит маркер процессу 5 (и отправит туда же запрос), после того как к нему вернется маркер от процесса 5, он отправит его процессу 6, его очередь на этом опустеет и фсе закончицца. Доходчиво?
Если ты хочешь сказать, что КАЖДЫЙ раз будет снова посылаться запрос, то сам решай в таком бредовом раскладе задачу - это не логично (более того, бессмысленно) и с диким оверхедом запросов.

А как там на экзамене с двойками? И какого хрена в 2.3 в структуре событие хранятся номера ожидающих процессов?

Слушай, на счёт "поссать" - понял, а на счёт задачки - нет. Я хотел сказать не это, я хотел сказать, что запрос должен добраться до процесса с маркером, это написано во ВСЕХ лекциях, зачем спорить? Много раз один и тот же процесс ничего не посылает - это факт, но процесс (как тут написано "форвадиться") к процессу с маркером.

Слушай твоё решение мне очень нравиться, но если мне за него поставят неуд, то я лично тебя на "Крючок" повешу... ;-)

народ, расскажите о алгоритме задиры.
например, ситуация такова: 7-й процесс начинает выборы. он шлет сообщения о выборах процессам 8, 9 и до 15. у 8-ки номер больше, она продолжает выборы. и рассылает сообщения 9-ке и т.д. а как же 7-ка? ей никто ничего не присылает, поэтому она считает себя координатором. - это то, насколько я понимаю алгоритм.
поясните, как это должно работать?

2Castor: Запрос в любом случае доберется до процесса с маркером, иначе процесс с маркером не будет знать куда его послать. В моем решении все знают куда че слать. Все работает, мля, че еще надо-то?! Если мне за это решение поставят неуд, я лектора повешу на крючок, благо фамилия соответствует =Е

2Lasso или как там: Фсе не так.
7й процесс начинает выборы и шлет сообщения процессам 8, 9 и 15.
После этого процессы 8, 9 и 15 его заваливают сообщениями "Мля, да ты ох@#л?!", после чего процесс номер 7 идет курить.
Дальше процессы 8,9 и 15 начинают спамить друг друга аналогичным образом, пока 15й всех не зарулит.

В любой момент процесс может получить сообщение «ВЫБОРЫ» от одного из коллег с меньшим номером. В этом случае он посылает ответ «OK», чтобы сообщить, что он жив и берет проведение выборов на себя.

Shika, ты тоже сникерсни.

Этот нажрался сникерса и тут давай всех валить. Да кстати в той задачки про "задиру", есть ещё два нюанса: во-первых, если 15 знает, что он самый большой - это здорово, а если нет - то будет ещё слать 16 17 18 и ждать какое-то время... во-вторых, я хотел бы послать сообщение "ОК" процессу с ником =E, чтобы он... Того... Ну короче, я координатор...

2Castor: КГ/АМ

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

Завтра расскажем... На экзамене!

вот это и пугает, что узнаю я это на экзамене...

ну вот у меня опять есть инет :)
если внимательно посмотрите на мое дерево к задаче 4.1 то увидите что там одинадцать персылок запроса
крюков на последней лекции говорил что надо построить оптимальное дерево

Я согласен, больше не спорю.

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

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

Спасибо. На экзамене мне и лектор расскажет, правдв уже после того, как спросит. Расскажите хоть были ли двойки у 20-21, если кто знает? И, кстати, когда пересдача?

пост
Liya
25.05.2005 00:10

... И, кстати, когда пересдача? ...

Это неправильный вопрос! Не говори "кстати" пока не попался на "Крючок"! ;-)

Liya, там во-первых все время "если ...". А что если "если..." не выполнилось? Какие есть варианты?
И вообще там плохо понятно из-за ">" и каких-то непонятных "2", которые влезают в рандомных местах =(

Лучше не думать о плохом и не попадаться на крючек.

Слышь =E - у неё всё правильно. Ты же знаешь, что доступ к синхронизационным переменным осуществляется по модели последовательной консистентности, т.е. в зависимости от порядка синхронизации - порядок изменения тех или иных переменных - т.е. их конечные значения при R(x) R(y). А ещё сказал, что "мне лучше знать"... Э нет... Учись, студент...!

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

Мля, унесите отсюда кастора нах, задолбал уже, чесслово =Е

обоих бы вас отсюда на, падонкофф :)

лектор жжот. во бред с этой консистенцией...

если вычесть из моего ника 100, то получим число слов с корнем "консистент" в этой темке...самая прикольная темка это вобще, даже лучше to give or not to give

нунах. спать пора.

ненунах надо на экзамен собираться :)) надо же в кой-то веки опозориться :))

=E - ну ты обурел, я тебе сегодня сникерс куплю!

Люди, у кого приняли задачи- расскажите правильные решения...

правильных решений нет и быть не может. Надо просто обосновать свое решение - этого достаточно, чтобы его считали правильным

вот и сникерснули, 5...

2Некто: При одном условии - если вы не попали к лектору.
А ДжонСмиту опять нереально повезло, он попал к асперше.

Да он вообще охамел, сегодня лично видел, как Березину деньги давал, чтобы ему допуск поставили. С языком набок добежал до РОС, получил 5, быстренько убежал... Халявщикам вечно везёт... ;-)

Моя реакция: O___O
Морган, какой же ты скользкий тип!!

Да, прокатил моего научника со спецкурсом. Сказал, что будет ходить - тот повёлся поставил, тот один раз пришёл! И главное не стыдно совсем...

Хаха..нас тут под ником некто довольно много =)

Дурак ты :))) Мне не везет - я сам выбираю кому сдавать :)) Половина выиграша - выбор партнера :)

2Castor: хорош уже девочку из себя строить :)) все равно никто не поверит :))

Таких как ты надо Крючку на привозе приносить! Желаю тебе попасться на МО к Наталье Михайловне!

на МО Н.М. самый халявный препод, асперы хуже, не говоря уже о других преподах

Так, по следам екзамена - какой-то он был странный...
При подготовке думал о четверке как о манне небесной, а теперь жалею, что 4 поставили... ))
Такого долгого екзамена у меня еще не было, взял билет примерно в 9-05, пошел отвечать в пол-второго )))
вообще, вроде халявный екзамен, только аспиранты ОЧЕНЬ долго спрашивают. Я вот видел, как некоторые отвечали гораздо больше часа и уходили с пятерками все красные ))))

ну да я вот например с апершей например обсуждал всяких падонкофф которые постят в сетке кривые решения :)

и тут никого

Да, глухо как-то...