نموذج إدارة البرنامج الآلي

1. مقدمة

في [1] ، تم تقديم إجابة على السؤال حول ما يعتبر البرمجة التلقائية (AP) ، لكن نموذج آلة الحالة المحدودة (SC) لم يتم وصفه بالتفصيل كنموذج تحكم للبرامج التلقائية. من الواضح أن التطبيق التلقائي المجرد النقي ليس مناسبًا لهذا الدور ، لأن محدودة بعدد القنوات. لكن النموذج الهيكلي للأوتوماتون ، وكذلك نظرية الأوتوماتيكية الهيكلية المقابلة له ، لا تسمح حتى الآن بإعطاء إجابة على اختيار نموذج الأوتوماتون.

تبدأ المشكلة بحقيقة أنه من بين العديد من الأعمال في نظرية الأوتوماتية المحدودة (TCA) ، هناك القليل من الأعمال التي تقدم تعريفًا لنموذج الأوتوماتيكي الهيكلي المحدود (SCA). صحيح ، يمكن للمرء أن يفهم أن الأوتوماتون الهيكلي هو مخطط [هيكلي] للأوتوماتة الأولية (العناصر الوظيفية) التي تنفذ نموذجًا لأوتوماتون مجردة [2]. تذكر أنه ، وفقًا للنظرية ، يبدأ كل شيء في إنشاء نموذج جهاز في شكل آلية تلقائية مجردة ، ثم تتمثل المهمة في تجميع دائرة رقمية تنفذها [3].

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

صحيح أن السؤال منطقي على الفور - لماذا هناك "مجموعة أدوات تلقائية" إضافية وغير عادية؟ سنحاول الإجابة على هذا السؤال من خلال تحديد نموذج للتحكم التلقائي [المتداخل] ، مع الأخذ في الاعتبار مزاياه مقارنةً بنموذج البرمجة المعتاد.

2. تعريف نموذج التحكم للبرامج الآلية

في عملية التطور ، شكلت ممارسة البرمجة متطلبات معينة لنموذج إدارة البرنامج. يجب أن ندرك أن نموذج آلة الحالة المحدودة الكلاسيكية يتوافق معها قليلاً. وإذا كانت المهمة هي استخدام الأتمتة في البرمجة ، فيجب تكييفها. من المستحسن القيام بذلك في إطار نظرية الأتمتة. يتم تقليل المطالبات الرئيسية إلى AP الموجودة إلى حقيقة أن هذا الشرط قد انتهكت.

التعريف 1. نطلق على الشكل العادي المفصل من الأوتوماتة المحدودة (DNKA) الأوتمات المحدودة المحددة تمامًا والتي تحمل علامات انتقالاتها عن طريق الارتباطات الأولية للمتغيرات المنطقية.

يعتمد نموذج الحمض النووي على نماذج رسمية لأوتوماتة محددة بالكامل (كاملة) مع حالة مجردة [4] وأتمتة منطقية [5].

التعريف 2. نحن نسمي الشكل المنفصل للأوتوماتون المحدود (DFA) بأنه آلي في شكل DFA يحتوي على انتقالات ناتجة فقط.

يتم تصنيف التحولات المميزة بإشارات الخرج والانتقالات بشرطة بدلاً من إشارات الخرج التي تغير الحالة الحالية للأوتوماتون على أنها انتقالات فعالة. تشكل التحويلات غير المضمنة في وصف الأوتوماتيكية المنفصلة إضافة DKA (DDA) إلى آلية DFA المعرفة بالكامل. مثل هذه الإضافة هي آلية تلقائية تتكون من حالات معزولة ذات انتقالات في شكل حلقات وبشرطات بدلاً من إشارات الخرج.

3. طراز الذاكرة لنموذج الحساب AP

وجود العديد من المدخلات والمخرجات من DFA يحدد التوازي بين مشغلي / وظائف البرمجيات المرتبطة به. لتنفيذه الصحيح ، مطلوب نموذج ذاكرة من نوع CREW (متزامن للقراءة حصرية - كتابة) [6]. ضمن إطارها ، يُسمح بقراءة قيم البيانات الحالية من جانب مجموعة من جميع الوظائف (المسندات والإجراءات) ، ولا يُسمح إلا لواحد منها بتغيير البيانات العامة لإجراءات قابلة للتنفيذ موازية.

طراز التحكم التلقائي ، على عكس طراز الحوسبة متعددة الخيوط ، يحد بوضوح من تنفيذ المشغلين / وظائف البرنامج التلقائي إلى حدود دورة زمنية منفصلة. في مثل هذه الحالة ، يمكن كتابة أي تغييرات تطرأ على الذاكرة بسبب الإجراءات التي يتم إجراؤها على دورة الساعة الحالية على "ذاكرة الظل" ، بحيث تصبح هذه القيم الجديدة بعد اكتمالها وقبل بدء دورة الساعة المنفصلة التالية.

سوف يطلق على تفاعل مشغلي برنامج التشغيل الآلي مع الذاكرة نموذج ذاكرة الظل . هذا النموذج هو جزء أساسي من النموذج العام للبرمجة التلقائية. إنه يضمن صحة التشغيل المتوازي لمشغلي AP ويبسط برمجة العمليات المتوازية.

في إطار نموذج الذاكرة ، ليست هناك حاجة إلى آليات معقدة وغير موثوقة للغاية لمزامنة العمليات المتعددة الخيوط (لمزيد من التفاصيل ، انظر [7]). لكن إذا لزم الأمر ، فنظرًا لمعادلة الأوتوماتة ومخططات الرسم البياني للخوارزميات (GAW) [8] ، فإن نموذج البرمجة التلقائي لا يحد من تطبيقها.

4. نماذج متداخلة والقصور الذاتي من automata

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

لذا ، فليكن مهمة إنشاء نموذج منفصل لعنصر منطق التأخير الذي يقوم بتنفيذ إرسال إشارة إدخال ثنائية. علاوة على ذلك ، لا تتزامن أوقات التأخيرتين t01 و t10 ، على التوالي ، إلى الوحدة والصفر في الحالة العامة.

يظهر أبسط نموذج للتأخير الفردي في شكل Mealy automaton في الشكل. 1 (انظر ، للمقارنة ، نموذج التأخير في [2]). يتم تحديد التأخير من خلال دورة واحدة على مدار الساعة منفصلة. يتم تقديم نماذج أكثر تعقيدًا من تأخيرات النقل (لمزيد من التفاصيل حول أنواع التأخيرات ، انظر [9]) في شكل Miley automaton ونموذج Miley-Moore مدمج ، على التوالي ، في الشكل. 2 أ والتين. 2B.


التين. 1. نموذج تأخير وحدة في شكل آلي مايلز


التين. 2. نموذج تأخير النقل للمايلز (أ) ومايلز مور (ب)

إشارة الدخل x3 (نذكر أنه في البرنامج التلقائي يتوافق مع المسند [1]) تأخذ قيمة حقيقية إذا كانت قيمة عداد الساعة مساوية لقيمة المتغير t مساوي للتأخير t01 أو t10. يتم تعيين قيمة المتغير t للإشارات y3 و y4 (في البرنامج ، وظائف الإجراء التي تحمل نفس اسم إشارات الإخراج). تقوم الإشارات y1 ، y2 بتعيين قيمة المتغير الذي يمثل ناتج النموذج. الإشارة y5 تزيد من عداد الساعة ، والذي تتم إعادة تعيينه بواسطة الإشارة y6.

ملاحظة 2. الحالات الداخلية للنموذج في الشكل. 1 ، أنها مريحة للربط مع حالة إخراج عنصر. هذا يسمح لنا باستبعاد ليس فقط مشغلي y1 و y2 ، ولكن أيضًا متغير المتغير نفسه.

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

التعريف 3. يطلق على الأوتوماتة المتداخلة "الأوتوماتا المتداخلة" بالحالة النهائية ، والانتقال الذي يبدأ فيه إجراء العودة إلى المستوى السابق (رتبة) التعشيش.

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


التين. 3. تأخير نموذج في شكل أوتوماتيكي المتداخلة

يوضح الشكل 3 نموذج التأخير ، حيث يمثل الشكل 3 أ نموذج المستوى العلوي والشكل 3 ب والشكل. 3c - بدائل من الأوتوماتة المتداخلة للنقل والتأخير بالقصور الذاتي (لمزيد من التفاصيل حول أنواع التأخير ، انظر [8]). في الوقت نفسه ، هذه أمثلة على نوعين من الأوتوماتيكية المتداخلة - العادية والقصور الذاتي . يتم تعريف نوع الإضافات التلقائية المتداخلة باسم حالاته النهائية: الدولة التي تحمل الاسم "00" تحدد الخروج المعتاد من الأوتوماتون المتداخل ، والحالة التي تحمل الاسم "XX" لا تغير الحالة الحالية لأتمتة المستوى الأعلى.

تفسيرا هاما لفهم خوارزمية التأخير بالقصور الذاتي. بالنسبة له (انظر الشكل 3 ج) ، فإن قيمة المسند x1 تعتمد على الانتقال الذي يتم فيه إنشاء الإضافة التلقائية المدمجة. بمعنى آخر ، يتحكم المسند في الحالة "0" في الحفاظ على "صفر" عند الإدخال ، وفي الحالة "1" ، على العكس ، "الوحدات". إذا كانت القيمة عند الإدخال تساوي صفرًا عند قيمة الصفر للإخراج ، فأنت بحاجة إلى إرجاع القيمة الحقيقية. علاوة على ذلك ، إذا تم انتهاك استقرار الإدخال (القيمة x1 خاطئة) ولم ينته وقت التأخير (القيمة x3 خاطئة) ، فسيتم الخروج من الجهاز المضمن من خلال حالة القصور الذاتي (انظر الشكل 3 ج).

التعريف 4. سيتم استدعاء Automata ، بما في ذلك استدعاء automata المتداخلة التي لها حالة بالقصور الذاتي النهائي ، automata بالقصور الذاتي .

في النموذج الموضح في الشكل 3 أ ، يُنشئ الإجراء z1 (الرمز z لأسماء الإجراءات التي تتضمن استدعاءًا إلى آلية تلقائية متداخلة) آلية تلقائية متداخلة إذا تم تحديد قيمة تأخير. كجزء من هذا الإجراء ، يتم تحديد نوع التأخير المحدد ، والذي يتم وفقًا إنشاؤه إنشاء أحد الأوتوماتة المتداخلة ، كما هو موضح في الشكل. 3C.

في المستوى الأعلى من التسلسل الهرمي ، يتزامن عرض الأوتوماتون في الشكل 3 أ تمامًا في الهيكل مع النموذج في الشكل 1 ، ويختلف فقط في وجود الإجراءات على التحولات. يكون للتأخيرات ذات الأوتوماتيكية المتداخلة شكل أبسط مقارنةً بالطراز أحادي المستوى في الشكل 2. يمكن أيضًا اعتبار الإضافة التلقائية المتداخلة كنوع من "مكتبة الأوتوماتون" التي يمكن استدعاؤها من أي آلية أخرى.

3. برمجة كائن آلي

يحتوي نموذج التحكم التلقائي ، بالإضافة إلى نموذج الرسوم ، أيضًا على شكل جدول بسيط - جدول انتقالي (TP) ، والذي يمكن تفسيره بشكل فعال في C ++. في إطاره ، يمكن تمثيل برنامج آلي تلقائي (أو جزء منه) ، وبالتالي ، يمكن تعريفه في شكل دائرة برنامج S بواسطة فئة. في هذه الحالة ، سوف تتوافق نماذج الذاكرة مع خصائص الفئة ، ومجموعة العمليات سوف تتوافق مع أساليب الفئة ، وسيصف التحكم التلقائي في شكل TP سلوك الفئة. يسمح لنا إدخال التحكم في الفصل بالتحدث عن الكائنات النشطة ، والتي تسمى أيضًا العوامل في الغالب ، إلخ.

تضفي العديد من الكائنات التي لها سلوك في شكل التحكم الآلي رسميًا مفهوم البرنامج الموازي للكائن التلقائي . في هذه الحالة ، يمكن تمثيل نموذج أي برنامج متوازي بواسطة مخطط برنامجي حيث سيتم تقديم التحكم C في شكل شبكة آلية ، حيث تصف المكونات التلقائية سلوك الكائنات النشطة ، وتمثل الذاكرة M بمزيج من خصائص الكائنات ، ويتم تمثيل العديد من العوامل A بمجموعة من أساليب كائنات البرنامج.

في بيئة VKPA ، يتم تعيين دور لغة البرمجة التلقائية للغة C ++. في "C ++ التلقائي" ، يتم منح الكائنات النشاط / السلوك ولديها وسائل لوصف وتنفيذ التوازي ، على مستوى أساليب الكائنات الفردية وعلى مستوى وصف التشغيل المتوازي للعديد من الكائنات.

تطبيقات كائن موجود من AP معقدة إلى حد ما. في VKPa ، يعتمد تطبيق الكائنات على تفسير الأتمتة والتحكم المخصص في البرنامج. على عكس التنفيذ المباشر للأوتوماتة ، المستخدم ، على سبيل المثال ، في تقنية SWITH ، فإن هذا يلغي الإجراء لتحويل نموذج الأوتوماتون إلى نموذج مخطط انسيابي. تشبه خوارزمية التفسير المستخدمة في VKPa طريقة تفسير جداول القرارات بواسطة E. Hamby [12].

ما لم ينص على خلاف ذلك ، سنربط مفهوم برنامج التشغيل التلقائي بمفهوم كائن التشغيل التلقائي (AO) بمعنى OOP ، ولكن مع الأخذ في الاعتبار مفهوم برنامج التشغيل المتوازي للكائن التلقائي المقدم أعلاه. نتيجة لهذا ، سيتم تحديد عوامل تشغيل وذاكرة AP من خلال أساليب وخصائص الكائنات النشطة. يتم تمييز كائنات Automata عن الكائنات العادية من خلال وجود سلوك يحدده طراز آلة الحالة.

4. الاستنتاجات

يعد إنشاء نموذج للأتمتة المتداخلة خطوة نحو تغيير نوعي في تقنية البرمجة. يشبه نموذج القصور الذاتي الموصوف للأوتوماتون مفهوم الحالات التاريخية في UML. التضمين المعتاد للأوتوماتة لديه تناظرية في البرمجة ، "التضمين بالقصور الذاتي" لا يحتوي عليه ، لأن في البرنامج ، لا يمكنك العودة إلى أمر يسبق مكالمة روتين فرعي. وهذه هي عناصر الاختلاف النوعي بين البرمجة التلقائية والبرمجة العادية.

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

الكائنات النشطة أيضا توسيع قدرات البرمجة. لكن "مجمّع الكائنات" ، من جانبه ، يؤثر نوعيًا على البرمجة التلقائية ، ويبسط إجراءات استدعاء وتطبيق الأوتوماتية المتداخلة. لذلك ، يتيح لك استخدام خصائص الفئة [المحلية] تطبيق ليس فقط التضمين ، ولكن أيضًا أي خوارزميات متكررة.