© psdesign1, Fotolia

Nur ausgewiesene Echtzeitbetriebssysteme konnten bislang mit einem “Earliest Deadline First Task”-Scheduler protzen. Seit Kernel 3.14 steht das überlegene CPU-Zuteilungsverfahren auch Linux-Nutzern zur Verfügung. Gegenüber dem prioritätengesteuerten Verfahren hat es einige Vorteile.

Kernel 3.14 erweitert die Liste der unterstützten Scheduling-Verfahren um Earliest Deadline First (EDF). Für Ein- und Ausgabeoperationen gibt es im Linux-Kernel zwar schon lange ein Deadline-Scheduling [1]; aber eines, das die von der CPU bereitgestellte Rechenleistung auf Rechenprozesse verteilt, ist ein Novum.

Earliest Deadline First kommt vor allem in Systemen zum Einsatz, die zeitlichen Anforderungen genügen müssen. Für derartige Echtzeitsysteme, wissenschaftlich eindeutiger als Realzeitsysteme oder mit englischem Anklang als Realtime-Systeme bezeichnet, ist es sogar das Verfahren der Wahl: Es verarbeitet Tasks auch noch dann fristgerecht, wenn das gängige prioritätengesteuerte Scheduling versagt (Abbildung 1 und Kasten “Utilization”).

<BI>images/utilization.png<BI>

<BI>images/limit.png<BI>

Abbildung 1: Beispielhafte CPU-Belegung. Prioritätengesteuert wird Task B nicht rechtzeitig fertig, der überlegene EDF-Scheduler kommt zurecht.

Vorteilhaft ist weiterhin, dass das Scheduling keine Prioritäten vergeben muss. Diese Aufgabe ist nämlich nur dann trivial, wenn die maximale Ausführungszeit einer Task mit deren Auftrittshäufigkeit korreliert.

Handarbeit

Dass Prioritäten die meisten Realzeitsysteme steuern, hängt wohl mit drei Faktoren zusammen: Erstens bieten nicht alle einen Deadline-Scheduler an, zweitens kennen die Systemarchitekten Prioritäten in der Regel besser als Deadlines und drittens müssen für dieses Verfahren die Deadlines und ebenso die maximalen Verarbeitungszeiten bekannt sein. Genau genommen müssen sowohl der Systemarchitekt als auch der Scheduler diese beiden Faktoren kennen, was häufig nicht der Fall ist.

Nicht zuletzt unterstützen die bisherigen Interfaces, die ein Scheduling-Verfahren auswählen und mit Parametern versehen, das EDF-Verfahren noch nicht.

Zwar hinkt die Entwicklung im Userland jener im Kernel hinterher, glücklicherweise können Admins das Earliest Deadline First Scheduling dennoch einsetzen. Nur ist hierzu etwas Handarbeit nötig, die darin besteht, dass die Admins benötigte Datenstrukturen und Schnittstellenfunktionen selbst definieren. Der Code aus der Kerneldokumentation [3] in Listing 1 zeigt, wie es geht.

001 #define _GNU_SOURCE
002 #include <unistd.h>
003 #include <stdio.h>
004 #include <stdlib.h>
005 #include <string.h>
006 #include <time.h>
007 #include <linux/unistd.h>
008 #include <linux/kernel.h>
009 #include <linux/types.h>
010 #include <sys/syscall.h>
011 #include <pthread.h>
012
013 #define gettid() syscall(__NR_gettid)
014
015 #define SCHED_DEADLINE  6
016
017 /* XXX use the proper syscall numbers */
018 #ifdef __x86_64__
019 #define __NR_sched_setattr      314
020 #define __NR_sched_getattr      315
021 #endif
022 #ifdef __i386__
023 #define __NR_sched_setattr      351
024 #define __NR_sched_getattr      352
025 #endif
026 #ifdef __arm__
027 #define __NR_sched_setattr      380
028 #define __NR_sched_getattr      381
029 #endif
030
031 static volatile int done;
032
033 struct sched_attr {
034     __u32 size;
035
036     __u32 sched_policy;
037     __u64 sched_flags;
038
039     /* SCHED_NORMAL, SCHED_BATCH */
040     __s32 sched_nice;
041
042     /* SCHED_FIFO, SCHED_RR */
043     __u32 sched_priority;
044
045     /* SCHED_DEADLINE (nsec) */
046     __u64 sched_runtime;
047     __u64 sched_deadline;
048     __u64 sched_period;
049 };
050
051 int sched_setattr(pid_t pid,
052     const struct sched_attr *attr,
053     unsigned int flags)
054 {
055     return syscall(__NR_sched_setattr,
056         pid, attr, flags);
057 }
058
059 int sched_getattr(pid_t pid,
060     struct sched_attr *attr,
061     unsigned int size,
062     unsigned int flags)
063 {
064     return syscall(__NR_sched_getattr,
065         pid, attr, size, flags);
066 }
067
068 void *run_deadline(void *data)
069 {
070     struct sched_attr attr;
071     int x = 0, ret;
072     unsigned int flags = 0;
073
074     printf("deadline thread start %ld\n",
075         gettid());
076
077     attr.size = sizeof(attr);
078     attr.sched_flags = 0;
079     attr.sched_nice = 0;
080     attr.sched_priority = 0;
081
082     /* creates a 10ms/30ms reservation */
083     attr.sched_policy = SCHED_DEADLINE;
084     attr.sched_runtime = 10 * 1000 * 1000;
085     attr.sched_period  = 30 * 1000 * 1000;
086     attr.sched_deadline= 30 * 1000 * 1000;
087
088     ret = sched_setattr(0, &attr, flags);
089     if (ret < 0) {
090         done = 0;
091         perror("sched_setattr");
092         exit(-1);
093     }
094
095     while (!done) {
096         x++;
097     }
098     return NULL;
099 }
100
101 int main (int argc, char **argv)
102 {
103     pthread_t thread;
104
105     printf("main thread [%ld]\n", gettid());
106     pthread_create(&thread, NULL, run_deadline, NULL);
107     sleep(10);
108     done = 1;
109     pthread_join(thread, NULL);
110     printf("main dies [%ld]\n", gettid());
111     return 0;
112 }

Der obere Teil ab Zeile 17 definiert die benötigten Systemcall-Nummern für drei Plattformen (ARM, PC 32 und 64 Bit). Die danach folgende zentrale Datenstruktur »struct sched_attr« (Zeile 33) nimmt die Scheduling-Parameter auf. Der dritte Teil implementiert die Aufrufe der Systemcalls (Zeile 51).

Der neue Systemcall »sched_setattr(pid_t pid, const struct sched_attr *attr, unsigned int flags)« [4] aktiviert dabei sowohl EDF als auch die anderen Scheduling-Verfahren (Zeile 51). Er bekommt drei Parameter mit auf den Weg. Der erste spezifiziert den Thread, für den das Scheduling gilt. Steht hier eine »0« , ist es derjenige, der den Aufruf tätigt. Der zweite Parameter wählt das Scheduling-Verfahren und eventuell benötigte Parameter aus. Der dritte Parameter ist für potenzielle Erweiterungen gedacht, zurzeit wird »0« übergeben.

Der Rückgabewert »0« signalisiert, dass das Scheduling erfolgreich ausgewählt und parametrisiert wurde. Kommt ein Fehler wie »-1« zurück, enthält die globale Variable »errno« einen Fehlercode, beispielsweise für ein »Permission denied« . Im letzten Fall läuft der Job vermutlich nicht mit den für die Auswahl des Scheduling notwendigen Rootrechten. Der Aufruf der Funktion »sched_setattr()« findet im Beispiel innerhalb der separaten Funktion »run_deadline()« statt, die der Code in Zeile 106 als eigenständigen Thread startet.

Zur Parametrisierung des EDF sind insgesamt vier Werte wichtig: das Scheduling-Verfahren selbst (Policy), die Verarbeitungszeit im ungünstigsten Fall (WCET), der kürzeste Zeitraum, in dem der Rechenprozess nach der letzten Aktivierung erneut aktiviert wird (Periode) und schließlich die eigentliche Deadline. Diese Zeiten sind in 64 Bit breiten Variablen abgespeichert und werden in Nanosekunden angegeben.

Die in Listing 1 programmierte Task wird in einem minimalen Abstand von 30 Millisekunden (Zeile 85) für maximal 10 Millisekunden (Zeile 84) aktiv. Spätestens nach ebenfalls 30 Millisekunden müssen die Berechnungen (der Zyklus) abgeschlossen sein (Zeile 86). Der Linux Earliest Deadline First Scheduler berechnet übrigens die Deadline mit jedem Aufwecken einer Task neu.

Cheaten ist nicht

Eigentlich müsste die Angabe der Deadline für die Parametrisierung des EDF ausreichen, aber der Linux-Kernel hat das klassische EDF um eine Auslastungskontrolle (Bandwidth Control) ergänzt, welche die Kenntnis der WCET und Periode erfordert. Der Quotient aus beidem ergibt die Auslastung durch den jeweiligen Rechenprozess.

Linux stellt sicher, dass sich die Auslastungen der per EDF auszuwählenden Jobs in der Standardeinstellung auf nicht mehr als 95 Prozent der zur Verfügung stehenden Rechenzeit summieren. Damit bleiben mindestens 5 Prozent für Tasks übrig, die ein anderer Scheduling-Algorithmus verwaltet. Diese Einstellung lässt sich über die Proc-Dateien »/proc/sys/kernel/sched_rt_period_us« sowie »/proc/sys/kernel/sched_rt_runtime_us« ändern. Um diese Auslastungskontrolle außer Betrieb zu setzen, schreibt der Admin eine »-1« in die Proc-Datei »sched_rt_runtime_us« .

Jobs, die bei der WCET oder der Periode falsche Angaben machen und sich mehr Rechenzeit nehmen als angefordert, würgt Linux sehr drastisch ab. Ihnen wird sogar Rechenzeit entzogen. Es weist auch jene ab, die zu große (mehr als 263) Deadlines oder Perioden angeben. Schließlich führen diese bei der Berechnung von Zeitdifferenzen zu Fehlern [2]. Will der Admin das System durch den Aufruf von »fork()« überlisten, bei dem der Kindprozess normalerweise die Attribute des Elternprozesses erbt, unterbindet Linux auch dies.

Die einmal gesetzten Scheduling-Parameter liest der ebenfalls mit Kernel 3.14 neu eingeführte Systemcall »int sched_getattr(pid_t pid, struct sched_attr *attr, unsigned int size, unsigned int flags)« (Zeile 59) aus. Der Parameter »pid« referenziert wieder die Task, wobei »0« die aufrufende Task repräsentiert. Bei »attr« handelt es sich um die Adresse eines Speicherbereichs von der Größe »size« , ab der das Programm die Parameter ablegen soll. Für »flags« ist eine »0« zu übergeben.

Kerneltausch

Aus dem Quellcode von Listing 1 macht der Befehl »make LDLIBS=”-lpthread” dl_test« ein lauffähiges Programm. Konsequent setzt dieses aber einen Kernel ab Version 3.14 voraus. Bei einem Ubuntu kommt die Version standardmäßig erst ab 14.10 (Utopic Unicorn) zum Zuge. Allerdings lässt sich auch auf älteren Versionen, insbesondere der Version 14.04 mit Long Term Support, ein aktueller Kernel mit wenig Aufwand installieren. Entsprechende Debian-Pakete liefert [5], wenn der Admin dieses Repository als externe Paketquelle angibt.

Kernel 3.18.1 für ein 64-Bit-Ubuntu lässt sich recht einfach über die in Listing 2 dargestellten Kommandos installieren. Will ein Entwickler die 32-Bit-Version nutzen, tauscht er in den Dateinamen von Listing 2 einfach den Textteil »amd64« gegen »i386« aus.

01 wget http://kernel.ubuntu.com/~kernel-ppa/mainline/v3.18.1-vivid/linux-image-3.18.1-031801-generic_3.18.1-031801.201412170637_amd64.deb
02 sudo dpkg -i linux-image-3.18.1-031801-generic_3.18.1-031801.201412170637_amd64.deb

Ausgefuchste Tests mit Earliest Deadline First ermöglicht die im Kasten “Testprogramme” erwähnte Software. Mit diesen Werkzeugen testen die Entwickler selbst das Realzeitverhalten der unterschiedlichen Scheduling-Verfahren.

01 # rt-app
02 quade@ezs-mobil:~$ sudo apt-get install git autoconf libtool
03 [...]
04 quade@ezs-mobil:~$ mkdir ~/linux-mag
05 quade@ezs-mobil:~$ cd linux-mag/
06 quade@ezs-mobil:~/linux-mag$ git clone https://github.com/scheduler-tools/rt-app
07 Klone nach 'rt-app'...
08 quade@ezs-mobil:~/linux-mag$ cd rt-app/
09 quade@ezs-mobil:~/linux-mag/rt-app$ ./autogen.sh
10 [...]
11 quade@ezs-mobil:~/linux-mag/rt-app$ ./configure --with-deadline
12 quade@ezs-mobil:~/linux-mag/rt-app$ make
13 # schedtool-dl
14 quade@ezs-mobil:~$ cd ~/linux-mag/
15 quade@ezs-mobil:~/linux-mag$ git clone https://github.com/scheduler-tools/schedtool-dl.git
16 [...]
17 quade@ezs-mobil:~/linux-mag$ cd schedtool-dl/
18 quade@ezs-mobil:~/linux-mag/schedtool-dl$ make

Verwirrende Ausgaben

Wie bereits erwähnt ist der Kernel dem Userland voraus. Das macht sich beispielsweise bei den einschlägigen Kommandos bemerkbar, die aktive Tasks darstellen. Sie kennen nämlich das Deadline-Scheduling noch nicht und zeigen daher für das verwendete Scheduling die Kernel-interne Nummer »#6« an (Abbildung 2). Diese Nummer ist auch sichtbar, wenn der Admin im Verzeichnis »/proc/PID/« die Datei »sched« eines Jobs ausliest, den EDF verwaltet. Der Eintrag darunter gibt die Priorität mit »-1« an (Abbildung 3). Auch das ist ein Indikator für Deadline-Scheduling, denn um interne Abläufe zu kennzeichnen und zu vereinfachen, bekommen EDF-Jobs eine Priorität von »-1« zugewiesen.

Abbildung 2: Die Ausgabe des Kommandos »ps -eLfc« zeigt die Kernel-interne Nummer »#6«.

Klassengesellschaft

Spannenderweise kann der Systemarchitekt bei Linux nicht nur mit einem Algorithmus planen, sondern alle von Linux unterstützte Verfahren in Kombination zugleich einsetzen. Seit die Entwickler das aktuelle Completely Fair Scheduling (CFS, [8]) eingeführt haben, steht das gesamte Scheduling dank der so genannten Scheduling-Klassen auf neuen Füßen (Abbildung 4). Sie ermöglichen es, diverse Scheduling-Verfahren gleichzeitig in einem System zu nutzen.

Abbildung 4: Scheduling-Klassen ermöglichen neuerdings den parallelen Einsatz unterschiedlicher Scheduling-Verfahren. EDF gliedert sich als »dl_sched_class« ein.

EDF gliedert sich mit der Klasse »sched_dl« ein. Linux arbeitet dann alle Klassen nacheinander ab: zuerst – folglich mit höchster Priorität – die neue Deadline-Scheduling-Klasse, danach die RT-Klasse und als Drittes schließlich das Completely Fair Scheduling.

Sahnetupfer

Die Entwickler haben Linux in den vergangenen Jahren zunehmend auf die Bedürfnisse von Realtime-Applikationen ausgerichtet. So ist es nur folgerichtig, den Kernel jetzt auch mit einem Earliest Deadline First Scheduler auszustatten. Der weist gegenüber dem klassischen prioritätengesteuerten Scheduling diverse Vorteile auf.

Alle Scheduling-Algorithmen parallel nutzen zu können, ist dabei lediglich das Sahnehäubchen obendrauf und ermöglicht im Verbund mit der Auslastungskontrolle eine einfache und sichere Handhabung.