Geum.ru

Петербургский Университет Телекомунникаций им проф. Бонч-Бруевича курс лекций

Вид материалаКурс лекций

Содержание


4.1. Выгоды многозадачности и многопроцессности
Стратегия планирования.
Delay()  p1
Подобный материал:
1   2   3   4   5   6   7   8   9   10   11

4.1. Выгоды многозадачности и многопроцессности


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

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

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

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

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

Теоретически можно возложить задачу распараллеливания на пользовательскую программу - так поступают некоторые разработчики программ реального времени для MS DOS или в некоторых кросс-системах.

Однако многопроцессность создает ряд специфических проблем, и оказывается целесообразным реализовать решения этих проблем один раз, собрать код, решающий их, в единый модуль и объявить этот модуль ядром ОС. Именно таким образом построено ядро систем RT-11, OS-9 и ОС, базирующихся на технологии микроядра (microkernel) - QNX, UNIX System V R4, HURD.

В других ОС в ядро помещен также код, занимающийся работой с внешними устройствами, и даже менеджеры файловых систем. Такие системы сейчас называются «монолитными». Выгоды и недостатки обоих решений будут обсуждаться ниже. 4.2. Проблемы при параллельной работе


Первой из проблем является проблема разделения ресурсов. Действительно, представим себе две программы, пытающиеся печатать что-то на одном принтере. Если они будут делать это произвольным образом, их вывод на бумаге будет перемешан и скорее всего окажется совершенно нечитаемым. Одним из разумных решений может быть монопольный захват принтера одной из программ. При этом другая программа будет вынуждена ждать, пока принтер не освободится. Значит, нужны средства для захвата ресурсов и ожидания их освобождения17. Другая проблема - это проблема реентерабельности (reenterability - повтоpной входимости, от re-enter) разделяемых программ.

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

Существует техника реализации этого модуля, при которой такой вызов не создаст никаких проблем. Такая техника состоит в том, что все данные, с которыми работает разделяемая программа, хранятся в ее локальных переменных. Для каждой инкарнации программы создается собственная копия таких данных. Такое требование легко выполняется для функций, не имеющих побочного эффекта, таких как вычисление синуса или поиск символа в текстовой строке. При других техниках программирования могут возникнуть серьезные проблемы, вплоть до развала системы. Модули, которые можно вызывать многократно, называются реентерабельными. Соответственно программы, которые так вызывать нельзя, называются нереентерабельными. Типичный пример нереентерабельной программы - ядро дисковой операционной системы MS DOS.

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

Во многих случаях оказывается выгодно рассматривать нереентерабельную программу как разделяемый ресурс и распределять доступ к нему теми же способами, что и к принтеру. Так поступает большинство известных авторам средств организации параллельной работы под MS DOS. Таким же образом микроядро организует доступ пользовательских программ к модулям ОС.

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

Первая, самая простая из них, состоит в вопросе - если одна задача производит данные, а вторая их потребляет, то как задача-потребитель узнает, что готова очередная порция данных? Или, что еще интереснее, как она узнает, что очередная порция данных еще не готова? Типичный случай такого взаимодействия - асинхронное чтение с диска, когда программа дает дисковому драйверу запрос: «читай с такого-то сектора в такой-то блок памяти», и продолжает заниматься своими делами. Это режим работы, поддерживаемый всеми ОС линии RT-11 - RSX-11 - VAX/VMS - OpenVMS и многими системами реального времени.

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

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


Процесс – подпрограмма, поступившая на уровень ядра ОС.


2 аспекта процесса:

а) теоретический;

б) практический.


а) Первый аспект – по Хоару: процесс+<событие>процесс+<событие>…;

По Крыковяку процесс – некоторая траектория:






Е

Параллельные процессы

сли  процесс последовательный.


- время квантования

Если  последовательные процессы

Если  параллельные процессы



б) Второй аспект;


OS/2  OS/380, OS/400 (ОС для больших ЭВМ)

  • сеанс;


Менеджер сеанса

Как только заканчивается сеанс – заканчиваются и все процессы этого сеанса





Пр. 1

Пр. 2

Пр. N

…



  • синхронизация и взаимодействие;
  1. процедура запуска одного процесса у другого;
  2. порождение нового процесса как самостоятельного.
  • самый высокий уровень, позволяющий делить задачу на куски, которые могут выполняться параллельно.


Состояния процессов.


В любой ОС процессы могут быть:
  1. активными;
  2. пассивными (куда входят готовые к выполнению и ожидающие).


пассивные


готовые



активные





ожидающие







Структурная схема ядра.

Очередь блокирования





планировщик













Очередь готовых



диспетчер

процессор




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

Реентерабельность – повторная входимость.

Если критический ресурс – программный код (подпрограмма), то все просто (создаются ее копии).

А если критический ресурс – физическое устройство, то здесь могут возникнуть проблемы.

Также реентерабельными могут быть и прерывания (как DOS, так и BIOS). Здесь тоже могут возникнуть серьезные трудности.

Метод взаимного исключения – если программа работает с критическим участком, то она работает с ним до самого конца, и никакая другая программа ей не может помешать. Следовательно, этот метод работает против систем разделения времени.

Диспетчер решает вопрос об очередности активности процессов. Иными словами, занимается переключением задач по времени.

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

На уровне пользователя решается вопрос о том, какие процессы необходимо запускать.


Стратегия планирования.

  1. без переключения контекста или выполнения до конца;
  2. с переключением (близко к разделению времени);

а) с постоянным шагом (размер тика не меняется);

б) с переменным шагом (размер тика меняется, соответственно).


Смена размера тика необходима, в частности, при использовании приоритетов.

  1. с приоритетом;

а) постоянный;

б) динамический.


Значения очередей следующее:
  • позволяет упорядочить доступ к ресурсам в режиме FIFO (с учетом приоритетов);
  • позволяет обращаться к процессам на абстрактном уровне.


Содержание дескриптора процессов:
  1. имя процесса;
  2. состояние ЭВМ (все регистры, состояния памяти процесса);
  3. данные о состоянии процесса (т.е. он готовый, активный или блокированный);
  4. данные для планирования (указ_очередь, в которой находится процесс, указ_на_сам_проц, указ_след_проц, указ_пред_проц);
  5. сведения о потомках и родителях (сведения о том, из какого процесса был запущен данный процесс и для какого из процессов он является родителем).


Ядро управляется 2-умя способами:
  1. прерываниями (с физического низкого уровня);
  2. примитивами (с высокого уровня).


Примитивы ядра.


Примитивы могут быть 3-ех уровней:
  1. управление процессами;
  2. примитивы синхронизации;

а) простейшая синхронизация;

б) временная (задержка для многозадачного режима);

в) событийная (по событию).
  1. примитивы обмена сообщений;

а) примитивы для синхронизации быстрых и медленных устройств;

б) процесс обмена информации между собой (почтовый ящик).


Все примитивы пишутся по одной и той же схеме:

Начало
  1. пролог; сохранение контекста активного и вхождение в критический участок
  2. контроль; проверка прав и параметров

<тело примитива>
  1. выделение процесса; переключение контекста


Примитивы управления процессами:
  • создать процесс;
  • уничтожить процесс.


Создать процесс:
  1. пролог;
  2. контроль;
  3. создать дескриптор;
  4. включить в очередь;
  5. переназначить.


Уничтожить процесс:
  1. пролог;
  2. контроль;
  3. извлечь из очереди;
  4. разрушить дескриптор;
  5. переназначить.


Эта схема не годится в случае удаления активного процесса, т.к. это опасно. Поэтому рассмотрим другой вариант:


Уничтожить процесс:
  1. пролог;
  2. контроль;
  3. извлечь из очереди;
  4. включить в очередь удаления;
  5. переназначить.


а) специальный процесс (демон);

б) в обработчике прерываний.


Обработчик прерываний:

Начало

Очистить очередь удаления

Переключение контекста

Конец


Простейшая синхронизация;

А
отладка
) отсрочить выполнение

Б) возобновить выполнение


Отсрочить выполнение:
  1. пролог;
  2. контроль;
  3. извлечь из очереди;
  4. включить в очередь приостановленных;
  5. переназначить;


Возобновить выполнение:
  1. пролог;
  2. контроль;
  3. извлечь из очереди приостановленных;
  4. включить в очередь готовых;
  5. переназначить.


Временная синхронизация;


DELAY()  P1


Участок активного ожидания

Недостатки:
  • простаивание процессора;
  • коллизии с обработчиком прерываний по таймеру.







К этому надо бы добавить:

+ реализация режима пассивных ожиданий;

+ избавление от иллюзии, связанной с обработчиком прерываний.


Постановка

указ дескриптор





















T=Tn+t






















Функцию возвращения из очереди удаляемых берет на себя обработчик прерываний.


Событийная синхронизация;


1) Латентность – скрытность (например, заболевания).




P1

P2


CLI

CLI


Критический участок

За это время система должна быть латентной



STI

STI


t << тик

2)Маскирование (запрет отдельных прерываний).

Маскирование используется для того, чтобы выделить в анализируемом значении указанные биты и сделать навидимыми остальные.

Микросхема PIC  20h, 21h, 22h (через порт 21h фактически и происходит маскирование)


Например, хотим запретить прерывание клавиатуры:

mov al, 00000010b

out 21h, al

  1. Режим взаимного исключения;

Монитор – объект, содержащий:
  • множество переменных (отражающих состояния системы);
  • множество функций (функции изменения переменных).



  1. Когда процесс получает доступ к ресурсу, то это влияет (приводит к) на изменение состояний системы.
  2. Когда процесс запрашивает ресурс через монитор.


Монитор “знает” состояния системы и владеет функциями, способными их изменить, может предоставить этот ресурс либо отказать процессу.

  1. Монитор работает в режиме взаимного исключения (ВИ).


0, критический участок свободен

FLAG =

1, критический участок занят


M: если FLAG = 1, то идти к М


Критический участок

FLAG = 0

Недостатки:
  • такая схема (3) приводит к режиму активного ожидания, т.е. режиму, при котором ожидаются ресурсы процессора;
  • нарушение принципа FIFO;
  • FLAG – тоже общий ресурс  к нему тоже можно осуществить доступ.


Отсюда видно, что эта схема практически неприемлема, а если и приемлема, то безграмотна.

Попробуем ее немного улучшить (попробуем устранить последний недостаток):


M: mov ax, 1


Режим блокировки шины




lock xchg ax, FLAG

Cmp ax, 1

Jz M


Критический участок

FLAG = 0


Семафор Дейкстры (устраняет все 3 недостатка):


Семафор – объект, который состоит из:
  • счетчика семафора;
  • очереди семафора;
  • 2-ух функций семафора (захват семафора, стоящий перед критическим участком и освобождение семафора, стоящий после критического участка).


Захват_семафор()

CLI

DEC счетчик семафора (если счетчик семафора < 0, то дескр_проц отправляется в очередь семафора)

STI

Освоб_семафор()

CLI

INC счетчик семафора (если счетчик семафора <= 0, то дескр_проц, стоящий в очереди семафора 1-ым, отправляется в критический участок)