Операционные системы и среды : практическая реализация моделей организации вычислительных работ

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

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ  
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ  
«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ «МИСиС» 

 

 
 
 

 

 

 

 
 

 

№ 2367 

Кафедра инженерной кибернетики

А.И. Широков 
О.Н. Калашникова 
 

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

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

Учебное пособие 

Под редакцией профессора Е.А. Калашникова 
и кандидата технических наук Ю.Ю. Прокопчука 

Рекомендовано УМО по образованию в области прикладной 
математики и управления качеством в качестве учебного пособия 
для студентов высших учебных заведений, обучающихся 
по направлению 231300 – Прикладная математика 

Москва  2014 

УДК 004.45 
 
Ш64 

Р е ц е н з е н т  
д-р техн. наук, проф. Н.В. Максимов (НИЯУ МИФИ) 

Широков, А.И. 
Ш64  
Операционные системы и среды : практическая реализация 
моделей организации вычислительных работ : учеб. пособие / 
А.И. Широков, О.Н. Калашникова. – М. : Изд. Дом МИСиС, 
2014. – 71 с. 
ISBN 978-5-87623-762-0 

Рассматриваются теоретические вопросы организации вычислительного 
процесса, прежде всего, управление порядком выполнения вычислительных 
работ и модели размещения программных единиц в памяти компьютера. Эти 
знания являются достаточными для самостоятельной программной реализации соответствующих упрощенных моделей. Примеры таких реализаций 
также рассматриваются в пособии. 
Содержание пособия соответствует дисциплине «Операционные системы 
и среды». 
Предназначено для студентов специальностей 220700, 230100, 230400, 
230700 и 231300. 

УДК 004.45 

ISBN 978-5-87623-762-0 
© А.И. Широков, 
О.Н. Калашникова, 2014

ОГЛАВЛЕНИЕ 

От авторов .................................................................................................4 
Введение....................................................................................................5 
1. Модели организации вычислительного процесса .............................6 
1.1. Модели обслуживания потока вычислительных заявок...........6 
1.2. Модели размещения вычислительных заявок в памяти .........10 
2. Реализация алгоритмов организации вычислительного 
процесса и функций стандартных утилит операционной системы..........17 
2.1. Примеры реализации алгоритмов планирования потока 
вычислительных работ......................................................................17 
2.2 Пример алгоритма, моделирующего загрузку программ 
в оперативную память компьютера ....................................................37 
2.3 Пример алгоритма, упрощенно моделирующего отдельные 
функции стандартных утилит .............................................................42 
3. Этапы выполнения курсовой работы или домашнего задания ......47 
Литература ..............................................................................................60 
Приложение 1. Титульный лист............................................................62  
Приложение 2. Этапы выполнения курсовой работы 
и формы отчетности ...............................................................................63 
Приложение 3. Пример консольного приложения, 
читающего текстовый файл .....................................................................63 
Приложение 4. Пример программы с графической интерпретацией 
результатов работы алгоритма..............................................................64 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Памяти 
Алексея Вадимовича 
Козловского 

От авторов 

Авторы данного пособия посвящают его памяти своего коллеги 
Алексея Вадимовича Козловского, скоропостижно скончавшегося 
9 октября 2009 г. 
После окончания механико-математического факультета МГУ 
в 1971 г. А.В. Козловский начал свою трудовую деятельность на кафедре инженерной кибернетики МИСиС в должности математикапрограммиста. В 1972 г. был избран на должность ассистента, 
а в 1976 г. – старшего преподавателя. 
Методико-преподавательская деятельность А.В. Козловского – это 
главным образом создание учебного курса «Численные методы». 
А.В. Козловский читал этот курс в течение 30 лет, систематически 
улучшая и перерабатывая его. По этому курсу им были изданы учебные 
и методические пособия, а также разработан и введен в практику цикл 
лабораторных работ на основе вычислительной техники.  
Очень много времени Алексей Вадимович уделял внеаудиторной 
работе со студентами кафедры инженерной кибернетики. Под его 
руководством были с успехом защищены не один десяток дипломных работ. 
Долгое время А.В. Козловский работал в должности ученого секретаря кафедры. Эту работу он выполнял на высоком уровне, чем снискал 
уважение как руководства института и кафедры, так и преподавателей.  
Занятия и лекции А.В. Козловский проводил на высоком научном 
уровне. За время работы в МИСиС он опубликовал более 30 научных 
статей и докладов. 
Авторы данного пособия сотрудничали с А.В. Козловским около 
40 лет. У них навсегда сохранились самые теплые воспоминания о нем 
как о высококвалифицированном специалисте, прекрасном педагоге 
и, что особенно важно, искреннем и доброжелательном товарище. 

Введение 

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

1. МОДЕЛИ ОРГАНИЗАЦИИ 
ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА  

1.1. Модели обслуживание потока 
вычислительных заявок 

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

t1
0
t2
t3
t4

A

B

C

 

Рис. 1.1. Временная диаграмма выполнения трех процессов 

На диаграмме (рис. 1.1) представлен фрагмент временной диаграммы выполнения центральным процессором трех вычислительных процессов с именами А, В и С. В первый интервал времени 
от 0 до t1 выполняется процесс А, затем с t1 до t2 – процесс В, затем (с t2 до t3) – снова А и последним (с t3 до t4) – С. После этого 
процессы продолжат обрабатываться дальше. 

Операционная система, работающая в мультипрограммном режиме, 
отслеживает изменения состояний выполняемых процессов и других вычислительных работ. Состояний, в которых может находиться процесс, 
много. Первое из них – выполнение. Оно может измениться на ожидание. 
Но причин такого состояния бывает много. Например, ожидание готового 
к выполнению процесса или ожидание какой-то операции, например, ввода необходимых для дальнейшей работы данных. 
Современные операционные системы могут различать более десятка 
состояний вычислительных работ. К примеру, команда ps, выводящая 
разнообразную информацию о процессах, выводит семь основных значений параметра «статус процесса» и около 10 дополнительных. Это 
справедливо для варианта freebsd команды ps. 
В самом общем случае при реализации какого-то алгоритма режима мультипрограммирования интервалы времени (кванты) работы 
каждого отдельного процесса могут быть различными, но часто они 
устанавливаются одинаковыми. Порядок поступления на обработку 
уже выполнявшихся процессов также может быть разным, т.е. изменение состояния «выполнение» вычислительного процесса на другое 
может происходить по разным причинам. Первая из них – истечение 
времени, отпущенного на выполнение процесса. Другими причинами 
могут быть ожидание операции ввода/вывода или поступление в систему более приоритетного процесса. Могут быть и другие причины, 
состав которых различен в зависимости от технологии реализации 
режима многозадачности. 
В режиме мультипрограммирования заявки на использование 
процессора должны выполняться поочередно, поэтому возникает задача диспетчеризации. Она является частным случаем задачи планирования вычислительных работ – краткосрочным. Кроме того, имеет 
место еще и долгосрочное и среднесрочное планирование. В большинстве современных операционных систем (ОС) долгосрочный 
планировщик отсутствует.  
В результате решения задачи краткосрочного планирования (диспетчеризации) должно быть определено, какие процессы и в каком 
порядке надо выполнять для того, чтобы достигнуть поставленной 
цели. Стратегий такого планирования много: 
1) по возможности заканчивать вычисления в том же порядке, 
в котором он были начаты;  
2) отдавать предпочтение более коротким задачам;  
3) предоставлять всем пользователям одинаковые услуги, в том 
числе и одинаковое время ожидания. 

В монографии [1], как и во многих других книгах по теории операционных систем, выделяются три класса последних:  
• 
пакетные системы; 
• 
интерактивные системы;  
• 
системы реального времени.  
Эти классы определяются различными условиями решения вычислительных задач. Для персональных компьютеров такие условия 
в большей мере соответствуют интерактивным системам. Они ориентированы на равномерное обслуживание множества программ. Хотя отдельные функции, реализованные в них, являются основными 
в других классах операционных систем. Системы пакетной обработки были реализованы в компьютерах третьего поколения, в которых 
основной задачей было выполнение множества заданий за возможно 
короткое время. Системы реального времени используются для 
управления техническими объектами, частой проблемой которых 
является выполнение задач к определенному времени.  
При диспетчеризации операционная система реализует некоторый 
алгоритм, который должен решать множество задач. Приведем задачи [1], которые должен решать планировщик заданий для всех классов операционных систем: 
Равнодоступность – предоставление каждому процессу справедливой доли времени центрального процессора.  
Принуждение к определенной политике – наблюдение за выполнением установленной политики.  
Баланс – поддержка загруженности всех составных частей системы. 
Теперь опишем задачи, которые в первую очередь реализуются 
в трех названных классах операционных систем.  
Пакетные системы: 
производительность – выполнение максимального количества заданий в час; 
оборотное время – минимизация времени между представлением 
задачи и ее завершением; 
использование центрального процессора – поддержка постоянной 
загруженности процессора.  
Интерактивные системы: 
время отклика – быстрый ответ на запросы; 
пропорциональность – оправдание пользовательских надежд; 
Системы реального времени: 
соблюдение предельных сроков – предотвращение потери данных; 
предсказуемость – предотвращение ухудшения качества в мультимедийных системах. 

Заметим, что алгоритмы краткосрочного планирования единиц 
вычислительных работ можно делить на два класса: приоритетные и 
неприоритетные. При первом из них предусматривается, что выполняющийся процесс по истечении определенного времени (определяемого сигналом прерывания от таймера) останавливается. Далее из 
всех имеющихся в системе процессов выбирается тот, у которого 
одна из характеристик – приоритет – имеет наилучшее значение. 
Именно он и будет выполняться в следующий квант времени. При 
неприоритетном обслуживании после запуска процесса он будет исполняться, пока не завершится или не возникнет ситуация, когда он 
вынужден остановиться (например, ему требуются данные, получаемые в результате выполнения операций ввода или вывода).  
Реализуемые операционными системами алгоритмы диспетчеризации можно разделить еще и на два таких класса: вытесняющие 
и невытесняющие. Две приведенные классификации имеют сходство. Один из двух представителей класса определяется как механизм, 
реализуемый только операционной системой (приоритетные, вытесняющие), а другой – реализуемый как операционной системой, так 
и самим процессом (неприоритетные, невытесняющие).  
Отметим, что можно назвать пример реализации вытесняющего 
алгоритма, который не является приоритетным. При таком механизме для выполнения в очередной период времени процесс выбирается 
не в соответствии с приоритетом, а каким-то другим способом, например, первый из очереди или даже случайным образом. Заметим, 
что в реальных системах могут быть реализованы комбинации таких 
механизмов. К примеру, процессы группируются по значению приоритета из некоторого диапазона. Механизм предполагает исполнение процессов в соответствии с приоритетным обслуживанием между группами (сначала выполняются все процессы из одной группы, 
а если их очередь пуста, начинают выполняться процессы из группы 
с более низким приоритетом).  
Следуя [1], кратко опишем алгоритмы краткосрочного планирования в трех названных типах операционных систем. 
А. Планирование в системах реального времени 
Первым пришел – первым обслужен (FIFS и FIFO). 
Сначала самое короткое задание (FSJ). 
Приоритет – наименьшему времени выполнения 
Б. Планирование в интерактивных системах 
Циклическое планирование. 
Приоритетное планирование. 

Использование нескольких очередей. 
Выбор следующим самого короткого процесса. 
Гарантированное планирование. 
Лотерейное планирование. 
Справедливое планирование. 
В. Планирование в системах реального времени 
С приоритетом, пропорциональным частоте запуска (RMS – Rate 
Monotonic Scheduling). 
С приоритетом для процесса с ближайшим истекающим крайним 
сроком (EDF – Earliest Deadline First). 
Каждая из активных единиц вычислительных работ описывается 
множеством характеристик. Они создаются при загрузке и сохраняются в памяти в процессе всего их жизненного цикла. Эти данные 
изменяются операционной системой, т.е. последняя фиксирует все 
события, которые происходят с процессами, потоками и волокнами 
от рождения (загрузки) до гибели (выгрузки).  

1.2. Модели размещения вычислительных 
заявок в памяти 

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

Активизация программ и данных начинается с загрузки в оперативную (или виртуальную) память данных с жесткого диска (или 
другого носителя). В виртуальной памяти одновременно могут находиться несколько загруженных процессов. Некоторые из них могут 
обращаться к общим областям памяти. Все это – следствие режима 
мультипрограммного режима работы. Такое положение приводит 
к тому, что в современных операционных системах выделяется специальная подсистема – менеджер памяти. Она должна решать множество задач, которые реализуются разными способами. Но в современных операционных системах реализуются комплексные технологии, основанные на организации виртуальной памяти. 
Операционная система при реализации мультипрограммирования 
должна выполнять множество функций [1]: 
1) отслеживание (учет) свободной и занятой памяти; 
2) первоначальное и динамическое выделение памяти процессам 
приложений и самой операционной системе и освобождение памяти 
по завершении процессов; 
3) настройка адресов программы на конкретную область физической памяти; 
4) полное или частичное вытеснение кодов и данных процессов 
из оперативной памяти (ОП) на диск, когда размеры ОП недостаточны для размещения всех процессов, и возвращение их в ОП; 
5) защита памяти, выделенной процессу, от возможных вмешательств со стороны других процессов; 
6) дефрагментация памяти. 
Существует несколько классификаций распределения памяти компьютера [6], выполняемых операционными системами (рис. 1.2), но все 
они делятся по признаку: используется внешняя память или нет.