Tutorial 4 SEB070028

The key to using memory efficiently is virtual memory management. Consider both
Windows and a UNIX/Linux operating system. Compare and contrast how each implements
virtual memory. Describe how each one handles page faults, page sizes and how
it reconciles thrashing issues. Cite your sources.

Windows		Linux
For each process, the operating system maps few addresses to real physical memory because RAM is expensive. Remaining memory for each process is maintained on secondary storage. That’s why it is called virtual memory. The addresses that are not mapped on physical RAM are marked as such. Whenever a process accesses such an address, the operating system brings the data into memory from secondary storage. If the operating system runs out of physical RAM, some data is thrown out to make space. We can always get back this data because a copy is maintained on secondary storage. The data to be thrown out is decided by the replacement policy. Windows NT uses First-In-First-Out (FIFO) replacement policy. According to this policy, the oldest data ( the data that was brought in the RAM first) is thrown out whenever there is a space crunch. To implement virtual memory management, Windows NT needs to maintain a lot of data. It needs to maintain whether each address is mapped to physical RAM or the data is to be brought in from secondary storage when a request with the address comes. Maintaining this information itself takes a lot of space. So Windows NT breaks the address space into 4KB pages and maintains this information in page tables. As we saw earlier, a page table entry (PTE) consists of the address of the physical page (if the page is mapped to physical RAM) and attributes of the page.	Implementation of virtual memory	Linux supports virtual memory that is, using a disk as an extension of RAM so that the effective size of usable memory grows correspondingly. The kernel will write the contents of a currently unused block of memory to the hard disk so that the memory can be used for another purpose. When the original contents are needed again, they are read back into memory. This is all made completely transparent to the user; programs running under Linux only see the larger amount of memory available and don't notice that parts of them reside on the disk from time to time. Of course, reading and writing the hard disk is slower (on the order of a thousand times slower) than using real memory, so the programs don't run as fast. The part of the hard disk that is used as virtual memory is called the swap space. Linux can use either a normal file in the file system or a separate partition for swap space. A swap partition is faster, but it is easier to change the size of a swap file (there's no need to repartition the whole hard disk, and possibly install everything from scratch). When you know how much swap space you need, you should go for a swap partition, but if you are uncertain, you can use a swap file first, use the system for a while so that you can get a feel for how much swap you need, and then make a swap partition when you're confident about its size.
If a page is not mapped onto physical RAM, Windows NT marks the page as invalid. Any access to this page causes a page fault, and the page fault handler can bring in the page from the secondary storage. To be more specific, when the page contains DLL code or executable module code, the page is brought in from the DLL or executable file. When the page contains data, it is brought in from the swap file. - When the page represents a memory-mapped file area, it is brought in from the corresponding file. Windows NT needs to keep track of free physical RAM so that it can allocate space for a page brought in from secondary storage in case of a page fault. This information is maintained in a kernel data structure called the Page Frame Database (PFD). The PFD also maintains a FIFO list of in-memory pages so that it can decide on pages to throw out in case of a space crunch. If there is pressure on space in RAM, then parts of code and data that are not currently needed can be ‘paged out’ in order to make room. The page file can thus be seen as an overflow area to make the RAM behave as if it were larger than it is. When Windows NT addresses an invalid page (that is, during the course of address translation one of the PTEs identifies a page as not present), a page-fault exception is raised by the processor. A page fault results in switching immediately to the pager. The pager then loads the page into memory and, upon return, the processor re-executes the original instruction that generated the page fault. This is a relatively fast process, but accumulating many page faults can have a drastic impact on performance.	Page Faults	A process has a memory map (page table) that contains page table entries which point to memory assigned to the process and describes to the CPU which memory locations are valid for a process to access. Memory is managed and assigned to processes in chunks called pages.Initially a process has no pages assigned at all and the page table is empty. Any access to memory areas not mapped by the page table result in the generation of a page fault by the CPU. The operating system must provide a page fault handler that has to deal with the situation and determine how the process may continue. On startup a process must set up its own memory areas and therefore page faults occur most frequently when a new process is started. In order to allow access to pages of memory never accessed before, the page fault handler must reserve a free page of memory and then make that page visible to the process by adding a page table entry to the page table. This process is critical: Page fault performance determines how quickly a process can acquire memory and is particularly importance for applications that utilize large amounts of memory. Three means of optimizing page fault performance are: First, one may avoid the use of the page table lock through atomic operations on page table entries. Second, the page fault handler may analyze the access pattern of the process. Optimizing sequential memory allocation is then possible by anticipating future accesses. The locking overhead is reduced thus SMP performance improves. Finally, if zeroed pages are available then the page fault handler may simply assign a zeroed page to the process avoiding the clearing of pages in the fault handler. This will reduce the number of times the page table lock.
Windows will expand a file that starts out too small and may shrink it again if it is larger than necessary, so it pays to set the initial size as large enough to handle the normal needs of your system to avoid constant changes of size. This will give all the benefits claimed for a ‘fixed’ page file. But no restriction should be placed on its further growth. As well as providing for contingencies, like unexpectedly opening a very large file, in XP this potential file space can be used as a place to assign those virtual memory pages that programs have asked for, but never brought into use. There is no downside in having potential space available. For any given workload, the total need for virtual addresses will not depend on the size of RAM alone. It will be met by the sum of RAM and the page file. Therefore in a machine with small RAM, the extra amount represented by page file will need to be larger but not smaller than that needed in a machine with big RAM. Unfortunately the default settings for system management of the file have not caught up with this: it will assign an initial amount that may be quite excessive for a large machine, while at the same leaving too little for contingencies on a small one. How big a file will turn out to be needed depends very much on your work-load. Simple word processing and e-mail may need very little but large graphics and movie making may need a great deal.	Page Sizes	Most modern operating systems have their main memory divided into pages. It allows better utilization of memory. A page is a fixed length block of main memory that is contiguous in both physical memory addressing and virtual memory addressing. To make this translation easier, virtual and physical memory are divided into handy sized chunks called pages. These pages are all the same size, they need not be but if they were not, the system would be very hard to administer. Linux on Alpha AXP systems uses 8 Kbyte pages and on Intel x86 systems it uses 4 Kbyte pages. Each of these pages is given a unique number; the page frame number (PFN). In this paged model, a virtual address is composed of two parts; an offset and a virtual page frame number. If the page size is 4 Kbytes, bits 11:0 of the virtual address contain the offset and bits 12 and above are the virtual page frame number. Each time the processor encounters a virtual address it must extract the offset and the virtual page frame number. The processor must translate the virtual page frame number into a physical one and then access the location at the correct offset into that physical page. To do this the processor uses page tables. Kernel swap and allocates memory using pages.
The problem of many page faults occurring in a short time, called “page thrashing”. Trashing is a scheme in virtual memory where the processes spends most of its time in swapping pages rather than executing instructions, this is due to inordinate number of page faults. When you trash something on the flash it creates a ".Trashes" directory on the root of the drive, and under that it creates a directory with the name being the of the user where it stores the files as-is. If you trash multiple files with the same name they get duplicate names the normal duplicate name algorithm is used. The actual trash location is a merger of all the trash, and name conflicts between different trash just show up as two files with the same name. The merging is dynamic, so if you show the trash and plug in a flash card its trash shows up in the trash window.	Trashing issues	The cache does not actually buffer files, but blocks, which are the smallest units of disk I/O (under Linux, they are usually 1 KB). This way, also directories, super blocks, other filesystem bookkeeping data, and non-filesystem disks are cached. The effectiveness of a cache is primarily decided by its size. A small cache is next to useless: it will hold so little data that all cached data is flushed from the cache before it is reused. The critical size depends on how much data is read and written, and how often the same data is accessed. The only way to know is to experiment. If the cache is of a fixed size, it is not very good to have it too big, either, because that might make the free memory too small and cause swapping (which is also slow). To make the most efficient use of real memory, Linux automatically uses all free RAM for buffer cache, but also automatically makes the cache smaller when programs need more memory.

Sources

http://www.windowsitlibrary.com/Content/356/04/3.html

http://www.tldp.org/LDP/sag/html/vm-intro.html

http://gentoo-wiki.com/FAQ_Linux_Memory_Management#Virtual_Memory_Area

http://oss.sgi.com/projects/page_fault_performance/#pagefault

http://www.linuxhq.com/guides/TLK/mm/memory.html