"टकराव" की न्यूनतम संख्या प्राप्त करने के समय प्रक्रियाओं को कैसे प्रसारित करें

Question

मैं एक एम्बेडेड सिस्टम के लिए शेड्यूलर विकसित कर रहा हूं। यह शेड्यूलर प्रत्येक एक्स मिलीसेकंड प्रत्येक प्रक्रिया को कॉल करेगा; इस समय, प्रत्येक प्रक्रिया के लिए अलग-अलग कॉन्फ़िगर किया जा सकता है।

सब कुछ कोड किया गया है और इसे हर प्रक्रिया को कॉल करना चाहिए; समस्या मैं का सामना करना पड़ रहा हूँ यह है: कल्पना कीजिए मैं 4 प्रक्रियाओं सेट हर 10, 15, 5 और 30 मिलीसेकंड क्रमशः के नाम से जाना:

A: 10ms 
B: 15ms 
C: 5ms 
D: 30ms 

समय के साथ बुला हो जाएगा जिसके परिणामस्वरूप:

     A   | 
     A B A  B   | 
    C C C C C C C  | processes being called 
         D   | 
---------------------------------- 
0 5 10 15 20 25 30 35... ms 

समस्या यह है कि जब 30ms तक पहुंचा जाता है, तो सभी प्रक्रियाओं को एक ही पल में (एक के बाद एक) कहा जाता है और इससे यहां से सही निष्पादन में देरी हो सकती है।

इसे प्रत्येक प्रक्रिया में देरी जोड़कर हल किया जा सकता है (लेकिन इसकी कॉलिंग आवृत्ति को संरक्षित करना), इसलिए आवृत्तियों एक-दूसरे के गुणक होने से रोकती हैं। मेरी समस्या यह है कि मुझे नहीं पता कि प्रत्येक प्रक्रिया पर लागू होने में देरी की गणना कैसे करें ताकि टकराव की संख्या कम हो।

क्या इसके लिए कोई ज्ञात एल्गोरिदम है, या कुछ गणितीय मार्गदर्शन है?

धन्यवाद।

Answer 1

अंतराल के एक सेट को देखते हुए, आप उस समय को पा सकते हैं जिस पर आपके पोस्ट पर टिप्पणी में जेसन द्वारा वर्णित least common multiple को ढूंढकर प्रारंभ समय (कोई ऑफसेट नहीं माना जाता)। आप कार्यों के एक सेट के लिए अंतराल के प्रमुख कारककरण करके एलसीएम पा सकते हैं।

ऐसा लगता है कि greatest common divisor (या सबसे बड़ा आम कारक जीसीएफ) गणना करने के लिए सबसे उपयोगी संख्या हो सकता है। वह नंबर आपको अंतराल देगा जिसमें दोहराएगा होगा। आपके उदाहरण में, जीसीएफ 5 है। 5 के जीसीएफ के साथ, प्रारंभिक समय को ओवरलैप करने से बचने के लिए प्रत्येक कार्य में 1, 2, 3 इत्यादि का प्रारंभिक ऑफसेट जोड़ना संभव है। इस प्रकार, 5 के जीसीएफ के साथ, आपके पास 5 कार्य हो सकते हैं जिनके शुरुआती समय हो सकते हैं जो कभी ओवरलैप नहीं होंगे। 20 के जीसीएफ के साथ, आपके पास कोई ओवरलैपिंग प्रारंभ समय के साथ निर्धारित 20 कार्य हो सकते हैं।यदि दो (या अधिक) कार्य अपेक्षाकृत प्राइम (जीसीएफ = 1) हैं, तो अंतराल कभी भी नहीं बदलेगा, इससे कोई फर्क नहीं पड़ता कि आप उन कार्यों के लिए किस ऑफ़सेट का उपयोग करते हैं, यदि अंतराल कभी नहीं बदलते हैं।

Answer 2

इसके लिए कोई सही समाधान नहीं है, वे समय-समय पर टकराएंगे। मैं चक्र की लंबाई के लिए छोटे (0.01-0.1ms) यादृच्छिक मूल्य जोड़ने का सुझाव दूंगा, इसलिए लंबी अवधि में वे वास्तव में शायद ही कभी ही कभी-कभी बुलाए जाएंगे।

वैकल्पिक रूप से, यदि आपके पास 5 एमएम शेड्यूलर ग्रैन्युलरिटी है, तो पहले धागे को हमेशा एक्स + 1 एमएमएस पर कॉल किया जाता है, दूसरा एक्स + 2, आदि पर होता है, ताकि यह हमेशा 1 एमएमएस निर्बाध रन की गारंटी हो (यदि आपके पास 10 धागे हैं, तो यह एक्स + 0.5, एक्स + 1, एक्स + 1.5 होगा)। लेकिन यह लागू करने के लिए काफी मुश्किल हो सकता है।

Answer 3

इस प्रकार की समस्या सीधे रीयल-टाइम प्रोग्रामिंग और शेड्यूलिंग एल्गोरिदम के डोमेन से संबंधित है। मैंने कॉलेज में इस विषय पर एक कक्षा ली, और यदि मुझे अच्छी तरह याद है, Rate-monotonic scheduling वह एल्गोरिदम है जिसे आप ढूंढ रहे हैं।

विचार यह है कि आप उन नौकरियों को प्राथमिकताएं देते हैं जो उनकी अवधि के विपरीत आनुपातिक हैं, यानि छोटी अवधि, प्राथमिकता जितनी अधिक होती है। लेकिन यह बेहतर काम करता है अगर आप अपनी नौकरियों में बाधा डाल सकते हैं और बाद में उन्हें फिर से शुरू कर सकते हैं।

अन्य विकल्प हैं, हालांकि EDF (earliest deadline first) की तरह, लेकिन ये गतिशील शेड्यूलिंग एल्गोरिदम हैं (यानी प्राथमिकताओं को निष्पादन के दौरान असाइन किया गया है)।

Answer 4

आसान समाधान उस शेड्यूल को बदलना है जिसमें आप subroutines कहते हैं। अर्थात। 5, 10, 15, और 30 एमएस के बजाय, क्या आप जीवित रह सकते हैं उदा। 5, 15, 15 और 30 के साथ? (ए = 5 ms proc, बी, सी = 15 एमएस proc, डी = 30 एमएस proc): तो फिर तुम निम्नलिखित पैटर्न का उपयोग कर सकते

AAAAAAAAAAAAAAAAAAAA ... 
B B B B B B B ... 
    C C C C C C C ... 
    D  D  D  ... 

मुझे यकीन है कि आप इस विचार सामान्यीकरण कर सकते हैं, लेकिन यह काम करता है केवल अगर आप वास्तव में स्थिर अंतराल बदल सकते हैं।

आप अंतराल में परिवर्तन नहीं कर सकते हैं, और यह भी आप उन्हें सख्ती से पालन करने की जरूरत है, तो मैं तुम्हें के रूप में वहाँ दो प्रक्रियाओं के बीच बदलने के लिए :)