كيفية زرع srand () لتجنب الاصطدام بعدد كبير من الأجهزة؟

Question

عادة، يتم البذر من srand() عن طريق:

srand(time(NULL));

في حالتي، أستخدم أرقامًا عشوائية لإنشاء معرف لعملية العميل الخاصة بي في وقت التشغيل على الشبكة.تتم إعادة تشغيل العملية أحيانًا وإنشاء معرف جديد.مع زيادة عدد العملاء، هناك فرصة جيدة أن يتصل عميلان srand(time(NULL)) في نفس الثانية، مما يؤدي إلى إنشاء معرفين متطابقين، أو حدوث تصادم كما يراه جانب الخادم. اقترح بعض الناس حلاً أفضل:

srand((time.tv_sec * 1000) + (time.tv_usec / 1000));

لكن المشكلة هنا هي أن البذرة ستتكرر كل 24 يومًا أو نحو ذلك، وعندما يكون عدد الآلات كبيرًا بدرجة كافية، لا تزال هناك فرصة للاصطدام. هناك حل آخر:

srand(time.tv_usec * time.tv_sec);

ولكن هذا يبدو مشكلة بالنسبة لي أيضًا لأن معامل هذا المنتج (البتات الأعلى تفيض ويتم التخلي عنها) لا يتم توزيعه بالتساوي ضمن نطاق unsigned int قيمة البذور.على سبيل المثال، لكل ثانية، time.tv_usec == 0 يؤدي إلى نفس البذرة.

فهل هناك طريقة لبذر srand() في حالتي؟

يحرر:يعمل العميل على Linux وWindows وAndroid وiOS /dev/random أو /dev/urandom ليس متاحا دائما.

ملاحظة.أنا على دراية بنهج GUID/UUID، ولكني أرغب في معرفة ما إذا كان من الممكن زرع srand() بشكل صحيح في هذه الحالة.

Answer 1

لديك مجالين:العملاء والعمليات.لذلك تحتاج إلى معرف فريد لكل واحد.من الواضح أنه يمكن إجراء العمليات باستخدام معرف العملية.بالنسبة للعملاء، أقترح استخدام عنوان MAC، الذي يجب أن يكون فريدًا لكل واجهة شبكة.أعتقد أن جميع الأنظمة الأساسية التي أدرجتها تدعم المقابس، لذا قد يكون SIOCGIFHWADDR ioctl مدعومًا.

المشكلة الوحيدة هي أن عناوين MAC هي 48 بت، ومعرفات PID عادةً ما تكون 32 بت، لذلك يتعين عليك اختيار أعلى بتات إنتروبيا من القيمتين لاستخدامها في بذرة السلسلة الخاصة بك.أقترح الـ 16 بت الأقل من PID والـ 16 بت الأقل من عنوان MAC.

Answer 2

srand و rand ببساطة غير مناسبة إذا كان لديك الكثير من العمليات أو سلاسل الرسائل التي تحتاج إلى عشوائية زائفة مستقلة فيما بينها.

في أنظمة POSIX، يمكنك استخدام rand48 عائلة من الوظائف مثل jrand48 التي عرفت حجم الدولة.إذا كنت تعتمد على استقلالية العملية والخيط والجهاز، فيجب عليك استخدام وحدات البت المهمة من معرف العملية ومعرف الخيط وعنوان IP والوقت لتهيئة الحالة. jrand[48] يأخذ (ويعدل) حالة الثلاثة short, ، لذلك يجب أن يكون من السهل نسبيًا زرعها بكميات مختلفة.

جميع الأنظمة التي قمت بإدراجها باستثناء نظام واحد هي POSIX، لذلك يجب أن يعمل هذا هناك.لا أعرف ما هو البديل المناسب لأنظمة Windows.

Answer 3

إذا لم يحدث أي تصادم بين مولدين للأرقام العشوائية، فهما ليسا عشوائيين.سيكون الأمر أشبه بلعب لعبة "Snap" ولكن لن تحصل على أي مباراة أبدًا.

لذا، ما تريده هو مولد أرقام عشوائية أسوأ، وليس أفضل.يعد استخدام المعرفات الفريدة العمومية (GUIDs) أحد الأساليب التي من شأنها أن تزيل المشكلة تمامًا بالنسبة لك.

ولكن، إذا كنت سعيدًا فقط بتقليل فرصة حدوث التصادمات، فبدلاً من القضاء عليها تمامًا، يمكنك استخدام عنوان IP الخاص بالجهاز (أو الرقم التسلسلي للمعالج، أو شيء من هذا القبيل) كجزء من البذرة.

Answer 4

إذا كنت تكتب لمنصة Linux، فاستخدم /dev/random و /dev/urandom للحصول على أرقام عشوائية.على عكس srand(), /dev/random و /dev/urandom يستخدم الضوضاء الناتجة عن الأجهزة الطرفية لإنشاء أرقام عشوائية. srand() يستخدم البذور المتوفرة كوسيطة لإنشاء رقم عشوائي.

Answer 5

أعتقد أنك ستكون مهتمًا بمقالة "الأرقام العشوائية المتوازية:سهلة مثل 1، 2، 3".

نقلا عن الملخص:"تجتاز جميع PRNG لدينا اختبارات إحصائية صارمة (بما في ذلك BigCrush الخاص بـ TestU01) وتنتج ما لا يقل عن 264 تدفقًا متوازيًا فريدًا من الأرقام العشوائية، كل منها بفترة 2128 أو أكثر"