[WARNINGS] link-id not found - [fmiosacomparativestudypartikernellandchapter1bootup|1 link-id not found - [fmiosacomparativestudypartikernellandchapter3scheduling|3 link-id not found - [fmiosacomparativestudypartikernellandchapter5memorymanagement|5 link-id not found - [fmiosacomparativestudypartikernellandchapter7deadlocks|7 link-id not found - [fmiosacomparativestudypartiiuserlandchapter8iolayers|8 link-id not found - [fmiosacomparativestudypartiiuserlandchapter10environmentlayer|10
Intro (I 1 2 3 4 5 6 7) (II 8 9 10 11) (D) (C) (B
I)
h1. Chapter 5: Memory Management
Allocating and managing memory is one of the primary tasks of an operating system. If there was just one process on the machine with plenty of memory to use, then the memory issue would be easy: the process talks directly to the physical memory using actual memory addresses. However, when you add multiple, simultaneous processes, multiple processors, and larger programs than the memory can hold at one time, you are faced with the need for a more complex memory management system.
h2. 1. Virtual Memory Basics
Let's start the discussion assuming there is plenty of memory. Managing this memory for multiprocessing machines is a full-time job, in and of itself.
Memory comes in three basic flavors:
Anonymous Memory
This is the typical form of memory people think of when they think of computer memory. It is memory allocated (set aside) for a process, or memory where the operating systems resides. This is also the memory that contains a processes' code, global data, stack and dynamic memory.
Files
Files often exist physically on a hard drive and are accessed as memory by using functions such as @mmap()@ (Section 6).
Permanently Allocated Memory
This is memory that is allocated for special uses, is also mapped, but is not managed since it usually is dedicated for the duration of operating system runtime. An example of this is a video frame buffer.
As processes are created and killed, anonymous memory and memory mappings pop up and go away regularly. If processes used physical memory alone without any structure or management, the many gaps that would form over time would result in a waste of memory space. Take, for example, the three processes, @foo@, @bar@, and @baz@. Suppose these processes fill the first 100 Kbytes of memory.
Now, assume @bar@ dies and process @bop@ starts.
As you can see, there is a gap between @foo@ and @baz@ while new processes continue to be allocated space at the end of inhabited memory. Since RAM is not infinite, some form of memory management is needed to make use of these gaps to recycle the memory.
As you can see in this diagram, @bop@ filled in the gap between @foo@ and @baz@. However, since @bop@ required more memory than was available in the gap left by @bar@, it had to be split up into two chunks. This management results in memory being scattered in chunks all over. If memory has been chopped up enough, a single process could be storing information in ten or fifty different chunks scattered around memory.
Another goal of memory management is for user processes to view memory as one contiguous entity, even though their memory is living within these scattered chunks in physical memory. Enter virtual memory (VM).
The best way to think of virtual memory is as a layer of abstraction between programs and physical memory space. Not only does this require a memory manager to connect the layers, it also protects physical memory from being accessed directly from user processes, thus minimizing corruption by user processes.
Two by-products of virtual memory are: providing an easy way to share memory between processes, and providing an easy way to swap rarely used memory to back-storage (on a hard drive or similar device; Section 5.3).
h2. 2. Paging
To keep memory chunks from getting broken up into smaller and smaller pieces, the size of a "chunk" is set to a standard. That way, they are created and erased in chunks of uniform size and contents may easily be moved from one chunk to another. These chunks are called pages. Surprisingly, when a process is executing, all of its pages do not have to be in physical memory at once - just those memory locations that are needed to execute the next instruction!
On a 32-bit system, addresses range from 0 to 2^32^. Each page is typically 4K bytes (4096 bytes) in size. Each virtual page is mapped to physical page via a page table. Each process has its own mappings, and so sharing is made possible by mapping different virtual pages to a single physical page.
Whenever a user asks to access an address, that virtual address must be translated to the physical address. Typically, the CPU has to do this for every single memory access; thus can really slow things down. Machines that implement virtual memory have a Memory Management Unit, or MMU, which does this kind of translating at the hardware level (outside of the CPU). One technique to speed up translations is to employ a Translation Lookaside Buffer (TLB) by the MMU. This is a buffer that caches common virtual/physical address conversions. A cache is storage that the computer has quick and easy access to, and is usually closer than the system bus (thus it has a lower access time than ordinary memory).
h2. 3. Swapping and Page Faults
There are times when a process' contents may need to be taken out of physical memory and stored on disk. This is called swapping. This is another important task that the memory manager may handle. Some occasions that constitute swapping are:
- The program is too big to fit in memory
- The process has blocked for a significant period
- Space is needed for higher-priority jobs
With virtual memory, swapping of the entire process is often not needed. Sometimes it is enough just to remove one or two pages from physical memory, leaving the process still able to run. As long as the memory references actually required are resident in memory, the process can continue to execute.
What happens when the CPU requests a page that is not in physical memory? At this point the MMU throws an exception called a page fault. This will then cause the memory manager to load in the page from external memory. This acts like a type of interrupt handler. When a page fault happens, the guilty thread suspends and the pager daemon takes over, recalling the needed page from the disk. Sometimes this method is used when a process is first created and executed. The process must be loaded into memory, but since the program is stored onto disk, numerous page faults will occur until it is sufficiently loaded. This technique is called demand paging.
A major consideration for page fault handlers is which policy should be used to determine which pages to swap out to disk when space is needed.
Not Recently Used
In this policy, the pager swaps out pages that are resident but not accessed for the greatest time. This requires, however, that the pager keep tabs on when a page was used, as well as a fast method of searching through the vast page table to find times and compare them. An option for this might be a tree with most recently used pages towards the top (return a page to the top after use), pruning only the leaves (lowest nodes).
FIFO and Second Chance
Pages are swapped on a first-loaded-first-purged basis. This means that pages that are oldest are pruned first. In the case that a page slated for removal is actually commonly or recently used it can be skipped and given a second chance.
Clock
This algorithm is similar to the round robin scheduling algorithm (Section 34). Imagine all of the pages are arranged in a circle where the swapper (synonymous for pager) goes from page to page like the hands on a clock. If this minute-hand of death comes to a page that is in use it skips over it and moves on.
Least Recently Used
This is similar to NRU (Not Recently Used). However, the pager swaps out pages that have been used the least since a certain point in time. This requires the pager to keep tabs of the times pages are accessed. This, and the search, both add to excessive overhead making this method very expensive.
Random
This is the easiest method to implement but it is seldom used. The pager picks a page at random to swap out. If the page is in use, or highly used, it can be skipped.
h2. 4. Page Tricks
Here are some useful data structures that are commonly used by a memory manager that works with pages.
Clean/Dirty Page Bits
When swapping out a page, the swapper must write the page that's in memory onto the disk. But what if the page wasn't altered while in memory? Why write it back to the disk if nothing is different? This is called a clean page. Only if the page is dirty would the pager bother writing it back to disk.
Pre-Paging
Each process has its own set of pages that it uses in the course of a typical execution run. This set of pages is called that process' working set. Sometimes, the CPU spends a lot of time handling page faults to keep pulling in pages for this set. Pre-paging is a technique that involves loading the entire working set of a process before it is run, thus combining the entire loading-into-memory procedure into one operation, cutting down on the expensive page-fault calls during execution.
Page Protections
When pages are being shared or passed around, there should be a method to protect them. Also, having a means of informing other threads, and the pager, of some thread's intentions on a page would be useful. These intentions, also called page protections, can be labeled as read-only, read/write, none, locked, executable, etc. Read-only pages will not allow a process to write to it. Locked pages, also called pinned pages, are flagged to stay in memory.
Page Swap Allocations
There are two basic scopes for page allocations.
1) Local page allocation: If a process needs a new page to be retrieved, one of its own pages is swapped out to disk make space for the new page.
2) Global page allocation: If process @foo@ needs a new page the pager swaps out any page (could be process @bar@'s page or process @baz@'s page, etc.) to make room.
Local is useful because it allows for control of specific memory divisions among processes. For example, if processes @foo@, @bar@, and @baz@ are each allotted 5 pages then they will always have 5 pages. If global is used then the allotments for those processes will vary depending on those processes' individual working sets. So suppose process @foo@ started requiring more and more memory. A global allocation system will give @foo@ more and more pages, possibly taking them from @bar@ and @baz@ if memory is low. However, if local allocations were being used, @foo@ would start faulting often because its page allotment is limited.
Mixing these two together can allow for dynamically controlling specific page allotments. If a process starts spitting out a lot of page faults, or its Page Fault Frequency (PFF) increases, then the memory manager could readjust the allotments globally while using local allocation to keep the processes within those new allotments.
Page Size
Page size is another consideration when designing a memory management system. If the page size is too small then the page tables get too big, adding to the management overhead, as well as storage of the tables. However, pages that are too large may result in wasted space because the pages may more often take up more space than the average process will need. The most widely used size is 4k (4096 bytes).
h2. 5. Segmentation
Segmentation is another useful tactic when approaching virtual memory. Instead of a process putting all of its information in one memory space, it splits that space into segments. These logical segments are individual virtual memory spaces, each with base address starting at 0. The way a programmer might use segments within their program is to put all of the variables in one segment during execution, all of the constant data into another, the stack into another, and the actual code into another, etc.
This definitive separation between the different memory spaces of a program is important: you would not put the stack in the code segment or put the read/write variables into the read-only data segment. An implication of this (and another one of the benefits of segmentation) is that each segment can have its own protections. For instance, the code segment would have an @execute@ protection, meaning that segment's contents are read-only and executable. For this purpose you would not put the program stack in the same segment because the stack is not read-only and definitely not executable.
There are other many powerful things you can do with segments. One popular use is having each segment be a procedure, or a library of procedures. When you compile the program that uses these procedures you just link the segments. If you had a program that used these libraries and you wanted to change the code inside one of the libraries you could just edit the code in that segment, recompile it, and then link it back to the original program without having to recompile everything else.
These segmented libraries can also be shared (shared libraries) among programs. For instance, if you have a massive graphics library that takes a lot of memory and you have a couple programs that use it, you can just have them share the one library instead of them each having their own. This way you would only need one library loaded in memory instead of two.
In the beginning of the chapter, we talked about a process taking up one single chunk in memory and growing and shrinking according to how much memory it was using. Then we talked about paging as a way to keep these spaces uniform and easily manageable. Segments are not much different: just imagine them as multiple growing and shrinking chunks of memory within one process. We would just fill the physical memory with segments made up of uniform-sized pages. Each segment could have its own page table, and each process will have its own segment table.
h2. 6. Memory Implementation Standards
In order for memory to be usable by users, the operating system must provide certain functionality to them. Programming languages such as C need to have access to certain functionality so it can provide memory functions to programmers. The standard for this is called ISO C and calls for implementation of such functions as @malloc()@, @memcpy()@, @memcmp()@, @memmove()@, etc. These are functions for allocating memory, copying memory, comparing memory, and moving memory, just to name a few.
POSIX compliance not only calls for these C standards, but also its own proprietary functions such as @mmap()@ and @memunmap()@. The function @mmap()@ maps a physical object (such as a file or video buffer) to a virtual address so the program can access it like normal memory.
For more on both of these standards see (Definitions, “Memory Mapped Files”).
h2. 7. O/S Examples
h3. MINIX
MINIX is a minimized version of UNIX written by Andrew Tanenbaum. Because of its simplistic design it was intended for academic purposes to help programmers learn about writing operating systems. MINIX was also designed to be as portable as possible. This means that it can easily be implemented on different processors. This is important because different processors have different instructions built into their hardware, and thusly require different programming on any software that works directly with the CPU (such as the operating system or other machine-code programs).
Since MINIX is small and only meant to work with small processes on consumer machines, it keeps its memory management simple by using non-paging and non-swapping techniques.
First of all, memory is assigned by using first-fit. This means that when allocating memory for a process, the manager starts at the beginning of memory and scans along until it finds the first chunk of unused memory big enough to fit all that the process needs.
Another unique trait of MINIX is the fact that it implements the memory manager in user space! A user process determines where process memory is placed. This was done to allow for easy implementing of different allocation algorithms. To use something other than just first fit, you would only need to run a different memory manager rather than rewriting the kernel code. The mapping of process memory to physical memory, however, is handled in the kernel. The way that the user land memory manager talks to the kernel mapper is through typical IPC calls.
Memory is allocated when a process @fork()@s, copying the parent memory to the child's. Memory is "erased" (or released without necessarily destroying) and then reallocated when the child @exec()@s (@fork()@ and @exec()@, see Chapter 2 Processes and Threads). Memory is then released when exiting or is killed by another program.
h3. Windows
The basic structure of Windows' memory management (using the Win32 standard) is fairly straightforward:
- Each process has its own VAS (Virtual Address Space, or virtual memory space), with 32bit addresses.
- The upper 2GB of memory is kernel info and is shared among all processes, but not accessible in user mode. Only when a syscall traps into kernel mode can the thread access that shared info. This may result in less data privacy, but means faster calls.
- The lower 2GB of memory is program code and data.
- Windows uses copy-on-write.
- Page protections are free, committed, or reserved (pinned).
- No pre-paging; strictly demand paging.
- Mixes local and global page allocations.
From here, though, the memory manager starts to get more complicated. Pages are shadowed, they can be shared, etc. There is also a 5-tiered physical memory manager. For more information, see (Windows).
h3. FMI/OS
Memory management for FMI/OS is another area in which we chose to use an already-working and efficient model. The one we chose is the UVM used in the NetBSD operating system.
h4. UVM Basics
The first thing worth mentioning about UVM is its separation between machine-dependent and machine-independent procedures. Getting full use of each MMU requires special considerations when programming. This specialized programming would not work on machines that implement theirs differently. The programs that have to make these special considerations are machine-dependent. However, much of the code managing virtual memory doesn't have to worry about the machine's specific hardware. Therefore, the VM manager is machine-independent.
UVM's machine-dependent code is called @pmap@. The @pmap@ procedures are small and easy to port to other processors (i.e. re-program to make compatible with other computer architectures) to take advantage of different types of MMUs.
UVM also has other VM basics:
- Each process holds its own VAS information (page tables).
- Processes can map memory objects into their VAS.
- A pager (A daemon that runs in the background. Pointers to the pager procedures are given to each memory object. Therefore, if an object causes a page fault, all it has to do is call those procedures to handle it).
- Demand-paging is used.
- Prepaging is allowed
- Copy-on-write during process and thread forking.
But then, UVM has some extra features
Page Loanout. This is a type of copy-on-write system for the IPC. Instead of copying messages from one process to another, the kernel "loans" the map over to the other process, giving it read-only properties. If the other process chooses to write to it, only then does the kernel make a copy.
Scatter-Gather Buffers. Instead of passing a single message from one process to the next, a list of messages (or "buffers") is passed. As each layer adds to the message, they would only need to add that message to the list. Therefore, the last process will receive a list of these buffers and will just write them all out at once. For instance, suppose a server is receiving a write-request message. This server will pass it on to an I/O server who will then add an EOF (End Of File) to the end of the list and write both buffers to disk, therefore not needing to copy the entire message to writable space just to add a byte of data. If the disk is using DMA (Chapter 8 IO Layers), the DMA server will then "gather" all of the "scattered" buffers and copy them into one, contiguous buffer which it then sends to the DMA. If using a programmable I/O (which writes bytes to disk one at a time) then there would be no need for the last "gathering" copy. The function would just go through each buffer, byte-by-byte, and write each byte to disk.
Lazy Allocation. This is a flag that a process can have set. On the rare occasion that the entire VM space is filled and a process is asking for yet more memory, then UVM has to make a decision on how to free some for it. If the offending process' lazy allocation flag is set, then the UVM takes the "lazy" route and kills that process. In the case that the offending process is not allowed to be killed (i.e. the flag's not set) then the pager daemon taps into its small buffer of reserve pages until it can kill another process.
There are many other specifics of UVM that are quite interesting. However, they fill a 270-page "dissertation written by Chuck Cranor":http://wiki.ocgnet.org:8080/FMIOS/UVM%20Dissertation.pdf for his Ph.D. so I leave the research up to the curious reader. Cranor and Parulkar wrote a short "abstract on UVM for the USENIX Tech Conference":http://www.usenix.org/events/usenix99/full_papers/cranor.
h4. Applying UVM to FMI/OS
UVM has extensive functionality, but not all of it is needed in FMI/OS. UVM was written for NetBSD, which is a monolithic kernel, and FMI/OS is a client-server. For starters, the file-system implementation is in user space, thus swapping gets complicated. A temporary solution is that the swapping has been removed completely. Future solutions include putting a single pager daemon into user space. Another option is putting a pager daemon into the C library (that is included and compiled into every file that will run on the OS; see libc in Chapter 10: Environment Layer) so each program will have its own pager daemon thread that will just sleep until needed. Although threads do not need to know about this personal pager thread (since paging is handled automatically), it does allow threads that do know about it to employ specialized handling. Also, if the kernel were to be running low on memory, it could use its normal swapping algorithm to determine which pages to remove and just signal the process that owns the page to swap it out (see "IRC discussion, 03-25-06":http://www.jpl.se/~dalen/irclogger/irclog.cgi?year=2006&month=3&day=25).
UVM allows user processes to loan pages to the kernel itself, because that's where the drivers reside (i.e. disk I/O, printer, etc). FMI/OS's kernel does not implement any drivers inside of it so it does not need the loan ability. Therefore, to promote simplicity, it has not been implemented.
However, FMI/OS does implement writable loans. This means that the kernel's IPC will loan out a page with write permissions. For instance, if a program was blocking, waiting for a keyboard input, then the message it passed to the keyboard's interrupt handler is actually loaned so that the handler can write the key pressed to the message and return it.
For more information on porting UVM to FMI/OS see Amatus' UVM page on the wiki.
Next up: Chapter 6 Multiple Processors
(c)2006 Dimitri Hammond
From: unknown Date: Sun, 09 Apr 2006 00:43:41 -0500 Subject: Andrew Tanenbaum wrote MINIX Message-ID: <20060409004341-0500@wiki.ocgnet.org:8080>
MINIX was written by Andrew Tanenbaum, not William Tanenbaum. I'm William Tanenbaum, and I did not write it.
