Memory management in Linux and Windows NT

Alin Dobra
dobra@cs

Project proposal

Memory management is one of the important issues in the design of an operating system; the way it is implemented being crucial from the overall performance, reliability and stability point of view. In these circumstances a close look at two of the newly emerged operating systems, Linux and Windows NT, can give an interesting insight at the current state-of-the-art methods in implementing memory management.

The purpose of this project is to analyze/compare the memory management in Linux and Windows NT operating systems with an emphasis on the virtual memory. Such a study can reveal interesting facts about different directions in this domain, results that can transcend the particular implementation of this two operating systems.

Four aspects will be considered: the conceptual framework (what particular algorithms, ideas are used in each OS), the implementation (since both Linux and NT source code are available), portability (both OS's run on more than one hardware platforms), and the performance (through synthetic and real tests).

Virtual memory in Linux and Windows NT

One of the best descriptions of the Linux Kernel is David Rusling's The Linux kernel and I will use it as a reference. An other noticeable description is Linux Kernel Guide .

For Windows NT Helen Custer's Inside Windows NT (Microsoft Press, 1993) is probably the most thorow description since it was written in collaboration with the WinNT designers. Chapter six of this book addresses the virtual memory problem. Other two articles, Inside Memory Management, Part 1 and Part 2 written by Mark Russinovich and Bryce Cogswell and published in Windows NT MAGAZINE are also a good reference.

The virtual memory systems in Linux and Windows NT have a number of common features (in fact present in most of the modern operating systems):

extensive use of the paging system of the modern processors to offer separate virtual memory space for each process to ensure isolation and protection
copy-on-write
shared memory
mapped files
page pinning (important pages are kept permanently in memory)
demand paging
external (user level) pager

There are, though, a number of fundamental differences between Linux and Windows NT:

Windows NT has a microkernel architecture, as opposed to the monolithic kernel of Linux, and the memory management is implemented in the microkernel. I expect that this has a negative impact on the execution time of system calls.
Windows NT uses working sets (the number of pages a program needs in memory to execute smoothly) as replacement policy as opposed to a global replacement policy used in Linux. It will be interesting to find out for what kind of applications workings sets are a disadvantage and in what situations they are clearly an advantage.
The Win32 API interface gives the application the possibility to manage the virtual memory somehow finer grained (alloc and commit) as opposed to the fact that in Linux is not possible to allocate virtual memory and not attach a physical support (memory or disk) for it. This can be both an advantage (programmer has more control) and a disadvantage (programmer has to much control so subtle bugs can be inserted in the programs).
In Windows NT the only elegant way two or more processes can share memory is through mapped files so a physical file has to be created for such a purpose. Linux implements IPC (Inter Process Communication) for which there is kernel support, so shared memory is a separate mechanism from mapped files.

Matthew Dillon, one of the FreeBSD designers, has made a critical review of Linux's Virtual Memory system in a posting on the linux-kernel use group.

Other memory management issues

Altho the main purpose of the project is Virtual Memory some other issues in memory management can be explored like cash management, TLB management, virtual memory fragmentation.

Review of the previous work

Little work has been done in comparing Linux and Windows NT from the memory management point of view and the tests that have been performed usually are not very precise or carefully designed.

There is some work in comparing systems that have common features with one of Linux or Windows NT. I will mention some of this work. The important thing about this is not their results (which might not be valid since this systems have evolved since then) but the methodology and tools used.

J. Bradley Chen and oth. compared NetBSD, Windows for Workgroups and Windows NT (The measured performance of personal computer operating systems, The Proceedings of the 15th ACM Symposium on Operating Systems Principles) and drew interesting conclusions. One of the interesting things used are the Pentium special (undocumented) counter registers that can help in very precise performance measurements.

A previous paper (The impact of Operating System Structure on Memory System Performance) of Chen and Bershad that compares Ultrix and Mach 3.0 with CMU's UNIX server is also relevant since a monolithic and a microkernel architecture are compared.

Some people have tried to use Lmbench benchmark to compare the performance of Linux and Windows NT. Aaron Brown has a nice paper (Operating System Benchmarking in the Wake of Lmbench: A Case Study of the Performance of NetBSD on the Intel x86 Architecture) about how to interpret the results of such a benchmark.

Other interesting papers that address the performance problem in an operating system are:

The Impact of Architectural Trends on Operating Systems Performance, Mendel Rosenblum, Edouard Bugnion, etc.
Experimental Comparison of Memory Management Policies for NUMA Multiprocessors, Richard Larowe Jr., Carla Schilatter Ellis
Memory System Performance of UNIX on CC-NUMA Multiprocessors, John Chapin, Stephen A. Herrod, etc.

Research questions, experimental methodology and expected results

I will address the following questions in this study:

How much does the microkernel architecture penalty is in the context of memory management
In what situations working sets have beneficial effects and when is not so convenient
What particularities of the two OS's can explain the experimental data (a close look at the source code will probably be the key)

I will run a number of synthetic and real programs in the spirit of the programs used in the previously mentioned papers to answer this questions. I will also look at the source code and the documentation (where available) in order to interpret the experimental results.

Some of the mentioned tests revealed in part the answers to this questions (e.g. microkernel architecture has quite a severe penalty as opposed to monolitic kernels). The tests I indent to do are somehow finer grained than the tests that are usually done. By correlating the results with the source code I hope to point out some interesting facts about some of the used methods.