Это первая моя статья. Не очень грамотная. Не оконченная. Нигде не опубликованная. В ней я хотел сравнить организацию многозадачности двух широко распространенных систем: Linux (2.4) b Windows (2000). Тема, как оказалось, очень обширна и мало кому интересна, а опыта, как оказалось, маловато… Возможно, что кто-то, сможет подчеркнуть для себя информацию о многозадачности в Linux 2.4. А возможно кто-то захочет присоединится и мы вместе закончим этот материал, но уже на новых ядрах и новых Windows
Данная работа представляет собой попытку сравнить модель многозадачности двух наиболее распространенных типов ОС: Windows и UNIX.
Оба класса операционных систем достаточно разнообразны (по назначению, объему, скорости, API…). В этой работе сравниваются семейства (далее просто ОС) Windows NT/2000 и Linux 2.4.
Необходимо дать некоторые комментарии. ОС Linux рассматривается начиная с ядра 2.4, многие (но далеко не все) основные моменты указанные в работе можно отнести и к наиболее ранним версиям. Кроме того, будут даны некоторые комментарии относительно UNIX system V (далее SYSV).
Сравнение идет исключительно с позиции Application Program Interface (API) ОС. Сравниваются возможности по созданию, управлению и уничтожению потоков. Так же сравнивается организация задач на уровне ядра системы (в смысле программной реализации и процесса создания приложений).
Работу не следует рассматривать как пособие по архитектуре ОС. Затрагиваются лишь аспекты программной реализации многозадачности (как со стороны ядра, так и со стороны прикладных программ). Даны краткие сведения об архитектуре.
Документ можно использовать в качестве пособия для создания многозадачных приложений и переноса программ с одной платформы на другую.
Обе ОС являются многозадачными многопользовательскими ОС. В обеих реализован механизм вытесняющей многозадачности. Это значит, что каждая задача (task) может находится в одном из трех состояний: готовность, блокировка, выполнение. Время выделяемое задаче со стороны ОС для каждой единицы выполнения в обеих ОС носит название кванта времени. Управление задачами происходит с учетом приоритетов. В обеих ОС выделяют несколько классов приоритетов.
Пожалуй, самое сложное – это дать определение задачи. Можно попробовать формально. Задача – единица работы, для выполнения которой предоставляется центральный процессор [1]. К этому можно добавить еще и такое. Задача – единица управления и единица потребления ресурсов [2]. В рамках данной работы под задачей будут пониматься объединение именно этих двух формальных определений. В Windows под это определение более подходит понятие потока (thread), а в UNIX процесса (process). Что касается Linux, то здесь все еще более запутанней. Под задачей следует понимать именно задачу. А вот однозначно определить процесс и поток не получится, так как в этих ОС эти понятия несколько различаются между собой.
Ядром ОС UNIX является ядро (kernel) – относительно небольшой участок кода работающий в привилегированном режиме. Именно ядро осуществляет управление и планирование задач.
Исторически, для UNIX подобных ОС процесс был представлен его паспортом. Который разделяется на две части: первая была представлена структурой proc (дескриптор процесса) и являлась резидентной частью паспорта процесса в таблице процессов в ядре; вторая – структура user (контекст процесса) являлась одним из сегментов программы, однако доступ к этому сегменту имело только ядро.
Такое деление имело свой смысл. В дескрипторе процесса была представлена меньшая часть информации о процессе, но необходимая ядру вне зависимости от состояния процесса: состояние процесса, расположение образа процесса в оперативной памяти и/или на диске, информация о приоритете, идентификатор пользователя, создавшего процесс, информация о родственных процессах, о событиях, осуществления которых ожидает данный процесс… Контекст процесса представлял собой более объемную часть: содержимое регистров процессора, коды ошибок выполняемых процессором системных вызовов, информацию о всех открытых данным процессом файлов и незавершенных операциях ввода-вывода (указатели на структуры file)… Контекст процесса используется ядром (структура user находится в адресном пространстве ядра) только когда процесс активен. Как только процесс становился неактивным эта информация удалялась из адресного пространства ядра. Это называлось переключением контекста (context switch).
Почему в прошедшем времени? Дело в том, что современные машины достаточно мощные, а оперативная память очень дешевая… Поэтому в ОС (Linux, FreeBSD) вся информация о процессе постоянно находится в памяти. В OC Linux она представлена структурой task_struct:
структура
task_struct (с комментариями)
struct task_struct { volatile long state; /* состояние процесса: -1 unrunnable, 0 runnable, >0 stopped */ unsigned long flags; /* флаги процесса */ int sigpending; mm_segment_t addr_limit; /* адресное пространство потока: 0-0xBFFFFFFF для пользовательских потоков 0-0xFFFFFFFF для потоков ядра */ 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. */ unsigned int cpu; int prio, static_prio; list_t run_list; prio_array_t *array; unsigned long sleep_avg; unsigned long sleep_timestamp; unsigned long policy; unsigned long cpus_allowed; unsigned int time_slice; task_t *next_task, *prev_task; /* предыдущая и следующая задачи в кольцевом двусвязном списке */ struct mm_struct *mm, /* адресное пространство процесса */ *active_mm; /* активное адресное пространство – для задач которые не имеют своего (например, задачи ядра) */ /* состояние задачи */ struct linux_binfmt *binfmt; int exit_code, exit_signal; int pdeath_signal; /* Этот сигнал посылается когда умирает родитель */ /* ??? */ 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) */ task_t *p_opptr, *p_pptr, *p_cptr, *p_ysptr, *p_osptr; struct list_head thread_group; /* PID hash table linkage. */ task_t *pidhash_next; task_t **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, total_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; /* namespace */ struct namespace *namespace; /* signal handlers */ spinlock_t sigmask_lock; /* Protects signal and blocked */ struct signal_struct *sig; /* ccылка на обработчики сигналов */ 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; /* TUX state */ void *tux_info; void (*tux_exit)(void); /* Thread group tracking */ u32 parent_exec_id; u32 self_exec_id; /* Protection of (de-)allocation: mm, files, fs, tty */ spinlock_t alloc_lock; /* journalling filesystem info */ void *journal_info; }; |
Множество всех процессов в Linux представлены совокупностью структур, которые связанны между собой:
Разъясним некоторые поля структуры:
| TASK_RUNNING | 0 | указывает на то, что задача "вероятно" находится в очереди запущенных задач (runqueue). Причина, по которой задача может быть помечена как TASK_RUNNING, но не помещена в runqueue в том, что пометить задачу и вставить в очередь - не одно и то же. Если заполучить блокировку runqueue_lock на чтение-запись и просмотреть runqueue, то можно увидеть, что все задачи в очереди имеют состояние TASK_RUNNING. Таким образом, утверждение "Все задачи в runqueue имеют состояние TASK_RUNNING" не означает истинность обратного утверждения |
| TASK_INTERRUPTIBLE | 1 | задача “спит”, но может быть “разбужена” сигналом или по истечению таймера |
| TASK_UNINTERRUPTIBLE | 2 | подобно TASK_INTERRUPTIBLE, только задача не может быть "разбужена" |
| TASK_ZOMBIE | 4 | задача, завершившая работу, до того как родительский процесс ("естественный" или "приемный") произвел системный вызов wait |
| TASK_STOPPED | 8 | задача остановлена, либо по управляющему сигналу, либо в результате вызова ptrace |
| ПРИМЕЧАНИЕ Системный вызов, это требование к ОС (ядру) произвести аппаратно/системно специфическую или привилегированную операцию |
#define PF_ALIGNWARN 0x00000001 /* Print alignment warning msgs */ /* Not implemented yet, only for 486*/ #define PF_STARTING 0x00000002 /* создается */ #define PF_EXITING 0x00000004 /* завершается */ #define PF_FORKNOEXEC 0x00000040 /* создан, но не запущен */ #define PF_SUPERPRIV 0x00000100 /* использует привилегии супер-пользователя */ #define PF_DUMPCORE 0x00000200 /* выполнен дамп памяти */ #define PF_SIGNALED 0x00000400 /* "убит" по сигналу */ #define PF_MEMALLOC 0x00000800 /* Распределение памяти */ #define PF_MEMDIE 0x00001000 /* Killed for out-of-memory */ #define PF_FREE_PAGES 0x00002000 /* per process page freeing */ #define PF_NOIO 0x00004000 /* avoid generating further I/O */ #define PF_USEDFPU 0x00100000 /* задача использует FPU this quantum (SMP) */ |
В Linux существует три типа задач:
Остановимся, несколько подробно на первом типе задач. Фоновая задача создается во время компиляции (at compile time) для первого CPU; и затем "вручную" размножается для каждого процессора вызовом fork_by_hand() из arch/i386/kernel/smpboot.c. Фоновая задача имеет общую структуру init_task, но для каждого процессора создается свой собственный TSS, в массиве init_tss. Все фоновые задачи имеют pid = 0 и никакой другой тип задач больше не может разделять pid, т.е. не могут клонироваться с флагом CLONE_PID через clone (см. ниже).
Структура init_task эквивалентна task_struct. Это видно из ее определения:
/* в файле sched.h */ typedef struct task_struct task_t; … #ifndef INIT_TASK_SIZE #define INIT_TASK_SIZE 2048*sizeof(long) #endif … union task_union { task_t task; /* структура фоновой задачи */ unsigned long stack[INIT_TASK_SIZE/sizeof(long)]; /* стек фоновой задачи */ }; extern union task_union init_task_union; /* в файле processor.h */ #define init_task (init_task_union.task) #define init_stack (init_task_union.stack) |
Со стороны API функции по созданию потоков представлены двумя семействами функций: fork и clone (обе функции являются платформенно-зависимыми). Со стороны ядра обе эти функции обращаются к do_fork (эта функция является переносимой). В этой работе я не буду подробно останавливаться на реализации этих функций, лишь основные моменты.
/* файл sched.h */ /* do_fork объявлена следующим образом */ extern int do_fork(unsigned long, unsigned long, struct pt_regs *, unsigned long); /* со следующими параметрами */ /* файл fork.h */ /* копирует системную информацию, сегмент данных. Устанавливает нужные регистры int do_fork(unsigned long clone_flags, unsigned long stack_start, struct pt_regs *regs, unsigned long stack_size){ … } |
Системный вызов pid_t fork() - создает дочерний процесс, который отличается от родительского только значениями PID (идентификатор процесса) и PPID (идентификатор родительского процесса), а также тем фактом, что счетчики использования ресурсов установлены в 0. Блокировки файлов и сигналы, ожидающие обработки, не наследуются.
При успешном завершении родителю возвращается PID дочернего процесса, а дочернему процессу возвращается 0. При неудаче родительскому процессу возвращается -1, дочернего процесса не создается, а errno выставляется следующим образом:
| EAGAIN | может возвратить в случае: "родитель" является пользовательским ресурсом и превышен RLIMIT_NPROC, превышено системное ограничение на общее число задач - max_threads |
| ENOMEM | в случае невозможности распределить память под новую структуру задачи |
| ПРИМЕЧАНИЕ /* файл asm-i386\resource.h */ #define RLIMIT_NPROC 6 /* максимальное число процессов */ |
| ПРИМЕЧАНИЕ /* В качестве максимально возможного числа потоков принимается безопасное значение: структуры потоков не могут занимать более половины имеющихся страниц памяти */ max_threads = mempages / (THREAD_SIZE/PAGE_SIZE) / 2; |
Системный вызов fork(): соответствует следующим спецификациям: SVr4, SVID, POSIX, X/OPEN, BSD 4.3.
При создании дочернего потока при помощи системного вызова fork дочерний процесс наследует от родительского некоторые части контекста выполнения. Например: пространства памяти, таблицу дескрипторов фалов, таблицу хэндлов сигналов… Иногда, это не нужно, более того, может быть опасным.
Основное применение системного вызова int clone(int (*fn)(void *), void *child_stack, int flags, void *arg) это создание вытесняющей многозадачности в рамках адресного пространства одного процесса.
Исполнение дочернего потока начинается с функции int (*fn)(void *) (родитель же, исполняет код непосредственно следующий за вызовом clone), указатель на которую и является первым параметром clone. Аргументом, передаваемым в fn при создании потомка, является значение void *arg. Окончание выполнения потомка заканчивается возвратом fn, а кодом завершения потомка является возвращаемое fn целое значение. Также потомок может завершится при помощи системного вызова exit() или по сигналу.
Родитель и потомок имеют одно адресное пространство, однако дочернему процессу нужен свой стек, об этом должен позаботится родитель. Для этого используется параметр void *child_stack, который и передает указатель на стек, выделенный родителем для своего “дитя”.
int flags снимает описанные выше проблемы с разделением контекста выполнения задачи. Он строго указывает какие части контекста следует разделять. К тому же, нижний байт flags может содержать значение сигнала, который потомок пошлет родителю о своем завершении (если этот байт не определен то родитель не будет информирован о завершении). flags принимает следующие значения, которые могут комбинироваться между собой:
/* файл sched.h */ /* флаги клонирования: позволяют разделять (или не разделять) те или иные ресурсы между родителем или потомком */ #define CSIGNAL 0x000000ff /* маска сигнала о завершении потомка*/ #define CLONE_VM 0x00000100 /* клонирование виртуального адресного пространства. Кроме того разделяются все карты памяти (memory mapping) созданные mmap или munmap */ #define CLONE_FS 0x00000200 /* клонирование файловой системы: корневой, текущий каталоги, а так же umask. В случае, если CLONE_FS не установлен, вызов в одном из потоков (родительском или дочернем) hroot, chdir, umask не будет иметь эффекта в другом */ #define CLONE_FILES 0x00000400 /* разделение таблицы дескрипторов открытых файлов */ #define CLONE_SIGHAND 0x00000800 /* разделение таблицы обработчиков сигналов */ #define CLONE_PID 0x00001000 /* клонировании pid потока (может быть выставлен только при создании фоновой задачи (см. выше)) */ #define CLONE_PTRACE 0x00002000 /* устанавливается в случае желания продолжать трассировку для дочернего процесса */ #define CLONE_VFORK 0x00004000 /* устанавливается, если родитель хочет, что бы потомок проснулся в ответ на mm_release */ #define CLONE_PARENT 0x00008000 /* предок и клон имеет одного и того же родителя */ #define CLONE_THREAD 0x00010000 /* потомок будет находится в той же группе потоков, что и родитель */ /* предопределено следующее значение */ #define CLONE_SIGNAL (CLONE_SIGHAND | CLONE_THREAD) |
В случае успешного завершения clone возвращает PID потомка. В противном случае: -1. А errno устанавливается следующим образом:
| EAGAIN | аналогично fork |
| ENOMEM | аналогично fork |
| EINVAL | child_stack был установлен в ноль |
| EPERM | флаг CLONE_PID был установлен процессом с ненулевым PID |
У clone есть свой минус он является Linux специфичным системным вызовом, и если необходимо писать переносимый код то лучше воспользоваться библиотекой реализующей стандарт POSIX 1003.1c на API по созданию потоков. А в частности функцией pthread_create.
Теперь небольшой пример на тему создания потоков.
#include <stdio.h> #include <sys/types.h> #include <sys/wait.h> #include <unistd.h> #include <sys/resource.h> #include <sched.h> void print_task_info(){ printf("---pid: %i---\n", getpid()); printf("\tParent ID: %i\n", getppid()); } /* функция клона (потомка) */ int cln_func(void*){ print_task_info(); return 0; } /* стек потомка */ struct child_stack{ char cnt[1000]; }; int main(){ printf("Родитель:\n"); print_task_info(); printf("\nПотомки:\n"); child_stack stacks[2]; /* стеки */ /* создание клонов с разными флагами */ clone(cln_func, &stacks[0], CLONE_PARENT, NULL); clone(cln_func, &stacks[1], 0x0, NULL); /* создание потомка системным вызовом fork */ if(!fork()){ /* код потомка */ print_task_info(); return 0; } /* код родителя */ wait(NULL); /* ожидаем завершения всех дочерних потоков */ return 0; } |
После запуска программа выведет следующее:
Родитель: ---pid: 10887--- Parent ID: 10303 Потомки: ---pid: 10888--- Parent ID: 10303 ---pid: 10889--- Parent ID: 10887 ---pid: 10890--- Parent ID: 10887 |
Отсюда видно, различие в родителях созданных потоков с флагом: CLONE_PARENT и без него. Все нюансы, связанные с флагами клонирования, будут рассмотрены в соответствующих главах.
Рассмотрим более подробно содержимое этих структур (здесь и далее приводятся фрагменты исходных кодов ядра ОС Linux 2.4.18-3 для архитектуры i386, а так же из GNU C Library)
фрагмент
файла user.h
struct user{ struct user_regs_struct regs; /* Структура в которой хранится содержимое регистров. */ int u_fpvalid; /* True если используется математический математический сопроцессор. */ /* Оставшаяся часть этого хлама позволяет gdb узнать откуда что берется и куда уходит. */ unsigned long int u_tsize; /* Размер сегмента кода (страницы). */ unsigned long int u_dsize; /* Размер сегмента данных (страницы). */ unsigned long int u_ssize; /* Размер сегмента стека (страницы). */ unsigned long start_code; /* Начальный виртуальный адрес области кода. */ unsigned long start_stack; /* Начальный виртуальный адрес области стека. На самом деле, это адрес дна стека, вершина стека всегда находится в регистре esp. */ long int signal; /* Сигнал вызвавший the core дамп. */ int reserved; /* Не используется */ struct user_pt_regs * u_ar0; /* Используется gdb для нахождения значений регистров. */ struct user_i387_struct* u_fpstate; /* Math Co-processor pointer. */ unsigned long magic; /* Для однозначной идентификации core файла. */ char u_comm[32]; /* User command that was responsible. */ int u_debugreg[8]; /* Содержимое регистров отладки (8 шт). */ }; |
Полагаю здесь все ясно. Однако, следует дать некоторые комментарии относительно core файла. Core файл содержит информацию необходимую для отладки процесса. Core файл создается, например, в случае критической ошибки в процессе или если процесс вызвал системный сбой. Содержимое core файла записывается таким образом, что бы отладчик (например gdb) в дальнейшем мог понять его и пользователь мог почерпнуть некоторую полезную для себя информацию. Обычно, сore файл имеет следующий формат:
UPAGE: эта часть обязательно должна быть равна одной странице (4096 байт). Она включает в себя содержимое структуры user. Непосредственно после нее идет копия содержимого структуры task_struct (см. ниже), пока она не используется gdb, но может быть очень полезна в ряде случаев. В эту часть также включается содержимое всех регистров.