内存管理模块主要介绍了计算机存储系统的基本概念；内存管理中的常用术语，包括程序名字空间、地址空间、内存空间、地址重定位等；分区管理方法；页式管理方法；段式管理方法；内存扩充技术、虚拟存储器等概念；请求页式管理；页面置换算法；请求段式管理；请求段页式管理等内容。

After studying this chapter, you should be able to: 
(1) Master: relocation and protection; memory management with linked lists; virtual memory; paging; page replacement algorithm
(2) Understand: memory manager; program name space; address space; memory space; multiprogramming with fixed partitions; memory management with bitmaps; search algorithm; page tables; page replacement algorithms; page size; segmentation
(3) Know: monoprogramming without swapping or paging; multiprogramming with dynamic partition; instruction table; inverted page tables; Belady anomaly

Basic:

1. The address space and memory space

2. Memory management with partition

3. Memory management with bitmaps

4. Search algorithm: best fit; first fit; next fit; worst fit

5. Thrashing

6. Page fault

7. MMU

Emphasis:

1. Virtual memory

2. Paging idea

3. The optimal page replacement algorithm

4. The not recently used page replacement algorithm

5. The first in, first out page replacement algorithm

6. The second chance page replacement algorithm

7. The least recently used

8. Simulating LRU in software

Difficulty:

1. Relocation and protection

2. Memory management with linked lists

3. Memory enlarge method

4. Two-level page tables

5. Implementation of pure segmentation

6. Segmentation with paging

1. Basic memory management

(1) Virtual address and Physical address
(2) Relocation: If a program is loaded in partition 1 (at address 100k), that instruction will jump to absolute address 100, which is inside the operating system. What is needed is a call to 100k+100. This problem is known as the relocation problem.
(3) Protection: in multi-user systems, it is highly undesirable to let processes read and with memory belonging to other users

2. Partition

(1) Monoprogramming without Swapping or Paging
Three simple ways of organizing memory:

(2) Multiprogramming with Fixed Partition

1. Single input queue

2. Multiple input queue

(3) Multiprogramming with Dynamic Partition

1. Management with Bitmaps

2. Management with Link List

(4) Partition selection algorithm

1. First fit: the memory manager scans along the list of segments until it finds a hole that is big enough

2. Next fit: it works the same way as first fit,except that it keeps track of where it is whenever it finds a suitable hole. The net time it is called to find a hole, it starts searching the list form the place where it left off last time,instead of always at the beginning, as first fit does

3. Best fit: searches the entire list and takes the smallest hole that is adequate

4. Worst fit: take the largest available hole, so that the ole broken off will be big enough to be useful

5. Quick fit: maintains separate lists for some for the more common sizes requested. For example, it might have a  table with n entries, in which the first entry is a pointer to the head of a list of 4-KB holes, the second entry is a pointer to a list of 8-KB holes, and so on…

· 3. Pure  Paging

(1)  Pure Paging idea
On a system that uses simple paging, memory is divided into fixed-size blocks called page frames. Process is divided into blocks called pages which are the same size as the page frames.
(2) Paging relocation
The virtual address is split into a virtual page number(high-order bits) and an offset  (low-order bits).different splits imply different page sizes

If a logical address contains L bits, and the page size is 2PB, P bits of an address specify     offset within a page, and the remaining L-P bits specify the page number. The hardware generates the physical address by appending the page offset to the page frame number extracted from the page table.

· 4. Pure Segmentation

(1) Pure Segmentation idea
Memory  segmentation  is the division of a computer's primary memory  into segments or sections. In a computer system using segmentation, a reference to a memory location includes a value that identifies a segment and an offset within that segment. Segments or sections are also used in object files of compiled programs when they are linked together into a program image and when the image is loaded into memory.
(2) Implementation
In a system using segmentation computer memory addresses consist of a segment id and an offset within the segment. A hardware memory management unit (MMU) is responsible for translating the segment and offset into a physical memory address, and for performing checks to make sure the translation can be done and that the reference to that segment and offset is permitted.
A segment table is very similar to a page table, the operating system must maintain a free list and allocate segments to memory holes.
A segment table entry must have fields for storing the segments’ starting address in main memory and the size of the segment. The logical address is below:

(3) Relocation
                       

· 5. Memory enlarge

(1) Swapping
Swapping may be used to increases the number of processes sharing the CPU. In addition to the processes stored in the main memory, one or more processes may be temporarily copied out of memory to a backing store. As space becomes available in main memory, swappen-out processes may be returned to memory. To execute on the CPU, a process must be in main memory. Decision on which process to swap out and which process to swap in are made by the operating system’s process scheduler.
(2) Overlays
Programs were too big go fit in the available memory. The solution usually adopted was to split the program into pieces, called overlays. Overlays allows a process to execute despite the system having insufficient physical memory. The programmer defines two or more overlay segments within the program such that no two overlay segments need be in memory at the same time. Overlay 0 start running first, when it was done, it would call another overlay. The OS would manage swapping overlay segments, reducing the amount of physical memory required by the program. The major disadvantage of overlays is the extensive programmer involvement in the process.

(3) Virtual memory
In computing, virtual memory is a memory management technique that is implemented using both hardware and software. It maps memory addresses used by a program, called virtual addresses, into physical addresses in computer memory. Main storage as seen by a process or task appears as a contiguous address space or collection of contiguous segments. The operating system manages virtual address spaces and the assignment of real memory to virtual memory. Address translation hardware in the CPU, often referred to as a memory management unit or MMU, automatically translates virtual addresses to physical addresses. Software within the operating system may extend these capabilities to provide a virtual address space that can exceed the capacity of real memory and thus reference more memory than is physically present in the computer.

· 6. Demand Paging

(1) Demand paging idea
In computer operating systems, demand paging is a method of virtual memory management. In a system that uses demand paging, the operating system copies a disk page into physical memory only if an attempt is made to access it and that page is not already in memory (i.e., if a page fault occurs). It follows that a process begins execution with none of its pages in physical memory, and many page faults will occur until most of a process's working set of pages is located in physical memory.
(2) Replace a page
Each entry in the page table has at a minimum two fields: page frame and in/out bit. When a virtual address is generated, the memory management hardware extracts the page number from the address, and the appropriate entry in the page table is accessed. The in/out bit is checked and, if the is in memory, the physical address is generated by appending the page offset to the page frame number. If the page is not in memory, a page fault occurs, transferring control to the page fault routine in the operating system.
When a page fault occurs, the OS checks to see if any page frames in memory are free. If not, it selects one page for removal. The page marked for removal is copied back out to secondary storage and the in/out bit in its entry in the page table is set to “out” . Given a free frame, the OS copies the modified to indicate the page frame number and that the page is in memory. The page fault routine then completes and the hardware reexecutes the instruction generating the trap.
(3) Page thrashing
When paging and page stealing are used, a problem called "thrashing" can occur, in which the computer spends an unsuitably large amount of time transferring pages to and from a backing store, hence slowing down useful work.

· 7.Page Replacement Algorithm

OPT
NRU
FIFO
Second Chance
LRU
Clock algorithm
NFU
Aging
Working Set

· 8.Segmentation with Paging

(1) Segmentation with Paging idea
Each program has a segment table, with one descriptor per segment. The segment table is itself a segment and is paged. A segment descriptor contains an indication of whether the segment is in main memory or not. If any part of the segment is in memory, the segment is considered to be in memory, and its page table will be in memory.

(2) Virtual address
An address consists of two parts: the segment number and the address within the segment (offset). The offset is further divided into a page number and a page offset.

(3) Relocation

Ⅰ.Select the correct answer
1. In memory management, the strategy, called (     ) , allows programs to run even when they are only partially in main memory.
A. virtual memory                                   B. swapping
C. paging                                                 D. segmentation
2.Which of the following is not the job of the memory manager?
A. allocating memory to processes
B. relocation and protection
C. keeping track of which parts of memory is in use     
D. scheduling a process to run
3.Comparing page with segment, which one is correct? (   )
A. Given a system, the page’s size is fixed, but the segment’s size is    dynamic;
B. Given a system, the page’s size is dynamic, but the segment’s size is fixed;
C. Given a system, both the page’s size and the segment’s size are dynamic;
D. Given a system, both the page’s size and the segment’s size are fixed.
4. That part of the program where the shared memory is accessed is called the (   ).
A. memory manager                 B. file system
C. scheduler                      D. critical region
5. In memory management, the strategy, called (     ) , consists of bringing in each process in its entirety, running it for a while, then putting it back on the disk.
A. virtual memory                                   B. swapping
C. paging                                           D. segmentation
6.  (   ) maps the virtual addresses onto the physical memory addresses.
A.TLB                              B. PCB 
C.DMA                              D. MMU
7. The device that performs the check and mapping virtual address onto physical address is called (  ).
A．scheduler                   B．MMU
C．device controller           D．page table
8. In the following page replacement algorithms, which can cause Belady’s anomaly. (  )
A．FIFO                           B．LRU  
C．NRU                           D．OPT
9. In memory management, the purpose of adopting swapping technique is (  ).
A．saving main memory space
B．extending main memory capacity in physical way
C．improving CPU efficiency
D．implementing main memory sharing
10. The maximum capacity of virtual memory (  ).
A．is sum of main memory and external memory
B．lies on address structure of computer
C．is discretionary（任意的）
D．lies on address space of jobs
11. The real-time system must respond to the occurring external event in (  ) .
A．response time                B．turnaround time
C．a certain time                D．scheduling time
12. In memory management, the size of each partition is (  ) by using fixed partition allocation.
A．same                       
B．changing with job
C．different but fixed beforehand（预先）
D．different but fixed with the length of job
13. The goals of virtual memory implementation is (  ).
A．protecting memory             B．program floating（浮动）
C．extending external memory       D．extending main memory
14. In memory management with segment, if physical address is expressed with 24 bits and the segment number is expressed with 8 bits, then the maximum length of each segment is (  ).
A．224                          B．216
C．28                           D．232
15.  Why the system could occur the thrashing?
A   Improper replacement algorithms
B    The large amount of information exchange
C    Memory capacity is sufficient
D    Demand paging method

Ⅱ. Fill in the blanks.
1.The virtual address space is divided up into units called                    . The corresponding units in the physical memory are called                    . Both of them are always the same size.
2.In memory management, the strategy, that allows programs to run even when they are only partially in main memory, is called                   .
3.In paging relocation algorithm,            could make Belady phenomenon .

Ⅲ. Using the following page table, supposing the computer has 32-bit addresses and the page size is 4KB, give the physical address corresponding to each of the following virtual addresses:

(a) 5000   (b) 12000

Ⅳ. A virtual memory has 32 pages in its user space, every 1KB, the main memory is 16KB. Suppose the user’s pages 0,1,2,3 are allocated in physical blocks 5, 10, 4, 7 respectively. Please translate virtual addresses 0A5C and 093C and 0000 0000 0010 0001 to physical addresses.

Ⅴ.Using the following page table, supposing the computer is 16-bit, the page size is 2K, give the physical address corresponding to each of the following virtual addresses:

(a) 100   (b) 144cH

Ⅵ. Consider a swapping system in which memory consists of the following hole sizes in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, and 15KB.Which hole is taken for successive segment requests of
1) 12KB
2) 10KB
3) 9KB
for first fit, best fit, worst fit, and next fit?

Ⅶ. Question about page replacement.
If the LRU,OPT and FIFO page replacement algorithm are used with three page frames, compute the page fault rate with the reference string 1, 2, 3, 4, 1, 2, 5, 1, 2, 3 ,4, 5, if the three frames are initially empty? Write out calculating procedure.

 Answer

Ⅰ.Select the correct answer
ADADB  DBAAB  CCDBA
Ⅱ. Fill in the blanks.

1. Pages, page frames

2. Virtual memory

3. FIFO

Ⅲ.Answer：

1. page number = int [5000/ 4096] = 1

Offset=5000%4096=904
Then physical address is 5 * 4096 + 904 = 21384

1. page number = int [12000/ 4096] = 2

Offset = 12000%4096= 3808
Then physical address is 3*4096+3808= 16096

Ⅳ. Answer：
The virtual memory has 32 pages, 2^5=32
So, the page number occupied 5 bits
1KB=2^10
So, the offset occupied 10 bits
So, the page number occupied 6 bits
0----0000
1----0001
2----0010
3----0011
4----0100
5----0101
6----0110
7----0111
8----1000
9----1001
A----1010
B----1011
C----1100
D----1101
E----1110
F----1111
0A5C=0000 1010 0101 1100
Page number=000010=2, offset=10 0101 1100=2^2+2^3+2^4+2^6+2^9=604
2----4
Starting address in physical memory=4*1024=4096
Physical address=4096+604=4700
And so on…...

Ⅴ.Answer：

1. page number = int [100/2048] = 0

   Offset = 100%2048 = 100
So its frame number is 4
Then physical address is 4*2048+100 = 8292
(b) 144cH    
0  0  0  1  0   1  0  0  0  1  0  0  1  1  0  0
Page number      offset
Or 144cH----5196; int [5196/2048] = 2; 5196%2048 = 1100
So page number is 2;
Offset is 1100                                                    Corresponding frame number is 1
Physical address：1*2048+1100 = 3148

Ⅵ.

1. first fit: 20KB    10KB    18KB               

2. best fit: 12KB    10KB   9KB                

3. worst fit: 20KB    18KB    15KB                

4. next fit:        20KB    18KB    9KB

Ⅶ.
LRU:

Page fault rate is 10/12*100% = 83.3%                        
OPT:

Page fault rate is 7/12*100% = 58.3% 
FIFO:

Page fault rate is 9/12*100% = 75%

Page Replacement Algorithm Implementation

1. The purpose and requirements of the experiment 
(1) By simulating the page replacement algorithm, further understanding of the performance of various algorithms.
(2) Grasp the advantages and disadvantages of various page replacement algorithm.
2. The experimental principle
(1) The realization principle by manual operation simulation of internal operating system page replacement.
(2) The control of various page replacement algorithm about the teaching process, the analysis of the advantages and disadvantages of various algorithms
3. the experimental steps
(1) Software installation: install the C++ software
(2) The experimenter in the understanding of the purpose of the experiment, the design of the page table format as follows:

(3) Design of array, each element is a job moving into the memory page frame number
(4) For example, the main memory page frame size is 1K, there are 6 pages, and from 0 page to 2 page, they have moved into the main memory.

(5) Sequential instruction set operations are executed in sequence is as follows:

(6) Using the FIFO page replacement algorithm to complete.

1.Consider a swapping a system in which memory consists of the following hole sizes in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB and 15KB. Which hole is taken for successive segment requests of
 (a) 12KB   (b) 10KB  (c)9KB
For first fie? Now repeat the question for best fit, worst fit and next fit.

Solution:
First fit

Next fit

Best fit

Worst fit

 
2.For each of the following decimal virtual addresses, compute the virtual page number and offset for a 4-KB page and for an 8-KB page: 20000, 32768, 60000.
Solution:

page size: 4K=4*1024=4096

1. 20000/4096=4…3616       page number is 4, offset is 3616

2. 32768/4096=8             page number is 8, offset is 0

3. 60000/4096=14…2656      page number is 14, offset is 2656

page size: 8K=8*1024=8192

1. 20000/8192=2…3616       page number is 2, offset is 3616

2. 32768/8192=4             page number is 4 offset is 0

60000/8192=7…2656       page number is 7, offset is 2656

3.If FIFO page replacement is used with four page frames and eight pages, how many page faults will occur with the reference string 017237103 if the four frames are initially empty? Now repeat this problem for LRU.
Solution:
(a) FIFO: Page fault rate=6/10=60%

(b) LRU: Page fault rate=7/10=70%

4.A computer has four page frames. The time of loading, time of last access, and the R and M bits for each page are as shown below (the timesa re in clock ticks):

1. Which page will NRU replace?

2. Which page will FIFO replace?

3. Which page will LRU replace?

4. Which page will second chance replace?

Solution :
(a) Page 2 (2)     (b) Page 3 (3)      (c) Page 1 (1)       (d) Page 2 (2)

 A student in a compiler design course propose a project of writing a compiler that will produce a list of page references that can be used to implement the OPT algorithm. Is this possible? Why ?  Is there anything that could be done to improve paging efficiency at rum time ?
This is probably not possible except for the unusual and not very useful case of a program whose course of execution is completely predictable at compiling time. If a compiler collects information about the locations in the code of calls to procedures, this information might be used at link time to rearrange the object code so that procedures were located close to the code that calls them. This would make it more likely that a procedure would be on the same page as the calling code. Of course this would not help much for procedures called from many places in the program.

1. What is thrashing?
When paging and page stealing are used, a problem called "thrashing" can occur, in which the computer spends an unsuitably large amount of time transferring pages to and from a backing store, hence slowing down useful work.

2. What is the difference between the pure paging and demand paging?
The pure paging is the method that when the process is executed the pages that the process involves need to all move into the main memory.
The demand paging is the method in that each page of a program is stored contiguously in the paging swap space on secondary storage. Following that  pages should only be brought into memory if the executing process demands them.
3. Why is paging faster than segmentation?
In segmentation, the offset must be added to starting segment address. With paging, no addition need be performed. The page frame number and the offset are concatenated to form the physical address. Concatenating the two bit patterns is faster than adding them.