Петербургский Университет Телекомунникаций им проф. Бонч-Бруевича курс лекций

Вид материала

Курс лекций

Содержание Обмен сообщениями между процессами. Алгоритмы априорного удаления тупиков. Алгоритм Дейкстры. Алгоритмы управления памятью.

Подобный материал:

• Федеральное агентство связи санкт-петербургский государственный университет телекоммуникаций, 39.82kb.
• Петербургский Государственный Университет телекоммуникаций им проф. М. А. Бонч-Бруевича, 55.39kb.
• Федеральное агентство связи санкт-петербургский государственный университет телекоммуникаций, 30.2kb.
• М. А. Бонч-Бруевича Кафедра опдс бочелюк Т. В., Доронин Е. М. «Назначение и примеры, 612.04kb.
• «мобильная связь», 49.1kb.
• Название доклада: универсальный, 63.37kb.
• Петербургский Государственный Университет Телекоммуникаций им проф. М. А. Бонч-Бруевича, 269.66kb.
• Петербургский Государственный Университет Телекоммуникаций им проф. М. А. Бонч-Бруевича, 143.46kb.
• Проблемы формирования учебно-методического комплекса, 151.02kb.
• Учебное пособие министерство Российской Федерации по связи и информатизации Санкт-Петербургский, 1446.56kb.

STI

Пример:




С
1)-3)
четчик семафора = 1 (начальное состояние)




P
P3
1 P2 P3

з
P2
ахв_семаф захв_сем захв_сем


Критический участок







о
4)
св_сем осв_сем осв_сем




1) P1: сч_сем = 0; P1 – в критический участок

2
P3
) P2: сч_сем = -1; P2 – в очередь семафора

3) P3 сч_сем = -2; P3 – в очередь семафора

4. P1 – закончился; сч_сем = -1; P2 – из очереди семафора в критический участок
   
5. P2 – закончился; сч_сем = 0; P3 – из очереди семафора в критический участок
   
6. P3 – финишировал; сч_сем = 1; код программы закончил свою работу
   

Примечание: в этой конструкции значение сч_сем = 1 – эквивалентно тому, что очередь семафора пуста, а критический участок – свободен.


Примитивы сообщения;

Самый медленный способ.

Придерживается следующих функций:

а) синхронизация медленных и быстрых устройств;

б) обмен сообщениями между процессами (подпрограммами).


С точки зрения ОС последовательные файлы – это ничто иное, как буферы к устройствам ввода/вывода.

Именно буфер выступает в качестве синхронизации между устройствами и вычислительной системой.


Буфер  кольцевая очередь (см. курс СиАОЭДЭВМ).


Достоинства:

+ операции чтения и записи можно разделить по времени (что приводит к синхронизации).


Недостаток:

• любой буфер является фиксированным.
  

Устранение недостатка:

а) содержать в буфере дескриптор очереди, а не сами данные, что уменьшает информативность;

б) дополнить соответствующими динамическими очередями (правда это снизит скорость обработки).


Обмен сообщениями между процессами.


Этот обмен обеспечивается посредством т.н. почтового ящика. Главное требование – доставка соответствующему адресату (причем правильная доставка).


Протокол (требования):

1. прием/передача сообщений на пользовательском уровне должны выглядеть как вызовы процедур чтения/записи;
   
2. при обращении к процедуре чтения сообщения в случае его отсутствия процесс приостанавливается и ждет появления сообщения;
   
3. при обращении к процедуре записи сообщения и отсутствии процесса, ждущего это сообщение, последнее становится в очередь;
   
4. процесс, передающий сообщение, приостанавливается и ждет подтверждения.
   

По сути дела почтовый ящик – набор очередей.


Почтовый ящик – объект, который в качестве данных содержит:

• очер_сообщ, ожидающую процессы;
  
• очер_проц, ожидающую сообщения;
  
• очер_проц, ждущих подтверждения.
  

Методы: чтение/запись.


Уровни планирования ресурсов.


1)Простейший уровень; FIFO

2)Простейший уровень с защитой от тупиков (Deadlock);

3)2) + оптимальное использование ресурсов.


Тупики и борьба с ними.


4 причины (одновременно):

• метод ВИ (взаимных исключений);
  
• условие ожидания ресурса, при котором неработающие ресурсы не отпускаются;
  
• отсутствие “перетряхиваемой” системы;
  
• режим круговых ожиданий.
  

1 ресурс



1 процесс

2 процесс



2 ресурс




Методы борьбы с тупиками:

1. алгоритм, не допускающий тупики;
   

а) априорной защиты (более жесткие);

б) обхода тупиков (более мягкие).

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

Алгоритмы априорного удаления тупиков.


Эти алгоритмы так или иначе связаны с разрушением какой-либо из причин возникновения тупиков.

1. метод устранения 2-ой причины возникновения тупиков;
   

Основная идея – предоставлять либо все ресурсы системы, либо ни одного.


Недостатки:

1. нарушаются принципы FIFO;
   
2. не оптимально тратятся ресурсы системы.
   

2. метод устранения 3-ей причины возникновения тупиков (метод перераспределяемости);
   

Заключается в том, что система “перетряхивается” (т.е. нерабочие ресурсы возвращаются).


Недостатки:

1. нарушаются принципы FIFO;
   
2. неоптимальное использование ресурсов.
   

3. метод устранения 4-ой причины возникновения тупиков (упорядоченные классы);
   

На самом деле – это режим кругового ожидания.

Ресурсы нумеруются – 1, 2, 3, …

1 ресурс








2 проц.

1 проц.


2 ресурс

Ресурс более высокого класса выделяется в том случае, если уже взят ресурс более низкого класса (более высокий класс – условное разделение).


Алгоритм Дейкстры.


Идея заключается в том, что:


Вводится понятие надежного состояния (это состояние, находясь в котором система не зависнет даже при самых неблагоприятных прогнозах).


Переход осуществляется из одного надежного состояния в другое.



Исходные данные для планирования – матрица ресурсов, процессов и т.д.

Каждый раз, когда запрашивается ресурс, то анализируется ситуация при каждом запросе процесса ресурсов; если выделение этого ресурса приводит к другим НС, то ресурс выделяется, в противном случае – нет.


Пример:

проц	рес	Макс. число рес.
P1	3	6
P2	2	4
P3	1	5

Свободно 2 ресурса. Какому процессу их отдать? – второму, т.к. он поработает и отдаст их системе, т.е. здесь имеет место НС.


Достоинства:

+ гибкий алгоритм;

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


Недостатки:

• алгоритм работает для конкретного числа процессов;
  
• если число процессов n, то число ресурсов = n!
  

Алгоритм Габермана.


Это – графический режим.


2 пр.

1 пр.

Вершины – процессы

Дуги - ресурсы


1 рес.





Суть метода заключается в предоставлении ресурса до тех пор, пока не образуется цикл в графе (из рисунка видно, что 3-ий ресурс не предоставляется первому процессу)




1 рес.

3 рес.






3 пр.

4 пр.

5 пр.

2 рес.

Достоинства:

1. нет ограничений на количество процессов;
   
2. сложность проверки на наличие цикла в графе.
   

Алгоритм обнаружения и устранения дедлоков (deadlocks).

1. обнаружение дедлока (с помощью алгоритма Дейкстры или Габермана);
   

• В отличии от алгоритмов обхода эти алгоритмы включаются в некоторые единицы времени, а не при каждом принятии решения.
  

2. устранение дедлока;
   

2.1) перезапуск всей системы;

+ просто;

• теряется много данных.
  

2.2) перезапуск только тупиковых процессов;

+ данных теряется меньше;

• требуются дополнительные ресурсы для реализации перезапуска тупиковых процессов;
  

2.3) перезапуск по одному процессу (последовательно);

+ данных теряется еще меньше;

• дополнительных ресурсов требуется еще больше.
  

2.4) пережидание некоторого времени для возможного автоматического устранения тупика, а если не помогает – воспользование п.2.1)-2.3).


Управление памятью.

Общие вопросы.


В IBM PC-совместимых машинах существует 3 типа ОЗУ:


СОЗУ

СОЗУ – сверхоперативное запоминающее устройство

ОП – оперативная память

ДП – память долговременного хранения


ОП

объем

скорость


ДП





- среднее время на одну операцию




i80386 – процессоры стали иметь кэш 1-го уровня, который и решил проблему с адресацией


Начиная с Pentium’ов, появился кэш 2-го уровня, где производятся вычисления.


Виртуальная (адресуемая)
и физическая память.


ФП – обычная линейная память, измеряемая в байтах.

ФП характеризуется:

1. объемом;
   
2. возможностью адресации.
   

16-разрядный процессор   64 Кбайт

32-разрадный процессор   4 Гбайта


ВП – память адресуемая, “вращается” в программе.


Возможны 2 случая:

а)

б) - для 32-разрядных процессоров


Виртуальная память должна “сажаться” на физическую. Здесь возникают 2 аспекта:

а) на каком этапе? (см. далее)

б) как быстро? (в зависимости от организации ВП, см. далее)


пример (хотим считать порт LPT1):


mov ax, 40h 40h: 08h - LPT1

mov es, ax ; 40h в ES 09h – LPT2

mov bl, es:[08h]

mov bh, es:[09h] ; BX – номер порта LPT1


Система управления памятью (СУП).


СУП


Управление ФП Управление ВП

1. однозадачн. 1) плоская (линейная)
   

• простые; 2) сегментная
  
• с оверлейями (ovelays). 3) страничная организация памяти (самая быстрая)
  

2. многозадачн. 4) сегментно-страничная (начиная с i80386)
   

• с фиксированными разделами памяти
  (перемещаемые/неперемещаемые модули)
  
• с переменными разделами памяти
  
• динамическое распределение памяти
  

1. однозадачный режим;
   

а) простой

о
ОП
граничение:


Системные программы





Транзитная обл. памяти


ОС

б) с оверлейями


; программа разбивается на сегменты

сегмент перекр. 1

корневой сегмент сегмент перекр. 2

сегмент перекр. 3

- условие должно выполняться (КС – корневой сегмент, СП – сегмент перекр.)

2. многозадачный режим;
   

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


Системные программы


1

а) разделы постоянной длины;

б) каждая задача решается своим разделом





2


3


ОС

Недостатки:

- неоптимальный расход ресурсов;

а) объемы разделены, как правило, неадекватно объемам соответствующих задач;

б) некоторые разделы могут простаивать, а некоторые могут быть переполнены  большая вероятность незадействования разделов.


Алгоритмы управления памятью.


Эти алгоритмы связаны с преобразованием ВП в ФП.


- число страниц


Вопросы:

а) когда загружать страницы задачи в память?

б) куда загружать?

в) какую страницу выгружать?


Рассмотрим 1-ый аспект:

1. по факту (в то время, когда необходима эта загрузка);
   

+ выигрыш в памяти;

- проигрыш в производительности.

2. впрок (при любом обращении к задаче загружать как можно больше страниц этой задачи).
   

+ выигрыш в производительности;

• проигрыш в памяти.
  

Рассмотрим 2-ой аспект:

1. в первое попавшееся (свободное место);
   
2. в наиболее подходящее место;
   
3. в наименее подходящее место.
   

Системные программы





1

2


(страницы задачи)





3