Product Design, Manufacturing & Innovation Resources
بيت » جدولة معدل أحادي (RMS)

جدولة معدل أحادي (RMS)

1973
  • C. L. Liu
  • James Layland
Computer workstation in a control room analyzing Rate-Monotonic Scheduling for real-time systems.

(صورة توضيحية فقط)

جدولة المعدل الرتيب (RMS) هي خوارزمية جدولة ذات أولوية ثابتة للمهام الدورية في نظام الوقت الحقيقي. تُحدد هذه الخوارزمية الأولويات بناءً على تكرار المهمة: فكلما قصرت فترة المهمة (أي زاد معدل تكرارها)، زادت أولويتها. تُعد RMS خوارزمية مثالية ذات أولوية ثابتة، بمعنى أنه إذا استطاعت أي خوارزمية ذات أولوية ثابتة جدولة مجموعة مهام، فإن RMS تستطيع ذلك أيضًا. ويمكن التحقق من قابلية الجدولة باستخدام اختبار قائم على الاستخدام. Traveling salesman problem applications also include sequencing jobs, a combinatorial task related to real-time scheduling. Scheduling theory, like the linear programming developed by Dantzig, aims for the best use of limited resources.

Rate-Monotonic Scheduling (RMS) is a cornerstone of real-time systems theory, introduced in a seminal 1973 paper by Liu and Layland. It provides a simple yet powerful method for scheduling a set of independent, preemptible, periodic tasks on a single processor. The core principle is to assign a fixed priority to each task inversely proportional to its period. A task that needs to run every 10ms will have a higher priority than a task that runs every 100ms.

تكمن أهمية خوارزمية RMS في مثاليتها ووجود اختبار جدولة بسيط. وقد ثبت أنها سياسة جدولة مثالية ذات أولوية ثابتة. هذا يعني أنه إذا أمكن جدولة مجموعة من المهام باستخدام أي خوارزمية ذات أولوية ثابتة، فإنه يمكن جدولتها أيضًا باستخدام خوارزمية RMS. يمكن تحديد قابلية جدولة مجموعة مهام باستخدام خوارزمية RMS من خلال اختبار حد الاستخدام. بالنسبة لمجموعة من n مهمة، فإن إجمالي استخدام المعالج U هو مجموع وقت التنفيذ Cᵢ مقسومًا على الفترة Tᵢ لكل مهمة i: U = ∑ᵢ₌₁ⁿ Cᵢ / Tᵢ. أثبت ليو ولايلاند أنه إذا كان إجمالي الاستخدام أقل من أو يساوي حدًا معينًا، [latex]U le n(2^{1/n}-1)[/latex]، فإن مجموعة المهام تضمن إمكانية جدولتها (أي لن يتم تفويت أي مواعيد نهائية). عندما يقترب ‘n’ من اللانهاية، يتقارب هذا الحد إلى [latex]ln(2) approx 0.693[/latex]. يوفر هذا شرطًا كافيًا، ولكنه ليس شرطًا ضروريًا، لإمكانية الجدولة. يمكن أيضًا استخدام اختبار أكثر دقة ولكنه أكثر تعقيدًا، يُسمى التحليل الدقيق أو تحليل زمن الاستجابة.

UNESCO Nomenclature: 1203
– Computer science

يكتب

Software/Algorithm

خلل

Incremental

الاستخدام

استخدام واسع النطاق

مقدمات

  • نظرية الطوابير
  • بحوث العمليات
  • الأعمال المبكرة حول خوارزميات جدولة الحاسوب
  • تطوير أنظمة التشغيل القائمة على المشاركة الزمنية

التطبيقات

براءات الاختراع:

NA

أفكار ابتكارية محتملة

  • schedulability analyzers for mixed-criticality systems
  • energy-efficient scheduling algorithms that adapt task rates
  • partitioned scheduling for multi-core real-time systems
  • adaptive rms for tasks with variable execution times in ai applications
  • network packet scheduling in time-sensitive networking (tsn) switches
  • resource reservation protocols for real-time cloud computing
  • compositional analysis frameworks for large-scale distributed real-time systems
  • probabilistic schedulability analysis for systems with uncertain execution times
  • security-aware scheduling to prevent timing-based side-channel attacks
  • co-scheduling of real-time tasks and non-real-time applications on a single processor
يتعلق بـ: جدولة المعدل الرتيب، RMS، أنظمة الوقت الحقيقي، خوارزمية الجدولة، الأولوية الثابتة، المهام الدورية، تحليل قابلية الجدولة، حد الاستخدام، liu وlayland، الجدولة المثلى.

السياق التاريخي

جدولة معدل أحادي (RMS)

1970
1970
1970
1973
1980
1980
1980
1970
1970
1970
1970-01-01
1975-06-01
1980
1980
1980

(إذا كان التاريخ غير معروف أو غير ذي صلة، على سبيل المثال "ميكانيكا الموائع"، يتم توفير تقدير تقريبي لظهوره الملحوظ)

أحدث الإضافات

أهم المنشورات والمقالات

أفضل الأدوات الأصلية

السنة العاشرة عيد

الصور والتنزيلات بالحجم الكامل متاحة فقط، ومجانية تمامًا، للأعضاء المسجلين.