Мультизадачный режим работы операционных систем

Организация многозадачности в ядре ОС

Волею судеб мне довелось разбираться с организацией многозадачности, точнее псевдо-многозадачности, поскольку задачи делят время на одном ядре процессора. Я уже несколько раз встречала на хабре статьи по данной теме, и мне показалось, что данная тема сообществу интересна, поэтому я позволю себе внести свою скромную лепту в освещение данного вопроса.
Сначала я попытаюсь рассказать о типах многозадачности (кооперативной и вытесняющей). Затем перейду к принципам планирования для вытесняющей многозадачности. Рассказ рассчитан скорее на начинающего читателя, который хочет разобраться, как работает многозадачность на уровне ядра ОС. Но поскольку все будет сопровождаться примерами, которые можно скомпилировать, запустить, и с которыми при желании можно поиграться, то, возможно, статья заинтересует и тех, кто уже знаком с теорией, но никогда не пробовал планировщик “на вкус”. Кому лень читать, может сразу перейти к изучению кода, поскольку код примеров будет взят из нашего проекта.
Ну, и многопоточные котики для привлечения внимания.

Введение

Сперва определимся, что означает термин “многозадачность”. Вот определение из русской Википедии:

Многозада́чность (англ. multitasking) — свойство операционной системы или среды программирования обеспечивать возможность параллельной (или псевдопараллельной) обработки нескольких процессов.

Английская дает, на мой взгляд, менее понятное, но более развернутое определение:

In computing, multitasking is a method where multiple tasks, also known as processes, are performed during the same period of time. The tasks share common processing resources, such as a CPU and main memory. In the case of a computer with a single CPU, only one task is said to be running at any point in time, meaning that the CPU is actively executing instructions for that task. Multitasking solves the problem by scheduling which task may be the one running at any given time, and when another waiting task gets a turn. The act of reassigning a CPU from one task to another one is called a context switch.

В нем вводится понятие разделение ресурсов (resources sharing) и, собственно, планирование (scheduling). Именно о планировании (в первую очередь, процессорного времени) и пойдет речь в данной статье. В обоих определениях речь идет о планировании процессов, но я буду рассказывать о планировании на основе потоков.

Таким образом, нам необходимо ввести еще одно понятие, назовем его поток исполнения — это набор инструкций с определенным порядком следования, которые выполняет процессор во время работы программы.
Поскольку речь идет о многозадачности, то естественно в системе может быть несколько этих самых вычислительных потоков. Поток, инструкции которого процессор выполняет в данный момент времени, называется активным. Поскольку на одном процессорном ядре может в один момент времени выполняться только одна инструкция, то активным может быть только один вычислительный поток. Процесс выбора активного вычислительного потока называется планированием (scheduling). В свою очередь, модуль, который отвечает за данный выбор принято называть планировщиком (scheduler).

Существует много различных методов планирования. Большинство из них можно отнести к двум основным типам:

• невытесняющие (кооперативные) — планировщик не может забрать время у вычислительного потока, пока тот сам его не отдаст
• вытесняющие — планировщик по истечении кванта времени выбирает следующий активный вычислительный поток, сам вычислительный поток также может отдать предназначенный для него остаток кванта времени

Давайте начнем разбираться с невытесняющего метода планирования, так как его очень просто можно реализовать.

Невытесняющий планировщик

Рассматриваемый невытесняющий планировщик очень простой, данный материал дан для начинающих, чтобы было проще разобраться в многозадачности. Тот, кто имеет представление, хотя бы теоретическое, может сразу перейти к разделу “Вытесняющий планировщик”.

Простейший невытесняющий планировщик

Представим, что у нас есть несколько задач, достаточно коротких по времени, и мы можем их вызывать поочередно. Задачу оформим как обычную функцию с некоторым набором параметров. Планировщик будет оперировать массивом структур на эти функции. Он будет проходиться по этому массиву и вызывать функции-задачи с заданными параметрами. Функция, выполнив необходимые действия для задачи, вернет управление в основной цикл планировщика.

#include <stdio.h>

#define TASK_COUNT 2

struct task {
   void (*func)(void *);
   void *data;
};

static struct task tasks[TASK_COUNT];

static void scheduler(void) {
   int i;
   for (i = 0; i < TASK_COUNT; i++) {
   	tasks[i].func(tasks[i].data);
   }
}

static void worker(void *data) {
   printf("%sn", (char *) data);
}

static struct task *task_create(void (*func)(void *), void *data) {
   static int i = 0;

   tasks[i].func = func;
   tasks[i].data = data;


   return &tasks[i++];
}


int main(void) {
   task_create(&worker, "First");
   task_create(&worker, "Second");

   scheduler();

   return 0;
}

Результаты вывода:

First
Second

График занятости процессора:

Невытесняющий планировщик на основе событий

Понятно, что описанный выше пример слишком уж примитивен. Давайте введем еще возможность активировать определенную задачу. Для этого в структуру описания задачи нужно добавить флаг, указывающий на то, активна задача или нет. Конечно, еще понадобится небольшое API для управления активизацией.

#include <stdio.h>

#define TASK_COUNT 2

struct task {
	void (*func)(void *);
	void *data;
	int activated;
};

static struct task tasks[TASK_COUNT];

struct task_data {
	char *str;
	struct task *next_task;
};

static struct task *task_create(void (*func)(void *), void *data) {
	static int i = 0;

	tasks[i].func = func;
	tasks[i].data = data;

	return &tasks[i++];
}

static int task_activate(struct task *task, void *data) {
	task->data = data;
	task->activated = 1;

	return 0;
}

static int task_run(struct task *task, void *data) {
	task->activated = 0;
	task->func(data);

	return 0;
}

static void scheduler(void) {
	int i;
	int fl = 1;

	while (fl) {
    	fl = 0;

    	for (i = 0; i < TASK_COUNT; i++) {
        	if (tasks[i].activated) {
            	fl = 1;
            	task_run(&tasks[i], tasks[i].data);
        	}
    	}
	}
}


static void worker1(void *data) {
	printf("%sn", (char *) data);
}

static void worker2(void *data) {
	struct task_data *task_data;

	task_data = data;

	printf("%sn", task_data->str);

	task_activate(task_data->next_task, "First activated");
}

int main(void) {
	struct task *t1, *t2;
	struct task_data task_data;

	t1 = task_create(&worker1, "First create");
	t2 = task_create(&worker2, "Second create");

	task_data.next_task = t1;
	task_data.str = "Second activated";

	task_activate(t2, &task_data);

	scheduler();

	return 0;
}

Результаты вывода:

Second activated
First activated

График занятости процессора

Невытесняющий планировщик на основе очереди сообщений

Проблемы предыдущего метода очевидны: если кто-то захочет два раза активировать некую задачу, пока задача не обработана, то у него это не получится. Информация о второй активации просто потеряется. Эту проблему можно частично решить с помощью очереди сообщений. Добавим вместо флажков массив, в котором хранятся очереди сообщений для каждого потока.

#include <stdio.h>
#include <stdlib.h>

#define TASK_COUNT 2

struct message {
	void *data;
	struct message *next;
};

struct task {
	void (*func)(void *);
	struct message *first;
};

struct task_data {
	char *str;
	struct task *next_task;
};

static struct task tasks[TASK_COUNT];


static struct task *task_create(void (*func)(void *), void *data) {
   static int i = 0;

   tasks[i].func = func;
   tasks[i].first = NULL;

   return &tasks[i++];
}

static int task_activate(struct task *task, void *data) {
	struct message *msg;

	msg = malloc(sizeof(struct message));
	msg->data = data;
	msg->next = task->first;

	task->first = msg;

	return 0;
}

static int task_run(struct task *task, void *data) {
   struct message *msg = data;

   task->first = msg->next;

	task->func(msg->data);

	free(data);

   return 0;
}

static void scheduler(void) {
   int i;
   int fl = 1;
	struct message *msg;

	while (fl) {
   	fl = 0;

   	for (i = 0; i < TASK_COUNT; i++) {
       	while (tasks[i].first) {
           	fl = 1;
           	msg = tasks[i].first;
           	task_run(&tasks[i], msg);
       	}
   	}
	}
}


static void worker1(void *data) {
   printf("%sn", (char *) data);
}

static void worker2(void *data) {
   struct task_data *task_data;

   task_data = data;

   printf("%sn", task_data->str);

   task_activate(task_data->next_task, "Message 1 to first");
   task_activate(task_data->next_task, "Message 2 to first");
}

int main(void) {
   struct task *t1, *t2;
   struct task_data task_data;

   t1 = task_create(&worker1, "First create");
   t2 = task_create(&worker2, "Second create");

   task_data.next_task = t1;
   task_data.str = "Second activated";

   task_activate(t2, &task_data);

   scheduler();

   return 0;
}

Результаты работы:

Second activated
Message 2 to first
Message 1 to first

График занятости процессора

Невытесняющий планировщик с сохранением порядка вызовов

Еще одна проблема у предыдущих примеров в том, что не сохраняется порядок активизации задач. По сути дела, каждой задачи присвоен свой приоритет, это не всегда хорошо. Для решения этой проблемы можно создать одну очередь сообщений и диспетчер, который будет ее разбирать.

#include <stdio.h>
#include <stdlib.h>

#define TASK_COUNT 2

struct task {
	void (*func)(void *);
	void *data;
	struct task *next;
};

static struct task *first = NULL, *last = NULL;

static struct task *task_create(void (*func)(void *), void *data) {
	struct task *task;

	task = malloc(sizeof(struct task));
	task->func = func;
	task->data = data;
	task->next = NULL;

	if (last) {
   	last->next = task;
	} else {
   	first = task;
	}

	last = task;

	return task;
}

static int task_run(struct task *task, void *data) {

	task->func(data);

	free(task);

   return 0;
}

static struct task *task_get_next(void) {
	struct task *task = first;

	if (!first) {
    	return task;
	}

	first = first->next;
	if (first == NULL) {
   	last = NULL;
	}

	return task;
}

static void scheduler(void) {
	struct task *task;

	while ((task = task_get_next())) {
   	task_run(task, task->data);
	}
}

static void worker2(void *data) {
	printf("%sn", (char *) data);
}

static void worker1(void *data) {
	printf("%sn", (char *) data);

	task_create(worker2, "Second create");
	task_create(worker2, "Second create again");
}


int main(void) {
   struct task *t1;

   t1 = task_create(&worker1, "First create");

   scheduler();

   return 0;
}

Результаты работы:

First create
Second create
Second create again

График занятости процессора

Прежде чем перейти к вытесняющему планировщику, хочу добавить, что невытесняющий планировщик используется в реальных системах, поскольку затраты на переключение задач минимальные. Правда этот подход требует большого внимания со стороны программиста, он должен самостоятельно следить за тем, чтобы задачи не зациклились во время исполнения.

Вытесняющий планировщик

Теперь давайте представим следующую картину. У нас есть два вычислительных потока, выполняющих одну и ту же программу, и есть планировщик, который в произвольный момент времени перед выполнением любой инструкции может прервать активный поток и активировать другой. Для управления подобными задачами уже недостаточно информации только о функции вызова потока и ее параметрах, как в случае с невытесняющими планировщиками. Как минимум, еще нужно знать адрес текущей выполняемой инструкции и набор локальных переменных для каждой задачи. То есть для каждой задачи нужно хранить копии соответствующих переменных, а так как локальные переменные для потоков располагаются на его стеке, то должно быть выделено пространство под стек каждого потока, и где-то должен храниться указатель на текущее положение стека.

Эти данные — instruction pointer и stack pointer — хранятся в регистрах процессора. Кроме них для корректной работы необходима и другая информация, содержащаяся в регистрах: флаги состояния, различные регистры общего назначения, в которых содержатся временные переменные, и так далее. Все это называется контекстом процессора.

Контекст процессора

Контекст процессора (CPU context) — это структура данных, которая хранит внутреннее состояние регистров процессора. Контекст должен позволять привести процессор в корректное состояние для выполнения вычислительного потока. Процесс замены одного вычислительного потока другим принято называть переключением контекста (context switch).

Описание структуры контекста для архитектуры x86 из нашего проекта:

struct context {
	/* 0x00 */uint32_t eip; /**< instruction pointer */
	/* 0x04 */uint32_t ebx; /**< base register */
	/* 0x08 */uint32_t edi; /**< Destination index register */
	/* 0x0c */uint32_t esi; /**< Source index register */
	/* 0x10 */uint32_t ebp; /**< Stack pointer register */
	/* 0x14 */uint32_t esp; /**< Stack Base pointer register */
	/* 0x18 */uint32_t eflags; /**< EFLAGS register hold the state of the processor */
};

Понятия контекста процессора и переключения контекста — основополагающие в понимании принципа вытесняющего планирования.

Переключение контекста

Переключение контекста — замена контекста одного потока другим. Планировщик сохраняет текущий контекст и загружает в регистры процессора другой.
Выше я говорила, что планировщик может прервать активный поток в любой момент времени, что несколько упрощает модель. На самом же деле не планировщик прерывает поток, а текущая программа прерывается процессором в результате реакции на внешнее событие — аппаратное прерывание — и передает управление планировщику. Например, внешним событием является системный таймер, который отсчитывает квант времени, выделенный для работы активного потока. Если считать, что в системе существует ровно один источник прерывания, системный таймер, то карта процессорного времени будет выглядеть следующим образом:

Процедура переключения контекста для архитектуры x86:

	.global context_switch
context_switch:
	movl 0x04(%esp), %ecx      	/* Point ecx to previous registers */
	movl (%esp), %eax          	/* Get return address */
	movl %eax, CTX_X86_EIP(%ecx)   /* Save it as eip */
	movl %ebx, CTX_X86_EBX(%ecx)   /* Save ebx */
	movl %edi, CTX_X86_EDI(%ecx)   /* Save edi */
	movl %esi, CTX_X86_ESI(%ecx)   /* Save esi */
	movl %ebp, CTX_X86_EBP(%ecx)   /* Save ebp */
	add $4, %esp               	/* Move esp in state corresponding to eip */
	movl %esp, CTX_X86_ESP(%ecx)   /* Save esp */
	pushf                      	/* Push flags */
	pop  CTX_X86_EFLAGS(%ecx)  	/* ...and save them */

	movl 0x04(%esp), %ecx      	/* Point ecx to next registers */
	movl CTX_X86_EBX(%ecx), %ebx   /* Restore ebx */
	movl CTX_X86_EDI(%ecx), %edi   /* Restore edi */
	movl CTX_X86_ESP(%ecx), %esi   /* Restore esp */
	movl CTX_X86_EBP(%ecx), %ebp   /* Restore ebp */
	movl CTX_X86_ESP(%ecx), %esp   /* Restore esp */
	push CTX_X86_EFLAGS(%ecx)  	/* Push saved flags */
	popf                       	/* Restore flags */
	movl CTX_X86_EIP(%ecx), %eax   /* Get eip */
	push %eax                  	/* Restore it as return address */

	ret

Машина состояний потока

Мы обсудили важное отличие структуры потока в случае с вытесняющим планировщиком от случая с невытесняющим планировщиком — наличие контекста. Посмотрим, что происходит с потоком с момента его создания до завершения:

• Состояния init отвечает за то, что поток создан, но не добавлялся еще в очередь к планировщику, а exit говорит о том, что поток завершил свое исполнение, но еще не освободил выделенную ему память.
• Состояние run тоже должно быть очевидно — поток в таком состоянии исполняется на процессоре.
• Состояние ready же говорит о том, что поток не исполняется, но ждет, когда планировщик предоставит ему время, то есть находится в очереди планировщика.

Но этим не исчерпываются возможные состояния потока. Поток может отдать квант времени в ожидании какого-либо события, например, просто заснуть на некоторое время и по истечении этого времени продолжить выполнение с того места, где он заснул (например, обычный вызов sleep).
Таким образом, поток может находиться в разных состояниях (готов к выполнению, завершается, находиться в режиме ожидания и так далее), тогда как в случае с невытесняющим планировщиком достаточно было иметь флаг об активности той или иной задачи.

Вот так можно представить обобщенную машину состояний:

В этой схеме появилось новое состояние wait, которое говорит планировщику о том, что поток уснул, и пока он не проснется, процессорное время ему выделять не нужно.
Теперь рассмотрим поподробнее API управления потоком, а также углубим свои знания о состояниях потока.

Реализация состояний

Если посмотреть на схему состояний внимательнее, то можно увидеть, что состояния init и wait почти не отличаются: оба могут перейти только в состояние ready, то есть сказать планировщику, что они готовы получить свой квант времени. Таким образом состояние init избыточное.

Теперь посмотрим на состояние exit. У этого состояния есть свои тонкости. Оно выставляется планировщику в завершающей функции, о ней речь пойдет ниже. Завершение потока может проходить по двум сценариям: первый — поток завершает свою основную функцию и освобождает занятые им ресурсы, второй — другой поток берет на себя ответственность по освобождению ресурсов. Во втором случае поток видит, что другой поток освободит его ресурсы, сообщает ему о том, что завершился, и передает управление планировщику. В первом случае поток освобождает ресурсы и также передает управление планировщику. После того, как планировщик получил управление, поток никогда не должен возобновить работу. То есть в обоих случаях состояние exit имеет одно и то же значение — поток в этом состоянии не хочет получить новый квант времени, его не нужно помещать в очередь планировщика. Идейно это также ничем не отличается от состояния wait, так что можно не заводить отдельное состояние.

Таким образом, у нас остается три состояния. Мы будем хранить эти состояния в трех отдельных полях. Можно было бы хранить все в одном целочисленном поле, но для упрощения проверок и в силу особенности многопроцессорного случая, который здесь мы обсуждать не будем, было принято такое решение. Итак, состояния потока:

• active — запущен и исполняется на процессоре
• waiting — ожидает какого-то события. Кроме того заменяет собой состояния init и exit
• ready — находится под управлением планировщика, т.е. лежит в очереди готовых потоков в планировщике или запущен на процессоре. Это состояние несколько шире того ready, что мы видим на картинке. В большинстве случаев active и ready, а ready и waiting теоретически ортогональны, но есть специфичные переходные состояния, где эти правила нарушаются. Про эти случаи я расскажу ниже.

Создание

Создание потока включает в себя необходимую инициализацию (функция thread_init) и возможный запуск потока. При инициализации выделяется память для стека, задается контекст процессора, выставляются нужные флаги и прочие начальные значения. Поскольку при создании мы работаем с очередью готовых потоков, которую использует планировщик в произвольное время, мы должны заблокировать работу планировщика со структурой потока, пока вся структура не будет инициализирована полностью. После инициализации поток оказывается в состоянии waiting, которое, как мы помним, в том числе отвечает и за начальное состояние. После этого, в зависимости от переданных параметров, либо запускаем поток, либо нет. Функция запуска потока — это функция запуска/пробуждения в планировщике, она подробно описана ниже. Сейчас же скажем только, что эта функция помещает поток в очередь планировщика и меняет состояние waiting на ready.
Итак, код функции thread_create и thread_init:

struct thread *thread_create(unsigned int flags, void *(*run)(void *), void *arg) {
	int ret;
	struct thread *t;

//…

	/* below we are going work with thread instances and therefore we need to
 	* lock the scheduler (disable scheduling) to prevent the structure being
 	* corrupted
 	*/
	sched_lock();
	{
    	/* allocate memory */
    	if (!(t = thread_alloc())) {
        	t = err_ptr(ENOMEM);
        	goto out;
    	}

    	/* initialize internal thread structure */
    	thread_init(t, flags, run, arg);

	//…

	}
out:
	sched_unlock();

	return t;
}

void thread_init(struct thread *t, unsigned int flags,
		void *(*run)(void *), void *arg) {
	sched_priority_t priority;

	assert(t);
	assert(run);
	assert(thread_stack_get(t));
	assert(thread_stack_get_size(t));

	t->id = id_counter++; /* setup thread ID */

	dlist_init(&t->thread_link); /* default unlink value */

	t->critical_count = __CRITICAL_COUNT(CRITICAL_SCHED_LOCK);
	t->siglock = 0;
	t->lock = SPIN_UNLOCKED;
	t->ready = false;
	t->active = false;
	t->waiting = true;
	t->state = TS_INIT;

	/* set executive function and arguments pointer */
	t->run = run;
	t->run_arg = arg;

	t->joining = NULL;

//...

	/* cpu context init */
	context_init(&t->context, true); /* setup default value of CPU registers */
	context_set_entry(&t->context, thread_trampoline);/*set entry (IP register*/
	/* setup stack pointer to the top of allocated memory
	 * The structure of kernel thread stack follow:
	 * +++++++++++++++ top
	 *                  |
	 *                  v
	 * the thread structure
	 * xxxxxxx
	 * the end
	 * +++++++++++++++ bottom (t->stack - allocated memory for the stack)
	 */
	context_set_stack(&t->context,
			thread_stack_get(t) + thread_stack_get_size(t));

	sigstate_init(&t->sigstate);

	/* Initializes scheduler strategy data of the thread */
	runq_item_init(&t->sched_attr.runq_link);
	sched_affinity_init(t);
	sched_timing_init(t);
}

Режим ожидания

Поток может отдать свое время другому потоку по каким-либо причинам, например, вызвав функцию sleep. То есть текущий поток переходит из рабочего режима в режим ожидания. Если в случае с невытесняющим планировщиком мы просто ставили флаг активности, то здесь мы сохраним наш поток в другой очереди. Ждущий поток не кладется в очередь планировщика. Чтобы не потерять поток, он, как правило, сохраняется в специальную очередь. Например, при попытке захватить занятый мьютекс поток, перед тем как заснуть, помещает себя в очередь ждущих потоков мьютекса. И когда произойдет событие, которое ожидает поток, например, освобождение мьютекса, оно его разбудит и мы сможем вернуть поток обратно в очередь готовых. Подробнее про ожидание и подводные камни расскажем ниже, уже после того, как разберемся с кодом самого планировщика.

Завершение потока

Здесь поток оказывается в завершающем состоянии wait. Если поток выполнил функцию обработки и завершился естественным образом, необходимо освободить ресурсы. Про этот процесс я уже подробно описала, когда говорила об избыточности состояния exit. Посмотрим же теперь на реализацию этой функции.

void __attribute__((noreturn)) thread_exit(void *ret) {
	struct thread *current = thread_self();
	struct task *task = task_self();
	struct thread *joining;

	/* We can not free the main thread */
	if (task->main_thread == current) {
    	/* We are last thread. */
    	task_exit(ret);
    	/* NOTREACHED */
	}

	sched_lock();

	current->waiting = true;
	current->state |= TS_EXITED;

	/* Wake up a joining thread (if any).
 	* Note that joining and run_ret are both in a union. */
	joining = current->joining;
	if (joining) {
    	current->run_ret = ret;
    	sched_wakeup(joining);
	}

	if (current->state & TS_DETACHED)
    	/* No one references this thread anymore. Time to delete it. */
    	thread_delete(current);

	schedule();

	/* NOTREACHED */
	sched_unlock();  /* just to be honest */
	panic("Returning from thread_exit()");
}

Трамплин для вызова функции обработки

Мы уже не раз говорили, что, когда поток завершает исполнение, он должен освободить ресурсы. Вызывать функцию thread_exit самостоятельно не хочется — очень редко нужно завершить поток в исключительном порядке, а не естественным образом, после выполнения своей функции. Кроме того, нам нужно подготовить начальный контекст, что тоже делать каждый раз — излишне. Поэтому поток начинает не с той функции, что мы указали при создании, а с функции-обертки thread_trampoline. Она как раз служит для подготовки начального контекста и корректного завершения потока.

static void __attribute__((noreturn)) thread_trampoline(void) {
	struct thread *current = thread_self();
	void *res;

	assert(!critical_allows(CRITICAL_SCHED_LOCK), "0x%x", (uint32_t)__critical_count);

	sched_ack_switched();

	assert(!critical_inside(CRITICAL_SCHED_LOCK));

	/* execute user function handler */
	res = current->run(current->run_arg);
	thread_exit(res);
	/* NOTREACHED */
}

Резюме: описание структуры потока

Итак, для описания задачи в случае с вытесняющим планировщиком нам понадобится достаточно сложная структура. Она содержит в себе:

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

Cоотвественно, описание структуры у нас в проекте выглядит следующим образом:

struct thread {
	unsigned int   	critical_count;
	unsigned int   	siglock;

	spinlock_t     	lock;     	/**< Protects wait state and others. */

	unsigned int   	active;   	/**< Running on a CPU. TODO SMP-only. */
	unsigned int   	ready;    	/**< Managed by the scheduler. */
	unsigned int   	waiting;  	/**< Waiting for an event. */

	unsigned int   	state;    	/**< Thread-specific state. */

	struct context 	context;  	/**< Architecture-dependent CPU state. */

	void        	*(*run)(void *); /**< Start routine. */
	void          	*run_arg;  	/**< Argument to pass to start routine. */
	union {
    	void      	*run_ret;  	/**< Return value of the routine. */
    	void      	*joining;  	/**< A joining thread (if any). */
	} /* unnamed */;

	thread_stack_t 	stack;    	/**< Handler for work with thread stack */

	__thread_id_t  	id;       	/**< Unique identifier. */

	struct task   	*task;     	/**< Task belong to. */
	struct dlist_head  thread_link;  /**< list's link holding task threads. */

	struct sigstate	sigstate; 	/**< Pending signal(s). */

	struct sched_attr  sched_attr;   /**< Scheduler-private data. */
	thread_local_t 	local;
	thread_cancel_t	cleanups;
};

В структуре есть поля не описанные в статье (sigstate, local, cleanups) они нужны для поддержки полноценных POSIX потоков (pthread) и в рамках данной статьи не принципиальны.

Планировщик и стратегия планирования

Напомним, что теперь у нас есть структура потока, включающая в том числе контекст, этот контекст мы умеем переключать. Кроме того, у нас есть системный таймер, который отмеряет кванты времени. Иными словами, у нас готово окружение для работы планировщика.
Задача планировщика — распределять время процессора между потоками. У планировщика есть очередь готовых потоков, которой он оперирует для определения следующего активного потока. Правила, по которым планировщик выбирает очередной поток для исполнения, будем называть стратегией планирования. Основная функция стратегии планирования — работа с очередью готовых потоков: добавление, удаление и извлечение следующего готового потока. От того, как будут реализованы эти функции, будет зависеть поведение планировщика. Поскольку мы смогли определить отдельное понятие — стратегию планирования, вынесем его в отдельную сущность. Интерфейс мы описали следующим образом:

extern void runq_init(runq_t *queue);
extern void runq_insert(runq_t *queue, struct thread *thread);
extern void runq_remove(runq_t *queue, struct thread *thread);
extern struct thread *runq_extract(runq_t *queue);
extern void runq_item_init(runq_item_t *runq_link);

Рассмотрим реализацию стратегии планирования поподробнее.

Пример стратегии планирования

В качестве примера я разберу самую примитивную стратегию планирования, чтобы сосредоточиться не на тонкостях стратегии, а на особенностях вытесняющего планировщика. Потоки в этой стратегии буду обрабатываться в порядке очереди без учета приоритета: новый поток и только что отработавший свой квант помещаются в конец; поток, который получит ресурсы процессора, будет доставаться из начала.
Очередь будет представлять из себя обычный двусвязный список. Когда мы добавляем элемент, мы вставляем его в конец, а когда достаем — берем и удаляем из начала.

void runq_item_init(runq_item_t *runq_link) {
	dlist_head_init(runq_link);
}

void runq_init(runq_t *queue) {
	dlist_init(queue);
}

void runq_insert(runq_t *queue, struct thread *thread) {
	dlist_add_prev(&thread->sched_attr.runq_link, queue);
}

void runq_remove(runq_t *queue, struct thread *thread) {
	dlist_del(&thread->sched_attr.runq_link);
}

struct thread *runq_extract(runq_t *queue) {
	struct thread *thread;

	thread = dlist_entry(queue->next, struct thread, sched_attr.runq_link);
	runq_remove(queue, thread);

	return thread;
}

Планировщик

Теперь мы перейдем к самому интересному — описанию планировщика.

Запуск планировщика

Первый этап работы планировщика — его инициализация. Здесь нам необходимо обеспечить корректное окружение планировщику. Нужно подготовить очередь готовых потоков, добавить в эту очередь поток idle и запустить таймер, по которому будут отсчитываться кванты времени для исполнения потоков.
Код запуска планировщика:

int sched_init(struct thread *idle, struct thread *current) {

	runq_init(&rq.queue);
	rq.lock = SPIN_UNLOCKED;

	sched_wakeup(idle);

	sched_ticker_init();

	return 0;
}

Пробуждение и запуск потока

Как мы помним из описания машины состояний, пробуждение и запуск потока для планировщика — это один и тот же процесс. Вызов этой функции есть в запуске планировщика, там мы запускаем поток idle. Что, по сути дела, происходит при пробуждении? Во-первых, снимается пометка о том, что мы ждем, то есть поток больше не находится в состоянии waiting. Затем возможны два варианта: успели мы уже уснуть или еще нет. Почему это происходит, я опишу в следующем разделе “Ожидание”. Если не успели, то поток еще находится в состоянии ready, и в таком случае пробуждение завершено. Иначе мы кладем поток в очередь планировщика, снимаем пометку о состоянии waiting, ставим ready. Кроме того, вызывается перепланирование, если приоритет пробужденного потока больше текущего. Обратите внимание на различные блокировки: все действо происходит при отключенных прерываниях. Для того, чтобы посмотреть, как пробуждение и запуск потока происходит в случае SMP, советую вам обратиться к коду проекта.

/** Locks: IPL, thread. */
static int __sched_wakeup_ready(struct thread *t) {
	int ready;

	spin_protected_if (&rq.lock, (ready = t->ready))
    	t->waiting = false;

	return ready;
}

/** Locks: IPL, thread. */
static void __sched_wakeup_waiting(struct thread *t) {
	assert(t && t->waiting);

	spin_lock(&rq.lock);
	__sched_enqueue_set_ready(t);
	__sched_wokenup_clear_waiting(t);
	spin_unlock(&rq.lock);
}


static inline void __sched_wakeup_smp_inactive(struct thread *t) {
	__sched_wakeup_waiting(t);
}

/** Called with IRQs off and thread lock held. */
int __sched_wakeup(struct thread *t) {
	int was_waiting = (t->waiting && t->waiting != TW_SMP_WAKING);

	if (was_waiting)
    	if (!__sched_wakeup_ready(t))
        	__sched_wakeup_smp_inactive(t);

	return was_waiting;
}

int sched_wakeup(struct thread *t) {
	assert(t);
	return SPIN_IPL_PROTECTED_DO(&t->lock, __sched_wakeup(t));
}

Ожидание

Переход в режим ожидания и правильный выход из него (когда ожидаемое событие, наконец, случится), вероятно, самая сложная и тонкая вещь в вытесняющем планировании. Давайте рассмотрим ситуацию поподробнее.
Прежде всего, мы должны объяснить планировщику, что мы хотим дождаться какого-либо события, причем событие происходит естественно асинхронного, а нам нужно его получить синхронно. Следовательно, мы должны указать, как же планировщик определит, что событие произошло. При этом мы не знаем, когда оно может произойти, например, мы успели сказать планировщику, что ждем события, проверили, что условия его возникновения еще не выполнены, и в этот момент происходит аппаратное прерывание, которое и вырабатывает наше событие. Но поскольку мы уже выполнили проверку, то эта информация потеряется. У нас в проекте мы решили данную проблему следующим образом.
Код макроса ожидания

#define SCHED_WAIT_TIMEOUT(cond_expr, timeout) 
	((cond_expr) ? 0 : ({                                            
		int __wait_ret = 0;                                          
		clock_t __wait_timeout = timeout == SCHED_TIMEOUT_INFINITE ? 
			SCHED_TIMEOUT_INFINITE : ms2jiffies(timeout);            
		                                                             
		threadsig_lock();                                            
		do {                                                         
			sched_wait_prepare();                                    
			                                                         
			if (cond_expr)                                           
				break;                                               
			                                                         
			__wait_ret = sched_wait_timeout(__wait_timeout,          
											&__wait_timeout);        
		} while (!__wait_ret);                                       
		                                                             
		sched_wait_cleanup();                                        
		                                                             
		threadsig_unlock();                                          
		__wait_ret;                                                  
	}))

Поток у нас может находиться сразу в суперпозиции состояний. То есть когда поток засыпает, он все еще является активным и всего лишь выставляет дополнительный флаг waiting. Во время пробуждения опять же просто снимается этот флаг, и только если поток уже успел дойти до планировщика и покинуть очередь готовых потоков, он добавляется туда снова. Если рассмотреть описанную ранее ситуацию на картинке, то получится следующая картина.

A — active
R — ready
W — wait

На картинке буквами обозначено наличие состояний. Светло-зеленый цвет — состояние потока до wait_prepare, зеленый — после wait_prepare, а темно-зеленый — вызов потоком перепланирования.
Если событие не успеет произойти до перепланирования, то все просто — поток уснет и будет ждать пробуждения:

Перепланирование

Основная задача планировщика — планирование, прошу прощения за тавтологию. И мы наконец подошли к моменту когда можно разобрать как этот процесс реализован у нас в проекте.
Во-первых перепланирование должно выполняться при заблокированном планировщике. Во-вторых мы хотим дать возможность разрешить вытеснение потока или нет. Поэтому мы вынесли логику работы в отдельную функцию окружили ее вызов блокировками и вызвали ее указав, что в этом месте мы не позволяем вытеснение.
Далее идут действия с очередью готовых потоков. Если активный на момент перепланирования потока не собирается уснуть, то есть если у него не выставлено состояние waiting, мы просто добавим его в очередь потоков планировщика. Затем мы достаем самый приоритетный поток из очереди. Правила нахождения этого потока реализуются с помощью стратегии планирования.
Затем если текущий активный поток совпадает с тем который мы достали из очереди, нам не нужно перепланирование и мы можем просто выйти и продолжить выполнение потока. В случае же если требуется перепланирование, вызывается функция sched_switch, в которой выполняются действия необходимые планировщику и главное вызывается context_switch который мы рассматривали выше.
Если же поток собирается уснуть, находится в состоянии waiting, то он не попадает в очередь планировщика, и с него снимают метку ready.
В конце происходит обработка сигналов, но как я отмечала выше, это выходит за рамки данной статьи.

static void sched_switch(struct thread *prev, struct thread *next) {
    sched_prepare_switch(prev, next);

    trace_point(__func__);

    /* Preserve initial semantics of prev/next. */
    cpudata_var(saved_prev) = prev;
    thread_set_current(next);
    context_switch(&prev->context, &next->context);  /* implies cc barrier */
    prev = cpudata_var(saved_prev);

    sched_finish_switch(prev);
}


static void __schedule(int preempt) {
	struct thread *prev, *next;
	ipl_t ipl;

	prev = thread_self();

	assert(!sched_in_interrupt());
	ipl = spin_lock_ipl(&rq.lock);

	if (!preempt && prev->waiting)
    	prev->ready = false;
	else
    	__sched_enqueue(prev);

	next = runq_extract(&rq.queue);

	spin_unlock(&rq.lock);

	if (prev != next)
    	sched_switch(prev, next);

	ipl_restore(ipl);

	assert(thread_self() == prev);

	if (!prev->siglock) {
    	thread_signal_handle();
	}
}

void schedule(void) {
	sched_lock();
	__schedule(0);
	sched_unlock();
}

Проверка работы многопоточности

В качестве примера я использовала следующий код:

#include <stdint.h>
#include <errno.h>
#include <stdio.h>
#include <util/array.h>

#include <kernel/thread.h>

#include <framework/example/self.h>


/**
 * This macro is used to register this example at the system.
 */
EMBOX_EXAMPLE(run);

/* configs */
#define CONF_THREADS_QUANTITY  	0x8 /* number of executing threads */
#define CONF_HANDLER_REPEAT_NUMBER 300  /* number of circle loop repeats*/

/** The thread handler function. It's used for each started thread */
static void *thread_handler(void *args) {
    int i;
    /* print a thread structure address and a thread's ID */
    for(i = 0; i < CONF_HANDLER_REPEAT_NUMBER; i ++) {
   	 printf("%d", *(int *)args);
    }
    return thread_self();
}

/**
 * Example's executing routine
 * It has been declared by the macro EMBOX_EXAMPLE
 */
static int run(int argc, char **argv) {
    struct thread *thr[CONF_THREADS_QUANTITY];
    int data[CONF_THREADS_QUANTITY];
    void *ret;
    int i;

    /* starting all threads */
    for(i = 0; i < ARRAY_SIZE(thr); i ++) {
   	 data[i] = i;   	
   	 thr[i] = thread_create(0, thread_handler, &data[i]);   	
    }

    /* waiting until all threads finish and print return value*/
    for(i = 0; i < ARRAY_SIZE(thr); i ++) {
   	 thread_join(thr[i], &ret);   	
    }
    printf("n");

    return ENOERR;
}

Собственно, это почти обычное приложение. Макрос EMBOX_EXAMPLE(run) задает точку входа в специфичный тип наших модулей. Функция thread_join дожидается завершения потока, пока я ее тоже не рассматривала. И так уже очень много получилось для одной статьи.
Результат запуска этого примера на qemu в составе нашего проекта следующий

Как видно из результатов, сначала созданные потоки выполняются один за другим, планировщик дает им время по очереди. В конце некоторое расхождение. Я думаю, это следствие того, что у планировщика достаточно грубая точность (не сопоставимая с выводом одного символа на экран). Поэтому на первых проходах потоки успевают выполнить разное количество циклов.
В общем, кто хочет поиграться, можно скачать проект и попробовать все вышеописанное на практике.
Если тема интересна, я попробую продолжить рассказ о планировании, еще достаточно много тем осталось не раскрытыми.

Многозадачность в операционных системах, виды многозадачности

Многозада́чность — свойство ОС или среды выполнения обеспечивать возможность параллельной обработки нескольких процессов. Иными словами, многозадачность — способ выполнения нескольких задач в один период времени. При этом задачи делят между собой общие ресурсы (resources sharing), помимо этого осуществляется планирование (scheduling). [1]

Система называется однозадачной,если она не обладает свойством многозадачности, т.е. задачи в ней выполняются последовательно. DOS — одноза­дачная ОС.

Многозадачность имеет место при наличии нескольких потоков исполнения.
Поток исполнения — набор последовательных инструкций, выполняемых процессором во время работы программы. На одном процессорном ядре одновременно выполняется лишь один поток исполнения, который называется активным. Процесс выбора активного исполнительного потока носит название планирование.

По типу наименьшего элемента управляемого кода

Процессная многозадачность.

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

Поточная многозадачность.

Многопоточность — специализированная форма многозадачности. Наименьший элемент управляемого кода — поток. Многопотоковая (multi-threaded) система предоставляет возможность одновременного выполнения одной программой 2 и более задач

По способу организации времени выполнения каждого процесса

Параллельная многозадачность

Параллельная многозадачность, когда каждая задача исполняется в своём аппаратном микропроцессорном ядре действительно одновременно друг с другом. Реализация данного типа многозадачности требует больших материальных вложений. Альтернативой параллельной многозадачности является применение псевдопараллельной многозадачности или совокупности параллельной и псевдопараллельной многозадачности при наличии нескольких процессорных ядер.

Типы псевдопараллельной многозадачности

Невытесняющая многозадачность. Существенным ограничением такого подхода является то, что время, затрачиваемое программой на обработку сообщения может быть очень большим, а управление операционной системе передается только после обработки сообщения.

Совместная или кооперативная многозадачность. ОС передает управление от одного приложения другому не в любой момент времени, а только когда текущее приложение отдает управление системе, получил, как было упомянуто, название кооперативной многозадачности

Вытесняющая, или приоритетная, многозадачность (режим реального времени)

С Windows 95 ОС действительно контролирует и управляет процессами, потоками и их переключением. Способность ОС прервать выполняемый поток практически в любой момент времени и передать управление другому ожидающему потоку определяется термином preemptive multitasking — преимущественная, или вытесняющая, многозадачность.

Многозадачность в операционной системе Windows

ТЕОРЕТИЧЕСКОЕ ОПИСАНИЕ

Многозадачность

Под многозадачностью понимается организация одновременного выполнения нескольких прикладных программ с помощью разделения между ними процессорного времени. Таким образом, можно говорить о переключении задач, которое происходит незаметно для пользователя и самих программ. Следует иметь в виду, что одновременное выполнение нескольких машинных команд на одном процессоре невозможно. Операционная система сама выделяет каждой задаче требуемые ресурсы и корректно решает проблемы распределения контроля над ними. Такими ресурсами могут быть оперативная память, внешние устройства и т. п. Быстрота, с которой процессор переключается с выполнения одной задачи на другую, создает впечатление одновременного их выполнения.

Распределение процессорного времени между несколькими задачами реализуется специальной компонентой операционной системы, называемой планировщиком. При каждой смене задачи планировщик должен сохранить статус (состояние) прерванной задачи, загрузить в процессор статус новой задачи и передать ей управление в той точке, где она была прервана в предыдущий раз. Статус задачи определяется содержимым счетчика команд, регистров общего назначения и т. п., и обычно сохраняется в специальной структуре данных, называемой управляющим блоком процесса, или РСВ (Process Control Block).

В принципе существуют два основных метода позволяющие организовать переключение задач в рамках какой — либо операционной системы:

• Переключение по событию
• Переключение по времени

Переключение по событию

Переключение задач по событию показано на рис 1.

В этом режиме операционная система не определяет самостоятельно момент смены текущей задачи. Он может быть указан активной задачей, «добровольно» приостанавливающей свое выполнение с помощью специального обращения к операционной системе. Кроме того, задача прерывается, если она обращается к функциям операционной системы, например, с запросом на ввод/вывод. Поскольку на время выполнения запроса к операционной системе задача ожидает результата затребованной операции, она переходит в режим ожидания, и операционная система может передать управление процессором другой задаче, которая на данный момент готова к выполнению. Этот метод требует организации системы приоритетов, позволяющей избежать ситуации, когда какая – либо программа, не осуществляющая обращений к функциям операционной системы, будет выполняться, фактически, в монопольном режиме. Поэтому самые высокие приоритеты назначаются задачам с большим количеством обращений к функциям операционной системы.

Переключение по времени

Переключение задач по времени показано на рис 2.

Рис 2. Переключение задач по времени.

Этот метод основан на использовании внешнего сигнала, поступающего на процессор через равные интервалы времени. Обычно используется аппаратное прерывание от внешнего таймера. Когда возникает такое прерывание, операционная система прекращает выполнение активной в данный момент задачи и сохраняет ее состояние. Планировщик анализирует затем список ожидающих задач и передает управление процессором выбранной задаче. Таким образом, метод основан на разделении, что позволяет выделить каждой задаче заранее определенный интервал времени.

Многозадачность в операционной системе Windows

В операционной системе Windows реализован метод разделения времени в сочетании с системой приоритетов. На практике переключение задач происходит в одном из следующих случаев:

1. Прерывание от таймера. Это означает, что время, предоставленное активной задаче, истекло. Планировщик прекращает ее выполнение и передает управление задаче с наибольшим приоритетом. Такое переключение происходит наиболее часто.

2. Текущая задача запрашивает операцию ввода/вывода. Поскольку задача должна ожидать окончания этой операции, планировщик приостанавливает ее выполнение и активизирует задачу с наибольшим приоритетом.

3. Активная задача освобождает ресурс, который ожидала задача с большим приоритетом. Планировщик приостанавливает выполнение текущей задачи в пользу другой, более приоритетной.

4. Внешнее, т. е., аппаратное прерывание сигнализирует о завершении операции ввода/вывода на периферийное устройство, которое ожидалось другой, более приоритетной задачей. Последняя начинает выполняться вместо текущей задачи.

В Windows каждая запущенная 32- х битовая программа называется процессом. Процесс в основном имеет дело с распределением ресурсов системы. Исполняемый код для системы является другим объектом, называемым нитью, или потоком управления (thread). Когда запускается новый процесс, ему автоматически придается одна нить. Нити (потоки) используются операционной системой Windows для диспетчеризации времени процессора. Диспетчеризация — это метод выделения времени каждой из нитей (не процессов, поскольку процесс может иметь несколько нитей). Операционная система рассматривает все готовые к запуску потоки и выбирает для выполнения один из них. Диспетчер также определяет квант времени, предоставляемый для выполнения каждому из потоков.

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

ОПИСАНИЕ ЛАБОРАТОРНОЙ РАБОТЫ

В данной лабораторной работе изучаются методы создания и запуска процессов и потоков в рамках операционной системы Windows.

Многозадачная ОС

Многозадачные операционные системы

Почти все современные операционные системы (Windows 95, Windows NT, Windows 2000, Unix) поддерживают преимущественную многозадачность Этот термин, который часто переводят как вытесняющая многозадачность, означает, что процесс или, точнее, его поток, который в данный момент активен, имеет преимущество перед другими конкурирующими потоками с одинаковым приоритетом. Системы Windows 3.1 и Macintosh поддерживают кооперативную многозадачность в которой все управление отдано системе. В такой системе легче программировать, но она менее эффективна.

Классификация ОС

Существует несколько схем классификации операционных систем. Ниже приведена классификация по некоторым признакам с точки зрения пользователя.

Реализация многозадачности

По числу одновременно выполняемых задач операционные системы можно разделить на два класса:

• многозадачные (Unix, OS/2, Windows);
• однозадачные (например, MS-DOS).

Многозадачная ОС, решая проблемы распределения ресурсов и конкуренции, полностью реализует мультипрограммный режим в соответствии с требованиями раздела «Основные понятия, концепции ОС «.

Многозадачный режим, который воплощает в себе идею разделения времени, называется вытесняющим (preemptive). Каждой программе выделяется квант процессорного времени, по истечении которого управление передается другой программе. Говорят, что первая программа будет вытеснена. В вытесняющем режиме работают пользовательские программы большинства коммерческих ОС.

В некоторых ОС (Windows 3.11, например) пользовательская программа может монополизировать процессор, то есть работать в невытесняющем режиме. Как правило, в большинстве систем не подлежит вытеснению код собственно ОС. Ответственные программы, в частности задачи реального времени, также не вытесняются. Более подробно об этом рассказано в лекции, посвященной планированию работы процессора.

По приведенным примерам можно судить о приблизительности классификации. Так, в ОС MS-DOS можно организовать запуск дочерней задачи и наличие в памяти двух и более задач одновременно. Однако эта ОС традиционно считается однозадачной, главным образом из-за отсутствия защитных механизмов и коммуникационных возможностей.

Поддержка многопользовательского режима

По числу одновременно работающих пользователей ОС можно разделить на:

• однопользовательские (MS-DOS, Windows 3.x);
• многопользовательские (Windows NT, Unix).

Наиболее существенное отличие между этими ОС заключается в наличии у многопользовательских систем механизмов защиты персональных данных каждого пользователя.

Многопроцессорная обработка

Вплоть до недавнего времени вычислительные системы имели один центральный процессор. В результате требований к повышению производительности появились многопроцессорные системы, состоящие из двух и более процессоров общего назначения, осуществляющих параллельное выполнение команд. Поддержка мультипроцессирования является важным свойством ОС и приводит к усложнению всех алгоритмов управления ресурсами. Многопроцессорная обработка реализована в таких ОС, как Linux, Solaris, Windows NT, и ряде других.

Многопроцессорные ОС разделяют на симметричные и асимметричные. В симметричных ОС на каждом процессоре функционирует одно и то же ядро, и задача может быть выполнена на любом процессоре, то есть обработка полностью децентрализована. При этом каждому из процессоров доступна вся память.

В асимметричных ОС процессоры неравноправны. Обычно существует главный процессор (master) и подчиненные (slave), загрузку и характер работы которых определяет главный процессор.

Системы реального времени

В разряд многозадачных ОС, наряду с пакетными системами и системами разделения времени, включаются также системы реального времени, не упоминавшиеся до сих пор.

Они используются для управления различными техническими объектами или технологическими процессами. Такие системы характеризуются предельно допустимым временем реакции на внешнее событие, в течение которого должна быть выполнена программа, управляющая объектом. Система должна обрабатывать поступающие данные быстрее, чем они могут поступать, причем от нескольких источников одновременно.

Столь жесткие ограничения сказываются на архитектуре систем реального времени, например, в них может отсутствовать виртуальная память, поддержка которой дает непредсказуемые задержки в выполнении программ. (См. также разделы, связанные с планированием процессов и реализацией виртуальной памяти.)

Приведенная классификация ОС не является исчерпывающей. Более подробно особенности применения современных ОС рассмотрены в [Олифер, 2001].

Заключение

Мы рассмотрели различные взгляды на то, что такое операционная система ; изучили историю развития операционных систем ; выяснили, какие функции обычно выполняют операционные системы ; наконец, разобрались в том, какие существуют подходы к построению операционных систем. Следующую лекцию мы посвятим выяснению понятия «процесс» и вопросам планирования процессов.