Лекция №3 13.10.2011

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

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

Почему появились ОС:

Увеличение аппаратных возможностей компьютеров (количества памяти, быстродействия, появления дисковой памяти большого объема), а также появление разнообразных периферийных устройств, привело к необходимости пересмотра того, как должны работать программы. Массовый выпуск компьютеров потребовал унификации доступа из программ к различным устройствам. Возникла идея, что из программы можно обращаться к устройству без учета особенностей его аппаратной реализации. Это возможно, если обращение к устройству идет не напрямую, а через прилагающуюся программу – драйвер устройства (по-английски driver означает "водитель"). Появились операционные системы - наборы драйверов и программ, распределяющих ресурсы компьютера между разными программами. Программное обеспечение стало разделяться на системное и прикладное. Системное программное обеспечение – непосредственно обращающееся к аппаратуре, прикладное – решающее какие-либо прикладные задачи и использующее аппаратные возможности компьютера не напрямую, а через вызовы программ операционной системы. Прикладные программы стали приложениями операционной системы, или, сокращенно, приложениями (applications). Этот термин означает, что программа может работать только под управлением операционной системы. Если на том же компьютере установить другой тип операционной системы, программа-приложение первой операционной системы не будет работать.

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

Существуют различные типы ОС:

• Пакетные (набор программ выполняется в заданном порядке)

• Реального времени

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

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

Если не выполняется обработка критических ситуаций либо она происходит недостаточно быстро, система жёсткого реального времени прерывает и блокирует операцию, чтобы не пострадала надёжность и готовность остальной части системы. Примерами систем жёсткого реального времени могут быть — бортовые системы управления (на самолёте, космическом аппарате, корабле, и пр.), системы аварийной защиты, регистраторы аварийных событий.^[6]

Системы мягкого реального времени характеризуются возможностью задержки реакции, что может привести к увеличению стоимости результатов и снижению производительности системы в целом. Примером может служить работа компьютерной сети.^[7] Если система не успела обработать очередной принятый пакет, это приведет к остановке на передающей стороне и повторной посылке (в зависимости от протокола). Данные при этом не теряются, но производительность сети снижается.

• Многозадачные

Речь будет вестись об многозадачных операционных системах семейств Unix и Windows.

Операционная система в общем случае состоит из следующих компонентов

• Загрузчик

• Ядро

• Командный процессор (интерпретатор)

• Драйверы устройств

• Интерфейс

Процесс загрузки любой ОС на компьютере x86 архитектуры выглядит следующим образом :

Включается тумблер питания. Производится самодиагностика блока питания. Когда все электрические параметры в норме БП посылает сигнал Power Good процессору. Время между включением питания и уходом сигнала обычно 0.1-0.5 секунд.

Таймер микропроцессора получает сигнал Power Good. С получением этого сигнала таймер перестает посылать сигнал Reset процессору, позволяя тому включиться.

CPU начинает выполнять код ROM BIOS. Процессор загружает ROM BIOS начиная с адреса FFFF:0000. По этому адресу прописан только переход на адрес настоящего кода BIOS ROM.

ROM BIOS проверяет выключение это или перезагрузка. Процедура два байта по адресу 0000:0472. Любое значение отличное от 1234h является свидетельством "холодного" старта.

POST (Power On Self Test).:

Система выполняет начальный тест железа (POST). Каждая ошибка, встречающаяся на этом этапе сообщается определенными звуковыми кодами, так как видео система еще не инициализирована. Также с помощью контрольной суммы проверяется целостность самого BIOS.

Если это включение ROM BIOS запускает полный POST. Если это перезагрузка, то из POST процедуры исключается проверка оперативной памяти.

В ходе POST BIOS проверяет работоспособность контроллеров на материнской плате, задаёт низкоуровневые параметры их работы (например, частоту шины и параметры центрального микропроцессора, контроллера оперативной памяти, контроллеров, AGP, PCI, USB)

BIOS ищет адаптеры, системные шины и контроллеры, которые могут потребовать загрузки своего BIOS-а. (Видеокарт, жестких дисков и т.д.)

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

Если первым является жесткий диск, BIOS проверяет самый первый сектор диска на наличие Master Boot Record (MBR).

Сектор диска — минимальная адресуемая единица хранения информации на дисковых запоминающих устройствах.

Master Boot Record - первый сектор на цилиндре 0, головке 0, 512 байт размером. Если она находится, то загружается в память по адресу 0000:7C00, потом проверяется на правильную сигнатуру - два последних байта должны быть 55AAh. Отсутствие MBR или этих проверочных байт останавливает процесс загрузки и выдает предупреждение. Сама MBR состоит из двух частей - системного загрузчика (partition loader или Boot loader), программы, которая получает управление при загрузке с этого жесткого диска; таблицы разделов (партиций), которая содержит информацию о логических дисках, имеющихся на жестком диске.

Загрузчик, находящийся в МБР, называется первичным. Такой маленькой программе обычно не под силу загрузить современную ОС; все, что она может сделать - это загрузить в память более мощную программу - вторичный загрузчик.

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

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

(подробно о загрузке XP - http://www.winblog.ru/2006/12/08/08120608.html )

Перейдем к ядру ОС.

Ядро́ — центральная часть операционной системы (ОС), обеспечивающая приложениям cкоординированный доступ к ресурсам компьютера, таким как процессорное время, память, внешнее аппаратное обеспечение, внешнее устройство ввода и вывода информации. Ядро обеспечивает работу механизмов межпроцессного взаимодействия. Также обычно ядро предоставляет сервисы файловой системы и сетевых протоколов.

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

Работа ядра современной ОС невозможна без механизма процессорных прерываний.

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

В зависимости от источника возникновения сигнала прерывания делятся на:

• асинхронные или внешние (аппаратные) — события, которые исходят от внешних источников (например, периферийных устройств) и могут произойти в любой произвольный момент: сигнал от таймера, сетевой карты или дискового накопителя, нажатие клавиш клавиатуры, движение мыши. Факт возникновения в системе такого прерывания трактуется как запрос на прерывание (англ. Interrupt request, IRQ) . Для обработки аппаратных прерываний существует специализированный чип - контроллер прерываний.

• синхронные или внутренние — события в самом процессоре как результат нарушения каких-то условий при исполнении машинного кода: деление на ноль или переполнение, обращение к недопустимым адресам или недопустимый код операции;

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

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

В реальном режиме элементом IDT (т.е. таблицы прерываний) является 32-битный адрес обработчика прерывания. (для 32-бит процессоров)

В защищённом режиме элементом IDT является шлюз прерывания длиной 8 байт, содержащий сегментный (логический) адрес обработчика прерывания, права доступа и др.

Что такое защищенный и реальный режим работы с памятью?

В реальном режиме процессоры работали только в DOS. Адресовать в реальном режиме дополнительную память за пределами 1мб вообще говоря нельзя.

Структура адресного пространства персоналки в реальном режиме:

Основная область памяти

В область, называемую основной областью памяти (англ. conventional memory), загружается таблица векторов прерываний, различные данные BIOS, а также могут загружаться 16-битные программы DOS. Основная область памяти занимает 640 Кбайт начиная с адреса 0000:0000.

Upper Memory Area – UMA - занимает 384 Кбайт и используется для размещения информации об аппаратной части компьютера. Область условно делится на три области по 128 Кбайт. Первая область служит для видеопамяти. Через вторую область доступны BIOS адаптеров. Третья область используется системной BIOS

Защищённый режим

В качестве простого примера защищенного режима можно взять его первую реализацию - в процессоре Intel 80286. В защищённом режиме этот 16-битный процессор может адресовать до 16 Мбайт виртуальной памяти за счёт изменения механизма адресации. Переключение из реального режима в защищённый происходит программно и относительно просто, однако для обратного перехода необходим аппаратный сброс процессора. Для отслеживания текущего режима работы процессора используется регистр слово состояния машины (MSW). Программы реального режима без модификаций в защищённом режиме исполняться не могут, также как и программы BIOS машины.

Суть защищённого режима данного процессора в следующем: программист и разрабатываемые им программы используют логическое адресное пространство, размер которого может составлять 16 мегабайт. Логический адрес преобразуется в физический адрес автоматически с помощью схемы управления памятью (MMU), являющимся аппаратным блоком процессора. Благодаря защищённому режиму, в памяти может храниться только та часть программы, которая необходима в данный момент, а остальная часть может храниться во внешней памяти (например, на жёстком диске). В случае обращения к той части программы, которой нет в памяти в данный момент, операционная система может приостановить программу, загрузить требуемую секцию кода из внешней памяти и возобновить выполнение программы. Следовательно, становятся допустимыми программы, размер которых больше объема имеющейся памяти, и пользователю кажется, что он работает с большей памятью, чем на самом деле.

Физический адрес формируется следующим образом. В сегментных регистрах хранится, индекс дескриптора в таблице дескрипторов (13 бит) (называется селектор), 1 бит, определяющий к какой таблице дескрипторов будет производиться обращение (к локальной или к глобальной) и 2 бита запрашиваемого уровня привилегий. Далее происходит обращение к соответствующей таблице дескрипторов и соответствующему дескриптору, который содержит начальный 24-битный адрес сегмента, размер сегмента и права доступа, после чего вычисляется необходимый физический адрес путём сложения адреса сегмента со смещением из 16-разрядного регистра.

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

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

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

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

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

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

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

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

Таким образом, возможность обеспечения (при поддержке операционной системы) для программы "видимости" практически неограниченной (характерный размер для 32-разрядных архитектур 2³² = 4 Гбайт) адресуемой пользовательской памяти (логическое адресное пространство) при наличии основной памяти существенно меньших размеров (физическое адресное пространство) – очень важный аспект.

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

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

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

После разбиения менеджером памяти виртуального адресного пространства на страницы виртуальный адрес преобразуется в упорядоченную пару (p,d), где p – номер страницы в виртуальной памяти, а d – смещение в рамках страницы p, внутри которой размещается адресуемый элемент. Процесс может выполняться, если его текущая страница находится в оперативной памяти. Если текущей страницы в главной памяти нет, она должна быть переписана (подкачана) из внешней памяти. При этом возникает прерывание, называемое page fault (страничный отказ). Обработка страничного нарушения заключается в том, что выполнение команды прерывается, затребованная страница подкачивается из конкретного места вторичной памяти в свободный страничный кадр физической памяти и попытка выполнения команды повторяется. При отсутствии свободных страничных кадров на диск выгружается редко используемая страница.

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

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

Подсчитаем примерный размер таблицы страниц. В 32-битном адресном пространстве при размере страницы 4 Кбайт (Intel) получаем 2³²/2¹²=2²⁰, то есть приблизительно миллион страниц, а в 64-битном и того более. Таким образом, таблица должна иметь примерно миллион строк (entry), причем запись в строке состоит из нескольких байтов. Заметим, что каждый процесс нуждается в своей таблице страниц (а в случае сегментно-страничной схемы желательно иметь по одной таблице страниц на каждый сегмент).

Понятно, что количество памяти, отводимое таблицам страниц, не может быть так велико. Для того чтобы избежать размещения в памяти огромной таблицы, ее разбивают на ряд фрагментов. В оперативной памяти хранят лишь некоторые, необходимые для конкретного момента исполнения фрагменты таблицы страниц. В силу свойства локальности число таких фрагментов относительно невелико. Выполнить разбиение таблицы страниц на части можно по-разному. Наиболее распространенный способ разбиения – организация так называемой многоуровневой таблицы страниц. Для примера рассмотрим двухуровневую таблицу с размером страниц 4 Кбайт, реализованную в 32-разрядной архитектуре Intel.( в 64-разрядной возможны 4K, 8K, 64K, 256K, 1M, 4M, 16M, 256M)

Таблица, состоящая из 2²⁰ строк, разбивается на 2¹⁰ таблиц второго уровня по 2¹⁰ строк. Эти таблицы второго уровня объединены в общую структуру при помощи одной таблицы первого уровня, состоящей из 2¹⁰ строк. 32-разрядный адрес делится на 10-разрядное поле p₁, 10-разрядное поле p₂ и 12-разрядное смещение d. Поле p₁ указывает на нужную строку в таблице первого уровня, поле p₂ – второго, а поле d локализует нужный байт внутри указанного страничного кадра

При помощи всего лишь одной таблицы второго уровня можно охватить 4 Мбайт (4 Кбайт x 1024) оперативной памяти. Таким образом, для размещения процесса с большим объемом занимаемой памяти достаточно иметь в оперативной памяти одну таблицу первого уровня и несколько таблиц второго уровня. Очевидно, что суммарное количество строк в этих таблицах много меньше 2²⁰. Такой подход естественным образом обобщается на три и более уровней таблицы. 2-Уровневый подход используется в 32-битных ос семейств Windows и Linux.

Естественно, такой подход замедляет преобразование адресов. Поэтому был реализован аппаратный кэш в виде ассоциативной памяти, иногда также употребляют термин буфер поиска трансляции (translation lookaside buffer – TLB).

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

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

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

В современных системах Windows и Unix используется именно Paging, а в более старых – свопинг. Файл для пейджинга Windows - pagefile.sys находится в корне активного раздела диска(он системный и скрыт).

Управление процессами:

На предыдущих страницах я пользовался термином процесс, не определив его. Исправим эту ситуацию:

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

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

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

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

Инициатором рождения нового процесса после старта операционной системы может выступить либо процесс пользователя, совершивший специальный системный вызов, либо сама операционная система, то есть, в конечном итоге, тоже некоторый процесс. В конкретных операционных системах состояния процесса могут быть еще более детализированы, могут появиться некоторые новые варианты переходов из одного состояния в другое. Так, например, модель состояний процессов для операционных систем семейства Windows NT содержит 7 различных состояний, а для операционной системы Unix – 9.

Process Control Block и контекст процесса

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

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

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

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

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

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

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

Ее состав и строение зависят, конечно, от конкретной операционной системы. Во многих операционных системах информация, характеризующая процесс, хранится не в одной, а в нескольких связанных структурах данных. Эти структуры могут иметь различные наименования, содержать дополнительную информацию или, наоборот, лишь часть описанной информации. Для нас это не имеет значения. Для нас важно лишь то, что для любого процесса, находящегося в вычислительной системе, вся информация, необходимая для совершения операций над ним, доступна операционной системе. Для простоты изложения будем считать, что она хранится в одной структуре данных. Мы будем называть ее PCB (Process Control Block) или блоком управления процессом. Блок управления процессом является моделью процесса для операционной системы. Любая операция, производимая операционной системой над процессом, вызывает определенные изменения в PCB . В рамках принятой модели состояний процессов содержимое PCB между операциями остается постоянным.

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

Процесс, инициировавший создание нового процесса, принято называть процессом-родителем (parent process), а вновь созданный процесс – процессом-ребенком (child process). В системе UNIX, если процесс-ребенок завершится, но процесс-родитель еще не считал код завершения, то такой процесс занимает идентификатор процесса (PID) и называется процессом-зомби.

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

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

Как происходит планирование процессов:

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

Существует несколько уровней планирования

Долгосрочное - Решение добавлении задания (процесса) в пул выполняемых в системе (при каждом запуске задания)

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

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

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

Цель планирования(диспетчеризации) – максимальная загрузка процессора, достигаемая с помощью многозадачности.

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

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

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

• Каким пользователем запущен процесс или сформировано задание.

• Насколько важной является поставленная задача, т. е. каков приоритет ее выполнения.

• Сколько процессорного времени запрошено пользователем для решения задачи.

• Каково соотношение процессорного времени и времени, необходимого для осуществления операций ввода-вывода.

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

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

Исполнение любого процесса можно рассматривать как цикл CPU / I-O – чередование периодов использования процессора и ожидания ввода-вывода.

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

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

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

Множество Алгоритмов планирования:

Стратегия First-Come-First-Served (обслуживание в порядке поступления) – Простейший алгоритм планирования. Представим себе, что процессы, находящиеся в состоянии готовность, выстроены в очередь. Когда процесс переходит в состояние готовность, он помещается в конец этой очереди. Очередь подобного типа имеет в программировании специальное наименование – FIFO¹⁾, сокращение от First In, First Out (первым вошел, первым вышел).

Такой алгоритм выбора процесса осуществляет невытесняющее планирование.

Round Robin (RR)

Модификацией алгоритма FCFS является алгоритм, получивший название Round Robin или сокращенно RR. По сути дела, это тот же самый алгоритм, только реализованный в режиме вытесняющего планирования. Можно представить себе все множество готовых процессов организованным циклически – процессы сидят на карусели. Карусель вращается так, что каждый процесс находится около процессора небольшой фиксированный квант времени, обычно 10 – 100 миллисекунд (см. рис. 3.4.). Пока процесс находится рядом с процессором, он получает процессор в свое распоряжение и может исполняться.

При очень больших величинах кванта времени, когда каждый процесс успевает завершить свой CPU burst до возникновения прерывания по времени, алгоритм RR вырождается в алгоритм FCFS.

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

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

При предсказании учитывается недавняя история вычислений.