7.-Конспект-лекций.-ОП.01-ОСиСреды.-09.02.07_compressed. Конспекты лекций по дисциплине оп. 01 Операционные системы и среды
 Скачать 1 Mb.
|
|
Алгоритмы, основанные на приоритетах Приоритет – число, характеризующее степень привилегированности процесса (обычно выражается числом). В каждой ОС это число трактуется по своему, оно может быть фиксированным или изменяться. В случае если изменяется, то называется динамическим (начальное значение устанавливает администратор) в отличие от неизменяемых, фиксированных приоритетов. Чем выше приоритет, тем выше привелегия, тем меньше времени проводит поток в очереди. Существует 2 разновидности таких алгоритмов: Использующие относительные приоритеты. Использующие абсолютные приоритеты. Алгоритмы планирования с относительными приоритетами – активный процесс выполняется пока не завершится или не перейдет в состояние ожидания. Алгоритмы планирования с абсолютными приоритетами – смена процесса происходит в тот момент, когда в системе появляется процесс, приоритет которого выше приоритета выполняемого процесса. Реально используются смешанные схемы планирования. Контрольные вопросы 1. Какие алгоритмы планирования процессов бывают? 2. Опишите особенности принципа FIFO и LIFO; 3. Опишите алгоритмы, основанные на квантовании времени 4. Опишите алгоритмы, основанные на приоритетах. Мультипрограммирование_в_системе_пакетной_обработки,_разделения_времени,_реального_времени'>Лекция 8 Мультипрограммирование в системе пакетной обработки, разделения времени, реального времени План 1. Определение мультипрограммирования; 2. Типы мультипрограммирования; 3. Особенности пакетной мультипрограммной обработки. Мультипрограммирование Мультипрограммирование, или многозадачность (multitasking), — это способ организации вычислительного процесса, при котором на одном процессоре попеременно выполняются сразу несколько программ. Эти программы совместно используют не только процессор, но и другие ресурсы компьютера: оперативную и внешнюю память, устройства ввода-вывода, данные. Мультипрограммирование призвано повысить эффективность использования вычислительной системы, однако эффективность может пониматься по- разному. Наиболее характерными критериями эффективности вычислительных систем являются: - пропускная способность — количество задач, выполняемых вычислительной системой в единицу времени; - удобство работы пользователей, заключающееся, в частности, в том, что они имеют возможность интерактивно работать одновременно с несколькими приложениями на одной машине; - реактивность системы — способность системы выдерживать заранее заданные (возможно, очень короткие) интервалы времени между запуском программы и получением результата. В зависимости от выбранного критерия эффективности ОС делятся на системы пакетной обработки, системы разделения времени и системы реального времени. Каждый тип ОС имеет специфические внутренние механизмы и особые области применения. Некоторые операционные системы могут поддерживать одновременно несколько режимов, например часть задач может выполняться в режиме пакетной обработки, а часть — в режиме реального времени или в режиме разделения времени. При использовании мультипрограммирования для повышения пропускной способности компьютера главной целью является минимизация простоев всех устройств компьютера, и прежде всего центрального процессора., Такие простои могут возникать из- за приостановки задачи по ее внутренним причинам, связанным, например, с ожиданием ввода данных для обработки. Данные могут храниться на диске или же поступать от пользователя, работающего за терминалом, а также от измерительной аппаратуры, установленной на внешних технических объектах. При возникновении такого рода блокировки выполняемой задачи естественным решением, ведущим к повышению эффективности использования процессора, является переключение процессора на выполнение другой задачи, у которой есть данные для обработки. Такая концепция мультипрограммирования положена в основу так называемых пакетных систем. Системы пакетной обработки предназначались для решения задач в основном вычислительного характера, не требующих быстрого получения результатов. Главной целью и критерием эффективности систем пакетной обработки является максимальная пропускная способность, то есть решение максимального числа задач в единицу времени. Для достижения этой цели в системах пакетной обработки используется следующая схема функционирования: в начале работы формируется пакет заданий, каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется мультипрограммная смесь, то есть множество одновременно выполняемых задач. Для одновременного выполнения выбираются задачи, предъявляющие разные требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины. Например, в мультипрограммной смеси желательно одновременное присутствие вычислительных задач и задач с интенсивным вводом- выводом. Таким образом, выбор нового задания из пакета заданий зависит от внутренней ситуации, складывающейся в системе, то есть выбирается «выгодное» задание. Следовательно, в вычислительных системах, работающих под управлением пакетных ОС, невозможно гарантировать выполнение того или иного задания в течение определенного периода времени. Рассмотрим более детально совмещение во времени операций ввода-вывода и вычислений. Такое совмещение может достигаться разными способами. Один из них характерен для компьютеров, имеющих специализированный процессор ввода-вывода. В компьютерах класса мэйнфреймов такие процессоры называют каналами. Обычно канал имеет систему команд, отличающуюся от системы команд центрального процессора. Эти команды специально предназначены для управления внешними устройствами, например «проверить состояние устройства», «установить магнитную головку», «установить начало листа», «напечатать строку». Канальные программы могут храниться в той же оперативной памяти, что и программы центрального процессора. В системе команд центрального процессора предусматривается специальная инструкция, с помощью которой каналу передаются параметры и указания на то, какую программу ввода-вывода он должен выполнить. Начиная с этого момента центральный процессор и канал могут работать параллельно (рис. 4.1, а). Рис.1. Параллельное выполнение вычислений и операций ввода-вывода Другой способ совмещения вычислений с операциями ввода-вывода реализуется в компьютерах, в которых внешние устройства управляются не процессором ввода-вывода, а контроллерами. Каждое внешнее устройство (или группа внешних устройств одного типа) имеет свой собственный контроллер, который автономно отрабатывает команды, поступающие от центрального процессора. При этом контроллер и центральный процессор работают асинхронно. Поскольку многие внешние устройства включают электромеханические узлы, контроллер выполняет свои команды управления устройствами существенно медленнее, чем центральный процессор — свои. Это обстоятельство используется для организации параллельного выполнения вычислений и операций ввода-вывода: в промежутке между передачей команд, контроллеру центральный процессор может выполнять вычисления (рис. 4.1, б). Контроллер может сообщить центральному процессору о том, что он готов принять следующую команду, сигналом прерывания либо центральный процессор узнает об этом, периодически опрашивая состояние контроллера. Максимальный эффект ускорения достигается при наиболее полном перекрытии вычислений и ввода-вывода. Рассмотрим случай, когда процессор выполняет только одну задачу. В этой ситуации степень ускорения зависит от природы данной задачи и от того, насколько тщательно был выявлен возможный параллелизм при ее программировании. В задачах, в которых преобладают либо вычисления, либо ввод-вывод, ускорение почти отсутствует. Параллелизм в рамках одной задачи невозможен также, когда для продолжения вычислений необходимо полное завершение операции ввода-вывода, например, когда дальнейшие вычисления зависят от вводимых данных. В таких случаях неизбежны простои центрального процессора или канала. Если же в системе выполняются одновременно несколько задач, появляется возможность совмещения вычислений одной задачи с вводом-выводом другой. Пока одна задача ожидает какого-либо события (заметим, что таким событием в мультипрограммной системе может быть не только завершение ввода-вывода, но и, например, наступление определенного момента времени, разблокирование файла или загрузка с диска недостающей страницы программы), процессор не простаивает, как это происходит при последовательном выполнении программ, а выполняет другую задачу. Общее время выполнения смеси задач часто оказывается меньше, чем их суммарное время последовательного выполнения (рис. 4.2, а). Однако выполнение отдельной задачи в мультипрограммном режиме может занять больше времени, чем при монопольном выделении процессора этой задаче. Действительно, при совместном использовании процессора в системе могут возникать ситуации, когда задача готова выполняться, но процессор занят выполнением другой задачи. В таких случаях задача, завершившая ввод-вывод, готова выполняться, но вынуждена ждать освобождения процессора, и это удлиняет срок ее выполнения. Так, из рис. 4.2 видно, что в однопрограммном режиме задача А выполняется за 6 единиц времени, а в мультипрограммном — за 7. Задача В также вместо 5 единиц времени выполняется за 6. Но зато время выполнения обеих задач в мультипрограммном режиме составляет всего 8 единиц, что на 3 единицы меньше, чем при последовательном выполнении. В системах пакетной обработки переключение процессора с выполнения одной задачи на выполнение другой происходит по инициативе самой активной задачи, например, когда она отказывается от процессора из-за необходимости выполнить операцию ввода-вывода. Поэтому существует высокая вероятность того, что одна задача может надолго занять процессор и выполнение интерактивных задач станет невозможным. Взаимодействие пользователя с вычислительной машиной, на которой установлена система пакетной обработки, сводится к тому, что он приносит задание, отдает его диспетчеру-оператору, а в конце дня после выполнения всего пакета заданий получает результат. Очевидно, что такой порядок повышает эффективность функционирования аппаратуры, но снижает эффективность работы пользователя. Рис. 2. Время выполнения двух задач: в однопрограммной системе (а), в мультипрограммной системе (б) 1. Дайте определение мультипрограммирования; 2. Какие типы мультипрограммирования вы знаете; 3. Назовите особенности пакетной мультипрограммной обработки. Контрольные вопросы Лекция 9 Мультипроцессорная обработка План 1. Симметричная обработка; 2. Ассиметричная обработка; 3. Параллельная обработка; 4. Конвейерная обработка. Мультипроцессорная обработка — это способ организации вычислительного процесса в системах с несколькими процессорами. В отличие от организации мультипрограммирования на одном процессоре мультипроцессорная обработка предполагает действительно одновременное выполнение нескольких процессов. Это приводит к усложнению всех алгоритмов ОС. Симметричная архитектура предполагает однородность всех процессоров и единообразное их включение в общую схему. Традиционно все процессоры при этом разделяют одну память и как следствие находятся в одном корпусе. При асимметричной архитектуре процессоры могут отличаться своими техническими характеристиками и функциональной ролью. Требование единого корпуса отсутствует. Система может состоять из нескольких корпусов (в каждом может быть один или несколько процессоров). Такие устройства называются кластерами. Для симметричной архитектуры вычислительный процесс может строиться симметричным образом (все процессоры равноправны) или асимметричным (процессоры различаются функционально). Дтя асимметричной архитектуры возможен только асимметричный способ ор- В мультипроцессорных компьютерах имеется несколько процессоров, каждый из которых может относительно независимо от остальных выполнять свою программу. В мультипроцессоре существует общая для всех процессоров операционная система, которая оперативно распределяет вычислительную нагрузку между процессорами. Взаи- модействие между отдельными процессорами организуется наиболее простым способом — через общую оперативную память. Основное достоинство мультипроцессора — высокая производительность, которая достигается за счет параллельной или конвейерной работы нескольких процессоров. Так как при наличии общей памяти взаимодействие процессоров происходит очень быстро, мультипроцессоры могут эффективно выполнять даже приложения с высокой Еще одним важным свойством мультипроцессорных систем является отказоустойчивость, т. е. способность к продолжению работы при отказах некоторых элементов, например процессоров или блоков памяти. При этом производительность, естественно, снижается, но не до нуля, как в обычных системах, в которых отсутствует избыточность. Параллельная обработка. Необходимость параллельной обработки может возникнуть, когда требуется уменьшить время решения данной задачи, увеличить пропускную способность, улучшить использование Для распараллеливания необходимо соответствующим образом организовать вычисления. Сюда входит следующее: - составление параллельных программ, т. е. отображение в явной форме параллельной обработки с помощью надлежащих конструкций языка, ориентированного на параллельные вычислений; - автоматическое обнаружение параллелизма. Последовательная программа автоматически анализируется, и в результате может быть выявлена явная или скрытая параллельная обработка. Последняя должна быть преобразована в явную. Рассмотрим граф, описывающий последовательность процессов большой программы, представленный на рис. 3. Видно, что выполнение процесса Р } не может начаться до завершения процессов Р 2 и Р } и, в свою очередь, выполнение процессов Р 2 и P i не может начаться до завершения процесса Р у В данном случае для выполнения программы достаточно трех процессоров. Ускорение обработки на мультипроцессоре определяется отношением времени однопроцессорной обработки к времени многопроцессорной обработки: Конвейерная обработка улучшает использование аппаратных ресурсов для заданного набора процессов, каждый из которых применяет эти ресурсы заранее предусмотренным способом. Хорошим примером конвейерной организации является сборочный транспортер на производстве, на котором изделие последовательно проходит все стадии вплоть до готового продукта. Преимущество этого способа состоит в том, что каждое изделие вдоль своего пути использует одни и те же ресурсы, и как только некоторый ресурс освобождается данным изделием, он сразу же может быть использован следующим изделием, не ожидая, пока предыдущее изделие достигнет конца сборочной линии. Если транспортер несет аналогичные, но не тождественные изделия, то это последовательный конвейер; если же все изделия одинаковы, это векторный конвейер. Последовательные конвейеры. На рис. 4, а показано устройство обработки команд, в котором имеется четыре ступени: выборка команды из памяти, декодирование, определение адреса и выборка операнда, исполнение. Ускорение обработки в данном устройстве измеряется отношением времени Ts, необходимого для последовательного выполнения L заданий (т. е. выполнения L циклов на одной обрабатывающей ступени), ко времени Тр выполнения той же обработки на конвейере. Классификация архитектур многопроцессорных систем. Мультипроцессоры, ориентированные на достижение сверхбольших скоростей работы, могут содержать по нескольку сравнительно простых процессоров с упрощенными блоками управления. Удачной для различных мультипроцессоров является классификация Флина, которая строится по признаку одинарности или множественности потоков команд и данных Структура ОКОД (один поток команд, один поток данных) — однопроцессорная ЭВМ (рис. 5). Структура ОКМД (один поток команд, много потоков данных) — матричная многопроцессорная структура. Система содержит некоторое число одинаковых сравнительно простых быстродействующих процессоров, соединенных друг с другом и с памятью данных регулярным образом так, что образуется сетка (матрица), в узлах которой размещаются процессоры (рис. 6). Возникает сложная задача распараллеливания алгоритмов решаемых задач для обеспечения загрузки процессоров. В ряде случаев эти вопросы лучше решаются в конвейерной системе. Структура МКОД (много потоков команд, один поток данных) — конвейерная многопроцессорная структура (рис. 7). Система имеет регу- лярную структуру в виде цепочки последовательно соединенных процессоров, так что информация на выходе одного процессора является входной информацией для следующего в конвейерной цепочке. +Процессоры образуют конвейер, на вход которого одинарный поток данных доставляет операнды из памяти. Каждый процессор обрабатывает соответствующую часть задачи, передавая результаты соответствующему процессору, который использует их в качестве исходных данных. Таким образом, решение задач для некоторых исходных данных развертывается последовательно в конвейерной цепочке. Это обеспечивает подведение к каждому процессору своего потока команд, т. е. имеется множественный поток команд. Структура МКМД (много потоков команд, много потоков данных) представлена на рис. 8. Существует несколько типов МКМД: мультипроцессорные системы, системы с мультиобработкой, многомашинные системы, компьютерные сети. Контрольные вопросы 1. Что такое симметричная обработка? 2. Что такое ассиметричная обработка? 3. Что такое параллельная обработка? 4. Что такое конвейерная обработка? 5. Какие типы очередей бывают при мультипроцессорной обработке? Лекция 10 Методы синхронизации: взаимное исключение, блокирующие переменные План 1. Цели и средства синхронизации. 2. Механизмы синхронизации. 1.Цели и средства синхронизации Существует достаточно обширный класс средств операционной системы, с по- мощью которых обеспечивается взаимная синхронизация процессов и потоков. Потребность в синхронизации потоков возникает только в мультипрограммной операционной системе и связана с совместным использованием аппаратных и информационных ресурсов вычислительной системы. Синхронизация необходима для исключения гонок и тупиков при обмене данными между потоками, разделении данных, при доступе к процессору и устройствам ввода-вывода. Во многих операционных системах эти средства называются средствами межпро- цессного взаимодействия — Inter Process Communications (IPC), что отражает историческую первичность понятия «процесс» по отношению к понятию «поток». Обычно к средствам IPC относят не только средства межпроцессной синхронизации, но и средства межпроцессного обмена данными. Выполнение потока в мультипрограммной среде всегда имеет асинхронный ха- рактер. Очень сложно с полной определенностью сказать, на каком этапе выполнения будет находиться процесс в определенный момент времени. Даже в однопрограммном режиме не всегда можно точно оценить время выполнения задачи. Это время во многих случаях существенно зависит от значения исходных данных, которые влияют на количество циклов, направления разветвления программы, время выполнения операций ввода-вывода и т. п. Так как исходные данные в разные моменты запуска задачи могут быть разными, то и время выполнения отдельных этапов и задачи в целом является весьма неопределенной величиной. Еще более неопределенным является время выполнения программы в мульти- программной системе. Моменты прерывания потоков, время нахождения их в очередях к разделяемым ресурсам, порядок выбора потоков для выполнения — все эти события являются результатом стечения многих обстоятельств и могут быть интерпретированы как случайные. В лучшем случае можно оценить вероятностные характеристики вычислительного процесса, например вероятность его завершения за данный период времени. Таким образом, потоки в общем случае (когда программист не предпринял спе- циальных мер по их синхронизации) протекают независимо, асинхронно друг другу. Это справедливо как по отношению к потокам одного процесса, выполняющим общий программный код, так и по отношению к потокам разных процессов, каждый из которых выполняет собственную программу. Любое взаимодействие процессов или потоков связано с их синхронизацией, ко- торая заключается в согласовании их скоростей путем приостановки потока до наступления некоторого события и последующей его активизации при наступлении этого события. Синхронизация лежит в основе любого взаимодействия потоков, связано ли это взаимодействие с разделением ресурсов или с обменом данными. Например, поток- получатель должен обращаться за данными только после того, как они помещены в буфер потоком-отправителем. Если же поток-получатель обратился к данным до момента их поступления в буфер, то он должен быть приостановлен. При совместном использовании аппаратных ресурсов синхронизация также со- вершенно необходима. Когда, например, активному потоку требуется доступ к последовательному порту, а с этим портом в монопольном режиме работает другой поток, находящийся в данный момент в состоянии ожидания, то ОС приостанавливает активный поток и не активизирует его до тех пор, пока нужный ему порт не освободится. Часто нужна также синхронизация с событиями, внешними по отношению к вычислительной системе, например реакции на нажатие комбинации клавиш Ctrl+C. Ежесекундно в системе происходят сотни событий, связанных с распределением и освобождением ресурсов, и ОС должна иметь надежные и производительные средства, которые бы позволяли ей синхронизировать потоки с происходящими в системе событиями. Для синхронизации потоков прикладных программ программист может исполь- зовать как собственные средства и приемы синхронизации, так и средства операционной системы. Например, два потока одного прикладного процесса могут координировать свою работу с помощью доступной для них обоих глобальной логической переменной, которая устанавливается в единицу при осуществлении некоторого события, например выработки одним потоком данных, нужных для продолжения работы другого. Однако во многих случаях более эффективными или даже единственно возможными являются средства синхронизации, предоставляемые операционной системой в форме системных вызовов. Так, потоки, принадлежащие разным процессам, не имеют возможности вмешиваться каким-либо образом в работу друг друга. Без посредничества операционной системы они не могут приостановить друг друга или оповестить о произошедшем событии. Средства синхронизации используются операционной системой не только для синхронизации прикладных процессов, но и для ее внутренних нужд. Обычно разработчики операционных систем предоставляют в распоряжение при- кладных и системных программистов широкий спектр средств синхронизации. Эти средства могут образовывать иерархию, когда на основе более простых средств строятся более сложные, а также быть функционально специализированными, например средства для синхронизации потоков одного процесса, средства для синхронизации потоков разных процессов при обмене данными и т. д. Часто функциональные возможности разных системных вызовов синхронизации перекрываются, так что для решения одной задачи программист может воспользоваться несколькими вызовами в зависимости от своих личных предпочтений. |