Шматструменнасць з доўгім сувязным спісам

У мяне ёсць алгарытм пытанне тут. Ёсць 10 патокаў у сістэме, і вы атрымаеце спіс спасылак з 10 K элементаў у ім. Як вы робіце сінхранізацыю патокаў (даданне выдалення і г.д.), так што ён аптымізаваны для працы? Выкарыстанне семафора для спісу не рэкамендуецца, паколькі гэта прывядзе да запаволення працы.

6
звязаны спіс структура дадзеных мяркуе, што ўсе аперацыі вынікаюць паслядоўным правілах.
дададзена аўтар Parag Bafna, крыніца
Як ўставіць/выдаліць, даючы нумар вузла ў якасці ўваходных дадзеных?
дададзена аўтар bjskishore123, крыніца
Ці сапраўды большасць аперацый на галаве/хвасце, або аперацыі, як правіла, ад выпадковых элементаў раскладзеных па спісе? Ці з'яўляецца спіс кругавой? Ці з'яўляецца 10K верхняя мяжа для памеру спісу?
дададзена аўтар jxh, крыніца
Пытанне: аптымізаваны для , які прадукцыйнасць?
дададзена аўтар UmNyobe, крыніца
Спосаб аптымізацыі кода шмат у чым залежыць ад таго, што ўсе аперацыі, якія выконваюцца ў спісе.
дададзена аўтар Dialecticus, крыніца
Калі ласка, апішыце, як менавіта выкарыстоўваецца спіс. Як і калі і кім ствараюцца, чытаюцца і мадыфікуюцца. І якія адносныя частоты гэтых аперацый (што адбываецца часцей).
дададзена аўтар Dialecticus, крыніца
Не, спіс не адсартаваны, таму аперацыі не гарантуюцца на галаве/хвасце. Спіс не з'яўляецца кругавым. 10K проста паказвае нумар сказаць сво доўгі спіс.
дададзена аўтар Adam, крыніца

7 адказы

Калі ўсе пазіцыі даступныя з той жа частатой, і вы можаце змяніць вузел спісу, вы можаце дадаць семафор для кожнага вузла:

typedef struct node{ 
   char* data;
   struct listNode *next;
   pthread_mutex_t lock; 
} listNode ;

Акрамя таго, у залежнасці ад памеру дадзеных вузла. Калі падміргнулі вельмі мала, гэта можа прывесці да накладных выдаткаў з-за захоўванне мьютекса, ствараць і выдаляць.

Калі падміргнула накладныя выдаткі ці не можа змяніць вузел, вы можаце падзяліць спіс у (напрыклад) 100 груп 100 элементаў і выкарыстоўваць семафор для кожнай групы

2
дададзена
Гэта мая першая думка таксама, але пры абыходзе спісу вы павінны заблакаваць/разблакаваць усе семафоры на вашым шляху, які не здаецца вельмі эфектыўным.
дададзена аўтар Dialecticus, крыніца

звязаны спіс структура дадзеных мяркуе, што ўсе аперацыі вынікаюць паслядоўным правілах. Паглядзіце на адначасовага звязанага спісу

<�Р> Незалежна ад таго, які выгляд тэхнікі выкарыстоўваецца для рэалізацыі яго,   інтэрфейс і чаканае паводзіны на ўвазе паслядоўную логіку.
1
дададзена

Я лічу адказ Эванс з'яўляецца правільным. Але я б прапанаваў выкарыстаць <�моцны> Узаемныя блакавання замест мьютексы . Ўзаемныя блакіроўкі з'яўляюцца больш эфектыўнымі ў выпадку нізкага паралелізму, і кароткае часу правядзення замкаў .

typedef 
struct ListNode { 
   void * data;
   struct ListNode * next;
   pthread_spinlock_t lock;
}
ListNode;
0
дададзена

Па-першае, калі выказаць здагадку, што даданне/выдаленне элементаў спісу не з'яўляецца прычынай для таго шматструменнасці (а логіка вызначэння/стварэння гэтых элементаў з'яўляецца працэс цяжкім) .. калі спіс ўстаўкі/выдалення час з'яўляецца вузкім месцам, то, магчыма, вы павінны перагледзець структуру дадзеных.

Далей, пры ўмове, што кожны струмень не будзе ўзаемадзейнічаць адзін з адным (адзін струмень не будзе выдаліць запіс, які быў устаўлены іншы) і што кожны паток мае канчатковы аб'ём працы. Хай кожная нітка не чапаць фактычны звязаны спіс, замест гэтага кожны паток падтрымлівае два дадатковыя спісы.

Вось як гэта працуе:

  1. Кожны паток запускаецца і стварае дзве дадатковыя спісы запісаў, выдаляць і ўстаўляць

  2. Улічваючы нітка малокомплектных калі нітка ўсё скончыць, мы можам проста дадаць спіс «новых пунктаў ДАДАТКОВЫХ» для кожнага патоку на пачатак ці канец існуючага спісу.

  3. Далей для аддаленых элементаў, мы аб'яднаем спіс элементаў, якія неабходна выдаліць з кожнага патоку, а затым мы абыходу арыгінальнага звязанага спісу і выдаленне прадметаў, як мы сутыкаемся з імі (можна палепшыць тут, выкарыстоўваючы хэш для спісу элементаў для выдалення.

Гэта працуе вельмі добра пры ўмове, што два здагадка ў пачатку справядліва. Акрамя таго, гэта азначае, што няма неабходнасці ў мьютексы або замкаў, ваш галоўны спіс абнаўляецца толькі ў канцы адзін паток пасля таго, як усе ніткі ўсе аб'яднаны зваротна ў асноўны паток.

0
дададзена

Правільнае рашэнне значна частоты працы залежыць ад аб'екта, які вы хочаце сінхранізаваць (спіс у вашым выпадку). Аперацыі на кантэйнеры з'яўляюцца стварэнне кантэйнера, мадыфікацыя кантэйнер, кантэйнер абыходам і мадыфікацыя элемента. Калі, напрыклад, спіс у асноўным пройдзены і чытаць, гэта можа быць, што спіс з'яўляецца няправільным кантэйнерам для працы. Можа быць, вам сапраўды трэба нейкае карта (таксама званы слоўнік), які забяспечвае вельмі хуткі доступ для чытання, калі ў вас ёсць ключавое значэнне. У гэтым выпадку няма ніякага абыходу на ўсіх, і гэта можа быць, што сінхранізацыя усяго кантэйнера на карце аказваецца найбольш эфектыўным, проста таму, што мы змянілі тып кантэйнера.

0
дададзена

Гэта залежыць ад працы, якую вы хочаце зрабіць у спісе спасылак, і калі спіс адсартаваны.

  1. Калі вы неспакой, што 2 ніткі змяніць значэнне якога-небудзь вузла, дадаць семафор для кожнай Норы, як любое тут.
  2. Калі вы непакой з нагоды працы спісу (даданне, выдаленне): гэта залежыць, калі вы больш чым чытаць запісу - выкарыстоўвайце блякаваньне для чытання пісьменніка, калі кожны струмень працуе на частцы спісу, чым вы можаце даць выдаліць доступ толькі да адпаведнай тэме
0
дададзена

Вы можаце выкарыстоўваць сістэмны выклік futex Linux для сінхранізацыі.

0
дададзена