Class 22: Microkernels and Beyond

Posted: Thu 17 April 2014

Don't forget to submit a Project Submission Option by Monday, 21 April (4:59pm). But, the earlier you submit the more likely you are to receive your first choice. Teams that do not submit this form on time, will be required to do whatever I choose, and also take a final exam.

Operating System Design

What are the design tradeoffs one should consider in putting something in the kernel?

Should the file system be in the kernel?

Microkernels

What aspects of an operating system must be in the kernel?

What are good reasons to put anything else in the kernel?

From The Tanenbaum-Torvalds Debate:


From: [email protected] (Andy Tanenbaum)
Newsgroups: comp.os.minix
Subject: LINUX is obsolete
Date: 29 Jan 92 12:12:50 GMT
 
I was in the U.S. for a couple of weeks, so I haven't commented much on
LINUX (not that I would have said much had I been around), but for what 
it is worth, I have a couple of comments now.
 
As most of you know, for me MINIX is a hobby, something that I do in the
evening when I get bored writing books and there are no major wars,
revolutions, or senate hearings being televised live on CNN. My real
job is a professor and researcher in the area of operating systems.
 
As a result of my occupation, I think I know a bit about where operating
are going in the next decade or so. Two aspects stand out:
 
1. MICROKERNEL VS MONOLITHIC SYSTEM
   Most older operating systems are monolithic, that is, the whole operating
   system is a single a.out file that runs in 'kernel mode.'  This binary
   contains the process management, memory management, file system and the
   rest. Examples of such systems are UNIX, MS-DOS, VMS, MVS, OS/360, 
   MULTICS, and many more.
 
   The alternative is a microkernel-based system, in which most of the OS
   runs as separate processes, mostly outside the kernel.  They communicate
   by message passing.  The kernel's job is to handle the message passing,
   interrupt handling, low-level process management, and possibly the I/O.
   Examples of this design are the RC4000, Amoeba, Chorus, Mach, and the
   not-yet-released Windows/NT.
 
   While I could go into a long story here about the relative merits of the
   two designs, suffice it to say that among the people who actually design
   operating systems, the debate is essentially over.  Microkernels have won.
   The only real argument for monolithic systems was performance, and there
   is now enough evidence showing that microkernel systems can be just as
   fast as monolithic systems (e.g., Rick Rashid has published papers comparing
   Mach 3.0 to monolithic systems) that it is now all over but the shoutin'.

Inter-process Communication

What are different methods you have used for inter-process communication? How expensive is each?

What can be done to make IPC less expensive?

Comparing Linux and Minix

Is Windows NT a microkernel?

David Black, David B. Golub, Daniel P. Julin, Richard F. Rashid, Richard P. Draves, Randall W. Dean, Alessandro Forin, Joseph Barrera, Hideyuki Tokuda, Gerald Malan, and David Bohman. Microkernel Operating System Architecture and Mach. USENIX Workshop on Microkernels, 1992.

How is IPC so fast on L4?

Jochen Liedtke. Improving IPC By Kernel Design. SOSP 1993.

Gerwin Klein, Kevin Elphinstone, Gernot Heiser, June Andronick, David Cock, Philip Derrin, Dhammika Elkaduwe, Kai Engelhardt, Rafal Kolanski, Michael Norrish, Thomas Sewell, Harvey Tuch, Simon Winwood. seL4: Formal Verication of an OS Kernel. SOSP 2009.

Kevin Elphinstone and Gernot Heiser. From L3 to seL4: What Have We Learnt in 20 Years of L4 Microkernels?. SOSP 2013.

How many microkernels are you carrying today?

Exokernels

Should an operating system do more than just manage resources?

Dawson Engler and Frans Kaashoek. Exterminate All Operating System Abstractions. Fifth Workshop on Hot Topics in Operating Systems, 1995.

Exokernel Talk Slides, 1998.

Homework or espionage? ("Mr. Kaashoek insists it was homework, not espionage.")

What's Next?

How should future operating systems be designed?

Bitter experience in the design of operating systems leads to the conclusion that radical changes must be made, both the way we think about functions of operating systems and in the way they are implemented. (Butler Lampson, 1969)

NATO Software Engineering Techniques Conference, Rome 1969.

comments powered by Disqus


Class 21: Bakers and Philosophers

Posted: Tue 15 April 2014

Project Design Meetings are this week. Your team should come to the design meeting prepared to explain what you are doing for your project and why, what you have done so far, your plan for finishing, and any questions you have.

Your team should submit a Project Submission Option by Monday, 21 April (4:59pm). But, the earlier you submit the more likely you are to receive your first choice.

Readings

The recommended text has a full chapter on Concurrency, including:

Concurrency and Threads
Thread API
Locks
Lock-based Concurrent Data Structures
Condition Variables
Semaphores
Common Concurrency Problems
Event-based Concurrency

These sections cover some of the topics we covered in class, as well as many other relevant and interesting topics. Because they use C with the pthread library, some of the specifics are quite different from Rust programming but the main ideas are the same (and Sarah and Robert are working on rewriting some of them for their project).

The main topic of the next class will be OS design focusing on microkernels and beyond. Much of the material will be based on this paper: Kevin Elphinstone and Gernot Heiser, From L3 to seL4: What Have We Learnt in 20 Years of L4 Microkernels?, SOSP 2013.

Mutual Exclusion

Why is it worthwhile to study mutual exclusion protocols?

Why is it a waste of time to study mutual exclusion protocols?

How hard it is to invent a protocol that provides mutual exclusion without liveness guarantees?

How does Dijkstra prove mutual exclusion?

What assumption does Lamport's solution give up that Dijkstra's solution relies on?

comments powered by Disqus


Class 20: Mutual Exclusion (Thu 10 April 2014)

Class 19: Synchronization (Tue 08 April 2014)

Class 18: System Calls (Thu 03 April 2014)

Class 17: Flash! (Tue 01 April 2014)

Class 16: Storage (Thu 27 March 2014)

Class 15: IronKernel Developers (Thu 20 March 2014)

Class 14: Entering Ring Naught (Tue 18 March 2014)


Pages

  • Amazon EC2
  • Challenges
  • Classes
  • Forum
  • Getting Started with Github
  • IRC
  • Open Discussion Forum
  • Pages
  • Problem Set 3 - Zhtta Server - Benchmarking
  • Projects
  • Problem Set 0 - Tutorial and Course Registration
  • Problem Set 1 - zhttpto Web Server
  • Problem Set 2 - The Good Auld Shell
  • Problem Set 2 - Exploration 1
  • Problem Set 2 - Exploration 2
  • Problem Set 3 - Zhtta Web Server
  • Problem Set 4 - IronKernel
  • PS4 - Setup Commands
  • Open Enrollment
  • Survey Comments
  • Syllabus
  • Forum
  • Using Materials
  • VirtualBox
  • Working on Github in cs4414
  • Setting up your Zhtta Server on EC2