Системное Программное Обеспечение СПО (Аристов Михаил Викторович) 4-й курс I семестр 2000/2001 гг. 07.09.2000

§1 Концепция ОС 1 Назначение ОС. Основные определения Назначение ОС – управление ресурсами. Ресурсы: - активный процессорный; - памяти; - устройств; - информации. Анализ ресурсов возможен: - с точки зрения пользователя; - с точки зрения системного программиста. Функции ОС: 1. формирование пользовательского и программного интерфейса; 2. разделение аппаратных средств между пользователями и процессами; 3. планирование коллективного доступа к общим разделяемым ресурсам; 4. эффективное управление специфическими операциями и операциями обмена (ввода/вывода); 5. восстановление информации после сбоев аппаратных средств. Прообразом ОС были системы спулинга данных – это специальные программы, которые обеспечивали предварительную подготовку информации на каких-то носителях. Автооператоры – специальные программы пакетной обработки данных: заданияпакетынаборна носитель задачи выполняются последовательно, без вмешательства оператора. Мультипрограммная обработка данных: тот же пакет, но все задачи выполняются параллельно. 2 Основные принципы построения ОС В основе построения ОС лежат принципы, с точки зрения которых все ОС выглядят одинаково:  частотный (наиболее общий) основан на выделении действий по частоте использования. Те действия, которые в работе ОС встречаются более часто, получают условия для приоритетного исполнения. Следствием  является введение многоуровневого планирования работы ОС. Выделяется два уровня планирования: 1. долгосрочного; 2. краткосрочного. На 1. выносятся большие по объёму задачи обработки информации. Здесь управление осуществляется в общем без детализации. На 2. выносятся процессы обработки информации частые (типичные) в системе. Здесь происходит управление конкретными ресурсами путём их предоставления или отбора.  модульности Модуль – функциональный элемент, который имеет законченное оформление и средства сопряжения с другими модулями. Другие модули подразделяются на модули более высокого, более низкого и аналогичного уровней. Исходя из , модули связываются между собой в обобщённый модуль некоторого функционального уровня. Каждый функциональный уровень скрывает внутри себя собственное устройство и по отношению к другим выступает в качестве базового уровня. Главным требованием при реализации  является то, что модули должны обеспечивать возможность многократного использования. Модули не должны модифицировать сами себя – это свойство называется чистотой / реентерабельностью модуля.  функциональной избирательности согласно  в ОС выделяются наиболее важные модули, которые для эффективной работы находятся всегда под рукой. Такие наиболее важные модули образуют основу ОС – ядро. Ядро, как правило, основной своей частью или целиком хранится в оперативной памяти. В состав ядра входят модули: - управления системой прерываний; - распределения времени ЦП и памяти; - перевода программ из активного состояния в неактивное и наоборот. Так как эти действия должны выполняться очень быстро, зачастую ядро выполняет не всю функцию, а часто порождает новый процесс для реализации любой из своих функций. Кроме ядра должен существовать набор обрабатывающих программ – утилит – они являются транзитами.  генерируемости требует, чтобы ОС была представлена в такой форме, при которой главная системная программа могла быть настроена в соответствии с конфигурацией вычислительной системы и кругом решаемых задач. Такая настройка называется генерацией ОС.  функциональной избыточности 14.09.2000 в ОС должна содержаться возможность выполнения любого действия с помощью различных средств, например, предоставление нескольких режимов обработки (монопольный, мультипрограммный). Другой пример избыточности: наличие для ОС несколько взаимозаменяемых типов ядер. умолчания используется для облегчения организации связей с системой, как при генерации, так и при работе. Реакция: в ОС хранится базовый набор описаний (структур, процессов, параметров, модулей). Если в базовом наборе что-то менять, то автоматически убирается базовый элемент. защиты существует несколько способов организации защиты: 1. защита отдельных ресурсов (файлов, устройств) путём введения паролей на доступ к этим ресурсам; 2. контекстная защита состоит в том, что каждый процесс работает в выделенном адресном пространстве, и попытки выйти из этого пространства воспринимаются, как нарушение защиты; 3. двух контекстная работа, когда процессор может работать в обычном или в привилегированном режиме. В обычном режиме невыполнимыми являются некоторые операции и ОС, переключая процессор из одного режима в другой, следит за тем, чтобы программы ОС работали в привилегированном режиме, а пользовательские программы – в обычном. независимости от внешних устройств выражается в том, что ОС должна одинаково управлять внешними устройствами независимо от их конкретного физического состава. Этот принцип реализуется через специальную систему программ и ПО для управления устройствами – драйверами. Благодаря этому можно одним и тем же ядром управлять бесконечной периферией. открытости требует, чтобы ОС была доступна для анализа пользователями. §2 Взаимосвязь ОС, аппаратуры и ПО 1 Аппаратные средства 1. наличие расслоения памяти выражается в том, что память делится на несколько отдельных областей и аппаратное средство поддерживает одновременное обращение сразу к нескольким областям, например, банк чётных и нечётных байтов. Тогда при считывании одного обращения получаем слово. Это увеличивает быстродействие. 2. наличие регистра перемещений регистр перемещений – аппаратно поддерживаемый базовый регистр для динамического перемещения модулей. 3. наличие механизма прерываний/механизма опроса состояний и прерывания и опрос состояний нужны ОС, чтобы организовать связь процессов друг с другом и с ресурсами. Прерывание – это специальный аппаратный сигнал, который прерывает работу процессора и заставляет ОС инициализировать специальную программу – обработчик прерывания. Опрос состояний: ОС периодически опрашивает какие-то устройства и принимает какие-то решения о дальнейших действиях. Эти два механизма являются взаимоисключаемыми. 4. буферизация буфер – область основной памяти, предназначенная для промежуточного хранения данных. Основным приложением буферизации является буферизация операций ввода – вывода. Это связано с тем, что устройства ввода – вывода работают медленно, а потребители работают быстро. 5. защита памяти состоит в том, чтобы контролировать доступ к какому-то участку памяти. Существует два приёма защиты: a) наличие граничных регистров граничные регистры – специальные регистры, которые существуют в процессоре. b) наличие ключей доступа основано на том, что память выделяется непрерывным блоком и с каждым блоком связывается определённое число – ключ доступа. Аналогичный ключ связывается с каждым процессом и во время выполнения любого процесса, его ключ присутствует в специальном слове состояния. 6. режим задача/супервизор это аппаратное средство, позволяющее процессору выполнять полный набор команд или какого-то подмножества из полного набора. Тогда режим задачи включает подмножество «безопасных» команд, а режим супервизора включает полный набор команд. 7. виртуальная память это аппаратное средство, позволяющее использовать программные адреса, несоответствующие реальным физическим адресам. Существует несколько способов организации виртуальной памяти, например, страничная организация. 8. конвейеризация т.е. наличие аппаратного средства выборки сразу нескольких команд и их совместного выполнения. Это повышает производительность ОС. 2 Программные средства 4. структура базовой системы ввода-вывода (IOCS – In-Out Control System); 5. спулинговые системы; 6. эмуляция состоит в том, что на одной машине функционально моделируется другая машина. Эмуляция выражается в том, что существуют программные средства, которые выполняют набор команд эмулируемого компьютера. Эти программные средства могут быть высокоуровневыми или низкоуровневыми (работать на уровне микро программ). §3 Основные понятия ОС 1 Процесс является базовым понятием ОС. Процесс – это есть некоторая деятельность, связанная с выполнением программы с помощью ЦП. По ГОСТу процесс – это система действий, реализующая в вычислительной системе законченную функцию и оформленная т.о., что управляющая программа ОС может перераспределять системные ресурсы в целях обеспечения мультипрограммирования. 21.09.2000 Более конструктивное определение процесса: Процесс – это траектория процессора в адресном пространстве. Процессы могут протекать по-разному. Одна из функций ОС: управление каждым процессом в отдельность и несколькими процессами вместе. Задача управления состоит в влиянии на состояния процесса. С точки зрения ОС для описаний процессов подходит Марковская модель случайных процессов с дискретным состоянием и непрерывным временем. Суть модели: у системы есть несколько состояний; для описания состояний системы используются графы; переходы из состояния в состояние могут происходить в случайные моменты времени. Модель процессов: основные состояния: 1. активности: характеризуется тем, что программа выполняется процессором; 2. готовности: характеризуется тем, что программа может быть исполнена, поскольку для этого есть возможности, и ожидает предоставления процессора; 3. ожидания: характеризуется тем, что программа не исполняется, а ожидает предоставления некоторого ресурса; Не основные состояния: 4. порождения: характеризуется тем, что резервируются ресурсы, необходимые для выполнения программы, и осуществляются действия по подготовке программы к первому исполнению; 5. окончания: характеризуется тем, что освобождаются все занятые ресурсы и ЦП, программа больше исполняться не будет и должна покинуть ОС. Граф процесса: Процесс в каждом состоянии характеризуется набором данных. Все переходы – это функции, которые должна выполнять ОС над процессами. Смысл работы ОС по управлению процессами заключается в выполнении этих функций. Набор этих функций может изменяться в зависимости от свойств ОС. Причины переходов системы из одного состояния в другое являются случайными событиями, которые могут быть разделены на две группы: 7. внешние причины: переходы 1, 2, 4, 5; 8. внутренние: переходы 3, 6. Классификация процессов. Процессы классифицируются по временным характеристикам переходов из состояния в состояние. Когда переходы привязаны к физическим моментам времени, тогда процессы называются процессами реального времени. Интерактивные процессы – это процессы, общая длительность которых не дольше заданной по времени реакции на воздействие или запрос. Процессы не реального времени и не интерактивные – пакетные процессы. Пакетные процессы с точки зрения ОС являются основными. Классификация пакетных процессов:  по принадлежности к ЦП: 1. внутренние: обрабатываются в ОС центральным процессором; 2. внешние: обрабатываются вне ОС;  по принадлежности к ОС: 1. системные: выполняются с использованием программ ОС; 2. пользовательские: выполняются с использованием программ пользователя;  по генеалогическим признакам: 1. порождающие; 2. порождённые;  по результативности: 1. различные: ничего общего между ними нет; 2. эквивалентные: дают одинаковый конечный результат на одинаковых данных (разные ЦП, программы, трассы); 3. тождественные: эквивалентные с одинаковыми программами; 4. равные: тождественные с одинаковыми трассами;  по динамичности: 1. последовательные: процессы, трассы которых не пересекаются; 2. параллельные: процессы, трассы которых пересекаются в определённые моменты времени; 3. комбинированные: то последовательные, то параллельные;  по связности: 1. изолированные; 2. информационно независимые: те, которые используют совместно какие-то ресурсы, но не обмениваются информацией; 3. взаимодействующие: те, которые имеют информационную связь; 4. конкурирующие: те, которые тесно связаны по ресурсам. 2 Ресурсы Одна из задач ОС – это задача оптимального управления ресурсами и предоставление их возможно большему количеству пользователей в возможно большем количестве. Ресурс – это характеристика надёжности (количественная); Ресурс – как объект. Для ресурса ОС более подходящим является второе определение. Характеристика ресурсов: наличие потребителя и ограниченность. Если это есть, то возникает задача управления ресурсами. В ОС ресурсы получают смысл, когда они потребляются. Потребителями ресурсов являются процессы. В качестве ресурса можно рассматривать: всю машину, подсистему шина-процессор, процессор (в зависимости от того, что распределяется). По ГОСТу: ресурс – это средство вычислительной системы, которое может быть выделено процессу на определённый период времени. Граф ресурса: Задача ОС по управлению ресурсами состоит в выполнении вышеперечисленных функций. Классификация ресурсов:  по реальности существования 1. физический: реально существующий; 2. виртуальный: моделирующий физический ресурс, т.е. существующий не в том виде, в котором он преподносится потребителю;  по возможности расширения свойств: 1. жёсткий: существующий в неизменном виде и не допускающий виртуализации; 2. эластичный: изменяемый и допускающий виртуализацию;  по степени активности: 1. активный: может активизировать другие ресурсы (ЦП); 2. пассивный (память);  по времени существования: 1. постоянный: существует независимо от процесса; 2. временный;  по степени важности: 1. главный; 2. второстепенный;  по структуре: 1. простой; 2. составной;  по восстанавливаемости: 1. воспроизводимый; 2. потребляемый; и т.д. Для ресурсов с разными характеристиками будет организовываться разное управление. 3 Концепция виртуализации 28.09.2000 ОС строит из реальных ресурсов виртуальные ресурсы и предоставляет их пользователю. На этом строится работа ОС. Виртуальный ресурс – это ресурс, который имеет идеальные характеристики по сравнению с реальным ресурсом или имеет такие характеристики, которых реальный ресурс не имеет. Примером виртуального ресурса является ресурс виртуальной памяти. Он является неограниченным, т.е. принимает такие размеры, которые требуются пользователю. Другим примером виртуального ресурса является электронный диск. Реальный диск имеет какие-то характеристики, и все операции выполняются на нём, а электронный диск – это ресурс, который моделирует операции чтения и записи, и все операции выполняются и размещаются не на диске, а в оперативной памяти. Но этот диск не хранит никакой информации. Одна из форм проявления виртуализации – это использование в любой ОС специальных управляющих программ – драйверов. Обычно на драйвер смотрят как на специфическую программу, которая управляет каким-либо устройством (драйвер мыши, драйвер клавиатуры). Но кроме этого драйвер выполняет функции виртуализации устройств (т.е. их идеализации). В UNIXе драйверы устройств независимо от физического характера устройств обеспечивают передачу и хранение данных в виде блоков по 0.5 kбайт, причём эти блоки прямо адресуются. Другой пример драйвера: драйвер нулевого устройства. Нулевое устройство – это устройство, которое необходимо для моделирования операции обмена. При выводе на нулевое устройство ОС всегда получает сигнал об успешном завершении операции, а при вводе – сигнал, соответствующий концу файла. Следующим уровнем после виртуализации отдельных устройств является понятие виртуальной машины. Виртуальная машина – это набор процессов, которые представляют работу реальных устройств или частей машины (например, интерпретатор языка программирования). Во многих случаях виртуальная машина создаётся ОС при возникновении какой-то задачи, т.е. выделяется соответствующий набор ресурсов (виртуальная память, виртуальный процессор и др.). концепция виртуализации нашла применение при проектировании ОС. При проектировании операционную систему стараются представить в виде набора планировщиков (управляют процессами) и распределителей (управляют ресурсами). Задача планировщиков состоит в том, чтобы переводить процессы из состояния в состояние. Задачей распределителей ресурсов является предоставление ресурса многим пользователям. Одной из типичных по распределению является схема «Монитор ресурса». Монитор – это специальная управляющая программа, которая осуществляет управление ресурсом и обрабатывает заявки к этому ресурсу. Причём доступ к этому ресурсу напрямую, минуя монитор, невозможен. Т.о. монитор гарантирует, что работа с ресурсом будет выполнена правильно и безопасно. Заявки могут обрабатываться двумя способами: либо заявка принимается, либо, если ресурс занят, отклоняется, при этом она может покинуть монитор, или монитор может управлять входной очередью (тогда он берёт на себя и функции планировщика). В любом случае монитор скрывает ресурс внутри себя. На основе концепции виртуализации разработан метод восходящего проектирования (МВП). Этот метод лежит в основе построения ОС, но и применяется при проектировании сложного ПО. МВП состоит в том. Что выделяется набор вложенных виртуальных машин. Машину самого нижнего уровня образует аппаратное средство. Машина нижнего уровня + работающая на ней управляющая программа – это следующий уровень. Программный слой для этой машины + эта машина – это следующий уровень, и т.д. свойства уровней: 1. на каждом уровне ничего не известно о свойствах и существовании более высоких уровней; 2. на каждом уровне ничего не известно о внутреннем строении других уровней. Связь между уровнями происходит только через фиксированные оговорённые сопряжения; 3. каждый уровень представляется группой модулей. Модули могут мыть двух типов: 3. внутренние: к ним нет доступа с других уровней и их имена не известны; 4. внешние: имена известны на других уровнях, но тогда – это точки сопряжения с другими уровнями; 4. каждый уровень должен обладать каким-то ресурсом и либо скрывать его от других, либо представлять другим в виртуальном виде; 5. каждый уровень должен обеспечивать некоторую абстракцию данных в системе; 6. на каждом уровне предположения о других уровнях должны быть минимальны, т.е. каждый уровень должен иметь “слабое сцепление” с другими уровнями. §4 Управление процессами Как было отмечено раньше, модель процессов – это Марковская модель случайных процессов с дискретным состоянием и непрерывным временем. В мультипрограммной системе существует множество процессов, которые находятся в различных состояниях. В однопроцессорной системе в активном состоянии в каждый данный момент может находиться только один процесс. Если в одном и том же состоянии может находиться множество процессов, то такие состояния должны описываться с помощью специальной структуры данных – списком. Очевидно, что в модели процессов должны поддерживаться два списка: S1 – список готовности; S2 – список ожидания. Эти списки могут быть устроены одинаково или по-разному. Как правило, S1 представляет собой приоритетную очередь, причём приоритеты могут быть статическими (постоянными) или динамическими (переначисляемыми). Очередь S2 – очередь по дисциплине FIFO. Перевод процесса из состояния в состояние – это выполнение некоторых функций, аргументами в которых являются имя процесса и имя соответствующей структуры данных. 1 – запуск (имя процесса, S1); 2 – активизация (имя процесса, S1); 3 – приостанов (имя процесса, S1); 4 – блокировка (имя процесса, S2*); 5 – подготовка (имя процесса, S1, S2*); 6 – завершение (имя процесса); * – очередь может быть общая или их может быть несколько, связанные с каждым ресурсом. Во всех функциях присутствует один общий параметр «имя процесса». 1 Способы управления процессами и основные операции 05.10.2000 Представителем процесса в глазах ОС является специальная структура данных – блок управления процессом (БУП или PCB). PCB содержит следующие элементы: • текущее состояние процесса; • уникальный идентификатор процесса (IP); • приоритет процесса; • один или несколько указателей на выделенные области памяти; • указатели на выделенные ресурсы; • область сохранения регистров; • … . Эта структура должна полностью характеризовать процесс, она должна быть компактной, и сохранять/восстанавливать процесс. Во многих аппаратных платформах выделяются специальные средства – аппаратные регистры для хранения блока управления, и аппаратные команды для воздействия на аппаратные регистры (загрузка, быстрый запуск и т.д.). Выполнение функций операционной системой заключается в модификации определённых полей PCB. Функции: – создание/порождение процесса; – уничтожение; – возобновление; – изменение приоритета; – блокировка/разблокировка; – запуск на первое исполнение; – … . Разберём функцию создания/порождения процесса. Она должна включать ряд действий: 1. присвоение процессу уникального имени, идентифицирующего процесс в глазах ОС; 2. включение этого имени в перечень имён, известных системе; 3. установка начального приоритета процесса; 4. выделение процессу первоначальных ресурсов. Эти действия должны сводиться к тому, что на их основе будет формироваться PCB и заполняться первоначальной информацией. Аналогично – уничтожение: 1. исключение данного имени из списка имён; 2. освобождение выделенных ресурсов. Эти действия должны сводиться к модификации полей PCB. Чтобы вызвать какую-то функцию, необходимо внешнее или внутреннее событие. Об этих событиях ОС будет узнавать с помощью прерываний. 2 Прерывания Прерывание – это причина, которая побуждает ОС реализовать ту или иную функцию. С другой стороны, прерывание – это событие, которое вмешивается в процедуру последовательного выполнения команд процессора. Сигнал прерывания обрабатывается аппаратно, но с привлечением программных средств. Обработка прерываний включает следующие моменты: • передача управления ядру ОС; • ядро запоминает состояние прерванного процесса; • ядро анализирует тип прерывания (причину) и порождает новый процесс, целью которого является реакция на произошедшее событие (прерывание). ОС инициализирует выполнение программы – обработчик прерывания (IH). Классической схемой организации прерываний является схема IBM 370. Здесь существует 5 типов прерываний: 1. SVC – прерывание по обращению к супервизору – внутреннее прерывание. Возникает, когда процессор выполняет специальную команду; 2. I/O – прерывание по вводу-выводу: инициализируется периферийной аппаратурой. Назначение: сообщить ЦП о завершении операции или изменении; 3. extern – внешнее прерывание – прерывание от внешних событий, не связанных с периферией, например, сигнал с таймера, с пульта оператора; 4. restart – прерывание по restart-у: требует перезагрузки ОС (инициализация процесса раскручивающей загрузки); 5. Check – прерывание от схем контроля: возникают при аппаратных сбоях, падении напряжения ниже какого-то фиксированного уровня. Если в ОС есть эти типы прерываний, то с ОС входят и 5 типов обработчиков. Все обработчики являются самостоятельными и работают одинаково – способом переключения контекста. PCB связан с PSW (статусное слово процесса). PSW содержит информацию, необходимую и достаточную для выполнения процесса, т.е. по PSW можно определить, что это за процесс. При возникновении прерывания PSW сохраняется в одной из нескольких областей – OLDPSW (их 5) – действие 1. Обработчики (их тоже 5) содержат адреса исполняемых команд. Действие 2 – загрузка нового PSW в текущее. Как только новое PSW заняло место текущего, начинается новый процесс, который инициализирует работу соответствующего обработчика. 3 Ядро ответственно за основные процедуры управления процессами. Главная функция ядра: обработка прерываний. В момент обработки одного прерывания обработка других прерываний запрещается. Это делается с помощью наложения разных масок. Маскирование прерываний должно быть коротким, поэтому ядро должно только намечать контуры обработки, т.к. сама обработка может быть длительной. После наметки контуров обработки ядро порождает какой-то процесс. В ядре выделяют следующие функции: 1. обработка прерываний (контур); 2. создание и уничтожение процессов; 3. переключение процессов из состояния в состояние; 4. распределение ресурсов; 5. приостановка/активизация процесса; 6. манипулирование PCB; 7. поддержка операций ввода-вывода; 8. поддержка распределения памяти; 9. поддержка работы файловой системы; 10. поддержка функций учёта и системного журнала. Существуют различные схемы реализации функций ядра. Одна из распространённых: двухуровневая система управления. 4° Двухуровневая система управления 12.10.2000 Предпосылки для введения двух уровней: процессы могут существенно отличаться друг от друга (по длительности, по частоте и т.д.). По одной из точек зрения на процессы, их можно разделить на 2 класса: • редкие, но объёмные; • по ресурсам менее ёмкие, но встречаются часто. Одним из критериев оптимальной работы ОС является то, что для разных процессов организуется разное управление. Выделяют 2 уровня управления: • верхний – долгосрочный: здесь процессы выделяются в задачи и задания; • нижний – краткосрочный: планировщик процессов, диспетчер процессов, супервизор процессов. Метод решения задач на уровне долгосрочного планирования подразумевает, что для каждой задачи создаётся виртуальная машина и порождаются заявки на нижний уровень. На нижнем уровне происходит выполнение фундаментальных функций ядра. Двухуровневая система управления была рассмотрена в IBM 360/370. там управление процессами делилось на следующие 2 уровня: • верхний: осуществляется специальным планировщиком заданий; • нижний: осуществляется супервизором задач. Долгосрочное планирование На этом уровне объектами управления являются укрупнённые процессы виртуальной машины. Жизнь этих укрупнённых процессов описывается такой же диаграммой состояний, что и у процессов. Но смысл этих состояний отличается. Пример: Состояние порождения состоит в том, что планировщик заданий будет формировать виртуальную машину. Его действия: резервирование ресурсов, резервирование памяти, создание информационной структуры, которая будет выполнять роль PCB (в терминах IBM – это дескриптор задания). Состояние готовности: виртуальная машина создана и не выделен виртуальный процессор. Состояние активности: выполнение каких-то реальных шагов задания. Выполнение состоит в формировании заявки для реального процесса. Когда придёт ответ с нижнего уровня, для виртуальной машины это переход из активного состояния в состояние готовности. Состояние окончания: разрушение виртуальной машины – освобождение выделенных ресурсов. Планировщик заданий может выполнять ещё несколько функций: например, при завершении процесса формируется бюджет этого процесса. Необходимо предоставить информацию о требуемых ресурсах. Существует 2 способа сообщения о содержании задания: 1. сообщить всю информацию о требуемых ресурсах. Это должно быть сделано с помощью какого-то языка. Сообщение должно быть обработано, после чего порождается виртуальная машина. Это – компилятивный принцип. 2. задание рассказывает, что ему нужно на каждом шаге. Это – принцип интерпретаций. Компилятивный принцип реализован в IBM-системах с помощью языка управления заданиями JCL. Этот язык содержит составные элементы, которые определяют: начало/конец задания: // JOB имя_задания, приоритет/ //; запрашиваемые ресурсы: // DD имя_ ресурса характеристики; этапы выполнения: // EXEC имя_шага, требуемые ресурсы (память, CPU). Принцип интерпретаций получил распространение в UNIX. Там есть специальная утилита – командный процессор Shell, который воспринимает команды от пользователя на специальном Shell-языке. Схема компиляции Основной блок ОС – программа управления заданиями. Функция этой программы: приём заданий, контроль их прохождения, планирование порядка выполнения, вывод результатов и подготовительные действия к началу выполнение и к завершению. Исходными данными для управления заданиями являются: операторы входного потока, пультовые команды оператора и информация из других частей ядра. Управление заданиями включает 4 компоненты:  главный планировщик - ГП;  чтение/интерпретация - RDR;  инициатор-терминатор - INIT;  системный вывод - WTR. Функции управления заданиями: 1. анализ входного потока; 2. выделение шагов задания, т.е. отдельных задач; 3. перезапись интерпретированного текста на диск с целью ускорения последующего прохождения задания; 4. подготовка задания к выполнению, для чего из каждого шага формируется отдельная задача; 5. распределение устройств ввода-вывода и закрепление их за заданиями; 6. распределение разделов оперативной памяти и выделение им ключей защиты. Общая схема управления заданиями: 19.10.2000 Особая роль главного планировщика состоит в том, что подсистема планирования верхнего уровня работает тогда, когда система раскручена, т.е. всё работает. А при первоначальной загрузке этой подсистемы не существует. Работа главного планировщика состоит в развёртывании подсистемы заданий. Значит, главный планировщик создаёт задачи чтение и интерпретация, инициатор-терминатор, системный вывод (RDR, WTR, INIT). После того, как главный планировщик создал эти задачи, за ним остаётся ещё и обработка консольных сообщений оператора. Чтение и интерпретация – программа RDR работает в двух режимах, определяемых главным планировщиком. Эти режимы состоят в том, что, либо во входном потоке интерпретируется каждый оператор, написанный на языке заданий, либо вначале все входные записи запоминаются во входном буфере на диске, а потом эти задачи извлекаются из буфера и интерпретируются. В любом случае выполняются следующие функции: – чтение входного потока; – анализ и интерпретация операторов входного языка; – включение каталогизированных процедур (обработка макрокоманд) – процедур, описания которых хранятся в каталогах; – управление очередью входных работ; – управление очередью входных наборов данных; – подготовка очереди выходных наборов. Инициатор-терминатор должен состоять из двух частей: 1. инициатор – готовит выполнение очередного шага; 2. терминатор – завершает выполнение очередного шага. 1 выбирает первое задание из первого приписанного к нему класса и пытается его запустить. Это продолжается, пока класс не станет пустым. Выполнение заданий 1 состоит в том, что он проверяет доступность наборов данных, распределяет устройства за наборами данных, выделяет дисковую память для выходных наборов и формирует заявку, в которой указывает имя процедуры, на нижний уровень (планировщику нижнего уровня). Дальнейшее развитие задачи связано с функционированием ядра ОС. Если класс становится пустым, 1 переходит в состояние ожидания. 2 проверяет условие завершения предыдущего шага. Если шаг последний, 2 должен освободить все ресурсы, проверить завершение задачи и инициировать программу системного вывода. Системный вывод состоит в том, что периферийные ресурсы строго разделяются между заданиями и каждое задание работает со своим собственным виртуальным ресурсом, и задачи не конфликтуют. Но устройства системного вывода отличаются тем, что на эти устройства претендуют все задачи. И поэтому задачей системного вывода является устранение этих конфликтов. Эти конфликты WTR устраняет путём создания отдельных выходных очередей для каждого задания. Комплекс управления заданиями базируется на системе связанных таблиц. Структура данных: Управление на нижнем уровне Выполняет супервизор задач. Основные его функции: распределение времени ЦП, памяти и координация (согласование) выполняемых задач. Эти задачи уже ближе к задачам управления процессами. Главной структурой является блок управления задачей (TCB). Такие блоки образуют очередь. Каждое задание порождает несколько задач, кроме того некоторые задачи порождаются самой ОС. Задача супервизора состоит в том, что из очереди (может быть очереди с приоритетами) выбрать очередную задачу для выполнения. Супервизор задач создаёт задачу: – при выполнении начальной загрузки – это задача главного планировщика; – при обработке директивы входного языка, который описывает шаг задания (// exec); – при выполнении специальной макрокоманды – ATTACH. Т.е. структура данных и схема работы: ATTACH создаёт подзадачу. Существует ещё одна макрокоманда DETACH, которая удаляет задачу из ОС. Макрокоманда содержит набор параметров и специальную команду обращения к супервизору SVC. Эта команда порождает прерывание, ЦП обрабатывает это прерывание. В процессе обработки из значений параметров выясняют причину и запускают соответствующий IH-обработчик. Запущенный обработчик выполняет все необходимые действия. Краткосрочное планирование 26.10.2000 Для краткосрочного планирования объектами управления являются процессы. Они выступают на данном уровне в качестве потребителей активных и пассивных ресурсов. Действиями на этом уровне являются переводы процессов из состояния в состояние. Т.к. в одном состоянии могут находиться несколько процессов, то эти состояния должны представлять собой очереди. Особенностью данного планирования является то, что управление состоит в том, что процессу предоставляются какие-то ресурсы. Поэтому часто управление на этом уровне называют диспетчеризацией и соответствующие части называются диспетчер задач, диспетчер процессов. Диспетчер обеспечивает управление состояниями:  порождения;  готовности;  активности;  уничтожения. Состояние  требует определение имени процесса и имени программы, которую этот процесс реализует, а также должен быть обеспечен доступ к ресурса, без которых выполнение программы невозможно. Такое порождение происходит в ответ на заявку с верхнего уровня. В параметрах должно быть указано: имя модуля/программы, параметры (аргументы запуска), указатели на ресурсы, указатели приоритетов и т.д. Выполнение системного вызова состоит в том, что диспетчер запускает специальную системную программу, которая создаёт структуру данных – дескриптор процесса, заполняет его информацией, также могут выполняться какие-то дополнительные действия (резервирование памяти), и дескриптор ставится в очередь. Т.е. ATTACH порождает процесс, который переводится в состояние готовности. Состояние  и процедура перевода в : по смыслу здесь действия обратные тому, что было в , но эти действия могут быть реализованы двумя разными способами. Это связано с причинами завершения процесса; причины могут быть внутренними и внешними. В любом случае освобождается память и ресурсы, и дескриптор процесса выводится из всех очередей. Но здесь существует проблема, связанная с тем, что процессы могут быть как независимыми, так и порождающими или порождёнными. Если есть цепочка порождённых процессов, то возникает вопрос: что делать с порождёнными процессами, когда порождающий удаляется? Существует два решения: 1. завершение родительского процесса автоматически влечёт за собой уничтожение порождённых процессов; 2. завершение родительского процесса откладывается до завершения порождённых им процессов. Чтобы реализовать второе решение, в состав систем управления процессами вводятся дополнительные системные средства, которые позволяют фиксировать события. Эти события состоят в том, что наступает завершение определённых процессов. В операционной системе IBM 370 такими системными вызовами являются: WAIT () и POST (); в операционной системе UNIX: wait () и exit (). Например, системный вызов wait () задерживает текущий процесс, т.е. переводит его из активного состояния в состояние ожидания. В состоянии ожидания он находится до события – завершение порождённого процесса. Завершение порождённого процесса среди прочих эффектов (освобождение ресурсов и т.д.) генерирует системный вызов exit (). Работа этого системного вызова состоит в том, что он находит процесс, находящийся в состоянии ожидания именно этого события, и переходит процесс в состояние готовности. Центральным моментом является перевод процесса из состояния готовности в состояние активности и обратно. Рассмотрим перевод из состояния готовности в состояние активности. В этом случае диспетчер должен: – обработать список готовности и выбрать процесс-кандидат на активизацию; – для выбранного процесса надо выполнить восстановление контекста, если имело место прерывание; – соответствующая модификация дескриптора; – передача управления на исполнение. Т.е. основным элементом является дескриптор задачи или процесса. При любой организации дескриптора информация в нём должна быть разбита на несколько функциональных групп: ~ идентификация: смысл – уникальное имя, может быть несколько уникальных имён, которые будут характеризовать процесс с нескольких сторон; ~ ресурсная: содержатся сведения о тех ресурсах, которые затребованы, фактически предоставлены или в данный момент используются; ~ статусная: информация, в каком состоянии находится процесс, и что надо, чтобы восстановить его; ~ связи: порождающий/порождённый (необходимо для корректного завершения); ~ учётная: содержит данные о приоритете статическом и динамическом, об использованных ресурсах (затраченное процессорное время). Это необходимо для правильного планирования использования процессов. Обычно применяется разделение на дескриптор и ссылку на дескриптор. Ссылка на дескриптор всегда находится в оперативной памяти в высокоактивном состоянии, а дескриптор связывается с данными того или иного процесса. Пример: схема диспетчеризации UNIX: Каждая строка таблицы процессов является дескриптором. В каждом дескрипторе содержится малая часть всей информации, а главное в дескрипторе – это адресная ссылка на область данных пользователя. В этой области содержится таблица пользователя, которая фактически является продолжением дескриптора. Таблица пользователя содержит то, что называется контекстом процесса (полный перечень информационных групп). Связывание дескриптора с областью данных имеет два плюса: 1. диспетчер работает с короткими информационными структурами; 2. т.к. область пользователя никому не доступна, то данные дескриптора являются защищёнными. Пример: диспетчеризация в Osx370 Супервизор задач содержит несколько управляющих компонент: см. рисунок. Эти структуры работают с двумя очередями: готовности и ожидания. Процессы циркулируют между этими очередями. Выборку из очереди готовности осуществляет диспетчер задач. Структура данных Osx370 Основным элементом является очередь готовности, в которой находятся TCB (Task Control Block) – дескрипторы. Текущий блок отслеживается CVT – указателем текущей задачи. Каждый из дескрипторов имеет ссылку на список блоков запросов RB. CDE (Contents Directory Entry) – справочники содержимого – информация о том, чем заполнена выделенная память. SPQE (Sub Pool Queue Element) – элементы очереди подпулов. Подпулы – это кусочки ОП, которые образуют наборы пулов. ECB (Event Control Block) – блоки управления событиями создаются, когда какой-то процесс, входящий в состав задачи, ожидает события. 5° Параллельные процессы 02.11.2000 это процессы, находящиеся в ОС, но не обязательно все активные. Если система многопроцессорная, то активными могут быть сразу несколько процессов – физически параллельные. Среди нескольких процессов всегда выделяется главный, который управляет ресурсами и т.п. Современные языковые средства позволяют обрабатывать параллельные процессы (Modula, Ada, модификация Pascal). 1 управляющие конструкции параллельных процессов Рассмотрим классическую задачу: нахождение корней квадратного уравнения. x := (- b  (b  2 – 4  a  c)  0.5) / (2  a) Последовательный алгоритм: 1. t1 = b  2 7. t7 = t6 + t5 2. t2 = 4  a 8. t8 = 2  a 3. t3 = t2  c 9. t9 = t7 / t8 4. t4 = t1 – t3 5. t5 = t4  0.5 6. t6 = - b В алгоритме есть шаги (1, 2, 6, 8), которые друг от друга не зависят, и они могут быть выполнены параллельно. Формально это обозначается так: Операнд1; Операнд2; Операнд3; – последовательная часть … операнд n; parbegin операнд m; операнд m + 1; – параллельная часть … parend При таком формализме алгоритм имеет вид: parbegin t1 = b 2; t2 = 4  a; t6 = - b; t8 = 2  a; parend t3 = t2  c t4 = t1 – t3 t5 = t4  0.5 t7 = t6 + t5 t9 = t7 / t8 2 Критические участки Пример: есть информационная система, которая обслуживает в режиме разделения времени множество терминалов. С каждого терминала производится ввод данных. Введённые данные подсчитываются, причём для каждого терминала существует свой процесс, который учитывает введённые данные. “Учётчик” LOAD число введённых строк ADD 1 STORE число введённых строк Т.е. каждый терминал учитывает, сколько строк введено. Пусть развиваются 2 процесса параллельно и независимо: Произошло искажение переменной 4ВвСтр. Это произошло потому, что оба процесса работают с разделяемым ресурсом (в данном случае – это 4ВвСтр). Существуют такие участки, когда процессы могут взаимодействовать (т.е. возможны всякие неприятности), они называются критическими. Следовательно, главной проблемой параллельного программирования будет выявление критических участков и недопущение попадания двух и более процессов на критические участки. Такое недопущение называется ситуацией взаимоисключения. 3 Примитивы взаимоисключения Под примитивами понимаются какие-то программы, модули, которые рассматриваются как какие-то неразделимые кусочки, и выполняют определённые функции. Примитив взаимоисключения (В) – такая конструкция, которая должна обрамлять критический участок и обеспечивать непопадание нескольких процессов на этот критический участок. Продолжаем пример: Program ВИ Var 4ВвСтр; Procedure Процесс1 While (.t.) do Begin Ввод очередной строки; Вход_В; /* примитив В */ 4ВвСтр := 4ВвСтр +1; /* критический участок*/ Выход_В; /* примитив В */ Обработка остальной части строки; End; Procedure Процесс2 While (.t.) do Begin Ввод очередной строки; Вход_В; 4ВвСтр := 4ВвСтр +1; Выход_В; Обработка остальной части строки; End; Parbegin Процесс1; Процесс2; Parend. Реализация примитивов должна быть не аппаратной, а программной. Не должно быть никаких предположений о скорости выполнения параллельных процессов. Процессы, которые находятся вне своих критических участков, не должны препятствовать другим процессам входить в их критические участки. Не должно быть бесконечного откладывания момента входа процесса на критический участок. 4 Алгоритмы Деккера представляют собой различные варианты программной реализации примитивов взаимоисключения. 1) Ситуация В реализуется с помощью специальной переменой – №_процесса. Program ВИ1 Var №_процесса; Procedure Процесс1 While (.t.) do Begin Предоперации процесса1; While (№_процесса = 2) do; /*вход В*/ Критический_участок; №_процесса = 2; /*выход В*/ Постоперации процесса1; End; Procedure Процесс2 While (.t.) do Begin Предоперации процесса2; While (№_процесса = 1) do; /*вход В*/ Критический_участок; №_процесса = 1; /*выход В*/ Постоперации процесса2; End; №_процесса := 1; Parbegin Процесс1; Процесс2; Parend. Здесь процессы находят свои критические участки строго по очереди – это жёсткая синхронизация. Она рекомендуется, когда процессы хорошо согласованы друг с другом. Недостаток: если один из процессов “умирает”, то вместе с ним исчезает и критический участок. Следовательно, схема перестаёт работать (оставшийся процесс просто виснет). 09.11.2000 2) Синхронизация с помощью 2-х переменных: флаги – процесс1_внутри, процесс2_внутри Program В2 Var процесс1_внутри, процесс2_внутри : логический; Procedure процесс1 Begin While (.t.) do Begin Предоперации1; While(процесс2_внутри) do; Параллельный цикл активного ожидания; Процесс1_внутри := .t.; Войти в критический участок процесса1; Процесс1_внутри := .f.; Постоперации1; End; End; Procedure процесс2 Begin While (.t.) do Begin Предоперации2; While (процесс1_внутри) do; Параллельный цикл активного ожидания; Процесс2_внутри := .t.; Войти в критический участок процесса2; Процесс2_внутри := .f.; Постоперации2; End; End; Begin Процесс1_внутри := .f.; Процесс2_внутри := .f.; Parbegin Процесс1;процесс2; Parend; End. Слабое место здесь в том, что между моментом, когда процесс определяет, что он может идти дальше, и моментом, когда он устанавливает флаг, проходит достаточно времени, чтобы второй процесс успел выйти на критический участок. 3) Схема с опережением: Во втором пункте действуем по схеме: проверка условия – установка флага; Здесь шаги меняют местами: установка флага – проверка условия и отказ при необходимости. Program В3 Var п1хочет, п2хочет: логический; // хочет войти на критический участок Procedure П1 Begin While (.t.) do Begin Предоперации1; П1хочет:= .t.; While (П2хочет) do; Критический участок1; П1хочет:= .f.; Постоперации1; End; End; Procedure П2 Begin While (.t.) do Begin Предоперации2; П2хочет:= .t.; While (П1хочет) do; Критический участок2; П2хочет:= .f.; Постоперации2; End; End; Begin П1хочет:=П2хочет:=.f.; Parbegin П1; П2; Parend; End. Интервал ловушки снизился. Если каждый процесс перед входом в цикл активного ожидания будет устанавливать свой флаг, то это будет препятствовать выходу из активного ожидания другого процесса. Такой особый случай взаимной блокировки называется тупиком. Если добавить в алгоритм разрешающее правило, которое будет действовать только в том случае, если возникла ситуация взаимной блокировки, то тупика можно избежать: 4) Вход В: (П1) П1хочет := .t.; While (П2хочет) do If (указатель процесса = 2) then Begin П1хочет:=.f.; While (указатель процесса = 2) do; П1хочет:=.t.; End; Выход В остаётся без изменения; П1хочет:=.f.; указатель процесса := 2; Program В4 Var указатель процесса : 1,2; П1хочет, П2хочет : логический; Procedure П1; Procedure П2; Begin П1хочет := П2хочет := .f.; указатель процесса := 1; // или 2 Parbegin П1; П2; Parend; End. При возникновении тупика включается механизм жёсткой синхронизации. 5) Использование специальных семафорных переменных Одним из способов организации В является использование специальных семафорных переменных (Дейкстра). Семафор (S) – специальная защищённая переменная: значения этой переменной можно опрашивать и изменять только с помощью специальных операций: P(S) – запрос; W(S) – освобождение. Семафоры условно делятся на двоичные (0,1) и считающие (0,1,2,…(целые неотрицательные)). P(S): если S > 0, то S:=S – 1 иначе ожидать S; W(S): если (1 или несколько процессов ожидают S), то (разрешить продолжиться одному) иначе S:=S + 1. С помощью этих операций можно организовать примитивы В. Для этого необходимо окружить операциями P и W критический участок. Program Semaphor Var S: семафор; Procedure П1 Begin While (.t.) do Begin Предоперации1; P(S); Критический участок1; W(S); Постоперации1; End; End; Procedure П2 Begin While (.t.) do Begin Предоперации2; P(S); Критический участок2; W(S); Постоперации2; End; End; Begin Инициализация S:=1; Parbegin П1; П2; Parend; End. При таком алгоритме синхронизация будет осуществляться для любого числа параллельных процессов. Главным является неделимый характер операций P и W – во время их выполнения не должно возникать прерываний, т.е. нужно потребовать, чтобы P и W выполнялись в системном режиме, когда прерывания запрещены; их можно реализовать и программно, и аппаратно. Основное назначение семафоров – синхронизация и организация взаимодействия процессов. 16.11.2000 5 Задача синхронизации 2-х процессов Синхронизация нужна, когда процессы связаны, но несильно: они независимы друг от друга, но иногда, например, Пр1 использует часть результатов Пр2. это можно изобразить так: Program Synchro Var S: семафор; Procedure Пр1 Begin Предоперации1; P(S); // запрос семафора S Постоперации1; End; Procedure Пр2 Begin Предоперации2; V(S); Постоперации2; End; Begin Инициализация S:=0; Parbegin Пр1; Пр2; Parend End. Взаимодействие процессов должно быть как-то санкционировано. Классической является задача “синхронизации пара «производитель – потребитель»”. Есть 2 процесса: Через буфер (специальную структуру данных) осуществляется взаимодействие этих процессов. Но при разноскоростных производителе и потребителе возникают проблемы: – быстрый производитель может несколько раз заполнить буфер прежде, чем медленный потребитель прочтёт его  потеря информации; – быстрый потребитель может несколько раз опустошить буфер прежде, чем медленный производитель заполнит его  дублирование информации. Смысл синхронизации состоит в том, чтобы данные не терялись и не дублировались. Здесь вводятся 2 семафора: Sd – семафор доступа – необходим для доступа к разделяемому ресурсу (буферу) в режиме взаимоисключения; Si – семафор информационный – необходим для синхронизации процессов. Program Synchro_PU Var Sd, Si: семафор; Buffer: int; // буфер на одно число Procedure Priduce Var Res: int; Beign While (.t.) do Begin Вычисление следующего результата; P(Sd); Buffer := Res; V(Sd);V(Si); End; End; Procedure Use Var Res: int; Beign While (.t.) do Begin P(Si); P(Sd); Res := Buffer; V(Sd); Вывод (S); End; End; /*работа*/ Begin Sd := 1; Si := 0; Parbegin Produce; Use; Parend End. 6 Мониторы Недостатки взаимоисключения и синхронизации: программируемые, они предоставлены в распоряжение пользователю и нет гарантии, что все эти механизмы будут работать правильно. Монитор – это специальная утилита высокого уровня, которая решает проблемы взаимоисключения, синхронизации и аналогичные. Смысл монитора: с одной стороны – упрощение решений проблем параллелизма; с другой – чтобы их было бы невозможно неправильно использовать / испортить с помощью программных средств. Монитором в ОС называется процедура организации параллелизма, которая содержит данные и процедуры, необходимые для динамического распределения общего ресурса  “монитор ресурса”. Чтобы обратиться к монитору, процесс должен осуществить процедуру ВХОД_В_МОНИТОР. Но эта процедура находится под контролем самого монитора, и монитор позволяет осуществить вход только одному процессу, а остальным процессам выдаётся отказ, что переводит процессы в состояние ожидания, причём процессы ожидают вне монитора. Очередь организуется средствами ОС. Но монитор управляет процессами в очереди ожидания, т.е. по мере освобождения ресурса, он оповещает очередь и один из процессов очереди может осуществить вход в монитор. Работа монитора основана на двух функциях: 1. реализует команду ожидания – WAIT (); смысл состоит в том, чтобы перевести процесс в состояние ожидания; 2. реализует команду SUGNAL ();смысл состоит в том, чтобы оповестить очередь о том, что кто-то из очереди может её покинуть и осуществить вход в монитор. И 1, и 2 связаны с определённой очередью. Попадание или выход из очереди связано с условием: свободен ресурс или занят. Это условие свели в одну переменную – переменную-условие. Переменная-условие – переменная специального типа, которая является структурой типа очередь. Когда эта переменная определяется, то заводится соответствующая очередь с указателями, своей дисциплиной обслуживания. Поэтому: WAIT (переменная-условие) и SUGNAL (переменная-условие). Monitor Распределитель Ресурсов Var ресурс_занят: логическая; ресурс_свободен: переменная-условие; Procedure Захват_ресурса Begin If (ресурс_занят) then WAIT (ресурс_свободен); End; Procedure Возврат_ресурса Begin ресурс_занят := .f.; SIGNAL (ресурс_свободен); End; Begin ресурс_занят := .f.; End. Использование монитора: Program Synchro Monitor PP Parbegin P1: S1, S2;…; PP (Захват_ресурса); Sk,…; PP (Возврат_ресурса);Sn,…; P2: T1, T2;…; PP (Захват_ресурса); Tk,…; PP (Возврат_ресурса);Tn,…; Parend. 7 Тупики Состояние тупика наступает, когда процессы ожидают событий, которые никогда не могут произойти. Причиной тупика является работа с разделяемым ресурсом. Рассмотрим P1, P2, которые работают с ресурсами D, Т в монопольном (неразделяемом) режиме. Это значит, что процесс запрашивает и освобождает ресурс, и после запуска и до освобождения этот ресурс недоступен. Если P1: … request(D) … request(T) … release(T) … release(D) P2: … request(T) … request(D) … release(T) … release(D), То в момент, когда либо request(T), либо request(D), наступает состояние взаимной блокировки. 23.11.2000 Проблемы, которые необходимо решить: 1. образование/предотвращение; 2. обнаружение; 3. обход; 4. ликвидация. Их легко решить на ПК. В многопользовательских системах необходим какой-то интеллект, который обнаруживает состояние взаимной блокировки. После диагностики необходимо либо обойти (т.е. изменить какие-то условия), либо ликвидировать это состояние. Необходимые условия образования тупиков Коффмана: Смысл: если они выполняются, то может образоваться тупик. 1. условие взаимоисключения: процессы требуют право монопольного управления выделяемыми ресурсами; 2. условие ожидания ресурса: ожидая дополнительного ресурса, процесс удерживает за собой уже выделенные ресурсы; 3. условие неперераспределения: ресурс нельзя отобрать у процесса до тех пор, пока ресурс не будет использован в связи с завершением процесса; 4. условие кругового ожидания: существует кольцевой граф, вершинами которого являются процессы и ресурсы, в котором каждый процесс использует, по крайней мере, один ресурс, используемый и следующим процессом в цикле. Способы решения образования тупиков: все они базируются на том, что создаются условия, гарантирующие невыполнение одного из необходимых условий Коффмана. Но все методы сводятся к тому, что будет снижаться производительность системы. Обнаружение тупиков – сложная задача ~ распознаванию образов (AI). Системы обнаружения строятся на основе моделирования: сначала проверяют существующие ресурсы и процессы и строят матрицу использования, в которой ищутся пути, образующие кольца – критические пути, где возможны тупики. П1 П2 D T П1 - 0 1 1 П2 0 - 1 1 D 1 1 – 0 T 1 1 0 - После обнаружения  ликвидация. Стандартный способ: Restart. Другой способ: разомкнуть цепь, уничтожив один из процессов. Определяют процесс, который порождает самое большое количество кольцевых ситуаций, и его уничтожают. Тогда, может быть, тупик ликвидируется. §5 Управление памятью 1 Физическая память может быть представлена в виде нескольких классов: 1. ЗУ – кэш память; 2. RAM – оперативная память; 3. внешняя память. Между этими видами памяти циркулирует информация (32123). Эти виды отличаются по: – времени … (min1, max3); – стоимости (min3, max1); – размеры (min1, max 3). ОС управляет обменами между 2 и 3 (менеджер памяти, система управления вводом-выводом). Управление обменом между 1 и 2 осуществляется ЦП. Организация памяти отвечает за:  размещение в памяти одной или нескольких программ;  организацию обменов 2 – 3.  реализуется с помощью так называемых разделов RAM, т.е. областей, содержащих коды и данные, относящиеся к одному процессу. Эти разделы могут быть защищёнными/незащищёнными, один/много, сплошными/непрерывными. Проблемы : как соответствующий раздел оказался в ОП: заранее или по опросу, т.е.: – время размещения; – место размещения (какой раздел должен быть использован); – замещение (какой из разделов должен быть уничтожен при создании нового раздела). Эти проблемы группируются в стратегии управления памятью. Существуют такие стратегии: 1. связанное однопользовательское распределение; 2. многопользовательское с фиксированными или переменными разделами (MFT/MVT); 3. страничное, сегментное и комбинированное распределение. 2 Связанное однопользовательское распределение это простейшее распределение – достоинство. Эта стратегия характеризуется тем, что RAM выделяет какую-то часть под ОС, а остальное – это пользовательский раздел. Если этот раздел больше, чем надо пользователю, то остаётся неиспользуемое пространство. Если размеры пользовательского раздела меньше, чем требуется пользователю, то либо отказываются от выполнения этой задачи, либо используется оверлейная организация (менеджер оверлея): Защита памяти – защита ОС от несанкционированного воздействия, т.е. необходимо развязать пользовательский раздел и раздел ОС. Для этого используется метод граничного регистра: в CPU выделяется граничный регистр, в котором содержится адрес границы между разделами ОС и пользователя. И процессор должен блокировать обращение к памяти по адресам, значения которых (в данном случае) меньше значения граничного регистра. Как пользовательский раздел может получить доступ к ОС? Обращение к ОС должно происходить с помощью прерываний. 3 Многопользовательское распределение с несколькими разделами – необходимое условие при организации мультипрограммной обработки. В OS/360 – это MFT – мультипрограммное распределение с фиксированным числом задач. Схема: Для этих разделов создавалась очередь, где происходит загрузка и связывание. Эта система удобна малыми расходами по поддержанию многозадачного режима. Недостаток: какая-то из очередей оканчивается ничем, тогда этот раздел оказывается неиспользованным; процесс из одной очереди нельзя перекинуть в другую. В OS/360 разделы создаются так: 1-й самый маленький (наибольший приоритет); 2-й средний по размерам; 3-й самый большой. Защита: 30.11.2000 Можно также использовать метод граничного регистра. Необходимо с каждым разделом в области ОС связать таблицу разделов, в которой для каждого раздела указаны нижняя и верхняя границы. Если выбран какой-то раздел, то из таблицы разделов в регистры CPU записываются значения нижней и верхней границ. И процессор отслеживает значение программного счётчика: LGRg> реальном R. Т.е. главной идеей является распределение адресов. При выполнении процессов выборка данных производится из реальной памяти, поэтому должен существовать механизм динамического преобразования адресов виртуальных в реальные. Этот механизм называется DAT. Т.е. смежные в VS ячейки могут оказаться несмежными в R. Главное условие – существование механизма отображения, кот должен отвлекать минимум системных ресурсов. Обычно копии ячеек VS хранятся на внешнем устройстве и какая-то часть этих ячеек – в R. Существуют таблицы отображения, которые показывают, что находится во внешней памяти, а что в динамической физической памяти. Каковы единицы VS и отображаемой R? С точки зрения процессов: размер ячеек = размерам единиц обрабатываемой информации (байт, слово). Чем меньше единица, тем больше таблиц отображения. Поэтому ячейки надо выбирать покрупнее. Но очень большие ячейки потребуют большого времени на операцию обмена с внешней памятью. Компромисс находится из удобства для работы с внешними устройствами и для процесса. Отображаемые блоки могут быть: – одинакового размера – страничная организация; – размеры блоков отвечают потребности процесса – сегментная организация. Существует странично-сегментная организация памяти. VS-поблочное отображение Если используется поблочное отображение, то виртуальные адреса из одномерных плоских становятся двумерными. Виртуальный адрес содержит 2 компоненты: № блока и смещение внутри блока (V=(b,d)). Этот виртуальный адрес V должен быть преобразован в адрес реальной памяти r. Преобразование адресов происходит по схеме: Каждый процесс должен хранить таблицу отображения блоков (ТОБ). В ней с каждым блоком связывается строка, которая увязывает № этого блока и адреса начала этого блока в физической памяти. В этой строке может находиться и дополнительная информация. Адрес начала ТОБ должен храниться в регистре начального адреса ТОБ. b' – адрес блока в оперативной памяти. Важно: трансляция логических адресов в физические должна производиться динамически во время выполнения процесса, поддерживаться на уровне аппаратных средств. В зависимости от содержания ТОБ существуют различные схемы организации виртуальной памяти. Страничная организация 7.12.2000 Похожа на распределение памяти с несколькими разделами, а именно, когда все разделы одного размера (MFT). Логическое пространство процессора содержит страницы, а оперативная память содержит страничные кадры. И виртуальный адрес, указывающий № страницы (p) и смещение относительно страницы (d), должен быть преобразован в реальный адрес, который указывает № страничного кадра (p') и смещение относительно страницы (d). Эта схема определяет формат таблицы преобразования адресов (ТПА). Строка ТПА должна содержать: № страницы (p), соответствующий № страничного кадра (p') и адрес этого кадра в ОЗУ (S). Но не все страничные кадры могут находиться в оперативной памяти, часть их может находиться во внешней памяти. Поэтому в ТПА вводят признак r, который показывает присутствие/отсутствие кадра в ОЗУ (r=0 – есть, r=1 – нет). Тогда S может быть либо реальным адресом в ОЗУ, лбо адресом кадра во внешней памяти. Если при обращении к таблице установлено, что S в ОП отсутствует, то менеджер виртуальной памяти должен генерировать соответствующее страничное прерывание и обработчик прерывания должен извлечь страницу из внешней памяти, разместить её в оперативной памяти и скорректировать её соответствующим образом в ТПА. Организация преобразования pp': существует несколько способов отображения:  прямое отображение основывается на таблице, содержащей по одной строчке на виртуальную страницу. В этой строчке содержится № страничного кадра, и вся таблица страниц хранится в оперативной памяти, а её начальный адрес грузится в специальный регистр. РИС.1  ассоциативное отображение. Характеристикой  является то, что обращение к памяти преобразуется в 2 обращения: обращение к таблице и ещё одно обращение. Т.е. скорость доступа снижается в 2 раза. Если разместить таблицу отображения страниц в сверхоперативной памяти (КЭШ, ассоциативной), то можно сэкономить одно обращение к памяти. Особенностью КЭШ памяти является одновременное обращение ко всем данным. РИС.2 Размеры ассоциативной памяти очень маленькие по сравнению с оперативной памятью. Возникает вопрос какие из страниц можно удалять? Практика показала, что не все страницы одинаково популярны. Поэтому используется третий способ отображения.  ассоциативно-прямое отображение: наиболее популярные страницы хранятся в ассоциативной памяти, а полная таблица отображения – в ОЗУ. РИС.3 Если полная таблица страниц состоит из  100 строк, а ассоциативная таблица – из  8 10 строк, то такое обращение обеспечивает 90% быстродействие по сравнению с чисто ассоциативным. Использование страничного механизма позволяет по-новому организовать доступ к информационным ресурсам (память). Главная проблема, с которой можно столкнуться: если несколько пользователей одновременно обращаются к одному разделяемому ресурсу, то надо, чтобы они не конфликтовали и действительно обращались к одному ресурсу. Но для страничной организации этой проблемы не существует. Доступ каждого процесса описывается своей таблицей страниц, и каждая таблица страниц может ссылаться на один и тот же страничный кадр. Но здесь возникают другие проблемы. Например, проблема синхронизации. Сегментная организация Эквивалентна MVT. Сегментная организация призвана спланировать страничный кадр такого размера, который соответствовал бы заявке процесса. Сегментная адресация является двумерной, т.е. виртуальный адрес содержит сегмент и смещение внутри сегмента V=(S, d). Размеры сегмента устанавливаются операционной системой в соответствии с запросом процесса. РИС.4 Отображение SS' требует следующего содержания таблицы сегментов: логический № сегмента S, физический адрес в ОП S', признак присутствия/ отсутствия в ОП r. Кроме этого вносят характеристики, обеспечивающие защиту памяти: l – длина сегмента; предположим, что при d>l обращение блокируется. m – маска, в которой устанавливаются условия доступа, которые описываются битовой комбинацией флагов, например, вводится маска из четырёх флагов: R – действие с сегментом – операция чтения; W – сегмент можно модифицировать; E – сегмент можно выполнять; A – допускает добавление в конец сегмента. Например, m = 0000 = 0 – полная защита сегмента (запрет всех действий); m = 0010 = 2 – разделяемый ресурс (можно только выполнять); m = 1111 = F – доступ без ограничений (полностью незащищённый сегмент); m = 1000 = 8 – информационный сегмент (можно только читать). В разных ОС разные масочные комбинации. Алгоритм доступа V(S, d)  R(S', d): 1) по виртуальному адресу сегмента находится соответствующая строка таблицы S  < r, l, m, S' >; 2) проверка наличия сегмента в ОП: r = 1 – есть – дальше; r = 0 – нет – сегментное прерывание (какого сегмента не хватает); 3) сравнить d и l: d < l – дальше; d > l – прерывание по защите памяти (выход за границы); 4) проверка прав доступа: mпроцесса <> M : соответствует – S'  R = S' + d; не соответствует – прерывание по защите (попытка нарушения доступа). Здесь также можно организовать доступ к разделяемым ресурсам. Недостаток: разные размеры сегментов, которые затрудняют операции обмена с периферийными устройствами. Комбинированная сегментно-страничная организация Здесь должна поддерживаться иерархия таблиц. Её можно изобразить так: Рис.5 Обращение любого процесса к данным превращается в 3 обращения. Используя комбинации ,  и , можно добиться приемлемых параметров доступа к данным. Вопросы 1. понятие о системном и проблемном ПО. Основные режимы организации работы ВС. 2. назначение ОС. ОС с точки зрения системного программиста и пользователя. 3. ОС: основные принципы построения, определение основные функции. 4. процесс в ОС. Классификация процессов. Состояние процесса. Задача ОС по управлению процессами. 5. ресурс с точки зрения ОС. Классификация ресурсов. 6. механизм прерываний и его использование для управления процессами. 7. концепция виртуализации в построении ОС. 8. реализация управления процессами с помощью БУП (PCB). 9. функции ядра ОС. 10. 2-х уровневая система управления процессами. Содержание долгосрочного и краткосрочного планирования. 11. параллельные процессы. Управляющие конструкции для описания параллелизма. 12. примитивы взаимоисключения, их реализация в алгоритмах Деккера. 13. семафоры и их применение для организации взаимоисключений. Синхронизация пары ПРОИЗВОДИТЕЛЬ – ПИТРЕБИТЕЛЬ. 14. монитор как средство организации взаимоисключений. 15. тупики в мультипрограммных системах. Необходимые условия их образования. 16. иерархия памяти. Задача ОС по управлению памятью. 17. связное однопользовательское распределение. Защита памяти. 18. распределение с фиксированным числом разделов. Фрагментация памяти. 19. распределение с переменным числом разделов. "Сборка мусора". 20. организация виртуальной памяти в ОС. 21. страничная организация памяти. 22. сегментное распределение. Управление доступом при сегментном распределении. 23. стратегия управления виртуальной памятью. Выталкивание страниц. 24. комбинированное странично-сегментное распределение.