Кратчайшая задача - первая

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

Пусть у нас есть четыре задачи: A, B, C и D, со временем выполнения 8, 4, 4 и 4 мин соответственно. Если мы запустим их в данном порядке, оборотное время задачи А будет 8 мин, В - 12 мин, С - 16 мин, D - 20 мин, и среднее время будет равно 14 мин. Запустим задачи в другом порядке : B, C, D, A, со временем выполнения 4, 4, 4 и 8 мин соответственно. Теперь значения оборотного времени составляют 4, 8, 12 и 20 соответственно, а среднее время равно 11 мин. Алгоритм оптимизирует задачу. Рассмотрим четыре процесса со временем выполнения a, b, c и d. Первая задача выполняется за время а, вторая - за время a+b и т. д. Среднее оборотное время будет равно (4a+3b+2c+d)/4. Очевидно, что вклад времени а в среднее больше, чем всех остальных интервалов времени, поэтому первой должна выполняться самая короткая задача, а последней - самая длинная, вносящая вклад, равный собственному оборотному времени.

Следует отметить, что эта схема работает лишь в случае одновременного наличия задач. В качестве контрпримера можно рассмотреть 5 задач, A, B, C, D и E, причем первые две доступны сразу же, а три оставшиеся - еще через 3 минуты. Время выполнения этих задач составляет 2, 4, 1, 1 и 1 мин соответственно. Вначале можно выбрать только А и В, поскольку остальные недоступны. Если руководствоваться алгоритмом "Кратчайшая задача - первая", задачи будут запущены в следующем порядке: A, B, C, D, E, и среднее оборотное время составит 4,6 мин. Если же запустить их в порядке B, C, D, E, A, то среднее оборотное время составит 4,4 мин.

Наименьшее оставшееся время выполнения

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

16. Алгоритмы планирования в интерактивных ОС

интерактивные системы ориентированы на максимальное удобство пользователя. В этих системах невозможно трёхуровневое планирование, однако двухуровневое широкок используется.

Циклическое планирование

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

Приоритетное планирование

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

Гарантированное планирование

Если в системе одновременно работаю k пользователей, то одному будет предоставлено (1/k) процессорного времени, а в системе с одним пользователем запущено n процессов, то каждому процессу достнется (1/n) процессорного времени. система самас ледит за количестволм процессов и отследивает промежутки процессорного времени, выделяфемого каждому из процессов (или пользователей)

Лотерейное планирование

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

Справедливое планирование

Во внимание берётся тот, кто запускает процесс. Если один пользователь создал 9 процессов, а параллельный ему второй - 1, то при таком планировании система распределит время процессора между пользователями попаам, в то время как другие виды планирования отали большинство процессорного времние первому пользователю. Данное планирование отведёт ровно 50% процессорного времени одному из дву пользоватлей, независимо от того, как он будет использовать эти 50%.

Q17

Планирование в ОС реального времени

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

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

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

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

В качестве примера рассмотрим гибкую систему реального времени с тремя периодическими сигналами с периодами в 100, 200 и 500 мс соответственно. Если на обработку этих сигналов уходит 50, 30 и 100 мс соответственно, система является поддающейся планированию, поскольку 0,5+0,15+0,2<1. Даже при добавлении четвертого сигнала с периодом в 1 с системой все равно можно будет управлять при помощи планирования, пока время обработки сигнала не будет превышать 150 мс. В этих расчетах существенным является предположение, что время переключения между процессами пренебрежимо мало.

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

18. Синхронизация процессов и потоков: цели и средства синхронизации.

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

Передача инфы между процессам

Контроль над деятельностью процессов

Согласование действий процессов

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

Синхронизация нужна для того, чтобы избежать:

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

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

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

Способы обеспечивания взаимного исключения:

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

Блокирующие переменные. С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. Операция проверки и установки блокирующей переменной должна быть неделимой, для этого используются команды "проверка-установка" типа BTC, BTR и тп, или их програмные аналоги.

Аппарат событий. С помощью этого средства могут решаться не только проблемы взаимного исключения, но и более общие задачи синхронизации процессов. В разных операционных системах аппарат событий реализуется по своему, но в любом случае используются системные функции аналогичного назначения, которые условно назовем WAIT(x) и POST(x), где x - идентификатор некоторого события. Если ресурс занят, то процесс не выполняет циклический опрос, а вызывает системную функцию WAIT(D), здесь D обозначает событие, заключающееся в освобождении ресурса D. Функция WAIT(D) переводит активный процесс в состояние ОЖИДАНИЕ и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию POST(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние ГОТОВНОСТЬ.

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

Мониторы?

19. Ситуация состязаний (гонки). Способы предотвращения.

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

Рис. 2.3.

Рассмотрим, например (рисунок 2.3), программу печати файлов (принт-сервер). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записывают в специальный общедоступный файл "заказов" другие программы. Особая переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции файла "заказов". Процессы-клиенты читают эту переменную, записывают в соответствующую позицию файла "заказов" имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT, значение которой для определенности предположим равным 4. Процесс запомнил это значение, но поместить имя файла не успел, так как его выполнение было прервано (например, в следствие исчерпания кванта). Очередной процесс S, желающий распечатать файл, прочитал то же самое значение переменной NEXT, поместил в четвертую позицию имя своего файла и нарастил значение переменной на единицу. Когда в очередной раз управление будет передано процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет имя файла также в позицию 4, поверх имени файла процесса S.

Таким образом, процесс S никогда не увидит свой файл распечатанным.

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

Способы опеспечения взаимного исключения:

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

Блокирующие переменные.

Аппарат событий.

Семафоры.

(способы расписаны в 18-м вопросе, про синхронизацию)

20. Семафоры Дийкстры.

В 1968 г. Э. Дейкстра предложил удобную форму механизма захвата/освобождения ресурсов, которую он назвал операциями P и V над считающими семафорами. Считающим семафором называют целочисленную переменную, выполняющую те же функции, что и байт блокировки. Однако в отличие от последнего она может принимать кроме "0" и "1" и другие целые положительные значения.

Семафоры – это часть абстракции, поддерживающая очередь постоянно ожидающих процессов.

Операции P и V над семафором S могут быть определены следующим образом.

P(S):

1. Уменьшить значение S на 1, т. е. S : = S – 1.

2. Если S < 0, выполнить ОЖИДАНИЕ (S).

V(S):

1. Увеличить значение S на 1, т. е. S : = S + 1.

2. Если S ³ 0, выполнить ОПОВЕЩЕНИЕ (S).

Операция ОЖИДАНИЕ (S) (WAIT) блокирует обслуживание процесса, делает соответствующую отметку об этом и связывает процесс со значением переменной S.

Операция ОПОВЕЩЕНИЕ (S) (SIGNAL) просматривает связанный с переменной S список блокированных процессов. Если в списке есть процессы, ожидающие освобождения некоторого ресурса, управляемого (сигнализируемого) S, один из них переводится в состояние готовности, а в соответствующей ему записи делается отметка. С этого момента процесс становится опять доступным планировщику.

По определению, ожидание, связанное с операцией P(S), не является ожиданием "зависания", так как ожидающие процессы не используют центральный процессор. Так как несколько процессов могут ожидать операцию P(S) над отдельным семафором, во время приращения должен быть осуществлен выбор, какую контрольную точку процесса сделать доступной. Алгоритм выбора не определен, за исключением требования равнодоступности процессов, т. е. никакой процесс не может быть "забыт".

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

Наиболее употребительные операции над семафорами:

· создать семафор;

· запросить состояние семафора;

· изменить состояние семафора;

· уничтожить семафор.

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

21. Взаимные блокировки. Условия, необходимые для возникновения тупика.

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

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

Системная тупиковая ситуация, или ситуация “зависания” системы - это ситуация, когда один или более процессов оказываются в состоянии тупика.

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

В проблеме тупиков выделяют следующие четыре основных направления:

предотвращение тупиков;

обход тупиков;

обнаружение тупиков;

восстановление после тупиков.

Cформулированы следующие четыре необходимых условия наличия тупика:

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

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

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

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

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

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

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

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

22. Обнаружение взаимоблокировки при наличии одного ресурса каждого типа.

Под одним ресурсом каждого типа, подразумевается один принтер, один сканер и один плоттер и т. д. Рассмотрим систему из 7-ми процессов и 6-ти ресурсов.

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

Рассмотрим один из алгоритмов. Для каждого узла N в графе выполняется пять шагов.

1Задаются начальные условия: L-пустой список, все ребра не маркированы.

2Текущий узел добавляем вконец списка L и проверяем количество появления узла в списке. Если он встречается два раза, значит цикл и взаимоблокировка.

3Для заданного узла смотрим, выходит ли из него хотя бы одно немаркированное ребро. Если да, то переходим к шагу 4, если нет, то переходим к шагу 5.

4Выбираем новое немаркированное исходящее ребро и маркируем его. И переходим по нему к новому узлу и возвращаемся к шагу 3.

5Зашли в тупик. Удаляем последний узел из списка и возвращаемся к предыдущему узлу. Возвращаемся к шагу 3. Если это первоначальный узел, значит, циклов нет, и алгоритм завершается.

Для нашего случая тупик обнаруживается в списке L=[B, T,E, V,G, U,D, T]

23. Обнаружение взаимоблокировок при наличии нескольких ресурсов каждого типа.

Рассмотрим систему.

m - число классов ресурсов (например: принтеры это один класс)

n - количество процессов

P(n) - процессы

E - вектор существующих ресурсов

E(i) - количество ресурсов класса i

A - вектор доступных (свободных) ресурсов

A(i) - количество доступных ресурсов класса i

С - матрица текущего распределения (какому процессу, какие ресурсы принадлежат)

R - матрица запросов (какой процесс, какой ресурс запросил)

C(ij) - количество экземпляров ресурса j, которое занимает процесс P(i).

R(ij) - количество экземпляров ресурса j, которое хочет получить процесс P(i).

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

Рассмотрим алгоритм поиска тупиков.

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

Рассмотрим работу алгоритма на реальном примере.

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

Рассмотрим работу алгоритма на реальном примере.

Используем алгоритм:

1Третий процесс может получить желаемые ресурсы, т. к. R= A

2Третий процесс освобождает ресурсы. Прибавляем их к A. А =+=(Маркируем процесс.

3Может выполняться процесс 2. По окончании А=(

4Теперь может работать первый процесс.

Тупиков не обнаружено.

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

Когда можно искать тупики:

Когда запрашивается очередной ресурс (очень загружает систему)

Через какой то промежуток времени (в интерактивных системах пользователь это ощутит)

Когда загрузка процессора слишком велика

24. Предотвращение взаимоблокировок. Алгоритм банкира для одного вида ресурсов.

"Банкира", потому что аналогия такая, клиенты-процессы, кредиты-ресурсы.

Рассмотрим систему: банкир может дать 10 кредитов (ресурсы), к нему попеременно обращаются четыре клиента.

Алгоритм банкира:

Банкиру поступает запрос от клиента на получение кредита

Банкир проверяет, приводит ли этот запрос к небезопасному состоянию.

Банкир в зависимости от этого дает или отказывает в кредите.

25. Предотвращение взаимоблокировок. Алгоритм банкира для нескольких видов ресурсов.

Рассмотрим систему:

Вектора:

E=(6342) - существующие ресурсы

P=(5322) - занятые ресурсы

A=(1020) - доступные ресурсы

Алгоритм поиска безопасного или небезопасного состояния:

Если состояние безопасное то ресурс дать можно, если нет то нельзя.

26. Синхронизирующие объекты ОС: системные семафоры, мьютексы, события, сигналы.

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

Примерами таких синхронизирующих объектов ОС являются:

системные семафоры

мьютексы

события

таймеры и другие.

Чтобы процессы могли разделять синхронизирующие объекты, в разных ОС используются разные методы

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

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

Все синхронизирующие объекты могут находиться в двух состояниях:

сигнальном

несигнальном (свободном).

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

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

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

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

любое обращение потока с системным вызовом Wait(X) влечет за собой действия в подсистеме планирования

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

из очереди готовых потоков выбирается и активизируется новый поток.

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

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

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

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

Объект-событие (в данном случае слово «событие» используется в узком смысле, как обозначение конкретного вида объектов синхронизации) обычно используется не для доступа к данным, а для того, чтобы оповестить другие потоки о том, что некоторые действия завершены. Пусть, например, в некотором приложении работа организована таким образом, что один поток читает данные из файла в буфер памяти, а другие потоки обрабатывают эти данные, затем первый поток считывает новую порцию данных, а другие потоки снова ее обрабатывают и так далее. В начале работы первый поток устанавливает объект-событие в несигнальное состояние. Все остальные потоки выполнили вызов Wait(X), где X — указатель события, и находятся в приостановленном состоянии, ожидая наступления этого события. Как только буфер заполняется, первый поток сообщает об этом операционной системе, выполняя вызов Set(X). Операционная система просматривает очередь ожидающих потоков и активизирует все потоки, которые ждут этого события.

27. Мониторы Хоара

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

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

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

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

Иногда монитор задерживает обратившийся к нему процесс. Это происходит, например, в случае обращения за занятым ресурсом. Монитор блокирует процесс с помощью команды "ЖДАТЬ", а в случае освобождения ресурса выдает команду "СИГНАЛ". При этом освободившийся ресурс предоставляется одному из ожидавших его процессов вместе с разрешением на продолжение работы. Управление передается команде монитора, непосредственно следующей за операцией "ЖДАТЬ".

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

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

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

Рис. 2.8. Классификация методов распределения памяти

Распределение памяти фиксированными разделами

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

Рис. 2.9. Распределение памяти фиксированными разделами: а - с общей очередью; б - с отдельными очередями

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

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

Распределение памяти разделами переменной величины

В этом случае память машины не делится заранее на разделы. Сначала вся память свободна. Каждой вновь поступающей задаче выделяется необходимая ей память. Если достаточный объем памяти отсутствует, то задача не принимается на выполнение и стоит в очереди. После завершения задачи память освобождается, и на это место может быть загружена другая задача. Таким образом, в произвольный момент времени оперативная память представляет собой случайную последовательность занятых и свободных участков (разделов) произвольного размера. На рисунке 2.10 показано состояние памяти в различные моменты времени при использовании динамического распределения. Так в момент t0 в памяти находится только ОС, а к моменту t1 память разделена между 5 задачами, причем задача П4, завершаясь, покидает память. На освободившееся после задачи П4 место загружается задача П6, поступившая в момент t3.

Рис. 2.10. Распределение памяти динамическими разделами

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

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4