7.-Конспект-лекций.-ОП.01-ОСиСреды.-09.02.07_compressed. Конспекты лекций по дисциплине оп. 01 Операционные системы и среды
 Скачать 1 Mb.
|
|
Необходимость синхронизации и гонки Пренебрежение вопросами синхронизации в многопоточной системе может при- вести к неправильному решению задачи или даже к краху системы. Рассмотрим, например (рис. 4.16), задачу ведения базы данных клиентов некоторого предприятия. Каждому клиенту отводится отдельная запись в базе данных, в которой среди прочих полей имеются поля Заказ и Оплата. Программа, ведущая базу данных, оформлена как единый процесс, имеющий несколько потоков, в том числе поток А, который заносит в базу данных информацию о заказах, поступивших от клиентов, и поток В, который фиксирует в базе данных сведения об оплате клиентами выставленных счетов. Оба эти потока совместно работают над общим файлом базы данных, используя однотипные алгоритмы, включающие три шага. 1. Считать из файла базы данных в буфер запись о клиенте с заданным иденти- фикатором. 2. Внести новое значение в поле Заказ (для потока А) или Оплата (для потока В). 3. Вернуть модифицированную запись в файл базы данных. Рис. 4.16. Возникновение гонок при доступе к разделяемым данным Обозначим соответствующие шаги для потока А как Al, A2 и A3, а для потока В как 81, В2 и ВЗ. Предположим, что в некоторый момент поток А обновляет поле Заказ записи о клиенте N. Для этого он считывает эту запись в свой буфер (шаг А1), модифицирует значение поля Заказ (шаг А2), но внести запись в базу данных (шаг A3) не успевает, так как его выполнение прерывается, например, вследствие завершения кванта времени. Предположим также, что потоку В также потребовалось внести сведения об оплате относительно того же клиента N. Когда подходит очередь потока В, он успевает считать запись в свой буфер (шаг В1) и выполнить обновление поля Оплата (шаг В2), а затем прерывается. Заметим, что в буфере у потока В находится запись о клиенте N, в которой поле Заказ имеет прежнее, не измененное значение. Когда в очередной раз управление будет передано потоку А, то он, продолжая свою работу, запишет запись о клиенте N с модифицированным полем Заказ в базу данных (шаг A3). После прерывания потока А и активизации потока В последний запишет в базу данных поверх только что обновленной записи о клиенте N свой вариант записи, в которой обновлено значение поля Оплата. Таким образом, в базе данных будут зафиксированы сведения о том, что клиент N произвел оплату, но информация о его заказе окажется потерянной (рис. 4.17, а). Сложность проблемы синхронизации кроется в нерегулярности возникающих ситуаций. Так, в предыдущем примере можно представить и другое развитие событий: могла быть потеряна информация не о заказе, а об оплате (рис. 4.17, 6) или, напротив, все исправления были успешно внесены (рис. 4.17, в). Все опреде- ляется взаимными скоростями потоков и моментами их прерывания. Поэтому отладка взаимодействующих потоков является сложной задачей. Ситуации, подобные той, когда два или более потоков обрабатывают разделяемые данные и конечный результат зависит от соотношения скоростей потоков, называются гонками. Рис. 4. Влияние относительных скоростей потоков на результат решения задачи Критическая секция Важным понятием синхронизации потоков является понятие «критической секции» программы. Критическая секция — это часть программы, результат выполнения которой может непредсказуемо меняться, если переменные, относящиеся к этой части программы, изменяются другими потоками в то время, когда выполнение этой части еще не завершено. Критическая секция всегда определяется по отношению к определенным критическим данным, при несогласованном изменении которых могут возникнуть нежелательные эффекты. В предыдущем примере такими критическими данными являлись записи файла базы данных. Во всех потоках, работающих с критическими данными, должна быть определена критическая секция. Заметим, что в разных потоках критическая секция состоит в общем случае из разных последовательностей команд. Контрольные вопросы 1.Как организована синхронизация процессов в ОС? 2. ОбЪясните необходимость синхронизации и гонки; 3. Что такое критическая секция. Лекция 11 Моделирование взаимоблокировок. Методы борьбы с взаимоблокировками План 1. Условия необходимые для взаимоблокировки; 2. Моделирование взаимоблокировок; 3. Методы борьбы с взаимоблокировками. Взаимоблокировка процессов может происходить, когда несколько процессов борются за один ресурс. Ресурсы бывают выгружаемые и невыгружаемые, аппаратные и программные. Выгружаемый ресурс - этот ресурс безболезненно можно забрать у процесса (например: память). Невыгружаемый ресурс - этот ресурс нельзя забрать у процесса без потери данных (например: принтер). Проблема взаимоблокировок процессов возникает при борьбе за невыгружаемый ресурсы. Условия необходимые для взаимоблокировки: 1. Условие взаимного исключения - в какой-то момент времени, ресурс занят только одним процессом или свободен. 2. Условие удержания и ожидания - процесс, удерживающий ресурс может запрашивать новые ресурсы. 3. Условие отсутствия принудительной выгрузки ресурса. 4. Условие циклического ожидания - должна существовать круговая последовательность из процессов, каждый, из которого ждет доступа к ресурсу, удерживаемому следующим членом последовательности. 5.2 Моделирование взаимоблокировок Моделирование тупиков с помощью графов. Условные обозначения На такой модели очень хорошо проверить возникает ли взаимоблокировка. Если есть цикл, значит, есть и взаимоблокировка. Рассмотрим простой пример: три процесса A, B, C три ресурса R, S, T Последовательное выполнение процессов, взаимоблокировка не возникает Рассмотрим циклический алгоритм: три процесса A, B, C три ресурса R, S, T Возникает взаимоблокировка Рассмотрим тот же самый случай, но допустим, что система, зная о предстоящей взаимоблокировке, заблокирует процесс B. Взаимоблокировка не возникает. 5.3 Методы борьбы с взаимоблокировками Четыре стратегии избегания взаимоблокировок: 1. Пренебрежением проблемой в целом (вдруг пронесет). 2. Обнаружение и устранение (взаимоблокировка происходит, но оперативно ликвидируется). 3. Динамическое избежание тупиков. 4. Предотвращение четырех условий, необходимых для взаимоблокировок. 5.3.1 Пренебрежением проблемой в целом (страусовый алгоритм) Если вероятность взаимоблокировки очень мала, то ею легче пренебречь, т.к. код исключения может очень усложнить ОС и привести к большим ошибкам. Также многие взаимоблокировки тяжело обнаружить. Этот алгоритм используется как в UNIX, так и в Windows. Поэтому (и не только) на серверах часто устанавливают автоматическую перезагрузку (раз в сутки, как правило ночью), если возникнет взаимоблокировка, то после перезагрузки ее не будет. 5.3.2 Обнаружение и устранение взаимоблокировок Система не пытается предотвратить взаимоблокировку, а пытается обнаружить ее и устранить. Обнаружение взаимоблокировки при наличии одного ресурса каждого типа Под одним ресурсом каждого типа, подразумевается один принтер, один сканер и один плоттер и т.д. Рассмотрим систему из 7-ми процессов и 6-ти ресурсов. Обнаружение взаимоблокировки при наличии одного ресурса каждого типа Визуально хорошо видна взаимоблокировка, но нам нужно чтобы ОС сама определяла взаимоблокировку. Для этого нужен алгоритм. Рассмотрим один из алгоритмов. Для каждого узла N в графе выполняется пять шагов. 1. Задаются начальные условия: L-пустой список, все ребра не маркированы. 2. Текущий узел добавляем вконец списка L и проверяем количество появления узла в списке. Если он встречается два раза, значит цикл и взаимоблокировка. 3. Для заданного узла смотрим, выходит ли из него хотя бы одно немаркированное ребро. Если да, то переходим к шагу 4, если нет, то переходим к шагу 5. 4. Выбираем новое немаркированное исходящее ребро и маркируем его. И переходим по нему к новому узлу и возвращаемся к шагу 3. 5. Зашли в тупик. Удаляем последний узел из списка и возвращаемся к предыдущему узлу. Возвращаемся к шагу 3. Если это первоначальный узел, значит, циклов нет, и алгоритм завершается. Алгоритм обнаружения взаимоблокировок Для нашего случая тупик обнаруживается в списке L=[B,T,E,V,G,U,D,T] Контрольные вопросы 1. Какие условия необходимые для взаимоблокировки? 2. Как осуществляется моделирование взаимоблокировок; 3. Поясните методы борьбы с взаимоблокировками. Лекция 12 Организация памяти План 1. Функции управления памятью в ОС 2. Типы адресов 3. Методы распределения памяти в ОС 4. Принцип кэширования данных в ОС Функции управления памятью в ОС Операционная система решает следующие задачи: Отслеживание свободной и занятой памяти. Выделение и освобождение памяти по запросам процессов. Обеспечение настройки адресов. Поддержка механизма виртуальной памяти Типы адресов Для идентификации переменных и команд используются символьные имена (метки), виртуальные адреса и физические адреса. Символьные имена Символьные имена присваивает пользователь при написании программы. Виртуальные адреса Виртуальные адреса вырабатывает компилятор. Так как не известно, в какое место оперативной памяти будет загружена программа, то компилятор присваивает переменным и командам виртуальные (условные) адреса, обычно считая по умолчанию, что программа будет размещена, начиная с нулевого адреса. Совокупность виртуальных адресов процесса называется виртуальным адресным пространством. Каждый процесс имеет собственное виртуальное адресное пространство. Физические адреса Физические адреса соответствуют номерам ячеек оперативной памяти, где в действительности расположены или будут расположены переменные и команды. Переход от виртуальных адресов к физическим может осуществляться двумя способами. В первом случае замену виртуальных адресов на физические делает специальная системная программа - перемещающий загрузчик. Перемещающий загрузчик на основании имеющихся у него исходных данных о начальном адресе физической памяти, в которую предстоит загружать программу, и информации, предоставленной компилятором об адресно-зависимых константах программы, выполняет загрузку программы, совмещая ее с заменой виртуальных адресов физическими. Второй способ заключается в том, что программа загружается в память в неизмененном виде в виртуальных адресах, при этом операционная система фиксирует смещение действительного расположения программного кода относительно виртуального адресного пространства. Во время выполнения программы при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Второй способ является более гибким, он допускает перемещение программы во время ее выполнения, в то время как перемещающий загрузчик жестко привязывает программу к первоначально выделенному ей участку памяти. Вместе с тем использование перемещающего загрузчика уменьшает накладные расходы, так как преобразование каждого виртуального адреса происходит только один раз во время загрузки, а во втором случае - каждый раз при обращении по данному адресу. Иногда (обычно в специализированных системах) заранее точно известно, в какой области оперативной памяти будет выполняться программа, и компилятор выдает исполняемый код сразу в физических адресах. Методы распределения памяти в ОС Выделяют следующие методы распределения памяти: Методы распределения памяти без использования дискового пространства Распределение памяти фиксированными разделами Подсистема управления памятью в этом случае выполняет следующие задачи: сравнивая размер программы, поступившей на выполнение, и свободных разделов, выбирает подходящий раздел, осуществляет загрузку программы и настройку адресов. Достоинства: с общей очередью - простота c отдельными очередями - большая производительность. Недостатки: Неэффективное распределение памяти (большие незаполненные фрагменты). Размер приложения может быть больше размера раздела. Перед запуском можно переразбить разделы. Распределение памяти разделами переменной величины С неперемещаемыми разделами ОС создает под каждую задачу раздел требуемого размера, когда задача завершается, то раздел освобождается. Достоинства: Снимается необходимость организации очередей. Больше шансов получить память нужного размера. Экономичнее. Недостатки: Фрагментация (свободный блок памяти оказывается разрезан) - не всякое приложение может быть запущено. С перемещаемыми разделами Фрагментация сжатия (перемещения): при каждом освобождении памяти разделы смещаются в сторону старших (младших) адресов. Достоинство: нет фрагментации. Недостаток: снижение производительности. Способы упорядочивания адресов Выделяют следующие способы упорядочивания адресов: 1. Произведение настройки адресов, когда приложение запущено (перемещающийся загрузчик). 2. Динамическое преобразование виртуальных адресов в физические. Способы борьбы с фрагментацией В определенные моменты времени происходит сжатие в сторону младших адресов. ОС последовательно просматривает занятые приложениями блоки, находит разрыв и смещает адрес. Данная схема эффективна в случае динамического преобразования; если используется перемещающийся загрузчик, то происходит полный пересчет адресов, который является очень ресурсоемким. Методы распределения памяти с использования дискового пространств Метод оверлеев Был использован и реализован в ОС MS DOS. Программист разбивает приложение на несколько частей (оверлеев), умещающихся в доступную память (640 кб). Сначала происходит загрузка 0-го оверлея, затем он выгружается и загружается 1-ый, и так далее. Программа содержится на диске, активный оверлей - в оперативной памяти, а все механизмы обеспечиваются программистом. Механизм требует тщательного проектирования программ. Страничное распределение виртуальной памяти Адресное пространство процесса делится на страницы фиксированных разделов. Физическая память в системе тоже делится на страницы, аналогичные виртуальной памяти. Для каждого процесса ОС создает служебную структуру - таблицу страниц (дает однозначное отображение виртуальных страниц в физические). При активизации очередного процесса в специальный регистр процессора загружается адрес таблицы страниц данного процесса. При каждом обращении к памяти происходит чтение из таблицы страниц информации о виртуальной странице, к которой произошло обращение. Если данная виртуальная страница находится в оперативной памяти, то выполняется преобразование виртуального адреса в физический. Если же нужная виртуальная страница в данный момент выгружена на диск, то происходит так называемое страничное прерывание. Выполняющийся процесс переводится в состояние ожидания, и активизируется другой процесс из очереди готовых. Параллельно программа обработки страничного прерывания находит на диске требуемую виртуальную страницу и пытается загрузить ее в оперативную память. Если в памяти имеется свободная физическая страница, то загрузка выполняется немедленно, если же свободных страниц нет, то решается вопрос, какую страницу следует выгрузить из оперативной памяти. Страницы выбираются согласно информации, заносимой в колонну Флаги. Виды флагов: время обработки было ли обращение или нет признак невыгружаемых страниц частота использования Рассмотрим механизм преобразования виртуального адреса в физический при страничной организации памяти. Виртуальный адрес при страничном распределении может быть представлен в виде пары (p, s), где p - номер виртуальной страницы процесса (нумерация страниц начинается с 0), а s - смещение в пределах виртуальной страницы. Учитывая, что размер страницы равен 2 в степени к, смещение s может быть получено простым отделением k младших разрядов в двоичной записи виртуального адреса. Оставшиеся старшие разряды представляют собой двоичную запись номера страницы p. При каждом обращении к оперативной памяти аппаратными средствами выполняются следующие действия: на основании начального адреса таблицы страниц, номера виртуальной страницы и длины записи в таблице страниц определяется адрес нужной записи в таблице, из этой записи извлекается номер физической страницы к номеру физической страницы присоединяется смещение. Таблицу страниц стремятся размещать в "быстрых" запоминающих устройствах. Это может быть, например, набор специальных регистров или память, использующая для уменьшения времени доступа ассоциативный поиск и кэширование данных. Страничное распределение памяти может быть реализовано в упрощенном варианте, без выгрузки страниц на диск. В этом случае все виртуальные страницы всех процессов постоянно находятся в оперативной памяти. Такой вариант страничной организации хотя и не предоставляет пользователю виртуальной памяти, но почти исключает фрагментацию. Достоинства: нет фрагментации память используется оптимально механизм не требует никаких действий со стороны программы быстрое преобразование виртуальных адресов в физические. Недостатки: при малых страницах высокие расходы при хранении таблицы страниц нет возможности указать тип содержащейся информации, поэтому нельзя установить права доступа. Сегментное распределение памяти Виртуальное адресное пространство процесса делится на сегменты, размер которых определяется программистом с учетом смыслового значения содержащейся в них информации. Отдельный сегмент может представлять собой подпрограмму, массив данных и т.п. Иногда сегментация программы выполняется по умолчанию компилятором. При загрузке процесса часть сегментов помещается в оперативную память (при этом для каждого из этих сегментов операционная система подыскивает подходящий участок свободной памяти), а часть сегментов размещается в дисковой памяти. Сегменты одной программы могут занимать в оперативной памяти несмежные участки. Во время загрузки система создает таблицу сегментов процесса (аналогичную таблице страниц), в которой для каждого сегмента указывается начальный физический адрес сегмента в оперативной памяти, размер сегмента, правила доступа, признак модификации, признак обращения к данному сегменту за последний интервал времени и некоторая другая информация. Если виртуальные адресные пространства нескольких процессов включают один и тот же сегмент, то в таблицах сегментов этих процессов делаются ссылки на один и тот же участок оперативной памяти, в который данный сегмент загружается в единственном экземпляре. Система с сегментной организацией функционирует аналогично системе со страничной организацией: время от времени происходят прерывания, связанные с отсутствием нужных сегментов в памяти, при необходимости освобождения памяти некоторые сегменты выгружаются, при каждом обращении к оперативной памяти выполняется преобразование виртуального адреса в физический. Кроме того, при обращении к памяти проверяется, разрешен ли доступ требуемого типа к данному сегменту. Виртуальный адрес при сегментной организации памяти может быть представлен парой (g, s), где g - номер сегмента, а s - смещение в сегменте. Физический адрес получается путем сложения начального физического адреса сегмента, найденного в таблице сегментов по номеру g, и смещения s. |