NordU2002 - The 4th NordU/USENIX Conference
February 18-22, 2002 in Helsinki, Finland



UNIX Kernel Internals: Data Structures and Algorihtms, Part I

The instructor: Dr. Marshall Kirk McKusick

Who should attend:

This course provides a broad overview of how the UNIX kernel implements its basic services. It will be most useful to those who need to learn how these services are provided. Individuals involved in technical and sales support can learn the capabilities and limitations of the system; applications developers can learn how to effectively and efficiently interface to the system; systems programmers without direct experience with the UNIX kernel can learn how to maintain, tune, and interface to such systems.

This course is directed to users who have had at least a year of experience of using the UNIX system and the C programming language. They should have an understanding of fundamental algorithms (searching, sorting, and hashing) and dataq structures (lists, queues, and arrays). Students will not need to prove relationship with a source license holder, as source code examples will be taken from the freely distributable FreeBSD system.


This course will provide a firm background in the UNIX kernel. The course includes coverage of most BSD-derived kernels including the FreeBSD system, BSDI's BSD/OS, and Sun's Solaris. The POSIX kernel interfaces will be used as examples where they are defined. Where they are not defined, the BSD interfaces will be described and then related to other vendors' interfaces. The course will cover basic kernel services, process structure, virtual and physical memory management, scheduling, paging and swapping. The kernel I/O structure will be described showing how I/O is multiplexed, special devices are handled, character processing is done, and the buffer pool is managed. The implementation of the filesystem and its capabilities will be described. The filesystem interface will then be generalized to show how to support multiple filesystem types such as Sun Microsystem's Network File System (NFS). Due to time limitations there will be no coverage of the networking subsystem. The presentations will emphasize code organization, data structure navigation, and algorithms. It will not cover the machine specific parts of the system such as device drivers.


Dr. Marshall Kirk McKusick, writes books and articles, consults, and teaches classes on UNIX- and BSD-related subjects. While at the University of California at Berkeley, he implemented the 4.2BSD fast file system, and was the Research Computer Scientist at the Berkeley Computer Systems Research Group (CSRG) overseeing the development and release of 4.3BSD and 4.4BSD. His particular areas of interest are the virtual-memory system and the filesystem. He earned his undergraduate degree in Electrical Engineering from Cornell University, and did his graduate work at the University of California at Berkeley, where he received Masters degrees in Computer Science and Business Administration, and a doctoral degree in Computer Science. He is a past president of the Usenix Association, and is a member of ACM and IEEE.