دانلود مقاله مطالعه اجمالی تکنیک های تجزیه و تحلیل قابلیت زمان بندی برای وظایف وابسته به سرعت
چکیده:
در سیستم‌های بلادرنگ تعبیه شده خودرویی، مانند واحد کنترل موتور، وظایفی وجود دارند که برای مثال هر بار زمانی فعال می‌شوند که میل لنگ به یک موقعیت زاویهای خاص برسد. در نتیجه شاهد افزایش تکرار تغییرات فعال‌سازی با سرعت زاویهای میل لنگ هستیم (یعنی RPM موتور). علاوه بر این، زمان اجرا و ضرب‌الاجل‌ها نیز ممکن است به سرعت و موقعیت زاویهای بستگی داشته باشند. در این مقاله مطالعه اجمالی در مورد تکنیک‌های تحلیلی قابلیت زمان‌بندی برای وظایفی با این رفتار وابسته به سرعت ارائه شده است که روش‌های تجزیه و تحلیل و مدل‌های وظایف مختلفی برای هر دوی زمان‌بندی‌هایی با اولویت ثابت و نخست زودترین ضرب‌الاجل پوشش داده شده است. یک رده‌بندی‌شناسی از روش‌های تجزیه و تحلیل مختلف و طبقه‌بندی آنها با توجه به فرضیه‌های ساخته شده و دقت تجزیه و تحلیل آنها در پایان مقاله ارائه شده است.
1. مقدمه
ویژگی اصلی سیستم‌های بلادرنگ نیاز به صحت در مورد زمان‌بندی و عملکرد است. این سیستم باید پاسخ‌هایی صحیح به محرک‌های ورودی را در محدودیت‌های زمان مشخص یا ضرب‌الاجل‌ها تولید کند. قابلیت بلادرنگ معمولا به مجموعه‌ای از وظایف تقسیم می‌شود که یا به شکل دوره‌ای فعال می‌شوند یا به شکل مستقیم در پاسخ به رویدادهایی در محیط هستند. با توجه به سیستم‌های مدیریت موتور در حوزه خودرو، توابعی وجود دارند که باید در یک دوره زمانی مشخص برای مثال 5، 10، 20، 50، 100 میلی‌ثانیه صورت بگیرند. علاوه بر این توابعی مرتبط با کنترل رفتار موتور (سوخت‌گیری، زمان اشتعال و غیره) وجود دارند که توسط چرخش میل لنگ فعال می‌شوند. چنین وظایفی دارای یک دوره زاویهای اندازه‌گیری شده در درجه چرخش دارند و در موقعیت‌های زاویهای مشخص یا فاز‌هایی خاص فعال می‌شوند. از آنجایی که سرعت موتور، بر حسب دور موتور در دقیقه (rpm)، اندازه‌گیری می‌شوند ممکن است در طیف گسترده ای از 500 rpm تا بیشتر از6500 rpm متفاوت باشند، سرعت زاویه ای میل لنگ و از این رو میزانی که این وظایف به شکل گسترده‌ای فعال شده‌اند می‌تواند بسیار متفاوت باشد. ضر‌الاجل برای چنین وظایف وابسته به سرعت نیز از نظر چرخش زاویهای اندازه‌گیری می‌شود. به عنوان مثال، در موتور بنزینی 4 سیلندری [26]، وظیفه‌ای که مقدار سوخت تزریق را محاسبه می‌کند باید هر 180 درجه چرخش را با یک ضرب‌الاجل 120 درجه‌ای انجام دهد. بنابراین در 1000 دور در دقیقه، زمان ورود به این وظیفه 30 میلی ثانیه است و ضرب‌الاجل نسبی 20 میلی ثانیه است، در حالی که در 5000 دور در دقیقه، زمان ورود کت بیم تنها 6 میلی ثانیه است و ضرب‌الاجل نسبی 4 میلی ثانیه است.
6. چشم‌انداز و کارهای آتی
در این مقاله تحقیقاتی برای تجزیه و تحلیل قابلیت زمان‌بندی برای وظایف وابسته به میزان اولویت ثابت یا زمان‌بندی EDF انجام شده است که از طریق منابعی همچون چرخش زاویهای مانند محور بادامک یا میل لنگ یک موتور بنزینی 4 زمانه ايجاد شده بود. در ابتدا، با تعدادی از مفروضات ساده اعمال شده، تجزیه و تحلیل کافی انجام شد. اخیرا، این تجزیه و تحلیل پیچیده تر از محدودیت های ارائه شده توسط سیستم فیزیکی (به عنوان مثال، محدودیت حداکثر سرعت شتاب) استفاده کرده است. تجزیه و تحلیل دقیق برای مدل‌های ساده شده (با فرض اینکه تمامی وظایف مرتبه مستقل دارای یک زمان زاویهای هستند و فرض بر این است که سرعت زاویهای لحظه ای در دسترس است) توسعه داده شده است، که با کاهش برخی مفروضات با هزینه دقت پایین، گسترش یافته است. جدول 1 طبقه‌بندی از روش‌های مختلف تجزیه و تحلیل را فراهم کرده است که طبق فرض‌های ساخته شده و دقت تجزیه و تحلیل (یعنی کافی یا دقیق) با توجه به فرضیه‌های آنها است.
کارهای آتی احتمالی می‌توانند شامل تجزیه و تحلیل دقیق برای یک مدل وظیفه وابسته به وظیفه جامع با شتاب دلخواه اما محدود باشد که سرعت زاویهای از طریق یک روش عملیاتی حاص شده است و پسماندها در حالت اجرا تغییر پیدا خواهند کرد. پیشرفت‌های بیشتر شامل سیستم‌هایی با وظایف فعال‌شده از چند منبع مستقل چرخشی و ارائه تجزیه و تحلیل برای سیستم‌های با آفست زاویهای است. یک منطقه دیگر برای بهبود، کاهش پیچیدگی زمان اجرا تجزیه و تحلیل دقیق خواهد بود. کارهای آتی می‌توانند به گسترش تست‌های قابلیت زمان‌بندی برای وظایف وابسته به سرعت برای سیستم‌هایی با چند هسته اشاره کرد.
Abstract
In automotive embedded real-time systems, such as the engine control unit, there are tasks that are activated whenever the crankshaft arrives at a specific angular position. As a consequence the frequency of activation changes with the crankshaft’s angular speed (i.e., engine rpm). Additionally, execution times and deadlines may also depend on angular speeds and positions. This paper provides a survey on schedulability analysis techniques for tasks with this rate-dependent behaviour. It covers different task-models and analysis methods for both fixed priority and earliest deadline first scheduling. A taxonomy of the different analysis methods, classifying them according to the assumptions made and the precision of the analysis, is provided at the end of the paper.
1. Introduction
Real-time systems are characterised by the need for both functional and timing correctness. The system must produce the correct responses to input stimuli within specified time constraints or deadlines. Real-time functionality is typically decomposed into a set of tasks that are either activated periodically in time, or directly in response to events in their environment. Considering engine management systems in the automotive domain, there are functions that need to be executed with a specific time period for example 5, 10, 20, 50, 100 ms. In addition, there are functions related to controlling the engine behaviour (fueling, ignition timing, and so on) that are triggered by the crankshaft rotation. Such tasks have an angular period measured in degrees of rotation and are triggered at specific angular positions or phases. Since the engine speed, measured in revolutions per minute (rpm), may vary over a wide range, from 500 rpm to more than 6500 rpm, the angular speed of the crankshaft and hence the rate at which these tasks are triggered varies widely. The deadline for such rate-dependent tasks is also measured in terms of angular rotation. For example, in a 4-cylinder petrol engine [26], the task that computes the quantity of fuel to be injected must execute every 180 degrees of rotation, with a deadline of 120 degrees. Thus at 1000 rpm, the inter-arrival time of this task is 30 ms and the relative deadline is 20 ms, whereas at 5000 rpm, the inter-arrival time is just 6 ms and the relative deadline is 4 ms.
The variation in the period and deadline of rate-dependent tasks, when viewed in the time domain, implies that the time interval available for computation is greatly reduced at high en-gine speeds. This means that while at lower engine speeds, typical of normal driving, there is time available to execute complex functionality aimed at optimizing fuel consumption and minimizing emissions, at higher engine speeds simpler functionality is required, otherwise the processor would be overloaded and the system would be unschedulable. In practice, different control algorithms are adopted for different ranges of engine speed, leading to tasks characterized by a set of execution modes. Figure 1 shows the worst-case execution time and the utilization of a rate-dependent task with six execution modes as a function of the angular speed in rpm. We note that the highest angular speed of each mode corresponds to the highest processor utilization for that mode.
6. Perspectives and Future work
This survey has reviewed research into schedulability analysis for rate-dependent tasks under fixed priority or EDF scheduling, triggered via sources of angular rotation, such as the crankshaft or camshafts of a 4-stroke petrol engine. Initially, sufficient analyses were developed with a number of simplifying assumptions applied. More recently, these have been supplanted by more sophisticated analyses that make use of constraints provided by the physical system (e.g., limits on the maximum rate of acceleration). Exact analyses have been developed for simplified models (assuming that all the ratedependent tasks have the same angular period, and assuming that the instantaneous angular speed is available), which have been extended by relaxing some assumptions at the cost of a lower precision. Table 1 provides a taxonomy of the different analysis methods classifying them according to the assumptions made and the precision of the analysis (i.e., sufficient or exact) with respect to their assumptions.
Possible future work includes a precise analysis for a more comprehensive rate-dependent task model with arbitrary but bounded acceleration, angular speed derived via a practical method, and hysteresis in the execution mode changes. Further enhancements include covering systems with tasks triggered from multiple independent rotational sources, and providing analysis for systems with angular offsets. Another area for improvement would be to reduce the runtime complexity of precise analysis. Further work could also extend schedulability tests for rate-dependent tasks to multi-core systems.
(جهت بزرگ نمایی روی عکس کلیک نمایید)
چکیده
1. مقدمه
2. مدل های وظیفه قبلی و اصطلاحات فنی
3. مدل‌هایی برای وظایف وابسته به سرعت
4. زمان‌بندی انحصاری اولویت ثابت
1. 4رضیات محدود‌ساز با کارهای مقدماتی
4.2 تست‌های مناسب
3. 4. تست‌های دقیق
4. 4 زمان‌بندی سطح حالت اولویت ثابت
4.5آزمایشات مقایسه دقت تجزیه و تحلیل
5. زمان‌بندی نخست اولین ضرب‌الاجل
1 .5 تست‌های کافی
2. 5تست‌های دقیق
6. چشم‌انداز و کارهای آتی
منابع
Abstract
1. Introduction
2. Previous Task Models and Terminology
3. Models for Rate-Dependent Tasks
4. Fixed Priority Preemptive Scheduling
4.1. Preliminary Work with Restrictive Assumptions
4.2. Sufficient Tests
4.3. Exact Tests
4.4. Fixed Priority Mode-level Scheduling
4.5. Experiments comparing the precision of the analysis
5. Earliest Deadline First Scheduling
5.1. Sufficient Tests
5.2. Exact tests
6. Perspectives and Future work
References
- اصل مقاله انگلیسی با فرمت ورد (word) با قابلیت ویرایش
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه