1) Hierbei handelt es sich um ein kombinatorisches Problem. Gesucht ist wohl \(\frac{!10}{10!}\), also der Anteil fixpunktfreier Permutationen an allen Permutationen. Dabei ist \(!10\) die Subfakultät. Allgemein gilt:
$$!n=n!\cdot \sum\limits_{k=0}^{n}{\frac{(-1)^k}{k!}}$$
Da in der Aufgabe nicht beschrieben wird, wie die Zuteilung erfolgt, nehmen wir an dieser Stelle an, dass diese zufällig erfolgt (sonst wäre die Aufgabe trivial, wenn man von einem rational denkenden Systementwickler ausgeht). Die zugrunde liegende Menge enthält die Indizes \(1\) bis \(10\) für Deine Prozesse und Zeitslots. Eine fixpunktfreie Permutation für das beschriebene Szenario wäre:
$$\left(\begin{matrix}1&2&3&4&5&6&7&8&9&10\\\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\10&9&8&7&6&5&4&3&2&1\\\end{matrix}\right)$$ Die Pfeile sind an dieser Stelle aus didaktischen Gründen platziert (die mathematisch saubere Notation kommt ohne aus). Zu lesen ist das dann wie folgt: \(P_1\) wird Zeitslot \(T_{10}\) zugeordnet, \(P_2\) zu \(T_9\), \(P_3\) zu \(T_8\) und so weiter. Ein Szenario, in dem das System nach obiger Beschreibung nicht stabil laufen würde, wäre:
$$\left(\begin{matrix}1&2&3&4&5&6&7&8&9&10\\\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow&\downarrow\\10&9&8&6&5&7&4&3&2&1\\\end{matrix}\right)$$ weil Prozess \(P_5\) Zeitslot \(T_5\) zugeordnet wird.
Wir berechnen \(\frac{!10}{10!}\) und erhalten:
$$\dfrac{!10}{10!}\approx 0.37\%$$
Du kannst hier theoretisch auch mit der \(37\%\) Regel bzw. \(\frac{!n}{n!}\approx \frac{1}{e}\) für \(n\geq 4\) arbeiten. Gibt es zu dieser Aufgabenstellung eine Lösung? Ich habe hier relativ viele Annahmen treffen müssen oder hast Du weitere Informationen aus dem Aufgabentext verschluckt?
2) Auch hier fehlen in meinen Augen wichtige Informationen. Was für ein Betriebssystem betrachten wir zum Beispiel? Welche Sprache? Ich vermute mal C. Ich frage deshalb, weil ein Konzept (z.B. der Scheduler) auf unterschiedlichen Betriebssystemen/in unterschiedlichen Sprachen implementierungstechnisch differierende Instanzen haben kann. So ist z.B. beim Wind-Task Scheduling die Prioritätenlogik invers zum POSIX-Standard.
Ich versuche es mal allgemein:
Angenommen, die Anwendung (User-Level) möchte über fread Daten von einem Device lesen. fread ist eine Library-Funktion, die der Systemhersteller bereitstellt. Bei einem Hardwarezugriff muss fread irgendwo die Funktion read aufrufen, was wiederum ein Systemcall ist, der einen Interrupt auslöst. Dadurch wechselt die Bearbeitung in den Kernel-Mode (Kernel-Level). Dort wird anhand des in read übergebenen Filedeskriptors durch die read Funktion des I/O-Subsystems (ebenfalls Kernel-Level) die entsprechend auszuführende Driver-Funktion ermittelt und aufgerufen. Hier passiert dann der eigentliche Hardware-Zugriff (Hardware-Level), der den Prozess, welcher fread aufgerufen hat, in den State „Waiting“ versetzt. Die Hardware arbeitet den Job ab und löst nach Beendigung einen Interrupt aus. Die entsprechende Interrupt-Service-Routine vom System startet die Interrupt-Service-Routine vom Device. Während die Interrupt-Service-Routinen vom System und dem Device aktiv sind, sind alle anderen Interrupts gesperrt. Die Routine vom Device startet einen Interrupt-Service-Thread. Der Interrupt-Service-Thread versetzt wiederum die Anwendung in den Zustand „ready“. Die read-Funktion des Devices liest die Daten vom Gerät (Hardware) und kopiert sie in den von der Anwendung übergebenen Speicherbereich (User-Level). Das Ergebnis des Hardwarezugriffs wird nun schrittweise „nach oben“ durchgereicht. Zuerst an read im I/O-Subsystem. Danach ist der Systemcall abgearbeitet (je nach Scheduling-Verfahren) wird der aufrufende Prozess nun aufgrund eines Priority-Boosts an die CPU gelassen. Das Ergebnis wird dann bis fread weitergereicht (User-Level).
Ich kann nur mutmaßen, dass das gemeint ist. Ist das die Original-Aufgabe?
