Smartphone Operating System (779883), страница 32
Текст из файла (страница 32)
Bybreaking up logical memory into pages, we can scatter those pages allover memory as needed. The operating system needs a way to keep trackof all this; a page table is used to keep of track where pages are (bothin memory and on page storage) and which process they belong to. Bydoing this, we can utilize as much memory as is available.We should note here that some operating systems do not actually keepa specific table called a ‘page table’. For some, the page data is storedwith the PCB data in the process table. The information gleaned from allPCBs forms the ‘page table’ we speak of here. In other cases, page tablesare kept, but they are kept on a per-process basis.
Again, these processpage tables together form the system page table we are discussing here.The page table is used in address calculation. Each logical addressused by programs on the CPU is composed of two parts: the page numberof the memory block being addressed and the offset within the page ofthe memory location. The page table, then, is a mapping between logicalmemory pages and physical-memory frames.
Let’s take an example asshown in Figure 7.4. In this example, logical-memory pages are 1 KB, asare physical-memory frames. In logical memory, addresses are (obviously)in sequence. The page table holds the physical-memory frame for eachlogical page, when that page exists in physical memory.The memory-page table is not the whole story here. There is also apage table for pages stored in secondary storage. As with the memorypage table, this is usually kept in one place, but it could be distributed toprocess-page tables. It is usually managed by either the operating systemor a memory-management unit on the hardware.Memory Allocation PatternsWhen we implement the carving up of process memory into logicalpages and mapping those pages to physical-memory frames, we have acoarse-grained allocation of physical memory to the total memory needsof a process. Within memory pages, actual memory use takes place asmemory is allocated and de-allocated by processes. There are patterns ofmemory allocation that emerge from fine-grained use of memory.148MEMORY MANAGEMENTPagetableLogicalmemoryPage 00Page 11000Page 22000Page 33000Page 4400001001103210231064108Physicalmemory100000100Page 0101000101102000102Page 2103Page 1103000104000104105000105106000106Page 3107000107108000108Page 4Figure 7.4 Using a page table to support memory pagingMemory is a chaotic place.
In addition to referring to memory locationsas data storage, processes cause the structures that the operating systemhas forced onto memory to change rapidly. When a process is movedfrom the ready queue to the running queue, it requires its memory pagesto be in memory. If some pages are in memory and some are not, thosethat are resident are used as needed. Eventually, there is probably a needfor pages to be swapped in, but that work is postponed as long as possible.Within memory pages, memory is allocated in both static and dynamicways.
Static allocations result from fixed or predictable memory needs.These needs include space for the object code that defines a program andspace for the fixed data requirements in a program. Declared variablesare good examples of fixed data requirements: their space needs can bedetermined from parsing the source code. Dynamic memory needs arethose that arise during program execution.
Examples of dynamic-memoryallocation are the creation of data objects using the new operator inC++ or using the malloc() call in C to create memory areas. Dynamicmemory allocations are usually granted as continuous memory spaces(this reduces the need for swapping).Even dynamic memory requirements are usually serviced from amemory area that is allocated in a static manner. Dynamic memorySWAPPING AND PAGING149allocations come from a structure called a heap; heaps are located inallocated memory space like any other memory requirement. Heapsare typically allocated in pieces of a fixed size, which allows dynamicmemory to fit into a memory-paging scheme.Configuring pages can be a challenge because of the variety of waysthat allocations take place.
A big challenge in page configuration is thedetermination of proper memory page size. There are several problemsthat can result from inaccurate choice of page size.Consider the inside of a memory page. If the memory area being usedinside a page does not utilize the entire page, there is a certain amountof memory wasted. For example, if the program code or use of the heapdoes not completely fill a page, there is free memory inside a pagethat cannot be reused for other pages.
This gets worse with heaps. Asmemory is allocated as a contiguous unit and deallocated in a program,dynamic memory areas develop ‘holes’: areas of unallocated memory aredispersed among areas of allocated memory. As time goes on and memoryis allocated and deallocated, these holes get spread out around the heap.This creation of free but unusable memory is called fragmentation.
Thetype of fragmentation that occurs inside a memory page is called internalfragmentation.The way dynamic storage is allocated can aggravate fragmentation.Dynamic memory needs are typically serviced in one of three ways:• first fit : a search is conducted through memory and the first area offree memory is allocated for the memory request; searching usuallystarts at the beginning of memory each time• best fit : a search is conducted through memory and the area of freememory that is closest in size to the request is allocated (this type ofallocation is best done if a table of free space – location and size – iskept; then the table is searched, not memory)• worst fit : a search is conducted and the largest block of memoryis allocated to the request; this approach allows a large amount ofmemory to be left behind as free space.If space is wasted between blocks of allocated space, we call thatexternal fragmentation.
Internal fragmentation wastes memory that cannotbe recovered, since the memory has already been allocated, but externalfragmentation can be recovered if memory allocation breaks down.Consider a memory allocation pattern like that in Figure 7.5.150MEMORY MANAGEMENT400 KB allocation200 KB free600 KB allocation200 KB free100 KB allocationFigure 7.5 Example of external fragmentationAll memory has been allocated except the fragments in the figure.Together, the two free blocks amount to 400 KB of space, but they arenot contiguous. The largest request that can be serviced is 200 KB – evenwhen the total free space is 400 KB.
When memory is contiguous, moreallocation requests can be serviced.Sometimes fragmentation can be avoided; other times it cannot. Fragmentation is caused by blocks of memory which cannot fit requests bythemselves. Joining fragments that are next to each other might alleviatesome of the problem; checking to see if fragments can be joined is usuallydone on memory deallocation. Another way of relieving the problems isto move fragments around so that they are next to each other and can bejoined. These methods can be quite costly but can result in more memorybeing used.On-demand Paging and ReplacementIn previous sections, we have discussed how memory is manipulated bya program that is continually moved in and out of the running state.
Wehave not, however, discussed the big picture: the execution environmenthas many processes, all of which are being moved in and out of theSWAPPING AND PAGING151running state, each of which requires memory pages. What happenswhen the number of pages required by all processes exceeds the numberof pages available in memory?We can partially alleviate this problem by using on-demand paging.This method brings pages into memory only when they are required, muchlike dynamic loading of program code. For example, an application’sprogram code might require three pages of memory, but only one page isrequired to start the program. For this situation, on-demand paging wouldonly bring in the first page as the program starts execution and bring therest of the pages as the code or data in them is needed.
The operatingsystem watches for page faults, which are events that are triggered whenmemory is referenced from a page that is not in memory, as determinedby referencing its address through the page table.Bringing one page into memory at a time might be too time-consuming.Therefore, an operating system might group certain pages into a workingset of pages that are brought in together.
For example, the first pageof an application’s code could be included in a working set with thememory pages for its statically declared variables and the first pagefor the application’s heap. Bringing in a working set cuts down on thenumber of page faults and the amount of time to service the faults. Theworking set is determined by the operating system; a standard workingset is typically used and adjusted as an application runs.One other method that is used to save memory is page replacement.Memory fills up with pages rather quickly as a computer boots up andstarts initial processes running. When memory is full of pages and anoperating system brings in a page from the disk that needs to be placed(as indicated by a page fault), it chooses an existing page to replace.These pages are then swapped – the old page is removed and placedon the disk and the new page takes its place.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
