IOException.de

Das UNIX-Betriebssystem wurde in den sechziger Jahren von Bell Laboratories entwickelt. Ein Großteil der heute populären Betriebssysteme wie GNU/Linux oder Mac OS X verwenden grundlegende Konzepte, die aus dem ursprünglichen UNIX-Betriebssystem stammen. Die BSD Familie oder Solaris sind direkte UNIX-Nachfolger. Man bezeichnet diese Systeme daher als unixoide Betriebssysteme. Es ist kein Zufall, dass die effizientesten, sichersten und fortschrittlichsten Betriebssysteme UNIX-Derivate sind. Unix-Systeme sind ideal für die Zukunft gerüstet, da sie die Grundannahme haben, dass sich alles ständig ändert. Der Aufbau ist deshalb äußerst flexibel gehalten.

Mit der Unix-Philosophie bezeichnet man die Konzepte, die beim Erstellen des ursprünglichen Unix-Systems von den Entwicklern angewandt wurden. UNIX wurde als System für Experten entworfen. Für Leute, die wissen was sie tun und was sie wollen. Auf Einsteigerfreundlichkeit wurde keinen Wert gelegt. Die Benutzerschnittstelle zur Interaktion mit dem Betriebssystem ist die Shell.

Es gibt einige Konzepte, die allgemein unter die Unix-Philosophie fallen. Ich möchte in diesem Beitrag einige der wichtigsten herausgreifen um einen Einblick zu geben.

Make each program do one thing well.
Anstatt ein großes monolithisches Programm zu entwickeln sollte ein Programm genau eine Sache tun — und das richtig! Ein solches Programm hat viele Vorteile:

Programme die genau eine Sache tun können speziell für diese Aufgabe konzipiert werden.

Viele einzelne Programme, die genau eine Sache machen, können sehr einfach kombiniert werden! Aus der Kombination von vielen einzelnen Dingen ergibt sich leicht etwas neues, viel größeres. Wie in einem Werkzeugkasten ist es sehr einfach sich die richtigen Programme für eine Aufgabe zu suchen und diese passend zu kombinieren. All das ermöglicht einen hohen Grad an Abstraktion, der es ermöglicht sehr schnell und effizient ein Ziel zu erreichen.

Um etwa herauszufinden, wie viele verschiedene Dateien in einem Verzeichnis liegen und welchen Typ diese haben können folgende Kommandos in der Shell kombiniert werden: file -b * | sort | uniq -c.
Pipes | sind ein effizientes Konzept um die Programmausgabe direkt als Eingabe an ein anderes Programm weiterzuleiten. Das Programm, an das weitergeleitet wird, beginnt mit der Verarbeitung sobald eine Eingabe vorliegt.
Summiert man die Quelltexte der einzelnen Programme auf kommt man auf mehrere tausend Zeilen Quelltext, die in dieser einen Zeile verwendet werden. Jedes dieser Programme wurde für genau eine Aufgabe entworfen, über Jahre konstant verbessert, ausgebessert und angepasst.

Bei unixoiden Systemen zieht sich dieser Aufbau durch, so sind viele Benutzeroberflächen oft einfach nur grafische Frontends für Kommandozeilentools (diskutil/Festplattendienstprogramm unter Mac OS X oder tcpdump/Wireshark etwa).

Small programs are beautiful.
Programme sollten klein sein. Das macht es einfach sie zu entwickeln, zu pflegen und zu verstehen. Für neue Entwickler ist es leichter sich in das Programm einzuarbeiten, die Funktionalität des Quelltextes ist überschaubar. Die Komplexität eines Programms wird so klein gehalten. Es fällt leichter Fehler zu finden und zu beheben.

Ein weiterer Vorteil ist, dass kleine Programme ressourcenschonend sind: Sie können vom Betriebssystem schnell geladen werden, swapping und paging sind seltener nötig. Im Endeffekt ergibt sich so ein schnelleres Gesamtsystem.

Wie aber legt man fest was ein “kleines” Programm ist? Mike Gancarz gibt in seinem Buch “The UNIX Philosophy” einige Anhaltspunkte: Funktionsdeklarationen, die aufgrund von vielen Parametern umgebrochen werden müssen oder auftretende Probleme, die nicht mehr augenblicklich einem Kontext zugeordnet werden können sind Warnsignale. Strikt der Unix-Philosophie folgend sollte ls keinen Flag zur Formatierung oder Sortierung der Ausgabe haben — hierfür gibt es andere Programme (column, sort, …).

Dieser Aufbau von vielen verschiedene kleinen Programmen die zusammenarbeiten, lässt sich dem Konzept “Divide & Conquer” zuordnen: Dadurch, dass große, komplexe Probleme in einfachere, kleine zerlegt werden wird es einfach diese einzeln zu lösen.

Avoid captive user interfaces.
Programme sollten so geschrieben sein, dass sie problemlos in einem Skript verwendet werden können. Die Schnittstelle muss für Maschinen entworfen sein — nicht für Menschen. Das bedeutet beispielsweise, dass Programme nach dem Aufruf nicht noch auf Benutzereingaben angewiesen sein sollten (“Sind Sie sicher, dass Sie …? y/n”), sondern nur über die Kanäle STDIN, STDOUT & STDERR kommunizieren sollten.
Das macht Automatisierung einfacher, es ist sehr einfach Programme miteinander zu verknüpfen, die eben nicht irgendwann auf eine Benutzereingabe warten und deswegen blocken. Das UNIX-Konzept macht es sehr einfach, Programme zu kombinieren.

Zum Vergleich: Befehle wie dir erzeugen unter Windows-Systemen auf ein leeres Verzeichnis angewandt eine Ausgabe mit mehreren Zeilen — ohne relevanten Informationen. Diese Ausgabe weiterzuverarbeiten oder zu parsen ist nicht ohne weiteres machbar. Programme, die strikt der Unix-Philosophie folgen verhalten sich dagegen nach dem Grundsatz “Silence is golden”.

Build a prototype as soon as possible.
In der Unix-Philosophie nehmen Prototypen eine zentrale Rolle ein. Die Sichtweise ist hier, dass viele traditionelle Softwareentwicklungsprozesse durch Anforderungsanalyse, Spezifikationen, etc. darauf abzielen von Anfang an das ideale System zu den Anforderungen zu bauen. Oder anders ausgedrückt: Beim ersten Mal alles richtig zu machen.

Die Sichtweise der Unix-Philosophie ist hier, dass sich ein solches System nie in einem Zyklus bauen lässt. Systeme müssen verschiedene Phasen durchlaufen und konstant, iterativ verbessert werden um Anforderungen ideal zu erfüllen. In jeder Phase muss dazu gelernt werden. Die Alternative ist einen Prototypen zu bauen und diesen iterativ auszubauen. Da Programme klein und überschaubar sein sollen fällt der Prototypenbau leichter.

Automate everything
Aufgaben, die heute von Hand ausgeführt werden, obwohl sie auch das System übernehmen könnte, sind nüchtern betrachtet Zeitsverschwendung. Da unter unixoiden Systemen Programme darauf ausgelegt sind mit anderen Programmen zu interagieren — und nicht mit Menschen, können Abläufe beispielsweise mittels Shellskripten einfach automatisiert werden. In Shellskripten können Programme und Kommandos wie Funktionen verwendet werden. Die Ausgabe kann direkt in den Programmfluss integriert weren.

Fazit
Die wichtigsten Konzepte zusammengefasst: Dinge einfach halten, Komplexität vermeiden. Eine Sache richtig machen. Programme miteinander kombinieren.

Das war jetzt lediglich ein kleiner Einblick in die Unix-Philosophie. Es gibt noch deutlich mehr Konzepte und man kann die Ideen auch nicht nur auf Betriebssysteme anwenden. Für weitere Informationen kann ich folgende Quellen sehr empfehlen:

• Das Buch “The UNIX Philosophy” von Mike Gancarz
• Chaosseminar zum Thema “Unix-Philosophie” von Markus Schnalke

Natürlich gibt es auch Probleme eines solchen Systemaufbaus. Diese habe ich hier absichtlich nicht thematisiert. Wer sich hierfür interessiert sollte sich etwa zu Plan 9 oder Kernelproblemen informieren.

Die Einführungsvorlesung “Computer Science 50: Introduction to Computer Science I” von Harvard College hat sehr gut gemachte Vorlesungen als Flash Video online, insbesondere die Vorlesungen über die C Grundlagen sind wirklich schön.

Meine Empfehlungen:

• Week 8. Huffman coding. Preprocessing. Compiling. Assembling. Linking. CPUs. Ant-8.
  • Vorlesung 1
  • Vorlesung 2
• Week 9. Writing secure C code. Buffer overruns. Dangerous functions.
  • Vorlesung 1

Die zentrale Frage bei der Implementierung des Schedulers ist die Frage nach der Datenstruktur in der die Tupel gehalten werden. Der Scheduler soll, gemäß der SJF Strategie, immer das Tupel auswählen dessen Joblänge am kürzesten ist. Für solche eine Problemstellung eignet sich die Datenstruktur std::set bzw. std::multiset parametrisiert auf std::pair am Besten. Jedoch ist zu beachten dass die Sortierung bei std::pair normalerweise auf dem ersten Element, also bei uns auf der ThreadId basiert. Daher müssen wir den Vergleichsoperator des std::multiset mit unserem eigenen Operator überschreiben.

/*
Scheduler.h
*/

/*
this struct is used to have a different compare operator for std::pair in my std::multiset. I have to compare the second argument of pair!
*/
struct compareBySecond {
  bool operator() (const std::pair<int,int>& a, const std::pair<int,int>& b) const
  {return (a).second<(b).second;}
};

/*
my scheduler class, schedules the requests
*/

class Scheduler{

  public:
    [  ... ]

  private:
    //multiset holds all pairs with (thread,job)
    std::multiset< std::pair<int,int> , compareBySecond > jobs;

    [  ... ]
    
};

Als Synchronisationselemente kommen normale RW-Locks und Condition-Variablen zur Anwendung, auf diese Standardelemente wird hier nicht weiter eingegangen. Guten Beispielcode für diese Elemente findet sich in den Qt3.3-Quellen (z.B.: QReadWriteLock).

Die einzige Methode die von den Anfragethreads ausgeführt wird ist Scheduler::enqueue(int thread, int length) (siehe Teil 1). Bemerkenswert ist hier nur der letzte Aufruf, da wir ja immer eine möglichst volle Queue gewährleisten wollen wartet der Scheduler darauf dass er Jobs erst auswählt, wenn die Queue voll ist oder eine volle Queue nicht mehr erreicht werden kann. Hierzu ist die Condition-Variable cv_queuefull nötig auf die beim Überprüfen der Queue gewartet wird.

/*
enqueues a job
*/
void  Scheduler::enqueue(int thread, int length){

  //wait if queue is full or thread has already job in queue
  while(isQueueFull() || threadHasRequestInQueue(thread)){
    cv->wait();
  }
  
  //new pair for enqueueing
  std::pair<int,int> tmp(thread,length);
  
  //lock and insert in queue
  rw->lockWrite();
  jobs.insert(tmp);
  rw->unlockWrite();
  
  //we did it!
  std::cout << "requester " << thread << " joblength " << length << std::endl;
  
  //signal scheduler thread that thread is now maybe full
  cv_queuefull->signal();  
}

Die beiden hier noch verwendeten Methoden bool Scheduler::isQueueFull() und bool Scheduler::threadHasRequestInQueue(int thread) sind aus Implementierungssicht trivial.

Die wichtigste Methode in der die eigentlichen Jobs “abgearbeitet” werden ist Scheduler::processNextJob(), hier muss zunächst überprüft werden ob die Queue bereit ist. Dies geschieht in Scheduler::QueueReady() und ist weiter unten erläutert. Für die Auswahl des nächsten Jobs mit der kürzesten Joblänge reicht es das erste Element des Sets zu entnehmen, dies ist nach der von uns definierten Ordnung im Set automatisch der Job mit der kürzesten Laufzeit. Nach dem Abarbeiten wird der Job aus der Queue gelöscht. Falls gerade ein Thread darauf wartet einen Job zu enqueuen dem es vorher nicht möglich war zu enqueuen da er schon einen Job in der Queue hatte wird dieser zum Schluss noch aufgeweckt.

/*
processes the next job
*/
void  Scheduler::processNextJob(){
  //is queue ready? 
  QueueReady();
  
  //get job
  rw->lockRead();
  std::pair<int,int> tmp = *( jobs.begin());
  rw->unlockRead();
  
  //process .......... :-)
  std::cout << "service requester " << tmp.first << " joblength " << tmp.second << std::endl;

  //delete from queue
  rw->lockWrite();
  jobs.erase(jobs.find(tmp)); 
  rw->unlockWrite();

  //wake up all guys that wait on enqueuing
  cv->signalAll();
}

Für die Überprüfung ob die Queue bereit ist, sind zwei Bedingungen nötig: Ersten muss die Queue voll sein, siehe Annahmen. In dem Fall dass schon Threads beendet wurden kann es passieren dass die Queue nicht voll werden kann. In diesem Fall soll der Scheduler trotz nicht voller Queue seine Arbeit aufnehmen. Hier wäre noch Optimierungspotential gegeben, da nicht garantiert wird dass die Queue in momentanen Zustand der Threads immer so voll wie möglich ist.

/*
checks if queue is ready
*/
void Scheduler::QueueReady(){
  while(!isQueueFull() && (jobs.size() < nrOfThreads) ){
    //wait if our queue is not full or some threads are already dead, thus we can proceed if #threads<Queuesize
    cv_queuefull->wait();
  }
}

Der hier vorgestellte Scheduler soll am Ende folgende Rahmenbedingungen erfüllen:

• Jeder Thread darf nur maximal eine Anfrage in der Warteschlange haben.
• Ein Thread stoppt falls alle seine Anfragen bearbeitet wurden.
• Der Scheduler arbeitet nach dem SJF (Shortest Job First) Verfahren
• Die Warteschlangengröße muss beim Programmstart festlegbar sein

Als Eingabe erhält das Programm die Warteschlangenlänge und eine Liste von Eingabedateien. Jede Eingabedatei entspricht einem anfragenden Thread und beinhaltet eine Liste von Nummern die die Joblänge symbolisieren sollen.

Der erste Teil besteht aus der Implementierung des Rahmenprogramm der sich der später zu implementierenden Schedulerklasse bedient.
Der erste Teil der main() Methode besteht aus den Auslese- und Initialisierungaufrufen. Insbesondere wird der Scheduler mit der Anzahl der Threads und der maximalen Warteschlangenlänge initialisiert.

  //get queue-size
  int maxQueue=atoi(argv[1]);
   
  if(maxQueue<=0) {
     std::cout << "min. queue size is 1" << std::endl;
     return 0;
  }
   
   
  //vector so store filenames   
  std::vector<std::string> files;
   
  //count #threads
  int numOfThreads=0;
   
  //save filenames 
  for (int i = 2; i < argc; i++) {
     files.push_back(std::string(argv[i]));
     //every file is one thread
     numOfThreads++;
  }
   
  //create new scheduler
  scheduler= new Scheduler(maxQueue, numOfThreads);  
  
  //just temp storage for reading file
  std::string line;
  
  //iterate through parameters
  for(int i = 0; i< argc-2; i++){
    //new parameter => new thread
    jobs.push_back(std::vector<int>());
    //open file
    std::ifstream myfile(files.at(i).c_str());
    if (myfile.is_open())
    {
      //push all job lengthes in vector
      while (! myfile.eof() )
      {
        std::getline (myfile,line);
        (jobs.at(i)).push_back(atoi(line.c_str()));
      }
      //close file
      myfile.close();
    }
  }

Im nächsten Schritt müssen alle anfragenden Threads gestartet werden, in diesem Fall kommen einfache pthreads zur Anwendung. Zu beachten ist dass &run_thread der Funktionspointer auf die sogenannte run-Methode darstellt.

   //array of threads
   pthread_t th[numOfThreads];
   
   //array of int* to transfer thread nr. to thread
   int* numbers[numOfThreads];
     
   for (int i = 0; i < numOfThreads; i++) {
      //save thread nr.
      numbers[i]=new int(i);
      //create thread and transfer parameter
      pthread_create (&th[i], NULL, &run_thread, numbers[i]);
   }

Im main() Thread läuft auch der Scheduler der solange Anfragen abarbeitet bis die Warteschlange leer ist. Danach muss um ein sauberes Programmende zu gewährleisten noch auf alle Threads gewartet werden.

   //process jobs until Queue is empty
   while(!scheduler->isQueueEmpty()){
       scheduler->processNextJob();
   }
  
  
   //wait until all threads are finished
   for (int i = 0; i < numOfThreads; i++){
      pthread_join (th[i], NULL);
   }

   return 0;
 

Die von den Anfragethreads ausgeführte Methode run_thread(void *number) hat ein paar Stolperfallen; hier ist zu beachten dass an pthreads übergebene Funktionen nur void* Pointer als Parameter haben dürfen, deshalb muss auch innerhalb der Methode die Threadnummer wieder auf int* gecastet werden. Nach dem einreihen aller Anfragen in die Warteschlange des Schedulers kann sich der Thread beenden.

static void* run_thread (void *number) {

   for(unsigned int i=0; i< (jobs.at(*( (int*) number))).size()-1;i++){
    //enqueue all jobs in waiting queue
    scheduler->enqueue(*( (int*) number), (jobs.at(*( (int*) number))).at(i) );
   }
   //all jobs are enqueued => thread has done his work
   scheduler->decreaseThreads();
   pthread_exit (NULL);
}

In nächsten Teil wird detailliert auf die Funktionsweise und den Aufbau eines des hier benutzten Schedulers eingegangen.