Жіңішке түйіршікті құлыптары бар тізбекті қауіпсіз тізім

Бағдарламада M сынып бар:

class M{
    /*
      very big immutable fields
    */
    int status;
};

Маған М типті объектілердің байланыстырылған тізімі қажет.

Тізімге қол жеткізудің үш түрі бар:

  • Өндірушілер: Тізімнің соңына нысандарды шығарыңыз және қосыңыз. Жаңадан шығарылған барлық нысандар = NEW мәртебесіне ие. (Жұмыс уақыты = O (1))
  • Тұтынушылар: Тізімнің басында заттарды қолданыңыз. Егер тұтынушы мәртебесі = CONSUMER_ID болса, тұтынушы оны тұтынуы мүмкін. Тұтынушылардың әрқайсысы байланыстырылған тізімдегі бірінші тармақты тұтыну үшін тұтыну үшін (амортизацияланады?) O (1) (төмендегі ескертуді қараңыз) сақтайды.
  • Destructor: объектінің дұрыс пайдаланылғаны туралы хабарландыру болған кезде тұтынылған нысандарды жояды (Операция уақыты = O (1)).
  • Модификатор: күй диаграммасына негізделген нысандардың күйін өзгертеді. Кез-келген нысанның соңғы мәртебесі - тұтынушының идентификаторы (Әрекетке арналған уақыт = O (1)).

Тұтынушылар саны 10-нан аз. Өндірушілер саны бірнеше жүзден асуы мүмкін. Бір модификатор бар.

note: The modifier may modify the already consumed objects and thus the stored items of consumers may move back and forth. I did not find any better solutions for this problem (Although, the comparison between objects is O(1), the operation is no more amortized O(1)).

Орындау өте маңызды. Сондықтан қажетсіз блоктауды болдырмау үшін атомдық операцияларды немесе ұсақ түйіршікті құлыптарды (бір нысанға бір) қолданғым келеді.

Менің сұрақтарым:

  1. Atomic operations are preferred because they are lighter. I guess I must use locks for updating the pointers in destructor thread only and I can use atomic operations for handling contention between other threads. Please let me know if I am missing something and there is a reason that I cannot use atomic operations on status field.

  2. I think I cannot use STL list because it does not support fine-grained locks. But would you recommend using Boost::Intrusive lists (instead of writing my own)? Here it is mentioned that intrusive data structures are harder to make thread-safe? Is this true for fine-grained locks?

  3. The producers, consumers and destructor would be called asynchronously based on some events (I am planning to use Boost::asio. But I don't know how to run the modifier to minimize its contention with other threads. The options are:

    • Asynchronously from producers.
    • Asynchronously from consumers.
    • Using its own timer.

Кез келген осындай қоңырау тізімде жұмыс істейтін болса, кейбір шарттар орындалады. Өзімнің түйсігі - модификатор деп атайтынымның арасындағы айырмашылық жоқ. Мен бірдеңе жетіспеймін бе?

Менің жүйем Linux/GCC болып табылады және мен маңыздылығы жағынан 1.47 күшейткімін пайдаланамын.

Similar question: Thread-safe deletion of a linked list node, using the fine-grained approach

3
@Martin. Жауап үшін рақмет. Маған бір деструктор керек, себебі тұтынудан кейін нысан қалпына келтірілуі мүмкін немесе мүмкін болмауы мүмкін. Мен объектіні қайтадан кіргізе алмаймын, себебі салынған нысандардың реті маңызды (олар бастапқыда сұрыпталады).
қосылды автор Shayan Pooya, көзі
@Mooding Жауап үшін рақмет. Сол себепті бірнеше тізімді пайдаланудың алдын алады. Әрбір тізімді сұрыптау керек және O (1) ішіндегі басқа тізімнің ортасына объект енгізе алмаймын. Қысқаша айтқанда, кез-келген нысанды қайтадан енгізу мүмкін емес.
қосылды автор Shayan Pooya, көзі
Алдымен, неге сіз деструктор қажет? Егер тұтынушы оны бөлшектегеннен кейін объектіні дұрыс пайдаланса, ол объектінің өзін бұзуы мүмкін. Кейінірек қайталап көруге мүмкіндік беретін түрдегі қате болса, ол күйді тиісті түрде орнатып, тізімге қайта жібереді.
қосылды автор Martin James, көзі
Мен модификатор тізімнің мақсатты объектісін алу үшін қысқа уақытқа бүкіл тізімді құлыптауға рұқсат беруге азғырылатын болар едім. Содан кейін оны басқа субъектілерден кедергісіз өзгертіп, содан кейін нысанды кері жүктей алады.
қосылды автор Martin James, көзі
Мен жеңілдету үшін үш тізімге ие болу идеясын тастайтын едім. Өндіруші-> Modifier- біреуі, біреуі Modifier-> Consumer, біреуі Тұтынушы-> Destructor үшін. Мен құлыптау болмаса, кодты оңайлатады деп ойлаймын.
қосылды автор Mooing Duck, көзі

4 жауаптар

Көрініс өте маңызды. Сондықтан қажетсіз блоктауды болдырмау үшін атомдық операцияларды немесе ұсақ түйіршікті құлыптарды (бір зат үшін бір) қолданғым келеді.

Бұл өнімділікті нашарлатады, сол себепті талқылайтын тақырыптар (сол деректерге қолжетімділік) түрлі ядраларда бір уақытта орындалады. Егер құлыптар тым жақсы болса, ағындар (кэштер арасындағы пинг-понг деректерін) қарсыласуы мүмкін және құлыпты құлыптап, қорқынышты өнімділікке әкелмей, баяу құлыптау қадамында жұмыс істейді.

Сіз бірдей деректер блогын мүмкіндігінше тез арада бір-бірімен таластыратын жіптерді жеткілікті мөлшерде пайдаланғыңыз келеді. Бұл жоспарлаушыны өнімді бұзатын кэш пинг-понгингін жойып, қарсыласпайтын тақырыптарды жоспарлауға мәжбүр етеді.

Сізде бұғаттау нашар болып табылатын жалпы қате түсінік бар. Шын мәнінде, шиеленіс нашар, өйткені ол өзегін автобустың жылдамдығына дейін баяулатады. Бұғаттаудың аяқталуы. Блоктау - бұл жақсы , себебі ол жоспарланбайтын, бәсеңдетілмейтін жіптерді (толық жылдамдықта бір мезгілде іске қосуға болатын) мүмкіндік беретін бәсекелес желілерді де жоспарлайды.

8
қосылды
Мен қақтығыстардан аулақ болу үшін майда түйіршіктерді қолданғым келеді. Әрбір ағынның кейбір нысандары бар және басқа нысандарды ұстамайды. Мысалы, әрбір тұтынушы өзіне тағайындалған нысандарға қызығушылық танытады. Қатты құлыпты пайдалану барлық тұтынушыларға (және модификаторлар мен өндірушілерге) олардың мақсаттарына қол жеткізуін болдырмайды. Жақсы дәнді құлыптарды қолданғанның арқасында, кейбір артықшылықтар бар, бірақ артықшылықтар, әсіресе сипатталған жағдайда.
қосылды автор Shayan Pooya, көзі
@Shayan: Жинақтарды қорғайтын құлыптардан нысандарды қорғайтын құлыптарды бөліп алу қажет болуы мүмкін.
қосылды автор David Schwartz, көзі
Spinlocks проблемасын түсіндіру үшін +1, онда дайын ағындар саны спинклок жарыстары салдарынан өзектердің санына жақындайды немесе асып түседі. Маған қиындық тудырады :) Осы күрделі талаптың арқасында, ең алдымен, жүйені функционалды түрде дұрыс жұмыс істеп, ядро ​​құлыптарын ауыр салмақпен сынақтан өткізгім келеді.
қосылды автор Martin James, көзі
Кезекке арналған бірыңғай стандартты OS құлпына ие болғанда, тек байланыстырылған тізім операциялары (нүктелік тапсырмалар) құлып астында орындалады деп ойлаймын.
қосылды автор cdleonard, көзі

Егер Boost Asio-ды қолданғыңыз келсе, онда жақсы жаңалық! Сіз өзіңіздің реттелетін асинхронды өндіруші-тұтынушы кезегін дәл қазір жазуды тоқтатуға болады.

Boost Asio io_service класы - асинхронды кезек, сондықтан оны өндірушілерден тұтынушыларға беру үшін оңай пайдалануға болады. Басқа ағын арқылы асинхронды қайта қоңырау шалу үшін байланыстырылған функция нысанын күшейту үшін io_service :: post() әдісін қолданыңыз.

boost::asio::io_service io_service_;

void produce()
{
    M* m = new M;
    io_service_.post(boost::bind(&consume, m));
}

void consume(M* m)
{
    delete m;
}

Өндірушілердің өңдеушілері produce() деп қоңырау шалып, содан кейін тұтынушыларға io_service_.run() қоңырау шалып, одан кейін consumption() деп аталатын болады тұтынушы ағындарына қайта қосыңыз. Instant producer-consumer!

Сонымен қатар, егер сіз желі сигналын оқиды және күтіп жатсаңыз, тұтынушы ағындарымен өңделетін io_service _ ішіне басқа әртүрлі оқиғалардың барлық түрлерін енгізуге болады. Asio тек қана желі кітапханасынан артық - бұл прокәрімді, реакторды, өндіруші-тұтынушыны, жіп-пулды немесе кез келген басқа ағындық архитектураны білдірудің оңай жолы.

EDIT

Oh, and one more tip. Don't make separate pools of dedicated producer threads and dedicated consumer threads. Just make one thread for each core available on your machine (4 core machine => 4 threads). Then have all those threads call io_service_.run(). Use the io_service_ to asynchronously read stuff to produce, from files or the network or whatever, then use the io_service_ again to asynchronously consume whatever was produced.

Бұл архитектураның ең жақсы жұмыс жасаушысы. Әрбір ядро ​​бір ядро.

2
қосылды
Жауап үшін рақмет. Мен io_service-ді тапсырмаларды асинхронды түрде басқаруға пайдалануды жоспарлап отырмын, ал модельде айтқаным - абстракция. Дегенмен, io_service проблемасы (функциясы) міндеттердің бір уақытта орындалуын қамтамасыз етпейді (егер біз сызықтарды пайдаланбасақ). Сондықтан io_service пайдаланған кезде де үндестіру қажет.
қосылды автор Shayan Pooya, көзі
io_service :: run() ішіндегі io_service жүйесіндегі синхронды оқиғаларға тапсырыс беруді қамтамасыз ету қажет болса, дәлірек, io_service :: strand бірден көп жіппен шақырылады. Сіз бұрынғыдай асиоды жақсы көрдіңіз және менің ойымша, сіз одан да тығыз көрінуі тиіс деп ойлаймын. Кристофер Колхофф сіз өндіруші-тұтынушы кезегінде кез-келген проблемаға тап болған кез-келген мәселені ойлап тауып, шешімді қамтамасыз еткенін таба аласыз.
қосылды автор James Brock, көзі

Мәселеге аздап басқа көзқараста кеңес берер едім:

Өндірушілер: Ортақ кезек (SQ) соңында нысандарды орындаңыз. Оянады модематор арқылы семафор.

producer()
{
  while (true)
  {
    o = get_object_from_somewhere ()
    atomic_enqueue (SQ.queue, o)
    signal(SQ.sem)
  }
}

Тұтынушылар: Әрбір тұтынушы кезегіне алдыңғы жағынан қарайтын заттар (CQ [i]).

consumer()
{
  while (true)
  {
    wait (CQ[self].sem)
    o = atomic_dequeue (CQ[self].queue)
    process (o)
    destroy (o)
  }
}

Destructor: Destructor жоқ, тұтынушы жасағаннан кейін объект, тұтынушы оны бұзады.

Modifier: Modifier ортақ кезектерден нысандарды ажыратады, оларды өңдейді және оларды тиісті тұтынушының жеке кезегіне айналдырады.

modifier()
{
  while (true)
  {
    wait (SQ.sem)
    o = atomic_dequeue (SQ.queue)
    FSM (o)
    atomic_enqueue (CQ [o.status].queue, o)
    signal (CQ [o.status].sem)
  }
}

Жалған кодта әртүрлі atomic_xxx функцияларына жазба: бұл CAS, CAS2 сияқты атомдық нұсқауларды пайдалану міндетті емес, LL/SC, etc. Atoms, spinlocks немесе қарапайым мудрлерді қолдануға болады. Мен оны ең қатаң түрде жүзеге асыратын кеңес (мысалы, mutexes) және кейінірек оңтайландырады, егер ол дәлелденсе өнімділік мәселесі.

1
қосылды

@David Schwartz әділ атап өткендей, бұғаттау әрдайым баяу және айналдыруға болмайды (пайдаланушылық кеңістікте многопоточные қосымшалар) өте қауіпті болуы мүмкін.

Сонымен қатар, Linux pthread кітапханасы pthread_mutex «ақылды» іске асырылуда. Ол «жеңіл» болу үшін жасалынған, яғни жіп, қазірдің өзінде сатып алынған мутахты құлыптауға тырысқан кезде, ол бұғатталмас бұрын құлыпты алуға бірнеше әрекет жасайды. Қате саны жүйеңізге зиян келтіретін немесе тіпті нақты уақыт талаптарын бұзатын жеткілікті үлкен емес (егер бар болса). Қосымша linux ерекшелігі жылдам пайдаланушылық кеңістік мутекі (FUTEX) деп аталады, бұл жүйенің санын азайтады . Негізгі идея mutex_lock syscall функциясын, егер шынымен мутахта бұғатталуы қажет болғанда (қисықсыз мутахты құлыптаған кезде, ол syscall жасамайды) ғана жасайды.

Шындығында көбінесе дөңгелекті қайта ойлап табудың қажеті жоқ, немесе кейбір ерекше құлыптау әдістерін енгізу қажет емес. Егер сізге қажет болса, онда дизайнмен дұрыс емес нәрсені немесе бір мезгілде жоғары деңгейде жұмыс істейтін болсаңыз (бірінші көзқарас үшін 10 тұтынушы көрінбейді және мұның бәрі инженерлік жағдайға ұқсас).

  • If I were you I'd prefer to use conditional variable + mutex protecting the list.
  • Another thing I'd do is to go over the design again. Why use one global list when consumer needs to do a search to find out whether the list contains the item with its ID (and if so, remove/dequeue it)? May be it's better to make a separate list for each consumer? In this case you probably can get rid of status field.
  • Does read access is more frequent than write access? If so it would be better to use R/W locks or RCU
  • If I wouldn't satisfied with pthread primitives and futex stuff (and if I wouldn't, I would have proved by the tests that locking primitives are bottleneck, not the number of consumers or the algorithm I chosen), then I'd try to think about complicated algorithm with reference counting, separate GC thread and restriction of all updates to be atomic.
1
қосылды