Разработка ядра Linux
Шрифт:
Если f(x) принадлежит множеству большого-тета от g(x), то g(x) является одновременно и верхней и нижней границей f(x)
Можно также сказать, что функция f(x) порядка функции g(x). Порядок, или множество "большого-тета" алгоритма, — один из наиболее важных математических инструментов изучения алгоритмов.
Следовательно, когда говорят об обозначении большого-О, то
Объединяем все вместе
Вернемся снова к подсчету количества людей в комнате. Допустим, что можно считать по одному человеку за секунду. Следовательно, если в комнате находится 7 человек, то подсчет займет 7 секунд. Очевидно, что если будет n человек, то подсчет всех займет n секунд. Поэтому можно сказать, что этот алгоритм масштабируется, как O(n). Что если задача будет состоять в том, чтобы станцевать перед всеми, кто находится в комнате? Поскольку, независимо от того, сколько человек будет в комнате, это займет одно и то же время, значит, этот алгоритм масштабируется, как O(1). В табл. В.1 показаны другие часто встречающиеся характеристики сложности.
Таблица В.1. Значения масштабируемости алгоритмов во времени
| O(g(x)) | Название |
| 1 | Постоянная (отличная масштабируемость) |
| log(n) | Логарифмическая |
| n | Линейная |
| n² | Квадратичная |
| n³ | Кубическая |
| 2ⁿ | Показательная, или экспоненциальная (плохо) |
| n! | Факториал (очень плохо) |
Как масштабируется алгоритм представления всех людей в комнате друг другу? Какая функция может промоделировать этот алгоритм? Для представления одного человека необходимо 30 секунд, сколько времени займет представление 10 человек друг другу? Что будет в случае 100 человек?
Опасность, связанная со сложностью алгоритмов
Очевидно, что будет разумным избегать алгоритмов, которые масштабируются, как О(n!) или O(2ⁿ). Более того, замена алгоритма, который масштабируется, как O(n), алгоритмом, который масштабируется, как O(1), — это обычно серьезное улучшение. Тем не менее это не всегда так, и нельзя принимать решение вслепую, базируясь только на описании "большого-О". Вспомните, что в определении множества О(g(x)) фигурирует константа, на которую умножается значение функции g(x). Поэтому есть возможность, что алгоритм, который масштабируется, как O(1), будет выполняться в течение 3 часов. Следовательно, он будет выполняться всегда в течение 3 часов, независимо от количества входных данных, но это может оказаться дольше, по сравнению с алгоритмом, который масштабируется, как O(n), при небольшом количестве входных данных. При сравнении алгоритмов необходимо всегда принимать во внимание количество входных данных. Не стоит слепо оптимизировать для некоторого случайно выбранного варианта.
Приложение Г
Библиография и список литературы
Список литературы отсортирован и содержит некоторые из самых интересных и полезных книг, которые близки по теме, или дополняют материал данной книги.
Полезность этих книг проверена временем. Некоторые из них представляют собой "священные писания" но соответствующим темам, в то время как другие просто кажутся автору интересными, глубокими или занимательными. Автор надеется, что читателю они тоже окажутся полезными.
Наилучшая ссылка на "дополнительное чтение", которая лучше всего дополняет материал данной книги — это исходный код ядра. Для работы с ОС Linux у нас есть неограниченный доступ к полному исходному коду ядра современной операционной системы. Не принимайте это как должное! Разберитесь с ним! Читайте код! Пишите код!
Книги по основам построения операционных систем
В этих книгах рассмотрены принципы работы операционных систем в объеме учебных курсов. В них описываются основные понятия, алгоритмы и проблемы, связанные с построением высокофункциональных операционных систем, а также решения указанных проблем. Все эти книги могут быть рекомендованы, но если нужно выделить одну, то это, конечно, книга H. Deitel.
• Deitel H., Deitel P. and Choffnes D. Operating Systems. Prentice Hall, 2003. Прекрасная книга по теории операционных систем с отличными примерами из теории и практики. Автор помогал в техническом редактировании этой книги, что, может быть, и является причиной его предвзятого отношения, но все же хочется верить, что от этого книга стала значительно лучше.
• Tanenbaum Andrew. Operating Systems: Design and Implementation.. Prentice Hall, 1997. Хорошие начальные сведения об основах построения, принципах работы и реализации Unix-подобной операционной системы Minix.
• Tanenbaum Andrew. Modern Operating Systems. Prentice Hall, 2001. Детальный обзор стандартных проблем разработки операционных систем, а также обсуждение многих концепций, которые используются в современных операционных системах, таких как Unix и Windows.
• Silberschatz A., Galvin P. and Gagne G. Operating System Concepts. John Wiley and Sons, 2001. Также известна, как "книга про динозавров", в связи с тем что на обложке нарисованы динозавры, которые не имеют никакого отношения к теме. Хорошее введение в основы построения операционных систем. Книга часто перерабатывается, но все издания должны быть хорошими.
Книги о ядрах Unix
В этих книгах описываются принципы работы и особенности реализации ядер Unix. В первых пяти рассмотрены конкретные варианты Unix, в двух последних — общие моменты всех вариантов Unix.
• Bach Maurice. The Design of the Unix Operating System. Prentice Hall, 1986. Обсуждение особенностей построения операционной системы Unix System V, Release 2.
• McKusick M., Bostic K., Karels M. and Quarterman J. The Design and Implementation of the 4.4BSD Operating System. Addison-Wesley, 1996. Описание особенностей построения и реализации операционной системы 4.4BSD от разработчиков этой системы.
• McKusick M. and Neville-Neil G. The Design and Implementation of the FreeBSD Operating System. Addison-Wesley, 2004. Основы построения операционной системы FreeBSD 5.
• Mauro J. and McDougall R. Solaris Internals: Core Kernel Architecture. Prentice Hall, 2000. Интересное обсуждение основных подсистем и алгоритмов работы ядра ОС Solaris.
• Cooper С. and Moore С. HP-UX 11i Internals. Prentice Hall, 2004. Обзор внутреннего устройства операционной системы HP-UX аппаратной платформы PA-RISC.