Операционные системы
Самостоятельная работа №1
Изучение алгоритмов реализации и использования сопрограмм
(моделирование принципов невытесняющей многозадачности)
Цель работы: познакомиться с алгоритмами реализации сопрограмм и способами их использования для организации многозадачности.
Общие сведения
Перед началом выполнения задания убедитесь, что вы понимаете назначение системного стека, смысл соглашения о вызовах, структуры стекового кадра и действий, выполняемых в прологе и эпилоге любой процедуры:
Сопрограммы — это средство прередачи управления из одной процедуры в другую без отношения вложенности. Выполняемой процедуре нет необходимости возвращаться в вызвавшую ее процедуру. Традиционные операторы ВЫЗОВ и ВОЗВРАТ в случае сопрограмм заменяются одним оператором — ПЕРЕДАТЬ_УПРАВЛЕНИЕ.
У каждой сопрограммы должен быть свой собственный стек. Под него можно отвести статический или динамический массив разумного размера (STACK_SIZE):
long *stack = calloc(STACK_SIZE, sizeof(long));
Текущее состояние стека каждой из сопрограмм должно храниться в структуре, называемой ДЕСКРИПТОР_СОПРОГРАММЫ:
typedef struct {
long *sp;
...
} descriptor_t;
Кроме указателя вершины стека, в структуре может храниться адрес зарезервированной под стек памяти для последующего освобождения, поля для организации связного списка, приоритет и иные параметры контекста сопрограммы.
Процедура переключения сопрограмм должна заменять стек одной сопрограммы на стек другой сопрограммы. Это делается ассемблерной вставкой путём изменения регистра RSP (для x86_64) или ESP (для x86_32).
|
Пример для 64-битной архитектуры: |
Пример для 32-битной архитектуры: |
Подробнее об ассемблерных вставках в GCC можно почитать в Википедии или в справочном руководстве по GCC.
Данный код написан в предположении, что для эпилога функции transfer компилятор сгенерирует более простой код:
popq %rbp ret |
popl %ebp ret |
Однако, если в процедуру transfer добавить вызовы каких-то других процедур и функций (например, для отладки), то компилятор сгенерирует эпилог с командой leave:
leave ret
Команда leave эквивалентна паре нижеследующих команд и «портит» выставленное в ассемблерной вставке значение RSP/ESP:
movq %rbp,%rsp popq %rbp |
movl %ebp,%esp popl %ebp |
Перед первым использованием в процедуре transfer дескриптор сопрограммы необходимо инициализировать, а также надо подготовить память стека.
|
Для 64-битной архитектуры при использовании соглашения о вызовах System V AMD64 параметры будут переданы через регистры RDI (old_desc) и RSI (new_desc), а стековый кадр в процедуре transfer будет иметь следующий вид:
Необходимо также помнить, что значение RBP должно быть выравнено по 16-байтной границе. |
Для 32-битной архитектуры при использовании соглашения о вызовах языка Си стековый кадр в процедуре transfer будет иметь следующий вид:
|
В стековый кадр по адресу RIP/EIP должна быть записана точка входа в сопрограмму (entry). Процедура, подготавливающая дескриптор сопрограммы, может выглядеть так:
|
Пример для 64-битной архитектуры: |
Пример для 32-битной архитектуры: |
Собираем всё вместе (64-битный пример):
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define STACK_SIZE 8192
typedef struct {
long *sp;
} descriptor_t;
descriptor_t o, d1, d2;
void newproc(void* entry, descriptor_t* d) {
printf("newproc %p\n", entry);
long *stack = (long*)calloc(STACK_SIZE, sizeof(long));
stack[STACK_SIZE-2] = (long)entry;
d->sp = stack + STACK_SIZE - 3;
}
void transfer(descriptor_t *old_desc, descriptor_t *new_desc) {
asm volatile ("movq %%rsp, %0" : "=r"(old_desc->sp) : : );
asm volatile ("movq %0, %%rsp" : : "r"(new_desc->sp) : );
}
void co1(void) {
int i;
for (i=0; i < 1000000; i++) {
printf("\x1B[10;10H(%d)\x1B[0K\n", i);
/* ESC [ m ; n H — перевод курсора в позицию (m,n)
ESC [ 0 K — очистка с текущей позиции до конца строки */
transfer(&d1, &d2);
}
transfer(&d1, &o);
}
void co2(void) {
int i;
for (i=0; i < 1000000; i++) {
printf("\x1B[11;10H[%d]\x1B[0K\n", i);
transfer(&d2, &d1);
}
transfer(&d2, &o);
}
int main() {
newproc(co1, &d1);
newproc(co2, &d2);
transfer(&o, &d1);
puts("all done — have fun!");
return 0;
}
Манипулирование содержимым стека для переключения контекста сопрограмм является очень тонким, зависящим от многих факторов (платформа, компилятор, ...) трюком. В стандарте POSIX предлагается группа условно портируемых вызовов, скрывающая от разработчика особенности той или иной платформы, позволяющая реализовать user-level threads своими силами (см. man swapcontext):
#include <ucontext.h> void makecontext(ucontext_t *ucp, void (*func)(), int argc, ...); int swapcontext(ucontext_t *oucp, const ucontext_t *ucp);
Для каждой сопрограммы необходимо инициализировать структуру ucontext_t:
typedef struct ucontext_t {
struct ucontext_t *uc_link;
sigset_t uc_sigmask;
stack_t uc_stack;
mcontext_t uc_mcontext;
...
} ucontext_t;
Здесь uc_link — ссылка на контекст, который должен получить управление в случае завершения данной сопрограммы (контекст основной программы), uc_sigmask — маска блокируемых сигналов, uc_stack — стек контекста, uc_mcontext — платформенно-зависимое представление контекста.
В таком случае процедура инициализации сопрограммы сведётся к следующей:
ucontext_t o, d1, d2;
...
void newproc(void* entry, ucontext_t* d) {
getcontext(d);
d->uc_stack.ss_sp = malloc(STACK_SIZE);
d->uc_stack.ss_size = STACK_SIZE;
d->uc_link = &o;
makecontext(d, entry, 0);
}
...
newproc(co1, &d1);
Задание 1: Модифицируйте приведённый выше пример под использование нескольких сопрограмм (больше трёх), составив из них очередь. Очередь может быть реализована связным списком или массивом. Для передачи управления реализуйте процедуру yield() без параметров, выбирающую следующую сопрограмму из очереди:
void yield(void);
Задание 2: Модифицируйте программу, получившуюся в задании 1, под использование makecontext и swapcontext.