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

Несколько входных очередей

DOO-

Раздел 4

Раздел 3

Раздел 2

Раздел 1

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

800 К 700 К

400 К

200 К 100 К О

Рис. 4.2. 8 - фиксированные разделы памяти с отдельными входными очередями для каждого раздела; б - фиксированные разделы памяти с одной очередью на вход

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

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

Подобная схема, где утром оператор задает фиксированные разделы и после этого они не изменяются, в течение многих лет практиковалась в системах OS/360 на больших мэйнфреймах компании IBM. Она носила название MFT (Multiprogramming with а Fixed number of Tasks - мультипрограммирование с фиксированным количеством задач, или OS/MFT). Она легка для понимания и не менее проста в исполнении: входящее задание стоит в очереди до тех пор, пока не станет доступным соответствующий раздел, затем оно загружается в этот раздел памяти и там работает до завершения процесса. Сейчас очень мало (если они вообще сохранились) операционных систем, поддерживающих такую модель.

Настройка адресов и защита

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

Например, предположим, что первая команда представляет собой вызов процедуры с абсолютным адресом 100 внутри двоичного файла, создаваемого компоновщиком. Если эта программа загружается в раздел 1 (по адресу 100 К), команда обратится к абсолютному адресу 100, принадлежащему операционной системе. А нужно вызвать процедуру по адресу 100 К + 100. Если же программа -зафужается во второй раздел, команду нужно переадресовать на 200 К + 100 и т. д. Эта проблема известна как проблема перемещения программ в памяти или настройки адресов.

Одним из возможных решений является модификация команд во время загрузки программы в память. В программе, загружаемой в первый раздел, к каждому адресу прибавляется 100 К, в программе, которая попадает во второй раздел, к адресам добавляется 200 К и т. д. Чтобы выполнить подобную настройку адресов во время загрузки, компоновщик должен включить в двоичную программу список или битовый массив с информацией о том, какие слова в программе являются адресами (и их нужно перераспределить), а какие - кодами машинных команд, постоянными или другими частями программы, которые не нужно изменять. Таким образом работает операционная система OS/MFT.

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

Для защиты компьютера IBM 360 разработчики приняли следующее решение: они разделили память на блоки по 2 Кбайт и назначили каждому блоку 4-битный защитный код. Регистр PSW (Program Status Word - слово состояния программы) содержал 4-разрядный ключ. Аппаратура IBM 360 перехватывала все попытки работающих процессов обратиться к любой части памяти, защитный код которой отличался от содержимого регистра слова состояния программы. Поскольку только операционная система была вправе изменять коды защиты и ключи, предотвращалось вмешательство пользовательских процессов в дела друг друга и в работу операционной системы.

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

ровании процесса в базовый регистр загружается адрес начала раздела памяти, а в ограничивающий регистр - длина раздела. К каждому автоматически формируемому адресу перед его передачей в память прибавляется содержимое базового регистра. Таким образом, если базовый регистр содержит величину 100 К, команда CALL 100 будет превращена в команду CALL 100К+100 без изменения самой команды. Кроме того, адреса проверяются по отношению к лимитирующему регистру для гарантии, что они не используются для адресации памяти вне текущего раздела. Базовый и ограничительный регистры защищаются аппаратно, чтобы не допустить их изменений пользовательскими программами.

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

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

4.2. Подкачка

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

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

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

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