Понятие процесса В ОС. Диаграмма состояний процесса. Контекст процесса и операции над процессами.

Понятие процесса в ОС. Диаграмма состояний процесса. Контекст процесса и операции над процессами.

Проце́сс — выполнение пассивных инструкций компьютерной программы на процессоре ЭВМ. Компьютерная программа сама по себе это только пассивная совокупность инструкций, в то время как процесс — это непосредственное выполнение этих инструкций.

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

Состояния процесса.

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

 

· Первая фаза - создание (рождение) процесса, которое осуществляется ОС.

· Вторая фаза - состояние готовности к исполнению.

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

· Четвертая фаза - ожидание. В это состояние процесс переходит, если

а) необходимо завершить операцию ввода/вывода

б) истекло время исполнения процесса по таймеру

· Пятая фаза- завершение. В это состояние процесс переходит, если:

а) операционная система завершила его исполнение

б) произошла фатальная ошибка времени исполнения.

 

Изменением состояния процессов занимается операционная система, совершая операции над ними. Количество таких операций в нашей модели пока совпадает с количеством стрелок на диаграмме состояний. Удобно объединить их в три пары:

 

создание процесса – завершение процесса;

приостановка процесса (перевод из состояния исполнение в состояние готовность) – запуск процесса (перевод из состояния готовность в состояние исполнение);

блокирование процесса (перевод из состояния исполнение в состояние ожидание) – разблокирование процесса (перевод из состояния ожидание в состояние готовность).

 

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

 

 

Контекст процесса.

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

 

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

Все данные подразделяются на:

инициализируемые неизменяемые данные (например, константы);

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

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

стек пользователя;

данные, расположенные в динамически выделяемой памяти (например, с помощью стандартных библиотечных C функций malloc(), calloc(), realloc()).

 

Контекст можно разделить условно на две составляюшие:

регистровый контекст:

содержимое регистров процессора;

системный контескт:

состояние, в котором находится процесс;

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

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

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

сведения об устройствах ввода-вывода, связанных с процессом (например, какие устройства закреплены за процессом, таблицу открытых файлов).

 

Контекст ядра - объединение системного контекста и регистрового контекста. В данные ядра входят:

идентификатор пользователя — UID,

групповой идентификатор пользователя — GID,

идентификатор процесса - — PID,

идентификатор родительского процесса — PPID.

Присвоение идентификационных номеров процессов начинается с номера 0, который получает процесс kernel при старте операционной системы.

 

Операции над процессами.

ОС должна иметь возможность выполнять определенные операции над процессами:

 

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

· уничтожение

· возобновление

· изменение приоритета

· блокирование

· пробуждение

· запуск

 

Создание нового процесса состоит из нескольких подопераций:

присвоение имени

включение этого имени в список имен процессов, известных ОС

присвоение начального приоритета

формирование БУП

выделение процессу начальных ресурсов

Новый процесс может породить дочерние процессы.

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

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

Изменение приоритета - это изменение значения приоритета в БУП.

Прерывания в ОС.
Прерывание - это событие, при котором меняется нормальная последовательность команд, выполняемых ЦП.
Если произошло прерывание, то:

Управление передается ОС

ОС запоминает состояние прерванного процесса

ОС анализирует тип прерывания и передает управление соответствующей программе по обработке данного типа прерывания.

 

Понятие ОС.

Реализация многозадачности

По числу одновременно выполняемых задач операционные системы можно разделить на два класса:

многозадачные (Unix, OS/2, Windows);

однозадачные (например, MS-DOS).

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

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

В некоторых ОС (Windows 3.11, например) пользовательская программа может монополизировать процессор, то есть работать в невытесняющем режиме. Как правило, в большинстве систем не подлежит вытеснению код собственно ОС. Ответственные программы, в частности задачи реального времени, также не вытесняются. Более подробно об этом рассказано в лекции, посвященной планированию работы процессора.

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

Многопроцессорная обработка

Вплоть до недавнего времени вычислительные системы имели один центральный процессор. В результате требований к повышению производительности появились многопроцессорные системы, состоящие из двух и более процессоров общего назначения, осуществляющих параллельное выполнение команд. Поддержка мультипроцессирования является важным свойством ОС и приводит к усложнению всех алгоритмов управления ресурсами. Многопроцессорная обработка реализована в таких ОС, как Linux, Solaris, Windows NT, и ряде других.

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

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

Системы реального времени

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

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

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

Особенности Windows:

Правила написания программы. Для работы в среде Windows программа должна быть написана по определенным правилам, существенно отличающимся от принятых в MS-DOS.

Windows позволяет запускать и программы, написанные для MS DOS, но при этом программы не могут использовать преимущества Windows.

Графический интерфейс пользователя в Windows основан на идее оконного интерфейса, принятого так же и в ряде других современных ОС (например, UNIX). Каждая программа имеет собственное окно, в котором и происходит обмен сообщений с пользователем. Для наглядности в Windows широко применяются иконки (пиктограммы), изображающие отдельные программы.

Кроме того, интерфейс Windows в значительной степени стандартизирован, что облегчает пользователям процесс освоения новых порограмм.

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

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

 

ОСОБЕННОСТИ UNIX

 

Стандартизация

Несмотря на многообразие версий UNIX, основой всего семейства являются принципиально одинаковая архитектура и ряд стандартных интерфейсов (в UNIX стандартизовано почти всё — от расположения системных каталогов и файлов до интерфейса системных вызовов и списка драйверов базовых устройств). Опытный администратор без особого труда сможет обслуживать другую версию, тогда как для пользователей переход на другую систему и вовсе может оказаться незаметным. Для системных же программистов такого рода стандарты позволяют полностью сосредоточиться на программировании, не тратя время на изучение архитектуры и особенностей конкретной реализации системы.

Многозадачность

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

 

КОДИРОВКА ХАФФМАНА

Идея, положенная в основу кодировании Хаффмана, основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код. Это нужно, так как мы хотим, чтобы, когда мы обработали весь ввод, самые частотные символы заняли меньше всего места (и меньше, чем они занимали в оригинале), а самые редкие — побольше (но так как они редкие, это не имеет значения). Для нашей программы я решил, что символ будет иметь длину 8 бит, то есть, будет соответствовать печатному знаку.

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

Для этого алгоритма вам потребуется минимальное понимание устройства бинарного дерева и очереди с приоритетами.

Предположим, у нас есть строка «beep boop beer!», для которой, в её текущем виде, на каждый знак тратится по одному байту. Это означает, что вся строка целиком занимает 15*8 = 120 бит памяти. После кодирования строка займёт 40 бит (на практике, в нашей программе мы выведем на консоль последовательность из 40 нулей и единиц, представляющих собой биты кодированного текста. Чтобы получить из них настоящую строку размером 40 бит, нужно применять битовую арифметику, поэтому мы сегодня не будем этого делать).

Чтобы лучше понять пример, мы для начала сделаем всё вручную. Строка «beep boop beer!» для этого очень хорошо подойдёт. Чтобы получить код для каждого символа на основе его частотности, нам надо построить бинарное дерево, такое, что каждый лист этого дерева будет содержать символ (печатный знак из строки). Дерево будет строиться от листьев к корню, в том смысле, что символы с меньшей частотой будут дальше от корня, чем символы с большей. Скоро вы увидите, для чего это нужно.

Чтобы построить дерево, мы воспользуемся слегка модифицированной очередью с приоритетами — первыми из неё будут извлекаться элементы с наименьшим приоритетом, а не наибольшим. Это нужно, чтобы строить дерево от листьев к корню.

Для начала посчитаем частоты всех символов:

Символ	Частота
'b'
'e'
'p'
' '
'o'
'r'
'!'

 

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

Теперь мы достаём два первых элемента из очереди и связываем их, создавая новый узел дерева, в котором они оба будут потомками, а приоритет нового узла будет равен сумме их приоритетов. После этого мы добавим получившийся новый узел обратно в очередь.

Повторим те же шаги и получим последовательно:

Ну и после того, как мы свяжем два последних элемента, получится итоговое дерево:

Теперь, чтобы получить код для каждого символа, надо просто пройтись по дереву, и для каждого перехода добавлять 0, если мы идём влево, и 1 — если направо:

Если мы так сделаем, то получим следующие коды для символов:

Символ	Код
'b'
'e'
'p'
' '
'o'
'r'
'!'

 

Чтобы расшифровать закодированную строку, нам надо, соответственно, просто идти по дереву, сворачивая в соответствующую каждому биту сторону до тех пор, пока мы не достигнем листа. Например, если есть строка «101 11 101 11» и наше дерево, то мы получим строку «pepe».

Важно иметь в виду, что каждый код не является префиксом для кода другого символа. В нашем примере, если 00 — это код для 'b', то 000 не может оказаться чьим-либо кодом, потому что иначе мы получим конфликт. Мы никогда не достигли бы этого символа в дереве, так как останавливались бы ещё на 'b'.

На практике, при реализации данного алгоритма сразу после построения дерева строится таблица Хаффмана. Данная таблица — это по сути связный список или массив, который содержит каждый символ и его код, потому что это делает кодирование более эффективным. Довольно затратно каждый раз искать символ и одновременно вычислять его код, так как мы не знаем, где он находится, и придётся обходить всё дерево целиком. Как правило, для кодирования используется таблица Хаффмана, а для декодирования — дерево Хаффмана.

 

 

Понятие процесса в ОС. Диаграмма состояний процесса. Контекст процесса и операции над процессами.

Проце́сс — выполнение пассивных инструкций компьютерной программы на процессоре ЭВМ. Компьютерная программа сама по себе это только пассивная совокупность инструкций, в то время как процесс — это непосредственное выполнение этих инструкций.

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

Состояния процесса.

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

 

· Первая фаза - создание (рождение) процесса, которое осуществляется ОС.

· Вторая фаза - состояние готовности к исполнению.

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

· Четвертая фаза - ожидание. В это состояние процесс переходит, если

а) необходимо завершить операцию ввода/вывода

б) истекло время исполнения процесса по таймеру

· Пятая фаза- завершение. В это состояние процесс переходит, если:

а) операционная система завершила его исполнение

б) произошла фатальная ошибка времени исполнения.

 

Изменением состояния процессов занимается операционная система, совершая операции над ними. Количество таких операций в нашей модели пока совпадает с количеством стрелок на диаграмме состояний. Удобно объединить их в три пары:

 

создание процесса – завершение процесса;

приостановка процесса (перевод из состояния исполнение в состояние готовность) – запуск процесса (перевод из состояния готовность в состояние исполнение);

блокирование процесса (перевод из состояния исполнение в состояние ожидание) – разблокирование процесса (перевод из состояния ожидание в состояние готовность).

 

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

 

 

Контекст процесса.

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

 

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

Все данные подразделяются на:

инициализируемые неизменяемые данные (например, константы);

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

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

стек пользователя;

данные, расположенные в динамически выделяемой памяти (например, с помощью стандартных библиотечных C функций malloc(), calloc(), realloc()).

 

Контекст можно разделить условно на две составляюшие:

регистровый контекст:

содержимое регистров процессора;

системный контескт:

состояние, в котором находится процесс;

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

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

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

сведения об устройствах ввода-вывода, связанных с процессом (например, какие устройства закреплены за процессом, таблицу открытых файлов).

 

Контекст ядра - объединение системного контекста и регистрового контекста. В данные ядра входят:

идентификатор пользователя — UID,

групповой идентификатор пользователя — GID,

идентификатор процесса - — PID,

идентификатор родительского процесса — PPID.

Присвоение идентификационных номеров процессов начинается с номера 0, который получает процесс kernel при старте операционной системы.

 

Операции над процессами.

ОС должна иметь возможность выполнять определенные операции над процессами:

 

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

· уничтожение

· возобновление

· изменение приоритета

· блокирование

· пробуждение

· запуск

 

Создание нового процесса состоит из нескольких подопераций:

присвоение имени

включение этого имени в список имен процессов, известных ОС

присвоение начального приоритета

формирование БУП

выделение процессу начальных ресурсов

Новый процесс может породить дочерние процессы.

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

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

Изменение приоритета - это изменение значения приоритета в БУП.

Прерывания в ОС.
Прерывание - это событие, при котором меняется нормальная последовательность команд, выполняемых ЦП.
Если произошло прерывание, то:

Управление передается ОС

ОС запоминает состояние прерванного процесса

ОС анализирует тип прерывания и передает управление соответствующей программе по обработке данного типа прерывания.