1. Процессы. Модель процесса. Создание и завершение процесса. Иерархия процессов. Состояния процессов. Реализация процессов.

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

- саму программу;                    

- данные к программе;            

- стек программы.

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

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

- указатель стека и другие.

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

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

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

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

Четыре основных события, приводящие к созданию процессов:

- инициализация системы;

- выполнение изданного работающим процессом системного запроса на создание процесса;

- запрос пользователя на создание процесса;

- инициирование пакетного задания.

С технической точки зрения во всех случаях новый процесс формируется одинаково: текущий процесс выполняет системный запрос на создание нового процесса. В UNIX существует только один системный вызов, направленный на создание нового процесса: fork (ветвление или вилка). Этот запрос создает дубликат вызываемого процесса. В Windows вызов функции CreateProcess интерфейса Win32 управляет и созданием процесса, и запуском в нем нужной программы. После создания нового процесса родительский и дочерний процессы имеют собственные различные адресные пространства.

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

События, приводящие к завершению процесса:

- обычный выход (преднамеренно);                                     

- выход по ошибке (преднамеренно);

- выход по неисправимой ошибке (непреднамеренно);

- уничтожение другим процессом (непреднамеренно).

В основном процессы завершаются по мере выполнения своей работы.

1) В Unix системный вызов exit, в Windows – ExitProcess.

2) Неустранимая ошибка.

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

4) Выполнение другим процессом системного запроса на уничтожение процесса. В Unix – kill, в Win32 – TerminateProcess.

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

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

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

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

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

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

Три возможных состояния процесса:

- выполнение (в этот конкретный момент использующий процессор);

- готовность (процесс временно приостановлен, чтобы позволить выполняться другому процессу);

- ожидание (процесс не может быть запущен прежде, чем произойдет некое внешнее событие).

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

Реализация процессов

2. Потоки. Модель потока. Использование потоков. Отличие потоков от процессов.

В обычных ОС каждому процессу соответствует адресное пространство и одиночный управляющий поток. Фактически это и определяет процесс.

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

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

- счетчик выполнения команд;           - регистры для текущих переменных;       - стек;             - состояние.

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

- адресное пространство;         - глобальные переменные;              - открытые файлы;

- таймеры;                                  - семафоры;                                       - статистическую информацию.

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

Использование потоков

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

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

- быстрота создания потока по сравнению с процессом примерно в 100 раз;

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

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

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

- Задание – набор процессов с общими квотами и лимитами.

- Процесс – контейнер ресурсов (память, …), содержит как минимум один поток.

- Поток – именно исполняемая часть, планируемая ядром.

3. Алгоритмы замещения страниц. Сравнительная характеристика.

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

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

4. Реализация потоков в пространстве пользователя, в ядре и смешанная реализация. Понятие всплывающих потоков.

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

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

Смешанная реализация - мультиплексирование потоков пользователя в потоках ядра. Поток ядра может содержать несколько потоков пользователя.

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

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

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

 

5. Межпроцессное взаимодействие. Состояние состязания. Понятие критической области (секции).

Межпроцессное взаимодействие (IPC, interprocess communication). Ситуации, при которых процессам приходится взаимодействовать:

- передача информации от одного процесса другому;

- контроль над деятельностью процессов (например, борьба за один ресурс);

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

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

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

- разделяемая память;

- канал (pipe) – это псевдофайл, в который один процесс пишет, а другой читает;

- сокеты – поддерживаемый ядром механизм, скрывающий особенности среды и позволяющий единообразно взаимодействовать процессам, как на одном компьютере, так и в сети;

- почтовые ящики (mail slots, только в Windows) – однонаправленные, возможность широковещательной рассылки;

- вызов удаленной процедуры – процесс A может вызвать процедуру в процессе B и получить обратно данные.

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

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

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

- два процесса не должны одновременно находиться в критических областях;

- в программе не должно быть предположений о скорости или количестве процессоров;

- процесс, находящийся вне критической области, не может блокировать другие процессы;

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

Пример требуемого поведения процессов:

 

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

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

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

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

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

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

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

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

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

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

- заблокированный процесс постоянно находится в цикле, проверяя, не изменилась ли переменная;

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

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

 

7. Алгоритм Петерсона. Примеры. Проблема инверсии приоритета.

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

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

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

Пример реализации алгоритма Петерсона для 2-х процессов.

#define FALSE 0

#define TRUE 1

#define N 2                                                        // Количество процессов

int turn;                                                   // Чья сейчас очередь?         

int interested[N];                        // Все переменные изначально равны 0

void enter_region(int process)    // Процесс 0 или 1

{

     int other = 1 – process;           // Номер второго процесса – противоположный процесс

     interested[process] = TRUE; // Индикатор интереса

     turn = process;                                   // Установка флага

     while (turn == process && interested[other] == TRUE);                // Пустой оператор

}   //вошел в критическую секцию

void leave_region(int process)    // process: процесс, покидающий критическую область

{

     interested[process] = FALSE;           // Индикатор выхода из критической области

}   //покинул критическую секцию

Цикл ожидания. Мы находимся в этом цикле, если второй процесс выполняет свою       кр.секцию. Как второй процесс выйдет из кр.секции, выполнится процедура ExitSection (int process_ID), флаг заинтересованности (interest[other_ID]) станет равен false, и цикл закончится.

Инверсия приоритета

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

 

8. Примитивы межпроцессного взаимодействия и проблема производителя-потребителя.

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

Используются как альтернатива активному ожиданию (алгоритм Петерсона и TSL).

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

 

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

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

1). выполнять требования задачи взаимного исключения по отношению к критическому ресурсу

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

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

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

Проблема производителя – потребителя.

const MAX = 100;  //макс. размер очереди

int count = 0;    //текущий размер очереди

void Producer() {

  int item;

  while (true) {

    item = ProduceItem();  //изготовить

    if (count == MAX)      //если очередь заполнена, то спать

      sleep();

    InsertItem(item);      //вставить продукт в очередь

    if (++count == 1)      //увеличить очередь. Если она ..

      WakeUp(Potrebitel);  //.. была пустой, то разбудить потр-ля

  }

}

void Potrebitel() {

  int item;

  while (true) {

    if (count == 0)        //если очередь пуста, то спать

      sleep();

    item = RemoveItem();   //извлечь продукт из очереди

    if (--count == N-1)    //уменьшить очередь. Если она ..

      WakeUp(Producer);    //.. была забита, то разбудить роизв-ля

    UseItem(item);         //как-то использовать продукт

 } }

 

9. Семафоры и проблема производителя-потребителя. Мьютексы.

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

     У семафора есть 2-е операции: up и down (обобщения sleep и wakeup).

     Все операции поднятия, опускание, проверки состояния и перевод процессора в состояния являются элементарным неделимым действием.

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

            Мьютекс – переменная, которая может находиться в одном из двух состояний: блокированном и неблокированном. Это частный случай семафора.

#define MAX 100;         //макс. размер очереди

semaphore mutex = 1;     //доступ в крит.секцию

semaphore empty = MAX;   //свободных мест в буфере

semaphore full = 0;      //занятых мест в буфере

void Producer(void) {

  int item;

  while (TRUE) {

    item = ProduceItem();    //изготовить

    down(&empty);            //уменьшить счетчик пустых мест

    down(&mutex);            //вход в крит.секцию

    InsertItem(item);        //вставить продукт в буфер

    up(&mutex);              //выход из крит.секции

    up(&full);               //увеличить счетчик занятых мест

  }

}

void Potrebitel(void) {

  int item;

  while (TRUE) {

    down(&full);             //уменьшить счетчик пустых мест

    down(&mutex);            //вход в крит.секцию

    item = RemoveItem(item); //извлечь продукт из буфера

    up(&mutex);              //выход из крит.секции

    up(&empty);              //увеличить счетчик пустых мест

    UseItem(item);           //как-то использовать продукт

  }

}

 

10. Мониторы и проблема производителя-потребителя.

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

            При обращении к монитору в любой момент времени активным может быть только один процесс.

Монитор – структурный элемент программирования, поэтому компилятор знает как его обрабатывать.

Монитор – структурный элемент программирования, поэтому компилятор знает, как его обрабатывать.monitor ProducerPotrebitel   condition full, empty;   integer count;   procedure Insert(item: integer);   begin     if count = N then wait(full);     InsertItem(item) ;     count := count+1;     if count = 1 then signal(empty);   end;   function Remove: integer;   begin     if count = 0 then wait(empty);     Remove := RremoveItem;     count := count-1;     if count = N-l then signal(full)   end;   count := 0; end monitor;

procedure Producer; begin   while true do begin     item := ProduceItem;     ProducerPotrebitel.Insert(item);   end; end;   procedure consumer; begin   while true do begin     item = ProducerConsumer.remove;     UseItem(item);   end; end;