Operating System Design
Fall 2010
Project
Organizational, Structural, Logical and Execution Relationships Between Important System Components in Linux Kernel Subsystems
A. Description of the Project
You are required to study the important system components, including important data structures, important functions and algorithms, and the various organizational, structural, logical and execution relationships between them, in one or more subsystems of the Linux kernel which provide some basic kernel functionality and clearly explain them. An important requirement is that you should try to draw as many as possible of your own diagrams, which illustrate, as many as possible of the following information:
A1. The names of the fields that connect the various data structures.
A2. Examples of data values in the various data structures which show their logical and
structural connections.
A3. Which part of the system they belong, or are executed in. For example, kernel-space/user-space; in-memory/on-disk; kernel-mode/user-mode, etc.
A4. Organizational and structural relationships.
A5. Logical relationships.
A6. Flow of execution and/or decision making.
A7. Changes in data values and/or organization structure at different stages of execution.
A8. Any other organizational, structural, logical and execution relationships
between the system components that may aid understanding of any important
aspect of the subsystem(s).
B. Examples of Diagrams of Linux Kernel Components and Their Relationships
Example 1. The diagram illustrating the data structures of in-memory VFS objects and on-disk objects and their relationships on slide 24 of the lecture notes OSD.4. This diagram illustrates A1, A2, A4 and A5.
Example 2. The diagrams illustrating the data structures of the internal structure of a small file system tree in Unix on slides 9 and 10 of the lecture notes OSD.4. These diagrams illustrate A2, A4 and A5.
Example 3. The diagrams illustrating the data structures of the Unix file system directory on-disk organization on slides 12 and 13 of the lecture notes OSD.4. These diagrams illustrate A2, A4 and A5.
Example 4. The diagrams illustrating the VFS mount tree of vfsmount Structures on slide 72 of the lecture notes OSD.4. These diagrams illustrate A2, A4 and A5.
Example 5. The diagram illustrating the ext2_sb_info data structure in Figure 18-4 on page 752 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A1, A3, A4 and A5.
Example 6. The diagram illustrating an example of the Ext2 directory in Figure 18-3 on page 749 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A1, A2 and A4.
Example 7. The diagram illustrating a buffer page including four buffers and their buffer heads in Figure 15-2 on page 615 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A1, A4, and A5.
Example 8. The diagram illustrating data structures for file memory mapping in Figure 16-2 on page 659 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A1, A4, and A5.
Example 9. The diagram illustrating the most important data structures related to signal handling in Figure 11-1 on page 426 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A1, A4 and A5.
Example 10. The diagram illustrating adding or removing a linear address interval in Figure 9-1 on page 359 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A4, A5 and A7.
Example 11. The diagram illustrating invoking a system call in Figure 10-1 on page 400 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A3, A4, A5, A6 and A7.
Example 12. The diagram illustrating the flow diagram of the page fault handler in Figure 9-5 on page 378 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A5 and A6.
Example 13. The diagram illustrating kernel components affected by a block device operation in Figure 14-1 on page 561 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A4 and A5.
Example 14. The diagram illustrating linking the block device descriptors with the other structures of the block subsystem in Figure 14-3 on page 587 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A1, A4 and A5.
Example 15. The diagram illustrating the runqueue structure and the two sets of runnable processes in Figure 7-1 on page 268 of "Understanding the Linux Kernel" 3rd Edition. This diagram illustrates A1, A2 and A4.
All of the diagrams in the book "Understanding the Linux Kernel" 3rd Edition are good examples of different types of diagrams that can help readers understand various aspects of how the various subsystems of the Linux kernel that provide some basic kernel functionality works.
C. What to Hand In
1. You are required to hand in both a hard copy and an electronic copy of the written report on the project described in A, including all the diagrams you have drawn.
2. You are also required to hand in both a hard copy and an electronic copy of the Linux source code files that relate to the report on the project described in A, further subject to the conditions in 3, 4 and 5 below.
3. In the hard copy of the Linux source code files, you are required to use a fluorescent marker to highlight:
3.1. The names of the data structures and any specific fields of the data structures, which are illustrated in your diagrams or explained in your report.
3.2. The most important statements in the source code that perform the functions that are illustrated in your diagrams or explained in your report.
4. If the Linux source code files that relate to the report on the project described in A total more than 30 pages, then the hard copy of the Linux source code that you submit should include only the following (there is no such restriction on the size of the electronic copy of the Linux source code files that you submit):
4.1. The data structures and any specific fields of the data structures which are illustrated in your diagrams or explained in your report which describe the data structures, together with a list of the names of the ".h" header files and source code line numbers in which they can be found.
4.2. The most important statements in the source code that perform the functions that are illustrated in your diagrams or explained in your report together with the procedure/function names, and a list of the names of the ".c" program files and source code line numbers in which they can be found.
5. In all cases, for both the electronic copy and the hard copy of the Linux source code files,
you should provide the Linux kernel version number, and the address of the website where
the source code can be found related to the Linux kernel subsystem(s) you have chosen at
the beginning of your report.
You are required to use the utility "submit" to submit the electronic version of the above to the directory: /cs/course/4221/submit/project
The hard copy should be handed in by Friday December 10, 2010 24:00 midnight.
- either give it to the secretary in the Department of Computer Science and Engineering Office to be put into my mailbox; or you may slip it under the door of my office CSEB 3018 (in the latter
case, you are responsible for making sure that the thickness of your hard copy allows it to be slipped under my office door).
D. Other Requirements
(a) You should try to organize your report in a way such that it is easy to understand and use. The reader should be able to find information on a particular topic as quickly as possible, and be introduced to important concepts and issues at a "higher level" first, before getting into "lower level" details.
(b) All the drawings must be produced electronically with a drawing program. All the drawings must be accompanied by figure numbers and captions.
(c) The report should contain in-text references to the portions of the highlighted source code in C.4.1. and C.4.2.above that are discussed in the report.
(d) The report must contain a table of contents, and must be clearly divided into sections and subsections, with section and subsection headings. Page numbers must be included.
(e) The report must clearly identify which sources of information you have used in which components of this assignment.
(f) If a good diagram/explanation on some aspect of the Linux kernel system/subsystem under consideration already exists in a book or paper that has been published by a publisher or posted on a website, you may include it together with the other drawings/explanations you have drawn/written yourself in your report; you may also add your own improvements on existing diagrams/explanations taken from various publications or postings. However, you must clearly identify the source of each original individual existing diagram/explanation that you have either improved upon or included with or without modification; and explain in detail exactly which improvements you have made to the original, if any, in your report. The identification and assembly of existing diagrams/explanations to form a more complete explanation of one or more subsystems of the Linux kernel is encouraged. If you have drawn a diagram or offered a written explanation that cannot be found anywhere else, you should explicitly identify it as such, as that is even more strongly encouraged.
(g) For this project, you should use some version of Linux kernel 2.6. You should indicate the particular version you are using, e.g., 2.6.11.
E. Evaluation of the Project
Your project will be evaluated according to:
(a) The quality, completeness, and originality of the diagrams, including how much information among A1-A8 listed above, have been illustrated for the important system components, including important data structures, important functions and algorithms, and the various organizational, structural, logical and execution relationships between them in the subsystem(s) of the Linux kernel that you have chosen to study.
(b) The overall quality, completeness, and originality of the combined graphical and written explanation, for the important system components, including important data structures, important functions and algorithms, and the various organizational, structural, logical and execution relationships between them in the subsystem(s) of the Linux kernel that you have chosen to study.
(c) The amount of effort and the degree of difficulty of the Linux kernel subsystem(s) involved.
(d) The clarity, readability and organization of the project report and importance/relevance of the highlighted portions of the provided Linux source code.