Открыть главное меню

Изменения

Кандаминимум 010109 - ответы к экзамену по смежной специальности

94 925 байтов добавлено, 19:02, 24 ноября 2009
Нет описания правки
__FORCETOC__[[Изображение:СмежнаяСпециальность.mm|800px]]
== Понятие программного средства и его жизненный цикл. Понятие качества ПС, критерии качества ПС ==
Весьма важно также, что эти конструкции являются уже математическими объектами (что, по существу, и объясняет причину успеха структурного программирования). Доказано, что для каждой неструктурированной программы можно построить функционально эквивалентную (то есть решающую ту же задачу) структурированную программу. Для структурированных программ можно математически доказывать некоторые свойства, что позволяет обнаруживать в программе некоторые ошибки.
 
Структурное программирование иногда называют еще «программированием без GO TO». Однако дело здесь не в операторе GO TO, а в его беспорядочном использовании. Очень часто при воплощении структурного программирования на некоторых языках программирования (например, на ФОРТРАНе) оператор перехода (GO TO) используется для реализации структурных конструкций, не снижая основных достоинств структурного программирования. Запутывают программу как раз «неструктурные» операторы перехода, особенно переход на оператор, расположенный в тексте модуля выше (раньше) выполняемого оператора перехода. Тем не менее, попытка избежать оператора перехода в некоторых простых случаях может привести к слишком громоздким структурированным программам, что не улучшает их ясность и содержит опасность появления в тексте модуля дополнительных ошибок. Поэтому можно рекомендовать избегать употребления оператора перехода всюду, где это возможно, но не ценой ясности программы.
 
К полезным случаям использования оператора перехода можно отнести выход из цикла или процедуры по особому условию, «досрочно» прекращающего работу данного цикла или данной процедуры, то есть завершающего работу некоторой структурной единицы (обобщенного оператора) и тем самым лишь локально нарушающего структурированность программы. Большие трудности (и усложнение структуры) вызывает структурная реализация реакции на возникающие исключительные (часто ошибочные) ситуации, так как при этом требуется не только осуществить досрочный выход из структурной единицы, но и произвести необходимую обработку (исключение) этой ситуации (например, выдачу подходящей диагностической информации). Обработчик исключительной ситуации может находиться на любом уровне структуры программы, а обращение к нему может производиться с разных нижних уровней. Вполне приемлемой с технологической точки зрения является следующая «неструктурная» реализация реакции на исключительные ситуации. Обработчики исключительных ситуаций помещаются в конце той или иной структурной единицы и каждый такой обработчик программируется таким образом, что после окончания своей работы производит выход из той структурной единицы, в конце которой он помещен. Обращение к такому обработчику производится оператором перехода из данной структурной единицы (включая любую вложенную в нее структурную единицу).
=== Пошаговая детализация ===
В качестве основного метода построения текста модуля современная технология программирования рекомендует пошаговую детализацию. Сущность этого метода заключается в разбиении процесса разработки текста модуля на ряд шагов. На первом шаге описывается общая схема работы модуля в обозримой линейной текстовой форме (то есть с использованием очень крупных понятий), причем это описание не является полностью формализованным и ориентировано на восприятие его человеком. На каждом следующем шаге производится уточнение и детализация одного из понятий (будем называть его уточняемым), в каком либо описании, разработанном на одном из предыдущих шагов. В результате такого шага создается описание выбранного уточняемого понятия либо в терминах базового языка программирования (то есть выбранного для представления модуля), либо в такой же форме, что и на первом шаге с использованием новых уточняемых понятий. Этот процесс завершается, когда все уточняемые понятия будут уточнения (то есть в конечном счете будут выражены на базовом языке программирования). Последним шагом является получение текста модуля на базовом языке программирования путем замены всех вхождений уточняемых понятий заданными их описаниями и выражение всех вхождений конструкций структурного программирования средствами этого языка программирования.
Пошаговая детализация связана с использованием частично формализованного языка для представления указанных описаний, который получил название '''псевдокода'''. Этот язык позволяет использовать все конструкции структурного программирования, которые оформляются формализованно, вместе с неформальными фрагментами на естественном языке для представления обобщенных операторов и условий. В качестве обобщенных операторов и условий могут задаваться и соответствующие фрагменты на базовом языке программирования.
Головным описанием на псевдокоде можно считать внешнее оформление модуля на базовом языке программирования, которое должно содержать:
== Понятие операционной системы (ОС). Основные концепции современных ОС (Unix, Windows NT) ==
 
Осторожно! Не очень профессиональная лажа! Взято из методички для подготовки к гос.экзамену. Также см. [[rupedia:Операционная система]], местами там более вменяемо.
 
'''Операционная система (ОС)''' — одна из основных компонент вычислительной системы (аппаратура + специальное программное обеспечение), представляющая собой комплекс программ, обеспечи­вающий функционирование вычислительной системы в целом и рас­пределение ресурсов вычислительной системы между процессами — программами во время их выполнения на ЭВМ.
 
Ресурсы вычислительной системы делятся на физические ресурсы, то есть те ресурсы, которые связаны с аппаратурой (маг­нитные диски, оперативная память, время работы процессора) и ло­гические (иногда их называют виртуальными) ресурсы, то есть ре­сурсы, которые в виде реального оборудования не существуют, но реализуются в виде некоторых программных средств и услуг, пре­доставляемых пользователю.
 
Наиболее известными в настоящее время являются следую­щие ОС: MS DOS, Windows 95, Windows 98, Windows 2000, Windows NT, UNIX, QNX, Linux, Solaris, OS/2, MacOS.
 
ОС состоит из '''ядра''', специальных '''обслуживающих про­грамм''' и '''файловой системы'''.
 
'''Ядро ОС''' — программы, непосредственно обеспечивающие разделение вычислительных ресурсов и управление ими. Ядро обыч­но является резидентной частью ОС. Ядро работает в режиме ОС, или в привилегированном режиме.
 
В ядро входят базовые средства управления основными сущностями, характерными для данной ОС, а также может входить набор программ, обеспечивающих управление некоторыми физиче­скими устройствами. В функции ядра, в частности, входит обработка прерываний.
 
Программы, управляющие работой отдельных устройств вычислительной системы, называют драйверами устройств (физи­ческих или логических). Например, в ядро ОС должен входить драй­вер оперативного запоминающего устройства.
 
Специальные '''обслуживающие программы''' — программы управления ресурсами вычислительной системы, которые наращи­ваются вокруг ядра. Первый уровень в основном состоит из драйве­ров физических устройств. Следующий уровень — драйверы логиче­ских устройств. Таких уровней может быть достаточно много, и чем дальше от ядра, тем большая абстрактность присуща соответствую­щим программам.
 
'''Файловая система''' — компонент операционной системы, обеспечивающий организацию создания, хранения и доступа к име­нованным наборам данных — файлам.
 
По способам организации размещения файлов во внешнем запоминающем устройстве (ВЗУ) выделяются файловые системы с одноуровневой организацией файлов в виде непрерывных сегмен­тов, файловые системы с блочной организацией файлов и иерархи­ческие файловые системы.
 
При одноуровневой организации файлов в виде непре­рывных сегментов в пределах пространства ВЗУ выделяется неко­торая область для хранения данных, которая называется каталогом. Каталог имеет следующую структуру:
 
<tab sep=bar class=simpletable>
Имя | Начальный блок | Конечный блок
</tab>
«Начальный блок» ссылается на некоторый относительный адрес пространства ВЗУ, с которого начинается файл с заданным именем. «Конечный блок» определяет последний блок данного фай­ла. Функция открытия файла сводится к нахождению в каталоге име­ни файла и определении его начала и конца. Это действие очень простое. Если создается новый файл, то он записывается на свобод­ное место. Чтение происходит также достаточно просто. Проблемы возникают, когда в файл нужно записать дополнительную информа­цию, а свободного пространства за этим файлом нет. В этом случае система может запустить некий процесс, который перенесет этот файл в другое место памяти и добавит нужную информацию (а это достаточно сложно), а может просто отказаться произвести запись в файл. Кроме того, при долговременной работе такой файловой сис­темы на диске случается фрагментация (ситуация, когда есть сво­бодные фрагменты памяти, но среди них нет такого, куда можно было бы разместить файл). Борьба с фрагментацией также достаточ­но сложна и опасна для такой организации файловой системы, кото­рая практически пригодна лишь для однопользовательской операци­онной системы.
 
В файловой системе с блочной организацией файлов пространство ВЗУ разделено на блоки. В такой файловой системе распределение информации происходит аналогично распределению информации о процессе в системе со страничной организацией опе­ративной памяти. В общем случае, с каждым именем файла связан набор номеров блоков устройства, в которых размещены данные этого файла. Причем, номера этих блоков имеют произвольный порядок, то есть блоки могут быть разбросаны по всему устройству. При такой организации нет фрагментации, хотя могут быть потери из-за хранения информации порциями, кратными целому блоку.
 
В файловых системах с блочной организацией файлов с ка­ждым файлом связаны имя файла и имя пользователя (по ним про­исходит доступ к файлу). В таких системах требуется уникальность имен лишь среди файлов одного пользователя. При этом файлы объ­единены в каталоги с табличной структурой, где i-тая строка соот­ветствует i-тому блоку файловой системы (занятому или свободно­му). Если блок занят, то в соответствующей строке указывается имя файла (либо ссылка на него) и имя пользователя (а может быть и еще какая-то дополнительная информация).
 
Файловые системы с блочной организацией файлов могут быть многопользовательскими, а в рамках одного пользователя они являются одноуровневыми.
 
В иерархической файловой системе все файлы объедине­ны в структуру, которая называется деревом. В корне дерева нахо­дится корень файловой системы. Если узел дерева является листом, то это отдельный файл (либо файл-каталог в случае пустого катало­га). Узлы дерева, отличные от листа, являются файлами-каталогами. Именование файлов в такой иерархической файловой системе может происходить как относительно ближайшего каталога (на одном уровне имена не могут повторяться), так и с использованием полного имени файла, которое составляется из всех имен каталогов, которые находятся на пути от корня файловой системы к конкретному файлу. Полные имена файлов есть пути, а в дереве от корня до любого узла существует единственный путь, следовательно, нет проблем с уни­фикацией имен, то есть иерархическая структура файловой системы дос­таточно удобна для организации многопользовательской работы. Кроме того, такая система может очень просто наращиваться.
 
Основные функции ОС:
 
* управление использованием времени центрального процессора (или нескольких процессоров в много­процессорных системах),
* управление «подкачкой» и буфером ввода процес­сов,
* управление разделяемыми ресурсами (в частности, сетевым взаимодействием компьютеров),
* обработка прерываний,
* защита ресурсов и установка ограничений на ис­пользование ресурсов,
* вызов специальных обслуживающих программ, буферизация ввода/вывода.
 
=== Управление использованием времени центрального процессора ===
 
От того, какой алгоритм выбора процесса для передачи ему в распоряжение ЦП реализован в ОС, зависят многие реальные экс­плуатационные свойства ОС. Выбор алгоритма почти целиком опре­деляется теми критериями эффективности, которые используются для оценки эффективности работы ОС. Поэтому управление исполь­зованием времени ЦП можно рассмотреть на фоне различных типов ОС.
 
==== Пакетные ОС ====
 
Пусть есть некоторое количество счетных задач, они требуют большого объема вычислений и мало обращаются к внешним устройствам. Эти задачи должны выполняться в одной вычислительной системе. В такой ситуации критерием эффективности работы вычислительной системы является степень загрузки ЦП. Если он мало простаивает, то система работает эффективно. Этого можно добиться с использованием соответствующего алгоритма планирования, который заключается в следующем. Запускается некоторый набор задач в режиме мультипрограммирования. Алгоритм планирования времени ЦП в этом случае будет следующий: если ЦП выделен одному из процессов, то этот процесс будет занимать ЦП до наступления одной из следующих ситуаций:
 
* обращение к внешнему устройству.
* завершение процесса.
* зафиксированный факт зацикливания процесса.
 
Как только наступила одна из этих ситуаций, управление передается другому процессу. Количество передач управления от одного процесса к другому минимизировано. Такой режим работы ОС называется пакетным, а ОС, работающая в этом режиме, называ­ется '''пакетной ОС'''.
 
==== ОС разделения времени ====
 
Пусть значительное количество пользователей находится в компьютерном классе, и каждый из них редактирует некоторый текст. С каждым из терминалов связана своя копия текстового редактора. В такой ситуации для системы в качестве критерия эффективности подойдет время ожидания пользователя с момента, как он послал заказ на выполнение какого-то действия, до момента выполнения этого заказа. Чем эффективнее работает система, тем это среднестатистическое время ожидания в системе меньше. При этом алгоритм распределения времени центрального процессора может быть следующим.
 
В системе используется некоторый параметр Δt — квант вре­мени. Все множество процессов, которое находится в мультипро­граммной обработке, подразделяется на два подмножества. Первое подмножество составляют те процессы, которые еще не готовы к продолжению выполнения: например, те процессы, которые заказа­ли себе обмен и ждут его результатов. Второе подмножество — про­цессы, которые готовы к выполнению. Работа будет осуществляться следующим образом. Тот процесс, который в данный момент време­ни занимает ЦП, будет владеть им до наступления одного из сле­дующих событий:
 
* обращение с заказом на обмен,
* завершение процесса,
* исчерпание выделенного данному процессу кванта времени Δt.
 
При наступлении одного из этих событий планировщик ОС выбирает из процессов, готовых к выполнению, некоторый процесс и передает ему ресурсы ЦП. А выбирает он этот процесс в зависимо­сти от того алгоритма планирования, который реализован в данной конкретной ОС. Первый способ: процесс может выбираться случай­но. Второй способ: происходит как бы последовательный обход процессов, то есть сначала начинает работать один из процессов, затем (после наступления одного из указанных трех событий) время ЦП предоставляется следующему по порядку процессу из готовых к выполнению. Третьим критерием, по которому отбирается очеред­ная задача, может быть время, в течение которого данный процесс не обслуживался ЦП. В этом случае система может выбирать про­цесс, у которого такое время самое большое. Эти алгоритмы должны быть реализованы в ОС, а значит, они должны быть простыми, ина­че система будет работать неэффективно. ОС, работающие по опи­санному принципу, называются '''ОС разделения времени'''.
 
==== ОС реального времени ====
 
ОС реального времени используются в вычислитель­ных системах, ориентированных на решения задач, для которых главным, решающим требованием к вычислительной системе явля­ется время гарантированной реакции системы на возникновение того или иного события из набора заранее предопределенных событий (например, задачи, связанные с управлением действиями систем са­молета в режиме автопилота). Обычно ОС реального времени имеют свое специфическое устройство, и в них используются достаточно простые алгоритмы.
 
==== Смешанные ОС ====
 
Реально, большинство современных ОС являются сме­шанными системами, то есть у них присутствует в элементах планиро­вания использования ЦП как алгоритмы, позволяющие управлять счетными задачами, так и алгоритмы, позволяющие управлять инте­рактивными задачами либо задачами отладочными, для которых надо немного времени ЦП.
 
Примером такой организации планирования ЦП может быть следующая схема. Планировщик построен по двухуровневой схеме. Мы считаем, что множество задач может содержать, предпо­ложим, счетные задачи и интерактивные задачи. Первый уровень определяет приоритет между двумя классами задач и либо отдает ЦП сначала счетной задаче, либо интерактивной задаче. А второй уровень определяет то, о чем мы говорили перед этим, то есть как вы­брать задачу в пределах одного класса и как ее прервать. Такая сме­шанная система может работать следующим образом. Первый уро­вень планирования будет работать по такому принципу: если в дан­ный момент нет ни одной интерактивной задачи, готовой к выпол­нению (а это вполне реальная ситуация, если пользователи занима­ются редактированием текста), то ЦП передается счетным задачам, но добавляется одно условие: как только появляется хотя бы одна интерактивная задача, счетная задача прерывается и управление пе­редается блоку интерактивных задач. Это то, что касается первой функции управления процессами.
 
=== Управление подкачкой и буфером ввода. ===
 
Пусть большое количество людей сидит за компьютерами, и все одновременно запустили какие-то процессы. Вычислительная система не может принять для работы в мультипрограммном режиме все задачи — это слишком много. В этом случае образуется буфер ввода задач или буфер ввода процессов, то есть буфер, в котором аккумулируются те процессы, которые ожидают начала своей обра­ботки процессором. Возникает проблема очередности выбора про­цессов из этого буфера для начала обработки. Это задача планирова­ния буфера.
 
Задача планирования «подкачки» возникает тогда, когда процессор выполняет сразу несколько программ, и все они целиком не помещаются в оперативной памяти. В этом случае для продолже­ния вычислений время от времени может быть необходимо какие-то из обрабатываемых задач (или их фрагменты) откачивать на внеш­нее запоминающее устройство, а какие-то подкачивать в оператив­ную память.
 
Для решения задач планирования буфера ввода и «подкач­ки» также нужны алгоритмы планирования, но они не столь принци­пиальные, как при планировании времени ЦП.
 
В реальных системах часто совмещается буфер подкачки, то есть то пространство на внешних носителях, куда осуществляется откачка информации из оперативной памяти, и буфер ввода процес­сов.
 
Современные ОС часто осуществляют откачку не едини­цами блоков памяти процессов, а откачивается весь процесс. При этом возникают две проблемы: каков критерий замещения процесса и каков критерий выбора из буфера того процесса, который нам тре­буется ввести для мультипрограммной обработки. Самый простой вариант заключается в использовании времени нахождения процесса в том или ином состоянии. В первом случае, если решается вопрос об откачке процесса из числа обрабатываемых в область подкачки, то можно взять тот процесс, который дольше всего находится в со­стоянии обработки по астрономическому времени. Обратные дейст­вия могут быть симметричными, то есть можно брать из буфера ввода процессов тот процесс, который дольше всего там находится. Это простые и реальные алгоритмы планирования, и они могут видоиз­меняться в соответствии с критериями, выбираемыми по тем или иным соображениям. Например, один из критериев: все задачи де­лятся на две категории — задачи ОС (они рассматриваются в первую очередь, и среди них действует алгоритм оценки времени нахожде­ния их в конкретном месте) и все остальные задачи.
 
=== Управление разделяемыми ресурсами. ===
 
Пусть есть два процесса, которые работают на общем про­странстве оперативной памяти. При этом должны быть определен­ные средства, которые бы позволили синхронизовать доступ к раз­деляемой памяти, то есть создать условия, при которых обмен каж­дого из работающих процессов с общей оперативной памятью будет Происходить корректно. Это значит, что при каждом чтении инфор­мации из разделяемой памяти должно быть гарантировано, что все пользователи, которые начали писать что-то в эту память, уже этот процесс завершили — должна быть синхронизация по обмену с разде­ляемой памятью.
 
Кроме того, удобно, чтобы процессы, которые функциони­руют одновременно, могли взаимодействовать друг с другом. Для реализации этого во многих ОС имеются средства обмена сигналами между процессами, что является некоторой программной эмуляцией прерываний. Один процесс просит подать сигнал другому процессу. В другом процессе происходит прерывание его выполнения и пере­дача управления на некоторую предопределенную функцию, которая должна обработать полученный сигнал. Организация всех этих дей­ствий тоже входит в функции ОС.
 
=== Обработка прерываний. ===
 
В каждой вычислительной машине имеется предопределен­ный, заданный при разработке набор некоторых событий и аппарат­ных реакций на возникновение каждого из этих событий. Ситуация, возникающая при наступлении такого события и сопровождающаяся временным или окончательным прекращением выполнения последо­вательности команд одной программы и переходом к выполнению команд другой программы, называется прерыванием. Аппарат пре­рываний используется, например, для управления внешними устрой­ствами и для реализации возможности асинхронной работы с ними. Примером прерывания может служить прерывание по завершению обмена данными.
 
В момент возникновения прерывания действия аппаратуры вычислительной системы следующие:
 
* В некоторые специальные регистры аппаратно заносит­ся (сохраняется) информация о выполняемой в данный момент программе. Это минимальная информация, не­обходимая для начала обработки прерывания. Обычно в этот набор данных входит счетчик команд, регистр результата, указатель стека и несколько регистров об­щего назначения. Происходит так называемое малое «упрятывание».
* В специальный управляющий регистр, иногда называе­мым регистром прерываний, помещается код возник­шего прерывания.
* Запускается программа обработки прерываний, входя­щая в состав операционной системы. Эта программа производит анализ причины прерывания. Если преры­вание было фатальным (деление на ноль, например), то ОС прекращает выполнение программы, в которой воз­никло данное прерывание. Если же прерывание не фа­тальное, производится дополнительный анализ ситуа­ции и делается вывод о том, можно ли оперативно об­работать прерывание. Пример прерывания, которое всегда можно обработать оперативно — прерывание по таймеру. А прерывание, связанное, например, с прихо­дом информации по линии связи, нельзя обработать оперативно, так как предварительно надо подкачать про­грамму ОС, которая займется обработкой этого преры­вания. При этом сначала происходит полное «упряты­вание»: все регистры сохраняются в таблицах системы (а не в аппаратных регистрах, как раньше) и фиксиру­ется то, что некоторые фрагменты программы, находя­щиеся в оперативной памяти, могут быть перенесены (при необходимости) на внешнее устройство, а затем производится обработка прерывания и возврат из пре­рывания.
 
Можно выделить следующие пять основных типов прерыва­ний: внешние прерывания (при нажатии кнопки прерывания на пуль­те или при завершении интервала времени по сигналу таймера), прерывания при обращении к специальным функциям ОС, прерыва­ния от схем контроля ЭВМ (при каких-либо сбоях аппаратуры), пре­рывания по вводу-выводу и программные прерывания (например, при делении на ноль, при передаче сигналов между программами).
 
=== Защита ресурсов и установка ограничений на использо­вание ресурсов. ===
 
В вычислительной системе, работающей в режиме мульти­программирования, возникает проблема защиты памяти, то есть необхо­дим реализованный на аппаратном уровне механизм, обеспечиваю­щий защиту адресного пространства каждой из программ от несанк­ционированного доступа других программ.
 
Для вычислительных систем со страничной организацией памяти механизм защиты памяти может быть устроен, например, следующим образом: в таблице приписки, в которой отражено соот­ветствие между физической и виртуальной памятью, в строках, от­носящихся к страницам, не принадлежащим данной программе или еще не загруженным в оперативную память, находится код меньше нуля. При попытке обратиться к такой странице в системе возникает прерывание по защите памяти. Обрабатывая это прерывание, ОС про­веряет, действительно ли этой страницы памяти у данной програм­мы нет, и, если эта страница чужая, то ОС прекращает выполнение данного процесса с диагностикой обращения в чужую память. Если же какие то страницы еще не загружены в память, то ОС игнорирует прерывание, так как ошибки нет.
 
=== Персонификация пользователей ===
 
Современные многопользовательские ОС также решают за­дачу персонификации пользователей.
 
Персонификация — это возможность операционной системы идентифицировать конкретного пользователя и в соответствии с этим принимать те или иные действия, в частности, по защите дан­ных.
 
Персонификация пользователей может быть организована, например, иерархически (аналогично иерархическим файловым сис­темам). При этом существуют понятия «конкретный пользователь», «группа пользователей» и «все пользователи». Все пользователи де­лятся на группы, группы состоят из конкретных пользователей. Зная пользователя, группу, к которой он принадлежит, ОС имеет возмож­ность определить и контролировать разные права доступа к ресур­сам вычислительной системы для различных пользователей. Такая схема может быть многоуровневой (группы могут делиться на под­группы и т. д.) с соответственным распределением прав и возможно­стей.
 
=== Буферизация ввода/вывода ===
 
По аналогии со способами борьбы с разницей в скорости доступа к различным компонентам вычислительной системы опера­ционная система вводит в своих пределах программную буфериза­цию, которая также решает проблемы сглаживания времени доступа и проблемы синхронизации в целом. Сглаживание проблем, связан­ных с временем доступа, заключается в том, что практически каждая операционная система имеет КЭШ-буфера, которые аккумулируют обращения (образуют их очередь) к внешнему запоминающему уст­ройству (ВЗУ) аналогично аппаратной буферизации при работе с оперативной памятью. Это позволяет существенно оптимизировать операционную систему. Признаком наличия такой буферизации яв­ляется требование завершить выполнение операционной системы перед выключением машины. Степень этой буферизации определяет реальную эффективность системы.
== Принципы объектно-ориентированного программирования ==
Изменение реализации, вообще говоря, не влечет за собой изменение интерфейса.
=== Иерархия ===
'''Определение'''. Иерархия в ОО — это ранжированная или упорядоченная иерархия абстракций.
* Общедоступную (public) — видимую для всех
=== Полиморфизм ===
'''Определение'''. Полиморфизм — это способность операции (функции) с одним и тем же именем выполнять различные действия в зависимости от типа своих операндов.
Виртуальные функции являются примером полиморфных функций. Виртуальная функция может быть переопределена в производном классе, следовательно ее реализация зависит от всей последовательности методических описаний и наследственной иерархии. Какая именно из виртуальных функций будет вызвана — зависит от динамического типа объекта и определяется в момент обращения к виртуальной функции. Для этого используется таблица виртуальных функций, определенная для каждого класса.
=== Дополнительные возможности ОО языков ===
Некоторые языки позволяют определять несколько специальных методов класса:
== Основные понятия реляционной модели данных. Понятие о языке SQL ==
 
Также см. [[rupedia:Реляционная модель данных]], [[rupedia:Нормальная форма]], [[rupedia:SQL]].
 
В широком спектре автоматизированных информационных систем особо выделяются системы, предназначенные для поддержки удобного и долговременного хранения и обработки больших объемов информации, имеющей, как правило, достаточно сложную структуру. Для хранения такого рода информации на практике используются базы данных (БД), при этом под базой данных в общем случае понимается набор любых систематизированных данных, согласованных между собой. Обращение к базе данных и управление ею осуществляется с помощью системы управления базами данных (СУБД), которая представляет собой программную систему, ориентированную на поддержку хранения, манипулирования и управления данными, обеспечивая при этом их целостность и безопасность.
 
Способ организации информации в базе данных определяется конкретной моделью данных, положенной в основу построения этой базы. Модель данных описывает на концептуальном уровне связи между элементами хранимых данных и допустимые операции над ними, то есть задает логическую структуру данных и механизм их обработки. Так иерархическая модель базируется на организации данных в виде деревьев, сетевая использует в качестве основного способа представления данных графы и сети.
 
Реляционная модель является теоретической основой не только широко распространенных на сегодняшний день реляционных баз данных и соответствующих СУБД, но и всей области баз данных. Впервые принципы реляционной модели были изложены Е. Ф. Коддом в 1969-70 годах. Позднее в 70-х годах были получены основные теоретические результаты в этой области и появились первые прототипы реляционных СУБД. Наиболее бурное развитие области пришлось на 80-е годы, и это привело к тому, что уже к середине 80-х годов реляционные системы практически вытеснили с мирового рынка ранние СУБД и остаются до сих пор наиболее распространенными. Причиной такой популярности реляционных систем по сравнению с другими СУБД являются такие достоинства реляционного подхода к организации баз данных как:
 
* наличие небольшого набора абстракций, в терминах которых можно достаточно просто моделировать предметную область;
* использование в качестве теоретической основы подхода простого, но мощного математического аппарата на базе теории множеств и математической логики;
* возможность обрабатывать данные, абстрагируясь от физической организации баз данных во внешней памяти.
 
=== Основные термины ===
 
Реляционный подход к организации баз данных базируется на понятии отношения, и, собственно, само название подхода (а также соответствующих БД и СУБД) произошло от английского термина «relation» (отношение). Для удобства изложения рассмотрим в качестве примера отношение СТУДЕНТЫ, которое содержит информацию о студентах некоторого учебного заведения, и проиллюстрируем на нем основные понятия реляционной модели данных. К числу таких понятий относятся тип данных, домен, атрибут, кортеж, первичный ключ и отношение.
 
Понятие типа данных в реляционной модели данных аналогично соответствующему понятию в языках программирования. Обычно в современных реляционных БД используются символьные и числовые данные, битовые строки, а также специализированные числовые данные (например, «Деньги») и специальные данные для обозначения времени (дата, время, временной интервал). В приведенном примере допускается использование данных трех типов: целые числа, строки символов и «Деньги».
 
[[Image:Методичка-Реляционная-Алгебра-Иллюстрация.jpg|600px]]
 
Домен представляет собой именованное множество атомарных значений одного и того же типа. При этом под атомарным значением подразумевается значение, не имеющее внутренней структуры в реляционной модели, то есть значение, которое не может быть представлено в терминах более мелких понятий той же модели. Таким образом, атомарное значение является наименьшей семантической единицей данных в реляционной модели. Примером атомарного значения может служить любое отдельное данное из отношения СТУДЕНТЫ (конкретный номер группы, размер стипендии и т. д.).
 
Все домены в реляционной базе данных имеют уникальные имена, и каждый домен задает множество допустимых значений данного типа. Для определения домена указывается базовый тип данных элементов этого домена и некоторый предикат, с помощью которого формулируются возможные ограничения на значения элементов домена, то есть во многом понятие домена в базах данных аналогично понятию подтипа в языках программирования. Например, домен «Номера групп» определен на базовом типе целых чисел, и в качестве ограничения используется тот факт, что значения элементов домена (номера групп) должны принадлежать диапазону 101—530.
 
Основным назначением доменов с точки зрения семантики является то, что они ограничивают сравнения, то есть данные считаются сравнимыми только в том случае, когда они принадлежат одному и тому же домену. Так, в приведенном выше примере нельзя сравнивать между собой значения элементов доменов «Номера студенческих билетов» и «Номера групп», хотя и те и другие значения относятся к типу целых чисел.
 
С понятием домена тесно связано понятие атрибута. Атрибут способен принимать значения из некоторого домена, причем каждый атрибут должен быть определен на единственном домене. В рамках одного отношения все имена атрибутов должны быть уникальными, причем эти имена могут совпадать с именами соответствующих доменов (если все атрибуты отношения определены на разных доменах) или отличаться от них.
 
Именованное множество пар вида {имя атрибута, имя домена} называется схемой отношения. Мощность такого множества называется степенью или арностью отношения. Из свойств атрибутов отношения следует, что все входящие в данную схему имена атрибутов различны, и каждый атрибут соответствует единственному домену. Например, схема отношения СТУДЕНТЫ содержит четыре пары указанного вида, следовательно, степень этого отношения равна четырем, и данное отношение является 4-арным.
 
Кортеж, соответствующий некоторой схеме отношения, представляет собой множество пар вида {имя атрибута, значение}, причем это множество содержит по одной паре такого вида для каждого имени атрибута указанной схемы отношения, а в качестве значения может употребляться любое допустимое значение из домена данного атрибута. Для кортежа так же, как и для схемы отношения, определено понятие его степени или арности (количество входящих в кортеж пар), при этом из определения понятия кортежа следует, что арность кортежа всегда совпадает с арностью соответствующей схемы отношения.
 
Отношение представляет собой множество кортежей, соответствующих одной схеме отношения. Мощность этого множества называется кардинальным числом данного отношения. Часто схему отношения называют заголовком отношения, а само отношение как множество кортежей — телом отношения.
 
Общепризнанным неформальным представлением отношения является таблица некоторого специального вида. Эта таблица состоит из заголовка, в качестве которого используется схема отношения, и некоторого числа неповторяющихся строк, каждая из которых является кортежем отношения. Имена атрибутов при данном способе представления соответствуют именам столбцов таблицы. Примером такой таблицы может служить таблица, задающая отношение СТУДЕНТЫ.
 
=== Свойства отношений ===
 
Из приведенных определений вытекают следующие основные свойства отношений, существенно использующиеся в реляционной модели данных:
 
* отсутствие в отношении одинаковых кортежей;
* отсутствие упорядоченности кортежей;
* отсутствие упорядоченности атрибутов;
* атомарность значений атрибутов.
 
Первые два свойства являются следствием определения отношения как множества кортежей, так как множество по определению представляет собой неупорядоченный набор различных значений.
 
Тот факт, что все кортежи данного отношения различны, гарантирует наличие у каждого отношения первичного ключа, под которым подразумевается некоторый набор атрибутов, значения которых однозначным образом определяют кортеж отношения. Таким образом, доступ к конкретному кортежу отношения осуществляется по первичному ключу. Исходя из свойства уникальности кортежей, в качестве первичного ключа отношения всегда можно использовать полный набор атрибутов данного отношения, однако при формальном определении первичного ключа необходимо обеспечивать неизбыточность составляющего этот ключ набора атрибутов. Это означает, что такой набор атрибутов должен быть минимальным в том смысле, что он не должен содержать в себе атрибуты, которые можно отбросить, не нарушая основное свойство первичного ключа — однозначно определять кортеж. Так, первичным ключом отношения СТУДЕНТЫ является набор из одного единственного атрибута СТНОМЕР, поскольку значение именно этого атрибута однозначным образом определяет любой кортеж данного отношения.
 
Свойство отсутствия упорядоченности атрибутов вытекает из определения схемы отношения как множества пар заданного вида.
 
Если доступ к конкретному кортежу отношения осуществляется по первичному ключу, то доступ к значению какого-либо атрибута в кортеже всегда осуществляется по имени этого атрибута.
 
Свойство атомарности значений атрибутов является следствием определения домена как потенциального множества значений некоторого простого типа данных, не имеющего внутренней структуры в реляционной модели. Отношение, удовлетворяющее данному свойству, называется нормализованным или представленным в первой нормальной форме. В реляционной модели данных рассматриваются только нормализованные п-арные отношения, которые составляют основу классического реляционного подхода к организации баз данных. Несмотря на наличие некоторых ограничений, нормализованные отношения существенно упрощают обработку данных.
 
=== Реляционная модель данных ===
 
Реляционной моделью данных называется формальная теория, лежащая в основе реляционных систем. Фундамент этой теории составляют теория множеств и логика предикатов. Реляционная модель описывает некоторый набор основных понятий и признаков, которыми должны обладать все СУБД и управляемые ими базы данных, основывающиеся на этой модели. Реляционная модель рассматривает данные только на логическом уровне, что позволяет абстрагироваться от конкретного способа их реализации.
 
В реляционной модели выделяется три аспекта рассмотрения данных — структура данных, целостность данных и обработка данных, и в соответствии с этим модель делится на три части, каждая из которых рассматривает один из этих аспектов.
 
Часть реляционной модели, связанная со структурой данных, — структурная часть модели — фактически уже описана в предыдущих разделах. В структурной части модели декларируется, что единственной структурой данных, используемой в реляционных базах данных, является нормализованное n-арное отношение.
 
Рассмотрению аспекта целостности данных посвящена целостная часть реляционной модели. Здесь формулируются следующие два требования целостности, которые должны поддерживаться в любой реляционной СУБД:
 
* целостность сущностей;
* целостность по ссылкам.
 
Более подробно эта часть модели описана в следующем разделе.
 
Аспект обработки данных рассматривается в манипуляционной части реляционной модели. Здесь определяются два основных механизма манипулирования реляционными данными — реляционная алгебра и реляционное исчисление. Первый механизм базируется на классической теории множеств, а второй на логике исчисления предикатов первого порядка. Оба эти механизма обладают свойством замкнутости относительно понятия отношения, то есть выражения реляционной алгебры и формулы реляционного исчисления определяются над отношениями и результатом вычисления также являются отношения, что позволяет использовать результат в других выражениях и формулах.
 
Причиной включения указанных механизмов в реляционную модель является их большая выразительная мощность, что позволяет формулировать сложные запросы к базе данных в виде одного выражения реляционной алгебры или одной формулы реляционного исчисления. Основной функцией манипуляционной части реляционной модели является обеспечение меры реляционное™ любого конкретного языка реляционных баз данных. При этом язык называется реляционно полным, если он обладает не меньшей выразительностью и мощностью, чем реляционная алгебра или реляционное исчисление, то есть если любой запрос, выражаемый с помощью одного выражения реляционной алгебры или одной формулы реляционного исчисления, может быть выражен одним оператором этого языка.
 
Механизмы реляционной алгебры и реляционного исчисления эквивалентны, то есть для любого выражения реляционной алгебры можно построить эквивалентную (приводящую к тому же результату) формулу реляционного исчисления и наоборот. Отличаются эти механизмы способом интерпретации выражений и формул: выражения реляционной алгебры имеют строго определенную однозначную интерпретацию, тогда как для формул реляционного исчисления однозначная интерпретация, как правило, отсутствует. Это означает, что при формулировке запроса к базе данных в реляционной алгебре четко указывается способ получения результирующего отношения в виде последовательности выполнения реляционных операций. В случае же реляционного исчисления указываются только свойства результирующего отношения без уточнения способа его формирования. Поэтому реляционная алгебра лежит в основе процедурных языков обработки реляционных данных, а реляционное исчисление составляет основу непроцедурных или декларативных языков. Более подробно реляционная алгебра и реляционное исчисление описаны ниже.
 
=== Целостность данных ===
 
В реляционных базах данных любой объект или сущность реального мира представляется некоторыми кортежами отношений. Требование целостности сущностей заключается в том, что для всех отношений должно выполняться условие: любой кортеж отношения должен отличаться от любого другого кортежа этого же отношения или, другими словами, любое отношение должно обладать первичным ключом. Выполнение этого требования в реляционной модели данных обеспечивается основными свойствами отношений этой модели.
 
Ограничение первой нормальной формы, требующее атомарности значений атрибутов в отношениях, приводит к тому, что сложные сущности реального мира невозможно представить в виде кортежей одного какого-либо отношения, они представляются в реляционной базе данных в виде некоторых кортежей нескольких отношений.
 
Пусть, например, в реляционной базе данных требуется представить сущность ГРУППА с атрибутами ГРНОМЕР (номер группы), ГРКОЛ (количество студентов в группе) и ГРСТУД (множество студентов группы), причем для каждого студента необходимо также хранить СГНОМЕР (номер студенческого билета), СТИМЯ (фамилия студента), СТСТИП (размер стипендии студента). Тогда для соблюдения ограничения нормализованное отношение необходимо представить сущность ГРУППА в виде двух отношений: ГРУППЫ (ГР НОМЕР, ГРКОЛ) с первичным ключом ГР_НОМЕР и СТУДЕНТЫ (СТНОМЕР, СТИМЯ, СТ_СТИП, СТ_ГР_НОМ) с первичным ключом СТНОМЕР.
 
В данном представлении основное назначение атрибута СТГРНОМ состоит в том, чтобы иметь возможность восстанавливать полную сущность ГРУППА. При этом существенно, что значение атрибута СТГРНОМ в любом кортеже отношения СТУДЕНТЫ должно соответствовать значению атрибута ГРНОМЕР в некотором кортеже отношения ГРУППЫ, то есть по сути оба эти атрибута должны представлять одно и то же свойство сущности. Такой атрибут называется внешним ключом, поскольку его значения однозначно характеризуют сущности (задают значения их первичного ключа), представленные кортежами другого отношения. В этом случае говорят, что отношение, в котором определен внешний ключ, ссылается на отношение, в котором такой же атрибут является первичным ключом. В нашем примере отношение СТУДЕНТЫ ссылается на отношение ГРУППЫ.
 
Требование целостности по ссылкам или требование внешнего ключа заключается в том, что для каждого значения внешнего ключа, входящего в отношение, из которого осуществляется ссылка, должен найтись кортеж с таким же значением первичного ключа в отношении, на которое эта ссылка осуществляется, в противном случае значение внешнего ключа должно быть неопределенным. Для рассмотренного примера требование целостности по ссылкам означает, что при указании для какого-либо студента номера группы необходимо существование группы с таким номером.
 
Оба указанные требования целостности данных должны поддерживаться реляционными СУБД. Для поддержки требования целостности сущностей достаточно обеспечить уникальность первичного ключа в рамках любого отдельного отношения. Основные проблемы по обеспечению целостности по ссылкам возникают при выполнении удаления кортежа из отношения, на которое имеется ссылка. Эти проблемы могут быть решены одним из следующих способов. Первый способ заключается в запрете удаления кортежей, на которые имеются ссылки. Второй способ при удалении кортежа, на который имеются ссылки, приводит к автоматической замене внешнего ключа на неопределенное значение во всех кортежах, ссылающихся на удаленный кортеж. И, наконец, третий способ (каскадное удаление) заключается в том, что наряду с удалением кортежа, на который имеются ссылки, удаляются все ссылающиеся на него кортежи. Выбор конкретного способа обеспечения целостности по ссылкам во многом определяется спецификой прикладной области.
 
=== Реляционная алгебра ===
 
В реляционной алгебре средства обработки отношений базируются на теоретико-множественных операциях, состав которых расширен некоторыми дополнительными операциями, специфичными для баз данных. Набор основных алгебраических операций состоит из восьми операций, которые делятся на два класса — теоретико-множественные операции и специальные реляционные операции. К теоретико-множественным операциям набора относятся операции:
 
* объединения отношений,
* пересечения отношений,
* вычитания отношений,
* прямого произведения отношений.
 
Специальные реляционные операции включают операции:
 
* ограничения отношения,
* проекции отношения,
* соединения отношений,
* деления отношений.
 
Кроме того, в состав реляционной алгебры включены операция присваивания, которая позволяет сохранить в базе данных результаты вычисления алгебраических выражений, и операция переименования атрибутов, в результате которой тело отношения остается неизменным, но меняются имена атрибутов. Операция переименования атрибутов обеспечивает возможность корректно сформировать схему (заголовок) результирующего отношения при возникновении конфликтов именования атрибутов в отношениях, являющихся операндами одной реляционной операции.
 
Теоретико-множественные операции имеют традиционную в теории множеств интерпретацию, хотя и обладают некоторыми особенностями. Результатом объединения двух отношений является отношение, в состав которого входят все кортежи, входящие хотя бы в одно из отношений-операндов. Пересечение двух отношений дает в результате отношение, включающее в себя все кортежи, входящие одновременно в оба отношения-операнда. Результатом вычитания двух отношений является отношение, содержащее все кортежи отношения, указанного в качестве первого операнда, которые не входят в отношение-второй операнд. Прямое произведение двух отношений дает в результате отношение, кортежи которого представляют собой конкатенацию (сцепление) кортежей первого и второго операндов.
 
Особенностью операций объединения, пересечения и вычитания является то, что для их выполнения схемы (заголовки) отношений-операндов должны быть одинаковыми, то есть в заголовках этих отношений должен использоваться один и тот же набор имен атрибутов, причем одноименные атрибуты должны быть определены на одном и том же домене. Если заголовки отношений-операндов совпадают с точностью до имен атрибутов, то полную идентичность заголовков можно обеспечить за счет применения операции переименования атрибутов. Для выполнения операции прямого произведения необходимо напротив, чтобы множества имен атрибутов отношений-операндов не пересекались. Добиться этого можно также путем применения операции переименования атрибутов к одному из отношений.
 
Все указанные теоретико-множественные операции реляционной алгебры являются ассоциативными и (за исключением операции вычитания отношений) коммутативными, то есть:
 
(А ор В) ор С = А ор (В ор С),
 
А ор В = В ор А, где А, В, С — отношения, ор — теоретико-множественная операция.
 
Рассмотрим теперь специальные реляционные операции. Результатом ограничения отношения по некоторому условию является отношение, состоящее из кортежей отношения-операнда, удовлетворяющих данному условию. Проекция отношения на заданный набор его атрибутов дает в результате отношение, кортежи которого формируются путем взятия соответствующих значений из кортежей отношения-операнда. Результатом соединения двух отношений по некоторому условию является отношение, кортежи которого представляют собой конкатенацию кортежей первого и второго отношений и удовлетворяют заданному условию. Более точно в качестве результата операции соединения отношений А и В по условию сотр принимается отношение, полученное при применении операции ограничения по условию сотр прямого произведения отношений А и В.
 
Операция реляционного деления определена над бинарным и унарным отношениями. В результате деления получается унарное отношение, содержащее в качестве кортежей все значения первого атрибута кортежей бинарного отношения, для которых множество значений второго атрибута (при фиксированном значении первого атрибута) совпадает с множеством значений исходного унарного отношения. То есть результатом деления бинарного отношения А(а,Ь) на унарное отношение В(Ь) является унарное отношение С(а), состоящее из таких кортежей v, для которых в отношении А имеются кортежи <v, w> такие, что множество значений {w} совпадает с множеством значений атрибута b в отношении В.
 
Заметим, что к бинарному и унарному отношениям можно привести отношения большей арности за счет введения понятия составного атрибута. Пусть, например, заданы отношения А с заголовком {a<sub>1</sub>, a<sub>2</sub>, ..., a<sub>n</sub>, b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>m</sub>} и В с заголовком {b<sub>1</sub>, b<sub>2</sub>, ..., b<sub>m</sub>}, причем атрибут Ы отношения А и атрибут b<sub>i</sub> отношения В имеют одно и то же имя и определены на одном и том же домене. Тогда множество атрибутов {aj} называется составным атрибутом а и, соответственно, множество атрибутов {b<sub>j</sub>} - составным атрибутом b. После этого можно говорить о реляционном делении бинарного отношения А(а,b) на унарное отношение В(Ь).
 
=== Реляционное исчисление ===
 
В основе реляционного исчисления лежит формальная теория исчисления предикатов первого порядка. Базисными понятиями реляционного исчисления являются понятие переменной с определенной для нее областью допустимых значений (область определения переменной) и понятие правильно построенной формулы, обеспечивающее формирование формул на основе литералов, переменных, предикатов и кванторов. В зависимости от того, что представляет собой область определения переменной, подразделяется два вида реляционного исчисления — исчисление кортежей и исчисление доменов. В исчислении кортежей переменные определены на отношениях базы данных, то есть допустимым значением каждой такой переменной является кортеж некоторого отношения. В исчислении доменов областями определения переменных служат домены, на которых определены атрибуты отношений базы данных, и допустимым значением любой такой переменной является значение элемента из некоторого домена.
 
Рассмотрим более подробно исчисление кортежей. Переменной этого исчисления является кортежная переменная, определяемая с помощью оператора RANGE, который указывает, кортежи какого отношения представляет данная переменная. Доступ к атрибутам кортежной переменной осуществляется по указанию имени переменной и имени атрибута. Для выражения условий, накладываемых на кортежные переменные, используются правильно построенные формулы (WFF — Well-Formed Formula). WFF строятся на базе простых сравнений (сравнений атомарных значений) с помощью логических связок NOT, AND, OR, конструкции IF … THEN и кванторов EXIST и FORALL.
 
Так же, как в исчислении предикатов в исчислении кортежей определяется понятие свободного и связанного вхождения переменной, при этом связывание вхождения переменной производится кванторами. Связанное вхождение ограничивает область видимости соответствующей переменной пределами ближайшей объемлющей WFF, связавшей данную переменную.
Для определения набора и имен атрибутов результирующего отношения в исчислении кортежей используется понятие целевого списка. Элементом целевого списка в общем случае является конструкция вида var.attr, где var — имя свободной переменной, attr -имя атрибута отношения, на котором определена переменная var. Если имя переменной в целевом списке указано без имени атрибута, то в целевой список включаются имена всех атрибутов определяющего отношения. При формировании целевого списка необходимо обеспечивать уникальность имен атрибутов результирующего отношения, для этого любое повторное вхождение имени атрибута в целевой список должно быть заменено новым именем.
 
Выражением исчисления кортежей называется конструкция вида tl WHERE wff. Значением этого выражения является отношение, тело которого определяется указанной в данном выражении WFF, а набор атрибутов и их имена — целевым списком tl.
 
В исчислении доменов областью определения переменных являются домены. Правила построения формул и выражений исчисления доменов аналогичны соответствующим правилам исчисления кортежей. Основным отличием является наличие в исчислении доменов дополнительного набора предикатов, с помощью которого выражается условие членства или условие принадлежности. Для n-арного отношения R это условие имеет вид:
 
R (pair<sub>1</sub>,…, pair<sub>m</sub>) (m <= n),
 
где каждая пара pair; задается конструкцией A:v, в которой А -имя атрибута отношения R, v — либо литерал, либо имя переменной домена. Условие членства принимает значение true тогда и только тогда, когда в отношении R существует кортеж, содержащий заданные значения указанных в нем атрибутов.
 
Литература:
 
* К. Дейт. Введение в системы баз данных. −6-е издание. Издательский дом «Вильяме», 1999.
* С. Д. Кузнецов. Основы современных баз данных. Информационно-аналитические материалы Центра Информационных Технологий: [http://citforum.ru/database/osbd/contents.shtml http://citforum.ru/database/osbd/contents.shtml]
== Экспертные системы: архитектура, типы решаемых задач, области применения ==
Параллельная обработка. Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени. Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени.
Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят - — ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени - — ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).
Казалось бы, конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, пять устройств предыдущего примера обработают 100 пар аргументов за 100 единиц времени, что быстрее времени работы конвейерного устройства! В чем же дело? Ответ прост, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость.
Cамой ранней и наиболее известной является классификация архитектур вычислительных систем, предложенная в 1966 году М.Флинном. Классификация базируется на понятии потока, под которым понимается последовательность элементов, команд или данных, обрабатываемая процессором. На основе числа потоков команд и потоков данных Флинн выделяет четыре класса архитектур: SISD, MISD, SIMD, MIMD.
* SISD (single instruction stream / single data stream) - — одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины, или иначе, машины фон-неймановского типа, например, PDP-11 или VAX 11/780. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка - — как машина CDC 6600 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными попадают в этот класс.* SIMD (single instruction stream / multiple data stream) - — одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - — элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производиться либо процессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, например, в машине CRAY-1.* MISD (multiple instruction stream / single data stream) - — множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных. Однако ни Флинн, ни другие специалисты в области архитектуры компьютеров до сих пор не смогли представить убедительный пример реально существующей вычислительной системы, построенной на данном принципе.* MIMD (multiple instruction stream / multiple data stream) - — множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных.
Предложенная схема классификации вплоть до настоящего времени является самой применяемой при начальной характеристике того или иного компьютера. Если говорится, что компьютер принадлежит классу SIMD или MIMD, то сразу становится понятным базовый принцип его работы, и в некоторых случаях этого бывает достаточно. Однако видны и явные недостатки. В частности, некоторые заслуживающие внимания архитектуры, например dataflow и векторно-конвейерные машины, четко не вписываются в данную классификацию. Другой недостаток - — это чрезмерная заполненность класса MIMD. Необходимо средство, более избирательно систематизирующее архитектуры, которые по Флинну попадают в один класс, но совершенно различны по числу процессоров, природе и топологии связи между ними, по способу организации памяти и, конечно же, по технологии программирования.
=== Массивно-параллельные системы (MPP) ===
* локальную память (прямой доступ к памяти других узлов невозможен),
* коммуникационный процессор или сетевой адаптер
* иногда - — жесткие диски (как в SP) и/или другие устройства В/В
К системе могут быть добавлены специальные узлы ввода-вывода и управляющие узлы. Узлы связаны через некоторую коммуникационную среду (высокоскоростная сеть, коммутатор и т.п.)
Общее число процессоров в реальных системах достигает нескольких тысяч (ASCI Red, Blue Mountain).
* На каждом узле работает полноценная UNIX-подобная ОС (вариант, близкий к кластерному подходу). Пример: IBM RS/6000 SP + ОС AIX, устанавливаемая отдельно на каждом узле.
Программирование в рамках модели передачи сообщений ( MPI, PVM, BSPlib)
Примеры: IBM RS/6000 SP2, Intel PARAGON/ASCI Red, SGI/CRAY T3E, Hitachi SR8000, транспьютерные системы Parsytec.
Система состоит из нескольких однородных процессоров и массива общей памяти (обычно из нескольких независимых блоков). Все процессоры имеют доступ к любой точке памяти с одинаковой скоростью. Процессоры подключены к памяти либо с помощью общей шины (базовые 2-4 процессорные SMP-сервера), либо с помощью crossbar-коммутатора (HP 9000). Аппаратно поддерживается когерентность кэшей.
Наличие общей памяти сильно упрощает взаимодействие процессоров между собой, однако накладывает сильные ограничения на их число - — не более 32 в реальных системах. Для построения масштабируемых систем на базе SMP используются кластерные или NUMA-архитектуры.
Вся система работает под управлением единой ОС (обычно UNIX-подобной, но для Intel-платформ поддерживается Windows NT). ОС автоматически (в процессе работы) распределяет процессы/нити по процессорам (scheduling), но иногда возможна и явная привязка.
=== Системы с неоднородным доступом к памяти (NUMA) ===
Система состоит из однородных базовых модулей (плат), состоящих из небольшого числа процессоров и блока памяти. Модули объединены с помощью высокоскоростного коммутатора. Поддерживается единое адресное пространство, аппаратно поддерживается доступ к удаленной памяти, т.е. то есть к памяти других модулей. При этом доступ к локальной памяти в несколько раз быстрее, чем к удаленной. В случае, если аппаратно поддерживается когерентность кэшей во всей системе (обычно это так), говорят об архитектуре cc-NUMA (cache-coherent NUMA)
Масштабируемость NUMA-систем ограничивается объемом адресного пространства, возможностями аппаратуры поддежки когерентности кэшей и возможностями операционной системы по управлению большим числом процессоров. На настоящий момент, максимальное число процессоров в NUMA-системах составляет 256 (Origin2000).
Обычно вся система работает под управлением единой ОС, как в SMP. Но возможны также варианты динамического "подразделения" «подразделения» системы, когда отдельные "разделы" «разделы» системы работают под управлением разных ОС (например, Windows NT и UNIX в NUMA-Q 2000).
Программирование аналогично SMP.
Узлы кластера могут одновременно использоваться в качестве пользовательских рабочих станций. В случае, когда это не нужно, узлы могут быть существенно облегчены и/или установлены в стойку.
Используются стандартные для рабочих станций ОС, чаще всего, свободно распространяемые - — Linux/FreeBSD, вместе со специальными средствами поддержки параллельного программирования и распределения нагрузки.
Программирование, как правило, в рамках модели передачи сообщений (чаще всего - — MPI). Дешевизна подобных систем оборачивается большими накладными расходами на взаимодействие параллельных процессов между собой, что сильно сужает потенциальный класс решаемых задач.
Примеры: NT-кластер в NCSA, Beowulf-кластеры.
IBM 709 (1958): независимые процессоры ввода/вывода.
Процессоры первых компьютеров сами управляли вводом/выводом. Однако скорость работы самого быстрого внешнего устройства, а по тем временам это магнитная лента, была в 1000 раз меньше скорости процессора, поэтому во время операций ввода/вывода процессор фактически простаивал. В 1958г1958 г. к компьютеру IBM 704 присоединили 6 независимых процессоров ввода/вывода, которые после получения команд могли работать параллельно с основным процессором, а сам компьютер переименовали в IBM 709. Данная модель получилась удивительно удачной, так как вместе с модификациями было продано около 400 экземпляров, причем последний был выключен в 1975 году - — 20 лет существования!
IBM STRETCH (1961): опережающий просмотр вперед, расслоение памяти.
CDC 6600 (1964): независимые функциональные устройства.
Фирма Control Data Corporation (CDC) при непосредственном участии одного из ее основателей, Сеймура Р.Крэя (Seymour R.Cray) выпускает компьютер CDC-6600 - — первый компьютер, в котором использовалось несколько независимых функциональных устройств.
CDC 7600 (1969): конвейерные независимые функциональные устройства.
CDC выпускает компьютер CDC-7600 с восемью независимыми конвейерными функциональными устройствами - — сочетание параллельной и конвейерной обработки.
ILLIAC IV (1974): матричные процессоры.
CRAY 1 (1976): векторно-конвейерные процессоры
В 1972 году С.Крэй покидает CDC и основывает свою компанию Cray Research, которая в 1976г1976 г. выпускает первый векторно-конвейерный компьютер CRAY-1: время такта 12.5нс, 12 конвейерных функциональных устройств, пиковая производительность 160 миллионов операций в секунду, оперативная память до 1Мслова (слово - — 64 разряда), цикл памяти 50нс. Главным новшеством является введение векторных команд, работающих с целыми массивами независимых данных и позволяющих эффективно использовать конвейерные функциональные устройства.
=== Конвейерность и параллелизм ===
Выполнение типичной команды можно разделить на следующие этапы:
* выборка команды - — IF (по адресу, заданному счетчиком команд, из памяти* извлекается команда);* декодирование команды / выборка операндов из регистров - — ID;* выполнение операции / вычисление эффективного адреса памяти - — EX;* обращение к памяти - — MEM;* запоминание результата - — WB.
Чтобы конвейеризовать эту схему, мы можем просто разбить выполнение команд на указанные выше этапы, отведя для выполнения каждого этапа один такт синхронизации, и начинать в каждом такте выполнение новой команды.
== Технология работы в сети Интернет (браузеры, способы описания сайтов) ==
См. также [[rupedia:Список браузеров]]. == Литература (из списка вопросов) == * Кауфман В. Ш. Языки программирования. Концепции и принципы. М.: Радио и связь, 1993.* Жоголев Е. А. Лекции по технологии программирования. -*: http://sp.cs.msu.su в разделе «Информация».* Машечкин И. В., Петровский М. И., Скулачев П. Д., Терехин А. Н. Системное Программное Обеспечение: файловые системы ОС Unix и Windows NT (конспект лекций). — М.: Диалог-МГУ, 1997.* Робачевский А. Операционная система UNIX. — СПб: BHV — Санкт-Петербург, 1997.* Дейт К.Дж. Введение в системы баз данных. — М. *Киев: Диалектика, 1998.* Интеллектуализация ЭВМ. — М.: Высшая школа, 1989.* Смирнов А. Д. Архитектура вычислительных систем. — М.: Наука, 1990.* Нильсен М. Знакомьтесь: World Wide Web. — Киев: BHV, 1996. Утверждено на Совете факультета ВМиК МГУ 29 марта 2000 г. == Источники сборки статьи == * Замок Дракона (без башни). Например, «Лекция 8 — Разработка программного модуля» — [http://ergeal.ru/txt/archive/cs/tp/08.htm http://ergeal.ru/txt/archive/cs/tp/08.htm].* [[Файл:Компиляция-ASP-Спецчасть-старая.doc|Некая «Спецчасть-старая.doc», найденная на просторах сети]].* [[esyrwiki:Языки программирования, 05 лекция (от 19 сентября)]] и последующие.* Методические материалы для подготовки к государственному экзамену по прикладной математике и информатике (по программе специалистов). А. В. Боресков, И. А. Волкова, И. В. Дмитриева, Г. П. Иванова, Е. А. Кузьменкова, С. И. Орлик, Д. С. Романов. Москва, Планета Знаний, 2007. [[Категория:УчёбаКандаминимум]]