BG Development


Страници: (11) [1] 2 3 ... последна »  ( Първото ново мнение ) Reply to this topicStart new topicStart Poll

> Алгоритъм за рязане на опашка., Идеи?
johnfound
Публикувано на: 04-08-2018, 19:40
Quote Post


Group Icon
Име:
Група: VIP
Ранг: Почетен член

Мнения: 6839
Регистриран на: 27.05.04



Задачата е следната - имаме опашка, в която се добавят записи.

Имаме неизвестен брой процеси, които четат записите от опашката и ги обработват. Всеки процес, започва за чете опашката от там, докъдето тя е стигнала в момента на стартирането на процеса. Такива процеси могат да са произволно количество. И те могат да четат записите произволно бързо или бавно.

Има и един отделен процес, чийто задача е да изтрива старите записи от опашката - тоест, такива, които са прочетени от всички процеси до момента.

Въпросът е как този процес да определи докъде да изтрива. Той не знае реално кой процес до къде е стигнал с обработката. Той даже не знае колко процеса четат записите.

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

Имам някакво вътрешно чувство, че задачата може да се реши просто и елегантно. Но не мога да го измисля. icon_lol.gif

Идеи?


--------------------
asm32 - Приложно програмиране на асемблер.
Tox: 2B446ADCEC7E180CD4C59391D81D4CAB3E99CA7AE767DB3AB45AF976F8A2050FF071DDB733F1
PMEmail PosterUsers Website
Top
kierenski
Публикувано на: 04-08-2018, 19:46
Quote Post



Име:
Група: Потребител
Ранг: Активен

Мнения: 291
Регистриран на: 10.01.16



Мислил ли си за флаг с който да бъде маркиран записа че е прочетен и ограничаване/указване кой кога може да промени флага.
PMEmail Poster
Top
AK-85
Публикувано на: 04-08-2018, 20:02
Quote Post



Име:
Група: Потребител
Ранг: Старо куче

Мнения: 777
Регистриран на: 06.07.06



Колко процеса добавят елементи в опашката? Има ли някакво изискване елементите да се разпределят равномерно?
PM
Top
Major Obvious
Публикувано на: 04-08-2018, 20:09
Quote Post



Име:
Група: Потребител
Ранг: Активен

Мнения: 171
Регистриран на: 16.12.17



На мен ми е по-интересно как си решил проблема с това да въртиш "неограничен" брой процеси при наличието на ограничени ресурси.
PMEmail Poster
Top
SuN
Публикувано на: 04-08-2018, 20:13
Quote Post


Group Icon
Име:
Група: Администратор
Ранг: Почетен член

Мнения: 7239
Регистриран на: 27.01.05



QUOTE (Major Obvious @ 04-08-2018, 20:09)
На мен ми е по-интересно как си решил проблема с това да въртиш "неограничен" брой процеси при наличието на ограничени ресурси.

На асемблер стават чудеса!


--------------------
Копирай лесно ударено и - ѝ Ѝ
Замърсяване на въздуха в София - http://aqicn.org/city/bulgaria/sofia/druzhba/
PMEmail Poster
Top
40oz
Публикувано на: 04-08-2018, 20:28
Quote Post



Име:
Група: Потребител
Ранг: Активен

Мнения: 237
Регистриран на: 23.05.13



Малко е неясно условието, но пробва ли да потърсиш отговори в Сборника? Ако си сложиш по едно числово id (както пише Там) на елементите и всеки като взема го инкрементваш, а чистача гледа дали това id е колкото броя текущи процеси?
PMEmail Poster
Top
Дон Реба
Публикувано на: 04-08-2018, 20:28
Quote Post



Име:
Група: Потребител
Ранг: Почетен член

Мнения: 7308
Регистриран на: 11.11.06



чайся, ти реши трудното, спънал си се на мекото? нещо не ми се вярва. трудното тука е как процесите да си хващат записи без да дублират/прескачат. както и да си го "решил" (решил ли си го?) това, ми ползвай го същия механизъм бе. как процеса разбира че тоя запис е вече зает? ми по същия начин да разбира и чистача и да трие
PM
Top
Major Obvious
Публикувано на: 04-08-2018, 20:37
Quote Post



Име:
Група: Потребител
Ранг: Активен

Мнения: 171
Регистриран на: 16.12.17



Те много процеси могат да обработват един и същи запис. Поне така излиза от условието. Виж че запис се трие само след като е прочетен от всички процеси.
PMEmail Poster
Top
johnfound
Публикувано на: 04-08-2018, 21:03
Quote Post


Group Icon
Име:
Група: VIP
Ранг: Почетен член

Мнения: 6839
Регистриран на: 27.05.04



@AK-85, по принцип няколко процеса могат да добавят елементи в опашката, но това реално няма връзка със задачата.

@40oz - реално не става, защото може да се появи нов процес и количеството процеси ще се увеличи, но новия процес няма да прочете старите записи и съответно няма да увеличи брояча.

Същото става и със намаляващ брояч – в момента на добавяне на записа в опашката, в него се добявя броя на процесите, работещи в момент – тоест, тези, които могат да го прочетат. След това, когато някой процес прочете записа, намалява брояча. А чистача трие при 0. Само че и това няма да работи, защото някой от процесите може да умре преди да стигне до въпросния запис и съответно няма да намали брояча.

@Дон Реба: Не съм съвсем сигурен за каква точно синхронизация говориш, но по принцип съм решил проблемите със синхронизацията между процесите. По принцип, обработката на запис от процеса не премахва този запис от опашката. Тоест всички процеси обработват всички записи вкарани в опашката след тяхното стартиране. То затова е и проблема с почистването.

Това мнение е било редактирано от johnfound на 04-08-2018, 21:03


--------------------
asm32 - Приложно програмиране на асемблер.
Tox: 2B446ADCEC7E180CD4C59391D81D4CAB3E99CA7AE767DB3AB45AF976F8A2050FF071DDB733F1
PMEmail PosterUsers Website
Top
dvader
Публикувано на: 04-08-2018, 21:14
Quote Post


Group Icon
Име:
Група: VIP
Ранг: Почетен член

Мнения: 4162
Регистриран на: 12.07.05



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

Това мнение е било редактирано от dvader на 04-08-2018, 21:16


--------------------
I find your lack of faith disturbing
PM
Top
1 потребители преглеждат тази тема в момента (1 гости, 0 анонимни потребители)
Потребители, преглеждащи темата в момента:

Topic Options Страници: (11) [1] 2 3 ... последна » Reply to this topicStart new topicStart Poll

 


Copyright © 2003-2018 | BG Development | All Rights Reserved
RSS 2.0