Реферат: Комплекс программ, предназначенный для обеспечения определенного уровня эффективности вс (вычислительной системы) за счет автоматизированного управления ее работой и предоставления пользователю определенного рода услуг.

Вопрос 1. Определение ОС. Место ОС в иерархической архитектуре вычислительной системы.


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

ОС должна обеспечивать определённый уровень производительности, безопасности и надёжности.

Место ОС в иерархической структуре ВС.

Интерфейс – набор правил для взаимодействия с данным уровнем системы. Каждый уровень обладает интерфейсом.

Интерфейс ОС:



^ ППО- прикладное ПО.

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

UI- (user interface)- интерфейс командной строки(система отвечает на команды юзера, работающего в консоли).

GUI- графический интерфейс (управление с помощью графических объектов).


^ Вопрос 2. Процессы. Определение процесса. Логическая и физическая модели процесса Графы состояний процесса для логической и физической модели. Контекст процесса


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

^ Последовательный процесс – работа, производимая процессором при выполнении программы с ее данными.

Логическая и физическая модели процесса.

В логической модели процесс описывается как упорядоченная по времени последовательность векторов состояний процессов. P=S1->S2->…->Sn.

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

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

Компонента вектора состояния – выполняется операция

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

некоторые параметры




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

Счетчик команд – указатель (инициатор) процесса.

СЧ АП



СЧ- счётчик адресов команд.

АП- адресное пространство.


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

Состояние процесса в логической модели: 2 состояния (активное и пассивное), изображают с помощью графа состояний.




^ Физическая модель описывает распределение процессоров для выполнения процессов.

Состояния физической модели.




Нужен процесс-диспетчер.

Выполняющийся (активный)- процесс, которому выделен процессор.

^ Готовый –процесс который готов, но ему еще не выделен процессор.

Блокированный- процесс добровольно отдает процессор, т.к. ждёт какой-то ресурс.


Блок->Гот: освободить(когда выделяются ресурсы для развития процесса). Гот->Блок: блокировать. Вып->Блок: запросили ресурс. Вып->Гот: операция «прервать» (аппаратно-программный механизм). Гот->Вып: м.б. переведён некоторым другим процессом (выполнить).


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

^ Дескриптор процесса- набор параметров процесса.


Должен быть механизм аппаратного прерывания процессов (*).



...



Аппар

При прерывании мы должны сохранить вектор состояния процесса (сохранение контекста процесса).

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

Совокупность этих операций называется операцией переключения контекста.

^ Контекст процесса – вектор состояния, та информация, которая необходима для продолжения работы процесса.

Мультипрограммирование – переключение процессов.

Кол-во готовых процессов- коэффициент мультипрограммирования.

^ Программный процесс – выполнение программного кода.


Вопрос 3. Классификация процессов ОС.


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


^ Классификация процессов.

По времени существования процессов.

пакетные (нет ограничений на время сущ-я)

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

процесс реального времени (требует такого планирования, чтобы окончание процесса было в конкретный момент времени t, либо до наступления этого момента)(жёстко связана со временем, исп-ся в ОС реального времени)

По отношению к ОС.

системные (самой ОС)

пользовательские (прикладные)

По генеалогическому признаку.

порождающие

порожденные

По связности.

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

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

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

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

По динамике развития.

последовательные(временные интервалы сущ-я не пересекаются)

параллельные (на рассматриваемом интервале существуют одновременно)

комбинированные





Вопрос 4. Ресурсы. Определение ресурса, Классификация ресурсов.


Для развития процесса нужны ресурсы.

^ Ресурс- средство ВС, которое может быть выделено процессу на определенный интервал времени.


Классификация ресурсов.

По реальности существования

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

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

по возможности расширения свойств

- эластичный (позволяет виртуализацию)

- жесткий (на позволяет виртуализацию)

по степени активности

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

- пассивный (над которым нельзя выполнять такие действия)

по времени существования по отношению к процессу

- постоянные (существуют до рождения данного процесса и все время его сущ-я).

- временные (появляются во время сущ-я процесса и могут уничтожаться).

по степени важности

- главные (без которых развитие процесса принципиально невозможно)

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


по структуре

- простой(рассм-ся как единое целое, может иметь 2-а состояния: занят, свободен)

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

по восстанавливаемости

-воспроизводимый (многократное использование цепочки «запрос-использование- освобождение», после этого восстан-ет свои свойства)

-потребляемый (допускает последовательность «освобождение-запрос-использование-снятие», после вып-я уничтожается(пр: сообщения))

по характеру использования

- параллельно используемый(может исп-ся || несколькими процессами)

- последовательно используемый (цепочка действий «запрос-исп-освоб», в данный момент времени доступен только одному процессу)

по форме реализации

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

- твердые (аппаратные, человеческие)

Вопрос 5. Формальная модель ОС


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

G=

Gp-граф процессов ОС. p=

Gr-множество ресурсов. r=

Aab=(Pa,Pb)- ориентированное ребро(вершина b нах-ся в иерархическом подчинении вершины a, Pb- потомок Pa)

Аab=[ Pa,Pb]- неориентированное ребро.

Граф ресурсов Gr состоит из вершин, соединённых ор. или неор. рёбрами.

Граф процессов Gp на верхнем уровне имеет единственную вершину Ро, все остальные процессы считаются порождёнными им. (?)Инициал происходит аппаратными процессами(?)

Gp, Gr – динамические графы, над которыми допустимы следующие операции:

добавление новой вершины

удаление вершины

установление связи между вершинами

удаление связей

измен состояния вершины


Вопрос 6. Управление процессами. Таблицы управления процессами. Дескриптор процесса. Операции над процессами. Прерывания процессов.


Управление процессами . Табл. Дескриптор. Операции над процессами. Прерывания.

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

Возможный дескрипторный набор:

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

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

инф-я о родителях и потомках данного процесса.

Инф-я о состоянии процесса (контекст процесса)

Инф-я о ресурсах, выделенных данному процессу (пр: о выделенной ОП)

Инф-я о выделенной ОП

Инф-я о созданных данным процессом ресурсах

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

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

Создать новый процесс (создаётся дескриптор процесса, он либо указатель на него заносится в таблицу управления процессами, процессу выделяются некоторые ресурсы)

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

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

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

Прерывания процессов.


...






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

^ Синхронное прерывание (внутреннее,1 рода) – происходит синхронно с выполняющимся процессом, по инициативе самого процесса. Такое прерывание возникает, когда у процесса, находящегося в состоянии выполнения возникает потребность:

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

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

прерывания возникают при ошибках, связанных с аппаратными процессами.

^ Асинхронное прерывание (внешнее, 2 рода)– возникает, когда процесс прерывается «без его ведома» (по времени и т.д.).

Каждое прерывание должно быть обработано.

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

восприятие запроса на прерывание;

запоминание состояния прерываемого процесса;

передача управления программе обработки прерываний;

обработка прерываний;

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

В большинстве вычислительных систем действия 1 – 3 реализуются аппаратно, а 4 – 5 – с помощью программ.

Полномочия процессов.

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

^ Полномочия позволяют:

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

процесс может передавать потомкам только подмножество своих ресурсов;

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

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


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



Синхронизация процесса обеспечивает:

упорядочивание процессов во времени в зависимости от типа отношения следования.

взаимоотношения между процессами (передача информации между ними).

Типы отношений между процессами :

отношение предшествования (какой-то из двух процессов переходит в другое состояние раньше);

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

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

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

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

отношение читатель – писатель (для файловых систем выделяются 2-а класса процессов: 1. только писатели. 2. только читатели)

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

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

Задача взаимного исключения.

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

одновременно внутри одного критического интервала находится не более одного процесса;

критические интервалы не должны иметь приоритета в отношении друг друга;

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

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

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

Задачи производители – потребители.

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

выполнить требования задачи взаимного исключения;

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




Задача читатели – писатели.

Могут быть установлены приоритеты как для читателя, так и для писателя. Если установлена приоритетность писателя, то он осуществляет запись, решает задачу на основе взаимного исключения: он исключает и писателей, и читателей. Если приоритет читателя, то читатели могут исключить и тех, и других или только писателей.(эта задача наиб часто решается при построении файловых систем).

Задачи кругового распределения ресурса («обедающие философы»)

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

Могут возникнуть 2-е опасности:

Возникновение тупиковой ситуации.

Возникновение ситуации голодания.



Чаще всего механизмы имеют программно-аппаратную форму синхронизации.


Вопрос 8. Синхронизация параллельных процессов, Механизмы синхронизации. Аппаратная и программная реализация взаимоисключений. Семафорные примитивы Дейкстры.


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

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


Реализация задачи взаимного исключения.

Аппаратно: блокировка памяти (нет доступа 2 процессам к одной ячейке), запрещение прерывания (процесс, который использует критический ресурс, блокирует обработку всех прерываний (снятие задачи) и никакой другой процесс не развивается), проверка и установка (TS (test-set) ).

«-» низкая эффективность, не гибкий механизм мешает мультипрограммированию.


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

Задача взаимного исключения решается в 3 этапа:

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

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

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


Если на 1-ом этапе обнаруживается, что критический ресурс занят, то возможны 2 решения:

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

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


Проверка и установка TS- является аппаратно поддерживаемой составной командой.

Выполняются команды:

1. Вводится специальная переменная, которая называется- блокирующая переменная ресурсов( 0- свободен, 1- занят).

2. Перед входом в критическую секцию процесс выполняет команду TS:

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

если Test F(D)=0 –то Set F(D)=1 устанавливается в 1 и выполняется критический интервал, после выполнения критического интервала устанавливаем F(D)=0.

Test Set- неделимые примитивы.


В системе команд многих процессоров предусмотрены единые неделимые команды анализа и присвоения значения логической переменной - BIC,STR, BTS (Pentium). Если соответствующих команд в составе процессора нет, то они реализуются в рамках ОС путем организации примитивов с помощью запретов.


Программная реализация взаимного исключения.

семафоры

мониторы

рандеву

программные каналы


Семафоры (семафорные примитивы Дейкстры).

Семафор- это переменная специального вида (S), которая доступна параллельным процессам для проведения только 2-ух операций: P(S) и V(S) операций.

P(S) ( закрытие семафора)

V(S) (открытие семафора)

Эти операции являются неделимыми примитивами.

Три основных класса семафоров:

1. Двоичный (S=0 или S=1)

2. Целочисленный (S= n, n- натуральное или S=0)

3. Любой целочисленный( S= z, z- целое, в т. ч. и отрицательное)

1) Выполнение P(S) – значение семафора S уменьшается на 1:

if S>0 S=S-1 - переход к следующей команде(операции);

if S=0 - процесс блокируется и становится в очередь ожидания к семафору S.

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

if S<0 - равно количеству процессов, блокированных по данному семафору.


2) V(S)

if S=0 , то семафор S предоставляется следующему процессу из очереди ожидания .

else S:=S+1


Достоинства семафоров.

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

Недостатки семафоров.

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


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

Пример исп-я семафора- mutex.

1) mutex – семафоры взаимного исключения, простейший двоичный семафор, который находится в двух состояниях: отмеченное и неотмеченное .

Если процесс становится владельцем объекта mutex, то он переводится в неотмеченное состояние, а когда процесс его возвращает – в отмеченное состояние.

Каждый mutex имеет собственное имя.

Для работы с mutex-ами исп-ся след функции:

создание mutex (при этом создаётся его имя. Mutex может наследоваться, т.е. передаваться потомкам, для этого и сущ-ет его имя)

открытие mutex

ожидание события mutex

освобождение mutex


2) Монитор. (мониторы синх-ии процессов (мониторы Хоара))

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


3) Рандеву.

Рассматривается задача межпроцессионной связи и синхронизации, т.е. сущ-ют 2-а процесса Pa и Pb.

Pa должен передать данные Pb. Для осущ-я передачи оба процесса должны выразить готовность для передачи сообщения. Эти сигналы могут не совпадать по времени. Тогда ждут ответного сигнала о принятии сообщения. После передачи сообщения процессы продолжают своё выполнение.


^ Программные каналы (транспортёр).

Программные каналы- средство, реализ-е во многих ОС (UNIX, Windows).

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


Реализация взаимоисключений в ОС Windows NT





Вопрос 9-10.

9. Дедлок( тупиковая ситуация). Условия возникновения.
10. Дедлок( тупиковая ситуация). Стратегии предотвращения и обхода дедлоков.


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

Условия возникновения дедлока:

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

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

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

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

Решение проблемы дедлока.

Стратегия предотвращения тупиков.

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

косвенный метод – предотвращение возникновения одного из первых 3-ёх условий возникновения дедлока;

прямой метод – предотвращение 4-го условия- циклического ожидания.

Условия взаимного исключения можно подавить неограниченным выделением ресурсов – это слишком дорого.

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

Отсутствие перераспределения подавляется отниманием операционной системой ресурсов.

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


Стратегия обхода дедлоков.

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

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


Стратегия распознавания дедлока.

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


Методы восстановления системы после возникновения дедлока.

Reset- принудительное завершение всех процессов, работы ОС и запуск ее заново;

Завершение процессов по одному, лучше всего завершать процесс, который находится в дедлоке;

Подождать, пока система сама предотвратит дедлок.


Вопрос 11-12

11. Управление ресурсами. Дескрипторы воспроизводимых и потребляемых ресурсов. Операции над семафорами ресурсов. Распределение ресурсов ОС. Задачи распределения.

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



Управление ресурсами в ОС.

Ресурсы делятся на:

1. воспроизводимый (повторно используемый, системный)

2. потребляемый (после потребления изымается из сферы обращения)

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


Каждый воспроизводимый ресурс требует для описания 3-и компоненты:

1. Опись(включает число и идентификацию доступных ресурсов)

2. Список ожидания (либо ссылка на него)(список процессов, ждущих определённое сообщение; с неудов-ми запросами на данный ресурс)

3. Указатель на распределитель ресурсов


Для потребляемых ресурсов дескриптор должен содержать:

1. Опись(содержит список сообщений, которые были выданы, но не были получены)

2. Список ожидания (либо ссылка на него)(в нём- блокированные процессы с неудов-ми запросами на данный ресурс)

3. Указатель на распределитель ресурсов


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

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

Основные элементы дескриптора(ещё раз на всякий случай)

Информация об идентификаторе.

Тип (воспроизводимый или потребляемый).

Имя процесса, создавшего ресурс.

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

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

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


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

Создать семафор ресурса. Эта операция создает дескриптор ресурса и помещает его в списки ОС.

Уничтожить семафор. Дескриптор удаляется.

Запросить элементы семафора. Процесс выдает команду «запросить». Процесс заносится в список ожидания и вызывается распределитель ресурсов.

Освободить элементы семафора ресурса – добавляет элементы сообщения в список (?).


Распределение ресурсов ОС

2-е основные схемы:

1. Централизованное распределение ресурсов.

2. Децентрализованная схема распределения ресурсов (на основе соглашений между процессами, без монитора)

Статическое и динамическое распределение ресурсов.

1. Статическое: ресурсы распределяются процессу в момент его рождения и являются постоянными для процесса всё время его сущ-я(такая схема соот-ет наиб быстрому развитию процесса).

2. Динамическое: ресурсы выдаются процессу по мере его развития(соот-ет наиб эффективному использованию ресурсов и минимизации простоев).


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


Дисциплина распределения ресурсов.

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

Дисциплины формирования очередей (совокупность правил размещен процессов в очереди к ресурсам)делятся на 2 класса:

статические – приоритет назначается до формирования;

динамические – приоритет в процессе формирования очереди.

Дисциплины обслуживания очереди (правило извлечен процесса из очереди с предоставлением ему ресурсов) разделяют на множество классов. Наиболее часто:

бесприоритетные

линейные

FIFО обслуживание в порядке поступления (по времени рождения запроса на ресурс);

LIFO в порядке, обратном времени поступления;

случайный выбор

циклические

RR круговой, циклический алгоритм (процессы выстраиваются в круг);

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

смешанный RR+FB

приоритетные

с фиксированным приоритетом: относительным, абсолютным, адаптивный алгоритм

с динамическим ожиданием: функция от ожидания или от обслуживания


Системы распределения ресурсов.(ещё раз)

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

Децентрализованная схема распределения. Распределение ресурсов осуществляется на основе некоторого соглашения между процессами.

^ Статические и динамические распределения.

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

^ Динамические распределения – ресурсы выделяются процессу по мере их развития. Позволяет наиболее эффективно использовать ресурс.

Защита ресурсов.

Угрозы ресурсам:

Несанкционированный доступ (предотвращается программно).

Нарушение целостности.

Утрата данных.

Злоупотребление ресурсом.

Утечка информации.


Вопрос 13-15.

13. Мультипрограммирование. Планирование и диспетчеризация процессов при МП.
14. Мультипрограммирование. Дисциплины диспетчеризации для невытесняющей и вытесняющей многозадачности.
15. Мультипрограммирование. Приоритетные и многоочередные дисциплины диспетчеризации.


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

Характеристические состояния процесса при мультипрограммировании:

состояние планирования ресурсов;

состояние владения ресурсами;

состояние выполнения.


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

Планирование – выделение ресурсов процессу, кроме выделения фактического процесса, т.е. процессу выделен виртуальный процессор (1 раз). А если выделен фактический процессор, то это диспетчеризация (многократно).


Варианты многопоточности процессов.

1 процесс-1 поток (MS-DOS).

Несколько процессов, а в каждом процессе по одному потоку (UNIX)

1 процесс и в нем несколько потоков управления (среда JAVA).

Несколько процессов и в каждом процессе несколько потоков (Windows 2000, Linux, Solaris).


^ Мультипрограмм