Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Дисциплины диспетчеризации и алгоритмы планирования процессов




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

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

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

Ресурс может быть выделен задаче, обратившейся к супервизору с соответствую­щим запросом, если:

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

· текущий запрос и ранее выданные запросы допускают совместное использование ресурсов;

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

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

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

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

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

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

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

2. Создание, уничтожение, возобновление, приостановление выполнения процессов;

Основные состояния процесса (рис. 2):

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

· готовность — процесс находится в очереди на выполнение;

· ожидание — процесс ожидает завершение события (например, освобож­дения ресурса);

· остановлен — процесс остановлен, как правило, в отладочном режиме;

· создание — выполнение действий, необходимых для создания процесса;

· завершение — выполнение действий, связанных с успешным завершением процесса;

· зомби — процесс закончен, но предок не принял его завершения.

Рис. 2. Основные состояния процесса

При создании процесса должны быть выполнены следующие действия:

· присвоение процессу уникального номера (ID);

· добавление процесса в список процессов, известных системе;

· определение начального приоритета;

· формирование блока управления процессом;

· выделение необходимых ресурсов.

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

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

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

· при выборе из очереди планировщиком (характерно для операционных сис­тем, работающих в пакетном режиме);

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

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

· при наступлении запланированного времени запуска программы.

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

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

Из состояния выполнения процесс может выйти по одной из следующих при­чин:

· процесс завершается, при этом он посредством обращения к супервизору пе­редает управление операционной системе и сообщает о своем завершении. В результате этих действий супервизор либо переводит его в список бездей­ствующих процессов (процесс переходит в пассивное состояние), либо уничто­жает (уничтожается, естественно, не сама программа, а именно задача, которая соответствовала исполнению некоторой программы). В состояние бездействия процесс может быть переведен принудительно: по команде оператора (действие этой и других команд оператора реализуется системным процессом, кото­рый «транслирует» команду в запрос к супервизору с требованием перевести указанный процесс в состояние бездействия), или путем обращения к супер­визору операционной системы из другой задачи с требованием остановить данный процесс;

· процесс переводится супервизором операционной системы в состояние готов­ности к исполнению в связи с появлением более приоритетной задачи или в связи с окончанием выделенного ему кванта времени;

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

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

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

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

· идентификатор процесса (так называемый PID — process identificator);

· тип (или класс) процесса, который определяет для супервизора некоторые пра­вила предоставления ресурсов;

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

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

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

· информацию о ресурсах, которыми процесс владеет и/или имеет право пользоваться (указатели на открытые файлы, информация о незавершенных операциях ввода/вывода и т.п.)

· место (или его адрес) для организации общения с другими процессами;

· параметры времени запуска;

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

Процессы делятся на традиционные (имеющие один поток управления) и многопоточные (многонитевые). Поток (нить) управления (thread) — исполнение команд программы в естест­венном порядке.

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

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

· операционные системы;

· сетевые серверы;

· встроенные системы;

· вычислительные программы.

Об использовании потоков

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

Многие операционные системы, ориентированные на рабочие станции и персональные компьютеры, начиная с середины 80-х годов XX века, включают поддержку многопоточности. Впервые стандарт на потоки появился в 1995 году. Это был стандарт IEEE POSIX 1003.1с-1995. Однако стандарт появился достаточно поздно, и некоторые компании успели выпустить свои версии многопоточных библиотек, существенно отличающихся от стандарта. Можно выделить следующие основные семейства потоков:

1. Потоки, поддерживающие стиль POSIX-стандарта. Это семейство состоит из трех подгрупп:

· "истинные" POSIX-потоки. Это потоки, базирующиеся на стандарте IEEE POSIX 1003.1с-1995 (также известного как ISO/IEC 9945-1:1996), являющегося частью стандарта ANSI/IEEE 1003.1;

· DCE-потоки, базирующиеся на ранней версии стандарта POSIX — 1003.1;

· Unix International потоки, также известные как Solaris-потоки. Они достаточно близки к стандарту и поддерживаются в операционных системах Solaris компании Sun Microsystems и UnixWare 2 компании SCO;

2. Потоки Microsoft. Это семейство состоит из двух подгрупп, причем обе разработаны в компании Microsoft:

· потоки WIN32, являющиеся стандартными для семейства операцион­ных систем Windows, включая Windows 2000, Windows 95, Windows 98, Windows ME и Windows СЕ;

· потоки OS/2, являющиеся стандартными для операционной системы OS/2 компании IBM.

3. Другие варианты потоков. Их не так много. Отдельного упоминания за­служивает лишь пакет С threads, имеющийся в операционной системе Маch.

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

 

 

Контрольные вопросы:
  1. .В чем состоит принципиальное отличие состояний «ожидания» и «готовности» потока, ведь и в том и в другом он ожидает некоторого события?
  2. Мультипрограммные операционные системы принято разделять на системы реального времени, системы разделения времени, системы пакетной обработки. С другой стороны, алгоритмы планирования могут быть основаны на квантовании, относительных приоритетах, абсолютных приоритетах. Предложите для каждого из перечисленных типов ОС наиболее подходящий, по вашему мнению, тип алгоритма планирования.
  3. В какой очереди (ожидающих или готовых) скапливается большее число процессов:
A) в интерактивных системах разделения времени; B) в системах пакетной обработки, решающих «счетные» задачи. Ответ: А — в очереди процессов, ожидающих ввода-вывода; В — в очереди готовых процессов.
  1. Что такое вектор прерываний?
 
Домашнее задание: 1. Конспект лекций 2. В ТЕТРАДИ ВЫПИСАТЬ ОТВЕТЫ НА ВОПРОСЫ


Лекция 10 (2/20)

Проверка Д/З: 1). У 3 чел. Проверить конспекты 2). 3 чел. спросить по предыдущему (см. выше)

Алгоритмы планирования

Операционная система выполняет следующие основные функции, связан­ные с управлением задачами:

1) создание и удаление задач;

2) планирование процессов и диспетчирезация задач;

3) синхронизация задач, обеспечение их средствами коммуникации.

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

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

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

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

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

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

2) отдавать предпочтение более коротким процессам;

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

Пречень дисциплин диспетчеризации и их классификация приведены на рис.1.

Рис. 1. Дисциплины диспетчеризации. Рассмотрим кратко основные дисциплины диспетчеризации. Рис.2. Дисциплина диспетчеризации FCFS   Самой простой в реализации является дисциплина   FCFS (первым пришел – первым обслужен). Согласно этой дисциплине задачи обслуживаются в порядке очереди, то есть в порядке их появления. Те задачи, которые были заблокированы в процессе работы после перехода в состояние готовности, вновь ставятся в эту очередь перед теми, которые еще не выполнялись. То есть, образуется две очереди (рис. 2): очередь новых задач и очередь ранее выполнявшихся задач.

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

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

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

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

1. Поток завершился или покинул систему;

2. Произошла ошибка;

3. Поток перешёл в состояние ожидания;

4. Исчерпан квант процессорного времени.




Поделиться с друзьями:


Дата добавления: 2013-12-12; Просмотров: 2923; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.058 сек.