Если долго всматриваться в бездну -
бездна начнет всматриваться в тебя.
Фридрих Ницше

Scheduler NewOS/OpenBeOS ядра.

1. Мысле к себе.

Вот сел и написал. Потом еще раз просмотрел и поправил. Наверно поэтому иногда "стрела" мысли сбивается по тексту и как будто возвращается на несколько шагов назад. Выбрал я Scheduler, в народе известный как Планировщик, Шедулер, Скедулер и по прочим кличкам. Почему Scheduler? Наверно потому, что 90% таких же писателей, как и я сам, начинает с bootstrap, или с ProtectedMode (защищенный режим процессора - очень популярная область по какой-то причине ! Это важно, нет спора, но почему тогда большинство на этом и заканчивают ?). Другая половина начинает с абстрактных дизайнов с претензиями создать уникальную, сверх-современную и сверх-быструю операционную систему с NULL-я. Внешне, я, конечно, двумя руками поддерживаю все эти начинания и ни в коей мере не нападаю на авторов, а наоборот, восхищаюсь ими. Внутренне, я скептически отношусь к этому, но все равно, восхищаюсь. Я сам бы не взялся за такое дело. Наверно потому, что я реалист и прекрасно осознаю, что гением меня природа не наделила, поэтому знания чрезвычайно ограничены и способности писать код еще в более плачевном состоянии. Цель, которую я преследаю, можно охарактеризовать простыми словами: "Как оно работает ?". Мне это интересно, поэтому я занимаюсь самообразованием. И пишу для себя. Зуд постучать по кнопкам, без кириллических наклеек. Как было замечено до этого, я прекрасно осознаю свой уровень, поэтому количество ошибок, неувязок, неправильных интерпретаций много. Еще одно причина, побудившая взять Scheduler, как первых шаг на лунную поверхнось - это потому, что этот компонент - достаточно простая часть ядра. Bootstrap и переключение ProtectedMode - тоже важно, нет спора, но их задача настолько специфична и прямолинейна, и вдобавок, 99% всех "доморощенных" *OS уже благополучно умерли после этого шага...

Знания С и ассемблера - обязательны. Незнание - также обязательно, иначе, зачем читать, если все уже знаешь.

2. Scheduler.

Scheduler занимается задачей распределения ресурсов процессоров. Ресурс процессора - это, собственно, выполнение кода. Кому как, а по мне, так Scheduler является сердцем ОС. Аналогия напрашивается сама - импульсы сердца и распределение крови различным органам, как тики таймера и распределение квантов (слайсов времени) разным процессам. Собственно, это и определяет основную задачу Scheduler-а - по-умному раздавать кванты времени выполнения всем процессам, чтобы они не "голодали" и все получили свою долю что-то выполнить. Это метод - Preemptive Multitasking, и является довольно распространенным подходом в современных ОС, так как процессы или струны не должны заботиться о том, чтобы "отдать" процессор кому-то еще, как было в системах с cooperative мультизадачностью (знаменитые Window 3 серия). UNIX изначально был ориентирован на очень "тяжелую" мультизадачность, если вспомнить на каких машинах он был написан (PDP-7 не в счет, более менее пристойная c-версия - это уже PDP-11). Современные UNIX системы, как коммерческие, так и бесплатные, имеют свои реализации Scheduler-ов. Если доступ к кодам коммерческих систем достаточно ограничен, то открытые UNIX системы во многом не уступают своим дорогим братьям. Насчет превосходят, наверно будет амбициозно сказано, достаточно сравнить Solaris или Tru64 с FreeBSD.

Cooperative multitasking если и используется в настоящее время, то только в небольших real-time embedded системах, где почти все процессы "заточены" для выполнения в строгой детерминистической последовательности. В системах, которые предоставляют достаточное количество ресурсов, вытесняющая мультизадачность (preemtive multitasking) стала "де-факто". Для меня именно Preemtive Multitasking Scheduler представляет интерес.

Чтобы сразу не утонуть в коде Scheduler-а с поддержкой Upcall и Kernel Activation и прочими "наворотами", предпочтительнее начать рассмотрение с простого, реального Scheduler-а. Выбор пал на Scheduler из OpenBeOS проекта, так как я лично испытываю определенную "слабость" к BeOS. Я еще вернусь к проекту OpenBeOS в будущем и "поразмышляю" о нем, а сейчас просто ограничусь их кодом. Сразу же расставлю точки над "i" - код, на который я посмотрю, изначально был написан не OpenBeOS группой, а одним талантливым молодым человеком по имени Трэвис Гайзелбрехт (Travis Geiselbrecht), который был сотрудником Be,Inc во времена, когда компания еще дышала. Трэвис написал небольшое ядро, названное "оригинально" - NewOS (http://newos.sourceforge.net/). OpenBeOS проект взял это ядро за основу своей системы и в настоящее время ядро развивается совсем небольшой группой под предводительством удивительно талантливого парня по имени Аксель Дёфлер (Axel Doefler). Аксель является главным разработчиком ядра OpenBeOS и еще он известен тем, что почти в одиночку написал открытую BeOS файловую систему (bfs). Безусловно, в будущем Scheduler будет достаточно основательно переписан, но его настоящая простота подкупает рассмотреть его, как пробу сил.

Для тех, кто читает это: есть три пути, как добраться до исходников OpenBeOS: прямиком на cvs сервер через cvs-клиент, или по HTTP через WebCVS интерфейс, или, вообще, "слить" tarball через HTTP. Что такое cvs я подразумеваю, знают все. Те кто в первый раз слышит, что это такое, наверно по ошибке читают этот текст. WebCVS - чрезвычайно полезная вещь когда нужно посмотреть "по-быстрому", а также тем бедным душам, которые сидят за Firewall (как я в настоящее время, которе совсем скоро истечет). Но это, как говориться, для "бедных". Для win32 платформ пойдет WinCVS, для BeOS: на сайте openbeos.org в секции Dev лежит ссылка на cvs клиент. Для BSD/Linux/commercial Unix систем - cvs свой (я полагаю, что это читают программисты, поэтому cvs себе поставили).

Все остальное чрезвычайно просто:
1) cvs -d:pserver:anonymous@cvs.sourceforge.net:/cvsroot/open-beos login
2) cvs -z3 -d:pserver:anonymous@cvs.sourceforge.net:/cvsroot/open-beos co current
3) cvs -d:pserver:anonymous@cvs.sourceforge.net:/cvsroot/open-beos logout
можно прописать в CVSROOT переменной путь к серверу, чтобы не использовать -d опцию в каждой команде. Если это первый checkout репозитория, то 11 метров - это вам не шутка по dialup модему, даже если -z3 опция используется. Для тех, кто сидит на кабеле или DSL - пара минут конечно, если sourceforge дышит... Иногда он кашляет, а иногда вообще задерживает дыхание надолго.
cvs создаст рабочий проект в текущей директории с имееи current.

Последний упомянутый метод - скачать tarball, архив cvs репозитория в tar архиве. Это удобно для тех, кто находиться за firewall-ом или кто не собирается заниматься разработкой OpenBeOS (а есть такие, кто собирается ?!). Недостаток тот, что надо качать 11 метров (на момент написания), даже, если изменился один файл, так что cvs - все еще самый гибкий метод. Для OpenBeOS проекта архив кода лежит здесь: http://cvs.sourceforge.net/cvstarballs/open-beos-cvsroot.tar.gz. Sourceforge регулярно пакует свои проекты в tarball, но как часто, я не уверен.

В дальнейшем, я буду приводить ссылки на WebCVS интерфейс, как самый универсальный и простой метод.

Открываем браузер и прямиком на http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/open-beos/current. Мой путь лежит прямо сюда: /src/kernel/core. Файл с незатейливым именем scheduler.c - это моя цель. На этапе написания, последняя за-checkin-ая версия файла: 1.9 от 23 января 2003 года.

Прежде чем просматривать код Scheduler-а, необходимо упомянуть, что является выполняемой единицей в OpenBeOS. Традиционные старые UNIX ядра давали кванты процессам и соответственно процесс являлся выполняемой единицей. Он содержал PCB (process control block), который хранил архитектурно-зависимое состояние процесса на момент, когда он не выполняется на процессоре (общие регистры, спец.регистры, информация о виртуальной памяти). С эволюцией систем и внедрением LWP (Light Wright Process) настала эпоха струнных систем. Scheduler-ы большинства современных систем (Solaris, OSF1 (Tru64), OpenVMS, BeOS, Mach3 (Hurd), NetBSD, поздние ядра Linux и FreeBSD) квантуют струны, а не процессы, так как они поддерживают внутриядерные струны. Это особо актуально для многопроцессорных машин. Вопросы пользовательских струн (user-land threads), LWP (псевдо-ядерных струн) и чистых ядерных струн (kernel threads) я здесь не рассматриваю.

Знаменитая BeOS базируется на собственном закрытом ядре и содержит один из самых "динамичных" Scheduler-ов, тщательно отшлифованный под Desktop приложения. Выполняемой единицей является ядерная струна. Scheduler BeOS выделяет кванты очень грамотно, динамически изменяя приоритет в зависимости от нагрузки, но всегда давая предпочтение интерактивным приложениям (что очень важно для Desktop системы). Все, кто хоть раз поработал с BeOS понимают о чем я говорю. Linux+XFree изо всех сил пытаются отточить "отзывачивость" Dekstop-а, но пока до BeOS еще очень далеко. Даже FreeBSD+XFree, для меня лично, более отзывчиво. Может потому, что я очень "люблю" Linux :)

OpenBeOS претендует на звание современной системы и хочет как можно точнее воспроизвести поведение BeOS. Поэтому, не удивительно, что Scheduler квантует струны. Так как основня платформа разработки OpenBeOS является Intel, то я буду смотреть преимущественно на ia32 архитектуру в коде.

Платформо-независимое описание струны лежит в файле thread_types.h а интерфейс - thread.h. Для начала в файл thread_types.h:

/* Thread definition and structures ** ** Distributed under the terms of the OpenBeOS License. */ #ifndef _KERNEL_THREAD_TYPES_H #define _KERNEL_THREAD_TYPES_H стандартная защита от многочисленныx переопределений #include <stage2.h> #include <ktypes.h> #include <cbuf.h> #include <vm.h> #include <smp.h> #include <signal.h> #include <timer.h> #include <list.h> #include <arch/thread_struct.h> инклуды как инклуды, разве что <arch/thread_struct.h> представляет повышенный интерес extern spinlock thread_spinlock; глобальный спин-лок мютекс на очередь струн. Спин-лок, синхронизирующий примитив, представляет собой наипростейший мютекс, выполняющий CPU-busy цикл, проверяя на особождение лока другой струной. Так как CPU-busy цикл является хорошим нагревательным методом для процессора, то такой синхронизатор должен, скорее, ОБЯЗАН, быть освобожден как только, так и сразу. #define GRAB_THREAD_LOCK() acquire_spinlock(&thread_spinlock) макрос для лока мютекса #define RELEASE_THREAD_LOCK() release_spinlock(&thread_spinlock) макрос для освобождения мютекса extern struct thread_queue dead_q; кэш струн. Это типичная оптимизация - кешировать освобожденный ресурс, так как практика показывает, что создавать прийдется немедленно через пару десятков миллисекунд. Поэтому структура струны не освобождается, а кэшируется в этой очереди и подхватывается, если надо создать новую. extern spinlock team_spinlock; глобальный мютекс для процесса, который в идеологии OpenBeOS называется командой. В смысле игровой командой, а не "приказом". Изначально разработчики BeOS называли процессы командами, поэтому OpenBeOS следует тому же принципу. На скриншоте BeOS5 видно, что основной kernel процесс имеет имя "kernel_team": Я буду придерживаться определения - процесс, так как это мне ближе // NOTE: TEAM lock can be held over a THREAD lock acquisition, // but not the other way (to avoid deadlock) #define GRAB_TEAM_LOCK() acquire_spinlock(&team_spinlock) #define RELEASE_TEAM_LOCK() release_spinlock(&team_spinlock) Глобальные синхронизаторы для операций над процессами. В ситуации, когда необходимо предохранять и струны и процессы, то следует очень строго придерживаться правила "одновременного" захвата мютексов, чтобы не зависнуть (deadlock). Правило простое: снача хватаем мютекс процессов, потом струн, освобождаем струны, освобождаем процессы. Deadlock возникает с гарантией 100% (как показывает практика, а не эмперические размышления), если нарушить последовательность. Почему, я думаю все понимают - перекрестный лок и ожидание перекрестного ресурса. enum additional_thread_state { // THREAD_STATE_READY = 0, // ready to run // THREAD_STATE_RUNNING, // running right now somewhere // THREAD_STATE_WAITING, // blocked on something // THREAD_STATE_SUSPENDED, // suspended, not in queue THREAD_STATE_FREE_ON_RESCHED = 7, // free the thread structure upon reschedule // THREAD_STATE_BIRTH // thread is being created }; только THREAD_STATE_FREE_ON_RESCHED используется, но я все равно в коде не увидел его. Даю 100%, что это хозяйство скоро исчезнет, так как thread_state заменяет все. enum team_state { TEAM_STATE_NORMAL, // normal state процесс в добром здравии и выполняется TEAM_STATE_BIRTH, // being contructed процесс создается TEAM_STATE_DEATH // being killed процесс уничтожается }; статус процесса enum { KERNEL_TIME, USER_TIME }; используеься для статистики струны количества тиков в ядре и коде процесса (это то, что видно в "ps" и "top" командах в нормальных системах, но пока не в OBOS) #define THREAD_RETURN_EXIT 0x1 #define THREAD_RETURN_INTERRUPTED 0x2 struct image; // defined in image.c представление процесса, как сборной секций, или почти копия представления процесса в файле. собственно процесс... struct team { struct team *next; /* next team in the hash */ следующий процесс в очереди процессов в ячейке хеша. Что такое хеш и почему там очереди, объяснять не надо, я полагаю. team_id id; идентификатор процесса (pid в нормальных системах ) char name[SYS_MAX_OS_NAME_LEN]; имя процесса int num_threads; /* number of threads in this team */ количество струн в процессе int state; /* current team state, see above */ текущий статус процесса int pending_signals; кол-во сигналов, которые необходимо послать процессу. Сигналы сразу не диспетчерезируются (во загнул !) сразу в процесс, а посылаются Scheduler-ом, когда ему дадут квант,перед передачей контекста главной струне void *io_context; конектс ввода/вывода (не знаю, что это, надо grep-ить) sem_id death_sem; /* semaphore to wait on for dying threads */ семафор, который используется для ожидания, когда струны процесса завершают работу. Что такое семафор, даже не обсуждается. aspace_id _aspace_id; /* address space pointer */ идентификатор адресного пространства процесса vm_address_space *aspace; виртуальное адресное пространство процесса, пользовательское vm_address_space *kaspace; виртуальная адресное пространство процесса, в ядре addr user_env_base; указатель на память, где лежат переменные окружения для процесса struct thread *main_thread; главная струна процесса, которая создается автоматически (какой смысл в процессе, если в нем нет струны) struct thread *thread_list; очередь струн, которые принадлежат процессу. Одни и те же струны лежат в многочисленных очередях для быстрого доступа. struct list image_list; список, содержащий секции процесса struct arch_team arch_info; архитектурно-зависимая информация процесса }; собственно струна... struct thread { struct thread *all_next; следующая струна в глобальной очереди струн struct thread *team_next; следующая струна в очереди струн процесса struct thread *queue_next; /* i.e. run queue, release queue, etc. */ следующая струна в очереди струн, которые в одинаковом состоянии (выполняемая очередь, очередь убитых и закешированных струн) timer alarm; таймер тревоги для SIGALRM сигнала и alarm() thread_id id; идентификатор струны char name[SYS_MAX_OS_NAME_LEN]; имя струны (в BeOS струны имеют именное пространство, в отличии, например от user-land струн в pthread) int priority; приоритет струны int state; текущий статус струны, что она делает int next_state; будущий статус струны, что она должна будет делать union cpu_ent *cpu; процессорная информация. Так как это важная информация, то рассмотрю это объединение прямо здесь. Файл headers/private/kernel/cpu.h typedef union cpu_ent { /** The information structure, followed by alignment bytes to make it ?? bytes */ struct { /** Number of this CPU, starting from 0 */ int cpu_num; номер процессора, на котором бежит струна. процессоры идут (0.. макс.определенный) /** If set this will force a reschedule when the quantum timer expires */ int preempted; флажок, идентифицирующий или у струны надо отобрать квант смысл будет понятен, когда рассмотрю код Scheduler-а /** Quantum timer */ timer quantum_timer; таймер кванта } info; /** Alignment bytes */ uint32 align[16]; пустышки, необходимые для выравнивания в кеше } cpu_ent; /** * Defined in core/cpu.c */ extern cpu_ent cpu[MAX_BOOT_CPUS]; количество процессоров, поддерживаемых ядром. Указатель в thread структуре направляет на элемент этого массива Пошли далее со струной... sigset_t sig_pending; маска сигналов, которые необходимо послать струне. sigset_t sig_block_mask; маска сигналов, которые не перехватываются струной и должны обрабатываться ядром struct sigaction sig_action[32]; bool in_kernel; флажек, определяющий или струна сейчас работает в ядре (системный вызов, например) sem_id sem_blocking; семафор на котором блокирована струна int sem_count; кол-во ресурсов семафора int sem_acquire_count; кол-во захваченных ресурсов int sem_deleted_retcode; чего такое ? int sem_errcode; код возврата семафора int sem_flags; аттрибуты семафора структуры сообщения для IPC (interprocess communication). Это же микроядро, в конце концов struct { sem_id write_sem; семафор для записи sem_id read_sem; семафор для чтения thread_id sender; струна, которая послала сообщение int32 code; код сообщения size_t size; размер сообщения cbuf *buffer; собственно сообщение } msg; addr fault_handler; перехватчик прерывания неподгруженной страницы памяти /* this field may only stay in debug builds in the future*/ int32 page_faults_allowed; кол-во разрешаемых перехватов. Обычно слишком высокое число означает, что идет сильный стесс виртуальной систым и страницы выгружаются и подгружаются неэффективно для разных процессов. Дебаг код будет проверять, чтобы это значение было небольшим и уходить в панику, если превысило лимит. Это позволит оптимизировать ядро и VM комментарий говорит, что для нормального ядра этого счетчика лимита не должно быть, что, конечно, логично. thread_func entry; адрес функции струны - собственно код, который выполняется в струне void *args; параметр, передаваемый в струну struct team *team; ссылка на процесс, которому "принадлежим". status_t return_code; код возврата, когда струны отыграла свое sem_id return_code_sem; код возврата семафора int return_flags; не знаю, что за флажки // stack стековое пространство струны region_id kernel_stack_region_id; идентификатор региона стека в ядре addr kernel_stack_base; адрес стека в ядре region_id user_stack_region_id; идентификатор региона стека в ядресном пространстве процесса addr user_stack_base; адрес пользовательского стека addr user_local_storage; адрес TSL (thread local storage), приватного конейнера данных струны струны шарят пространство процесса, но для своих нужд имеют свою небольшую память (например errno переменная наиболее известна) // usually allocated at the safe side of the stack как говорит комментарий, TSL размещается в стеке, что есть умно int kernel_errno; код возврата системных функций для внутри-ядерных нужд // kernel "errno" differs from its userspace alter ego статистическая информация, используемая умными Scheduler-ами для убийства процессов при серьезной недостаче виртуалки и при динамическом изменении приоритетов (не в OBOS) bigtime_t user_time; кол-во времени, проведенного в коде процесса bigtime_t kernel_time; кол-во времени, проведенного в коде ядра bigtime_t last_time; суммарное кол-во времени в ядре и процессе на последнем кванте int last_time_type; // KERNEL_TIME or USER_TIME // architecture dependant section struct arch_thread arch_info; платформо-зависимая информация струны }; очередь струн предствалена чрезвычайно простым определением: struct thread_queue { struct thread *head; начало очереди, первая струна struct thread *tail; конец очереди, последняя струна }; #endif /* _KERNEL_THREAD_TYPES_H */ Платформо-зависимая информация: headers/private/kernel/arch/x86/thread_struct.h /* ** Copyright 2001-2002, Travis Geiselbrecht. All rights reserved. ** Distributed under the terms of the NewOS License. */ #ifndef _KERNEL_ARCH_x86_THREAD_STRUCT_H #define _KERNEL_ARCH_x86_THREAD_STRUCT_H struct farcall { unsigned int *esp; unsigned int *ss; }; указатель на стек #define IFRAME_TRACE_DEPTH 4 сколько прерываний может держать одна струна. 4 означает, что 1-й раз струну остановят при первом трэпе, и еще 3 прерывания можна обработать поверху, прежде чем отдать управление обратно струне. // architecture specific thread info непосредственно intel-зависимая структура, которая держится контекстом струны struct arch_thread { struct farcall current_stack; текущий указатель на стек struct farcall interrupt_stack; указатель на стек при прерывании // used to track interrupts on this thread struct iframe *current_iframe; указатель на структуру, держащую текущий фрейм прерывания (interrupt-фрейм, файл arch_cpu.h) когда происходит аппаратное прерывание (trap), обработчик (функция void i386_handle_trap(struct iframe frame) в arch_thread.c), определяет, какая струна в данный момент выполнялась и сохраняет в этой переменной ссылку на i-фрейм. Сам i386_handle_trap() вызывается из дзен-уровня: arch_interrupts.S. Код там заслуживает небольшого ознакомления с AT&T асмом, поэтому оставлю на потом. Смысл же кода в том, чтобы получить управление при аппаратном прерывании, занести вектор трэпа, затолкнуть i-фрейм на стек и вызвать i386_handle_trap(). Так как i386_handle_trap "загрязнен" тем, что вызывает "высокоуровневую" функцию Scheduler-а, то я к нему вернусь после просмотра самого кода Scheduler-а. struct iframe *iframes[IFRAME_TRACE_DEPTH]; при многочисленных перехватах (разные прерывания), несколько i-фрэймов должно лежать на стеке, поэтому несколько указателей будут в ограниченном массиве. функция void i386_push_iframe(struct thread *thread, struct iframe *frame) из arch_thread.c отвечает за сохранение i-фрейма в контесте струны и увеличении счетчика. При переборе, уходим в панику на assert-е. int iframe_ptr; счетик количества сохраненных i-фреймов (он же индекс массива) // 512 byte floating point save point uint8 fpu_state[512]; контекст сопроцессора }; struct arch_team { // nothing here }; процесс не содержит ничего "архитектурного" (что есть логично) #endif /* _KERNEL_ARCH_x86_THREAD_STRUCT_H */ Статус струны и приоритеты лежат в общем, открытом файле: /headers/os/kernel/OS.h typedef enum { B_THREAD_RUNNING = 1, струна бежит B_THREAD_READY, струна готова бежать (было создана или блокирована до этого) B_THREAD_RECEIVING, не используется B_THREAD_ASLEEP, струна блокирована, например, на вызов sleep() (не используется) B_THREAD_SUSPENDED, струна приостановлена, например, SIGSTP сигналом (не используется) B_THREAD_WAITING струна ожидает ресурс и блокирована (не используется) } thread_state; приоритеты: #define B_IDLE_PRIORITY 0 #define B_LOWEST_ACTIVE_PRIORITY 1 #define B_LOW_PRIORITY 5 #define B_NORMAL_PRIORITY 10 #define B_DISPLAY_PRIORITY 15 #define B_URGENT_DISPLAY_PRIORITY 20 #define B_REAL_TIME_DISPLAY_PRIORITY 100 #define B_URGENT_PRIORITY 110 #define B_REAL_TIME_PRIORITY 120 #define B_FIRST_REAL_TIME_PRIORITY B_REAL_TIME_DISPLAY_PRIORITY #define B_MIN_PRIORITY B_IDLE_PRIORITY #define B_MAX_PRIORITY B_REAL_TIME_PRIORITY тут и без лишних слов понятно, что к чему. B_REAL_TIME_PRIORITY самый "сильный" приоритет, и струны на нем будут бегать в ущерб всем остальным.

Наконец-то код Scheduler-а:

/* scheduler.c 
** The scheduler code 
**/
/* 
** Copyright 2001-2002, Travis Geiselbrecht. All rights reserved. 
** Distributed under the terms of the NewOS License. 
*/
Копирайт Трэвиса, заботливо оставленный ребятами из OpenBeOS. 

#include <OS.h> 
#include <kernel.h> 
#include <thread.h> 
#include <thread_types.h> 
#include <timer.h> 
#include <int.h> 
#include <smp.h> 
#include <cpu.h> 
#include <khash.h> 
#include <Errors.h> 
#include <kerrors.h>
Инклуды, как говориться.
#define TRACE_SCHEDULER 0 
#if TRACE_SCHEDULER 
# define TRACE(x) dprintf x 
#else 
# define TRACE(x) ; 
#endif
Все понятно и без слов.

// prototypes 
static int dump_run_queue(int argc, char **argv); 
static int _rand(void);

парочка неэкспортируемых локальных функий. Ниже они будут описаны.

// The run queue. Holds the threads ready to run ordered by priority. static struct thread_queue 
gRunQueue = {NULL, NULL};

Это самая главная глобальная структура. Она держит очередь струн, которые будут квантоваться 
Scheduler-ом на выполнение
static int _rand(void)
{
   static int next = 0;
   if (next == 0) next = system_time();
   next = next * 1103515245 + 12345;
   return((next >> 16) & 0x7FFF);
}
Функция возвращает псевдослучайное число, запускаемое от значения системного 
таймера и впоследствии генерируемое тривиальной бит-арифметическими 
преобразованиями. 

static int dump_run_queue(int argc, char **argv)
{
   struct thread *thread;
   thread = gRunQueue.head;

   if (!thread) 
      dprintf("Run queue is empty!\n");
   else 
   {
      while (thread) 
      {
         dprintf("Thread id: %ld - priority: %d\n", 
                 thread->id,thread->priority);
         thread = thread->queue_next;
      }
   }
   return 0;
}
Понятно и без слов: хватаем голову очереди потоков, бежим по всем и выводим
идетификатор потока и его приоритет.

/** Enqueues the thread into the run queue.
  * Note: THREAD_LOCK must be held when entering this function
*/

Функция занимается тем, что добавляет струну в главную очередь струн.
Из комментария видно, что люди понимают, что лочить надо, так как
код страшно reentrant и из каких потоков мы сюда будем попадать, только
богу будет известно. Как будет видно из кода, лок будет идти из
вызывающий функций.
void scheduler_enqueue_in_run_queue(struct thread *thread)
{
  struct thread *curr, *prev;
 
  // these shouldn't exist
  if (thread->priority > B_MAX_PRIORITY)
     thread->priority = B_MAX_PRIORITY;
  if (thread->priority < B_MIN_PRIORITY)
     thread->priority = B_MIN_PRIORITY;

  это безусловно левый код, о чем человек в комментарии и пишет.

  for(curr = gRunQueue.head, prev = NULL; 
      curr && (curr->priority >= thread->priority); 
      curr = curr->queue_next) 
  {
     if (prev)
       prev = prev->queue_next;
     else
       prev = gRunQueue.head;
  }

  бежим по всей очереди, начиная с головы, проверяя что струна, которую
  мы добавляем все еще меньше или равна в приоритете текущей струне на
  итерации в очереди: (curr->priority >= thread->priority). В процессе
  беготни по очереди все время помним предыдущую струну - она нам очень 
  понадобиться, чтобы правильно вставить нашу новую стрну. Вообще, работа
  с очередями (связанными списками) должна быть у читателя на уровне
  мозжечка.

  thread->queue_next = curr;

  когда нашли место для нашей новой струны, то в curr как раз ее адрес,
  а prev - соответственно держит предыдущую струну.

  if(prev)
     prev->queue_next = thread;
  else
     gRunQueue.head = thread;

  подсоединяем предыдущую струну к нашей новой и уходим.
}


/** Removes a thread from the run queue.
  * Note: THREAD_LOCK must be held when entering this function
*/

Функция удаляет струну из глобальной очереди.
void scheduler_remove_from_run_queue(struct thread *thread)
{
   struct thread *item, *prev;

   // find thread in run queue
   for (item = gRunQueue.head, prev = NULL; 
        item && item != thread; 
        item = item->queue_next) 
   {
      if (prev)
         prev = prev->queue_next;
      else
         prev = gRunQueue.head;
   }

   Пробежались по нашей очереди и нашли себя: item != thread, попутно,
   запомнив предыдущую струну в очереди в prev.
   
   ASSERT(item == thread);

   Проверим, что мы не слон, другими словами, что то, что мы нашли - это мы,
   так как докатиться могли аж до item равному NULL, но вызывать
   scheduler_remove_from_run_queue(NULL) как-то рука не подымается...

   if (prev)
      prev->queue_next = item->queue_next;
   else
      gRunQueue.head = item->queue_next;

   как обычно, правильно настроим указатели в предыдущей струне.
}

context_switch - более "глубокая" функция, ответственная за переключение
контекста, или на нормальном языке - передать CPU другому потоку. На 
теоретичеком уровне переключение контекста выполнения - достаточно
важный этап. Мало того, что текущее состояние процессора и арифметического
процессора должно быть сохранено, но надо еще работу с виртуальной
памятью проделать (переключить виртуалку, флашануть TLB кэш и т.п.)
Работы много и она очень дорогая в понятиях тактов. Все это богатство 
всегда архитектурно-зависимо и пишется на ассемблере. Компилируется хорошей такой серией 
#if defined() в зависимости от платформы.
Здесь надо заметить, что после того как произошло переключение контекса в context_switch,
новая струна немедленно начинаем работать (адрес откуда продолжить работу будет
лежать на стеке и туда уйдет код после ret.


static void context_switch(struct thread *fromThread, struct thread *toThread)
входные параметры - с какой струны переключаемся на какую другую струну.
{
   bigtime_t now;
   // track kernel & user time
   now = system_time();
   запомним текущий системный таймер

   if(fromThread->last_time_type == KERNEL_TIME)
      fromThread->kernel_time += now - fromThread->last_time;
   else
      fromThread->user_time += now - fromThread->last_time;
   здесь мы запомним статистику текущей струны: сколько проработали в
   коде ядра, а сколько непосредственно в самом коде процесса. Эта 
   статистика видна по "top" команде, а также очень охотно используется
   продвинутыми Scheduler-ами для динамического изменения приоритетов, если 
   струна обнаглела и захватила CPU только для себя.

   toThread->last_time = now;
   запомним текущий таймер в струне, куда переключаемся
   toThread->cpu = fromThread->cpu;
   переключаемся на тот же процессор, на котором выполнялась предыдущая
   струна, так как высока вероятность, что струна тогоже процесса и тогда не надо 
   флашить TLB и кеш
   fromThread->cpu = NULL;
   старая струна больше неактивна на этом процессоре
 
   arch_thread_set_current_thread(toThread);
   устанавливает новую текущую (выполняемую струну).
   arch_thread_context_switch(fromThread, toThread);
   платформо-зависимый код для переключения контекста.
   отсюда уже бежит новая струна, куда переключились
}

Платформо-зависимые функции отлеживаются в файлах: headers/private/kernel/arch/x86/arch_thread.h и
headers/private/kernel/arch/x86/arch_cpu.h.

static inline void
arch_thread_set_current_thread(struct thread *t)
{
   write_dr3(t);
}
#define write_dr3(value) \
   __asm__("movl	%0,%%dr3" :: "r" (value))
все эти строки выливаются в 1 ассемблерную инструкцию. gcc использует AT&T синтаксис 
ассемблера, где регистры префиксируются "%", и источник/получатель направление
изменено на противоположное. Например mov eax,ebx (intel) соответствует movl %ebx,%eax (AT&T).
Буквочки (l,b,w) добавляются к имени операнда вместо а-ля 'dword ptr' конструкций.
К сожалению, inline-ассемблер в gcc еще более извращен. Регистры
должны иметь еще один "%", так как одиночный "%" является аргументом функции. Сразу после
ассемблерной инструкции идет ":", как ограничитель. Затем выходные регистры, еще ограничитель,
входные регистры и есть еще список "грязных регистров", также после ограничителя.
Буквочка "r" обозначает - выбери сам регистр, компилятор. В скобках идет собственно для 
какого аргумента использовать регистр. Полная интерпретация выливается в:
1) скопировать аргумент value (который будет представлен регистром (который выбирет 
компилятор) в дебаг регистр dr3.
2) игнорировать результат.
Так как функция inline, то реальный код будет всего одной ассемблерной инструкцией.

Видно, что OBOS держит глобально текущую выполняемую струну в регистре dr3 
(указатель на нее, что делает OBOS пока не 64-битно совместимым).

void arch_thread_context_switch(struct thread *t_from, struct thread *t_to)
{
   addr new_pgdir;
   #if 0
   int i;
   dprintf("arch_thread_context_switch: cpu %d 0x%x -> 0x%x, aspace 0x%x -> 0x%x, old stack = 0x%x:0x%x, stack = 0x%x:0x%x\n"
      smp_get_current_cpu(), t_from->id, t_to->id,
      t_from->team->aspace, t_to->team->aspace,
      t_from->arch_info.current_stack.ss, t_from->arch_info.current_stack.esp,
      t_to->arch_info.current_stack.ss, t_to->arch_info.current_stack.esp);
   #endif

   #if 0
   for (i = 0; i < 11; i++)
   dprintf("*esp[%d] (0x%x) = 0x%x\n", i, ((unsigned int *)new_at->esp + i), *((unsigned int *)new_at->esp + i));
   #endif
  
   весь этот код не линкуется, но может написать много полезной
   информации о состоянии струн на момент переключнения контекста.
  
   i386_set_tss_and_kstack(t_to->kernel_stack_base + KSTACK_SIZE);
   загрузить TSS для текущего процессора, если нужно, и установить указатель на
   ядерный стек струны. TSS (Task State Segment) - это сегмент состояния задачи в IA-32 
   архитектуре.
      а вот, как это делается:
      void i386_set_tss_and_kstack(addr kstack)
      {
         int currentCPU = smp_get_current_cpu();
         получить текущий процессор. мутная функция, посмотрю сразу после этой
         if (!tss_loaded[currentCPU]) {
            если TSS для этого процессора не загружено, то надо бы...
            short seg = ((TSS_BASE_SEGMENT + currentCPU) << 3) | DPL_KERNEL;
            вычисляем где храниться TSS. Формула проста: берем начало сегмента дескрипторов 
            TSS в GDT (константа TSS_BASE_SEGMENT), которое равно 5, прибавляем текущий 
            процессор (0-первый,1-второй и так далее),
            сдвигаем на 3 влево, чтобы освободить место под идентификатор уровня защиты
            и говорим, что это сегмент уровня привилегий 0 (Ring-0). За это отвечает 
            маска DPL_KERNEL, равная, безусловно 0. Например, если текущий процессор - 0-ой, 
            то дескриптор получиться равным 40.
            константы здесь: headers/private/kernel/arch/x86/descriptors.h

            asm("movw %0, %%ax;"
                "ltr %%ax;" : : "r" (seg) : "eax");
            загружаем TSS вычисленным дескриптором.

            tss_loaded[currentCPU] = true;
            флажкуем, что TSS загружен.
         }
         tss[currentCPU]->sp0 = kstack;
         загружаем ядерный стек в TSS.
      }
      
      Как TSS представлен (headers/private/kernel/arch/x86/arch_cpu.h):
      struct tss {
	     uint16 prev_task;
	     uint16 unused0;
	     uint32 sp0;
	     uint32 ss0;
	     uint32 sp1;
	     uint32 ss1;
	     uint32 sp2;
	     uint32 ss2;
	     uint32 sp3;
	     uint32 ss3;
	     uint32 cr3;
	     uint32 eip, eflags, eax, ecx, edx, ebx, esp, ebp, esi, edi;
	     uint32 es, cs, ss, ds, fs, gs;
	     uint32 ldt_seg_selector;
	     uint16 unused1;
	     uint16 io_map_base;
      };

   далее по коду arch_thread_context_switch() :

   // set TLS GDT entry to the current thread - since this action is
   // dependent on the current CPU, we have to do it here
   if (t_to->user_local_storage != NULL)
      set_tls_context(t_to);
   если струна имеет свой собственный контейнер данных (TLS), то установим его дескриптор в GDT.
   Быстро по коду (src/kernel/core/arch/x86/arch_thread.c):
      set_tls_context(struct thread *thread)
      {
	     int entry = smp_get_current_cpu() + TLS_BASE_SEGMENT;
         получить место для TLS дескриптора в GDT. 
         TLS_BASE_SEGMENT равен (TSS_BASE_SEGMENT + smp_get_num_cpus()).
         Вообще-то, принимая во внимание ответственность переключения контекста, необходимо
         избегать лишние вызовы, а smp_get_num_cpus() довольно "громоздкая" функция
         set_segment_descriptor_base(&gGDT[entry], thread->user_local_storage);
         установить базу дескриптора: (headers/private/kernel/arch/x86/descriptors.h):
            static inline void
            set_segment_descriptor_base(struct segment_descriptor *desc, addr base)
            {
               desc->base_00_15 = (addr)base & 0xffff;	// base is 32 bits long
               desc->base_23_16 = ((addr)base >> 16) & 0xff;
               desc->base_31_24 = ((addr)base >> 24) & 0xff;
            }

         set_fs_register((entry << 3) | DPL_USER);
         установить регистр FS (src/kernel/core/arch/x86/arch_thread.c):
            set_fs_register(uint32 segment)
            {
               asm("movl %0,%%fs" :: "r" (segment));
            }
            все понятно и без слов
      }

   дальше по arch_thread_context_switch() :
   if (t_from->team->_aspace_id >= 0 && t_to->team->_aspace_id >= 0) 
   {
      сюда попадаем, если обе струнки работают в процессе пользователя
      if (t_from->team->_aspace_id == t_to->team->_aspace_id) 
      {
         new_pgdir = NULL;
         если струны принадлежат одному процессу, то никаких операций с виртуалкой
         делать не надо, естественно.
      } else 
      {
         // switching to a new address space
         new_pgdir = vm_translation_map_get_pgdir(&t_to->team->aspace->translation_map);
         а это тяжелый случай - необходимо переключиться на виртуальную память новой струны
         Виртуальная память - такая обширная тема, что я не буду углубляться здесь.
      }
   } 
   else 
   if (t_from->team->_aspace_id < 0 && t_to->team->_aspace_id < 0) 
   {
      если обе струны бегают в ядре, то виртуальной памяти дадим отдохнуть
      new_pgdir = NULL;
   } 
   else 
   if (t_to->team->_aspace_id < 0) 
   {
      если струна, куда переключаемся, бегает в ядре
      new_pgdir = vm_translation_map_get_pgdir(&t_to->team->kaspace->translation_map)
      надо переключать виртуалку
   } 
   else 
   {
      new_pgdir = vm_translation_map_get_pgdir(&t_to->team->aspace->translation_map);
      крайний случай, когда новая струна в процессе, а старая в ядре, то тоже
      переключиться стоит
   }
  
   if ((new_pgdir % PAGE_SIZE) != 0)
      panic("arch_thread_context_switch: bad pgdir 0x%lx\n", new_pgdir);
   паникуем, если адрес таблицы виртуалки не выравнен по границе страницы (4 кило, как обычно)

   i386_fsave_swap(t_from->arch_info.fpu_state, t_to->arch_info.fpu_state);
   обменяемся состоянием сопроцессора между струнами (/src/kernel/core/arch/x86/arch_x86.S):
      /* void i386_fsave_swap(void *old_fpu_state, void *new_fpu_state); */
      FUNCTION(i386_fsave_swap):
         movl	4(%esp),%eax
         fsave	(%eax)
         сохранить состояние со-проца в буфер. Забыл сказать, что неявная адресация в 
         AT&T синтаксисе представлена (), а не [], как в Intel.
         movl	8(%esp),%eax
         frstor	(%eax)
         восстановить со-проц, но на этот раз в контексте новой струны
         ret
   

   i386_context_switch(&t_from->arch_info, &t_to->arch_info, new_pgdir);
   ну и самое главное - это произвести переключение !
      Переключатель (/src/kernel/core/arch/x86/arch_x86.S):
      /* void i386_context_switch(struct arch_thread *old_state, struct arch_thread *new_state, addr new_pgdir); */
      FUNCTION(i386_context_switch):
         pusha                  /* pushes 8 words onto the stack */
         запомнили регистры (комментарий не совсем верен, так как это 32битка).
         movl   36(%esp),%eax   /* save old_state->current_stack */
         уложили в eax адрес old_state->current_stack. 
         36 - это 8*4 на регистры, плюс "пища" для ret, так как это __cdecl и old_state 
         будет "ниже" в стеке/"выше" в памяти, если память идет сверху вниз :-)
         current_stack является первым членом структуры, поэтому больше никаких смещений
         movl   %esp,(%eax)
         запихиваем в old_state->current_stack.esp текущий стековый указатель
         pushl  %ss
         popl   %edx
         сохраняем в edx дескриптор стека
         movl   %edx,4(%eax)
         сохраняем дескриптор стека в old_state->current_stack.ss (4 - пропуск current_stack.esp)
         movl   44(%esp),%eax   /* get possible new pgdir */
         это самый настоящий "hack", который я не ожидал увидеть ! 
         В простых словах, здесь тянем переменную из другой функции. Не верю ! Ладно, считаю:
         8*4 на регистры, 4 на возрат, 4+4 на 2 аргумента, получаем 44, а new_pgdir
         лежит на стеке arch_thread_context_switch() в самом начале.
         orl    %eax,%eax       /* is it null? */ 
         je     skip_pgdir_swap
         проверим на NULL и улетим, если не надо менять виртуалку
         movl   %eax,%cr3
         грузим адрес таблицы виртуалки в cr3. cr3 эксклюзивно используется в ядре для 
         хранения виртуалки текущего процесса (понятно, что струны одного процесса "шарят" одну
         виртуалку.
      skip_pgdir_swap:
         movl   40(%esp),%eax   /* get new new_state->current_stack */
         вытянули адрес new_state.
         lss    (%eax),%esp
         загружаем ss:esp значением, куда указывает eax. А указывает он на new_state->current_stack
         popa
         забрали 8 регистров, но уже из стека новой струны. Каждая струна, которая 
         переключается, кладет свои 8 регистров при входе и держит их, пока неактивна.
         когда она становиться активной, то забирает эти 8 регистров здесь.
         Напрашивается резонный вопрос: "А что делать с абсолютно девственной струной, 
         которую еще не "...." (которая еще не содержит эти 8 регистров и прочую ботву на
         стеке и current_stack ?"  За это отвечает хитрый код в arch_thread_init_kthread_stack()
         ret
         ушли в arch_thread_context_switch(), но уже из новой струны. 
   
   выход из arch_thread_context_switch(). 
   после ret этой функции, будет выполнять код новой струны.
}
Возвращаюсь к абстрактному, платформо-независимому коду в scheduler.c:

static int32 reschedule_event(timer *unused)
{
   // this function is called as a result of the timer event set by the scheduler
   // returning this causes a reschedule on the timer event
   thread_get_current_thread()->cpu->info.preempted= 1;
   флажек текущей струне, что процессор отобрали для другой струны
   return B_INVOKE_SCHEDULER;
   приказываем обработчику таймера, что квант струны истек и
   надобно вызвать scheduler_reschedule() для переключения на другую струну.
   обработчик проверит, что мы возвратили приказ и вызовет scheduler_reschedule.
}
Функция reschedule_event() является callback обработчиком для таймера, который создается в
scheduler_reschedule() и вызывается после истечения кванта, выделяемого струне.  
Здесь невозможно вызывать scheduler_reschedule(), так как код в контексте прерывания. 

Мы подошли к самой главной функции Scheduler-а, а именно той, которая и распределяет
кванты времени разным струнам.

/** Runs the scheduler.
  * NOTE: expects thread_spinlock to be held
  Напоминание, что неплохо бы было защититься каким нибудь локом
*/
void scheduler_reschedule(void)
{
  struct thread *oldThread = thread_get_current_thread();
  запомним текущую активную струну (та, которая на данный момент выполняется)
  struct thread *nextThread, *prevThread;

  TRACE(("reschedule(): cpu %d, 
         cur_thread = 0x%x\n", smp_get_current_cpu(), thread_get_current_thread()));
  захламим debug консоль немного, чтобы видеть, что не зависли.

  а теперь проверим будущий статус активной струны и на его основе решим, что
  с ней делать
  switch (oldThread->next_state) 
  {
     case B_THREAD_RUNNING:
        струна желает бежать (обчно, когда была только создана или блокирована)
     case B_THREAD_READY:
        струна выполнила свой квант и ее надо возвратить назад в очередь
        TRACE(("enqueueing thread 0x%x into run q. pri = %d\n", oldThread, 
              oldThread->priority));
        scheduler_enqueue_in_run_queue(oldThread);
        добавляем струну в то место в очереди, куда указывает ее приоритет
        break;

     case B_THREAD_SUSPENDED:
        струна хочет чтобы ее блокировали (подвесили)
        TRACE(("reschedule(): suspending thread 0x%lx\n", oldThread->id));
        break;

     case THREAD_STATE_FREE_ON_RESCHED:
        струна жаждет умереть
        // This will hopefully be eliminated once the slab
        // allocator is done
        как говорит комментарий, в будущем это будет лишним кодом, если 
        дойдут руки до написания KA (Kernel Memory Allocator), что есть
        аналог malloc/free но для ядра.  
        OpenBeOS хочет использовать slab-allocator,
        что есть очень разумный шаг, так как это один из самый оптимальных алгоритмов.
        thread_enqueue(oldThread, &dead_q);
        поместить струну в очередь кешированных мертвых струн.
        break;

     default:
        по умолчанию ничего не делать
        TRACE(("not enqueueing thread 0x%x into run q. next_state = %d\n", 
              old_thread, old_thread->next_state));
        break;
  }

  oldThread->state = oldThread->next_state;
  будущее статус струны становиться настоящим, что логично, так как его уже обработали

  // select next thread from the run queue
  nextThread = gRunQueue.head;
  выбираем следующую струну, которую запустить на процессоре. Так как струны отсортированы
  в очереди по приоритетам, то голова очереди как раз держит следующую струну
  prevThread = NULL;
  предыдущей нет

  так струны с разными приоритетами лежат большой кучей в одном списке и мы не знаем
  границы приоритетов, то прийдется немного побегать по очереди
  while (nextThread && (nextThread->priority > B_IDLE_PRIORITY)) 
  {
     а бежим до тех пор пока есть струны и они все хотят работать, а не отдыхать (B_IDLE_PRIORITY)
     // always extract real time threads
     if (nextThread->priority >= B_FIRST_REAL_TIME_PRIORITY)
        break;
     если мы натолкнулись на струну с приоритетом реального времени, то ей и дадим квант.
     Scheduler очень любит такие струны и будет их гонять пока они не скажут сами - хватит

     // never skip last non-idle normal thread
     if(nextThread->queue_next 
        && (nextThread->queue_next->priority == B_IDLE_PRIORITY))
        break;
     это простая проверка на дурака: если мы знаем, что наша струна хочет выполнять, а следующая
     струна окажется B_IDLE_PRIORITY, то и все остальные до конца очереди будут также
     "струны-разгильдяи" и мы упустим шанс запустить ту струну, что хочет работать. 
     Поэтому и проверяем

     // skip normal threads sometimes
     if (_rand() > 0x3000) break;
     это просто чудесный код из серии "лотерейный билет". Как говориться, иногда струне,
     которая хочет работать, мы квант не дадим и побежим дальше.

     prevThread = nextThread;
     nextThread = nextThread->queue_next;
     невезучая струна, может следующей повезет...
  }
  
  if (!nextThread)
     panic("reschedule(): run queue is empty!\n");
  вот этого ядро никак не ожидало: ни одну струну не нашли для запуска ! В реальной жизни
  такого естественно не бывает, так как кто-то всегда выполняется и все струны не могут
  быть в B_IDLE_PRIORITY приоритете. Для многих ядер (Linux, NetBSD,...), функция panic() 
  является катапультирующим механизмом, паникой. Она вызывается в случаях, когда серьезная
  внутренняя ошибка в ядре не позволяет безопасно продолжать работу, а самый лучший метод
  в таких случаях - сразу же уйти в корку (в обычных приложениях) или запаниковать в ядре.
  panic() также умеет создавать корку (core файл) содержащий адресное пространство ядра,
  текущий стек и регистры. 

  // extract selected thread from the run queue
  if (prevThread)
     prevThread->queue_next = nextThread->queue_next;
  else
     gRunQueue.head = nextThread->queue_next;
  удалить готовую струну из очереди

  nextThread->state = B_THREAD_RUNNING;
  nextThread->next_state = B_THREAD_READY;
  готовая струна становиться выполняемой - B_THREAD_RUNNING, а ее будущий статус по умолчанию
  естественно - B_THREAD_READY, т.е. выполнила квант и должна быть возвращена в очередь.

  if (nextThread != oldThread || oldThread->cpu->info.preempted) 
  {
     если готовая струна является не старой активной, или кто-то затребовал
     переключиться на новую струну, то надо это сделать прямо здесь

     bigtime_t quantum = 3000; // ToDo: calculate quantum!
     фиксированный квант, равный 3000 тикам таймера. 
     Тип кванта: bigtime_t (headers/os/support/SupportDefs.h), 
     который также является типом, возвращаемым
     ассемблерной функций system_time(), но там тики процессора, которые обновляются каждый
     раз при тактовом импульсе процессора (rdtsc инструкция). Сначало это меня сбило с
     толку, но потом быстрый просмотр add_timer показал, что sys_time() прибавляется и
     вычитается одновременно. 
     timer *quantum_timer= &oldThread->cpu->info.quantum_timer;
     адрес понадобиться в следующей строке

     if (!oldThread->cpu->info.preempted)
        _local_timer_cancel_event(oldThread->cpu->info.cpu_num, quantum_timer);
     вызов _local_timer_cancel_event (синтакс: headers/private/kernel/timer.h)
     
     если старая активная струна нормально отработала и ее не хотели прерывать, то
     отменяем. 
     oldThread->cpu->info.preempted = 0;
     стираем флажок требования передать квант для старой струны.
     add_timer(quantum_timer, &reschedule_event, quantum, B_ONE_SHOT_RELATIVE_TIMER);
     создаем таймер, который вызовет callback с имеем reschedule_event. Таймер принимает
     значение времени, как относительное количество тиков от текущего значение 
     (аттрибут B_ONE_SHOT_RELATIVE_TIMER), и вызовет callback через quantum число тиков.

     if (nextThread != oldThread)
        context_switch(oldThread, nextThread);
     если мы передаем управление новой струне, то переключаем контекст. При выходе из этой
     функции, новая струна уже побежала. context_switch() была рассмотрена до этого.
  }
}

/** This starts the scheduler. Must be run under the context of
 * the initial idle thread.
*/
Функция вызывается для инициализации Scheduler-а из main() в src/kernel/core/main.c.

void start_scheduler(void)
{
   int state;
   используется для запрещения/разрешения прерываний (запомнить и восстановить) 
   // XXX may not be the best place for this
   // invalidate all of the other processors' TLB caches
   state = disable_interrupts();
   запретить прерывания
   arch_cpu_global_TLB_invalidate();
   сбросить TLB кеш для процессоров. TLB (Translation Lookaside Buffer) - это аппаратный
   кеш преобразования виртуальных адресов в физические. Так как большинство современных
   ОС работают с виртульным адресным пространством, то помощь на уровне электроники - 
   как нельзя кстати. 
   smp_send_broadcast_ici(SMP_MSG_GLOBAL_INVL_PAGE, 0, 0, 0, NULL, SMP_MSG_FLAG_SYNC);
   послать сигнал всем процессорам о том, что кеш был сброшен.
   restore_interrupts(state);
   восстановаить прерывания

   // start the other processors
   smp_send_broadcast_ici(SMP_MSG_RESCHEDULE, 0, 0, 0, NULL, SMP_MSG_FLAG_ASYNC);
   послать сигнал всем процессорам, что ..., не знаю, надо смотреть функцию

   state = disable_interrupts();
   запретить прерывания
   GRAB_THREAD_LOCK();
   глобальный лок. Этот мютекс - глобальный для всего ядра, поэтому должен использоваться
   как можно реже и код должен выполняться как можно быстрее в критической секции.
   Так как в главной функции Scheduler-а нет лока, то здесь он кстати. 
   scheduler_reschedule();
   самый первый квант
   RELEASE_THREAD_LOCK();
   освободить лок
   restore_interrupts(state);
   восстановить прерывания

   add_debugger_command("run_queue",&dump_run_queue, "list threads in run queue");
   добавить команду в собственный внутриядерный дебаггер для просмотра очереди струн.
}


Вроде все ясно, кроме еще одного главного шага, который не прослежен - прерывание таймера и что там 
с ним делается. Код ответственный за таймер немаленький и заслуживает пристального 
"разбирательства", но я вроде уже превзошел себя в объеме бреда для одного прочтения, поэтому,
полное рассмотрение таймера - в другой раз, а сейчас только бегло по нему. 
Таймер выстреливает событие reschedule_event(). Код add_timer() из /src/kernel/core/timer.c 
добавляет callback в список таймеров. timer_interrupt() - функция, которая собственно
ответственна за проверку кто в списке callback-ов должен быть вызван. Сама  timer_interrupt()
вызывается или из isa_timer_interrupt() или из apic_timer_interrupt(), в зависимости от
того, поддерживаем SMP или нет. Если симметричная многопроцессорка поддерживается, то APIC
таймер будет прыгать, иначе старая, добрая ISA. Последовательность arch_init_timer()+
install_io_interrupt_handler() + install_interrupt_handler() устанавливает timer_interrupt
в цепочку обработчиков io_vectors[]. Цепочка обрабатывается и выстреливается из
int_io_interrupt_handler(), ну и наконец, сам int_io_interrupt_handler() опускается до
архитектурного уровня в i386_handle_trap(). i386_handle_trap() - это сердце обработчика
аппаратных прерываний:

void
i386_handle_trap(struct iframe frame)
{
   int ret = B_HANDLED_INTERRUPT;
   флажек, что прерывание обработано
   struct thread *thread = thread_get_current_thread();
   текущая струна, которая прервана  

   if (thread) {
      i386_push_iframe(thread, &frame);
      thread->arch_info.current_iframe = &frame;
      "наслоить" прерывание в цепочку (было рассмотрено до этого)
   }

   проверим, а кто создал прерывание:
   switch (frame.vector) {
     case 8: 
        двойной фолт по памяти
        ret = i386_double_fault(frame.error_code);
        <код пропущен> 
        break;
     case 13: 
        GPF (General Protection Fault) - доступ к запрещенной странице
        <код пропущен>
        break;
     case 14: 
     {
        стандарный фолт на отсутствующую виртуалку
        <код пропущен>
        break;
     }
     case 99:	
	 {
        системный вызов из кода процесса в ядро. Трэвис выбрал вектор 99. Красиво !...
        <код пропущен>
        break;
     }
     default:
        обработчик всех остальных прерываний, куда входит и таймер:
        if (frame.vector >= 0x20) {
           interrupt_ack(frame.vector); // ack the 8239 (if applicable)
           подтверждение PIC (Priority Interrupt Controller)
           ret = int_io_interrupt_handler(frame.vector);
           обработать прерывание. В моем случае reschedule_event() будет вызван, если
           квант истек. Функция выставит код возврата B_INVOKE_SCHEDULER
        } else {
           panic("i386_handle_trap: unhandled cpu trap 0x%x at ip 0x%x!\n", frame.vector, 
                 frame.eip);
           паникуем, так как этими прерываниями не занимаемся
           ret = B_HANDLED_INTERRUPT;
        }
        break;
   }
  
   if (ret == B_INVOKE_SCHEDULER) {
      если reschedule_event() был вызван, то попадаю сюда, как приказ переключить струнки.
      int state = disable_interrupts();
      всем прерываниям отбой, так как таймер - самый главный
      GRAB_THREAD_LOCK();
      всем операциям по струнам также отбой
      scheduler_reschedule();
      квантуем...
      RELEASE_THREAD_LOCK();
      разблокировать струны
      restore_interrupts(state);
      запустить прерывания
   }

   if (frame.cs == USER_CODE_SEG || frame.vector == 99)
      thread_atkernel_exit();
   если выполнялись в коде процесса и был системный вызов, то выйти из ядра.
   
   if (thread)
      i386_pop_iframe(thread);
   восстановить фрейм, если перехватили струну
}

Установка таймера производиться в set_isa_hardware_timer() или в arch_smp_set_apic_timer().
Для Исы, контроллер программируется стандартно:

#define pit_clock_rate 1193180 
максимальная частота Intel8253 контроллера
#define pit_max_timer_interval ((long long)0xffff * 1000000 / pit_clock_rate)
static void set_isa_hardware_timer(long long relative_timeout)
{
   unsigned short next_event_clocks;
   if (relative_timeout <= 0)
      next_event_clocks = 2;
   else if (relative_timeout < pit_max_timer_interval)
      next_event_clocks = relative_timeout * pit_clock_rate / 1000000;
      вычисляем, когда сигналить контроллеру: 3000*1193180/1000000 = 3579
      получается около 333 герц, или раз в 3 миллисекунды. 
      BeOS была (и еще есть) знаменитой своей real-time "отзывчивостью", и вроде там квант
      был 3мс (подтвержденная латентность - 4.5мс). 
      Для сравнения, небольшая неполная таблица (точность и правдивость не гарантирую, 
      латентность измерялась на одной машине естественно):

   назад к коду:   
      
   else
      next_event_clocks = 0xffff;

   out8(0x30, 0x43);
   out8(next_event_clocks & 0xff, 0x40);
   out8((next_event_clocks >> 8) & 0xff, 0x40);
   стандартная инициализация контроллера (как написано в инструкции Intel)
}


Один момент, который погряз в тумане, а именно, что происходит со струной, 
которая была создана и еще не получала кванта. Ведь тогда у нее не будет правильного стека
и при переключении контекста с другой струны, однозначно подвесим ядро ?.
Ответ кроется в файле kernel/core/arch/x86/arch_thread.c:

arch_thread_init_kthread_stack(struct thread *t, int (*start_func)(void), 
                               void (*entry_func)(void), void (*exit_func)(void))
{
   unsigned int *kstack = (unsigned int *)t->kernel_stack_base;
   указатель на начала стека ядра струны (почему он unsigned int* - для меня тоже загадка)
   unsigned int kstack_size = KSTACK_SIZE;
   размер стека (#define KSTACK_SIZE   (PAGE_SIZE * 2)), что равно 8 кило.
   unsigned int *kstack_top = kstack + kstack_size / sizeof(unsigned int);
   конец стека по тривиальной формуле. Не забываем, что С "умничает" с типизированными указателями
   int i;

   // dprintf("arch_thread_initialize_kthread_stack: kstack 0x%p, start_func 0x%p, entry_func 0x%p\n",
   // kstack, start_func, entry_func);
   
   // clear the kernel stack
   memset(kstack, 0, kstack_size);
   очистим стек от грязи, чтобы в случае чего подхватить SIGBUS или SIGSEGV

   // set the final return address to be thread_kthread_exit
   kstack_top--;
   *kstack_top = (unsigned int)exit_func;
   кладем в самое начало стека адрес функции, завершающей струну - exit_func
   это thread_kthread_exit из core/thread.c.
   kstack_top-- это эмуляция "push".

   // set the return address to be the start of the first function
   kstack_top--;
   *kstack_top = (unsigned int)start_func;
   следующим в стеке будет лежать функция, которая запускает струну. В большинстве случаев, это
   будет _create_kernel_thread_kentry из core/thread.c.

   // set the return address to be the start of the entry (thread setup) function
   kstack_top--;
   *kstack_top = (unsigned int)entry_func;
   следующей в стеке будет функция входа. 
   В большинстве случаев, это будет thread_kthread_entry из core/thread.c. 

   // simulate pushfl
   // kstack_top--;
   // *kstack_top = 0x00; // interrupts still disabled after the switch
   это эмуляция pushfl. 0 лежит там, тоесть все флажки в 0 и прерывания выключены.
   включит прерывания функция thread_kthread_entry

   // simulate initial popad
   for (i = 0; i < 8; i++) {
      kstack_top--;
      *kstack_top = 0;
   }
   эмуляция 8 регистров в стеке. Как помним, переключатель контекста будет ожидать 
   в своем стеке 8 обычных регистров и адрес возврата в свой код. "Регистры" вот
   положили, а возрат аккуратно зашвырнет в код entry_func. Просто и элегантно.

   // save the stack position
   t->arch_info.current_stack.esp = kstack_top;
   t->arch_info.current_stack.ss = (int *)KERNEL_DATA_SEG;
   а все эта информация о стеке, которую берет переключатель контекста,
   лежит той паре ss:esp в аппаратно-зависимой части структуры струны. 
   KERNEL_DATA_SEG селектор, кстати равен 0х10.

   return 0;
}
3. Послесловие.

Все, что здесь рассмотрено - это даже не верхушка айсберга, а один сугроб на верхушке. И вдобавок, это один из самых простых и примитивных квантовщиков на данный момент. Нет динамического расчета приоритетов, оптимизации по масштабируемости от количества струн (один процесс, создавший 1000 струн положит ядро на лопатки), и т.п.

Что говорить тогда о FreeBSD с ее KSE (Kernel Scheduling Entities) или NetBSD с поддержкой Upcall и Scheduler Activation. Или о том же linux с его уже 3 разными квантовщиками. А один из самых "продвинутых" Scheduler-ов в Solaris ? Там без пол-литра точно не разберешься.

4. Полезные и бесполезные ссылки.

	(с) 2003, andreyk Оригинал размещен на http://aka.com.ua Плагиат без разрешения автора не поощряется.