| dbo:abstract
|
- Earliest Deadline First (EDF) je plánovací algoritmus používaný v operačních systémech reálného času, který na rozdíl od RMS nevyžaduje periodické úlohy a zpracování úloh probíhá na základě mezní doby platnosti procesu. (cs)
- Earliest Deadline First (EDF) ist ein Scheduling-Verfahren von Betriebssystemen, mit dessen Hilfe es den Prozessen (engl. Tasks) Prozessor-Zeit zuteilt. Es gehört zu den zeitbasierten Verfahren, denn es trifft seine Entscheidungen so, dass Fertigstellungstermine (Deadlines) eingehalten werden. Die präemptive Variante von Earliest Deadline First wird vor allem für Echtzeitsysteme verwendet. (de)
- Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution. EDF is an optimal scheduling algorithm on preemptive uniprocessors, in the following sense: if a collection of independent jobs, each characterized by an arrival time, an execution requirement and a deadline, can be scheduled (by any algorithm) in a way that ensures all the jobs complete by their deadline, the EDF will schedule this collection of jobs so they all complete by their deadline. With scheduling periodic processes that have deadlines equal to their periods, EDF has a utilization bound of 100%. Thus, the schedulability test for EDF is: where the are the worst-case computation-times of the processes and the are their respective inter-arrival periods (assumed to be equal to the relative deadlines). That is, EDF can guarantee that all deadlines are met provided that the total CPU utilization is not more than 100%. Compared to fixed priority scheduling techniques like rate-monotonic scheduling, EDF can guarantee all the deadlines in the system at higher loading. Note that use the schedulability test formula under deadline as period. When deadline is less than period, things are different. Here is an example: The four periodic tasks needs scheduling, where each task is depicted as TaskNo( computation time, relative deadline, period). They are T0(5,13,20), T1(3,7,11), T2(4,6,10) and T3(1,1,20). This task group meets utilization is no greater than 1.0, where utilization is calculated as 5/20+3/11+4/10+1/20 = 0.97 (two digits rounded), but it's still unscheduable, check EDF Scheduling Failure figure for details. EDF is also an optimal scheduling algorithm on non-preemptive uniprocessors, but only among the class of scheduling algorithms that do not allow inserted idle time. When scheduling periodic processes that have deadlines equal to their periods, a sufficient (but not necessary) schedulability test for EDF becomes: Where p represents the penalty for non-preemption, given by max / min . If this factor can be kept small, non-preemptive EDF can be beneficial as it has low implementation overhead. However, when the system is overloaded, the set of processes that will miss deadlines is largely unpredictable (it will be a function of the exact deadlines and time at which the overload occurs.) This is a considerable disadvantage to a real time systems designer. The algorithm is also difficult to implement in hardware and there is a tricky issue of representing deadlines in different ranges (deadlines can not be more precise than the granularity of the clock used for the scheduling). If a modular arithmetic is used to calculate future deadlines relative to now, the field storing a future relative deadline must accommodate at least the value of the (("duration" {of the longest expected time to completion} * 2) + "now"). Therefore EDF is not commonly found in industrial real-time computer systems. Instead, most real-time computer systems use fixed priority scheduling (usually rate-monotonic scheduling). With fixed priorities, it is easy to predict that overload conditions will cause the low-priority processes to miss deadlines, while the highest-priority process will still meet its deadline. There is a significant body of research dealing with EDF scheduling in real-time computing; it is possible to calculate worst case response times of processes in EDF, to deal with other types of processes than periodic processes and to use servers to regulate overloads. (en)
- Earliest deadline first scheduling (« échéance proche = préparation en premier ») est un algorithme d'ordonnancement préemptif, à priorité dynamique, utilisé dans les systèmes temps réel. Il attribue une priorité à chaque requête en fonction de l'échéance de cette dernière, les tâches dont l’échéance est proche recevant la priorité la plus élevée. (fr)
- Earliest deadline first scheduling is een dynamisch schedulingprincipe gebruikt in real-timebesturingssystemen. Het plaatst processen in een wachtrij met prioriteiten. Aan het einde van elke procesexecutie, wordt het achteraan de wachtrij geplaatst en de wachtrij wordt doorzocht naar het proces dat het dichtste bij zijn deadline zit. Dit proces zal als eerstvolgende uitgevoerd worden. Vergeleken met statische scheduling technieken zoals rate-monotonic scheduling zal earliest deadline first beter presteren en tot 100% van de beschikbare processortijd gebruiken (wanneer het processor tijd uitdeelt). Maar het systeem kijkt niet naar prioriteiten. Dit betekent dat wanneer een proces zijn deadline mist, het systeem volledig onvoorspelbaar zal worden. (nl)
- L'Earliest Deadline First (EDF), in italiano prima la scadenza più vicina, è un algoritmo di scheduling tipico dei sistemi operativi in tempo reale. Come dice il nome stesso, lo scheduler seleziona come prossimo processo da eseguire quello con la distanza minore dalla sua deadline. EDF è un algoritmo a priorità dinamica, in quanto la priorità assegnata ai processi cambia potenzialmente ad ogni esecuzione dello scheduler e il suo valore dipende unicamente dalle caratteristiche temporali degli stessi (tempo di arrivo, deadline, ecc.). La complessità dell'algoritmo è tradizionalmente , anche se in letteratura scientifica è possibile trovare algoritmi che ammortizzano la complessità a . (it)
- 최단 마감 우선 스케줄링(Earliest Deadline First Scheduling, 줄여서 EDF 스케줄링)은 실시간 운영 체제에서 사용되는 동적 CPU 스케줄링 알고리즘의 하나이다.프로세스를 큐를 통해 수행한다. 스케줄링 이벤트가 일어날 때마다, 큐에서 마감시간이 가장 가까운 프로세스를 탐색하여 다음에 수행되도록 한다. 주기적인 작업 뿐만 아니라 단일 처리기 환경에서 선점형 프로세스들을 스케줄링할 수 있다. 작업(task)이 N개일 때 복잡도는 이다. RM 스케줄링은 사용률에 제약이 있는 반면 EDF 스케줄링은 사용률이 1이하이기만 하면 스케줄링 가능하다. 또한, 수학적으로 최적이라는 것이 증명되어 있다. 하지만 현실적으로 프로세스의 마감시간을 예측하는 것이 어렵기 때문에, 실제로는 RM 스케줄링을 사용하는 경우가 많다. (ko)
- Earliest Deadline First – optymalny algorytm szeregowania zadań wykorzystywany w systemach czasu rzeczywistego, wykorzystujący kolejkę priorytetową do przechowywania procesów. Za każdym razem, kiedy w systemie pojawi się zdarzenie wymagające działania algorytmu szeregującego (np. jeden z procesów ukończy swoje zadanie), z kolejki priorytetowej zostanie pobrany proces o najwyższym priorytecie (najbliższe do swojego deadline'u), a następnie zostanie mu przydzielony czas procesora. Optymalność algorytmu polega na tym, że jeśli EDF nie może uszeregować danego zbioru zadań to żaden algorytm z dynamicznym przydziałem priorytetów nie znajdzie wykonalnego szeregowania oraz w sytuacji gdy każdy algorytm z dynamicznym przydziałem priorytetów potrafi uszeregować dany zbiór zadań to również EDF potrafi.Zbiór zadań jest szeregowalny za pomocą algorytmu EDF wtedy i tylko wtedy, gdy stopień wykorzystania procesora dla danego zbioru zadań wynosi: U < 1. (pl)
- Earliest Deadline First (EDF) とは、リアルタイムオペレーティングシステムで使用される動的スケジューリング規則の一種である。プロセスは優先度付きキューに置かれる。スケジューリングイベントが発生すると(タスク終了、新規タスク生成など)、そのキューを探索して最も実行期限(デッドライン)が近いプロセスを選ぶ。そのプロセスが次に実行すべきものとしてスケジュールされる。 (ja)
- Earliest Deadline First (EDF) kan översättas till "tidigaste tidsgräns först" och är en schemaläggningsalgoritm som används inom datavetenskap, speciellt inom realtidssystem. Algoritmen fungerar genom att den process som har kortast tid tills den måste vara färdig kör först. Algoritmen använder sig därför inte av när den avgör vilken process som ska köra näst. Algoritmen kan schemalägga om och endast om Förutsättningarna är att:
* Alla processer är oberoende av varandra och delar inga enheter eller resurser.
* Alla processer har sin tidsgräns satt till början av nästa period.
* Alla processer släpps i början av perioden de ska köra i. Utnyttjandegraden får man fram genom följande ekvation: Där är exekveringstid (den tid det tar att köra en process) och är periodtid (tidslängden från att en process körs, tills att den vill köra igen). Earliest Deadline First är optimal om ovanstående uppfylls, och är en av de effektivaste schemaläggningsalgoritmerna. Problemet med den är att den är svår att implementera på annat än specialdesignade realtidssystem som bygger på att alla processer har just en tidsgräns. (sv)
- Алгоритм планирования по ближайшему сроку завершения (EDF) - динамический алгоритм планирования. Используется в операционных системах реального времени для помещения процессов в очередь по приоритетам. При наступлении события планирования (задача завершена, появилась новая задача и т. п.) в очереди производится поиск процесса, ближайшего к своему крайнему сроку исполнения. Этот процесс будет запланирован для выполнения следующим. Планирование по ближайшему сроку завершения оптимально для однопроцессорных систем с вытеснением в следующем смысле: если существует возможность гарантированно выполнить набор независимых задач, каждая из которых характеризуется временем поступления, требованием выполнения и крайним сроком завершения, к крайнему сроку, то алгоритм EDF тоже сможет это сделать. При планировании периодических процессов, которые имеют крайние сроки равные их периодам, алгоритм планирования по ближайшему сроку завершения использует полную загрузку. Следовательно, тестом на возможности планирования для данного алгоритма будет: где — наихудшее время выполнения процессов, а — соответствующий период между сроками их поступления (подразумевая, что он равен соответствующим крайним срокам). То есть, назначение по ближайшему сроку завершения гарантирует, что все крайние сроки будут соблюдены, при условии что общая загрузка процессора не превышает 100 %. В сравнении с использованием фиксированных приоритетов, планирование по ближайшему сроку завершения гарантирует соблюдение всех крайних сроков при большей загрузке. Тем не менее, если система перегружена, то набор процессов, для которых крайний срок будет упущен, окажется крайне непредсказуем (он будет зависеть от точных сроков и времени возникновения перегрузки.) Это — заметный недостаток для проектировщиков систем реального времени. Кроме того, алгоритм трудно реализовать аппаратно, и существуют сложности для представления крайних сроков в различных диапазонах (сроки не могут назначаться точнее, чем такты, использованные для планирования). Если для вычисления будущих крайних сроков используется модульная арифметика, поля, хранящие будущие крайние сроки должны содержать как минимум значение «удвоенная продолжительность наибольшего ожидаемого времени выполнения» + «сейчас». Поэтому планирование по ближайшему сроку завершения не является общепринятым в индустриальных компьютерных системах реального времени. Вместо этого большинство компьютерных систем реального времени используют планирование с фиксированным приоритетом. При фиксированном приоритете легче гарантировать, что при перегрузке процессы с низким приоритетом пропустят крайние сроки, в то время как процессы с высоким приоритетом по-прежнему будут выполнены вовремя. Проведено множество исследований по части планирования по ближайшему сроку завершения; существует возможность вычислить наихудшее время отклика процессов при этом алгоритме, для работы с иными типами процессов чем периодические процессы и использованию серверов для регулирования перегрузок. (ru)
- 最早截止时间 (EDF) 是一个实时操作系统中使用的，动态优先级的将进程放入优先队列的算法。每当一个引起调度的事件发生(任务完成等) ，将搜索出队列中最后期限最接近的进程，接下来要被执行的就是这个进程。 EDF在抢占式、单CPU的场景下是一个最优的调度算法：如果有一组互相无关的任务，每个任务都有一个到达时间、一个执行需求和一个截止时间，如果存在一个调度算法能够确保在截止时间前完成这些任务，使用EDF算法来调度这些任务将会达到这个效果。 对于调度最后期限等于其周期的周期性进程， EDF 的利用率为100％。EDF 的可调度性检验是： 然而，当该系统超载、会错过最后期限的进程集合很大程度上是不可预知的。在实时操作系统上，这是一个相当大的缺点。 算法也难以使用硬件实现，表达不同范围内的截止时间也是一个棘手的问题(截止时间不能比用于调度的时间粒度更为精确)。 因此， EDF 并不常用于工业实时计算机系统中。 相反，大多数实时计算机系统使用 固定优先级调度 (通常使用 速率的单调调度)。由于优先级是固定的，显然，超载时会造成的低优先级的任务会错过最后期限，而最高的优先级进程将仍然满足其最后期限。 (zh)
|
| rdfs:comment
|
- Earliest Deadline First (EDF) je plánovací algoritmus používaný v operačních systémech reálného času, který na rozdíl od RMS nevyžaduje periodické úlohy a zpracování úloh probíhá na základě mezní doby platnosti procesu. (cs)
- Earliest Deadline First (EDF) ist ein Scheduling-Verfahren von Betriebssystemen, mit dessen Hilfe es den Prozessen (engl. Tasks) Prozessor-Zeit zuteilt. Es gehört zu den zeitbasierten Verfahren, denn es trifft seine Entscheidungen so, dass Fertigstellungstermine (Deadlines) eingehalten werden. Die präemptive Variante von Earliest Deadline First wird vor allem für Echtzeitsysteme verwendet. (de)
- Earliest deadline first scheduling (« échéance proche = préparation en premier ») est un algorithme d'ordonnancement préemptif, à priorité dynamique, utilisé dans les systèmes temps réel. Il attribue une priorité à chaque requête en fonction de l'échéance de cette dernière, les tâches dont l’échéance est proche recevant la priorité la plus élevée. (fr)
- 최단 마감 우선 스케줄링(Earliest Deadline First Scheduling, 줄여서 EDF 스케줄링)은 실시간 운영 체제에서 사용되는 동적 CPU 스케줄링 알고리즘의 하나이다.프로세스를 큐를 통해 수행한다. 스케줄링 이벤트가 일어날 때마다, 큐에서 마감시간이 가장 가까운 프로세스를 탐색하여 다음에 수행되도록 한다. 주기적인 작업 뿐만 아니라 단일 처리기 환경에서 선점형 프로세스들을 스케줄링할 수 있다. 작업(task)이 N개일 때 복잡도는 이다. RM 스케줄링은 사용률에 제약이 있는 반면 EDF 스케줄링은 사용률이 1이하이기만 하면 스케줄링 가능하다. 또한, 수학적으로 최적이라는 것이 증명되어 있다. 하지만 현실적으로 프로세스의 마감시간을 예측하는 것이 어렵기 때문에, 실제로는 RM 스케줄링을 사용하는 경우가 많다. (ko)
- Earliest Deadline First (EDF) とは、リアルタイムオペレーティングシステムで使用される動的スケジューリング規則の一種である。プロセスは優先度付きキューに置かれる。スケジューリングイベントが発生すると(タスク終了、新規タスク生成など)、そのキューを探索して最も実行期限(デッドライン)が近いプロセスを選ぶ。そのプロセスが次に実行すべきものとしてスケジュールされる。 (ja)
- 最早截止时间 (EDF) 是一个实时操作系统中使用的，动态优先级的将进程放入优先队列的算法。每当一个引起调度的事件发生(任务完成等) ，将搜索出队列中最后期限最接近的进程，接下来要被执行的就是这个进程。 EDF在抢占式、单CPU的场景下是一个最优的调度算法：如果有一组互相无关的任务，每个任务都有一个到达时间、一个执行需求和一个截止时间，如果存在一个调度算法能够确保在截止时间前完成这些任务，使用EDF算法来调度这些任务将会达到这个效果。 对于调度最后期限等于其周期的周期性进程， EDF 的利用率为100％。EDF 的可调度性检验是： 然而，当该系统超载、会错过最后期限的进程集合很大程度上是不可预知的。在实时操作系统上，这是一个相当大的缺点。 算法也难以使用硬件实现，表达不同范围内的截止时间也是一个棘手的问题(截止时间不能比用于调度的时间粒度更为精确)。 因此， EDF 并不常用于工业实时计算机系统中。 相反，大多数实时计算机系统使用 固定优先级调度 (通常使用 速率的单调调度)。由于优先级是固定的，显然，超载时会造成的低优先级的任务会错过最后期限，而最高的优先级进程将仍然满足其最后期限。 (zh)
- Earliest deadline first (EDF) or least time to go is a dynamic priority scheduling algorithm used in real-time operating systems to place processes in a priority queue. Whenever a scheduling event occurs (task finishes, new task released, etc.) the queue will be searched for the process closest to its deadline. This process is the next to be scheduled for execution. With scheduling periodic processes that have deadlines equal to their periods, EDF has a utilization bound of 100%. Thus, the schedulability test for EDF is: (en)
- L'Earliest Deadline First (EDF), in italiano prima la scadenza più vicina, è un algoritmo di scheduling tipico dei sistemi operativi in tempo reale. Come dice il nome stesso, lo scheduler seleziona come prossimo processo da eseguire quello con la distanza minore dalla sua deadline. EDF è un algoritmo a priorità dinamica, in quanto la priorità assegnata ai processi cambia potenzialmente ad ogni esecuzione dello scheduler e il suo valore dipende unicamente dalle caratteristiche temporali degli stessi (tempo di arrivo, deadline, ecc.). (it)
- Earliest Deadline First – optymalny algorytm szeregowania zadań wykorzystywany w systemach czasu rzeczywistego, wykorzystujący kolejkę priorytetową do przechowywania procesów. Za każdym razem, kiedy w systemie pojawi się zdarzenie wymagające działania algorytmu szeregującego (np. jeden z procesów ukończy swoje zadanie), z kolejki priorytetowej zostanie pobrany proces o najwyższym priorytecie (najbliższe do swojego deadline'u), a następnie zostanie mu przydzielony czas procesora. (pl)
- Earliest deadline first scheduling is een dynamisch schedulingprincipe gebruikt in real-timebesturingssystemen. Het plaatst processen in een wachtrij met prioriteiten. Aan het einde van elke procesexecutie, wordt het achteraan de wachtrij geplaatst en de wachtrij wordt doorzocht naar het proces dat het dichtste bij zijn deadline zit. Dit proces zal als eerstvolgende uitgevoerd worden. (nl)
- Алгоритм планирования по ближайшему сроку завершения (EDF) - динамический алгоритм планирования. Используется в операционных системах реального времени для помещения процессов в очередь по приоритетам. При наступлении события планирования (задача завершена, появилась новая задача и т. п.) в очереди производится поиск процесса, ближайшего к своему крайнему сроку исполнения. Этот процесс будет запланирован для выполнения следующим. где — наихудшее время выполнения процессов, а — соответствующий период между сроками их поступления (подразумевая, что он равен соответствующим крайним срокам). (ru)
- Earliest Deadline First (EDF) kan översättas till "tidigaste tidsgräns först" och är en schemaläggningsalgoritm som används inom datavetenskap, speciellt inom realtidssystem. Algoritmen fungerar genom att den process som har kortast tid tills den måste vara färdig kör först. Algoritmen använder sig därför inte av när den avgör vilken process som ska köra näst. Algoritmen kan schemalägga om och endast om Förutsättningarna är att: Utnyttjandegraden får man fram genom följande ekvation: (sv)
|
