В данной статье описываются философия и структура мультипрограммной системы, которая может быть расширена иерархией операционных систем в соответствии с различными требованиями планирования программ и распределения ресурсов. Ядро системы моделирует среду, в которой выполнение программы и ввод/вывод обрабатываются равномерно как параллельные, взаимодействующие процессы. Фундаментальный набор примитивов позволяет динамично создавать и контролировать иерархию процессов, а также связь между ними.
1 Введение
Мультипрограммная система, разработанная компанией Regnecentralen для компьютера RC 4000, является общим инструментом для проектирования операционных систем. Это позволяет динамично создавать иерархию процессов, в которых могут быть реализованы различные стратегии планирования программ и распределения ресурсов.
Для проектировщика современных информационных систем жизненно важным требованием любой операционной системы является то, чтобы она позволяла ему изменять режим работы, которым она управляет; в противном случае его свобода проектирования может быть серьезно ограничена. К сожалению, именно этого не позволяют современные операционные системы. Большинство из них основаны исключительно на одном режиме работы, таком как пакетная обработка, приоритетное планирование, планирование в реальном времени или диалоговый доступ (conversational access).
Когда возникает необходимость, пользователь часто считает безнадежным модифицировать операционную систему, которая сделала жесткие предположения в своей базовой конструкции о конкретном режиме работы. Альтернатива - заменить оригинальную операционную систему новой в большинстве компьютеров является серьезной, если не невозможной, проблемой, потому что остальная часть программного обеспечения тесно связана с соглашениями, требуемыми исходной системой.
Эта неудачная ситуация указывает на то, что главная проблема при проектировании мультипрограммной системы заключается не в определении функций, удовлетворяющих конкретным операционным потребностям, а в обеспечении ядра системы, которое может быть упорядоченно расширено новыми операционными системами. Это основная цель системы RC 4000
Далее объясняется философия и структура мультипрограммной системы RC 4000. Обсуждение не включает в себя детали реализации; размер и производительность представлены, однако, чтобы дать представление о целесообразности этого подхода. Функциональные характеристики мультипрограммной системы подробно описаны в отчете (Brinch Hansen 1969a), доступном в Regnecentralen.
2 Ядро системы
Наша основная позиция при проектировании состояла в том, чтобы не делать никаких предположений о конкретной стратегии, необходимой для оптимизации данного типа установки, а сосредоточиться на фундаментальных аспектах управления средой, состоящей из параллельных взаимодействующих процессов.
Наша первая задача состояла в том, чтобы придать точное значение понятию процесса, то есть ввести однозначную терминологию, определяющую, что такое процесс и как он реализуется на реальном компьютере.
Следующим шагом был выбор примитивов для синхронизации и передачи информации между параллельными процессами.
Наши окончательные решения касались правил динамического создания, контроля и удаления процессов.
Целью системного ядра является реализация следующих фундаментальных понятий: моделирование процессов; связь между процессами; создание, управление и удаление процессов
3 Процессы
Мы различаем внутренние и внешние процессы, примерно соответствующие выполнению программы и ввод / вывод.
Точнее, внутренний процесс - это выполнение одной или нескольких прерываемых программ в заданной области хранения. Внутренний процесс идентифицируется уникальным именем процесса. Таким образом, другие процессы не должны знать о фактическом местоположении внутреннего процесса в хранилище, но могут ссылаться на него по имени.
Проводится резкое различие между понятиями программа и внутренний процесс. Программа - это набор инструкций, описывающих вычислительный процесс, тогда как внутренний процесс-это выполнение этих инструкций в заданной области хранения.
Используя ввод/вывод система различает периферийные устройства, документы и внешние процессы.
Периферийное устройство - это аппаратное устройство, подключенное к каналу передачи данных и идентифицируемое номером устройства. Документ - это совокупность данных, хранящихся на физическом носителе, например, колода перфокарт, бланк принтера, катушка магнитной ленты или файл на носителе.
Внешний процесс - это ввод / вывод документа, идентифицируемый уникальным именем процесса. Эта концепция подразумевает, что внутренние процессы могут ссылаться на документы по имени, не зная реальных устройств, на которых они установлены.
Мультипрограммирование и связь между внутренними и внешними процессами координируется ядром системы - программой реагирования на прерывания с полным контролем ввода-вывода, защитой памяти и системой прерываний. Мы рассматриваем ядро системы не как самостоятельный процесс, а скорее как программное расширение аппаратной структуры, что делает компьютер более привлекательным для мультипрограммирования. Его функция заключается в реализации нашей концепции процесса и примитивов, которые процессы могут вызывать для создания и управления другими процессами и общения с ними.
До сих пор мы описывали мультипрограммную систему как набор независимых, параллельных процессов, идентифицируемых по именам. Акцент был сделан на четком понимании взаимосвязей между ресурсами (хранилищем и периферийными устройствами), данными (программами и документами) и процессами (внутренними и внешними).
4 Коммуникация процессов
В системе параллельных взаимодействующих процессов должны быть предусмотрены механизмы синхронизации двух процессов при передаче информации.
Дейкстра (1965) продемонстрировал, что неделимые операции блокировки и разблокировки, действующие на двоичных семафорах, являются достаточными примитивами с логической точки зрения. Однако мы были вынуждены сделать вывод, что сама по себе концепция семафора не отвечает нашим требованиям безопасности и эффективности в динамичной среде, в которой некоторые процессы могут оказаться паршивой овцой и нарушить правила игры.
Вместо этого мы ввели буферизацию сообщений внутри ядра системы как основное средство коммуникации процессов. Ядро системы управляет общим пулом буферов сообщений и очередью сообщений для каждого процесса.
Для связи между внутренними процессами доступны следующие примитивы:
send message(receiver, message, buffer),
wait message(sender, message, buffer),
send answer(result, answer, buffer),
wait answer(result, answer, buffer).
Send message копирует сообщение в первый доступный буфер пула и доставляет его в очередь именованного получателя. Приемник активируется, если он ожидает сообщения. Отправитель продолжает работу после получения информации об идентичности буфера сообщений.
Wait message задерживает процесс запроса до тех пор, пока сообщение не поступит в его очередь. Когда процессу разрешено вернуться к выполнению, он снабжается именем отправителя, содержимым сообщения и идентификатором буфера сообщений. Буфер удаляется из очереди и готовится к передаче ответа.
Send answer копирует ответ в буфер, в котором было получено сообщение, и доставляет его в очередь исходного отправителя. Отправитель сообщения активируется, если он ждет ответа. Процесс ответа продолжается немедленно.
Wait answer задерживает запрашиваемый процесс до тех пор, пока ответ не поступит в заданный буфер. По прибытии ответ копируется в процесс, а буфер возвращается в пул. Результат определяет, является ли ответ ответом от другого процесса или фиктивным ответом, генерируемым ядром системы в ответ на сообщение, адресованное несуществующему процессу.
Сообщение ожидания процедуры заставляет процесс обслуживать свою очередь в порядке первый пришёл - первый обслужен (first come - first served). Однако система также включает в себя два примитива, которые позволяют процессу ждать прибытия следующего сообщения или ответа и обслуживать свою очередь в любом порядке.
Эта система связи имеет следующие преимущества.
Мультипрограммная система динамична в том смысле, что процессы появляются и исчезают в любое время. Поэтому процесс вообще не обладает полным знанием о существовании других процессов. Это отражено в сообщении ожидания процедуры, которое позволяет процессу не знать о существовании других процессов, пока он не получит от них сообщения.
С другой стороны, как только связь между двумя процессами установлена (т. е. посредством сообщения), они нуждаются в общей идентификации этой связи, чтобы договориться о том, когда она будет прекращена (т. е. посредством ответа). Таким образом, мы можем рассматривать буфер как механизм создания идентификации разговора. Счастливым следствием этого является то, что он позволяет двум процессам обмениваться более чем одним сообщением одновременно.
Мы должны быть готовы к появлению ошибочных или вредоносных процессов в системе (например, незадействованных программ). Это допустимо только в том случае, если ядро системы гарантирует, что ни один процесс не может вмешиваться в диалог между двумя другими процессами. Это делается путем хранения идентификаторов отправителя и получателя в каждом буфере и проверки их всякий раз, когда процесс пытается отправить или дождаться ответа в данном буфере.
Эффективность достигается за счет очереди буферов, что позволяет процессу отправки продолжаться сразу после доставки сообщения или ответа, независимо от того, готов ли получатель к его обработке.
Чтобы сделать систему динамичной, жизненно важно, чтобы процесс мог быть удален в любое время, даже если он вовлечен в один или несколько разговоров. В этом случае ядро системы оставляет все сообщения от удаленного процесса нетронутыми в очередях других процессов. Когда эти процессы отвечают на них, ядро системы возвращает буферы в общий пул.
Возможна и обратная ситуация: при удалении процесса ядро системы находит не отвеченные сообщения, отправленные процессу. Они возвращаются как фиктивные ответы отправителям.
Основным недостатком буферизации сообщений является то, что она создает еще одну проблему ресурсов, поскольку общий пул содержит конечное число буферов. Если бы процессу было разрешено опустошать пул, посылая сообщения неосведомленным процессам, которые не отвечают ответами, дальнейшая коммуникация внутри системы была бы заблокирована. Следовательно, устанавливается ограничение на количество сообщений, которые процесс может отправлять одновременно. Делая это и позволяя процессу передавать ответ в полученном буфере, мы возлагаем весь риск разговора на процесс, который его открывает.
5 Внешние процессы
Первоначально коммуникационные примитивы были предназначены для обмена сообщениями между внутренними процессами. Позже мы также решили использовать send message и wait answer для связи между внутренними и внешними процессами.
Для каждого вида внешнего процесса ядро системы содержит фрагмент кода, который интерпретирует сообщение от внутреннего процесса и инициирует ввод/вывод с использованием области хранения, указанной в сообщении. Когда ввод / вывод прерывается прерыванием, ядро генерирует ответ внутреннему процессу с информацией о фактическом размере блока и возможных условиях ошибки. Это, по сути, реализация концепции внешнего процесса.
Мы считаем важным аспектом системы то, что внутренние и внешние процессы управляются равномерно как независимые, автономные процессы. Разница между ними заключается лишь в способности к обработке. Следствием этого является то, что любой внешний процесс может быть заменен внутренним процессом с тем же названием, Если становятся желательными более сложные критерии доступа и реагирования.
Внешние процессы создаются по запросу внутренних процессов. Создание-это просто присвоение имени определенному периферийному устройству. Чтобы гарантировать внутренним процессам исключительный доступ к последовательным документам, примитивы имеют возможности для резервирования и создания внешних процессов.
Консоли пишущей машинки (клавиатуры прим. пер.) - это единственные внешние процессы, которые могут отправлять сообщения внутренним процессам. Оператор открывает разговор, нажимая клавишу прерывания и вводя имя внутреннего приемника, за которым следует строка текста.
Файл в резервном хранилище можно использовать как внешний процесс, скопировав описание файла из каталога в резервном хранилище в ядро системы; после этого внутренние процессы могут инициировать ввод/вывод, отправляя сообщения файловому процессу.
Синхронизация внутренних процессов в реальном времени достигается путем отправки сообщений в тактовый процесс. По истечении интервала времени, указанного в сообщении, часы возвращают ответ процессу отправки.
В общем случае внешние процессы могут быть использованы для получения синхронизации между внутренними процессами и любым сигналом из внешнего мира. Например, внутренний процесс может послать сообщение сторожевому (watchdog прим. пер.) процессу и получить ответ, когда магнитная лента установлена на станции. В ответ внутренний процесс может дать станции временное имя, идентифицировать ленту, прочитав ее этикетку, и соответственно переименовать станцию.
6 Внутренние процессы
Конечный набор примитивов в ядре системы позволяет создавать, контролировать и удалять внутренние процессы.
Внутренние процессы создаются по запросу других внутренних процессов. Создание включает в себя присвоение имени смежной области хранения, выбранной родительским процессом. Хранилище должно находиться в области родителя.
После создания родительский процесс может загрузить программу в дочерний процесс и запустить его. Дочерний процесс теперь разделяет вычислительное время с другими активными процессами, включая родительский процесс.
По запросу родительского процесса ядро системы ожидает завершения всех вводов/ выводов, инициированных дочерним процессом, и останавливает его. В остановленном состоянии процесс все еще может получать сообщения и ответы в своей очереди. Они могут быть обработаны при перезапуске процесса.
Наконец, родительский процесс может удалить дочерний процесс, чтобы назначить его область хранения другим процессам.
Согласно нашей философии, процессы должны иметь полную свободу выбора собственной стратегии планирования программ. Ядро системы поставляет только необходимые примитивы для инициации и управления процессами. Следовательно, понятия загрузки и замены программ не являются частью ядра. Однако совместное использование общего пространства хранения между дочерними процессами на основе обмена возможно, поскольку система не проверяет, перекрывают ли внутренние процессы друг друга, пока они остаются в пределах областей хранения их родителей. Переход от процесса А к процессу В может быть реализован в родительском процессе следующим образом: stop(A); output(A); input(B); start(B).
7 Иерархия процессов
Идея ядра системы была описана как моделирование среды, в которой выполнение программы и ввод/вывод обрабатываются равномерно как параллельные, взаимодействующие процессы. Фундаментальный набор примитивов позволяет динамично создавать и контролировать процессы, а также общаться между ними.
Для этого нам все еще нужны, как часть системы, программы, которые управляют стратегиями связи операторов, планирования программ и распределения ресурсов; но для упорядоченного роста системы важно, чтобы эти операционные системы были реализованы как другие программы. Поскольку разница между операционными системами и производственными программами заключается только в юрисдикции, эта проблема решается путем организации внутренних процессов в иерархии, в которой родительские процессы имеют полный контроль над дочерними процессами.
После начальной загрузки внутренний накопитель содержит ядро системы и базовую операционную систему S, которая может создавать параллельные процессы A, B, C и т. д. Процессы, в свою очередь, могут создавать другие процессы, D, E, F и т. д. Таким образом, в то время как S действует как примитивная операционная система для A, B и C, они, в свою очередь, действуют как операционные системы для своих детей, D, E и F. Это иллюстрируется Рис. 1, на котором показано семейное древо процессов слева и соответствующее распределение памяти справа. Это генеалогическое древо процессов может быть расширено до любого уровня, при условии только ограничения общего числа процессов
В этой мультипрограммной системе все привилегированные функции реализуются в ядре системы, которое не имеет встроенной стратегии. Стратегии могут быть внедрены на различных более высоких уровнях, где каждый процесс имеет право контролировать планирование и распределение ресурсов своих дочерних процессов. Единственными правилами, применяемыми ядром, являются следующие: процесс может выделять только подмножество своих собственных ресурсов (включая хранилище и буферы сообщений) своим дочерним элементам; процесс может только запускать, останавливать и удалять своих собственных дочерних элементов (включая их потомков). После удаления процесса его ресурсы возвращаются родительскому процессу. Первоначально все системные ресурсы принадлежат базовой операционной системе S. Для получения подробной информации об управлении процессом и распределении ресурсов читателю следует обратиться к руководству системы (Brinch Hansen 1969a).
Подчеркнем, что единственной функцией генеалогического древа является определение правил управления процессами и распределения ресурсов. Вычислительное время распределяется циклическим планированием между активными процессами независимо от их положения в иерархии, и каждый процесс может взаимодействовать со всеми другими процессами.
Что касается будущего развития операционных систем, то наиболее важными характеристиками системы в настоящее время можно считать следующие:
- Новые операционные системы могут быть реализованы как другие программы Без модификации ядра системы. В этой связи следует отметить, что языки Алгол и Фортран для RC 4000 содержат средства для вызова ядра и инициирования параллельных процессов. Таким образом, можно писать операционные системы на языках высокого уровня.
- Операционные системы могут быть заменены динамически, что позволяет установке переключаться между различными режимами работы; несколько операционных систем могут быть активны одновременно.
- Стандартные программы и пользовательские программы могут выполняться под разными операционными системами без изменений, при условии наличия общего соглашения о возможном общении между родительскими и дочерними процессами.
8 Реализация
RC 4000 - это 24-битный двоичный компьютер с типичным временем выполнения команд 4 микросекунды (Brinch Hansen 1969 b). Это позволяет практически неограниченно расширять внутреннее хранилище и стандартизировать подключение всех видов периферийных устройств. Мультипрограммирование облегчается прерыванием программы, защитой памяти и привилегированными инструкциями.
Нынешняя реализация системы делает возможным мультипрограммирование с минимальным хранилищем 16K-32K слов, подкрепленных быстрым барабаном или диском. Ядро системы включает в себя внешние процессы для часов реального времени, пишущих машинок, ввода/вывода бумажной ленты, линейного принтера, магнитной ленты и файлов на резервном хранилище. Размер ядра и базовой операционной системы выглядит следующим образом:
Примитивы коммуникации выполняются в непрерывном режиме внутри ядра системы. Время их выполнения ограничивает реакцию системы на события реального времени:
Анализ показывает, что 2 миллисекунды, необходимые для полного разговора (сумма четырех примитивов), используются следующим образом:
Это распределение настолько равномерное, что нельзя надеяться увеличить скорость системы, вводя дополнительные, специальные машинные инструкции. Единственное реалистичное решение - сделать аппаратное обеспечение быстрее.
Примитивы для создания, запуска, остановки и удаления процессов реализуются в анонимном внутреннем процессе внутри ядра системы, чтобы избежать невыносимо длительных периодов в непрерывном режиме. Типичное время выполнения для них:
Чрезмерное время запуска и удаления внутреннего процесса связано со специфической системой защиты памяти RC 4000, которая требует установки ключа защиты в каждом слове хранения процесса.
Оригинал - https://www.classes.cs.uchicago.edu/archive/2020/winter/33100-1/papers/nucleus.pdf
9 Заключение
Идеи, подобные описанным здесь, были предложены другими (Harrison 1967; Huxtable 1967; Wichmann 1968). Мы представили нашу систему, потому что считаем, что в целом она представляет собой систематический и практический подход к проектированию сменных операционных систем. Как источник вдохновения для других проектировщиков, возможно, самое важное, что он иллюстрирует последовательность этапов проектирования, ведущих к общему ядру, а именно к определению концепции процесса, коммуникационной схемы и динамическому созданию и структурированию процессов.
Мы понимаем, конечно, что окончательная оценка системы может быть сделана только после того, как она была использована для разработки ряда операционных систем.