...продолжение второй лекции.

Shortest Job First

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

Shortest Remaining Time (SRT)

SRT - наименьшее оставшееся время.

Выполняющийся процесс может быть прерван (вытеснен с выполнения), если поступит процесс с меньшим оценочным временем выполнения.

Например, запрошенное время для выполнения процесса было 5 минут; 2 минуты он уже выполнялся, осталось - 3 минуты, и пришел процесс, запрошенное время которого - 2.5 минуты; следовательно время, которое запросил процесс меньше, чем время, оставшееся у процесса, который выполняется и он будет вытеснен.

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

Этот алгоритм так же приводит к бесконечному откладыванию, поэтому появился алгоритм HRRN.

Highest response ratio next (HRRN)

HRRN - наибольшее относительное время ответа.

Дисциплина с динамическим приоритетом. Приоритет процесса - динамический, вычисляется по формуле: p=(tw+ts)/(ts)

где ts - запрошенное время обслуживания, tw - время ожидания в очереди готовых процессов.

Чем дольше процесс простаивает в очереди, тем выше его приоритет. (Приоритет увеличивается при увеличении времени ожидания)

Итоги

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

Пользователи в перфокартах указывали время выполнения процессов. Если кто-то указал неправильное время выполнения (меньше, чем есть в действительности), то штрафовался на 1$ :)

Системы разделения времени

За терминалами сидят пользователи, которые не могут долго ждать, когда выполнится процесс. Комфортное время ожидания не может превышать 3 секунд.

1. Round Robin (RR)

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

Недостаток - статический квант времени.

В настоящее время используется модификация этого алгоритма путем назначения динамического кванта времени: Min Max Round Robin (MMRR) и другие.

2. Приоритетное планирование или многоуровневые очереди

В первую очередь с наивысшим приоритетом поступают вновь созданные процессы или процессы, завершившие ожидание ввода/вывода.

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

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

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

Переключение контекста

Нарисуем еще раз диаграмму состояний процесса

-это важнейшая абстракция любой ОС.

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

Режим ядра

ОС - программа, которая выполняется на самом высоком уровне привилегий. Например, в процессорах Intel 4 кольца защиты, и ОС Unix, Windows выполняются на нулевом уровне привилегий. Игры и приложения выполняются на третьем уровне привилегий. Сделано это для защиты системы.

Действия из диаграммы, которые выполняются ОС (на нулевом уровне привилегий): порождение процессов выполняет система. Породить процесс - это значит идентифицировать и выделить ему дескриптор (строку в таблице процессов). Таблица процессов - главная системная таблица, при этом на самом деле в наших системах процессы создаются по мере необходимости, ресурсы выделяются по мере надобности, то есть такая таблица не может быть статической, поэтому на самом деле это - не таблица, а связный список. В наших системах используется динамический пересчет приоритетов, который присутствует в реальных ОС, значит, процессы должны переставляться в очереди процессов, а проще всего это сделать при помощи связных списков, которые легко редактировать, и трудно сделать при помощи таблицы, которая является массивом. Это действие режима ядра.

Дальше процесс поименован, ему выделен дескриптор; для того, чтобы он мог начать выполняться, ему надо выделить память, которая выделяется системой. После этого он перейдет в очередь готовых процессов и квант времени выдаст система. => Все эти действия выполняются в режиме ядра.

Блокировка: процесс запросил ввод/вывод, ни одна система не позволяет процессу напрямую обратиться к внешним устройствам. Чтобы обратиться к устройству ввода/вывода, система перейдет в режим ядра.

== Коротко выше сказанное: ==

Принцип работы ОС с процессами:

1. Создание процесса - процесс поименован и ему назначен дескриптор.
2. ОС выдает процессу все ресурсы, кроме кванта времени.
3. ОС выдает процессу квант времени.
4. Принятие запроса на I/O от процесса и его обработка.
5. Система возвращает занятые ресурсы.

Тут Рязанова начала зачитывать Вахалию, стр. 64:

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

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

Коды ОС - тоже ресурсы системы.

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

Три события, переводящие систему в режим ядра:

• Системные вызовы
• Исключения
• Аппаратные прерывания

fork() - основной системный вызов создания процесса.

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

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

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

Контекст

Контекст бывает двух типов:

• Аппаратный контекст - содержимое регистров.
• Полный контекст

Аппаратный контекст входит в полный контекст. В полном контексте запоминаемая информация значительно шире. Сохранение аппаратного контекста в системе происходит очень часто, поддерживается аппаратно, для этого в системе есть команды

pusha

popa

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

Стремление сократить накладные расходы на переключение контекста привели к появлению потоков.

Процессы и потоки

Характерные черты процесса

Процесс имеет две характерные черты:

• Процесс владеет ресурсами
• Планирование и выполнение

1. Процесс владеет ресурсами

Процесс имеет защищенное виртуальное адресное пространство. Адресным пространством процесс владеет всё время.

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

2. Планирование и выполнение

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

В результате планирования процессу выделяется процессорное время.

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

thread

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

Задачи

В системе существуют две задачи, связанные с выполнением процессов:

• Планирование - постановка процессов в очередь.
• Диспетчеризация - непосредственное выделение процессу процессорного времени.

Единицей диспетчеризации может быть поток.

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

Отличительные черты потока

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

Поток владеет счетчиком команд.

Потоки бывают двух типов:

• Потоки режима пользователя
• Потоки режима ядра