[C] Random getal in twee threads

Pagina: 1
Acties:

Onderwerpen


Acties:
  • 0 Henk 'm!

  • dtech
  • Registratie: Juni 2005
  • Laatst online: 13-06 23:19
Hallo,

ik fork in een C programma ergens, en wil vervolgens dat de beide threads een ander random getal genereren. Dat lukt echter niet goed omdat de seed (time()) die ik gebruik vaak hetzelfde is bij beide threads. Weet iemand een manier waarmee het wel werkt?

Het zou erg lastig zijn om het programma te refactoren zodat de functie een argument meekrijgt, anders had ik gewoon in het hoofd-process twee numbers gegenereerd en a.d.v. de return van fork() gekozen.

Voorbeeld:
code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <unistd.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>

int p4( void ){
    srand(time(NULL));
    prinft("%d\n", rand()%8);
}

int main( void ){
    fork();
    p4();
    return 0;
}

[ Voor 16% gewijzigd door dtech op 25-05-2010 12:06 ]


Acties:
  • 0 Henk 'm!

  • Broken
  • Registratie: Maart 2004
  • Laatst online: 20-05 08:24
Een echt nette oplossing weet ik niet, maar je zou met getppid() kunnen kijken in welke thread je zit. Je zou een kleine delay kunnen inbouwen om dit probleem te omzeilen.

Een andere oplossing is gebruike maken van een andere random functie, hier zal je nog even moeten zoeken.

01101000 01100101 01101100 01110000


Acties:
  • 0 Henk 'm!

  • KompjoeFriek
  • Registratie: Maart 2001
  • Laatst online: 11-06 04:49

KompjoeFriek

Statsidioot

Seeden met pid (of desnoods pid+time()) lijkt me al voldoende.

WhatPulse! - Rosetta@Home - Docking@Home


Acties:
  • 0 Henk 'm!

  • dtech
  • Registratie: Juni 2005
  • Laatst online: 13-06 23:19
Hmm, kan ik niet gewoon getppid() gebruiken? Het gaat er namelijk niet om dat het een 100% veilige random functie is, maar vooral dat de waarden verschillen tussen de twee processen.

@KompjoeFriek
Ja, dankjewel :)

[ Voor 8% gewijzigd door dtech op 25-05-2010 12:13 . Reden: te laat ]


Acties:
  • 0 Henk 'm!

  • Semyon
  • Registratie: April 2001
  • Laatst online: 08:00
en de fork geeft vanzelf al terug of een 0 (main) of childpid:

code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <unistd.h>
#include <time.h>
#include <stdlib.h>
#include <stdio.h>

int p4( int x ){
    srand((x+1)*time(NULL));
    printf("%d\n", rand()%8);
}

int main( void ){
    int x=fork();
    p4(x);
    return 0;
}

[ Voor 5% gewijzigd door Semyon op 25-05-2010 12:15 ]

Only when it is dark enough, can you see the stars


Acties:
  • 0 Henk 'm!

  • Broken
  • Registratie: Maart 2004
  • Laatst online: 20-05 08:24
Seeden met het pid(+time()) klinkt als een aardige oplossing.

01101000 01100101 01101100 01110000


Acties:
  • 0 Henk 'm!

  • dtech
  • Registratie: Juni 2005
  • Laatst online: 13-06 23:19
Semyon schreef op dinsdag 25 mei 2010 @ 12:14:
en de fork geeft vanzelf al terug of een 0 (main) of childpid:
Het zou erg lastig zijn om het programma te refactoren zodat de functie een argument meekrijgt
Anders zou dit inderdaad een prima oplossing zijn:

code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int p4 (int rand);

int main( void ){
    int rand1, rand2;
    srand(time(NULL));
    rand1 = rand()%8;
    rand2 = rand()%8;
    int pid = fork();
    if(pid == 0){
        p4(rand2);
    }else if(pid > 0){
        p4(rand1);
    }else{
        fprintf(stderr, "Error creating child process");
    }
}

Acties:
  • 0 Henk 'm!

Anoniem: 47102

Bij de oplossing van Seymon niet de +1 bij x+1 vergeten, anders wordt een van de threads altijd met 0 geseed ;)
Een andere oplossing is een random van je random device halen (*NIX) /dev/random of twee seeds laden alvorens de fork te doen...

Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 13:46

.oisyn

Moderator Devschuur®

Demotivational Speaker

dtech schreef op dinsdag 25 mei 2010 @ 12:12:
Hmm, kan ik niet gewoon getppid() gebruiken? Het gaat er namelijk niet om dat het een 100% veilige random functie is, maar vooral dat de waarden verschillen tussen de twee processen.
Dan moet je gewoon het resultaat van de fork() gebruiken, of idd louter het PID van het huidige proces, die zijn gegarandeerd verschillend voor het parent- en het child-proces. Je kunt wel verschillende seeds gebruiken, maar zelfs dat garandeert niet dat de twee processen een verschillend resultaat krijgen (net als dat 2x gooien met een dobbelsteel ook niet garandeert dat je niet 2x hetzelfde gooit)

[ Voor 3% gewijzigd door .oisyn op 25-05-2010 12:20 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • dtech
  • Registratie: Juni 2005
  • Laatst online: 13-06 23:19
(net als dat 2x gooien met een dobbelsteel ook niet garandeert dat je niet 2x hetzelfde gooit)
Goed punt, maar ik ben al veel blijer met de 12,5% die het nu is dan met de bijna 90% die ik eerst kreeg. Iemand een ander idee om het (bijna) 100% verschillend te maken? Nogmaals: een argument aan p4 meegeven is helaas niet echt een optie.
/dev/random is idd een aardig idee maar misschien wat overkill.

Acties:
  • 0 Henk 'm!

Anoniem: 47102

.oisyn schreef op dinsdag 25 mei 2010 @ 12:20:
[...]

Dan moet je gewoon het resultaat van de fork() gebruiken, of idd louter het PID van het huidige proces, die zijn gegarandeerd verschillend voor het parent- en het child-proces. Je kunt wel verschillende seeds gebruiken, maar zelfs dat garandeert niet dat de twee processen een verschillend resultaat krijgen (net als dat 2x gooien met een dobbelsteel ook niet garandeert dat je niet 2x hetzelfde gooit)
Als de getallen perse verschillend moeten zijn moet je de twee threads toch echt met elkaar laten praten en bij gelijk zijn een ervan (bijv. child) opnieuw laten randomen.

Waarop kan je p4() geen argument meegeven? Je kan altijd (vies!) nog een global variable met de pid laden en die dan in p4() weer gebruiken.

[ Voor 9% gewijzigd door Anoniem: 47102 op 25-05-2010 12:24 ]


Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 13:46

.oisyn

Moderator Devschuur®

Demotivational Speaker

dtech schreef op dinsdag 25 mei 2010 @ 12:22:
/dev/random is idd een aardig idee maar misschien wat overkill.
Voor /dev/random geldt natuurlijk exact hetzelfde. Het lost je probleem niet op - het is hoogstens een betere PRNG. Zelfs al is je RNG totaal en perfect random, er bestaat een kans dat je 100x achter elkaar hetzelfde getal eruit krijgt. Goed, die kans is erg klein, maar niet nonexistent.
Anoniem: 47102 schreef op dinsdag 25 mei 2010 @ 12:23:
[...]

Als de getallen perse verschillend moeten zijn moet je de twee threads toch echt met elkaar laten praten en bij gelijk zijn een ervan (bijv. child) opnieuw laten randomen.
Dat hoeft helemaal niet
dtech in "[C] Random getal in twee threads"
Als je in die code ervoor zorgt dat rand1 en rand2 altijd verschillend zijn voordat je forkt, dan hoeven ze niet met elkaar te praten.

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • H!GHGuY
  • Registratie: December 2002
  • Niet online

H!GHGuY

Try and take over the world...

De oplossing is al tal van keren voorbij gekomen:
C:
1
srand(time(NULL) + getpid());


Wat is er nog dat je tegenhoudt?

ASSUME makes an ASS out of U and ME


Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 13:46

.oisyn

Moderator Devschuur®

Demotivational Speaker

Wat is er nog dat je tegenhoudt?
Bijvoorbeeld het probleem dat ik al 2x in mijn post heb beschreven? Of wil jij beweren dat de eerstvolgende rand() call van twee van dat soort initialisaties gegarandeerd verschillende uitkomsten geeft?

[ Voor 38% gewijzigd door .oisyn op 25-05-2010 12:30 ]

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • dtech
  • Registratie: Juni 2005
  • Laatst online: 13-06 23:19
Ik bouw wel iets in dat foutcorrectie doet als de getallen hetzelfde zijn (het is voor een concept-netwerkprotocol dus daarom kunnen de processen niet vooraf met elkaar praten). Dankuwel iig.

@H!GHGuY

Dat er dan nog altijd een 1/n (waarbij n de range nummers is waaruit je kiest) kans is dat je hetzelfde nummer krijgt.

Acties:
  • 0 Henk 'm!

Anoniem: 47102

.oisyn schreef op dinsdag 25 mei 2010 @ 12:27:
[...]
Dat hoeft helemaal niet
dtech in "[C] Random getal in twee threads"
Als je in die code ervoor zorgt dat rand1 en rand2 altijd verschillend zijn voordat je forkt, dan hoeven ze niet met elkaar te praten.
Op twee voorwaarden: rand1 en rand2 zijn ongelijk (dus eigenlijk moet je een do{ rand2=rand()%8; }while(rand1==rand2); gebruiken) en dat de random getallen die gebruikt worden na seeden hiermee niet afgerond worden (met bijv. %8).
Het is dus afhankelijk van of de getallen gegarandeerd verschillend moeten zijn of niet.

@dtech: als het een netwerk protocol betreft kan je de twee partijen tijdens de handshake de getallen overeen laten komen (bij een client-server of producer-consumer model, moeilijker bij een h2h of p2p model). Je kan dan zelfs de ene een random getal aan de andere laten verstrekken.

[ Voor 17% gewijzigd door Anoniem: 47102 op 25-05-2010 12:34 ]


Acties:
  • 0 Henk 'm!

  • pedorus
  • Registratie: Januari 2008
  • Niet online
.oisyn schreef op dinsdag 25 mei 2010 @ 12:29:
Bijvoorbeeld het probleem dat ik al 2x in mijn post heb beschreven? Of wil jij beweren dat de eerstvolgende rand() call van twee van dat soort initialisaties gegarandeerd verschillende uitkomsten geeft?
Bij de meestvoorkomende implementatie van die rng is er een situatie mogelijk waarbij time() het verschil tussen de psid's verschuift. Als je time() achterwege laat, dan is die kans niet meer aanwezig, en kun je er van uitgaan dat je verschillende waardes krijgt, als je evenveel random numbers opvraagt aan beide rng's.

Voor de zekerheid kun je even een simpele rng toevoegen:
C:
1
#define CONG (jcong=69069*jcong+1234567)

Andere beginwaarde voor jcong leidt altijd tot ander resultaat, periode is 2^32, jcong is 32 bit unsigned.

Maar als het over meerdere machines gaat of om een ongelijk aantal opvragingen is dit natuurlijk vragen om problemen. Voor GUID's is voor 128 bits gekozen, en zelfs daar zijn problemen mee bekend (vanwege zeer veelvuldig gebruik en/of verkeerde generatiemethode). Je kan denk ik maar beter rekening houden met het 'onmogelijke'. :p

Vitamine D tekorten in Nederland | Dodelijk coronaforum gesloten


Acties:
  • 0 Henk 'm!

Anoniem: 47102

Als het hier betrekking heeft op een netwerk protocol, dat zul je bij twee losse applicaties geen last hebben van dit probleem: de kans dat je beide programma's tegelijk start is nihil, evenals de kans dat twee computers tot op de microseconde gelijke klokken hebben (m.u.v. gesynchroniseerde NTP klokken).

Acties:
  • 0 Henk 'm!

  • dtech
  • Registratie: Juni 2005
  • Laatst online: 13-06 23:19
@RoadRunner84

Ik draai echter ook simulaties waarboor er eerst een process geforkt wordt en die dan het protocol opstart, daarbij is het dus wel een probleem :)

Acties:
  • 0 Henk 'm!

  • dtech
  • Registratie: Juni 2005
  • Laatst online: 13-06 23:19
De netwerksimulator die ik gebruik werkt bij nader inzien met threads, niet met processes, ze hebben dus hetzelfde process ID. Weet iemand iets van een thread_id oid of zal ik gewoon lezen uit /dev/random?

Acties:
  • 0 Henk 'm!

Anoniem: 47102

dtech schreef op dinsdag 25 mei 2010 @ 13:27:
De netwerksimulator die ik gebruik werkt bij nader inzien met threads, niet met processes, ze hebben dus hetzelfde process ID. Weet iemand iets van een thread_id oid of zal ik gewoon lezen uit /dev/random?
Ik snap niet waar je heen wilt, je stopt nu twee "endpoints" in één proces, terwijl ze later niet eens op dezelfde machine draaien. Kan je niet veel beter direct via sockets de twee applicaties tegen elkaar laten praten, dat is een stuk meer in de buurt van het eigenlijke doel. Nu zit je feitelijk een probleem op te lossen dat er niet eens is in de praktijk.

Acties:
  • 0 Henk 'm!

  • pedorus
  • Registratie: Januari 2008
  • Niet online
Anoniem: 47102 schreef op dinsdag 25 mei 2010 @ 13:13:
Als het hier betrekking heeft op een netwerk protocol, dat zul je bij twee losse applicaties geen last hebben van dit probleem: de kans dat je beide programma's tegelijk start is nihil, evenals de kans dat twee computers tot op de microseconde gelijke klokken hebben (m.u.v. gesynchroniseerde NTP klokken).
Nee, het is niet zo alsof er soms vele computers met hetzelfde image tegelijkertijd worden opgestart met een druk op de knop. En er worden ook niet meer dan 1000 computers per seconde opgestart. En de resolutie van time(NULL) is in microseconden. Oh wacht... :+

In werkelijkheid is een van de limitaties van time(NULL) juist het beperkte stukje gebied dat je op een bepaalde dag kan terugkrijgen, en zeker geen voordeel. Overigens komt een RAND_MAX van slechts 32767 nog vaak voor.
dtech schreef op dinsdag 25 mei 2010 @ 13:27:
De netwerksimulator die ik gebruik werkt bij nader inzien met threads, niet met processes, ze hebben dus hetzelfde process ID. Weet iemand iets van een thread_id oid of zal ik gewoon lezen uit /dev/random?
Iets als gettid/pthread_self. /dev/random zou met zeer lage kans juist twee keer hetzelfde resultaat kunnen teruggeven, dus dat zou ik niet doen.. Wel realistischer, maar een test die met een kleine kans opeens niet slaagt is wat onhandig als die kans net uitkomt..

Vitamine D tekorten in Nederland | Dodelijk coronaforum gesloten


Acties:
  • 0 Henk 'm!

  • dtech
  • Registratie: Juni 2005
  • Laatst online: 13-06 23:19
Kijk, in de praktijk is dit (meestal) geen probleem, maar bij mijn simulatie wel. En aangezien ik toch wel wil simuleren is het voor mij wel een probleem.
Overigens praten ze dus wel via "sockets" (of eigenlijk, mijn implementatie daarvan) met elkaar, maar het probleem is dat je moet bepalen wie eerst data gaat versturen. Nu heb ik dat dus zo aangepakt dat ze beide een random getal genereren, en degene met het hoogste getal begint (ze versturen dit getal naar elkaar). Het probleem was dus alleen dat in 99% van de gevallen dit getal hetzelfde was tijdens mijn simulatie.

Acties:
  • 0 Henk 'm!

Anoniem: 47102

dtech schreef op dinsdag 25 mei 2010 @ 13:56:
Kijk, in de praktijk is dit (meestal) geen probleem, maar bij mijn simulatie wel. En aangezien ik toch wel wil simuleren is het voor mij wel een probleem.
Overigens praten ze dus wel via "sockets" (of eigenlijk, mijn implementatie daarvan) met elkaar, maar het probleem is dat je moet bepalen wie eerst data gaat versturen. Nu heb ik dat dus zo aangepakt dat ze beide een random getal genereren, en degene met het hoogste getal begint (ze versturen dit getal naar elkaar). Het probleem was dus alleen dat in 99% van de gevallen dit getal hetzelfde was tijdens mijn simulatie.
Dan doe je toch gewoon een "rock-paper-scissors" via netwerk? M.a.w.: je laat ze de getallen naar elkaar versturen, zijn ze gelijk dan laat je ze beiden een nieuw getal randommen en versturen. En dat herhaal je tot ze verschillend zijn.
Ik zeg nog steeds: maak 1 applicatie die je 2 keer start, een hoop van de problemen die je nu tegenkomt zijn dan weg en bovendien is de situatie realistischer voor je uiteindelijke doel.

Acties:
  • 0 Henk 'm!

  • dtech
  • Registratie: Juni 2005
  • Laatst online: 13-06 23:19
M.a.w.: je laat ze de getallen naar elkaar versturen, zijn ze gelijk dan laat je ze beiden een nieuw getal randommen en versturen. En dat herhaal je tot ze verschillend zijn.
Dat doe ik dus nu, maar als het random getal steeds hetzelfde is schiet je daar niks mee op. Daarom moest ik dus een ander random getal hebben voor beide threads, wat dus een probleem was aangezien time(NULL) steeds hetzelfde gaf.
Ik zeg nog steeds: maak 1 applicatie die je 2 keer start, een hoop van de problemen die je nu tegenkomt zijn dan weg en bovendien is de situatie realistischer voor je uiteindelijke doel.
Ik gebruik een kant-en-klare netwerksimulator (die bouw je ook niet even zomaar zelf), dus dat is geen optie.

Acties:
  • 0 Henk 'm!

Anoniem: 47102

dtech schreef op dinsdag 25 mei 2010 @ 14:17:
Ik gebruik een kant-en-klare netwerksimulator (die bouw je ook niet even zomaar zelf), dus dat is geen optie.
Je netwerk simulator is te perfect, in de praktijk zal de latency van pakketten varieren en daarmee ook het moment waarop een nieuw getal gerandommed wordt, dat nog los van het feit dat beide applicaties op verschillende momenten gestart worden. Daarnaast zal niet iedere host eenzelfde kloksnelheid hebben en zullen andere applicaties (in een multi-tasking omgeving) invloed hebben op het gedrag van je programma's.
Zorg ervoor dat je één of meer van deze imperfecties voor elkaar krijgt in je simulator, dan is je probleem in het geheel opgelost.

Wat is de code die je gebruikt om de "applicaties" te creeeren? Als je namelijk fork() gebruikt zoals in je startpost kan je dat gebruiken in je seed (de returnwaarde van fork is altijd anders voor het parent en child proces). Blijkbaar kan dit niet, hoe doe je dit dan?

Acties:
  • 0 Henk 'm!

  • pedorus
  • Registratie: Januari 2008
  • Niet online
dtech schreef op dinsdag 25 mei 2010 @ 13:56:
Overigens praten ze dus wel via "sockets" (of eigenlijk, mijn implementatie daarvan) met elkaar, maar het probleem is dat je moet bepalen wie eerst data gaat versturen.
Er is toch altijd een initiator van een connectie? Waarom laat je die niet gewoon bepalen wie begint?

Vitamine D tekorten in Nederland | Dodelijk coronaforum gesloten


Acties:
  • 0 Henk 'm!

Anoniem: 47102

pedorus schreef op dinsdag 25 mei 2010 @ 14:33:
[...]

Er is toch altijd een initiator van een connectie? Waarom laat je die niet gewoon bepalen wie begint?
Misschien gebruikt 'ie UDP, dan is er geen sprake van een connectie, maar inderdaad, er is er altijd eentje die begint.

Acties:
  • 0 Henk 'm!

  • MSalters
  • Registratie: Juni 2001
  • Laatst online: 18-06 11:36
Anoniem: 47102 schreef op dinsdag 25 mei 2010 @ 14:49:
[...]
Misschien gebruikt 'ie UDP, dan is er geen sprake van een connectie, maar inderdaad, er is er altijd eentje die begint.
Nee, grappig genoeg niet. Stel dat op t=0 beide zijden tegelijk beginnen, en op t=1 ontvangen beiden het bericht van de ander. Beiden denken dus dat zij als eersten zijn gestart. En sinds Einsteins relativiteitstheorie weten we dat beiden tegelijk gelijk kunnen hebben - tijd is bij uitstek relatief.

Voor de oplossing van dit probleem kun je naar de klassieke Ethernet algoritmes (Aloha, CD/MA) kijken. In dat geval kun je tot de conclusie komen dat dingen "relatief tegelijk" gebeurd zijn. De oplossing is dan "random wait and retry".

Man hopes. Genius creates. Ralph Waldo Emerson
Never worry about theory as long as the machinery does what it's supposed to do. R. A. Heinlein


Acties:
  • 0 Henk 'm!

Anoniem: 47102

MSalters schreef op dinsdag 25 mei 2010 @ 16:45:
[...]

Nee, grappig genoeg niet. Stel dat op t=0 beide zijden tegelijk beginnen, en op t=1 ontvangen beiden het bericht van de ander. Beiden denken dus dat zij als eersten zijn gestart. En sinds Einsteins relativiteitstheorie weten we dat beiden tegelijk gelijk kunnen hebben - tijd is bij uitstek relatief.

Voor de oplossing van dit probleem kun je naar de klassieke Ethernet algoritmes (Aloha, CD/MA) kijken. In dat geval kun je tot de conclusie komen dat dingen "relatief tegelijk" gebeurd zijn. De oplossing is dan "random wait and retry".
En we zijn weer terug bij het random (wait) probleem ;)
Nee, we hebben het over een practisch ssyteem, en practisch worden niet beiden tegelijk gestart, noch doen beiden er exact (tot op de klokcyclus) even lang over om het bericht van de ander te ontvangen.

Acties:
  • 0 Henk 'm!

  • G33rt
  • Registratie: Februari 2002
  • Laatst online: 22-06-2022
dtech schreef op dinsdag 25 mei 2010 @ 14:17:
[...]


Dat doe ik dus nu, maar als het random getal steeds hetzelfde is schiet je daar niks mee op. Daarom moest ik dus een ander random getal hebben voor beide threads, wat dus een probleem was aangezien time(NULL) steeds hetzelfde gaf.


[...]


Ik gebruik een kant-en-klare netwerksimulator (die bouw je ook niet even zomaar zelf), dus dat is geen optie.
Vergeet niet dat de kans dat zoiets ongelofelijk vaak gebeurt natuurlijk in de praktijk nihil is. Als die kans 0.125 is, is dat (1/8)n, wat voor jouw doeleinden voldoende snel afneemt! (1/8, 1/64, 1/512, 1/4096, 1/32768, 1/262144)

Overigens heb je dan wel een trade-off dat je nog steeds twee random getallen per iteratie moet genereren en PRNGs getallen laten genereren is bepaald het niet goedkoopste wat je kunt doen, maar dat kun je natuurlijk oplossen door slechts 1 random getal te genereren - als dat groter is dan 0.5 dan laat je het ene deel het werk doen, anders het andere (even los van de, hele valide, punten in de paar voorgaande posts). Dan is het ook niet erg dat het getal voor beide delen hetzelfde is (sterker nog, dat wil je dan graag).

Acties:
  • 0 Henk 'm!

  • pedorus
  • Registratie: Januari 2008
  • Niet online
MSalters schreef op dinsdag 25 mei 2010 @ 16:45:
Nee, grappig genoeg niet. Stel dat op t=0 beide zijden tegelijk beginnen, en op t=1 ontvangen beiden het bericht van de ander. Beiden denken dus dat zij als eersten zijn gestart. En sinds Einsteins relativiteitstheorie weten we dat beiden tegelijk gelijk kunnen hebben - tijd is bij uitstek relatief.
In dat geval kijk je gewoon naar het IP(v6)-adres. Hoogste wint. :p

Vitamine D tekorten in Nederland | Dodelijk coronaforum gesloten


Acties:
  • 0 Henk 'm!

  • H!GHGuY
  • Registratie: December 2002
  • Niet online

H!GHGuY

Try and take over the world...

@.oisyn: ik heb nu pas door dat niet het random zijn danwel het verschillend zijn belangrijkst is.

Tenzij je met quantum computing aan de slag gaat, kun je nooit garanderen dat de 2 cijfers verschillend zijn wanneer ze op verschillende plaatsen gegenereerd worden. Je kan ze hoogstens de kans in de praktijk zo klein mogelijk maken:
- /dev/random wordt op normale Linux systemen constant geseed met entropie op het toestel en eventueel daarbuiten gegenereerd. Het is dus een behoorlijk goeie RNG. Eventueel kun je een voldoende hoeveelheid karakters uitlezen en deze hashen tot een kleinere waarde.
- Je kan als extra entropie de waarde van de monotonic clock uitlezen. De tijd sinds boot zal gemakkelijk verschillend zijn.
- Op x86 kun je ook de timestamp counters van de CPU gebruiken als extra entropie bron.
- gettid(), getpid() en consorten geven nog een extraatje.

Voeg dit samen met wat je nu reeds hebt (het communiceren van de getallen en opnieuw genereren bij gelijkheid) en je hebt een systeem dat van zijn hele leven niet zo'n clash zal hebben + de zekerheid dat zulke clashes toch gedetecteerd en gecorrigeerd worden.

Op elk van die voorstellen heb je inderdaad de kans dat er alsnog gelijke waardes uitkomen, bvb 2 gelijke PC's met dezelfde software die op hetzelfde moment geboot worden kunnen dezelfde boot-time teruggeven.
Van /dev/random denk ik echter dat het quasi onmogelijk is dat opeenvolgende nummers oneindig lang (of lang genoeg om merkbaar te zijn) gelijk blijven.

It just doesn't get better than that.

edit:
als beide processen op dezelfde server draaien is het gebruiken van de monotonic clock (wel de HR variant met kernel optie high-res timers aan) met tijdelijke thread affinity op processor 0 voldoende. Er kunnen namelijk geen 2 processen tegelijk actief zijn op 1 logische processor en de kernel lost voor jou op dat er een volgorde ontstaat in het uitlezen van de time counters.

[ Voor 11% gewijzigd door H!GHGuY op 25-05-2010 21:35 ]

ASSUME makes an ASS out of U and ME


Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 13:46

.oisyn

Moderator Devschuur®

Demotivational Speaker

H!GHGuY schreef op dinsdag 25 mei 2010 @ 21:26:
Tenzij je met quantum computing aan de slag gaat, kun je nooit garanderen dat de 2 cijfers verschillend zijn wanneer ze op verschillende plaatsen gegenereerd worden.
Hoe helpt quantum computing dan? Je zou quantum entanglement kunnen gebruiken (dat is nog geen quantum computing overigens), maar dan moeten de deeltjesparen wel ooit op 1 plek zijn geweest, en in al die tijd mag je ze niet uitlezen. En daarna kun je 'm niet meer opnieuw gebruiken.
Je kan ze hoogstens de kans in de praktijk zo klein mogelijk maken:
- [...]
- MAC adres van de netwerkkaart

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

Anoniem: 47102

De geopperde oplossingen zijn nog steeds schijn. Zowel het MAC adres, IPv6 adres, timestamp, CPU serial number enzovoorts zijn gelijk in de kunstmatige omgeving die de TS gebruikt.
De oplossing is dus om een minder ideale omgeving te gebruiken, zoals het in de praktijk ook zal zijn.
Een workaround is de computer forceren om de ene als "eerste" en de andere als "tweede" te beschouwen (bijv. met de affinity die boven beschreven is). Je zou ook een arbiter proces kunnen draaien, die aan de eerst verbonden client zendrecht geeft. Die arbiter kan nooit tegelijk vna beiden een request verwerken, dus moet dit werken. Blijft dat het een workaround is om de nadelen van je verkeerde (te goede) simulatie te onderdrukken.

Acties:
  • 0 Henk 'm!

  • .oisyn
  • Registratie: September 2000
  • Laatst online: 13:46

.oisyn

Moderator Devschuur®

Demotivational Speaker

Waarom zouden dingen als MAC adres en IP adres van de verschillende "computers" in een netwerk simulator gelijk zijn?

Give a man a game and he'll have fun for a day. Teach a man to make games and he'll never have fun again.


Acties:
  • 0 Henk 'm!

  • H!GHGuY
  • Registratie: December 2002
  • Niet online

H!GHGuY

Try and take over the world...

.oisyn schreef op dinsdag 25 mei 2010 @ 22:45:
[...]
Hoe helpt quantum computing dan? Je zou quantum entanglement kunnen gebruiken (dat is nog geen quantum computing overigens), maar dan moeten de deeltjesparen wel ooit op 1 plek zijn geweest, en in al die tijd mag je ze niet uitlezen. En daarna kun je 'm niet meer opnieuw gebruiken.
Net zoals je zegt: door er net 1 uit te lezen wijzig je de eigenschappen. De 2de die uitleest krijgt dus iets anders te zien dan de eerste die uitleest. ;)
Het was eigenlijk meer figure of speech, maar blijkbaar kan het nog kloppen ook.

Ik denk dat mijn approach voldoende waterdicht is.
Je kan nooit of te nimmer zomaar garanderen dat 2 onlosmakelijk verbonden events (wat random poogt te zijn) plots toch verbonden zijn. Je moet dus een check inbouwen om conflict op te lossen en voldoende entropie voorzien om de kans op conflict te minimaliseren.

ASSUME makes an ASS out of U and ME

Pagina: 1