Мультипрограммирование. Формы многопрограммной работы

Мультипрограммирование призвано повысить эффективность использования вычислительной системы [10, 17]. Однако эффективность может пониматься по-разному. Наиболее характерными показателями эффективности вычислительных систем являются:

- пропускная способность – количество задач, выполняемых системой в единицу времени;

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

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

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

Системы пакетной обработки предназначались для решения задач в основном вычислительного характера, не требующих быстрого получения результатов [11]. Максимальная пропускная способность компьютера достигается в этом случае минимизацией простоев его устройств и прежде всего процессора. Для достижения этой цели пакет заданий формируется так, чтобы получающаяся мультипрограммная смесь сбалансированно загружала все устройства машины. Например, в такой смеси желательно присутствие задач вычислительного характера и с интенсивным вводом-выводом. Однако в этом случае трудно гарантировать сроки выполнения того или иного задания.

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

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

Рис. 4.4. Иллюстрация эффекта мультипрограммирования

 

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

Рис. 4.5. Система разделения времени

 

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

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

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

Интересная форма мультипрограммной работы связана с мультипроцессорной обработкой. Мультипроцессорная обработка – это способ организации вычислительного процесса в системе с несколькими процессорами, при котором несколько задач (процессов, потоков) могут одновременно выполняться на разных процессорах системы. Концепция мультипроцессирования не нова, она известна с 70-х годов, однако стала доступной в широком масштабе лишь в последнее десятилетие, особенно с появлением многопроцессорных ПК (часто в качестве серверов ЛВС).

В отличие от мультипрограммной обработки, в мультипроцессорных системах несколько задач выполняется одновременно, т.к. имеется несколько процессоров. Однако это не исключает мультипрограммной обработки на каждом процессоре. При этом резко усложняются все алгоритмы управления ресурсами, т.е. операционная система. Современные ОС, как правило, поддерживают мультипроцессирование (Sun Solaris 2.x, Santa Cruz Operation Open Server 3.x, OS/2, Windows NT/2000/2003/XP, NetWare, начиная с версии 4.1 и др.).

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

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

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

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

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

 

Лекция 5. Тема: Контекст процесса. Операции над процессами. Вытесняющая та невитесняющая многозадачность в основных архетипах операционных систем.

 

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

- создание процессов и потоков;

- обеспечение процессов и потоков необходимыми ресурсами;

- изоляция процессов;

- планирование выполнения процессов и потоков (вообще, следует говорить и о планировании заданий);

- диспетчеризация потоков;

- организация межпроцессного взаимодействия;

- синхронизация процессов и потоков;

- завершение и уничтожение процессов и потоков.

К созданию процесса приводят пять основных событий:

- инициализация ОС (загрузка);

- выполнение запроса работающего процесса на создание процесса;

- запрос пользователя на создание процесса, например, при входе в систему в интерактивном режиме;

- инициирование пакетного задания;

- создание операционной системой процесса, необходимого для работы каких-либо служб.

Обычно при загрузке ОС создаются несколько процессов. Некоторые из них являются высокоприоритетными процессами, обеспечивающими взаимодействие с пользователями и выполняющими заданную работу. Остальные процессы являются фоновыми, они не связаны с конкретными пользователями, но выполняют особые функции – например, связанные с электронной почтой, Web-страницами, выводом на печать, передачей файлов по сети, периодическим запуском программ (например, дефрагментации дисков) и т.д. Фоновые процессы называют демонами.

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

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

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

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

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

- сохранение контекста текущего потока;

- загрузка контекста потока, выбранного в результате планирования;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

 

Лекция 6. Тема: Механизмы наследования процессов для основных архетипов операционных систем

 

Создание процессов и потоков. Модели процессов и потоков

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

Примерами таких описателей процесса являются:

- блок управления задачей (ТСВ – Task Control Block) в OS/360;

- управляющий блок процесса (PCB – Process Control Block) в OS/2;

- дескриптор процесса в UNIX;

- объект-процесс (object-process) в Windows NT/2000/2003.

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

Множество, в которое входят программа, данные, стеки и атрибуты процесса, называется образом процесса.

Типичные элементы образа процесса приведены ниже.

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

 

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

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

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

- информация по идентификации процесса;

- информация по состоянию процесса;

- информация, используемая при управлении процессом.

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

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

- состояние процесса, определяющее готовность процесса к выполнению (выполняющийся, готовый к выполнению, ожидающий какого-либо события, приостановленный);

- данные о приоритете (текущий приоритет, по умолчанию, максимально возможный);

- информация о событиях – идентификация события, наступление которого позволит продолжить выполнение процесса;

- указатели, позволяющие определить расположение образа процесса в оперативной памяти и на диске;

- указатели на другие процессы (в частности, находящиеся в очереди на выполнение);

- флаги, сигналы и сообщения, имеющие отношение к обмену информацией между двумя независимыми процессами;

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

- указатели на ресурсы, которыми управляет процесс (например, перечень открытых файлов);

- сведения по истории использования ресурсов и процессора;

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

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

В контексте процесса содержится следующая основная информация [10]:

- содержимое регистров процессора, доступных пользователю;

- содержимое счетчика команд;

- состояние управляющих регистров и регистров состояния;

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

- указатели вершин стеков, хранящие параметры и адреса вызова процедур и системных служб.

Следует заметить, что часть этой информации, известная как "слово состояния программы" (Program Status Word – PSW), фиксируется в специальном регистре процессора (например, в регистре EFLAGS в процессорах Pentium).

Самую простую модель процесса можно построить исходя из того, что в любой момент времени процесс либо выполняется, либо не выполняется, т.е. имеет только два состояния. Если бы все процессы были бы всегда готовы к выполнению, то очередь по этой схеме могла бы работать вполне эффективно. Такая очередь работает по принципу обработки в порядке поступления, а процессор обслуживает имеющиеся в наличии процессы круговым методом (Round-robin). Каждому процессу отводится определенный промежуток времени, по истечении которого он возвращается в очередь.

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

 

Рис 6.1

 

Лекция 7. Тема: Нитки управления. Анализ ниток і процессов для основных архетипов операционных систем

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

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

Ввести массив А

Ввести массив В

Ввести массив С

А=А+В

С=А+С

Вывести массив С

При выполнении такой программы в рамках одного процесса этот процесс будет 4 раза блокироваться ожидая окончания операции ввода/вывода. Но этот алгоритм обладает внутренним параллелизмом. Вычисление суммы массивов А+В можно было бы выполнять параллельно с ожиданием окончания операции ввода массива С. Такое совмещение операций можно реализовать использую два взаимодействующих процессов. Для простаты считаем, что процессы взаимодействуют через разделяемую память.

Процесс 1 процесс 2

Создать процесс

Переключение контекста

Выделение общей памяти

Ожидание ввода А и В

Переключение контекста

Выделение общей памяти

Переключение контекста

А=А+В

Переключение контекста

С=А+С

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

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

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

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

Процесс находится в состоянии исполнения если одна из его нитей находится в состояние исполнения. Процесс находится в состояние ожидания если все его нити находятся в состоянии ожидания. Наконец, процесс находится в состоянии завершил исполнение если все его нити находятся в состоянии завершил исполнение.

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

Различают ОС поддерживающие нити на уровне ядра и на уровне библиотеки. ОС поддерживающая нити на уровне ядра использует планирование Ц.П. в терминах нити а управление памятью и другими ресурсами остается в терминах процесса. В ОС поддерживающей нити на уровне библиотек пользователей и планирование Ц.П. и управление ресурсами осуществляется в терминах процесс.

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

 

 

Лекция 8. Тема: Семафоры. Определения. Реализация. Задача взаимодействия производителя и потребителя данных и ее решение с помощью блокировок и семафоров

Семафоры могут применяться для различных целей. Их можно использовать для взаимного исключения, синхронизации взаимодействия процессов и управления выделением ресурсов. В зависимости от конкретного применения используются разные начальные значения семафора и различные последовательности вызова методов SImWait() и SimSignal().

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

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

 

2) Условная синхронизация – два взаимосвязанных процесса должны иметь возможность синхронизировать свои действия. Процессы могут быть связаны следующим образом: при достижении процессом А определенной точки, он не может продолжить роботу, пока процесс В не выполнит некоторую задачу. Для их синхронизации можно применять инициализированный значением 0 семафор, у которого процесс А должен ждать в точке синхронизации, выполнив вызов SimWait(), пока процесс В не вызовет метод SimSignal(). Особенность данного способа применения семафора заключается в том, что вызов SimWait() выполняет один процесс, а вызов SimSignal() – другой.

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

 

3) Использование более одного экземпляра ресурса. В ОС типичной бывает ситуация, когда несколько процессов имеют возможность обращаться к ресурсу одновременно, но количество таких обращений должно быть ограничено. Если в системе имеется два принтера, которые представляют собой ресурс, которым одновременно могут пользоваться несколько процессов, соответствующий семафор этого ресурса нужно инициализировать значением 2. Каждый раз, когда некоторый процесс запрашивает доступ к ресурсу и значение семафора этого ресурса больше 0, данное значение уменьшается на 1. Как только значение семафора станет равным 0, последующие попытки доступа к ресурсу должны быть блокированы, а соответствующие процессы установлены в очередь. После ого, как процесс освободит ресурс, семафор проверит имеющиеся в очереди другие процессы. При их отсутствии значение семафора увеличивается на 1, в противном случае одному из процессов предоставляется доступ к ресурсу.

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

Для успешного функционирования семафора недостаточно одних атомарных операций SimWait() и SimSignal(). Необходимо также, чтобы эти операции начавших обязательно завершились, причем без чрезмерных задержек. Проверка и изменение значения семафора задержек не вызывает. Изменение состояния процесса требует доступа к его дескриптору, возможно с вызовом операций блокировать и разблокировать, реализованных в другом модуле.

Доступ к дескриптору процесса может осуществляться от имени другого процесса. Если предположить, что время выполнения операций блокировать и разблокировать фиксировано, то можно гарантировать и время выполнения операций SimWait() и SimSiganl().

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

 

 

Лекция 9. Тема: Логическая организация файловых систем

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

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

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

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

Таким образом, необходимо хранить данные на устройствах компьютеров.