3.4.5. Алгоритмы планирования, основанные на квантовании
В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени квант.
Смена активного потока происходит, если:
поток завершился и покинул систему;
произошла ошибка;
поток перешел в состояние ожидания;
исчерпан квант процессорного времени, отведенный данному потоку.
Поток, который исчерпал свой квант, переводится в состояние готовности и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых. Граф состояний потока, изображенный на рис. 3.3, соответствует алгоритму планирования, основанному на квантовании.
Поток завершен
или ошибка
Потоку Поток
предоставлен Поток инициировал
квант исчерпал ввод-вывод
квант
Ввод-вывод завершен
Рис. 3.3. Граф состояний потока в системе с квантованием
Кванты, выделяемые потокам, могут быть одинаковыми для всех потоков или различными.
Если квант короткий, то суммарное время, которое проводит поток в ожидании процессора, прямо пропорционально времени, требуемому для его выполнения (то есть времени, которое потребовалось бы для выполнения этого потока при монопольном использовании вычислительной си-стемы).
Чем больше квант, тем выше вероятность того, что потоки завершатся в результате первого же цикла выполнения, и тем менее явной становится зависимость времени ожидания потоков от времени их выполнения. При достаточно большом кванте алгоритм квантования вырождается в алгоритм последовательной обработки, присущий однопрограммным системам, при котором время ожидания задачи в очереди никак не зависит от ее длительности. Кванты, выделяемые одному потоку, могут быть фиксированной величины, а могут и изменяться в разные периоды жизни потока. Пусть, например, первоначально каждому потоку назначается достаточно большой квант, а величина каждого следующего кванта уменьшается до некоторой заранее заданной величины. В таком случае преимущество получают короткие задачи, которые успевают выполняться в течение первого кванта, а длительные вычисления будут проводиться в фоновом режиме. Можно представить себе алгоритм планирования, в котором каждый следующий квант, выделяемый определенному потоку, больше предыдущего. Такой подход позволяет уменьшить накладные расходы на переключение задач в том случае, когда сразу несколько задач выполняют длительные вычисления.
Многозадачные ОС теряют некоторое количество процессорного времени для выполнения вспомогательных работ во время переключения контекстов задач. При этом запоминаются и восстанавливаются регистры, флаги и указатели стека, а также проверяется статус задач для передачи управления. Затраты на эти вспомогательные действия не зависят от величины кванта времени, поэтому чем больше квант, тем меньше суммарные накладные расходы, связанные с переключением потоков.
В алгоритмах, основанных на квантовании, какую бы цель они ни преследовали (предпочтение коротких или длинных задач, минимизация накладных расходов, связанных с переключениями), не используется никакой предварительной информации о задачах. При поступлении задачи на обработку ОС не имеет никаких сведений о том, является ли она короткой или длинной, насколько интенсивными будут ее запросы к устройствам ввода-вывода, насколько важно ее быстрое выполнение и т.д. Дифференциация обслуживания при квантовании базируется на «истории существования» потока в системе.
- Рецензенты:
- Ответственные за выпуск:
- Оглавление
- Введение
- 1. Назначение и функции операционной системы
- 1.1. Функциональные компоненты операционной системы автономного компьютера
- 1.1.1. Управление процессами
- 1.1.2. Управление памятью
- 1.1.3. Управление файлами и внешними устройствами
- 1.1.4. Защита данных и администрирование
- 1.1.5. Интерфейс прикладного программирования
- 1.1.6. Пользовательский интерфейс
- Вопросы для самопроверки
- Контрольные вопросы
- 1.2. Сетевые операционные системы
- 1.2.1. Сетевые и распределенные ос
- 1.2.2. Два значения термина «сетевая ос»
- 1.2.3. Функциональные компоненты сетевой ос
- 1.2.4. Сетевые службы и сетевые сервисы
- 1.2.5. Встроенные сетевые службы и сетевые оболочки
- 1.3. Требования к современным операционным системам
- Вопросы для самопроверки
- Контрольные вопросы
- 2. Архитектура операционной системы
- 2.1. Ядро и вспомогательные модули ос
- 2.2. Ядро и привилегированный режим
- 2.3. Многослойная структура ос
- 2.4. Аппаратная зависимость ос
- 2.5. Переносимость операционной системы
- Вопросы для самопроверки
- Контрольные вопросы
- 2.6. Микроядерная архитектура
- 2.6.1. Концепция
- 2.6.2. Преимущества и недостатки микроядерной архитектуры
- 2.7. Совместимость и множественные прикладные среды
- 2.7.1. Двоичная совместимость и совместимость исходных текстов
- 2.7.2. Трансляция библиотек
- 2.7.3. Способы реализации прикладных программных сред
- Вопросы для самопроверки
- Контрольные вопросы
- 3. Процессы и потоки
- 3.1. Мультипрограммирование
- 3.1.1. Мультипрограммирование в системах пакетной обработки
- 3.1.2. Мультипрограммирование в системах разделения времени
- 3.1.3. Мультипрограммирование в системах реального времени
- Вопросы для самопроверки
- Контрольные вопросы
- 3.2. Мультипроцессорная обработка
- Вопросы для самопроверки
- Контрольные вопросы
- 3.3. Планирование процессов и потоков
- 3.4. Понятия «процесс» и «поток»
- 3.4.1. Создание процессов и потоков
- 3.4.2. Планирование и диспетчеризация потоков
- 3.4.3. Состояния потока
- 3.4.4. Вытесняющие и невытесняющие алгоритмы планирования
- 3.4.5. Алгоритмы планирования, основанные на квантовании
- 3.4.6. Алгоритмы планирования, основанные на приоритетах
- 3.4.7. Смешанные алгоритмы планирования
- 3.5. Синхронизация процессов и потоков
- 3.5.1. Цели и средства синхронизации
- 3.5.2. Сигналы
- Вопросы для самопроверки
- Контрольные вопросы
- 4. Управление памятью
- 4.1. Функции операционной системы по управлению памятью
- 4.2. Типы адресов
- Вопросы для самопроверки
- Контрольные вопросы
- 4.3. Алгоритмы распределения памяти
- 4.3.1. Алгоритмы распределения без использования внешней памяти Распределение памяти динамическими разделами
- Распределение памяти перемещаемыми разделами
- 4.3.2. Алгоритмы распределения с использованием внешней памяти
- Свопинг и виртуальная память
- Страничное распределение
- Сегментное распределение
- Сегментно-страничное распределение
- Разделяемые сегменты памяти
- Вопросы для самопроверки
- Контрольные вопросы
- 5. Ввод-вывод и файловая система
- 5.1. Задачи операционной системы по управлению файлами и устройствами
- 5.2. Специальные файлы
- 5.3. Логическая организация файловой системы
- 5.3.1. Цели и задачи файловой системы
- 5.3.2. Типы файлов
- 5.3.3. Иерархическая структура файловой системы
- 5.3.4. Имена файлов
- 5.3.5. Монтирование
- 5.3.6. Атрибуты файлов
- 5.3.7. Логическая организация файла
- Вопросы для самопроверки
- Контрольные вопросы
- 5.4. Физическая организация файловой системы
- 5.4.1. Диски, разделы, секторы, кластеры
- 5.4.2. Физическая организация и адресация файла
- 2048 Записей
- 5.5. Физическая организация fat
- Кластер № 17 – начальный кластер файла file1; кластер № 18 – начальный кластер файла file2
- 5.6. Физическая организация файловых систем s5 и ufs
- 5.7. Физическая организация файловой системы ntfs
- 5.7.1. Структура тома ntfs
- 5.7.2. Структура файлов ntfs
- 5.7.3. Каталоги ntfs
- Вопросы для самопроверки
- Контрольные вопросы
- 5.8. Контроль доступа к файлам
- 5.8.1. Доступ к файлам как частный случай доступа к разделяемым ресурсам
- 5.8.2. Механизм контроля доступа
- Имена файлов
- 5.8.3. Организация контроля доступа в ос unix
- Процесс
- Запрос операции
- Вопросы для самопроверки
- Контрольные вопросы
- 5.8.4. Организация контроля доступа в ос Windows nt
- 5.8.5. Разрешения на доступ к каталогам и файлам
- Соотношение индивидуальных и стандартных разрешений для файлов
- Вопросы для самопроверки
- Контрольные вопросы
- Ответы на вопросы для самопроверки
- Лабораторные работы
- Методические указания для проведения лабораторных занятий и выполнения контрольной работы
- Лабораторная работа № 1 Системный реестр Windows 9x. Редактор базы данных регистрации
- Редактор системного реестра. Утилита regedit.Exe
- Командный файл системного реестра
- Утилита редактора системных правил Poledit
- Список ключей системного реестра
- Заблокировать возможность удаления принтеров.
- Заблокировать возможность добавления принтеров.
- Скрыть вкладку «Устройства» утилиты «Система».
- Скрыть вкладку «Профили оборудования» утилиты «Система».
- Лабораторная работа № 2 Администрирование сетевой ос Windows xp
- Установка удаленного терминала (Remote DeskTop Connection)
- Работа с Windows 2003 Server
- Утилиты панели управления
- Управление рабочей станцией
- Администрирование
- Конфигурирование сервера
- Управление контроллером домена
- Предоставление доступа к ресурсам сервера
- Привилегия клиента удаленного терминала
- Панель задач. Управление процессами
- Лабораторная работа № 3 Командные центры Windows 9х
- Утилита «Дата/время»
- Утилита «Клавиатура»
- Утилита «Мышь»
- Утилита «Специальные возможности»
- Утилита «Принтеры»
- Утилита «Шрифты»
- Утилита «Установка и удаление программ»
- Утилита «Система»
- Утилита «Язык и стандарты» Окно утилиты Язык и стандарты содержит вкладки Денежные единицы, Время, Дата, Региональные стандарты, Числа.
- Рабочий стол. Свойства рабочего стола
- Лабораторная работа № 4 Установка ос Fedora Core X. Режимы работы системы. Инсталляция приложений
- Подготовка жесткого диска к инсталляции ос Linux
- Программа редактирования разделов жесткого диска PowerQuest PartitionMagic 8.0
- Создать как: (Create as:) Logical Partition Тип раздела: (Partition type:) Linux Ext3 Размер: (Size:) 9500
- Инсталляция ос Fedora Core X
- Графический интерфейс gnome ос Linux
- Лабораторная работа № 4 Установка ос Fedora Core X
- Текстовый интерфейс ос Linux Алфавитно-цифровой терминал
- Режимы работы ос Linux
- Установка приложений в ос Red Hat
- Лабораторная работа № 5 Подсистемы управления ос
- Управление ресурсами ос Linux
- Графические утилиты управления процессами. Системный монитор
- Подсистемы управления, общие для всех ресурсов
- Администрирование в ос Red Hat. Локальные системы
- Пользовательский интерфейс
- Регистрация событий
- Лабораторная работа № 6 Файловые системы. Сетевые сервисы ос Linux
- Команды и утилиты, предназначенные для работы с файловыми системами
- Создание, редактирование и удаление разделов жесткого диска. Утилита fdisk
- Создание и локализация файловой системы
- Файловые службы и сетевые файловые системы
- Автомонтирование
- Сервисы Linux
- Список вопросов к контрольной работе
- Библиографический список