8.3.2. Реализация управления памятью. Управление памятью в автономных однопроцессорных компьютерах

Управление вводом-выводом

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

Устройства ввода-вывода делятся на два типа: блок-ориентированные устройства и байт-ориентированные устройства.

Блок-ориентированные устройства ввода-вывода хранят информацию в блоках фиксированного размера, каждый из которых имеет свой собственный адрес. Самое распространенное блок-ориентированное устройство – диск.

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

Любое внешнее устройство обычно состоит из механического и электронного компонента. Электронный компонент называют контроллером устройства или адаптером. Механический компонент представляет собственно устройство. Некоторые контроллеры могут управлять несколькими устройствами. Если интерфейс между контроллером и устройством стандартизован, то независимые производители могут выпускать совместимые как контроллеры, так и устройства.

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

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

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

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

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

Еще один ключевой вопрос – это использование блокирующих (синхронных) и неблокирующих (асинхронных) передач. Большинство операций физического ввода-вывода выполняется асинхронно – процессор начинает передачу и переходит на другую работу, пока не наступает прерывание. Пользовательские программы намного легче писать, если операции ввода-вывода блокирующие. ОС выполняет операции ввода-вывода асинхронно, но представляет их для пользовательских программ в синхронной форме.

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

Для решения имеющихся проблем целесообразно разделить программное обеспечение ввода-вывода на четыре слоя:

1) обработка прерываний;

2) драйверы устройств;

3) слой операционной системы, независимый от устройств;

4) пользовательский слой программного обеспечения.

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

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

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

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

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

Типичными функциями слоя операционной системы, независимого от устройств, являются:

– обеспечение общего интерфейса к драйверам устройств;

– именование устройств;

– защита устройств;

– обеспечение независимого размера блока;

– буферизация;

– распределение памяти на блок-ориентированных устройствах;

– распределение и освобождение выделенных устройств;

– уведомление об ошибках.

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

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

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

Другой категорией программного обеспечения ввода-вывода является подсистема спулинга (spooling). Спулинг – это способ работы с выделенными устройствами в многозадачной системе. Одно из типичных устройств, требующих спулинга, – принтер. Хотя технически легко позволить каждому пользовательскому процессу открыть специальный файл, связанный с принтером, такой способ опасен из-за того, что пользовательский процесс может монополизировать принтер на произвольное время. Вместо этого создается специальный процесс-монитор, который получает исключительные права на использование этого устройства. Также создается специальный каталог, называемый каталогом спулинга. Для того, чтобы напечатать файл, пользовательский процесс помещает выводимую информацию в этот файл и помещает его в каталог спулинга. Процесс-монитор по очереди распечатывает все файлы, содержащиеся в каталоге спулинга.

Запись или чтение большого количества информации из ад-ресного пространства ввода-вывода (например, с диска) приводят к большому количеству операций ввода-вывода, которые должен выполнять процессор. Для освобождения процессора от операций последовательного вывода данных из оперативной памяти или последовательного ввода в нее был предложен механизм прямого доступа внешних устройств к памяти – ПДП или DMA (Direct Memory Access). Суть работы этого механизма заключается в следующем. Для того чтобы какое-либо устройство, кроме процессора, могло за­писать информацию в память или прочитать ее из памяти, необходимо чтобы это устройство могло забрать у процессора управление локальной магистралью для выставления соответствующих сигналов на шины адреса, данных и управления. Для централизации эти обязанности обычно возла­гаются не на каждое устройство в отдельности, а на специальный контрол­лер – контроллер прямого доступа к памяти. Контроллер прямого доступа к памяти имеет несколько спаренных линий – каналов DMA, которые мо­гут подключаться к различным устройствам. Перед началом использова­ния прямого доступа к памяти этот контроллер необходимо запрограмми­ровать, записав в его порты информацию о том, какой канал или каналы предполагается задействовать, какие операции они будут совершать, ка­кой адрес памяти является начальным для передачи информации и какое количество информации должно быть передано. Получив по одной из ли­ний – каналов DMA – сигнал запроса на передачу данных от внешнего уст­ройства, контроллер по шине управления сообщает процессору о желании взять на себя управление локальной магистралью. Процессор (возможно, через некоторое время, необходимое для завершения его действий с маги­стралью) передает управление маги­стралью контроллеру DMA, известив его специ­альным сигналом. Контроллер DMA выставляет на адресную шину адрес памяти для передачи очередной порции информации и по второй линии канала прямого доступа к памяти сообщает устройству о готовности маги­страли к передаче данных. После этого, используя шину данных и шину управления, контроллер DMA, устройство ввода-вывода и память осуще­ствляют процесс обмена информацией. Затем контроллер прямого досту­па к памяти извещает процессор о своем отказе от управления магистра­лью, и тот берет руководящие функции на себя. При передаче большого количества данных весь процесс повторяется циклически.

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

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

studfiles.net

Контрольные вопросы и задания

1. Охарактеризуйте существующие методы управления оперативной памятью.

2. Какие способы распределения виртуальной памяти чаще всего применяются, в чем их недостатки и преимущества?

3. Укажите отличие блок-ориентированных устройств ввода-вывода от байт-ориентированных?

4. В чем заключается смысл разбиения программного обеспечения ввода-вывода на несколько уровней?

5. Приведите примеры разделяемых и выделенных устройств ввода-вывода.

6. Опишите механизм прямого доступа устройств к памяти.

7. Дайте определение понятиям «система управления файлами» и «файловая система».

8. Какие функции в операционных системах выполняет система управления файлами?

9. Опишите структуру магнитного диска.

10. Дайте понятие логической организации файлов.

11. Охарактеризуйте наиболее известные способы физической организации файлов.

12. Какие уровни составляют многоуровневую модель функционирования файловой системы?

3. Управление процессами и ресурсами в автономных многопроцессорных вычислительных машинах

3.1. Реализация операционных систем многопроцессорных вычислительных машин

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

Возможны различные варианты организации операционных систем многопроцессорных машин.

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

Следует отметить следующие аспекты данной схемы.

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

Во-вторых, поскольку у каждой операционной системы есть свои собственные таблицы, у нее есть также и свой набор процессов, которые она сама планирует. Совместного использования процессов при этом нет. Если пользователь регистрируется на центральном процессоре 1, то и все его процессы работают на центральном процес­соре 1. В результате может случиться так, что центральный процессор 1 окажется загружен работой, тогда как центральный процессор 2 будет простаивать.

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

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

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

При другом способе организации ОС для многопроцессорных ВМ используется всего одна копия операционной системы, работающая только на центральном процессоре 1. Все системные вызовы перенаправляются для обработки на центральный процессор 1. Центральный процессор 1 может также выполнять процессы пользователя, если у него будет оставаться для этого время. Такая схема называется «ведущий-ведомый», так как центральный процессор 1 является ведущим (или главным), а все остальные процессоры – или ведомыми (или подчиненными).

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

Недостаток этой модели состоит в том, что при большом количестве централь­ных процессоров «ведущий» может стать узким местом системы. Ведь ему приходится обрабатывать все системные вызовы от всех центральных процессоров. Следова­тельно, такая модель проста и работоспособна для небольших мультипроцессоров, но на машинах с относительно большим числом процессоров она будет работать крайне неэффективно.

Третья модель, представляющая собой модель так называемых «симметричных мультипроцессоров» SMP (Symmetric Multiprocessor), позволяет устранить недостатки вышеописанной модели. Как и в предыдущей схеме, в данной модели в памяти находится всего одна копия операционной сис­темы, но выполнять ее может любой процессор. При системном вызове на цент­ральном процессоре, обратившемся к системе с системным вызовом, происходит прерывание с переходом в режим ядра и обработкой системного вызова. При этом модель обеспечивает динамический баланс процессов и памяти, поскольку в ней имеется всего один набор таблиц операционной системы. Она также позво­ляет избежать простоя системы, связанного с перегрузкой ведущего центрального процессора, так как в ней его нет. И все же данная модель имеет собственные проблемы. В частности, если код опе­рационной системы будет выполняться одновременно на двух или более центральных процессорах, произойдет «катастрофа» (например, если два центральных про­цессора одновременно берут один и тот же процесс для запуска или запраши­вают одну и ту же свободную страницу памяти).

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

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

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

studfiles.net

7.3. Управление памятью в unix

7.3.1. Основные понятия

У каждого процесса в системе UNIX есть адресное пространство, состоящее из трех сегментов: текста (программы), данных и стека. Текстовый (программный) сегмент содержит машинные команды, образующие исполняемый код программы. Он создается компилятором и ассемблером при трансляции программы, написанной на языке высокого уровня, в машинный код. Как правило, тексто­вый сегмент разрешен только для чтения. Текстовый сегмент не изменяется ни в размерах, ни по своему содержанию.

Сегмент данных содержит переменные, строки, массивы и другие данные про­граммы. Он состоит из двух частей: инициализированных данных и неинициали­зированных данных. По историческим причинам вторая часть называется BSS (Bulk Storage System – запоминающее устройство большой емкости или массовое запоминающее устройств). Инициализированная часть сегмента данных содержит переменные и константы компилятора, значения которых должны быть заданы при запуске программы. Например, на языке С можно объявить символьную строку и в то же время за­дать ее значение, то есть проинициализировать ее. Когда программа запускается, она предполагает, что в этой строке уже содержится некий осмысленный текст. Чтобы реализовать это, компилятор назначает строке определенное место в адрес­ном пространстве и гарантирует, что в момент запуска программы по этому адресу будет располагаться соответствующая строка. С точки зрения операционной сис­темы, инициализированные данные не отличаются от текста программы – тот и другой сегменты содержат сформированные компилятором последовательности битов, загружаемые в память при запуске программы.

Неинициализированные данные необходимы лишь с точки зрения оптимиза­ции. Когда начальное значение глобальной переменной явно не указано, то, соглас­но семантике языка С, ее значение устанавливается равным 0. На практике боль­шинство глобальных переменных не инициализируются, и, таким образом, их начальное значение равно 0. Это можно реализовать следующим образом: создать целый сегмент исполняемого двоичного файла, точно равного по размеру числу байтов данных, и проинициализировать весь этот сегмент нулями. Однако с целью экономии места на диске этого не делается. Файл содержит только те переменные, начальные значения которых явно заданы. Вместо неинициализи­рованных переменных компилятор помещает в исполняемый файл просто одно слово, содержащее размер области неинициализированных данных в байтах. При запуске программы операционная система считывает это слово, выделяет нужное число байтов и обнуляет их.

В отличие от текстового сегмента, который не может изменяться, сегмент дан­ных может модифицироваться. Программы изменяют свои переменные постоян­но. Более того, многим программам требуется выделение дополнительной памяти динамически, во время выполнения. Чтобы реализовать это, операционная систе­ма UNIX разрешает сегменту данных расти при динамическом выделении памяти программам и уменьшаться при освобождении памяти программами. Програм­ма может установить размер своего сегмента данных с помощью системного вызо­ва brk. Таким образом, чтобы получить больше памяти, программа может увеличить размер своего сегмента данных. Этим системным вызовом пользуется библиотеч­ная процедура, используемая для выделения памяти.

Третий сегмент – это сегмент стека. На большинстве вычислительных машин он начи­нается около старших адресов виртуального адресного пространства и растет вниз к 0. Если указатель стека оказывается ниже нижней границы сегмента стека, как правило, происходит аппаратное прерывание, при котором операционная сис­тема понижает границу сегмента стека на одну страницу памяти. Программы не управляют явно размером сегмента стека. Когда программа запускается, ее стек не пуст. Напротив, он содержит все пере­менные окружения (оболочки), а также командную строку, введенную в оболочке при вызове этой программы. Таким образом, программа может узнать параметры, с которыми она была запущена.

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

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

На некоторых вычислительных машинах аппаратное обеспечение поддерживает раздельные адресные пространства для команд и для данных. Если такая возможность есть, система UNIX может ею воспользоваться. Например, на компьютере с 32-разряд­ными адресами при возможности использования раздельных адресных пространств можно получить 4 Гбайт адресного пространства для команд и еще 4 Гбайт адрес­ного пространства для данных. Передача управления по адресу 0 будет восприни­маться как передача управления по адресу 0 в текстовом пространстве, тогда как при обращении к данным по адресу 0 будет использоваться адрес 0 в пространстве данных. Таким образом, это свойство удваивает доступное адресное пространство.

Многими версиями UNIX поддерживается отображение файлов на адресное пространство памяти. Это свойство позволяет отображать файл на часть адресно­го пространства процесса, так чтобы можно было читать из файла и писать в файл, как если бы это был массив, хранящийся в памяти. Отображение файла на адрес­ное пространство памяти делает произвольный доступ к нему существенно более легким, нежели при использовании системных вызовов, таких как read и write. Совместный доступ к библиотекам предоставляется именно при помощи этого механизма.

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

studfiles.net

8.3.2. Реализация управления памятью

В операционной системе Windows 2000 поддерживается подгружаемое по тре­бованию одинарное линейное 4-гигабайтное адресное пространство для каждого процесса. Сегментация в любой форме не поддерживается. Теоретически размер страниц может быть любой степенью двух, вплоть до 64 Кбайт. На компьютерах с процессором Pentium страницы имеют фиксированный размер в 4 Кбайт. На компьютерах с процессором Itanium они могут быть 8 или 16 Кбайт. Кроме того, сама операционная система может использовать страницы по 4 Мбайт, чтобы снизить размеры таблицы страниц.

В отличие от планировщика, выбирающего отдельные потоки для запуска и не заботящегося о процессах, менеджер памяти занимается исключительно процесса­ми и не беспокоится о потоках, так как именно процессы, а не потоки вла­деют адресным пространством, которым занимается менеджер памяти. При выде­лении области виртуального адресного пространства менеджер памяти создает для нее описатель виртуаль­ной памяти VAD (Virtual Address Descriptor), в котором хранится информация о диапазоне отображаемых адресов, файле резервного хранения и смещении в файле для отображаемой части файла, а также режим доступа. Когда происходит обращение к первой странице, создается каталог таблиц страниц, а указатель на нее помещается в описатель виртуальной памяти. Адресное пространство полнос­тью описывается списком своих описателей виртуальной памяти. Такая схема по­зволяет поддерживать несплошные адресные пространства, так как неиспользуе­мые области между отображаемыми областями не потребляют ресурсов.

В операционной системе Windows 2000 опережающая подкачка страниц не ис­пользуется ни в каком виде. Когда запускается процесс, в памяти не находится ни одной страницы процесса. При каждом страничном прерывании происходит пе­редача управления ядру. Ядро формирует машинно-независимый описатель, в который помещается инфор­мация о том, что случилось, и передает его части исполняющей системы, выпол­няющей функции менеджера памяти. Менеджер памяти проверяет полученный описатель на корректность. Если страница, вызвавшая прерывание, попадает в фик­сированную или зарезервированную область, он ищет адрес в списке описателей виртуальной памяти, находит (или создает) таблицу страниц и ищет в ней соот­ветствующий элемент. Элементы таблицы страниц различаются в разных архитектурах. У неотображаемых страниц также есть записи в таблице, но их формат несколько отличается. Например, если неотображаемая страница должна быть обнулена перед употреблением, этот факт отражается в таблице.

Страничные прерывания подразделяются на пять категорий:

1.Страница, к которой было обращение, не является фиксированной.

2.Произошло нарушение защиты.

3.Запись в совместно используемую страницу.

4.Стеку требуется дополнительная память.

5.Страница, к которой было обращение, является фиксированной, но в насто­ящий момент она не загружена в память.

Первый и второй случаи представляют собой фатальные ошибки, которые не могут быть исправлены или проигнорированы. У третьего случая симптомы схо­жи со вторым (попытка записи в страницу, для которой разрешено только чтение), но лечение этого случая возможно. В этом случае страница копируется в новый физический страничный блок, после чего для копии разрешается чтение/запись. Таким образом, работает копирование при записи. Если совместно используемая страница помечена как доступная для записи во всех процессах, использующих ее, страничного прерывания при записи в такую страницу не возникает и копии при записи не возникает также. В четвертом случае требуется выделение нового стра­ничного блока и его отображение. Однако правила безопасности требуют, чтобы эта страница содержала только нули, что не позволяет новому процессу узнать, чем занимался предыдущий владелец страницы. Таким образом, нужно найти страни­цу, содержащую одни нули или, если это невозможно, нужно выделить другой страничный блок и обнулить его на месте. Наконец, пятый случай представляет собой нормальное страничное прерывание. Менеджер памяти находит страницу на диске и считывает ее в память.

Отметим, что операционная система Windows 2000 не читает отдельные страницы прямо с дис­ка. Вместо этого считывается несколько последовательных страниц, как правило, от 1 до 8, чтобы минимизировать количество обращений к диску. Для страниц, со­держащих код программы, используются серии из большего числа страниц, чем при считывании страниц данных.

Замена страниц происходит следующим образом. Система пытается поддерживать определенное количество свободных страниц в памяти, чтобы, когда произойдет страничное прерывание, свободная страница могла быть найдена немедленно, без необходимости сначала записать несколько других страниц на диск. В результате применения такой стратегии большинство страничных прерываний удовлетворя­ются при помощи всего одной дисковой операции (чтения страницы с диска), хотя иногда приходится выполнять две операции (запись на диск «грязной» страницы, после чего с диска читается требуемая страница). Конечно, страницы, пополняющие список свободных страниц, должны откуда-то поступать. Поэтому настоящая работа алгоритма замещения страниц характери­зуется тем, как эти страницы забираются у процессов и помещаются в список сво­бодных страниц.

В системе подкачки активно использует­ся понятие рабочего набора. У каждого процесса (не у каждого потока) есть рабо­чий набор. Этот набор состоит из отображенных страниц, находящихся в памяти, при обращении к которым, следовательно, не происходит страничных прерываний. Размер и состав рабочего набора, естественно, меняются по мере работы процесса. Рабочий набор каждого процесса описывается двумя параметрами: минималь­ным и максимальным размерами. Эти размеры не являются жесткими границами. Процесс может иметь в памяти меньше страниц, чем значение нижней границы, или (при определенных обстоятельствах) больше установленного максимума. Вначале эти границы одинаковы для каждого процесса, но они могут меняться со временем. Начальное значение минимума по умолчанию находится в диапазоне от 20 до 50 страниц, а начальное значение максимума по умолчанию находится в диапазоне от 45 до 345 страниц, в зависимости от общего объема оперативной па­мяти. Значения по умолчанию могут быть изменены системным администратором.

Если происходит страничное прерывание, а размер рабочего набора меньше минимального значения, то к рабочему набору добавляется страница. С другой стороны, если происходит страничное прерывание, а размер рабочего набора боль­ше максимального значения, то из рабочего набора (но не из памяти) изымается страница, чтобы выделить место для новой страницы. Этот алгоритм означает, что в операционной системе Windows 2000 используется локальный алгоритм, не по­зволяющий процессу получить слишком много памяти, что предотвращает при­чинение процессами ущерба друг другу. Однако система пытается настроить эти параметры. Например, если она замечает, что один процесс слишком активно за­нимается подкачкой (а остальные процессы нет), система может увеличить значе­ние максимального предела для рабочего набора. Таким образом, алгоритм пред­ставляет собой смесь локальных и глобальных решений. Тем не менее существует абсолютный предел размера рабочего набора: даже если в системе работает всего один процесс, он не может занять последние 512 страниц, чтобы оставить немного оперативной памяти для новых процессов.

Раз в секунду выделенный демон-поток ядра, называемый менеджером балансового множества, проверяет, доста­точно ли в системе свободных страниц. Если свободных страниц меньше, чем нуж­но, он запускает менеджер рабочих наборов, который исследует рабочие наборы и освобождает дополнительные страницы. Менеджер рабочих наборов сначала определяет порядок, в котором нужно исследовать процессы. В первую очередь страницы отнимаются у больших процессов, которые бездействовали в течение долгого времени. В последнюю очередь рассматривается процесс переднего плана. Затем менеджер рабочих наборов начинает исследование процессов в выбран­ном порядке. Если рабочий набор процесса в настоящий момент оказывается мень­ше своего нижнего предела или с момента последней инспекции число странич­ных прерываний у этого процесса было выше определенного уровня, то страницы у него не отнимаются. В противном случае менеджер рабочих наборов отнимает у процесса одну или несколько страниц. Количество забираемых у процесса стра­ниц довольно сложным образом зависит от общего объема ОЗУ, а также от того, насколько много требуется памяти текущим процессам, и от того, как размер текущего рабоче­го набора соотносится с верхним и нижним пределами, и кроме того от других парамет­ров. Все страницы рассматриваются по очереди.

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

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

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

Каждая страница памяти находится в одном или не­скольких рабочих наборах или в одном из пяти списков. В списке «чистых» (резервных) и в списке «грязных» (модифицированных) страниц учитываются страницы, которые недавно были удалены из рабочих набо­ров, но все еще находятся в памяти и все еще ассоциированы с процессами, ис­пользовавшими их. Различие между ними заключается в том, что у чистых стра­ниц есть копия на диске, тогда как у модифицированных страниц таких копий нет, и эти страницы еще предстоит сохранить. В список свободных страниц входят чи­стые страницы, уже не ассоциированные ни с какими процессами. В список обну­ленных страниц входят страницы, не ассоциированные ни с какими процессами и заполненные нулями. Пятый список состоит из физически дефектных страниц памяти. Это гарантирует, что эти страницы ни для чего не используются.

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

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

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

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

Для отслеживания всех страниц и всех списков операционная система Win­dows 2000 содержит базу данных страничных блоков, состоящую из записей по числу страниц ОЗУ. Эта таблица проиндексирована по номеру физи­ческого страничного блока. Записи таблицы имеют фиксированную длину, но для различных типов записей используются различные форматы (например, для дей­ствительных записей и для недействительных). Действительные записи содержат информацию о состоянии страницы, а также счетчик, хранящий число ссылок на эту страницу в таблицах страниц. Этот счетчик позволяет системе определить, ког­да страница уже более не используется. Если страница находится в рабочем наборе, то в записи также указывается номер рабочего набора. Кроме того, в записи содер­жится указатель на таблицу страниц, в которой есть указатель на эту страницу (если такая таблица страниц есть). Страницы, используемые совместно, учитыва­ются особо. Также запись содержит ссылку на следующую страницу в списке (если такая есть) и различные другие поля и флаги, такие как «страница читается», «страница пишется» и т. д.

Итак, управление памятью представляет собой очень сложную подсистему с большим количеством структур данных, алгоритмов и эвристических методов. Во многом она является саморегулируемой, но у нее есть также много механизмов, которые может использовать системный администратор, чтобы влиять на про­изводительность системы. Следует подчеркнуть, что управление памятью в реальных системах намного сложнее простого алгорит­ма подкачки, вроде алгоритма часов или алгоритма старения.

studfiles.net

Планирование и синхронизация в многопроцессорных вычислительных машинах

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

Рассмотрим планирование независимых процессов.

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

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

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

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

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

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

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

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

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

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

Основой любого практического мьютекс-протокола является команда процессо­ра, позволяющая исследовать и изменить слово в памяти за одну операцию. Для этого можно использовать команду TSL (Test and Set Lock – проверить и установить блокировку), которая считывает слово памяти в регистр процессора. Одновременно она записывает 1 (или другое ненулевое значение) в слово памяти. Конечно, для выполнения операций чтения и записи памяти требуется два цикла шины. В однопроцессорной ВМ, поскольку одна команда процессора не мо­жет быть прервана на полпути, команда TSL работает должным образом. Для решения проблемы взаимного исключения в многопроцессорной ВМ команда TSL сначала должна блокировать шину, не допуская обращения к ней других центральных процессоров, затем выполнить оба обращения к памяти, после чего разблокировать шину. Как правило, для блоки­ровки шины сначала выполняется обычный запрос шины по стандартному прото­колу, затем устанавливается в 1 некая специальная линия шины. Пока эта линия шины установлена в 1, никакой другой центральный процессор не может получить к ней доступ. Такая команда может быть выполнена только на шине, у которой есть необходимые специальные линии и аппаратный протокол для их использования (современные шины обладают подобными свойствами). Если команда TSL корректно реализована и применяется, она гарантирует пра­вильную работу взаимного исключения. Однако подобный способ реализации взаимного исключения использует спин-блокировку, так как запрашивающий центральный процессор находится в цикле опроса блокировки с максимальной скоростью. Этот метод является не только тратой времени запрашивающего цент­рального процессора (или процессоров), но он также может накладывать значительную нагрузку на шину или память, существенно снижая скорость работы всех остальных центральных процессоров, пытающихся выполнять свою обычную работу.

Наличие кэширования не устра­няет проблему конкуренции за шину. Теоретически, как только за­прашивающий центральный процессор прочитал слово блокировки, он должен по­лучить его копию в свой кэш. Пока ни один другой центральный процессор не предпринимает попыток использовать это слово, запрашивающий центральный процессор может работать с ним в своем кэше. Когда центральный процессор, владеющий словом блокировки, записывает в него 1, протокол кэша автомати­чески помечает как недействитель-ные все копии этого слова в удаленных кэшах, требуя получения правильных значений. Однако проблема заключается в том, что кэш оперирует блоками по 32 или 64 байт. Обычно слова, окружающие слово блокировки, нужны центральному процессору, удерживающему это слово. Поскольку команда TSL представляет собой запись (так как она модифицирует слово блокировки), ей требуется монопольный доступ к блоку кэша, содержащему слово блокировки. Таким образом, каждая команда TSL помечает блок кэша владельца блокировки как недействительный и получает при­ватную, эксклюзивную копию для запрашивающего центрального процессора. Как только владелец блокировки изменит слово, соседнее с блокировкой, блок кэша перемещается на его процессор. В результате весь блок кэша, содержащий слово блокировки, постоянно челночно перемещается от центрального про­цессора, удерживающего блокировку, к центральному процессору, пытающемуся ее получить. Все это создает довольно значительный и совершенно излишний трафик шины.

Проблему можно было бы решить, если бы удалось избавиться от всех опера­ций записи, вызванных командой TSL запрашивающей стороны. Это можно сделать, если запрашивающая сторона сначала будет выполнять простую операцию чтения, чтобы убедиться, что мьютекс свободен. Только убедившись, что он свободен, цен­тральный процессор выполняет команду TSL, чтобы захватить его. В результате большинство операций опроса представляют собой операции чтения, а не опера­ции записи. Когда мьютекс считан, владелец выполняет операцию записи, для чего требуется монопольный доступ. При этом все остальные копии этого блока кэша объявляются недействительными. При следующей операции чтения запрашива­ющий центральный процессор перезагрузит этот блок кэша. При одновременном споре двух центральных процессоров за один и тот же мьютекс может случиться, что они одновременно увидят, что мьютекс свободен, и одновременно выполнят команду TSL. Ничего катастрофичного в этом случае не про­изойдет, так как выполнена будет только одна команда TSL и такая ситуация не приведет к состоянию состязания.

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

Еще более эффективный способ заключается в том, чтобы каждому центральному про­цессору, желающему заполучить мьютекс, позволить опрашивать свою собствен­ную переменную блокировки. Во избежание конфликтов перемен­ная должна располагаться в не используемом для других целей блоке кэша. Работа алгоритма состоит в том, что центральный процессор, которому не удается запо­лучить мьютекс, захватывает переменную блокировки и присоединяется к концу списка центральных процессоров, ожидающих освобождения мьютекса. Когда цен­тральный процессор, удерживающий мьютекс, покидает критическую область, он освобождает приватную переменную, проверяемую первым центральным процес­сором в списке (в его собственном кэше). Тем самым следующий центральный процессор получает возможность войти в критическую область. Покинув крити­ческую область, этот процессор освобождает переменную блокировки, тестируе­мую следующим процессором и т.д. Хотя такой протокол несколько сложен (это необходимо, чтобы не допустить одновременного присоединения двух централь­ных процессоров к концу списка), однако его практическое применение достаточно результативно.

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

Если допустить, что оба варианта (опрос в цикле и переключение потоков) вы­полнимы, возникает следующая ситуация. Циклический опрос напрямую расхо­дует процессорное время. Периодическая проверка состояния мьютекса не явля­ется продуктивной работой. Переключение процессов, однако, также расходует циклы процессора, так как для этого требуется сохранить текущее состояние пото­ка, получить мьютекс списка свободных процессов, выбрать из этого списка поток, загрузить его состояние и передать ему управление. Более того, кэш центрального процессора будет содержать не те блоки, поэтому после переключения потоков возможно много промахов кэша. Также вероятны ошибки TLB. Наконец, потре­буется переключение обратно на исходный поток, результатом которого снова бу­дут промахи кэша. Циклы процессора, потраченные на эти два переключения кон­текста, плюс промахи кэша представляют собой существенные накладные расходы.

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

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

Резюме

По своему основному содержанию операционные системы для многопроцессорных ВМ представляют собой обычные ОС, выполняющие традиционные функции по обработке системных вызовов, управлению памятью, обслуживанию файловой системы, управлению устройствами ввода-вывода. Главным отличием в реализации ОС для многопроцессорных ВМ является изменение содержания состояния «выполнение» процессов. В этом состоянии может находиться не один процесс (как в однопроцессорных ВМ), а сразу несколько процессов, выполняющихся на разных процессорах многопроцессорной ВМ.

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

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

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

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

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

Простейший алгоритм планирова­ния независимых процессов – поддержание единой струк­туры данных для готовых процессов.

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

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

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

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

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

studfiles.net

8.2. Процессы и потоки в Windows 2000

8.2.1. Основные понятия

В операционной системе Windows 2000 поддерживаются традиционные процес­сы, способные общаться и синхронизироваться друг с другом так же, как это дела­ют процессы в UNIX. Каждый процесс содержит по крайней мере один поток, со­держащий, в свою очередь, как минимум одно волокно (облегченный поток). Более того, для управления определенными ресурсами процессы могут объединяться в задания. Все вместе – задания, процессы, потоки и волокна – образует общий набор инструментов для управления ресурсами и реализации параллелизма как на однопроцессорных, так и на многопроцессорных машинах.

Задание в Windows 2000 представляет собой набор, состоящий из одного или нескольких процессов, управляемых как единое целое. В частности, с каждым заданием ассоциированы квоты и лимиты ресурсов, хранящиеся в соот­ветствующем объекте задания. Квоты включают такие пункты, как максимальное количество процессов (не позволяющее процессам задания создавать бесконтроль­ное количество дочерних процессов), суммарное время центрального процессора, доступное для каждого процесса в отдельности и для всех процессов вместе, а также максимальное количество используемой памяти для процесса и для всего задания. Задания также могут ограничивать свои процессы в вопросах безопасности, на­пример, запрещать им получать права администратора (суперпользователя) даже при наличии правильного пароля.

Как и в системе UNIX, процессы представляют собой контейнеры для ресур­сов. У каждого процесса есть 4-гигабайтное адресное пространство, в котором пользователь занимает нижние 2 Гбайт (в версиях Windows 2000 Advanced Server и Datacenter Server этот размер может быть по желанию увеличен до 3 Гбайт), а операционная система занимает остальную его часть. Таким образом, операци­онная система присутствует в адресном пространстве каждого процесса, хотя она и защищена от изменений с помощью аппаратного блока управления памятью MMU. У процесса есть идентификатор процесса, один или несколько потоков, список дескрипторов (управляемых в режиме ядра) и маркер доступа, хранящий информацию защиты. Процессы создаются с помощью вызова Win32, который принимает на входе имя исполняемого файла, определяющего начальное содер­жимое адресного пространства, и создает первый поток.

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

Как правило, поток работает в пользовательском режиме, но когда он обраща­ется к системному вызову, то переключается в режим ядра, после чего продолжает выполнять тот же поток, с теми же свойствами и ограничениями, которые были у него в режиме пользователя. У каждого потока есть два стека – один используется в режиме ядра, а другой в режиме пользователя. Помимо состояния, идентифика­тора и двух стеков, у каждого потока есть контекст (в котором сохраняются его регистры, когда он не работает), приватная область для локальных переменных, а также может быть свой собственный маркер доступа. Если у потока есть свой мар­кер доступа, то он перекрывает маркер доступа процесса, чтобы клиентские потоки могли передать свои права доступа серверным потокам, выполняющим работу для них. Когда поток завершает свою работу, он может прекратить свое существование. Когда прекращает существование последний активный поток, процесс завершается.

Важно понимать, что потоки представляют собой концепцию планирования, а не концепцию владения ресурсами. Любой поток может получить доступ ко всем объектам его процесса. Все, что ему для этого нужно сделать, – это заполучить дес­криптор и обратиться к соответствующему вызову Win32. Для потока нет ника­ких ограничений доступа к объекту, связанных с тем, что этот объект создан или открыт другим потоком. Система даже не следит за тем, какой объект каким потоком создан. Как только дескриптор объекта помещен в таблицу дескрипторов про­цесса, любой поток процесса может его использовать.

Помимо нормальных потоков, работающих в процессах пользователя, в опера­ционной системе Windows 2000 есть множество процессов-демонов, не связанных ни с каким пользовательским процессом (они ассоциированы со специальной си­стемой или простаивающими процессами). Некоторые демоны выполняют адми­нистративные задачи, как, например, запись «грязных» (модифицированных) страниц на диск, тогда как другие формируют пул, и ими могут пользоваться компоненты исполняющей системы или драйверы, которым нужно выполнить какие-либо асинхронные за­дачи в фоновом режиме. Переключение потоков в операционной системе Windows 2000 занимает до­вольно много времени, так как для этого необходимо переключение в режим ядра, а затем возврат в режим пользователя. Для предоставления сильно облегченного псевдопараллелизма в Windows 2000 используются волокна, подобные потокам, но планируемые в пространстве пользователя создавшей их программой (или ее системой поддержки исполнения). У каждого потока может быть несколько воло­кон, так же как у процесса может быть несколько потоков, с той разницей, что когда волокно логически блокируется, оно помещается в очередь блокированных волокон, после чего для работы выбирается другое волокно в контексте того же потока. Операционная система не знает о смене волокон, так как все тот же поток продолжает работу. Так как операционная система ничего не знает о волокнах, то с ними, в отличие от заданий, процессов и потоков, не связаны объекты испол­няющей системы. Для управления волокнами нет и настоящих системных вызо­вов. Однако для этого есть вызовы Win32 API. Они относятся к тем вызовам Win32 API, которые не обращаются к системным вызовам.

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

Верхний предел в 32 центральных процессора является жестким пределом, так как во многих местах операционной системы для учета использования централь­ных процессоров используются битовые массивы размером в 32-разрядное машин­ное слово. Например, один однословный битовый массив используется для того, чтобы следить, какой из центральных процессоров свободен в данный момент, а другой массив используется в каждом процессе для перечисления центральных процессоров, на которых этому процессу разрешено работать. 64-разрядная версия Windows 2000 должна будет без особых усилий поддерживать до 64 центральных процессоров. Для превышения этого ограничения потребуется существенная пере­делка программы (с использованием по нескольку слов для битовых массивов).

studfiles.net

1.3. Межпроцессное взаимодействие

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

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

Важным понятием синхронизации процессов является понятие «критическая секция» или «критическая область» программы. Критическая секция (критическая область) – это часть программы, в которой осуществляется доступ к разделяемым данным. Для исключения эффекта гонок по отношению к некоторому ресурсу, необходимо обеспечивать такие ситуации, чтобы в каждый момент времени в критической секции, связанной с этим ресурсом, находился максимум один процесс. Этот прием называют взаимным исключением. Простейший способ обеспечить взаимное исключение – позволить процессу, находящемуся в критической секции, запрещать все прерывания. Однако этот способ далеко не всегда пригоден, так как весьма опасно доверять управление системой пользовательскому процессу: он может надолго занять процессор, а при «крахе» процесса в критической области «крах» потерпит вся система, потому что прерывания никогда не будут разрешены.

Другим способом взаимного исключения является использование блокирующих переменных. При этом каждому разделяемому ресурсу ставится в соответствие двоичная переменная, которая принимает, например, значение 0, если ресурс свободен (то есть ни один из процессов не находится в данный момент в критической секции, связанной с данным процессом), и значение 1, если ресурс занят.

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

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

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

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

Например, если ресурс занят, то процесс не выполняет циклический опрос, а вызывает некоторую системную функцию wait(D), где D обозначает событие, заключающееся в освобождении ресурса D. Функция wait(D) переводит активный процесс в состояние «ожидание» и делает отметку в его дескрипторе о том, что процесс ожидает события D. Процесс, который в это время использует ресурс D, после выхода из критической секции выполняет системную функцию post(D), в результате чего операционная система просматривает очередь ожидающих процессов и переводит процесс, ожидающий события D, в состояние «готовность».

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

Для работы с семафорами применяются две операции: down и up. Операция down сравнивает значение семафора с нулем. Если значение семафора больше нуля, операция down уменьшает его (то есть расходует один из сохраненных сигналов активации) и просто возвращает управление. Если значение семафора равно нулю, процедура down не возвращает управление процессу, а процесс переводится в состояние ожидания. Все операции проверки значения семафора, его изменения и перевода процесса в состояние ожидания выполняются как единое и неделимое элементарное действие. Тем самым гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания или блокирования операции. Элементарность операции чрезвычайно важна для разрешения пробле­мы синхронизации и предотвращения состояния состязания.

Операция up увеличивает значение семафора. Если с этим семафором связаны один или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой (например, случайным образом) и ему разрешается завершить свою операцию down. Таким образом, после операции up, примененной к семафору, связанному с несколькими ожидающими процессами, значение семафора так и останется равным 0, но число ожидающих процессов уменьшится на единицу. Операция увеличения значения семафора и активизации процесса тоже неделима. Ни один процесс не может быть блокиро­ван во время выполнения операции up.

Часто используется упрощенная версия семафора, называемая мьютексом (от англоязычного термина mutex, происходящего от сокращения словосочетания mutual exclusion – «взаимное исключение»).

Мьютекс не может считать сигналы, а может лишь управлять взаимным исключением доступа к совместно используемым ресурсам. Реализация мьютекса проста и эффективна. Мьютекс является переменной, которая может находиться в одном из двух состояний: блокированном или неблокированном. Поэтому для описания мьютекса требует­ся всего один бит, хотя чаще используется целая переменная, у которой 0 означает неблокированное состояние, а все остальные значения соответствуют блокирован­ному состоянию. Значение мьютекса устанавливается двумя процедурами. Если процесс собирается войти в критическую секцию, он вызывает проце­дуру mutex_lock. Если мьютекс не заблокирован (то есть вход в критическую секцию разрешен), запрос выполняется и вызывающий процесс может попасть в критическую секцию. Напротив, если мьютекс заблокирован, вызывающий процесс блокируется до тех пор, пока другой процесс, находящийся к критической секции, не выйдет из нее, вызвав процедуру mutex_unlock. Если мьютекс блокирует несколько процессов, то из них случайным образом выбирается один.

Одним из наиболее простых, удобных и интуитивных интерфей­сов межпроцессного взаимодействия является буфер обмена. Буфер обмена может содержать в себе один информаци­онный объект – фрагмент текста, рисунок и т. д. С помощью сис­темного вызова процесс может получить копию информации, со­держащейся в буфере обмена, или сам поместить объект в буфер, при этом старое содержимое буфера теряется. Таким образом, про­граммы получают простой, но эффективный способ взаимного обмена инфор­мацией во время своей работы.

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

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

Процессы в зависимости от соотношения собственных скоростей могут либо совершенно независимо использовать разделяемые ресурсы, либо образовывать очереди к разделяемым ресурсам, либо взаимно блокировать друг друга. Тупиковые ситуации следует отличать от простых очередей, хотя те и другие возникают при совместном использовании ресурсов и внешне похожи друг на друга: процесс приостанавливается и ждет освобождения ресурса. Однако очередь – это нормальное явление, неотъемлемый признак высокого коэффициента использования ресурсов при случайном поступлении запросов. Она возникает тогда, когда ресурс недоступен в данный момент, но через некоторое время он освобождается, и процесс продолжает свое выполнение. Тупик же, что видно из его названия, является в некотором роде неразрешимой ситуацией. В рассмотренном примере тупик (взаимоблокировка) был образован двумя процессами, но взаимно блокировать друг друга может и большее число процессов. Проблема взаимоблокировок включает в себя задачи предотвращения взаимоблокировок, распознавания взаимоблокировок и восстановления системы после взаимоблокировок.

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

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

В некоторых случаях, когда тупиковая ситуация образована многими процессами, использующими множество ресурсов, распознавание взаимоблокировки является нетривиальной задачей. Существуют формальные программно-реализованные методы распознавания взаимоблокировок, основанные на ведении таблиц распределения ресурсов и таблиц запросов к занятым ресурсам. Анализ этих таблиц позволяет обнаружить взаимные блокировки. Если же тупиковая ситуация возникла, то не обязательно снимать с выполнения все заблокированные процессы. Можно снять только часть из них (при этом освобождаются ресурсы, ожидаемые остальными процессами), можно вернуть некоторые процессы в область свопинга(см. раздел 2), можно совершить «откат» некоторых процессов до так называемойконтрольной точки, в которой запоминается вся информация, необходимая для восстановления выполнения программы с данного места. Контрольные точки расставляются в программе в тех местах, после которых возможно возникновение тупика.

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

studfiles.net

---

• 
  Компьютерное зрение это
• 
  Компьютерная томография радиация
• 
  Как запустить ios приложения на компьютере
• 
  Как запустить приложения ios на компьютере
• 
  Что такое блок питания для компьютера
• 
  Процессор у компьютера
• 
  Как майнить с обычного компьютера
• 
  Число операций выполняемых микропроцессором персонального компьютера за 1 с
• 
  Облучение компьютерная томография
• 
  Очки для игры за компьютером
• 
  Открытие компьютера