3 Prozessverwaltung

sieht einen Prozess als Objekt der Verwaltung,

mit Operationen zur geeigneten Manipulation

organisiert das Multiplexen der vorhandenen

Prozessoren unter den existierenden Prozessen/Threads

stellt Operationen für Synchronisation/Kommunikation

zur Verfügung

besorgt die primäre Unterbrechungsbehandlung

3.1 Prozessdeskriptor und Prozesstabelle

Prozessdeskriptor (Prozesssteuerblock, process control block, PCB)

ist Verbund (record), der die Verwaltungsdaten

für einen Prozess umfasst, und ist enthalten in der

Prozesstabelle

ist Feld von Prozessdeskriptoren, typischerweise

von fester Länge (= Maximalzahl von Prozessen)

Makro-Zustände eines Prozesses:

aktiv (active, running):

im Besitz eines Prozessors

wartend/blockiert (waiting, blocked):

in einer Synchronisationsoperation blockiert

bereit (ready):

nicht wartend und nicht aktiv

tot (dead, terminated):

blockiert und nicht mehr deblockierbar

Objektorientierte Sicht :

class Process {

// process descriptor attributes:

Processor status; // processor registersint pid; // process idint priority; // process priorityint runtime; // accumulated processor timeboolean blocked; // is process blocked?boolean dead; // is process dead?Process next; // successor in process list

// operations:

public void wake(){...} // unblock & put in ready list

public void block() {...} // block & remove from ready l.

public void setStatus(Processor status) {...} // set processor status

public void incRuntime(int time) {...} // increment runtime

.....

// process management for uniprocessor system: public static Process current(){return current;}static Process current; //currently active proc.static Process previous;//previously active proc.

static Set<Process> readyList = new ReadyList(); // ready-to-run processes

// system startup: establish idle process:

static {current = new Process(); while(true); // idle }

} // end of class Process

Beteiligte Prozesslisten (Typ List<Process>):

Bereitliste (ready list), implementiert als ReadyList,

enthält die bereiten Prozesse

Wartelisten (waiting lists)

sind Synchronisationsobjekten (z.B. Semaphoren)

zugeordnet und enthalten blockierte Prozesse

Zustandsdiagramm für Makro-Zustände eines Prozesses p:(vgl. 1.1.1)

aktiv

bereit wartend

p.block()

p.wake()

q.block()und p wird aktiviert

Achtung!

block/wake sind im Gegensatz zu 1.1.1 betriebssysteminterne Operationen !

tot

neup.wake()

q.wake()

3.2 Prozessumschaltung(dispatching)

deaktiviert einen Prozess und aktiviert einen anderen.

Wann ?

aktiver Prozess wird vom Prozessor verdrängtzugunsten eines bereiten Prozesses

aktiver Prozess blockiert, und somit kann ein bereiter Prozess aktiviert werden

aktiver Prozess wird vom Prozessor verdrängtzugunsten eines aufgeweckten Prozesses mit höherer Priorität

Die Bereitliste und ihre Operationen:

class ReadyList implements Set<Process> {...}

interface Set<T> {// set of T items, initially empty

public void enter(T item) {...} // enter item into set

public T remove() {...} // remove and deliver some set element, // if set not empty, else deliver null}

static void dispatch(int elapsed) { current.incRuntime(elapsed); previous = current; current = readyList.remove(); if(current != previous) switch();

}

mit folgender Prozedur switch, die den notwendigen

Kontextwechsel (context switch) bewirkt:

Prozessumschaltung,

nachdem der aktive Prozess seit seiner Aktivierung

die Zeit elapsed verbraucht hat:

static void switch() { previous.status = SAVESTATUS(); LOADSTATUS(current.status);

}

! Pseudocode –

entspricht dem resume für Koroutinen (NSP Kap. 5),notwendigerweise in Assembler programmiert !

Im einfachsten Fall –

ohne Berücksichtigung von Prozessormodus, Adressabbildung, ... –

ändert sich beim Wechsel des Prozessorstatus nur der Kellerzeiger (stack pointer)

...; load address of current.status into EAX

...; load address of previous.status into EBX

MOV 0(EBX), ESP ; SAVE STACK POINTER

MOV ESP, 0(EAX) ; LOAD STACK POINTER

RET ; return to address

; on top of stack !

Für diesen Fall sieht switch so aus:

3.2.1 Zeitscheibenverfahren

Aktiver Prozess wird vom Prozessor verdrängtzugunsten eines bereiten Prozesses:

typischerweise nach Ablauf einer bestimmten,

dem Prozess zugeteilten Zeit, genannt

Zeitscheibe (time slice) (z.B. 10 ms),

deren Ablauf gemeldet wird durch

Zeitgeberunterbrechung (timer interrupt)

public static void timeSliceEnd() { readyList.enter(current); dispatch(timeSlice); SETTIMER(timeSlice);

}

Zeitgeberunterbrechung bewirkt „unerwarteten Prozeduraufruf“

(unexpected/implicit procedure call) (3.x)

und aktiviert folgende Prozedur in Process:

3.2.2 Blockieren

Wenn aktiver Prozess blockiert,

kann ein bereiter Prozess aktiviert werden:

public void block() { // block & remove from ready list; // only used for/by active process!

blocked = true; dispatch(timeSlice - GETTIMER()); SETTIMER(timeSlice);

}

3.2.3 Aufwecken

Aktiver Prozess wird eventuell vom Prozessor verdrängt

zugunsten eines aufgeweckten Prozesses mit höherer Priorität:

public void wake(){ // unblock & put in ready list

blocked = false; readyList.enter(this); readyList.enter(current); dispatch(timeSlice - GETTIMER()); SETTIMER(timeSlice);

}

3.2.4 Mehrprozessorsysteme

Symmetrische Mehrprozessorsysteme (SMP)

erfordern nur leicht geänderte Verwaltung (3.1)der

aktiven und bereiten Prozesse – bei n Prozessoren so:

public static Process current(){ return current[PROCESSOR_ID()];}

static Process[] current = new Process[n];

// system startup: establish n idle processes:

for(int i=0; i<n; i++)current[i] = new Process();

PROCESSOR_ID liefert die Nummer des ausführenden Prozessors

Achtung: Wenn ein aufgeweckter Prozess einen der naktiven Prozesse verdrängt, wird dieser i.a.in einem anderen Prozessor laufen –

wie wird dann verdrängt?

Hardware stellt dafür inter-processor interrupt zur Verfügung,

der ähnlich wie die Zeitgeberunterbrechung behandelt wird:

public static void interProcInt() { readyList.enter(current()); dispatch(timeSlice - GETTIMER()); SETTIMER(timeSlice);

}

Jedem Prozessor ist ein eigener Zeitgeber zugeordnet.

Auslösung dieser Unterbrechung durch modifiziertes wake :

public void wake(){ blocked = false; readyList.enter(this); readyList.enter(current()); if((p=victim()) != -1) INTERRUPT(p); dispatch(timeSlice - GETTIMER()); SETTIMER(timeSlice);

}

prüft, ob bei einem Prozessorverdrängt werden muß

3.3 Strategien zur Ablaufsteuerung

Klasse Process = Mechanismus

Klasse ReadyList = Strategie

class Process {...static Set<Process> readyList = new ReadyList();...}

Prinzip der Trennung von Strategie (Richtlinie, policy) und

Mechanismus (mechanism)

bedeutet bei der Prozessverwaltung

Strategie der Prozessverwaltung heißt

Strategie der Ablaufsteuerung (scheduling strategy)

oder einfach Ablaufsteuerung (scheduling)

und hat die Aufgabe, knappe Ressourcen - Prozessoren -

in geschickter Weise an die Prozesse zu vergeben

Mögliche Ziele der Ablaufsteuerung (teilweise in Konflikt):

Effiziente Nutzung von Prozessoren und anderen Ress.

Bevorzugung wichtiger Prozesse

Termingerechtheit (bei Echtzeitsystemen)

Fairness

3.3.1 Grundbegriffe

Warteschlangensystem (queueing system)für knappe Betriebsmittel:

Auftrag Ergebnis

Warteschlange Bedienstation(en) (Auftragsstauraum) (Betriebsmittel, Anbieter, server)

z.B. Bereitliste Prozessor(en)

oder Druckerwarteschlange Drucker

Verdrängung

Bedienung

Mathematische Behandlung:

Warteschlangentheorie (Teil der Wahrscheinlichkeitstheorie),

basierend auf Ankunftsraten und Bearbeitungszeiten

Grobe Klassifikation der Bedienung von Warteschlangen:

verdrängende (präemptive, preemptive)Strategien

nichtverdrängende (non-preemptive)

Beachte: bei manchen Ressourcen-Typen sindkeine verdrängenden Strategien möglich;Beispiel: Drucker

Def.: faire Strategie: jeder eintreffende Auftrag wird

nach endlicher Zeit erledigt (Beispiel: FCFS)

(verschiedene Präzisierungen möglich)

Def.: Verweilzeit t eines Auftrags (auch Antwortzeit):

Wartezeit w + Bearbeitungszeit s

! Oft ist s nicht – oder nur näherungsweise – bekannt !

3.3.2 Elementare Strategien

FCFS (FIFO) (first-come, first-served; first in, first out)

Bedienung in der Reihenfolge des Eintreffens

nichtverdrängend+ einfach+ fair– kleine Aufträge werden ungebührlich benachteiligt:

Verzögerung (response ratio)

t/s = (w+s)/s = 1 + w/s

wächst stark für kleine s !

SJF (shortest job first)

Bedienung gemäß ansteigender Bearbeitungszeiten

nichtverdrängend+ einfach+ schnelle Erledigung kleiner Aufträge,

mittlere Verweilzeit wird minimiert– Bearbeitungszeit muß bekannt sein– nicht fair

Variante mit Verdrängung:

SRTF (shortest remaining time first)Bearbeitung wird unterbrochen, wenn neuer Auftrageintrifft, dessen Bearbeitungszeit kleiner als dieaktuelle Restbearbeitungszeit ist

RR (round-robin, „Ringelreihen“, Reihum-Verfahren)

FCFS-Warteschlange, aber bearbeiteter Auftrag

wird grundsätzlich nach Ablauf einer Zeitscheibe

verdrängt und am Ende der Schlange eingereiht

verdrängend+ fair: wenn n Aufträge in Bearbeitung sind, erhält

jeder 1/n der Betriebsmittel-Kapazität(unabhängig vom Zeitpunkt des Eintreffens!)

– Aufwand

PRIO (priority, Priorität)

Bedienung nach Dringlichkeit (zusätzliches Attribut),

typischerweise gemäß abfallenden Rangzahlen

nichtverdrängend+ einfach+ Verallgemeinerung von

FCFS (Rang = Ankunftzeit)SJF (Rang = Bearbeitungszeit)

– nicht fair (bei extern festgelegten Prioritäten)

HRN (highest response ratio next)

lange Wartezeit geht als Bonus ein:

bedient wird der Auftrag mit maximaler Verzögerung

t/s = 1 + w/s

(Aufträge gleich groß FCFS,

Aufträge gleichzeitig SJN )

Guter Kompromiss zwischen FCFS und SJF,

wenn verdrängende Strategie (wie RR) nicht möglich !

SRR (selfish RR)

wie RR, aber neue Aufträge werden nicht sofort

an der Ressource beteiligt:

zum Zeitpunkt a eintreffender Auftrag wird erstzum Zeitpunkt a/r , 0 r 1 , am RR beteiligt (oder wenn kein RR-Beteiligter mehr vorhanden)

kontinuierliches Spektrum von Strategien

mit FCFS für r = 0 , RR für r = 1 .

3.3.3 Gemischte Strategien

MLQ (multi-level queues)

Kombination von PRIO mit anderen Strategien

jeweils für Aufträge gleicher Priorität

Beliebt für die Ablaufsteuerung ist PRIO mit RR:

Bereitliste:

4

3

2

1

Benutzerprozesse

Systemprozesse

Treiber

zeitkritische Treiber