ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
УФИМСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра ВТ и ЗИ
РЕФЕРАТ
По предмету:
«Особенности СПО ВВС»
Выполнил: магистрант 2 года
ФИРТ ВВС - 609
Евграфов М.Ю.
Проверил:
профессор Гараев Р.А.
УФА 2010
Содержание
1Методы и средства программирования ВВС 3
2Синхронизация процессов 3
3Средства синхронизации и взаимодействия процессов 3
4Проблема синхронизации 3
5Семафоры 4
6Почтовые ящики 5
7Монитор Хоара 5
8Программирование процессов 6
9Состояние процессов 6
10Контекст и дескриптор процесса 7
11Алгоритмы планирования процессов 7
12Вытесняющие и невытесняющие алгоритмы планирования 9
13Методы структурного программирования 11
14Краткое описание подхода 11
15Основная структура данных – сеть данных 12
16Потоковая обработка 13
17Алгоритм золотой горы 14
18Алгоритм Евклида 14
19Метод нисходящего программирования 16
20Методология SADT 17
21Операционные системы ВВС 19
22 ОС UNIX 19
23История 20
24Предшественники 20
25Первые UNIX 20
26Раскол 21
27Свободные UNIX-подобные операционные системы 22
28Современность 23
29Влияние UNIX на эволюцию операционных систем 24
30Некоторые архитектурные особенности ОС UNIX 25
31Стандарты 26
32Стандартные команды ОС UNIX 27
33ОС QNX 27
34Что такое QNX 28
35Архитектура ядра системы QNX 28
36Ядро системы QNX 28
37Системные процессы 29
38Системные процессы и процессы пользователя 29
39Драйверы устройств 29
40Связь между процессами 30
41Операционная система с передачей сообщений 30
42Языки программирования ВВС 31
43Язык ОККАМ 31
44Процессы 31
45 Процессы, не выполняющие действий 31
46Последовательные процессы 31
47Параллельные процессы. 31
48Процессы времени 32
49Описание данных 32
50Циклы 32
51Приоритеты 32
52 Структура программирования 32
53Язык Forth 33
54История 33
55Основные понятия классической Форт-системы 34
56Типы кода Форта 35
57Примеры программ 36
58Место Forth среди других языков программирования 37
1Методы и средства программирования ВВС 2Синхронизация процессов
Важнейшей частью операционной системы, непосредственно влияющей
на функционирование вычислительной машины, является подсистема управления процессами. Процесс (или по-другому, задача) - абстракция, описывающая выполняющуюся программу. Для операционной системы процесс представляет собой единицу работы, заявку на потребление системных ресурсов. Подсистема управления процессами планирует выполнение процессов, то есть распределяет процессорное время между несколькими одновременно существующими в системе процессами, а также занимается созданием и уничтожением процессов, обеспечивает процессы необходимыми системными ресурсами, поддерживает взаимодействие между процессами.
3Средства синхронизации и взаимодействия процессов
Возможно выделить следующие средства синхронизации:
а) Семафоры
б) Почтовые ящики
в) Монитор Хоара
Для того чтобы осуществлять совместный доступ к данным двух процессов одновременно используются критические секции.
4Проблема синхронизации
Процессы, выполняемые в мультипрограммном режиме, можно рассматривать как набор последовательных слабосвязанных процессов, которые действуют почти независимо друг от друга, лишь изредка используя общие ресурсы. Взаимосвязь между такими процессами устанавливается с помощью различных сообщений и так называемого механизма синхронизации, который позволяет согласовывать и координировать работу процессов.
Хотя каждый процесс, выполняемый в мультипрограммном режиме, имеет доступ к общим ресурсам, существует некоторая область, которую в фиксированный момент времени может использовать лишь один процесс. Нарушение этого условия приведет к неизвестному порядку обработки процессов. Назовем такую область критической. При использовании критической области возникают различные проблемы, среди которых можно выделить проблемы состязания (гонок) и тупиков (клинчей).
Условие состязания возникает, когда процессы настолько связаны между собой, что порядок их выполнения влияет на результат операции.
Условие тупиков появляется, если два взаимосвязанных процесса блокируют друг друга при обращении к критической области.
- Пример тупиковой ситуации
В системах, допускающих перераспределение любых ресурсов в произвольной последовательности, но имеющей и неосвобожденные ресурсы, время от времени должны возникать тупиковые ситуации.
Пример. Пусть программе А нужен ресурс R1. Она запрашивает его и получает. Программе В нужен ресурс R2. Она запрашивает его и получает(см. рис 1). Далее, пусть программа А, не отпуская R1, запрашивает R2, а программа В, не отпуская R2, запрашивает R1. Налицо типичный клинч, если только один из ресурсов R1 или R2 не может быть освобожден до момента завершения обработки соответствующего процесса.
5Семафоры
В 1968 г. Э. Дейкстра предложил удобную форму механизма захвата/освобождения ресурсов, которую он назвал операциями P и V над считающими семафорами. Считающим семафором называют целочисленную переменную, выполняющую те же функции, что и байт блокировки. Однако в отличие от последнего она может принимать кроме "0" и "1" и другие целые положительные значения.
Семафоры – это часть абстракции, поддерживающая очередь постоянно ожидающих процессов.
Операции P и V над семафором S могут быть определены следующим образом.
P(S):
1. Уменьшить значение S на 1, т. е. S : = S – 1.
2. Если S < 0, выполнить ОЖИДАНИЕ (S).
V(S):
1. Увеличить значение S на 1, т. е. S : = S + 1.
2. Если S 0, выполнить ОПОВЕЩЕНИЕ (S).
Операция ОЖИДАНИЕ (S) (WAIT) блокирует обслуживание процесса, делает соответствующую отметку об этом и связывает процесс со значением переменной S.
Операция ОПОВЕЩЕНИЕ (S) (SIGNAL) просматривает связанный с переменной S список блокированных процессов. Если в списке есть процессы, ожидающие освобождения некоторого ресурса, управляемого (сигнализируемого) S, один из них переводится в состояние готовности, а в соответствующей ему записи делается отметка. С этого момента процесс становится опять доступным планировщику.
По определению, ожидание, связанное с операцией P(S), не является ожиданием "зависания", так как ожидающие процессы не используют центральный процессор. Так как несколько процессов могут ожидать операцию P(S) над отдельным семафором, во время приращения должен быть осуществлен выбор, какую контрольную точку процесса сделать доступной. Алгоритм выбора не определен, за исключением требования равнодоступности процессов, т. е. никакой процесс не может быть "забыт".
Типичным примером использования алгоритма семафоров является задача производитель/потребитель. Задается максимальная емкость хранилища. Производитель не должен переполнять его, а потребитель не должен пытаться брать продукцию из пустого хранилища.
Наиболее употребительные операции над семафорами:
создать семафор;
запросить состояние семафора;
изменить состояние семафора;
уничтожить семафор.
Операции над семафорами в силу своей неделимости позволяют блокировать или активизировать процессы при освобождении или запросах ресурсов любого типа (памяти, процессоров, устройств ввода-вывода и т. п.).
Наиболее показательно аппарат семафоров можно применить на следующей задаче.
Три курильщика сидят за столом. У одного есть табак, у другого – бумага, у третьего – спички. На столе могут появиться извне два из трех упомянутых предмета. Появившиеся предметы забирает тот курильщик, у которого будет полный набор предметов. Он сворачивает папиросу, раскуривает ее и курит. Новые два предмета могут появиться на столе только после того, как он кончит курить. Другие курильщики в это время не могут начать курение.
Задание. Описать с помощью P и V – операций над семафорами – систему процессов, которая моделирует взаимодействия этих курильщиков.
Указание. Выделить шесть процессов, три из которых соответствуют трем курильщикам X, Y, Z, а три других имеют следующее назначение: А – поставляет спички и бумагу, В – табак и спички, С – бумагу и табак.
Требование. Процессы-поставщики не знают, какие предметы находятся у курильщиков.
Проблема взаимоисключения включает в себя нахождение протокола, который может использоваться отдельными процессами в момент входа в критический раздел или выхода из него.
Рассмотренные приемы синхронизации просты и сравнительно эффективны, однако их использование приводит порой к сложным и труднопостижимым конструкциям, которые чувствительны к незначительным изменениям.
6Почтовые ящики
Почтовый ящик – это информационная структура с заданием правил, описывающих его работу. Она состоит из главного элемента, где располагается описание почтового ящика, и нескольких гнезд заданных размеров для размещения сообщений.
Если процесс p1 желает послать процессу p2 некоторое сообщение, он записывает его в одно из гнезд почтового ящика, откуда p2 в требуемый момент времени может его извлечь. Иногда оказывается необходимым процессу p1 получить подтверждение, что p2 принял переданное сообщение. Тогда образуются почтовые ящики с двусторонней связью. Известны и другие модификации почтовых ящиков, в частности порты, многовходовые почтовые ящики и т. д. Для установления связей между процессами широко используются почтовые ящики. Примером такого применения может служить операционная система IPMX86 ВС фирмы Intel для вычислительных комплексов на основе микропроцессоров IAPX86 или IAPX88. Для целей синхронизации разрабатываются специальные примитивы создания и уничтожения почтовых ящиков, отправки и запроса сообщений.
Можно выделить три типа имеющихся в системе запросов: с ожиданием (ограниченным и неограниченным) или без ожидания. В случае ограниченного ожидания процесс, издавший запрос, если почтовый ящик пуст, ожидает некоторое время поступления сообщения. Если по истечении заданного кванта времени сообщение в почтовый ящик не поступило, процесс активизируется и выдает уведомление, что запрос не обслужен. В случае запроса без ожидания, если почтовый ящик пуст, указанные действия выполняются немедленно. Если время ожидания неограничено, процесс не активизируется до поступления сообщения в почтовый ящик.
Очевидно, что почтовые ящики позволяют осуществлять как обмен информацией между процессами, так и их синхронизацию.
7Монитор Хоара
Монитор – это набор процедур и информационных структур, которыми процессы пользуются в режиме разделения, причем в фиксированный момент времени им может пользоваться только один процесс.
Отличительная особенность монитора в том, что в его распоряжении находится некоторая специальная информация, предназначенная для общего пользования, но доступ к ней можно получить только при обращении к этому монитору.
Монитор не является процессом, это пассивный объект, который приходит в активное состояние только тогда, когда какой-то объект обращается к нему за услугами. Часто монитор сравнивают с запертой комнатой, от которой имеется только один ключ. Услугами этой комнаты может воспользоваться только тот, у кого есть ключ. При этом процессу запрещается оставаться там сколь угодно долго. Другой процесс должен ждать до тех пор, пока первый не выйдет из нее и передаст ключ.
В качестве примера программы-монитора может выступать планировщик ресурсов. Действительно, каждому процессу когда-нибудь понадобятся ресурсы и он будет обращаться к планировщику. Но планировщик одновременно может обслуживать только один ресурс.
Иногда монитор задерживает обратившийся к нему процесс. Это происходит, например, в случае обращения за занятым ресурсом. Монитор блокирует процесс с помощью команды "ЖДАТЬ", а в случае освобождения ресурса выдает команду "СИГНАЛ". При этом освободившийся ресурс предоставляется одному из ожидавших его процессов вместе с разрешением на продолжение работы. Управление передается команде монитора, непосредственно следующей за операцией "ЖДАТЬ".
Мониторы более гибки, чем семафоры. В форме мониторов сравнительно легко можно реализовать различные синхронизирующие примитивы, в частности семафоры и почтовые ящики. Кроме того, мониторы позволяют нескольким процессам совместно использовать программу, представляющую собой критический участок.
|
