Реклама
SNT.su - http://snt.su/detskie-elektromobili/.
Спонсорские ссылки
-
Статья
Версия для печати
Обсудить на форуме (11)
Организация совместного доступа к ограниченным ресурсам


(C) Dale, 25.10.2010 - 27.10.2010.

Предисловие

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

Коллективное использование ресурса

Тема коллективного использования ресурса обширна и выходит далеко за рамки вычислительных систем.
Некоторыми ресурсами мы владеем монопольно: например, к ним относятся наши личные вещи, которыми мы распоряжаемся по своему усмотрению. Другие ресурсы находятся в общем (коллективном) пользовании: телефонные станции, банковские терминалы, места в пассажирских вагонах; для того, чтобы корректно ими воспользоваться, необходимо соблюдать некоторые процедуры, не имеющие смысла при монопольном использовании. Так, например, звоня по телефону, мы должны быть готовы к тому, что линия окажется занята другим абонентом, который позвонил раньше нас; к банкомату может быть очередь, и мы должны встать в ее конец и дожидаться, когда нас обслужат; перед тем, как угнездиться на полке в купе, мы должны пройти процедуру приобретения билета, в результате которой за нами будет зарезервировано определенное место на некоторый срок. При несоблюдении этих процедур мы не только не достигаем желаемого, по и порой нам гарантирован конфликт с другими претендентами на тот же ресурс в тот же момент времени.
В данном контексте нас больше интересуют вычислительные процессы, которые претендуют на ресурсы вычислительной системы: процессор, оперативную память, файл, принтер и т.д. Но здесь нет никаких принципиальных отличий от предыдущих случаев. Суть не меняется: есть некоторое ограниченное число ресурсов, находящихся в общем доступе, но не позволяющих одновременное использование, и некоторое число желающих ими воспользоваться. В случае, когда число желающих меньше, чем число ресурсов, никакой проблемы нет: каждый потребитель забирает свободный ресурс и пользуется им по своему усмотрению. Если же ресурс дефицитный, необходимо выработать какую-то дисциплину для доступа к нему, а также обеспечить ее неукоснительное соблюдение.
В случае, когда мы имеем дело с компьютером общего назначения, эти заботы берет на себя операционная система. Для этого в ней имеется набор средств, в частности, примитивы синхронизации. Если же компьютер представляет собой микроконтроллер, управляющий неким объектом, то в этом случае зачастую операционной системы нет в принципе, программа выполняется автономно, и задача корректной организации вычислительного процесса целиком ложится на плечи программиста, который должен корректно реализовать не только программу для решения прикладной задачи, но и всю инфраструктуру, необходимую для работы этой программы.
Задача управления совместным доступом к ресурсам может быть решена многими способами, которые отличаются сложностью механизма, трудоемкостью реализации и эффективностью. Их строгие формальные описания обладают точностью м непротиворечивостью, но могут оказаться довольно трудными для чтения. Поэтому я постарался подыскать для них простейшие житейские аналогии, которые достаточно близко отражают суть и в то же время просты для понимания.
Итак, семья в составе: Папа (П), Мама (М) и Сын (С) выезжает на дачу на выходные. После приезда они делятся планами на ближайшее будущее. Оказывается, что П собирается посадить картошку на огороде, М решила разбить клумбу перед домом, а С намерен найти на участке клад. К сожалению, лопата (Л) в сарае оказалась лишь одна, а нужна она всем троим. Тем самым Л становится дефицитным ресурсом, на который претендуют сразу трое: П, М и С. После недолгих препирательств всем становится очевидно, что необходимо разработать (и впоследствии соблюдать) подходящую стратегию его использования.

1. Очередь.

П, используя свой авторитет и преимущество в физической силе, узурпирует Л и пользуется ей до тех пор, пока не выполнит задуманное полностью. Остальное семейство терпеливо ждет своей очереди. Когда П освобождает захваченный ресурс Л, ресурс поступает в распоряжение М. С продолжает ожидать его, а дождавшись, реализует свои планы.
Данная стратегия предельно проста: к дефицитному ресурсу выстраивается очередь.Это может быть простейшая очередь FIFO или более сложная структура с приоритетами, когда последний пришедший помещается не в конец очереди, а занимает место в ней в соответствии с некоторыми критериями. Но суть остается примерно одинаковой: первый в очереди захватывает ресурс и пользуется им до тех пор, пока не завершит свою работу и не покинет очередь. Ресурс переходит в распоряжение следующего в очереди, и так далее.
На заре развития вычислительной техники именно так организовывался вычислительный процесс: колоды перфокарт с заданиями собирались в пакеты и загружались в приемный бункер считывателя. Затем задания поочередно считывались и выполнялись. Этот режим до сих пор называется "пакетным", хотя сами перфокарты давно стали достоянием истории.
Достоинства:
  • очевидная простота реализации;
  • минимальные накладные расходы на поддержание очереди.
Недостатки:
  • невозможно предсказать, когда ресурс освободится.
  • зациклившееся задание намертво блокирует всю очередь.
  • ресурс может использоваться текущим владельцем неэффективно.
Для борьбы с зацикливаниями при запуске очередного пакетного задания указывалось максимальное время его выполнения. По истечении этого времени задание снималось с выполнения принудительно.

2. Кооперативная многозадачность.

Маясь вынужденным бездельем, М и С наблюдают за работой П и замечают, что ресурс Л загружен не на 100%: после того, как выкопана лунка, П откладывает Л в сторону и некоторое время затрачивает на процесс посадки, в ходе которого Л простаивает. Они вносят предложение изменить стратегию использования Л следующим образом: как только тот, кто в данный момент владеет ресурсом, перестает им пользоваться, ресурс переходит в распоряжение того, кто ожидает его освобождения.
Такая стратегия получила название кооперативной многозадачности. Она использовалась в 16-разрядных версиях MS Windows (до версии 3.11 включительно), а также поныне используется в виртуальной машине для выполнения 16-разрядных приложений в 32- и 64-разрядных версиях MS Windows. Ее особенность состоит в том, что временный хозяин ресурса должен периодически добровольно его освобождать, чтобы другие желающие тоже могли им воспользоваться.
Достоинства:
  • теперь ресурс используется более рационально. Его простой исключен, поскольку как только необходимость в его использовании у текущим владельца пропадает, он тут же поступает в распоряжение нового владельца, который ожидает своей очереди.
Недостатки:
  • успешность применения стратегии полностью зависит от добросовестности всех претендентов на ресурс. Каждый владелец ресурса добровольно передает его следующему; если же он отказывается это сделать, нет никакого механизма принудить его к этому. По этой причине зациклившееся приложение полностью подвешивало 16-разрядную Windows, и единственным выходом была перезагрузка системы.
Кроме того, увидев, что Л освободилась, новый владелец должен сначала доставить ее на место работы. Появляются накладные расходы на переключение процессов. Если процессы будут переключаться слишком часто, то эти хождения начнут занимать существенное время, что сведет на нет достигнутое повышение эффективности использования ресурса (начнется "пробуксовка" системы).

3. Вытесняющая многозадачность

П не в восторге от новой стратегии: быстро выкопав лунку, он отставляет Л в сторону, с тем чтобы другие могли также ей воспользоваться. Однако С, дорвавшись до Л, не спешит ее отдавать. Остальные вынуждены подолгу ждать своей очереди, чтобы пару раз копнуть и снова ждать. Никого, кроме С, такой поворот дела не устраивает.
П решает вновь изменить правила пользования Л: тот, в чьи руки она попала, может пользоваться ей не более 5 минут подряд (разумеется, можно и меньше). Предложение принимается большинством голосов (два против одного).
Наша система теперь ведет себя более предсказуемо: освободив ресурс, каждый участник концессии точно знает, что снова получит к нему доступ не более чем через 10 минут независимо от намерений каждого из его временных владельцев. Правда, накладные расходы на смену владельца Л по-прежнему присутствуют.
Стабильность 32- и 64-разрядных версий Windows в сравнении с 16-разрядными в немалой степени определяется именно применением вытесняющей многозадачности, пришедшей на смену кооперативной. Даже зацикленное приложение не сможет непрерывно пользоваться процессором дольше, чем длится выделенный ему временной квант, после чего управление будет передано следующему в очереди процессу.
Достоинства:
  • стабильная работа процессов даже в том случае, если один или даже несколько процессов зависнут;
  • предсказуемость поведения системы в целом.
Недостатки:
  • более сложная реализация;
  • накладные расходы на переключение процессов.
Кроме того, появляется более тонкая проблема. Некоторые операции (их называют атомарными) должны выполняться полностью как единое целое. Например, процессы выдают текстовые сообщения на консоль. Если сообщение будет выведено лишь частично, а затем другой процесс получит управление и начнет выводить другое сообщение, мы получим в итоге месиво нечитаемых строк. Поэтому необходимо производить квантование времени таким образом, чтобы не нарушать атомарность.
Также возрастает доля накладных расходов на переключение процессов. Если при кооперативной многозадачности в точности известны точки, в которых возможна передача управления другому процессу, и есть возможность заранее подготовиться к этому событию, то истечение кванта времени при вытесняющей многозадачности может произойти когда угодно, а следовательно, нужно сохранить больше информации (контекст), чтобы впоследствии продолжить выполнение процесса с прерванной точки.

4. Другие стратегии планирования процессов

Можно найти множество путей дальнейшего совершенствования стратегий распределения доступа к ограниченному ресурсу. Например, такой: П и М решают, что С своим баловством тормозит их работу, и постановляют: отныне П и М используют Л в режиме вытесняющей многозадачности; если С видит, что Л свободна, он имеет право ей пользоваться до тех пор, пока она не понадобится П или М, после чего он немедленно и беспрекословно отдает Л и переходит в режим ожидания следующей возможности завладеть Л.
Теперь у нас более сложная иерархия: имеются два процесса с высоким приоритетом, которые конкурируют за дефицитный ресурс, и фоновый процесс, осуществляющий свою деятельность по остаточному принципу.Можно дальше совершенствовать систему планирования: ввести уровень реального времени, на котором доступ к ресурсу предоставляется с минимальной задержкой; добавить различные уровни приоритетов и изощренные правила, по которым процесс переходит с одного уровня на другой, и т.д. Впрочем, это все детали, а основная суть от этого существенно не изменится. Эта суть заключается вот в чем: процесс либо периодически добровольно отказывается от ресурса, предоставляя возможность другим желающим тоже получить к нему доступ, либо этот ресурс у него изымается принудительно по какому-то критерию (обычно по истечении определенного кванта времени). Все вышеперечисленные (равно как и и не перечисленные) стратегии так или иначе сводятся к этим двум.

Краткий итог

Итак, мы определили два основных подхода к совместному использованию ресурса несколькими процессами:
1) Кооперативный (добровольный), при котором процесс отказывается от использования ресурса по своей инициативе. Его достоинства:
  • простота реализации;
  • понятность структуры потока управления (мы точно знаем, в каких точках меняется хозяин ресурса);
  • компактность данных о состоянии процесса (контексте) в этих точках.
Недостатки:
  • повышенная чувствительность к ошибкам программирования: зациклившийся процесс не только перестает выполнять полезную работу, но и не дает ее делать другим, поскольку не может отпустить захваченный ресурс;
  • непредсказуемость поведения всей системы в динамике: если некоторый процесс, получивший ресурс, написан не нами и мы не располагаем его исходными текстами, мы не можем гарантировать, что его поведение не нарушит работу остальных процессов (фактически следствие предыдущего пункта).
2) Вытесняющий (принудительный), при котором процесс может пользоваться ресурсом не долее определенного кванта времени, после чего ресурс принудительно изымается. Его достоинства и недостатки в принципе противоположны достоинствам и недостаткам его кооперативного собрата. Также к недостаткам можно отнести проблему обеспечения атомарности операций.

Теперь учтем специфику микроконтроллеров.

Возьмем, к примеру, "середнячок" AVR ATMega16 фирмы Atmel. Он имеет одно вычислительное ядро гарвардского типа с архитектурой RISC, 16 Кбайт программной Flash-памяти, 1 Кбайт динамического ОЗУ, 512 байт энергонезависимой памяти, а также 32 8-разрядных регистра общего назначения. Если мы решим организовать на нем процессы с вытесняющей мультизадачностью, очевидно, что самым большим препятствием для этого станет маленький объем ОЗУ. Для каждого процесса нам понадобится структура для сохранения контекста, а это как минимум 32 байта для сохранения значений РОН, несколько байт для флагов и указателя стека, а также выделить место для локального стека процесса - ведь если мы будем писать программу на языке C, нам и параметры функций нужно передавать через стек, и автоматические переменные размещать, да и сами вызовы функций тоже требуют места в стеке. Не разгуляешься. С младшими моделями семейства AVR дело обстоит еще хуже.
Есть в семействе, конечно, и старшие модели, у которых ОЗУ побольше, но не хотелось бы переходить на них лишь потому, что к этому вынуждают высокие накладные расходы на организацию вычислительного процесса.
Исходя из вышесказанного, делаем вывод: для микроконтроллеров начального и среднего уровня наиболее критичным ресурсом является малый объем ОЗУ, поэтому для них предпочтительнее будет использование кооперативной мультизадачности, поскольку она требует меньше затрат памяти на сохранение контекста.

(Продолжение следует)
Версия для печати
Обсудить на форуме (11)