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

Вычислительная среда (система) – это совокупность аппаратуры и операционной среды.

ОС – это преобразователь с языка возможностей аппаратуры на язык пользователя.

Аппаратура:

• ЦП (центр и ядро системы 4*3 ГГц)

  • Кэш (скорость сравнима со скоростью ЦП)

• ОЗУ (частота системной шины 0,5-1 ГГц)

• устройства ввода-вывода

• каналы ввода-вывода

• групповые устройства ввода-вывода

Ресурс – это объект, распределяемый (в пространстве либо во времени) внутри системы.

2 способа распределения ресурсов:

• Централизованный (сейчас основной) – кто-то один отвечает

• Децентрализованный – каждое приложение отвечает

Основные функции операционной среды.

1. Обеспечение интерфейса между аппаратурой и прикладными программами

2. Предоставление средств для работы с большими структурами данных

3. Распределение времени процессора

4. Управление оперативной памятью

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

6. Управление вводом-выводом

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

8. Синхронизация

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

Эксплуатационные требования к ОС:

1. Надежность – не ниже надежности аппаратуры.

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

3. Предсказуемость операционных характеристик вычислительной системы – скорость (время) выполнения задач.

4. Эффективность – ОС должна занимать минимум ресурсов (оперативная память, время ЦП).

5. Удобство работы пользователя в ОС.

ОС общего назначения как правило использует централизованное управление ресурсами.

Все программы ОС и приложений подчиняются главной программе – супервизору (ядру).

Функции супервизора:

1. Контроль и управление выполнения задач пользователей.

2. Организация связи между программами.

3. Защита ОС и пользователей.

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

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

1. Простота организации – все основные функции в одном месте.

2. Простота реализации функций управления и защиты – все обращения с системным функциям и внешней среде проходят через супервизор.

Недостатки супервизора:

1. Супервизор может быть узким местом среды – при интенсивном обращении к супервизору за служебными функциями.

2. Трудность внесения изменений в функции супервизора – все функции супервизора тесно связаны.

Процессы.

Аппаратура ЭВМ работает параллельно.

ОС выполняет множество задач.

Процесс – формализация идеи независимости

Работа (задание)

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

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

Свойства процессов:

1. Независимые работы

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

3. Различные скорости выполнения работ

Иногда процессам необходимо обмениваться информацией (межпроцессное взаимодействие).

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

Процесс – это пространство состояний набора переменных (переменные состояния).

Состояния описываются заданием значений всех переменных.

Действие – это присваивание значений некоторым переменным состояния.

Функция действия – это функция, отображающая состояние в действие.

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

Переменные состояния – это ячейки памяти с данными.

Процесс – это некая программа, данные, которые она обрабатывает и некий дескриптор, описывающий состояние процесса в реальной вычислительной среде.

Дескриптор – это некоторая структура данных, в которой содержится информация о процессе

1. Переменная состояния (определяет текущее состояние процесса):

   1. готов к работе – в очереди готовых процессов

   2. работающий (текущий) – на процессоре

   3. заблокирован – в очереди ожидания (операции ввода-вывода, операции синхронизации)

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

3. Информация о ресурсах, которыми владеет процесс.

4. Разделяемые переменные, структуры данных, которые необходимы для общения с другими процессами.

Общение между процессами.

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

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

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

Участок программы, в котором используется критический ресурс, называется критическим участком.

Критические участки должны быть взаимно исключаемыми. Нужен некий механизм синхронизации.

Механизм синхронизации.

Свойства:

1. Если один или более процессов желает войти в критический участок, то один из них должен получить разрешение на вход.

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

Инструменты синхронизации.

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

2. Инструменты, основанные на низкоуровневых примитивах – низкоуровневые методы синхронизации (семафоры).

3. Высокоуровневые инструменты синхронизации.

Два источника параллелизма:

1. Независимые потоки команд (различные программы).

2. Несвязанные потоки данных.

Синхронизация на основе операций блокировки памяти.

Все операции в ЦП – неделимые для процессов.

Алгоритм Деккера (для синхронизации двух процессов).

{

bool c1, c2;

int q;

c1 = c2 = 0;

q = 1;

//c1, c2 - намерение процесса войти в критический участок

parbegin

процесс 1: {

c1 = 1;

while (c2 == 1) {

if (q == 2) {

c1 = 0;

while (q == 2) { }

c1 = 1;

}

}

<критический участок>

c1 = 0;

q = 2;

<оставшаяся часть первого процесса>

}

процесс 2: {

c2 = 1;

while (c1 == 1) {

if (q == 1) {

c2 = 0;

while (q == 1) { }

c2 = 1;

}

}

<критический участок>

c2 = 0;

q = 1;

<оставшаяся часть второго процесса>

}

parend

}

Минус – активное ожидание входа в критический участок.

Метод, основанный на неделимой операции «проверить и установить» - ПИУ – TSL

ПИУ(локальная переменная, общая переменная) => лок = общ; общ = 1;

begin int общ; общ := 0;

parbegin

П1:

begin

int лок1;

лок1 := 1;

do while (лок1 = 1)

ПиУ(лок1, общ)

end

<критический участок>

общ := 0;

<остальное>

end

П2:

begin

int лок2;

лок2 := 1;

do while (лок2 = 1)

ПиУ(лок2, общ)

end

<критический участок>

общ := 0;

<остальное>

end

parend

end

Минус – активное ожидание

Механизмы с пассивным ожиданием входа в КУ.

Реализуется через средства, расположенные в супервизоре.

Семафоры – прием, позволяющий реализовать пассивное ожидание.

Бывают общие и двоичные.

Семафор – целочисленная переменная, над которой определены 2 неделимые операции: операция – запросить ресурс либо вход в КУ, и – вернуть ресурс или выйти из КУ.

1)

2) Если , то процесс продолжает работать

3) Если , то процесс останавливается и встает в очередь

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

1)

2) Если , то процесс продолжает работу

3) Если , то один из процессов удаляется из очереди ожидания, получает ресурс и конкурирует с текущим процессом за право получить время ЦП.

Количество конкурирующих процессов ( – количество ресурсов в системе

Возврат в прикладной процесс произойдет после завершения запроса к супервизору.

Двоичный семафор

1 – ни один процесс не находится в КУ

0 – один процесс находится в своем КУ

-1 – 1 процесс в КУ, 1 процесс ожидает вход в КУ

Алгоритм синхронизации 2-х процессов:

begin

int своб; своб = 1;

parbegin

П1:

begin

<начало П1>

P(своб)

КУ П1

V(своб)

<конец П1>

end

П2:

begin

<начало П2>

P(своб)

КУ П2

V(своб)

<конец П2>

end

parend

end

Задача поставщик-потребитель (используется при вводе-выводе)

Используется общий семафор

2 процесса:

1. поставляет данные для обработки

2. ведет обработку данных

Для общения процессов используется буфер обмена.

Общие семафоры:

1. Буф – количество свободных буферов

2. Зан – количество занятых буферов

Двоичный семафор: Синхро – используется для синхронизации работы с очередями

begin int буф, зан, синхро;

буф = <количество буферов в системе, выделенных для решения задач>

зан = 0;

синхро = 1;

parbegin

П1(поставщик):

begin

do while (true)

<приготовить данные>

P(буф)

P(синхро)

<взять буфер из списка>

<послать сообщение>

V(зан)

V(синхро)

end

end

П2(потребитель):

begin

do while (true)

P(зан)

P(синхро)

<получить сообщение>

V(буф)

V(синхро)

<обработка сообщения>

end

end

parend

end

В нетривиальных системах очень часто требуется организация сложного ожидания:

1. Одного из нескольких ресурсов

2. Нескольких ресурсов

3. Одного из нескольких событий

4. Нескольких событий

5. 1+2+3+4

2 и 4 необходимо реализовывать через 1 и 3.

Мониторы.

Монитор – набор управляющих структур и процедуры доступа к ним. Эти процедуры неделимы для прикладных процессов и реализованы в ядре/супервизоре.

Монитор позволяет организовать сложные ожидания и взаимодействия процессов.

Ожидания:

• 1 из ресурсов из списка

• 1 из событий из списка

• ограничения ожидания по времени

Монитор, основанный на таблице синхронизации.

Таблица синхронизации

Процесс	Обл. сохр	Готовность	Таймер	Ресурсы	Соб1	Соб2	…	СобN
P1	Обл1	Не готов	0	Список1	0	1		1
P2	Обл2	Готов	0	0	0	0		0
P3	Обл3	Не готов	5	Список3	1	1		1
…
PM	ОблM	Готов	0	0	0	0		0

P_M – системный процесс

Процедуры работы с ТС:

1. TP(указатель на список ресурсов, указатель на список событий, таймаут) – запрос всего

2. TV(ресурс) – возврат ресурсов

3. TWAIT(указатель на список событий, таймаут) – запрос событий

4. TPOST(событие) – извещение о наступлении события

Процесс CLOCK

TP(указатель на список ресурсов, указатель на список событий, таймаут)

begin <задержать текущий процесс>

for i=1 to <число семафоров в процессе> do

if семафор(i)>0 then

<взять ресурс из списка ресурсов>

<передать семафор и экземпляр ресурса в область сохранения процесса>

<активизировать задержанный процесс>

end

end

табл[текущий, готовность]="не готов"

табл[текущий, таймер]=Tout

табл[текущий, ресурсы]=указатель на список ресурсов

<отметить в столбцах заказанные события>

<активизировать наиболее приоритетный процесс>

end

TV(семафор, ресурс)

begin <задержать текущий процесс>

for i=1 to <число строк в таблице> do

if <список ожидающих ресурсов содержит возвращаемый ресурс> then

<передать в область сохранения Pi адрес семафора и адрес ресурса>

for j=3 to <количество столбцов в таблице> do

табл[i, j]=0

end

табл[i, готов]=да

if i<текущий then

<активизировать Pi>

else

<активизировать текущий>

end

end

end

<возвратить ресурс в систему>

<активизировать текущий процесс>

end

TWAIT(указатель на список событий, Tout)

begin <задержать текущий процесс>

табл[текущий, готовность]= не готов

табл[текущий, таймер] = Tout

<отметить в таблице события, указанные в запросе>

<активизировать наиболее приоритетный процесс>

end

TPOST(событие)

begin <задержать текущий процесс>

for i = 1 to <количество строк в таблице> do

if табл[i, событие] <> 0 then

for j = 3 to <количество столбцов в таблице> do

табл[i, j] = 0

end

<отметить в области сохранения Pi наступление события>

табл[i, готовность] = готов

if i < текущий then

<активизировать Pi>

else

<активизировать текущий процесс>

end

end

end

<активизировать текущий процесс>

end

Процесс CLOCK

begin

do while (true)

<запустить на один цикл работы таймера текущий процесс>

for i = 1 to <количество строк в таблице> do

if табл[i, таймер] then

табл[i, таймер]--

if табл[i, таймер] = 0 then

for i = 3 to <количество столбцов в таблице> do

табл[i, j] = 0

end

табл[i, готов] = да

end

end

текущий = <самый приоритетный готовый процесс>

end

end

Тупики.

Ситуация, в которой процессы ждут друг друга неопределенно долго.

Вычислительная система = множество состояний + множество процессов

Процесс – это функция, отображающая одно состояние в другое

Необходимые условия тупика:

1. Условие взаимоисключения (монопольного управления ресурсами).

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

3. Условие неперераспределяемости ресурсов (ресурсы нельзя отобрать насильно, ресурсы освобождаются добровольно после завершения обработки).

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

Тупик может наступить при выполнении всех 4 условий. Это необходимые условия.

Направления борьбы с тупиками:

1. Предупреждение (предотвращение) тупиков (нарушается одно из условий – стратегия Хавендера). Минус – неэффективное использование ресурсов.

2. Обход тупика (алгоритм банкира).

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

Обнаружение тупика и восстановление после него.

1. Стратегия Хавендера – нарушение одного из необходимых условий.

   1. Нарушать нельзя (иначе - однопрограммность).

   2. Все ресурсы, необходимые для обработки, запрашиваются сразу (в одном запросе). Минус – неэффективное использование ресурсов (простаивание ресурса по времени).

   3. Разрешение насильного изъятия ресурсов у процессов. Минусы:

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

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

   4. Для всех процессов вводится упорядочение всех ресурсов по типам, запрос ресурсов возможен только в соответствие с номерами типов (в порядке, предусмотренном типами). Минусы:

      1. Упорядочение ресурсов по типам может быть неудобно для некоторых процессов.

      2. Усложняется разработка приложений.

      3. Неэффективное использование ресурсов (простаивание ресурсов).

2. Алгоритм банкира – обход тупика.

Менее жесткие ограничения (по сравнению со стратегией Хавендера) => лучшее использование ресурсов.

Алгоритм:

Исходная информация:

1. Имеется K единиц ресурса.

2. Имеется N процессов.

3. Для каждого процесса известна потребность в ресурсах:

   1. Максимальная потребность – MAXР.

   2. Количество выделенных ресурсов – КВР.

   3. Остаток потребности в ресурсах – ОР.

Проверка безопасности состояния при выделении ресурса (по запросу).

begin

сбоврес = k

for i = 1 to N do

begin

свобрес -= КВР[i]

ОР[i] = MAXР[i] - КВР[i]

тупик[i] = true

end

признак = true

do while признак

begin

признак = false

for i = 1 to N do

begin

if ОР[i] <= свобрес then

begin

свобрес += КВР[i]

признак = true

тупик[i] = false

end

end

end

if свобрес = K then

<состояние системы безопасное>

else

<состояние небезопасно>

end

3. Обнаружение и восстановление.

Установить факт тупика.

Определить количество процессов, вовлеченных в тупик.

Определить типы ресурсов, заблокированных в тупике.

Определение жертв-процессов.

Изъятие ресурсов у жертв => потеря проделанной работы.

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

Распределение времени процессора.

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

В вычислительной среде имеется смесь активных задач.

Различают 2 режима мультипрограммирования:

1. Режим разделения времени.

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

2. Режим квантования времени.

Нет деления на основные и фоновые задачи.

Планирование времени процессора включает:

1. Способ выбора готового процесса на исполнение

2. Способ вычисления величины кванта

В общем случае каждому процессу ставится в соответствие число – приоритет (важность процесса).

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

Статистические:

• Объем занимаемой памяти

• Ожидаемое время выполнения

• Ожидаемый ввод/вывод

• Коэффициент важности задачи

Динамические:

• Ресурсы, принадлежащие процессу

• Общее время выполнения задачи

• Количество процессорного времени, полученного за некоторый последний отрезок времени

• Объем ввода/вывода за последний период времени

• Время пребывания в заблокированном состоянии

При планировании используют следующие показатели производительности:

1. Загрузка ресурсов

2. Время простоя

3. Пропускная способность ВС

4. Время выполнения заданий

3 класса алгоритмов планирования:

1. По наивысшему приоритету (HPF – High Priority First)

2. Круговорот

3. Планирование с обратной связью – в системах пакетной обработки

Многоуровневое планирование

Разбивает задачу планирования на подзадачи

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

1. Работа с очередями

2. Переключение процессов

3. Вычисление приоритетов

4. Текущее измерение характеристик процессов

Элементы многоуровневого планирования:

1. Диспетчер

2. Кратковременный планировщик (более трудоемкий)

3. Долговременный планировщик (самый трудоемкий) – пересчитывает приоритеты

Управление памятью.

Управление памятью – отображение информации в оперативную память с помощью трех функций:

1. Именующая функция => отображает имя объекта, данное пользователем, в однозначный идентификатор информации.

2. Функция памяти => отображает идентификатор в программные адреса.

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

Имена пользователей, данные объектам –

Обработка программ включает этапы:

1. Компиляция

2. Сборка

3. Загрузка

Разрешение ссылок может быть выполнено несколькими способами:

1. Объединение модулей при компиляции

2. Объединение модулей

   1. до загрузки на этапе сборки

   2. во время загрузки

3. Объединение модулей откладывается до запуска на счет и реализуется системой (ОС) в процессе счета.

Исходная информация о модулях (объединяемых):

1. Модуль

2. Длина модуля.

3. Имена, описанные в модуле, на которые возможны ссылки из внешних модулей (ссылки внутрь).

4. Имена, не описанные в модуле, но на эти имена имеются ссылки (ссылки наружу).

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

Работа сборщика.

Модули располагаются друг за другом.

При сборке составляется таблица сборщика.

Имя	Ссылка разрешена	Адрес объекта / список неразрешенных ссылок
Имя 1	1	Адрес объекта, именуемый имя1
Имя2	0	Указатель на список неразрешенных ссылок

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

Главный вопрос задач распределения памяти состоит в том, чтобы решить, как объединенный модуль записать в ОЗУ.

Функция памяти – выдает переместимому модулю реальные ячейки памяти.

1. Статическое распределение

Привязку реализует

1. программист, компилятор до загрузки

2. загрузчик во время загрузки

1. Динамическое распределение

Привязка происходит во время выполнения программы

Узловые моменты привязки к памяти:

1. Программирование в абсолютных адресах => объединения отображений И и П раз и навсегда.

2. Программирование в символьных обозначениях.

Компилятор порождает адреса вместо символьных имен:

1. Порождаемые адреса – фиксированные абсолютные.

Привязка П происходит сразу же за И.

2. Порождаемые адреса допускают настройку и при загрузке получают абсолютные значения.

Привязка к памяти происходит во время загрузки.

3. Порождаемые адреса допускают настройку и получают абсолютные значения при каждом обращении к адресуемым объектам.

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

1, 2a, 2b – статическое

2c – динамические

Стратегии:

1. Перекрытие программ – планируется пользователем

2. Попеременная загрузка заданий – реализуется системой

3. Сегментация программ – ОС

4. Страничная организация памяти – ОС

5. 3+4 = Сегментация программ со страничной организацией памяти