هناك نوعان من هياكل البيانات المعروفة لأي مبرمج والتي تعتبر بديهيات بحيث لا أحد يحاول حتى تحليل ما إذا كانت هناك حاجة إليها ، وما إذا كان هناك أي فائدة منها وما إذا كان هذا الضرر لا يتجاوزها.
قائمة الانتظار
بادئ ذي بدء ، سوف نناقش قائمة الانتظار. ما معنى الطابور؟ قائمة الانتظار عبارة عن مخزن مؤقت. ومتى نحتاج إلى حاجز؟ عندما لا يكون لدينا الوقت لمعالجة الأحداث الواردة بوتيرة وصولهم.
فيما يتعلق بما سبق ، ينشأ سؤال واحد: لماذا؟ الإجابة هي أننا نأمل أن يحدث شيء ما وفجأة سيسمح لنا النظام بمعالجة الأحداث.
أولاً ، دعنا نتعامل مع الفقرة الأولى. ما الذي يجب أن يحدث للنظام ، حيث يتوقف فجأة عن الكبح ويبدأ في هضم البيانات بشكل أسرع؟ على الأرجح ، ستنهي بعض العمليات كثيفة الموارد ببساطة وتحرر الموارد. ولكن ماذا لو لم يحدث هذا؟ ماذا تفعل بالبيانات؟ من المعروف أن: إما أن نعيد ضبطها فقط ، أو أن النظام بأكمله يتوقف فقط بسبب نقص الموارد.
بطة ، هناك سؤالان:
- ولماذا لا يمكنك إسقاط البيانات على الفور إذا علمنا أنه ليس لدينا الموارد اللازمة لمعالجتها؟ هذا هو السبب في أنه من المستحيل إنشاء قائمة انتظار من عنصر واحد؟
- أو السؤال العكسي. لماذا لدينا أوهام ولا نزود النظام بالكمية اللازمة من الموارد لمعالجة البيانات بمعدل الاستلام؟
إن الإجابات على هذه الأسئلة واضحة في الواقع. نحن ببساطة لا نعرف كيفية تصميم أنظمة البرامج والأجهزة. لأنه إذا كنا نعرف كيفية تصميمها ، فسوف نعرف مقدار البيانات المدخلة لدينا ، ومعدل استلامها ، وكم نحتاج إلى معالجتها ، وبالتالي يمكننا حساب الحاجة الحقيقية للموارد. لكن الوضع الحالي لأدوات ومنهجيات تطوير تكنولوجيا المعلومات والاتصالات ، باستثناء جزء من الأنظمة التكنولوجية (وليس جميعها على الإطلاق) ، لا يسمح لنا بإجراء حسابات موضوعية لمتطلبات الموارد.
ونغلق هذه العيوب مع جميع أنواع المخازن المؤقتة ، على وجه الخصوص ، في شكل قوائم انتظار. نتيجة لذلك ، لدينا قنبلة وضعت في أساس المبنى حتى على مستوى الحفرة ، لأن هذه العكازات بمثابة مصدر لمختلف الاحتقار وصعوبة استيعاب المشاكل مع الموثوقية والأمان وببساطة جودة العمل.
ولكن ، دعنا نستمر ، أمامنا أكثر الهياكل المفضلة لدي - المكدس!
المكدس
هذا أمر مؤكد ، كما قال Hoar ذات مرة عن Null ، أن هذا خطأ مليار دولار ، لذلك يمكن قول الشيء نفسه عن المكدس.
هذا هو واحد من أكثر الهياكل إشكالية المستخدمة في تكنولوجيا المعلومات والاتصالات وتجنبه الأقصى في ممارسة إنشاء الأجهزة والبرامج ، حتى الاستئصال الكامل ، أمر مرغوب فيه للغاية.
إذن ما هي بالضبط مشكلة المكدس؟ نعم ، تمامًا كما هو الحال في قائمة الانتظار. المداخن من المستحيل بشكل أساسي ترتيبها. بمجرد أن يكون هناك شخص يتنبأ بدقة مقدار الذاكرة التي يحتاجها أي برنامج تعسفي ، أعتذر شخصيًا وأكتب مقالًا ضخمًا كنت مخطئًا وأطلب الصفح.
لكن شيئًا ما يخبرني أنه من غير المحتمل أن يحدث هذا في المستقبل المنظور.
دعونا نحلل لماذا نحتاج إلى مكدسات؟ نعم ، بالضبط نفس الشيء ، الذي في قائمة الانتظار. هذا عازلة. أي أنها عكازات لعقل كسول لا يريد تصميم أنظمة البرامج والأجهزة بشكل صحيح.
لذا فإن الدرس هو هذا: يجب تجنب التكرارات عندما يكون هناك حل تكراري واضح. ومع ذلك ، هذا لا يعني أنه يجب التخلص من عمليات التكرار بأي ثمن. هناك العديد من الأمثلة الجيدة لاستخدام العودية ، والتي سنوضحها في الأقسام والفصول اللاحقة. حقيقة أن هناك تطبيقات لإجراءات العودية على الآلات غير العودية تقريبًا تثبت أنه لأغراض عملية يمكن تحويل أي برنامج عودي إلى برنامج تكراري بحت. ومع ذلك ، يتطلب هذا عملًا صريحًا مع حزمة العودية ، وغالبًا ما تحجب هذه الإجراءات جوهر البرنامج بحيث يكون من الصعب فهمه. الخلاصة: الخوارزميات العودية ذات الطبيعة غير التكرارية تحتاج إلى صياغة كإجراءات عودية.
نيكلاوس ويرث. الخوارزميات وهياكل البيانات
أتفق مع السيد حول خيارات التحويل ، أنا لا أتفق مع نهجه الناعمة لاستخدام المكدس.
طرحت نظرية: يمكن تحويل أي خوارزمية مكدس إلى حلقة ، وتلك التي لا يمكن تحويلها سيئة.
يجب إيقاف ممارسة استدعاء البرامج الفرعية ذات المعلمات المارة من خلال المكدس ، ويجب أن يذهب هناك أيضًا العودية التي لا تتوسع في الحلقة والممارسات الأخرى المستخدمة على نطاق واسع.
يمكننا استبدال المكدس للحالات التالية:
- العودية ، تنفذ في شكل توسيع خوارزمية المكدس إلى حلقة مع كتلة من البيانات التي يتم تغييرها أثناء تنفيذ الحلقة.
- إذا كنت بحاجة إلى نقل المعلمات ، فستنظم نظامًا للبرامج الثابتة مع المراسلة. وحول المراسلة ، نذهب إلى السطور التي تم وصفها في الجزء الأول من المقالة. إذا كنت ترغب حقًا في تكديس ، فمن الواضح أنه لا يجب عليك دفع عشرات ومئات الكيلوبايت من الكائنات هناك ، ولكنك تحتاج إلى تخصيص ذاكرة لهذا بشكل طبيعي ، في كومة الذاكرة المؤقتة.
في نفس الوقت ، في المستوى الأعلى ، يمكن للمبرمجين استخدام أي هياكل بيانات ، والأمر متروك للمترجمين لتحويلها بحيث يتم استبعاد استخدام المكدس.
بالطبع ، ربما تضيع بعض الفرص ، ولكن هذا إذا تم النظر فيه بالتفصيل ، فإنه ليس حقيقة.
بلوكوت
في عام 1995 ، مع زميلي في الصف ، قمت بصياغة مبادئ بناء نظام تشغيل يستبعد كلا هذين النموذجين.
كانت المبادئ على النحو التالي:
- البرمجيات - شبكات العمليات التفاعلية.
- يتم تفاعل العمليات من خلال تبادل الرسائل.
- يتم تنظيم شبكة عمليات التفاعل على النحو التالي: مصادر الرسائل الأساسية في هذه الشبكة ليست سوى أحداث من العالم الخارجي يتم توفيرها بواسطة المعدات ، والمستهلكون النهائيون للرسائل هم فقط الأجهزة التي تؤدي إجراءات في العالم الخارجي. أي أن الشبكة تبدأ في العالم الحقيقي وتنتهي بها.
- لا يمكن أن يكون للعمليات أولويات. يمكن أن تحتوي الأولويات على شبكة من العمليات فقط.
- لا تقوم الشبكة بتخزين الرسائل مؤقتًا. يجب تنظيم مجمع برمجيات الأجهزة بطريقة تمكنها من معالجة الرسائل بوتيرة استلامها من العالم الخارجي.
- مجمع الأجهزة عبارة عن شبكة من عقد الحوسبة المتصلة بقنوات الاتصال.
- لكل عقدة "تكلفة" ، اعتمادًا على قوة معالجتها وحجم الذاكرة وعامل التحميل والوزن ، مع مراعاة تكاليف إنشائها وصيانتها.
- لكل قناة اتصال "تكلفة" ، اعتمادًا على عرض النطاق الترددي والازدحام ومعامل الوزن ، مع مراعاة تكاليف إنشائها وصيانتها.
- يوفر نظام التشغيل بدء العمليات استجابة للرسائل الواردة وتوجيه الرسائل.
- يضمن نظام التشغيل توزيع العمليات والرسائل بين عقد الحوسبة ، مما يحسن الوظيفة f (cpu ، mem) على هيكل الشبكة ، مع مراعاة تكلفة إرسال رمز العملية والرسائل إلى العقدة.
- بالنظر إلى بناء النظام ، يمكنك دائمًا حساب مقدار الذاكرة المطلوب للعملية بدقة . يمكن حساب مقدار الوقت المطلوب للعد بدقة بناءً على تحليل الخوارزمية.
معالج BIND
كجزء من مهنته في التدريس ، مع الطلاب ، شارك مرة واحدة في مسابقة IEEE CPU emulator. تم تطوير معالج غير مكدس للأغراض العامة من بنية جامعة هارفارد باستخدام نظام أوامر مشابه لأجهزة ARM السابقة. بالإضافة إلى ذلك ، تم دمج الفكرة المنسية عن الناقلات في وحدة المعالجة المركزية وتم تجهيز المعالج بـ 16 قناة إرسال واستقبال 8 بت.
وبالتالي ، لم تكن هناك عمليات اتصال / رد في المعالج. فقط كان الانتقال مشروط / غير مشروط ممكن. بالنظر إلى أنه لا أحد يكتب في المجمّع تقريبًا في الوقت الحالي ، كان من المفترض أن يتم تعيين جميع الأسئلة المتعلقة بإنشاء برنامج في رمز الآلة إلى المترجم.
كان الهدف الرئيسي من هذا المعالج هو دعم مبادئ نظام Blockout OS على مستوى الأجهزة بسلاسة من خلال إنشاء شبكة من المعالجات في عقدة الحوسبة المحلية المتصلة بقنوات الاتصال التي سيتم بالفعل توزيع العمليات عليها.
الاستنتاجات
يُظهر النص العيوب المميتة لهياكل البيانات في قائمة الانتظار والمكدس. يتم إعطاء مبادئ تصميم أنظمة البرامج والأجهزة التي تسمح باستبعاد هذه الهياكل من ممارسة التطبيق.
هذا النص ، بالأحرى ، هو مجموعة من الأفكار التي حدثت طوال فترة العمل في مجال تكنولوجيا المعلومات ، إذا جاز التعبير ، لتقليل كل شيء في مكان واحد.