Pliki źródłowe:
Uwaga: niektóre z omawianych tutaj funkcji w kodzie Linuksa są zrealizowane przy użyciu dodatkowych funkcji pomocniczych lub korzystają z bardziej rozbudowanych struktur danych.
Jądro Linuksa do implementacji m.in kolejek procesów gotowych oraz kolejek procesów oczekujących używa standardowych dwukierunkowych list cyklicznych. Definicja struktur danych i funkcji implementujących operacje na listach znajduje się w pliku źródłowym:
include/linux/list.h
Węzeł na liście zawiera wskaźniki do następnego i poprzedniego elementu listy:
struct list_head {
struct list_head *next, *prev;
};Za pustą uznaje się listę składającą się z jednego elementu (atrapy, wskaźnika na listę), dla którego następnik (a także poprzednik) wskazują na niego samego.
Przykład użycia struktury listowej: task_struct (metryczka procesu):
struct task_struct {
struct list_head run_list;
struct list_head tasks;
struct list_head children;
struct list_head sibling;
...
}
Tworzy strukturę typu list_head o podanej nazwie i inicjuje ją, tworząc pustą listę.
#define LIST_HEAD(name) \
struct list_head name = { &(name), &(name) }
Wszystkie podstawowe operacje na listach wykonują się w czasie O(1).
Zaimplementować wybrane funkcje z podanego zestawu:
Dodawanie nowego elementu na początku listy:
static inline void list_add(struct list_head *new, struct list_head *head)
{
new->next = head->next;
new->prev = head;
head->next->prev = new;
head->next = new;
}
Dodawanie nowego elementu na końcu listy:
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
new->next = head;
new->prev = head->prev;
head->prev->next = new;
head->prev = new;
}
Usuwanie elementu z listy, w której jest umieszczony:
Uwaga: Po usunięciu elementu z listy przy pomocy tej funkcji nie staje się on pustą listą, lecz jest w stanie nieokreślonym.
static inline void list_del(struct list_head *entry)
{
entry->next->prev = entry->prev;
entry->prev->next = entry->next;
}
Sprawdzenie, czy lista jest pusta:
static inline int list_empty(struct list_head *head)
{
return head->next == head;
}
Dodanie całej dodatkowej listy na początek starej listy:
static inline void list_splice(struct list_head *list,
struct list_head *head)
{
struct list_head *first = list->next;
if (first != list) {
struct list_head *last = list->prev;
struct list_head *at = head->next;
first->prev = head;
head->next = first;
last->next = at;
at->prev = last;
}
}
Bardzo przydatne jest też makro - iterator po wszystkich elementach listy:
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos = pos->next)
list_entry
Skoro istnieje osobna struktura listy, to czy możemy dostać się do samego
obiektu, który jest przechowywany w liście? Przecież "wędrując" po liście
napotykamy tylko elementy typu list_head, które same w sobie
nic nie znaczą...
Skoro list_head jest polem w jakiejś strukturze, to możemy łatwo wyśledzić, gdzie w pamięci mieści się owa struktura, jeśli tylko mamy o niej jakąś informację. Język C umożliwia takie manipulacje, dlatego też dostępne jest makro:
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
Przekazuje ono obiekt typu type, którego member o podanej nazwie jest typu list_head i zawiera element listy wskazywany przez ptr.
Przykład użycia:
struct list_head *jakas_lista;
proces = list_entry(jakas_lista, struct task_struct, run_list);
Każdy proces w systemie ma dokładnie jednego ojca i moze mieć jedno lub więcej dzieci. Odpowiednie dowiązania są trzymane w metryczce procesu w polach parent i children.
Oto dowiązanie do ojca bieżącego procesu:
struct task_struct *task = current->parent;
A taki kod pozwala na przejrzenie listy dzieci:
struct task_struct *task;
struct list_head *list;
list_for_each(list, ¤t->children) {
task = list_entry(list, struct task_struct, sibling);
/* teraz task wskazuje na kolejne dziecko bieżącego procesu */
}
Praprzodkiem wszystkich procesów jest proces init, o identyfikatorze 1. Taki kod zawsze doprowadzi nas do procesu init:
struct task_struct *task;
for (task = current; task != &init_task; task = task->parent)
;
/* teraz task wskazuje na init */
Oto kilka makr i funkcji do obsługi powiązań rodzinnych procesu.
/**
* list_del_init - deletes entry from list and reinitialize it.
* @entry: the element to delete from the list.
*/
static inline void list_del_init(struct list_head *entry)
{
list_del(entry);
INIT_LIST_HEAD(entry);
}
#define remove_parent(p) list_del_init(&(p)->sibling)
#define add_parent(p) list_add_tail(&(p)->sibling,
&(p)->parent->children)
static inline struct task_struct *eldest_child(struct task_struct *p)
{
if (list_empty(&p->children)) return NULL;
return list_entry(p->children.next,struct task_struct,sibling);
}
static inline struct task_struct *older_sibling(struct task_struct *p)
{
if (p->sibling.prev==&p->parent->children) return NULL;
return list_entry(p->sibling.prev,struct task_struct,sibling);
}
static inline struct task_struct *younger_sibling(struct task_struct *p)
{
if (p->sibling.next==&p->parent->children) return NULL;
return list_entry(p->sibling.next,struct task_struct,sibling);
Wstawienie do tej listy następuje po utworzeniu procesu, a usuwanie - gdy proces już się zakończył i uregulował swoje sprawy z ojcem (przekazał mu swój status zakończenia albo został przez niego zignorowany).
Lista wszystkich procesów jest zaimplementowana tak jak inne listy dwukierunkowe, z użyciem struktury list_head. Operacje na tej liście wykonuje się stosunkowo rzadko - każdy proces powinien być tylko raz wstawiany i raz usuwany.
Początek listy stanowi proces idle. Jest to logiczne, bo proces ten jest tworzony jako pierwszy i nigdy nie jest usuwany. Stanowi więc idealną atrapę.
To jest zwykłe makro, zastępujące pętlę do przeglądania całej listy procesów (wersja uproszczona).
#define next_task(p) list_entry((p)->tasks.next, struct task_struct, tasks)
#define for_each_process(p) \
for (p = &init_task ; (p = next_task(p)) != &init_task ; )
Struktura kolejki procesów gotowych runqueue jest tworzona poprzez pole run_list znajdujące się w strukturze task_struct (zdefiniowanej w pliku źródłowym include/linux/sched.h). Jest ono typu list_head. Na początek kolejki wskazuje zmienna runqueue_head.
static LIST_HEAD(runqueue_head);
Do operowania na kolejce procesów gotowych służą następujące funkcje (plik kernel/sched.c):
Dodawanie procesu do kolejki (ważne: dodawanie zawsze na początek!!):
static inline void add_to_runqueue(struct task_struct *p)
{
list_add(&p->run_list, &runqueue_head);
nr_running++;
}
Usuwanie procesu z kolejki:
static inline void del_from_runqueue(struct task_struct *p)
{
nr_running--;
p->sleep_time = jiffies;
list_del(&p->run_list);
p->run_list.next = NULL;
}
Podczas usuwania pole run_list.next jest ustawiane na NULL. Dzięki temu można później rozpoznać, czy dany proces znajduje się w kolejce procesów gotowych.
Do sprawdzania czy proces jest w kolejce procesów gotowych służy funkcja:
static inline int task_on_runqueue(struct task_struct *p)
{
return (p->run_list.next != NULL);
}
Warto zaznaczyć, że proces (procesy, jeśli mamy do czynienia z systemem wieloprocesorowym) idle ma pole run_list zainicjowane na pustą kolejkę (to znaczy next wskazuje na nią samą). Z tego powodu funkcja task_on_runqueue() przekaże TRUE dla idle, pomimo że nie znajduje się on w kolejce procesów gotowych.
Przesunięcie procesu na początek kolejki:
static inline void move_first_runqueue(struct task_struct *p)
{
list_del(&p->run_list);
list_add(&p->run_list, &runqueue_head);
}
Przesunięcie procesu na koniec kolejki:
static inline void move_last_runqueue(struct task_struct *p)
{
list_del(&p->run_list);
list_add_tail(&p->run_list, &runqueue_head);
}
Wszystkie wymienione operacje korzystają z funkcji zdefiniowanych w list.h, a także odpowiednio zmieniają wartość zmiennej nr_running, na której jest przechowywana liczba procesów w kolejce procesów gotowych. Żadne (oprócz funkcji usuwającej) nie korzystają bezpośrednio ze wskaźników na element następny ani poprzedni.
Zaimplementować wybrane funkcje z podanego zestawu.
Implementacja kolejek procesów oczekujących znajduje się w pliku include/linux/wait.h. Tutaj pokazano nieco uproszczoną wersję.
Element kolejki wait_queue jest postaci:
struct wait_queue_t {
unsigned int flags;
struct task_struct *task;
struct list_head task_list;
}
Jedyną używaną flagą jest WQ_FLAG_EXCLUSIVE. Powoduje ona, że proces będzie budzony samodzielnie, a nie wszystkie procesy z kolejki na raz.
Początek listy jest elementem wyróżnionym o nieco innej strukturze:
struct wait_queue_head_t {
spinlock_t lock;
struct list_head task_list;
}
Początek wait_queue nie jest związany z żadnym procesem, za to posiada pole używane do zapewnienia niepodzielności operacji na kolejce. Kolejki procesów oczekujących są obsługiwane zarówno przez funkcje jądra, jak i przez przerwania, więc operacje na nich (wstawianie i usuwanie) muszą być wykonywane z wyłączonymi przerwaniami.
Do tworzenia nowych kolejek używane są następujące makra:
Tworzy element kolejki o nazwie name związany z podanym procesem i listą ze wskaźnikami zainicjowanymi na NULL.
#define DECLARE_WAITQUEUE(name, tsk) \
wait_queue_t name = { \
task: tsk, \
task_list: { NULL, NULL }}
Tworzy nowy początek kolejki o nazwie name, z podniesioną blokadą i wskaźnikami wskazującymi na ten element, czyli pustą listą.
#define DECLARE_WAIT_QUEUE_HEAD(name) \
wait_queue_head_t name = { \
lock: SPINLOCK_UNLOCKED, \
task_list: { &(name).task_list, &(name).task_list }}
Do wykonywania operacji dodawania i usuwania elementów z kolejki służą następujące funkcje:
Wstawia element na początek kolejki bez ustawiania flagi WQ_FLAG_EXCLUSIVE.
void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
unsigned long flags;
wait->flags &= ~WQ_FLAG_EXCLUSIVE;
spin_lock_irqsave(&q->lock, flags);
list_add(&wait->task_list, &q->task_list);
spin_unlock_irqrestore(&q->lock, flags);
}
Wstawia element na koniec kolejki ustawiając flagę WQ_FLAG_EXCLUSIVE.
void add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *wait)
{
unsigned long flags;
wait->flags |= WQ_FLAG_EXCLUSIVE;
spin_lock_irqsave(&q->lock, flags);
list_add_tail(&wait->task_list, &q->task_list);
spin_unlock_irqrestore(&q->lock, flags);
}
Usuwa element z kolejki.
void remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
unsigned long flags;
spin_lock_irqsave(&q->lock, flags);
list_del(&wait->task_list);
spin_unlock_irqrestore(&q->lock, flags);
}
Funkcje te zapewniają atomowość operacji.
Użycie add_wait_queue() i add_wait_queue_exclusive() gwarantuje specyficzny układ procesów w kolejce:
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 są zaimplementowane cztery funkcje usypiające procesy. Są to:
Pierwsze dwie funkcje przenoszą proces w stan TASK_INTERRUPTIBLE, a dwie następne w stan TASK_UNINTERRUPTIBLE. 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.
Rozwiązanie: kod funkcji z pliku kernel/sched.c:
void sleep_on(wait_queue_head_t *q)
{
unsigned long flags;
wait_queue_t wait;
wait.flags = 0;
wait.task = current;
current->state = TASK_UNINTERRUPTIBLE;
spin_lock_irqsave(&q->lock,flags);
list_add(&wait->task_list, &q->task_list);
spin_unlock(&q->lock);
schedule();
spin_lock_irq(&q->lock);
list_del(&wait->task_list);
spin_unlock_irqrestore(&q->lock,flags);
}
Uwagi:
Funkcje z końcówką _timeout w nazwie wywołują schedule_timeout zamiast schedule.
Funkcje interruptible ustawiają stan na TASK_INTERRUPTIBLE.
Operacja budzenia procesu wstawia proces do kolejki procesów gotowych. Kiedy taki proces otrzyma procesor, sam siebie usuwa z kolejki procesów oczekujących.
Zaimplementować wybrane z opisanych funkcji.
Funkcja try_to_wake_up budzi pojedynczy proces. Najpierw dodaje go 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ć) jest uruchamiana funkcja reschedule_idle.
extern spinlock_t runqueue_lock;
static inline int try_to_wake_up(struct task_struct *p, int synchronous)
{
unsigned long flags;
int success = 0;
spin_lock_irqsave(&runqueue_lock, flags);
p->state = TASK_RUNNING;
if (task_on_runqueue(p))
goto out;
add_to_runqueue(p);
if (!synchronous ||
!(p->cpus_allowed & (1 << smp_processor_id())))
reschedule_idle(p);
success = 1;
out:
spin_unlock_irqrestore(&runqueue_lock, flags);
return success;
}
Funkcja reschedule_idle m.in. sprawdza, czy priorytet budzonego procesu jest wyższy od priorytetu bieżącego procesu i jeśli tak, to ustawia flagę need_resched, która docelowo spowoduje wywołanie wątku szeregującego procesy.
static inline int preemption_goodness(struct task_struct *prev,
struct task_struct *p, int cpu)
{
return goodness(p, cpu, prev->active_mm) -
goodness(prev, cpu, prev->active_mm);
}
static void reschedule_idle(struct task_struct *p)
{
......
tsk = cpu_curr(this_cpu);
if (preemption_goodness(tsk, p, this_cpu) > 0)
tsk->need_resched = 1;
}
Funkcja wake_up_process budzi asynchronicznie jeden process.
inline int wake_up_process(struct task_struct *p)
{
return try_to_wake_up(p, 0);
}
Funkcja __wake_up_common może obudzić więcej procesów. Do budzenia procesów wykorzystuje funkcję try_to wake_up. Parametr mode umożliwia budzenie procesów, które są w podanym stanie (np. TASK_INTERRUPTIBLE). Parametr nr_exclusive służy do wskazania liczby procesów z flagą WQ_FLAG_EXCLUSIVE, które zostaną obudzone. Jeśli nr_exclusive=0, to budzone są wszystkie procesy. Ostatni parametr określa sposób budzenia (synchroniczny/asynchroniczny).
static inline void __wake_up_common (wait_queue_head_t *q, unsigned int mode,
int nr_exclusive, const int sync)
{
struct list_head *tmp;
struct task_struct *p;
list_for_each(tmp,&q->task_list) {
unsigned int state;
wait_queue_t *curr = list_entry(tmp, wait_queue_t, task_list);
p = curr->task;
state = p->state;
if (state & mode) {
if (try_to_wake_up(p, sync) &&
(curr->flags & WQ_FLAG_EXCLUSIVE) &&
!--nr_exclusive)
break;
}
}
}
Funkcja __wake_up budzi procesy z kolejki asynchronicznie.
void __wake_up(wait_queue_head_t *q, unsigned int mode, int nr)
{
if (q) {
unsigned long flags;
spin_lock_irqsave(&q->lock, flags);
__wake_up_common(q, mode, nr, 0);
spin_unlock_irqrestore(&q->lock, flags);
}
}
Funkcja __wake_up_sync działa jak __wake_up, tylko że synchronicznie.
void __wake_up_sync(wait_queue_head_t *q, unsigned int mode, int nr)
{
if (q) {
unsigned long flags;
spin_lock_irqsave(&q->lock, flags);
__wake_up_common(q, mode, nr, 1);
spin_unlock_irqrestore(&q->lock, flags);
}
}
W pliku include/linux/sched.h jest ponadto wiele pomocnicznych makr.
#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)
| Janina Mincer-Daszkiewicz |