Informatik: Scheduling-Verfahren
Released by matroid on Mo. 26. April 2004 20:00:44 [Statistics]
Written by student - 7254 x read [Outline] Printable version Printer-friendly version -  Choose language   
Informatik

\(\begingroup\)

Scheduling-Verfahren

Eine der Hauptaufgaben eines Betriebssystems ist die Überwachung und Steuerung von Prozessen. Bei Mehrprozesssystemen bzw. Mehrprogrammsystemen gibt es mehrere Prozesse, deren Ablauf koordiniert werden muss. Das Scheduling ist in solchen Betriebssystemen dafür zuständig den verschiedenen Prozessen Betriebsmittel - insbesondere den Prozessor - zuzuweisen bzw. auch wieder zu entziehen. Es muss sichergestellt sein, dass jeder bereite Prozess irgendwann mal ausgeführt wird, sodass der Eindruck eines zeitlich verzahnten Ablaufs aller Prozesse entsteht. Im Wesentlichen gibt es dazu drei Verfahren, die in modernen Betriebssystemen eingesetzt werden. Diese werden wir jetzt mal genauer unter die Lupe nehmen.


Round Robin

Bei dem "Round Robin" genannten Verfahren erhält jeder Prozess eine Zeitscheibe, das heißt er kann den Prozessor eine gewisse Zeit benutzen. Ist diese Zeit abgelaufen, wird der Prozess wieder ans Ende der Warteschlange der bereiten Prozesse gestellt. Diese Warteschlange heißt Ready-Queue. Danach wird der nächste Prozess aus der Ready-Queue ausgewählt und dieser Prozess laufend gesetzt (d. h. er bekommt den Prozessor zugeteilt). Hat ein Prozess schon vor dem Ablauf der zugeteilten Zeit seine Arbeiten erledigt, so gilt die Zeitscheibe als abgearbeitet; dies bedeutet, dass der nachfolgende Prozess nicht die eingesparte Zeit des vorigen Prozesses erhält. Somit kann man festhalten, dass jeder Prozess seine eigene Zeitscheibe hat und sich diese nicht auf andere Prozesse übertragen lässt. Zu diesem Verfahren habe ich zur Verdeutlichung des Ablaufs ein Bild gezeichnet, welches die parallele Ausführung von drei Prozessen zeigt.

Priority-Based-Scheduling

Dieses Verfahren basiert auf Round Robin. Zusätzlich wird jedem Prozess eine Wichtigkeitsstufe zugeordnet - die Priorität. Bei einem Prozesswechsel wird nun der Prozess aus der Ready-Queue ausgewählt, der die höchste Priorität besitzt. Es wird nun stets der Prozess mit der höchsten Priorität aktiv und verdrängt somit Prozesse niedrigerer Priorität. Verdrängung bedeutet, dass einem Prozess vorzeitig ein Betriebsmittel (hier der Prozessor) entzogen wird, weil ein Prozess höherer Priorität diese benötigt. Den Prozessen ist beim Priority-Based-Scheduling jeweils eine feste Priorität zugeordnet, die sich während der kompletten Lebensdauer des Prozesses nicht ändert. Haben mehrere Prozesse die gleiche Priorität, so wird Round Robin angewendet.

Multilevel-Feedback

Dieses Verfahren basiert wiederum auf dem Priority-Based-Scheduling. Allerdings werden hier die Prozessprioritäten dynamisch zugeordnet: Je mehr Ressourcen (d. h. Betriebsmittel) ein Prozess verbraucht, desto niedriger wird seine Priorität. Dies ist notwendig, damit jeder Prozess an die Reihe kommt.

Um dieses Verfahren zu veranschaulichen, betrachten wir die Berechnungsformel für UNIX-Systeme. Diese setzt sich aus zwei Teilen zusammen:

  1. TCPU = TCPU : 2
  2. Dynamische Priorität = TCPU : Konstante + Basispriorität + nice
Intern zählt die CPU in jedem Takt einen Zähler hoch. Der Zählerstand wird Ticks genannt. Hierüber können Zeitfunktionen implementiert werden. Dies ist beim Scheduling recht nützlich. Damit unsere Variable TCPU nicht irgendwann einen Überlauf verursacht, wird sie vor der Berechnung der Priorität durch 2 geteilt. Zusätzlich wird diese Variable (eingesetzt in Formel b)) noch durch eine vom Betriebssystem abhängige Konstante geteilt. Beim Start des Prozesses bekommt dieser eine Basispriorität zugeteilt, die nie unterschritten wird. Außerdem kann der Benutzer noch einen "nice" genannten Wert festlegen, der allerdings nur positiv sein kann und somit die Prozesspriorität nur negativ beeinflussen kann. Denn je niedriger der errechnete Wert, desto höher ist die Priorität - und umgekehrt.
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Grundstudium Informatik :: Informatik :: Betriebssysteme :
Scheduling-Verfahren [von Student]  
Vorstellung einiger Scheduling-Verfahren:Round Robin, Priority-Based-Scheduling, Multilevel-Feedback
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 7254
 
Aufrufstatistik des Artikels
Insgesamt 369 externe Seitenaufrufe zwischen 2012.01 und 2021.07 [Anzeigen]
DomainAnzahlProz
http://google.de31384.8%84.8 %
https://google.com143.8%3.8 %
https://google.de133.5%3.5 %
https://www.bing.com41.1%1.1 %
http://images.google.de20.5%0.5 %
https://duckduckgo.com20.5%0.5 %
http://www.bing.com113%3 %
http://avira.search.ask.com10.3%0.3 %
http://mixidj.delta-search.com10.3%0.3 %
http://search.genieo.com10.3%0.3 %
http://de.yhs4.search.yahoo.com10.3%0.3 %
http://google.com20.5%0.5 %
http://search.conduit.com10.3%0.3 %
http://search.yahoo.com10.3%0.3 %
https://www.ecosia.org10.3%0.3 %
http://search.snapdo.com10.3%0.3 %

Häufige Aufrufer in früheren Monaten
Insgesamt 329 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2012-2017 (192x)http://google.de/url?sa=t&rct=j&q=
2012-2014 (26x)http://google.de/url?sa=t&rct=j&q=scheduling verfahren
201405-05 (16x)http://google.de/url?sa=t&source=web&cd=9&ved=0CEYQFjAI
2020-2021 (14x)https://google.com/
201501-01 (12x)http://google.de/url?sa=t&source=web&cd=7&ved=0CC0QFjAG
201409-09 (12x)http://google.de/url?sa=t&source=web&cd=6&ved=0CDIQFjAF
201205-05 (12x)http://google.de/url?sa=t&rct=j&q=scheduling mathe
201207-07 (10x)http://google.de/url?sa=t&rct=j&q=round robin priorität rechnung
201305-05 (8x)http://google.de/url?sa=t&rct=j&q=round robin verfahren informatik
202006-08 (8x)https://google.de/
201212-12 (6x)http://google.de/url?sa=t&rct=j&q=schedulingverfahren
202103-07 (5x)https://google.de
2020-2021 (4x)https://www.bing.com/
201306-06 (4x)http://google.de/url?sa=t&rct=j&q=zeitscheiben im round robin

[Top of page]

"Informatik: Scheduling-Verfahren" | 5 Comments
The authors of the comments are responsible for the content.

Re: Scheduling-Verfahren
von: Ueli am: So. 02. Mai 2004 15:57:40
\(\begingroup\)Hallo student,

ich möchte noch den Begriff "preemtive" bzw. "nonpreemtive" beifügen.
Nicht verdrängend (nonpreemtive): Ein Prozess läuft so lange, bis er blockiert. (wartet z.B. auf eine Eingabe).
Verdrängend (preemtive): Bsp.: Das Zeitquantum des Prozesses ist erschöpft (Systemuhr-Interrupt); er muss abgeben. (Round Robin) Oder
ein Ein/Ausgabe-Interrupt schiebt einen anderen Prozess vor.

mfg Ueli\(\endgroup\)
 

Re: Scheduling-Verfahren
von: matroid am: Di. 04. Mai 2004 13:12:26
\(\begingroup\)Hi student,

gut gemacht. Ich habe die Informatik ja nie gelernt, nur angewendet. :D
das Multilevel-Feedback bevorzugt demnach die Kurzläufer. Welches Verfahren wird / wurde von welchem Betriebssystem eingesetzt? Welches ist älter / jünger? Gibt es spezielle Eignungen?
Kann ich meinen Computer fragen, wie er das Scheduling organisiert?

Ich würde mich freuen, wenn Du darüber auch Informationen hättest.

Gruß
Matroid\(\endgroup\)
 

Re: Scheduling-Verfahren
von: student am: Di. 25. Mai 2004 12:48:25
\(\begingroup\)Hi Matroid,

soweit mir bekannt, wird das letzte Verfahren heutzutage unter UNIX angewandt. Da die vorgestellten Verfahren chronologisch sortiert sind, wurde gab es zuerst Round Robin, dann Priority Based Scheduling und dann Multilevel Feedback, welches in abgeänderter Form auch unter den verschiedenen Windows'en gefunden werden kann. Round Robin und Priority Based Scheduling wird heute nur noch für das Scheduling von Threads angewendet (dieses sind "Leichtgewichtsprozesse", die den Prozessen untergeordnet sind).
Bei Windows Betriebssystemen kann ich dir leider nicht sagen, ob es überhaupt einen Befehl oder eine Möglichkeit gibt, herauszufinden, wie dein Computer konkret schedult. Bei UNIX - insbesondere bei Linux - steht es meistens dabei, wenn du dir einen neuen Kernel-Release runterlädtst. Viel interessanter ist aber hier die Angabe der Zeitkomplexität (bei den neueren meistens O(1)). Aber ich schweife schon wieder ab...

Ich hoffe ich konnte deine Fragen zu deiner Zufriedenheit beantworten.

MfG

student\(\endgroup\)
 

Re: Scheduling-Verfahren
von: matroid am: Di. 25. Mai 2004 13:30:19
\(\begingroup\)Hi student,

ja, danke. Das hilft mir die Infos einordnen.
Die Threads als Beispiel, das ist auch interessant.


Gruß
Matroid\(\endgroup\)
 

Re: Scheduling-Verfahren
von: Lavant am: So. 25. Dezember 2005 15:03:59
\(\begingroup\)Sehr schöner Artikel! Ich konnte mir das schon vorher vorstellen aber jetzt weiß ich endlich mehr darüber. xD Danke und mach weiter so... mfg Lavant\(\endgroup\)
 

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]