Wie läuft ein Befehlszyklus ab? Am Anfang steht die Adresse des nächsten auszuführenden Befehls im Befehlszählregister, die ins Speicheradreßregister übertragen wird und von dort auf den Adreßbus gelangt. Damit wird die entsprechende Zelle im Hauptspeicher angesprochen, deren Inhalt über den Datenbus in das Speicherinhaltsregister der CPU übertragen wird. Da es sich um einen Befehl handelt, wird dieser ins Befehlsregister kopiert und dort decodiert und interpretiert. Dazu sind meist weitere Speicherzugriffe notwendig (Abholen der Befehlsoperanden). [1801.KE1 S. 7f.] Welche Speicherarten gibt es allgemein? Hauptspeicher, Cache, Sekundärspeicher (Magnetplatten), Tertiärspeicher (preiswerte, auswechselbare Medien wie z.B. Disketten und CD-ROMs). [1801.KE1 S. 6ff.] Wie funktioniert DMA? Voraussetzung sind das Vorhandensein eines DMA-Controllers, der selbständig unter Umgehung der CPU über den Bus Daten in den Hauptspeicher übertragen kann, sowie Gerätecontroller, die für das DMA-Verfahren ausgelegt sind. Der Ablauf ist folgender: Der Gerätetreiber teilt dem Controller die Nummer des zu lesenden Blocks mit und dem DMA-Controller die Anfangsadresse des Hauptspeicherbereichs, in den die Daten zu übertragen sind. Jedesmal, wenn das nächste Wort im Register des Controllers bereitsteht, sendet er über eine Anforderungsleitung ein Signal an den DMA-Controller; dieser antwortet mit einem Signal über eine Bestätigungsleitung (handshaking), übergibt auf dem Adreßbus die Hauptspeicheradresse für das Datenwort und zählt die Adresse weiter hoch. Nach Übertragung aller Datenwörter löst er eine Unterbrechung der CPU aus. [1801.KE1 S. 24] Was sind die Bestandteile eines Prozessors? Ein von-Neumann-Rechner (= Prozessor) besteht aus: Steuerwerk, Operationswerk, Registersatz, Adresswerk, Systembus-Schnittstelle. Der Kurs 1801 beschränkt sich auf die Nennung von Rechenwerk, Befehlszählregister (Programmzähler), Speicheradressregister, Speicherinhaltsregister, Befehlsregister und Akkumulator. [1801.KE1 S. 6ff., ausführlich in 1707.KE7 S. 24f.] Wie ist die allgemeine Hardwarearchitektur eines Computers? Die wesentlichen Bestandteile der Hardware sind: Prozessor (CPU), Hauptspeicher (main memory) und die Ein-Ausgabegeräte (I/O devices). [1801.KE1 S. 6] Was sind virtuelle Geräte? Treiber, Controller und Gerät bilden als virtuelles Gerät eine konzeptuelle Einheit; daran lassen sich die Konzepte der Abstraktion, der Kapselung und des Schichtenmodells demonstrieren. [1801.KE1 S. 18] Mit welchem Datentyp kann der Hauptspeicher beschrieben werden? Als Array von Wörtern. [1801.KE1 S. 6] Was passiert beim Lesezugriff auf die Festplatte? Hier wird die Hardware-Sicht beschrieben (zur Software-Sicht siehe Frage [147]): Zunächst wird der Schreib-/Lesekopf auf den richtigen Zylinder positioniert; dann wird abgewartet, bis der gesuchte Sektor am Kopf vorbeiläuft; dann wird der Sektor gelesen und seine Daten werden in den Hauptspeicher übertragen. Die Zugriffszeit setzt sich folglich zusammen aus Positionierungs-, Latenz- und Übertragungszeit. [1801.KE1 S. 11] Wie ist eine Festplatte aufgebaut? Aus einer oder mehreren magnetisierbar beschichteten Scheiben, die synchron über eine Spindel angetrieben werden und sich (fast) permanent mit gleicher Umdrehungszahl drehen. Auf jeder Oberfläche gleitet ein Schreib-/Lesekopf, wobei alle Köpfe synchron auf die so genannten Zylinder (= alle übereinander liegenden Spuren aller Platten) positioniert werden. Jede der mehreren tausend kreisförmigen Spuren pro Platte ist in mehrere hundert Sektoren unterteilt; ein Sektor ist die kleinste Einheit, auf die wahlfrei zugegriffen werden kann. [1801.KE1 S. 10f.] Wie läuft so ein Interrupt genau ab? Nach vollständiger Beendigung des laufenden Befehls gibt der Prozessor der Interruptanforderung statt, falls der Interrupt zugelassen ist (NMI oder durch IE-Bit im Statusregister). Anschließend wird der aktuelle Prozessorzustand gerettet und über einen Interruptvektor die Startadresse einer Interruptroutine ermittelt und diese gestartet. [1801.KE1 S. 21, ausführlich in 1707.KE7 S. 41f., 44f.] Welche Interrupts gibt es? Hardware-Unterbrechungen und Software-Unterbrechungen. [1801.KE1 S. 21ff.] Wie können Zugriffe auf die Festplatte optimiert werden? Die drei üblichen Strategien sind: FCFS (first-come-first-served) bearbeitet die Aufträge in der Reihenfolge ihres Eingangs; diese Strategie ist am wenigsten optimal. SSTF (shortest-seek-time-first) bearbeitet jeweils denjenigen Auftrag als nächsten, dessen Spur der momentanen Position des Schreib-/Lesekopfes am nächsten liegt. SCAN bewegt den Kopf abwechselnd von außen nach innen und zurück über die gesamte Platte und führt dabei die Aufträge aus, deren Spuren gerade überquert werden. [1801.KE1 S. 12] Was haben Threads nicht gemeinsam? Jeder Thread hat seine eigenen Registerinhalte, insbesondere seinen eigenen Befehlszähler, und sein eigenes Stacksegment. [1801.KE2 S. 63f.] Wie werden Prozesse generiert? Das Betriebssystem stellt einen Prozessraum bereit, lädt das angeforderte Programm, initialisiert Register und das Stacksegment, setzt den Befehlszähler auf den Anfangswert und macht den Prozess bereit. Im Kurs wird die C-Funktion fork vorgestellt, die über einen Systemaufruf eine genaue Kopie des aufrufenden Elternprozesses (einschließlich aller Registerinhalte, Stack und Befehlszähler) erzeugt und bereit macht. [1801.KE2 S. 59ff.] Wie kann es zu einem deadlock kommen? Zum Beispiel durch die Benutzung mehrerer Semaphoren in der falschen Reihenfolge: Angenommen, es gibt einen binären Semaphor Z, der den Zugriff auf einen Puffer steuert, und zwei Semaphoren F und B für bis zu n freie bzw. belegte Einträge in diesem Puffer. Ferner sei Z.count = 1, F.count = 0 und B.count = n, d.h. es gibt keine freien Einträge. Wenn nun ein einfügender Prozess zuerst down(Z) ausführt, sperrt er damit den Zugriff für jeden anderen Prozess; ein anschließendes down(F) läßt ihn ebenfalls blockieren, da ja keine Einträge frei sind. Ein anderer Prozess, der vielleicht up(F) ausführen könnte, damit der erste Prozess wieder bereit werden kann, kommt aber nicht dazu, weil er zuvor bei Abfrage von Z keinen Zugriff erhält. Damit sind sowohl der erste Prozess als auch alle anderen Prozesse für immer blockiert. Das nennt man Verklemmung oder deadlock. Die richtige Reihenfolge, die keinen deadlock verursacht, wäre: (a) für einfügende Prozesse: down(F), down(Z), Einfügen, up(Z), up(F); (b) für entnehmende Prozesse: down(B), down(Z), Entnehmen, up(Z), up(B). [1801.KE2 S. 79f., 56f.] Wie werden Prozesse generiert? Das Betriebssystem stellt einen Prozessraum bereit, lädt das angeforderte Programm, initialisiert Register und das Stacksegment, setzt den Befehlszähler auf den Anfangswert und macht den Prozess bereit. Im Kurs wird die C-Funktion fork vorgestellt, die über einen Systemaufruf eine genaue Kopie des aufrufenden Elternprozesses (einschließlich aller Registerinhalte, Stack und Befehlszähler) erzeugt und bereit macht. [1801.KE2 S. 59ff.] Wenn in einem Multitaskingsystem ein Prozess vom Prozessor ausgeführt wird, wie geht dass dann vonstatten, dass ein anderer Prozess drankommt (wo doch der Prozessor vom einen Prozess blockiert ist)? Der Timer erzeugt einen Interrupt, aufgrund dessen der Scheduler des Betriebssystems den Prozessor erhält. Der Scheduler verwaltet die bereiten Prozesse und übergibt an den, der an der Reihe ist. Wie heißt der Teil des Betriebssystems, der für die Umschaltung (von Prozessen) zuständig ist? Dispatcher. In welchen Fällen ist die Scheduling-Strategie shortestjob- first sinnvoll? Im Batchbetrieb. [1801, KE 1, S.30] Wie kann ein Prozess bei Round-Robin seine Zeitscheibe vorzeitig freigeben? Durch Systemaufrufe. [1801, KE 1, S.31] Nutzen denn beim Round-Robin alle Prozesse ihre Zeitscheibe voll aus? Nein, durch das Auslösen von Interrupts kann ein Prozess seine Zeitscheibe vorzeitig verlieren, bzw. zurückgeben (preemptive Multitasking). Was passiert beim Lesezugriff auf die Festplatte? (Softwaresicht) Hier wird die Software-Sicht beschrieben (zur Hardware-Sicht siehe Frage [129]): 1. Eine Software-Unterbrechung wird ausgelöst, der Kontext des Prozesses wird gerettet, der Ein-/Ausgabeteil des Betriebssystems wird gerufen. 2. Falls die Daten schon im Cache stehen, werden sie in den Adressraum des Prozesses kopiert, der sofort wieder rechnend wird. 3. Anderenfalls wird der Prozess blockiert, der Leseauftrag wird in die Warteschlange des Plattenlaufwerks geschrieben (= Auftrag an den Gerätetreiber). 4. Sobald der Gerätetreiber rechnend wird, liest er den Auftrag aus der Warteschlange, reserviert Speicherplatz und schickt einen Lesebefehl an den Plattencontroller. Danach blockiert er. 5. Der Plattencontroller führt den Leseauftrag aus, überträgt (mit dem DMAController) die Daten in den reservierten Bereich und löst eine Unterbrechung aus. 6. Der Unterbrechungsvektor aktiviert die Unterbrechungsroutine für Plattenzugriffe, die den Gerätetreiber wieder bereit macht und dann von der Unterbrechung zurückkehrt. 7. Sobald der Gerätetreiber rechnend wird, entfernt er den Auftrag aus der Warteschlange, informiert den Ein-/Ausgabeteil des Betriebssystems (betroffener Prozess, Adresse des reservierten Speicherplatzes) und wird wieder bereit. 8. Der Ein-/Ausgabeteil des Betriebssystems kopiert die Daten aus dem Systemspeicher in den Adressraum des Prozesses, der wieder bereit wird. 9. Sobald der Prozess wieder rechnend wird, ist der Systemaufruf beendet. [1801.KE1 S. 32] Wann ist Round-Robin bei der Scheduling Strategie sinnvoll? Im Time-Sharing-Betrieb (Multitasking). Wie heißt die Datenstruktur, welche die Prozesse verwaltet? Der Scheduler. Wie funktioniert die inode-Struktur? Die inode-Struktur ist eine Besonderheit von UNIX und seinen Derivaten. Am Anfang eines inode stehen die Attribute der Datei, gefolgt von den physischen Adressen der ersten 12 Blöcke und drei weiteren Adressen, nämlich eines einfach-indirekten, eines zweifachindirekten und eines dreifach-indirekten Index. Der einfach-indirekte Index enthält bei einer Blockgröße von B bits und einer Partitiongröße von b Blöcken B / log2 b Blockadressen. Der zweifach-indirekte Index verweist auf ebenso viele Blöcke der einfach-indirekten, der dreifach-indirekte Index auf ebenso viele Blöcke der zweifach-indirekten Struktur. [1801.KE2 S. 71f., 81] Wie funktioniert die FAT? Die FAT (file allocation table) ist eine Struktur, die von den Betriebssystemen MS-DOS (einschließlich Windows) und OS/2 verwendet wird. Sämtliche Blöcke der Magnetplatte werden darin verwaltet, wobei der Verzeichniseintrag einer Datei auf den ersten Block der Datei verweist. In der FAT findet sich zu jedem Block die Nummer des Folgeblocks bzw. ein Kenner für eof (end of file). Sinnvollerweise wird zur Laufzeit eine Kopie der FAT im Cache des Hauptspeichers gehalten. [1801.KE2 S. 71f.] Wie wird der Speicher einer Festplatte verwaltet? Zur optimalen Nutzung des Platzes wurde die Forderung nach zusammenhängender Speicherung aufgegeben. Stattdessen wurden Speicherverfahren entwickelt, bei denen die Blöcke einzeln gespeichert werden können, wo immer gerade Platz frei ist (Stichworte FAT und inode). [1801.KE2 S. 71] 1): Wie wird der Hauptspeicher im Rechner verwaltet? Nur das Betriebssystem hat direkten Zugriff auf den gesamten physischen Adressraum; den Prozessen steht ein eigener Adressraum zur Verfügung, der über logische Adressen angesprochen wird (Stichworte: Basisregister, Grenzregister). Bei konkurrierendem Zugriff auf den Hauptspeicher durch mehrere Prozesse können bereite oder blockierte Prozesse in den Externspeicher ausgelagert werden (swapping); beim erneuten Einlagern kann der Prozess bei gleichem logischen einen anderen physischen Adressraum zugeteilt bekommen. Beim paging wird der Hauptspeicher in gleich große Bereiche (Seiten, pages) aufgeteilt, jeder Prozess erhält die benötigte Anzahl von (nicht notwendigerweise im Speicher zusammenhängenden) Seiten, und die Umsetzung von logischen in physische Adressen erfolgt über die Seitentabelle. [1801.KE2 S. 47ff.] Was sind Dateien und wie werden sie realisiert? Eine Datei ist eine Folge von Datensätzen, die zusammengehörige Information enthalten. Für den Benutzer wird die Datei durch ihren Zugriffspfad und ihren Namen (filename) identifiziert. [1801.KE2 S. 66] Nennen Sie typische Anwendungen für Threads! Typische Anwendungen für Threads sind: • Parallelisierung von Programmen auf Mehrprozessorrechnern; verschiedene Threads können jeweils einem eigenen Prozessor zugewiesen werden. • Gerätetreiber für langsame Geräte; der Prozessor im Controller kann schon die nächste Anfrage bearbeiten, falls die vorherige Anfrage noch im Zustand blockiert ist. • Verteilte (Client-Server-)Systeme. Ein Server bietet seine Dienste verschiedenen Clients an und nutzt dabei für jeden Client einen Thread. [1801.KE2 S. 80] Was ist zu beachten, wenn mehrere Threads schreibend und lesend auf eine gemeinsame Datei zugreifen? Es gilt dasselbe wie bei Synchronisierung von Prozessen, vgl. Frage [154]. [1801.KE2 S. 52f.] Was haben Threads nicht gemeinsam? Jeder Thread hat seine eigenen Registerinhalte, insbesondere seinen eigenen Befehlszähler, und sein eigenes Stacksegment. [1801.KE2 S. 63f.] Was sind Threads im Unterschied zu normalen Prozessen? Mehrere Threads (leichtgewichtige Prozesse = LWPs) teilen sich ein Programm, einen Adressraum (Codesegment, Datensegment) und dieselben Dateien. [1801.KE2 S. 63] 1): Welche Seite lagert man aus wenn ein Prozess mehr Seitenrahmen benötigt als verfügbar? Es gibt verschiedene Strategien. Man kann zum Beispiel diejenige Seite auslagern, deren Benutzung am weitesten zurückliegt (LRU = least recently used). [1801.KE2 S. 51] Was ist denn ein deadlock? Eine Verklemmung beim gemeinsamen Zugriff auf Ressourcen. [1801.KE2 S. 79] 2): Erklären Sie die auf Semaphoren definierten Operationen up und down genauer! down: wenn count > 0, dann dekrementiere count, anderenfalls füge aufrufenden Prozess in W ein und blockiere ihn. up: wenn W nicht leer, dann entferne den nächsten Prozess aus W und mache ihn bereit, anderenfalls inkrementiere count. Ein Prozess ruft down auf, wenn er ein Betriebsmittel benutzen will, und up, sobald er das Betriebsmittel wieder freigibt. [1801.KE2 S. 54] Welche Operationen sind auf einem Semaphor definiert? down und up. [1801. KE2 S. 54] Aus welchen Komponenten besteht ein Semaphor? Aus einer Zählvariablen count (Anzahl freier Betriebsmittel) und einer Prozessmenge W (Warteschlange). W ist leer, falls count>0. [1801.KE2 S. 54] Was ist ein Semaphor? Ein abstrakter Datentyp. [1801.KE2 S. 54] (naja...) Welche Möglichkeiten der Prozesssynchronisierung gibt es? (a) Schalter: schlecht, weil das ständige Abfragen unnötig CPUZeit verbraucht, und weil Prozesse voneinander abhängig werden. (b) Verwendung des von Dijkstra entwickelten Konzepts des Semaphors. (c) Monitore [1801.KE2 S. 53f.] 1): Wie kann man das Problem lösen das entsteht wenn mehrere Prozesse gleichzeitig ablaufen? Durch Prozesssynchronisierung. [1801.KE2 S. 53] Welches Problem gibt es, wenn mehrere Prozesse gleichzeitig ablaufen? Wenn mehrere Prozesse auf dieselbe Ressource teils lesend, teils schreibend zugreifen, liegen so genannte Wettkampfbedingungen (race conditions) vor; welcher Prozess als erster das Ziel erreicht, ist nicht vorhersehbar. Wenn kritische Abschnitte in den Prozessen nicht gegen Unterbrechungen geschützt werden, ist der Inhalt der Ressource (bzw. ihr Zustand) unbestimmt. [1801.KE2 S. 52f.] 3): Wie nennt man das Verfahren, das die Idee nur gerade benötigten Speicher im Hauptspeicher zu halten mit Paging kombiniert? Virtueller Speicher (virtual memory). [1801. KE2 S. 51] Was tut man, wenn ein Prozess mehr Seitenrahmen benötigt als verfügbar sind? Dann muss eine andere Seite in den Sekundärspeicher ausgelagert werden. [1801.KE2 S. 51] Wie wird der logische auf den physischen Speicher abgebildet? Zusammenhängende Adressräume: Der Inhalt des Basisregisters wird zur logischen Adresse addiert. Wird der Inhalt des Grenzregisters überschritten, liegt eine Verletzung des Speicherschutzes vor. Paging: Eine logische Adresse besteht aus einem höherwertigen Teil, der als Index für die Seitentabelle benutzt wird, und einem niederwertigen Teil, der relativen Adresse innerhalb der Seite. Durch Austausch der höherwertigen Bits mit Hilfe der Seitentabelle ergibt sich die physische Adresse. [1801.KE2 S. 47ff.] Wie kommunizieren die Prozesse mit dem Betriebssystem? Über die Programmierschnittstelle (Systemaufrufe). [1801.KE1 S. 23, 33f.] Wie sollten die Zeitscheiben für round robin gewählt werden? (Prozessorzuteilung) Wie effizient das Verfahren arbeitet, hängt von der Dicke der Zeitscheiben ab; extreme Werte sind unzweckmäßig. Bei zu dicken Zeitscheiben werden Ein-/Ausgabe-intensive Prozesse, die frühzeitig blockieren und daher ihre Zeitscheibe nicht ausnutzen, von rechenzeitintensiven Prozessen ausgebremst; bei zu dünnen Zeitscheiben verbringt die CPU einen zu großen Teil ihrer Zeit mit unproduktiven Kontextwechseln. [1801.KE1 S. 30, 45] Welche Zuteilungsstrategien für den Prozessor sind für interaktive Systeme geeignet? Interaktive Systeme, die mit vielen Benutzern gleichzeitig kommunizieren, arbeiten im Time-Sharing-Betrieb; daher kommt das Zeitscheiben-Verfahren in Frage. [1801.KE1 S. 30] Welche Zuteilungsstrategien für den Prozessor gibt es? FCFS (first-come-first-served) verwaltet eine FIFO-Warteschlange und arbeitet sie ab. Das ist leicht zu implementieren, hat aber den Nachteil, dass ein Prozess alle nachfolgenden blockieren kann, wenn er sehr rechenintensiv ist. SJF (shortest job first) bearbeitet die bereiten Prozesse in der Folge aufsteigenden Bedarfs an Rechenzeit. Voraussetzung ist, dass sich der Rechenzeitbedarf aus Erfahrungswerten gut vorhersagen lässt. Wenn das gegeben ist, ist SJF sehr effizient. Im Time-Sharing-Betrieb wird einem bereiten Prozess nur eine Zeitscheibe (time slice) an Rechenzeit zugeteilt und bei Ablauf wieder entzogen, falls vorher keine Unterbrechung eingetreten ist. Die Reihenfolge, in der die Zuteilung erfolgt, kann durch eine ringförmige Warteschlange festgelegt werden (round robin). Der Kontextwechsel wird vom Dispatcher durchgeführt. [1801.KE1 S. 29f.] Wer teilt denn die CPU-Zeit den Prozessen zu? Welcher der bereiten Prozesse als nächster rechnen darf, entscheidet der CPU-Scheduler. [1801.KE1 S. 29] Wie funktionieren parallele Prozesse? Zu jedem beliebigen Zeitpunkt ist höchstens ein Prozess rechnend; die Parallelität oder Gleichzeitigkeit ist also eine Illusion. [1801.KE1 S. 30] 1): Was für ein Problem gäbe es, wenn ein blockierter Prozess direkt in den Zustand "rechnend" übergehen könnte? Die Fairneß bei der Zuteilung der CPU würde nicht beachtet. [implizit in 1801.KE1 S. 29] Wie kann es zu Änderungen der Prozesszustände kommen? Durch Interrupts, z.B. den Anstoß oder den Abschluß einer Ein- /Ausgabeanforderung oder durch Unterbrechung des Schedulers (Entzug der Zeitscheibe). [1801.KE1 S. 28] Welche Zustände kann ein Prozess durchlaufen? Erzeugt - bereit - rechnend - blockiert - beendet. [Immer zeichnen! Man sollte vor allem darauf achten, dass alle Pfeile korrekt eingezeichnet werden.] [1801.KE1 S. 28 Abbildung 1.10] Worin liegt der Unterschied von Programmen und Prozessen? Zum Prozess gehört auch noch der Prozesskontext, bestehend aus den Registerinhalten (insbesondere Befehlszähler und Grenzen des Adreßraums) sowie der Prozessnummer, im Prozesskontrollblock (PCB) zusammengefaßt. Dort ist auch vermerkt, ob der Prozess im System- oder Benutzermodus arbeitet, und in welchem Zustand er sich befindet. [1801.KE1 S. 28] Wie nennt man ein laufendes Programm? Ein Programm, das sich gerade in Ausführung befindet, heißt Prozess. [1801.KE1 S. 28] Was ist ein Prozess? Ein Programm, das sich gerade in Ausführung befindet, heißt Prozess. [1801.KE1 S. 28] Was sind die Aufgaben eines Betriebssystems? Das Betriebssystem bildet eine Schicht zwischen der Rechnerhardware und den Benutzern und ihren Anwendungsprogrammen. Es stellt zwei Schnittstellen zur Verfügung, eine Benutzerschnittstelle und eine Programmierschnittstelle, und kapselt damit die Zugriffe auf die Hardware (Speicherverwaltung, Speicherschutz, Ein- /Ausgabefunktionen). Außerdem koordiniert es die Prozesse (Scheduling, Synchronisation). [1801.KE1 S. 2, 29f.] 1): Wie funktioniert die BS-Kommunikation mit Geräten? Die Geräte sind über Controller und einen Bus mit dem Prozessor verbunden; das Betriebssystem kommuniziert über Gerätetreiber mit den Controllern. Der Gerätetreiber verwendet entweder spezielle Ein-/Ausgabebefehle des Betriebssystems und greift über besondere Adressen auf die Controllerregister (data-out, data-in, status, control) zu, oder diese Register sind als Teil des Hauptspeichers realisiert (memory-mapped I/O). [1801.KE1 S. 16f.]