2 Logistics
Location: GCB 208
Times: Tuesday, Thursday 3:30PM - 5:00PM
Instructor: Jonathan Appavoo
Office: MCS 284
Office Hours: Tuesdays 10-12 & Thursdays 10-12
0 Formal Course Description
During this hands-on course small teams of 2-3 students will design and build their own little multi-server operating systems on top of the L4Ka::Pistachio microkernel. The goal is to gain practical experience in applying the theory of operating systems to the design and implementation of a consistent and functioning set of operating system services that manage and abstract the hardware resources and provide a base system on which a robust user environment can be developed.
The lectures focus on different "building blocks" of operating systems such as: communication, multi-tasking/-processing, virtual memory management, and file services. Examples and case-studies found in contemporary operating systems are included. A major component of the course is the class project. The project gives the students the opportunity to design (and later implement in teams), their own little multi-sever operating system on top of the L4Ka::Pistachio microkernel. After the build environment, tools, and example code is presented, we focus on incorporating the building blocks from the lectures into our to-be-designed OS. Each student (or team, depending on enrollment) will present their own design ideas for one particular aspect. Expect several hours of work per week in order to produce a functioning implementation of the OS by the end of the course. There is no required text for the course.
Prerequisites:
A good understanding of OS concepts from CS 552 Operating Systems or equivalent. During the course you will be required to read and write C or C++ code. Basic programming skills in C will do; C++ is fine, however, the programming and debugging load will be high.
3 Evaluation
All students, including PhD students, will be required to attend the lectures, do the two small homework assignments, design and present a specific operating system service and take the take-home final exam. The remaining 50% of the grade will be based on a project component. Ph.D students may propose to the instructor a different individualized operating systems related project. However, you will be required to submit a detailed plan and evaluation scheme by the end of the third week of the course and it must be approved by the instructor.
4 Class Schedule
1 Acknowledgments
This course draws heavily from the work done by the L4 community and in particular this course is modeled after the Universität Karlsruhe System Design and Implementation course. A special thanks goes to Jan Stoess whose help and advice have been invaluable.
6 Resources
7 Documentation
There is no required text for the course. You may find the following books, papers and manuals, useful
Books on Operating Systems
D. Bovet and M. Cesati. Understanding the Linux kernel. O'Reilly & Associates, Inc.. 2nd edition. p639-640
A. Tanenbaum. Modern Operating Systems Prentice Hall, 2nd ed. 2001 . Bovet and M. Cesati.
General Multiserver Papers
A. Gefflaut, T. Jaeger, Y. Park, J. Liedtke, K. Elphinstone, V. Uhlig, J.E. Tidswell, L. Deller, and L. Reuther.The SawMill Multiserver Approach. In 9th SIGOPS European Workshop, Kolding, Denmark, September 2000.
Daniel P. Julin. The Mach 3.0 Multi-Server System Overview. July 1991
Micro-kernel Background
Levin, R., Cohen, E., Corwin, W., Pollack, F., and Wulf, W. 1975. Policy/mechanism separation in
Hydra. In Proceedings of the Fifth ACM Symposium on Operating Systems Principles (Austin, Texas,
United States, November 19 - 21, 1975). SOSP '75. ACM, New York, NY, 132-140.
DOI= http://doi.acm.org/10.1145/800213.806531
Wulf, W., Cohen, E., Corwin, W., Jones, A., Levin, R., Pierson, C., and Pollack, F. 1974. HYDRA: the
kernel of a multiprocessor operating system. Commun. ACM 17, 6 (Jun. 1974), 337-345.
DOI= http://doi.acm.org/10.1145/355616.364017
Liedtke, J. 1996. Toward real microkernels. Commun. ACM 39, 9 (Sep. 1996), 70-77.
DOI= http://doi.acm.org/10.1145/234215.234473
Liedtke, J. 1995. On micro-kernel construction. SIGOPS Oper. Syst. Rev. 29, 5 (Dec. 1995), 237-250.
DOI= http://doi.acm.org/10.1145/224057.224075
Additional L4 Micro-kernel details
Prof. Dr. Frank Bellosa, Raphael Neider, “Micro-kernel Construction Course”, Summer 2009, Universität Karlsruhe (TH), Department of Computer Science , System Architecture Group, http://i30www.ira.uka.de/teaching/courses/lecture.php?courseid=182
Lecture notes for above course http://i30www.ira.uka.de/~neider/edu/mkc/mkc.html
Naming
D. R. Cheriton and T. P. Mann. Decentralizing a global naming service for improved performance and fault tolerance. In ACM Transactions on Computer Systems Volume 7 (2), May, 1989.
Daniel P. Julin.Naming Facilities for Operating System Emulation in Mach 3.0, Aug 1991.
Threads, Scheduling
T. Anderson et. al. The Performance Implications of Thread Management Alternatives for Shared-Memory Multiprocessors., IEEE Transactions on Computers 38:12 1989
T. E. Anderson, B.N. Bershad, E.D. Lazowska, and H.M. Levy Scheduler Activations: Effective Kernel Support for the User-Level Management of Parallelism., ACM Transactions on Computer Systems, Vol. 10, No. 1, February 1992, Pages 53-79.
M. Auslander et al. Scheduling in K42 , IBM Research, http://www.research.ibm.com/K42, August 2002.
File Systems
Microsoft Corporation. Microsoft Extensible Firmware Initiative FAT32 File System Specification. FAT: General Overview of On-Disk Format. Version 1.03, 2000
R.Sandberg et al. Design and Implementation of the Sun Network Filesystem. Proceedings of the USENIX 1985 Summer Conference.
D. Giampaolo Practical File System Design Morgan Kaufmann Publishers. 1st edition (1999)
Virtual Memory Management
J. Moran, "SunOS Virtual Memory Implementation", European UNIX Users Group (EUUG) Conference, Spring 1988
Richard W. Carr and John L. Hennessy. WSCLOCK a simple and effective algorithm for virtual memory management, Proceedings of the eighth symposium on Operating systems principles 1981
Özalp Babaoglu and William Joy. Converting a swap-based system to do paging in an architecture lacking page-referenced bits, Proceedings of the eighth symposium on Operating systems principles 1981
F. Mehnert Dynamic Loading of Native L4 Programs, Proceedings of the Second Workshop on Microkernel-based Systems 2001
Device Drivers
M. Tsegaye and R. Foss A comparison of the Linux and Windows device driver architectures, Operating Systems Review 2004 2:38 p.8-33
Manuals
L4 X.2 API Reference Manual can found at http://l4ka.org/ for more recent versions.
IDL4 User Manual can also be found at http://l4ka.org/
A manual on the ELF binary format.
Notes on the original version GRUB are here (http://www.uruk.org/orig-grub/). Note that the version of GRUB that we are using is a modified version based on the original GRUB. There is also a note on the multiboot standard (http://www.uruk.org/orig-grub/boot-proposal.html) which describes how boot information is passed around during startup.
The reference manual for the original NS16550A.
NS16550A: Design and application considerations.
Intel 8295A Programmable Interrupt Controller (8259A/8259A-2). Intel Corporation, December 1988
Intel 82093AA I/O Advanced Programmable Interrupt Controller (IOAPIC) Intel Corporation, May 1996
vmplayer dev/vm.vmx
vmplayer test/vm.vmx
Virtual Private Ethernet
Virtual Private Serial Line
dev
test
Physical Host
Physical External Network.
Linux
OS*
The basic environment for this course is composed of two virtual machines. One “dev” and the other “test”. You will use VMWare player to execute both. The diagram above illustrates the virtual setup of the two virtual machines. To create this setup download the vms.tgz file and un-tar (tar -xzf vms.tgz) it to a working directory. This should create two subdirectories: dev and test. The “dev” machine/host will be used to do your development (edit and build), serve the boot images to “test” machine and allow you to interact with the “test” machine’s serial console. I recommend that you periodically backup your source from the “dev” machine to another location.
Issue the following command to start the “dev” machine: vmplayer dev/vm.vmx. Log into vmplayer console of the “dev” host with the user: user and the standard course password. This user has sudo privileges so you may run root commands from the user as you see fit using : sudo <cmd>. The default vm.vmx file that you can use on the ugrad machines does not have external network access. However, on your own physical host you might want to use dev/vm.vmx.nat to allow the dev host access to external networks. You may find this particularly useful if you want to install additional software. Eg. sudo apt-get install <pkg>. Once logged into the console determine the ip address of the “dev” host via the command /sbin/ifconfig. Then on the physical host open a new xterm and ssh into the “dev” host with the following command: ssh user@<ip>. From here follow the instructions in the README file ~user/README.553.txt. This will walk you through building an instance of the OS* template and installing into into the appropriate directories that will allow you to boot the “test” host with the instance. The README includes instructions on how to start a serial console window in which the “test” host’s output will appear and also how to start the “test” host instance. You may freely reboot or stop the “test” host via the vmplayer “reset” menu option under the “Troubleshoot” menu or the menu options to “Power Off and Quit”. WARNING you must cleanly shutdown the “dev” machine properly with the command: ‘sudo halt’ to ensure that the virtual disk that has your current work on it is safe. So when you are done working always shutdown both virtual machines appropriately. The following video show’s a screen capture of the above process (you might have to install a quick time player to view it): 553.mov.
Good Luck and HAVE FUN!!!!
----
Working on the ugrad machines:
You should find a user directory for yourself in /cs/coursedata/cs553/Users/<username>. You may use this as your working directory to host your vm images for this course. You will find a copy of the vms.tgz file in /cs/coursedata/cs553/Archive/vms.tgs. You should be able to directly untar this into your directory, Eg. cd /cs/coursedata/cs553/Users/$USER;tar -zxf ../../Archive/vms.tgz. At this point you should be able to follow the instructions above on the ugrad machines. WARNING: don’t forget to back up your work (eg. source code) from your vm image to some where safe like your CS home directory.
-----
Setting things up on your own machine
To get things working in your own environment you will need to ensure that the dev machine can bring up three communication interfaces: 1 serial line, 1 external ethernet and 1 private ethernet. The vmx files in the dev dir contain the config of these three lines. The following discusses each line.
A) serial line
Relevant lines from the vmx files
From dev/vm.vmx
serial0.present = "TRUE"
serial0.fileType = "pipe"
serial0.fileName = "/tmp/com_1"
serial0.pipe.endPoint = "server"
and
From test/vm.vmx
serial0.present = "TRUE"
serial0.fileType = "pipe"
serial0.fileName = "/tmp/com_1"
serial0.pipe.endPoint = "client"
The above configures the dev machine and the test machine to have a shared serial line connected between the them. It specifies that a named pipe should be used to simulate the serial line and that the dev machine should be the server side and the test machine the client side. Further more it explicitly names the file location for the named pipe as /tmp/com_1. This, of course, must match in both files for them to share the line. The above assumes a linux environment. If you plan to run on Window you must change the both files to look something like the following:
dev/vm.vmx:
serial0.present = "TRUE"
serial0.fileType = "pipe"
serial0.fileName = "\\.\pipe\com_1"
serial0.tryNoRxLoss = "FALSE"
serial0.pipe.endPoint = "server"
test/vm.vmx
serial0.present = "TRUE"
serial0.fileType = "pipe"
serial0.fileName = "\\.\pipe\com_1"
serial0.tryNoRxLoss = "FALSE"
serial0.pipe.endPoint = "client"
Please note I have not confirmed the windows config.... so try it out and let me know ;-)
B) External ethernet that connects the dev guest machine to your real host: ethernet0 on the dev machine
From dev/vm.vmx
ethernet0.present = "TRUE"
ethernet0.virtualDev = "vlance"
ethernet0.connectionType = "hostonly"
ethernet0.addressType = "generated"
This is a standard config for an virtual ethernet. Note however, it is specified to be "hostonly" meaning that the dev machine will only be able to talk to the real host an not any external ip address. This is the config required for the ugrad machines. You will find there is also a dev/vm.vmx.nat file which changes this value to "nat". On your own machine you are free to use that config as it will allow your dev host to communicate with the outside world.
C) Private ethernet connecting the dev and test machines. ethernet1 on dev and ethernet0 on the test machine:
From dev/vm.vmx
ethernet1.present = "TRUE"
ethernet1.virtualDev = "vlance"
ethernet1.connectionType = "custom"
ethernet1.vnet = "vmnet3"
ethernet1.addressType = "generated"
From test/vm.vmx
ethernet0.present = "TRUE"
ethernet0.virtualDev = "vlance"
ethernet0.connectionType = "custom"
ethernet0.vnet = "vmnet3"
ethernet0.addressType = "generated"
The main thing to note here is that the config explicitly names a custom network config "vmnet3". To get things working you will need to configure a custom network and update the vmx files if you do not use vmnet3. The following is the relevant config values for vmnet3 as it is configured on the ugrad machines:
grep VNET_3 /etc/vmware/networking
answer VNET_3_DHCP no
answer VNET_3_HOSTONLY_HOSTADDR 192.168.5.1
answer VNET_3_HOSTONLY_NETMASK 255.255.255.0
answer VNET_3_HOSTONLY_SUBNET 192.168.5.0
answer VNET_3_NAT no
answer VNET_3_VIRTUAL_ADAPTER yes
You will need to add similar lines to your vmware config. The VNET_3_HOSTONLY_* values 192.168.5.1, 255.255.255.0 and 192.168.5.0 should not actually matter as this network will only be used between the dev and test machine and the dev machine is configured statically to 192.168.1.1 on it (see /etc/network/interfaces on dev machine) and will use dhcp to assign an ip address to the test machine.
-----
X11
Additional note for windows users. If you do not have X11 installed then you will not be able to start xterms on the dev machine and have them on your desktop, given this, the default doscon will fail. An X11 server is not strictly necessary but will make your life more convenient see http://en.wikipedia.org/wiki/Cygwin/X and http://en.wikipedia.org/wiki/Xming for info about two X11 servers for windows. To operate without X11 use some ssh client (such as putty) to login to the dev host. By default the doscon script will attempt to run minicom in its own xterm (eg. xterm -geometry 80x40 -title testcon -bg black -fg gree -e minicom &). Howerver, you do not need to do this. Simply start another ssh login to the dev machine and start minicom by hand.
BTW another way around this is to start a vnc server on the dev machine and use a vncclient on your host to connect to it.
--------
COURSE WIKI
Added a wikipage for the course. You should be able to login with you bu id and kerbrose password. Use this as you like to exchange info with each other:
http://www.cs.bu.edu/tiki/tiki-index.php?page=CS553
5 Assignments
Assignment 1 : DUE Beginning of Class on Feb 9th
The assignment should be completed individually. You should each individually hand in your written answers to part A and a tar of your source code for part B.
Part A:
Download a copy of the L4 API manual from http://l4hq.org. (You will also find a copy in the development disk image). Read and understand the following chapters and sections.
-
•Chapter 1 Basic Kernel Interface
-
•Chapter 2 Threads
-
•Section 4.3 SpaceControl
-
•Chapter 5 IPC ( focus on 5.1, 5.4, 5.5 and 5.6 )
Afterwards you should be able to answer these questions:
1) KERNEL INTERFACE PAGE
What is the Kernel Interface Page?
Who creates it?
Can it be mapped?
How does one know where it is mapped?
2) THREADS AND ADDRESS SPACES
What types of thread ids exist?
What’s the difference between them?
Who is allowed to invoke ThreadControl and SpaceControl?
What parameters must be passed to ThreadControl to create: i) a thread within an existing address space; ii) a thread in a new address space.
How are address spaces created?
How are they destroyed?
3) IPC
What types of messages are supported?
How are they constructed?
Part B:
Follow the instructions in the Resources section of this web page to setup a build and test environment for yourself. Then complete the following:
Thread Creation
The locator service and the logging server are created as a thread within the root task address space. Create two new threads within the root task that display ’Hello World Thread #no’ using the logging server.
The testclient is created and started in a new address space. Build a second testclient binary. Keep in mind that this involves adding a new directory and replacing the link address of the new binary appropriate. The two testclients shall display ”Hello testclient #no” using the logging server.
Sending and Receiving IPC
Using the two threads you created in the first portion of the above and send a message with two DWORDs from the first thread (sender) to the second thread (receiver). The receiver adds the DWORDs together and sends the result back to the sender (reply). Both threads should display the following message via the logserver, the receiver the two received DWORDs and the sender the result.
NOTES:
L4 API functions: The naming convention is written down in the L4 API Manual (About the Manual-Using the API). In short, every function name that relates to a L4 system-call is prepended by ”L4_”.
Convenience functions: Please use the convenience functions for preparing and sending the message item.
Assignment 2 : DUE Beginning of Class on Feb 16th
In assignment 1 you have learned how to create threads and address spaces, and how to manually send IPC messages between threads. The following assignment will teach you to generate client and server communication code using the IDL4 stub code compiler. IDL stands for Interface Definition Language; the IDL4 compiler allows you to automatically create communication stub code for L4 clients and servers, based on a interface defined in CORBA IDL.
Build A Syscall Server
In L4, privileged system calls can only be successfully executed by privileged threads. In the current L4 implementation, all threads in the root task’s address space are defined to be privileged.
In this assignment you will develop a simple privileged syscall server that runs within the root task’s address space and exports an IPC interface to clients allowing them to invoke privileged system calls. You will define the interface in IDL, and leverage the IDL4 compiler to generate the interface code from your interface definition. The following steps outline the procedure; although the steps are specific to the syscall server, they may still serve as a rough guide for implementing new servers or interfaces.
1. Identify the privileged system calls.
Hint You can safely ignore MemoryControl and ProcessorControl; you won’t need them in SDI.
2. Identify the parameters and results of each privileged system call.
3. Create a new IDL file in sdios/if/ and place your interface description in it.
4. Create a server template in sdios/src/root using idl4 with the -t option.
-
5.Fill the functions in the server template as appropriate. 6. Start the privileged system call server as another thread in the root task.
-
6.Test it using your test clients from assignment 1.