Конспект лекций по дисциплине " Операционные системы"

Вид материалаКонспект
Имя процесса
Распределение времени процессора.
Специализированный процессор ввода-вывода
Внешние устройства управляются контроллерами
Системы разделения времени
Системы реального времени .
Мультипроцессорная обработка
Симметричная архитектура
Ассиметричное мультипроцессирование
Симметричное мультипроцессирование
Понятия процесса и потока
Дескриптор процесса
Контекст процесса
Вытесняющие и невытесняющие алгоритмы планирования.
Алгоритмы планирования, основанные на квантовании.
Алгоритмы планирования, основанные на приоритетах.
Смешанные алгоритмы планирования.
Планирование в системах реального времени.
Моменты перепланировки.
Мультипрограммирование на основе прерываний.
...
Полное содержание
Подобный материал:
1   2   3   4   5   6   7







Имя процесса

Максимальная потребность

Выделено


Остаток

б)

A

4

2

2




B

6

3

3




C

8

4

4

Допустим, процесс С запросил еще два устройства и его удовлетворили, то если один из процессов запросит то количество устройств, которое ему положено максимально или больше 1 для завершения, будет дедлок. Поэтому удовлетворять запрос С – опасно.

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

Один из них носит название “Алгоритм Банкира”.

Каждому процессу поставлено в соответствие целое число i (1 i N). Процессу i соответствуют его максимальная потребность в устройствах МАКС(i), количество устройств, выделенных ему в данный момент ВЫДЕЛУСТР(i), полагающийся ему остаток – ОСТАТОК(i) и признак МОЖЕТ НЕ ЗАКОНЧИТЬ(i).

Системы заводят глобальную переменную ОБЩУТР, обозначающую общее число имеющихся в системе устройств.

В начале работы неизвестно, может ли какой либо процесс окончиться МОЖЕТ НЕ ЗАКОНЧИТЬ(i) true для всех i.

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

Если состояние системы становится небезопасным, то она не удовлетворяет соответствующий запрос.


..........

СВОБУСТР:=ОБЩУСТР;

for i:=1 step 1 until N do

begin

СВОБУСТР:=СВОБУСТР-ВЫДЕЛУСТР(i);

МОЖЕТНЕЗАКОНЧИТЬ(i):=True;

ОСТАТОК(i):=МАКС(i)-ВЫДЕЛУСТР(i);

end;

ПРИЗНАК:=Ture;

do while (ПРИЗНАК);

ПРИЗНАК:=False;

for i:=1 step 1 until N do

begin

if МОЖЕТНЕЗАКОНЧИТЬ(i) and ОСТАТОК(i) <= СВОБУСТР;

СВОБУСТР:=СВОБУСТР+ВЫДЕЛУСТР(i);

ПРИЗНАК:=True;

end; end; end; end;

if СВОБУСТР=ОБЩУСТР then Состояние системы безопасное

else Состояние системы не безопасное

..........


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

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

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

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

В зависимости от этого ОС делятся на:
  • Системы пакетной обработки;
  • Системы разделения времени;
  • Системы реального времени.


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

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

Для пакетных ОС характерно совмещение операций ввода-вывода и вычислений. Такое совмещение может достигаться разными способами :
  1. Специализированный процессор ввода-вывода.

Иногда такие процессоры называют каналами. Канал имеет систему команд, отличающуюся от системы команд центрального процессора. Эти команды специально ориентированы для управления внешними устройствами :
    • установить магнитную головку;
    • напечатать строку и т.д.

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




  1. Внешние устройства управляются контроллерами.

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




Максимальный эффект при пакетной обработке достигается при наиболее полном перекрытии вычислений и ввода-вывода.

В случае одной задачи ускорение зависит от её характера. При преобладании вычислений или ввода-вывода ускорение практически отсутствует.


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

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


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

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

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


Мультипроцессорная обработка.

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

В настоящее время стало обычным явлением включение нескольких процессоров в архитектуру персонального компьютера.

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

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

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

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

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

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

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

Ассиметричное мультипроцессирование является наиболее простым способом организации. Этот способ иногда называют «ведущий - ведомый».

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

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

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

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

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


Понятия процесса и потока

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

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

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

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

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

Для этих целей в ряде современных ОС используется механизм многопоточной обработки. При этом вводится новая единица работы – поток выполнения, а понятие «процесс» в некоторой степени меняет смысл.

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

При управлении процессами ОС использует два основных типа информационных структур:
  • дескриптор процесса;
  • контекст процесса.

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

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

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

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

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

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

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

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

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

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

Планирование потоков включает в себя решение двух задач:
  • определение момента времени для смены текущего активного потока;
  • выбор для выполнения потока из очереди готовых потоков.

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

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

Планирование может быть динамическим или статическим.

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

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

Планировщик называется статическим, если он принимает решения о планировании не во время работы системы, а заранее.

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

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

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

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

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

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

Граф состояний потока в многозадачной среде можно представить как на рисунке:




«Вытеснение потока» означает прекращение его выполнения процессором, например, вследствие исчерпания отведенного для выполнения кванта времени.

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


Вытесняющие и невытесняющие алгоритмы планирования.

Все множество алгоритмов планирования можно разделить на два класса: вытесняющие и невытесняющие .

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

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

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

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

Почти все современные ОС, такие как UNIX, Windows NT/2000, OS-2, Windows 95/98 реализуют вытесняющие алгоритмы планирования потоков.


Алгоритмы планирования, основанные на квантовании.

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

Смена активного потока происходит, если:
  • поток завершился и покинул систему;
  • произошла ошибка;
  • поток перешел в состояние ожидания;
  • исчерпан квант процессорного времени.

Поток, исчерпавший свой квант, переводится в состояние готовности и ожидает в очереди. Граф состояний потока представлен на рисунке:



Поток инициировал

ввод-вывод

Кванты для потоков могут быть одинаковыми или различными.

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

Соответствующий граф состояний потока можно представить как:




Алгоритмы планирования, основанные на приоритетах.

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

В ОС Windows NT определено 32 уровня приоритетов и два класса потоков – потоки реального времени и потоки с переменными приоритетами.

Диапазон от 1 до 15 отведен для потоков с переменными приоритетами, а от 16 до 32 – для более критичных ко времени потоков реального времени.

Смешанные алгоритмы планирования.

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

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


Планирование в системах реального времени.

В системах реального времени главным критерием является обеспечение временных характеристик вычислительного процесса.

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

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

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


Моменты перепланировки.

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

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

Мультипрограммирование на основе прерываний.

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

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

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

Внешние прерывания возникают в результате действий пользователя или в результате поступления сигналов от аппарат­ных устройств. Данный класс прерываний является ассинхронным по отношению к потоку инструкций прерываемой программы.

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

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

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

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

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

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

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


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

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

В противном случае в зависимости от поступившей в процессор информации происходит автоматический вызов процедуры обработки прерывания, адрес которой находится в специальной таблице ОС, размещаемой либо в регистрах процессора, либо в определенном месте опера­тивной памяти.
  1. Автоматически сохраняется некоторая часть контекста прерванного потока, которая позволит ядру возобновить исполнение потока процесса после обработки прерывания. В это подмножество включаются значения счетчика команд, слова состояния машины, хранящего признаки основных режимов работы процессора (пример слова — регистр EFLAGS в Intel Pentium), а также нескольких регистров общего назначения, которые требуются программе обработки прерывания. Может быть сохранен и полный контекст процесса, если ОС обслуживает данное прерывание со сменой процесса.
  2. Одновременно с загрузкой адреса процедуры обработки прерываний в счетчик команд может автоматически выполняться загрузка нового значения слова состояния машины, которое определяет режимы работы процессора при обработке прерывания, в том числе работу в привилегированном режиме.
  3. Временно запрещаются прерывания данного типа, чтобы не образовалась очередь вложенных друг в друга потоков одной и той же процедуры. Детали выполнения этой операции зависят от особенностей аппаратной платформы, например может использоваться механизм маскирования прерываний..
  4. После того как прерывание обработано ядром ОС, прерванный контекст восстанавливается, и работа потока возобновляется с прерванного места.

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