Working Set Model & Locality

Title Page

Institute Name:

Australian College Of Business And Technology

Degree Program:

Diploma In IT

Semester:

Semester 1, 2008

Unit Name:

Operating Systems (CSG1206)

Lecture Name:

Mr. S. Wickramasinghe

Assignment No:

01

Assignment Title:

Working Set Model and Locality

Date Of Submission:

10th May 2008

ID No:

PESBI72

Name:

Sunimali Perera

Word Count

2732

Contents Executive Summary................................................................ ...............3 Background Information.............................................. ..........................4 Memory Management Requirements......................................................................4 The roles of working set model and locality in an operating system......................5 Discussion ..................................................... ......................................6 The two basic types of locality................................................................................6 Virtual Memory Management in two real operating systems.................................7 Virtual Memory Management in Windows XP ............................................7 Windows virtual address map..........................................................8 Windows paging ............................................................................8 Virtual Memory Management in Linux........................................................9 Future Trends for operating systems.....................................................................9 Current trends............................................................................................9 Future trends............................................................................................10 References....................................................................... ..................11 Bibliography.............................................. .........................................12

2

Executive Summary

This technical report explains the working set model and locality of reference and how it is applied to different operating systems. Moreover, it illustrates virtual memory management and the comparison of this, concerning two real operating systems. Ultimately, the term locality is commonly used to determine the number of assigned pages. The number of pages that meet the requirement of locality is called a working set. The ability to design operating systems to be highly efficient depends on many factors. Among these, the most important factor is a proper understanding of the concept of locality. One of the most important yet complex tasks of an operating system is memory management. Memory management involves treating main memory as a resource to be allocated to and shared among a number of active processes. Most operating systems supporting multiprogramming, aim to provide effective and efficient memory management in order to increase CPU utilization and to allow as many active processes as possible. A virtual memory management scheme requires both hardware and software support. The hardware support is provided by the processor. Virtual memory has become a vital requirement over the years, as the cost of secondary memory decreases, and the memory demands of software increase. In order to balance the use of primary memory among processes, sophisticated algorithms are necessary to manage the replacement of virtual pages. This report outlines the pros and cons of a variety of solutions, including both static based demands and dynamic pre-fetch replacement algorithms. The concluding part of the report provides an understanding of future trends through identifying the potential issues regarding the virtual memory management for future operating systems. In the process of doing so, some of the current trends are listed and the possible modifications that can be done to these listed trends are discussed.

3

4

Background Information Memory management requirements In computer systems main memory is divided into two parts, one part for the operating system and the other part for the program currently being used. In operating systems there are procedures for optimizing the use of random access memory. These procedures are collectively identified as memory management. Selectively storing data, monitoring it carefully and freeing memory when the data is no longer needed, are all part of these procedures. Memory management in programming is the process of ensuring that a program releases each chunk of memory when it is no longer needed. The task of subdivision is carried out dynamically by the operating system and is known as memory management. In memory management, there are vital concerns memory management expects to fulfill. They are;

•

Relocation or binding is the translation of the memory references in the program code (logical addresses) into physical addresses. This is required since it is not possible to know in advance where a program should be placed in the main memory. In addition, to maximize processor utilization through swapping, it should be possible to move a program to any address in memory in order to execute it. Hardware support is required to map from logical addresses to physical addresses.

•

Protection is when a process should be protected against memory-reference violations (accidental or intentional) by other processes. A user process cannot access areas of the operating system and other processes without permission. Hardware support for protection is the same as that used to support relocation.

•

Sharing of the same portion of memory by several processes should be allowed by the flexible enough protection mechanism employed by the operating system, if required. For example, it is useful to allow several processes to share the same copy of a compiler. Cooperating processes may also need to share access to the same data structure. The mechanism used to support relocation can be employed to support sharing capabilities.

•

Logical organization – Users write programs in modules (parts, components) with different characteristics as Instruction modules and Data

5

modules. The operating system and hardware should support a basic form of module to provide the necessary protection and sharing.

‘Main memory and secondary memory are organized as linear, or one dimensional address space. However, most user programs are organized into modules. Thus, the operating system must be able to deal effectively with programs and data in the form of modules.’ (Dr C. Chithramjaree, June 2000) •

Physical organization - In a computer system, there are two main levels of memory (storage). The first level is the main memory or primary (real) memory. It is used to hold programs and data currently in use (i.e. short-term storage). The next level is the secondary memory (storage) that is used to provide permanent (long-term) storage of programs and data. The task of moving programs and data between the two main levels of memory is done by memory management system.

The roles of working set model and locality in an operating system A working set model is the set of physical memory pages (main memory) presently given to a particular process i.e. the set of active virtual memory pages for a process stored in random access memory (RAM) at a given instant. The size of the working set model in any operating system is important. It should not be too large or too small. If the working set is too small, then further additional requests must be made in the swapping area (space) to regain required pages. If the working set is too large, then fewer processes will be available to be executed. The definition of the working set model states that a process can be in the main memory if it consumes the memory of the main memory. In this model, if the use for pages increases, there will be no room in the primary memory (main memory). If so, the process is removed or eliminated from memory to free some memory for other processes to load and execute. In other words, the working set policy stops thrashing (poor performance of paging system) while keeping the scale of multiprogramming as high as possible. Thus, it optimizes processor utilization and throughput. 6

Locality is the tendency of programs considering their references over any given interval of time, to a subset of the paces of the program, and for this subset to change rather slowly with time. Locality is the point to which a program keeps memory references limited to a small number of locations over any short length of time. The better the locality of reference, the more likely a program will execute entirely from the cache memory. The more scattered a programs’ memory references, the higher the chance that it will access main memory, while the worse that can happen being loading a page from swapping area.

Discussion The two basic types of locality The concept of locality is typically used to determine the number of assigned pages. The ability to design operating systems that is maximally efficient depends on many factors. Among those, the most important is our understanding of the concept of locality. Locality is a set of pages actively used together. It has been suggested that the property of locality be split into two components temporal locality and spatial locality. This is illustrated by Madnick, S.E., & Donavan J.J. (1997). Temporal locality is the property where a high probability exists that a pace, once referenced, will be referenced shortly thereafter. Temporal locality refers to an observed property of most programs, i.e. once a location, data or instruction is referenced, it is often referenced again very soon. This behavior can be rationalized by program constructs such as loops, frequently used variables, and subroutines. Spatial locality, on the other hand, is said to exist if there is a high probability that pages close to the paw currently being referenced, will be referenced within a short time. Spatial locality refers to the probability that once a location is referenced, a nearby location will be referenced soon. This behavior can be rationalized by program constructs such as sequential instruction sequencing, linear structures (e.g., arrays), and the other tendency of programmers to put commonly used variables near one another. The degree of locality varies from program to program. In general, it is desirable to develop programs with a high degree of locality. A high degree of temporal locality indicates a low fault rate with the least recently used (LRU) or Working set (WS) replacement algorithms. A high degree of spatial locality suggests that doubling the page size might improve pads performance. 7

An item of information that has just been referenced in a particular level is very unlikely to be referenced again in a short time even though the program makes repeated references to it. This is because a copy of that information exists at a higher level and, consequently, references will not filter down to the lower level. As a result, the spatial locality of the program would have to be measured at every level. “It would be far better if the model of spatial locality were such that it was a function of only the program and not of the level in the hierarchy.” This was signified by Rau, B. R. (1975). In other words, the spatial locality should be modeled such that it is an invariant in the hierarchy. The temporal locality, on the other hand, will, most definitely, be a function of the level in the hierarchy. It should not, however, be characterized so as to be a function of the spatial locality. Accordingly, the temporal locality must be characterized in terms of the smallest unit of information that the processor is capable of requesting. This might be larger than the smallest addressable unit. This is the natural choice by default, a smaller page size being meaningless. The spatial locality must be characterized by some property which function of page size, but is invariant with the level in the hierarchy. Once this has been done, there is but one problem that remains to be solved. As has been noted, the fault stream out of one level (the request stream for the lower level) is different from the request stream to the level. The difference is mainly in the temporal locality of the two streams. A method must exist for deriving the model for the fault stream, given the model for the request stream and the parameters of the memory level. Rau, B. R. (1975).

Virtual Memory Management in two real operating systems Virtual memory or virtual memory addressing is a memory management technique, used by multitasking computer operating systems wherein noncontiguous memory is presented to a software application as contiguous memory. This contiguous memory is referred to as the virtual address space. Virtual memory addressing is typically used in paged memory systems. This in turn is often combined with memory swapping, whereby memory pages stored in primary storage are written to secondary storage, thus freeing faster primary storage for other processes to use.

Virtual Memory Management in windows XP

8

Virtual memory has been a feature of Microsoft Windows since Windows 3.1 in 1992. 386SPART.PAR (or WIN386.SWP on Windows 3.11 and Windows for Workgroups) is a hidden file created by Windows 3.x for use as a virtual memory swap file. It is generally found in the root directory, but it may appear elsewhere (typically in the WINDOWS directory). Its size depends on how much virtual memory the system has set up or user define “under Control Panel - Enhanced under "Virtual Memory"”. This page file is located at C:\pagefile.sys on all NT-based versions of Windows (including Windows 2000 and Windows XP), though Windows may be configured to place additional page files on other drives. Eskicioglu, & Marsland, (n.d) Windows 95 uses a similar file, except it is named WIN386.SWP, and the controls for it are located under “Control Panel - System - Performance tab - Virtual Memory”. Windows automatically sets the page file to start 1.5x physical memory, and expand up to 3x physical memory if necessary. If a user runs memory intensive applications on a low physical memory system, it is preferable to manually set these sizes to a value higher than default. The Windows virtual memory manager controls how memory is allocated and how the paging is performed. The memory manager is designed to operate over a variety of and use page sizing ranges from 4 Kbytes to 64 Kbytes. Intel, PowerPC, and MPIS platforms have 4096 bytes per page and DEC Alpha platforms have 8196 bytes per page. Stallings, W (1990, p.379-380).

Windows virtual address map Each window user process sees a separate 32-bit address space, allowing 4 Gbytes of memory per process. By default, a portion of this memory is reserved for the operating system, so each user actually has 2 Gbytes of system space. There an option that allows user space to be increased to 3 Gbytes, leaving 1 Gbyte for system space. The Windows documentation indicates that this feature is intended to support large memory intensive applications of servers with multiple gigabytes of RAM, and that the use of the larger address space can dramatically improve for applications such as decision support or data mining. Figure 1.0 shows the default virtual address space seen by a user process. It consists of four stages.   

0x00000000 to 0x0000FFFF: Set aside to help programmers catch NullPointer assignments. 0x00010000 to 0x7FFFFFFF: Available user address space. This space is divided into pages that may be loaded into main memory. 0x7FFF0000 to 0x7FFFFFFF: A guard page inaccessible to the user. This page makes it easier for the operating system to check on out-of-bounds pointer 9



references. 0x80000000 to 0xFFFFFFFF: system address space. This 2-Gbyte Process is used for the Windows Executive, microkernal, and device drivers.

Windows paging When a process is created, it can in principle make use of the entire user space in 2 Gbytes (minus 128 Kbytes). Stallings, W (1990, p.379-380) says that “this space is divided into fixed-size pages, any of which can be bought into main memory.” In practice, the accounting, page can be in one of three states, they are available, reserved and committed. Stallings, W (1990, p.379-380).

When main memory is plentiful, the virtual memory manager allows the resident sets of active processes to grow. When memory becomes scarce, the virtual memory manager recovers memory for the system by moving less recently used pages out of the working sets of active processes, reducing the size of those resident sets. (This was emphasized by Stallings W. 1998 p. 380).

Virtual Memory Management in Linux Linux makes use of a three-level page table structure, consisting of the following types of tables (each individual table is the size of one page): Page directory: An active process has a single page directory that is the size of one page. Each entry in the page directory points to one page of the page middle directory. The page directory must be in main memory for an active process. Page middle directory: the page middle directory may span multiple pages. Each entry in the page middle directory points to one page in the page table. Page table: the page table may also span multiple pages. Each page table entry refers to one virtual page of the process. The Linux page table structure is platform independent and was designed to accommodate the 64-bit Alpha processor, which provides hardware support for 10

three levels of paging. With 64-bit addresses, the use of only two levels of pages on the alpha would result in very large pages and directories. The 32-bit Pentium/x86 architecture has a two-level scheme by defining the size of the page middle directory as one. Page allocation, Page replacement algorithms and page replacement are some of the mechanisms used in dealing with contiguous blocks of pages. See Stallings, W. (1998, p. 378)

Future trends for Operating Systems Current trends Larger physical memory In this case, replacing pages will have to be done a less number of times compared to when the physical memory is lesser. Also, large page size gives better TLB coverage and small page tables. The pages being less, makes it easier to manage page tables. By having large physical memory, the hardware support for replacement policies enhances. Larger address spaces This allows substantial address spaces. Here, larger address spaces indicate single (combined) address space (part of the OS for the user processes).

File systems using virtual memory • •

Memory mapped files File caching with virtual memory

Future trends Operating systems make frequent changes to their page tables, so keeping shadow copies up to date in software can encounter undesirable overhead. Hardware-managed shadow page tables have long been present in mainframe virtualization architectures and would prove a fruitful direction for accelerating x86 CPU virtualization. Resource management holds great promise as an area for future research. Much work remains in investigating ways for VMMs and guest operating 11

systems to make cooperative resource management decisions. In addition, research must look at resource management at the entire data center level, and can be expected to make significant strides in this area in the coming years. Analysis of virtual memory proves that its concept is not only feasible, but extremely useful and a necessity in ever-growing computer systems where high speed primary memory is limited. In the future we will see the size of memory considerably very high and they will be affordable. Effective and more efficient ways of memory management will be found. In order to make the best use of multiple levels of memory, such as cache to make a program run faster, or, paging to make fuller use of the RAM; a way of predicting which chunk of memory will be required by the program, can be expected in the near future. Fortunately, many programs exhibit a high degree of locality in their memory reference patterns. Eventually this concept can be used in designing both the hardware of a computer, the structures and algorithms of an operating system. Another way to boost performance is to use a virtual cache. A virtual cache uses a portion of physical memory to store code and data that the operating system might use frequently. Since the operating system is responsible for loading applications and data files into memory, it can accumulate this type of tracking information for use with the virtual cache.

12

References

•

Avaliable WWW: http://www.redhat.com/docs/manuals/linux/RHL-9Manual/custom-guide/ch-swapspace.html [Access date 01/05/2008]

•

Dr Chirathamjaree, C. (2000), CSG 2343: Operating Systems unit guide (version 1.1). Perth: Edith Cowan University.

•

Dr Chirathamjaree, C. (2000). Operating Systems: Unit Guide. Australia. Edith Cowan University

•

Eskicioglu, & Marsland, (n.d), Virtual Memory, Avaliable WWW: www.cs.ualberta.ca/~tony/C379/Notes/PDF/08.4.pdf . [access date 21/04/2008]

•

Garfinkel, T., & Rosenblum M. (2005, May) VMware Inc. Available WWW: www.stanford.edu/group/comparch/papers/Computer_RosenblumGarfinkel.pd f [access date 24/04/2008]

•

http://www.computerworld.com/action/article.do?command=viewArticleBasic &articleId=60855&pageNumber=2 [Access Date 11/04/2008]

•

Madnick, S.E., & Donavan J.J. (1997), Operating systems, (fifth edtion), Tata McGraw-Hill Publishing Company Limited New Delhi

•

McCraw, T. (n.d), Virtual Memory Page Replacement Algorithms, people.msoe.edu/~mccrawt/resume/papers/CS384/mccrawt_cs384_virtual.pd f, [Access Date 29/04/2008]

•

Rau, B. R. (1975), The stack working set: A characterization of spatial locality, ftp://reports.stanford.edu/pub/cstr/reports/csl/tr/75/95/CSL-TR-75-95.pdf [Access Date 19/04/2008]

•

Silberschatz, A., Galvin, P.B., & Gagne, G. (2005). Operating System Concepts, 7th edition. Palatino: Wiley. p.346.

•

Stalling, W. (2005). Operating Systems: Internals and Design Principles. New Delhi: Prentice-Hall of India Private Limited

13

Bibliography •

Avaliable WWW: http://www.redhat.com/docs/manuals/linux/RHL-9Manual/custom-guide/ch-swapspace.html [Access date 01/05/2008]

•

Dr Chirathamjaree, C. (2000), CSG 2343: Operating Systems unit guide (version 1.1). Perth: Edith Cowan University.

•

Dr Chirathamjaree, C. (2000). Operating Systems: Unit Guide. Australia. Edith Cowan University

•

Eskicioglu, & Marsland, (n.d), Virtual Memory, Avaliable WWW: www.cs.ualberta.ca/~tony/C379/Notes/PDF/08.4.pdf . [access date 21/04/2008] G, Binny. (2005). Temporal locality. Available WWW: http://www.usenix.org/events/fast05/tech/full_papers/gill/gill_html/node7.html [access date: 10/05/2007].

•

•

Garfinkel, T., & Rosenblum M. (2005, May) VMware Inc. Available WWW: www.stanford.edu/group/comparch/papers/Computer_RosenblumGarfinkel.pd f [access date 24/04/2008]

•

http://www.computerworld.com/action/article.do?command=viewArticleBasic &articleId=60855&pageNumber=2 [Access Date 11/04/2008]

•

Madnick, S.E., & Donavan J.J. (1997), Operating systems, (fifth edtion), Tata McGraw-Hill Publishing Company Limited New Delhi

•

McCraw, T. (n.d), Virtual Memory Page Replacement Algorithms, people.msoe.edu/~mccrawt/resume/papers/CS384/mccrawt_cs384_virtual.pd f, [Access Date 29/04/2008] Paul, R. (year not given). Locality of Reference. Available WWW: http://citeseer.ist.psu.edu/337869.html [Access date: 10/04/2008].

•

•

•

•

Rau, B. R. (1975), The stack working set: A characterization of spatial locality, ftp://reports.stanford.edu/pub/cstr/reports/csl/tr/75/95/CSL-TR-75-95.pdf [Access Date 19/04/2008] S, William. (2005). Types of locality. New Delhi: Prentice-Hall of India Private Limited Silberschatz, A., Galvin, P.B., & Gagne, G. (2005). Operating System Concepts, 7th edition. Palatino: Wiley. p.346.

14

•

Stalling, W. (2005). Operating Systems: Internals and Design Principles. New Delhi: Prentice-Hall of India Private Limited

15