Einleitung Inhalt Queues


Prozesse

Anzahl der Prozesse in einem Linuxsystem

Seit dem Kernel 2.4 wird die Anzahl der Prozesse in einem Linuxsystem dynamisch berechnet. Noch in Kernel 2.2 gab es eine Obergrenze von 4090 Tasks, die nicht überschritten werden konnte. Nun hängt das Maximum der Prozesse im System vom verfügbaren Speicher ab. Wieviele Prozesse man gleichzeitig im System haben kann, kann man sich ansehen, wenn man den Befehl cat /proc/sys/kernel/threads-max eingibt. Die Anzahl der Prozesse läßt sich über diesen Mechanismus auch zur Laufzeit ändern.

Process Descriptor

Jeder Prozess hat einen eigenen Process Descriptor, in dem steht in welchem Zustand sich der Prozess befindet, was er gerade macht, welche Dateien er offen hat... usw. Dieser Process Descriptor ist in der Datei sched.h definiert und nennt sich task_struct.

struct task_struct {
	/*
	 * offsets of these are hardcoded elsewhere - touch with care
	 */
	volatile long state;	/* -1 unrunnable, 0 runnable, >0 stopped */
	unsigned long flags;	/* per process flags, defined below */
	int sigpending;
	mm_segment_t addr_limit;	/* thread address space:
					 	0-0xBFFFFFFF for user-thead
						0-0xFFFFFFFF for kernel-thread
					 */
	struct exec_domain *exec_domain;
	volatile long need_resched;
	unsigned long ptrace;

	int lock_depth;		/* Lock depth */

/*
 * offset 32 begins here on 32-bit platforms. We keep
 * all fields in a single cacheline that are needed for
 * the goodness() loop in schedule().
 */
	long counter;
	long nice;
	unsigned long policy;
	struct mm_struct *mm;
	int has_cpu, processor;
	unsigned long cpus_allowed;
	/*
	 * (only the 'next' pointer fits into the cacheline, but
	 * that's just fine.)
	 */
	struct list_head run_list;
	unsigned long sleep_time;

	struct task_struct *next_task, *prev_task;
	struct mm_struct *active_mm;

/* task state */
	struct linux_binfmt *binfmt;
	int exit_code, exit_signal;
	int pdeath_signal;  /*  The signal sent when the parent dies  */
	/* ??? */
	unsigned long personality;
	int did_exec:1;
	pid_t pid;
	pid_t pgrp;
	pid_t tty_old_pgrp;
	pid_t session;
	pid_t tgid;
	/* boolean value for session group leader */
	int leader;
	/* 
	 * pointers to (original) parent process, 
	 * youngest child, younger sibling,
	 * older sibling, respectively.  (p->father can be replaced with 
	 * p->p_pptr->pid)
	 */
	struct task_struct *p_opptr, *p_pptr, *p_cptr, *p_ysptr, *p_osptr;
	struct list_head thread_group;

	/* PID hash table linkage. */
	struct task_struct *pidhash_next;
	struct task_struct **pidhash_pprev;

	wait_queue_head_t wait_chldexit;	/* for wait4() */
	struct completion *vfork_done;		/* for vfork() */
	unsigned long rt_priority;
	unsigned long it_real_value, it_prof_value, it_virt_value;
	unsigned long it_real_incr, it_prof_incr, it_virt_incr;
	struct timer_list real_timer;
	struct tms times;<
	unsigned long start_time;
	long per_cpu_utime[NR_CPUS], per_cpu_stime[NR_CPUS];
/* mm fault and swap info: this can 
   arguably be seen as either mm-specific or thread-specific */
	unsigned long min_flt, maj_flt, nswap, cmin_flt, cmaj_flt, cnswap;
	int swappable:1;
/* process credentials */
	uid_t uid,euid,suid,fsuid;
	gid_t gid,egid,sgid,fsgid;
	int ngroups;
	gid_t	groups[NGROUPS];
	kernel_cap_t   cap_effective, cap_inheritable, cap_permitted;
	int keep_capabilities:1;
	struct user_struct *user;
/* limits */
	struct rlimit rlim[RLIM_NLIMITS];
	unsigned short used_math;
	char comm[16];
/* file system info */
	int link_count;
	struct tty_struct *tty; /* NULL if no tty */
	unsigned int locks; /* How many file locks are being held */
/* ipc stuff */
	struct sem_undo *semundo;
	struct sem_queue *semsleeping;
/* CPU-specific state of this task */
	struct thread_struct thread;
/* filesystem information */
	struct fs_struct *fs;
/* open file information */
	struct files_struct *files;
/* signal handlers */
	spinlock_t sigmask_lock;	/* Protects signal and blocked */
	struct signal_struct *sig;

	sigset_t blocked;
	struct sigpending pending;

	unsigned long sas_ss_sp;
	size_t sas_ss_size;
	int (*notifier)(void *priv);
	void *notifier_data;
	sigset_t *notifier_mask;
	
/* Thread group tracking */
   	u32 parent_exec_id;
   	u32 self_exec_id;
/* Protection of (de-)allocation: mm, files, fs, tty */
	spinlock_t alloc_lock;
};


Beispiel: task_struct
Im obigen Beispiel ist der task_struct abgebildet, die Stellen, mit denen wir uns jetzt weiterhin beschäftigen wollen sind hervorgehoben.
Als erstes kommt das Feld state. Dieses zeigt an, in welchem Zustand sich der Prozess gerade befindeet. Diese Zustände sind ebenfalls in sched.h definiert:
#define TASK_RUNNING		0
#define TASK_INTERRUPTIBLE	1
#define TASK_UNINTERRUPTIBLE	2
#define TASK_ZOMBIE		4
#define TASK_STOPPED		8
Zustände der Prozesse
TASK_RUNNING
Zeigt an, daß der Prozess entweder gerade ausgeführt wird oder aber direkt auf seine Ausführung wartet, d.h. daß er am Wettbewerb um die CPU teilnimmt.
TASK_INTERRUPTABLE
Der Prozess wurde suspendiert und wartet nun auf ein externes Ereignis, z.B. einen Interrupt, daß ein I/O Vorgang beendet wurde oder er wartet auf eine Systemresource, die erst noch verfügbar wird. Tritt das erwartete Ereignis ein, begibt sich der Prozess in den TASK_RUNNING Zustand und nimmt wieder am Wettbewerb um die CPU teil.
TASK_UNINTERRUPTABLE
Hier passiert das gleiche wie bei TASK_INTERRUPTABLE, mit der Ausnahme, das der Prozess sich nicht um externe Ereignisse kümmert und seinen Status trotz eintretendem Ereignis beibehält. Dieser Status wird selten genutzt. Ein Beispiel hierzu wäre, wenn ein Gerätetreiber eine Hardware auf überprüft, hierbei wäre es nicht sinnvoll, wenn jedesmal, wenn die Hardware reagiert der Prozess in einen anderen Zustand wechselt.
TASK_STOPPED
Dieser Zustand sagt aus, daß der Prozess angehalten wurde. Dies kann z.B. beim Debuggen passieren, wenn man ein Programm an einer bestimmten Stelle anhält und seinen Zustand überprüft.
TASK_ZOMBIE
Falls ein Programm beendet wird muß der Elternprozess noch sein Enverständnis geben. Dies ist notwendig, da es vorkommen kann, daß der Elternprozess noch Resourcen von seinem Kind braucht. Somit werden diese erst dann freigegeben, wenn der Elternprozess ein wait Systemaufruf aufruft. Wenn ein Programm also beendet ist, der Elternprozess es aber noch nicht freigegeben hat befindet es sich in diesem Zombie Zustand.
Das Feld p->mm zeigt auf einen Struct, in dem die Informationen zu dem Speicher enthalten sind, der dem Prozess zugeteilt wurde. Bei Prozessen im Kernelmode ist dieses Feld auf NULL gesetzt.
p->fs enthält Informationen über das Filesystem auf dem der Prozess arbeitet.

Auffinden von Prozessen

Die Prozesse sind untereinander durch eine doppeltverlinkte Ringliste miteinander verbunden. Die Zeiger hierfür sind prev_task, für den Vorgängerprozess und next_task für den nachfolgenden Prozess. Bei dem letzten Prozess zeigt next_task wieder auf den Ersten. Der erste Prozess ist der init_task, bei ihm zeigt der prev_task Pointer wieder auf den letzten Prozess.
Will man einen neuen Prozess einfügen benutzt man das SET_LINKS Makro aus sched.h.
#define SET_LINKS(p) do { \
	(p)->next_task = &init_task; \
	(p)->prev_task = init_task.prev_task; \
	init_task.prev_task->next_task = (p); \
	init_task.prev_task = (p); \
	(p)->p_ysptr = NULL; \
	if (((p)->p_osptr = (p)->p_pptr->p_cptr) != NULL) \
		(p)->p_osptr->p_ysptr = p; \
	(p)->p_pptr->p_cptr = p; \
	} while (0)
SET_LINKS Makro
Hierbei wird zunächst der neue Prozess p an das Ende der Liste gepackt und mit dem letzten und ersten Prozess verlinkt. Anschließend werden die Zeiger vom ersten und letzten Prozess auf den Neuen gesetzt. Zu guter Letzt kümmert sich das Makro noch um die Eltern Kind Beziehungen, um die wir uns später noch kümmern.

Zum Löschen eines Prozesses aus der Liste wird das REMOVE_LINKS Makro verwendet:
#define REMOVE_LINKS(p) do { \
	(p)->next_task->prev_task = (p)->prev_task; \
	(p)->prev_task->next_task = (p)->next_task; \
	if ((p)->p_osptr) \
		(p)->p_osptr->p_ysptr = (p)->p_ysptr; \
	if ((p)->p_ysptr) \
		(p)->p_ysptr->p_osptr = (p)->p_osptr; \
	else \
		(p)->p_pptr->p_cptr = (p)->p_osptr; \
	} while (0)
REMOVE_LINKS Makro
Hierbei werden nun Nachfolger und Vorgänger des zu entfernenden Elements miteinander verbunden. Wie auch bei SET_LINKS wird sich auch hier noch um die Eltern Kind Beziehungen gekümmert.

Ein weiteres recht nützliches Makro ist for_each_task(p). Es ermöglicht alle Prozesse durchzugehen, um eine bestimmte Aktion auszuführen. Es ist folgendermaßen definiert:
#define for_each_task(p) \
	for (p = &init_task ; (p = p->next_task) != &init_task ; )
for_each_task Makro
Der init_task wird hier wiederum als Listenanfang verwendet. Nun wird durch alle Process Descriptors gegangen bis man wieder bei init_task angelangt ist.

Um eine Prozess zu identifizieren hat er eine eindeutige Nummer, die Prozess ID oder PID. Dies ist notwendig, da einige Befehle diese PID direkt als Parameter mitzubekommen um einen Prozess zu identifizieren. Ein recht bekannter Vertreter dieser Art ist das kill Kommando.
Nun wäre der erste naive Ansatz um einen Prozess zu finden mit dem for_each_task(p) Makro durch die Prozesse zu gehen, bis man das Makro mit der gesuchten PID gefunden hat. Dies wäre allerdings eine recht teure Operation, also gibt es unter Linux eine weitere Möglichkeit um an einen bestimmten Prozess heranzukommen: nämlich über eine Hashtable, mit dem Namen pidhash[]. Nun ist das Problem bei Hashfunktionen, daß nicht gesichert ist, daß es eine eins-zu-eins Beziehung zwischen den pids und dem Index in der Hashtable gibt. Um dieses Problem zu lösen hängt hinter jedem Tabelleneintrag in der Hashtable eine doppelt verkettete Liste mit den einzelnen Process Descriptors.
Die Hashfunktion ist folgendermaßen definiert:
#define pid_hashfn(x)	((((x) >> 8) ^ (x)) & (PIDHASH_SZ - 1))
Hashfunktion
Um nun an einen Prozess mit einer bestimmten PID heranzukommen wird folgende Funktion aufgerufen:
static inline struct task_struct *find_task_by_pid(int pid)
{
	struct task_struct *p, **htable = &pidhash[pid_hashfn(pid)];

	for(p = *htable; p && p->pid != pid; p = p->pidhash_next)
		;

	return p;
}
find_task_by_pid()
Als Parameter wird hier die PID übergeben. In der Funktion wird nun zunächst die Hashfunktion mit der PID aufgerufen. htable zeigt nun auf den ersten Process Desciptor, dessen PID der Hashfunktion entspricht. Anschließend wird die Liste durchlaufen bis man den Prozess mit der entsprechenden PID gefunden hat. Wird kein Prozess gefunden, so ist der Rückgabewert NULL.

Eltern-Kind-Beziehungen

Wie eingangs erwähnt hat jeder Prozess einen Elternprozess (diese biologische Anschauungsweise impliziert zwar, daß es mehrere Eltern gibt, dies ist aber mitnichten der Fall: Jeder Prozess hat nur ein Elternteil). Dies hat zur Folge, daß man einen relativ komplizierten Stammbaum hat, da ein Prozess mehrere Kinder und somit ja auch diverse Geschwister haben kann. Diese ganze Struktur wird im task_struct mit folgenden Feldern abgebildet:
p_opptr
Original parent: Zeigt auf den process descriptor des Prozesses, der ihn erzeugt hat oder auf den init process descriptor. Letzteres ist der Fall, wenn der Prozess, der ihn erzeugt hat nicht mehr existiert.
p_pptr
Parent: Der momentane Elternprozess des Prozesses. In den meisten Fällen ist dieser identisch mit p_opptr, es sei denn ein anderer Prozess möchte mit ptrace diesen Prozess monitoren.
p_cptr
Child: Zeigt auf den process descriptor des jüngsten Kindprozesses, also dem vom Prozess zuletzt erstellten Prozess.
p_ysptr
younger sibling: Zeigt auf den jüngeren Geschwisterprozess, also den Prozess, der vom Elternprozess direkt nach ihm erstellt wurde.
p_osptr
older sibling: Zeigt auf den älteren Geschwisterprozess, also auf den Prozess, der gleich nach diesem vom Elternprozess erstellt wurde.

Beispiel:
Kind Eltern Beziehung

Obenstehendes Bild zeigt die Verzeigerung zwischen verschiedenen Prozessen. Die Situation hierbei ist folgende: P0 hat drei Kinder erzeugt, nämlich P1, P2 und P3. Dieser hat wiederum ein Kind, P4.

Einleitung Inhalt Queues