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

Размеры кластера

Размеры кластера определяются используемой файловой системой в зависимости от размеров логического диска.

Фрагментация

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

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

Файловая система NTFS делит все полезное место на кластеры - блоки данных, используемые единовременно. NTFS поддерживает почти любые размеры кластеров - от 512 байт до 64 Кбайт, неким же стандартом считается кластер размером 4 Кбайт.

Физический и логический формат диска

Любой диск имеет физический и логический формат.

Физический формат диска определяет размер сектора (в байтах), число секторов на дорожке (или

— для жёстких дисков — в цилиндре), число дорожек (цилиндров) и число сторон.

Логический формат диска задаёт способ организации информации на диске и фиксирует размещение информации различных типов.

Логический диск или том — часть долговременной памяти, рассматриваемая как единое целое для удобства работы. Термин «логический диск» используется в противоположность «физическому диску», под которым рассматривается память одного конкретного носителя информации

Таблица расположения файлов (File Allocation Table - FAT)

Для выполнения файловых операций ОС отслеживает распределение пространства диска между файлами с помощью таблицы FAT.

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

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

Для повышения быстродействия FAT копируются в оперативную память ПЭВМ.

Стандартная файловая система для семейства операционных систем MS Windows: NTFS (New Technol File System)

Стандартная файловая система для семейства операционных систем MS Windows.

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

MFT (Master File Table) — главная файловая таблица (база данных), в которой хранится информация о содержимом тома NTFS, представляющая собой таблицу, строки которой соответствуют файлам тома, а столбцы — атрибутам файлов).

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

Раздел 8 (Лекция 14)

Понятие алгоритма Алгоритм – это точное предписание, которое задает алгоритмический процесс, начинающийся с

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

Алгоритмический процесс Алгоритмический процесс – это процесс последовательного преобразования конструктивных

объектов (слов, чисел, пар слов, пар чисел, предложений и т.п.), происходящий дискретными «шагами». Каждый шаг состоит в смене одного конструктивного объекта другим.

Страница 39 из 45

Семь независимых параметров алгоритма

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

правило непосредственной переработки; правило окончания; правило извлечения результата.

Пример: параметры алгоритма Евклида

предназначен для нахождения наибольшего общего делителя пары натуральных чисел (m, n) 1 {Нахождение остатка} r:=m mod n.

2{Замена} m:=n; n:=г.

3{Остановка?} Если n<>0, то переход к п.1.

4{Остановка процесса} m — искомое число.

Смена конструктивных объектов в алгоритме Евклида для пары чисел m=10, n=4: (10, 4) (4, 2) (2, 0)

Способы описания алгоритмов

Словесно-формульный Структурный (блок - схемный)

С помощью граф-схем Блок-схема — это ориентированный граф, вершины которого могут быть одним из трех типов: Функциональная вершина используется для представления функции f: X—>Y. Предикатная вершина используется для представления функции (или предиката) р: X —» ( T, F), т.е. логического выражения, передающего управление по одной из двух возможных ветвей.

Объединяющая вершина представляет передачу управления от одной из двух входящих ветвей к одной выходящей.

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

Структурные блок - схемы алгоритмов: Линейные Ветвящиеся Циклические

С помощью сети Петри

Словесно-формульный способ

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

Блок-схемный

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

Страница 40 из 45

Структурная блок-схема алгоритма

Структурная блок-схема — это блок-схема, которая может быть выражена как композиция из 4 элементарных блок-схем.

Линейные, ветвящиеся и циклические алгоритмы

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

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

Направление ветвления выбирается логической проверкой, в результате которой возможны два ответа: «да» - условие выполнено и «нет»- условие не выполнено.

Циклическими называются программы, содержащие циклы. Цикл – это многократно повторяемый участок программы. В организации цикла можно выделить следующие этапы: подготовка (инициализация) цикла (И); выполнение вычислений цикла (Т); модификация параметров (М); проверка условий окончания цикла (У);

Методы разработки алгоритмов

Страница 41 из 45