Доступные операции с данными

Память только для чтения (read-only memory, ROM)

Память для чтения/записи

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

10. Сетевые ОС: особенность работы, примеры, график - Основные функциональные компоненты сетевой ОС.

1) Серверная часть ОС - это средство предоставления локальных ресурсов и услуг в общее пользование.

2) Клиентская часть - это средство запроса доступа к удаленным ресурсам.

3) Транспортные - это средства обмена сообщениями в сети.

11. Зарисовать упрощенную схему работы сетевой ОС, написать пояснение.

12. Требования к современным ОС -

1) Расширяемость - это возможность внесения изменений без нарушения целостности системы, достигается модульной структурой.

2) Переносимость - ОС должна легко переносится с аппаратной платформы одного типа на аппаратную плотформу другого типа. Такое свойство называют многоплатформенностью.

3) Совместимость - Совместимости разделяют на 2 типа:

1) На уровне двоичного кода.

2) На уровне исходных текстов.

4) Надежность и защитоустойчивость - защита от внутренних ошибок, сбоев и отказов. Приложения не должны наносить вред ОС.

5) Безопасность - защита данных.

6) Производительность - быстродействие и время реакции. Определяется архитектурой ОС.

Процесс может находиться в одном из 3-х состояний:
1) Готовность - пассивное состояние, процесс заблокирован, имеет все ресурсы, но процессор занят
2) Выполнение - активное состояние, ресурсы есть, процесс выполняется.
3) Ожидание - пассивное состояние процесс заблокирован, процесс не может выполняться по внутренним причинам.

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

Процесс – единица работы вычислительной системы, требующая ресурсов. Наиболее распространенное определение – «программа в стадии выполнения». Точнее, это объединение программ и данных, требующих ресурсов для своей реализации.

14. Пакетные ОС: цели, схема функционирования, концепция мультипрограммирования-

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

15.Системы разделения времени: цели, схема функционирования, концепция мультипрограммирования-

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

16. Системы реального времени: цели, схема функционирования, концепция мультипрограммировани

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

17. Понятие процессов и потоков-

Процесс – единица работы вычислительной системы, требующая ресурсов. Наиболее распространенное определение – «программа в стадии выполнения». Точнее, это объединение программ и данных, требующих ресурсов для своей реализации.
Примеры процессов: компиляция программы (компилятор + исходный модуль + ресурсы); редактирование межмодульных связей объектных модулей (редактор + совместно выполняемые объектные модули + ресурсы); выполнение загруженной программы (исполняемый код + входные данные задачи + ресурсы); выполнение любого приложения или системной программы.
Для обеспечения безопасности процессов они изолируются друг от друга и каждый процесс обеспечивается отдельным виртуальным адресным пространством. При необходимости взаимодействия ОС предоставляет процессам средства межпроцессорной связи – конвейеры, почтовые ящики, разделяемые секции памяти и др.
В операционных системах, где существует распараллеливание вычислений, процесс рассматривается как заявка на потребление всех видов ресурсов, кроме процессорного времени. Процессорное время распределяется между потоками данного процесса. Понятию «поток», таким образом, соответствует некоторая последовательность команд программы в процессе ее выполнения.
Применительно к таким операционным системам речь идет уже о многопоточной обработке (multithreading). При этом потоки рассматриваются как новые единицы работы, между которыми ОС распределяет процессорное время.
Итак, ОС назначает процессу адресное пространство и набор ресурсов, кроме процессорного времени. Процессорное время распределяется между потоками данного процесса. Поток – это единица работы внутри процесса.
Все потоки одного процесса изолированы друг от друга гораздо меньше, чем процессы, и используют общие ресурсы своего процесса. Задача, оформленная в виде нескольких потоков в рамках одного процесса, может быть выполнена быстрее за счет псевдопараллельного выполнения ее отдельных частей.

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

19. Понятие контекст процесса. Задачи контекста- Контекст процесса содержит менее оперативную, но более объемную часть информации о процессе, необходимую для возобновления выполнения процесса с прерванного места: содержимое регистров процессора, коды ошибок выполняемых процессором системных вызовов, информацию о всех открытых данным процессом файлов и незавершенных операциях ввода-вывода (указатели на структуры file) и другие данные, характеризующие состояние вычислительной среды в момент прерывания. Контекст, так же как и дескриптор процесса, доступен только программам ядра, то есть находится в виртуальном адресном пространстве операционной системы, однако он хранится не в области ядра, а непосредственно примыкает к образу процесса и перемещается вместе с ним, если это необходимо, из оперативной памяти на диск. В UNIX для процессов предусмотрены два режима выполнения: привилегированный режим - "система" и обычный режим - "пользователь". В режиме "пользователь" запрещено выполнение действий, связанных с управлением ресурсами системы, в частности, корректировка системных таблиц, управление внешними устройствами, маскирование прерываний, обработка прерываний. В режиме "система" выполняются программы ядра, а в режиме "пользователь" - оболочка и прикладные программы. При необходимости выполнить привилегированные действия пользовательский процесс обращается с запросом к ядру в форме так называемого системного вызова. В результате системного вызова управление передается соответствующей программе ядра. С момента начала выполнения системного вызова процесс считается системным. Таким образом, один и тот же процесс может находиться в пользовательской и системной фазах. Эти фазы никогда не выполняются одновременно.

20. Зарисовать типичный граф состояний потока в многозадачной системе, описать принцип его работы- Многозада́чность — свойство операционной системы или среды программирования обеспечивать возможность параллельно обработки нескольких процессов. Истинная многозадачность операционной системы возможна только в распределённых вычислительных системах.

21.Алгоритмы планирования процессов и потоков- Планирование процессов включает в себя решение следующих задач:
1.определение момента времени для смены выполняемого процесса;

2.выбор процесса на выполнение из очереди готовых процессов.

Различные алгоритмы планирования могут преследовать различные цели и обеспечивать разное качество мультипрограммирования. Например, алгоритм должен гарантировать, что ни один процесс не будет занимать процессор дольше определенного времени; другой обеспечивает максимально быстрое выполнение «коротких» задач; третий обеспечивает преимущественное право на процессорное время интерактивным приложениям. Именно особенности планирования процессов в наибольшей степени определяют специфику ОС.

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

Статический тип планирования используется в специализированных системах, где набор одновременно выполняемых задач определен заранее (например, в системах реального времени). Здесь решение о планировании принимается заранее (off-line).

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

2.загрузка контекста нового процесса;

3.запуск нового процесса.

В отличие от планирования, осуществляемого программными средствами ОС, диспетчеризация реализуется совместно с аппаратными средствами процессора.

22. Зарисовать типичный граф состояний потока в системе с приоритетом, описать принцип его работы-

Современная ОС динамически реагирует на различные действия происходящие в системе.

Планирование осуществляется статически или динамически.

Смешанные алгоритмы планирования.

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

К примеру, в основе – концепция квантования, а определение кванта и/или дисциплина обслуживания очередей базируется на приоритетах.
БИЛЕТ 26. Планирование в ОС UNIX
Пересчет приоритета процесса происходит в момент выбора процесса для выполнения на ЦП 1 раз в секунду.
Процессам назначается базовый приоритет, чтобы их можно было разделять на фиксированные группы уровней приоритетов.
Эти группы используются для оптимизации доступа к блочным устройствам (например, к диску) и обеспечения быстрого отклика операционной системы на системные вызовы.

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

Планирование в Windows NT.

Квантование сочетается с использованием динамических абсолютных приоритетов.
В системе определено 32 уровня приоритетов.
Два класса нитей: Нити с переменными приоритетами (0-15];
Нити “реального” времени (16-31] – высокоприоритетные нити.
Нити с переменными приоритетами
Изначально процессу присваивается базовый приоритет.
Базовый приоритет процесса может меняться ОС, следовательно, могут измениться базовые приоритеты составляющих его нитей.
Нить получает значение приоритета из диапазона базового приоритета.
Приоритет нити может отклоняться от своего базового приоритета, и это может быть не связано с изменением базового приоритета процесса (см. диапазон значений динамического приоритета нитей).

Планирование свопинга в ОС Unix

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

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

Планирование в системах реального времени

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

Надо также учитывать последствия, к которым может привезт несоблюдение временных рамок.
Системы реального времени бывают “Жесткие” и ” мягкие ”.

В первом случае время завершения выполнения каждого из процессов должно быть гарантировано для всех сценариев функционирования системы.
Это может быть обеспечено за счет: полного тестирования всевозможных сценариев; построения статического расписания; выбора математически просчитанного алгоритма динамического планирования.
Периодические запросы – все моменты запроса периодического процесса можно определить заранее.
Пусть {Ti} набор периодических процессов с периодами – pi, предельными сроками выполнения di и требованиями ко времени выполнения ci.
Расписание удается построить не всегда.
Для проверки возможного составления расписания анализируется расписание на отрезке времени равному наименьшему общему множителю периодов этих процессов.
С целью определения возможности построения расписания используются различные критерии.
Необходимое условие наличия расписания:
Сумма коэффициентов использования m=S ci / pi <= k, где k - количество доступных процессоров.
Общие критерии для сравнения алгоритмов планирования

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

Планирование обработки прерываний

Правильное планирование обработки прерываний – залог правильного планирования процессов.

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

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

^ Упорядоченное планирование прерываний

Механизм прерываний поддерживает приоритезацию и маскирование прерываний.

Источники прерываний делятся на классы – каждому классу свой уровень приоритета запроса на прерывание.

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

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

^ Планирование обработки прерываний в Windows NT

Все источники прерываний делятся на несколько классов, и каждому уровню присваивается уровень запроса прерывания – Interrupt Request Level (IRQL). Этот уровень и представляет приоритет данного класса.

Поступление запроса на прерывание/исключение – вызов диспетчера прерываний, который: Запоминает информацию об источнике прерывания; Анализирует его приоритет.

^ Если приоритет <= IRQL прерванного, то отложить в очередь, иначе текущий обработчик – в очередь, управление – новому.

Особенности планирования ввода/ вывода

Одна из важных задач планирования – обеспечение занятости внешних устройств

Для этого можно присваивать процессам высокий приоритет в периоды, когда они интенсивно используют ввод/ вывод

Эти периоды легко прослеживаются: процесс блокируется про обращении к вводу/выводу; операции ввода/вывода обычно бывают сконцентрированы в отдельных частях программ.

25.

26.

27. Проблема тупиков: график, описание

Тупики. Приведенный выше пример поможет нам проиллюстрировать еще одну проблему синхронизации - взаимные блокировки, называемые также дедлоками (deadlocks), клинчами (clinch) или тупиками. Если переставить местами операции P(e) и P(b) в программе "писателе", то при некотором стечении обстоятельств эти два процесса могут взаимно заблокировать друг друга. Действительно, пусть "писатель" первым войдет в критическую секцию и обнаружит отсутствие свободных буферов; он начнет ждать, когда "читатель" возьмет очередную запись из буфера, но "читатель" не сможет этого сделать, так как для этого необходимо войти в критическую секцию, вход в которую заблокирован процессом "писателем".

Рассмотрим еще один пример тупика. Пусть двум процессам, выполняющимся в режиме мультипрограммирования, для выполнения их работы нужно два ресурса, например, принтер и диск. На рисунке 2.6,а показаны фрагменты соответствующих программ. И пусть после того, как процесс А занял принтер (установил блокирующую переменную), он был прерван. Управление получил процесс В, который сначала занял диск, но при выполнении следующей команды был заблокирован, так как принтер оказался уже занятым процессом А. Управление снова получил процесс А, который в соответствии со своей программой сделал попытку занять диск и был заблокирован: диск уже распределен процессу В. В таком положении процессы А и В могут находиться сколь угодно долго.

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

Рис. 2.6. (a) фрагменты программ А и В, разделяющих принтер и диск;
(б) взаимная блокировка (клинч);(в) очередь к разделяемому диску;
(г) независимое использование ресурсов

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

Проблема тупиков включает в себя следующие задачи:

• предотвращение тупиков,
• распознавание тупиков,
• восстановление системы после тупиков.

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

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

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

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

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

28.Понятие критической секции, график описание.

Критические секции. Объект-критическая секция помогает программисту выделить участок кода, где нить получает доступ к разделяемому ресурсу, и предотвратить одновременное использование ресурса. Перед использованием ресурса нить входит в критическую секцию (вызывает функцию EnterCriticalSection). Если после этого какая-либо другая нить попытается войти в ту же самую критическую секцию, ее выполнение приостановится, пока первая нить не покинет секцию с помощью вызова LeaveCriticalSection. Используется только для нитей одного процесса. Порядок входа в критическую секцию не определен.Существует также функция TryEnterCriticalSection, которая проверяет, занята ли критическая секция в данный момент. С ее помощью нить в процессе ожидания доступа к ресурсу может не блокироваться, а выполнять какие-то полезные действия.

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

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

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

Другим способом является использование блокирующих переменных. С каждым разделяемым ресурсом связывается двоичная переменная, которая принимает значение 1, если ресурс свободен (то есть ни один процесс не находится в данный момент в критической секции, связанной с данным процессом), и значение 0, если ресурс занят. На рисунке 2.4 показан фрагмент алгоритма процесса, использующего для реализации взаимного исключения доступа к разделяемому ресурсу D блокирующую переменную F(D). Перед входом в критическую секцию процесс проверяет, свободен ли ресурс D. Если он занят, то проверка циклически повторяется, если свободен, то значение переменной F(D) устанавливается в 0, и процесс входит в критическую секцию. После того, как процесс выполнит все действия с разделяемым ресурсом D, значение переменной F(D) снова устанавливается равным 1.

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

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

Обобщающее средство синхронизации процессов предложил Дейкстра, который ввел два новых примитива. В абстрактной форме эти примитивы, обозначаемые P и V, оперируют над целыми неотрицательными переменными, называемыми семафорами. Пусть S такой семафор. Операции определяются следующим образом:

V(S): переменная S увеличивается на 1 одним неделимым действием; выборка, инкремент и запоминание не могут быть прерваны, и к S нет доступа другим процессам во время выполнения этой операции.

P(S): уменьшение S на 1, если это возможно. Если S=0, то невозможно уменьшить S и остаться в области целых неотрицательных значений, в этом случае процесс, вызывающий P-операцию, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также является неделимой операцией.

Рис. 2.5. Реализация критической секции с использованием системных
функций WAIT(D) и POST(D)

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

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

Введем два семафора: e - число пустых буферов и f - число заполненных буферов. Предположим, что запись в буфер и считывание из буфера являются критическими секциями (как в примере с принт-сервером в начале данного раздела). Введем также двоичный семафор b, используемый для обеспечения взаимного исключения. Тогда процессы могут быть описаны следующим образом:

29. Влияние относительных скоростей потоков на результат решения задачи.

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

1. Считать из файла базы данных в буфер запись о клиенте с заданным идентификатором.

2. Внести новое значение в поле Заказ (для потока А) или Оплата (для потока В).

3. Вернуть модифицированную запись в файл базы данных.

Рис. 6.1.1. Возникновение гонок при доступе к разделяемым данным

Обозначим соответствующие шаги для потока А как Al, A2 и A3, а для потока В как Bl, B2 и ВЗ. Предположим, что в некоторый момент поток А обновляет поле Заказ записи о клиенте N. Для этого он считывает эту запись в свой буфер (шаг А1), модифицирует значение поля Заказ (шаг А2), но внести запись в базу данных (шаг A3) не успевает, так как его выполнение прерывается, например, вследствие завершения кванта времени.

Предположим также, что потоку В также потребовалось внести сведения об оплате относительно того же клиента N. Когда подходит очередь потока В, он успевает считать запись в свой буфер (шаг В1) и выполнить обновление поля Оплата (шаг В2), а затем прерывается. Заметим, что в буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение.

Когда в очередной раз управление будет передано потоку А, то он, продолжая свою работу, запишет запись о клиенте N с модифицированным полем Заказ в базу данных (шаг A3). После прерывания потока А и активизации потока В последний запишет в базу данных поверх только что обновленной записи о клиенте N свой вариант записи, в которой обновлено значение поля Оплата. Таким образом, в базе данных будут зафиксированы сведения о том, что клиент N произвел оплату, но информация о его заказе окажется потерянной (рис. 6.1.2, а).

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

Рис. 6.1.2. Влияние относительных скоростей потоков на результат решения задачи

30. Понятие блокирующих переменных.

31.Семафорные примитивы Дейкстра.

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

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

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

PCS): уменьшение S на 1, если это возможно. Если S=0 и невозможно уменьшить S, оставаясь в области целых неотрицательных значений, то в этом случае поток, вызывающий операцию Р, ждет, пока это уменьшение станет возможным. Успешная проверка и уменьшение также являются неделимой операцией.

Никакие прерывания во время выполнения примитивов V и Р недопустимы.

В частном случае, когда семафор S может принимать только значения 0 и 1, он превращается в блокирующую переменную, которую по этой причине часто называют двоичным семафором. Операция Р заключает в себе потенциальную возможность перехода потока, который ее выполняет, в состояние ожидания, в то время как операция V может при некоторых обстоятельствах активизировать другой поток, приостановленный операцией Р.

Рассмотрим использование семафоров на классическом примере взаимодействия двух выполняющихся в режиме мультипрограммирования потоков, один из которых пишет данные в буферный пул, а другой считывает их из буферного пула. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись. В общем случае поток-писатель и поток-читатель могут иметь различные скорости и обращаться к буферному пулу с переменой интенсивностью. В один период скорость записи может превышать скорость чтения, в другой — наоборот. Для правильной совместной работы поток-писатель должен приостанавливаться, когда все буферы оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, поток-читатель должен приостанавливаться, когда все буферы пусты, и активизироваться при появлении хотя бы одной записи.

Введем два семафора: е — число пустых буферов, и f — число заполненных буферов, причем в исходном состоянии е =N, a f =0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис. 6.1.5).

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

Рис. 6.1.5. Использование семафоров для синхронизации потоков

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

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

49. Таблица прав файлов и папок для Web-интерфейсов.

50. Понятие виртуальной памяти.

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

При использовании виртуальной памяти упрощается программирование, так как программисту больше не нужно учитывать ограниченность памяти, или согласовывать использование памяти с другими приложениями. Для программы выглядит доступным и непрерывным все допустимое адресное пространство, вне зависимости от наличия в ЭВМ соответствующего объёма ОЗУ.

Применение механизма виртуальной памяти позволяет:

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

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

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

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

Не нашли, что искали? Воспользуйтесь поиском: