Minix Kernel Internals

This course must have been last taught by me, if I recall correctly, in 2008 in a deemed university in Andhra Pradesh, India. I think I taught this course for two or three batches/years. The class was I. M.Tech. (Comp. Sc.) and class size was typically around 14 to 18 students.

Essentially this was a course designed to give students a feel of kernel internals design and code.

One interesting discussion I had with other faculty was on whether we should have a Minix Kernel Internals course or a Linux Kernel Internals course. The important points related to my view of that discussion are available here.

Prerequisites for the Course

C Programming including debugging skills, User level knowledge of Unix (Unix commands like ls, chmod, mkdir, kill etc.) and theoretical knowledge of modern operating systems like Unix./Linux Kernel Internals. Note that students typically would learn such theory of modern operating systems in a separate theory course done either prior to this course or in parallel to this course.

Course Book

“Operating Systems – Design and Implementation”, Second edition by Tanenbaum and Woodhull, http://minix1.woodhull.com/osdi2/.

A later edition, 3rd edition, is available, http://www.flipkart.com/operating-systems-design-implementation-3rd/p/itmdytczcxvugj3h. But I do not know whether it is appropriate to use that book for this course material. [BTW Instructor resources (would be useful for students too, I guess) is available here on request, http://www.pearsonhighered.com/educator/academic/product/0,3110,0131429388,00.html#resources. This course site of a US university, http://www.cise.ufl.edu/~nemo/cop4600/, seems to be using the 3rd edition book as the main course book. The site has slides which can be downloaded.]

Note: While the course book has some theory of Operating Systems as well, this course focuses only on design and implementation of Minix. A separate theory course on Operating Systems is done by students either prior to this course or in parallel to this course.

Minix website: http://www.minix3.org/

Teaching with Minix Howto (has links to Minix course websites): http://minix1.woodhull.com/teaching/

Chapter Wise Study Notes

Chapter 1 – Introduction

If time permits the whole chapter should be read. Sections 1.2.5 – History of Minix, 1.3 – Operating System Concepts, 1.4 – System Calls are important sections which MUST be read (they are a reading assignment for this course).

Given below are some notes of the important parts of this chapter for this course.

History of MINIX

  • Tanenbaum writes MINIX from scratch using same system interface as UNIX but the implementation being completely different from AT&T’s UNIX thereby avoiding licensing issues and making MINIX suitable for study in edcuational institutions (like universities). MINIX stands for mini-UNIX.
  • Students can dissect a real operating system – MINIX – like biology students dissect frogs.
  • MINIX code is meant to be studied and be readable unlike UNIX where the objective of the design was efficiency.
  • This book’s MINIX version is based on POSIX standard.
  • MINIX is written in ‘C’ programming language.
  • MINIX initial implementation was for the IBM PC; subsequently ported to other machines/architectures like Macintosh and SPARC
  • Running MINIX similar to running UNIX; commands like ls, cat, grep and make as well as the shell are available.
  • Finnish student, Linus Torvalds, wrote a MINIX clone called LINUX to be a “feature-heavy production system” as against an educational tool that MINIX is.

Operating System Concepts

  • System calls are the interface between OS and user programs

Processes

  • A program in execution is a process
  • A process had address space – memory locations which the program can read from and write to
  • Address space is divided into code – executable program, data and stack; (stack is also data but of a different type)
  • Each process has a set of registers including program counter and stack pointer needed to run the program (using the underlying processor and processor instructions).
  • In a time-sharing system OS suspends one process, saves its process state, and starts/re-starts another process; the suspended process is re-started after some time at which time first its process state must be restored; process table entry stores the process state when the process is suspended
  • Command interpreter or shell has to execute programs; as part of program execution and control of that execution it needs a system call to create a process which will execute the program; on the program finishing a system call is needed for the process to terminate

Files

  • Broad category of system calls that deal with the file system
  • system calls are available to create and remove files; to open, read, write and close files
  • hierarchical directory structure: system calls available to create and remove directories; put an existing file in a directory, remove an existing file from a directory; a directory itself can be a file entry in another directory thereby providing for a hierarchical directory structure
  • 9-bit file protection code giving rwx permissions for owner, group and others

Shell

  • Command interpreter is called shell; it is the primary interface between user on terminal giving commands and the operating system
  • On user login a shell is started up for the user; typical prompt is $; user types in command at this command prompt
  • input and output file redirection via < and >

Memory Layout of Process

  • A process has three segments in its address (memory) space – text (or code), data and stack; data segment grows upward and stack segment grows downward (see fig. 1-11)

Monolithic Operating System with User Mode and Kernel Mode

  • Most CPUs have (at least) two modes – kernel mode where all instructions are allowed and user mode where some instructions are prohibited
  • Special trap instruction in the CPU instruction set known as kernel call or supervisor call switches the CPU from user mode to kernel mode
  • Parameters of the kernel call/supervisor call instruction are used to identify which system call should be invoked

OS components

  • Four components of Minix OS – process management, I/O device management, memory management and file management; course book chapters are also on these lines.

Lab work: Installing VMWare on Linux and then installing Minix on VMWare (Instead of VMWare for some years/batches Bochs emulator was also used). One great advantage of using Minix on VMWare for this course was that Minix kernel crash (due to modified kernel code of students typically) only crashed the virtual machine. Bringing up a new virtual machine Minix (with stable kernel) on VMWare was quick and straightforward. This contrasts very positively with the time lost on Minix kernel crash on physical machine and resultant time and effort to bring up Minix (with stable kernel) on the physical machine.

This link provides info. on installing Minix on VMWare and other virtual machine/emulator software, and has some other related support info. too: http://minix1.woodhull.com/hints.html#emul-virt.

Chapter 2 – Processes

Section 2.5 – Overview of Processes in Minix and section 2.6 Implementation of Processes in Minix (pages 93 to 147) are very vital sections of the book. These are the first, and perhaps the most important, sections that delve into Minix kernel source code. These sections have to read and understood in conjunction with the actual source code they refer to.

[The Minix source code listing is provided in the book itself as Appendix A – The Minix Source Code from page 523 to page 903 (380 pages) consisting of 27646 lines of (line numbered) code. Appendix B is an Index to Files (pages 907 and 908) which gives the filenames and starting line number in listing for files in include directory, kernel, memory manager and file system. Appendix C is an Index to Symbols (Pages 911 to 923) giving symbol name and listing line number. These symbols include function names and macros (#define).]

[I discussed these sections (2.5 and 2.6) in class and also walked through appropriate code where required. These were intense sessions and required high level of commitment from students if they wanted to really benefit from the course.]

These sections involve some assembler code. Some, if not all, the detailed pages/sub-sections are listed below:
a) stackframe_s structure: Page 115 Lines 4537 to 4558 (Lines refer to the source code listing included as Appendix A)
b) mpx386.s Page 124
c) Section 2.6.7: Interrupt handling in MINIX, Pages 128 to 137
d) Section 2.6.10: Hardware-Dependent Kernel Support Pages 142 to 145
e) Section 2.6.11: Utilities and the Kernel Library, Pages 145 to 147

The assembler code (if I recall correctly) is Intel 386 code. So there must be some understanding of Intel 386 architecture and instructions. The students would have taken a computer architecture course in the past which would have covered Intel 386 architecture and instructions to some extent, at least.

The wikipedia page, http://en.wikipedia.org/wiki/Intel_80386, seems to give a decent overview of Intel 386.

An Intel 386 programmer’s reference manual is available here: http://intel80386.com/. From this reference these two chapters are important for understanding the assembler code (if I recall correctly) in Minix source code referenced by the course book:

Lab. Assignment: Change process scheduling algorithm – I am afraid I don’t recall the details now – could be changing scheduling from round-robin to lottery scheduling (random).

Assessment: Ideally assessment for this very intense chapter would involve quizzes/viva-voce to examine a student’s understanding of the design and implementation details covered by this chapter. However, I have to be honest and state that very few students of the batch had the time, inclination and/or resolve to get that deep into Minix design & code. Most students chose to focus on doing the lab. assignments where one could do some fiddling with part of the code without having got a full understanding of the design and code covered in this chapter. I could not blame the students much as the time available for this lab. course in terms of both study time and computer lab. time was limited (competition from other courses and other activities that students had to get involved with). Having said this, I must also say that the objective of exposing most students to the complexity of kernel internals of Minix got achieved with intense coverage in class of some of the design & code covered by this chapter. So, if in future, say for a IInd M.Tech. (CS) project, a bright student chose to do an OS component design & implementation project (like a filesystem implementation/port to Minix), the background exposure would have been provided by this course for the student to take up the challenge.

Chapter 3 – Input/Output

In this course we do not focus much on this chapter. However the following sections must be read as they may be useful (are useful, if I recall correctly) for better understanding of later chapters:

  • 3.4.1 Interrupt Handlers in Minix
  • 3.8.3 Overview of the Clock Driver in Minix
  • 3.10 The System Task in Minix

Chapter 4 – Memory Management

This whole chapter is an important part of this course and so the whole chapter should be read. In particular the following sections must be studied in-depth:

  • 4.6.3 Segmentation with Paging: The Intel Pentium
  • 4.7 Overview of Memory Management in Minix (including subsections)
  • 4,8 Implementation of Memory Management in Minix (including subsections)

The following topics were discussed in depth in class – fork system call implementation; Process scheduling, process table, process memory map and Translation. Viva-Voce/Quiz was conducted to test understanding of these topics by the students.

Lab. Assignment 1: Modify memory allocation algorithm from first fit to best fit.

Lab. Assignment 2: Add a new system call in MINIX (in MM). The system call should take in, say, two parameters, and have a return value. The system call’s service may be a very trivial one as the objective is to understand how add a new system call to Minix (and then test it, of course).

Lab. Assignment 3: Add a new system call in MM that gets the memory map for the requested process.

 Chapter 5 – Filesystems

Due to lack of time this chapter was not covered. However, if students have the time and inclination this chapter should be read and understood. [A couple of students who underwent this course in Ist. M.Tech. (CS) took up implementation/port in Minix of a filesystem supported on Linux but not in Minix (2.0). That project involved understanding this chapter and related code very well.]

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s