20. Синхронизация процессов. Способ использования

семафорного механизма. Мониторы.

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

Семафорный механизм. Предложен в 1965г Э.Дейкстра.

Семафор- переменная специального типа, которая доступна параллельным процессам для проведения над ней только двух видов примитивных операций (простейших) "закрытия" и "открытия", называемых соответственно P- и V-операциями.

Пусть имеется некоторый ресурс R. Поставим ему в соответствие целочисленную переменную семафор: S. Тогда:

- операция P(S) уменьшает величину S на единицу и :

если S.0, то процесс продолжает работу;

если S<0, то процесс блокируется, пока операция V(S), выполненная другим процессом, не разблокирует его.

-операция V(S) увеличивает величину S на единицу, и если после этого S>0, то ранее заблокированный процесс разблокируется, а также процесс, выполнивший операцию V(S), может продолжаться далее.

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

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

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

Для синхронизации обобщенных отношений "поставщиков и потребителей" (количество сообщений в буфере больше одного) вводят три общих семафора:

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

Для синхронизации процессов кроме семафорного механизма применяются так называемые мониторы.

Монитор - это набор процедур и структур данных, которые выполняют все работы по организации доступа к ресурсу или группе однотипных ресурсов.

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

21. Синхронизация процессов. Тупики.

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

ТУПИКИ

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

Пусть процесс А владеет ресурсом R1 и ему дополнительно требуется ресурс R2, в то же время процесс В владеет ресурсом R2 и ему дополнительно требуется ресурс R1. В этом случае говорят, что эти процессы зашли в тупик.

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

- принудительное изъятие ресурсов или;

- ликвидация процессов.

Совокупность условий необходимых и достаточных для возникновения тупиков:

Процессы не разрешают отведенный им ресурс одновременно использовать другим процессам(взаимное исключение);

Требуя новые ресурсы, процессы не отдают полученные ранее (условие ожидания);

Ресурсы не могут быть отняты у процессов(отсутствие предпочтения);

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

Тупики можно предотвращать, обнаруживать и устранять.

Способы предотвращения тупика.

ПЕРВЫЙ ПОДХОД

Каждый процесс должен запрашивать сразу все необходимые ему ресурсы, и только получив их может начинать свою работу(устраняется условие ожидания);

Если процесс получает отказ на запрашиваемый ресурс, то он должен освободить занятые им ресурсы(устраняется отсутствие предпочтения);

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

Такой подход приводит к неэффективному использованию ресурсов,

однако легко реализуется.

ВТОРОЙ ПОДХОД (Алгоритм банкира)

Имеется N единиц некоторого ресурса R и на обслуживание принимаются только те процессы, которым может потребоваться не более N единиц ресурса.

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

Поступает новый запрос. Он может быть принят на обслуживание если:

- оставшийся после его удовлетворения ресурс - должен быть достаточным для завершения хотя бы одного из процессов, ранее уже получивших часть ресурса;

- освобожденный этим процессом ресурс и неиспользованный ранее ресурс вместе должны быть достаточны для завершения еще хотя бы одного процесса;

- и так далее, до завершения всех начатых процессов.

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

Выход из тупика: Существует два общих подхода:

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

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

а) Приоритет процесса;

б) Затраты времени на повторный запуск процесса и его выполнение до точки прекращения;

в) Внешняя цена, определяемая пользователем породившим этот процесс (студент, администрация, системный программист, производство)

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

22. Управление памятью.Содержимое памяти . Типы

адресов.

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

Память распределяется между пользовательскими и системными программами ОС.

К основным функциям ОС по управлению памятью относятся:

Учет свободной и занятой памяти;

Выделение памяти процессам и ee освобождение;

Вытеснение кодов и данных процессов на диск, когда памяти не хватает и возврат на место;

Настройка адресов на конкретную область физической памяти;

Дефрагментация;

Защита памяти.

операционная система должна выполнять такие функции.

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

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

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

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

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

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

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

Аппаратное обеспечение процессора вместе с операционной системой предоставляют пользователю "виртуальный процессор", который имеет доступ к виртуальной памяти. Это хранилище может быть организовано в виде линейного адресного пространства или в виде набора сегментов, представляющих собой непрерывные блоки переменной длины. с помощью средств языка программирования можно обращаться к ячейкам виртуальной памяти, в которых содержится программа и ее данные. Чтобы изолировать процессы друг от друга, каждому из них можно выделить свою область памяти, не пересекающуюся с областью памяти другого процесса. Общее использование памяти можно организовать, частично перекрывая участки двух областей виртуальной памяти. Файлы создаются на долговременном запоминающем устройстве. Чтобы с ними могли работать программы, файлы или их фрагменты могут копироваться в виртуальную память.

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

Типы адресов

Для идентификации команд программы и данных используются адреса.

Адреса подразделяются на:

Символьные имена. Присваивает программист (например метки);

Виртуальные адреса. Формирует транслятор. Начальный адрес равен нулю;

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

Совокупность виртуальных адресов составляет виртуальное адресное пространство. Виртуальное адресное пространство определяется разрядностью компьютера. Для 32-разрядных –4 Гб.

Существует два основных типа представления виртуальных адресов:

Линейная, при которой адрес начала всегда равен нулю, а адрес целое число;

Деление на сегменты, при котором адрес – это пара чисел (n,m), где n- номер сегмента, m- смещение.

Некоторые понятия связанные с виртуальными адресами

Максимально возможное виртуальное адресное пространство(ВАП) – определяется разрядностью процессора. Для 32 – разрядного Intel Pentium эта величина составляет 4Гб.

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

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

Системная и пользовательская части ВАП (по 2 Гб каждая).

23. Иерархия запоминающих устройств. Принцип и

алгоритм кэширования данных . Проблема согласо-

вания данных.

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

Рис. 2.17. Иерархия ЗУ

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

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

Рис. 2.18. Кэш-память

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

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

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

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

Проблема согласования данных

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

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

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

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

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