Процессы и потоки (нити)

Лекция 5. Процессы и потоки (нити). Взаимодействие процессов.

5.1 Процессы

5.1.1 Понятие процесса

      Процесс (задача) - программа, находящаяся в режиме выполнения.

С каждым процессом связывается его адресное пространство, из которого он может читать и в которое он может писать данные.

Адресное пространство содержит:

• саму программу
• данные к программе
• стек программы

С каждым процессом связывается набор регистров, например:

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

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

Рекомендуемые материалы

Некоторые поля таблицы

5.1.2 Модель процесса

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

Рассмотрим схему с четырьмя работающими программами.

В каждый момент времени активен только один процесс

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

5.1.3 Создание процесса

     Три основных события, приводящие к созданию процессов (вызов fork или CreateProcess):

• Загрузка системы
• Работающий процесс подает системный вызов на создание процесса
• Запрос пользователя на создание процесса

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

   Каждому процессу присваивается идентификатор процесса PID - Process IDentifier.

5.1.4 Завершение процесса

(вызов exit или ExitProcess):

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

    Таким образом, приостановленный процесс состоит из собственного адресного пространства, обычно называемого образом памяти (core image), и компонентов таблицы процессов (в числе компонентов и его регистры).

5.1.5 Иерархия процессов

      В UNIX системах заложена жесткая иерархия процессов. Каждый новый процесс созданный системным вызовом fork, является дочерним к предыдущему процессу. Дочернему процессу достаются от родительского переменные, регистры и т.п. После вызова fork, как только родительские данные скопированы, последующие изменения в одном из процессов не влияют на другой, но процессы помнят о том, кто является родительским.

В таком случае в UNIX существует и прародитель всех процессов - процесс init.

Дерево процессов для систем UNIX

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

5.1.6 Состояние процессов

      Три состояния процесса:

• Выполнение (занимает процессор)
• Готовность (процесс временно приостановлен, чтобы позволить выполняться другому процессу)
• Ожидание (процесс не может быть запущен по своим внутренним причинам, например, ожидая операции ввода/вывода)

Возможные переходы между состояниями:

                                          1. Процесс блокируется, ожидая входных данных

                                          2. Планировщик выбирает другой процесс

                                          3. Планировщик выбирает этот процесс

                                          4. Поступили входные данные

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

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

5.2 Потоки (нити, облегченный процесс)

5.2.1 Понятие потока

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

Сравнение многопоточной системы с однопоточной

5.2.2 Модель потока

      С каждым потоком связывается:

• Счетчик выполнения команд
• Регистры для текущих переменных
• Стек
• Состояние

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

• Адресное пространство
• Глобальные переменные
• Открытые файлы
• Таймеры
• Семафоры
• Статистическую информацию.

В остальном модель идентична модели процессов.

      В POSIX  и Windows есть поддержка потоков на уровне ядра.

      В Linux есть новый системный вызов clone для создания потоков, отсутствующий во всех остальных версиях системы UNIX.

      В POSIX есть новый системный вызов pthread_create для создания потоков.

      В Windows есть новый системный вызов Createthread для создания потоков.

5.2.3 Преимущества использования потоков

1. Упрощение программы в некоторых случаях, за счет использования общего адресного пространства.
2. Быстрота создания потока, по сравнению с процессом, примерно в 100 раз.
3. Повышение производительности самой программы, т.к. есть возможность одновременно выполнять вычисления на процессоре и операцию ввода/вывода. Пример: текстовый редактор с тремя потоками может одновременно взаимодействовать с пользователем, форматировать текст и записывать на диск резервную копию.

5.2.4 Реализация потоков в пространстве пользователя, ядра и смешанное

А - потоки в пространстве пользователя

B - потоки в пространстве ядра

      В случае А ядро о потоках ничего не знает. Каждому процессу необходима таблица потоков, аналогичная таблице процессов.

      Преимущества случая А:

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

      Недостатки случая А:

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

Мультиплексирование потоков пользователя в потоках ядра

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

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

      Используется четыре понятия:

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

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

5.3. Взаимодействие между процессами

      Ситуации, когда приходится процессам взаимодействовать:

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

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

5.3.1. Передача информации от одного процесса другому

      Передача может осуществляться несколькими способами:

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

Схема для канала

Схема для сокетов

5.3.2 Состояние состязания

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

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

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

out - переменная, указывающая на следующее имя файла для печати

Пример состязания

      Распишем события по пунктам.

1. Процесс А считывает переменную in (равную 7), и сохраняет ее в своей переменной next_free_slot.
2. Происходит прерывание по таймеру, и процессор переключается на процесс В.
3. Процесс В считывает переменную in (равную 7), и сохраняет ее в своей переменной next_free_slot.
4. Процесс В сохраняет имя файла в сегменте 7.
5. Процесс В увеличивает переменную next_free_slot на единицу (next_free_slot+1), и заменяет значение in на 8.
6. Управление переходит процессу А, и продолжает с того места на котором остановился.
7. Процесс А сохраняет имя файла в сегменте 7, затирая имя файла процесса В.
8. Процесс А увеличивает переменную next_free_slot на единицу (next_free_slot+1), и заменяет значение in на 8.

      Как видно из этой ситуации, файл процесса В не будет напечатан.

5.3.3 Критические области

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

      Условия избегания состязания и эффективной работы процессов:

1. Два процесса не должны одновременно находиться в критических областях.
2. Процесс, находящийся вне критической области, не может блокировать другие процессы.
3. Невозможна ситуация, когда процесс вечно ждет попадания в критическую область (зависает).

Пример:

Взаимное исключение с использованием критических областей

5.3.4 Взаимное исключение с активным ожиданием

      Рассмотрим методы взаимного исключения

      Запрещение прерываний

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

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

      Переменные блокировки

      Вводится понятие переменной блокировки, т.е. если значение этой переменной равно, например 1, то ресурс занят другим процессом, и второй процесс переходит в режим ожидания (блокируется) до тех пор, пока переменная не примет значение 0.

метод блокирующих переменных

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

      Строгое чередование

      В этой модели, процессы могут выполняться строго по очереди, используя переменную.

Строгое чередование

     Недостатки метода:

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

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

5.3.5 Примитивы взаимодействия процессов

      Вводится понятия двух примитивов.

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

wakeup - системный запрос, в результате которого блокированный процесс будет запущен.

Применение примитивов

Основное преимущество - это отсутствие активного ожидания.

Проблема заключается в следующем, если спулер пуст, то wakeup срабатывает в пустую.

       Проблема переполненного буфера (проблема производителя и потребителя)

      Рассмотрим два процесса, которые совместно используют буфер ограниченного размера, один процесс пишет в буфер, другой считывает данные.

Чтобы первый процесс не писал, когда буфер полный, а второй не считывал, когда он пуст, вводится переменная count для подсчета количества элементов в буфере.

Проблема переполненного буфера

      В этой ситуации оба процесса могут попасть в состояние ожидания, если пропадет сигнал активации.

      Алгоритм такой ситуации:

1. Процесс В, считал count=0 (заблокироваться он еще не успел)
2. Планировщик передал управление процессу А
3. Процесс А, выполнил все вплоть до wakeup, пытаясь разблокировать процесс В (но он не заблокирован, wakeup срабатывает впустую)
4. Планировщик передал управление процессу В
5. И он заблокировался, и больше сигнала на разблокировку не получит
6. Процесс А в конце концов заполнит буфер и заблокируется, но сигнала на разблокировку не получит.

5.3.6 Семафоры

      Семафоры - переменные для подсчета сигналов запуска, сохраненных на будущее.

      Были предложены две операции down и up (аналоги sleep и wakeup).

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

      up увеличит значение семафора на 1 или разблокирует процесс, находящийся в ожидании..

      down уменьшает значение семафора на 1 или блокирует процесс, если семафор =0.

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

      Решение проблемы переполненного буфера с помощью семафора

      Применим три семафора:

full - подсчет заполненных сегментов (в начале = 0)

empty - подсчет пустых сегментов (в начале = количеству сегментов)

"18 - Правила ведения переговоров" - тут тоже много полезного для Вас.

mutex - для исключения одновременного доступа к буферу двух процессов. (в начале = 1)

      Мьютекс упрощенная версия семафора, он управляет доступом к ресурсу. Показывает, блокирован или нет ресурс.

Решение проблемы переполненного буфера с помощью семафора

      Применение семафоров для устройств ввода/вывода

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