Задание
Разработать программу, моделирующую работу мультипроцессорных систем в вышеперечисленный режимах;
Провести эксперимент на моделях в равных условиях с целью определения их эффективности.
Показателем эффективности является время обслуживания заявки.
Исходные данные:
Заявки поступают случайным образом с равным законом распределения;
Время обработки заявки случайно.
5. Cодержание отчёта
постановка задачи;
задание;
программы решения задачи;
контрольный пример;
результаты работы программ и их анализ.
Лабораторная работа n4
Анализ методов случайного доступа к каналу в ЛВС (Локальных Вычислительных Сетях). Методы Алоха.
Цель и порядок работы.
Целью данной работы является:
Научиться осуществлять анализ методов случайного доступа к каналу в LVS;
Произвести сравнение методов Алоха на предмет выявления более эффективного.
Порядок работы:
1. Ознакомиться с описанием лабораторной работы;
2. Выполнить задание раздела 3;
3. Ответить на контрольные вопросы теста;
4. Оформить отчет согласно указаниям раздела 4.
5. Представить результаты работы преподавателю.
2. Теоретические сведения. Принципы случайного доступа.
Двумя основными способами доступа к общей среде передачи являются управляемый доступ с применением опроса и случайный доступ. В свою очередь существуют различные типы стратегий случайного доступа.
Методы случайного доступа полностью децентрализованы. Пользователь может передавать когда угодно, лишь с незначительными ограничениями, зависящими от метода доступа.
Из-за случайности моментов времени, в которые пользователи могут решить начать передачу, независимо от метода не исключена возможность того, что два или несколько пользователей могут выйти на связь в пересекающиеся промежутки времени. Это приводит к столкновениям (коллизиям), которые сначала должны быть распознаны, а затем разрешены. При увеличении нагрузки увеличивается и вероятность коллизий, что приводит к возможной неустойчивости работы рассматриваемых механизмов.
В результате производительность ограничивается некоторым максимальным значением, меньшим пропускной способности канала, и это значение в каждом случае зависит от первоначального механизма доступа и алгоритма разрешения коллизий.
Сначала методы случайного доступа были предложены для случаев, когда большое число пользователей пытаются довольно редко передать пачки сообщений или, когда друг с другом связываются небольшое число ЭВМ. Но применимо к производственным процессам, которые требуют строгого управления задержкой доступа, более предпочтителен управляемый доступ. Рассмотрим два простейших типа стратегии случайного доступа: чистую Алоху и синхронную Алоху.
Чистая Алоха.
Эта схема сначала была применена для доступа к общему каналу сотрудниками Гавайского университета в начале 1970-х годов. По этой схеме пользователь, желающий передать сообщение, делает это когда угодно. В результате могут наложится во времени два или несколько сообщений, вызвав столкновение (коллизию).
Распознавание коллизий и сообщение о них пострадавшим пользователям в первоначальной системе Алоха направлялись по радио на центральный пункт. Также это могло осуществляться путем применения положительгых подтверждений в сочетании с перерывом. При обнаружении столкновения пострадавшие станции предпринимают попытки повторной передачи потерянного сообщения, но они должны распределять время попыток случайным образом, следуя некоторому алгоритму столкновения нового конфликта.
Стратегия доступа типа Чистой Алохи позволяет добиться производительности самое большее 1/2e0,18 пропускной способности канала. Введем сначала некоторые определения. За доступ к каналу состязаются N станций. Станция передает, в среднем, пакетов в секунду (интенсивность обращений к сети). Величина 1/m представляет собой пропускную способность канала () в передаваемых пакетах в секунду. Рассмотрим теперь частный случай, при котором все передаваемые сообщения (пакеты) имеют среднюю длину , соответствующую m единицам времени передачи. Будем считать, что интенсивность нагрузки S (эквивалентно - нормированной по нагрузке) характеризует использование канала вновь поступающими пакетами
S Nm.
Величина 1/, которая обозначается , представляет собой пропускную способность канала в передаваемых пакетах в секунду. Таким образом, N/ Nm - относительное использование канала, или производительность, нормированная относительно каждого компьютера одинакова. Общая интенсивность пакетов, передаваемых в канал, включая вновь генерируемые и передаваемые повторно, имеет некоторое значение ’ > (из-за коллизий от каждого компьютера будет передаваться больше сообщений из-за необxодимости возобновлять поток). Тогда фактическая интенсивность нагрузки, или использование канала, является параметром G, который равен
G = N’.
Рассмотрим типичное сообщение длительностью с, показанное на рис.1.
Ошибка! Ошибка связи.
Рис. 1. Столкновение двух сообщений
Оно подвергается столкновению с другим сообщением, если эти два сообщения будут наложены одно на другое в любой точке. Легко заметить, передвигая пунктирное сообщение во времени, что столкновение может произойти в промежутке времени продолжительностью 2 с. Вероятность того, что в промежутке 2 с не произойдет столкновения, равна e-2N’m=e-2G.
Отношение S/G представляет долю сообщений из числа передаваемых в канал, которые проходят успешно. Это число должно быть равно вероятности отсутствия столкновений. Таким образом уравнение производительности для чистой Алохи:
S = Ge-2G (1).
Здесь S - нормированная производительность (средняя скорость поступления пакетов, деленная на максимальную производительность 1/m), а G - нормированная пропущенная нагрузка. Таким образом, S – независимая переменная, а G - ее функция. График зависимости G от S имеет вид двузначной кривой (рис. 2).
Рис.2. Характеристика производительности; Чистая Алоха
Отметим, что S имеет максимум S = 0,5e-1 0,18 при G = 0.5. Судя по формуле (1) или кривой при малой постутающей нагрузке S столкновения происходят редко, и G S. Когда S начинает расти, приближаясь к максимальному значению 0.18, число столкновений быстро увеличивается, что ведет в свою очередь к росту вероятности столкновения. Система теряет устойчивость, S падает, а G увеличивается до больших значений.