Dieser Artikel beschreibt die Implementierung von Pipelines im Unix-Kernel. Ich war etwas enttäuscht, dass ein kürzlich erschienener Artikel mit dem Titel „" hat sich herausgestellt nicht über die innere Struktur. Ich wurde neugierig und stöberte in alten Quellen, um die Antwort zu finden.
Worüber reden wir?
Pipelines sind „wahrscheinlich die wichtigste Erfindung in Unix“ – ein bestimmendes Merkmal der zugrunde liegenden Philosophie von Unix, kleine Programme zusammenzustellen, und des bekannten Befehlszeilen-Slogans:
$ echo hello | wc -c
6
Diese Funktionalität hängt vom vom Kernel bereitgestellten Systemaufruf ab pipe, die auf den Dokumentationsseiten beschrieben wird и :
Pipelines bieten einen unidirektionalen Kanal für die Kommunikation zwischen Prozessen. Die Pipeline verfügt über einen Eingang (Schreibende) und einen Ausgang (Leseende). An den Eingang der Pipeline geschriebene Daten können am Ausgang gelesen werden.
Die Pipeline wird durch Aufruf erstellt
pipe(2), der zwei Dateideskriptoren zurückgibt: einer bezieht sich auf die Eingabe der Pipeline, der zweite auf die Ausgabe.
Die Trace-Ausgabe des obigen Befehls zeigt die Erstellung einer Pipeline und den Datenfluss durch sie von einem Prozess zum anderen:
$ strace -qf -e execve,pipe,dup2,read,write
sh -c 'echo hello | wc -c'
execve("/bin/sh", ["sh", "-c", "echo hello | wc -c"], …)
pipe([3, 4]) = 0
[pid 2604795] dup2(4, 1) = 1
[pid 2604795] write(1, "hellon", 6) = 6
[pid 2604796] dup2(3, 0) = 0
[pid 2604796] execve("/usr/bin/wc", ["wc", "-c"], …)
[pid 2604796] read(0, "hellon", 16384) = 6
[pid 2604796] write(1, "6n", 2) = 2
Der übergeordnete Prozess ruft auf pipe()um angehängte Dateideskriptoren zu erhalten. Ein untergeordneter Prozess schreibt in einen Deskriptor und ein anderer Prozess liest dieselben Daten von einem anderen Deskriptor. Die Shell „benennt“ die Deskriptoren 2 und 3 mit dup4 um, damit sie mit stdin und stdout übereinstimmen.
Ohne Pipelines müsste die Shell die Ausgabe eines Prozesses in eine Datei schreiben und sie an einen anderen Prozess weiterleiten, um die Daten aus der Datei zu lesen. Dadurch würden wir mehr Ressourcen und Speicherplatz verschwenden. Pipelines eignen sich jedoch nicht nur zur Vermeidung temporärer Dateien:
Wenn ein Prozess versucht, aus einer leeren Pipeline zu lesen, dann
read(2)wird blockiert, bis die Daten verfügbar sind. Wenn ein Prozess versucht, in eine vollständige Pipeline zu schreiben, dannwrite(2)wird blockiert, bis genügend Daten aus der Pipeline gelesen wurden, um den Schreibvorgang abzuschließen.
Wie die POSIX-Anforderung ist dies eine wichtige Eigenschaft: Schreiben in die Pipeline bis zu PIPE_BUF Bytes (mindestens 512) müssen atomar sein, damit Prozesse über die Pipeline auf eine Weise miteinander kommunizieren können, wie es normale Dateien (die solche Garantien nicht bieten) nicht können.
Mit einer regulären Datei kann ein Prozess seine gesamte Ausgabe in diese Datei schreiben und an einen anderen Prozess weitergeben. Oder Prozesse können in einem harten Parallelmodus arbeiten und einen externen Signalmechanismus (wie ein Semaphor) verwenden, um sich gegenseitig über den Abschluss eines Schreib- oder Lesevorgangs zu informieren. Förderbänder ersparen uns all diesen Ärger.
Was suchen wir?
Ich werde es Ihnen an den Fingern erklären, damit Sie sich leichter vorstellen können, wie ein Förderband funktionieren kann. Sie müssen einen Puffer und einen bestimmten Zustand im Speicher zuweisen. Sie benötigen Funktionen zum Hinzufügen und Entfernen von Daten zum Puffer. Sie benötigen eine Möglichkeit, Funktionen während Lese- und Schreibvorgängen für Dateideskriptoren aufzurufen. Und um das oben beschriebene spezielle Verhalten zu implementieren, sind Sperren erforderlich.
Wir sind nun bereit, den Quellcode des Kernels unter hellem Lampenlicht zu befragen, um unser vages mentales Modell zu bestätigen oder zu widerlegen. Aber seien Sie immer auf das Unerwartete vorbereitet.
Wo suchen wir?
Ich weiß nicht, wo mein Exemplar des berühmten Buches liegt.« mit Unix 6-Quellcode, aber dank kann online gesucht werden sogar ältere Versionen von Unix.
Ein Spaziergang durch die Archive der TUHS gleicht einem Museumsbesuch. Wir können auf unsere gemeinsame Geschichte zurückblicken und ich habe Respekt vor den jahrelangen Bemühungen, all dieses Material Stück für Stück aus alten Kassetten und Ausdrucken wiederherzustellen. Und ich bin mir der Fragmente, die noch fehlen, sehr bewusst.
Nachdem wir unsere Neugier auf die alte Geschichte der Pipelines gestillt haben, können wir uns zum Vergleich moderne Kerne ansehen.
Übrigens pipe ist die Systemrufnummer 42 in der Tabelle sysent[]. Zufall?
Traditionelle Unix-Kernel (1970–1974)
Ich habe keine Spur gefunden pipe(2) weder hinein (Januar 1970), noch in (November 1971), noch im unvollständigen Quellcode (Juni 1972).
Das behauptet die TUHS (Februar 1973) war die erste Version mit Pipelines:
Die dritte Ausgabe von Unix war die letzte Version mit einem in Assembler geschriebenen Kernel, aber auch die erste Version mit Pipelines. Im Jahr 1973 wurde an der Verbesserung der dritten Edition gearbeitet, der Kernel wurde in C umgeschrieben und so war die vierte Edition von Unix geboren.
Ein Leser fand einen Scan eines Dokuments, in dem Doug McIlroy die Idee vorschlug, „Programme wie einen Gartenschlauch zu verbinden“.
Im Buch von Brian KernighanIn der Entstehungsgeschichte von Förderbändern wird dieses Dokument ebenfalls erwähnt: „... es hing 30 Jahre lang in meinem Büro bei Bell Labs an der Wand.“ Hier und noch eine Geschichte von :
Als Unix auf den Markt kam, veranlasste mich meine Leidenschaft für Coroutinen dazu, den Betriebssystemautor Ken Thompson zu bitten, zuzulassen, dass Daten, die in einen Prozess geschrieben wurden, nicht nur zum Gerät, sondern auch zum Ausgang eines anderen Prozesses gelangen. Ken entschied, dass es möglich war. Als Minimalist wollte er jedoch, dass jedes Systemmerkmal eine bedeutende Rolle spielt. Ist das direkte Schreiben zwischen Prozessen wirklich ein großer Vorteil gegenüber dem Schreiben in eine Zwischendatei? Und erst als ich einen konkreten Vorschlag mit dem eingängigen Namen „Pipeline“ und einer Beschreibung der Syntax des Zusammenspiels von Prozessen machte, rief Ken schließlich aus: „Ich werde es tun!“.
Und tat es. Eines schicksalhaften Abends änderte Ken den Kernel und die Shell, reparierte mehrere Standardprogramme, um zu standardisieren, wie sie Eingaben (die möglicherweise aus einer Pipeline stammen) akzeptieren, und änderte Dateinamen. Am nächsten Tag wurden Pipelines sehr häufig in Anwendungen eingesetzt. Am Ende der Woche schickten die Sekretärinnen damit Dokumente aus Textverarbeitungsprogrammen an den Drucker. Etwas später ersetzte Ken die ursprüngliche API und Syntax zum Umschließen der Verwendung von Pipelines durch sauberere Konventionen, die seitdem verwendet werden.
Leider ist der Quellcode für den Unix-Kernel der dritten Edition verloren gegangen. Und obwohl wir den Kernel-Quellcode in C geschrieben haben , das im November 1973 veröffentlicht wurde, aber einige Monate vor der offiziellen Veröffentlichung erschien und keine Implementierung von Pipelines enthält. Es ist schade, dass der Quellcode für dieses legendäre Unix-Feature verloren geht, vielleicht für immer.
Wir haben Dokumentationstext für pipe(2) aus beiden Versionen, sodass Sie zunächst die Dokumentation durchsuchen können (Für bestimmte Wörter, die „manuell“ unterstrichen sind, eine Folge von ^H-Literalen, gefolgt von einem Unterstrich!). Dieses Proto-pipe(2) ist in Assembler geschrieben und gibt nur einen Dateideskriptor zurück, stellt aber bereits die erwartete Kernfunktionalität bereit:
Systemaufruf Rohr erstellt einen E/A-Mechanismus namens Pipeline. Der zurückgegebene Dateideskriptor kann für Lese- und Schreibvorgänge verwendet werden. Wenn etwas in die Pipeline geschrieben wird, puffert sie bis zu 504 Byte Daten, danach wird der Schreibvorgang angehalten. Beim Lesen aus der Pipeline werden die gepufferten Daten übernommen.
Im folgenden Jahr wurde der Kernel in C umgeschrieben erhielt sein modernes Aussehen mit dem Prototyp „pipe(fildes)»:
Systemaufruf Rohr erstellt einen E/A-Mechanismus namens Pipeline. Die zurückgegebenen Dateideskriptoren können in Lese- und Schreibvorgängen verwendet werden. Wenn etwas in die Pipeline geschrieben wird, wird der in r1 (bzw. fildes[1]) zurückgegebene Deskriptor verwendet, bis zu 4096 Byte Daten gepuffert, wonach der Schreibvorgang angehalten wird. Beim Lesen aus der Pipeline übernimmt der an r0 zurückgegebene Deskriptor (bzw. fildes[0]) die Daten.
Es wird davon ausgegangen, dass nach der Definition einer Pipeline zwei (oder mehr) interagierende Prozesse (durch nachfolgende Aufrufe erstellt) entstehen Gabel) übergibt Daten aus der Pipeline mithilfe von Aufrufen lesen и schreiben.
Die Shell verfügt über eine Syntax zum Definieren eines linearen Arrays von Prozessen, die über eine Pipeline verbunden sind.
Aufrufe zum Lesen aus einer leeren Pipeline (die keine gepufferten Daten enthält), die nur ein Ende hat (alle Schreibdateideskriptoren geschlossen), geben „Ende der Datei“ zurück. Schreibaufrufe in einer ähnlichen Situation werden ignoriert.
Früheste Bedenken (Juni 1974), aber es ist fast identisch mit dem, das in der nächsten Veröffentlichung erschien. Nur Kommentare hinzugefügt, daher kann die fünfte Auflage übersprungen werden.
Sechste Unix-Ausgabe (1975)
Ich fange an, Unix-Quellcode zu lesen (Mai 1975). Vor allem dank Löwen es ist viel einfacher zu finden als die Quellen früherer Versionen:
Seit vielen Jahren das Buch Löwen war das einzige Dokument zum Unix-Kernel, das außerhalb von Bell Labs verfügbar war. Obwohl die Lizenz der sechsten Auflage Lehrern die Nutzung des Quellcodes erlaubte, schloss die Lizenz der siebten Auflage diese Möglichkeit aus, sodass das Buch in illegalen, maschinengeschriebenen Kopien verbreitet wurde.
Heute können Sie eine Neuauflage des Buches erwerben, dessen Cover Studierende am Kopierer zeigt. Und dank Warren Toomey (der das TUHS-Projekt gestartet hat) können Sie es herunterladen . Ich möchte Ihnen eine Vorstellung davon geben, wie viel Aufwand in die Erstellung der Datei gesteckt wurde:
Vor über 15 Jahren habe ich eine Kopie des bereitgestellten Quellcodes eingegeben Löwenweil mir die Qualität meines Exemplars im Vergleich zu einer unbekannten Anzahl anderer Exemplare nicht gefiel. Die TUHS existierte noch nicht und ich hatte keinen Zugriff auf die alten Quellen. Aber 1988 fand ich ein altes Band mit 9 Spuren, das von einem PDP11-Computer gesichert war. Es war schwer zu sagen, ob es funktionierte, aber es gab einen intakten /usr/src/-Baum, in dem die meisten Dateien mit 1979 markiert waren, was schon damals alt aussah. Es war die siebte Ausgabe oder ein PWB-Derivat, dachte ich.
Ich habe den Fund als Grundlage genommen und die Quellen manuell auf den Stand der sechsten Auflage gebracht. Ein Teil des Codes blieb gleich, ein Teil musste leicht bearbeitet werden, wodurch das moderne Token += in das veraltete =+ geändert wurde. Etwas wurde einfach gelöscht, etwas musste komplett neu geschrieben werden, aber nicht zu viel.
Und heute können wir an der TUHS online den Quellcode der sechsten Auflage von lesen .
Das Hauptmerkmal des C-Codes vor der Zeit von Kernighan und Ritchie ist übrigens auf den ersten Blick sein Kürze. Es kommt nicht oft vor, dass ich Codeschnipsel ohne umfangreiche Bearbeitung einfügen kann, damit sie in einen relativ schmalen Anzeigebereich auf meiner Website passen.
Am Anfang Es gibt einen erläuternden Kommentar (und ja, es gibt noch mehr). ):
/*
* Max allowable buffering per pipe.
* This is also the max size of the
* file created to implement the pipe.
* If this size is bigger than 4096,
* pipes will be implemented in LARG
* files, which is probably not good.
*/
#define PIPSIZ 4096
Die Puffergröße hat sich seit der vierten Ausgabe nicht geändert. Aber hier sehen wir, ohne öffentliche Dokumentation, dass Pipelines einst Dateien als Fallback-Speicher verwendeten!
Die LARG-Dateien entsprechen , der vom „großen Adressierungsalgorithmus“ zur Verarbeitung verwendet wird zur Unterstützung größerer Dateisysteme. Da Ken gesagt hat, dass es besser ist, sie nicht zu benutzen, verlasse ich mich gern auf sein Wort.
Hier ist der eigentliche Systemaufruf pipe:
/*
* The sys-pipe entry.
* Allocate an inode on the root device.
* Allocate 2 file structures.
* Put it all together with flags.
*/
pipe()
{
register *ip, *rf, *wf;
int r;
ip = ialloc(rootdev);
if(ip == NULL)
return;
rf = falloc();
if(rf == NULL) {
iput(ip);
return;
}
r = u.u_ar0[R0];
wf = falloc();
if(wf == NULL) {
rf->f_count = 0;
u.u_ofile[r] = NULL;
iput(ip);
return;
}
u.u_ar0[R1] = u.u_ar0[R0]; /* wf's fd */
u.u_ar0[R0] = r; /* rf's fd */
wf->f_flag = FWRITE|FPIPE;
wf->f_inode = ip;
rf->f_flag = FREAD|FPIPE;
rf->f_inode = ip;
ip->i_count = 2;
ip->i_flag = IACC|IUPD;
ip->i_mode = IALLOC;
}
Der Kommentar beschreibt deutlich, was hier passiert. Aber es ist nicht so einfach, den Code zu verstehen, teilweise weil „» und registriert R0 и R1 Es werden Systemaufrufparameter und Rückgabewerte übergeben.
Versuchen wir es mit auf die Festplatte legen , und mit der Hilfe - zwei speichern . Wenn alles gut geht, setzen wir Flags, um diese Dateien als die beiden Enden der Pipeline zu identifizieren, verweisen sie auf denselben Inode (dessen Referenzanzahl 2 wird) und markieren den Inode als geändert und in Verwendung. Achten Sie auf Anfragen an in Fehlerpfaden, um den Referenzzähler im neuen Inode zu dekrementieren.
pipe() fällig durch R0 и R1 Gibt Dateideskriptornummern zum Lesen und Schreiben zurück. falloc() gibt einen Zeiger auf eine Dateistruktur zurück, gibt aber auch „via“ zurück u.u_ar0[R0] und einen Dateideskriptor. Das heißt, der Code wird gespeichert r Dateideskriptor zum Lesen und weist einen Deskriptor zum direkten Schreiben zu u.u_ar0[R0] nach dem zweiten Anruf falloc().
Flagge FPIPE, das wir beim Erstellen der Pipeline festlegen, steuert das Verhalten der Funktion , das bestimmte I/O-Routinen aufruft:
/*
* common code for read and write calls:
* check permissions, set base, count, and offset,
* and switch out to readi, writei, or pipe code.
*/
rdwr(mode)
{
register *fp, m;
m = mode;
fp = getf(u.u_ar0[R0]);
/* … */
if(fp->f_flag&FPIPE) {
if(m==FREAD)
readp(fp); else
writep(fp);
}
/* … */
}
Dann die Funktion readp() в pipe.c liest Daten aus der Pipeline. Es ist jedoch besser, die Implementierung ausgehend von zu verfolgen writep(). Auch hier ist der Code aufgrund der Art der Argumentübergabekonvention komplizierter geworden, einige Details können jedoch weggelassen werden.
writep(fp)
{
register *rp, *ip, c;
rp = fp;
ip = rp->f_inode;
c = u.u_count;
loop:
/* If all done, return. */
plock(ip);
if(c == 0) {
prele(ip);
u.u_count = 0;
return;
}
/*
* If there are not both read and write sides of the
* pipe active, return error and signal too.
*/
if(ip->i_count < 2) {
prele(ip);
u.u_error = EPIPE;
psignal(u.u_procp, SIGPIPE);
return;
}
/*
* If the pipe is full, wait for reads to deplete
* and truncate it.
*/
if(ip->i_size1 == PIPSIZ) {
ip->i_mode =| IWRITE;
prele(ip);
sleep(ip+1, PPIPE);
goto loop;
}
/* Write what is possible and loop back. */
u.u_offset[0] = 0;
u.u_offset[1] = ip->i_size1;
u.u_count = min(c, PIPSIZ-u.u_offset[1]);
c =- u.u_count;
writei(ip);
prele(ip);
if(ip->i_mode&IREAD) {
ip->i_mode =& ~IREAD;
wakeup(ip+2);
}
goto loop;
}
Wir wollen Bytes in den Pipeline-Eingang schreiben u.u_count. Zuerst müssen wir den Inode sperren (siehe unten). plock/prele).
Dann überprüfen wir den Inode-Referenzzähler. Solange beide Enden der Pipeline offen bleiben, sollte der Zähler 2 sein. Wir halten an einem Link fest (von rp->f_inode), wenn der Zähler also kleiner als 2 ist, sollte dies bedeuten, dass der Lesevorgang sein Ende der Pipeline geschlossen hat. Mit anderen Worten: Wir versuchen, in eine geschlossene Pipeline zu schreiben, was ein Fehler ist. Erster Fehlercode EPIPE und signalisieren SIGPIPE erschien in der sechsten Ausgabe von Unix.
Aber auch wenn das Förderband geöffnet ist, kann es voll sein. In diesem Fall geben wir die Sperre frei und gehen in den Ruhezustand, in der Hoffnung, dass ein anderer Prozess aus der Pipeline liest und genügend Platz darin freigibt. Wenn wir aufwachen, kehren wir zum Anfang zurück, legen das Schloss wieder auf und starten einen neuen Schreibzyklus.
Wenn in der Pipeline genügend freier Speicherplatz vorhanden ist, schreiben wir mithilfe von Daten darauf . Parameter i_size1 Die Inode'a (bei einer leeren Pipeline kann gleich 0 sein) zeigt auf das Ende der Daten, die sie bereits enthält. Wenn genügend Platz zum Schreiben vorhanden ist, können wir die Pipeline damit füllen i_size1 auf PIPESIZ. Dann geben wir die Sperre frei und versuchen, jeden Prozess zu aktivieren, der darauf wartet, aus der Pipeline zu lesen. Wir gehen zurück zum Anfang, um zu sehen, ob wir es geschafft haben, so viele Bytes zu schreiben, wie wir brauchten. Wenn nicht, starten wir einen neuen Aufnahmezyklus.
Normalerweise Parameter i_mode Inode wird zum Speichern von Berechtigungen verwendet r, w и x. Aber im Fall von Pipelines signalisieren wir mithilfe von Bits, dass ein Prozess auf einen Schreib- oder Lesevorgang wartet IREAD и IWRITE bzw. Der Prozess setzt das Flag und ruft auf sleep(), und es wird erwartet, dass in Zukunft ein anderer Prozess aufgerufen wird wakeup().
Die wahre Magie geschieht in sleep() и wakeup(). Sie werden in implementiert , die Quelle des berühmten Kommentars „Von Ihnen wird nicht erwartet, dass Sie das verstehen“. Zum Glück müssen wir den Code nicht verstehen, schauen Sie sich einfach einige Kommentare an:
/*
* Give up the processor till a wakeup occurs
* on chan, at which time the process
* enters the scheduling queue at priority pri.
* The most important effect of pri is that when
* pri<0 a signal cannot disturb the sleep;
* if pri>=0 signals will be processed.
* Callers of this routine must be prepared for
* premature return, and check that the reason for
* sleeping has gone away.
*/
sleep(chan, pri) /* … */
/*
* Wake up all processes sleeping on chan.
*/
wakeup(chan) /* … */
Der Prozess, der aufruft sleep() für einen bestimmten Kanal kann später von einem anderen Prozess aufgeweckt werden, der ihn aufruft wakeup() für den gleichen Kanal. writep() и readp() Koordinieren Sie ihre Aktionen durch solche gepaarten Anrufe. beachten Sie, dass pipe.c immer Prioritäten setzen PPIPE wenn angerufen sleep(), so alles sleep() kann durch ein Signal unterbrochen werden.
Jetzt haben wir alles, um die Funktion zu verstehen readp():
readp(fp)
int *fp;
{
register *rp, *ip;
rp = fp;
ip = rp->f_inode;
loop:
/* Very conservative locking. */
plock(ip);
/*
* If the head (read) has caught up with
* the tail (write), reset both to 0.
*/
if(rp->f_offset[1] == ip->i_size1) {
if(rp->f_offset[1] != 0) {
rp->f_offset[1] = 0;
ip->i_size1 = 0;
if(ip->i_mode&IWRITE) {
ip->i_mode =& ~IWRITE;
wakeup(ip+1);
}
}
/*
* If there are not both reader and
* writer active, return without
* satisfying read.
*/
prele(ip);
if(ip->i_count < 2)
return;
ip->i_mode =| IREAD;
sleep(ip+2, PPIPE);
goto loop;
}
/* Read and return */
u.u_offset[0] = 0;
u.u_offset[1] = rp->f_offset[1];
readi(ip);
rp->f_offset[1] = u.u_offset[1];
prele(ip);
}
Möglicherweise fällt es Ihnen leichter, diese Funktion von unten nach oben zu lesen. Der Zweig „Lesen und Zurückgeben“ wird normalerweise verwendet, wenn sich einige Daten in der Pipeline befinden. In diesem Fall verwenden wir Lesen Sie so viele Daten wie verfügbar sind, beginnend mit dem aktuellen f_offset Lesen Sie den Wert des entsprechenden Offsets und aktualisieren Sie ihn.
Bei nachfolgenden Lesevorgängen ist die Pipeline leer, wenn der Leseoffset erreicht ist i_size1 am Inode. Wir setzen die Position auf 0 zurück und versuchen, jeden Prozess aufzuwecken, der in die Pipeline schreiben möchte. Wir wissen, dass, wenn das Förderband voll ist, writep() einschlafen ip+1. Und da die Pipeline nun leer ist, können wir sie aktivieren, um ihren Schreibzyklus fortzusetzen.
Wenn es nichts zu lesen gibt, dann readp() kann eine Flagge setzen IREAD und weiter einschlafen ip+2. Wir wissen, was ihn erwecken wird writep()wenn einige Daten in die Pipeline geschrieben werden.
Kommentare zu wird Ihnen helfen, das zu verstehen, anstatt Parameter durch „u» Wir können sie wie normale E/A-Funktionen behandeln, die eine Datei, eine Position, einen Puffer im Speicher übernehmen und die Anzahl der zu lesenden oder zu schreibenden Bytes zählen.
/*
* Read the file corresponding to
* the inode pointed at by the argument.
* The actual read arguments are found
* in the variables:
* u_base core address for destination
* u_offset byte offset in file
* u_count number of bytes to read
* u_segflg read to kernel/user
*/
readi(aip)
struct inode *aip;
/* … */
/*
* Write the file corresponding to
* the inode pointed at by the argument.
* The actual write arguments are found
* in the variables:
* u_base core address for source
* u_offset byte offset in file
* u_count number of bytes to write
* u_segflg write to kernel/user
*/
writei(aip)
struct inode *aip;
/* … */
Was das „konservative“ Blockieren betrifft? readp() и writep() Blockieren Sie Inodes, bis sie fertig sind oder ein Ergebnis erhalten (das heißt, sie rufen auf). wakeup). plock() и prele() einfach funktionieren: mit einem anderen Satz von Anrufen sleep и wakeup Erlauben Sie uns, jeden Prozess aufzuwecken, der die gerade freigegebene Sperre benötigt:
/*
* Lock a pipe.
* If its already locked, set the WANT bit and sleep.
*/
plock(ip)
int *ip;
{
register *rp;
rp = ip;
while(rp->i_flag&ILOCK) {
rp->i_flag =| IWANT;
sleep(rp, PPIPE);
}
rp->i_flag =| ILOCK;
}
/*
* Unlock a pipe.
* If WANT bit is on, wakeup.
* This routine is also used to unlock inodes in general.
*/
prele(ip)
int *ip;
{
register *rp;
rp = ip;
rp->i_flag =& ~ILOCK;
if(rp->i_flag&IWANT) {
rp->i_flag =& ~IWANT;
wakeup(rp);
}
}
Zuerst konnte ich nicht verstehen, warum readp() verursacht nicht prele(ip) vor dem Anruf wakeup(ip+1). Die erste Sache writep() ruft in seiner Schleife dies auf plock(ip), was zu einem Deadlock führt, wenn readp() hat seinen Block noch nicht entfernt, daher muss der Code irgendwie korrekt funktionieren. Wenn man hinschaut wakeup(), wird deutlich, dass es nur den schlafenden Prozess als bereit zur Ausführung markiert, also in der Zukunft sched() habe es wirklich auf den Weg gebracht. So readp() Ursachen wakeup(), entsperrt, setzt IREAD und Ursachen sleep(ip+2)- das alles schon einmal writep() startet den Zyklus neu.
Damit ist die Beschreibung der Pipelines in der sechsten Auflage abgeschlossen. Einfacher Code, weitreichende Implikationen.
(Januar 1979) war eine neue Hauptversion (vier Jahre später), die viele neue Anwendungen und Kernel-Funktionen einführte. Es hat auch erhebliche Änderungen im Zusammenhang mit der Verwendung von Typumwandlungen, Vereinigungen und typisierten Zeigern auf Strukturen erfahren. Jedoch hat sich praktisch nicht verändert. Wir können diese Ausgabe überspringen.
Xv6, ein einfacher Unix-ähnlicher Kernel
Um einen Kern zu schaffen beeinflusst von der sechsten Edition von Unix, aber in modernem C geschrieben, um auf x86-Prozessoren zu laufen. Der Code ist leicht zu lesen und verständlich. Außerdem können Sie es im Gegensatz zu Unix-Quellen mit TUHS kompilieren, ändern und auf etwas anderem als PDP 11/70 ausführen. Daher wird dieser Kern an Universitäten häufig als Lehrmaterial für Betriebssysteme verwendet. Quellen .
Der Code enthält eine klare und durchdachte Implementierung , unterstützt durch einen Puffer im Speicher anstelle eines Inodes auf der Festplatte. Hier gebe ich nur die Definition von „struktureller Pipeline“ und die Funktion pipealloc():
#define PIPESIZE 512
struct pipe {
struct spinlock lock;
char data[PIPESIZE];
uint nread; // number of bytes read
uint nwrite; // number of bytes written
int readopen; // read fd is still open
int writeopen; // write fd is still open
};
int
pipealloc(struct file **f0, struct file **f1)
{
struct pipe *p;
p = 0;
*f0 = *f1 = 0;
if((*f0 = filealloc()) == 0 || (*f1 = filealloc()) == 0)
goto bad;
if((p = (struct pipe*)kalloc()) == 0)
goto bad;
p->readopen = 1;
p->writeopen = 1;
p->nwrite = 0;
p->nread = 0;
initlock(&p->lock, "pipe");
(*f0)->type = FD_PIPE;
(*f0)->readable = 1;
(*f0)->writable = 0;
(*f0)->pipe = p;
(*f1)->type = FD_PIPE;
(*f1)->readable = 0;
(*f1)->writable = 1;
(*f1)->pipe = p;
return 0;
bad:
if(p)
kfree((char*)p);
if(*f0)
fileclose(*f0);
if(*f1)
fileclose(*f1);
return -1;
}
pipealloc() Legt den Status aller übrigen Implementierungen fest, einschließlich Funktionen piperead(), pipewrite() и pipeclose(). Der eigentliche Systemaufruf sys_pipe ist ein Wrapper, der in implementiert ist . Ich empfehle, seinen gesamten Code zu lesen. Die Komplexität liegt auf dem Niveau des Quellcodes der sechsten Auflage, ist aber deutlich einfacher und angenehmer zu lesen.
Linux 0.01
Den Quellcode für Linux 0.01 finden Sie hier. Es wird aufschlussreich sein, die Implementierung von Pipelines in seinem zu untersuchen fs/pipe.c. Hier wird ein Inode verwendet, um die Pipeline darzustellen, aber die Pipeline selbst ist in modernem C geschrieben. Wenn Sie sich durch den Code der sechsten Ausgabe gehackt haben, werden Sie hier keine Probleme haben. So sieht die Funktion aus write_pipe():
int write_pipe(struct m_inode * inode, char * buf, int count)
{
char * b=buf;
wake_up(&inode->i_wait);
if (inode->i_count != 2) { /* no readers */
current->signal |= (1<<(SIGPIPE-1));
return -1;
}
while (count-->0) {
while (PIPE_FULL(*inode)) {
wake_up(&inode->i_wait);
if (inode->i_count != 2) {
current->signal |= (1<<(SIGPIPE-1));
return b-buf;
}
sleep_on(&inode->i_wait);
}
((char *)inode->i_size)[PIPE_HEAD(*inode)] =
get_fs_byte(b++);
INC_PIPE( PIPE_HEAD(*inode) );
wake_up(&inode->i_wait);
}
wake_up(&inode->i_wait);
return b-buf;
}
Auch ohne einen Blick auf die Strukturdefinitionen zu werfen, können Sie herausfinden, wie der Inode-Referenzzähler verwendet wird, um zu überprüfen, ob ein Schreibvorgang zu einem Ergebnis führt SIGPIPE. Zusätzlich zur byteweisen Arbeit ist diese Funktion leicht mit den oben genannten Ideen zu vergleichen. Sogar Logik sleep_on/wake_up sieht nicht so fremd aus.
Moderne Linux-Kernel, FreeBSD, NetBSD, OpenBSD
Ich ging schnell einige moderne Kernel durch. Keiner von ihnen verfügt bereits über eine festplattenbasierte Implementierung (keine Überraschung). Linux hat eine eigene Implementierung. Und obwohl die drei modernen BSD-Kernel Implementierungen enthalten, die auf Code basieren, der von John Dyson geschrieben wurde, sind sie im Laufe der Jahre zu unterschiedlich geworden.
Lesen fs/pipe.c (unter Linux) oder sys/kern/sys_pipe.c (auf *BSD) erfordert es echte Hingabe. Leistung und Unterstützung für Funktionen wie Vektor- und asynchrone E/A sind heutzutage im Code wichtig. Und die Details der Speicherzuweisung, Sperren und Kernelkonfiguration variieren stark. Dies ist nicht das, was Universitäten für einen Einführungskurs in Betriebssysteme benötigen.
Auf jeden Fall war es für mich interessant, ein paar alte Muster (zum Beispiel das Generieren) aufzudecken SIGPIPE und zurück EPIPE beim Schreiben in eine geschlossene Pipeline) in all diesen so unterschiedlichen modernen Kerneln. Ich werde wahrscheinlich nie einen PDP-11-Computer live sehen, aber es gibt noch viel zu lernen aus dem Code, der einige Jahre vor meiner Geburt geschrieben wurde.
Der von Divi Kapoor im Jahr 2011 verfasste Artikel „ist ein Überblick darüber, wie Linux-Pipelines (bisher) funktionieren. A veranschaulicht das Pipeline-Modell der Interaktion, dessen Fähigkeiten die von temporären Dateien übertreffen; und zeigt auch, wie weit sich Pipelines vom „sehr konservativen Sperren“ im Unix-Kernel der sechsten Edition entfernt haben.
Source: habr.com