В.Д. Валединский - Краткий конспект курса лекций «Работа на ЭВМ и программирование» (1119512), страница 7

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 7)

устройством FIFO, т.е. очередью)Теперь обратим внимание, что нигде в Inode не упоминается имя файла, зато есть запись«количество ссылок на файл». Это не случайно: один и тот же файл может иметь несколькоимен, причем в разных каталогах. Ссылки хранятся отдельно – в специальных файлах –каталогах. Такой файл представляет из себя просто набор записей вида: номер Inode - имяфайла. При попытке обращения к тому или иному файлу ОС ищет в каталоге ссылку с темже именем, находит по этой ссылке Inode и в дальнейшем работает именно с этойструктурой.

Ясно, что при таком подходе очевидным образом можно создавать каталоги иподкаталоги; кроме того существует выделенный «начальный» каталог – так называемаяточка монтирования файловой системы. Точка монтирования обозначается /; поиск нужногофайла по пути происходит так: если имя файла /home/usr1/file01, то ОС ищет в точкемонтирования файл home – это директория, в ней ищется файл usr1, затем в этом файледиректории ищется файл file01. Для сокращения записей существуют специальныесокращения: . – текущий каталог, .. – предыдущий каталог. Например, обращение ./file01 –найти файл с именем file01 в текущей директории (обращения к файлам в FAT происходитаналогичным образом).

Соответственно, имя файла в Inode не фигурирует, но фигурируетколичество ссылок на данный файл. При удалении ссылки на файл это число уменьшаетсяна 1, но файл удаляется только когда число ссылок на него становится равным 0;существуют и специальный команды, позволяющие создать ссылку на файл. Ссылка можетбыть жесткой (hard link) – в этом случае в соответствующем каталоге, где надо разместитьссылку, добавляется соответствующая запись со ссылкой на уже существующий Inode, асчетчик ссылок в Inode увеличивается на 1 и символической (symbolical link, ее мы восновном и используем) – когда запись в каталоге создается, но вместо указания номераInode в записи просто указывается имя файла, на который эта ссылка указывает – при этомсчетчик в Inode не увеличивается.

В отличие от hard link символические ссылки могутуказывать на несуществующий файл (при попытке обращения к ссылке будет выданасоответствующая ошибка), а также на файл из другой файловой системы.Как и в FAT диск в EXT2 делится на блоки одинакового размера – только ониназываются не секторами, а просто блоками.

Данные о том, в каких блоках лежит файлсодержатся в разделе «таблица ссылок на блоки данных». Первые 10 (примечание: на сайтеwww.science.unitn.it указано, что в EXT2 прямыми ссылками являются первые 12 ссылок)ссылок являются «прямыми» - в Inode сразу записываются номера первых 10 блоковданных. 11я ссылка уже является ссылкой на специальную запись из 256 элементов – ссылокпервого уровня на блоки данных. 12я ссылка – уже на запись из 256 элементов – ссылок наЛекции по ЭВМ.

Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год23записи по 256 указателей на блоки данных – ссылки второго уровня; аналогично 13я ссылкадает нам еще 256 3 блоков третьего уровня. Всего, соответственно, файл может содержатьдо 256 3  256 2  256  10 блоков, что дает определенные ограничения на размеры файла(около 4Gb при размере блока в 1Kb), зато более эффективно расходует место под файловуюсистему. Заполняются ссылки на блоки подряд, начиная с 0-го уровня; когда файлзаканчивается в очередную ссылку записывается специальное значение (7777h?).Соответственно, по Inode можно восстановить цепочку принадлежащих файлу блоков ипреобразовывать смещение от начала файла в реальные физические адреса на диске.

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

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

– обеспечивает малофрагментированный файл. При удалении файла информация о освобожденных блокахзапихивается обратно в соответствующие стеки.Лекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год242. Некоторые алгоритмы обработки и преобразования данных2.1. Эффективные сортировкиОдной из наиболее часто встречающихся операций над данными является сортировкаэтих данных. Нужна она прежде всего для организации данных в виде линейного массива(обладающего непревзойденным временем доступа и скоростью работы) с сохранениемвозможности быстрого поиска, добавления и удаления элементов.

Простейшие сортировки –сортировка «пузырьком», сортировка вставкой, сортировка поиском минимума илимаксимума известны всем. Их трудоемкость на массиве длины n составляет O n 2  операций.Зададимся вопросом: какова минимальная трудоемкость сортировки на массиве длины n?Теорема 1 (оценка снизу трудоемкости сортировки). Ни одна сортировка, основаннаяна попарном сравнении элементов, не может работать быстрее O n log 2 n  на массиве длиныnДоказательство: Пусть у нас есть алгоритм сортировки и мы подаем на него некиевходные данные. Каждая операция сравнения дает нам 2 дальнейших варианта развитиясобытий. Соответственно, за h сравнений мы может получить не больше 2 h различныхвариантов результатов работы алгоритма.

Если у нас алгоритм сортировки корректный, топри любых входных данных мы придем к отсортированному массиву, т.е. если алгоритм за hшагов корректно отсортирует все мыслимые входные массивы, то среди этих 2 h вариантовработы будут присутствовать все n! возможных перестановок входного массива из nэлементов (т.к. любая сортировка массива – некоторая его перестановка). Получили оценкуn! 2 h . Пользуясь формулой Стирлинга, упрощаем оценку:nnnnnnh.   n! 2  h  log 2    n log 2  n log 2 n eln 2 ee Соответственно h у нас – максимальное время работы алгоритма на массиве длины n неможет быть меньше O n log 2 n  .

Быстрее этого значения ни одна сортировка работать напроизвольном массиве данных не может.Таким образом, сортировку можно считать эффективной, если она работает заO n log 2 n  операций. Рассмотрим примеры эффективных сортировок:Быстрая (quicksort) сортировка. Для массива длины 1 сортировка не требуется. Длябольших массивов будем проводить сортировку массива следующим образом: на каждомшаге разобьем сортируемый участок массива на 2 части следующим образом: выберемнекоторое число x, заведем 2 указателя и пойдем по массиву с двух его концов навстречудруг другу. Начнем движение с начала массива, и будем двигать первый указатель помассиву вправо, пока не встретим первый элемент, больший x.

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

Запустим теперь нашу сортировку для каждой из полученных частей. Легковидеть, что в итоге получится отсортированный массив, поскольку все элементы левой частиЛекции по ЭВМ. Конспект. Лектор В.Д. Валединский.Группа 208, 3 семестр, 2002 год25не больше x не больше элементов правой части, а и левая и правая части отсортированы –значит, отсортирован и массив в целом.Лучший случай при такой сортировке – когда массив каждый раз делится строгопополам.

Число операций в этом случае, как легко посчитать O n log 2 n  . Но возможен и«плохой» случай, когда каждый раз при делении массива у нас один кусочек будетполучаться в 1 элемент, другой – все остальные. Число операций в этом случае, как легкопосчитать, будет порядка O n   n  1  ...  1  O n 2 и получается, что quicksort нельзяназвать эффективной сортировкой – она может работать достаточно долго.

Но оказывается,что среднее время сортировки – все те же O n log 2 n  .Теорема 2: среднее время сортировки quicksort на случайных входных данных O n log 2 n Доказательство: пусть f(n) – среднее время сортировки на quicksort на массиве длины n.Тогда, учитывая равную вероятность любого из разбиений массива на 2 части, получаемсреднее время сортировки1 nf  n    f  k   f  n  k   n .n k 1 Предположим, что для n = N у нас верно, что среднее время сортировки меньшеСn log 2 n (для n = 1 это верно).

Для n = N + 1 имеем:1 n 11 n 1  n   n 1f  n    Сk log 2 k  С  n  k  log 2  n  k   n     Cn log 2    n   Cn log 2 n  Cn  n n k 1n k 1 n2 =  n  1  C log 2 n  1  C    Cn log 2 n  (n  1)1  C  , достаточно взять C>1 и по индукцииформула будет справедлива для всех n. Ч.т.д.Примечание: использовался легко проверяемый факт, что a log c a  b log c b , a+b=constмаксимальноприa=b,чтолегкопроверяетсяпроверкойтого,чтоa C a.приОтсюдаипереход a log c a   C  a  log c  C  a    0k log 2 k   n  k  log 2  n  k   2k  (n  k )k  (n  k )nlog 2 n log 2 .222Несмотря на столь, казалось бы невыдающиеся параметры (минимальное и среднеевремя сортировки O n log 2 n  , худшее O n 2  , используется память (под стек рекурсивныхвызовов функций) от O log 2 n  до O n  ) quicksort в большинстве случаев благодаря своейпростоте работает быстрее всех других сортировок.Тем не менее, хочется иметь сортировку с гарантированно хорошими оценками.

Вкачестве таковой обычно приводят турнирную (пирамидальную, heapsort) сортировку. Воснову ее положена т.н. пирамида.Пирамида – такое бинарное дерево, которое можно получить заполнением дерева поуровням сверху вниз слева направо (т.е. пока есть свободные элементы на уровне, тодобавляем элемент по максимуму «слева» если смотреть по чертежу дерева, если уровеньзаполнен полностью, то заполняем следующий уровень и т.д.). Очевидно, что пирамида –идеально сбалансированное дерево, легко также видеть, что существует биекция междумножеством пирамид из n элементов и множеством массивов из n элементов.Действительно, сопоставим корню дерева нулевой элемент массива; если у нас элементимеет номер n в массиве, то его левый потомок имеет номер 2n+1, правый – 2n+2.

Характеристики

Список файлов лекций