edu-csa

# Архитектура компьютера

## Лекция 10-11

## Ввод-вывод. <br/> Многозадачность. <br/> Система прерываний. Взаимодействие процессов

Пенской А.В., 2025

---

## Устройство ввода-вывода

Типовое взаимодействие:

1. конфигурация устр./доступа;
1. проверка состояния;
1. отправка данных;
1. проверка статуса ответа;
1. чтение ответа.

Примеры устройств: диоды, ключи, клавиатуры, таймеры, часы, сопроцессоры, диски, и т.п.

</div><div class="col">

![](/fig/input-output-system-example.png)

</div></div>

----

## Устройство ввода-вывода. Интерфейс CPU

<div>

1. регистры данных;
1. регистры статуса;
1. протокол взаимодействия.

</div>

</div><div class="col">

![](/fig/input-output-model.jpg)

</div></div>

---

## Ввод-вывод с точки зрения ISA

Как выглядят операции ввода-вывода с точки зрения CPU?

1. Ввод-вывод через порты. Port-Mapped I/O (PMIO)
1. Ввод-вывод через память. Memory-Mapped I/O (MMIO)

![](/fig/io-memory-mapped-vs-port-mapped.png)

----

### Ввод-вывод через порты. <br/> Port-Mapped I/O (PMIO)

- Ввод-вывод через спец. инструкции: `in 11; out 12;`
- Адресация регистров ввода-вывода не зависит от адресации памяти (Isolated I/O).

#### Достоинства PMIO

1. Минимизация логики управления (малое адресное пространство). Оптимизация IO.
2. Ввод-вывод и доступ к памяти разделены.
3. Адресное пространство памяти однородно.
4. Простота системы в целом.

</div><div class="col">

#### Недостатки PMIO

1. Усложнение ISA и процессора.
2. Данные ввода-вывода — данные второго сорта (особенно для CISC процессоров).
3. "Лишние" копирования данных.
4. Очередное адресное пространство.

</div></div>

----

### Ввод-вывод через память. <br/> Memory-Mapped I/O (MMIO)

1. Регистры внешних устройств отображаются в адресное пространство памяти.
1. Ввод-вывод реализуется через инструкции доступа к памяти.

</div><div class="col">

![_Memory-Mapped I/O_](/fig//memory-mapped-io.png)

</div></div>

----

#### Достоинства MMIO

1. Простота процессора. Без изменения микроархитектуры.
1. Единый набор механизмов доступа: автоинкремент, векторные операции, работа с барьерами.
1. Обработка данных без переноса в память.
1. Адресное пространство памяти.

</div><div class="col">

#### Недостатки MMIO

1. Одна шина для ввода-вывода и памяти. Разница скорости шин.
1. Неоднородность памяти, сложная конфигурация системы.
1. Избыточный адрес для устройств ввода-вывода.
1. Проблемы с параллелизмом уровня инструкций и кешами:
    - flush при вводе-выводе;
    - порядок записи регистров.

</div></div>

---

## Варианты ввода-вывода

1. **Программно-управляемый ввод-вывод** — операции реализуются процессором. Все действия реализуются через инструкции процессора.
2. **Ввод-вывод по прерыванию**. Снимает с процессора задачу наблюдения и позволяет это реализовать по внешнему событию.
3. **Channel I/O** и **прямой доступ к памяти** (Direct Memory Access — DMA). Процессор ставит задачу и оповещается по готовности.

</div><div class="col">

![](/fig/io-devices.png)

</div></div>

---

## Программно-управляемый <br/> ввод-вывод

Работа с вводом-выводом управляется единым потоком управления.

Типичный подход к программированию: polling.

1. Наблюдаем за состоянием устройства ввода-вывода.
2. Реагируем.

-------------------------

Рассмотрим на примерах:

1. Работа с ключом.
1. SPI.
1. Имитация параллелизма.

----

### Пример: работа с ключом /1

Задача: посчитать количество нажатий на ключ (кнопку).

```python
counter = 0

while True:
    if switch() == 1:
        counter += 1
```

Будет работать?

</div><div class="col">

![](/fig/keyboard-switch.png)

</div></div>

<div>

1. Нет, это не сигнал, это уровень. Нажатие — поднял и опустил.
2. Нет, есть дребезг контактов.

</div><div class="col">

![](/fig/io-switch-bouncy.png)

</div></div>

</div>

----

### Пример: работа с ключом /2

```python
counter = 0
switch_prev = switch()

def sleep(ms):
    begin = now()
    while now() - begin < ms: pass

while True:
    switch_cur = switch()
    if switch_prev != switch_cur:
        if switch_cur == 1:
            sleep(200) # ms
            switch_cur = switch()
            if switch_cur == 1:
                counter += 1
                switch_prev = switch_cur
        if switch == 0:
            sleep(200) # ms
            switch_cur = switch()
            if switch_cur == 0:
                switch_prev = switch_cur
```

- `switch_prev` для обнаружения отпускания кнопки.
- `sleep` и повторная проверка позволяет избежать дребезга.

Проблемы?

----

#### Программно-управляемый ввод-вывод. Проблемы

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

---

#### Пример: Serial Peripheral Interface (SPI)

![_SPI подключение_](/fig/spi-connection.gif)

- **MOSI** (Master Out Slave In) или COPI — выход ведущего, вход ведомого. Передача данных от ведущего устройства ведомому.
- **MISO** (Master In Slave Out) или CIPO — вход ведущего, выход ведомого. Передача данных от ведомого устройства ведущему.
- **SCLK** (Serial Clock) или SCK — последовательный тактовый сигнал. Передача тактового сигнала для ведомых устройств.
- **CS** (Chip Select) или SS (Slave Select) — выбор микросхемы, выбор ведомого.

----

##### Временная диаграмма SPI

![](/fig/io-spi-wave-diagram.png)
(один из возможных вариантов)

</div><div class="col">

##### Устройство SPI передатчиков

![](/fig/io-spi-shift-register.jpg)

</div></div>

Почему сигнал `CS` устанавливает по нулевому значению?

<div>

`CS` часто подключается к сигналу `Reset`, тем самым включая устройство на время взаимодействия.

</div>

---

### Параллелизм ввода-вывода <br/> через конечные автоматы

Задача: посчитать количество нажатий на два ключа одновременно.

Варианты реализации:

1. Усложняем цикл, наблюдая сразу за 2 кнопками. <br/> Решаем проблему одновременного наблюдения.
1. **Разрываем поток управления через конечный автомат.**
1. Используем прерывания (к ним мы вернёмся позже).

----

#### Пример: работа с <br/> 2 ключами /1

Разрываем код цикла в конечный автомат для счётчика.

![](/fig/io-switch-fsm.png)

```python
class Counter():
  def __init__(self):
    self.state = 'wait1'
    self.counter = 0
    self.begin = None
    self.switch_prev = 0
```

</div><div class="col">

Оригинальный цикл:

```python
counter = 0
switch_prev = switch()

def sleep(ms):
    begin = now()
    while now() - begin < ms: pass

while True:
  switch_cur = switch()
  if switch_prev != switch_cur:
    if switch_cur == 1:
      sleep(200) # ms
      switch_cur = switch()
      if switch_cur == 1:
        counter += 1
        switch_prev = switch_cur
    if switch == 0:
      sleep(200) # ms
      switch_cur = switch()
      if switch_cur == 0:
        switch_prev = switch_cur
```

</div></div>

----

##### Пример: работа с <br/> 2 ключами /2

Разрываем код цикла в конечный автомат для счётчика.

![](/fig/io-switch-fsm.png)

```python
class Counter():
  def __init__(self):
    self.state = 'wait1'
    self.counter = 0
    self.begin = None
    self.switch_prev = 0
```

</div><div class="col">

Логика управляющего автомата:

```python
def process(self, switch_cur):
  if self.state == 'wait1':
    if self.switch_prev != switch_cur:
      self.state = 'hold1'
      self.begin = now()
  elif state == 'hold1':
    if now() - self.begin > delay:
      if switch_cur == 0:
        self.state = 'wait1'
        self.begin = None
      elif switch_cur == 1:
        self.state = 'wait0'
        self.counter += 1
        self.begin = None
        self.switch_prev = 1
  elif self.state == 'wait0':
    if self.switch_prev != switch_cur:
      self.state = 'hold0'
      self.begin = now()
  elif state == 'hold0':
    if now() - self.begin > delay:
      if switch_cur == 0:
        self.state = 'wait1'
        self.begin = None
        self.switch_prev = 1
      elif switch_cur == 0:
        self.state = 'wait0'
        self.begin = None
```

</div></div>

Notes:

```dot
digraph G {
  init -> wait1;

wait1 -> wait1[label="prev == cur"];
  wait1 -> hold1[label="prev != cur"];

hold1 -> hold1[label="sleep"];

hold1 -> wait1[label="cur == 0"];
  hold1 -> wait0[label="cur == 1"];

wait0 -> wait0[label="prev == cur"];
  wait0 -> hold0[label="prev != cur"];

hold0 -> hold0[label="sleep"];

hold0 -> wait0[label="cur == 1"];
  hold0 -> wait1[label="cur == 0"];
}
```

----

##### Пример: работа с 2 ключами /3

Запускаем счётчики в "параллельную" работу.

```python
counter1 = Counter()
counter2 = Counter()

while True:
    counter1.process(switch1())
    counter2.process(switch2())
```

Особенности реализации:

1. ООП и Python для простоты. Тривиально переписать на C.
2. `now()` — лучше вынести из автоматов на уровень общего цикла (тестирование, эффективность).
3. Инициализация сделана некорректно.
4. Многие проблемы сохранились: нагрузка, требования к частоте, энергопотребление.
5. По сути — это пример кооперативной многозадачности.

Перейдём к многозадачности.

---

## Параллелизм

1. Когда нужно работать сразу над несколькими задачами (ввод-вывод, системы управления).
2. Когда нужно повысить уровень утилизации ресурсов (не простаиваем, а занимаемся чем-то полезным).
3. Когда нужно повысить производительность компьютера (делаем больше дел за единицу времени).

### Виды параллелизма

1. **Уровень битов** (Bit-level Parallelism). "Ширина" комбинационных схем, шин данных и машинного слова.
1. **Уровень команд** (Instruction-level parallelism). Параллельное выполнение нескольких инструкций.
1. **Уровень задач** (Task/Thread-level parallelism). Параллельное выполнение нескольких программ. $\longrightarrow$

----

### Concurrency vs. Parallelism

![](/fig/concurrency.webp) 
![](/fig/parallelism.webp)

Сейчас нас интересует **Concurrency**.

---

## Параллелизм уровня задач

**Проблемы**:

1. Архитектура фон Неймана не рассчитана на параллелизм.
1. Поток инструкций — один.
1. Процессор должен "молотить" инструкции до `Halt`.

</div><div class="col">

![](/fig/juggernaut.jpg)

</div></div>

Варианты обеспечения параллелизма:

1. Кооперативная многозадачность (Cooperative Multitasking), <br/> соответствующая архитектуре фон Неймана.
2. Вытесняющая многозадачность (Preemptive Multitasking) <br/> или истинная многозадачность.

----

_Question_: Что происходит с контроллером, если он поделит на ноль?

---

## Кооперативная многозадачность (Cooperative Multitasking)

Многозадачность, при которой _следующая задача_ выполняется, когда _текущая задача_ явно объявит о готовности отдать процессорное время.

Грубо: есть вызов `Pause`.

</div><div class="col">

![](/fig/threads-cooprative.gif)

</div></div>

1. Активная программа получает всё процессорное время.
2. Фоновые — заморожены.
3. Приложение захватывает столько ресурсов, сколько хочет.
4. Приложения делят процессор, передавая управление следующему.

----

### Cooperative Multitasking. <br/> Вычислительные механизмы

1. Механизм **остановки** выполнения задачи: добровольная передача управления "диспетчеру".
1. Механизм **сохранения** состояния задачи: регистры, стек, состояния сопроцессоров, память, ввод-вывод, кеш, состояние предсказателя переходов, и т.п.
1. Механизм **планирования** — какой задаче отдать процессорное время следующей.
1. Механизм **возобновления** остановленного процесса: восстановление состояния и передача управления.

--------------------

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

----

### Cooperative Multitasking. Анализ

#### Преимущества

1. Контроль за ресурсами со стороны задачи.
1. Известные точки остановки. Отсутствие гонок.
1. Легкость и эффективность (при программной реализации).

</div><div class="col">

#### Недостатки

1. Контроль за ресурсами осуществляется задачей.
2. Сбой задачи может быть глобальным.
3. Низкая эффективность и трудоёмкость ввода-вывода.
4. Сложность разработки интерактивных приложений.

</div></div>

---

### Cooperative Multitasking. Подходы

1. Имитация через конечные автоматы (см. прог. ввод-вывод).
1. С диспетчером задач на уровне:
    - ОС (системные вызовы паузы/передачи управления).
    - Virtual Machine/Run Time, "шитый код", `time_slice`:
        - в интерпретаторе,
        - в машинном коде.
    - Программный код:
        - `event-loop` + `callbacks`
        - `async`/`await`, `yield`

</div><div class="col">

![](/fig/cooperative-multitasking-scheduler.gif)
![](/fig/node-js-event-loop.jpeg)

</div></div>

----

### Cooperative Multitasking. Практика

1. Пакетный режим и медленный ввод-вывод (в мейнфреймах), <br/> чтобы освободить процессор на время I/O.
1. Простые встроенные системы, bare-metal программирование.
1. Realtime. Статическое планирование.
1. Оптимизации систем, требующих частого переключения задач:
    - пример: single thread vs. multi thread web server (nginx/apache);
    - Node.js. Green Threads $\longrightarrow$

![](/fig/cyclogramm-schedule.png) 
![](/fig/cgi-process.jpg)

----

#### Green Threads

Проблема: как остановить долгую задачу без прерываний и ОС?

- **Erlang/OTP**. Green threads are implemented within a virtual machine. The internal scheduler (counting the number of executed instructions for each thread) allows the virtual machine to ensure an even distribution of processor time and meet the requirements of soft real-time. [Erlang Scheduler: what does it do?](https://erlang.org/pipermail/erlang-questions/2001-April/003132.html)

- **Golang**. Go-routines. It is a compromise between native threads (since it is a compiled language in machine code) and native threads (the language's run-time tracks key points of the algorithm that would interrupt the execution stream without the operating system).

</div><div class="col">

![](/fig/go-goroutine-schedule.jpg)

</div></div>

---

## Вытесняющая многозадачность (Preemptive Multitasking)

(истинная многозадачность)

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

</div><div class="col">

![](/fig/threads-preemptive.gif)

</div></div>

1. Переключение процессов происходит буквально между любыми двумя инструкциями (между — это где на конвейере?).
2. Распределение процессорного времени осуществляется планировщиком.
3. Возможна "мгновенная" реакция на действия пользователя.

----

### Preemptive Multitasking. <br/> Вычислительные механизмы

1. ~Механизм **остановки** задачи.~ $\longrightarrow$ Механизм **прерывания** процесса — забрать процессор у задачи независимо от её желания.
1. Механизм **сохранения** состояния задачи: регистры, стек, состояния сопроцессоров, память, ввод-вывод, кеш, состояние предсказателя переходов, и т.п.
1. Механизм **планирования** — какой задаче отдать процессорное время следующей.
1. Механизм **возобновления** остановленного процесса: восстановление состояния и передача управления.

--------------------

---

### Система прерываний

Архитектура фон Неймана характеризуется:

1. последовательным исполнением команд и [без]условным переходом;
2. процессор будет "молотить" инструкции столько, сколько сможет;
3. оптимизация "число-дробилки" для одной задачи.

</div><div class="col">

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

![](/fig/interrupts-in-computer-architecture-process-detail.png)

</div></div>

----

### Система прерываний. Принцип работы

1. Выполнение "основного" потока.
2. Запрос прерывания (HW).
3. Сохранение адреса возврата.
4. Вызов обработчика прерывания (ISR) — обычного кода в специальном месте.
5. Завершение ISR.
6. Восстановление адреса возврата.
7. Продолжение основного потока.

</div><div class="col">

![](/fig/interop-processing-2.png)

</div></div>

Система прерываний обеспечивает минимум два уровня задач:

1. Основной поток исполнения.
2. Поток (потоки) обработчиков прерываний.

----

#### Система прерываний. Источники прерываний

1. **Аппаратные**.
    1. **Внешние** (асинхронные для внутренних циклов процессора): переполнение таймера, нажатие клавиши, сетевой пакет.
    1. **Внутренние** (синхронные): деление на `0`, ошибка доступа к памяти, и т.п.
1. **Программные** (вызывается инструкцией): взаимодействие программы и ОС.

![](/fig/interrupts-instruction-cycle.jpg)

----

#### Система прерываний. Контроллер прерываний

1. Обычно, реализуется аппаратно (скорость и параллелизм).
2. Конкурирующие прерывания (приоритеты, потери, очереди):
    - Маскируемые/Немаскируемые.
    - Относительные/Абсолютные (прерывает прерывание).

</div><div class="col">

`3.` Вид события/прерывания:

- По фронту.
- По уровню (требует "сброса"). By OR — Spurious Interrupts.
- По сообщению (Message Signaled).
- По дверному звонку (Doorbell). Сигнал и информация разделены.

</div></div>

![](/fig/interrupts-in-computer-architecture-flow.png)

---

### Система прерываний. SPI — Master

Программно-управляемый ввод-вывод и таймер.

1. Начало передачи:
    - Настройка таймера. Вкл. прерывания.
    - `CS = 0`
    - `MOSI = o.pop()`
1. На каждое прерывание таймера:
    - `SCLK = !SCLK`
    - `if (!SCLK) MOSI = o.pop()`
    - `if ( SCLK) i.push( MISO )`
1. Окончание передачи:
    - `CS = 1`
    - `ready_flag = 1`

`i` - input, `o` - output

</div><div class="col">

![](/fig/io-spi-wave-diagram.png)
(длительность — произвольна)

![_SPI подключение_](/fig/spi-connection.gif)

</div></div>

----

### Система прерываний. SPI — Slave

1. Прерывание от **CS** (negedge):
    - Вкл. прерывания от **SCLK**.
    - `MISO = o.pop()`
1. Прерывание от **SCLK** (both):
    - `SCLK = !SCLK`
    - `if (!SCLK) MISO = o.pop()`
    - `if ( SCLK) i.push( MOSI )`
1. Прерывание от **CS** (posedge):
   - Выкл. прерывания от **SCLK**.
   - `ready_flag = 1`

`i` - input, `o` - output

--------------------

Альтернатива: вся передача данных программно внутри прерывания.

</div><div class="col">

![](/fig/io-spi-wave-diagram.png)
(длительность — произвольна)

![_SPI подключение_](/fig/spi-connection.gif)

</div></div>

---

#### Система прерываний. Пример. Watchdog Timer

**Сторожевой таймер** — _аппаратно_ реализованная схема контроля от зависания системы.

A **watchdog timer** is an _electronic or software_ timer that is used to detect and recover from computer malfunctions.

![](/fig/watchdog-timer-block-diagram.png) 
![](/fig/watchdog-timer-in-time.png)

---

### Preemptive Multitasking. Анализ

#### Преимущества PM

1. Простота разработки ПО с одним процессом.
1. Контроль за ресурсами со стороны ОС. Изоляция.
1. Интерактивность системы (почти мгновенная реакция).

</div><div class="col">

#### Недостатки PM

1. "Лишние" переключения.
1. "Тяжесть" процессов (прерывания, состояния, и т.п.).
1. Разделяемые состояния и непредсказуемые переключения. Синхронизация. Гонки.
1. Непредсказуемая длительность работы. Реальное время.

</div></div>

- Почему потоки — это фундаментальная проблема арх. фон Неймана?
    - [The Problem with Threads](https://www2.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-1.pdf)
- Максимальная длительность остановки процесса?
    - [Checkpoint/Restore In Userspace, or CRIU](https://criu.org/Main_Page)
- Почему это очень сложно (пример)? $\longrightarrow$

----

#### MapReduce

![](/fig/mapreduce-workflow.png)

1. `split data set` <br/> `:: [a] -> [[a]]`
1. `map foreach data set` <br/> `:: [[a]] -> [[b]]`
1. `reduce data sets` <br/> `:: [[b]] -> c`

--------------------

Проблема: <span> ошибки и остановка. </span>

</div><div class="col">

![](/fig/merge-sort-copy.png)

</div></div>

---

## Сосуществование задач

Параллелизм требует (оба вида):

1. Обеспечить **совмещение** и **изоляцию** между задачами.
1. Обеспечить **взаимодействие** между задачами.

Предмет совмещения:

- процессорное время;
- **память/регистры**.

Что надо совместить/изолировать? $\longrightarrow$

----

Что надо совместить/изолировать?

- Регистры.
- Адреса инструкций (переходы).
- Адреса данных (переменных).
- Динамическую память (куча).
- Автоматическую память (стек).

--------------------

Когда надо совмещать/изолировать?

- _Compile-time_ (состав задач фиксирован).
- _Run-time_ (состав задач динамический).

----

### Как совместить две задачи по памяти?

1. Инструкции:
    - **Размещаем** инструкции в разных областях памяти.
    - **Корректируем** все абсолютные адреса переходов.
1. Данные:
    - **Размещаем** данные в разных областях памяти.
    - **Корректируем** все абсолютные адреса.
1. Регистры:
    - **Формируем** соглашение о вызове процедур внутри задач.
    - **Сохраняем** и **загружаем** регистры между задачами.
1. Автоматическая память:
    - **Оцениваем** потребность в памяти.
    - **Выделяем** подходящие диапазоны (фрагментация).
1. Динамическая память: **выделяем** диапазон.
1. **Верим** в "добросовестное использование".

---

### Изоляция памяти

1. Банки памяти (Memory Bank), отчасти
1. Сегментация (Segmentation)
1. Виртуальная память (Virtual Memory)

---

### Банки памяти (Memory Bank)

Когда используется:

1. Память имеет большее адресное пространство, чем процессор.
1. Расширение машинного слова.
1. Переключение режима работы (аппаратная изоляция).
1. Изоляция задач — редко.

![even-odd-memory-banks](/fig/even-odd-memory-banks.jpg)

</div><div class="col">

- Расширение машинного слова:
    - два чипа памяти параллельно;
    - младший бит адреса `0` и `1` — выбор чипа;
    - машинное слово процессора — $2*8 = 16$ бит.
- Расширение памяти, изоляция:
    - адрес в процессоре — 8 бит;
    - `+ 2` бит выбора банка памяти;
    - итого: 10 бит адреса.
    - (схемы дальше)

</div></div>

----

#### Банки памяти. Расширение памяти и изоляция

![](/fig/bankswitch.png)  
![](/fig/memory-bank.jpg)

Notes: A hypothetical memory map of bank-switched memory for a processor that can only address 64 KB. This scheme shows 200 KB of memory, of which only 64 KB can be accessed at any time by the processor. The operating system must manage the bank-switching operation to ensure that program execution can continue when part of memory is not accessible to the processor.

---

### Сегментная память (Segmentation)

Разметим память процессора по назначению. <br/> Как внутри задач, так и между ними.

1. Сегментная адресация памяти — способ логической адресации памяти, где адрес: `сегмент` + `смещение`.
1. `Сегмент` — выделенная область адресного пространства **определённого размера**.
1. `Смещение` — адрес ячейки памяти относительно начала сегмента.

</div><div class="col">

![segment_map_table](/fig/segment_map_table.jpg)

</div></div>

----

#### Сегментная память. Позволяет

1. Независимая адресация внутри сегментов (нет коллизиям).
1. Управление доступом (чтение, запись). Запрет доступа к "чужим" сегментам.
1. Взаимодействие задач через общий сегмент.
1. Изоляция программных модулей, динамические библиотеки (ПО — 1, data — N).
1. Перекрытие сегментов. $\downarrow$

</div><div class="col">

![paging-and-segmentation](/fig/paging-and-segmentation.png)

</div></div>

----

![](/fig/segment-addressing.png)

----

#### Сегментная память. Анализ

##### Segmentation. Достоинства

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

</div><div class="col">

##### Segmentation. Недостатки

1. Non-von Neumann way
    - Поддержка со стороны компилятора, ПО.
    - Участие программистов (количество сегментов, размер сегментов).
1. Считается устаревшей, имеет ограниченную поддержку ОС (Linux).
1. Внешняя фрагментация. $\longrightarrow$

</div></div>

----

#### Внутренняя фраг

![](/fig/fragmentation-internal.jpg)

Данные размещаются в блоках фиксированного размера. <br/> `P1` — требует 3 Mb, блок — 4 Mb.

</div><div class="col">

#### Внешняя фрагментация

![](/fig/fragmentation-external.jpg)

Данные размещаются в блоках произвольных размеров. <br/> Проблема плотной укладки.

</div></div>

---

### Виртуальная память (Virtual Memory)

Предоставим каждой задаче своё виртуальное адресное пространство. <br/> Пусть каждый процесс думает, что **всё адресное пространство его**.

1. **Режем** вирт. адресные пространства на страницы.
1. **Отображаем** страницы на физические адреса по запросу.
1. **Физическая память кончилась**:
    - **находим** неиспользуемые страницы любой задачи;
    - **выгружаем** их на диск.
1. **Страницы нет** в физической памяти:
    - **загружаем** её с диска.

</div><div class="col">

![](/fig/virtual-memory-map.jpg)

</div></div>

----

#### Виртуальная память. Позволяет

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

</div><div class="col">

![](/fig/virtual-memory-process.png)
![](/fig/virtual-memory-data-and-stack.jpg) 
![](/fig/virtual-memory-shared.jpg)

</div></div>

----

#### Виртуальная память. Анализ

##### ВП. Достоинства

1. Прозрачна для программистов.
1. Работа с "бесконечной" памятью, динамическое распределение памяти.
1. Повышает общую стабильность системы (аналогично Preemptive Multitasking).
1. Отсутствует внешняя сегментация.

</div><div class="col">

##### ВП. Недостатки

1. Большой объём таблиц страниц, длительный поиск (кеш).
1. Высокие накладные расходы (ввод-вывод, перенос страниц...)
1. Нет изоляции внутри адресного пространства.
1. Непредсказуемая длительность доступа к памяти.
1. Высокая сложность реализации.

</div></div>

---

### Взаимодействие между задачами

Типовые виды задач (условно):

1. **Main**/Kernel/Основной поток — исходный поток инструкций.
1. **Прерывания**. Особый исходный код обработчиков прерываний.
1. **Процессы**. Изолированные адресные пространства. Нет прямого доступа.
1. **Потоки**. Работают в адресном пространстве процесса. Прямой доступ ко всем его данным.
1. **Зелёные потоки**. В рамках Run-Time или виртуальной машины.

(_подробнее в курсе ОС_)

</div><div class="col">

![](/fig/process-and-threads.jpg)
![](/fig/user-and-kernel-spaces.png)

</div></div>

----

#### Взаимодействие процессов

**Проблема**: как получить доступ к изолированной памяти.

1. Shared Memory
1. Signals
1. IO: Network, Files, Pipes

</div><div class="col">

![](/fig/shared-memory.png)

</div></div>

![](/fig/ipc-signal-handler.png)

----

#### Взаимодействие потоков <br/> (вытесняющая многозадачность)

**Проблема**: непредсказуемая последовательность исполнения инструкций с недетерминированным результатом.

**Решение**: искусственная синхронизация процессов.

1. Атомарные операции: `compare&swap`, `conditional store` и т.п.
1. Mutex `(0/1)`, Semaphore `(0..N)`.
1. [Software] Transactional Memory ([S]TM).
1. Process Network, Promise, Futures, Actor-Model...

---

## Детерминизм многопоточности /1

```c
// Глобальные переменные с
// разделяемым состоянием.
int x, y, a, b;

// Два зеркальных потока.
void* thread1(void* unused) {
    x = 1;
    a = y;
    return NULL;
}

void* thread2(void* unused) {
    y = 1;
    b = x;
    return NULL;
}
```

Возможна ли остановка алгоритма?

</div><div class="col">

```c
int main() {
    int i = 0;
    while (1) {
        x = 0; y = 0; a = 0; b = 0;
        pthread_t tid1, tid2;
        pthread_attr_t attr1, attr2;

pthread_attr_init(&attr1);
        pthread_attr_init(&attr2);

pthread_create(&tid1, &attr1, thread1, NULL);
        pthread_create(&tid2, &attr2, thread2, NULL);

pthread_join(tid1, NULL);
        pthread_join(tid2, NULL);

i++;
        if(a == 0 && b == 0) break;
    }
    printf("Iterations: %d\n", i);
    return 0;
}
```

</div></div>

----

### Детерминизм многопоточности в теории

| | | | | | `a/b` |
|:----------|:---------|:------------|:------------|:------------|:-----:|
| `thread1` | `1 -> x` | `y(0) -> a` | | | `0` |
| `thread2` | | | `1 -> y` | `x(1) -> b` | `1` |
| | | | | | |
| `thread1` | `1 -> x` | | `y(1) -> a` | | `1` |
| `thread2` | | `1 -> y` | | `x(1) -> b` | `1` |
| | | | | | |
| `thread1` | `1 -> x` | | | `y(1) -> a` | `1` |
| `thread2` | | `1 -> y` | `x(1) -> b` | | `1` |
| | | | | | |
| `thread1` | | | `1 -> x` | `y(1) -> a` | `1` |
| `thread2` | `1 -> y` | `x(0) -> b` | | | `0` |

Нет.

----

### Детерминизм многопоточности на практике

```shell
$ clang src/thread-magic.c
$ ./a.out
Iterations: 27243
$ ./a.out
Iterations: 297675
$ ./a.out
Iterations: 4302
```

Да.

Источник: [Другой взгляд на многопоточность](https://habr.com/en/post/590339/)

---

## Вернёмся к вводу-выводу

1. Программно-управляемый ввод-вывод — операции реализуются процессором. Все действия реализуются через инструкции процессора.
2. Ввод-вывод по прерыванию. Снимает с процессора задачу наблюдения и позволяет это реализовать по внешнему событию.
3. **Channel I/O** и **прямой доступ к памяти** (Direct Memory Access — DMA). Процессор ставит задачу и оповещается по готовности.

----

### Channel I/O. Процессоры ввода-вывода

- Позволяют задать программу для взаимодействия с внешним устройством. К примеру: "считать запись на диске, идентифицированную записанным ключом":

```text
SEEK             <cylinder/head number>
SEARCH KEY EQUAL <key value>
TIC              *-8 Back to search if not equal
READ DATA        <buffer>
```

- ISA канала адаптирована для ввода-вывода (пример: автоматическая конвертация форматов).
- Ранее применялись в мэйнфреймах.
- Сегодня вытеснено (упрощено до) DMA.

---

### Прямой доступ к памяти (DMA)

- Как освободить процессор от работы с вводом-выводом?
- Добавить больше процессоров!
    - Direct Memory Access (DMA).
    - Выполняет команды переноса данных между памятью устройств ввода-вывода и памятью процессора.

![_Direct Memory Access_](/fig/dma-block-diagram-ru.png)

----

#### Прямой доступ к памяти. Интерфейс

```c
DMA_SRC_ADDR   // Исходный адрес (откуда читать)
DMA_DST_ADDR   // Целевой адрес (куда писать)
DMA_COUNT      // Количество байт/слов для передачи
DMA_CONTROL    // Управление (направление, режим работы, запуск/остановка)
DMA_STATUS     // Статус (занят/готов, ошибки)
```

```text
┌───────────┐          ┌──────────────┐          ┌───────────┐
│           │◄─────────┤              │◄─────────┤           │
│           │  Данные  │  DMA         │  Данные  │           │
│ Память    │          │  Контроллер  │          │ Устройство│
│           │─────────►│              │─────────►│ (UART/SPI)│
│           │  Данные  │              │  Данные  │           │
└───────────┘          └──────────────┘          └───────────┘
      ▲                       ▲
      │                       │
      └───────────┬───────────┘
                  │
            ┌─────▼─────┐
            │           │
            │ Процессор │
            │           │
            └───────────┘
```

----

#### Прямой доступ к памяти. Интеграция в систему

- **Third-party**. Управление DMA осуществляется процессором.
- **Bus mastering**. Управление DMA может осуществляться и устройствами ввода-вывода.

--------------------

#### Прямой доступ к памяти. <br/> Взаимодействие с процессором

- **Пакетный режим** (Burst Mode). Приоритет DMA.
    Передача данных осуществляется единой операцией, которая не может быть прервана процессором.
- **Циклический режим** (Cycle stealing mode). <br/> Приоритет конфигурируется.
    Для процессора и DMA выделяется фиксированный слот времени в рамках цикла.
- **Прозрачный режим** (Transparent Mode). Приоритет процессора.
    Передача данных, когда процессор не взаимодействует с памятью.

----

#### Прямой доступ к памяти. Достоинства

1. Скорость и эффективность контроллера DSA.
1. Интерактивность, так как процессор разгружен от "рутины".
1. Параллелизм: DMA может иметь несколько каналов для параллельной работы.

--------------

#### Прямой доступ к памяти. Недостатки

1. Проблемы совместимости.
1. Сложность при непоследовательном доступе к памяти.
1. Ограниченный контроль за системной шиной. Синхронизация работы процессора и DMA.
1. Конфликты использования DMA разными устройствами ввода-вывода.

---

## Тенденция: <br/> унификация и упрощение

- Memory-Mapped IO (отображение интерфейсов в память)
- Direct Memory Access (представление протокола передачи как перемещения данных в памяти)
- Virtual Memory (Унификация памяти с точки зрения процесса)

Итого: **всё есть память и она одна.**

----

### Операционные системы: всё есть файл

1. **Универсальный интерфейс**:
    - Все ресурсы системы представлены как файлы.
    - Единый набор операций: открытие, чтение, запись, закрытие.
2. **Простота и управляемость**.  Использование общих инструментов для манипуляций с различными ресурсами.
3. **Прозрачность системы**. Все взаимодействия с ресурсами легко отслеживаются.
4. **Масштабируемость и распределённость**. Локальные и удалённые ресурсы доступны через одинаковые интерфейсы.

----

#### Пример: Linux

Исключения:

1. **Сетевые интерфейсы**: `socket()`, `bind()`, `listen()`, `accept()`.
2. **Процессы и потоки**: `/proc` — информация о процессах, но не управление.
3. **Аппаратные устройства** (некоторые)
4. **Специальные файловые системы** sysfs и devfs, которые предоставляют интерфейсы к устройствам и ядру, но их поведение отличается от обычных файлов.
5. **Графические интерфейсы**.

----

#### ОС: Всё есть файл: Plan 9

- Файловая система `/net`:
    - Каждое сетевое соединение представлено как файл.
    - Создание и управление соединениями через стандартные файловые операции.

--------------------

##### Процесс установки TCP-соединения

1. Открытие файла `/net/tcp/clone`:
   - Система возвращает файловый дескриптор для нового соединения.
   - Автоматическое создание файлов `ctl`, `data`, `status` для управления соединением.
2. Управление соединением через файл `ctl`:
   - Команды для настройки IP-адреса, порта и других параметров.
3. Обмен данными через файл `data`:
   - Передача и приём данных посредством чтения и записи в файл.