Формальное определение

диаграмма автомата с магазинной памятью

В отличие от конечных автоматов, автомат с магазинной памятью является набором:

K — конечное множество состояний автомата

Σ — допустимый входной алфавит, из которого формируются строки, считываемые автоматом

S — алфавит памяти (магазина)

Память работает как стек, то есть для чтения доступен последний записанный в неё элемент. Таким образом, функция перехода является отображением e, в магазин ничего не добавляется, а элемент с вершины стирается. Если магазин пуст, то срабатывают правила с e в левой части.
Автомат с магазинной памятью может распознать любой контекстно-свободный язык.
В чистом виде автоматы с магазинной памятью используются крайне редко. Обычно это модель используется для наглядного представления отличия обычных конечных автоматов от синтаксических грамматик. Реализация автоматов с магазинной памятью отличается от конечных автоматов тем, что текущее состояние автомата сильно зависит от любого предыдущего.

2. Организация шин.

Совокупность трактов, объединяющих между собой основные устройства ВМ (цен­тральный процессор, память и модули ввода/вывода), образует структуру взаи­мосвязей вычислительной машины.

Структура взаимосвязей должна обеспечивать обмен информацией между: центральным процессором и памятью; центральным процессором и модулями ввода/вывода; памятью и модулями ввода/вывода.

С развитием вычислительной техники менялась и структура взаимосвязей ус­тройств ВМ (рис. 4.2). На начальной стадии преобладали непосредственные связи между взаимодействующими устройствами ВМ. С появлением мини-ЭВМ, и осо­бенно первых микроЭВМ, все более популярной становится схема с одной общей шиной. Последовавший за этим быстрый рост производительности практически всех устройств ВМ привел к неспособности единственной шины справиться с возросшим трафиком, и ей на смену приходят структуры взаимосвязей на базе нескольких шин. Дальнейшие перспективы повышения производительности вы­числений связаны не столько с однопроцессорными машинами, сколько с много­процессорными вычислительными системами. Способы взаимосвязей в таких си­стемах значительно разнообразнее, и их рассмотрению посвящен один из разделов учебника. Возвращаясь к вычислительным машинам, более внимательно рассмот­рим вопросы, связанные с организацией взаимосвязей на базе шин.

Рис. 4.2. Эволюция структур взаимосвязей (ЦП — центральный процессор, ПАМ — модуль основной памяти, МВВ — модуль ввода/вывода)

Взаимосвязь частей ВМ и ее «общение» с внешним миром обеспечиваются си­стемой шин. Большинство машин содержат несколько различных шин, каждая из которых оптимизирована под определенный вид коммуникаций. Часть шин скры­та внутри интегральных микросхем или доступна только в пределах печатной платы. Некоторые шины имеют доступные извне точки, с тем чтобы к ним легко можно было подключить дополнительные устройства, причем большинство таких шин не просто доступны, но и отвечают определенным стандартам, что позволяет подсоединять к шине устройства различных производителей.

Чтобы охарактеризовать конкретную шину, нужно описать (рис. 4.3): совокупность сигнальных линий; физические, механические характеристики и электрические характеристики шины используемые сигналы арбитража, состояния, управления и синхронизации;

правила взаимодействия подключенных к шине устройств (протокол шины).

Рис. 4.3. Параметры, характеризующие шину

Шину образует набор коммуникационных линий, каждая из которых способна передавать сигналы, представляющие двоичные цифры 1 и 0. По линии может пе­ресылаться развернутая во времени последовательность таких сигналов. При со­вместном использовании несколько линий могут обеспечить одновременную (па­раллельную) передачу двоичных чисел. Физически линии шины реализуются в виде отдельных проводников, как полоски проводящего материала на монтажной плате либо как алюминиевые или медные проводящие дорожки на кристалле микросхемы.

Операции на шине называют транзакциями. Основные виды транзакций — транзакции чтения и транзакции записи. Если в обмене участвует устройство вво­да/вывода, можно говорить о транзакциях ввода и вывода, по сути эквивалентных транзакциям чтения и записи соответственно. Шинная транзакция включает в себя две части: посылку адреса и прием (или посылку) данных.

Когда два устройства обмениваются информацией по шине, одно из них долж­но инициировать обмен и управлять им. Такого рода устройства называют ведущи­ми (bus master). В компьютерной терминологии «ведущий» — это любое устрой­ство, способное взять на себя владение шиной и управлять пересылкой данных. Ведущий не обязательно использует данные сам. Он, например, может захватить управление шиной в интересах другого устройства. Устройства, не обладающие возможностями инициирования транзакции, носят название ведомых (bus slave). В принципе к шине может быть подключено несколько потенциальных ведущих, но в любой момент времени активным может быть только один из них: если не­сколько устройств передают информацию одновременно, их сигналы перекрыва­ются и искажаются. Для предотвращения одновременной активности нескольких ведущих в любой шине предусматривается процедура допуска к управлению ши­ной только одного из претендентов (арбитраж). В то же время некоторые шины допускают широковещательный режим записи, когда информация одного веду­щего передается сразу нескольким ведомым (здесь арбитраж не требуется). Сиг­нал, направленный одним устройством, доступен всем остальным устройствам, подключенным к шине.

Английский эквивалент термина «шина» — «bus» — восходит к латинскому слову omnibus, означающему «для всего». Этим стремятся подчеркнуть, что шина ведет себя как магистраль, способная обеспечить всевозможные виды трафика.

Типы шинВажным критерием, определяющим характеристики шины, может служить ее це­левое назначение. По этому критерию можно выделить: шины «процессор-память»; шины ввода/вывода; системные шины.

Шина «процессор-память»обеспечивает непосредственную связь между централь­ным процессором (ЦП) вычислительной машины и основной памятью (ОП). В со­временных микропроцессорах такую шину часто называют шиной переднего плана и обозначают аббревиатурой FSB (Front-Side Bus). Интенсивный трафик между процессором и памятью требует, чтобы полоса пропускания шины, то есть количе­ство информации, проходящей по шине в единицу времени, была наибольшей. Роль этой шины иногда выполняет системная шина (см. ниже), однако в пла­не эффективности значительно выгоднее, если обмен между ЦП и ОП ведется по отдельной шине. К рассматриваемому виду можно отнести также шину, свя­зывающую процессор с кэш-памятью второго уровня, известную как шина зад­него плана — BSB (Back-Side Bus). BSB позволяет вести обмен с большей ско­ростью, чем FSB, и полностью реализовать возможности более скоростной кэш-памяти.

Поскольку в фон-неймановских машинах именно обмен между процессором и памятью во многом определяет быстродействие ВМ, разработчики уделяют свя­зи ЦП с памятью особое внимание. Для обеспечения максимальной пропускной способности шины «процессор-память» всегда проектируются с учетом особенно­стей организации системы памяти, а длина шины делается по возможности мини­мальной

Шина ввода/вывода служит для соединения процессора (памяти) с устройствами ввода/вывода (УВВ). Учитывая разнообразие таких устройств, шины ввода/вы­вода унифицируются и стандартизируются. Связи с большинством УВВ (но не с видеосистемами) не требуют от шины высокой пропускной способности. При проектировании шин ввода/вывода в учет берутся стоимость конструктивна и со­единительных разъемов. Такие шины содержат меньше линий по сравнению с ва­риантом «процессор-память», но длина линий может быть весьма большой. Ти­пичными примерами подобных шин могут служить шины PCI и SCSI.

Системная шинаС целью снижения стоимости некоторые ВМ имеют общую шину для памяти и устройств ввода/вывода. Такая шина часто называется системной. Системная шина служит для физического и логического объединения всех устройств ВМ. Поскольку основные устройства машины, как правило, размещаются на общей монтажной плате, системную шину часто называют объединительной шиной (backplane bus), хотя эти термины нельзя считать строго эквивалентными.

Системная шина в состоянии содержать несколько сотен линий. Совокупность линий шины можно подразделить на три функциональные группы (рис. 4.4): шину данных, шину адреса и шину управления. К последней обычно относят также ли­нии для подачи питающего напряжения на подключаемые к системной шине мо­дули.

Функционирование системной шины можно описать следующим образом. Если один из модулей хочет передать данные в другой, он должен выполнить два дей­ствия: получить в свое распоряжение шину и передать по ней данные. Если какой-то модуль хочет получить данные от другого модуля, он должен получить доступ к шине и с помощью соответствующих линий управления и адреса передать в другой модуль запрос. Далее он должен ожидать, пока модуль, получивший за­прос, пошлет данные.

Физически системная шина представляет собой совокупность параллельных электрических проводников. Этими проводниками служат металлические полос­ки на печатной плате. Шина подводится ко всем модулям, и каждый из них подсо­единяется ко всем или некоторым ее линиям. Если ВМ конструктивно выполнена на нескольких платах, то все линии шины выводятся на разъемы, которые затем объединяются проводниками на общем шасси.

3. На языке С++ вычислить сумму ряда целых чисел от 1 до n.

#pragma hdrstop

//---------------------------------------------------------------------------

#include <iostream.h>

void main()

{

int N,S=0,i;

cout<<"\n Vvedite N ==";

cin>>N;

for(i=1;i<=N;i++) S=S+i;

cout<<"\n Summa =="<<S;

}