УЗБЕКСКОЕ АГЕНСТВО СВЯЗИ И ИНФОРМАТИЗАЦИИ

 

ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

 

ФАКУЛЬТЕТ "ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ"

 

 

 

 

 

КОНСПЕКТ ЛЕКЦИЙ ПО КУРСУ

 

 

 

«ОПЕРАЦИОННЫЕ СИСТЕМЫ»

 

 

 

 

 

 

 

 

 

 

 


 

Содержание

 

 

Введение.

3

Глава 1.

Основные понятия

5

Глава 2.

Управление задачами

47

Глава 3.

Управление памятью в операционных системах

72

Глава 4.

Особенности архитектуры

микропроцессоров i80x86 для организации

мультипрограммных операционных систем

104

Глава 5.

Управление вводом-выводом в операционных системах

136

Глава 6.

Файловые системы

172

Глава 7.

Организация параллельных взаимодействующих вычислений

222

Глава 8.

Проблема тупиков и методы борьбы с ними

262

Глава 9.

Архитектура операционных систем

291

Глава 10.

Краткий обзор современных операционных систем

328

 

 

 

 

Введение

 

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

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

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

 

 

 

 

 

 

Глава 1. Основные понятия

 

Эта глава является вводной и, пожалуй, самой главной. Любой предмет имеет свои основные понятия и положения. Не является исключением и дисциплина «Опе­рационные системы». К основным понятиям, без которых практически невозмож­но по-настоящему изучить эту дисциплину, понять основные принципы организа­ции вычислений, взаимодействия прикладных программ с операционной системой и пользователей с компьютерами, следует, прежде всего, отнести понятия вычис­лительных процессов и ресурсов, системной программы, супервизора, операцион­ной среды, прерываний. Мы также рассмотрим относительно новые понятия, к которым относятся поток выполнения и задача: они дополняют понятие вычисли­тельного процесса и позволяют более эффективно организовать работу компьюте­ра. Поскольку абсолютное большинство операционных систем обеспечивают воз­можность параллельного выполнения нескольких программ, мы познакомимся с понятием мультипрограммирования. Завершается глава обзором основных обще­принятых классификаций.

 

Назначение и функции операционных систем

 

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

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

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

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

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

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

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

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

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

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

Для автоматизации труда программиста (кодера) стали разрабатывать специаль­ные алгоритмические языки высокого уровня, а для автоматизации труда опера­тора вычислительного комплекса была разработана специальная управляющая программа, загрузив которую в память один раз оператор мог ее далее использо­вать неоднократно и более не обращаться к процедуре программирования ЭВМ через пульт оператора. Именно эту управляющую программу и стали называть операционной системой. Со временем на нее стали возлагать все больше и больше задач, она стала расти в объеме. Прежде всего разработчики стремились к тому, чтобы операционная система как можно более эффективно распределяла вычис­лительные ресурсы компьютера, ведь в 60-е годы операционные системы уже по­зволяли организовать параллельное выполнение нескольких программ. Помимо задач распределения ресурсов появились задачи обеспечения надежности вычис­лений. К началу 70-х годов диалоговый режим работы с компьютером стал преоб­ладающим, и у операционных систем стремительно начали развиваться интерфейс­ные возможности. Напомним, что термином интерфейс (interface) обозначают целый комплекс спецификаций, определяющих конкретный способ взаимодей­ствия пользователя с компьютером.

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

1   Системными принято называть такие программы, которые используются всеми остальными про­граммами.

 

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

Можно попробовать перечислить основные функции операционных систем.

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

·        Загрузка в оперативную память подлежащих исполнению программ.

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

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

·        Идентификация всех программ и данных.

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

·        Обслуживание всех операций ввода-вывода.

·        Обеспечение работы систем управлений файлами (СУФ) и/или систем управ­ления базами данных (СУБД), что позволяет резко увеличить эффективность всего программного обеспечения.

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

·        Планирование и диспетчеризация задач в соответствии с заданными стратеги­ей и дисциплинами обслуживания.

·        Организация механизмов обмена сообщениями и данными между выполняю­щимися программами.

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

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

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

·        Удовлетворение жестким ограничениям на время ответа в режиме реального времени (характерно для операционных систем реального времени).

·        Обеспечение работы систем программирования, с помощью которых пользова­тели готовят свои программы.

·        Предоставление услуг на случай частичного сбоя системы.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 1.1. Взаимодействие пользователя и его программ с компьютером

через операционную систему

 

Понятие операционной среды

 

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

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

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

Можно сказать, что программы создаются для работы в некоторой заданной опе­рационной среде. Например, можно создать программу для работы в среде DOS, Если такая программа все функции, связанные с операциями ввода-вывода и с за­просами памяти, выполняет не сама, а за счет обращения к системным функциям DOS, то она будет (в абсолютном большинстве случаев) успешно выполняться и в MS DOS, и в PC DOS, и в Windows 9х, и в Windows 2000, и в OS/2, и даже в Linux. Итак, параллельное существование терминов «операционная система» и «опера­ционная среда» вызвано тем, что операционная система (в общем случае) может поддерживать несколько операционных сред. Почти все современные 32-разряд­ные операционные системы, созданные для персональных компьютеров, поддер­живают по нескольку операционных сред. Так, операционная система OS/2 Warp, которая в свое время была одной из лучших в этом отношении, может выполнять следующие программы:

·        основные программы, созданные с учетом соответствующего «родного» 32-разряднго программного интерфейса этой операционной системы;

·        16-разрядные программы, созданные для систем OS/2 первого поколения;

·        16-разрядные приложения, разработанные для выполнения в операционной среде MS DOS или PC DOS;

·        16-разрядные приложения, созданные для операционной среды Windows 3.x;

·        саму операционную оболочку Windows 3.x и уже в ней — созданные для нее программы.

А операционная система Windows XP позволяет выполнять помимо основных приложений, созданных с использованием Win32API, 16-разрядные приложения для Windows 3.x, 16-разрядные DOS-приложения, 16-разрядные приложения для первой версии OS/2.

Операционная среда может включать несколько интерфейсов: пользовательские и программные. Если говорить о пользовательских, то, например, система Linux имеет для пользователя как интерфейсы командной строки (можно использовать различные «оболочки» — shell), наподобие Norton Commander, например Midnight Commander, так и графические интерфейсы, например X-Window с различными менеджерами окон — KDE, Gnome и др. Если же говорить о программных интер­фейсах, то в тех же операционных системах с общим названием Linux программы могут обращаться как к операционной системе за соответствующими сервисами и функциями, так и к графической подсистеме (если она используется). С точки зре­ния архитектуры процессора (и персонального компьютера в целом) двоичная программа, созданная для работы в среде Linux, использует те же команды и фор­маты данных, что и программа, созданная для работы в среде Windows NT. Однако в первом случае мы имеем обращение к одной операционной среде, а во втором к другой. И программа, созданная непосредственно для Windows. не будет выпол­няться в Linux; однако если в операционной системе Linux организовать полно­ценную операционную среду Windows, то наша Windows - программа может быть выполнена. Завершая этот раздел, можно еще раз сказать, что операционная среда — это то системное программное окружение, в котором могут выполняться про­граммы, созданные по правилам работы этой среды.

 

Прерывания

 

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

Идея прерывания была предложена также очень давно — в середине 50-х годов, — можно без преувеличения сказать, что она внесла наиболее весомый вклад в раз­витие вычислительной техники. Основная цель введения прерываний — реализа­ция асинхронного режима функционирования и распараллеливание работы отдель­ных устройств вычислительного комплекса.

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

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

1.  Установление факта прерывания (прием сигнала запроса на прерывание) и идентификация прерывания (в операционных системах идентификация пре­рывания иногда осуществляется повторно, на шаге 4).

2.  Запоминание состояния прерванного процесса вычислений. Состояние процесса выполнения программы определяется, прежде всего, значением счетчика ко­манд (адресом следующей команды, который, например, в i80x86 определяется регистрами CS и IP — указателем команды [1, 8, 48]), содержимым регистров процессора, и может включать также спецификацию режима (например, режим пользовательский или привилегированный) и другую информацию.

3.  Управление аппаратно передается на подпрограмму обработки прерывания. В простейшем случае в счетчик команд заносится начальный адрес подпро­граммы обработки прерываний, а в соответствующие регистры — информация из слова состояния. В более развитых процессорах, например в 32-разрядных микропроцессорах фирмы Intel (начиная с i80386 и включая последние про­цессоры Pentium IV) и им подобных, осуществляются достаточно сложная про­цедура определения начального адреса соответствующей подпрограммы обра­ботки прерывания и не менее сложная процедура инициализации рабочих регистров процессора (подробно эти вопросы рассматриваются в разделе «Си­стема прерываний 32-разрядных микропроцессоров i80x86» главы 4).

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

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

6.  Восстановление информации, относящейся к прерванному процессу (этап, об­ратный шагу 4).

7.  Возврат на прерванную программу.

Шаги 1-3 реализуются аппаратно, шаги 4-7 — программно.

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

·        распознавание или классификация прерываний;

·        передача управления соответствующему обработчику прерываний;

·        корректное возвращение к прерванной программе.

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

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

Внешние прерывания вызываются асинхронными событиями, которые происходят вне прерываемого процесса, например:

·        прерывания от таймера;

·        прерывания от внешних устройств (прерывания по вводу-выводу);

·        прерывания по нарушению питания;

·        прерывания с пульта оператора вычислительной системы;

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

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

·        при наличии в поле кода операции незадействованной двоичной комбинации;

·        при делении на ноль;

·        вследствие переполнения или исчезновения порядка;

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

 

 

 

 

 

 

 

 

 

Подпись: Прерывание
 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 1.2. Обработка прерывания

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 1.3. Распределение прерываний по уровням приоритета

 

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

Программное управление специальными регистрами маски (маскирование сигна­лов прерывания) позволяет реализовать различные дисциплины обслуживания.

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

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

·        По принципу стека, или, как иногда говорят, по дисциплине LCFS (Last Come First Served - последним пришел, первым обслужен), то есть запросы с более низким приоритетом могут прерывать обработку прерывания с более высоким приоритетом. Дли этого необходимо не накладывать маску ни на один из сиг­налов прерывания и не выключать систему прерываний.

Следует особо отметить, что для правильной реализации последних двух дисцип­лин нужно обеспечить полное маскирование системы прерываний при выполне­нии шагов 1-4 и 6-7. Это необходимо для того, чтобы не потерять запрос и пра­вильно его обслужить. Многоуровневое прерывание должно происходить на этапе собственно обработки прерывания, а не на этапе перехода с одного процесса вы­числений на другой.

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

Как мы уже знаем, при появлении запроса на прерывание система прерываний идентифицирует сигнал и, если прерывания разрешены, то управление передает­ся на соответствующую подпрограмму обработки. Из рис. 1.2 видно, что в под­программе обработки прерывания имеется две служебные секции. Это - первая секция, в которой осуществляется сохранение контекста прерываемых вычисле­ний, который не смог быть сохранен на шаге 2, и последняя, заключительная сек­ция, в которой, наоборот, осуществляется восстановление контекста. Для того что­бы система прерываний не среагировала повторно на сигнал запроса на прерывание, она обычно автоматически «закрывает» (отключает) прерывания, поэтому необ­ходимо потом в подпрограмме обработки прерываний вновь включать систему пре­рываний. В соответствии с рассмотренными режимами обработки прерываний (с относительными и абсолютными приоритетами и по правилу LCFS) установка этих режимов осуществляется в конце первой секции подпрограммы обработки. Таким образом, на время выполнения центральной секции (в случае работы в ре­жимах с абсолютными приоритетами и по дисциплине LCFS) прерывания разре­шены. На время работы заключительной секции подпрограммы обработки систе­ма прерываний вновь должна быть отключена и после восстановления контекста опять включена. Поскольку эти действия необходимо выполнять практически в каждой подпрограмме обработки прерываний, во многих операционных систе­мах первые секции подпрограмм обработки прерываний выделяются в уже упо­минавшийся специальный системный программный модуль, называемый супер­визором прерываний.

Супервизор прерываний прежде всего сохраняет в дескрипторе текущей задачи ра­бочие регистры процессора, определяющие контекст прерываемого вычислитель­ного процесса. Далее он определяет ту подпрограмму, которая должна выполнить действия, связанные с обслуживанием настоящего (текущего) запроса на преры­вание. Наконец, перед тем, как передать управление на эту подпрограмму, супер­визор прерываний устанавливает необходимый режим обработки прерывания. После выполнения подпрограммы обработки прерывания управление вновь пере­дается ядру операционной системы. На этот раз уже на тот модуль, который зани­мается диспетчеризацией задач (см. раздел «Планирование и диспетчеризация процессов и задач» в главе 2). И уже диспетчер задач, в свою очередь, в соответ­ствии с принятой дисциплиной распределения процессорного времени (между выполняющимися вычислительными процессами) восстановит контекст той за­дачи, которой будет решено выделить процессор. Рассмотренную нами схему ил­люстрирует рис, 1.4.

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

 

 

Подпись: Прерывание 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 1.4. Обработка прерывания при участии супервизоров ОС

 

 

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

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

Понятия вычислительного процесса и ресурса

 

Понятие последовательного1 вычислительного процесса, или просто процесса, является одним из основных при рассмотрении операционных систем. Как поня­тие процесс является определенным видом абстракции, и мы будем придерживаться следующего неформального определения, приведенного в [47]. Последовательный процесс, иногда называемый задачей2 (task), — это отдельная программа с ее дан­ными, выполняющаяся на последовательном процессоре. Напомним, что под последовательным мы понимаем такой процессор, в котором текущая команда выполняется после завершения предыдущей. В современных процессорах мы стал­киваемся с ситуациями, когда возможно параллельное выполнение нескольких команд. Это делается для повышения скорости вычислений. В этих процессорах параллелизм достигается двумя основными способами — организацией конвейер­ного механизма выполнения команды и созданием нескольких конвейеров. Одна­ко в подобных процессорах аппаратными решениями обязательно достигается ло­гическая последовательность в выполнении команд, предусмотренная программой. Необходимость этого объясняется в главе 7, посвященной организации параллель­ных вычислительных процессов.

Концепция процесса предполагает два аспекта: во-первых, он является носителем данных и, во-вторых, он собственно и выполняет операции, связанные с обработ­кой этих данных.

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

 

Концепция процесса преследует цель выработать механизмы распределения и уп­равления ресурсами. Понятие ресурса, так же как и понятие процесса, является, пожалуй, основным при рассмотрении операционных систем. Термин ресурс обыч­но применяется по отношению к многократно используемым, относительно ста­бильным и часто недостающим объектам, которые запрашиваются, задействуются и освобождаются в период их активности. Другими словами, ресурсом называется всякий объект, который может распределяться внутри системы. Ресурсы могут быть разделяемыми, когда несколько процессов используют их одно­временно (в один и тот же момент времени) или параллельно (попеременно в тече­ние некоторого интервала времени), а могут быть и неделимыми (рис. 1.5).

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 1.5. Классификация ресурсов

 

 

При разработке первых систем ресурсами считались процессорное время, память, каналы ввода-вывода и периферийные устройства [22, 53]. Однако очень скоро понятие ресурса стало гораздо более универсальным и общим. Различного рода программные и информационные ресурсы также могут быть определены для сис­темы как объекты, которые могут разделяться и распределяться и доступ к кото­рым необходимо соответствующим образом контролировать. В настоящее время понятие ресурса превратилось в абстрактную структуру с целым рядом атрибутов, характеризующих способы доступа к этой структуре и ее физическое представле­ние в системе. Более того, помимо системных ресурсов, о которых мы сейчас гово­рили, ресурсами стали называть и такие объекты, как сообщения и синхросигна­лы, которыми обмениваются задачи.

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

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

 

 

Мультипрограммирование,

многопользовательский режим работы

и режим разделения времени

 

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

 

 

 

 

 

 

 

 

Вв

 

   CPU

 

Вв

 

   CPU

 
 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 1.6. Пример выполнения двух программ в мультипрограммном режиме

 

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

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

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

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

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

Очевидно, что диалоговый режим работы может быть реализован и без мульти-

программирования. Наглядное тому доказательство — многочисленные дисковые операционные системы, начиная от СР-М и кончая PC-DOS 7.0. которые долгие годы устанавливались на персональные компьютеры и обеспечивали только однопрограммный режим. Однако эти однопрограммные диалоговые системы появились гораздо позже мультипрограммных. Как это ни кажется странным, им пред­шествовали многочисленные и разнообразные операционные системы, позволяю­щие одновременно работать с компьютером большому количеству пользователей и параллельно решать множество задач. Основная причина тому — стоимость ком­пьютера. Только с удешевлением компьютеров поя вилась возможность иметь свой персональный компьютер, и первое время считалось, что однопрограммного ре­жима работы вполне достаточно. Главным для персональных компьютеров до сих пор считается удобство работы, причем именно в диалоговом режиме, простота интерфейса и его интуитивная понятность.

 

Совмещение диалогового режима работы с компьютером и режима мультипрог­раммирования привело к появлению мулътитерминалъных, или многопользова­тельских, систем. Организовать параллельное выполнение нескольких задач можно разными способами. Если это осуществля­ется таким образом, что на каждую задачу поочередно выделяется некий квант времени, после чего процессор передается другой задаче, готовой к продолжению вычислений, то такой режим принято называть режимом разделения времени (time sharing). Системы разделения времени активно развивались в 60-70 годы, и сам термин означал именно мультитерминальную и мультипрограммную систему. Итак, операционная система может поддерживать мультипрограммирование (мно­го-процессность). В этом случае она должна стараться эффективно использовать имеющиеся ресурсы путем организации к ним очередей запросов, составляемых тем или иным способом. Это требование достигается поддерживанием в памяти более одного вычислительного процесса, ожидающего процессор, и более одного процесса, готового использовать другие ресурсы, как только последние станут до­ступными.

Общая схема выделения ресурсов такова. При необходимости использовать ка­кой-либо ресурс (оперативную память, устройство ввода-вывода, массив данных и т. п.) вычислительный процесс (задача) путем обращения к супервизору1 (supervisor) операционной системы посредством специальных вызовов (команд, ди­ректив) сообщает о своем требовании. При этом указывается вид ресурса и, если надо, его объем. Например, при запросе оперативной памяти указывается количе­ство адресуемых ячеек, необходимое для дальнейшей работы.

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

Ресурс может быть выделен вычислительному процессу (задаче), обратившемуся к операционной системе с соответствующим запросом, если:

·        ресурс свободен и в системе нет запросов от задач более высокого приоритета к этому же ресурсу;

·        текущий запрос и ранее выданные запросы допускают совместное использование ресурсов;

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

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

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

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

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

 

Диаграмма состояний процесса

 

Необходимо отличать системные управляющие вычислительные процессы, определяющие работу супервизора операционной системы и занимающиеся распределением и управлением ресурсов, от всех других процессов: задач пользователей и системных обрабатывающих процессов. Последние, хоть и относятся к операци­онной системе, но не входят в ядро операционной системы и требуют общих ре­сурсов для своей работы, которые получают от супервизора. Для системных управ­ляющих процессов, в отличие от обрабатывающих, в большинстве операционных систем ресурсы распределяются изначально и однозначно. Эти вычислительные процессы сами управляют ресурсами системы, в борьбе за которые конкурируют все остальные процессы. Поэтому исполнение системных управляющих программ не принято называть процессами, и термин «задача» следует употреблять только по отношению к процессам пользователей и к системным обрабатывающим про­цессам. Однако это справедливо не для всех операционных систем. Например, в так называемых «микроядерных» операционных системах  большинство управляющих программных модулей самой операционной системы и даже драй­веры имеют статус высокоприоритетных процессов, для выполнения которых необходимо выделить соответствующие ресурсы. В качестве примера можно привести хорошо известную операционную систему реального времени QNX фирмы Quantum Software Systems. Аналогично и в UNIX-системах, которые хоть и не относятся к микроядерным, выполнение системных программных модулей тоже имеет статус системных процессов, получающих ресурсы для своего испол­нения.

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

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

·        выполнения — все затребованные процессом ресурсы выделены (в этом состоя­нии в каждый момент времени может находиться только один процесс, если речь идет об однопроцессорной вычислительной системе);

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

·        блокирования, или ожидания, — затребованные ресурсы не могут быть предо­ставлены, или не завершена операция ввода-вывода.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 1.7. Граф состояний процесса

 

 

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

Процесс из состояния бездействия может перейти в состояние готовности в следу­ющих случаях.

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

·        При выборе из очереди планировщиком (характерно для операционных сис­тем, работающих в пакетном режиме).

·        При вызове из другой задачи (посредством обращения к супервизору один про­цесс может создать, инициировать, приостановить, остановить, уничтожить другой процесс).

·        По прерыванию от внешнего инициативного устройства1 (сигнал о свершении некоторого события может запускать соответствующую задачу).

·        При наступлении запланированного времени запуска программы.

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

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

Из состояния выполнения процесс может выйти по одной из следующих при­чин.

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

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

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

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

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

 

Реализация понятия последовательного процесса в операционных системах

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

·        идентификатор процесса (Process Identifier, PID);

·        тип (или класс) процесса, который определяет для супервизора некоторые пра­вила предоставления ресурсов;

·        приоритет процесса, в соответствии с которым супервизор предоставляет ре­сурсы (в рамках одного класса процессов в первую очередь обслуживаются бо­лее приоритетные процессы);

·        переменную состояния, которая определяет, в каком состоянии находится про­цесс (готов к работе, выполняется, ожидает устройства ввода-вывода и т. д.);

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

·        информацию о ресурсах, которыми процесс владеет и/или имеет право пользо­ваться (указатели на открытые файлы, информация о незавершенных опера­циях ввода-вывода и др.);

·        место (или его адрес) для организации общения с другими процессами;

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

·        в случае отсутствия системы управления файлами адрес задачи на диске в ее исходном состоянии и адрес на диске, куда она выгружается из оперативной па­мяти, если ее вытесняет другая задача (последнее справедливо для диск-резидент­ных задач, которые постоянно находятся во внешней памяти на системном маг­нитном диске и загружаются в оперативную память только на время выполнения).

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

В некоторых операционных системах количество описателей определяется жест­ко и заранее (на этапе генерации варианта операционной системы или в конфигу­рационном файле, который используется при загрузке ОС), в других по мере необходимости система может выделять участки памяти под новые описатели. На­пример, в уже мало кому известной системе OS/2, которая несколько лет тому назад многими специалистами считалась одной из лучших ОС для персональных компьютеров, максимально возможное количество описателей задач указывается в конфигурационном файле CONFIG.SYS. Например, строка THREADS=1024 в файле CONFIG.SYS означает, что всего в системе может параллельно существовать и вы­полняться до 1024 задач, включая вычислительные процессы и их потоки. В ныне широко распространенных системах Windows NT/2000/ХР количество описателей нигде в явном виде не задается. Это переменная величина, и она опре­деляется самой операционной системой. Однако посмотреть на текущее количе­ство таких описателей можно. Если, работая в Windows NT/2000/XP, нажать од­новременно комбинацию клавиш Ctrl+Shift+Esc, появится окно Диспетчера задач. На вкладке Быстродействие этой программы мы увидим поле с названием Всего де­скрипторов и соответствующее число. Тут же указывается количество дескрипто­ров для управления потоками (задачами) и число полноценных вычислительных процессов. Более подробно о процессах и потоках см. далее.

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

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

Для аппаратной поддержки работы операционных систем с этими информацион­ными структурами (дескрипторами задач) н процессорах могут быть реализованы соответствующие механизмы. Так, например, в микропроцессорах Intel 80x86 имеется специальный регистр TR (Task Register), указывающий мес­тонахождение специальной информационной структуры — сегмента состояния задачи (Task State Segment, TSS), в котором при переключении с задачи на задачу автоматически сохраняется содержимое регистров процессора [1, 8, 48]. Поскольку между терминами «процесс» и «задача» со временем появилось суще­ственное различие, мы сейчас подробно рассмотрим этот вопрос.

 

Процессы и задачи

 

Хотя понятия мультипрограммного и мультизадачного режимов работы достаточ­но близки, это все-таки не одно и то же. К сожалению, здесь до сих пор имеется некоторая путаница. Основные причины тому — не только то, что терминология еще не устоялась и что многие фирмы-разработчики по-разному предпочитали называть один и те же сущности, но и сложность, неоднозначность ситуации.

Мультипрограммный режим предполагает, что операционная система организует параллельное выполнение нескольких вычислительных процессов на одном ком­пьютере. И каждый вычислительный процесс может, в принципе, никак не зави­сеть от другого вычислительного процесса. Разве что они могут задержать выпол­нение друг друга из-за необходимости поочередно разделять ресурсы или сильно задерживать выполнение друг друга при владении неразделяемым ресурсом. У них может не быть ни общих файл он, ни общих переменных. Они вообще могут при­надлежать разным пользователям. Просто эти процессы, с позиций внешнего на­блюдателя, выполняются на одном и том же компьютере в одно и то же время. Хотя могут выполняться и в разное время, и на разных компьютерах. Главное — это то, что мультипрограммный режим обеспечивает для этих процессов их неза­висимость. Каждому процессу операционная система выделяет затребованные ре­сурсы, он выполняется как бы на отдельной виртуальной машине. Средства защиты системы должны обеспечить невмешательство одного вычислительного процесса в другой вычислительный процесс. И если такую защиту обеспечить невозможно,

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

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

Термин мультизадачный режим работы стали применять как раз для тех случаев, когда необходимо обеспечить взаимодействие между вычислениями. Мультиза­дачный режим означает, что операционная система позволяет организовать парал­лельное выполнение вычислений, и имеются специальные механизмы для передачи данных, синхросигналов, каких-либо сообщений между этими взаимодействую­щими вычислениями. Это можно сделать за счет того, что такие вычисления не должны системой изолироваться друг от друга. Операционная система не должна для них в обязательном порядке задействовать все механизмы защиты вычисле­ний от невмешательства друг в друга. При мультизадачном режиме разработчик программы должен позаботиться о разделении ресурсов между его задачами. Опера­ционная система будет всего лишь разделять процессорное время между задачами. Понятие процесса было введено для реализации идей мультипрограммирования. Термин задача тоже, к сожалению, в большинстве случаев применялся для того же. В свое время различали термины «мультизадачность» и «мультипрограмми­рование», но потом они стали заменять друг друга, и это вносило немалую путани­цу. Таким образом, для реализации мультизадачности в ее исходном толковании необходимо было ввести соответствующую сущность. Такой сущностью стали лег­ковесные (thin) процессы, или. как их теперь преимущественно называют, потоки выполнения1, нити, или треды (threads).

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

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

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

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

Особенно эффективно можно использовать многопоточность для выполнения рас­пределенных приложений. Например, многопоточный сервер может параллельно выполнять запросы сразу нескольких клиентов. Как известно, операционная сис­тема OS/2 была одной из первых систем, используемых в персональных компью­терах, которая поддерживала многопоточность. В середине 90-х годов для этой опе­рационной системы было создано большое количество приложений, в которых наличие механизмов многоноточной обработки реально приводило к существен­ному повышению скорости вычислений. Для систем Windows, с которыми мы все имеем дело, ярко выраженной многопоточностью обладают такие продукты,-как SQL Server, Oracle. И хотя те же Word, Excel, Internet Explorer также при своей работе образуют потоки, явного параллелизма в этих программах почти не под­держивается. Поэтому при увеличении числа процессоров в компьютере такие программы не начинают выполняться быстрее.

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

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

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

Для того чтобы .можно было эффективно организовать параллельное выполнение рассмотренных сущностей (процессов и потоков), в архитектуру современных про­цессоров включены средства для работы со специальной информационной струк­турой, описывающей ту или иную сущность. Для этого уже на уровне архитектуры микропроцессора используется понятие задача (task). Оно как бы объединяет в себе и обычный процесс, и поток выполнения (тред). Это понятие и поддерживаемая для него на уровне аппаратуры информационная структура позволяют в дальней­шем при разработке операционной системы строить соответствующие дескрипто­ры как для задач, так и для процессов. И отличаться эти дескрипторы будут прежде всего тем, что дескриптор задачи может хранить только контекст приостановлен­ного вычислительного процесса, тогда как дескриптор процесса должен содержать поля, описывающие тем или иным способом ресурсы, выделенные этому процес­су. Для хранения контекста задачи в микропроцессорах с архитектурой i32 имеет­ся специальный сегмент состояния задачи (Task State Segment, TSS). А для отобра­жения информации о процессе используется уже иная информационная структура, однако она включает в себя TSS. Другими словами, сегмент состояния задачи, по­дробно рассматриваемый в разделе «Адресация в 32-разрядных микропроцессо­рах i80x86 при работе в защищенном режиме» главы 4, используется как основа для дескриптора процесса. Таким образом, дескриптор процесса больше по разме­ру, чем TSS, и включает в себя такие традиционные поля, как идентификатор про­цесса, его имя, тип, приоритет и проч.

Каждый поток (в случае использования так называемой «плоской» модели памя­ти — см. раздел «Сегментная, страничная и сегментно-страничная организация памяти» в главе 3) может быть оформлен в виде самостоятельного сегмента, что приводит к тому, что простая (не много поточная) программа будет иметь всего один сегмент кода в виртуальном адресном пространстве.

 

Теперь, если вернуться к уже упомянутому файлу CONFIG.SYS, в котором для опера­ционной системы OS/2 указываются наиболее важные параметры, определяющие ее работу, стоит заметить, что в этом файле строка THREADS=1024 указывает на ко­личество не процессов, а именно задач. И под задачей в данном случае понимается как процесс, так и поток этого процесса.

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

В завершение можно привести несколько советов по использованию потоков вы­полнения при создании приложений, заимствованных из.

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

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

·        Потокам можно назначать разные приоритеты для того, чтобы наименее значи­мые процессы выполнялись в фоновом режиме. Это путь честного разделения ресурсов процессора. Однако необходимо осознать тот факт, что процессор один на всех, а потоков много. Если в вашей программе главная процедура передает нечто для обработки в низкоприоритетный поток, то сама программа становит­ся просто неуправляемой.

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

·        Помните, что память виртуальна. Механизм виртуальной памяти (см. раз­дел «Память и отображения, виртуальное адресное пространство» в главе 3) сле­дит за тем, какая часть виртуального адресного пространства должна находить­ся в оперативной памяти, а какая должна быть сброшена в файл подкачки. Потоки усложняют ситуацию, если они обращаются в одно и то же время к раз­ным адресам виртуального адресного пространства приложения. Это значи­тельно увеличивает нагрузку на систему, особенно при небольшом объеме кэш­памяти. Помните, что реально память не всегда «свободна», как это пишут в информационных окошках «О системе». Всегда отождествляйте доступ к па­мяти с доступом к файлу на диске и создавайте приложение с учетом вышеска­занного.

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

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

 

Основные виды ресурсов

и возможности их разделения

 

Рассмотрим кратко основные виды ресурсов вычислительной системы и способы их разделения (см. рис. 1.5). Прежде всего, одним из важнейших ресурсов являет­ся сам процессор1, точнее — процессорное время. Процессорное время делится попеременно (параллельно). Имеется множество методов раздааения этого ресур­са (см. раздел «Планирование и диспетчеризация процессов и задач»в главе 2). Вторым видом ресурсов вычислительной системы можно считать память. Опера­тивная память может делиться и одновременно (то есть в памяти одновременно может располагаться несколько задач или, по крайней мере, текущих фрагментов, участвующих и вычислениях), и попеременно (в разные моменты оперативная па­мять может предоставляться для разных вычислительных процессов). Память — очень интересный вид ресурса. Дело в том, что в каждый конкретный момент вре­мени процессор при выполнении вычислений обращается к очень ограниченному числу ячеек оперативной памяти. С этой точки зрения желательно память выде­лять для возможно большего числа параллельно исполняемых задач, С другой сто­роны, как правило, чем больше оперативной памяти может быть выделено для конкретного текущего вычислительного процесса, тем лучше будут условия его выполнения. Поэтому проблема эффективного разделения оперативной памяти между параллельно выполняемыми вычислительными процессами является одной из самых актуальных. Достаточно подробно вопросы распределения памяти между параллельно выполняющимися процессами рассмотрены в главе 3. Внешняя память тоже является ресурсом, который часто необходим для выполне­ния вычислений. Когда говорят о внешней памяти (например, памяти на магнит­ных дисках), то собственно память и доступ1 к ней считаются разными видами ресурса. Каждый из этих ресурсов может предоставляться независимо от другого. Но для полноценной работы с внешней памятью необходимо иметь оба этих ре­сурса. Собственно внешняя память может разделяться и одновременно, а вот дос­туп к ней всегда разделяется попеременно.

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

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

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

Повторно используемые программные модули, в свою очередь, могут быть непри­вилегированными, привилегированными и реентерабельными. Все они допуска­ют корректное повторное выполнение программного кода при обращении к нему из другой программы.

Привилегированные программные модули работают в так называемом привилеги­рованном режиме, то есть при отключенной системе прерываний (часто говорят, что прерывания закрыты), когда никакие внешние события не могут нарушить естественный порядок вычислений. Как результат, программный модуль выпол­няется до своего конца, после чего он может быть вновь вызван на исполнение из другой задачи (другого вычислительного процесса). С позиций стороннего наблю­дателя по отношению к вычислительным процессам, которые попеременно (при­чем, возможно, неоднократно) в течение срока своей «жизни» вызывают некото­рый привилегированный программный модуль, такой модуль будет выступать как попеременно разделяемый ресурс. Структура привилегированных программных модулей изображена на рис. 1.8. Здесь в первой секции программного модуля вы­ключается система прерываний. Следовательно, при выполнении вычислений в первой секции ничто не может их прервать, и беспокоиться о промежуточных переменных нет необходимости. В последней секции, напротив, система прерыва­ний включается. Даже если тут же возникнет прерывание и другой процесс запро­сит этот же привилегированный модуль, все равно все вычисления уже выполне­ны и ничто не сможет их испортить.

Отключение прерываний

 

Собственно тело программного модуля

 

Включение прерываний

 

Рис. 1.8. Структура привилегированного программного модуля

 

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 1.9. Структура реентерабельного программного модуля

 

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

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

Кроме реентерабельных программных модулей существуют еще повторно входимые (re-entrance). Этим термином называют программные модули, которые тоже допус­кают свое многократное параллельное использование, но, в отличие от реентерабель­ных, их нельзя прерывать. Повторно входимые программные модули состоят из привилегированных секций, и повторное обращение к ним возможно только после завершения какой-нибудь из таких секций. После выполнения очередной такой при­вилегированной секции управление может быть передано супервизору, который может предоставить возможность выполняться другой задаче, а значит, возможно повторное вхождение в рассматриваемый программный модуль. Другими словами, в повторно входимых программных модулях четко предопределены все допусти­мые (возможные) точки входа. Следует отметить, что повторно входимые программ­ные модули встречаются гораздо чаще реентерабельных (повторно прерываемых). Наконец, имеются и информационные ресурсы, то есть в качестве ресурсов могут выступать данные. Информационные ресурсы могут существовать как в виде пе­ременных, находящихся в оперативной памяти, так и в виде файлов. Если процессы используют данные только для чтения, то такие информационные ресурсы можно разделять. Если же процессы могут изменять информационные ресурсы, то необхо­димо специальным образом организовывать работу с такими данными. Это одна из наиболее сложных проблем.

 

Классификация операционных систем

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

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

Прежде всего, традиционно различают ОС общего и специального назначения. ОС специального назначения, в свою очередь, подразделяются на ОС для носимых микрокомпьютеров и различных встроенных систем, организации и ведения баз данных, решения задач реального времени и т. п. Еще не так давно операционные системы для персональных компьютеров относили к ОС специального назначе­ния. Сегодня современные мультизадачные ОС для персональных компьютеров уже многими относятся к ОС общего назначения, поскольку их можно использо­вать для самых разнообразных целей — так велики их возможности. По режиму обработки задач различают ОС, обеспечивающие однопрограммный и мультипрограммный (мультизадачный) режимы. К однопрограммным ОС отно­сится, например, всем известная, хотя нынче уже практически и не используемая MS DOS. Напомним, что под мультипрограммированием понимается способ орга­низации вычислений, когда на однопроцессорной вычислительной системе созда­ется видимость одновременного выполнения нескольких программ. Любая задер­жка в решении программы (например, для осуществления операций ввода-вывода данных) используется для выполнения других (таких же либо менее важных) про­грамм. Иногда при этом говорят о мультизадачном режиме, причем, вообще гово­ря, термины «мультипрограммный режим» и «мультизадачный режим» — это не синонимы, хотя и близкие понятия. Основное принципиальное отличие этих тер­минов заключается в том, что мультипрограммный режим обеспечивает параллель­ное выполнение нескольких приложений, и при этом программисты, создающие эти программы, не должны заботиться о механизмах организации их  параллель­ной работы (эти функции берет на себя сама ОС; именно она распределяет между выполняющимися приложениями ресурсы вычислительной системы, осуществ­ляет необходимую синхронизацию вычислений и взаимодействие). Мультизадач­ный режим, наоборот, предполагает, что забота о параллельном выполнении и вза­имодействии приложений ложится как раз на прикладных программистов. Хотя в современной технической и тем более научно-популярной литературе об этом различии часто забывают и тем самым вносят некоторую путаницу. Можно, одна­ко, заметить, что современные ОС для персональных компьютеров реализуют и мультипрограммный, и мультизадачный режимы.

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

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

По основному архитектурному принципу операционные системы разделяются на микроядерные и макроядерные (монолитные). В некоторой степени это разделе­ние тоже условно, однако можно в качестве яркого примера микроядерной ОСРВ QNX, тогда как в качестве монолитной можно назвать Windows 95/98 или ОС Linux. Если ядро ОС Windows мы не можем изменить, нам недоступны исходные коды и у нас нет программы для сборки (компиляции) этого ядра, то в случае с Linux мы можем сами собрать то ядро, которое нам необходимо, включить в него те программные модули и драйверы, которые мы считаем целесообразным включить именно в ядро (ведь к ним можно обращаться и из ядра).

Контрольные вопросы и задачи

1.  Что такое операционная система? Перечислите основные функции операци­онных систем.

2.  Что означает термин «авторизация»? Что означает термин «аутентификация»? Какая из этих операций выполняется раньше и почему?

3.  Что такое операционная среда? Какие основные, наиболее известные опера­ционные среды вы можете перечислить?

4.  Что такое прерывание? Какие шаги выполняет система прерываний при воз­никновении запроса на прерывание? Какие бывают прерывания?

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

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

7.  Как можно и как следует толковать процесс — одно из основных понятий опе­рационных систем? Объясните, в чем заключается различие между такими понятиями, как «процесс» и «задача»?

8.   Изобразите диаграмму состояний процесса, поясните все возможные перехо­ды из одного состояния в другое.

9.   Объясните значения терминов «задача», «процесс», «поток выполнения»? Как они между собой соотносятся?

10.  Для чего каждая задача получает соответствующий дескриптор? Какие поля, как правило, содержатся в дескрипторе процесса (задачи)? Что такое «кон­текст задачи»?

11. Объясните понятие ресурса. Почему понятие ресурса является одним из фун­даментальных при рассмотрении операционных систем? Какие виды и типы ресурсов вы знаете?

12.  Как вы считаете, сколько и каких списков дескрипторов задач может быть в си­стеме? От чего должно зависеть это число?

13.  В чем заключается различие между повторно входимыми и реентерабельны­ми программными модулями? Как они реализуются?

14.  Что такое привилегированный программный модуль? Почему нельзя создать мультипрограммную операционную систему, в которой бы не было привиле­гированных программных модулей?

 

 

 

Глава 2. Управление задачами

 

Понятия процесса (process) и потока выполнения (thread) нам уже известны. Мы теперь знаем, в чем здесь имеется сходство, а в чем — существенное различие. Од­нако в данной главе при рассмотрении вопросов распределения процессорного времени мы не всегда будем разделять эти понятия. Дело в том, что по отношению к этому ресурсу — процессорному времени — оба этих понятия практически экви­валенты. Они выступают просто как некоторая работа, для выполнения которой необходимо предоставить центральный процессор. Поэтому мы будем в основном использовать термин задача (task), который является как бы обобщающим. Ведь каждый поток выполнения на самом деле получает статус задачи, и для него созда­ется соответствующий дескриптор. Но мы должны помнить о различиях между дескриптором процесса и дескриптором задачи. Даже если процесс состоит из един­ственного потока, мы говорим о дескрипторе процесса, содержащем информацию, с помощью которой операционная система отслеживает все ресурсы, необходи­мые процессу для его выполнения. Один из основных модулей супервизора опера­ционной системы — диспетчер задач — переводит процессы в одно из состояний в зависимости от того, доступен тот или иной ресурс или не доступен. И посколь­ку в мультизадачной системе любой процесс содержит хотя бы один поток, то по­току (то есть задаче) ставится в соответствие дескриптор задачи, в котором сохра­няется контекст этих вычислений. Сказанное справедливо для мультипрограммных систем, поддерживающих мультизадачный режим. В мультипрограммных систе­мах, не поддерживающих мультизадачность, контекст прерванного процесса хра­нится в дескрипторе этого процесса. Заметим, что повсеместно распространенные системы Windows 9x /NT/2000/XP являются и мультипрограммными, и мульти­задачными. Не случайно начиная с Windows NT и Windows 95 компания Microsoft отказалась от термина «задача» и стала использовать понятия процесса и потока выполнения (треда, нити). Правда, для изложения вопросов диспетчеризации это становится неудобным, ибо здесь чаще используется обобщающее понятие, еще одним доводом в пользу термина «задача» при рассмотрении вопросов ор­ганизации распределения процессорного времени между выполняющимися вы­числениями является аналогичный выбор этой сущности разработчиками процессоров. Именно для отображения этой ситуации и обеспечения дополнитель­ными возможностями системных программистов в решении вопросов распреде­ления процессорного времени они вводят специальные информационные струк­туры и аппаратную поддержку для работы с ними. Во многих современных микропроцессорах, предназначенных для построения на их основе мощных муль­типрограммных и мультизадачных систем, имеются дескрипторы задач. Приме­ром, подтверждающим этот тезис, являются микропроцессоры, совместимые с архитектурой ia32, то есть с 32-разрядными процессорами фирмы Intel. Основ­ные архитектурные особенности этих микропроцессоров, специально прорабо­танные для организации мультизадачных операционных систем, рассматрива­ются достаточно подробно в главе 4. Здесь мы лишь отметим тот факт, что в этих процессорах имеется специальная аппаратная поддержка организации мульти­задачного (и мультипрограммного) режима. Речь идет о сегменте состояния за­дачи (Task State Segment, TSS), который предназначен, прежде всего, для сохра­нения контекста потока или процесса и который легко позволяет организовать и мультипрограммный, и мультизадачный режимы. Не случайно был введен тер­мин «задача», ибо он здесь применим и по отношению к полноценному вычисли­тельному процессу, и по отношению к легковесному процессу (потоку выполне­ния, треду, нити). На самом деле этот аппаратный механизм применяется гораздо реже, чем об этом думали разработчики архитектуры ia32. На практике оказа­лось, что для сохранения контекста потоков эффективнее использовать программ­ные механизмы, хотя они и не обеспечивают такой же надежности, как аппарат­ные.

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

           создание и удаление задач;

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

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

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

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

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

 

Планирование и диспетчеризация

процессов и задач

Когда говорят о диспетчеризации, то всегда в явном или неявном виде подразуме­вают понятие задачи (потока выполнения). Если операционная система не под­держивает механизм потоковых вычислений, то можно заменять понятие задачи понятием процесса. Ко всему прочему, часто понятие задачи используется в таком контексте, что для его трактовки приходится использовать термин «процесс».

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

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

Задача планирования процессов возникла очень давно — в первых пакетных опе­рационных системах при планировании пакетов задач, которые должны были выполняться на компьютере и по возможности бесконфликтно и оптимально использовать его ресурсы. В настоящее время актуальность этой задачи стала меньше, первый план уже очень давно вышли задачи динамического (или краткосрочного) планирования, то есть текущего наиболее эффективного распределения ресурсов, возникающего практически по каждому событию. Задачи динамического планирования стали называть диспетчеризацией. Очевидно, что планирование процессов осуществляется гораздо реже, чем текущее распределение ресурсов меж­ду уже выполняющимися задачами. Основное различие между долгосрочным и краткосрочным планировщиками заключается в частоте их запуска, например: крат­косрочный планировщик может запускаться каждые 30 или 100 мс, долгосрочный — один раз в несколько минут (или чаще; тут многое зависит от общей длительности решения заданий пользователей).

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

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

 

Планирование вычислительных процессов и стратегии планирования

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

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

·        по возможности заканчивать вычисления (вычислительные процессы) в том же самом порядке, в котором они были начаты;

·        отдавать предпочтение более коротким вычислительным задачам;

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

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

На сегодняшний день абсолютное большинство компьютеров — это персональные IBM-совместимые компьютеры, работающие на платформах Windows компании Microsoft. Это однопользовательские диалоговые мультипрограммные и мульти­задачные системы. При создании операционных систем для персональных компь­ютеров разработчики, прежде всего, стараются обеспечить комфортную работу с системой, то есть основные усилия уходят на проработку пользовательского ин­терфейса. Что касается эффективности организации вычислений, то она, видимо, тоже должна оцениваться с этих позиций. Если же считать системы Windows опе­рационными системами общего назначения, что тоже возможно, ибо эти системы повсеместно используют для решения самых разнообразных задач автоматизации, то также следует признать, что принятые в системах Windows стратегии обслужи­вания приводя к достаточно высокой эффективности вычислений. Некоторым даже удается использовать системы Windows NT/2000 для решения задач реаль­ного времени. Однако выбор этих операционных систем для таких задач скорее всего делается либо вследствие некомпетентности, либо из-за невысоких требова­ний ко времени отклика и гарантиям обслуживания со стороны самих систем ре­ального времени, которые реализуются на Windows NT/2000.

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

Например, в Windows 2000 можно открыть окно Свойства системы, перейти на вкладку Дополнительно, щелчком на кнопке Параметры быстродействия открыть од­ноименное окно и с помощью переключателя в разделе Отклик приложений уста­новить режим Оптимизировать быстродействие приложений. Это будет соответство­вать выбору такой стратегии диспетчеризации задач, в соответствии с которой приоритет на получение процессорного времени будут иметь задачи пользователя, а не фоновые служебные вычисления. В предыдущей версии ОС – Windows NT 4.0- для выбора нужной ему стратегии пользователь должен был на вкладке Быстродействие окна Свойства системы установить желаемое значение в поле Ускорение приложения переднего плана. Это ускорение можно сделать максимальным (по умолчанию) а можно его свести к нулю. Последний вариант означал бы, что запущенные пользователем приложения будут иметь одинаковый приоритет. Последнее важно, если пользователь часто запускает сразу по нескольку за­дач, каждая из которых требует длительных вычислений, причем эти приложе­ния часто используют операции ввода-вывода. Например, если нужно обрабо­тать несколько десятков музыкальных или графических файлов, причем каждый файл имеет большие размеры, то выполнение всей этой работы как множества параллельно исполняющихся задач будет завершено за меньшее время, если ука­зать стратегию равенства обслуживания. Должно быть очевидным, что любой другой вариант решения этой задачи потребует больше времени. Например, по­следовательное выполнение задач обработки каждого файла (то есть обработка следующего файла может начинаться только по окончании обработки предыду­щего) приведет к самому длительному варианту. Стратегия предоставления про­цессорного времени в первую очередь текущей задаче пользователя, которая установлена в системах Windows по умолчанию, приведет нас к промежуточно­му (по затратам времени) результату.

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

 

Дисциплины диспетчеризации

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

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

·        приоритет, присвоенный задаче, является величиной постоянной;

·        приоритет изменяется в течение времени решения задачи (динамический прио­ритет).

 

 

 

 

 

 

 

 

 

 

 

Подпись: В порядке очередиПодпись: Случайный выбор процессаПодпись: Циклический алгоритмПодпись: Многоприоритетный циклический алгоритм

Подпись: С относительными
приоритетами
Подпись: С абсолютными приоритетамиПодпись: Адаптивное обслуживаниеПодпись: Приоритет зависит от времени ожиданияПодпись: Приоритет зависит от времени обслуживания

Подпись: ЛинейныеПодпись: ЦиклическиеПодпись: С фиксированным
приоритетом
Подпись: С динамическим
приоритетом

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 2.1. Дисциплины диспетчеризации

 

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

Рассмотрим некоторые основные (наиболее часто используемые) дисциплины диспетчеризации.

Самой простой в реализации является дисциплина FCFS (First Come First Served -первым пришел, первым обслужен), согласно которой задачи обслуживаются «в по­рядке очереди», то есть в порядке их появления. Те задачи, которые были заблокированы в процессе работы (попали в какое-либо ил состояний ожидания, напри­мер из-за операций ввода-вывода), после перехода в состояние готовности вновь ставятся в эту очередь готовности. При этом возможны два варианта. Первый (са­мый простой) — это ставить разблокированную задачу в конец очереди готовых к выполнению задач. Этот вариант применяется чаще всего. Второй вариант за­ключается в том, что диспетчер помещает разблокированную задачу перед теми задачами, которые еще не выполнялись. Другими словами, в этом случае образу­ется две очереди (рис. 2.2): одна очередь образуется из новых задач, а вторая оче­редь — из ранее выполнявшихся, но попавших в состояние ожидания. Такой подход позволяет реализовать стратегию обслуживания «по возможности заканчивать вычисления в порядке их появления». Эта дисциплина обслуживания не требует внешнего вмешательства в ход вычислений, при ней не происходит перераспреде­ления процессорного времени. Про нее можно сказать, что она относится к не вы­тесняющим дисциплинам.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 2.2. Дисциплина диспетчеризации FCFS

 

К достоинствам этой дисциплины прежде всего можно отнести простоту реализа­ции и малые расходы системных ресурсов на формирование очереди задач.

Однако эта дисциплина приводит к тому, что при увеличении загрузки вычисли­тельной системы растет и среднее время ожидания обслуживания, причем короткие задания (требующие небольших затрат машинного времени) вынуждены ожидать столько же, сколько трудоемкие задания. Избежать этого недостатка позволяют дисциплины SJN и SRT. Правило FCFS применяется и в более сложных дисциплинах диспетчеризации. Например, в приоритетных дисциплинах диспетчеризации, если имеется несколько задач с одинаковым приоритетом, которые стоят в очереди гото­вых к выполнению задач, то попадают они в эту очередь с учетом времени. Дисциплина обслуживания SJN (Shortest Job Next — следующим выполняется са­мое короткое задание) требует, чтобы для каждого задания была известна оценка в потребностях машинного времени. Необходимость сообщать операционной сис­теме характеристики задач с описанием потребностей в ресурсах вычислительной системы привела к тому, что были разработаны соответствующие языковые сред­ства. В частности, ныне уже забытый язык JSL (Job Control Language - язык уп­равления заданиями) был одним из наиболее известных. Пользователи вынужде­ны были указывать предполагаемое время выполнения задачи и для того, чтобы они не злоупотребляли возможностью указать заведомо меньшее время выполне­ния (с целью возможности получить результаты раньше других), ввели подсчет реальных потребностей. Диспетчер задач сравнивал заказанное время и время вы­полнения и в случае превышения указанной оценки потребности в данном ресур­се ставил данное задание не в начало, а в конец очереди. Еще в некоторых операци­онных системах в таких случаях использовалась система штрафов, при которой в случае превышения заказанного машинного времени оплата вычислительных ре­сурсов осуществлялась уже по другим расценкам.

 

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

Для устранения этого недостатка и была предложена дисциплина SRT (Shortest Remaining Time) — следующим будет выполняться задание, которому осталось меньше всего выполняться на процессоре.

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

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

Дисциплина обслуживания RR предполагает, что каждая задача получает процес­сорное время порциями или, как говорят, квантами времени (time slice) q. После окончания кванта времени q задача снимается с процессора, и он передается сле­дующей задаче. Снятая задача ставится в конец очереди задач, готовых к выполне­нию. Эту дисциплину обслуживания иллюстрирует рис. 2.3. Для оптимальной ра­боты системы необходимо правильно выбрать закон, по которому кванты времени выделяются задачам.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 2.3. Карусельная дисциплина диспетчеризации

 

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

В некоторых операционных системах есть возможность указывать в явном виде величину кванта времени или диапазон возможных значений, тогда система будет стараться выбирать оптимальное значение сама. Например, в операционной сис­теме OS/2 в файле CONFIG.SYS есть возможность с помощью оператора TIMESLICE указать минимальное и максимальное значения для кванта q. Так, например, стро­ка TIMESLICE=32,256 указывает, что минимальное значение равно 32 мс, а макси­мальное — 256. Если некоторая задача прервана, поскольку израсходован выде­ленный ей квант времени q, то следующий выделенный ей интервал будет увеличен на время, равное одному периоду таймера (около 32 мс), и так до тех пор, пока квант времени не станет равным максимальному значению, указанному в операто­ре TIMESLICE. Этот метод позволяет OS/2 уменьшить накладные расходы на пе­реключение задач в том случае, если несколько задач параллельно выполняют длительные вычисления. Следует заметить, что диспетчеризация задач в этой опе­рационной системе реализована, пожалуй, наилучшим образом с точки зрения ре­акции системы и эффективности использования процессорного времени.

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

Дисциплина диспетчеризации RR — это одна из самых распространенных дисцип­лин. Однако бывают ситуации, когда операционная система не поддерживает в яв­ном виде дисциплину карусельной диспетчеризации. Например, в некоторых опе­рационных системах реального времени используется диспетчер задач, работающий по принципу абсолютных приоритетов (процессор предоставляется задаче с мак­симальным приоритетом, а при равенстве приоритетов он действует по принципу очередности). Другими словами, причиной снятия задачи с выполнения может быть только появление задачи с более высоким приоритетом. Поэтому если нужно организовать обслуживание задач таким образом, чтобы все они получали процессорное время равномерно и равноправно, то системный оператор может сам организовать эту дисциплину. Для этого достаточно всем пользовательским задачам присвоить одинаковые приоритеты и создать одну высокоприоритетную задачу которая не должна ничего делать, но которая, тем не менее, будет по таймеру (через указанные интервалы времени) планироваться на выполнение. Благодаря высокому приоритету этой задачи текущее приложение будет сниматься с выполнения и ставиться в конец очереди, а поскольку этой высокоприоритетной задаче

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

В своей простейшей реализации дисциплина карусельной диспетчеризации пред­полагает, что все задачи имеют одинаковый приоритет. Если же необходимо ввес­ти механизм приоритетного обслуживания, то это, как правило, делается за счет организации нескольких очередей. Процессорное время предоставляется в первую очередь тем задачам, которые стоят в самой привилегированной очереди. Если она пустая, то диспетчер задач начинает просматривать остальные очереди. Именно по такому алгоритму действует диспетчер задач в операционных системах OS/2, Windows 9x, Windows NT/2000/XP и многих других. Отличия в основном заклю­чаются в количестве очередей и в правилах, касающихся перемещения задач из одной очереди в другую.

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

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

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

Итак, диспетчеризация без перераспределения процессорного времени, то есть не вытесняющая (non-preemptive multitasking), или кооперативная, многозадачность (cooperative multitasking), — это такой способ диспетчеризации задач; при кото­ром активная задача выполняется до тех пор, пока она сама, что называется «по собственной инициативе», не отдаст управление диспетчеру задач для того, чтобы тот выбрал из очереди другой, готовый к выполнению процесс или поток. Дисцип­лины обслуживания FCFS, SJN, SRT относятся к не вытесняющим.

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

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

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

Например, в ныне уже забытой операционной среде Windows 3.x нативные 16-раз­рядные приложения этой системы разделяли между собой процессорное время именно таким образом. И именно программисты должны были обеспечивать «дру­жественное» отношение своей программы к другим выполняемым одновременно с ней программам, достаточно часто отдавая управление ядру системы. Крайним проявлением «недружественности» приложения является его зависание, приво­дящее к общему краху системы — прекращению всех вычислений. В системах с вы-тесняющей многозадачностью такие ситуации, как правило, исключены, так как центральный механизм диспетчеризации, во-первых, обеспечивает все задачи про­ворным временем, во-вторых, дает возможность иметь надежные механизмы мониторинга вычислений и, в-третьих, позволяет снять зависшую задачу с выполнения.

Однако распределение функций диспетчеризации между системой и приложени­ями не всегда является недостатком, а при определенных условиях может быть и достоинством, потому что дает возможность разработчику приложений самому планировать распределение процессорного времени наиболее подходящим для данного фиксированного набора задач образом Так как разработчик сам определяет в программе момент времени передачи управления, то при этом исключаются нерациональные прерывания программ в «неудобные» для них мо­менты времени. Кроме того, легко разрешаются проблемы совместного использо­вания данных: задача во время каждой итерации использует их монопольно и уве­рена, что на протяжении этого периода никто другой их не изменит. Примером эффективного применения не вытесняющей многозадачности является сетевая операционная система Novell NetWare, в которой в значительной степени благо­даря этому достигнута высокая скорость выполнения файловых операций. Менее удачным оказалось использование не вытесняющей многозадачности в операци­онной среде Windows 3.x. К счастью, на сегодня эта операционная система уже нигде не применяется, ее с успехом заменила сначала Windows 95, а затем и Win­dows 98. Правда, следует заметить, что при выполнении в этих операционных систе­мах старых 16-разрядных приложений, разработанных в свое время для операци­онной среды Win16 API, создается виртуальная машина, работающая по принципам не вытесняющей многозадачности.

 

Качество диспетчеризации и гарантии обслуживания

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

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

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

Гарантировать обслуживание можно, например, следующими тремя способами.

□ Выделять минимальную долю процессорного времени некоторому классу про­цессов, если по крайней мере один из них готов к исполнению. Например, можно отводить 20 % от каждых 10 мс процессам реального времени, 40 % от каждых 2 с — интерактивным процессам и 10 % от каждых 5 мин — пакетным (фоно­вым) процессам.

□ Выделять минимальную долю процессорного времени некоторому конкретно­му процессу, если он готов к выполнению.

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

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

□ Загрузка центрального процессора (CPU utilization). В большинстве персональ­ных систем средняя загрузка процессора не превышает 2-3 %, доходя в момен­ты выполнения сложных вычислений и до 100 %. В реальных системах, где компьютеры (например, серверы) выполняют очень много работы, загрузка про­цессора колеблется в пределах от 15-40 % (для легко загруженного процессо­ра) до 90-100 % (для тяжело загруженного процессора).

□ Пропускная способность центрального процессора (CPU throughput). Пропус­кная способность процессора может измеряться количеством процессов, кото­рые выполняются в единицу времени.

□ Время оборота (turnaround time). Для некоторых процессов важным критери­ем является полное время выполнения, то есть интервал от момента появления процесса во входной очереди до момента его завершения. Это время названо временем оборота и включает время ожидания во входной очереди, время ожи­дания в очереди готовых процессов, время ожидания в очередях к оборудова­нию, время выполнения в процессоре и время ввода-вывода.

□ Время ожидания (waiting time). Под временем ожидания понимается суммар­ное время нахождения процесса в очереди готовых процессов.

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

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

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

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

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

В случае мультипроцессорных систем применяются следующие методы повыше­ния производительности системы:

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

□ планирование, при котором находящиеся в критической секции задачи не пре­рываются, а активно ожидающие входа в критическую секцию задачи не ста­вятся на выполнение до тех пор, пока вход в секцию не освободится;

□ планирование с учетом так называемых подсказок (hints) программы (во время се выполнения), например, в известной своими новациями ОС Mach имелось два класса таких подсказок: во-первых, указания (разной степени категорично­сти) о снятии текущего процесса с процессора, во-вторых, указания о том про­цессе, который должен быть выбран взамен текущего.

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

 

Диспетчеризация задач с использованием

динамических приоритетов

При выполнении программ, реализующих какие-нибудь задачи контроля и управ­ления (что характерно, прежде всего, для систем реального времени), может слу­читься такая ситуация, когда одна или несколько задач не могут быть реализова­ны (решены) в течение длительного промежутка времени из-за возросшей нагрузки в вычислительной системе. Потери, связанные с невыполнением таких задач, могут оказаться больше, чем потери от невыполнения программ с более высоким прио­ритетом. При этом оказывается целесообразным временно изменить приоритет «аварийных» задач (для которых истекает отпущенное для них время обработки). После выполнения этих задач их приоритет восстанавливается. Поэтому почти в лю­бой операционной системе реального времени (ОС РВ) имеются средства для дина­мического изменения приоритета (dynamic priority variation) задачи. Есть такие средства и во многих операционных системах, которые не относятся к классу ОС РВ. Рассмотрим, например, как реализован механизм динамических приоритетов в опе­рационной системе UNIX, которая, как известно, не относится к ОС РВ. Операционные системы класса UNIX относятся к мультитерминальньм диалоговым системам. Основная стратегия обслуживания, применяемая в UNIX-системах, — это равенство в обслуживании и обеспечение приемлемого времени реакции системы. Реализует­ся эта стратегия за счет дисциплины диспетчеризации RR с несколькими очередями и механизма динамических приоритетов. Приоритет процесса вычисляется следую­щим образом. Во-первых, в вычислении участвуют значения двух полей деск­риптора процесса— p_nice и p_cpu. Первое из них назначается пользователем явно или формируется по умолчанию с помощью системы программирования. Второе поле формируется диспетчером задач (планировщиком разделения времени) и на­зывается системной составляющей или текущим приоритетом. Другими словами, каждый процесс имеет два атрибута приоритета. С учетом этого приоритета и рас­пределяется между исполняющимися задачами процессорное время: текущий при­оритет, на основании которого происходит планирование, и заказанный относи­тельный приоритет (называемый nice number, или просто nice).

Схема нумерации текущих приоритетов различна для различных версий UNIX. Например, более высокому значению текущего приоритета может соответствовать более низкий фактический приоритет планирования. Разделение между приори­тетами режима ядра и задачи также зависит от версии. Рассмотрим частный слу­чай, когда текущий приоритет процесса варьируется в диапазоне от 0 (низкий при­оритет) до 127 (наивысший приоритет). Процессы, выполняющиеся в режиме задачи, имеют более низкий приоритет, чем в режиме ядра. Для режима задачи приоритет меняется в диапазоне 0-65, для режима ядра — 66-95 (системный диа­пазон). Процессы, приоритеты которых лежат в диапазоне 96-127, являются про­цессами с фиксированным приоритетом, не изменяемым операционной системой, и предназначены для поддержки приложений реального времени.

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

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

Текущий приоритет процесса в режиме задачи p_priuser, как мы только что отмечали, зависит от значения относительного приоритета p_nice и степени использова­ния вычислительных ресурсов p_cpu:

p_priuser = a x p_nice – b x p_cpu

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

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

Возможно использование следующей формулы:

p_cpu - p_cpu/2

В этом правиле проявляется недостаток нивелирования приоритетов при повы­шении загрузки системы. Происходит это потому, что в таком случае каждый про­цесс получает незначительный объем вычислительных ресурсов и, следовательно, имеет малую составляющую p_cpu, которая еще более уменьшается благодаря фор­муле пересчета величины p_cpu. В результате загрузка процессора перестает ока­зывать заметное влияние на приоритет, и низкоприоритетные процессы (то есть процессы с высоким значением nice number) практически «отлучаются» от вычис­лительных ресурсов системы.

В некоторых версиях UNIX для пересчета значения p_cpu используется другая формула:

p_cpu = p_cpu х (2 х load)/(2 x load + 1)

Здесь параметр load равен среднему числу процессов, находившихся в очереди на выполнение за последнюю секунду, и характеризует среднюю загрузку системы за этот период времени. Этот алгоритм позволяет частично избавиться от недостатка планирования по формуле p_cpu = p_cpu/2, поскольку при значительной загрузке системы уменьшение p_cpu при пересчете будет происходить медленнее.

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

Аналогичные механизмы имеют место и в таких операционных системах, как OS/2 или Windows NT/2000/XP. Правда, алгоритмы изменения приоритета задач в этих системах иные. Например, в Windows NT/2000/XP каждый поток выполнения имеет базовый уровень приоритета, который лежит в диапазоне от двух уровней ниже базового приоритета процесса, его породившего, до двух уровней выше этого приоритета, как показано на рис. 2.4. Базовый приоритет процесса определяет, сколь сильно могут различаться приоритеты потоков этого процесса и как они соотно­сятся с приоритетами потоков других процессов. Поток наследует этот базовый приоритет и может изменять его так, чтобы он стал немного больше или немного меньше. В результате получается приоритет планирования, с которым поток и на­чинает исполняться. В процессе исполнения потока его приоритет может откло­няться от базового.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 2.4. Схема динамического изменения приоритетов

в Windows NT/2000/XP

 

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

Для определения порядка выполнения потоков диспетчер задач использует систе­му приоритетов, направляя на выполнение задачи с высоким приоритетом раньше задач с низким приоритетом. Система прекращает исполнение, или вытесняет (preempts), текущий поток, если становится готовым к выполнению другой поток с более высоким приоритетом.

Имеется группа очередей — по одной для каждого приоритета. В операционных системах Windows NT/2000/XP используется один и тот же диспетчер задач. Он поддерживает З2 уровня приоритета. Задачи делятся на два класса: реального времени и переменного приоритета. Задачи реального времени, имеющие приоритеты от 6 До 31, — это высокоприоритетные потоки, используемые программами, критическими по времени выполнения, то есть требующими немедленного вни­мания системы (по терминологии Microsoft).

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

Большинство задач в системе относятся к классу переменного приоритета с уров­нями приоритета (номером очереди) от 1 до 15. Эти очереди используются зада­чами с переменным приоритетом (variable priority), так как диспетчер задач для оптимизации отклика системы корректирует их приоритеты по мере выполне­ния. Диспетчер приостанавливает исполнение текущей задачи, после того как та израсходует свой квант времени. При этом если прерванная задача — это поток переменного приоритета, то диспетчер задач понижает приоритет этого потока выполнения на единицу и перемещает в другую очередь. Таким образом, прио­ритет задачи, выполняющей много вычислений, постепенно понижается (до зна­чения его базового приоритета). С другой стороны, диспетчер повышает при­оритет задачи после ее освобождения из состояния ожидания. Обычно добавка к приоритету задачи определяется кодом исполнительной системы, находя­щимся вне ядра операционной системы, однако величина этой добавки зависит от типа события, которого ожидала заблокированная задача. Так, например, поток, ожидавший ввода очередного байта с клавиатуры, получает большую добавку к значению своего приоритета, чем поток ввода-вывода, работавший с дисковым накопителем. Однако в любом случае значение приоритета не мо­жет достигнуть 16.

В операционной системе OS/2 схема динамической приоритетной диспетчериза­ции несколько иная, хоть и похожа. В OS/2 также имеется четыре класса задач. И для каждого класса задач имеется своя группа приоритетов с интервалом значе­ний от 0 до 31. Итого, 128 различных уровней и, соответственно, 128 возможных очередей готовых к выполнению задач (потоков).

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

 

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

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

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

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

OS/2 самостоятельно изменяет приоритет выполняющихся программ независимо от уровня, установленного самим приложением. Этот механизм называется повы­шением приоритета (priority boost). Операционная система изменяет приоритет задачи в трех случаях.

□ Повышение приоритета активной задачи (foreground boost). Приоритет задачи автоматически повышается, когда она становится активной. Это снижает вре­мя реакции активного приложения на действия пользователя по сравнению с фоновыми программами.

□ Повышение приоритета ввода-вывода (Input/Output boost). По завершении операции ввода-вывода задача получает самый высокий уровень приоритета ее класса. Таким образом обеспечивается завершение всех незаконченных опера­ций ввода-вывода.

□ Повышение приоритета «забытой» задачи (starvation boost). Если задача не по­лучает управление в течение достаточно долгого времени (этот промежуток вре­мени задает оператор MAXWAIT в файле CONFIG.SYS), диспетчер задач OS/2 вре­менно присваивает ей уровень приоритета, не превышающий критический. В результате переключение на такую «забытую» программу происходит быст­рее. После выполнения приложения в течение одного кванта времени его приоритет вновь снижается до остаточного. В сильно загруженных системах этот механизм позволяет программам с остаточным приоритетом работать хотя бы в краткие интервалы времени. В противном случае они вообще никогда бы не получили управление. Если нет необходимости использовать метод динамического изменения приори­тета, то с помощью оператора PRIOPITY = ABSOLUTE в файле CONFIG.SYS можно ввести дисциплину абсолютных приоритетов; по умолчанию оператор PRIOPITY имеет зна­чение DYNAMIC.

 

 

Контрольные вопросы и задачи

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

2.            В чем заключается основное различие между планированием процессов и дис­петчеризацией задач?

3.            Что такое стратегия обслуживания? Перечислите известные вам стратегии об­служивания.

4.            Какие дисциплины диспетчеризации задач вы знаете? Поясните их основные идеи, перечислите достоинства и недостатки.

5.            Расскажите, какие дисциплины диспетчеризации следует отнести к вытесняю­щим, а какие — к не вытесняющим.

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

7.            Что такое «гарантия обслуживания»? Как ее можно реализовать?

8.            Опишите механизм динамической диспетчеризации, реализованный в UNIX-системах.

9.            Сравните механизмы диспетчеризации задач в операционных системах Windows NT и OS/2. В чем они похожи друг на друга и в чем заключаются основные различия?

 

 

 

Глава 3. Управление памятью в операционных системах

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

Память и отображения, виртуальное адресное пространство

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 3.1. Память и отображения

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

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

Если рассматривать общую схему двухэтапного отображения адресов, то с пози­ции соотношения объемов упомянутых адресных пространств можно отметить наличие следующих трех ситуаций:

       объем виртуального адресного пространства программы V, меньше объема фи­зической памяти Vp (Vv < Vp);

       объем виртуального адресного пространства программы Vv равен объему фи­зической памяти Vp (Vv = Vp);

    объем виртуального адресного пространства программы Vv больше      

      объема фи­зической памяти Vp (Vv > Vp).

Первая ситуация (Vv< Vp) ныне практически не встречается, но, тем не менее, это реальное соотношение. Скажем, не так давно 16-разрядные мини-ЭВМ имели систе­му команд, в которых пользователи-программисты могли адресовать до 216 = 64 Кбайт адресов (обычно в качестве адресуемой единицы выступала ячейка памяти разме­ром с байт). А физически старшие модели этих мини-ЭВМ могли иметь объем опе­ративной памяти в несколько мегабайтов. Обращение к памяти столь большого объема осуществлялось с помощью специальных регистров, содержимое которых складывалось с адресом операнда (или команды), извлекаемым из поля операнда или указателя команды (и/или определяемым по значению поля операнда или ука­зателя команды). Соответствующие значения в эти специальные регистры, высту­пающие как базовое смещение в памяти, заносила операционная система. Для од­ной задачи в регистр заносилось одно значение, а для второй (третьей, четвертой и т. д.) задачи, размещаемой одновременно с первой, но в другой области памяти, заносилось, соответственно, другое значение. Вся физическая память таким обра­зом разбивалась на разделы объемом по 64 Кбайт, и на каждый такой раздел осуще­ствлялось отображение своего виртуального адресного пространства. Вторая ситуация (Vv - Vp) встречается очень часто, особенно характерна она была для недорогих вычислительных комплексов. Для этого случая имеется большое количество методов распределения оперативной памяти.

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

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

Общие принципы управления памятью

в однопрограммных операционных системах

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

□ область, занимаемая операционной системой;

□ область, в которой размещается исполняемая задача; □ незанятая ничем (свободная) область памяти.

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

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

Если есть необходимость создать программу, логическое адресное пространство которой должно быть больше, чем свободная область памяти, или даже больше, чем весь возможный объем оперативной памяти, то используется распределение с перекрытием — так называемые оверлейные структуры (от overlay — перекры­тие, расположение поверх чего-то). Этот метод распределения предполагает, что вся программа может быть разбита на части — сегменты. Каждая оверлейная про­грамма имеет одну главную (main) часть и несколько сегментов (segments), при­чем в памяти машины одновременно могут находиться только ее главная часть и один или несколько не перекрывающихся сегментов.

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

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

Распределение оперативной памяти в MS DOS

Как известно, MS DOS — это однопрограммная операционная система для персо­нального компьютера типа IBM PC. В ней, конечно, можно организовать запуск резидентных, или TSR-задач, в результате которого в памяти будет находиться не одна программа, но в целом система MS DOS предназначена для выполнения толь­ко одного вычислительного процесса. Поэтому распределение памяти в ней по­строено по схеме простого непрерывного распределения. Система поддерживает механизм распределения памяти с перекрытием (оверлейные структуры). Как известно, в IBM PC использовался 16-разрядный микропроцессор i8088, который за счет введения сегментного способа адресации позволял указывать адрес ячейки памяти в пространстве объемом до 1 Мбайт. В последующих пер­сональных компьютерах (IBM PC AT, AT386 и др.) было принято решение под­держивать совместимость с первыми, полому при работе в DOS прежде всего рассматривают первый мегабайт. Вся эта память разделялась на несколько об­ластей, что иллюстрирует рис. 3.2. На этом рисунке показано, что памяти мо­жет быть и больше, чем 1 Мбайт, но более подробное рассмотрение этого во­проса мы здесь опустим, отослав желающих изучить данную тему глубже к монографии.

Если не вдаваться в детали, можно сказать, что в состав MS DOS входят следую­щие основные компоненты.

Подсистема BIOS (Base Input-Output System — базовая подсистема ввода-вы­вода), включающая в себя помимо программы POST (Power On Self Test —самотестирование при включении компьютера) программные модули обработки прерываний, с помощью которых можно управлять основными контроллерами на материнской плате компьютера и устройствами ввода-вывода. Эти модули часто называют обработчиками прерываний. По своей функциональной сути они представляют собой драйверы. BIOS располагается в постоянном запоми­нающем устройстве компьютера. В конечном итоге почти все остальные модули MS DOS обращаются к BIOS. Если и не напрямую, то через модули более высокого уровня иерархии.

Модуль расширения BIOS — файл I0.SYS (в других DOS-системах он может называться иначе, например _BIO.COM).

Основной, или базовый, модуль обработки прерываний DOS — файл MSDOS.SYS.
Именно этот модуль в основном реализует работу с файловой системой.

  Командный процессор (интерпретатор команд) — файл COMMAND.COM.

       Утилиты и драйверы, расширяющие возможности системы.

       Программа загрузки MS DOS — загрузочная запись (Boot Record, BR), распо­ложенная на дискете или на жестком диске (подробнее о загрузочной записи и о других загрузчиках см. главу 6).

Вся память в соответствии с архитектурой IBM PC условно может быть разбита на следующие три части.

   В самых младших адресах памяти (первые 1024 ячейки) размещается таблица векторов прерывания (см. раздел «Система прерываний 32-разрядных микро­процессоров i80x86» в главе 4). Это связано с аппаратной реализацией процес­сора i8088. В последующих процессорах (начиная с i80286) адрес таблицы пре­рываний определяется через содержимое соответствующего регистра, но для обеспечения полной совместимости с первым процессором при включении или аппаратном сбросе в этот регистр заносятся нули. При желании, однако, в слу­чае использования современных микропроцессоров i80x86 вектора прерыва­ний можно размещать и в других областях.

 

 

0000-003FF          1 Кбайт

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

00400-005FF       512 байт

Глобальные переменные BIOS; глобальные переменные DOS

В ранних версиях здесь располагались глобальные

переменные интерпретатора

Бейсик

00600-0А000

 

 

 

 

35-60Кбайт

Модуль IO. SYS; Модуль MSDOS. SYS:

- обслуживающие функции;

- буферы, рабочие

и управляющие области;

- устанавливаемые драйверы;

Резидентная часть

COMMAND. COM:

- обработка программных прерываний;

- системная программа загрузки;

- программа загрузки транзитной
части COMMAND. COM

 

 

 

Размер этой области зависит от версии MSDOS и, главное, от конфигурационного файла CONFIG. SYS

 

 

 

 

580Кбайт

Область памяти для выполнения программ пользователя и утилит MS DOS. В эту область попадают программы типа *.СОМ и *.ЕХЕ

 

 

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

транзитную область

COMMAND. COM

 

Область расположения стека исполняющейся программы

Стек «растет» снизу вверх

18 Кбайт

Транзитная часть командного процессора COMMAND. COM

Собственно командный интерпретатор

А0000-С7FFF

160 Кбайт

Видеопамять. Область и размер используемого видеобуфера зависят от текущего режима

При работе в текстовом режиме область памяти A0000-B0000 свободна и может быть использована в программе

С8000-Е0000       96 Кбайт

Зарезервировано для расширения BIOS

 

F0000-FFFF

64Кбайт

Область ROM BIOS (System BIOS)

Обычно объем этой области равен 32 Кбайт, но может достигать и 128 Кбайт, занимая младшие адреса

Более 100000

High Memory Area.

 

При наличии драйвера HIMEM. SYS здесь можно расположить основные MS DOS, освобождая тем самым область основной памяти в первом мегабайте системные файлы

 

 

 

 

 

Может использоваться при наличии специальных драйверов. Используются спецификации XMS и EMS

Рис. 3.2. Распределение оперативной памяти в MS DOS

 

□ Вторая часть памяти отводится для программных модулей самой системы MS DOSЬ и для программ пользователя. Эту область памяти мы рассмотрим чуть позже, здесь только заметим, что она называется основной, или стандартной, памятью (conventional memory).

□ Наконец, третья часть адресного пространства отведена для постоянных запо­минающих устройств и функционирования некоторых устройств ввода-выво­да. Эта область памяти получила название UMA (Upper Memory Area — об­ласть памяти, адрес которой выше основной).

В младших адресах основной памяти размещается то, что можно условно назвать ядром этой операционной системы — системные переменные, основные программные модули, блоки данных для буферизации операций ввода-вывода. Для управления устройствами, драйверы которых не входят в базовую подсистему ввода-вывода, загружаются так называемые загружаемые, или устанавливаемые, драйверы. Перечень устанавливаемых драйверов определяется специальным конфи­гурационным файлом CONFIG.SYS. После загрузки расширения BIOS — файла IO.SYSпоследний (загрузив модуль MSDOS.SYS) считывает файл CONFIG.SYS и уже в соот­ветствии с ним подгружает в память необходимые драйверы. Кстати, в конфи­гурационном файле CONFIG.SYS могут иметься операторы, указывающие на количество буферов, отводимых для ускорения операций ввода-вывода, и на количество файлов, которые могут обрабатываться (для работы с файлами необходимо зарезервировать место в памяти для хранения управляющих структур, с помощью которых выполняются операции с записями файла). В случае использования микропроцессоров i80x86 и наличия в памяти драйвера HIMEM.SYS модули I0.SYS и MSDOS.SYS могут быть размещены за пределами первого мегабайта в области, которая получила название HMA (High Memory Area — область памяти с большими адресами).

Память с адресами, большими чем 10FFFFh, может быть использована в DOS-программах при выполнении их на микропроцессорах, имеющих такую возможность (например, микропроцессор i80286 имел 24-разрядную шину адреса, а i80386 — уже 32-разрядную). Но для этого с помощью специальных драйверов необходимо переключать процессор в другой режим работы, при котором он сможет использовать адреса выше 10FFFFh. Широкое распространение получили две основные спецификации: XMS (Extended Memory Specification) и EMS (Expanded Memory Specification). Последние годы система MS DOS практически перестала применяться. Теперь ее используют в основном для запуска некоторых утилит, с помощью которых подготавливают дисковые устройства, или для установки других операционных систем. И поскольку основным утилитам, необходимым для обслуживания персонального компьютера, спецификации EMS и XMS, как правило, не нужны, мы не будем здесь их рассматривать.

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

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

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

 

 

Распределение памяти статическими и

динамическими разделами

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

Начнем с методов неразрывного распределения памяти. Самая простая схема рас­пределения памяти между несколькими задачами предполагает, что память, не за­нятая ядром операционной системы, может быть разбита на несколько непрерыв­ных частей — разделов (partitions, regions). Разделы характеризуются именем, типом, границами (как правило, указываются начало раздела и его длина).

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

Разделы с фиксированными границами

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


      

 

 

 

Рис. 3.3. Распределение памяти разделами с фиксированными границами

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

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

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

·        выделять раздел ровно такого объема, который нужен под текущую задачу;

·        размещать задачу не в одной непрерывной области памяти, а в нескольких об­ластях.

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

Разделы с подвижными границами

Чтобы избавиться от фрагментации, можно попробовать размещать в оператив­ной памяти задачи плотно, одну за другой, выделяя ровно столько памяти, сколь­ко задача требует. Одной из первых операционных систем, в которой был реализо­ван такой способ распределения памяти, была OS MVT (Multiprogramming with a Variable number of Tasks — мультипрограммирование с переменным числом за­дач). В этой операционной системе специальный планировщик (диспетчер памя­ти) ведет список адресов свободной оперативной памяти. При появлении новой задачи диспетчер памяти просматривает этот список и выделяет для задачи раз­дел, объем которой либо равен необходимому, либо чуть больше, если память вы­деляется не ячейками, а некими дискретными единицами. При этом модифициру­ется список свободных областей памяти. При освобождении раздела диспетчер памяти пытается объединить освобождающийся раздел с одним из свободных уча­стков, если таковой является смежным.

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

·        первый подходящий участок;

·        самый подходящий участок;

·        самый неподходящий участок.

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

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

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

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

Сегментная, страничная

и сегментно-страничная организация памяти

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

 

Сегментный способ организации виртуальной памяти

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

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

Таким образом, виртуальный адрес для этого способа будет состоять из двух по­лей — номера сегмента и смещения относительно начала сегмента. Соответствую­щая иллюстрация приведена на рис. 3.4 для случая обращения к ячейке, виртуаль­ный адрес которой равен сегменту с номером 11 со смещением от начала этого сегмента, равным 612. Как мы видим, операционная система разместила данный сегмент в памяти, начиная с ячейки с номером 19700.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 3.4. Сегментный способ организации виртуальной памяти

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

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

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

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

При поиске свободного места используется одна из вышеперечисленных дисцип­лин работы диспетчера памяти (применяются правила «первого подходящего» и «самого неподходящего» фрагментов). Если свободного фрагмента памяти дос­таточного объема нет, но, тем не менее, сумма этих свободных фрагментов превы­шает требования по памяти для нового сегмента, то в принципе может быть при­менено «уплотнение памяти», о котором мы уже говорили в подразделе «Разделы с фиксированными границами» раздела «Распределение памяти статическими и динамическими разделами».

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

       правило FIFO (First In First Out - первый пришедший первым и выбывает);

       правило LRU (Least Recently Used - дольше других неиспользуемый);

       правило LFU (Least Frequently Used — реже других используемый);

       случайный (random) выбор сегмента.

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

В алгоритме FIFO с каждым сегментом связывается очередность его размещения в памяти. Для замещения выбирается сегмент, первым попавший в память. Каж­дый вновь размещаемый в памяти сегмент добавляется в хвост этой очереди. Ал­горитм учитывает только время нахождения сегмента в памяти, но не учитывает фактическое использование сегментов. Например, первые загруженные сегменты программы могут содержать переменные, требующиеся на протяжении всей ее ра­боты. Это приводит к немедленному возвращению к только что замещенному сег­менту.

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

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

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

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

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

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

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

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

Примером использования сегментного способа организации виртуальной памяти является операционная система OS/2 первого поколения, которая была создана для персональных компьютеров на базе процессора i80286. В этой операционной системе в полной мере использованы аппаратные средства микропроцессора, ко­торый специально проектировался для поддержки сегментного способа распреде­ления памяти.

OS/2 v.l поддерживала распределение памяти, при котором выделялись сегмен­ты программы и сегменты данных. Система позволяла работать как с именованны­ми, так и с неименованными сегментами. Имена разделяемых сегментов данных имели ту же форму, что и имена файлов. Процессы получали доступ к именован­ным разделяемым сегментам, используя их имена в специальных системных вызо­вах. Операционная система OS/2 v. 1 допускала разделение программных сегментов приложений и подсистем, а также глобальных сегментов данных подсистем. Вообще, вся концепция системы OS/2 была построена на понятии разделения памяти: процессы почти всегда разделяют сегменты с другими процессами. В этом состояло существенное отличие системы OS/2 от систем типа UNIX, которые обычно разделяют только реентерабельные программные модули между процес­сами.

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

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

Механизм перекачки сегментов использовал файловую систему для выгрузки данных из физической памяти и обратно. Ввиду того что перекачка и компрессия вли­яли на производительность системы в целом, пользователь мог сконфигурировать систему так, чтобы эти функции не выполнялись. Было организовано в OS/2 и динамическое присоединение обслуживающих про­грамм. Программы OS/2 используют команды удаленного вызова. Ссылки, гене­рируемые этими вызовами, определяются в момент загрузки самой программы или ее сегментов. Такое отсроченное определение ссылок называется динамическим присоединением. Загрузочный формат модуля OS/2 представляет собой расшире­ние формата загрузочного модуля DOS. Он был расширен, чтобы поддерживать необходимое окружение для свопинга сегментов с динамическим присоединени­ем. Динамическое присоединение уменьшает объем памяти для программ в OS/2, одновременно делая возможными перемещения подсистем и обслуживающих про­грамм без необходимости повторного редактирования адресных ссылок к приклад­ным программам.

 

Страничный способ организации

виртуальной памяти

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

Разбиение всей оперативной памяти на страницы одинаковой величины, причем кратной степени двойки, приводит к тому, что вместо одномерного адресного про­странства памяти можно говорить о двухмерном. Первая координата адресного пространства — это номер страницы, вторая координата — номер ячейки внутри выбранной страницы (его называют индексом). Таким образом, физический адрес определяется парой (Рр, i), а виртуальный адрес — парой (Pv, i), где Рv — номер виртуальной страницы, Рр — номер физической страницы, i — индекс ячейки внутри страницы. Количество битов, отводимое под индекс, определяет размер страницы, а количество битов, отводимое под номер виртуальной страницы, — объем потен­циально доступной для программы виртуальной памяти. Отображение, осуществ­ляемое системой во время исполнения, сводится к отображению Pv в Рр и припи­сыванию к полученному значению битов адреса, задаваемых величиной i. При этом нет необходимости ограничивать число виртуальных страниц числом физических, го есть не поместившиеся страницы можно размещать во внешней памяти, которая в данном случае служит расширением оперативной.

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

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

·        только чтение;

·        чтение и запись;

·        только выполнение.

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

При обращении к виртуальной странице, не оказавшейся в данный момент в опера­тивной памяти, возникает прерывание, и управление передается диспетчеру памя­ти, который должен найти свободное место. Обычно предоставляется первая же сво­бодная страница. Если свободной физической страницы нет, то диспетчер памяти по одной из вышеупомянутых дисциплин замещения (LRU, LFU, FIFO, случайный доступ) определит страницу, подлежащую расформированию или сохранению во внешней памяти. На ее месте он разместит новую виртуальную страницу, к которой было обращение из задачи, но которой не оказалось в оперативной памяти.

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 3.5. Страничный способ организации виртуальной памяти

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

Для абсолютного большинства современных операционных систем характерна дисциплина замещения страниц LRU как самая эффективная. Так, именно эта дисциплина используется в OS/2 и в Linux. Однако в операционных системах Windows NT/2000/XP разработчики, желая сделать их максимально независимы­ми от аппаратных возможностей процессора, отказались от этой дисциплины и при­менили правило FIFO. А для того чтобы хоть как-то компенсировать неэффектив­ность правила FIFO, была введена «буферизация» тех страниц, которые должны быть записаны в файл подкачки на диск1 или просто расформированы. Принцип буферизации прост. Прежде чем замещаемая страница действительно окажется во внешней памяти или просто расформированной, она помечается как кандидат на выгрузку. Если в следующий раз произойдет обращение к странице, находящейся в таком «буфере», то страница никуда не выгружается и уходит в конец списка FIFO. В противном случае страница действительно выгружается, а на ее место в «буфер» попадает следующий «кандидат». Величина такого «буфера» не может быть большой, поэтому эффективность страничной реализации памяти в Windows NT/2000/XP намного ниже, чем в других операционных системах, и явление пробуксовки начинается даже при существенно большем объеме оперативной па­мяти.

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

Как и в случае с сегментным способом организации виртуальной памяти, странич­ный механизм приводит к тому, что без специальных аппаратных средств он суще­ственно замедляет работу вычислительной системы. Поэтому обычно использует­ся кэширование страничных дескрипторов. Наиболее эффективным механизмом кэширования является ассоциативный кэш. Именно такой ассоциативный кэш и создан в 32-разрядных микропроцессорах i80x86. Начиная с i80386, который под­держивает страничный способ распределения памяти, в этих микропроцессорах имеется кэш на 32 страничных дескриптора. Поскольку размер страницы в этих микропроцессорах равен 4 Кбайт, возможно быстрое обращение к памяти разме­ром 128 Кбайт.

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

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

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

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

 

Сегментно-страничный способ организации

виртуальной памяти

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Рис. 3.6. Сегментно-страничный способ

организации виртуальной памяти

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

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

Контрольные вопросы и задачи

1.            Что такое «виртуальный адрес», «виртуальное адресное пространство»? Чем (в общем случае) определяется максимально возможный объем виртуального адресного пространства программы?

2.            Имеются л и виртуальные адреса в программах, написанных для работы в среде DOS? Приведите примеры абсолютной двоичной программы для таких опера­ционных систем, как MS DOS и Windows NT/2000/XP.

3.            Изложите способ распределения памяти в MS DOS.

4.            Что дает использование оверлеев при разработке DOS-приложений?

5.            Объясните и сравните алгоритмы «первый подходящий», «самый подходящий» и «самый неподходящий», используемые при поиске и выделении фрагмента памяти.

6.            Что такое «фрагментация памяти»? Какой метод распределения памяти по­зволяет добиться минимальной фрагментации и почему?

7.            Что такое «уплотнение памяти»? Когда оно применяется?

8.            Объясните сегментный способ организации виртуальной памяти. Что пред­ставляет собой (в общем случае) дескриптор сегмента?

9.            Что представляет собой динамическое присоединение программ? Что оно даст?

10.    Сравните сегментный и страничный способы организации виртуальной па­мяти. Перечислите достоинства и недостатки каждого.

11.    Какие дисциплины применяются для решения задачи замещения страниц? Какие из них являются наиболее эффективными и как они реализуются?

12.    Что такое «рабочее множество»? Что позволяет разрешить реализация этого понятия?

13.    В каких случаях возникает «пробуксовка»? Почему системы Windows NT/ 2000/ХР требуют для своей нормальной работы существенно большего объ­ема оперативной памяти?

 

 

 

 

 

 

 

 

 

Глава 4. Особенности архитектуры

микропроцессоров i80x86 для организации

мультипрограммных операционных систем

 

В рамках данной книги мы, естественно, не будем рассматривать все многообразие современных 32-разрядных микропроцессоров, используемых в персональных компьютерах и иных вычислительных системах, а ограничимся рассмотрением только архитектурных, а не технических характеристик микропроцессоров, и под обозначением i80x86 будем понимать любые 32-разрядные микропроцессоры, име­ющие основной набор команд такой же, как и в первом 32-разрядном микропро­цессоре Intel 80386, и те же архитектурные решения, что и в микропроцессорах фирмы Intel. Нас не будут интересовать новые наборы команд типа ММХ или SSE, не будем мы касаться и архитектурных особенностей микропроцессоров, повыша­ющих их производительность. Мы опишем только те механизмы, которые позво­ляют организовать мультипрограммный и мультизадачный режимы, виртуальную память, обеспечить надежные вычисления.

 

Реальный и защищенный режимы

работы процессора

Широко известно, что первым микропроцессором, на базе которого был создан персональный компьютер IBM PC, был Intel 8088. Этот микропроцессор отличал­ся от первого 16-разрядного микропроцессора фирмы Intel (микропроцессора 8086), прежде всего, тем, что у него была 8-разрядная шина данных, а не 16-разряд­ная (как у 8086). Оба этих микропроцессора предназначались для создания вычислительных устройств, работающих в однозадачном режиме, то есть специаль­ных аппаратных средств для поддержки надежных и эффективных мультипрог­раммных операционных систем в них не было.

Однако к тому времени, когда разработчики осознали необходимость включения специальной аппаратной поддержки мультипрограммных вычислений, уже было создано очень много программных продуктов. Поэтому для совместимости с пер­выми компьютерами в последующих версиях микропроцессоров была реализова­на возможность использовать их в двух режимах: реальном (real mode) — так на­звали режим работы первых 16-разрядных микропроцессоров — и защищенном (protected mode), означающем, что параллельные вычисления могут быть защи­щены аппаратно-программными механизмами.

Подробно рассматривать архитектуру первых 16-разрядных микропроцессоров i8086/i8088 мы не будем, поскольку этот материал должен изучаться в других дисциплинах. Итак, мы исходим из того, что читатель знаком с архитектурой про­цессора i8086/i8088 и с программированием на ассемблере для этих 16-разряд­ных процессоров Intel. Для тех же, кто с ней незнаком, можно рекомендовать, например, такие книги, как и многие другие. Однако мы напомним, что в этих микропроцессорах (а значит, и в остальных микропроцессорах семей­ства i80x86 при работе их в реальном режиме) обращение к памяти с возможным адресным пространством в 1 Мбайт осуществляется посредством механизма сег­ментной адресации (рис. 4.1). Этот механизм был использован для того, чтобы увеличить с 16 до 20 количество разрядов, участвующих в формировании адреса ячейки памяти, по которому идет обращение, и тем самым увеличить доступный объем памяти.

 

 

 

 

 

 

 

 


Рис. 4.1. Схема определения физического адреса для процессора 8086

 

Для конкретности будем рассматривать определение адреса команд, хотя для адресации операндов используется аналогичный механизм, только участвуют в этом случае другие сегментные регистры. Напомним, что для определения физическо­го адреса команды содержимое регистра сегмента кода (Code Segment, CS) умножается на 16 за счет добавления справа (к младшим битам) четырех нулей, после го к полученному значению прибавляется содержимое регистра указателя команд (Instruction Pointer, IP). Получается 20-разрядное значение, которое и по­зволяет указать любой байт из 2020.

В защищенном режиме работы определение физического адреса осуществля­ется совершенно иначе. Прежде всего, используется сегментный механизм для организации виртуальной памяти. При этом адреса задаются 32-разрядными значениями. Кроме этого, возможна страничная трансляция адресов, также с 32-разрядными значениями. Наконец, при работе в защищенном режиме, ко­торый по умолчанию предполагает 32-разрядный код, возможно исполнение двоичных программ, созданных для работы микропроцессора в 16-разрядном режиме. Для этого введен режим виртуальной 16-разрядной машины, и 20-раз­рядные адреса реального режима транслируются с помощью страничного ме­ханизма в 32-разрядные значения защищенного режима. Наконец, есть еще один режим — 16-разрядный защищенный, позволяющий 32-разрядным микропро­цессорам выполнять защищенный 16-разрядный код, который был характерен для микропроцессора 80286. Правда, следует отметить, что этот последний ре­жим практически не используется, поскольку программ, созданных для него, не так уж и много.

Для изучения этих возможностей рассмотрим сначала новые архитектурные воз­можности микропроцессоров i80x86.

Новые системные регистры микропроцессоров 180x86

Основные регистры микропроцессора i80x86, знание которых необходимо для по­нимания защищенного режима работы, приведены на рис. 4.2. На этом рисунке следует обратить внимание на следующее:

       указатель команды (EIP) — это 32-разрядный регистр, младшие 16 разрядов которого представляют регистр IP;

       регистр флагов (EFLAGS) — это 32-разрядный регистр, младшие 16 разрядов которого представляют регистр FLAGS;

       регистры общего назначения ЕАХ, ЕВХ, ЕСХ, EDX, а также регистры ESP, EBP, ESI, EDI 32-разрядные, однако их младшие 16 разрядов представляют собой известные регистры АХ, ВХ, CX.DX, SP, ВР, SI, DI;

       сегментные регистры CS, SS, DS, ES. FS, GS 16-разрядные, при каждом из них пунктиром изображены скрытые от программистов (недоступные никому, кроме собственно микропроцессора) 64-разрядные регистры, в которые загружаются дескрипторы соответствующих сегментов;

 

□ при 16-разрядном регистре-указателе на локальную таблицу дескрипторов (Lo­cal Descriptor Table Register, LDTR) также имеется «теневой» (скрытый от про­граммиста) 64-разрядный регистр, в который микропроцессор заносит дескрип­тор, указывающий на таблицу дескрипторов сегментов задачи, описывающих ее локальное виртуальное адресное пространство;

□ 16-разрядный регистр задачи (Task Register, TR) указывает на дескриптор в глобальной таблице дескрипторов, который позволяет получить доступ к дескриптору сегмента состояния задачи (Task State Segment, TSS) — информацион­ной структуре, которую поддерживает микропроцессор для управления зада­чами;

   48-разрядный регистр GDTR (Global Descriptor Table Register) глобальной таб­лицы дескрипторов (Global Descriptor Table, GDT) содержит как дескрипторы общих сегментов, так и специальные системные дескрипторы, в частности, в GDT находятся дескрипторы, с помощью которых можно получить доступ к сегментам TSS;