Проблема
Аналогия основана на гипотетической парикмахерской с одним парикмахером. У парикмахера есть одно рабочее место и приемная со многими стульями. Когда парикмахер заканчивает подстригать клиента, он отпускает клиента и затем идет в приёмную, чтобы посмотреть, есть ли ждущие клиенты. Если есть, он приглашает одного из них и стрижет его. Если ждущих клиентов нет, он возвращается к своему креслу и спит в нем.
Каждый приходящий клиент смотрит на то, что делает парикмахер. Если парикмахер спит, то клиент будит его и садится в кресло. Если парикмахер работает, то клиент идет в приёмную. Если есть свободный стул в приёмной, клиент садится и ждёт своей очереди. Если свободного стула нет, то клиент уходит. Основываясь на наивном анализе, вышеупомянутое описание должно гарантировать, что парикмахерская функционирует правильно с парикмахером, стригущим любого пришедшего, пока есть клиенты, и затем спящим до появления следующего клиента. На практике есть много проблем, которые могут произойти, которые иллюстрируют общие проблемы планирования.
Все проблемы связаны с фактом, что все действия и парикмахера, и клиента (проверка приёмной, вход в парикмахерскую, занятие места в приёмной, и т. д.) занимают неизвестное количество времени. Например, клиент может войти и заметить, что парикмахер работает, тогда он идет в приёмную. Пока он идет, парикмахер заканчивает стрижку, которую он делает и идет, чтобы проверить приемную. Так как там никого нет (клиент еще не дошел) он возвращается к своему месту и спит. Парикмахер теперь ждет клиента, и клиент ждет парикмахера. В другом примере два клиента могут прибыть в то же самое время, когда в приемной есть единственное свободное место. Они замечают, что парикмахер работает, идут в приёмную, и оба пытаются занять единственный стул.
Доступно множество возможных решений. Основной элемент каждого — mutex
, который гарантирует, что изменить состояние (state
) может только один из участников. Парикмахер должен захватить это mutex
исключение, прежде чем проверить клиентов, и освободить его, когда он начинает или спать, или работать. Клиент должен захватить mutex
, прежде чем войти в магазин, и освободить его, как только он займет место или в приемной, или у парикмахера. Это устраняет обе проблемы, упомянутые в предыдущей секции. Семафоры
также обязаны указывать на состояние системы. Например, можно было бы сохранить число людей в приемной.
У варианта с несколькими парикмахерами есть дополнительная сложность координирования нескольких парикмахеров среди ждущих клиентов.
Классическая задача. Читатели и писатели
Дана некоторая разделяемая область память, к этой структуре данных может обращаться произвольное количество «читателей» и произвольное количество «писателей».
Несколько читателей могут получить доступ одновременно, писатели в этот момент не допускаются. Только один писатель может получить доступ, другие писатели и читатели должны ждать.
Первое решение
Читатель может войти в критическую секцию, если нет писателей.
Это решение несправедливо, так как отдает предпочтение читателям
Плотный поток запросов от читателей может привести к тому, что писатель никогда не получит доступа к критической секции – ситуация «голодания» (starvation).
Второе решение
Отдадим предпочтение писателям, то есть читатель не входит в критическую секцию, если есть хотя бы один ожидающий писатель.
Данное решение отдает приоритет писателям, и тоже несправедливо, так как возможно «голодание»
(starvation) читателей.
Третье решение
Не отдавать никому приоритета, просто использовать мьютекс
.
Билеты для подготовки к экзамену по Информатике. Трофимов Владислав, Махонин Кирилл
Файловые системы
FAT — File Allocation Table
FAT12 для дискет
FAT16 диски до 2гб
UFAT можно использовать нелатинские символы в названиях
FAT32 имя хранится в заголовке файла
MBR
– главная загрузочная запись (размер кластера, место загрузки ОС)
FAT
– таблица разметки.
имя файла
свойства файлов
начальная позиция на диске
В
последнем байте при фрагментации файла – адрес след. фрагмента файла.
Каждый следующий фрагмент в начале имеет ссылку на предыдущий фрагмент.
HPFS – High Performance File System
Super block
– аналог главной загрузочной записи
Spear block
– информация в процентном отношении о занятости каждой битовой карты (картотека битовых карт)
Bitmap
– битовая карта, аналог FAT, показывает, какие данные записаны (размер 8мб)
Билеты для подготовки к экзамену по Информатике. Трофимов Владислав, Махонин Кирилл
NTFS – New technologies file system
Log MFT
– загрузочная запись, аналог mbr
MFT
– ссылка на адрес журнала событий (записи о каждом файле на диске(имя, владелец, создатель, атрибуты, дата последнего изменения, наличие мягких и твердых ссылок) размером 1 Кб, или любые другие файлы размером до 1кб). Занимает 12%. Если не хватает, то система будет сдвигать границу.
Инверсия приоритетов возникает, когда два потока, высоко приоритетный (В
) и низкоприоритетный (Н
) разделяют некий общий ресурс (Р
). Предположим, также что в системе присутствует третий поток, приоритет которого находится между приоритетами В
и Н
. Назовем его средним (С
). Если поток В переходит в состояние готовности когда активен поток Н
и Н
заблокировал ресурс Р
, то поток В
вытеснит поток Н
и Р
останется заблокирован. Когда В
понадобится ресурс Р
, то он сам перейдет в заблокированное состояние. Если в состоянии готовности находится только поток Н
, то ничего страшного не произойдет, Н
освободит заблокированный ресурс и будет вытеснен потоком В
. Но если на момент блокирования потока В
, в состоянии готовности находится поток С
, приоритет которого выше чем у Н
, то активным станет именно он, а Н
опять будет вытеснен, и получит управление только после того, как С
закончит свою работу. Подобная задержка вполне может привести к тому, что критическое время обслуживания потока В
будет пропущено. Если В
это поток жесткого реального времени, то подобная ситуация недопустима.
Какие же механизмы защиты от этой проблемы используют разработчики ОСРВ? Наиболее широко распространенный и проверенный механизм – это наследование приоритетов.
Механизм наследования приоритетов, к сожалению, не всегда может решить проблемы, связанные с блокирование высокоприоритетного потока на заблокированном ресурсе. В случае, когда несколько средне– и низко–приоритетных потоков разделяют некоторые ресурсы с высокоприоритетным потоком возможна ситуация, когда высокоприоритетному потоку придется слишком долго ждать пока каждый из младших потоков не освободит свой ресурс и критический срок обслуживания будет потерян. Однако такие ситуации (разделения ресурсов высокоприоритетного потока) должны отслеживаться разработчиками прикладной системы. В принципе наследование приоритетов является наиболее распространенным механизмом защиты от проблемы инверсии приоритетов.
Другой, несколько менее распространенный метод, называется Протокол Предельного Приоритета (Priority Ceiling Protocol) . Метод этот заключается в добавлении к стандартным свойствам объектов синхронизации параметра, определяемого максимальным приоритетом потока, которые к этому объекту обращаются. Если этот параметр установлен, то приоритет любого потока, обращающегося к этому объекту синхронизации, будет увеличен до указанного уровня, и, таким образом, не сможет быть вытеснен никаким потоком, который может нуждаться в заблокированном им ресурсе. После разблокирования ресурса, приоритет потока понижается до начального уровня. Таким образом, получается нечто вроде предварительного наследования приоритетов. Однако этот метод имеет ряд серьезных недостатков. В первую очередь, на разработчика ложиться работа по «обучению» объектов синхронизации их уровню приоритетов. Во вторых, возможны задержки в запуске высокоприоритетных потоков на время отработки низкоприоритетных потоков. В целом максимально эффективно этот механизм может быть использован в случае, когда имеется один поток жесткого реального времени и несколько менее приоритетных потоков, разделяющих с ним ресурсы.
11.Межпроцессное взаимодействие
(англ. Inter-Process Communication, IPC) — набор способов обмена данными между множеством потоков в одном или более процессах. Процессы могут быть запущены на одном или более компьютерах, связанных между собой сетью. IPC-способы делятся на методы обмена сообщениями, синхронизации, разделяемой памяти и удаленных вызовов (RPC). Методы IPC зависят от пропускной способности и задержки взаимодействия между потоками и типа передаваемых данных.
IPC наряду с концепцией адресного пространства является основой для разграничения адресного пространства.
Метод
Реализуется (операционной системой или другим окружением)
Файл
Все операционные системы.
Сигнал
Большинство операционных систем; некоторые системы, как например, Windows, только реализуют сигналы в библиотеке запуска Си, но не обеспечивают их полноценной поддержки для использования методов IPC.
Сокет
Канал
Именованный канал
Все системы, соответствующие POSIX.
Семафор
Все системы, соответствующие POSIX.
Разделяемая память
Все системы, соответствующие POSIX.
Обмен сообщениями
(без разделения)
Используется в парадигме MPI, Java RMI, CORBA и других.
Проецируемый в память файл
Все системы, соответствующие POSIX; несет риск появления состояния гонки в случае использования временного файла. Windows также поддерживает эту технологию, но использует API отличный от POSIX.
Очередь сообщений
Большинство операционных систем.
Почтовый ящик
Некоторые операционные системы.
12. Классические проблемы межпроцессного взаимодействия
Проблема обедающих философов
В 1965 году Дейкстра сформулировал и решил проблему синхронизации, названную им проблемой обедающих философов. Проблему можно сформулировать следующим образом: пять философов сидят за круглым столом, и у каждого есть тарелка со спагетти. Спагетти настолько скользкие, что каждому философу нужно две вилки, чтобы с ними управиться. Между каждыми двумя тарелками лежит одна вилка.
Жизнь философа состоит из чередующихся периодов поглощения пищи и размышлений. Когда философ голоден, он пытается получить две вилки, левую и правую, в любом порядке. Если ему удалось получить две вилки, он некоторое время ест, затем кладет вилки обратно и продолжает размышления. Вопрос состоит в следующем: можно ли написать алгоритм, который моделирует эти действия для каждого философа и никогда не застревает.
Ситуация, в которой все программы продолжают работать сколь угодно долго, но не могут добиться хоть какого-то прогресса, называется зависанием процесса.
С точки зрения практики возникают проблемы с эффективностью: в каждый момент времени может есть спагетти только один философ. Но вилок пять, поэтому необходимо разрешить есть в каждый момент времени двум философам. Философ может начать есть, только если ни один из его соседей не ест.
Проблема читателей и писателей
Другой известной задачей является проблема читателей и писателей, моделирующая доступ к базе данных. Представьте себе базу данных бронирования билетов на самолет, к которой пытается получить доступ множество процессов. Можно разрешить одновременное считывание данных из базы, но если процесс записывает информацию в базу, доступ остальных процессов должен быть прекращен, даже доступ на чтение. Как запрограммировать читателей и писателей?
Пока в базе есть хотя бы один активный читающий процесс, доступ остальным читателям разрешается, а они все приходят и приходят. Чтобы избежать такой ситуации, нужно немного изменить программу: если пишущий процесс ждет доступа к базе, новый читающий процесс доступа не получает, а становится в очередь за пишущим процессом.
Проблема спящего брадобрея
В парикмахерской есть один брадобрей, его кресло и п стульев для посетителей. Если желающих воспользоваться его услугами нет, брадобрей сидит в своем кресле и спит. Если в парикмахерскую приходит клиент, он должен разбудить брадобрея. Если клиент приходит и видит, что брадобрей занят, он либо садится на стул (если есть место), либо уходит (если места нет). Необходимо запрограммировать брадобрея и посетителей так, чтобы избежать состояния состязания.
В предлагаемом решении используются три семафора: customers, для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается — он уже не ждет); barbers, количество брадобреев (0 или 1), простаивающих в ожидании клиента, и mutex для реализации взаимного исключения. Также используется переменная waiting, предназначенная для подсчета ожидающих посетителей.
13. Взаимоблокировка
-это ситуация когда группа процессов находиться в тупиковой ситуации, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из той же группы.
Выгружаемые ресурсы-безболезненно забрать у владеющего им процесса.
Невыгружаемый ресурс-не может быть безболезненно отобран у процесса.
Алгоритм использования ресурсов в общем виде:
2. Использование ресурсов
3. Возврат ресурсов
Условие взаимоблокировок
:
1. Условие взаимного исключения. Каждый ресурс в данный момент времени или отдан ровно одному процессу или доступен.
2. Условие удержания и ожидания. Процессы в данный момент удерживающие полученные раннее ресурсы могут запрашивать новые ресурсы.
3. Условие отсутствия принудительной выгрузки ресурсов. У процесса нельзя принудительным образом забрать полученные ранее ресурсы. Процесс владеющий должен сам освободить ресурсы.
4. Условие циклического ожидания. Должна существовать круговая последовательность из двух или более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Обнаружение и устранение взаимоблокировок:
1. Восстановление при помощи принудительном выпуске ресурса заключается в преднамеренном отборе ресурсов у процесса и используется в основном на системах пакетной обработки данных. Имеет недостаток:не все ресурсы могут быть отобраны у процесса.
2. Восстановление через откат. Заключаться в создании контрольных точек разработчиками в приложениях. После возникновения взаимоблокировки процесс возвращается к ближайшей контрольной точке и вновь начинает свою работу с того момента.
3. Во становление путем уничтожения процессов.Заключается в уничтожении одного из процессов попавших в заимоблокировку. Если уничтожение не помогает, уничтожается следующий из процессов пока не будет разрешена тупиковая ситуация.
Избежание взаимоблокировок:
Состояние безопасно, если оно не находиться в тупике и существует некоторый порядок в планировщике в котором каждый процесс защищен (даже если все процессы захотят получить максимальное кол-во ресурсов).
Предотвращение взаимоблокировок:
1. Атака условия взаимного исключения
Если в системе нет ресурса,представленных в единоличное пользование одному процессу, то никогда не произойдет тупиковой ситуации. Следует избегать выделения ресурсов, когда это не является действительно необходимым и важно пытаться обеспечить ситуацию в которой претендовать на ресурс может минимально количество процессов.
2. Атака условия удержания и ожидания
Программирование процесса таким образом, чтобы они требовали все ресурсы сразу перед началом работы программы.
Недостатки данного способа решения:
· Не все процессы знаю сколько и каких ресурсов им понадобиться до начала работы.
· Ресурсы не будут использоваться оптимально
3. Атака условия отсутствия принудительной выгрузки ресурсов
Не существует нормального способа избежания взаимоблокировки, т.к. принудительное изъятие ресурса у процесса при его работе практически не возможна.
4. Атака условия циклического ожидания
· Управление ресурсами как правило гласят что процессу дано право только на один ресурс в конкретный момент времени. Данное правило может быть задействовано не для всех процессов.
· Общая нумерация всех ресурсов и введения правила в соответствии с которым процесс должен запрашивать несколько устройств согласно последовательности их нумерации. Работает только на сравнительно небольших количествах ресурсов.
5. Алгоритм банкира
Безопасное состояние-это такое состояние для которого иметься хотя бы одна последовательности событий которая не приведет к взаиоблокировке.
Суть алгоритма:
· Предположим, что у системы есть «х» устройств.
· Операционная система принимает запрос от пользовательского процесса, если его макс потребность не превышает «х».
· Пользователь гарантируется, что если операционная система в состоянии удовлетворить его запрос то все устройства будут возвращены в систему в течении конечного промежутка времени.
· Текущее состояние системы называется надежным, если ОС может обеспечить всем процессам их выполнения в течении конечного времени.
· В соответствии с алгоритмом банкира выделения устройств возможно только если состояние системы остается надежным.
Выводы: Имеются различные способы выхода из взаимоблокировок.
· Снятие оператором выполняющимся процессом до тех пор пока не исчезнет взаимоблокировка.
· Рестарт системы с контрольной точки
Контрольная точка — полное состояние ПК сохраненное на внешнем носителе.
14. Выгружаемые ресурсы
См.13й (в интернетах нет нихчего, инфа 146%).
15. Невыгружаемые ресурсы
См.13й.
16. FAT
(англ. File Allocation Table — «таблица размещения файлов») — классическая архитектура файловой системы, которая из-за своей простоты всё ещё широко используется для флеш-дисков и карт памяти. В недавнем прошлом использовалась в дискетах, на жёстких дисках и других носителях информации.
Разработана Биллом Гейтсом и Марком МакДональдом (англ.) в 1976-1977 годах. Использовалась в качестве основной файловой системы в операционных системах семейств DOS и Windows (до версии Windows 2000).
Структура FAT следует стандарту ECMA-107 и подробно определяется официальной спецификацией от Microsoft, известной под названием FATGEN.
FAT16
FAT32
Реализована и используется большинством операционных систем (MS-DOS, Windows 95/98/ Me , Windows 2000 и Windows XP , OS/2, UNIX).
На данный момент поддерживается только в Windows 95/98/ Me , Windows 2000 и Windows XP (бородатая статья, даже Висты нет, будьте оптимистами – врите, что все всё реализовали)
Очень эффективна для логических дисков размером менее 256 Мбайт.
Не работает с дисками объемом менее 512 Мбайт.
Поддерживает сжатие дисков, например по алгоритму DriveSpace.
Не поддерживает сжатие дисков.
Обрабатывает максимум 65 525 кластеров, размер которых зависит от объема логического диска. Так как максимальный размер кластеров равен 32 Кбайт, FAT16 может работать с логическими дисками объемом не более 2 Гбайт.
Способна работать с логическими дисками объемом до 2 047 Гбайт при максимальном размере кластеров в 32 Кбайт.
Чем больше размер логического диска, тем меньше эффективность хранения файлов в FAT»16-системе, так как увеличивается и размер кластеров. Пространство для файлов выделяется кластерами, и поэтому при максимальном объеме логического диска файл размером 10 Кбайт потребует 32 Кбайт, а 22 Кбайт дискового пространства пропадет впустую.
На логических дисках объемом менее 8 Гбайт размер кластеров составляет 4 Кбайт.
Максимально возможная длина файла в FAT32 равна 4 Гбайт за вычетом 2 байтов. Win32-приложения могут открывать файлы такой длины без специальной обработки. Остальные приложения должны использовать прерывание Int 21h, функцию 716С (FAT32) с флагом открытия, равным EXTEND-SIZE (1000h).
В файловой системе FAT32 на каждый кластер в таблице размещения файлов отводится по 4 байта, тогда как в FAT16 — по 2, а в FАТ12 — по 1,5.
Старшие 4 бита 32-разрядного элемента таблицы FAT32 зарезервированы и не участвуют в формировании номера кластера. Программы, напрямую считывающие РАТ32-таблицу, должны маскировать эти биты и предохранять их от изменения при записи новых значений.
Файловые системы (NTFS)
Файловая система
– это способ организации данных на носителях информации. Файловая система определяет, где и каким образом на носителе будут записаны файлы, и предоставляет операционной системе доступ к этим файлам.
К современным файловым системам предъявляют дополнительные требования: возможность шифрования файлов, разграничение доступа для файлов, дополнительные атрибуты. Обычно файловая система записана в начале жесткого диска.
NTFS
(аббревиатура New Technology File System
— Файловая Система Новой Технологии
) — стандартная файловая система для семейства операционных систем Microsoft Windows NT.
Представлена 27 июля 1993 вместе с Windows NT 3.1. NTFS разработана на основе файловой системы HPFS (аббревиатура High Performance File System
— Высокопроизводительная Файловая Система
), создававшейся Microsoft совместно с IBM для операционной системы OS/2.
Основные особенности NTFS:
встроенные возможности разграничивать доступ к данным для различных пользователей и групп пользователей, а также назначать квоты (ограничения на максимальный объём дискового пространства, занимаемый теми или иными пользователями), использование системы журналирования для повышения надёжности файловой системы.
Спецификации файловой системы являются закрытыми. Обычно размер кластера равен 4Кб. На практике не рекомендуют создавать тома более 2ТБ. Жесткие диски только достигли таких размеров, возможно в будущем нас ждет новая файловая система.
Во время установки ОС Windows ХР предлагается отформатировать диск в системе FAT
или NTFS
. При этом имеется в виду FAT32
.
Все файловые системы построены на принципе: один кластер – один файл. Т.е. один кластер хранит данные только одного файла.
Основное отличие для обычного пользователя между этими системами – размер кластера. «Давным-давно, когда диски были маленькими, а файлы – очень маленькими» это было очень заметно.
Рассмотрим на примере одного тома на диске объемом 120Гб и файла размером 10Кб.
Для FAT32
размер кластера будет 32Кб, а для NTFS –
4Кб.
В FAT32
такой файлзаймет 1 кластер, при этом останется 32-10=22Кб незанятого места.
В NTFS
такой файлзаймет 3 кластера, при этом останется 12-10=2Кб незанятого места.
Таким образом, переход от FAT32
к NTFS
позволяет более оптимально использовать жесткий диск при наличии большого количества мелких файлов в системе.
И межпроцессного взаимодействия (interprocess communication
) в многозадачной операционной системе . Проблема заключается в обеспечении того, чтобы парикмахер работал, когда есть клиенты и отдыхал, когда клиентов нет.
Энциклопедичный YouTube
1
/
1
✪ Неэффективное собрание. Фильм «Афо́ня»
Субтитры
Проблема
Аналогия основана на гипотетической парикмахерской с одним парикмахером. У парикмахера есть одно рабочее место и приемная с несколькими стульями. Когда парикмахер заканчивает подстригать клиента, он отпускает клиента и затем идет в приёмную, чтобы посмотреть, есть ли там ожидающие клиенты. Если они есть, он приглашает одного из них и стрижет его. Если ждущих клиентов нет, он возвращается к своему креслу и спит в нем.
Каждый приходящий клиент смотрит на то, что делает парикмахер. Если парикмахер спит, то клиент будит его и садится в кресло. Если парикмахер работает, то клиент идет в приёмную. Если в приёмной есть свободный стул, клиент садится и ждёт своей очереди. Если свободного стула нет, то клиент уходит. Основываясь на наивном анализе, вышеупомянутое описание по идее должно гарантировать, что парикмахерская функционирует правильно с парикмахером, стригущим любого пришедшего, пока есть клиенты, и затем спящим до появления следующего клиента. На практике же существует несколько конфликтных ситуаций, которые иллюстрируют общие проблемы планирования.
Все эти конфликтные ситуации связаны с тем фактом, что действия и парикмахера, и клиента (проверка приёмной, вход в парикмахерскую, занятие места в приёмной, и т. д.) занимают неизвестное количество времени и/или могут происходить одновременно. Например, клиент может войти и заметить, что парикмахер работает, тогда он идет в приёмную. Пока он идет, парикмахер заканчивает стрижку, которую он делает и идет, чтобы проверить приемную, причём делает это быстрее направляющегося туда клиента. Так как в приёмной пока ещё никого нет (клиент ещё не дошел), он возвращается к своему месту и спит. Парикмахер теперь ждет клиента, а клиент ждет парикмахера. В другом примере два клиента могут прибыть в то же самое время, когда в приемной есть единственное свободное место. Они замечают, что парикмахер работает, идут в приёмную, и оба пытаются занять единственный стул.
Проблема спящего парикмахера часто приписывается Эдсгеру Дейкстра (1965), одному из пионеров информатики.
Решение
Существует несколько возможных решений данной проблемы. Основной элемент каждого из решений — мьютекс — механизм, который гарантирует, что изменить состояние (state
) в данный момент времени может только один из участников. Парикмахер должен захватить мьютекс, прежде чем проверить клиентов, и освободить его, когда он начинает или спать, или работать. Клиент должен захватить тот же мьютекс, прежде чем войти в парикмахерскую, и освободить его, как только он займет место или в приемной, или у парикмахера. Это устраняет обе проблемы, упомянутые в предыдущей секции. Возможно также использование более общего механизма семафоров для указания текущего состояние системы. Например, при помощи семафора можно выразить число людей в приемной.
У варианта той же задачи с несколькими парикмахерами есть дополнительная сложность координирования нескольких парикмахеров среди ждущих клиентов.
1.cpp
bradobrej1.dsp
bradobrej1.dsw
bradobrej1.ncb
bradobrej1.opt
bradobrej1.plg
1.obj
bradobrej1.exe
bradobrej1.ilk
bradobrej1.pch
bradobrej1.pdb
vc60.idb
vc60.pdb
bradobrej1.exe
2.cpp
bradobrej2.dsp
bradobrej2.dsw
bradobrej2.ncb
bradobrej2.opt
bradobrej2.plg
2.obj
bradobrej2.exe
bradobrej2.ilk
bradobrej2.pch
bradobrej2.pdb
vc60.idb
vc60.pdb
bradobrej2.exe
162kb.
05.09.2008 12:01
- Смотрите также:
Лр1.doc
Операционные системы.
Лабораторная работа №1
Тема:
Подсистема управления процессами. Задача о спящем парикмахере.
Цель:
Ознакомится с основными методами которые применяются в подсистемах управления процессами.
Материал для предварительного изучения:
1. Понятие и организация процессов.
2. Реализация процессов в ОС Windows.
3. Средства языка С для работы с процессами.
Теоретический материал.
Процессам часто бывает необходимо взаимодействовать между собой. Например, в конвейере ядра выходные данные первого процесса должны передаваться второ-му и т. д. по цепочке. Поэтому возникает необходимость в правильно организованном взаимодей-ствии между процессами (IPC, interprocess communication), по возможности не использующим прерываний.
Проблема разбивается на три пункта. Первый мы уже упомянули: передача информации от одного процесса другому. Второй связан с контролем над дея-тельностью процессов: как гарантировать, что два процесса не пересекутся в кри-тических ситуациях (представьте себе два процесса, каждый из которых пытается завладеть последним мегабайтом памяти). Третий касается согласования действий процессов: если процесс А
должен поставлять данные, а процесс В
выводить их на печать, то процесс В
должен подождать и не начинать печатать, пока не поступят данные от процесса А
.
Важно понимать, что два из трех описанных пунктов в равной мере относятся и к потокам. Первый — передача информации — в случае потоков проблемой не является, поскольку у потоков общее адресное пространство (передача информа-ции между потоками с разным адресным пространством уже является проблемой передачи информации между процессами). Остальные два с тем же успехом касаться потоков: те же проблемы, и те же решения. Мы будем рассматривать эти ситуации в контексте процессов, но имейте в виду, что эти же рассуждения приме-ры и для потоков.
^
1. Состояние состязания.
В некоторых операционных системах процессы, работающие совместно, могут совместно использовать некое общее хранилище данных. Каждый из процессов может считывать из общего хранилища данных и записывать туда информацию. Это хранилище представляет собой участок в основной памяти (возможно, в структуре данных ядра) или файл общего доступа. Местоположение совместно используемой памяти не влияет на суть взаимодействия и возникающие проблемы. Рассмотрим межпроцессное взаимодействие на простом, но очень распространенном примере: спулер печати.
Если процессу требуется вывести на печать файл, он помещает имя файла в специальный каталог спулера. Другой процесс, демон печати, периоди-чески проверяет наличие файлов, которые нужно печатать, печатает файл и уда-ляет его имя из каталога.
Представьте, что каталог спулера состоит из большого числа сегментов, прону-мерованных 0, 1, 2, …, в каждом их которых может храниться имя файла. Также есть две совместно используемые переменные: out,
указывающая на следующий файл для печати, и in,
указывающая на следующий свободный сегмент. Эти две переменные можно хранить в одном файле (состоящем из двух слов), доступном всем процессам. Пусть в данный момент сегменты с 0 по 3 пусты (эти файлы уже напечатаны), а сегменты с 4 по 6 заняты (эти файлы ждут своей очереди на печать). Более или менее одновременно процессы А и В
решают поставить файл в очередь на печать. Описанная ситуация схематически изображена на рис. 2.14.
В соответствии с законом Мерфи (он звучит примерно так: «Если что-то плохое может случиться, оно непременно случится») возможна следующая ситуация. Процесс А
считывает значение (7) переменной in
и сохраняет его в локальной переменной next_free_slot.
После этого происходит прерывание по таймеру, и процессор переключается на процесс В.
Процесс В,
в свою очередь, считывает значение переменнойin
и сохраняет его (опять 7) в своей локальной переменной next_free_slot.
В данный момент оба процесса считают, что следующий свободный сегмент седьмой. Процесс В
сохраняет в каталоге спулера имя файла и заменяет значение in
на 8 затем продолжает заниматься своими задачами, не связанными с печатью. Наконец управление переходит к процессу А
, и он продолжает с того места на котором остановился. Он обращается к переменной next_freе_ slot,
считывает ее значение и записывает в седьмой сегмент имя файла (разумеется, удаляя при этом имя файла, записанное туда процессом В).
Затем он заменяет значение in
на 8 (next_free_slot
+1 = 8). Структура каталога спулера не нарушена, так что демон печати не заподозрит ничего плохого, но файл процесса В
не будет напе-чатан.
Ситуации, в ко-торых два (и более) процесса считывают или записывают данные одновременно и конечный результат зависит от того, какой из них был первым, называются состояниями состязания.
Критические области.
Как избежать состязания? Основным способом предотвращения проблем в этой и любой другой ситуации, связанной с совместным использованием памяти, файлов и чего-либо еще, является запрет одновременной записи и чтения разделенных данных более чем одним процессом. Говоря иными словами, необходимо взаим-ное исключение. Это означает, что в тот момент, когда один процесс использует разделенные данные, другому процессу это делать будет запрещено. Проблема, описанная выше, возникла из-за того, что процесс В
начал работу с одной из совместно используемых переменных до того, как процесс А
ее закончил. Выбор подходящей примитивной операции, реализующей взаимное исключение, является серьезным моментом разработки операционной системы.
Проблему исключения состояний состязания можно сформулировать на абст-рактном уровне. Некоторый промежуток времени процесс занят внутренними рас-четами и другими задачами, не приводящими к состояниям состязания. В другие моменты времени процесс обращается к совместно используемым данным или выполняет какое-то другое действие, которое может привести к состязанию. Часть программы, в которой есть обращение к совместно используемым данным, назы-вается критической областью или критической секцией. Если нам удастся избежать одновременного нахождения двух процессов в критических областях, Мы сможем избежать состязаний.
Несмотря на то, что это требование исключает состязание, его недостаточно для совместной работы параллельных процессов и эффективного использования данных. Для этого необходимо выполнение четырех условий:
1. Невозможна ситуация, в которой процесс вечно ждет попадания в крити-ческую область.
2. Два процесса не должны одновременно находиться в критических обла-стях.
3. В программе не должно быть предположений о скорости или количестве процессоров.
4. Процесс, находящийся вне критической области, не может блокировать дру-гие процессы.
В абстрактном виде требуемое поведение процессов представлено на рис. 2.15. Процесс А попадает в критическую область в момент времени Т
1
. Чуть позже, в мо-мент времени Т
2
,
процесс В
пытается попасть в критическую область, но ему это не удается, поскольку в критической области уже находится процесс А,
а два процесса не должны одновременно находиться в критических областях. Поэто-му процесс В
временно приостанавливается, до наступления момента времени Т
3
, когда процесс А
выходит из критической области. В момент времени Т
4
процесс В
также покидает критическую область, и мы возвращаемся в исходное состояние, когда ни одного процесса в критической области не было.
Семафоры.
В 1965 году Дейкстра (Е. W. Dijkstra) предложил использовать целую перемен-ную для подсчета сигналов запуска, сохраненных на будущее. Им был пред-ложен новый тип переменных, так называемые семафоры
,
значение которых мо-жет быть нулем (в случае отсутствия сохраненных сигналов активизации) или некоторым положительным числом, соответствующим количеству отложенных активизирующих сигналов.
Дейкстра предложил две операции, down
и up
(обобщения sleep
и wakeup
). Опе-рация down
сравнивает значение семафора с нулем. Если значение семафора боль-ше нуля, операция down
уменьшает его (то есть расходует один из сохраненных сиг-налов активации) и просто возвращает управление. Если значение семафора равно нулю, процедура down
не возвращает управление процессу, а процесс переводится в состояние ожидания. Все операции проверки значения семафора, его изменения и перевода процесса в состояние ожидания выполняются как единое и неделимое элементарноедействие. Тем самым гарантируется, что после начала операции ни один процесс не получит доступа к семафору до окончания или блокирования операции. Элементарность операции чрезвычайно важна для разрешения пробле-мы синхронизации и предотвращения состояния состязания.
Операция up
увеличивает значение семафора. Если с этим семафором связаны один или несколько ожидающих процессов, которые не могут завершить более раннюю операцию down, один из них выбирается системой (например, случайным образом) и ему разрешается завершить свою операцию down. Таким образом, послеоперации up
примененной к семафору, связанному с несколькими ожидающими процессами, значение семафора так иостанется равным 0, но число ожидающих процессов уменьшится на единицу. Операция увеличения значения семафора и активизации процесса тоже неделима. Ни один процесс не может быть блокирован во время выполнения операции up
, как ни один процесс не мог быть блокирован во время выполнения операции wakeup
в предыдущей модели.
В оригинале Дейкстра использовал вместо down
иup
обозначения Р и V соответственно. Мы не будем в дальнейшем использовать оригинальные обозначения поскольку тем, кто не знает датского языка, эти обозначения ничего не говорят (да и тем, кто знает язык, говорят немного). Впервые обозначения down
иup
появились в языке Algol 68.
Решение проблемы производителя и потребителя с помощью семафоров.
Как показано в листинге 2.4, проблему потерянных сигналов запуска можно ре-шить с помощью семафоров. Очень важно, чтобы они были реализованы неде-лимым образом. Стандартным способом является реализация операций down
и up
в виде системных запросов, с запретом операционной системой всех прерываний на период проверки семафора, изменения его значения и возможного перевода про-цесса в состояние ожидания. Поскольку для выполнения всех этих действий тре-буется всего лишь несколько команд процессора, запрет прерываний не приносит никакого вреда. Если используются несколько процессоров, каждый семафор необ-ходимо защитить переменной блокировки с использованием команды TSL, чтобы гарантировать одновременное обращение к семафору только одного процессора. Необходимо понимать, что использование команды TSL принципиально отличает-ся от активного ожидания, при котором производитель или потребитель ждут на-полнения или опустошения буфера. Операция с семафором займет несколько мик-росекунд, тогда как активное ожидание может затянуться на существенно больший промежуток времени.
Листинг 2.4.Проблема производителя и потребителя с семафорами
#define N 100 /* количество сегментов в буфере */
Typedef int semaphore; /* семафоры — особый вид целочисленных переменных */ semaphore mutex =1; /* контроль доступа в критическую область */
Semaphore empty = N; /*
число пустых сегментов буфера /
Semaphore full =
О; /* число полных сегментов буфера */
voidproducer(void)
While(TRUE)
{ /* TRUE — константа, равная 1*/
Item = protiuce_item (); /* создать данные, помещаемые в буфер */
Down(&empty); /* уменьшить счетчик пустых сегментов буфера */
Down(&mutex): /* вход в критическую область */
Insert_item(item); /* поместить в буфер новый элемент */
Up(&mutex): /* выход из критической области */
Up(&ful1); /* увеличить счетчик полных сегментов буфера */
Void consumer(void)
{ /* бесконечный цикл */
Down(&full); /* уменьшить числа полных сегментов буфера */
Down(&mutex); /* вход в критическую область */
Item = remove_item(); /* удалить элемент из буфера */
Up(&mutex); /* выход из критической области */
Up(&empty): /* увеличить счетчик пустых сегментов буфера */
Consume_item(item): /* обработка элемента */
В представленном решении используются три семафора: один для подсчета за-полненных сегментов буфера (full),
другой для подсчета пустых сегментов (empty),
а третий предназначен для исключения одновременного доступа к буферу произ-водителя и потребителя (mutex).
Значение счетчика full
исходно равно нулю, счет-чик empty
равен числу сегментов в буфере, a mutex
равен 1. Семафоры, исходное значение которых равно 1, используемые для исключения одновременного нахож-дения в критической области двух процессов, называются двоичными семафора-ми.
Взаимное исключение обеспечивается, если каждый процесс выполняет опе-рацию down
перед входом в критическую область и
up после выхода из нее.
Теперь, когда у нас есть примитивы межпроцессного взаимодействия, вернем-ся к последовательности прерываний, показанной в табл. 2.2. В системах, исполь-зующих семафоры, естественным способом скрыть прерывание будет связать с каждым устройством ввода-вывода семафор, исходно равный нулю. Сразу после запуска устройства ввода-вывода управляющий процесс выполняет операцию down
на соответствующем семафоре, тем самым входя в состояние блокировки. В случае прерывания обработчик прерывания выполняет up
на соответствующем семафоре, переводя процесс в состояние готовности. В такой модели пятый шаг в табл. 2.2 заключается в выполнении up
на семафоре устройства, чтобы следующим шагом планировщик смог запустить программу, управляющую устройством. Разумеет-ся, если в этот момент несколько процессов находятся в состоянии готовности, планировщик может выбрать другой, более значимый процесс.
В примере, представленном в листинге 2.4, семафоры использовались двумя различными способами. Это различие достаточно значимо, чтобы сказать о нем особо. Семафор mutex
используется для реализации взаимного исключения, тоесть для исключения одновременного обращения к буферу и связанным переменным двух процессов.
Остальные семафоры использовались для синхронизации.Семафоры full
и empty
необходимы, чтобы гарантировать, что определенные последовательности событий происходятили не происходят. В нашем случае они гарантируют, что производительпрекращает работу, когда буфер полон, а потребитель прекращает работу когда буфер пуст.
^
Постановка задачи:
Задача о парикмахере который спит является аллегорической демонстрацией подсистемы управления процессами и была сформулирована Дейкстрой в 1968 г. Формулируется задача следующим образом: Парикмахерская состоит из комнаты ожидания О и комнаты, в которой стоит кресло парикмахера З. Через двери Д можно попасть из комнаты О в комнату З, а из комнаты З на улицу. Если парикмахер заходит в комнату ожидания и никого там не находит, то он идет спать. Если клиент заходит в парикмахерскую и находит спящего парикмахера, то он его будит. В комнате ожидания число мест ограничено и равно N.
Согласно данной задаче необходимо определить элементы который будут запрограммированы отдельными процессами, разработать алгоритм и программно его реализовать.
В решении предлагается использовать три семафора:
customers,
для подсчета ожидающих посетителей (клиент, сидящий в кресле брадобрея, не учитывается – он уже не ждет);
barbers,
количество брадобреев (0 или 1), простаивающих в ожидании клиента;
mutex
для реализации взаимного исключения.
Также используся переменная waiting,
предназначенная для подсчета ожидающих посетителей. Она является копией переменной customers.
Присутствие в программе этой переменной связано с тем фактом, что прочитать текущее значение семафора невозможно. В этом решении посетитель, заглядывающий в парикмахерскую, должен сосчитать количество ожидающих посетителей. Если посетителей меньше, чем стульев, новый посетитель остается, в противном случае он уходит.
1. Тема и цель работы.
2. Задание на лабораторную работу.
3. Алгоритм программы.
4. Полученные результаты.
5. Выводы по работе с анализом реализованной модели взаимодействия процессов.
Размер: px
Начинать показ со страницы:
Транскрипт
1
Классические задачи синхронизации, ч. 2 Читатели и писатели Производители и потребители Спящий парикмахер
2
Читатели и писатели Дана некоторая разделяемая область память К этой структуре данных может обращаться произвольное количество «читателей» и произвольное количество «писателей» Несколько читателей могут получить доступ одновременно, писатели в этот момент не допускаются Только один писатель может получить доступ, другие писатели и читатели должны ждать
3
Решение 1 Первое решение: читатель может войти в критическую секцию, если нет писателей Это решение несправедливо, так как отдает предпочтение читателям Плотный поток запросов от читателей может привести к тому, что писатель никогда не получит доступа к критической секции: ситуация «голодания» (starvation)
4
Решение 2 Отдадим предпочтение писателям, то есть читатель не входит в критическую секцию, если есть хотя бы один ожидающий писатель pthread_mutex_t m; pthread_cond_t cw, cr; int rcnt, wcnt; int wwcnt; // число ожидающих писателей void rdlock() { pthread_mutex_lock(&m); while (wcnt > 0 wwcnt > 0) pthread_cont_wait(&cr, &m); rcnt++; pthread_mutex_unlock(&m); }
5
Решение 2 void wrlock() { pthread_mutex_lock(&m); while (wcnt > 0 rcnt > 0) { wwcnt++; pthread_cond_wait(&cw, &m); wwcnt—; } wcnt++; pthread_mutex_unlock(&m); } void unlock() { // }
6
Решение 2 Данное решение отдает приоритет писателям, и тоже несправедливо Возможно «голодание» (starvation) читателей Третье решение: не отдавать никому приоритета, просто использовать мьютекс
7
Производители-потребители (producer-consumer problem) Дан буфер фиксированного размера (N), в котором размещается очередь. Производители добавляют элементы в конец очереди, если буфер заполнился, производители засыпают Потребители забирают элементы из начала очереди, если буфер пуст, потребители засыпают
8
Производители-потребители int buf[n]; int head, tail; pthread_mutex_t m; pthread_cond_t cc; // consumer condvar pthread_cond_t pc; // producer condvar void put(int x) { pthread_mutex_lock(&m); while ((tail + 1) % N == head) pthread_cond_wait(&pc, &m); buf = x; tail = (tail + 1) % N; if ((head + 1) % N == tail) pthread_cond_signal(&cc); pthread_mutex_unlock(&m); }
9
Производители-потребители int get(void) { int val; pthread_mutex_lock(&m); while (head == tail) pthread_cond_wait(&cc, &m); val = buf; if ((tail + 1) % N == head) pthread_cond_signal(&pc); head = (head + 1) % N; pthread_mutex_unlock(&m); return val; }
10
Спящий парикмахер (sleeping barber) В парикмахерской имеется одно кресло для стрижки и N кресел для ожидающих посетителей Если нет посетителей, парикмахер спит Если приходит посетитель и кресло для стрижки свободно, посетитель садится в него и парикмахер начинает его стричь В противном случае посетитель садится в кресло для ожидающих Если все кресла заняты, посетитель уходит
11
Спящий парикмахер pthread_mutex_t m; pthread_t chair_thr; // кого стрижем int wait_cnt; // сколько посетителей ожидают pthread_cond_t bc; // barber condvar pthread_cond_t cc; // consumer condvar void barber(void) { while (1) { pthread_mutex_lock(&m); while (chair_thr == NULL && wait_cnt == 0) pthread_cond_wait(&bc, &m); pthread_mutex_unlock(&m); make_haircut(); pthread_mutex_lock(&m); chair_thr = NULL; pthread_cond_signal(&cc); pthread_mutex_unlock(&m); }}
12
Спящий парикмахер int consumer(void) { pthread_mutex_lock(&m); if (chair_thr!= NULL && wait_cnt == N) { // no space, leaving pthread_mutex_unlock(&m); return -1; } while (chair_thr!= NULL) { wait_cnt++; pthread_cond_wait(&cc, &m); wait_cnt—; } chair_thr = pthread_self(); pthread_cond_signal(&bc); pthread_mutex_unlock(&m); get_haircut(); return 0; }
13
Обнаружение тупиков Process 1: lock(&a); lock(&b); Process 2: lock(&b); lock(&a); Process 1 A Process 2 B Захваченный ресурс дуга от процесса к ресурсу Ожидаемый ресурс дуга от ресурса к процессу Если в графе есть цикл, система попала в состояние тупика
14
Группы процессов Группа процессов процессы, объединенные для выполнения задачи (например, для выполнения конвейера) Группа процессов выступает как единое целое при Получении сигналов, в особенности, от терминала (например, Ctrl-C SIGINT) При работе с терминалом (основная и фоновые группы процессов) Идентификатор группы процессов это идентификатор одного из процессов в группе
15
Создание группы #include pid_t getpgid(pid_t pid); int setpgid(pid_t pid, pid_t pgid); Группу процессов можно получить только у процесса из текущей сессии, при этом если pid == 0, возвращается группа процессов текущего процесса Для setpgid pid == 0 означает текущий процесс, pgid == 0 группа процессов с pgid текущего процесса
16
Создание группы, особые случаи setpgid(0, 0); Процесс создает новую группу процессов и помещает в нее себя (выполняется в сыне) setpgid(0, pgid); Процесс помещает себя в существующую группу процессов (в сыне) setpgid(pid, pid); Процесс создает новую группу процессов и помещает туда указанный процесс (в отце)
17
Группы процессов и терминал У терминала может быть одна основная группа процессов и произвольное количество фоновых групп процессов Основная группа процессов: Имеет право чтения с терминала (попытка чтения для фоновой группы процессов вызывает приостановку процесса фоновой группы) Получает сигналы SIGINT, SIGQUIT с терминала
18
Основная группа процессов терминала pid_t tcgetpgrp(int fd); int tcsetpgrp(int fd, pid_t pgrp); fd любой файловый дескриптор терминала (например, 0 стандартный ввод) tcsetpgrp устанавливает основную группу процессов терминала
19
Пример: ls -l wc -l int main(void) { pipe(fds); if (!(pid1 = fork())) { setpgid(0, 0); tcsetpgrp(0, getpid()); dup2(fds, 1); close(fds); close(fds); execlp(«/bin/ls», «/bin/ls», «-l», NULL); } setpgid(pid1, pid1); tcsetpgrp(0, pid1); if (!(pid2 = fork())) { setpgid(0, pid1); dup2(fds, 0); close(fds); close(fds); execlp(«/usr/bin/wc», «/usr/bin/wc», «-l», NULL); } setpgid(pid2, pid1); close(fds); close(fds); wait(0); wait(0); tcsetpgrp(0, getpgid(0)); return 0; }
20
Процессы-демоны
21
Планирование процессов Планировщик компонента ядра операционной системы Планировщик определяет, какой процесс из числа готовых к выполнению назначается на выполнение на ЦП Типы планировщиков: Пакетный Разделения времени Реального времени
22
Пакетное планирование Цель обеспечить максимальную пропускную способность ВС (то есть максимальное число выполненных задач) Ядро переключается с одного на другой процесс при следующих условиях: Выполнявшийся процесс завершил работу При выполнении возникла фатальная ошибка или процесс исчерпал отведенные ему ресурсы Выполнявший процесс инициировал операцию, которая не может быть выполнена немедленно Процесс запросил добровольное переключение
23
Планирование разделения времени Цель: разделить процессорное время между процессами, готовыми к выполнению Ядро переключается с одного процесса на другой при следующих условиях Процесс завершил работу При выполнении возникла ошибка Процесс инициировал операцию, которая не может быть выполнена немедленно Истек квант времени выполнения процесса Процесс запросил добровольное переключение
24
Классификация процессов По поведению «I/O-bound» — процесс выполняет активный обмен с внешними устройствами и проводит много времени в ожидании ввода-вывода (пример: веб-сервер, редактор текста) «CPU-bound» — процессы, интенсивно занимающие процессорное время (пример: компиляция программ, вычислительные задачи, рендеринг изображений и т. п.)
25
Классификация процессов По назначению: Интерактивные основное время проводят в ожидании пользовательского ввода, при поступлении ввода должны быстро активироваться, чтобы не было ощущения «торможения» Пакетные не ожидают ввода пользователя (компиляторы, численные приложения…)
26
Параметры планирования процессов разделения времени Значение nice: [-20, 19] чем меньше значение, тем выше приоритет. 0 приоритет по умолчанию Приоритет группы процессов: grpnice Приоритет пользователя: usrnice Полный приоритет: nice + grpnice + usrnice отсеченное по интервалу [-20; 19] Нормализованный приоритет normprio = 20 — fullnice, находится в интервале чем больше значение, тем больше приоритет
27
Планирование в Linux Планирование процессов разделено на эпохи В начале каждой эпохи каждому процессу назначается базовый квант base_quantum = normprio/4 + 1 counter число «неотработанных» квантов в эпохе, изначально counter = base_quantum За каждый квант, когда процесс выполняется, значение counter уменьшается на 1 Приоритет: priority = counter + normprio Выбирается процесс с наибольшим приоритетом
28
Планирование в Linux Эпоха заканчивается, когда у всех готовых к выполнению процессов counter == 0 В начале очередной эпохи: base_quantum = counter/2 + normprio/4 + 1 Таким образом приоритет отдается I/O-bound процессам
29
Планирование реального времени Цель: обеспечить минимальное время отклика, то есть время от наступления события до постановки на выполнение процесса, ожидающего этого события Виды планирования реального времени На основе фиксированного расписания На основе статических приоритетов
30
Планирование реального времени Ядро переключается с одного процесса на другой при следующих условиях Процесс завершил работу При выполнении возникла ошибка Процесс инициировал операцию, которая не может быть выполнена немедленно Готов к выполнению процесс с большим приоритетом Истек квант времени выполнения процесса Процесс запросил добровольное переключение
31
Статический приоритет Каждый процесс реального времени имеет статический приоритет Процессы разделения времени имеют статический приоритет 0, то есть назначаются на выполнение, только если нет готовых к выполнению процессов реального времени
32
Типы планирования р.в. SCHED_FIFO нет квантования времени, процесс выполняется, пока не появится более высокоприоритетный процесс, либо процесс не начнет ввод-вывод, либо не будет снят SCHED_RR (round-robin) выполнение квантуется, процессы одного приоритета выполняются по очереди
33
Инверсия приоритета (priority inversion) Предположим, что низкоприоритетный процесс P1 захватил некоторый ресурс R В это время стал готов к выполнению высокоприоритетный процесс P2, которому требуется ресурс R. Процесс P2 ожидает освобождения ресурса R процессом P1 В это время может быть назначен на выполнение среднеприоритетный процесс P3, который еще более отсрочит время освобождения ресурса R процессом P1
34
Инверсия приоритета Проблема возникает, потому что процессы, ожидающие освобождения ресурса неявно получают приоритет процесса, захватившего ресурс. Отсрочка выполнения высокоприоритетного процесса может иметь катастрофические последствия Однозначного решения проблемы не существует Возможный вариант: назначать процессу, захватившему ресурс, максимальный приоритет ожидающего процесса (наследование приоритета)
35
Управление приоритетами в Linux int nice(int inc); void sched_yield(void); int sched_setscheduler(pid_t pid, int policy, const struct sched_param *param);
Содержание 1 Управление заданиями (job control) 1 1.1 Основные концепции………………………….. 1 1.2 Дополнительность управления заданиями………………… 2 1.3 Управляющий терминал………………………….
Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Операционные системы: аспекты параллелизма Планирование ЦП Линёв А.В. Тема обсуждения Потокам
Алгоритмы планирования потоков Вытесняющие и невытесняющие алгоритмы планирования Невытесняющие алгоритмы основаны на том, что активному потоку позволяется выполняться, пока он сам, по собственной инициативе,
ГЛАВА 15 Управление заданиями Управление заданиями возможность, стандартизованная в POSIX.1 и предоставляемая многими другими стандартами позволяет одному терминалу выполнять несколько заданий. Задание
Важнейшей частью операционной системы, непосредственно влияющей на функционирование вычислительной машины, является подсистема управления процессами. Процесс (или по-другому, задача) — абстракция, описывающая
Название Лекция 5. Планирование задач Операционные системы 6 ноября 2012 г. Лекция 5 1 / 39 Планирование Начало Цели планирования Основные алгоритмы Определение Политика планирования: (Scheduling Strategy)
Модуль 3. УПРАВЛЕНИЕ ПРОЦЕССАМИ 1. Распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает
Планирование процессов Многозадачность ОС является многозадачной, если она способна чередовать выполнение нескольких процессов, создавая видимость, что в каждый момент времени работает более одного процесса
Лекция 8. Нити POSIX Эффективное использование IPC — разделяемой памяти и семафоров все таки ограничивается затратами на порождение новых процессов системным вызовом fork/2, даже при использовании технологии
Лекция 2. Подсистема управления процессами. Управление процессами в многозадачной системе заключается в выделении ресурсов ядра для каждого запущенного процесса, осуществлении переключения контекста процессов
UNIX Лекция 4 UNIX. Л.4 1 ПРОЦЕССЫ ОС UNIX Процесс — это задание в ходе его выполнения. П — образ программы, включающий отображение в памяти исполняемого файла, полученного в ходе компиляции, сегментов
Лабораторная работа 4 ЗНАКОМСТВО С ПРОЦЕССАМИ Цель работы Познакомиться с понятием процесса. Научиться получать список имеющихся в системе процессов и управлять их состоянием. 1. Теоретические сведения
Процессы и потоки Операционные системы Лекция 2 Ульяновск, УлГТУ, кафедра «Информационные системы» 1 / 12 Модель процесса Четыре программы, работающие в многозадачном режиме а); концептуальная модель четырех
Основы ОС Unix Сигналы Основы ОС Unix 28.2.08 Слайд 1 из 34 Сегодня Что такое сигнал? Терминология Старые проблемы с сигналами POSIX и Linux сигналы Работа с наборами сигналов Основы ОС Unix 28.2.08 Слайд
НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ ЯДЕРНЫЙ УНИВЕРСИТЕТ «МИФИ» Кафедра информатики и процессов управления (17) Курс «Современные операционные системы» Лекция 7 Планирование Москва 2016 Содержание 1. Основные
Сигналы Средство асинхронного взаимодействия процессов Посылаются: Одним процессом другому процессу Ядром ОС процессу для индикации событий, затрагивающих процесс Ядром ОС процессу в ответ на некорректные
4.1 Процессы 4.1.1 Понятие процесса Процесс (задача) — программа, находящаяся в режиме выполнения. С каждым процессом связывается его адресное пространство, из которого он может читать и в которое он может
Операционные системы. Разработка и реализация. Таненбаум Э., Вудхалл А. 3-е изд. — СПб.: Питер, 2007. 704 с. Третье издание классического труда Эндрю Таненбаума » Операционные системы. Разработка и реализация»
Операционные системы Лекция 2 Процессы и потоки (нити). 2.1 Процессы 2.1.1 Понятие процесса Процесс (задача) — программа, находящаяся в режиме выполнения. С каждым процессом связывается его адресное пространство,
Именованные каналы Канал, доступ к которому выполняется через точку привязки файловой системы Ядро создает по одному объекту именованного канала для каждой записи в файловой системе int mkfifo(const char
1 Работа с процессами в POSIX-системах Понятие «процесс» наряду с понятием «файл» относится к основным понятиям операционной системы. Под процессом можно понимать программу в стадии выполнения. С процессом
Занятие 6. Понятие процесса. Состояния процесса. Диспетчеризация. План занятия. 1. Процесс. Классификация процессов. 2. Ресурсы. Классификация ресурсов. 3. Управление процессами. 4. Планирование процессов.
Название Лекция 6. Алгоритмы блокировок Операционные системы 19 ноября 2012 г. Лекция 6 1 / 46 Цели планирования Требования ко взаимным исключениям Требования В любой момент времени в одном критическом
Процессы и потоки Понятия «процесс» и «поток» Процесс (задача) — программа, находящаяся в режиме выполнения. Потоќ выполне ния (thread нить) наименьшая часть программы, исполнение которой может быть назначено
ВСТРОЕННЫЕ ИНФОРМАЦИОННО-УПРАВЛЯЮЩИЕ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ Лекция 4: Статико-динамическое планирование вычислений в системах интегрированной модульной авионики Кафедра АСВК, Лаборатория Вычислительных
СУПЕРКОМПЬЮТЕРНЫЙ КОНСОРЦИУМ УНИВЕРСИТЕТОВ РОССИИ Проект Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного программного обеспечения
Лекция 10. Подходы к синхронизации. Содержание Задача читателей-писателей Замки Подходы к синхронизации Задача читаталей-писателя Задача читателей-писателей Имеется область памяти, к которой обращаются
Планирование процессов в ОС Windows NT Свойства 1) Процессы Windows NT реализованы в форме объектов, и доступ к ним осуществляется посредством службы объектов. 2) Процесс Windows NT имеет многонитевую
Название Мёртвая блокировка Сети Петри Требования к алгоритмам Лекция 6. Алгоритмы блокировок Операционные системы 11 ноября 2016 г. Лекция 6 1 / 65 Пример: сравнение данных POSIX Название Мёртвая блокировка
Реализация параллелизма с использованием «эффективных объектов» Решение задач организации параллелизма приложения происходит традиционно, применяя вытесняющую многозадачность. Такая схема целесообразна,
Операционные системы Лекция 3 Процессы 1 Понятие процесса Операционная система во время работы выполняет одну или несколько программ, планирует задания (совокупность программы, команд для ее выполнения
UNIX Лекция 6 UNIX. Л.6 1 СИГНАЛЫ Прерывания и особые ситуации Прерывания. Внешние устройства ввода-вывода, системные часы и т.п. асинхронно прерывают работу ЦП. По получении сигнала прерывания ядро операционной
Название Лекция 7. Алгоритмы блокировок Операционные системы 24 марта 2016 г. Лекция 7 1 / 48 Пример: сравнение данных POSIX Мёртвая блокировка Сети Петри Требования к алгоритмам Пример Пример (окончание)
RTOS Операционные системы реального времени Страница 1 План лекции Определение операционной системы Особенности встраиваемых ОС Процессы, задачи, нити Системное время Межпроцессное взаимодействие Обработка
UNIX Лекция 5 UNIX. Л.5 1 Зомби и сироты Добавим к известным четырем состояниям процесса еще одно пятое: выполнение процесса в режиме ядра; выполнение процесса в режиме задачи; приостановка; готовность
Параллельность 1 Введение 2 3 Потоки в языке Java Потоки в языке C# Введение Параллельность может возникать на четырех уровнях Уровень машинных инструкций Уровень инструкций высокоуровневого языка программирования
Рыбинская государственная авиационная технологическая академия имени П.А. Соловьева «УТВЕРЖДАЮ» Декан ФРЭИ А.И. Дворсон РАБОЧАЯ ПРОГРАММА По дисциплине «Операционные системы» для направления 230100 «Информатика
Лабораторная работа 4. Варианты Вариант 1: Необходимо решить проблему «Санта Клаус» с использованием библиотеки PTHREAD с учетом следующих ограничений: Санта все время спит, пока его не будет либо все
1 Средства межпроцессного взаимодействия Поскольку адресные пространства каждого процесса изолированы друг от друга, система должна предоставлять процессам средства взаимодействия. Простейшее взаимодействие
Взаимоотношения между процессами.. Операционные системы 2011/12 Татьяна Романова 17 сентября 2011 г. 1 / 29 План на сегодня Терминалы. Группы процессов. Сессии. Концепция сигналов. Надежные и ненадежные
Объекты ядра Windows Типы объектов ядра маркеры доступа / access token события / event файлы / file проекции файлов / file mapping порты завершения ввода-вывода / I/O completion port задания / Job почтовые
Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Операционные системы: аспекты параллелизма Синхронизация-1 Линёв А.В. Тема обсуждения При
Операционная система FX-RTOS интерфейса HAL Версия 2.2 Содержание Введение… 3 Об этом руководстве… 3 Терминология… 3 Формат описания функций API… 3 Интерфейсы HAL… 5 Управление прерываниями…
Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Операционные системы: аспекты параллелизма Процессы и потоки Линёв А.В. Тема обсуждения
Технология адаптивного квотирования для построения высоконадежных систем Белохвостиков Эдуард инженер отдела сервисов SWD Software Построение комплексных систем Большая команда, местоположение разработчиков
* 1. Решение задачи взаимоблокировки ресурсов. Взаимоблокировка возникает, когда две и более задач постоянно блокируют друг друга из-за того, что задача каждой из сторон блокирует ресурс, необходимый другой
Домашняя работа 4 (2015) Problem H41: Синхронное чтение-2 Условие этой задачи практически дословно повторяет условие задачи H32, только вместо сигналов должны быть использованы семафоры. Напишите программу,
КВАЗИПЛАНИРОВЩИК ДЛЯ ИСПОЛЬЗОВАНИЯ ПРОСТАИВАЮЩИХ ВЫЧИСЛИТЕЛЬНЫХ МОДУЛЕЙ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ ПОД УПРАВЛЕНИЕМ СУППЗ А.В. Баранов, Е.А. Киселёв, Д.С. Ляховец Межведомственный суперкомпьютерный
32. Принципы построения операционных систем. Вычислительный процесс и его реализация с помощью ОС. Управление вычислительными процессами, вводом-выводом, реальной памятью. Принципы построения операционных
Параллелизм Многопоточность Зачем создавать параллельные системы? Природные ограничения Невозможно бесконечно наращивать быстродействие одноядерных процессоров. Пример 1 такт 4 ГГц процессора 0.25 нс.
Лекция 6. Использование файловых дескрипторов. Пользовательский файловый дескриптор Cистемныe вызовы для работы с файлом: 1. open/creat 1 открыть/создать файл с заданными опциями и режимом доступа int
ВГКС Кафедра ПОСТ Курс «Системное программное обеспечение» Лабораторная работа 1 (4 часа) Тема: «Создание потоков в Win32 API для ОС MS Windows». Создается поток функцией CreateThread, которая имеет следующий
ГОУВПО «Поволжский государственный университет телекоммуникаций и информатики» Раздел 6. Программное обеспечение управляющих комплексов. Операционные системы Лектор: реального времени проф. кафедры АЭС
Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Операционные системы: аспекты параллелизма Задача «Производители-Потребители» Потребители
«Операционные системы» Контрольная работа. Задание. Управление процессами. Наиболее сложно объясняемое задание, но я постараюсь объяснить, чтобы было хоть коечто понятно. Итак, нам дана таблица и процесса,
Лекция 22 Топологическая сортировка. 22.1. Представление произвольного дерева в виде двоичного. 22.1.1. В отличие от двоичного дерева произвольное дерево не может быть пустым (по определению оно должно
Министерство образования Республики Беларусь Учреждение образования «Белорусский государственный университет информатики и радиоэлектроники» Кафедра электронно-вычислительных средств Д. С. Лихачёв РАЗРАБОТКА
Лабораторная работа 4 Цель: Лабораторная работа предназначена для приобретения практического опыта в создании приложения с использованием языка программирования С++ для математических расчѐтов. Призвана:
Модуль 1. ОБЩИЕ СВЕДЕНИЯ ОБ ОПЕРАЦИОННЫХ СИСТЕМАХ, СРЕДАХ И ОБОЛОЧКАХ 1. Операционная система это 1) комплекс управляющих и обрабатывающих программ 2) компоненты вычислительных машин и вычислительных систем
СИСТЕМНОЕ ПРОГРАММИРОВАНИЕ В WINDOWS Побегайло А. П. Системное программирование в Windows. СПб.: БХВ- Петербург, 2006. — 1056 с: ил. ISBN 5-94157-792-3 Подробно рассматриваются вопросы системного программирования
СОСТАВИТЕЛИ: Рябый В.В., старший преподаватель кафедры математического обеспечения электронно-вычислительных машин Белорусского государственного университета; Побегайло А.П., доцент кафедры технологии
Примитивы синхронизации 2011 В чем основная проблема программных методов взаимоисключения? Невозможно гарантировать неразрывность выполнения отдельных действий: Программа может прерваться в любой момент
Источник: