Пятница, 29 Мар 2024, 03:55
Uchi.ucoz.ru
Меню сайта
Форма входа

Категории раздела
Учителю физики [224]
Учителю химии [112]
Учителю биологии [744]
Учителю информатики [147]
Учителю математики [110]
Учителю русского языка [250]
Учителю астрономии [437]
Учителю иностранного языка [182]
Учителю истории (открытые уроки) [151]
Учителю обществознания [53]
Учителю истории [354]
Учителю труда [14]
Учителю ОБЖ [2]
Учителю искусствоведения [0]
Изо
Учителю белорусского языка и литературы [1]
Учителю допризывной и медицинской подготовки [0]
Учителю географии [9]
Учителю МХК [1]
Учителю музыки [3]
Учителю физкультуры [15]
Учителю черчения [0]
Новости
Чего не хватает сайту?
500
Статистика
Зарегистрировано на сайте:
Всего: 51635


Онлайн всего: 5
Гостей: 5
Пользователей: 0
Яндекс.Метрика
Рейтинг@Mail.ru

Каталог статей


Главная » Статьи » По предмету » Учителю информатики

Семафоры и квантование времени
Все описанные выше ключевые понятия, относящиеся к взаимоисключению, Дейкстра суммировал в своей концепции семафоров. Семафор – это защищенная переменная, значение которой можно опрашивать и менять только при помощи специальных операций P и V и операции инициализации, которую мы будем называть «инициализациясемафора». Двоичные семафоры могут принимать только значения 0 и 1. Считающие семафоры (семафоры со счетчиками) могут принимать неотрицательные целые значения. Операция P над семафором записывается, как P(S) и выполняется следующим образом:

если S > 0

то S := S – 1

иначе (ожидать на S).

Операция V над семафором записывается, как V(S) и выполняется следующим образом:

если (один или более процессов ожидают на S) то (разрешить одному из этих процессов продолжить работу) иначе S := S + 1.

Предполагается, что очередь процессов, ожидающих на S, обслуживается в соответствии с дисциплиной «первый пришедший обслуживается первым». Как и операция testandset, операции P и V являются неделимыми. Участки взаимоисключения по семафору S в процессах обрамляются операциями P(S) и V(S). Если одновременно несколько процессов попытаются выполнить операцию P(S), это будет разрешено только одному из них, а остальным придется ждать.

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

Ниже приводится пример того, каким образом можно обеспечить взаимоисключение при помощи семафоров. Здесь примитив P(активный) – эквивалент для «входвзаимоисключения», а примитив V(активный) – для «выходвзаимоисключения».

program примерсемафораодин;

var активный: семафор;

procedure процессодин;

begin

while истина do

begin

предшествующиеоператорыодин;

P(активный);

критическийучастокодин;

V(активный);

прочиеоператорыодин

end

end;

procedure процессдва;

begin

while истина do

begin

предшествующиеоператорыдва;

P(активный);

критическийучастокдва;

V(активный);

прочиеоператорыдва

end

end;

begin

инициализациясемафора(активный,1);

parbegin

процессодин;

процессдва

parend

end.

Синхронизация процессов при помощи семафоров

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

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

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

program блокированиевозобновление;

var событие: семафор;

procedure процессодин;

/* этот процесс ожидает P(событие) наступления к-либо события */

/* P(событие) переводит его в состояние ожидания */

begin

предшествующиеоператорыодин;

P(событие);

прочиеоператорыодин

end;

procedure процессдва;

/* этот процесс активизирует V(событие) ждущий процесс */

/* V(событие) переводит ждущий процесс в активный */

begin

предшествующиеоператорыдва;

V(событие);

прочиеоператорыдва

end;

begin

инициализациясемафора(событие,0);

parbegin

процессодин;

процессдва

parend

end.

Здесь «процессодин» выполняет некоторые «предшествующиеоператорыодин», а затем операцию P(событие). Ранее при инициализации семафор был установлен в нуль, поэтому «процессодин» будет ждать. Со временем «процессдва» выполнит операцию V(событие), сигнализируя о том, что данное событие произошло (например завершилась операция ввода/вывода). Тем самым «процессодин» получает возможность продолжить свое выполнение. Отметим, что подобный механизм будет выполнять свои функции даже в том случае, если «процессдва» обнаружит наступление события и просигнализирует об этом еще до того, как «процессодин» выполнит операцию P(событие); при этом семафор переключится из 0 в 1, так что операция P(событие) просто произведет обратное переключение из, 1 в 0, и «процессодин» продолжит свое выполнение без ожидания. Пара «производитель – потребитель» Когда в последовательной программе одна процедура вызывает другую и передает ей данные, обе эти процедуры вызываются частями единого процесса – они не выполняются параллельно. Если, однако, один процесс передает данные другому процессу, возникают определенные проблемы. Подобная передача может служить примером взаимодействия, или обмена информацией между процессами.

program парапроизводительпотребитель;

var исключительный доступ: семафор;

procedure процессодин;

begin

while истина do

begin

предшествующиеоператорыодин;

P(активный);

критическийучастокодин;

V(активный);

прочиеоператорыодин

end

end;

procedure процессдва;

begin

while истина do

begin

предшествующиеоператорыдва;

P(активный);

критическийучастокдва;

V(активный);

прочиеоператорыдва

end

end;

begin

инициализациясемафора(активный,1);

parbegin

процессодин;

процессдва

parend

end.

Квантование времени.

(Г. Лорин Х. М. Дейтел Операционные системы. «Ф и С» 1984г.)

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

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

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

Циклические очереди с обратной связью. Циклические подочереди с обратной связью состоят из n подочередей.

Подочередь 1 Подочередь 2 ... Подочередь n

Процесс начинает выполняться в подочереди 1. Он становится в ней первым и получает I1 интервалов времени обслуживания. Затем этот процесс перемещается в конец той же подочереди, со временем снова становится первым и получает очередные I1 интервалов. Это повторяется N1 раз, после чего процесс попадает в подочередь 2. Далее, находясь в подочереди 2, он получает N2 по I2 интервалов обслуживания и перемещается в подочередь 3, и т. д. Попав в самую последнюю подочередь, процесс находится в ней до полного завершения выполнения. Находясь в подочереди х, процесс может получить управление только в том случае, если ни в одной из подочередей с меньшими номерами нет готовых выполнению процессов. Обычно соблюдаются следующие соотношения: Ni>Nj и Ii>Ij при i>j. Величины: n, Ni и Ii можно задавать при генерации ОС.

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

Такая структура может применяться в системах разделения времени (СРВ), где процесс подлежащий выполнению, всякий раз перегружается (подкачивается) в ОП, а по окончании выделенного интервала изгоняется из ОП во внешнюю память. В подобных системах загрузка / выгрузка процессов происходит довольно часто, и значит процессор подолгу простаивает. Можно разделив всю ОП на три раздела: «предыдущий», «текущий» и следующий, и на основании регулярности смены выполняющихся процессов, обеспечиваемой режимом квантования, в процессе выполнения «текущего» процесса, «загружать» следующий и выгружать - «предыдущий». Это вообще говоря возможно, если компьютер допускает параллельные операции.

Пример: пусть n = 3. Характеристики очередей – следующие:

I1= 50 мкс, N1= 6; I2= 150 мкс, N2= 12; I3= 400 мкс, N3 > 12

Блок

управления

задачей

и т. д.



Блок

управления

процессом

и т. д.



процессом

Блок

управления

процессом

и т. д.



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

При таком алгоритме планирования процессорного времени преимущественное право обслуживания получают более время емкие процессы. Пусть имеются те же три очереди и в каждой из них находится 6 заданий. Задания 1 – очереди в сумме получат 300 мкс, 2 – й очереди – 900 мкс, а 3 –й – 2400 мкс. На однократный просмотр и обслуживание всех заданий уйдет 3600 мкс. Итак 66% времени будет выделено на обслуживание самых крупных заданий. Для мелких заданий промежутки между интервалами обслуживания составят 3550 мкс.
Категория: Учителю информатики | Добавил: Wrecker (04 Авг 2012)
Просмотров: 1163 | Рейтинг: 1.0/ 12 Оштрафовать | Жаловаться на материал
Похожие материалы
Всего комментариев: 0

Для блога (HTML)


Для форума (BB-Code)


Прямая ссылка

Профиль
Пятница
29 Мар 2024
03:55


Вы из группы: Гости
Вы уже дней на сайте
У вас: непрочитанных сообщений
Добавить статью
Прочитать сообщения
Регистрация
Вход
Улучшенный поиск
Поиск по сайту Поиск по всему интернету
Наши партнеры
Интересное
Популярное статьи
Портфолио ученика начальной школы
УХОД ЗА ВОЛОСАМИ ОЧЕНЬ ПРОСТ — ХОЧУ Я ЭТИМ ПОДЕЛИТ...
Диктанты 2 класс
Детство Л.Н. Толстого
Библиографический обзор литературы о музыке
Авторская программа элективного курса "Практи...
Контрольная работа по теме «Углеводороды»
Поиск
Главная страница
Используются технологии uCoz