Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Процессы и потоки
Содержание
- 1. Процессы и потоки
- 2. Ресурсы системыУправляющие таблицы ОСОбраз процессаПроцесс 1Процесс NПамятьУстройстваФайлыПроцессыПроцесс 1Процесс 3Процесс 2Процесс NПроцессорПервичные таблицы процессовТаблицы памятиТаблицы ввода-выводаТаблицы файлов
- 3. Управление процессамиПроцесс (process) - это программа при
- 4. Понятие процессаОС исполняет множество классов программ:Пакетная система
- 5. Задание (JOB)ОбъектыПроцесс 2Процесс NПроцесс 1Поток 2Thread 2Поток kThread kПоток 1Thread 1Волокна (Fibers)
- 6. Однопоточные и многопоточные процессы
- 7. Образ процесса: программа, данные, стек и атрибуты процесса
- 8. Дескриптор процесса содержит:1. Информацию по идентификации процесса
- 9. Слайд 9
- 10. Слайд 10
- 11. Информация по состоянию и управлению процессом
- 12. КОНТЕКСТ ПРОЦЕССА Содержимое регистров процессора, доступных пользователю
- 13. Переключение контекста процесса (context switch)Когда процессор переключается
- 14. Простейшая модель процессаДиспетчеризацияПаузаНе выполняетсяВыполняетсяВходВыходCPUВходВыходОчередьПаузаДиспетчеризацияCPUГраф состояний и переходовtкв
- 15. Потоки и их модели Описатель потока: блок
- 16. Типичный граф состояния потокаВЫПОЛНЕНИЕГОТОВНОСТЬОЖИДАНИЕПоток завершен или ошибкаПоток
- 17. В мультипрограммной системе поток может находиться в
- 18. Переход от выполнения одного потока к другому
- 19. Алгоритмы планирования потоковНевытесняющие (non-preemptive) планирование распределяется между
- 20. В большинстве операционных систем универсального назначения планирование
- 21. Критерии диспетчеризацииИспользование процессора – поддержание его в
- 22. Алгоритмы планирования, основанные на квантовании Каждому потоку
- 23. Поток, который исчерпал свой квант, переводится в
- 24. Стратегия Round Robin (RR) – “круговая система”Каждый
- 25. Алгоритмы планирования, основанные на приоритетах Приоритет
- 26. Во многих ОС предусматривается возможность изменения приоритетов
- 27. 313016-1015Системные приоритетыПользоват. приоритеты786НаивысшийПовышенныйОбычныйПониженныйНаинизшийПоток обнуления страницПустой потокБазовый приоритетНаивысшийНаинизшийОчереди системных потоков и потоков псевдореального времениНаивысшийНаинизшийПРОЦЕССОР
- 28. Изменение базового приоритета потока
- 29. Механизм прерыванийПрерывание принудительная передача управления от
- 30. Схема обработки прерываний
- 31. Обозначения;! Прерывание (сигнал – установление факта
- 32. Назначение и типы прерываний В зависимости от
- 33. Внутренние прерывания, называемые также исключениями (exeption), происходят
- 34. Программные прерывания отличаются от предыдущих двух классов
- 35. Прерываниям приписывается приоритет, с помощью которого они
- 36. Процедуры, вызываемые по прерываниям, обычно называют обработчиками
- 37. Распределение прерываний по уровням приоритета Средства контроля процессораСистемный таймерМагнитные дискиСетевое оборудованиеТерминалыПрограммные прерыванияВнешние устройстваПриоритет
- 38. Два основных способа, с помощью которых шины
- 39. Вектор прерываний, передаваемый в процессор, представляет собой
- 40. При использовании опрашиваемых прерываний процессор получает от
- 41. Слайд 41
- 42. Слайд 42
- 43. Взаимодействие и синхронизация процессов и потоков Проблемы взаимодействия и синхронизации
- 44. Конкуренция процессов в борьбе за ресурсыКонкуренция –
- 45. Взаимоблокировки (тупики, deadlock) Группа процессов находится в
- 46. Проблема “голодание”RRRRP1P2P3P1P2P3P1P2P3P1P2P3АктивныйБлокированныеБлокированныеАктивныйАктивныйБлокированныеБлокированныеАктивный
- 47. Сотрудничество с использованием разделенияПроцессы, взаимодействующие с другими
- 48. Методы взаимоисключенийЗапрещение прерываний при входе в критическую
- 49. Использование системных функций входа в критическую секциюСистемный
- 50. Семафоры Дийкстры (Dijkstra)Семафор: переменная S, примитивы P
- 51. Слайд 51
- 52. feNНачальные значения семафоровe = N; f =
- 53. Взаимоблокировки (тупики)Условия возникновения взаимоблокировки (тупиковой) ситуации:Взаимное исключение.
- 54. Методы обнаружения взаимоблокировокВ системе один ресурс каждого
- 55. циклRACSFDBTEUWGVГраф ресурсов и процессов
- 56. 2. В системе несколько ресурсов каждого типа.
- 57. Алгоритм обнаружения тупиковОснован на сравнении векторов ресурсов.
- 58. Методы устранения тупиковПринудительная выгрузка ресурсов. Изъятие ресурса
- 59. Синхронизирующие объекты ОСДля синхронизации потоков, принадлежащих разным
- 60. Слайд 60
- 61. Слайд 61
- 62. Проблема обедающих философов. Полезна для моделирования
- 63. Решение задачи обедающих философов#define N 5 /*
- 64. void take_forks(int i) /* i - номер
- 65. Траектории ресурсов ДискДиск
- 66. Алгоритм банкира
- 67. Межпроцессное взаимодействие (англ. Inter-Process Communication, IPC) —
- 68. Виды механизмов межпроцессного взаимодействия (InterProcess Communication - IPC)
- 69. Слайд 69
- 70. Межпроцессный обмен на локальном компьютереЗапись
- 71. Слайд 71
- 72. Организации очереди в массивеУказатель на конец Указатель на начало
- 73. Слайд 73
- 74. Слайд 74
- 75. Отображаемые файлы
- 76. Слайд 76
- 77. Слайд 77
- 78. Слайд 78
- 79. Скачать презентанцию
Ресурсы системыУправляющие таблицы ОСОбраз процессаПроцесс 1Процесс NПамятьУстройстваФайлыПроцессыПроцесс 1Процесс 3Процесс 2Процесс NПроцессорПервичные таблицы процессовТаблицы памятиТаблицы ввода-выводаТаблицы файлов
Слайды и текст этой презентации
Слайд 2Ресурсы системы
Управляющие таблицы ОС
Образ процесса
Процесс 1
Процесс N
Память
Устройства
Файлы
Процессы
Процесс 1
Процесс 3
Процесс 2
Процесс
N
Слайд 3Управление процессами
Процесс (process) - это программа при ее исполнении. Для
процесса требуется ряд ресурсов, включая время процессора, память, файлы, устройства
ввода-вывода, сетевые устройства и др.Обычно при создании процесса для него создается новое пространство виртуальной памяти
ОС отвечает за следующие действия, связанные с управлением процессами:
Создание и удаление процессов.
Приостановка и возобновление процессов.
Обеспечение механизмов для:
Синхронизации процессов (семафоры, мониторы и др.)
Взаимодействия процессов (условные переменные, события и др.)
Слайд 4Понятие процесса
ОС исполняет множество классов программ:
Пакетная система (batch system) –
задания (jobs)
Система с разделением времени – пользовательские программы (задачи –
tasks)Во многих учебниках термины “задание” и “процесс” – почти синонимы
Процесс – программа при ее выполнении; он должен выполняться последовательно
Процесс включает:
Счетчик команд (program counter)
Стек (stack)
Секцию данных (data section)
Слайд 5Задание (JOB)
Объекты
Процесс 2
Процесс N
Процесс 1
Поток 2
Thread 2
Поток k
Thread k
Поток 1
Thread
1
Волокна (Fibers)
Слайд 8Дескриптор процесса содержит:
1. Информацию по идентификации процесса (идентификатор процесса, идентификатор
пользователя,
идентификаторы родительского и дочерних процессов).
2. Информацию по состоянию процесса
3. Информацию,
используемую для управления процессом
Слайд 11Информация по состоянию и управлению процессом
Состояние процесса, определяющее
его готовность к выполнению (выполняющийся, готовый к выполнению, ожидающий события,
приостановленный);Данные о приоритете (текущий, по умолчанию, максимально возможный);
Информация о событиях – идентификация события, наступление которого позволит продолжить выполнение процесса;
Указатели, позволяющие определить расположение образа процесса в оперативной памяти и на диске;
Указатели на другие процессы (находящиеся в очереди на выполнение);
Флаги,сигналы и сообщения, имеющие отношение к обмену информацией между двумя независимыми процессами;
Данные о привилегиях, определяющие прав доступа к определенной области памяти или возможности выполнять определенные виды команд, использовать системные утилиты и службы;
Указатели на ресурсы, которыми управляет процесс;
Сведения по использованию ресурсов и процессора;
Информация, связанная с планированием.
Слайд 12КОНТЕКСТ ПРОЦЕССА
Содержимое регистров процессора, доступных пользователю (обычно 8 –
32 регистра и до 100 регистров в RISC – процессорах);
Содержимое счетчика команд;Состояние управляющих регистров и регистров состояния;
Коды условия, отражающие результат выполнения последней арифметической или логической операции (например, равенство нулю,переполнение);
Указатели стеков,хранящие параметры и адреса вызова процедур и системных служб.
Значительная часть этой информации фиксируется в виде слова состояния программы PSW (program status word – EFLAGS в процессоре Pentium).
Слайд 13Переключение контекста процесса (context switch)
Когда процессор переключается на другой процесс,
система должна сохранить состояние старого процесса и загрузить сохраненное состояние
для нового процессаПереключение контекста относится к накладным расходам (overhead); система не выполняет никаких полезных действий при переключении с одного процесса на другой
Время зависит от аппаратной поддержки.
Слайд 14Простейшая модель процесса
Диспетчеризация
Пауза
Не выполняется
Выполняется
Вход
Выход
CPU
Вход
Выход
Очередь
Пауза
Диспетчеризация
CPU
Граф состояний и переходов
tкв
Слайд 15Потоки и их модели
Описатель потока: блок управления потоком и контекст
потока (в многопоточной системе процессы контекстов не имеют).
Способы реализации пакета
потоков:в пространстве пользователя (user – level threads – ULT);
в ядре (kernel – level threads – KLT).
Слайд 16Типичный граф состояния потока
ВЫПОЛНЕНИЕ
ГОТОВНОСТЬ
ОЖИДАНИЕ
Поток завершен или ошибка
Поток ожидает завершения ввода-вывода
или другого события
Ввод-вывод завершен (событие произошло)
Поток вытеснен (исчерпал квант)
Поток выбран
на выполнениеВновь созданный поток
Слайд 17В мультипрограммной системе поток может находиться в одном из трех
основных состояний:
выполнение активное состояние потока, во время которого поток
обладает всеми необходимыми ресурсами и непосредственно выполняется процессором;ожидание пассивное состояние потока, находясь в котором поток заблокирован по своим внутренним причинам (ждет осуществления некоторого события, например завершения операции ввода-вывода, получения сообщения от другого потока или освобождения какого-либо необходимого ему ресурса);
готовность также пассивное состояние потока, но в этом случае поток заблокирован в связи с внешним по отношению к нему обстоятельством (имеет все требуемые для него ресурсы, готов выполняться, однако процессор занят выполнением другого потока).
Слайд 18Переход от выполнения одного потока к другому осуществляется в результате
планирования и диспетчеризации. Планирование потоков включает в себя решение двух
задач:определение момента времени для смены текущего активного потока;
выбор для выполнения потока из очереди готовых потоков.
Диспетчеризация сводится к следующему:
сохранение контекста текущего потока, который требуется сменить;
загрузка контекста нового потока, выбранного в результате планирования;
запуск нового потока на выполнение.
Слайд 19Алгоритмы планирования потоков
Невытесняющие (non-preemptive)
планирование распределяется между ОС и прикладными
программами;
необходимость частых передач управлений ОС, в противном случае возможна
монополизация процессора приложением;зависания приложений могут привести к краху системы
2. Вытесняющие (preemptive)
функции планирования сосредоточены в ОС;
планирование на основе квантования процессорного времени;
планирование на основе приоритетов потоков: статических, динамических, абсолютных, относительных, смешанных;
Слайд 20В большинстве операционных систем универсального назначения планирование осуществляется динамически (on-line),
то есть решения принимаются во время работы системы на основе
анализа текущей ситуации.Планировщик называется статическим, если он принимает решения о планировании не во время работы системы, а заранее (off-line).
Слайд 21Критерии диспетчеризации
Использование процессора – поддержание его в режиме занятости, насколько
это возможно
Пропускная способность (throughput) – число процессов, завершающих свое выполнение
за единицу времениВремя обработки (turnaround time) – время, необходимое для исполнения какого-либо процесса
Время ожидания (waiting time)– время, которое процесс ждет в очереди процессов, готовых к выполнению
Время ответа (response time) – время, требуемое от момента первого запроса до первого ответа (для среды разделения времени)
Слайд 22Алгоритмы планирования, основанные на квантовании
Каждому потоку поочередно для выполнения предоставляется
ограниченный непрерывный период процессорного времени квант.
Смена активного потока
происходит, если:поток завершился и покинул систему;
произошла ошибка;
поток перешел в состояние ожидания;
исчерпан квант процессорного времени, отведенный данному потоку.
Слайд 23Поток, который исчерпал свой квант, переводится в состояние готовности и
ожидает, когда ему будет предоставлен новый квант процессорного времени, а
на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых.Кванты, выделяемые потокам, могут быть одинаковыми для всех потоков или различными.
Слайд 24Стратегия Round Robin (RR) – “круговая система”
Каждый процесс получает небольшой
квант процессорного времени, обычно – 10-100 миллисекунд. После того, как
это время закончено, процесс прерывается и помещается в конец очереди готовых процессов.Если всего n процессов в очереди готовых к выполнению, и квант времени - q, то каждый процесс получает 1/n процессорного времени порциями самое большее по q единиц за один раз. Ни один процесс не ждет больше, чем (n-1)q единиц времени.
Производительность
q велико FIFO
q мало q должно быть большим, по сравнению со временем контекстного переключения, иначе слишком велики накладные расходы
Слайд 25Алгоритмы планирования, основанные на приоритетах
Приоритет это число, характеризующее
степень привилегированности потока при использовании ресурсов вычислительной машины, в частности,
процессорного времени: чем выше приоритет, тем выше привилегии, тем меньше времени будет проводить поток в очередях.
Слайд 26Во многих ОС предусматривается возможность изменения приоритетов в течение жизни
потока.
В этом случае приоритеты называются динамическими в отличие от
неизменяемых, фиксированных, приоритетов.
Слайд 2731
30
16
-1
0
15
Системные приоритеты
Пользоват. приоритеты
7
8
6
Наивысший
Повышенный
Обычный
Пониженный
Наинизший
Поток обнуления страниц
Пустой поток
Базовый приоритет
Наивысший
Наинизший
Очереди системных потоков и
потоков псевдореального времени
Наивысший
Наинизший
ПРОЦЕССОР
Слайд 28Изменение базового приоритета потока
Увеличение приоритета
+ 1 – завершение ввода-вывода по диску; + 2 – для последовательной линии; + 6 – клавиатура; + 8 – звуковая карта; + 2 – снимается блокировка по семафору (для потока переднего плана); + 1 - снимается блокировка по семафору (для потока непереднего плана); приоритет 15 на 2 кванта процессора, если готовый к выполнению поток простаивает более некоторого директивного времени.
Уменьшение приоритета
- 1 – если полностью использован квант времени процессора (многократно, вплоть до базового приоритета).
Слайд 29Механизм прерываний
Прерывание принудительная передача управления от выполняемой программы к
системе, происходящая при возникновении определенного события.
Слайд 31Обозначения;
! Прерывание (сигнал – установление факта прерывания)
1 Идентификация
прерывания
2 Отключение всех других прерываний
3 Смена контекста_1
(сохранение состояния прерванного процесса из системных регистров, загрузка в системные регистры контекста соответствующего обработчика прерываний)4 Обработка прерывания, включающая определение программы Q, которую следует запустить;
5 Смена контекста_2 (загрузка в системные регистры контекста определенной на предыдущем шаге программы Q)
6 Установка прежнего режима системы прерываний.
Слайд 32Назначение и типы прерываний
В зависимости от источника прерывания делятся на
три больших класса:
внешние;
внутренние;
программные.
Внешние прерывания могут возникать в результате
действий пользователя или оператора за терминалом, или же в результате поступления сигналов от аппаратных устройств — сигналов завершения операций ввода-вывода, вырабатываемых контроллерами внешних устройств компьютера . Внешние прерывания называют также аппаратными.Данный класс прерываний является асинхронным по отношению к потоку инструкций прерываемой программы.
Слайд 33Внутренние прерывания, называемые также исключениями (exeption), происходят синхронно выполнению программы
при появлении аварийной ситуации в ходе исполнения некоторой инструкции программы.
Примерами исключений являются деление на нуль, ошибки защиты памяти, обращения по несуществующему адресу, попытка выполнить привилегированную инструкцию в пользовательском режиме и т. п.
Слайд 34Программные прерывания отличаются от предыдущих двух классов тем, что они
по своей сути не являются «истинными» прерываниями. Программное прерывание возникает
при выполнении особой команды процессора, .выполнение которой имитирует прерывание, то есть переход на новую последовательность инструкций.
Слайд 35Прерываниям приписывается приоритет, с помощью которого они ранжируются по степени
важности и срочности. О прерываниях, имеющих одинаковое значение приоритета, говорят,
что они относятся к одному уровню приоритета прерываний.
Слайд 36Процедуры, вызываемые по прерываниям, обычно называют обработчиками прерываний, или процедурами
обслуживания прерываний (Interrupt Servie Routine, ISR). Аппаратные прерывания обрабатываются драйверами
соответствующих внешних устройств, исключения — специальными модулями ядра, а программные прерывания — процедурами ОС, обслуживающими системные вызовы.В операционной системе может находиться так называемый диспетчер прерываний, который координирует работу отдельных обработчиков прерываний.
Слайд 37Распределение прерываний по уровням приоритета
Средства контроля процессора
Системный таймер
Магнитные диски
Сетевое оборудование
Терминалы
Программные
прерывания
Внешние устройства
Приоритет
Слайд 38Два основных способа, с помощью которых шины выполняют прерывания: векторный
(vectored) и опрашиваемый (polled). В обоих способах процессору предоставляется информация
об уровне приоритета прерывания.В случае векторных прерываний в процессор передается также информация о начальном адресе программы - обработчика прерываний.
Слайд 39Вектор прерываний, передаваемый в процессор, представляет собой целое число в
диапазоне от 0 до 255, указывающее на одну из 256
программ обработки прерываний, адреса которых хранятся в таблице обработчиков прерываний.
Слайд 40При использовании опрашиваемых прерываний процессор получает от устройства только информацию
об уровне приоритета прерывания.
С каждым уровнем прерываний может быть связано
несколько устройств и соответственно несколько программ — обработчиков прерываний. процессор должен определить, какое устройство запросило прерывание. Это достигается вызовом всех обработчиков прерываний для данного уровня приоритета, пока один из обработчиков не подтвердит, что прерывание пришло от обслуживаемого им устройства. 
Слайд 44Конкуренция процессов в борьбе за ресурсы
Конкуренция – ситуация, когда два
или более процессов требуют доступ к одному и тому же
ресурсу (принтеру, файлу и т.п.), называемому критическим. Часть программы, использующая критический ресурс, называется критической секцией.Процесс А
Процесс В
Процесс А попадает в критическую область
T1
T2
T3
T4
Процесс А покидает критическую область
Процесс В пытается попасть в критическую область
Процесс В блокирован
Процесс В попадает в критическую область
Процесс В покидает критическую область
T
T
Процессы не должны одновременно находиться в критических областях.
В программе не должно быть предположений о скорости или количестве процессов.
Процесс, находящийся вне критической области, не может блокировать другие процессы.
Невозможна ситуация, в которой процесс вечно ждет попадания в критическую область.
Необходимость взаимоисключений:
Слайд 45Взаимоблокировки (тупики, deadlock)
Группа процессов находится в тупиковой ситуации, если
каждый процесс из группы ожидает события, которое может вызвать только
другой процесс из этой же группыПроцесс
Ресурс
R1
P2
R2
P1
Исходное распределение ресурсов
R1
P2
R2
P1
P2
P1
R1
R2
Тупиковая ситуация
Слайд 46Проблема “голодание”
R
R
R
R
P1
P2
P3
P1
P2
P3
P1
P2
P3
P1
P2
P3
Активный
Блокированные
Блокированные
Активный
Активный
Блокированные
Блокированные
Активный
Слайд 47Сотрудничество с использованием разделения
Процессы, взаимодействующие с другими процессами без наличия
явной информации о друг друге, обращаются к разделяемым переменным, к
совместно используемым файлам или базам данных.Проблемы: взаимоисключение, взаимоблокировка, голодание. Дополнительно: синхронизация процессов для обеспечения согласованности данных
Пример: пусть должно выполняться a = b при начальном значении a = b = 1
1-й вариант: процессы выполняются последовательно
P1: a = a + 1; b = b + 1; P2: b = 2 * b; a = 2 * a;
2-й вариант: процессы прерывают друг друга
P1: a = a + 1; прерывание; P2: b = 2 * b; прерывание;
P1: b = b + 1; прерывание; P2: a = 2 * a;
Согласование нарушено: a = 4, b = 3
Ситуации, в которых два или более процессов обрабатывают разделяемые данные (файлы) и конечный результат зависит от скоростей процессов (потоков), называются гонками.
Слайд 48Методы взаимоисключений
Запрещение прерываний при входе в критическую область и разрешение
прерываний после выхода из критической области. Достоинства: простота реализации. Недостатки:
монополизация процессора, возможный крах ОС при сбое процесса, невозможность использования в многопроцессорных системах.Блокирующие переменные (программный подход)
F(D)=1?
Да, свободен
Нет, занят
Попытка доступа к разделяемому ресурсу D
Занять ресурс F(D)=0
Критическая секция (работа с ресурсом D)
Освободить ресурс F(D)=1
Неделимая операция “проверка-установка”
Команды TC, BTR, BTS процессора Pentium (анализ и присвоение значения логической переменной)
Недостатки: необходимость постоянного опроса другими потоками, требующими тот же ресурс, блокирующей переменной; дополнительные затраты процессорного времени.
Слайд 49Использование системных функций входа в критическую секцию
Системный вызов
EnterCriticalSection()
Попытка доступа
к разделяемому ресурсу D
F(D)=1?
Нет
Да
Перевести данный поток в ожидание D
Установить блокирующую
переменную в состояние “Занято”, F(D) = 0Критическая секция (работа с ресурсом D)
Установить блокирующую переменную в состояние “Свободно”, F(D) = 1
Перевести поток, ожидающий ресурс D, в состояние Готовность
Системный вызов
LeaveCriticalSection()
Достоинство: исключается потеря времени процессора на циклическую проверку освобождения занятого ресурса.
Недостаток: растут накладные расходы ОС на по реализации функции входа в критическую секцию и выхода из нее
Слайд 50Семафоры Дийкстры (Dijkstra)
Семафор: переменная S, примитивы P (proberen – проверка;
down) и V (verhogen – увеличение, up)
V(S) – переменная S
увеличивается на 1 единым действием. Выборка, наращивание и запоминание не могут быть прерваны. К переменной S нет доступа во время выполнения этой операции.P(S) – переменная S уменьшается на 1, если это возможно, составясь в области неотрицательных значений. Если S уменьшить невозможно, поток, выполняющий операцию P, ждет, пока это уменьшение станет возможным. Операция P неделима.
В частном случае семафор S может принимать двоичные значения 0 и 1, превращаясь в блокирующую переменную (двоичный семафор).
Операция P заключает в себе потенциальную возможность перехода процесса, который ее выполняет, в состояние ожидания (если S = 0).
Операция V может при некоторых обстоятельствах активизировать процесс, приостановленный операцией P.
Для хранения процессов, ожидающих семафоры, используется очередь, работающая по принципу FIFO.
Слайд 52f
e
N
Начальные значения семафоров
e = N; f = 0
P(e)
Работа с разделяемым
ресурсом (e=e-1)
V(f) ( f=f+1)
Потоки-писатели
Потоки-читатели
Буферный пул
e > 0
P(f)
f > 0
Работа с
разделяемым ресурсом (f=f-1)V(e) (e=e+1)
e – пустые буферы, f – занятые буферы
Слайд 53Взаимоблокировки (тупики)
Условия возникновения взаимоблокировки (тупиковой) ситуации:
Взаимное исключение. Каждый ресурс в
данный момент или отдан ровно одному процессу, или недоступен.
Условие удержания
и ожидания. Процессы, в данный момент удерживающие полученные ранее ресурсы, могут запрашивать новые ресурсы.Отсутствие принудительной выгрузки ресурсов. У процесса нельзя забрать принудительно ранее полученные ресурсы.
Условие циклического ожидания. Существует круговая последовательность из двух и более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности.
Стратегии борьбы с взаимоблокировками:
1. Пренебрежение проблемой в целом. 2. Обнаружение и устранение взаимоблокировок (восстановление). 3. Недопущение тупиковых ситуаций с помощью аккуратного распределения ресурсов. 4. Предотвращать с помощью структурного опровержения одного из четырех условий, необходимых для взаимоблокировки
Слайд 54Методы обнаружения взаимоблокировок
В системе один ресурс каждого типа.
Например, пусть
система из семи процессов (A, B, C, D, E, F,
G) и шести ресурсов (R, S, T, V, W, U) в некоторый момент соответствует следующему списку:Процесс A занимает ресурс R и хочет получить ресурс S.
Процесс B ничего не использует, но хочет получить ресурс T.
Процесс C ничего не использует, но хочет получить ресурс S.
Процесс D занимает ресурс U и хочет получить ресурсы S и T.
Процесс E занимает ресурс T и хочет получить ресурс V.
Процесс F занимает ресурс W и хочет получить ресурс S.
Процесс G занимает ресурс V и хочет получить ресурс U.
ВОПРОС: Заблокирована ли эта система и если да, то какие процессы в этом участвуют?
ОТВЕТ МОЖНО ПОЛУЧИТЬ, ПОСТРОИВ ГРАФ РЕСУРСОВ И ПРОЦЕССОВ.
Слайд 562. В системе несколько ресурсов каждого типа.
P = {P1, P2,
. . . , Pn} – множество процессов, n –
число процессов;E = {E1, E 2, . . . , Em } – множество ресурсов, m – число типов ресурсов;
A = {A1, A2, . . . , Am} – вектор свободных ресурсов; AJ <= EJ, j = 1, m;
C = {cI J | i = 1, n; j = 1, m } – матрица текущего распределения ресурсов;
R = {ri j | i = 1, n; j = 1, m } – матрица запрашиваемых ресурсов.
Существующие ресурсы Доступные ресурсы
E = {E1, E 2, . . . , Em } A = {A1, A2, . . . , Am}
c11 c12 . . . . c1m r11 r12 . . . . r1m
c21 c21 . . . . c2m r21 r22 . . . . r2m
. . . . . . . . . . . . . .
cn1 cn2 cnm rn1 rn2 . . . . Rnm
Слайд 57Алгоритм обнаружения тупиков
Основан на сравнении векторов ресурсов. В исходном состоянии
все процессы не маркированы (не отмечены). По мере реализации алгоритма
на процессы будет ставиться отметка, обозначающая, что они могут закончить свою работу, т. е. не находятся в тупике. После завершения алгоритма любой немаркированный процесс находится в тупиковой ситуации.Алгоритм
Ищется процесс Pi , для которого i – я строка матрицы R меньше вектора
A, т. е. Ri <= A или ri j <= Aj , j = 1, m.
Если такой процесс найден, он маркируется, и далее прибавляется I - я
строка матрицы С к вектору A, т.е. Aj := Aj + сi j , j = 1, m.
Возврат к шагу 1.
3. Если таких процессов не существует, работа алгоритма заканчивается. Если есть немаркированные процессы, то они попали в тупик.
Слайд 58Методы устранения тупиков
Принудительная выгрузка ресурсов. Изъятие ресурса у процесса, передача
его другому процессу, а затем возврат ресурса таким образом, что
исходный процесс этого “ не замечает” (сложно и чаще всего невозможно).Восстановление через “откат”. Процессы периодически создают контрольные точки, позволяющие запустить процесс с предыстории. При возникновении тупика процесс, занимающий необходимый ресурс “откатывается” к контрольной точке, после которой он получил ресурс. Если возобновленный процесс вновь попытается получить данный ресурс, он переводится в режим ожидания освобождения этого ресурса.
Восстановление путем уничтожения процессов.
Недопущение тупиков путем безопасного распределения ресурсов. Подобные алгоритмы базируются на концепции безопасных состояний. Например, Дейкстрой был разработан алгоритм планирования, позволяющий избегать взаимоблокировок (алгоритм банкира).
Слайд 59Синхронизирующие объекты ОС
Для синхронизации потоков, принадлежащих разным процессам, ОС должна
предоставлять потокам системные объекты синхронизации.
К таким объектам относятся события (event),
мьютексы (mutex – mutual exclusion – взаимное исключение), системные семафоры и др. Объект-событие используется для того, чтобы оповестить потоки о том, что некоторые действия завершены.
Мьютекс (простейший двоичный семафор) используется для управления доступом к данным.
Семафоры используются для оповещения свершения последовательности событий.
Для синхронизации используются также “обычные ” объекты ОС: файлы, процессы, потоки
Все объекты синхронизации могут находиться в сигнальном и несигнальном (свободном) состоянии. Поток с помощью системного вызова WAIT(X) может синхронизировать свое выполнение с объектом синхронизации X. С помощью системного вызова SET(X) поток может перевести объект X в сигнальное состояние. Кроме того, в ОС определен набор сигналов для логической связи меду процессами, а также процессами и пользователями (терминалами).
Слайд 62Проблема обедающих философов. Полезна для моделирования процессов, соревнующихся за монопольный
доступ к ограниченному количеству ресурсов, например к устройствам ввода/вывода.
Слайд 63Решение задачи обедающих философов
#define N 5 /* Количество философов */
#define
LEFT (i+N-1)%N /* Номер левого соседа философа с номером i */
#define RIGHT (i+1)%N /* Номер правого соседа философа с номером i */
#define THINKING 0 /* Философ размышляет */
#define HUNGRY 1 /* Философ пытается получить вилки */
#define EATING 2 /* Философ ест */
typedef int semaphore; /* Семафоры - особый вид целочисленных переменных */
int state[N]; /* Массив для отслеживания состояния каждого философа */
semaphore mutex =1; /* Взаимоисключение для критических областей */
semaphore s[N]; /* Каждому философу по семафору */
void philosopher(int i) /* i - номер философа, от 0 до N-1 */
{
while (TRUE) { /* Повторять до бесконечности */
think(); /* Философ размышляет */
take_forks(i); /* Получает две вилки или блокируется */
eat(); /* Философ ест спагетти */
put_forks(i); /* Кладет на стол обе вилки */
}
}
Слайд 64void take_forks(int i) /* i - номер философа, от 0
до N-1*/
{
down(&mutex); /* Вход в критическую область */
state[i] =
HUNGRY; /* Фиксация наличия голодного философа */test(i); /* Попытка получить две вилки */
up(&mutex); /* Выход из критической области */
down(&s[i]); /* Блокировка, если вилок не досталось */
}
void put_forks(i) /* i - номер философа, от 0 до N-1*/
{
down(&mutex); /* Вход в критическую область */
state[i] = THINKING; /* Философ перестал есть */
test(LEFT); /* Проверить, может ли есть сосед слева */
test(RIGHT); /* Проверить, может ли есть сосед справа */
up(&mutex); /* Выход из критической области */
}
void test(i) /* i - номер философа, от 0 до N-1*/
{
if (state[i] == HUNGRY && state[LEFT] != EATING && state[RIGHT] != EATING) {
State[i] = EATING;
up(&s[i]);
}
}
Слайд 67Межпроцессное взаимодействие (англ. Inter-Process Communication, IPC) — набор способов обмена
данными между множеством потоков в одном или более процессах. Процессы
могут быть запущены на одном или более компьютерах, связанных между собой сетью. IPC-способы делятся на методы обмена сообщениями, синхронизации, разделяемой памяти и удаленных вызовов (RPC). Методы IPC зависят от пропускной способности и задержки взаимодействия между потоками и типа передаваемых данных.IPC также может упоминаться как межпотоковое взаимодействие (англ. inter-thread communication), межпоточное взаимодействие и межпрограммное взаимодействие (англ. inter-application communication).
