Paradigm Shift in Kernel Programming
内核编程的范式转移
Raymond Kwan
这篇小文章主要分析了操作系统内核编程中主要使用C和命令式范式的原因，同时讨论了其他范式在内核编程中的可能性。新的范式在这方面作出了很多有益的尝试，同时也是将来操作系统的一个发展方向，但当前仍然有很多问题需要克服。关于编程范式，可以参阅 Programming Paradigms 编程范式-笔记。有空再将本文的主要观点翻译成中文。
Introduction
Traditional imperative paradigm is prevalent in operatingsystem kernel programming. This essay attempts to analyze the reason behind thedominance of imperative paradigm and to discuss the suitability of otherprogramming paradigms.
Background
An operating system (especially its kernel) plays the role ofintermediary of user of a computer and the computer hardware and providesnecessary services to other programs. Basically an operating system is also aprogram, or to be precise, is a collection of software. Therefore it isdeveloped with certain programming languages and programming paradigms. From1950s, when operating systems were first introduced to the world, till presentmost mainstream kernels of operating systems are developed by C or othersimilar languages1. Though C can support object-oriented factors, itis generally accepted as imperative or procedural programming. There are 4major kinds of programming paradigms: Imperative, Object-oriented, Functional,and Logic2. However, besides imperative programming, otherprogramming paradigms are less involved in this particular area.
TheocraticImperative Programming
From 1930’s on, Turning Machines and Von Neumann architectureas well as other pioneering theories greatly affect how people design an actualcomputer.
Inprinciple, computers can only understand machine codes that present data andinstructions in binary sequences. Developing programs in machine codes could beof great difficulties. Assembly languages translate binary sequences intomnemonics and memory addresses, making programming more understandable for programmers.Both of these languages are ordering machine to execute some commands in verystrictly organized sequences. However, one has to be familiar with the hardwareso that he or she can write codes that can be understood by the hardware.Operating system intertwined with high-level language (e.g. C) was thenoriginated to ease this problem. On one hand, kernel, as the main component ofoperating system, was developed to provide an abstract layer of the hardwarehence making the hardware resources more accessible to the programmers. On theother hand, C was designed to replace assembly language with a relatively straightforwardcompiler during the development of Unix. By 1973, most of the Unix kernel waseven rewritten in C. Despite the fact that C is a great progress compared tomachine codes and assembly languages, these three languages work in a similarway: imperative way.
Tracing back to the root of contemporary operating systems,most mature and popular systems have been developed on the similar foundationand architecture and unsurprisingly share the same development tools andprogramming paradigms. At 1970’s, there were not much choices or even only onechoice in some way: C and imperative programming.
NewAttempts
Later on, new programming paradigms emerged. When programminglanguages gradually supported various paradigms, attempts to rewrite operatingsystems in new ways have been proposed. Object-oriented Programming is ageneral direction in this diversion. C++, the successor of C, more or lesschallenged the position of C in operating systems1, but nowadaysmost kernels still contains overwhelming quantities of C. Some designers‘refused’ to adopt too many new changes. Linux even went to the extreme that noC++ was applied.’ C++ is a horrible language.’ for the reason that C++ is less efficientand more error-prone. C understands low-level system and thus a must choicerather than C++. According to Linus, ‘And limiting your project to C means thatpeople don't screw that up, and also means that you get a lot of programmersthat do actually understand low-level issues and don't screw things up with anyidiotic "object model" crap.’4, Object-oriented paradigmseems frothy and unsuitable for dealing with hardware. Meanwhile otherscould not resist the temptation. The following projects introduced are fewamong the new tide:
· JOS,free and open operating system based on Java, aims to run with only Java ByteCodes. No update since 20105.
· JNode,free and open operating system based on Java, aims to run Java application infast and secure environment. However, the n-Kernel was completely written inassembly language. Also, part of the Virtual machine was written in assemblylanguage. Whereas the memory manager and IO ports were finished in Java6.
· Phantom Operating System, ‘a huge pool of fine-grainedobjects’, based on virtual machine thus not all programming languages aresupported7.
· Cosmos (C# Open Source Managed Operating System),an operating system development kit, support languages like VB.NET, Fortran,Delphi Prism, IronPython, F#. Its kernel routine is primarily written in C#8.
· The SPIN Operating System ‘is an operatingsystem that blurs the distinction between kernels and applications.’ Based onModula-39.
Among all those efforts,Microsoft’s ‘Singularity’ project10 is the most eye-catching one. ‘Inthe Singularity project, we have built a new operating system, a newprogramming language, and new software verification tools. The Singularityoperating system incorporates a new software architecture based on softwareisolation of processes. Our programming language, Sing# , is an extension of C#that provides verifiable, first-class support for OS communication primitivesas well as strong support for systems programming and code factoring.”11
There are three basic features of‘Singularity’: software-isolated processes, contract-based channels, andmanifest-based programs. ‘Singularity’ tried to rebuild the Operating Systemarchitecture from the ground up and all these features aimed to ensure securityand dependability rather than extreme efficiency. Although the main body of‘Singularity’ consists of Sing#, ‘Approximately 6% of the Singularity kernel iswritten in C++, consisting primarily of the kernel debugger and low-levelsystem initialization code. ‘11
Generally speaking, the legacy ofimperative paradigms can be indistinctly found on these new attempts. Theseattempts are less popular, partly due to lack of hardware supports andcommercial promotions. Rarely can these attempts can last long unless they arelead by huge companies or leading researching institutes.
FutureOS, a Dilemma
New challenges encourage advent offresh ideas. Operating system also evolves with new theories. It seems to beendless if one tried to figure out what is the best design decision foroperating system. So does the programming paradigms decision. Even though theremaybe no answer for such question, the following questions are more or lesseasier to determine.
1. Whetherthe kernel with specific paradigm is supported by the hardware?
2. Whetherthe kernel with specific paradigm is efficient for the hardware?
3. Whetherthe kernel with specific paradigm is easy for developers to develop, maintainand extend?
C and imperative paradigm answerthese questions imperfectly (mostly due to the third question) but they areprevalent and still remain an acceptable choice. C is relatively easier tocompile, lower level and hence enjoys high portability.
C compliers are nowadays prevalenton most hardware; this is one significant reason that C dwarfs other languages,e.g. Java, in kernel programming. What’s more, despite the fact thathigher-level programming languages usually support new paradigms, they could betoo abstract to be understood by the hardware therefore making them lowefficient. For example, Java is low efficient and consume much more memorycompared to C and C++12. Other programming paradigms do have their ownadvantages and are used in various situations accordingly. They are more abstract and provide a morehuman view for programmers. Also, they are less ‘trivial’ and low-level, focusmore on result instead of details of hardware execution. More extendable,highly modularized, more accessible to programmers, are the general features ofother programming paradigms, which gain more points for other programming paradigms.
Modern kernel are faced with suchdilemma: if it is built in a abstract way, programmers can understand it moreeasily whereas the hardware could find it harder to interpret and execute. Andvice versa if it is built in a detailed and low-level way. As technologyadvances, the trade-off has been moving to the abstract side: from machinecodes to assembly language and lately to C. Based on current techniques andcomputer hardware, C is the exact sweet spot for being a kernel language,because it is neither too low nor too high. It is reasonable to expect thatthis shifting will be continuous, as well as causing the paradigms to shift.However, it is never easy to decide when is the exact point to replaceimperative with other paradigms. It will maybe come after new forms of hardwaredesign (bio-circuits or DNA Computing13) or completely new operatingsystem theories. It may also come in a gradual way that no one even realizesthat. But there is one thing of sure: choosing which paradigms in kernel is worthof reconsidering in the coming years.
Conclusion
Imperative has been dominating inkernel programming and its superiority in this field and will remain still fora while. There are some attempts toapply or combine other paradigms but they lack significant breakthroughs sofar. Future kernel designers will have to keep a constantly shifting balancebetween all these paradigms to cater developers and hardware.
References
1. VincentLextrait. The Programming Languages Beacon. Last updated April 2012. [Cited 15November 2012]. Available from: http://www.lextrait.com/vincent/implementations.html
2. N?rmark,Kurt. Overview of the four main programming paradigms. Last updated July 2010.[Cited 15 November 2012]. Available from: http://people.cs.aau.dk/~normark/prog3-03/html/notes/paradigms_themes-paradigm-overview-section.html
3. Silberschatz,Galvin, Gagne. Operating System Concepts. 8th Edition. New York: JohnWiley & Sons; 2009.
4. TORVALD,L.,(torvalds@linux-foundation.org)2007.Re:[RFC]Convertbuilin-mailinfo.c to use The Better String Library. Email to: Newsgroups: gmane.comp.version-control.git.Available from: http://thread.gmane.org/gmane.comp.version-control.git/57643/focus=57918
5. JOSProject. A Free Java Based Operating System. Last updated May 2010. [Cited 17November 2012]. Available from: http://jos.sourceforge.net
6. EwoutPrangsma, Levente Santha. Java New Operating System Effort. Last updatedJanuary 2009. [Cited 17 November 2012]. Available from: http://www.jnode.org/
7. Dmitry Zavalishin. Phantom Operating System. Last updatedDecember 2011. [Cited 17 November 2012]. Available from: http://www.dz.ru/en/solutions/phantom#09
8. Chad Z.Hower. Develop Your OwnOperating System in C# or VB.NET. Last updated August 2010. [Cited 17 November2012]. Available from: http://www.codeproject.com/Articles/99928/Develop-Your-Own-Operating-System-in-C-or-VB-NET
9. Departmentof Computer Science and Engineering,University of Washington. The SPIN Operating System. [Cited 17 November2012]. Available from: http://www-spin.cs.washington.edu/
10. MicrosoftResearch. Singularity. [Cited 19 November 2012]. Available from:http://research.microsoft.com/en-us/projects/singularity/
11. Hunt GC.and Larus JR. Singularity: Rethinking the Software Stack. ACM SIGOPS OperatingSystems ReviewYear of publication 41. 2 (2007) :37-49.
12. Prechelt,Lutz. "Comparing Java vs. C/C++ efficiency differences to interpersonaldifferences." Communications of the ACM 42.10 (1999): 109-112.
13. Amos,Martyn. Theoretical and experimental DNA computation. Springer, 2005.