Operatsioonisüsteemid. Операционные системы Virumaa Kolledž TTÜ Lektor Larissa Joonas

2 Ummikud. Взаимоблокировки

3 Ressursid. Ресурсы Ressursside näidised. Примеры ресурсов –Printerid Принтеры –Strimmerid Ленточные накопители –Tableid andmebaasis Таблица в базе данных Protsess sai kätte ressurss A ja küsib ressurss B. Процесс получил ресурс A и запрашивает ресурс B –Samal ajal teine protsess sai kätte ressursi B ja küsib ressursi A. В то же самое время другой процесс получил ресурс B и запрашивает ресурс A –Mõlemad protsessid on blokeeritud. Оба процесса блокируются

4 Ressursid. Ресурсы (1) Ummik võib tekkida juhul kui: Взаимоблокировки происходят, если … –Protsessid saavad kätte eksklusiivse juurdepääsu seadmetele. Процессы получают эксклюзивный доступ к устройствам –Me pöördume nende seadmete poole kui ressursidele. Мы обращаемся к этим устройствам, как к ресурсам Ressursid, mida on võimalik välja laadida. Выгружаемые ресурсы –Можно безболезненно забирать у владеющего им процесса Ressurssid, mida ei ole võimalik välja laadida. Невыгружаемые ресурсы –Нельзя забрать, не уничтожив результата вычислений Ei ole võimalik välja võtta, kui tulemus ei ole hävitatud

5 Ressursid. Ресурсы (2) Sündmuste järjestus, mis on vajalik ressursside kasutamiseks. Последовательность событий, необходимых для использования ресурса 1.Ressurssi taotlemine. Запрос ресурса 2.Ressurssi kasutamine. Использование ресурса 3.Ressurssi vabastamine. Возврат ресурса Kui ressurss on kinni, peab protsess ootama. Процесс вынужден ждать, если ресурс недоступен –Automaatselt blokeerub. Автоматически блокируется –Annab tagasi vea koodi Возвращает код ошибки

6 Sissejuhatus. Введение Formaalne definitsion. Формальное определение : Protsesside grupp on ummikus, kui iga protsess grupis ootab sündmust, mis võimaldaks kutsuda ainult teist protsessi samast grupist. – Группа процессов находится в тупиковой ситуации, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из той же группы

7 Sissejuhatus. Введение (1) Tavaliselt on vaja vabastada kinnitatud ressurss. –Обычно необходимо освободить ресурс, который занят Mitte ükski protsess ei saa... Ни один из процессов не может … –Olla käivitatud. Быть запущен –Vabastada ressurssi. Освободить ресурс –Taastuma. Возобновиться

8 Neli tingimusi ummiku ilmumist Четыре условия взаимоблокировки Mõlemapoolne väljaheitmise tingimus Условие взаимного исключения Iga ressurss on igal momendil antud kas ühele kindlale protsessile või on vaba. Каждый ресурс в данный момент или отдан ровно одному процессу, или доступен 1

9 Neli tingimusi ummiku ilmumist Четыре условия взаимоблокировки(1) Kinni pidamise ja ootamise tingimus Условие удержания и ожидания Protsessid, mis hoiavad enne saadud ressursse, saavad küsida uusi ressursse. Процессы, в данный момент удерживающие полученные ранее ресурсы, могут запрашивать новые ресурсы 2

10 3 Neli tingimusi ummiku ilmumist(2) Четыре условия взаимоблокировки Sundusliku väljalaadimise puudumise tingimus. Условие отсутствия принудительной выгрузки ресурса Ei ole võimalik võtta ära enne saatud ressurssid protsessidest. Protsess peab and välja ressurss vabatahtlikult У процесса нельзя принудительным образом забрать полученные ранее ресурсы. Процесс, владеющий ими, должен сам освободить ресурсы

11 4 Neli tingimusi ummiku ilmumist(2) Четыре условия взаимоблокировки Tsükkli ootamise tingimus Условие циклического ожидания Tsükkli järjestik 2. või rohkem protsessidest, kui iga protsess ootab järgmise protsessi ressurssi vabastamist. Круговая последовательность из 2-х или более процессов, каждый из которых ждет доступа к ресурсу, удерживаемому следующим членом последовательности

12 Ummiku modellerimine. Моделирование взаимоблокировок (1) Ressursi-allokatsiooni graaf –Графы распределения ресурсов Ressurss M kasutab protsess A. ресурс M занят процессом A –Protsess B küsib või ootab ressurssi. процесс B запрашивает или ожидает ресурс N –Protsessid A ja B on ummikus процессы A и B взаимоблокированы M A M A N B N A M B

13 Ummiku modellerimine. Моделирование взаимоблокировок (2) Ummikutega töötluse strateegia: Стратегии взаимодействия со взаимоблокировками: Probleemi ignoreerimine Проигнорировать проблему Leidmine ja ennistamine Обнаружение и восстановление

14 Ummiku modellerimine. Моделирование взаимоблокировок(3) Ummikutega töötluse strateegia: Стратегии взаимодействия со взаимоблокировками: Ummikute dünaamiline vältimine (avoidance) Динамическое избежание тупиковых ситуаций Аккуратное распределение ресурсов Ummikute ära hoidimine (prevention) Предотвращение Püüab garanteerida, et vähemalt üks eelpool mainitud 4-s tingimusest ei teki Структурное опровержение одного из 4 условий, необходимых для взаимоблокировки

15 Ummikute tekkimine. Возникновение взаимоблокировок A B C Ummiku modellerimine. Моделирование взаимоблокировок (3) M B N C P A

16 Ummiku modellerimine. Моделирование взаимоблокировок (4) Ummikute ära hoidimine. Предотвращение взаимоблокировок M B N C P A

17 Jaanalinnu algorütm. Страусовый алгоритм Teesklema, et probleeme ei eksisteeri. –Притвориться, что проблема не существует

18 Jaanalinnu algorütm. Страусовый алгоритм (2) Arukas, kui –Разумна, если Ummikuid tekkivad harva. Взаимоблокировки случаются редко Vältimise maksumus on kõrge. Стоимость предотвращения очень высока UNIX ja Windows kasutavad seda algporütmi. UNIX и Windows используют этот алгоритм Valik mugavuse ja korrektsuse vahel Выбор между –удобством –корректностью

19 Ummiku leidmine, kui saame ühe ressurssi igast tüüpist. Обнаружение взаимоблокировки при наличии одного ресурса каждого типа (1) Ressurssi graaf. Граф ресурсов A C B F D E M RS OP N

20 Ummiku leidmine, kui saame ühe ressurssi igast tüüpist. Обнаружение взаимоблокировки при наличии одного ресурса каждого типа (2) Maatriksid. Матрицы Mitmed ressussid igast tüüpist. Несколько ресурсов каждого типа

21 Ummikust väljaumine. Выход из взаимоблокировки (1) Ennistamine sundusliku väljalaadimise abil Восстановление при помощи принудительной выгрузки ресурса –Võtta ära teise protsessi ressurssi. Забрать ресурс у другого процесса –Sõltub ressurssi tüübist Зависит от типа ресурса Ennistamine tagastamise abil Восстановление через откат –Perioodilised kontroll punktid. Периодические контрольные точки –Kasutama salvestatus seisundit. Использовать сохраненное состояние –Protsessi ümberkäivitamine. Перезапустить процесс

22 Ummikust väljamine. Выход из взаимоблокировки (2) Ennistamine peale protsessi hävitamist. Восстановление путем уничтожения процесса –Karm ja kergem variant Грубейший, но и простейший способ выхода –Hävitama üht protsessi ummiku tsüklist. Уничтожить один из процессов из цикла взаимоблокировки –Valida protsessi, mis on võimalik ümberkäivitada algusest ilma kaotuseta. Выбрать процесс, который можно перезапустить с самого начала без потери

23 Ohutud ja ohtlikud seisundid. Безопасные и небезопасные состояния (1) Näitab, et a on ohutu. Демонстрация того, что состояние (a) безопасно (a) (b) (c) (d) (e) A39 B24 C27 Vaba 3 A39 B44 C27 Vaba 1 A39 B0- C27 Vaba 5 A39 B0- C77 Vaba 0 A39 B0- C0- Vaba 7

24 Ohutud ja ohtlikud seisundid. Безопасные и небезопасные состояния (2) (a) (b) (c) (d) A39 B27 C13 Vaba 3 A49 B24 C27 Vaba 2 A49 B44 C27 Vaba 0 A49 B-- C-7 Vaba 4 Näitab, et seisund b ei ole ohutu. Демонстрация того, что b небезопасно

25 Pankuri algorütm ühe ressurssi tüübile. Алгоритм банкира для одного вида ресурсов Kolm seisundid ressurssi jaotamisele. Три состояния распределения ресурсов (a) (b) (c) A 06 B 05 C 04 D 07 A 16 B 15 C 24 D 47 A 16 B 25 C 24 D 47 –ohutu безопасное –Ohutu безопасное –Mitte ohutu небезопасное Vaba 3 vaba 2 vaba 1

26 Ummikute ära hoidimine. Mõlemapoolne väljaheitmise tingimuse atakk. Предотвращение взаимоблокировок. Атака условия взаимного исключения Mõned seadmed, nagu printer, saavad kasutada cash-faili. Некоторые устройства, например, принтер, могут использовать подкачку –Printeri ressurssi kasutab ainult printeri deemon. Ресурсы принтера использует только демон принтера –On võimalik eemaldada ummik printerile. Можно исключить такую взаимоблокировку для принтера

27 Mõlemapoolne väljaheitmise tingimuse atakk. Атака условия взаимного исключения Mitte kõik seadmed kasutavad cash-i. Не все устройства используют подкачку Printsiipid Принципы: –Ärge andke ressursse, kui see ei ole vajalik. Избегайте выделения ресурса, если это не является необходимостью –Resurssile peab pretendeerima nii vähe protsesse, kui vähegi võimalik. На ресурс должно претендовать как можно меньше процессов

28 Kinni pidamise ja ootamis tingimuse atakk. Атака условия удержания и ожидания Välja nõudma ressursside taotlemist enne protsessi starti Требовать от процессов запроса ресурсов до старта –Protsess ei ole kohustatud ootama vajalike asju. Процесс никогда не должен ждать того, что ему нужно

29 Probleeme. Проблемы: Mõnikord protsess enne starti ei tea, kui palju ja missugused ressurssie on vaja. До старта может быть неизвестно, сколько и каких ресурсов необходимо Raske kasutada ressursse optimaalselt. Ресурсы не могут быть использованы оптимально Variandid. Вaрианты: Protsess peab vabastama kõik kasutatavad ressursid. Процесс должен освободить все используемые им ресурсы Taotlema kõiki vajalike ressursse. Запрашивает сразу все необходимое Kinni pidamise ja ootamis tingimuse atakk. Атака условия удержания и ожидания (2)

30 Sundusliku väljalaadimise puudumise tingimuse atakk Атака условия отсутствия принудительной выгрузки ресурса Mitte kindel tingimus. Ненадежное условие Printeri eemaldamine. Изъятие принтера

31 Tsükkli ootamise tingimuse atakk. Атака условия циклического ожидания (1) Nummerdatud ressurssid. Пронумерованные ресурсы Graaf.

32 Kahefaaside blokeering Двухфазовое блокирование Esimene faas. Первая фаза –Protsess katsub blokeerida kõik vajalikud kirjendid ühe kaupa. Процесс пытается заблокировать все требуемые записи по одной за раз –Kui mingisugune kirjend on blokeeritud, kõik blokeeringud vabastuvad ja algab 1. faas Если какая-то запись заблокирована, то все блокировки освобождаются и 1 фаза начинается заново Kui 1. faas läks edukalt, 2. faas algab. Если первая фаза прошла успешно, то начинается вторая фаза –Uuendamine. Обновление –Blookeringute vabastamine.Освобождение блокировок Ei ole samasugune nagui üheaegne ressurssi taotlemise metood. Не имеет общего с методом одновременного запроса всех ресурсов Algorütm töötab, kui programmerija vaatas üle varem tehtud 1. faasi haldamise. –Алгоритм работает, если программист предусмотрел обработку первой фазы Программа может быть остановлена и перезапущена

33 Ummikud ilma ressursita. Тупики без ресурсов Võimalik, kui kaks protsessid koostöötavad Возможно при взаимодействии двух процессов –Igasugune ootab kuni teine täidab oma ülesanne. Каждый ждет, пока другой выполнит какую-то задачу Võib juhtuda semafooriga.Может случиться с семафорами –Igasugune protsess tahab kasutada down() kahe semafooriga (mutex ja teine) Каждый процесс хочет совершить down() на двух семафорах (mutex и другой) –Kui järjekord on ebaõige, juhtub ummik. Если последовательность неправильна, то происходит блокировка

34 Nälgimine Голодание Ressurside jaotamise algorütm. Алгоритм распределения ресурсов –Võib anda lühemale ülesannele Может быть дано самой короткой задаче Töötab hästi süsteemis koos paljude väiksete ülessannetega. Хорошо работает в системе со множеством маленьких задач Võib lasta surra nälga suurel ülessandel Может дать умереть с голоду большой задаче Lahendamine. Решение: –Esimene tuli - esimene on teenindatud. Первым пришел – первым обслужен