Параллельный сумматор. Принцип работы, функциональная схема.

Дешифратор. Принцип работы.

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

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

Работа в любом заданном разряде при сложении кодов сводится к сложению трех одноразрядных двоичных чисел. Устройство, которое выполняет такую работу, называется сумматором .

Построение функциональной схемы сумматора начнем с построения таблицы истинности. Суммируемые разряды обозначим буквами A и B, значение переноса из младшего разряда - P, младшую цифру результата суммирования - Res, а значение переноса в старший разряд - Tran. Таблица истинности будет выглядеть следующим образом:

A B P Res Tran

0 0 1 0 0

0 0 1

1

0

0 1 0

1

0

0 1 1 0

1

1 0 0

1

0

1 0 1 0

1

1 1 0 0

1

1 1 1

1

1

Сначала будем строить функцию Res. Выделим строки таблицы, имеющие в колонке Res значение 1 (вторая, третья, пятая и восьмая).

Составим для каждой строки истинное логическое выражение с учетом значений A,B и P. Будем иметь

Логически сложим выражения X1,X2,X3,X4 . Получим следующее

. (33)

Упростим (33) на основе логических законов с использованием операции XOR

. (34)

Выражению (34) соответствует схема, изображенная на рисунке 19.

Рисунок 19. Функциональная схема логической функции Res(A,B,P)

Для построения функции Tran воспользуемся четвертой, шестой, седьмой и восьмой строками таблицы истинности.

(35)

Сокращая (35), получим

. (36)

Функциональную схему функции Tran можно представить следующим образом.

Рисунок 20. Функциональная схема Tran(A,B,P)

Теперь мы с вами готовы изобразить функциональную схему двоичного одноразрядного сумматора. Для этого объединим функциональные схемы Res(A,B,P) и Tran(A,B,P).

Рисунок 21. Функциональная схема двоичного одноразрядного сумматора

2)Обычно в ЭВМ используют обработку данных параллельно по разрядам. Для такой обработки используются параллельные сумматоры.

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

Пример построения многоразрядного сумматора представлен на рис. 4.5.

Рис.4.5. Схема параллельного сумматора

Сумматор имеет 2n входных разрядных линий ai и bi для приема цифр слагаемых, n выходных линий Sn разрядов суммы, выход переноса Рn из старшего разряда и вход переноса р0 на младший разряд сумматора.

На функциональных схемах многоразрядные функциональные узлы обозначаются в виде прямоугольников с тремя полями (рис.4.6).

Рис. 4.6. Параллельный сумматор

В основном поле обозначается функциональное назначение схемы. Для сумматора это SM,СМ,å.

Боковые поля предназначены для обозначения данных: правое поле для входных данных, левое – для выходных. Боковые поля могут иметь секции для разделения разноименных входных или выходных данных.

3)дешифратор (или декодер) – это логическое комбинационное устройство, служащее для преобразования двойного двоичного кода в сигнал управления в десятичной системе исчисления на одном из выходов.

Обычно дешифратор имеет n-входов и 2n выходов, при этом n — разрядность дешифрируемого кода. Определенной комбинации на входе соответствует активный сигнал на одном из выходов, или при сигнале «00» — мы имеем «1» на нулевом выходе схемы; при «01» имеем — «1» на первом выходе, сигнал «10» трансформируется в 1 – на втором выходе и т.д. Другими словами, эти элементы схем могут преобразовывать двоичный код в различные системы исчисления (это может быть десятичная, шестнадцатеричная и пр.), поскольку все зависит от конкретной задачи, выполняемой микросхемой.

В стандартные типы дешифраторов входят модели на 4, 8 и 16 выходов, при этом на выходе — 2, 3 и 4 разрядов входного кода. Входы дешифраторов называют часто адресными, и на схемах нумеруют 1,2,4,8, при этом цифра соответствует весу двоичного кода. Сигнал на выходе 1,2,4,8 устанавливает номер активного выхода. С1,С2 – входы разрешения (или стробирования), которые работают с условием «и». Сигнал на этом входе сообщает о моменте срабатывания дешифратора. Также их можно использовать для увеличения разрядности логических устройств.

16

1. Мультиплексор. Принцип работы. Назначение.

Мультиплексор представляет собой комбинированное цифровое устройство, обеспечивающее поочередную передачу на один выход нескольких входных сигналов. Он позволяет передавать (коммутировать) сигнал с желаемого входа на выход, в этом случае выбор требующегося входа реализуется определенной комбинацией управляющих сигналов. Число мультиплексных входов принято называть количеством каналов, их может быть от 2 до 16, а число выходов называют разрядами мультиплексора, обычно это 1 — 4.

Мультиплексоры по способу передачи сигналы различают на:

— аналоговые;

— цифровые.

Так, аналоговые устройства при помощи непосредственного электрического соединения подключают вход к выходу, в таком случае его сопротивление составляет порядка нескольких единиц – десятков Ом. Их поэтому называют коммутаторами или ключами. Цифровые (дискретные) же устройства не имеют прямой электрической связи входа и выхода, они только копируют на выход сигнал – «0» или «1».

В общем виде принцип действия мультиплексора можно объяснить на примере коммутатора, обеспечивающего соединение входов с выходом устройства. Работа коммутатора обеспечивается на основе управляющей схемы, в которой существуют адресные и разрешающие входы. Сигналы с адресных входов указывают, какой именно информационный канал соединен с выходом. Разрешающие входы применяют для увеличения возможностей – увеличения разрядности, синхронизации с протеканием работы прочих механизмов и пр. Для создания управляющей схемы мультиплексора обычно используют дешифратор адреса.

2. Демультиплексор. Принцип работы. Назначениe

Демультиплексором называют устройство, в котором сигналы с одного информационного входа, поступают в желаемой последовательности по нескольким выходам в зависимости от кода на адресных шинах. Таким образом, демультиплексор в функциональном отношении противоположен мультиплексору. Демультиплексоры обозначают через DMX или DMS.

Если соотношение между числом выходов n и числом адресных входов m определяется равенством n= 2m, то такой демультиплексор называется полным, при n< 2m демультиплексор является неполным.

Принцип работы демультиплексора поясним с помощью схемы на рисунке, на котором обозначено: Х – информационный вход, А – вход адреса, YО, Y1 – выходы. Схема содержит два элемента И и один элемент НЕ.

3. Поясните,почему у RS-триггера существует запрещенная комбинация

входных сигналов.

Сущность запрещенного состояния вытекает из принципа работы RS-триггера. С приходом активного сигнала на вход или, на прямом входе установиться напряжение высокого уровня, на инверсном, соответственно, низкого. На втором входе при этом должен быть нейтральный сигнал. В новое состояние триггер переходит скачком благодаря положительной перекрёстной обратной связи между элементами. Если после переключения триггера активный сигнал на входе станет нейтральным, триггер сохранит новое состояние, в котором он будет удерживаться действием той же обратной связи. Повторные импульсы на входеS ник

переключение: на прямом выходе появиться низкое напряжение, а на инверсном – высокое. Появление активных сигналов одновременно на обоих входах приводит к тому, что на обоих выходах будут напряжения одинакового уровня. Такое сочетание входных сигналов и называют запрещенным состоянием и в условиях нормальной работы его избегают. Такая комбинация входных сигналов неприемлема по двум причинам: не выполняется условие взаимной инверсности входов и после снятия входных сигналов триггер с равной вероятностью может перейти в состояние, при котором на прямом выходе 1, или в состояние, при котором на прямом выходе 0. Противоречивая команда R=S=1 не запоминается триггерной ячейкой.

17

1. Алгори́тм — набор инструкций, описывающих порядок действий исполнителя для достижения некоторого результата.

Различают следующие виды алгоритмов:

линейный – список команд (указаний), выполняемых последовательно друг за другом;

разветвляющийся – алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения;

циклический – алгоритм, предусматривающий многократное повторение одной и той же последовательности действий. Количество повторений обусловливается исходными данными или условием задачи.

Любая алгоритмическая конструкция может содержать в себе другую конструкцию того же или иного вида, т. е. алгоритмические конструкции могут быть вложенными.

Рассмотрим свойства алгоритма.

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

Определенность (детерминированность). Это свойство означает, что неоднозначность толкования записи алгоритма недопустима, многократное применение алгоритма к одним и тем же исходным данным должно приводить к одним результатам.

Результативность. Алгоритм обязательно должен приводить к определенному результату за конечное число шагов и обеспечивать его выдачу на устройство вывода информации (экран монитора, принтер) или в файл. Для этого в алгоритме должно быть предусмотрено исключение недопустимых ситуаций (деление на ноль, вычисление логарифма нуля или отрицательного числа и т. п.). Если решение задачи не существует, то в качестве результата может быть выведено сообщение об этом.

Массовость. Обычно алгоритмы предназначены для решения не одной конкретной задачи, а некоторого класса задач данного типа. В простейшем случае массовость подразумевает возможность использования различных исходных данных.

Формальность. Эта особенность указывает на то, что любой исполнитель, способный воспринимать и выполнять инструкции алгоритма, действует формально, т. е. отвлекается от содержания поставленной задачи, не вникает в ее смысл, а лишь строго выполняет инструкции.

Эффективность. Это свойство, которое позволяет решить задачу за приемлемое время.

Существуют различные способы описания алгоритмов:

словесный (пошаговое описание);

табличный и в виде формул;

графический (в виде схем);

с использованием псевдокода (алгоритмического языка).

Блок-схема алгоритма — графическое изображение алгоритма в виде связанных между собой с помощью стрелок (линий перехода) и блоков — графических символов, каждый из которых соответствует одному шагу алгоритма. Внутри блока дается описание соответствующего действия.

В таблице приведены наиболее часто употребляемые символы.

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

18

1)Цикл — разновидность управляющей конструкции в высокоуровневых языках программирования, предназначенная для организации многократного исполнения набора инструкций.

Цикл с предусловием — цикл, который выполняется, пока истинно некоторое условие, указанное перед его началом. Это условие проверяется до выполнения тела цикла, поэтому тело может быть не выполнено ни разу (если условие с самого начала ложно). В большинстве процедурных языков программирования реализуется оператором while, отсюда его второе название — while-цикл.

Цикл с постусловием — цикл, в котором условие проверяется после выполнения тела цикла. Отсюда следует, что тело всегда выполняется хотя бы один раз.

Циклы нужны для экономии памяти отводимой под программные инструкции при необходимости повторять одни и те же действия много раз. Например: надо заполнить подряд идущие 1000 ячеек памяти. Можно написать тысячу команд, которые будут записывать каждая в свою ячейку, а можно организовать цикл и команд потребуется на три порядка меньше. Есть алгоритмы в которых неизвестно заранее сколько раз придется повторить действие. Например: вычисление длины символьной строки, которая заканчивается нулем. Но иногда, в специфических случаях, для выигрыша в скорости выполнения, циклы наоборот "разворачивают" - избавляются от затрат времени на ведение счетчика и на команду перехода в начало цикла.

2)Алгоритмом называют систему четких однозначных указаний, которые определяют последовательность действий над некоторыми объектами и после конечного числа шагов приводят к получению требуемого результата.

Рекурсивный алгоритм – это алгоритм, решающий задачу путем сведения ее к решению одной или нескольких таких же задач, но в сокращенном их варианте. 3)Типы данных:

а) простые: - целые (integer и др) - логические (Boolean) - символьные (char) - перечисляемые - интервальные - вещественные (REAL и др) - строчные (String) б) структурированные: Массивы представляют собой формальное объединение нескольких однотипных объектов (чисел, символов, строк и т.п.), рассматриваемое как единое целое. Все компоненты массива – это данные одного типа.

Общий вид определения массива:

Type A = array [тип индекса массива] of [тип компонент массива]

Например, М1=array [1..100] of real;

Строки – это массив символов, но количество символов в строке может меняться. Строка трактуется как цепочка символов произвольной длины. Максимальное количество символов не более 255. Каждый символ в строке имеет свой индекс (номер).

Line = string[80];

Запись – это структура данных, состоящая из фиксированного числа компонентов, называемых полями записи. В отличие от массива, компоненты записи (поля) могут быть различного типа. Записи позволяют объединять значения различных типов.

Date = record

Month : (Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sept, Oct, Nov, Dec);

Day : 1..31;

Year : 2000..2050;

End;

Множества – это наборы однотипных, логически связанных друг с другом объектов. Количество элементов, входящих в множество может меняться от 0 до 256. Именно непостоянством своих элементов множества отличаются от массивов и записей.

Digits = Set of 1..5;

Файл – именованная область внешней памяти. Файл содержит компоненты одного типа, кроме файлов ( т.е. нельзя создать «файл файлов»). Длина файла не оговаривается и ограничивается только ёмкостью устройств внешней памяти.

F : File of Integer;

19

1. Понятие интерпретатора и компилятора

Компилятор — это обслуживающая программа, выполняющая трансляцию на машинный язык программы, записанной на исходном языке программирования. Компилятор обеспечивает преобразование программы с одного языка на другой (чаще всего, в язык конкретного компьютера) .Вместе с тем, команды исходного языка значительно отличаются по организации и мощности от команд машинного языка. Существуют языки, в которых одна команда исходного языка транслируется в 7-10 машинных команд. Однако есть и такие языки, в которых каждой команде может соответствовать 100 и более машинных команд

Интерпретатор - программа или устройство, осуществляющее пооператорную трансляцию и выполнение исходной программы. В отличие от компилятора, интерпретатор не порождает на выходе программу на машинном языке. Распознав команду исходного языка, он тут же выполняет ее. Как в компиляторах, так и в интерпретаторах используются одинаковые методы анализа исходного текста программы. Но интерпретатор позволяет начать обработку данных после написания даже одной команды. Это делает процесс разработки и отладки программ более гибким. Кроме того, отсутствие выходного машинного кода позволяет не «захламлять» внешние устройства дополнительными файлами, а сам интерпретатор можно достаточно легко адаптировать к любым машинным архитектурам, разработав его только один раз на широко распространенном языке программирования.

2. Состав системы программирования. Понятие CASE.

Системой программирования называется комплекс программных средств предназначенных для разработки и отладки ПО. Современные системы программирования, как правило, представляют собой интегрированную среду разработки, к компонентам которой относятся следующие программные средства:

- текстовый редактор , предназначенный для создания текстов исходной программы на языке высокого уровня или ассемблере

- компилятор, предназначенный для трансляции (перевода) исходного текста входной программы в эквивалентную ей выходную программу (объектный код) на языке нижнего уровня – машинных команд или ассемблера;

- библиотека стандартных или прикладных подпрограмм , содержащая часто используемые функции в виде готовых объектных модулей;

- компоновщик, предназначенный для объединения нескольких объектных модулей, созданных компилятором или взятых из стандартных библиотек, в единое целое – исполняемый файл программы;

- загрузчик, обеспечивающий подготовку готовой программы к выполнению;

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

CASE (computer-aided software engineering)— набор инструментов и методов программной инженерии для проектирования программного обеспечения, который помогает обеспечить высокое качество программ, отсутствие ошибок и простоту в обслуживании программных продуктов.

3.Обзор классификации языков программирования

Процедурные (или алгоритмические) программы представляют из себя систему предписаний для решения конкретной задачи. Роль компьютера сводится к механическому выполнению этих предписаний.

Процедурные языки разделяют на языки низкого и высокого уровня.

Разные типы процессоров имеют разные наборы команд. Если язык программирования ориентирован на конкретный тип процессора и учитывает его особенности, то он называется языком программирования низкого уровня. Имеется в виду, что операторы языка близки к машинному коду и ориентированы на конкретные команды процессора.

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

Языки программирования высокого уровня значительно ближе и понятнее человеку, нежели компьютеру. Особенности конкретных компьютерных архитектур в них не учитываются, поэтому создаваемые программы на уровне исходных текстов легко переносимы на другие платформы, для которых создан транслятор этого языка. Разрабатывать программы на языках высокого уровня с помощью понятных и мощных команд значительно проще, а ошибок при создании программ допускается гораздо меньше.

Основное достоинство алгоритмических языков высокого уровня - возможность описания программ решения задач в форме, максимально удобной для восприятия человеком. Но так как каждое семейство ЭВМ имеет свой собственный,

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

20

1. Различные формулировки понятия алгоритм. Их смысл и область применения.

Алгоритм – конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.

Алгоритм – всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

Алгоритм – последовательность действий, направленных на получение определённого результата за конечное число шагов.

Алгоритм - это точная, однозначная, конечная последовательность действий, которую должен выполнить пользователь для достижения конкретной цели либо для решения конкретной задачи или группы задач за конечное число шагов.

Виды алгоритмов как логико-математических средств отражают указанные компоненты человеческой деятельности и тенденции, а сами алгоритмы в зависимости от цели, начальных условий задачи, путей её решения. Следует подчеркнуть принципиальную разницу между алгоритмами вычислительного характера, преобразующими некоторые входные данные в выходные (именно их формализацией являются упомянутые выше машины Тьюринга, Поста, РАМ, нормальные алгорифмы Маркова и рекурсивные функции), и интерактивными алгоритмами (уже у Тьюринга встречается C-машина, от англ. choice — выбор, ожидающая внешнего воздействия, в отличие от классической A-машины, где все начальные данные заданы до начала вычисления и выходные данные недоступны до окончания вычисления). Последние предназначены для взаимодействия с некоторым объектом управления и призваны обеспечить корректную выдачу управляющих воздействий в зависимости от складывающейся ситуации, отражаемой поступающими от объекта управления сигналами. В некоторых случаях алгоритм управления вообще не предусматривает окончания работы (например, поддерживает бесконечный цикл ожидания событий, на которые выдается соответствующая реакция), несмотря на это, являясь полностью правильным.

2. Основные свойства алгоритмов.

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.

Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.

Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.

Завершаемость (конечность) — в более узком понимании алгоритма как математической функции, при правильно заданных начальных данных алгоритм должен завершать работу и выдавать результат за определённое число шагов.

Массовость (универсальность). Алгоритм должен быть применим к разным наборам начальных данных.

Результативность — завершение алгоритма определёнными результатами.

3. Оценка сложности алгоритма.

Сложность алгоритмов обычно оценивают по времени выполнения или по используемой памяти. В обоих случаях сложность зависит от размеров входных данных: массив из 100 элементов будет обработан быстрее, чем аналогичный из 1000. При этом точное время мало кого интересует: оно зависит от процессора, типа данных, языка программирования и множества других параметров. Важна лишь асимптотическая сложность, т. е. сложность при стремлении размера входных данных к бесконечности.

Допустим, некоторому алгоритму нужно выполнить 4n3 + 7n условных операций, чтобы обработать n элементов входных данных. При увеличении n на итоговое время работы будет значительно больше влиять возведение n в куб, чем умножение его на 4 или же прибавление 7n. Тогда говорят, что временная сложность этого алгоритма равна О(n3), т. е. зависит от размера входных данных кубически.

Использование заглавной буквы О (или так называемая О-нотация) пришло из математики, где её применяют для сравнения асимптотического поведения функций. Формально O(f(n)) означает, что время работы алгоритма (или объём занимаемой памяти) растёт в зависимости от объёма входных данных не быстрее, чем некоторая константа, умноженная на f(n).

Примеры

O(n) — линейная сложность

Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.

O(log n) — логарифмическая сложность

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.

O(n2) — квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n, т. е. n2.

Бывают и другие оценки по сложности, но все они основаны на том же принципе.

Также случается, что время работы алгоритма вообще не зависит от размера входных данных. Тогда сложность обозначают как O(1). Например, для определения значения третьего элемента массива не нужно ни запоминать элементы, ни проходить по ним сколько-то раз. Всегда нужно просто дождаться в потоке входных данных третий элемент и это будет результатом, на вычисление которого для любого количества данных нужно одно и то же время.

Аналогично проводят оценку и по памяти, когда это важно. Однако алгоритмы могут использовать значительно больше памяти при увеличении размера входных данных, чем другие, но зато работать быстрее. И наоборот. Это помогает выбирать оптимальные пути решения задач исходя из текущих условий и требований.

21

1. Алгоритм, как абстрактная машина. Обоснование возможности такой формулировки.

Алгоритм – это любая конечная система правил преобразования информации (данных) над любым конечным алфавитом.

Точное описание класса частично рекурсивных функций вместе с тезисом Черча дает одно из возможных решений задачи об уточнении понятия алгоритма. Однако это решение не вполне прямое, так как понятие вычислимой функции является вторичным по отношению к понятию алгоритма. Спрашивается, нельзя ли уточнить непосредственно само понятие алгоритма и уже затем при его помощи определить точно и класс вычислимых функций? Такое направление поиска привело к построению иного, нежели рекурсивные функции, класса моделей алгоритма. Основная его идея состоит в том, что алгоритмические процессы – это процессы, которые может осуществлять определенным образом устроенная машина, моделирующая тем самым выполнение отдельных операций человеком. Функционирование такой машины и есть выполнение некоторого алгоритма. Основные требования к таким машинам:

-характер их функционирования должен быть дискретным, т.е. состоять из отдельных шагов , каждый из которых выполняется только после завершения предыдущего;

-действия должны быть детерминированы, т.е. шаги выполняются в строгом порядке, а их результат определяется самим шагом и результатами предыдущих шагов;

-перед началом работы машине предоставляются исходные данные из области определения алгоритма;

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

-машина должна быть универсальной, т.е. такой, чтобы с ее помощью можно было бы выполнить любой алгоритм.

Обоснование

Пусть исходные данные из области определения алгоритма представлены посредством алфавита A и образуют при этом конечную последовательность знаков {a1…a n} – такая последовательность называется словом. В результате выполнения алгоритма сформируется новое слово {b1…bm}, представленное, в общем случае, в другом алфавите B. На первый взгляд для проведения такого преобразования в качестве элементарных выделяются следующие операции (шаги):

1.замена одного знака исходного слова ai знаком bj из алфавита B;

2.удаление знака исходного слова;

3.добавление к исходному слову знака из алфавита B.

Однако если в алфавиты включен знак, имеющий смысл пустого знака, добавление которого к слову слева или справа не изменяет этого слова (аналог числового нуля), то легко видеть, что операция (2) есть ни что иное, как замена ai пустым знаком, а операция (3) есть замена пустого знака знаком bj. Таким образом, все возможные алфавитные преобразования сводится к операции (1) – замене одного знака другим. Именно по этой причине функционирование абстрактной машины сводится к тому, что она обозревает символы (т.е. считывает и распознает их), записанные в памяти (в этом качестве выступает бесконечная лента), и в зависимости от своего состояния и того, каков обозреваемый символ, она заменяет его

другим символом; после этого она переходит в новое состояние, читает следующий символ и т.д. до команды о прекращении работы. Поскольку подобные машины являются чисто модельным, теоретическим построением, они получили название абстрактных машин и рассматриваются в качестве одной из возможных универсальных алгоритмических систем.

2. Машина Тьюринга. Математическое описание. Область применения.

Машина Тьюринга (МТ)— абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.

Устройство машины Тьюринга

В состав машины Тьюринга входит бесконечная в обе стороны лента(возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство, способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.

Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки ленты символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.

Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.

Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной.

Описание машины Тьюринга

Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk(если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо (R), остаться на месте (N)). Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.

3. Машина Поста. Описание, принцип работы

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы.

В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

Машина Поста состоит из …

* бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),

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

Текущее состояние машины Поста описывается состоянием ленты и положением каретки.

Состояние ленты – информация о том, какие секции пусты, а какие отмечены.

Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.

Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:

i K j,

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

22

1. Классификация данных

Данные – это сведения, характеризующие какую-то систему, явление, процесс или объект, представленные в определенной форме и предназначенные для дальнейшего использования.

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

Данные имеют несколько классификационных признаков: данные бывают различных типов, делятся на простые и структурированные, подразделяются на переменные и постоянные, могут являться входными, промежуточными и выходными.

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

Тип данных определяет:

Набор их допустимых значений;

Правила их обработки (преобразования);

Порядок их размещения в памяти компьютера при хранении;

Порядок доступа к ним (обращения и извлечения с места хранения);

Допустимый набор типов данных и их особенности определяются программной системой или языком программирования, на котором система написана. При этом возможности различных языков по разнообразию допустимых типов данных, а также по построению новых типов данных различаются весьма сильно. Ясно, что чем более широкой и гибкой оказывается типизация данных в языке программирования, тем больше возможностей предоставляется пользователю при решении задач оптимального представления, хранения и применения данных. Типизация данных влияет и на компактность самой исполняемой программы.

2. Структурированные типы данных.

Структурированные типы данных классифицируют по следующим основным признакам: однородная - неоднородная, упорядоченная - неупорядоченная, прямой доступ - последовательный доступ, статическая - динамическая. Эти признаки противостоят друг другу лишь внутри пары, а вне этого могут сочетаться.

Структуру называют упорядоченной, если между ее элементами определен порядок следования. Наличие индекса в записи элементов структуры уже указывает на ее упорядоченность.

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

Если у структуры размер (длина, количество элементов) не может быть изменен по ходу действия, а фиксирован заранее, то такую структуру называют статической.

Программные средства информатики иногда позволяют не фиксировать размер структуры, а устанавливать его по ходу решения задачи и менять при необходимости, что бывает очень удобно. Такую структуру называют динамической.

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

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

Обобщением массива является комбинированный тип данных - запись, являющаяся неоднородной упорядоченной статической структурой прямого доступа. Запись есть набор именованных компонент - полей (часто разного типа), объединенных одним общим именем и идентифицируемых (адресуемых) с помощью как имени записи, так и имен полей.

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

1) новые компоненты могут добавляться лишь в хвост очереди;

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

Размер очереди заранее не оговаривается и теоретически может считаться бесконечным. Для запоминания (хранения) компонент очереди часто используют внешне запоминающие устройства большой емкости - магнитные диски и ленты. Отсюда другое название очереди - файл.

3. Неструктурированные типы данных.

В математике принято классифицировать величины в соответствии с их характеристиками. Различают целые, вещественные, комплексные и логические величины, представляющие собой отдельные значения, множества значений или множества множеств. Аналогично и в информатике.

Целые числа, используемые компьютером, имеют те же свойства, что и целые числа в арифметике. Все вычисления с ними выполняются абсолютно точно (не приближенно). Имеется только одно отличие в свойствах компьютерных целых чисел - ограниченность диапазона: для каждой компьютерной системы имеется самое большое допустимое в ней целое число и самое малое, отрицательное. Это свойство компьютерных чисел связано с особенностями их кодирования в ячейках памяти компьютера.

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

Главным свойством литерных (символьных) данных является их упорядоченность, то есть свойство быть сравнимыми. Обычным признаком значения символьной или текстовой величины являются кавычки. Каждый символ имеет определенный числовой код (например, код символа латинской буквы 'А' в большинстве кодировок 63) и упорядочение происходит в соответствии с этими числовыми кодами. Как правило, имеются функции, позволяющие получить по символу его код и символ по коду.

К логическим данным, способным принимать значения «истина» или «ложь». Иногда можно использовать операции импликации («если»), эквиваленции («если и только если») и тому подобное.

23

Вопрос 1. Понятие программы. Отличие программы от алгоритма.

Программа – описание на языке программирования структур данных и алгоритма решения задачи, автоматически переводимое, при помощи специальной программы-транслятора(компилятора или интерпретатора), на язык команд компьютера для последующего выполнения. Можно сказать, что компьютерная программа – один из способов реализации понятия алгоритма, а язык программирования – средство описания алгоритмов. Компьютерная программа, в отличие от абстрактного алгоритма, имеет данные – собственные элементы, над которыми она совершает действия, и которые являются ее составной частью.

Вопрос 2. Понятие языка программирования. Требования к языкам программирования.

Язык программирования — формальная знаковая система, предназначенная для записи компьютерных программ. Язык программирования определяет набор лексических, синтаксических и семантических правил, задающих внешний вид программы и действия, которые выполнит исполнитель (компьютер) под её управлением.

Основные требования, предъявляемые к языкам программирования: наглядность - использование в языке по возможности уже существующих символов, хорошо известных и понятных как программистам, так и пользователям ЭВМ; единство - использование одних и тех же символов для обозначения одних и тех же или родственных понятий в разных частях алгоритма. Количество этих символов должно быть по возможности минимальным; гибкость - возможность относительно удобного, несложного описания распространенных приемов математических вычислений с помощью имеющегося в языке ограниченного набора изобразительных средств; модульность - возможность описания сложных алгоритмов в виде совокупности простых модулей, которые могут быть составлены отдельно и использованы в различных сложных алгоритмах; однозначность - недвусмысленность записи любого алгоритма. Отсутствие ее могло бы привести к неправильным ответам при решении задач.

Вопроос 3. Алфавит. Синтаксис. Семантика.

Алфавит – совокупность символов, отображаемых на устройствах печати и экранах и/или вводимых с клавиатуры терминала.

Синтаксис – совокупность правил образования языковых конструкций, или предложений языка программирования – блоков, процедур, составных операторов, условных операторов, операторов цикла и пр. Особенностью синтаксиса является принцип вложенности (рекурсивность) правил построения конструкций. Это значит, что элемент синтаксиса языка в своем определении прямо или косвенно в одной из его частей содержит сам себя. Например, в определении оператора цикла телом цикла является оператор, частным случаем которого является все тот же оператор цикла.

Семантика – смысловое содержание конструкций, предложений языка, семантический анализ – это проверка смысловой правильности конструкции. Например, если мы в выражении используем переменную, то она должна быть определена ранее по тексту программы, а из этого определения может быть получен ее тип. Исходя из типа переменной, можно говорить о допустимости операции с данной переменной. Семантические ошибки возникают при недопустимом использовании операций, массивов, функций, операторов и пр.

24

1. Классификация языков программирования с подробным описанием каждого класса.

Классификация языком программирования по категориям связана с методами, которые используются при написании программ.

1.1. Процедурные языки.

Процедурные языки — языки высокого уровня, в которых используется метод разбиения программ на отдельные связанные между собой модули – процедуры и функции. Компоненты языка состоят из последовательности операторов, которые используют библиотечные (встроенные в программу) процедуры и функции.

Языки программирования низкого уровня.

Программирование на первых компьютерах происходило с помощью двоичных машинных кодов. Такое программирование довольно трудоёмкое и тяжёлое. Для упрощения процесса программирования разрабатывались языки программирования низкого уровня, которые позволяли задавать машинные команды в понятном для человека виде. Чтобы преобразовать их в двоичный код создавались специальные программы – трансляторы.

К языкам низкого уровня относится:

• программирование в машинных кодах;

• ассемблер;

• макроассемблер.

Языки низкого уровня ориентировались на определённый тип процессора и учитывали его особенности, поэтому для того, чтобы перенести программу, написанную на ассемблере, на другую аппаратную платформу (на другой язык программирования) — её нужно было почти полностью переписать.

Языками низкого уровня пользуются преимущественно для написания небольших системных программ, а также микропроцессоров, когда немаловажным является компактность, быстродействие и возможность прямого доступа к аппаратным ресурсам.

Языки программирования высокого уровня.

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

Зачастую достаточным является

Разработка программ на языках высокого уровня значительно проще и ошибок намного меньше. К тому же время разработки программы значительно уменьшается, что является особенно важным фактором при работе над сложными программными проектами.

Недостаток некоторых языков высокого уровня состоит в большом размере программ по сравнению с программами на языках низкого уровня. В то же время текст программ на языке высокого уровня гораздо меньше, но в байтах код, написанный на ассемблере, будет более компактным. Поэтому языки высокого уровня преимущественно используют для создания программного обеспечения для компьютеров и вычислительных устройств с большим объемом памяти. Языки же низкого уровня используются для написания программ к устройств, для которых критичным является размер программы.

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

Наиболее распространенные универсальные языки C#, C++, Basic, Pascal используются для разработки Windows-приложений, а также языки для разработки Интернет-приложений. К ним относятся современные версии C#, Basic, J#.

Проблемно-ориентированными языками, которые используются на Интернет-серверах и клиентских Интернет-приложениях, являются PHP, Perl, JavaScript, VBScript.

1.2. Непроцедурные языки.

Это группа языков, описывающих организацию данных, обрабатываемых по фиксированным алгоритмам.

Объектно-ориентированные языки.

Объектно-ориентированные языки стали дальнейшим уровнем развития процедурных языков, основной концепцией которых есть совокупность программных объектов. Написание программы на языке представляется в виде последовательности создания экземпляров объектов и использование их методов. К ним относятся из первых языков Simula и SmallTalk, далее C++, Java.

Языки сценариев (скрипты). (не входят в таблицу)

Языки относятся к объектно-ориентированным языкам, используются для написания программ, которые исполняются в определённой программной среде. Тексты программ, написанные на языке сценариев, можно включать в тело HTML-документа. Первыми скриптами были Perl и Python, которые изначально были разработаны для операционной системы UNIX, а уже в дальнейшем появились версии языков для операционных систем Windows и Macintosh.

Декларативные языки программирования.

В декларативном программировании задаётся спецификация решения задачи, то есть даётся описание того, что представляет собой проблема и какой ожидается результат. Программы, созданные с помощью декларативного языка, не содержат переменные и операторы присваивания. К декларативным языкам можно отнести SQL и HTML. К подвидам декларативного программирования относится функциональное и логическое программирование.

Функциональные языки программирования.

Функциональные языки являются языками искусственного интеллекта. Программа, написанная на функциональном языке, состоит из последовательности функций и выражений, которые необходимо вычислить. Основной структурой данных является связный список. Функциональное программирование принципиально отличается от процедурного. Основными функциональными языками являются Lisp, Miranda, Haskel.

Логические языки программирования.

Языки, ориентированные на решение задач без описания алгоритмов, языки искусственного интеллекта. Представителем логического программирования является Prolog, которым написано большинство экспертных систем.

1.3. Языки, ориентированные на данные. (не входят в таблицу)

Языки ориентированы на работу с одним определённым типом данных. Например, APL работает с матрицами и векторами, Snobol обрабатывает строки, SETL выполняет операции над множествами. Особое развитие получили языки для работы с базами данных: 3GL, PL/SQL, FoxPro.

Широкими возможностями обработки документов текстового процессора Microsoft Word, электронных таблиц MS Excel, баз данных MS Access и даже программ подготовки слайдовых презентаций MS PowerPoint обладает встроенный язык системы MS Office – Visual Basic for Application (VBA).

2. Объектно-ориентированное программирование. Основные понятия. Их применение. Примеры.

2.1. Объектно-ориентированное программирование (ООП) — методология (учение о методах, способах и стратегиях исследования предмета) программирования, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определённого класса (набор полей и методов программы), а классы образуют иерархию наследования.

2.2. Основные понятия.

Инкапсуляция.

Инкапсуляция — это понятие в объектно-ориентированном программировании, обозначающее защиту данных (сокрытие данных) от внешнего пользователя.

Наследование.

Наследование —это понятие объектно-ориентированного программирования, позволяющее наследовать функционал (набор полей и методов) одного класса в другой.

Полиморфизм подтипов.

Полиморфизм — это понятие объектно-ориентированного программирования, позволяющее одному и тому же методу вести себя по-разному.

3.3. Применение и примеры.

Пример инкапсуляции — чтобы совершить звонок по сотовому телефону, необязательно знать как работают сотовые сети, где расположены вышки связи, как у них организованно хранение данных и прочее. Всё, что нужно знать, чтобы совершить звонок по сотовому телефону — это что должен быть номер того абонента, кому нужно позвонить, и деньги на счету.

То есть свойство инкапсуляции в объектно-ориентированном программировании обозначает то, что нужно дать пользователю программы доступ только к нужным интерфейсам (методам) и скрыть доступы к внутренним приватным методам и полям класса.

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

За человеком тянется целая эволюционная цепочка генов, начиная с генов древних людей, заканчивая генами современного человека — его родителей. В объектно-ориентированном программировании, наследование — аналогичное свойство.

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

Пример полиморфизма — когда человек приходит в супермаркет, кассир на кассе может не только продать ему один товар, например хлеб, но и продать другие продукты в его корзине. И более того, кассир может принять от него как наличные деньги, так и кредитную карту.

Если полиморфизм перенести на пример с классами — то это общий метод для объектов.

3. Понятие системы визуального программирования.

Визуальное программирование — способ создания программы для ЭВМ (Электронно-вычислительной машины) путём манипулирования графическими объектами вместо написания её текста.

Визуальное программирование часто представляют как следующий этап развития текстовых языков программирования. Наглядным примером может служить утилита «Визуальный Pascal» или «Microsoft Visual Studio», где редактируются графические объекты и одновременно отображается соответствующий текст программы.

В последнее время визуальному программированию стали уделять больше внимания — в связи с развитием мобильных сенсорных устройств.

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

Среда визуального программирования позволяет написать Веб-приложение для браузеров. Среда визуального программирования позволяет создать консольное приложение (программа без графического интерфейса и без вывода сообщений в консоль) для программирования микроконтроллеров, программируемых микросхем.

25

1.Методы проектирования программ. Методы проектирования программ, основанные на модульном принципе, делятся на три группы:

* методы нисходящего проектирования,

* методы расширения ядра

* методы восходящего проектирования.

На практике обычно применяются различные сочетания этих методов. 1. Метод нисходящего проектирования Метод нисходящего проектирования подобен методу получения детального изображения из более общего вида с помощью телескопического увеличения. На начальном шаге формируется предложение, описывающее функцию

всей программы. Затем определяются ее подфункции. Эта процедура является рекурсивной, т. е., следуя ей, каждая из подфункций может расчленяться до тех пор, пока ее составные части не будут окончательно уточнены.

2. Метод расширения ядра Метод расширения ядра отличается от способа нисходящего проектирования: в нем больше внимания вначале уделяется выявлению множества вспомогательных функций, а не определению функции всей программы в целом. Эти функции можно получить, применяя методы проектирования структур данных, которые используются при иерархическом модульном проектировании, или определяя области хранения данных с последующим анализом связанных с ними функциональных единиц. 3. Метод восходящего проектирования При использовании метода восходящего проектирования в первую очередь определяются вспомогательные функции, которые могут потребоваться для проектируемой программы.Функции, определяемые как вспомогательные при восходящем проектировании, реализуются с помощью модулей самых нижних уровней, предназначенных для выполнения таких операций, как чтение, сортировка, формирование страниц и печать.

2.Жизненный цикл программного обеспечения- Это период времени, который начинается с момента принятия решения о необходимости создания программного продукта и заканчивается в момент его полного изъятия из эксплуатации.

3. Разработка модели программного обеспечения

процесс разработки программного обеспечения— структура, согласно которой построена разработка программного обеспечения.

Существует несколько моделей такого процесса, каждая из которых описывает свой подход, в виде задач и/или деятельности, которые имеют место в ходе процесса.

1)Водопадная (каскадная, последовательная) модель

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

2)Итерационная модель (IID)

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

Подход IID имеет и свои отрицательные стороны, которые, по сути, — обратная сторона достоинств. Во-первых, целостное понимание возможностей и ограничений проекта очень долгое время отсутствует. Во-вторых, при итерациях приходится отбрасывать часть сделанной ранее работы. В-третьих, добросовестность специалистов при выполнении работ всё же снижается, что психологически объяснимо, ведь над ними постоянно довлеет ощущение, что «всё равно всё можно будет переделать и улучшить позже».

Спиральная модель

При использовании этой модели ПО создается в несколько итераций (витков спирали).

Каждая итерация соответствует созданию фрагмента или версии ПО, на ней уточняются цели и характеристики проекта, оценивается качество полученных результатов и планируются работы следующей итерации.

На каждой итерации оцениваются:

* риск превышения сроков и стоимости проекта;

* необходимость выполнения ещё одной итерации;

* степень полноты и точности понимания требований к системе;

* целесообразность прекращения проекта.

Важно понимать, что спиральная модель является не альтернативой эволюционной модели (модели IID), а специально проработанным вариантом. Отличительной особенностью спиральной модели является специальное внимание, уделяемое рискам, влияющим на организацию жизненного цикла, и контрольным точкам.

Подчеркнутое – самое важное

26

1) Предпосылки к разработке объектно-ориентированного программирования. Цели использования объектно-ориентированного программирования.

Эволюция типов данных

Простые типы

Простые, или скалярные, типы (целые и вещественные числа, логические значения, символы) были доступны уже в самых ранних языках программирования, так как эти типы данных непосредственно поддерживались компьютерами на встроенном уровне. Однако, по мере возрастания сложности задач, которые ставились перед программистами, и увеличением объема данных (особенно, сходных, обрабатываемых единообразно) становилась все более заметной ограниченность этих типов, связанная с тем, что скалярная величина представляет только одно значение.

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

Составные типы

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

Типы, определенные пользователем

Еще большую гибкость в работе с данными обеспечила появившаяся в некоторых языках возможность объявлять свои собственные типы данных. Хоть эти пользовательские типы и базировались на стандартных, но примечательным является сам факт снятия жестких рамок, задаваемых при создани языка.

Парадигмы программирования

Последовательное программирование

Первые языки программирования были практически лишены средств управления потоком выполнения команд. Заданные при написании программы команды выполнялись последовательно одна за другой, и только иногда эта монотонная последовательность нарушалась оператором безусловного (GOTO) или условного (IF GOTO) перехода на определенную строку программы. Весь командный код воспринимался как единый однородный блок.

Безусловно, с ростом сложности и объема решаемых задач такой стиль программирования стал вызывать серьезные проблемы. Вынужденное использование множества команд перехода приводило к возникновению запутанных цепочек вычислений, в которых подчас было трудно разобраться самому автору программы, не говоря уже о его коллегах. Отладка и сопровождение программ также становилось все более проблематичными.

Структурное программирование

В начале 70-х был предложен иной стиль программирования. Он предполагал использование контрольных структур ветвления (if..then..else..endif), выбора (switch..case) и повторения (while, for). Одновременно резкой критике было подвергнуто использование оператора GOTO.

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

Функциональное программирование

Если использование контрольных структур обеспечило низкоуровневую структуризацию программного кода, то функции открыли путь к структуризации высокого уровня.

Существенным является отделение пространства данных функций от глобального. Переменные, объявленные внутри функции, не видны ни из других функций, ни из остальной программы.

Модульное программирование

Еще один способ высокоуровневой структуризации - разбиение программного кода на отдельные части (модули). Каждый модуль хранится в отдельном файле. Примечательно, что пространство модуля является локальным уже не только для данных, но даже и для функций. Функции и переменные одного модуля не доступны из других модулей, если только они не будут специально объявлены как глобальные.

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

Объектно-ориентированное программирование

Таким образом, в программировании сформировалась отчетливая тенденция к структуризации путем все более тесного объединения взаимосвязанных данных и фрагментов кода в одном блоке при все большем отделении таких блоков друг от друга. В конечном итоге, эта тенденция привела к возникновению объектно-ориентированного программирования, которое в 90-х годах заняло господствующее положение.

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

2) Программная инженерия. Применение.

(все важно)

Термин «программная инженерия» появился впервые в 1968 году на конференции НАТО и предназначался для провоцирования поиска решений, происходившего в то время «кризиса программного обеспечения». С тех пор это переросло в профессию программного инженера и область исследований, посвящённых созданию программного обеспечения, более качественного, доступного, лучше поддерживаемого и быстрее разрабатываемого.Разработка программного обеспечения связана с дисциплинами информатики, управления проектами, и системной инженерии.

Когда первые современные цифровые компьютеры появились в начале 1940-х годов, наборы исполняемых команд уже были встроены в машину. Специалисты быстро поняли, что этот подход не слишком удобен. Так появилась «архитектура хранимых программ» или архитектура фон Неймана. Таким образом, деление на «аппаратное» и «программное обеспечение» началось с абстракции, используемой чтобы решить проблему сложности вычислений.(информация из вопроса 1 ООП)

Первые языки программирования стали появляться в 1950-х годах, и это был ещё один важный шаг в абстракции. Основные языки, такие как Фортран, Алгол и Кобол, были выпущены в конце 1950-х для решения научных, алгоритмических и бизнес-задач соответственно. Дэвид Парнас ввёл ключевое понятие модульности и скрытия информации в 1972 году, чтобы помочь программистам справляться со всё более и более сложными программными системами. Системное программное обеспечение для управления аппаратным, названное «операционная система», было представлено компанией Unix в 1969 году. В 1967 году язык Симула ввёл понятие объектно-ориентированного программирования.

Эти достижения в области программного обеспечения были встречены большим прорывом в компьютерной технике. В середине 1970-х годов был представлен микрокомпьютер, что позволило любителям получить собственный компьютер и писать свои программы для него. Это, в свою очередь привело к появлению персональных компьютеров (ПК) и Microsoft Windows. Также в середине 1980-х появляются такие понятия как жизненный цикл программного обеспечения в качестве некоторого консенсуса для централизованной разработки программного обеспечения. Конец 1970-х и начало 1980-х годов ознаменовались появлением нескольких новых симула-подобных объектно-ориентированных языков программирования, в том числе Smalltalk, Objective-Cи C++.

3) Процесс разработки программного обеспечения с использованием объектно-ориентированного подхода включает четыре этапа:

1) анализ;

2) проектирование;

3) эволюция;

4) модификация.

Анализ. Цель анализа - максимально полное описание задачи. На этом этапе выполняется анализ предметной области задачи, объектная декомпозиция разрабатываемой системы и определяются важнейшие особенности поведения объектов (описание абстракций).

По результатам анализа разрабатывается структурная схема программного продукта, на которой показываются основные объекты и сообщения, передаваемые между ними, а также выполняется описание абстракций.

Проектирование. Различают:

а) логическое проектирование, при котором принимаемые решения практически не зависят от условий эксплуатации (операционной системы и используемого оборудования);

б) физическое проектирование, при котором приходится принимать во внимание указанные факторы.

Логическое проектирование заключается в разработке структуры классов: определяются поля для хранения составляющих состояния объектов и алгоритмы методов, реализующих аспекты поведения объектов. При этом используются рассмотренные выше приемы разработки классов (наследование, композиция, наполнение, полиморфизм и т.д.). Результатом является иерархия или диаграмма классов, отражающие взаимосвязь классов, и описание классов.

Физическое проектирование включает объединение описаний классов в модули, выбор схемы их подключения (статическое или динамическая компоновка), определение способов взаимодействия с оборудованием, с операционной системой и/или другим программным обеспечением (например, базами данных, сетевыми программами), обеспечение синхронизации процессов для систем параллельной обработки и т.д.

Эволюция системы – это процесс поэтапной реализации и подключения классов к проекту.

Процесс начинается с создания основной программы или проекта будущего программного продукта. Затем реализуются и подключаются классы, так чтобы создать грубый, но, по возможности, работающий прототип будущей системы. Он тестируется и отлаживается. Например, таким прототипом может служить система, включающая реализацию основного интерфейса программного продукта (передача сообщений в отсутствующую пока часть системы не выполняется). В результате мы получаем работоспособный прототип продукта, который может быть, например, показан заказчику для уточнения требований.

Использование поэтапной реализации существенно упрощает тестирование и отладку программного продукта.

Модификация – это процесс добавления новых функциональных возможностей или изменение существующих свойств системы. Как правило, изменения затрагивают реализацию класса, оставляя без изменения его интерфейс, что при использовании ООП обычно обходится без особых неприятностей, так как процесс изменений затрагивает локальную область.

Простота модификации позволяет сравнительно легко адаптировать программные системы к изменяющимся условиям эксплуатации, что увеличивает время жизни систем, на разработку которых затрачиваются огромные временные и материальные ресурсы.

Особенностью ООП является то, что объект или группа объектов могут разрабатываться отдельно, и, следовательно, их проектирование может находиться на различных этапах. Например, интерфейсные классы уже реализованы, а структура классов предметной области еще только уточняются. Обычно, проектирование начинается, когда какой-либо фрагмент предметной области достаточно полно описан в процессе анализа.

27

1. Понятие системы управления базами данных

Система управления базами данных (СУБД) – это совокупность языковых и программных средств, предназначенных для создания, ведения и совместного использования БД многими пользователями

2. Структура СУБД. Функциональные элементы СУБД.

Существует три основных модели хранения данных:

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

Пример. Организация файловой системы.

· Сетевая модель базы данных - в ней все данные считаются потенциально взаимосвязанными.

· Реляционная модель использует табличный способ хранения данных. Реляционная база данных может состоять из нескольких раздельных файлов (таблиц). Каждый из них представляет собой организованное собрание связанных записей. Каждая запись состоит из набора данных, каждый элемент которых представляет собой поле.

4.5.3. Система управления базами данных Access

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

СУБД представляет собой программу, которая позволяет создать новую базу данных, открыть существующую, просмотреть записи, выбрать необходимую информацию по условию, удалить запись и т. д. Управление производится с помощью меню или специальных команд в командном окне. С помощью специальных средств, предоставляемых СУБД, можно создать свою программу, которая будет автоматически осуществлять определенные операции с конкретной базой данных.

3. Размещение элементов СУБД в оперативной памяти.

Такие СУБД хранят данные целиком в оперативной памяти. Что это означает? Каждый раз, отправляя запрос на поиск или обновление данных, вы обращаетесь только к оперативной памяти в обход жесткого диска — на нем никакие операции не производятся. И это хорошо, потому что оперативная память работает намного быстрее любого диска. Примером такой СУБД является Memcached.

Секундочку, скажете вы, а как же восстановить данные после перезагрузки или поломки машины с такой СУБД? Если на машине установлена СУБД для хранения данных только в оперативной памяти, о них можно забыть: при отключении питания данные бесследно исчезнут.

Можно ли объединить достоинства хранения данных в оперативной памяти с надежностью проверенных временем СУБД вроде MySQL или Postgres? Конечно! Повлияет ли это на производительность? Вы удивитесь, но нет!

Встречайте СУБД для данных в оперативной памяти, обеспечивающие их сохранность: Redis, Aerospike, Tarantool.

28

1)Область SQL

Область SQL можно использовать для создания собственных инструкций SQL. Инструкции также можно создавать в области критериев или области схем, при этом в области SQL будут созданы инструкции SQL. После построения запроса он автоматически обновляется и переформатируется в области SQL с целью сделать его более удобным для восприятия. Чтобы открыть область SQL, сначала откройте конструктор запросов и представлений (с объектом базы данных, выбранным в обозревателе серверов в меню База данных, выберите пункт Создать запрос). Затем в меню Конструктор запросов укажите пункт Область и выберите пункт SQL.

В области SQL можно выполнять следующие действия:

* создавать новые запросы посредством ввода инструкций SQL;

* изменять инструкции SQL, созданные конструктором запросов и представлений, с использованием собственных параметров, введенных в областях схем и условий;

* вводить инструкции, которые пользуются преимуществами функций, доступных в конкретной базе данных.

Примечание

Отображаемые на компьютере имена или расположения некоторых элементов пользовательского интерфейса Visual Studio могут отличаться от указанных в следующих инструкциях. Текущий запрос можно редактировать непосредственно в области SQL. При переходе в другую область конструктор запросов и представлений автоматически форматирует инструкцию и затем изменяет области схем и критериев для соответствия этой инструкции.

Если инструкция не может быть представлена в областях схем и критериев, учитывая, что эти области видимы, конструктор запросов и представлений выводит ошибку и предлагает два выхода:

* не учитывать невозможность представления инструкции в областях схем и критериев;

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

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

Можно продолжить изменение инструкции и выполнить ее, как любую инструкцию SQL.

Примечание

Если введена инструкция SQL, но потом внесены изменения в запрос, с изменением областей схем и критериев конструктор запросов и представлений перестроит и заново отобразит инструкцию SQL. В некоторых случаях это приводит к тому, что инструкция SQL строится отлично от той, которая была введена изначально (хотя результат получится одинаковый). Эта разница, в частности, возможна, если ведется работа с условиями поиска, содержащими несколько предложений, связанных операторами AND и OR.

2)Модуль управления транзакциями

Транзакцией называется последовательность операций над базой данных, рассматриваемых СУБД как единое целое. Если все операции успешно выполнены, то транзакция также считается успешно выполненной и СУБД фиксирует (COMMIT) все изменения данных, произведенные этой транзакцией (то есть заносит изменения во внешнюю память). Если же хотя бы одна операция транзакции заканчивается неудачей, то транзакция считается невыполненной и производится откат (ROLLBACK) — отмена всех изменений данных, произведенных в ходе выполнения транзакции, и возврат базы данных к состоянию до начала выполнения транзакции.

Управление транзакциями необходимо для поддержания логической целостности базы данных. Поддержка механизма транзакций является обязательным условием даже однопользовательских, а тем более для многопользовательских СУБД. При соответствующем управлении параллельно выполняющимися транзакциями со стороны СУБД каждый из пользователей может, в принципе, ощущать себя единственным пользователем СУБД.

3)Системный каталог СУБД

Системный каталог - это набор таблиц, в которых содержится информация, необходимая для правильного функционирования СУБД: о поддерживаемых базах данных и их базовых таблицах, представлениях, курсорах, индексах, пользователях и их правах доступа к информации, правилах модификации данных и т.д. В разных СУБД, поддерживающих SQL, существует от десятка до нескольких десятков системных таблиц, структура которых ничем не отличается от уже знакомой нам структуры пользовательских таблиц.

Так, в каждой строке системной таблицы SYSTABLES хранится описание одной из таблиц пользовательских или системной баз данных. Для каждой из них указывается имя таблицы, имя пользователя, который создал эту таблицу, число столбцов в ней и ряд других элементов информации. В таблице SYSCOLUMNS содержится строка для каждого столбца каждой таблицы, в которой указано имя столбца, имя таблицы, частью которой является данный столбец, тип данных для этого столбца и много другой информации о столбце.

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

SELRCTTab_name,N_col,N_row,Tab_owner,Comments

FROMSYSTABLES;

и получить результат, показанный на рис. 5.1,а.

Для получения же некоторых данных о столбцах таблицы Блюда можно дать запрос

SELECTCol_name, Type, Length, Comments

FROMSYSCOLUMNS

WHERETab_name = 'Блюда';

и получить результат, показанный на рис. 5.1,б.

а)

Tab_name N_col N_row Tab_owner Comments

...

SYS_TABLES 11 SYSTEM

SYS_COLUMNS 14 SYSTEM

...

Блюда 6 33 KIRILLOW Перечень блюд, известных шеф-повару

Поставки 4 37 GROMOW Данные о поставляемых продуктах

Вид_блюд 2 5 KIRILLOW Перечень видов блюд

Трапезы 2 3 GROMOW Перечень трапез в пансионате

Состав 3 148 KIRILLOW Состав блюд

Продукты 11 17 KIRILLOW Таблица продуктов

...

б)

Col_name Type Length Comments

БЛ INTEGER 4 Код блюда

Блюдо TEXT 16 Название блюда

В TEXT 1 Код вида блюда (З, С, ...)

Основа TEXT 6 Основной продукт в блюде

Выход REAL 4 Масса порции готового блюда

Труд INTEGER 4 Стоимость приготовления блюда (коп)

В заключение следует отметить, что СУБД не позволяет обновлять каталог с помощью предложений DELETE, INSERT и UPDATE.

29

1. Классификация файлов, используемых в системе баз данных.

2.Понятие файла. Файлы прямого доступа. Устройства внешней памяти. Файлы с переменной длинной записи

* Файл — это определенное количество информации (программа или данные), имеющее имя и хранящееся в долговременной (внешней) памяти.

* Файлы с постоянной длиной записи, расположенные на устройствах прямого доступа (УПД), являются файлами прямого доступа. В этих файлах физический адрес расположения нужной записи может быть вычислен по номеру записи (NZ). Каждая файловая система СУФ - система управления файлами поддерживает некоторую иерархическую файловую структуру, включающую чаще всего неограниченное количество уровней иерархии в представлении внешней памяти.

* Внешняя память компьютера В состав внешней памяти входят: 1) накопители на жестких магнитных дисках (НЖМД); 2) накопители на гибких магнитных дисках (НГМД); 3) накопители на магнитооптических компакт дисках; 4) накопители на оптических дисках (CD-ROM); 5) накопители на магнитной ленте и др.

3. Понятие хеширования файлов

Хеширование - это специальный метод адресации данных (некоторый алгоритм расстановки) по их уникальным ключам для быстрого поиска нужной информации

Хеш-таблица представляет собой обычный массив со специальной адресацией, задаваемой некоторой функцией (Хеш-функция).

30

1. Механизм удаления записи из SQL

Для удаления записей из таблицы применяется оператор DELETE:

DELETE FROM "имя таблицы" WHERE "условие"

Данный оператор удаляет из указанной таблицы записи (а не отдельные значения столбцов), которые удовлетворяют указанному условию. Условие — это логическое выражение.

Если таблица содержит несколько записей, удовлетворяющих условию, то все они будут удалены.

В операторе WHERE может находиться подзапрос на выборку данных (оператор SELECT). Подзапросы в операторе DELETE работают точно так же, как и в операторе SELECT.

Для удаления всех записей из таблицы достаточно использовать оператор DELETE без ключевого слова WHERE. При этом сама таблица со всеми определенными в ней столбцами сохраняется и готова для вставки новых записей.

2.Понятие синонима, размещение синонимов.

Синоним — это альтернативный способ обращения к существующей таблице со стороны пользователей. Синонимы позволяют обращаться к объекту б

Однако синоним не изменяет характеристики описания таблицы. Таким образом, с помощью синонимов пользователи могут обращаться к таблице, не предваряя ее имени именем владельца.

Синонимы могут быть общими или частными. К частному (private) синониму может обращаться только тот пользователь, который создал его и владеет им. Если же синоним общий (public), он доступен любому пользователю базы данных. Частный и общий синонимы создаются с помощью команд CREATE SYNONYM и CREATE PUBLIC SYNONYM. Причем на создание общих синонимов нужно иметь специальную привилегию.

Общий синоним создается привилегированным пользователем и позволяет другим пользователям базы данных обращаться к конкретной таблице, не предваряя ссылку на нее именем схемы

Для удаления синонимов используется команда DROP SYNONYM

3.Понятие коллизий, стратегия разрешения коллизий

Файлы с постоянной длиной записи, расположенные на устройствах прямого доступа (УПД), являются файлами прямого доступа

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

Файлы с прямым доступом обеспечивают наиболее быстрый способ доступа. Мы не всегда можем хранить информацию в виде файлов прямого доступа, но главное — это то, что доступ по номеру записи в базах данных весьма неэффективен. Чаще всего в базах данных необходим поиск по первичному или возможному ключам, иногда необходима выборка по внешним ключам, но во всех этих случаях мы знаем значение ключа, но не знаем номера записи, который соответствует этому ключу.

При организации файлов прямого доступа возможно построение функции, которая по значению ключа однозначно вычисляет адрес (номер записи файла) Однако далеко не всегда удается построить взаимно-однозначное соответствие между значениями ключа и номерами записей.

Часто бывает, что значения ключей разбросаны по нескольким диапазонам.

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

Суть методов хэширования состоит в том, что мы берем значения ключа и используем его для начала поиска, то есть мы вычисляем некоторую хэш-функцию h(k) и полученное значение берем в качестве адреса начала поиска. То есть мы не требуем полного взаимно-однозначного соответствия, но, с другой стороны, для повышения скорости мы ограничиваем время этого поиска для окончательного получения адреса. Таким образом, мы допускаем, что нескольким разным ключам может соответствовать одно значение хэш-функции (то есть один адрес). Подобные ситуации называются коллизиями .Значения ключей, которые имеют одно и то же значение хэш-функции, называются синонимами.

Стратегии разрешения коллизий с областью переполнения

При выборе этой стратегии область хранения разбивается на 2 части:

основная область ,область переполнения.

Для каждой новой записи вычисляется значение хэш-функции, которое определяет адрес ее расположения, и запись заносится в основную область в соответствии с полученным значением хэш-функции.

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

31

1.Накопи́тель на жёстких магни́тных ди́сках, или НЖМД, жёсткий диск, винчестер — запоминающее устройство (устройство хранения информации) произвольного доступа, основанное на принципе магнитной записи. Является основным накопителем данных в большинстве компьютеров.

Магнитный принцип чтения и записи информации

В магнитных носителях информации цифровая запись производится на магнито чувствительный материал. К таким материалам относятся некоторые разновидности оксидов железа, никель, кобальт и его соединения, сплавы, а также магнитопласты и магнитоэласты со вязкой из пластмасс и резины, микропорошковые магнитные материалы.

Магнитное покрытие имеет толщину в несколько микрометров. Покрытие наносится на немагнитную основу, в качестве которой для магнитных лент и гибких дисков используются различие пластмассы, а для жестких дисков — алюминиевые сплавы и композиционные материалы подложки. Магнитное покрытие диска имеет доменную структуру, т.е. состоит из множества намагниченных мельчайших частиц.

Магнитный домен — это микроскопическая, однородно намагниченная область в ферромагнитных образцах, отделенная от соседних областей тонкими переходными слоями (доменными границами).

Под воздействием внешнего магнитного поля собственные магнитные поля доменов ориентируются в соответствии с направлением магнитных силовых линий. После прекращения воздействия внешнего поля на поверхности домена образуются зоны остаточной намагниченности. Благодаря этому свойству на магнитном носителе сохраняется информация, действовавшем магнитном поле.

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

Схема записи и чтения с магнитного диска дана на рис.3.1 Изменение направления ЭДС в течение некоторого промежутка времени отождествляется с двоичной единицей, а отсутствие этого изменения — с нулем. Указанный промежуток времени называется битовым элементом.

Поверхность магнитного носителя рассматривается как последовательность точечных позиций, каждая из которых ассоциируется с битом информации. Поскольку расположение этих позиций определяется неточно, для записи требуются заранее нанесенные метки, которые помогают находить необходимые позиции записи. Для нанесения таких синхронизирующих меток должно быть произведено разбиение диска на дорожки и секторы — форматирование.

Организация быстрого доступа к информации на диске является важным этапом хранения данных. Оперативный доступ к любой части поверхности диска обеспечивается, во-первых, за счет придания ему быстрого вращения и, во-вторых, путем перемещения магнитной головки чтения/записи по радиусу диска. Гибкий диск вращается со скоростью 300—360 об/мин, а жесткий диск — 3600— 7200 об/мин.

2. Низкоуровневое форматирование — операция, в процессе которой на магнитную поверхность жёсткого диска наносятся так называемые сервометки — служебная информация, которая используется для позиционирования головок диска. Выполняется в процессе изготовления жёсткого диска, на специальном оборудовании, называемом серворайтером.

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

3. В отличие от гибкого диска (дискеты), информация в НЖМД записывается на жёсткие (алюминиевые или стеклянные) пластины, покрытые слоем ферромагнитного материала, чаще всего диоксида хрома — магнитные диски. В НЖМД используется одна или несколько пластин на одной оси. Считывающие головки в рабочем режиме не касаются поверхности пластин благодаря прослойке набегающего потока воздуха, образующейся у поверхности при быстром вращении. Расстояние между головкой и диском составляет несколько нанометров (в современных дисках около 10 нм]), а отсутствие механического контакта обеспечивает долгий срок службы устройства. При отсутствии вращения дисков головки находятся у шпинделя или за пределами диска в безопасной («парковочной») зоне, где исключён их нештатный контакт с поверхностью дисков.

Также, в отличие от гибкого диска, носитель информации обычно совмещают с накопителем, приводом и блоком электроники. Такие жёсткие диски часто используются в качестве несъёмного носителя информации.

Главная загрузочная запись (master boot record, MBR) — код и данные, необходимые для последующей загрузки операционной системы и расположенные в первых физических секторах (чаще всего в самом первом) на жёстком диске или другом устройстве хранения информации.

MBR содержит небольшой фрагмент исполняемого кода, таблицу разделов диска и специальную сигнатуру.

Функция MBR — «переход» в тот раздел жёсткого диска, с которого следует исполнять «дальнейший код» (обычно — загружать ОС). На «стадии MBR» происходит выбор раздела диска, загрузка кода ОС (происходит на более поздних этапах алгоритма).

В процессе запуска компьютера, после окончания начального теста (Power-on self-test — POST), Базовая система ввода-вывода(BIOS) загружает «код MBR» в оперативную память (в IBM PC обычно с адреса 0000:7c00) и передаёт управление находящемуся в MBR загрузочному коду.

Алгоритм загрузки компьютера с использованием MBR

BIOS (до MBR)

BIOS проводит начальную инициализацию оборудования (POST).

BIOS определяет, с какого устройства производить дальнейшую загрузку: дискета, флеш-накопитель, жёсткий диск и т. д. (выбор устройства зависит от версии и от настроек BIOS)

BIOS считывает один сектор (512 байт), т.е. непосредственно MBR, который находится по адресу: «цилиндр 0, головка 0, сектор 1», и помещает его в область памяти по физическому адресу 0x7C00.

BIOS проверяет, что этот сектор оканчивается сигнатурой 55ААh

BIOS передаёт управление по физическому адресу 0x7C00 (то есть сектору MBR), предварительно записав в регистр DL номер диска, с которого этот сектор считан. Для первого жёсткого диска это значение будет равно 80h (128 в десятичной системе), для дисковода A: равно 0. Кроме того, Plug-n-Play BIOS может записать в регистры ES:DI указатель на структуру «$PnP».

32

1)Интерфейс. Серийно выпускаемые внутренние жёсткие диски могут использовать интерфейсы ATA(он же IDE и PATA),SATA,eSATA,SCSI,SAS,FireWire,SDIOиFibre Channel.

Ёмкость — количество данных, которые могут храниться накопителем. С момента создания первых жёстких дисков в результате непрерывного совершенствования технологии записи данных их максимально возможная ёмкость непрерывно увеличивается. Ёмкость современных жёстких дисков (с форм-фактором3,5 дюйма) на ноябрь 2010г. достигает 3000 ГБ (3 Терабайт). В отличие от принятой винформатикесистемы приставок, обозначающих кратную 1024 величину, производителями при обозначении ёмкости жёстких дисков используются величины, кратные 1000. Так, ёмкость жёсткого диска, маркированного как «200 ГБ», составляет 186,2ГБ.

Физический размер (форм-фактор). Почти все современные (2001—2008 года) накопители дляперсональных компьютеровисерверовимеют ширину либо 3,5, либо 2,5дюйма— под размер стандартных креплений для них соответственно в настольных компьютерах иноутбуках. Также получили распространение форматы 1,8 дюйма, 1,3 дюйма, 1 дюйм и 0,85 дюйма. Прекращено производство накопителей в форм-факторах 8 и 5,25 дюймов.

Время произвольного доступа — время, за которое винчестер гарантированно выполнит операцию чтения или записи на любом участке магнитного диска. Диапазон этого параметра невелик — от 2,5 до 16мс. Как правило, минимальным временем обладают серверные диски, самым большим из актуальных — диски для портативных устройств.

Скорость вращения шпинделя — количество оборотов шпинделя в минуту. От этого параметра в значительной степени зависят время доступа и средняя скорость передачи данных. В настоящее время выпускаются винчестеры со следующими стандартными скоростями вращения: 4200, 5400 и 7200 (ноутбуки), 5400, 7200 и 10000 (персональные компьютеры), 10000 и 15000 об/мин (серверы и высокопроизводительные рабочие станции). Увеличению скорости вращения шпинделя в винчестерах для ноутбуков препятствует гироскопический эффект, влияние которого пренебрежимо мало в неподвижных компьютерах.

Надёжность — определяется как среднее время наработки на отказ(MTBF). Также подавляющее большинство современных дисков поддерживают технологиюS.M.A.R.T.

Количество операций ввода-вывода в секунду — у современных дисков это около 50 оп./с при произвольном доступе к накопителю и около 100 оп./сек при последовательном доступе.

Потребление энергии — важный фактор для мобильных устройств.

Уровень шума — шум, который производит механика накопителя при его работе. Указывается в децибелах. Тихими накопителями считаются устройства с уровнем шума около 26 дБ и ниже. Шум состоит из шума вращения шпинделя (в том числе аэродинамического) и шума позиционирования.

Сопротивляемость ударам — сопротивляемость накопителя резким скачкам давления или ударам, измеряется в единицах допустимой перегрузки во включённом и выключенном состоянии.

Скорость передачи данных при последовательном доступе:

* внутренняя зона диска: от 44,2 до 74,5 Мб/с;

* внешняя зона диска: от 60,0 до 111,4 Мб/с.

Объём буфера — буфером называется промежуточная память, предназначенная для сглаживания различий скорости чтения/записи и передачи по интерфейсу. В современных дисках он обычно варьируется от 8 до 64 Мб.

2) Носители жестких дисков, в отличие от гибких, имеют постоянное число дорожек и секторов, изменить которое невозможно. Эти числа определяются типом модели и производителем устройства. Поэтому, физический объем жестких дисков определен изначально и состоит из объема, занятого служебной информацией (разметка диска на дорожки и сектора) и объема, доступного пользовательским данным. Физический объем жесткого диска, также, зависит от типа интерфейса, метода кодирования данных, используемого физического формата и др. Производители накопителей указывают объемы дисков в миллионах байт, предполагая, исходя из десятичной системы исчисления, что в одном мегабайте 1000000 байт. Однако, ПО оперирует не десятичной, а двоичной системами, полагая, что в одном килобайте не 1000 байт, а 1024. Такие несложные разногласия в системах исчисления приводят к несоответствиям при оценке объема накопителей, данном в описании и - выдаваемом различными программными тестами.

Носители жестких дисков, в отличие от гибких, имеют постоянное число дорожек и секторов, изменить которое невозможно. Эти числа определяются типом модели и производителем устройства. Поэтому, физический объем жестких дисков определен изначально и состоит из объема, занятого служебной информацией (разметка диска на дорожки и сектора) и объема, доступного пользовательским данным. Физический объем жесткого диска, также, зависит от типа интерфейса, метода кодирования данных, используемого физического формата и др. Производители накопителей указывают объемы дисков в миллионах байт, предполагая, исходя из десятичной системы исчисления, что в одном мегабайте 1000000 байт. Однако, ПО оперирует не десятичной, а двоичной системами, полагая, что в одном килобайте не 1000 байт, а 1024. Такие несложные разногласия в системах исчисления приводят к несоответствиям при оценке объема накопителей, данном в описании и - выдаваемом различными программными тестами.

Одним из возможных, но не желательных способов повышения физической емкости, для производителей, является увеличение емкости сектора. В настоящее время, стандартной емкостью сектора для IBM-совместимых компьютеров является 512 байт. Многие адаптеры позволяют, в процессе физического форматирования, программным путем, изменять емкость сектора, например, до 1024 байт. При этом соотношение пользовательских данных и служебной информации для сектора улучшается, но снижается надежность хранения данных, т.к. тот же полином ECC будет использоваться для коррекции большего объема данных. Однако, выигрыш на физическом уровне еще не означает тот же результат на логическом, т.к. логическая структура диска может оказаться не эффективной, например, при использовании для работы с файлами малой длинны (менее 1 К). Логический же объем зависит от того, как операционная система или программа записывает информацию в сектора. В случае использования программ и операционных систем с программной компрессией данных, можно повысить объем носителя на величину, зависящую от степени сжатия данных.

Для оптимального использования поверхности дисков применяется так называемая зонная запись (Zoned Bit Recording - ZBR), принцип которой состоит в том, что на внешних дорожках, имеющих большую длину (а, следовательно - и потенциальную информационную емкость на единицу площади), информация записывается с большей плотностью, чем на внутренних. Таких зон с постоянной плотностью записи в пределах всей поверхности образуется до десятка и более; соответственно, скорость чтения и записи на внешних зонах выше, чем на внутренних. Благодаря этому файлы, расположенные на дорожках с большим диаметром, в целом будут обрабатываться быстрее файлов, расположенных на дорожках с меньшим диаметром, т.к. для них будет производится меньшее число позиционирований с дорожки на дорожку.

В ЖД последнего поколения используются технологии PRML (Partial Response, Maximum Likelihood - максимальное правдоподобие при неполном отклике) и S.M.A.R.T. (Self Monitoring Analysis and Report Technology - технология самостоятельного слежения анализа и отчетности). Первая разработана по причине того, что при существующих плотностях записи уже невозможно четко и однозначно считывать сигнал с поверхности диска - уровень помех и искажений очень велик. Вместо прямого преобразования сигнала используется его сравнение с набором образцов, и на основании максимальной похожести (правдоподобия) делается заключение о приеме того или иного машинного слова.

Накопитель, в котором реализована технология S.M.A.R.T., ведет статистику своих рабочих параметров (количество стартов/остановок и наработанных часов, время разгона шпинделя, обнаруженные/исправленные физические ошибки и т.п.), которая регулярно сохраняется в перепрограммируемом ПЗУ или служебных зонах диска. Эта информация накапливается в течение всего периода эксплуатации и может быть в любой момент затребована программами анализа. По ней можно судить о состоянии механики, условиях эксплуатации или примерной вероятности выхода из строя. 3) С удаленностью от центра магнитного диска длина дорожек увеличивается, что позволяет записать на них больше информации (секторов) при постоянной скорости вращения шпиндельного двигателя, сохраняя постоянную плотность записи на всей поверхности магнитного диска, что позволяет более эффективно использовать емкость магнитной поверхности пластины без ущерба надежности хранящихся на ней данных. Данная технология получила название зонной записи (ZBR) и используется совместно с другими технологиями магнитной записи для увеличения плотности записи.

33

1. SCSI. Назначение, применение. SATA,SAS

SCSI (англ. Small Computer System Interface, произносится «скази»[1][2] (встречается вариант эс-си-эс-ай)) — представляет собой набор стандартов для физического подключения и передачи данных между компьютерами и периферийными устройствами. SCSI-стандарты определяют команды, протоколы и электрические и оптические интерфейсы. Разработан для объединения на одной шине различных по своему назначению устройств, таких, как жёсткие диски, накопители на магнитооптических дисках, приводы CD, DVD, стримеры, сканеры, принтеры и т. д. Раньше имел неофициальное название Shugart Computer Systems Interface в честь создателя Алана Ф. Шугарта, разработанный в 1978 г. и опубликованный в 1981 году.

Теоретически возможен выпуск устройства любого типа на шине SCSI.

После стандартизации в 1986 году SCSI начал широко применяться в компьютерах Sun Microsystems. В компьютерах, совместимых с IBM PC, SCSI не пользуется такой популярностью в связи со своей сложностью и сравнительно высокой стоимостью и применяется преимущественно в серверах.

SCSI широко применяется на серверах, высокопроизводительных рабочих станциях; RAID-массивы на серверах часто строятся на жёстких дисках со SCSI-интерфейсом (однако в серверах нижнего ценового диапазона всё чаще применяются RAID-массивы на основе SATA). В настоящее время устройства на шине SAS постепенно вытесняют устаревшую шину SCSI.

Система команд SCSI на уровне программного обеспечения употребляется в единых стеках поддержки устройств хранения данных в ряде операционных систем, таких, как Microsoft Windows.

Существует реализация системы команд SCSI поверх оборудования (контроллеров и кабелей) IDE/ATA/SATA, называемая ATAPI — ATA Packet Interface. Все используемые в компьютерной технике подключаемые по IDE/ATA/SATA приводы CD/DVD/Blu-Ray используют эту технологию.

Также система команд SCSI реализована поверх протокола USB, что является частью спецификации класса Mass Storage device[3][4]. Это позволяет подключать через интерфейс USB любые хранилища данных (от флеш-накопителей до внешних жёстких дисков), не разрабатывая для них собственного протокола обмена, а вместо этого используя имеющийся в операционной системе драйвер SCSI.

SATA использует 7-контактный разъём вместо 40-контактного разъёма у PATA. SATA-кабель имеет меньшую площадь, за счёт чего уменьшается сопротивление воздуху, обдувающему комплектующие компьютера, упрощается разводка проводов внутри системного блока.

SATA-кабель за счёт своей формы более устойчив к многократному подключению. Питающий шнур SATA также разработан с учётом многократных подключений. Разъём питания SATA подаёт 3 напряжения питания: +12 В, +5 В и +3,3 В; однако современные устройства могут работать без напряжения +3,3 В, что даёт возможность использовать пассивный переходник со стандартного разъёма питания IDE на SATA. Ряд SATA-устройств поставляется с двумя разъёмами питания: SATA и Molex.

Стандарт SATA отказался от традиционного для PATA подключения по два устройства на шлейф; каждому устройству полагается отдельный кабель, что снимает проблему невозможности одновременной работы устройств, находящихся на одном кабеле (и возникавших отсюда задержек), уменьшает возможные проблемы при сборке (проблема конфликта Slave/Master устройств для SATA отсутствует), устраняет возможность ошибок при использовании нетерминированных PATA-шлейфов.

Стандарт SATA поддерживает функцию очереди команд (NCQ, начиная с SATA Revision 1.0a[источник не указан 2793 дня]).

В отличие от PATA, стандарт SATA предусматривает горячее подключение устройства (используемого операционной системой) (начиная с SATA Revision 1.0)

(SAS) — последовательный компьютерный интерфейс, разработанный для подключения различных устройств хранения данных, например, жёстких дисков и ленточных накопителей. SAS разработан для замены параллельного интерфейса SCSI и основывается во многом на терминологии и наборах команд SCSI.

SAS обратно совместим с интерфейсом SATA: устройства 3 Гбит/с и 6 Гбит/с SATA могут быть подключены к контроллеру SAS, но не наоборот.

Последняя реализация SAS обеспечивает передачу данных со скоростью до 12 Гбит/с на одну линию. К 2017 году ожидается появление спецификации SAS со скоростью передачи данных 24 Гбит/с[1].

Протокол SAS разработан и поддерживается комитетом T10[2]. Консорциум производителей различного оборудования под названием SCSI Trade Association (SCSITA) занимается продвижением различных технологий, связанных с SCSI, в том числе SAS.

2. Понятие RAID. Виды RAID-массивов. Описание структуры каждого из

уровней RAID.

RAID (англ. redundant array of independent disks — избыточный массив независимых жёстких дисков) — массив из нескольких дисков, управляемых контроллером, взаимосвязанных скоростными каналами и воспринимаемых внешней системой как единое целое. В зависимости от типа используемого массива может обеспечивать различные степени отказоустойчивости и быстродействия. Служит для повышения надёжности хранения данных и/или для повышения скорости чтения/записи информации. Изначально, подобные массивы строились в качестве резерва носителям на оперативной (RAM) памяти, которая в то время была дорогой. Со временем, аббревиатура приобрела второе значение – массив уже был из независимых дисков, подразумевая использование нескольких дисков, а не разделов одного диска, а также дороговизну (теперь уже относительно просто нескольких дисков) оборудования, необходимого для построения этого самого массива.

RAID 0 (Stripe). Режим, при использовании которого достигается максимальная производительность. Данные равномерно распределяются по дискам массива, диски объединяются в один, который может быть размечен на несколько. Распределенные операции чтения и записи позволяют значительно увеличить скорость работы, поскольку несколько дисков одновременно читают/записывают свою порцию данных. Пользователю доступен весь объем дисков, но это снижает надежность хранения данных, поскольку при отказе одного из дисков массив обычно разрушается и восстановить

данные практически невозможно. Область применения - приложения, требующие высоких скоростей обмена с диском, например видеозахват, видеомонтаж. Рекомендуется использовать с высоконадежными дисками.

RAID1

RAID 1 (Mirror). Несколько дисков (обычно 2), работающие синхронно на запись, то есть полностью дублирующие друг друга. Повышение производительности происходит только при чтении. Самый надежный способ защитить информацию от сбоя одного из дисков. Из-за высокой стоимости обычно используется при хранении очень важных данных. Высокая стоимость обусловлена тем, что лишь половина от общей емкости дисков доступна для пользователя.

RAID10

RAID 10, также иногда называется RAID 1+0 - комбинация двух первых вариантов. (Массив RAID0 из массивов RAID1). Имеет все скоростные преимущества RAID0 и преимущество надежности RAID1, сохраняя недостаток - высокую стоимость дискового массива, так как эффективная ёмкость массива равна половине ёмкости использованных в нём дисков. Для создания такого массива требуется минимум 4 диска. (При этом их число должно быть чётным).

RAID 0+1 - Массив RAID1 из массивов RAID0. Фактически не применяется из-за отсутствия преимуществ по сравнению с RAID10 и меньшей отказоустойчивости.

RAID1E

RAID 1E - Похожий на RAID10 вариант распределения данных по дискам, допускающий использование нечётного числа дисков (минимальное количество - 3)

RAID 2, 3, 4 - различные варианты распределенного хранения данных с дисками, выделенными под коды четности и различными размерами блока. В настоящее время практически не используются из-за невысокой производительности и необходимости выделять много дисковой емкости под хранение кодов ЕСС и/или четности.

RAID5

RAID 5 - массив, также использующий распределенное хранение данных аналогично RAID 0 (и объединение в один большой логический диск) + распределенное хранение кодов четности для восстановления данных при сбоях. Относительно предыдущих конфигураций размер Stripe-блока еще больше увеличен. Возможно как одновременное чтение, так и запись. Плюсом этого варианта является то, что доступная для пользователя емкость массива уменьшается на емкость лишь одного диска, хотя надежность хранения данных ниже, чем у RAID 1. По сути, является компромиссом между RAID0 и RAID1, обеспечивая достаточно высокую скорость работы при неплохой надежности хранения данных. При отказе одного диска из массива данные могут быть восстановлены без потерь в автоматическом режиме. Минимальное количество дисков для такого массива - 3.

"Программные" реализации RAID5, встроенные в южные мосты материнских плат, не отличаются высокой скоростью записи, поэтому годятся далеко не для всех применений.

RAID5EE

RAID 5EE - массив, аналогичный RAID5, однако кроме распределенного хранения кодов четности используется распределение резервных областей - фактически задействуется жесткий диск, который можно добавить в массив RAID5 в качестве запасного (такие массивы называют 5+ или 5+spare). В RAID 5 массиве резервный диск простаивает до тех пор, пока не выйдет из строя один из основных жестких дисков, в то время как в RAID 5EE массиве этот диск используется совместно с остальными HDD все время, что положительно сказывается на производительность массива. К примеру, массив RAID5EE из 5 HDD сможет выполнить на 25% больше операций ввода/вывода за секунду, чем RAID5 массив из 4 основных и одного резервного HDD. Минимальное количество дисков для такого массива - 4.

RAID6

RAID 6

RAID 6 - аналог RAID5 c большим уровнем избыточности - информация не теряется при отказе двух любых дисков, соответственно, общая ёмкость массива уменьшается на ёмкость двух дисков. Минимальное количество дисков, необходимое для создания массива такого уровня - 4. Скорость работы в общем случае примерно аналогична RAID5. Рекомендуется для применений, где важна максимально высокая надёжность.

RAID50

RAID 50 - объединение двух(или более, но это крайне редко применяется) массивов RAID5 в страйп, т.е. комбинация RAID5 и RAID0, частично исправляющая главный недостаток RAID5 - низкую скорость записи данных за счёт параллельного использования нескольких таких массивов. Общая ёмкость массива уменьшается на ёмкость двух дисков, но, в отличие от RAID6, без потери данных такой массив переносит отказ лишь одного диска, а минимально необходимое число дисков для создания массива RAID50 равно 6. Наряду с RAID10, это наиболее рекомендуемый уровень RAID для использования в приложениях, где требуется высокая производительность в сочетании с приемлемой надёжностью.

RAID60

RAID 60 - объединение двух массивов RAID6 в страйп. Скорость записи повышается примерно в два раза, относительно скорости записи в RAID6. Минимальное количество дисков для создания такого массива - 8. Информация не теряется при отказе двух дисков из каждого RAID 6 массива.

Matrix RAID — технология, реализованная фирмой Intel в своих южных мостах, начиная с ICH6R, позволяющая организовать всего на двух дисках несколько массивов RAID0 и RAID1, одновременно создавая разделы как с повышенной скоростью работы, так и с повышенной надёжностью хранения данных.

JBOD (От английского "Just a Bunch Of Disks")- последовательное объединение нескольких физических дисков в один логический, не влияющее на производительность (надёжность при этом падает аналогично RAID0), при этом диски могут иметь разные размеры. В настоящее время практически не применяется.

3. Понятие RAID-2. Описание, способы использования.

Массивы такого типа основаны на использовании кода Хемминга . Диски делятся на две группы: для данных и для кодов коррекции ошибок, причём если данные хранятся на 2n - n - 1 дисках, то для хранения кодов коррекции необходимо n дисков.

Данные распределяются по дискам, предназначенным для хранения информации, так же, как и в RAID 0, т.е. они разбиваются на небольшие блоки по числу дисков. оставшиеся диски хранят коды коррекции ошибок, по которым в случае выхода какого-либо жёсткого диска из строя возможно восстановление информации.

Метод хемминга давно применяется в памяти типа ECC и позволяет на лету исправлять однократные и обнаруживать двукратные ошибки.

Достоинством массива RAID 2 является увеличение надежности и повышение скорости дисковых операций, по сравнению с производительностью одного диска.

Недостатком массива RAID 2 является то, что минимальное количество дисков, при котором имеет смысл его использовать, - 7. При этом нужна структура из почти двойного количества дисков (для n=3 данные будут храниться на 4 дисках), поэтому такой вид массива не получил распространения. Если же дисков около 30-60, то перерасход получается 11-19%.

(+): высокая надежность и увеличение скорости.

(-): "перерасход дисков" и, как следствие - цена.

Минимальное количество дисков: 3.

34

1. Понятие файловой системы (на примере FAT,NTFS,ExtFS).

Файловая система - это функциональная часть операционной системы, обеспечивающая хранение данных на дисках и доступ к ним.

Файловая система определяет формат содержимого и способ физического хранения информации, которую принято группировать в виде файлов. Конкретная файловая система определяет размер имен файлов, максимальный возможный размер файла и раздела, набор атрибутов файла. Некоторые файловые системы предоставляют сервисные возможности, например, разграничение доступа или шифрование файлов.

FAT (таблица размещения файлов) - это классическая архитектура файловой системы, которая из-за своей простоты всё ещё широко используется для флеш - накопителей. Используется в дискетах, картах памяти и некоторых других носителях информации.

Не стоит использовать файловую систему FAT для дисков и разделов, чей размер больше 200 МБ. Это объясняется тем, что по мере увеличения размера тома производительность файловой системы FAT быстро падает. Для файлов, расположенных в разделах FAT, невозможно установить разрешения. Разделы FAT имеют ограничение по размеру.

В файловой системе FAT использован традиционный формат имен 8.3, имена файлов должны состоять из символов ASCII. Имя файла или каталога должно состоять не более чем из 8 символов, затем следует разделитель «.» (точка) и расширение длиной до 3 символов.

NTFS(файловая система новой технологии) - файловая система, целью которой является : обеспечение надежности, имеющей большое значение для высокопроизводительных систем и файловых серверов, Устранение ограничений, характерных для файловой системы FAT.

Для обеспечения надежности файловой системы NTFS особое внимание было уделено трем основным вопросам: способности к восстановлению, устранению неустранимых ошибок одного сектора и экстренному исправлению.

Эта файловая система представляет собой гибкую платформу с широкими функциональными возможностями, которую могут использовать другие файловые системы. Кроме того, в NTFS полностью реализована модель безопасности Windows NT и поддержка нескольких потоков данных. Файл данных перестал быть отдельным потоком данных. Кроме того, пользователи могут добавлять собственные атрибуты файлов.

Имена файлов могут состоять не более чем из 255 символов, включая любое расширение. В именах сохраняется регистр введенных символов, но сами имена не зависят от регистра.

ExtFS (Extended File System (расширенная файловая система)) - первая файловая система, разработанная специально для операционных систем на ядре Linux.

2.Понятие журналирования. Применение журнала в рамках файловой системы

Журналирование — процесс записи информации о происходящих с каким-то объектом (или в рамках какого-то процесса) событиях в журнал (например, в файл) . Применительно к компьютерной памяти журнал это запись в хронологическом порядке операций обработки данных, которые могут быть использованы для того, чтобы воссоздать существовавшую или альтернативную версию компьютерного файла. Журналируемая файловая система — файловая система (ФС) , в которой осуществляется ведение журнала, хранящего список изменений и, в той или иной степени, помогающего сохранить целостность файловой системы при сбоях.

3.Журналируемые файловые системы Linux. Описание, основные характеристики.

1.JFS2

JFS2 - это 64-разрядная файловая система, которая была усовершенствована в плане масштабируемости и поддержки многопроцессорных архитектур.

JFS2 поддерживает упорядоченное журналирование, обладает высокой производительностью и временем восстановления менее секунды. Для повышения быстродействия в ней применяется метод размещения файлов на основе экстентов. Размещение на основе экстентов означает размещение файла в виде нескольких непрерывных участков, а не множества одинаковых блоков. Благодаря непрерывности, эти участки обеспечивают более быстрое чтение и запись. Дополнительное преимущество экстентов - меньшие расходы на работу с метаданными. При размещении файла блоками записи подлежат метаданные каждого блока. Если используются экстенты, то изменяются метаданные для экстентов, которые обычно состоят из нескольких блоков.

2.XFS

XFS использует полноценную 64-разрядную адресацию и обеспечивает очень высокую производительность за счет применения B+-деревьев для размещения каталогов и файлов. XFS хранит данные в виде экстентов, поддерживая переменный размер экстентов (от 512 байт до 64 килобайт). Наряду с экстентами в XFS применяется отложенное размещение, при котором размещение блоков задерживается до тех пор, пока не наступит время их записи на диск. Такая особенность повышает вероятность заполнения подряд нескольких дисковых блоков, поскольку на момент записи будет известно их количество.

3. Ext3FS

В Ext3FS поддерживаются все три стратегии журналирования (обратная запись, упорядочивание и режим данных), однако по умолчанию используется режим упорядочивания. Политику переноса данных журнала на диск можно настраивать, но изначально она такова, что перенос происходит либо по заполнении 1/4 журнала, либо по истечении одного из таймеров переноса.

4. ReiserFS

В ReiserFS применяется много современных подходов, например B+-деревья. Формат файловой системы базируется на единственном B+-дереве, что делает операции поиска особенно быстрыми и масштабируемыми. Политика переноса данных из журнала на диск зависит от размера журнала и основана на количестве блоков, требующих переноса.

Основной метод журналирования - упорядочивание. Поддерживается увеличение размера файловой системы "на лету"

35

1.Твердотéльный накопи́тель SSD— компьютерное энергонезависимое немеханическое запоминающее устройство на основе микросхем памяти, которое пришло на смену HDD.

Назначение: накопитель информации, носитель информации, основанный на чипах энергонезависимой памяти, которые сохраняют данные после отключения питания.

Виды SSD: 1) SLC. Этот тип дисков считается самым производительным. Запись здесь идет на одноуровневые ячейки памяти, где в каждую помещается только 1 бит информации – единица или ноль бинарного кода. Такой вариант хранения данных обеспечивает высокую работоспособность диска и позволяет использовать одну и ту же ячейку бесконечное количество раз. 2)MLC. В этих накопителях на каждый транзистор записывается по 2 бита информации. Скорость считывания меньше чем SLC и количество циклов перезаписи на одну и ту же ячейку ограничено 3000-10000. 3) ТLC. Информация еще больше уплотняется: SSD записывает по 3 бита данных в одну ячейку. Благодаря этому

накопители TLC по размеру оказываются самыми маленькими. Из-за это снижена скорость чтения и число циклов перезаписи (1000-3000).

2. Отличия работы SSD и магнитного жесткого диска(HDD): Основное различие заключается в способе хранения данных. Так в HDD используется магнитный способ, то есть, данные записываются на диск путем намагничивания его областей. В SSD вся информация записывается в специальный тип памяти, который представлен в виде микросхем.

3 Область применения SSD, достоинства и недостатки.

В персональных компьютерах ССД-диски часто выполняют роль системных. Таким образом можно сэкономить на стоимости системного блока — скорость загрузки и работы ОС, благодаря ССД-винчестеру, значительно возрастает.

Еще одна область применения твердотельных дисков — установка в современные серверы. Они значительно ускоряют перемещение оперативной информации. Он способен выполнять одновременно сотни тысяч операций, что в разы больше по сравнению с HDD.

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

* Отсутствие шума при работе;

* Высокая скорость чтения/записи;

* Меньше подвержены механическим поломкам.

Недостатки.

* Высокая стоимость за 1 Гб

* Меньший объем хранения данных.

 

 

---

Дата добавления: 2019-02-26; просмотров: 909; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!