---

Hej,

Jeg har brug for en kø, som jeg har tænkt mig at implementere vha. en
passende container (deque eller list).
Nogle tråde fylder data i vha. push_back(), og nogle henter data ud vha.
pop_front() og efterfølgende erase().

Problemet er at der ikke findes en pop()-variant der både returnere det
sidste element og fjerner det fra køen.
Det giver en race-condition mellem pop_front() og erase().
Skal jeg selv lægge en lås uden om de 2 kald, eller findes der en anden
løsning?

Leo Havmøller.

---

Leo Havmøller wrote:
> Jeg har brug for en kø, som jeg har tænkt mig at implementere vha. en
> passende container (deque eller list).
> Nogle tråde fylder data i vha. push_back(), og nogle henter data ud vha.
> pop_front() og efterfølgende erase().
>
> Problemet er at der ikke findes en pop()-variant der både returnere det
> sidste element og fjerner det fra køen.
> Det giver en race-condition mellem pop_front() og erase().
> Skal jeg selv lægge en lås uden om de 2 kald, eller findes der en anden
> løsning?

Selv om der fandtes en pop-variant der returnerede det fjernede element,
så ville det ikke hjælpe dig. Standard library kender ikke noget til
tråde. Du bliver derfor selv nødt til at lægge en lås hver gang du læser
eller skriver til din container.

Ivan Johansen

---

"Leo Havmøller" <leh@-nospam-rtx.dk> wrote:

[8<8<8<]
> Jeg har brug for en kø, som jeg har tænkt mig at implementere vha. en
> passende container (deque eller list).

Hvad med at bruge std::queue container adapteren eller lave lave en
tilsvarende container adapter med de ønskede tråd egenskaber ?

Jeg har lavet en sådan tråd sikker adapter. Den er lavet ovenpå ObjectSpace
Thread<ToolKit> bibliotekets tråd klasser.
Send mig en mail, så returnerer jeg gerne koden (uden nogen form for
garantier eller ansvar for korrekt funktion).

Det er ikke helt trivielt at få så simpel så man er _sikker_ på at den
virker (og stress teste den for at fjerne fejl).
Den blev lavet således at mange tråde kunne indsætte i køen men kun een tråd
fjernede fra den (og dermed har den ikke det problem du egentlig spørger
om).

Der ligger nogle vigtige tråd beslutninger:
* skal "back" og "front" udgøre ventepunkter hvis køen er tom ?
* hvad med timeout ?
* hvis ikke, hvordan skal tråden(e) der tager ud fra køen finde ud af
hvornår der bliver sat noget ind i køen - bortset fra at bruge busy-wait
(while(!queue.empty());)
* skal containeren håndtere hvis nogle tråde venter på at der bliver sat
noget ind i køen, når køen bliver nedlagt ?
og der er sikkert flere.


> Nogle tråde fylder data i vha.
> push_back(), og nogle henter data ud vha.
> pop_front() og efterfølgende erase().

Formelt set siger C++ Standarden ikke noget om tråde, og derfor er det ikke
specificeret hvordan container klasserne opfører sig i forhold til tråde.

Når det er sagt forventes det almindeligvis at det er trådsikre på samme
måde som en integer.

Se eventuelt http://www.sgi.com/tech/stl/thread_safety.html

[8<8<8<]
> Problemet er at der ikke findes en pop()-variant der både returnere
> det sidste element og fjerner det fra køen.

Årsagen til det at der ikke findes en sådan operation er at det generelt
ikke kan gøres exception sikkert.
Hvis det skulle være anderledes og man ville _garantere_ at man ikke mister
elementer skulle man _kræve_ at copy-constructoren ikke må smide exceptions.


> Det giver en
> race-condition mellem pop_front() og erase(). Skal jeg selv lægge en
> lås uden om de 2 kald, eller findes der en anden løsning?

Ja, f.eks.:

1.
Lås den ekternt. Kræv f.eks. pop funktionen tager en reference til et lås
objekt - så er man sikker på at det findes (på den pæne side af et hack).

2.
Lad pop funktionen tage en reference til et objekt, således at der bruges
assignment (i stedet for copy-constructor) inde i pop-funktionen som man så
_ved_ gik godt inden elementet fjernes fra køen.

3.
Alloker en kopi af elementet på heapen og returner en auto_ptr (auto_ptr
copy-constructor smider _aldrig_ exceptions) til kopien. Man _ved_ således
inden pop-funktionen at oprettelsen af kopien gik godt inden elementet
fjernes fra køen.

4. Sørg for at der kun er een tråd der fjerner fra køen

Venlig hilsen

Mogens Hansen

---

Mogens Hansen wrote:
> Formelt set siger C++ Standarden ikke noget om tråde, og derfor er det ikke
> specificeret hvordan container klasserne opfører sig i forhold til tråde.
>
> Når det er sagt forventes det almindeligvis at det er trådsikre på samme
> måde som en integer.

På hvilken måde er en integer trådsikker?

Den eneste integer type som kan betragtes som trådsikker er vel
"sig_atomic_t" som er erklæret i <signal.h> for C og måske(?) i
<csignal> for C++.

sig_atomic_t er kun garanteret til at være på mindst 8 bit. På mit
Linux-system med gcc er den identisk med en 32-bit "int".

---

"Byrial Jensen" <bjensen@nospam.dk> wrote:

[8<8<8<]
> > Formelt set siger C++ Standarden ikke noget om tråde, og derfor er det
ikke
> > specificeret hvordan container klasserne opfører sig i forhold til
tråde.
> >
> > Når det er sagt forventes det almindeligvis at det er trådsikre på samme
> > måde som en integer.
>
> På hvilken måde er en integer trådsikker?

To tråde kan frit oprette og nedlægge hver sin integer uden skal foretages
synkronisering.
To tråde kan frit læse og skrive til hver sin integer uden at der kal
foretages synkronisering.
To tråde kan frit læse fra samme integer samtidig hvis man _ved_ (f.eks. en
konstant) at der ikke bliver skrevet til den.
To tråde _skal_ synkronisere tilgangen til samme integer hvis de vil ændre
integeren eller hvis de vil ikke med sikkerhed _ved_ at værdien er konstant.

Det er naturligvis ikke garanteret af sprog standarden (C eller C++), men
det er klart hvad man ville forvente.

De samme ting vil man forvente gælder for container klasserne i C++ Standard
Library.
Det er værd at bemærke at det _ikke_ var tilfældet for visse tidlige
implementeringer af STL.

Se eventuelt artiklen "STL Implementations and Thread Safety" af Sergey
Ignatchenko fra C++ Report July/August 1998, for en beskrivelse af en
opfattelse af tråd sikkerhed i relation til STL og en tilhørende test af en
række (gamle) implementeringer.
Dengang var SGI og ObjectSpace implementeringerne trådsikre, men
Hewlett-Packard, Rogue Wave og Microsoft ikke var. Men det er længe siden
nu, og jeg vil klart forvente at alle moderne implementeringer er trådsikre.

Venlig hilsen

Mogens Hansen