виждал съм всякакви вариации, затова се конкретизира предварително

Четенето и актуализацията на указателя трябва да са в една атомична операция! Ето един пример защо:

Това се разлага на 4 отделни под-операции: 1. прочита се стойността на указателя, 2. прочита се стойността от ареса към който указателя сочи, 3. указателя се намалява с 1, 4. записва се новата стойност на указателя

Ако тази последователност бъде прекъсната някъде между стъпки 1 и 4 и бъде изпълнено друго четене - могат да се случат бъгливи сценарии, като например да се обработи два пъти един и същ елемент или да се пропусне елемент. Нещата могат да станат още по-зле ако повече от две нишки четат от опашката!

Същото важи и за вкарването на елемент в опашката.

може да си ги разбиеш и на 400 операция, все тая!
От другата страна се виждат само две състояния - стара стойност и някаква нова стойност и доколкото и двете стойности са валидни няма никакъв проблем



Прекъсвай колкото искаш, но такъв филм с класическо фифо няма...


Ех ако не знаеш какво ползваш, нещата могат да станат много по-зле

Какво е това класическо фифо, което няма проблем с прекъсванията?!

Такова, което спира като се напълни и игнорира следващите данни, докато не се освободи място. При такъв сорт фифо и ако само един пъха и друг вади - проблем с прекъсванията няма, защото двата процеса ПИШАТ свойте си указатели и само четат отсрещните. В момента в който пишещия види, че има достатъчно място почва да пише, а даже и през това време четящия да го прекъсне и да премести пойтера , проблем съществен няма.

фифо е вид структура от данни

И е базова примитива за синхронизация както в хардуера, така и в софтуера. Особено в хардуера е толкова базова, че няма накъде повече... може би се ползва в 99.99% от случаите при синхронизация на група сигнали между два клок домейна.

В софтуера класическо фифо е кръгов буфер с 2 указателя и позволява синхронизация между две нишки. Без каквито и да е забрани, стига архитектурата да поддържа атомичен запис с размер размерите на указателите и паметта да е последователен модел (т.е. да няма разбъркване в кеша).

Съгласен съм, че ако нишките са само две (едната вкарва елемент в опашката, а другата вади) то тогава голяма беля не може да стане.

Но, според мен има смисъл да се говори за "thread safe FIFO" когато много нишки вкарват, а една изкарва или обратното или пък най-сложния вариант - много вкарват и много изкарват. Ако случая на използване на въпросното ФИФО е такъв - то тогава за да бъде то "thread safe" трабва да има атомични операции казващи се примерно push и pull, които да не дават достъп на нишката от която се викат до указателите, а просто да си свършват работата наведнъж без да могат да бъдат прекъсвани от друга push или pull операция. Така ли е или греша някъде?

Много неща могат да се направят....

Въпросът е, че първо трябва да се дефинират проблемите, които бориш и след това да търсиш решението. В твоето "tread safe fifo" има два различни проблема. Единият е как да обменяш данни асинхронно между две страни, Другият проблем е как от едната страна да имаш много маймуни.

Първият проблем накратко възниква когато имаш данни с повече от две състояния и две страни дето не са синхронни. Ако са синхронни няма проблем. Ако са две състояния няма проблем. Но тия ако-то не са спазени имаш проблем, щото другата страна може и да не види състоянията правилно
Пример - представи си една жица. Ако от едната страна на жицата пращаш нула или едно и от другата страна ще виждаш нула или едно. Но ако са две жиците става сложничко, защото сигналите никога в реални жици не пътуват еднакво бързо. И ако от едната страна пращаш примерно 10-01-10-01, от другата страна може да ти изглежда всякак, включително 10-00-11-00... т.е. ще виждаш грешни комбинации. Това е проблемът.
Решението е или да ползваш разни трикове като да кажем грей код, но това налага ограничения как да се сменят данните. Или фифо. При фифото в най-простият вариант по пътя на жиците слагаш две клетки памет и добавяш още две жици. Пишештата страна гледа жицата на четящата и решава в коя от клетките да пише и дали да пише изобщо. И обратно четящата гледа нейната жица и решава от коя клетка да чете и дали да чете.
Забелижи, че многото състояния отиват в клетките, но всяка страна работи с клетка с която другата не работи, така че няма фалшиви междинни комбинации. В клетките може да имаш коооолкото си искаш състояния и информация. И забележи че информацията между страните се обменя по една жица, така че пак нямаш проблем.
Сега, до тук имаш решение на проблема как да предаваш неограничен брой състояния от една страна към друга асинхронно, т.е. не се налага едната страна да блокира, т.е. може да се чете и пише по едно и също време без проблем!
Следващия тънък момент е какво правиш ако се налага да предваш повече от един комплект данни, т.е. как да ги буферираш. Винаги може да добавиш повече от две клетки памет, нали? И ще може да буферираш... само че си ако си внимал дотук ще се сетиш че за да адресираш повече от две клетки ти трябва повече от една жица за да ги адресираш. И стигнахме до същия проблем който по принцип решаваме. Само че клетките се пълнят и празнят в определен порядък и аз по-горе споменах за грей кода. В случай че не знаеш при него номерът е, че при промяна се променя само 1 бит, т.е. от всички жици за адресите ще се клати само една и бинго! С една жица нямаш проблем
И сега вече нямаш никакви ограничения и може да си предаваш и приемаш както си искаш без ядове.

Относно втория проблем... имаш много маймуни от едната страна. Пращането може да стане асинхронно, т.е. нито една маймуна да не блокира друга маймуна. Простичко казано ти трябват толкова на брой фифо-та колкото са маймуните и ти трябва още една маймуна дето да обожда от другия им край и да вади данните и да ги събира в едно друго фифо. При получаването тоя номер е лееко безсмисле, надявам се сещаш защо...
И така стигаме до другия вариант при който маймуните се изчакват. Това е друг концептуален проблем "много маймуни ползват общ ресурс" и съответно има различни решения, като почнеш от забрана на прекъсванията до разните синхронизационни примитиви като семафори, критични секции и т.н.
Ама много дълга лекция стана та мисля да спра до тук...

Малко нагледно.



miro_atc , не разбрах когато са многото маймуни на клона как се решава проблема?

Някой може ли да ми даде пример за реално приложение на едно FIFO в което много маймуни вкарват данни и съответно много маймуни вадят данни?

По скоро е комбинация с LIFO
И на мен ми е интересно как се решава проблема понеже точно това ми създава проблеми.
Като пример мога да ти посоча 1-Write но там има изчакване и много се бави. С код на грей е долу горе почти като УСБ.

многото маймуни стават или със забрана на прекъсванията/таск суич или с атомични read-modify-write или по някой от софтуерните алгоритми.

Най-чисто може би е с атомични операции (ако ги има архитектурата). За разлика от прекъсванията те бачкат и когато маймуните не седят на един и същ кур.
А софтуерните алгоритми са с овърхед, които расте с броя на маймнуните.... Има ги описани във вики-то ако някой се интересува.
Сега това е как става на ниско ниво, иначе ОС-те и библиотечките си имат стандартни абстракции от сорта на мютекси, семафори, критични секции и т.н. И обикновено те се ползват за маймуните, вместо всеки път на ниско ниво да си го правиш сам...

Не бе Миро, аз не питах как става , а кое е реалното приложение където се налага да става така.

Message queue-то на Windows е точно такъв пример - има няколко драйвера които слагат съобщения вътре и има много програми които ги вадят.

аз мислех, че въпросът ти е реторичен

Значи много към много е рядкост, поне в момента не се сещам някога да съм го ползвал за нещо.

Много към един или един към много се среща. На практика във всеки стек или по-сложен драйвер имаш подобна организация, щото имаш много клиенти дето пускат заявки, а от другата страна някой (един) ги вади и обработва една по една...