Курс «Операционные системы» профессора Ли Чжуня из Харбинского университета техники配有实验

int iam(const char * name);

int whoami(char* name, unsigned int size);

gcc -o iam iam.c
gcc -o whoami whoami.c
gcc -o testlab2 testlab2.c
./testlab2 # Максимальное количество баллов — 50
./testlab2.sh # Максимальное количество баллов — 30

#define _syscall3(type, name, atype, a, btype, b, ctype, c) \
type name(atype a, btype b, ctype c) \
{ \
long __res; \
__asm__ volatile ("int $0x80" \
: "=a" (__res) \
: "0" (__NR_##name), "b" ((long)(a)), "c" ((long)(b)), "d" ((long)(c))); \
if (__res >= 0) \
return (type) __res; \
errno = -__res; \
return -1; \
}

main() -> sched_init() -> set_system_gate() -> _set_gate()

63                               48 47 46  44 43     40 39 37 36        32
+----------------------------------+--+----+--+--------+-+-+-+----------+
|                                  |  |    |  |        |     |          |
|       &system_call[31:16]        |P |DPL |S |  TYPE  |0 0 0| Reserved |
|                                  |1 | 00 |0 | 1|1|1|1|     |          |
+-------------+--+--+--+--+--------+--+----+--+--------+-+-+-+----------+
31                               17 16                                  0
+----------------------------------+------------------------------------+
|                                  |                                    |
|         Сегментный селектор         |           &system_call[15:0]       |
|              0x0008               |                                    |
+----------------------------------+------------------------------------+

#define _syscall1(type, name, atype, a) \
type name(atype a) \
{ \
long __res; \
__asm__ volatile ("int $0x80" \
: "=a" (__res) \
: "0" (__NR_##name), "b" ((long)(a))); \
if (__res >= 0) \
return (type) __res; \
errno = -__res; \
return -1; \
}

pid    X    time

12    N    1056
12    J    1057
4     W    1057
12    R    1057
13    N    1058
13    J    1059
14    N    1059
14    J    1060
15    N    1060
15    J    1061
12    W    1061
15    R    1061
15    J    1076
14    R    1076
14    E    1076
 .     .     .     .     .     .

#define TASK_RUNNING		0
#define TASK_INTERRUPTIBLE	1
#define TASK_UNINTERRUPTIBLE	2
#define TASK_ZOMBIE		3
#define TASK_STOPPED		4

int copy_process(.  .  .  ) // параметры опущены
{
    // Подробный анализ функций fork и copy_process() представлен в эксперименте 4
    .  .  .
}
p->state = TASK_RUNNING;	/* do this last, just in case */
// В этот момент подпроцесс p переключается в состояние готовности (J)
return last_pid;
}

void schedule(void)
{
	int i, next, c;
	struct task_struct ** p;
	/* проверка тревоги, пробуждение всех прерываемых задач, которые получили сигнал */
	for (p = &LAST_TASK; p > &FIRST_TASK; --p)
		if (*p) {
			if ((*p)->alarm && (*p)->alarm < jiffies) {
				(*p)->signal |= (1 << (SIGALRM - 1));
				(*p)->alarm = 0;
			}
			if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) && (*p)->state == TASK_INTERRUPTIBLE)
				// Если в сигнальном битовом поле процесса p есть сигналы, кроме тех, которые заблокированы, то он переключается из состояния ожидания (W) в состояние готовности (J)
				(*p)->state = TASK_RUNNING;
		}
	/* это основная часть планировщика: */
	while (1) {
		c = -1;
		// Начальное значение равно -1, если нет доступных для планирования задач, будет планироваться задача 0 (хотя в этот момент задача 0 может быть заблокирована). Задача 0 выполняет только системный вызов pause, который снова возвращает её сюда
		// Таким образом, задача 0 является единственной задачей, которая может переключаться из заблокированного состояния в состояние готовности
		next = 0;
		i = NR_TASKS;
		p = &task[NR_TASKS];
		while (--i) {
			if (! *--p)
				continue; // Пропуск пустых слотов задач
``````markdown
 			if ((*p)->state == TASK_RUNNING && (*p)->counter > c) // Два условия: задача в состоянии готовности и counter максимальный
  				c = (*p)->counter, next = i;
  		}
  		if (c) break; // Если существует задача с counter не равным нулю (что означает, что время выполнения ещё не истекло), или нет доступных для выполнения задач (c == -1), то выходим из цикла
  		for (p = &LAST_TASK; p > &FIRST_TASK; --p)
  			if (*p)
  				(*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
  	}
      // Если next не равен текущей задаче current, то в switch_to current переключается в состояние готовности (J), а next переключается в состояние выполнения (R)
      // Linux 0.11 использует TASK_RUNNING для представления как состояния готовности (J), так и состояния выполнения (R), поэтому в исходном коде нет необходимости изменять state для current и next
      // Однако в соответствии с требованиями эксперимента, необходимо различать их и выводить
  	switch_to(next); // Переключение на другую задачу, switch_to одновременно реализует переключение потока команд и TSS, то есть его вторая часть кода не будет выполнена
  } // Этот скобочный блок не будет выполнен, только если текущая задача будет переключена обратно

```markdown
// Устанавливает текущий процесс (здесь процесс и задача — одно и то же, но задача подчеркивает, что процесс находится в ядре) в состояние ожидания, которое нельзя прервать, и делает указатель на голову очереди сна указывать на текущий процесс.
// В Linux 0.11 это состояние ожидания обозначается как TASK_UNINTERRUPTIBLE.

```c
// В отличие от wake_up, этот процесс может быть пробужден сигналом (сохраненным в векторе сигналов процесса).
// Основное отличие от sleep_on заключается в том, что он может пробудить процесс, находящийся в середине очереди, что требует корректировки очереди.
``````c
void interruptible_sleep_on(struct task_struct **p)
{
    struct task_struct *tmp;
    if (!p)
        return;
    if (current == &(init_task.task))
        panic("task[0] trying to sleep");
    tmp = *p;
    *p = current;
    current->state = TASK_INTERRUPTIBLE; // текущий процесс current переходит из состояния выполнения (R) в состояние блокировки (W), которое можно пробудить сигналом (в schedule()) или функцией wake_up()
repeat:	schedule();
}

- `sched.c` функции `interruptible_sleep_on()`
  ```c
  void interruptible_sleep_on(struct task_struct **p)
  {
      if (p && *p && *p != current) {
          (**p).state = 0; // процесс **p становится в состоянии "готов к выполнению" (J)
          goto repeat;
      }
      *p = NULL;
      if (tmp)
          tmp->state = 0; // процесс tmp (ранее введенный в состояние ожидания) переходит из состояния "ожидание" (W) в "готов к выполнению" (J)
  }

 `TASK_INTERRUPTIBLE` означает состояние "ожидание" с возможностью прерывания. Если процесс находится в ядре и ожидает доступ к системному ресурсу, он может перейти в это состояние с помощью функции `interruptible_sleep_on()`. Сигналы и функция `wake_up()` могут переключить это состояние в `TASK_RUNNING`. Это состояние встречается в следующих местах:
 - `sched. c` функция `schedule()`
 - `sched. c` функция `interruptible_sleep_on()`
 Эти две функции были рассмотрены при анализе состояния `TASK_RUNNING`. В функции `schedule()` состояние `TASK_INTERRUPTIBLE` переключается в `TASK_RUNNING` при наличии соответствующего сигнала.
 - `sched. c` функция `sys_pause()`
   ```c
   // Когда система не занята, процесс 0 будет циклически вызывать sys_pause(), чтобы активировать алгоритм планирования
   // В этом случае состояние процесса может быть "ожидание", когда есть другие процессы, готовые к выполнению; или "выполнение", так как он единственный процесс, выполняющийся на CPU, хотя его эффект заключается в ожидании
   // Здесь используется второй вариант, так как если использовать первый вариант, то в /var/process. log появится множество записей о переключении состояния процесса 0
   // Поэтому, при выводе необходимо проверять, является ли текущий процесс 0, если да, то вывод не производится
   int sys_pause(void)
   {
       current->state = TASK_INTERRUPTIBLE; // текущий процесс переходит из состояния "выполнение" (R) в "ожидание" (W)
       schedule();
   }

    return 0;
}
```
- `exit. c` файл содержит вызов `sys_waitpid()`.`sys_waitpid()` вызывается пользовательской функцией `waitpid()`, которая, в свою очередь, вызывается функцией `wait()`, а `wait()` вызывается инициализирующей функцией задачи 1, `init()`.

```c
// Приостанавливает текущий процесс до тех пор, пока подпроцесс с pid не завершится или не получит сигнал, завершающий процесс
// Если подпроцесс с pid находится в состоянии TASK_ZOMBIE (мертвый процесс), вызов завершается немедленно
// Подробный анализ см. в книге "Полное пояснение Linux-ядра"
int sys_waitpid(pid_t pid, unsigned long *stat_addr, int options)
{
   . . .
   if (flag) {
       if (options & WNOHANG) // Если опции, переданные waitpid, равны WNOHANG, вызов завершается немедленно
           return 0;
       current->state = TASK_INTERRUPTIBLE; // Текущий процесс переходит из состояния готовности (R) в состояние ожидания (S)
       schedule();
       // После перезапуска задачи, если сигнал, отличный от SIGCHLD, не получен, процесс повторяет обработку
       if (! (current->signal &= ~(1 << (SIGCHLD - 1))))
           goto repeat;
       else
           return -EINTR;
   }
   return -ECHILD;
}
```

#### TASK_UNINTERRUPTIBLE
`TASK_UNINTERRUPTIBLE` означает состояние неотключаемого ожидания/блокировки. Разница с `TASK_INTERRUPTIBLE` заключается в том, что его можно разбудить только с помощью `wake_up()`. Это состояние встречается в следующих местах:
- Файл `fork.c` содержит вызов `copy_process()`.

```c
int copy_process(. . . ) // Входные параметры опущены
{
   . . .
   // Подробный анализ fork и copy_process() см. в эксперименте 4
   . . .
```    // get_free_page получает страницу памяти размером 4KB (подробности о памяти будут рассмотрены позже, malloc нельзя использовать, так как это библиотечный код пользователя, а в ядре нельзя использовать)
    // Находит страницу с mem_map = 0 (пустая страница), возвращает её адрес и преобразует тип, используя страницу памяти как task_struct(PCB)
    // Эта страница 4KB используется для хранения task_struct и стека ядра
    p = (struct task_struct *) get_free_page();
    if (!p)
        return -EAGAIN;
    task[nr] = p;
    *p = *current;
    // Новый процесс p переходит в состояние TASK_UNINTERRUPTIBLE, но в соответствии с требованиями эксперимента он соответствует новому процессу (N)
    p->state = TASK_UNINTERRUPTIBLE;
    . . .
}
```
- `sched.c` файл содержит вызов `sleep_on()`.
Эта ядра функция уже упоминалась при анализе `TASK_RUNNING`.
#### TASK_ZOMBIE
`TASK_ZOMBIE` означает состояние мертвого процесса. Когда процесс завершил свою работу, но его родительский процесс ещё не запросил его состояние, то этот процесс находится в состоянии мертвого процесса. Чтобы родительский процесс мог получить информацию о завершении работы этого процесса, его структура данных задачи должна сохраняться. Как только родительский процесс вызывает `wait()` для получения информации о дочернем процессе, структура данных задачи дочернего процесса освобождается. Это состояние возникает в следующих местах:
  - `exit.c` в функции `do_exit()`
  ```c
 int do_exit(long code)
 {
 	int i;
 	// Сначала освобождаются страницы памяти, занимаемые сегментами кода и данных текущего процесса
     // Страница памяти, содержащая структуру task_struct текущего процесса, не освобождается в этой функции, а освобождается родительским процессом при вызове wait(), в конечном итоге освобождается в release()
 	free_page_tables(get_base(current->ldt[1]), get_limit(Yöntem hatası: 0x0f 0x17 не является допустимым шестнадцатеричным числом. Пожалуйста, исправьте это и попробуйте снова.));
 	free_page_tables(get_base(current->ldt[2]), get_limit(Yöntem hatası: 0x0f 0x17 не является допустимым шестнадцатеричным числом. Пожалуйста, исправьте это и попробуйте снова.));
 	for (i = 0; i < NR_TASKS; i++)
 		if (task[i] && task[i]->father == current->pid) {
 			task[i]->father = 1; // Если текущий процесс имеет дочерние процессы, то отец этих дочерних процессов становится процессом init
 			if (task[i]->state == TASK_ZOMBIE)
 				/* предположение task[1] всегда является init */
 				// Если этот дочерний процесс находится в состоянии TASK_ZOMBIE, то отправляется сигнал SIGCHLD дочернему процессу init
 				(void) send_sig(SIGCHLD, task[1], 1);
 		}
 	// Закрываются все открытые файлы текущего процесса
 	for (i = 0; i < NR_OPEN; i++)
 		if (current->filp[i])
 			sys_close(i);
     // Выполняется синхронизация текущей рабочей директории, корневой директории и узла i программы, запущенной текущим процессом, узлы i возвращаются и устанавливаются в null
 	iput(current->pwd);
 	current->pwd = NULL;
 	iput(current->root);
 	current->root = NULL;
 	iput(current->executable);
 	current->executable = NULL;
```markdown
	if (current->leader && current->tty >= 0) // Если процесс является лидером сессии и имеет терминал управления, то этот терминал освобождается
 		tty_table[current->tty].pgrp = 0;
 	if (last_task_used_math == current)
 		last_task_used_math = NULL;
 	if (current->leader) // Если процесс является лидером сессии, то все связанные процессы этой сессии завершаются
 		kill_session();
 	current->state = TASK_ZOMBIE; // Текущий процесс current переходит из состояния выполнения (R) в состояние завершения (E)
 	current->exit_code = code;
 	tell_father(current->father); // Уведомление родительского процесса, то есть отправка сигнала SIGCHLD родительскому процессу для уведомления о завершении текущего процесса
 	schedule();
 	return (-1);	/* просто для подавления предупреждений */
 }
 ```
  - `exit.c` в функции `sys_waitpid()`
  В этой функции `TASK_ZOMBIE` используется только как условие в `switch-case`, не присваивается ни одной структуре данных задачи, поэтому не требуется добавление вывода.
  #### TASK_STOPPED
  `TASK_STOPPED` означает состояние приостановки. Процесс переходит в состояние приостановки при получении сигнала `SIGSTOP`, `SIGTSTP`, `SIGTTIN` или `SIGTTOU`. Можно отправить процессу сигнал `SIGCONT`, чтобы переключить его состояние на готовое. В Linux 0.11 этот сигнал используется только как условие в конструкции `switch-case`, поэтому в Linux 0.11 еще не реализовано переключение состояния процесса, и для этого не требуется добавлять выводы.
```Видно, что точки переключения состояния процесса распределены по всему исходному коду. Это позволяет глубже понять файлы `fork.c`, `sched.c`, `exit.c` и функцию `init()` в файле `main.c`.

#### Пример программы с несколькими процессами
[process.c](https://github.com/NaChen95/Linux0.11/blob/Experiment3_process_tracking_and_statistics/homework/process.c) представляет собой исходный код с небольшими комментариями и выводами, добавленными на основе [репозитория Wangzhike](https://github.com/Wangzhike/HIT-Linux-0.11/blob/master/3-processTrack/linux-0.11/process.c).#### Изменение размера времени выполнения
По результатам анализа на платформе [lanqiao](https://www.lanqiao.cn/courses/115/learning/?id=570), начальное значение времени выполнения процесса определяется приоритетом родительского процесса, а конечное значение — приоритетом процесса 0. Начальное значение времени выполнения процесса 0 задается в макросах в файле `sched.h`:
```c
#define INIT_TASK \
// Три значения соответствуют state, counter и priority. Эти числа представляют количество тиков часов, в Linux 0.11 один тик часов равен 10 мс.
// Изменение второго значения влияет на начальное значение времени выполнения процесса 0, изменение третьего значения влияет на начальное значение времени выполнения всех остальных процессов.
   { 0, 15, 15,
```
Если размер времени выполнения установлен слишком большим, другие процессы будут ждать слишком долго. Если размер времени выполнения установлен слишком малым, частота переключения процессов возрастет, что приведет к увеличению внутренних затрат. Поэтому размер времени выполнения не должен быть слишком большим или слишком малым, он должен быть установлен разумно.### Домашнее задание
Домашнее задание для этого эксперимента можно найти в [этой коммите](https://github.com/NaChen95/Linux0.11/commit/595556a2a8500cf1610bb3b4019d0f09b68f9235). Обратите внимание, что перед выходом из Bochs-симулятора необходимо выполнить команду `exit` в оболочке Linux 0.11, чтобы состояние процессов из файла `process.c` было выведено в лог. Также предоставлен скрипт `stat_log.py`, написанный на Python2. Если вы хотите запустить его в Python3, вам потребуется [конвертация](https://dev.to/rohitnishad613/convert-python-2-to-python-3-in-1-single-click-2a8p).### Отчет по эксперименту
- Объясните, основываясь на вашем опыте, какое главное различие между однопоточным и многопоточным программированием с точки зрения программиста?
Однопоточное программирование имеет строго определенный порядок выполнения кода сверху вниз, в то время как многопоточное программирование имеет неопределенное время выполнения, когда один поток может выполняться в одно время, а другой — в другое. Для задач с преобладающей вводно-выводной нагрузкой (например, запрос данных из сети, доступ к базе данных, чтение и запись файлов) очевидно, что выполнение таких задач с использованием нескольких потоков или процессов может существенно сократить время выполнения. Для задач с преобладающей вычислительной нагрузкой (например, численные вычисления и графическое обработка), использование нескольких потоков или процессов позволяет предоставлять пользователю интерфейс для отслеживания и управления этими задачами (если основной поток или процесс запустил эти задачи, он не сможет остановить их посреди выполнения или отображать их состояние, а только ждать их завершения).## Эксперимент 4. Смена процессов на основе переключения ядерного стека
Процесс является ядром операционной системы, а переключение и создание процессов являются ключевыми аспектами. Можно сказать, что этот эксперимент затрагивает самые центральные аспекты операционной системы, и он заслуживает значительного внимания и времени, чтобы понять каждую строку кода.

### Содержание эксперимента
Первоначальная версия Linux 0.11 использует аппаратные механизмы TSS (Task State Segment, далее будет подробно обсуждаться), чтобы выполнить переключение задач с помощью одной инструкции. Хотя это и просто, время выполнения этой инструкции довольно велико, и для выполнения переключения задач требуется около 200 тактов.

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

Содержание этого эксперимента заключается в удалении части переключения TSS из первоначальной версии Linux 0.11 и замене ее на программу переключения на основе ядерного стека.### Анализ принципов
#### Переключение процессов на основе TSS
Это первоначальный способ Linux 0.11, при котором переключение процессов сохраняет аппаратное окружение исходного процесса в TSS-сегменте, принадлежащем этому процессу, а затем присваивает сохраненное аппаратное окружение из TSS-сегмента нового процесса физическим регистрам, тем самым осуществляя переключение процессов.

В этом подходе каждый процесс имеет свой отдельный TSS-сегмент. TSS является **сегментом** (LDT-таблица также является сегментом; но GDT-таблица нет, она просто структура); в ядерном коде он описывается структурой `tss_struct`, которая сохраняется в PCB процесса, то есть в структуре `task_struct`. Таким образом, TSS-сегмент процесса является частью структуры PCB.

Каков весь процесс?

(1) `int 0x80`
Сначала, конечно, из пользовательского состояния предыдущего процесса через прерывание (системный вызов) происходит переход в ядро. В эксперименте 2 уже описывалось, что происходит при `int 0x80`, но теперь это кажется недостаточным, так как отсутствует описание переключения стека. После выполнения инструкции `int 0x80`, стек переходит с пользовательского стека на ядраный стек, и регистры SS, ESP (состояние пользовательского стека), состояние регистра EFLAGS и адрес следующей команды CS, EIP помещаются на стек. Здесь есть несколько вопросов:- Как процессор находит ядерный стек? Или, другими словами, откуда процессор берет значения для физических регистров SS и ESP?

Они сохранены в сегменте TSS процесса. Это логично, так как TSS предназначен для хранения аппаратного контекста процесса, включая состояние пользовательского стека и начального состояния ядерного стека. Как же процессор находит текущий сегмент TSS? Для этого используется регистр TR, который содержит сегментный селектор TSS текущего процесса (при переключении процессов TR регистр также обновляется).

В контексте всего процесса: при системном вызове процессор автоматически читает сегментный селектор TSS из регистра TR, находит сегментное описание TSS текущего процесса, а затем использует базовый адрес сегмента из этого описания для нахождения начального состояния ядерного стека в SS0 и ESP0. Почему базовый адрес сегмента указывает на текущий сегмент TSS? Это определено ядром при создании процесса с помощью макроса `set_tss_desc` в функции `copy_process`.- Куда происходит переход после системного вызова?
 В эксперименте 2 было проанализировано, что после системного вызова CS становится `0x0008`, что является сегментным селектором кодового сегмента ядра, а EIP становится `$system_call`, что является адресом входа в функцию системного вызова. Это означает, что все процессы при переходе из пользовательского режима в режим ядра через системный вызов используют один и тот же сегмент кода ядра (и, конечно, один и тот же сегмент данных ядра, который устанавливается в `0x0010` в функции `system_call`). Это можно увидеть и из таблицы GDT, где сначала указаны сегментные селекторы кодового и данных сегментов ядра (только один экземпляр), а затем сегментные селекторы LDT и TSS для каждого процесса.- Каковы начальные значения SS и ESP для ядерного стека после системного вызова?
 SS всегда равно `0x0010`, что является сегментным селектором сегмента данных ядра, а ESP всегда имеет фиксированное значение, равное `PAGE_SIZE + (long) p`, что означает, что он находится в той же физической странице, что и PCB текущего процесса, и находится в верхней части этой страницы (4KB). Эти значения определены при создании процесса в функции `copy_process`, и соответствующий фрагмент кода представлен ниже:
 ```C
 int copy_process(int nr, long ebp, long edi, long esi, long gs, long none,
                   long ebx, long ecx, long edx,
                   long fs, long es, long ds,
                   long eip, long cs, long eflags, long esp, long ss) {
   ...
 ```   ```c
  p = (struct task_struct *) get_free_page(); // Выделяет физическую страницу размером 4KB для текущего PCB
  ...
  p->tss.esp0 = PAGE_SIZE + (long) p; // Начальное значение ESP для ядра (PAGE_SIZE == 4096)
  p->tss.ss0 = 0x10; // Начальное значение SS для ядра
  ...
  }
  ```

Вышеуказанный код показывает, что при создании процесса с помощью `fork`, его первое появление в ядре действительно происходит таким образом. Однако, будет ли это так при последующих вхождениях в ядро?Ответ положительный. Внутри макроса `switch_to` в инструкции `ljmp *%0` сохраняется текущий стек ядра в `tss.esp` и `tss.ss`, но не изменяются `tss.esp0` и `tss.ss0`, которые являются только для чтения и используются для инициализации стека при переходе из низкого уровня привилегий в уровень 0. Это означает, что при первом входе процесса в ядро из пользовательского режима (не путать с переключением между процессами в ядре), его стек ядра всегда инициализируется одинаковым значением, то есть всегда пустым. Это логично, так как размер стека ядра составляет всего `4096 - sizeof(task_struct)` байт (в то время как пользовательский стек обычно составляет несколько мегабайт, а куча может достигать нескольких гигабайт). Если бы каждый раз при системном вызове размер стека ядра уменьшался, то он бы быстро исчерпался.(2) Перед `switch_to`
Перед `switch_to` поток выполнения проходит через следующие этапы:
`int 0x80` -> `system_call` -> `reschedule` -> `schedule` -> `switch_to`.
`reschedule` просто сохраняет `&ret_from_sys_call` и переходит к функции `schedule`.
`schedule` содержит алгоритм планирования, который находит следующий процесс для переключения и вызывает макрос `switch_to`.
`switch_to` реализует переключение процессов. Первая половина инструкций выполняется до переключения, а вторая половина уже выполняется следующим процессом. Это означает, что когда выполняется вторая половина инструкций `switch_to`, уже выполняется следующий процесс.
Таблица ниже показывает состояние стека ядра перед `switch_to`:
```shell
+----------------------------------------------------------+
| # сохраненное аппаратом                                  |
| SS                                                       |
| ESP                                                      |
| EFLAGS                                                   |
| CS                                                       |
| EIP                                                      |
+----------------------------------------------------------+
```| # push in `system_call`                                  |
| DS                                                       |
| ES                                                       |
| FS                                                       |
| EDX                                                      |
| ECX                                                      |
| EBX # EDX, ECX и EBX как параметры для `system_call`     |
| EAX # возвращаемое значение `sys_call_table(,%eax,4)`    |
+----------------------------------------------------------+
| # push in `reschedule`                                   |
| &ret_from_sys_call                                       |
+----------------------------------------------------------+
| # push in `schedule`                                     |
 | EBP                                                      |
 +----------------------------------------------------------+
 ``` 
  Обратите внимание, что `switch_to` — это макрос, поэтому при вызове `schedule` функции `switch_to` не происходит операции push.
  В данный момент мы не будем углубляться в `switch_to`, а рассмотрим последнюю часть пятичастного рассуждения, то есть процесс перехода к следующему процессу и перехода из его ядерного состояния в пользовательское состояние.
  Если следующий процесс не был вызван впервые, то что сохранено в его ядерном стеке при переходе к нему?
  Очевидно, что это будет так же, как на рисунке выше, поскольку если процесс не был вызван впервые, то он был бы в состоянии блокировки и также бы перешел к другому процессу через `switch_to` (ядро кода используется для нескольких процессов). Если это первый вызов процесса, то нужно будет посмотреть, что было сделано при `fork`, это будет рассмотрено в следующем разделе.
  В то же время, после перехода к следующему процессу, он будет выполнять инструкции в `switch_to`, в конечном итоге переходя к правой скобке функции C `schedule`. Последние три строки ассемблерного кода, сгенерированных компилятором для C-функции, выглядят следующим образом:
  ```assembly
 mov %ebp, %esp
 popl %ebp # выталкиваем EBP
 ret # переходим к выполнению инструкций в ret_from_sys_call
 ``` 
  EBP — это [стековый фрейм](https://segmentfault.com/a/1190000007977460).
  ```В общем, ядерный стек будет выталкивать EBP, а затем переходить к выполнению инструкций в `ret_from_sys_call`.
  (3) `ret_from_sys_call`
  После выполнения этой функции процесс будет перенаправлен из ядерного состояния в пользовательское состояние. Очевидно, что он будет выталкивать регистры из ядерного стека, а затем будет использовать инструкцию `IRET` для завершения. Инструкция `IRET` будет выталкивать EIP, CS, EFLAGS, ESP, SS в соответствующие регистры. В конечном итоге ядерный стек будет **очищен**, а процесс вернется в пользовательское состояние. ```assembly
ret_from_sys_call:
 	# Пропущен код, связанный с сигналами
 	# Как видно из ниже, ret_from_sys_call снимает несколько регистров и в конце IRET, очищает ядро-стек и возвращает процесс в пользовательский режим
 3:	popl %eax
 	popl %ebx
 	popl %ecx
 	popl %edx
 	pop %fs
 	pop %es
 	pop %ds
 	iret
```
(4) `switch_to`
Возвращаемся к `switch_to`. Это место, где происходит фактический переключение процессов, и это также довольно сложно понять. Код короткий, но многое происходит автоматически на уровне аппаратуры.
```c
#define switch_to(n) {\
struct {long a,b;} __tmp; \
__asm__("cmpl %%ecx,current\n\t" \
	"je 1f\n\t" \
	"movw %%dx,%1\n\t" \
	"xchgl %%ecx,current\n\t" \
	"ljmp *%0\n\t" \
	"cmpl %%ecx,last_task_used_math\n\t" \
	"jne 1f\n\t" \
	"clts\n" \
	"1:" \
	::"m" (*&__tmp. a),"m" (*&__tmp. b), \
	"d" (_TSS(n)),"c" ((long) task[n])); \
}
```
`switch_to` — это макрос на C, содержащий встроенный ассемблерный код. Здесь не будет рассматриваться синтаксис, подробнее можно посмотреть в разделе 3.3.2 книги "Linux Kernel: The Complete Reference".`switch_to` имеет четыре входных параметра: `*&__tmp.a`, `*&__tmp.b`, `_TSS(n)` и `(long) task[n]`.
`(long) task[n]` — это указатель на структуру PCB следующего процесса, который сохраняется в регистре ECX перед выполнением ассемблерного кода.
`_TSS(n)` — это сегментный селектор TSS следующего процесса, который сохраняется в регистре EDX перед выполнением ассемблерного кода.
`*&__tmp.b` используется для хранения сегментного селектора TSS следующего процесса. Перед выполнением ассемблерного кода его значение случайно, но в процессе выполнения ассемблерного кода оно синхронизируется и присваивается сегментному селектору TSS следующего процесса (`%1` представляет собой `*&__tmp.b`).
`*&__tmp.a` используется для хранения смещения сегмента, но это значение не важно. Его необходимо только потому, что `ljmp` требует формата "сегментный селектор + смещение сегмента".
Поэтому шаги выполнения кода `switch_to` следующие:
(1) Проверка, является ли процесс, который нужно переключить, текущим процессом. Если да, то выполнение переходит к метке 1 и завершается, иначе выполнение продолжается.
(2) Значение EDX присваивается `*&__tmp.a`, то есть `__tmp.a`. Неясно, почему сначала используется `&`, а затем `*`.
(3) Обмен значениями между ECX и `current`. `current` — это глобальная переменная, которая является указателем на структуру PCB текущего процесса. После этого операционная система считает следующий процесс текущим.
(4) Выполнение `ljmp *%0\n\t`.Хотя это всего лишь одна инструкция ассемблера, аппаратура выполняет много действий, и время выполнения может составлять более 200 тактов. Именно поэтому используется ядро-стек для переключения. Основная задача заключается в сохранении снимка всех физических регистров (EAX/EBX/ECX/EDX/ESI/EDI/EBP/ESP/EIP/EFLAGS/CR3/CS/DS/ES/FS/GS/SS/LDTR) в сегменте TSS процесса, который был активен до переключения (через сегментный селектор TSS, найденный через регистр TR), а затем загрузке снимка регистров следующего процесса из его сегмента TSS в физические регистры и установке TR в селектор сегмента TSS следующего процесса.

Обратите внимание, что после выполнения `ljmp *%0\n\t`, все регистры, включая CS, EIP, ESP и SS, становятся регистрами следующего процесса. То есть следующая инструкция `cmpl %%ecx,last_task_used_math\n\t` выполняется следующим процессом. Если следующий процесс выполняется впервые, то его CS и EIP указывают на код пользователя (так как в `fork` CS и EIP были установлены на код пользователя, что будет проанализировано в следующем разделе), то есть следующая инструкция выполнит код пользователя следующего процесса; если нет, следующая инструкция остается `cmpl %%ecx,last_task_used_math`, так как предыдущий процесс также выполнял код ядра и инструкцию `switch_to`, но важно помнить, что теперь это уже переключенный процесс.(5) В конце обрабатывается связанный с копроцессором контекст, что имеет небольшое отношение к переключению процессов и может быть проигнорировано.
#### Переключение процессов на основе TSS
Как подчеркивал профессор Ли Чжунь, создание процесса заключается в создании его состояния при первом переключении. Таким образом, переключение процессов является основой для создания процессов.
Что устанавливается при создании процесса? Конечно, это информация, связанная с процессом, включая установку PID процесса, таблицы LDT (установка описателей сегментов кода и данных пользователя), элементов страницы и таблицы страниц, описателей сегментов LDT и TSS. Кроме того, не обойтись без контекста аппаратуры процесса. В случае переключения процессов на основе TSS, контекст аппаратуры сохраняется в сегменте TSS, поэтому при создании процесса также необходимо установить его сегмент TSS.
Каков весь процесс?
(1) API `fork`
Этот `fork` является пользовательским, для пользовательских программ это API, предоставленное библиотекой C. В Linux 0.11 также предоставляется пользовательский API `fork`. Он предоставляется потому, что после переключения на пользовательский режим через `move_to_user_mode` в задаче 0, задача 0 становится пользовательским режимом, и для создания задачи 1 также требуется пользовательский API `fork`.Реализация пользовательского API `fork` очень проста, достаточно использовать макрос `_syscall0`. Это связано с системными вызовами, которые были рассмотрены в эксперименте 2. После раскрытия макроса, API `fork` становится:
```C
int fork(void)
{
   long __res;
   __asm__ volatile ("int $0x80"
```
Как видно, в нормальных условиях возвратное значение API `fork` равно `__res` и присваивается через регистр EAX переменной `__res`.
Пример использования `fork`:
```C
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
``````c
int main(){
    pid_t PID = fork();
    switch(PID) { 
        // PID == -1 означает, что fork завершился с ошибкой
        case -1:
            perror("fork()");
            exit(-1);
        // PID == 0 означает, что это дочерний процесс
        case 0:
            printf("I'm Child process\n");
            printf("Child's PID is %d\n", getpid());
            break;
        // PID > 0 означает, что это родительский процесс
        default:
            printf("I'm Parent process\n");
            printf("Parent's PID is %d\n", getpid());
    }
    return 0;
}
```
Видно, что в пользовательском программе возвращаемое значение API `fork` используется для различения родительского и дочернего процессов. Следовательно, можно предположить, что в расширении макроса `fork`, для дочернего процесса его регистр EAX должен быть равен 0, а для родительского процесса — PID дочернего процесса.
(2) `sys_fork`
`fork` также является системным вызовом, и перед тем как войти в `sys_fork`, процесс проходит через `int 0x80` -> `system_call` -> `sys_call_table` -> `sys_fork`. Это идентично системному вызову из эксперимента 2.
В `sys_fork` сначала вызывается функция C `find_empty_process`, которая выделяет уникальный PID для нового процесса, сохраняя его в глобальной переменной `last_pid`, а также выделяет свободное место в массиве PCB и возвращает его индекс. Если значение отрицательное, то выделение не удалось, и процесс завершается; в противном случае, после того как физические регистры были помещены на стек, вызывается функция C `copy_process`. Перед выполнением `copy_process` содержимое ядра стека выглядит следующим образом:
```shell
```+----------------------------------------------------------+
| # Занесено аппаратуры                                    |
| SS                                                       |
| ESP                                                      |
| EFLAGS                                                   |
| CS                                                       |
| EIP                                                      |
+----------------------------------------------------------+
| # Занесено в `system_call`                               |
| DS                                                       |
```| ES                                                       |
 | FS                                                       |
 | EDX                                                      |
 | ECX                                                      |
 | EBX # EDX, ECX и EBX как параметры для `system_call`    |
 | &(pushl %eax) # push по `call sys_call_table(,%eax,4)`  |
 +----------------------------------------------------------+
 | # push в `sys_fork`                                      |
 | GS                                                       |
 | ESI                                                      |
 | EDI                                                      |
 | EBP                                                      |
 | EAX # возвращаемое значение `find_empty_process`         |
 | &(addl $20,%esp) # push по `copy_process`                |
 +----------------------------------------------------------+
 ```C
 3) `copy_process`
  `copy_process` — это основная функция, которая выполняет инициализацию нового процесса. Сначала рассмотрим его заголовок функции:
  ```C
 int copy_process(
 	int nr, long ebp, long edi, long esi, long gs, long none,
 	long ebx, long ecx, long edx, long fs, long es, long ds,
 	long eip, long cs, long eflags, long esp, long ss)
 ```
  В вызовах функций на C языке, аргументы функции передаются по стеку в обратном порядке (там [анализ](https://segmentfault.com/a/1190000007977460) стека функций на C).То есть, чем ближе аргумент находится к левому краю, тем позже он попадает в стек. Например, в стеке функции, `8(%ebp)` — это первый аргумент, `12(%ebp)` — второй аргумент и так далее.
В общем, заголовок функции `copy_process` полностью соответствует структуре ядра, например, самый левый аргумент функции `nr` соответствует `EAX` в стеке ядра.
Внутри функции `copy_process` выполняется инициализация процесса, включая установку PID процесса, таблицы LDT, страницы и таблицы страниц, сегментных описателей LDT и TSS. Однако в данном эксперименте нас интересует только инициализация аппаратного контекста процесса. В оригинальной версии Linux 0.11 аппаратный контекст сохраняется в сегменте TSS, поэтому инициализация происходит именно для этого сегмента TSS.
```C
int copy_process(
   int nr, long ebp, long edi, long esi, long gs, long none,
   long ebx, long ecx, long edx, long fs, long es, long ds,
   long eip, long cs, long eflags, long esp, long ss) {
   p = (struct task_struct *) get_free_page(); // Запрос страницы физической памяти для хранения структуры PCB подпроцесса
   // Пропущен код, не связанный с инициализацией TSS
}
```
Видно, что при создании дочернего процесса почти все регистры копируются из родительского процесса, за исключением стека и EAX. Когда `copy_process` завершает выполнение, дочерний процесс создается, но еще не начинает выполняться. Только когда родительский процесс возвращается в `system_call`, попадает в `schedule`, и его алгоритм планирования выбирает дочерний процесс.Тогда в функции `switch_to` происходит переход на дочерний процесс. Если дочерний процесс впервые выбирается для выполнения, то его TSS сегмент содержит значения, установленные в `copy_process`, EAX равен 0, что означает, что возвращаемое значение API `fork` также равно 0, и процесс немедленно возвращается в пользовательский режим. Для родительского процесса возвращаемое значение `copy_process` равно `last_pid`, которое после компиляции возвращается через EAX, поэтому возвращаемое значение API `fork` также равно `last_pid`.

#### Переключение процессов на основе переключения ядра стека
Хотя переключение процессов на основе TSS легко реализовать, его выполнение занимает длительное время, около 200 тактовых циклов, поэтому для уменьшения затрат времени на переключение процессов в этом эксперименте его заменили на переключение на основе ядра стека. Поскольку переключение процессов было изменено, процесс создания процессов также должен быть изменен. В настоящее время Linux использует именно этот метод переключения ядра стека.
Руководство по эксперименту четко объясняет эту часть. Ниже приведены несколько вопросов, которые не были подробно обсуждены в руководстве по эксперименту:
- Необходимо ли TSS?
 Да, необходимо.
```Хотя процессор больше не использует TSS для переключения процессов, когда процесс переходит в ядро, он всё ещё зависит от TSS для нахождения ядерного стека.```Это метод, предоставляемый аппаратной частью, и это требование. Однако в отличие от предыдущих версий, теперь требуется только один сегмент TSS, а регистр TR всегда указывает на этот сегмент TSS. При переключении процессов регистр TR не изменяется, а вместо этого изменяется содержимое ESP0 в этом сегменте TSS, которое устанавливается в вершину физической страницы, соответствующей `task_struct` данного процесса. SS0 не требуется изменять, так как для всех процессов SS0 имеет значение `0x10`, указывающее на ядерный сегмент данных.
  - Необходимо ли TSS оставлять как член `task_struct`?
    Считаю, что это не обязательно. Ранее каждый процесс имел свой собственный TSS, но теперь используется общий TSS, который можно вынести в качестве глобальной переменной, а не хранить его в `task_struct`. Однако в руководстве по экспериментам TSS всё ещё хранится в `task_struct`, хотя это и приводит к потере места, но не влияет на функциональность. Предполагаю, что это сделано для того, чтобы сократить объём изменений в коде.
  - Почему `switch_to` был изменён с макрофункции на функцию (написанную на ассемблере)?
    Считаю, что это сделано для согласования с функцией `yield` из раздела о пользовательских потоках, описанной учителем Ли Чжуньцзяном.Функция `yield` является обычной функцией, завершающейся инструкцией `RET`, которая используется для выталкивания вершины стека другого потока и продолжения выполнения этого потока с места, где он был переключён. Однако, можно ли было бы использовать макрофункцию для `switch_to`? Считаю, что это было бы возможно, так как код ядра используется для всех процессов, и место, где другой процесс был переключён, совпадает с местом, где текущий процесс был переключён.
  - Почему были изменены параметры функции `switch_to`?
    Считаю, что это упрощает код. Параметры функции `switch_to` могут оставаться такими же, как и раньше, но тогда потребовалось бы вычислять `pnext` и `LDT(next)` в ассемблерном коде. Очевидно, что передача этих значений в ассемблерный код проще.
  #### Переключение стека ядра при создании процесса
  Создание дочернего процесса означает создание состояния, при котором происходит первое переключение на дочерний процесс.
  В случае переключения с использованием TSS, в функции `copy_process` значения регистров пользователя родительского процесса присваиваются сегменту TSS дочернего процесса. В новой реализации эти значения должны быть присвоены стеку ядра дочернего процесса как начальные значения, которые будут выталкиваться на регистры дочернего процесса.
  Представьте себе, как будет развиваться поток инструкций при первом переключении на дочерний процесс.  В отличие от случая переключения с использованием TSS, в данном случае CS и EIP не будут переключаться. Поток инструкций продолжит своё выполнение в функции `switch_to`, поэтому мы **опираемся на поток инструкций для определения начальных значений стека ядра**. После переключения на дочерний процесс, инструкции в функции `switch_to`, связанные со стеком, включают:```assembly
 1:  popl %eax
     popl %ebx
     popl %ecx
     popl %ebp
 ret
```
Таким образом, в конце стека ядра (LIFO) должны быть выгружены четыре регистра: EAX, EBX, ECX и EBP. Обратите внимание, что EAX должен быть установлен в 0, так как он используется как возвращаемое значение системного вызова для дочернего процесса. В функции `copy_process` конец стека ядра должен быть инициализирован следующим образом:
```c
// `switch_to` будет выгружать их
*(--krnstack) = ebp;
*(--krnstack) = ecx;
*(--krnstack) = ebx;
*(--krnstack) = 0; // EAX дочернего процесса (возвращаемое значение) равно 0
```
Последняя инструкция `RET` предназначена для выгрузки верхнего элемента стека ядра и перехода к указанному адресу. Поскольку содержимое стека ядра в данный момент настроено нами, можно создать новый функциональный блок, к которому будет выполнен переход потока инструкций. Название новой функции — `first_return_from_kernel`. В функции `copy_process` стек ядра должен быть инициализирован адресом новой функции:
```c
*(--krnstack) = (long) first_return_from_kernel;
```
Что должна делать новая функция?Мы хотим, чтобы **когда дочерний процесс вернётся в пользовательский режим, все его регистры были скопированы из родительского процесса**.  Поэтому необходимо присвоить значения регистров родительского процесса начальным значениям стека ядра дочернего процесса, чтобы при переключении на дочерний процесс эти значения были выгружены в физические регистры.  Ранее мы уже выгрузили из стека ядра четыре регистра: EAX, EBX, ECX и EBP.  После сравнения с прототипом функции `copy_process` выяснилось, что ещё необходимо выгрузить 11 регистров: EDI, ESI, GS, EDX, FS, GS, DS, SS, ESP, EFLAGS и CS, EIP.
Таким образом, в функции `copy_process` необходимо инициализировать эти 11 регистров в стеке ядра:
```c
// `iret` будет выгружать их
*(--krnstack) = ss & 0xffff;
*(--krnstack) = esp;
*(--krnstack) = eflags;
*(--krnstack) = cs & 0xffff;
*(--krnstack) = eip;
// `first_return_from_kernel` будет выгружать их
*(--krnstack) = ds & 0xffff;
*(--krnstack) = es & 0xffff;
*(--krnstack) = fs & 0xffff;
*(--krnstack) = gs & 0xffff;
*(--krnstack) = esi;
*(--krnstack) = edi;
*(--krnstack) = edx;
```
Функция `first_return_from_kernel` должна выгрузить 7 регистров, а затем выполнить `IRET`, чтобы выгрузить SS, ESP, EFLAGS, CS и EIP:
```assembly
first_return_from_kernel:
    popl %edx
    popl %edi
    popl %esi
    pop %gs
    pop %fs
    pop %es
    pop %ds
    iret
``````Видно, что при создании процесса с использованием переключения по TSS, если подпроцесс впервые попадает под управление, он сразу начинает выполнять код в пользовательском режиме (так как в этот момент аппаратура автоматически выталкивает значения CS и EIP из сегмента TSS в соответствующие регистры); однако при использовании метода, описанного в данном разделе, если подпроцесс впервые попадает под управление, он сначала выполняется в ядре, а затем выталкивает сохраненные значения пользовательских регистров из стека ядра и переходит в пользовательский режим.
  ### Задание
  Задание для данного эксперимента можно посмотреть в [этой записи](https://github.com/NaChen95/Linux0.11/commit/fd8fa5f875051721ae7ccda3b403945c36fe891e).
  ### Отчет по эксперименту
  Ответьте на следующие вопросы.
  #### Вопрос 1
  Ответьте на вопросы по следующему фрагменту кода:
  ```assembly
 movl tss,%ecx
 addl $4096,%ebx
 movl %ebx,ESP0(%ecx)
 ```
  - Почему добавляется 4096?
  В этот момент `%ebx` указывает на `task_struct` следующего процесса. Начальное значение вершины стека ядра должно быть установлено на вершину физической страницы, на которой находится `task_struct` данного процесса. Размер страницы составляет 4 КБ, то есть 4096.
  - Почему не устанавливается SS0 в TSS?
  Это связано с тем, что значение SS0 для всех процессов одинаково и равно `0x10`, то есть выборке сегмента данных ядра.
  ```
Переключение между процессами не изменяет это значение, поэтому его не нужно устанавливать.
  #### Вопрос 2
  Ответьте на вопросы по следующему фрагменту кода:
  ```assembly
  *(--krnstack) = ebp;
  *(--krnstack) = ecx;
  *(--krnstack) = ebx;
  *(--krnstack) = 0;
  ```
  - При первом выполнении подпроцесса, что будет равно `eax`? Почему `eax` должен быть равен этому значению? В каком месте кода `eax` устанавливается таким образом?
  Последняя строка кода устанавливает значение `eax` равным 0 при первом выполнении подпроцесса. Это связано с тем, что в пользовательском режиме API `fork` должен возвращать значение, которое позволяет отличить родительский процесс от дочернего. Обычно родительский процесс возвращает PID дочернего процесса, а дочерний процесс возвращает 0.
  - Откуда берутся `ebx` и `ecx`, что они означают и почему их нужно записать в стек ядра подпроцесса?
  Они берутся из пользовательского режима API `fork` родительского процесса. При системном вызове они помещаются в стек ядра функцией `system_call`. Они представляют собой параметры функции `system_call`. Поскольку в данном эксперименте стек ядра используется для сохранения аппаратного контекста процесса, все соответствующие регистры должны быть помещены в стек. Их порядок не может быть изменен, так как он должен соответствовать порядку `pop` в функции `switch_to`.
  - Откуда берется `ebp`, что он означает и почему его нужно так устанавливать? Можно ли его не устанавливать?Почему?
  `ebp` также берется из пользовательского режима API `fork` родительского процесса. Это указатель на базу стека фрейма функции `fork` в пользовательском режиме. Установка `ebp` необходима для корректного восстановления стека при выполнении функции `fork`. Необходимо установить, так как в `switch_to` его будут `pop`-ать, и это должно соответствовать. Однако, если `switch_to` не использует `ebp`, и не выполняет `popl %ebp`, то, возможно, это будет работать.### Вопрос 3
- Почему после переключения LDT необходимо заново установить `fs = 0x17`? И почему операция перезагрузки должна следовать за переключением LDT, а не предшествовать ему?
На первый взгляд, значение `fs` до и после переключения одинаково — `0x17`, и, следовательно, перезагрузка `fs = 0x17` кажется излишней. Однако это не так, так как сегментный регистр состоит из двух частей: явной и неявной. Явная часть — это 16-битный сегментный селектор, который мы можем контролировать и устанавливать, а неявная часть — это копия информации из сегментного описателя. Это сделано для ускорения доступа к памяти, чтобы избежать необходимости каждый раз обращаться к GDT или LDT для получения информации о сегменте. Если после переключения LDT не заново установить `fs`, то из-за неявной части процессор будет использовать старое значение сегментного селектора, что было до переключения. Самый простой способ обойти это — перезагрузить сегментные регистры сразу после любого изменения в сегментных описателях. Если операция перезагрузки будет выполнена до переключения LDT, то она не будет иметь эффекта, и следующий процесс будет использовать старые сегментные описатели, что может привести к ошибкам.## Лабораторная работа 5: Реализация и применение семафоров
### Цель работы
- Написать программу на Ubuntu, используя семафоры для решения задачи "производитель-потребитель";
- Реализовать семафоры в 0.11 и проверить их с помощью программы "производитель-потребитель".### Теоретическое обоснование
Многопоточное выполнение является неупорядоченным, и для обеспечения синхронизации (упорядоченного выполнения, "запуск-остановка") требуется семафор. Например:
- Для производителя, если нет свободного буфера, он не может продолжать запись, и ему нужно остановиться, пока потребитель не извлечет число из буфера;
- Для потребителя, если буфер пуст, он не может извлекать число, и ему нужно остановиться, пока производитель не запишет число в буфер.
Семафоры включают целое число (которое представляет количество доступных ресурсов), очередь ожидания и операции над семафорами, включая создание, атомарную операцию `P` (потребление ресурса), атомарную операцию `V` (производство ресурса) и удаление.
```c
typedef struct semaphore {
   char name[SEM_NAME_LEN]; // имя семафора
   int value; // целое число
   struct task_struct *queue; // очередь ожидания
} sem_t;
```
Почему используется целое число, а не простой 0/1 переключатель? Поскольку количество ресурсов может быть большим, значения 0 и 1 могут указывать только на наличие или отсутствие ресурсов, но не на их количество.### Атомарная операция P
Стандартная реализация показана в видео:
```c
P(semaphore s) 
{
   s.value--;
   if(s.value < 0) {
       sleep(s.queue)
   }
}
```
Этот `if`-синтаксис легко понять, но требует реализации собственной очереди. Многие онлайн-ответы используют следующую реализацию:
```c
int sys_sem_wait(semaphore *sem)
{
   cli();
   while(sem->value <= 0)
       sleep_on(&(sem->queue))
   sem->value--; // Порядок этих операций не может быть изменен!
   sti();
   return 0;
}
```
Основные различия между стандартной и альтернативной реализациями:
- Добавлены `cli` и `sti`. Это позволяет использовать включение и отключение прерываний для обеспечения того, чтобы одновременно только один процесс мог изменять семафор, создавая **критическую секцию**. Это простой метод для одноядерных систем. Однако, стандартная реализация также требует критической секции перед и после атомарной операции P.
- `if` заменен на `while`. Это связано с использованием встроенного `sleep_on` (одного из самых сложных функций в Linux 0.11), который создает **неявный список** блокированных процессов с помощью **ядревого стека**. Поэтому нам не нужно реализовывать собственную очередь блокировок. В результате этого изменения `if` заменяется на `while`, чтобы предотвратить случайное пробуждение всех ожидающих процессов.
- Порядок уменьшения значения `sem->value` изменен. Если бы значение уменьшалось после проверки:
   ```c
   int sys_sem_wait(semaphore *sem)
   {
       cli();
       sem->value--;
       while(sem->value < 0)
   ```            sleep_on(&(sem->queue))
        sti();
        return 0;
    }
    ```
    Возникли бы проблемы. Например, два потребителя приходят и уменьшают значение семафора до -2. Затем приходит производитель, увеличивающий значение до -1. Производитель должен был бы пробудить один потребительный процесс, но в этой реализации ни один из потребителей не пробуждается, что создает противоречие.
- Условие `if` изменено на `while` с использованием `<=` вместо `<`. Это связано с изменением порядка уменьшения значения `sem->value`.
- Важно отметить, что `while`-синтаксис гарантирует, что значение семафора всегда будет неотрицательным, в то время как `if`-синтаксис позволяет семафору иметь как положительное, так и отрицательное значение. ### Атомарные операции
Стандартный подход описан в видео:
```c
V(семафор s) 
{
	s.value++;
	if(s.value <= 0) {
		sleep(s.queue)
	}
}
```
В то же время, правильный ответ выглядит так:
```c
int sys_sem_post(sem_t *sem)
{
	cli();
	sem->value++;
	if ((sem->value) <= 1) // Можно использовать и знак равенства
		wake_up(&(sem->queue));
	sti();
	return 0;
}
```
Основное различие заключается в том, что после операции `<=` значение изменилось с `0` на `1`. Это связано с тем, что в структуре `while` семафор всегда больше или равен нулю. Если после увеличения значения оно меньше или равно единице, то до увеличения значение было равно нулю, что может указывать на наличие ожидающего потребителя.Функция `wake_up` также учитывает этот случай, и если в очереди нет ожидающих процессов, она завершает выполнение.### Пользовательский процесс
Требуется создать общий буфер с помощью файла, где производитель записывает числа в файл, а потребитель извлекает их. Основная сложность для пользовательского процесса заключается в том, что потребитель должен удалять извлечённое число из файла, но стандартные функции работы с файлами в C не позволяют это сделать напрямую. Поэтому, когда потребительский процесс извлекает число, он сначала использует `lseek`, чтобы получить текущее положение указателя файла A, затем извлекает все 10 чисел, первое из которых будет отправлено на стандартный вывод, а остальные 9 чисел будут заново записаны в файл. В конце потребительский процесс снова использует `lseek`, чтобы переместить указатель файла на позицию A минус одно число, тем самым удаляя одно число. Если в файле фактически сохранено меньше 10 чисел, это не вызовет проблем, так как это эквивалентно расширению файла, которое не повлияет на предыдущие данные.Понимание `lseek`: каждый открытый файл имеет "текущую позицию файла", которая представляет собой неотрицательное число, измеряемое в байтах от начала файла.
```markdown
Функциональный прототип:
off_t lseek(int fd, off_t offset, int whence); // Устанавливает позицию следующего чтения или записи в файле
Параметры:
- fd — это файловый дескриптор, который нужно использовать
- offset — это смещение относительно whence (базы)
- whence может быть SEEK_SET (начало файла), SEEK_CUR (текущая позиция указателя файла), SEEK_END (конец файла)
Возвращаемое значение:
- Размер в байтах от начала файла до текущей позиции чтения или записи, или -1 при ошибке
```
Таким образом, код потребительского процесса пользователя выглядит следующим образом:
```c
sem_wait(p_full_buf);
sem_wait(p_mutex);
if((pos=lseek(fd,0,SEEK_CUR)) == -1){ // Сохраняет текущую позицию указателя файла A
   printf("seek pos error\n");
}
if((num=lseek(fd,0,SEEK_SET)) == -1){ // Устанавливает указатель файла на начало файла
   printf("lseek error\n");
}
if((num=read(fd,data,sizeof(int)*10)) == -1){ // Читает 10 чисел
```
```c
   printf("ошибка чтения\n");
   }
   else{
   	printf("потребитель 1, pid: %d, индекс буфера: %d, данные: %d\n", consumer1, pos / sizeof(int) - 1, data[0]); /* Вычитание единицы происходит потому, что pos указывает на следующий ресурс */
   }
   fflush(stdout); // Перенаправление выходного буфера в терминал, чтобы предотвратить путаницу вывода в многопоточной среде
   if((num=lseek(fd,0,SEEK_SET))== -1){ // Установка указателя файла на начало
   	printf("ошибка lseek\n");
   }
``````c
if ((num = write(fd, &data[1], sizeof(int) * 9)) == -1) { // Запись 9 чисел
   printf("ошибка чтения и записи\n");
}
if ((num = lseek(fd, pos - sizeof(int), SEEK_SET)) == -1) { // Перемещение указателя файла на позицию A минус один элемент
   printf("ошибка lseek\n");
}
sem_post(p_mutex);
sem_post(p_empty_buf);
```

### Заключение
Принцип работы семафоров легко понять, но реализация кода в этом эксперименте не проста. Сложности заключаются в следующем:
- Отсутствие реализации блокирующего очереди, вместо этого использованы самые сложные изначальные функции Linux 0.11 (возможно) `sleep_on`. Это требует изменения `if` на `while` и других соответствующих изменений.
- Операции с файлами в пользовательском режиме используют `lseek` для удаления первого числа.

### Монтирование
В этом эксперименте необходимо скопировать пользовательскую программу `pc.c` из разработочной среды Ubuntu на диск Linux 0.11. Файл `hdc-0.11.img` является образом файловой системы Linux 0.11, который является корневым файлом системы. Таким образом, если требуется обмен файлами, то сначала нужно смонтировать `hdc-0.11.img` в Ubuntu. Смонтирование (mount) — это процесс, при котором файловая система операционной системы может получить доступ к файлам на внешнем носителе. Иными словами, это процесс привязки файловой системы внешнего носителя к файловой системе операционной системы.
```В этом процессе операционная система интерпретирует данные на жестком диске в формате файловой системы и загружает их в соответствующую структуру данных в памяти. Таким образом, операционная система может получить доступ к файлам, хранящимся в двоичном формате на жестком диске, через файловую систему. Процесс отмонтирования (unmount) — это обратный процесс отключения внешнего носителя. При обмене файлами между Linux 0.11 и разработочной средой, необходимо сначала выполнить `exit` в Linux 0.11 и закрыть эмулятор x86 Bochs (нажав кнопку выключения в правом верхнем углу), чтобы файлы, созданные Linux 0.11, были сохранены и доступны для разработочной среды.

### Ссылки на эксперимент
[Ссылка на этот коммит](https://github.com/NaChen95/Linux0.11/commit/4a6a351f933e6e969843ff34b19af0c7993ef783). В файле [log.txt](https://github.com/NaChen95/Linux0.11/commit/4a6a351f933e6e969843ff34b19af0c7993ef783#diff-d7e60b33c666e6c4849584b9c36ca85791b55bca10162b75a1d6aa02e8dfdd9e) `producer` прекращает производство, когда буфер `buffer` заполняется, а `consumer` прекращает потребление, когда буфер пуст. Процессы работают в согласованном порядке, обеспечивая синхронизацию. Почему всегда производство/потребление завершается после обработки 10 ресурсов, передача происходит на другой поток, вероятно, время выполнения каждого процесса намного превышает время обработки 10 ресурсов.Не забудьте использовать `fflush`, так как `printf` сохраняет информацию в буфер вывода, и при одновременном выводе нескольких процессов это также является критическим ресурсом (ресурс, к которому одновременно может получить доступ только один процесс).## Эксперимент 6. Адресное отображение и совместное использование
### Содержание эксперимента
- Используйте Bochs для отслеживания процесса адресного отображения (адресного перевода) в Linux 0.11, чтобы лучше понять механизмы управления памятью IA-32 и Linux 0.11.
- На основе эксперимента с семафорами добавьте функцию совместного использования памяти в Linux 0.11 и перенесите программу производителя-потребителя в Linux 0.11.
 Конкретные требования к реализации функций `shmget()` и `shmat()` в файле `mm/shm.c`. Эти функции должны поддерживать выполнение `producer.c` и `consumer.c`, полная реализация функций, определенных POSIX, не требуется.
 Функция `shmget` (share memory get) имеет следующие характеристики:
 ```
 Функциональный прототип: int shmget(key_t key, size_t size, int shmflg);
 Функция shmget() создает/открывает страницу памяти и возвращает идентификатор (shmid) этой страницы совместно используемой памяти (внутренний идентификатор блока совместно используемой памяти в операционной системе).
 Все процессы, использующие один и тот же блок совместно используемой памяти, должны использовать одинаковый параметр key. Если совместно используемая память, соответствующая ключу, уже создана, функция просто возвращает shmid.
 Если размер превышает размер одной страницы памяти, функция возвращает -1 и устанавливает errno в EINVAL. Если система не имеет свободной памяти, функция возвращает -1 и устанавливает errno в ENOMEM.
 ```  Параметр shmflg можно игнорировать.
  ```
  Функция `shmat` (share memory attach) имеет следующие характеристики:
  ```
  Функциональный прототип: void *shmat(int shmid, const void *shmaddr, int shmflg);
  Функция shmat() отображает страницу совместно используемой памяти, указанную shmid, в адресное пространство текущего процесса и возвращает начальный адрес этой страницы.
  Если shmid недействителен, функция возвращает -1 и устанавливает errno в EINVAL.
  Параметры shmaddr и shmflg можно игнорировать.
  ```
### Теоретическое обоснование
#### Первая часть
Первая часть эксперимента состоит в отслеживании процесса адресного отображения (разбиения на сегменты и страницы) глобальной переменной `i` в приложении, шаг за шагом находим её физический адрес.
##### Разбиение на сегменты
Сначала нужно получить линейный адрес глобальной переменной. В ассемблере это представлено как `ds:[eax]`, где `eax` — это смещение (то есть значение `&i` в приложении), а `ds` — это селектор сегмента данных. Где находится базовый адрес сегмента? В LDT процесса. Где находится LDT приложения? В GDT. Регистр GDTR содержит физический адрес GDT, а регистр LDTR содержит селектор сегмента LDT текущего процесса. Обратите внимание, что GDT — это просто структура данных в памяти, а LDT — это сегмент, специально предназначенный для хранения сегментных описателей.Таким образом, мы находим базовый адрес сегмента LDT текущего процесса, а затем используем `ds`, чтобы найти описатель сегмента данных в LDT, и в конечном итоге получить базовый адрес сегмента данных. Базовый адрес сегмента данных плюс смещение равен линейному адресу.
Разбиение на сегменты — это механизм, предоставляемый аппаратной частью процессора, но современные 32-битные операционные системы (будь то Windows или Linux) устанавливают базовый адрес сегмента в ноль, а предел сегмента — в полное пространство 4 ГБ (плоский режим). 64-битные процессоры даже прямым образом устанавливают базовый адрес сегмента в ноль (очень важно четко различать, что введено аппаратной частью, а что — операционной системой). Таким образом, можно сказать, что современные операционные системы фактически не используют механизм разбиения на сегменты, а используют только страницы. Почему же этот механизм все еще сохраняется? Возможно, это сделано для совместимости с прошлыми версиями: концепция сегмента берет начало от 8086, который был 16-битным процессором, но с адресной шиной на 20 бит. Как 16-битные регистры могут обращаться к 20-битным адресам? Базовый адрес сегмента сдвигается на 4 бита влево (то есть умножается на 16) плюс смещение внутри сегмента, что дает 20-битный адрес (это и есть режим реального адреса, в который Linux 0.11 входит сразу после запуска).##### Разбиение на страницы
Линейные адреса в Linux 0.11 имеют 32 бита, из которых первые 10 бит — это смещение по таблице страниц, следующие 10 бит — это смещение по таблице страниц, а последние 12 бит — это смещение внутри страницы. Регистр CR3 содержит физический базовый адрес таблицы страниц (все нули), затем по смещению по таблице страниц ищется таблица страниц, и получается элемент таблицы страниц. Элемент таблицы страниц — это структура из 32 бит, из которых первые 20 бит — это физический адрес страницы, то есть базовый адрес страницы. Затем по смещению по таблице страниц ищется таблица страниц, и получается элемент таблицы страниц. Элемент таблицы страниц имеет ту же структуру, что и элемент таблицы страниц, и его первые 20 бит — это физический адрес страницы (базовый адрес страницы). В конечном итоге базовый адрес страницы плюс смещение внутри страницы дают финальный физический адрес.

Разбиение на страницы — это также механизм, предоставляемый аппаратной частью процессора. Его основная цель — **повышение эффективности использования памяти**, **уменьшение фрагментации памяти** и **обеспечение защиты**. С помощью разбиения на страницы операционная система может не загружать весь исполняемый файл процесса в память, а загружать его по страницам.#### Вторая часть
Вторая часть эксперимента включает добавление функции совместного использования памяти в Linux 0.11 и проверку её на примере программы производителя-потребителя. Структура данных для совместного использования памяти выглядит следующим образом:
```c
typedef struct shm_ds
{
   unsigned int key; // Идентификатор совместно используемой памяти
   unsigned int size; // Размер совместно используемой памяти, но в эксперименте требуется, чтобы размер превышал одну страницу, поэтому этот параметр не используется
   unsigned long page; // Физический базовый адрес совместно используемой памяти
} shm_ds;
```
Функция `sys_shmget` имеет простую логику. Если `key` существует, возвращается структура совместно используемой памяти, если нет, вызывается `get_free_page`, чтобы получить физическую страницу памяти и вставить её в массив структур `shm_list`.
```c
int sys_shmget(unsigned int key, size_t size)
{
   int i;
   void *page;
   if (size > PAGE_SIZE || key == 0)
       return -EINVAL;
   for (i = 0; i < SHM_SIZE; i++) /* Если key существует, возвращается идентификатор совместно используемой памяти */
   {
       if (shm_list[i].key == key)
       {
           printk("Find previous shm key:%u\n", shm_list[i].key);
           return i;
       }
   }
   page = get_free_page(); /* get_free_page устанавливает mem_map в 1 */
   /* Необходимо сбросить mem_map в 0, так как в sys_shmat будет увеличиваться количество ссылок на запрошенную физическую страницу */
   decrease_mem_map(page);
   if (!page)
       return -ENOMEM;
   printk("Shmget get memory's address is 0x%08x\n", page);
}
```    for (i = 0; i < SHM_SIZE; i++) /* Найти свободное место для совместного использования памяти */
    {
        if (shm_list[i].key == 0)
        {
            shm_list[i].page = page;
            shm_list[i].key = key;
            shm_list[i].size = size;
            printk("Generate a new shm key:%u\n", shm_list[i].key);
            return i;
        }
    }
    return -1;
}
```
Обратите внимание, что `decrease_mem_map` — это пользовательский функционал, который используется вместе с `increase_mem_map` в функции `sys_shmat`. Определение функций находится в файле `memory.c`:
```c
void increase_mem_map(unsigned long page)
{
    page -= LOW_MEM;
    page >>= 12;
    mem_map[page]++;
}
``````c
void decrease_mem_map(unsigned long page)
{
   page -= LOW_MEM;
   page >>= 12;
   mem_map[page]--;
}
```

Если эти функции не использовать (многие ответы в интернете их не используют), то физическая страница может быть использована двумя процессами, и при завершении каждого процесса страница будет освобождена, что приведёт к ошибке, так как `mem_map[page]` будет равен 1. В результате операционная система вызовет `panic` при попытке освободить страницу во второй раз. (см. файл `mm/memory.c#L98`) Система зависла.

`sys_shmat` устанавливает отображение виртуального пространства текущего процесса и общего сегмента.

`current->start_code` инициализируется в момент `fork` (выполнение исполняемого файла начинается с `fork`, затем с `execve`) как номер процесса, умноженный на 64 МБ. `current->brk` инициализируется в `do_execve` как сумма размеров сегментов Bss (хранит неинициализированные глобальные переменные), Data (хранит инициализированные глобальные переменные) и Text (код исполняемого файла). Поскольку в нашем программном обеспечении для потребителей и производителей глобальные переменные не используются, размер сегмента Bss равен нулю; также, согласно комментариям в `exec.c`, поскольку используется исполняемый файл с форматом ZMAGIC, сегменты данных и кода выровнены по страницам, поэтому `current->brk + current->start_code` также выровнены по страницам, и нет необходимости в округлении вверх.

```c
void *sys_shmat(int shmid)
{
   if (shmid < 0 || SHM_SIZE <= shmid || shm_list[shmid].key == -1)
   {
       return (void *) -1;
   }
   ...
}
``````markdown
page == 0 || shm_list[shmid].key == 0)
         return (void *)-EINVAL;
     /* Устанавливает отображение физического адреса и линейного адреса (первые 20 бит) */
     /* current->brk и current->start_code выровнены по 4 КБ */
     printk("current->brk: 0x%08x, current->start_code: 0x%08x\n", current->brk, current->start_code);
     put_page(shm_list[shmid].page, current->brk + current->start_code);
      /* Необходимо увеличить количество ссылок на общую физическую страницу, иначе система зависнет при вызове free_page */
     increase_mem_map(shm_list[shmid].page);
     current->brk += PAGE_SIZE;
     return (void *)(current->brk - PAGE_SIZE);
 }
 ```
  ### Задание
  См. [этот коммит](https://github.com/NaChen95/Linux0.11/commit/f2bc091c75504d7b736fdc78177e13d150a66ef6). В дополнение к семафорам и общему памяти, добавлен системный вызов [`get_jiffies`](https://github.com/NaChen95/Linux0.11/commit/fb29004fd027fddcef16353bfdb086a20f253c47#diff-f0650daa46b3094cc95addf8c615b8243587446cde5d6992a777e66a1e86667) для получения количества прерываний таймера, чтобы проверить работоспособность семафора. Из [producer.log](https://github.com/NaChen95/Linux0.11/commit/f2bc091c75504d7b736fdc78177e13d150a66ef6#diff-3d94a1bf04c5a7891471bc11e98c55e805f349d1157f1f74ed44fa40cf8a7a41) и [consumer.log](https://github.com/NaChen95/Linux0.11/commit/f2bc091c75504d7b736fdc78177e13d150a66ef6#diff-403c58c34bb897c68559d697a052245a4fb794f7bbb8f71714755709062b750e) видно, что процессы производителя и потребителя синхронизированы.
```