Реферат на тему синхронизация потоков
Обновлено: 02.07.2024
Процесс — это объединение нескольких потоков. А объединяет эти потоки единое виртуальное адресное пространство. В этом пространстве размещаются код и данные приложения (обычно это один exeи несколько dll-модулей). Именно единство этого пространства и делает обмен данными между потоками приложения предельно простым. Наоборот, адресные пространства различных процессов независимы и отделены друг… Читать ещё >
Процессы, потоки, синхронизация ( реферат , курсовая , диплом , контрольная )
Целью данной курсовой работы было изучение потоков, их реализации, технологии и средства синхронизации. Задачи, поставленные при выполнении курсовой работы. Рассмотреть такое понятие как поток и процесс дать их определение. Изучить работу многопоточных приложений, разобрать средства синхронизации, используемые при работе с потоками. Разработать многопоточное приложение, которое наглядно будет представлять работу приоритетов при выполнении потоков. Поток, процесс определение, назначение.
Технологии многопоточности
Основные направления развития архитектуры современных микропроцессоров определяются стремлением к увеличению их производительности. Последнюю можно повышать, например, наращивая тактовую частоту и/или увеличивая число команд, выполняемых за один такт.
При использовании базового типа параллелизма на уровне потоков (TLP) в микропроцессоре необходимо иметь не менее двух аппаратных расширений для потоков. Это регистры общего назначения, счетчик команд, слово состояния процесса и т. п. В любой момент времени работает только один поток (тред). Он выполняется до возникновения определенной ситуации (например, выполнения команды загрузки регистра при отсутствии данных в кэш-памяти). В этом случае процессор переключается на выполнение другого потока. Поскольку при непопадании в кэш-память операции с памятью могут потребовать до сотни тактов процессора, его простои по причине ожидания данных могли бы быть весьма значительными. Современные процессоры, имеющие возможности спекулятивного внеочередного выполнения команд, в подобной ситуации могут продолжить выполнение других команд, но на практике число независимых команд быстро исчерпывается и процессор останавливается.
Архитектура с одновременным выполнением тредов — SMT (Simultaneous Multi-Threading) допускает одновременное выполнение нескольких потоков. В этом случае на каждом новом такте на выполнение в какое-либо исполнительное устройство может направляться команда любого потока. Одна из основных особенностей SMT у многих современных процессоров — переименование регистров, когда логические (архитектурные) регистры отображаются в физические, с которыми и ведется реальная работа. Техника переименования регистров может, очевидно, применяться для того, чтобы избежать прямого дублирования файлов регистров как аппаратной принадлежности потока. Анонсированная в 2002 году компанией Intel технология Hyper-Threading — пример многопоточной обработки команд. Данная технология является чем-то средним между многопоточной обработкой, реализованной в мультипроцессорных системах, и параллелизмом на уровне инструкций, реализованном в однопроцессорных системах. Фактически технология Hyper-Threading позволяет организовать два логических процессора в одном физическом. Таким образом, с точки зрения операционной системы и запущенного приложения в системе существует два процессора, что даёт возможность распределять загрузку задач между ними.
Посредством реализованного в технологии Hyper-Threading принципа параллельности можно обрабатывать инструкции в параллельном (а не в последовательном) режиме, то есть для обработки все инструкции разделяются на два параллельных потока. Это позволяет одновременно обрабатывать два различных приложения или два различных потока одного приложения и тем самым увеличить IPC процессора (количество инструкций, выполняемых процессором в секунду), что сказывается на росте его производительности.
В конструктивном плане процессор с поддержкой технологии Hyper-Threading состоит из двух логических процессоров, каждый из которых имеет свои регистры и контроллер прерываний (Architecture State, AS), а значит, две параллельно исполняемые задачи работают со своими собственными независимыми регистрами и прерываниями, но при этом используют одни и те же ресурсы процессора для выполнения своих задач. После активизации каждый из логических процессоров может самостоятельно и независимо от другого процессора выполнять свою задачу, обрабатывать прерывания либо блокироваться. Таким образом, от реальной двухпроцессорной конфигурации новая технология отличается только тем, что оба логических процессора используют одни и те же исполняющие ресурсы, одну и ту же разделяемую между двумя потоками кэш-память и одну и ту же системную шину. Использование двух логических процессоров позволяет усилить процесс параллелизма на уровне потока, реализованный в современных операционных системах и высокоэффективных приложениях. Команды от исполняемых параллельно потоков одновременно посылаются для обработки ядру процессора. Используя технологию out-of-order (исполнение командных инструкций не в порядке их поступления), ядро процессора способно параллельно обрабатывать оба потока за счёт использования нескольких исполнительных модулей.
Идея технологии Hyper-Threading тесно связана с микроархитектурой NetBurst процессора Pentium 4 и является в каком-то смысле её логическим продолжением.
Микроархитектура Intel NetBurst позволяет получить максимальный выигрыш в производительности при выполнении одиночного потока инструкций, то есть при выполнении одной задачи. Однако даже в случае специальной оптимизации программы не все исполнительные модули процессора оказываются задействованными на протяжении каждого тактового цикла. В среднем при выполнении кода, типичного для набора команд IA-32, реально используется только 35% исполнительных ресурсов процессора, а 65% исполнительных ресурсов процессора простаивают, что означает неэффективное использование возможностей процессора. Было бы логично реализовать работу процессора таким образом, чтобы в каждом тактовом цикле максимально использовать его возможности. Именно эту идею и реализует технология Hyper-Threading, подключая незадействованные ресурсы процессора к выполнению параллельной задачи.
Средства синхронизации потоков и процессов
Семафоры — представляют собой доступные ресурсы, которые могут быть приобретены несколькими потоками в одно и то же время, пока пул ресурсов не опустеет. Тогда дополнительные потоки должны ждать, пока требуемое количество ресурсов не будет снова доступно. Семафоры очень эффективны, поскольку они позволяют одновременный доступ к ресурсам. Семафор есть логическое расширение мьютекса — семафор со счетчиком 1 эквивалентен мьютексу, но счетчик может быть и более 1.
Описание программы
Разработанное приложение имеет простой и интуитивно понятный интерфейс работы с потоками. Интерфейс приложение отображает наглядно, сколько операций в секунду выполняется по каждому из 2 потоков, а ползунки снизу служат для назначения приоритета, каждое деление на шкале ползунка соответствует значению приоритета (низкий, средний, реального времени, высокий) под значением приоритета можно понять какую роль данное приложение будет получать в системе, то есть чем выше значение приоритета, тем выше роль данного приложения и тем больше оно будет потреблять ресурсов системы не рациональное использование приоритетов может вызвать сбои в работе, как приложения, так и всей системы в целом.
Листинг программы
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Для синхронизации действий, выполняемых разными потоками существует несколько различных способов. Условно их можно разделить на следующие:
· синхронизация с помощью глобальных переменных
· синхронизация с помощью обмена событиями
· синхронизация с помощью специальных объектов (событий, семафоров, критических секций, объектов исключительного владения и других)
Первый метод синхронизации следует признать самым неудачным, так как он требует постоянного опроса состояния глобальной переменной. У этого метода есть и более серьезные недостатки — так, например, возможна полная блокировка потоков, если поток, ожидающий изменения глобальной переменной имеет более высокий приоритет, чем поток, изменяющий эту переменную. Правда, его можно несколько улучшить — вводя дополнительные временные задержки между последовательными опросами.
Третий метод — синхронизация с помощью специальных объектов — потребует рассмотрения разных объектов и разных методов синхронизации с использованием объектов. В Win32 API существует большое число объектов, которые могут быть применены в качестве синхронизирующих, причем во многих случаях вместо одного объекта может применяться объект другого типа. Поэтому будет интересно рассмотреть несколько основных методов синхронизации с использованием объектов.
Общие представления о методах синхронизации
При рассмотрении способов синхронизации удобно выделить несколько основных способов, применяемых разными операционными системами. В числе таких способов можно выделить четыре метода:
· объекты исключительного владения
· синхронизация группой объектов
Последовательно рассмотрим эти основные методы, используя в качестве примера функции по работе с глобальной кучей. Попробуем абстрактно разобраться со свойствами этих функций, что бы понять, какие методы синхронизации и в каких случаях удобно применять.
Во–первых, глобальную кучу в целом можно рассматривать как некий сложный объект, над которым могут выполняться некоторые операции (пока мы рассматриваем только операции над кучей в целом, не вдаваясь в нюансы работы с отдельными блоками — при необходимости доступ к отдельным блокам кучи должен быть синхронизирован, но это уже не функции кучи, а проблема того, кто пользуется кучей).
Часть операций, например получение указателя на какой–либо блок в куче, не нуждается в изменении самой кучи. То есть функции, осуществляющие подобные операции могут выполняться одновременно разными потоками не конфликтуя друг с другом. Такие функции удобно назвать “читателями” — они не изменяют кучу как единый объект.
Другие операции, например выделение нового блока в куче, требуют внесения изменений в кучу — изменения в цепочке выделяемых блоков. Обычно такие изменения осуществляются не в одном месте, а требуется согласованное внесение изменений в нескольких структурах данных. В процессе такой операции структура кучи какое–то время оказывается нарушенной, вследствие чего одновременное выполнение таких действий должно быть исключено. Такие функции удобно назвать “писателями” — они изменяют кучу как единый объект.
Можно сформулировать несколько правил для работы с таким объектом:
· если к объекту имеет доступ читатель, то возможен одновременный доступ других читателей и запрещен доступ писателям;
· если объект свободен, то первый пришедший писатель или читатель имеет право доступа.
Рассмотренный пример очень удобен, так как подобная ситуация (много читателей, единственный писатель) встречается сплошь и рядом — а стандартного объекта для синхронизации доступа к такому объекту нет. Благодаря этому такой пример становится благодатной почвой для рассмотрения разных способов синхронизации.
Критические секции
Этот синхронизирующий объект может использоваться только локально внутри процесса, создавшего его. Остальные объекты могут быть использованы для синхронизации потоков разных процессов. Название объекта “критическая секция” связано с некоторым абстрактным выделением части программного кода (секции), выполняющего некоторые операции, порядок которых не может быть нарушен. То есть попытка двумя разными потоками одновременно выполнять код этой секции приведет к ошибке.
Например, такой секцией может быть удобно защитить функции–писатели, так как одновременный доступ нескольких писателей должен быть исключен.
Для критической секции вводят две операции:
· войти в секцию;
Пока какой–либо поток находится в критической секции, все остальные потоки при попытке войти в нее будут автоматически останавливаться в ожидании. Поток, уже вошедший в эту секцию, может входить в нее многократно, не ожидая ее освобождения.
· покинуть секцию;
При покидании потоком секции уменьшается счетчик числа вхождений этого потока в секцию, так что секция будет освобождена для других потоков только если поток выйдет из секции столько раз, сколько раз в нее входил. При освобождении критической секции будет пробужден только один поток, ожидающий разрешения на вход в эту секцию.
Вообще говоря, в других API, отличных от Win32 (например, OS/2), критическая секция рассматривается не как синхронизирующий объект, а как фрагмент кода программы, который может исполняться только одним потоком приложения. То есть вход в критическую секцию рассматривается как временное выключение механизма переключения потоков до выхода из этой секции. В Win32 API критические секции рассматриваются как объекты, что приводит к определенной путанице — они очень близки по своим свойствам к неименованным объектам исключительного владения (mutex, см. ниже).
При использовании критических секций надо следить, что бы в секции не выделялись чересчур большие фрагменты кода, так как это может привести к существенным задержкам в выполнении других потоков.
Можно выделить несколько случаев эффективного применения критических секций:
· все потоки имеют примерно равные права доступа (скажем, нельзя выделить чистых писателей и читателей);
· при построении составных синхронизирующих объектов, состоящих из нескольких стандартных, для защиты последовательных операций над составным объектом.
Объекты исключительного владения
Объекты исключительного владения — mutex (mut ualex clusion) — могут принадлежать только одному потоку одновременно. Соответственно определяются операции над этими объектами:
· затребовать владение объектом;
При запросе владения система проверяет, владеет–ли какой–либо другой поток этим объектом или нет. Если имеется другой поток–владелец, то данный поток останавливается до тех пор, пока объект не освободиться. Как только объект становится свободным, система отдает его во владение новому потоку. Поток, уже владеющий объектом, может многократно вступать во владение им.
· освободить объект;
При освобождении объекта система просматривает, имеются–ли другие потоки, ожидающие освобождения этого объекта. Если имеются, то возобновит работу только один поток, а все остальные продолжат ожидание — объект mutex может быть во владении только у одного потока. Освобождать объект может только тот поток, который им в данный момент владеет, другие потоки этого сделать не могут. Для полного освобождения объекта поток должен столько раз освободить его, сколько раз он затребовал владение с того момента, как ему дали этот объект во владение.
Если учесть, что владеть объектом mutex может только один поток, то получается, что такие объекты похожи на критические секции — с того момента, как система отдала объект во владение потоку все остальные, которые захотят получить его во владение, будут ожидать его освобождения. Отличия заключаются в некоторых нюансах использования — во–первых, объекты mutex могут быть использованы разными процессами (для этого предусмотрены именованные объекты, которые могут быть использованы другими процессами) и, во–вторых, ожидать владения этим объектом можно разными способами — с ограничением по времени или, например, использовать его для синхронизации сразу с несколькими объектами (другими объектами mutex, семафорами, событиями и прочим). Об этом — подробнее в последующих разделах.
События
События, как и объекты исключительного владения, могут использоваться для синхронизации потоков, принадлежащих разным приложениям. Самые значительные отличия сводятся к следующему:
· событиями никто не владеет — то есть устанавливать события в свободное или занятое состояние могут любые потоки, имеющие право доступа к этому объекту
· события различают только два состояния — свободное и занятое. Сколько бы раз вы не переводили событие в занятое состояние, один единственный вызов функции, освобождающей это событие, освободит его. И наоборот.
· в классическом варианте освобождение события разрешает запуск всех потоков, ожидающих его. Объекты исключительного владения и критические секции позволяли возобновить исполнение только одного потока[2] .
· смена состояния события осуществляется в любой момент времени. Так, для вхождения в критическую секцию или для получения объекта mutex во владение необходимо было дождаться их освобождения (что выполнялось автоматически). Для событий это не так.
Соответственно, применительно к событиям, говорят о двух основных состояниях: свободном (установленном) и занятом (сброшенном) и о трех операциях, выполняемых над ними:
· сбросить событие;
Событие в сброшенном состоянии считается занятым. Аналогия — флажок такси (в России — лампа зеленого цвета). Опущенный флаг (или выключенная лампа) означают, что такси занято. Любой поток, имеющий доступ к событию, может сбросить его, независимо от того, какой поток это событие устанавливал.
· установить (иногда — послать) событие;
Установленное (посланное) событие считается свободным. Как только событие освобождается, все ожидающие его потоки могут возобновить свое исполнение (см. сноску). Устанавливать событие может также любой поток.
· дождаться события;
Так как сброс и установка событий происходит в любой момент времени, независимо от предыдущего состояния события, то приходится вводить специальную операцию — дождаться освобождения объекта.
Эти особенности выделяют события в особую категорию синхронизирующих объектов. Рассмотренные ранее критические секции и объекты исключительного владения позволяют осуществить монопольный доступ к какому–либо ресурсу или объекту данных, в то время как события определяют некоторые условия, после которых возможно выполнение тех или иных операций.
Пример. Возвращаясь к примеру с глобальной кучей — для работы с ней необходимо создать составной синхронизирующий объект. Пример такого объекта можно найти в книге “Windows для профессионалов” Джеффри Рихтера. Естественно, логика построения объекта одинакова и в рассматриваемом случае, что позволяет детально сравнить несколько близких решений и заострить внимание на некоторых “мелочах”. Сейчас мы рассмотрим только “скелет” такого объекта и основные правила работы с ним. Позже, после рассмотрения функций Win32 API, рассмотрим конкретную реализацию этого составного объекта и сравним ее с чрезвычайно похожим объектом, приведенным в книге Рихтера.
Сначала попробуем составить представление о тех стандартных объектах, которые надо использовать для построения составного синхронизирующего объекта. Мы имеем дело с потоками–писателями, имеющими исключительный доступ к данным, и потоками–читателями, которые могут иметь одновременный доступ к тем–же данным. Однако наличие хотя–бы одного читателя исключает для писателей возможность доступа к данным.
Из этих соображений следует наличие:
· Критической секции или объекта исключительного владения для синхронизации потоков–писателей. Выбор одного из этих объектов определяется необходимостью исключительного доступа только одного потока–писателя к данным. Удобно также, что освободить секцию или mutex может только тот поток, который его занял. В рассматриваемом примере будем использовать объект mutex, для большей схожести с Рихтером (это позволит подчернуть несколько нюансов в разработке такого объекта).
· События, переходящего в занятое состояние при наличии хотя–бы одного читателя. В данном случае целесообразно выбрать событие, которое будет сбрасываться в занятое состояние при появлении первого потока–читателя и устанавливаться в свободное последним читателем (последним из числа тех, кто пытается осуществить чтение одновременно с другими, но не вообще последнего).
· Счетчика числа потоков–читателей, осуществляющих одновременный доступ. Нулевое значение счетчика соответствует установленному в свободное состояние событию. При увеличении счетчика проверяется его начальное значение, и если оно было 0, то событие сбрасывается в занятое состояние. При уменьшении счетчика проверяется результат — если он 0, то событие устанавливается в свободное состояние.
Можно примерно описать структуру такого объекта (назовем его NEWSWMRG, по сравнению с объектом SWMRG, рассматриваемым у Рихтера — S ingle W riter M ulti R eader G uard). Эта структура должна быть описана примерно так:
struct NEWSWMRG СОБЫТИЕ НЕТ_ЧИТАТЕЛЕЙ;
СЧЕТЧИК ЧИСЛО_ЧИТАТЕЛЕЙ;
ОБЪЕКТ_ИСКЛЮЧИТЕЛЬНОГО_ВЛАДЕНИЯ ЕСТЬ_ПИСАТЕЛИ;
>;
Для работы с ней надо будет выделить четыре специальных функции (инициализацию и удаление этого объекта пока не рассматриваем): две функции, используемые потоками–читателями для получения доступа к данным и для обозначения конца операции чтения, а также две аналогичных функции для потоков–писателей.
void RequestWriter( NEWSWMRG* p ) // дождаться разрешения для писателя
Захватить объект ЕСТЬ_ПИСАТЕЛИ;
// если объект получен во владение — других писателей больше нет
// и пока мы его не освободим — не появятся.
Дождаться события НЕТ_ЧИТАТЕЛЕЙ;
// если событие установлено — читателей также нет
>
void ReleaseWriter( NEWSWMRG* p ) // после изменения данных разрешаем доступ другим писателям и читателям
Освободить объект ЕСТЬ_ПИСАТЕЛИ;
>
void RequestReader( NEWSWMRG* p ) // дождаться разрешения для читателя — убедиться, что нет писателей
// для этого можно захватить объект ЕСТЬ_ПИСАТЕЛИ и сразу освободить его
// захват пройдет только тогда, когда писателей нет.
Захватить объект ЕСТЬ_ПИСАТЕЛИ;
// реально надо не только убедиться в отсутствии писателей, но и
// увеличить счетчик и при необходимости сбросить событие НЕТ_ЧИТАТЕЛЕЙ
if ( ЧИСЛО_ЧИТАТЕЛЕЙ == 0 ) Сбросить событие НЕТ_ЧИТАТЕЛЕЙ в занятое;
ЧИСЛО_ЧИТАТЕЛЕЙ++;
// а вот теперь можно смело освобождать объект ЕСТЬ_ПИСАТЕЛИ — во время
// работы читателя достаточно иметь сброшенное событие НЕТ_ЧИТАТЕЛЕЙ Освободить объект ЕСТЬ_ПИСАТЕЛИ;
>
void ReleaseReader( NEWSWMRG* p ) // после считывания данных уменьшаем счетчик и разрешаем доступ писателям
// при достижении нулевого значения счетчика.
--ЧИСЛО_ЧИТАТЕЛЕЙ;
if ( ЧИСЛО_ЧИТАТЕЛЕЙ == 0 ) Установить событие НЕТ_ЧИТАТЕЛЕЙ в свободное;
>
Естественно, это еще не рабочая схема, а только намек на нее. Полностью обсудим некоторые особенности при рассмотрении функций Win32 API. На первый взгляд виден небольшой “прокол” — в функции ReleaseReader счетчик сначала уменьшается, а только потом происходит проверка его значения и установка события при необходимости. Однако возможен (хотя и очень маловероятен) случай, когда поток будет прерван для выполнения операций другими потоками где–то между уменьшением счетчика и установкой события. В это время другие потоки могут изменить значение счетчика и событие будет установлено тогда, когда этого делать уже не следует.
Выйти из этой ситуации можно разными путями — либо добавлением еще одного объекта исключительного владения или критической секции для упорядочивания операций со счетчиком, либо другими способами. Для разбирательства с этими альтернативными способами следует рассмотреть синхронизацию с группой объектов.
[2] В Win32 API существуют специальные механизмы, позволяющие возобновлять исполнение только одного потока при освобожении события. Однако, по сравнению с другими операционными системами, скажем OS/2, такое поведение события нетипично.
Название работы: Необходимость синхронизации процессов и потоков. Критическая секция
Предметная область: Информатика, кибернетика и программирование
Описание: Необходимость синхронизации процессов и потоков.4 Синхронизация процессов и потоков. В многозадачной ОС синхронизация процессов и потоков необходима для исключения конфликтных ситуаций при обмене данными между ними разделении данных доступе к процессору и устройствам вводавывода. Пренебрежение вопросами синхронизации процессов выполняющихся в многозадачной системе может привести к неправильной их работе или даже к краху системы.
Размер файла: 19.14 KB
Работу скачали: 15 чел.
Вопрос 21. Необходимость синхронизации процессов и потоков. Критическая секция.
§4.4 Синхронизация процессов и потоков.
В многозадачной ОС синхронизация процессов и потоков необходима для исключения конфликтных ситуаций при обмене данными между ними, разделении данных, доступе к процессору и устройствам ввода-вывода. Во многих ОС эти средства называются средствами межпроцессного взаимодействия ( InterProcess Communications IPC ).
Выполнение потока в многозадачной среде имеет асинхронный характер, поэтому сложно сказать, на каком этапе выполнения будет находиться поток в определенный момент времени. Задача синхронизации заключается в согласовании скоростей потоков путем их приостановки до наступления некоторого события и последующей активизации при наступлении этого события.
Пренебрежение вопросами синхронизации процессов, выполняющихся в многозадачной системе, может привести к неправильной их работе или даже к краху системы.
Рассмотрим в качестве примера программу печати файлов (принт-сервер). Эта программа печатает по очереди все файлы, имена которых последовательно в порядке поступления записывают в специальный общедоступный файл "заказов" другие программы. В данном случае это процессы-клиенты R и S, содержащие операции R 1, R 2, R 3 и S 1, S 2, S 3 (рис. 4.8). Особая переменная NEXT, также доступная всем процессам-клиентам, содержит номер первой свободной для записи имени файла позиции файла "заказов". Процессы-клиенты читают эту переменную, записывают в соответствующую позицию файла "заказов" имя своего файла и наращивают значение NEXT на единицу. Предположим, что в некоторый момент процесс R решил распечатать свой файл, для этого он прочитал значение переменной NEXT, значение которой предположим равно 4. Процесс запомнил это значение, но поместить имя файла не успел, так как его выполнение было прервано (например, вследствие исчерпания кванта). Очередной процесс S, желающий распечатать файл, прочитал то же самое значение переменной NEXT, поместил в четвертую позицию имя своего файла и нарастил значение переменной на единицу. Когда в очередной раз управление будет передано процессу R, то он, продолжая свое выполнение, в полном соответствии со значением текущей свободной позиции, полученным во время предыдущей итерации, запишет имя файла также в позицию 4, поверх имени файла процесса S. Таким образом, файл процесса S не будет напечатан.
Рис. 4 .8. Доступ процессов к разделяемым данным
Можно представить и другое развитие событий: были потеряны файлы нескольких процессов или, напротив, не был потерян ни один файл. В данном случае все определяется взаимными скоростями процессов и моментами их прерывания. Сложность проблемы синхронизации состоит в нерегулярности возникающих ситуаций.
Ситуация, когда два или более процессов обрабатывают разделяемые данные, и конечный результат зависит от соотношения скоростей процессов, называется состоянием состязания или гонками .
Критическая секция это часть программы, которая должна выполняться без прерываний со стороны других потоков. Критическая секция всегда определяется по отношению к определенным критическим данным , при несогласованном изменении которых результат выполнения программы может быть непредсказуем. Во всех потоках, работающих с критическими данными, должна быть определена критическая секция, которая в общем случае состоит из разных последовательностей команд. Критическая секция, например, используется для предоставления доступа к разделяемым ресурсам ВС.
Чтобы исключить эффект гонок по отношению к разделяемым данным, необходимо обеспечить, чтобы в каждый момент в критической секции, связанной с этими данными, находился только один поток. Этот прием называют взаимным исключением. При этом неважно, находится этот поток в активном или в приостановленном состоянии.
Для реализации взаимных исключений используются различные способы: запрещение прерываний , блокирующие переменные , семафоры , синхронизирующие объекты ОС , рассмотренные ниже.
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Одним из первых механизмов, предложенных для синхронизации поведения процессов, стали семафоры, концепцию которых описал Дейкстра (Dijkstra) в 1965 году. Он предложил использовать переменные, которые могут принимать целые неотрицательные значения. Такие переменные, используемые для синхронизации вычислительных процессов, получили название семафоров.
Семафор начинает действовать с назначенного для него начального отсчета. Всякий раз, когда поток получает права владения эти объектом (через функцию ожидания), счетчик в семафоре уменьшается на единицу. И всякий раз, когда поток уступает свои права владения объектом владения этим объектом, счетчик в семафоре увеличивается на единицу. Как только счетчик в семафоре достигнет нуля, семафор блокируется в несигнальном состоянии и ни один из потоков не может получить к нему доступ.
Для работы с семафорами вводятся два примитива, традиционно обозначаемых Р (от датского слова proberen — проверять) и V (от verhogen увеличивать). Пусть переменная S представляет собой семафор. Тогда классическое определение действия V ( S ) и P ( S ) операций выглядит следующим образом:
ТО процесс блокируется;
Эта запись означает следующее:
- при выполнении операции P над семафором S сначала проверяется его значение. Если оно больше 0, то из S вычитается 1.
Если оно меньше или равно 0, то процесс блокируется до тех пор, пока S не станет больше 0, после чего из S вычитается 1. Успешная проверка и уменьшение являются неделимой операцией.
- при выполнении операции V над семафором S к его значению просто прибавляется 1. Во время выполнения этой операции к переменной S нет доступа другим потокам.
Никакие прерывания во время выполнения примитивов V и Р недопустимы.
Одной из типовых задач, требующих организации взаимодействия процессов с использованием семафоров, является задача producer - consumer (производитель-потребитель).
Например. Пусть буферный пул состоит из N буферов, каждый из которых может содержать одну запись.
Поток-производитель осуществляет запись в буфер, а поток-потребитель – чтение из буфера. В общем случае поток-производитель и поток-потребитель могут иметь различные скорости и обращаться к буферному пулу с переменой интенсивностью, В один период скорость записи может превышать скорость чтения, в другой - наоборот.
Для правильной совместной работы поток-производитель должен приостанавливаться, когда все буферы оказываются занятыми, и активизироваться при освобождении хотя бы одного буфера. Напротив, поток-потребитель должен приостанавливаться, когда все буферы пусты, и активизироваться при появлении хоти бы одной записи.
Введем два семафора: е — число пустых буферов, и f — число заполненных буферов, причем в исходном состоянии е = N , a f = 0. Тогда работа потоков с общим буферным пулом может быть описана следующим образом (рис.1).
Поток-производитель прежде всего выполняет операцию Р(е), с помощью которой он проверяет, имеются ли в буферном пуле незаполненные буферы. В соответствии с семантикой операции Р, если семафор е равен 0 (т.е. свободных буферов в данный момент нет), то поток-производитель переходит в состояние ожидания.
Если же значением е является положительное число, то он уменьшает число свободных буферов, записывает данные в очередной свободный буфер и после этого наращивает число занятых буферов операцией V ( f ). Поток-потребитель действует аналогичным образом, с той разницей, что он начинает работ у с проверки наличия заполненных буферов, а после чтения данных наращивает количество свободных буферов.
Семафор может находиться в сигнальном или несигнальном состоянии. Приложение выполняет ожидание для семафора при помощи таких функций, как WaitForSingleObject() или WaitForMultipleObject().
Рассмотрим средства синхронизации Win32 АР I , основанные па использовании объектов исполнительной системы с дескрипторами. Для всех таких объектов организация ожидания сводится к вызыванию потоком управления функции ожидания, что принимает как параметр дескриптор объекта (или массив дескрипторов) и проверяет, не состоялась ли сигнализация этого объекта. Условие сигнализации зависит от объекта синхронизации.
В случае невыполнения условия сигнализации поток переходит в состояние ожидания, тратя очень мало ресурсов (процессорного времени и тому подобное), до тех пор, пока сигнализация все-таки не состоится или пока не минует максимальное время ожидания, если он был задан.
Когда сигнализация состоялась, поток немедленно выходит из состояния ожидания (из функции ожидания) и продолжает свое выполнение. Функция ожидания в этом случае перед выходом может изменить состояние объекта (например, занять блокировку).
Для ожидания сигнализации одного объекта у Win32 используют функцию WaitForSingleQbject(), синтаксис которой следующий :
DWORD Wait ForSingleObject(HANDLE handle, DWORD timeout);
handle – определяет дескриптор синхронизированного объекта;
timeout – задает максимальное время ожидания в милисеку н дах (значение INFINITE свидетельствует о бесконечном ожидании).
Возвращаемое значение: Функция WaitForSingle O bject() возвращает такие значения: WAIT_OBJECT_0 - состоялась сигнализация объекта; WAIT_TIMEOUT - минуло время ожидания (если timeout не равнялся INFINITE), а объект своего состояния так и не изменил.
Можно ожидать сигнализации не одного объекта, а нескольких сразу (некоторый аналог использования нескольких условий ожидания для условной переменной). Для этого используют функцию WaitForMultipleObjects():
DWORD W aitForMultipleObjects ( DWORD count , CONST HANDLE handles , BOOL waitall , DWORD timeout );
count – длина массива дескрипторов;
handles – задает максимальное время ожидания в миллисекундах (значение INFINITE свидетельствует о бесконечном ожидании).
waitall – флажок режима ожидания ;
timeout – аналогичная к WaitForSingleObject
Функция принимает массив дескрипторов handles длиной count (максимальная длина массива 64 элемента). Режим ожидания и возвращенное значение зависеть от флажка waitall.
Если waitall равняется TRUE, задан режим ожидания всех объектов. Ожидание завершается в случае осуществления сигнализации всех объектов, функция повернет WAIT_ O BJECT_0.
Если waitall равняется FALSE, задан режим ожидания одного объекта. Ожидание завершается в случае осуществления сигнализации хотя бы одного из объектов, функция повернет WA I T_OBJECT_0+i, где i - индекс дескриптора этого объекта в массиве handles.
Применительно к семафорам, если он находится в несигнальном состоянии, задача, вызвавшая для него функцию WaitForSingleObject(), находится в состоянии ожидания. Когда же состояние семафора становится сигнальным, работа задачи возобновляется.
С каждым семафором связывается счетчик, начальное и максимальные значения которого задаются при создании семафора. Значение этого счетчика уменьшается, когда задача вызывает для семафора функцию WaitForSingleObject() или WaitForMultipleObject(), и увеличивается при вызове функции ReleaseSemaphore ().
Если значение счетчика семафора равно нулю, он находится в несигнальном состоянии. Если же это значение больше нуля, семафор переходит в сигнальное состояние.
Например. Пусть приложение создало семафор, указав для него максимальное значение счетчика, равное трем. Пусть начальное значение этого счетчика также будет равно трем.
Если в этой ситуации несколько запускаемых по очереди задач будут выполнять с помощью функции WaitForSingleObject() ожидание семафора, то первые три запущенные задачи будут работать, а все остальные перейдут в состояние ожидания.
Это связано с тем, что первые три вызова функции WaitForSingleObject() приведут к последовательному уменьшению значения счетчика семафора до нуля, в результате чего семафор переключится в несигнальное состояние.
Задача, запущенная четвертой, вызовет функцию WaitForSingleObject() для неотмеченного семафора, в результате чего она будет ждать. Точно также, задачи, запущенные после запуска четвертой задачи, будут выполнять ожидание для того же семафора.
Как долго продлится ожидание?
До тех пор, пока одна из первых трех задач не освободит семафор, увеличив его счетчик на единицу вызовом функции ReleaseSemaphore (). Сразу после этого будет запущена одна из задач, ожидающих наш семафор.
Рассмотрим функции программного интерфейса операционной системы Windows, предназначенные для работы с семафорами.
Для того, чтобы создать семафор, приложение должно вызвать функцию CreateSemaphore (), синтаксис которой выглядит следующим образом.
HANDLE CreateSemaphore ( LPSECURITY _ ATTRIBUTES lpThreadSecurity , LONG lSemInitialCount , LONG lSemMaxCount , LPCTSTR lpszSemName )
lpThreadSecurity – указатель на структуру, содержащую атрибуты доступа к семафору. Если атрибуты не используются, он может содержать значение, равное NULL ;
lSemInitialCount – начальное значение счетчика в семафоре, которое должно быть больше или равно нулю и меньше либо равно значению параметра lSemMaxCount ;
lSemMaxCount – максимальное значение счетчика в семафоре. Это значение должно быть больше нуля;
lpszSemName – указатель на строку, содержащую имя семафора. Имя не должно совпадать с именем существующего события, семафора или объекта отображения файла;
Возвращаемое значение. При успешном выполнении функция возвращает хэндл созданного семафора, в противном случае – возвращается NULL .
Для уничтожения семафора вы должны передать его идентификатор функции CloseHandle(). Заметим, что при завершении процесса все созданные им семафоры уничтожаются автоматически.
Если семафор используется только для синхронизации задач, созданных в рамках одного приложения, вы можете создать безымянный семафор, указав в качестве параметра lpszSemName функции CreateSemaphore() значение NULL.
В том случае, когда необходимо синхронизовать задачи разных процессов, следует определить имя семафора. При этом один процесс создает семафор с помощью функции CreateSemaphore, а второй открывает его, получая идентификатор для уже существующего семафора.
Существующий семафор можно открыть функцией OpenSemaphore (), синтаксис которой следующий
HANDLE OpenSemaphore (DWORD dwAccessFlag, BOOL bInherit , LPCTSTR lpszSemName)
dwAccessFlag – указатель на требуемый тип доступа к семафору;
bInherit – определяет возможность наследования семафора другими процессами, создаваемые функцией CreateProcess ();
lpszSemName – указатель на строку, содержащую имя открываемого семафора.
Возвращаемое значение. При успешном выполнении функция возвращает хэндл открытого семафора, в противном случае – возвращается NULL .
Флаги доступа могут принимать одно из трех значений:
Устанавливает все возможное флаги доступа для данного семафора
Разрешает изменение счетчика ресурсов в функции ReleaseSemaphore ()
Разрешает использование в любой из ожидающих функций сигнала об изменении состояния семафора
Для увеличения значения счетчика семафора приложение должно использовать функцию ReleaseSemaphore (), синтаксис которой выглядит следующим образом
BOOL ReleaseSemaphore ( HANDLE hSemaphore , LONG lReleaseCount , LPLONG lpPreviosCount )
hSemaphore – хэндл освобожденного объекта семафора;
lReleaseCount – число, которое определяет значение, установленное в счетчике ресурсов семафора при его освобождении;
lpPreviosCount – указатель на место хранения предыдущего значения счетчика.
Возвращаемое значение. При успешном выполнении функция возвращает TRUE , в противном случае – возвращается NULL .
Функция ReleaseSemaphore() увеличивает значение счетчика семафора, идентификатор которого передается ей через параметр hSemaphore, на значение, указанное в параметре l ReleaseCount.
Заметим, что через параметр l ReleaseCount вы можете передавать только положительное значение, большее нуля.
При этом если в результате увеличения новое значение счетчика должно будет превысить максимальное значение, заданное при создании семафора, функция ReleaseSemaphore()возвращает признак ошибки и не изменяет значение счетчика.
Предыдущее значение счетчика, которое было до использования функции ReleaseSemaphore(), записывается в переменную типа LONG. Адрес этой переменной передается функции через параметр lpPreviousCount.
Таким образом, функция используется для решения двух задач:
Во-первых, с помощью этой функции задачи освобождают ресурс, доступ к которому регулируется семафором. Они могут делать это после использования ресурса или перед своим завершением.
Во-вторых, эта функция может быть использована на этапе инициализации мультизадачного приложения.
Создавая семафор с начальным значением счетчика, равным нулю, главная задача блокирует работу задач, выполняющих ожидание этого семафора. После завершения инициализации главная задача с помощью функции ReleaseSemaphore() может увеличить значение счетчика семафора до максимального, в результате чего известное количество ожидающих задач будет активизировано.
В программном интерфейсе операционной системы Windows нет функции, специально предназначенной для уменьшения значения счетчика семафора.
Этот счетчик уменьшается, когда задача вызывает функции ожидания, такие как WaitForSingleObject() или WaitForMultipleObject(). Если задача вызывает несколько раз функцию ожидания для одного и того же семафора, содержимое его счетчика каждый раз будет уменьшаться.
Таким образом, алгоритм работы с семафорами выглядит следующим образом:
поток создает или открывает семафор с помощью функций CreateSemaphore () или OpenSemaphore () соответственно;
поток вызывает функцию WaitForSingleObject () для того, чтобы определить, свободен ли требуемый потоку ресурс. В зависимости от результата, возвращаемого этой функцией, определяются дальнейшие действия;
при завершении поток вызывает функцию ReleaseSemaphore (), освобождающую семафор.
Единственная возможность определения текущего значения счетчика семафора заключается в увеличении этого значения функцией ReleaseSemaphore() Значение счетчика, которое было до увеличения, будет записано в переменную, адрес которой передается функции ReleaseSemaphore() через параметр lplPreviousCount.
Одной из проблем, которая возникает при использовании семафоров является проблема синхронизации – взаимные блокировки (дедлоки, клинчи, тупики).
Реферат по ОС Linux, о конкуренции за ресурсы, рассматриваются интерфейсы к ним, а также особенности их работы и использования.
Рассматриваются
- Атомарные операции
- Целочисленные атомарные операции
- Битовые атомарные операции
- Спин-блокировки
- Другие средства работы со спин-блокировками
- Спин-блокировки и обработчики нижних половин
- Спин-блокировки чтения-записи
- Семафоры
- Создание и инициализация семафоров
- Семафоры чтения-записи
- Условные переменные
- BLK: Большая блокировка ядра
- Секвентные блокировки
- Средства запрещения преемптивности
- Барьеры и порядок выполнения
Снабжена достаточно подробными примерами кода.
Содержит длинный, короткий и совсем короткий вариант реферата.
Абельсон. Структура и интерпретация компьютерных программ (второе издание)
- формат pdf
- размер 3.54 МБ
- добавлен 02 ноября 2009 г.
Добросвет, 2006, второе издание. Структура и интерпретация компьютерных программ — это вводный курс по информатике в Массачусетском Технологическом институте (MIT). Он обязателен для всех студентов MIT на специальностях ѕэлектротехникаї и информатика, как одна из четырех частей ѕобщей базовой программы обучения, которая включает еще два курса по электрическим схемам и линейным системам, а также курс по проектированию цифровых систем. Мы принимал.
Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение
- формат pdf
- размер 3.45 МБ
- добавлен 06 сентября 2008 г.
2002 г. Операционные системы и среды. Основные понятия: Понятие операционной среды. Понятия вычислительного процесса и ресурса. Диаграмма состояний процесса. Реализация понятия последовательного процесса в Ос. Процессы и треды. Прерывания. Основные виды ресурсов. классификация операционных систем. контрольные вопросы и задачи. Управление задачами и памятью в операционных системах: Планирование и диспетчеризация процессов и задач. сегментная, стр.
Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение
- формат djvu
- размер 9.73 МБ
- добавлен 06 сентября 2008 г.
2003 г. ВНИМАНИЕ, отсутствуют стр. 243-462 (отсутствующие разделы есть в одноименной ниже представленной книге формата pdf 2002 г.). В данной версии исправлена ошибка с порядком следования страниц. В данном учебнике помимо общетеоретических вопросов описаны конкретные реализации системных программ. Поэтому учебник может быть полезен не только студентам, детально изучающим системное программное обеспечение, но и тем, кто собирается самостоятельно.
Гордеев А.В., Молчанов А.Ю. Системное программное обеспечение
- формат djvu
- размер 6.93 МБ
- добавлен 23 октября 2011 г.
Учебник для ВУЗов. Издательство "Питер" - 2001г., 736стр. Качество хорошее. В отличии от вариантов этой книги, выложенных на этом сайте, данный экземпляр не кастрирован, и содержит все страницы, включая с 243 по 462, где описаны в том числе так необходимые Формы Бэкуса-Наура. Разделы: часть 1. Операционные системы и среды. Основные понятия. Управление задачами и памятью в операционных системах. Особенности архитектуры микропроцессоров i80x86.
Кузьмин Д.А. Системное программное обеспечение. Методическое пособие
- формат pdf
- размер 1.49 МБ
- добавлен 04 октября 2010 г.
В методическом пособии дается описание 14 лабораторных работ по дисциплине "Системное программное обеспечение". Основной акцент делается на изучение организации управления процессами на примере OC Linux, которая является многопроцессной Unix - подобной операционной системы (ОС). Данная OC представляет собой систему с открытым кодом, что обеспечивает возможность использования ее в образовательных учреждениях. СФУ, Красноярск, 2007 г.
Кузьмин Д.А., Наревский Ю.В. Системное программное обеспечение
- формат pdf
- размер 1.49 МБ
- добавлен 08 мая 2011 г.
Конспект лекций. - Красноярск: СФУ, 2007. - 272с. Оглавление Введение в курс Раздел 1. Общая характеристика операционных систем . История развития и совершенствования современных операционных систем (ОС) Общая характеристика современных операционных систем Особенности организации семейства Unix-подобных систем Раздел 2. Процессы Понятие и реализация процессов Планирование процессов Взаимодействие процессов Синхронизация процессов.
Кучеров М.М., Кузьмин Д.А. Системное программное обеспечение. Операционные системы
- формат pdf
- размер 862.63 КБ
- добавлен 08 мая 2011 г.
Учебное пособие. - Красноярск: СФУ, 2007. - 129с. Цель изучения операционных систем. Процессы. Параллельные потоки. Кооперативные потоки. Синхронизация. Взаимное исключение. Определение семафоров. Определение монитора. Условия возникновения тупика. Принципы планирования процессора. Организация операционных систем. Организация и управление памятью. Кэширование и трансляция адресов. Управление виртуальной памятью.
Прытков В.А. Конспект лекций по дисциплине Системное программное обеспечение ЭВМ
- формат pdf
- размер 2.91 МБ
- добавлен 11 августа 2011 г.
Реферат - Системное программное обеспечение (СПО)
- формат doc
- размер 65.5 КБ
- добавлен 14 марта 2011 г.
Реферат по вычислительным системам на тему "Системное программное обеспечение". В работе рассматриваются следующие вопросы: Системное программное обеспечение, его состав. Операционные системы, их функции. Системы управления файлами. Утилиты, их функции и типы. Системы программирования. Требования к системному программному обеспечению.
Хоар Ч. Взаимодействующие последовательные процессы
- формат pdf
- размер 4.3 МБ
- добавлен 13 февраля 2011 г.
Книга известного системного программиста и теоретика информатики (Великобритания), последовательно излагающая теорию взаимодействующих процессов; эта тематика тесно связана с такими реальными понятиями, как операционные системы, мультипроцессорные комплексы и сети ЭВМ. Автор рассматривает параллелизм в языках высокого уровня АДА, Симула 67, Паскаль. Для специалистов в области системного программирования, теоретической информатики, математической.
Читайте также: