Многозадачность в системах разделения времени

Курсовая работа

по дисциплине:

" Безопасность операционных систем"

«Многозадачность в системах разделения времени»

Ставрополь, 2011

К моменту появления персональных компьютеров в мире существовало несколько технических решений позволяющих реализовать многозадачность на больших машинах. В бывшем СССР это были машины серии ЕС и болгарские ИЗОТ. Они теоретически позволяли подключать до 255 терминалов, где каждому терминалу выделялось некоторое количество ресурсов компьютера и процессорного времени. На практике нормальная работа такого комплекса обеспечивалась при наличии не более 25−30 терминалов, или меньше при сложных задачах.

Для персональных ЭВМ многозадачность не вводилась принципиально. Ведь исходя из названия PC — «Personal Computer» предполагалось, что работать будет один человек с одной текущей задачей. В качестве операционной системы была принята переработанная система CP/M под названием MS-DOS. Она так же не предусматривала многозадачности. Основная проблема разработки многозадачной операционной системы это не реентерабельность ее функций. То есть если один процесс запустил функцию чтения файла, то другой процесс не сможет не только обращаться к файлам, но и вообще вызвать другие ее функции. Для этого необходима поддержка на уровне процессора которая была введена с разработкой линейки 286. Многозадачность (multitasking) — это способность операционной системы выполнять несколько программ одновременно. В основе этого принципа лежит использование операционной системой аппаратного таймера для выделения отрезков времени (time slices) для каждого из одновременно выполняемых процессов. Если эти отрезки времени достаточно малы, и машина не перегружена слишком большим числом программ, то пользователю кажется, что все эти программы выполняются параллельно.

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

Для того, чтобы многозадачность стала реальностью на персональных компьютерах, потребовалось достаточно много времени. Но, кажется, сейчас мы приближаемся к эпохе использования многозадачности на ПК (PC). Как мы увидим вскоре, некоторые расширенные 16-разрядные версии Windows поддерживают многозадачность, а имеющиеся теперь в нашем распоряжении Windows NT и Windows 95 — 32-разрядные версии Windows, поддерживают кроме многозадачности еще и многопоточность (multithreading).

1. Управление процессами

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

В многозадачной (многопроцессной) системе процесс может находиться в одном из трех основных состояний:

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

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

Готовность — также пассивное состояние процесса, но в этом случае процесс заблокирован в связи с внешними по отношению к нему обстоятельствами: процесс имеет все требуемые для него ресурсы, он готов выполняться, однако процессор занят выполнением другого процесса.

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

Рис. 1. Граф состояний процесса в многозадачной среде В состоянии ВЫПОЛНЕНИЕ в однопроцессорной системе может находиться только один процесс, а в каждом из состояний ОЖИДАНИЕ и ГОТОВНОСТЬ — несколько процессов, эти процессы образуют очереди соответственно ожидающих и готовых процессов. Жизненный цикл процесса начинается с состояния ГОТОВНОСТЬ, когда процесс готов к выполнению и ждет своей очереди. При активизации процесс переходит в состояние ВЫПОЛНЕНИЕ и находится в нем до тех пор, пока либо он сам освободит процессор, перейдя в состояние ОЖИДАНИЯ какого-нибудь события, либо будет насильно «вытеснен» из процессора, например, вследствие исчерпания отведенного данному процессу кванта процессорного времени. В последнем случае процесс возвращается в состояние ГОТОВНОСТЬ. В это же состояние процесс переходит из состояния ОЖИДАНИЕ, после того, как ожидаемое событие произойдет.

1.1 Контекст и дескриптор процесса

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

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

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

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

1. создать информационные структуры, описывающие данный процесс, то есть его дескриптор и контекст;

2. включить дескриптор нового процесса в очередь готовых процессов;

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

1.2 Алгоритмы планирования процессов

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

1. определение момента времени для смены выполняемого процесса;

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

3. переключение контекстов «старого» и «нового» процессов.

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

· процесс завершился и покинул систему,

· произошла ошибка,

· процесс перешел в состояние ОЖИДАНИЕ,

· исчерпан квант процессорного времени, отведенный данному процессу.

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

Кванты, выделяемые процессам, могут быть одинаковыми для всех процессов или различными. Кванты, выделяемые одному процессу, могут быть фиксированной величины или изменяться в разные периоды жизни процесса. Процессы, которые не полностью использовали выделенный им квант (например, из-за ухода на выполнение операций ввода-вывода), могут получить или не получить компенсацию в виде привилегий при последующем обслуживании. По разному может быть организована очередь готовых процессов: циклически, по правилу «первый пришел — первый обслужился» (FIFO) или по правилу «последний пришел — первый обслужился» (LIFO). Другая группа алгоритмов использует понятие «приоритет» процесса. Приоритет — это число, характеризующее степень привилегированности процесса при использовании ресурсов вычислительной машины, в частности, процессорного времени: чем выше приоритет, тем выше привилегии.

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

Рис. 2. Графы состояний процессов в системах (а) с относительными приоритетами; (б) с абсолютными приоритетами Во многих операционных системах алгоритмы планирования построены с использованием как квантования, так и приоритетов. Например, в основе планирования лежит квантование, но величина кванта и / или порядок выбора процесса из очереди готовых определяется приоритетами процессов.

1.3 Вытесняющие и невытесняющие алгоритмы планирования

Существует два основных типа процедур планирования процессов — вытесняющие (preemptive) и невытесняющие (non-preemptive).

Non-preemptive multitasking — невытесняющая многозадачность — это способ планирования процессов, при котором активный процесс выполняется до тех пор, пока он сам, по собственной инициативе, не отдаст управление планировщику операционной системы для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс.

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

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

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

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

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

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

Однако почти во всех современных операционных системах, ориентированных на высокопроизводительное выполнение приложений (UNIX, Windows, OS/2, VAX/VMS), реализована вытесняющая многозадачность. В последнее время дошла очередь и до ОС класса настольных систем, например, OS/2 Warp и Windows XP. Возможно в связи с этим вытесняющую многозадачность часто называют истинной многозадачностью.

2. Аналитическая часть

2.1 Общие сведения о матричных принтерах

Матричный принтер (Dot-Matrix-Printer) — старейший из ныне применяемых типов принтеров, был изобретён в 1964 году корпорацией Seiko Epson.

Принцип работы матричного принтера следующий. Изображение формируется с помощью печатающей головки, которая представляет собой один или два ряда вертикально расположенных тонких иголок (игольчатая матрица), приводимых в действие электромагнитами. Головка устанавливается на ракетке и передвигается построчно вдоль листа, при этом иголки в нужный момент времени ударяют через красящую ленту по бумаге, формируя точечное изображение. Этот тип принтеров называется SIDM (англ. Serial Impact Dot Matrix — последовательные ударно-матричные принтеры).

Существуют принтеры с 9, 12, 14, 18 и 24 иголками в головке. Основное распространение получили 9-ти (дешевые модели) и 24-х игольчатые принтеры. Качество печати и скорость графической печати зависят от числа иголок: больше иголок — больше точек. Качество печати в 9-ти игольчатых принтерах улучшается при печати информации не в один, а в два или четыре прохода печатающей головки вдоль печатаемой строки. Более качественная и быстрая печать обеспечивается 24-игольчатыми принтерами, называемыми LQ (англ. Letter Quality — качество пишущей машинки). Однако эти принтеры не только более дорогостоящи, но и менее надежны, а также замена вышедших из строя печатающих головок представляет определенные трудности.

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

Для перемещения красящей ленты используется передаточный механизм, использующий движение каретки. За перемещение каретки отвечает шаговой двигатель. Еще один шаговой двигатель отвечает за перемещение бумагоопорного валика. Именно поэтому скорость печати матричных принтеров невысока. В зависимости от выбранного качества печати и модели принтера скорость печати составляет от 10 до 60 секунд на страницу. Скорость печати матричных принтеров измеряется в CPS (англ. characters per second — символах в секунду).

Матричные принтеры оборудованы внутренней памятью (буфером) для хранения данных, полученных от персонального компьютера. Объем памяти недорогих принтеров составляет от 4 до 64 Кбайт. Хотя существуют модели, имеющие и больший объем памяти (например, Seikosha SP-2415 имеет буфер размером 175 Кбайт).

2.2 Проектирование символов для матричных принтеров

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

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

Загружаемые шрифты становятся доступными только после размещения их описания в оперативную памяти принтера и могут воспроизводиться только до конца текущего сеанса (до выключения питания принтера) или до момента загрузки в оперативную память принтера описания другого шрифта.

Проектирование и воспроизведение произвольных литер состоит из следующих этапов:

1. Сначала изображается кривая, образующую литеру.

2. Далее рассчитываются данные, необходимые для описания кривой.

3. Затем эти данные посылаются в оперативную память принтера для связи описание символа с определенным кодом.

4. Принтеру дается команда напечатать данную литеру вместо той, которую он воспроизводит в соответствии с описанием для этого же кода из постоянной памяти.

Рассмотрим механизм формирования символов на примере принтера Epson LX1050. Этот матричный принтер имеет печатающую головку с 24 иголками и может воспроизводить символы в нескольких режимах. В каждом из режимов допускается конструирование символов с помощью матриц различной ширины и высоты (таблица 1). Минимальная ширина символов — 5.

Таблица 1 — Таблица соответствия размеров матриц режимам принтера

Рисунок 3 — Пример формирования матрицы для печати символа «А»

Символ представляет собой матрицу, в которой темные ячейки соответствуют выпячиваемым иголкам, а светлые — утапливаемым. Такая матрица может быть закодирована. Каждой строке матрицы присвоен номер. Все строки матрицы разбиты на три группы, внутри каждой из которых нумерация повторяется. Каждый столбец матрицы кодируется тремя байтами, соответствующими одной из групп строк. Значение каждого из трех байтов, кодирующих столбец, определяется суммой, присвоенной строкам, на пересечении которых с данным столбцом размещен знак"*" (рисунок 2).

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

При описании символа количество колонок (ml), образующих символ, и общее пространство (m0+ml+m2). занимаемое символом, не должны превышать значений, представленных в таблице 3.

Таблица 2 — Таблица соответствия значения количества колонок и общего пространства режимам принтера

В соответствии с условием поставленной задачи рассматриваемым режимом матричного принтера является Draft, следовательно, матрица имеет размеры в ширину 9 позиций и в высоту 24 иголок. Ширину отступов от символа слева (m0) и справа (m2) выберем равными одной иголке.

Чтобы связать описание символа с соответствующим кодом, необходимо послать на принтер набор команд, указывающих режим, номер кода загружаемого символа, три байта общего описания символа (m0, ml, m2) и байты описания столбцов матрицы. Данные операции прослеживаются на примере листингов приложений.

Заданием на курсовую работу было проектирование своих инициалов — т. е. С, Б, П.

Проектирование символа «С»

1. На клеточном поле 9×24 изображается кривая проектируемого символа, затем на ее основе проектируется матрица (Рисунок 4).

Рисунок 4 — Матрица символа «С»

2. Каждый столбец матрицы кодируется тремя байтами (таблица 3).

Таблица 3 — Значение кодирующих байтов матрицы для символа «С»

3. Затем в оперативную память принтера передается данные, связанные с кодом литеры, и подается команда печати спроектированного символа. Проектирование символов «П», «Б» осуществляется аналогично.

Проектирование символа «Б»

Рисунок 5 — Матрица символа «Б»

Таблица 4 — Значение кодирующих байтов матрицы для символа «Б»

Листинг третьего этапа проектирования приведен в приложении 2.

Проектирование символа «П»

Рисунок 6 — Матрица символа «П»

Таблица 5 — Значение кодирующих байтов матрицы для символа «П»

Листинг третьего этапа проектирования приведен в приложении 3.

Заключение

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

1. Гайчук Д. В., Подопригора Н. Б. Методические указания к выполнению курсовой работы по дисциплине «Безопасность операционных систем» для студентов специальности 90 105 «Комплексное обеспечение информационной безопасности автоматизированных систем», Ставрополь 2006;05−15

2. В. Г. Олифер, Н. А. Олифер «Сетевые операционные системы» Серия: Учебник для вузов. Издательство: Питер, 2008 г.

3. Операционные системы, среды и оболочки И. И. Попов, Т.Л. Партыка

2003 г., Изд: Форум, 400 с.

4. Дмитрий Иртегов «Введение в операционные системы» Санкт — Петербург, 2003 г., Изд: BHV, 624 с.