O tym jak w Linuksie działają kolejki, a także usypianie i budzenie procesów.
Przygotował: Adam Kluźniak

Temat główny: `Procesy`
Podtemat: `Kolejki oraz usypianie i budzenie procesów.`

Spis treści:

1.	Kolejki
1.1	Implementacja list dwukierunkowych
1.2	Kolejka procesów gotowych (`runqueue`)
1.3	Kolejki procesów oczekujących (`wait_queue`)
2.	Usypianie i budzenie procesów
2.1	Usypianie procesów (`sleep_on`)
2.2	Budzenie procesów (`wake_up`)

1. Kolejki

1.1 Implementacja list dwukierunkowych

Jądro Linux'a w wersji 2.4 do implementacji m.in. kolejek procesów gotowych oraz kolejek procesów oczekujących używa standardowych dwukierunkowych list. Kod źródłowy dla tych list znajduje się w pliku:

include/linux/list.h .

Czym NIE są listy dwukierunkowe jądra Linux'a:

Nie są to makra, które ułatwiają dodawanie do tworzonych struktur pola next i prev.
Nie są to struktury, które jako elementy listy przechowują wskaźniki do innych struktur.

Jak wobec tego działają listy dwukierunkowe w Linux'ie.

Zdefiniowane są w następujący sposób:

struct list_head {
	struct list_head *next, *prev;
};

Umieszcza się je jako pole struktury, która ma być elementem listy, na przykład tak:
```
struct element_listy {
	int wartosc;
	struct list_head lista;
};
```

A jak zdobyć wskaźnik do elementu listy mając wskaźnik do jego węzła? Do tego służy makro list_entry , zdefiniowane następująco:

#define list_entry(ptr, type, member) \
	((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))

	gdzie:
	ptr    -  to wskaźnik do węzła typu list_head,
	type   -  to typ strukury, która jest elementem listy,
	member -  to nazwa pola typu list_head w strukturze 
	          elementu listy.

Na chłopski rozum działa to tak:
- Obliczamy przesunięcie pola typu list_head od początku struktury elementu listy.
- Odejmujemy to przesunięcie od wskaźnika do węzła listy, który mamy.
- W ten sposób dostajemy wskaźnik na strukturę, która jest elementem listy.
Bardzo przydatnym makrem jest list_for_each(pos, head) , które tworzy pętlę for przechodzącą zmienną pos po całej liście poczynając od head.
```
#define list_for_each(pos, head) \
	for (pos = (head)->next; pos != (head); pos = pos->next)
```
Oprócz opisanych powyżej dostępne są też makra inicjalizujące: LIST_HEAD_INIT, LIST_HEAD, INIT_LIST_HEAD.
Oczywiście potrzebne są też operacje dodawania i usuwania elementów z listy. Do tego służą m.in. funkcje:
- list_add
- list_add_tail
- list_del
Przydatna jest też funkcja list_empty, która mówi, czy lista jest pusta, czy nie.

1.2 Kolejka procesów gotowych (`runqueue`)

Co warto wiedzieć o kolejce procesów gotowych:

Jest tylko jedna taka kolejka w jądrze Linux'a!
Kolejka procesów gotowych jest implementowana przez pole run_list w strukturze task_struct (plik include/linux/sched.h).
Zmienna przechowująca początek kolejki procesów gotowych (runqueue_head) jest zadeklarowana w pliku kernel/sched.c.
Implementacje funkcji operujących na tej kolejce również znajdują się w tym pliku, a także w pliku include/linux/sched.h.
Kolejka procesów gotowych jest zaimplementowana na standardowej liście dwukierunkowej.

Funkcje operujące na kolejce procesów gotowych to:

add_to_runqueue(struct task_struct * p): Dodaje do kolejki runqueue proces ze strukturą task_struct wskazywaną przez p.
move_last_runqueue(struct task_struct * p): Powoduje przesunięcie procesu na koniec kolejki.
move_first_runqueue(struct task_struct * p): Powoduje przesunięcie procesu na początek kolejki.
del_from_runqueue(struct task_struct * p): Usuwa proces z koleji runqueue .
task_on_runqueue(struct task_struct *p): Podaje czy process jest w kolejce runqueue.

Dwie ostatnie funkcje są zaimplementowane w pliku include/linux/sched.h. Implementacje powyższych funkcji są bardzo proste. Przykład:

static inline void add_to_runqueue(struct task_struct * p)
{
	list_add(&p->run_list, &runqueue_head);
	nr_running++;
}

Funkcje te w prosty sposób korzystają z implementacji standardowych list dwukierunkowych. W tym przypadku aktualizowana jest jeszcze zmienna przechowująca ilość działających procesów (deklarowana w pliku kernel/fork.c).

1.3 Kolejki procesów oczekujących (`wait_queue`)

Co warto wiedzieć o kolejkach procesów oczekujących.

Kolejki procesów oczekujących używane są w przypadku, gdy proces żąda od jądra wykonania czegoś co nie może być w danej chwili wykonane, ale może być wykonane później. Proces jest wtedy usypiany, a budzony jest w przypadku, gdy zaistnieje większa szansa na wykonanie rządania.
Dobrym przykładem są semafory. Proces, który wiesza się na semaforze jest odkładany na kolejkę procesów oczekujących związaną z tym semaforem.
Jak można się było domyśleć kolejki procesów oczekujących są zaimplementowane poprzez standardowe listy dwukierunkowe.
Większość funkcji i makr operujących na kolejkach procesów oczekujących jest zdefiniowana w pliku include/linux/wait.h.

Listy procesów oczekujących są zaimplementowane poprzez dwa typy:

wait_queue_t: Jest to typ opisujący węzły kolejki. Zawiera pola przechowujące task_struct procesu, dodatkowe flagi oraz pole typu list_head tworzące listę.
wait_queue_head_t: Ten typ jest początkiem kolejki. Przechowuje dodatkowo blokadę (lock) umożliwiającą zachowanie wyłącznego dostępu do kolejki.

Funkcje operujące na tych typach:

__add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
__add_wait_queue_tail(wait_queue_head_t *head, wait_queue_t *new)
__remove_wait_queue(wait_queue_head_t *head, wait_queue_t *old)

z pliku wait.h w trywialny sposób korzystają z analogicznych operacji dla standardowych list dwukierunkowych.
Ciekawsze są funkcje dotyczące kolejek procesów oczekujących z pliku kernel/fork.c:

add_wait_queue(wait_queue_head_t *q, wait_queue_t * wait)
add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t * wait)
remove_wait_queue(wait_queue_head_t *q, wait_queue_t * wait)

Funkcje te działają podobnie do siebie. Warto zerknąć choć na jedną z nich:

void add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t * wait)
{
	unsigned long flags;

	wq_write_lock_irqsave(&q->lock, flags);
	wait->flags |= WQ_FLAG_EXCLUSIVE;
	__add_wait_queue_tail(q, wait);
	wq_write_unlock_irqrestore(&q->lock, flags);
}

Funkcja najpierw zamyka blokadę do zapisu, aby zachować wyłączny dostęp. W tym przypadku ustawiana jest flaga WQ_FLAG_EXCLUSIVE, która powoduje, że proces będzie budzony samodzielnie, a nie wszystkie z kolejki. Następnie proces opisany przez zmienną wait jest wstawiany do kolejki. Teraz już można z powrotem otworzyć blokadę.

Uwaga: Węzeł dodawany do kolejki procesów oczekujących powinien być utworzony wcześniej np. przy wykorzystaniu makra DECLARE_WAITQUEUE(name, tsk) lub deklarując zmienną samemu i korzystając z funkcji init_waitqueue_entry .

2. Usypianie i budzenie procesów

Operacje usypiania (sleep_on) oraz budzenia (wake_up) korzystają z kolejek procesów oczkujących oraz kolejki procesów gotowych. Kolejki procesów oczekujących podajemy zwykle jako parametr dla któreś z tych funkcji.

2.1 Usypianie procesów (`sleep_on`)

Funkcje służące do usypiania procesu działają na aktualnie wykonywanym procesie. Innymi słowy proces usypia sam siebie.

W pliku kernel/sched.c zaimplementowane są cztery funkcje usypiające procesy. Są to:

interruptible_sleep_on(wait_queue_head_t *q)
interruptible_sleep_on_timeout(wait_queue_head_t *q, long timeout)
sleep_on(wait_queue_head_t *q)
sleep_on_timeout(wait_queue_head_t *q, long timeout)

Pierwsze dwie funkcje przenoszą process w stan TASK_INTERRUPTIBLE, a dwie następne w stan TASK_UNINTERRUPTIBLE (patrz: referat opisujący działanie planisty). Dodatkowo funkcje z końcówką _timeout w nazwie pozwalają wywołującemu zdefiniować okres czasu, po którym proces zostanie obudzony przez jądro.

Zasady działania tych funkcji są podobne. Zerknijmy na sleep_on:

void sleep_on(wait_queue_head_t *q)
{
	unsigned long flags;
	wait_queue_t wait;
	init_waitqueue_entry(&wait, current);
	
	current->state = TASK_UNINTERRUPTIBLE;

	wq_write_lock_irqsave(&q->lock,flags);
	__add_wait_queue(q, &wait);
	wq_write_unlock(&q->lock);

	schedule();

	wq_write_lock_irq(&q->lock);
	__remove_wait_queue(q, &wait);
	wq_write_unlock_irqrestore(&q->lock,flags);
}

Co robi ta funkcja? Ano to:

Najpierw tworzona jest struktura, która będzie węzłem w kolejce procesów oczekujących.
Następnie stan procesu ustawiany jest na TASK_UNINTERRUPTIBLE.
Dalej, po zamknięciu blokady proces jest wstawiany do podanej kolejki procesów oczekujących.
Teraz wywołujemy planistę (schedule()), który usuwa proces z kolejki procesów gotowych oraz przydziela procesor następnemu procesowi.
Ostatnia część funkcji (za wywołaniem planisty) uruchamiana jest dopiero po obudzeniu procesu. Wtedy to proces usuwa siebie z kolejki, do której wcześniej się wstawił.

Uwagi:
Funkcje z końcówką _timeout w nazwie wywołują schedule_timeout zamiast schedule.
Funkcje interruptible ustawiają stan na TASK_INTERRUPTIBLE.

Do usypiania można wykorzystać jeszcze rodzinę makr wait_event(wq, condition) z pliku include/linux/sched.h. Makra te, po każdym wzbudzeniu procesu, sprawdzają czy zachodzi odpowiedni warunek (condition) i jeśli nie to proces zostaje uśpiony ponownie.

2.2 Budzenie procesów (`wake_up`)

Operacja budzenia procesu wstawia proces do kolejki procesów gotowych. Kiedy taki proces otrzyma przydział czasu procesora, sam siebie usuwa z kolejki procesów oczekujących.

Podstawowymi funkacjmi powodującymi obudzenie procesu są:

try_to_wake_up
__wake_up_common

Pierwsza z nich budzi pojedynczy proces, a druga może obudzić więcej procesów. Funkcja __wake_up_common wykorzystuje do budzenia procesów funkcję try_to wake_up.

Funkcja try_to_wake_up najpierw dodaje budzony proces do kolejki procesów gotowych. Następnie jeśli proces ma być budzony asynchronicznie (lub aktualnie rozpatrywany procesor nie jest tym, na którym proces może działać) uruchamiana jest funkcja reschedule_idle (patrz: referat opisujący działanie planisty).

Oto nagłówek funkcji __wake_up_common:

static inline void __wake_up_common (wait_queue_head_t *q, unsigned int mode,
			 	     int nr_exclusive, const int sync)

Jak łatwo się domyślić q jest kolejką, z której to budzimy procesy.
Następny parametr, mode, umożliwia budzenie procesów, które są w podanym stanie (np. TASK_INTERRUPTIBLE).
Parametr nr_exclusive służy określeniu ilości procesów z flagą WQ_FLAG_EXCLUSIVE, które zostaną obudzone. Jeśli nr_exclusive=0 to budzone są procesy bez tej flagi oraz jeden z ustawioną tą flagą.
Ostatni parametr określa sposób budzenia (synchroniczny / asynchroniczny).

Pozostałe funkcje budzące procesy to:

wake_up_process: Budzi asynchronicznie jeden proces.
__wake_up: Budzi procesy z kolejki asynchronicznie. Korzysta bezpośrednio z __wake_up_common, dodatkowo zamyka blokadę związaną z kolejką.
__wake_up_sync: Działa jak __wake_up tylko, że synchronicznie.

Jest również cała masa makr w pliku include/linux/sched.h, kórych definicja mówi sama za siebie:

#define wake_up(x)           
             __wake_up((x),TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1)
#define wake_up_nr(x, nr)         
             __wake_up((x),TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, nr)
#define wake_up_all(x)     
             __wake_up((x),TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 0)
#define wake_up_sync(x)
             __wake_up_sync((x),TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1)
#define wake_up_sync_nr(x, nr)
             __wake_up_sync((x),TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, nr)
#define wake_up_interruptible(x)          
             __wake_up((x),TASK_INTERRUPTIBLE, 1)
#define wake_up_interruptible_nr(x, nr)   
             __wake_up((x),TASK_INTERRUPTIBLE, nr)
#define wake_up_interruptible_all(x)
             __wake_up((x),TASK_INTERRUPTIBLE, 0)
#define wake_up_interruptible_sync(x)     
             __wake_up_sync((x),TASK_INTERRUPTIBLE, 1)
#define wake_up_interruptible_sync_nr(x)  
             __wake_up_sync((x),TASK_INTERRUPTIBLE,  nr)

O tym jak w Linuksie działają kolejki, a także usypianie i budzenie procesów. Przygotował: Adam Kluźniak

Temat główny: Procesy Podtemat: Kolejki oraz usypianie i budzenie procesów.

1. Kolejki

1.1 Implementacja list dwukierunkowych

1.2 Kolejka procesów gotowych (runqueue)

1.3 Kolejki procesów oczekujących (wait_queue)