Нарисуйте схему кругового циклического алгоритма и поясните его особенности. (80-81 пункт 3)

Круговой циклический алгоритм (КЦА) (рис.2.7, в) [10] или карусельная (Round Robin) дисциплина [1]. Здесь: НЗ – новый запрос, ОЗ – обслуженный запрос, t_k – квант обслуживания. Алгоритм основан на дисциплине FIFO и используется при реализации режима РДВ.

Рис.2.7. Дисциплины обслуживания FIFO, LIFO и КЦА

В КЦА возможны две ситуации, когда могут быть:

· короткий НЗ, имеющий длительность облуживания t₁≤ t_k. Он обслуживается очень быстро;

· длинный НЗ, его длительность облуживания t₂ > t_k. Если измерять условную длину (l) запроса числом использованных t_k и обозначить n_ср – среднюю длину очереди, а t^ср_ожид – среднее время ожидания, то

откуда

Время обслуживания зависит от t_k, длины запроса (l), длины очереди (n_ср).

Сравните различные одноочередные ДРР. (80 пункт 2.6.2)

Вначале рассмотрим простейшие одноочередные ДРР [10], когда организуется единственная очередь запросов на ресурс от процессов (рис.11).

1. Дисциплина обслуживания в порядке поступления или First In – First Out (FIFO) (рис.2.7,а).

2. Дисциплина обслуживания в порядке, обратном порядку поступления, Last In – First Out (LIFO), по сути представляющая стек (рис.2.7,б).

В принципе возможна и очередь с двумя концами, имеющая название «дек» – от слов double ended queue (deque).

3. Круговой циклический алгоритм (КЦА) (рис.2.7, в) [10] или карусельная (Round Robin) дисциплина [1]. Здесь: НЗ – новый запрос, ОЗ – обслуженный запрос, t_k – квант обслуживания. Алгоритм основан на дисциплине FIFO и используется при реализации режима РДВ.

Рис.2.7. Дисциплины обслуживания FIFO, LIFO и КЦА

В КЦА возможны две ситуации, когда могут быть:

· короткий НЗ, имеющий длительность облуживания t₁≤ t_k. Он обслуживается очень быстро;

· длинный НЗ, его длительность облуживания t₂ > t_k. Если измерять условную длину (l) запроса числом использованных t_k и обозначить n_ср – среднюю длину очереди, а t^ср_ожид – среднее время ожидания, то

откуда

Время обслуживания зависит от t_k, длины запроса (l), длины очереди (n_ср).

4. Дисциплина обслуживания вида «следующим будет выполняться самый короткий запрос» [1].

5. Дисциплина обслуживания вида «следующим будет выполняться запрос, которому осталось меньше всех выполняться на процессоре» [1].

Нарисуйте схему бесприоритетной многоочередной ДРР и поясните ее особенности. (82 рис.2.8 (я не уверен))

1. Неприоритетная многоочередная ДРР (рис.2.8) основана на КЦА:

· организуется N очередей;

· все новые запросы поступают в конец очереди 1;

· первый запрос очереди i (1≤i≤N) поступает на обслуживание, если очереди 1, 2,…, (i-1) – пусты;

· на обслуживание выделяется квант времени t_k;

· не до конца обслуженный запрос возвращается в конец очереди (i+1), что похоже на неявное снижение приоритета длинного запроса.

Рис.2.8. Схема неприоритетной многоочередной ДРР

Ее особенности: наиболее быстро обслуживаются короткие запросы; возникают непроизводительные затраты времени на перемещение запросов из одной очереди в другую; длинные запросы обслуживаются еще медленнее, чем в КЦА.

Нарисуйте схему приоритетной многоочередной ДРР и поясните ее особенности. (82-83 рис.2.9)

Приоритетная многоочередная ДРР (рис.2.9) также основана КЦА и является модификацией предыдущей дисциплины. Она отличается от предыдущей дисциплины тем, что каждый новый запрос имеет приоритет p=1÷N и попадает в очередь с номером j=N-p+1.

Рис.2.9. Схема приоритетной многоочередной ДРР

По отношению к новым запросам с приоритетами возможны две следующие стратегии поведения системы.

52. Как изменится поведение приоритетной многоочередной ДРР при переходе на работу с динамическими приоритетами? (84-87)

Кроме рассмотренных ДРР, существуют и другие, ориентированные на специфику самого распределяемого ресурса. Например, при распределении ОП используется:

· разная техника распределения ОП:

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

Ø динамическое распределение – в момент порождения процесса (требуется ожидание освобождения ОП, поэтому возможны задержки, простои);

Ø комбинированное распределение – частично статически, частично динамически;

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

При распределении непрерывными областями может возникать явление фрагментации [1-4, 10]. Его суть состоит в том, что после многократного выделения и освобождения областей ОП остаются незаполненные области (НО) все более малого размера – такие, что размера каждой из них уже будет недостаточно для загрузки программы, а суммарный размер свободной ОП будет достаточно большим. Пример фрагментации приведен на рис.2.11,а–д, где показано распределение ОП для задач разного объема (в условных единицах в скобках) по состоянию в разные моменты времени t₁, t₂, …, t₅. Из рис.2.11 видно, что в момент времени t₅ в ОП не может быть загружена задача объемом 3 единицы в то время, когда суммарный объем НО составляет 20 единиц из общего числа 27 единиц. Ограничение объема загружаемых задач ужесточается с течением времени, что отражено в табл.2.2.

Поэтому при таком распределении ОП необходимы программные средства объединения всех малых НО ОП в единственную непрерывную область на основе различных известных алгоритмов устранения «дыр» в ОП.

а) t₁ б) t₂ в) t₃ г) t₄ д) t₅

Задача 1 (12)     Задача 2 (10) Задача 3 (1)   НО-1 (4)

Задача 4 (8)   НО-2 (4)   Задача 5 (8)   НО-3 (2) Задача 3 (1)   НО-1 (4)

Задача 7 (6) НО-5 (2) Задача 6 (2) НО-4 (2)     Задача 8 (6) НО-6 (2) НО-3 (2) Задача 3 (1)   НО-1 (4)

Задача 7 Задача 9 (2) Задача 6 Задача 10 (2)   Задача 8 (3) Задача 11 (2) НО-7 (1) НО-6 (2) НО-3 (2) НО-8 (1) Задача 12 (2) НО-1 (2)

Задача 13 (4) НО-9 (2) НО-10 (2) НО-11 (2) НО-12 (2)   Задача 8 (3) НО-13 (2) НО-7 (1) НО-6 (2) НО-3 (2) НО-8 (1) НО-14 (2) НО-1 (2)

Рис.2.11. Распределение ОП для задач разного объема по состоянию моменты времени t₁, t₂, …, t₅.

Таблица 2.2

Момент времени:	t0=0	t1	t2	t3	t4	t5
Предел объема загружаемой задачи (усл.ед.) в момент ti
Предел объема загружаемой задачи (усл.ед.) после ti и завершения других задач

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

Смена «представителя» в главной карусели организуется за счет динамического временного повышения или понижения приоритета задач в локальной карусели. В главной карусели предоставление процессора может осуществляться по аналогичному или иному правилу.

Рис.2.12. Двухступенчатая карусельная схема

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

Рис.2.13. Многоступенчатая карусельная схема

53. Чем в ДРР различаются обслуживание с абсолютным и относительным приоритетом и какое обслуживание организовать проще?

2. Обслуживание с абсолютным приоритетом. Если во время обслуживания запроса из очереди i поступает запрос в очередь j < i, то обслуживание i-го уровня прерывается, система начинает обслуживать более приоритетный запрос в течение t_k. После окончания его обслуживания продолжается обслуживание прерванного запроса i-го уровня. Особенности: дискриминация низкоприоритетных запросов, время ожидания высокоприоритетных уменьшается, усложняется логика работы системы и ее реализация, появляется проблема прерывания обслуживания, и понадобятся дополнительные средства и ресурсы для ее реализации. Дисциплина подходит для систем управления объектами, в которых важна быстрая реакция на событие. Но при таком подходе возникают и сложные организационные проблемы:

· найти удачное правило продолжения обслуживания прерванного запроса:

Ø когда ему вновь выделять ресурс (если сразу – новые затраты);

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

· выбрать, в какую очередь помещать прерванный запрос (i+1, i, i-1);

· что делать, если во время прерывания обслуживания появится еще запрос уровня q < I (проблема маскирования)?

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

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

· взаимосвязи процессов;

· стратегий распределения других ресурсов;

· тупиковых ситуаций, когда возникает циклический конфликт занятости ресурсов [1, 2]. Пример подобной ситуации приведен на рис.2.10, где Процессу 1 требуются Ресурсы 1 и 2, но выделяется только Ресурс 1, так как Ресурс 2 ранее уже был выделен Процессу 2, которому требовался еще Ресурс 1. Но Ресурс 1 также занят и не может быть выделен Процессу 2;

· прав процесса использовать разделяемый ресурс;

· специфики самого ресурса.

	Процесс 1		Процесс 2
	Ресурс 1		Ресурс 2

Рис.2.10. Пример тупиковой ситуации

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

№25Перечислете и поясните функции подсистемы управления памятью. Существует большое разнообразие алгоритмов распределения памяти. Одним из наиболее популярных способов управления памятью в современных операционных системах является так называемая виртуальная память. Наличие в ОС механизма виртуальной памяти позволяет программисту писать программу так, как будто в его распоряжении имеется однородная оперативная память большого объема, часто существенно превышающего объем имеющейся физической памяти. функциями ОС по управлению памятью являются отслеживание свободной и занятой памяти; выделение памяти процессам и освобождение памяти при завершении процессов; защита памяти; вытеснение процессов из оперативной памяти на диск, когда размеры основной памяти недостаточны для размещения в ней всех процессов, и возвращение их в оперативную память, когда в ней освобождается место, а также настройка адресов программы на конкретную область физической памяти. Защита памяти — это избиpaтeльнaя способность предохранять выполняемую задачу от записи или чтения памяти, назначенной другой задаче. Правильно написанные программы не пытаются обращаться к памяти, назначенной другим.

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

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

№28Кто и для чего использует API,ГИП? Возможности операционной системы доступны прикладному программисту в виде набора функций, называющегося интерфейсом прикладного программирования (API). Для разработчиков приложений все особенности конкретной операционной системы представлены особенностями ее API. Поэтому операционные системы с различной внутренней организацией, но с одинаковым набором функций API кажутся им одной и той же ОС, что упрощает стандартизацию операционных систем и обеспечивает переносимость приложений между внутренне различными ОС, соответствующими определенному стандарту на API. Операционная система должна обеспечивать удобный интерфейс не только для прикладных программ, но и для человека, работающего за терминалом. Этот человек может быть конечным пользователем, администратором ОС или программистом. Современные ОС поддерживают развитые функции пользовательского интерфейса для интерактивной работы за терминалами двух типов: алфавитно-цифровыми и графическими.

№29 Каковы роль и возможности ГИП в современных ОС? Трудно переоценить роль интерфейса пользователя в современных программах. Удачный или неудачный интерфейс во многом предопределяет успех или неудачу всей системы. В еще большей степени это относится к офисным системам, пользователи которых не искушены в программировании и зачастую не имеют большого опыта работы на компьютере. Разработчик таких систем обычно сосредоточивает усилия на создании дружелюбного и удобного интерфейса пользователя. Удобство интерфейса - вещь субъективная: то, что нравится одному пользователю, может оказаться неудобным и даже совершенно неприемлемым для другого. Поэтому при проектировании системы желательно заранее включать в нее возможность настройки интерфейса на различные категории пользователей. Современные ОС поддерживают развитые функции пользовательского интерфейса для интерактивной работы за терминалами двух типов: алфавитно-цифровыми и графическими. При работе за алфавитно-цифровым терминалом пользователь имеет в своем распоряжении систему команд, мощность который отражает функциональные возможности данной ОС. Обычно командный язык ОС позволяет запускать и останавливать приложения, выполнять различные операции с файлами и каталогами, получать информацию о состоянии ОС (количество работающих процессов, объем свободного пространства на дисках и т. п.), администрировать систему. Команды могут вводиться не только в интерактивном режиме с терминала, но и считываться из так называемого командного файла, содержащего некоторую последовательность команд.

№30Опишите концепции построения ГИП. Основу Гип составляют следующие концепции: 1)графическая модель интерфейса, концепция рабочего стола, концепция окон, объектная ориентация, фундаментальная концепция укажи и выбери, направляемое главенство пользователя, концепция согласованности интерфейса.

№31Опишите основные принципы постороения ГИП. 1)Пользователь почти всегда прав. Этот принцип подразумевает, что разработчик ГИП может и должен сделать многое во имя пользователя. 2) ПС должна быть удобной, а ГИП – естественным и дружелюбным. 3)Пользователь может разработать свою концептуальную модель интерфейса, то есть модель работы программы. Интерфейс должен поддерживать эту модель и обеспечить ожидаемый пользователем результат. 4)Пользователь может и должен управлять диалогами. Система должна позволить пользователю выполнить любое корректное действия. 5) ГИП должен быть предсказуемым и учитывать здравый смысл, опыт взаимодействия с другими ПС. 6)Действия пользователя должны быть обратимыми, чтобы исключить потерю информации. 7)Контекст- обеспечивает поддержку пользовательской ориентации. 8)Наглядность ПИ с минимум доверия к памяти пользователя. 9)Обратная связь для действия пользователя: цвет, выделения и специальные индикации отбора для выделения места и сделанного выбора, звук. 10)Необходимость подтверждения потенциально разрушительных действий с выводом сообщений в окнах или опций. 11)Совместимость интерфейса с экраном и безоконными средствами. 12) Наличие альтернативных средств выполнения многошаговых действий. 13) Делать эффективным интерфейс клавиатуры для наиболее часто встречающихся офисных приложений и ПС. 14)Обеспечить поддержку совместного действия мыши и клавиатуры в любой точке диалога. 15) Старятся придерживаться совместимости и согласованности, особенно фундаментальных понятий и отношений во всех операционных средах. Три вида согласованности: семантическая, синтаксическая, физическая.

№32Опишите примеры технических приемов и дополнительных правил построения ГИП. 1) ГИП не должен бросаться в глаза. 2)ГИП должен иметь эстетическую привлекательность. 3)ГИП должен деликатно поддерживать пользовательскую технологию освоения ПС методом проб и ошибок: удачный выход из ситуации потери ориентации; снижение вероятности ошибок – понятные варианта выбора. 4) ГИП должен предвосхищать события – следующие шаги пользователя. 5) ГИП должен быть целостным и функционально полным. 6)Если при использовании вашего ГИП хоть один пользователь сделал ошибочное действие, то вам еще есть над чем работать. Например, название окна «Завершение работы с Windows…» лучше перевести «Варианты завершения/продолжения…» . 6) Если какое-то правило неприменимо или не имеет смысла, то хороший разработчик знает, когда можно его нарушить или изменить.

№33Покажите необходимость, роль и классы прерываний. Прерывания являются основной движущей силой любой операционной системы. Отключите систему прерываний — и «жизнь» в операционной системе немедленно остановится. Периодические прерывания от таймера вызывают смену процессов в мультипрограммной ОС, а прерывания от устройств ввода-вывода управляют потоками данных, которыми вычислительная система обменивается с внешним миром. В зависимости от источника прерывания делятся на три больших класса: внешние; внутренние;программные. Внешние прерывания могут возникать в результате действий пользователя или оператора за терминалом, или же в результате поступления сигналов от аппаратных устройств — сигналов завершения операций ввода-вывода, вырабатываемых контроллерами внешних устройств компьютера, такими как принтер или накопитель на жестких дисках, или же сигналов от датчиков управляемых компьютером технических объектов. Внутренние прерывания, называемые также исключениями происходят синхронно выполнению программы при появлении аварийной ситуации в ходе исполнения некоторой инструкции программы. Программные прерывания отличаются от предыдущих двух классов тем, что они по своей сути не являются «истинными» прерываниями. Программное прерывание возникает при выполнении особой команды процессора, выполнение которой имитирует прерывание, то есть переход на новую последовательность инструкций.