Роберт Лав - Разработка ядра Linux

Опасность, связанная со сложностью алгоритмов

Очевидно, что будет разумным избегать алгоритмов, которые масштабируются, как О(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.

• 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.

• Vahalia, Uresh. Unix Internals: The New Frontiers. Prentice Hall, 1995. Отличная книга о возможностях современных Unix-подобных операционных систем, включая управление потоками и вытеснением кода в режиме ядра.

• Schimmel Curt. UNIX Systems for Modern Architectures: Symmetric Multiprocessing and Caching for Kernel Programmers. Addison-Wesley, 1994. Прекрасная книга о проблемах поддержки современных аппаратных платформ современными Unix-подобными операционными системами.

В этих книгах, как и в текущей, рассказывается о ядрах Linux.

• Rubini A. and Corbet J. Linux Device Drivers. O'Reilly and Associates, 2001. Прекрасная книга о том, как писать драйверы устройств для ядер Linux серии 2.4.

• Bovet D. and Cesati M. Understanding the Linux Kernel. O'Reilly and Associates, 2002. Обсуждение основных алгоритмов работы ядер Linux серии 2.4. Основное внимание уделено основополагающим принципам функционирования ядра.

• Mosberger D. and Eranian S. IA-64 Linux Kernel: Design and Implementation. Prentice Hall, 2002. Отличная книга, посвященная аппаратной платформе Intel Itanium и ядру Linux серии 2.4 для этой аппаратной платформы.

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

• Kogan M. and Deitel H. The Design of OS/2. Addison-Wesley, 1996. Интересный обзор операционной системы OS/2 2.0.

• Solomon D. and Russinovich M. Inside Windows 2000. Microsoft Press, 2000. Интересный взгляд на операционную систему, которая чрезвычайно отличается от Unix.

• Richter Jeff. Advanced Windows. Microsoft Press, 1997. Описание низкоуровневого и системного программирования под ОС Windows.

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

• Stevens W. Richard. Advanced Programming in the UNIX Environment. Addison-Wesley, 1992. Отличное, если не самое полное, обсуждение интерфейса системных вызовов Unix.

• Stevens W. Richard. UNIX Network Programming, Volume 1. Prentice Hall, 1998. Классический учебник по API сокетов операционной системы Unix.

• Johnson M. and Troan E. Linux Application Development. Addison-Wesley, 1998. Общий обзор операционной системы Linux и интерфейсов, которые специфичны для этой операционной системы.

Книги, которые не посвящены операционным системам, но имеют к ним прямое отношение.

• Knuth Donald. The Art of Computer Programming, Volume 1. Addison-Wesley, 1997. Бесценный курс по фундаментальным алгоритмам и теории вычислительных систем, который включает лучшие и не самые лучшие алгоритмы управления памятью. (Имеется русский перевод: Кнут Дональд Эрвин. Искусство программирования. Том 1. Основные алгоритмы, 3-е издание. — M: "Вильямс", 2000.)

• Kernighan В. and Ritchie D. The С Programming Language. Prentice Hall, 1988. Наилучшая книга по языку программирования С. (Имеется русский перевод: Брайан Керниган, Деннис Ритчи. Язык программирования С — M: "Вильямс", 2005 г.)

• Hofstadter Douglas. Godel, Escher, Bach: An Eternal Golden Braid. Basic Books, 1999. Глубокий взгляд на человечество через исследование различных предметов, включая компьютерные науки.

Эти WWW-сайты предоставляют последние новости и другую информацию, связанную с операционной системой Linux и ее ядром.

• Kernel Traffic. Отличный обзор сообщений в списке рассылки разработчиков ядра Linux (lkml) за последнюю неделю (очень рекомендуется). http://www.kerneltraffic.org/

• Linux Weekly News. Хороший сайт новостей о том, что произошло касательно ядра Linux за последнюю неделю, с прекрасными комментариями (очень рекомендуется). http://www.lwn.net/

• Kernel Newbies. Сайт "Kernel Newbies" — это проект сообщества разработчиков с целью предоставления информации и помощи начинающим хакерам, которые стремятся заниматься разработкой ядра. http://www.kernelnewbies.org/

• Kernel.org. Официальный архив исходных кодов ядра. Здесь также находятся домашние страницы многих разработчиков основных подсистем ядра с соответствующими заплатами. http://www.kernel.org/

• KernelTrap. Сайт, посвященный всему, что связано с ядром операционной системы, с большим уклоном в сторону ядра Linux. На сайте много информации о новостях и обзорах из области разработки ядра Linux. Здесь также в большом количестве размещаются интервью с ведущими разработчиками ядра. http://www.kerneltrap.org