Last chapter,we discussed various memory-management strategies used in
computer systems.All these strategies have the same goal:to keep many processes in memory simultaneously to allow multiprogramming.However,they tend to require that an entire process be in memory before it can execute.
It is a technique that allows the execution of the processes that are not completely in memory.One major advantage of this scheme is that programs can be larger than physical memory.Further,virtual memory abstracts main memory into an extremely large,uniform array of storage,separating logical memory as viewed by the user from physical memory.This technique frees programmers from the concerns of memory-storage limitations.Virtual memory also allows processes to share files easily and to implement shared memory.In addition,it provides an efficient mechanism to process creation.
tu vm
Logical memory and Physical memory and kernel memory
When kernel runs,after booting,part of memory is for kernel,part is for user,so can say physical memory has 2 parts(physical memory and logical memory).Only interrupt or system call can access physical memory otw traps in user memory
Physical memory is the MAIN MEMORY, i.e. the RAM in your computer.
Logical memory is the main memory, seen as a contiguous sequence of bytes.(You can see pages are contiguous from 0,1 to ...,but 1st page maybe in frame 5,2nd page maybe in frame 2...
The amount of data for logical memory and physical memory is totally same.)
For the code segment, for example, the CPU generates logical addresses, starting from 0 up to the end of the program.
The logical address is translated to the physical by the paging software/hardware, through the page tables.(when execute 1st time a program,the cpu will generate the logical address,then put in page table,if find it's valid which means the page is in the memory,can execute directly,otw will generate a page fault,swap in the page from the backing store)
Virtual memory(virtually expand physical memory to match huge logical memory) is an extension of logical memory that virtualizes the logical memory, allowing a program to have more pages than the actual frames of RAM.This is done through the PAGING ON DEMAND mechanism, using the page faults exceptions to require the kernel the transfer from the disk of a page that is not currently present in RAM.
We may have logical memory without virtual memory(no disk)
Flash memory is only used at the boot of the system,nothing related to physical or logical memory.
And ROM is not in memory,it's for bootstrap,it's on disk(a piece os program)
RAM:
Ram and virtual memory:
The idea of virtual memory is to create a virtual address space that doesn't correspond to actual addresses in RAM. The system stores the official copy of memory on disk and caches only the most frequently used data in RAM. To make this workable, we break virtual memory into chunks calledpages; a typical page size is four kilobytes. We also break RAM into page frames, each the same size as a page, ready to hold any page of virtual memory.
The system also maintains a page table, stored in RAM, which is an array of entries, one for each page, storing information about the page. The most important piece of information in each page table entry is whether the corresponding page is loaded into a frame of RAM and, if so, which frame contains it. The CPU uses this page table in looking up data in virtual memory.
Consider the following illustration of a system using virtual memory.
Here, we have eight pages on disk pictured on the left and three page frames in the memory pictured at right. (This example is much smaller than in real life, where you would have thousands of pages and page frames.) In this example, each of the three frames holds a page from memory: The data of page 0 (in red) is in frame 1, page 2 (yellow) is in frame 3, and page 4 (blue) is in frame 2. You can see that the page table, also stored in RAM, contains this mapping from pages to frames.
Memory
physical memory
Memory made of RAM chips. The term is generally used to differentiate main memory (physical memory) and disk or solid state storage. It is also used in discussions about virtual memory, contrasting the data in main memory with the data that have been swapped temporarily to storage. See , and .
Memory Is Often Not RAM!
A smartphone or tablet's specification of 16GB or 32GB of memory does not refer to RAM; rather it is the unit's flash memory capacity for storing apps and data. The internal RAM is in the 256MB-3GB range but is not widely promoted to the general public, presumably to avoid confusion between RAM (temporary workspace) and flash memory (permanent storage).
What is the difference between RAM and hard drive storage?
hard drive storage is permanet which stores data no matter pc is turned on or off.Ram stores data temporaly,and it has limited space so only stores most important information
which can use several strategies like LRU,FIFO to choose pages to be loaded into frames breaked in RAM.And Ram uses page table to do the mapping from page to frame.
Virtual memory:-separation of logical memory as perceived by users from physical memory which allows an extremely large virtual memory to be provided for programmers when only a smaller physical memory is available.
Virtual address space:refers to the logical(or virtual) view of how a processs is stored in memory.
tu vap
space but will require actual physical pages only if the heap or stack grows.
In addition to separating logical memory from physical memory,virtual memory also allows files and memory to be shared by two or more processes through page sharing.
tu sl
Demand Paging
Initially load pages only as they are needed.
With demand-paged virtual memory,pages are only loaded when they are demanded during program execution;pages that are never accessed are thus never loaded into physical memory.
lazy swapper:never swaps a page into memory unless that page will be needed.
A swapper manipulates entire processes,whereas a pager is concerned with the
individual pages of a process,which is used in connection with demand paging.
tu to
When a process is to be swapped in,the pager guesses which pages will be used before the process is swapped out again.Instead of swapping in a whole process,the pager brings only those necessary pages into memory.Thus,it avoids reading into memory pages that will not be used anyway,decreasing the swap time and the amount of physical memory needed.
Hardware support to distinguish the pages that are in memory and on the disk:
valid-invalid bit scheme.
valid:the associated page is legal and in memory
invalid:the page either is not valid(that is,not in the logical address space of the process)or is valid but is currently on the disk
Notice that marking a page invalid will have no effect if the process never attempts to access that page.
tu lm
if the process tries to access a page that was not brought into memory:
Access to a page marked invalid causes a page-fault trap.
The procedure for handling this page fault is straightforward:
tu pf
1.check an internal table(usually kept with the process control block) for this process to determine whether the reference was a valid or an invalid memory access.
2.If the reference wa invalid,we terminate the process.If it was valid we have not yet brought in that page,we now page it in.
3.We find a free frame(by taking one from the free-frame list,for example)
4.We schedule a disk operation to read the desired page into the newly allocated frame.
5.When the disk read is complete,we modify the internal table kept with the process and the page table to indicate that the page is now in memory.
6.We restart the instruction that was interruptes by the trap.The process can now access the page as though it had always been in memory.
Performance of Demand Paging
effective access time
p:probablility of a page fault(0<=p<=1)(expect it to be close to 0--have only a fw page faults)
effective access time=(1-p)*ma+p*page fault time
Copy-on-write
allows the parent and child processes initially to share the same pages.These shared pages are marked as copy-on-write pages,meaning that if either process writes to a shared page,a copy of the shared page is creates.
-->only the pages that are modified by either process are copied;all unmodified pages can be shared by the parent and child processes
tu bc
tu ac
When it is determined that a page is going to be duplicated using cow,it is important to note the location from which the free page will be allocated.Many os provide a pool of free pages for such requests,These free pages are typically allocated when the stack or heap for a process must expand or when there are cow pages to be managed.Os typically allocate these pages using a technique known as zero-fill-on demand.Zero-fill-on-demand pages have been zeroed-out before being allocated,thus erasing the previous contents.
Page Replacement
tu prr
Approach: If no frame is free,we find one that is not currently being used and free it.We can free a frame by writing its contents to swap space and changing the page table(and all other tables)to indicate that the page is no longer in memory.We can now use the freed frame to hold the page for which the process faulted.We modify the page-fault service to include page replacement
Page-replacement algorithm
tu a1
tu s3
tu a3
for a memory with three frames
What is the difference between paging and segment in memory management?
Paging is used to get a large linear address space without having to buy more physical memory. Segmentation allows programs and data to be broken up into logically independent address spaces and to aid sharing and protection.
Paging does not distinguish and protect procedures and data separately.
Segmentation distinguishes and separately protects procedures and data.
Unlike segmentation, Paging does not facilitate sharing of procedures.
Paging is transparent to programmers(system handles it automatically).
Segmentation requires programmer to be aware of memory limits as programmer
tries to allocate memory to functions and variables or tries to access read
only memory violation, which results in segmentation fault
(see for more details on different types of seg. faults)
Mapping from logical to physical address is different for paging and segmentation.
Here's an illustration based on 16 bit-address space:
For paging :
The 6-bit page value is used to select a proper entry in process page table. the 6-bit process entry occupying the six most significant bit and the 10-bit offset occupying the 10 least significant bit forms a 16-bit physical address.
For segmentation :
The 4-bit segment of a logical address selects the proper entry in the process segment table. The base value is added to the 12 bit offset value to get the 16 bit physical address.
In segmentation, the address space is typically divided into a preset number of segments like data segment (read/write), code segment(read-only), stack(read/write) etc. And the programs are divided into these segments accordingly. Logical addresses are represented as tuple <segment, offset>.
While with paging, the address space is divided into a sequence of fixed size units called "pages". And logical addresses take the form of a tuple <page, offset>.
Each of these techniques offer several benefits e.g., segmentation offers better security since the segments are pre-defined and we can avoid spurious reads/writes at the time of address translations etc.
On the other hand, paging helps reduce fragmentation and ensures better memory management.
So, most modern operating systems employ a combination of both these techniques for their memory management.
Replacement Algorithm
FIFO Page Replacement
Belady's anamaly:for some page -replacement algorithms,the page-fault rate may
increase as the number of allocated frames increases.Optimal Page Replacement:has the lowest page-fault rate of all algorithms and
will never suffer from Belady's anomaly.
Replace the page that will not be used for the longest period of time.
LRU Page Replacement
The key distinction between the FIFO and OPT algorithms(other than looking backword versus forward in time)is that the FIFO algorithm uses the time when a page was brought into memory,whereas the OPT algorithm uses the time when a page is to be used.
LRU:if we use the recent past as an approxiamation of the near future,then we can replace the page that has not been used for the longest period of time.
It associates with each page the time of that page's last use.(optimal page-replacement algorithm looking backward in time)
Additional-Reference-Bits Algorithm
We can gain additional ordering information by recording the reference bits at regulare intervals.We can keep an 8-bit byte for each page in a table in memory.At regular intervals(say,every 100 milliseconds),a timer interrupt transfers control to the os.The os shifts the reference bit for each page into the high-order bit of its 8-bit,shifting the other registers contain the history of page use for the last eight time periods.If the shift register contains 00000000,e.g.then the page has not been used for 8 time-periods;a page that is used at least once in each period has a shift registe value of 11111111.
If we interpret these 8-bit bytes as unsigned integers,the page with the lowest number is the LRU page,and it can be replaced.
The number of bits of history can be varied,and is selected(depending on the hardware available) to make the updating as fast as possible.In the extreme case,the number can be reduced to zero,leaving only the reference bit itself.
---->
Second-Chance Algorithm
The basic algorithm of it is FIFO replacement algorithm.
If the reference bit is set to 1,we give the page a second chance and move on to select the next FIFO page.When a page gets a second chance,its reference bit is cleared,and its arrival time is reset to the current time.Thus, a page that is given a second chance will not be replaced until all other pages have been replaced(or given second chances).
It degerated to FIFO replacement if all bits are set.
Counting Algorithm
Keep a counter of the number of references that have been made to each page and develop the following 2 schemes:
LFU requires page with the smallest count be replaced.Reason:an actively used page should have a large reference count.A problem arises,the page is used heavily during the initial phase of a process but then never used again,hence it has a large count and remains in memory even though it is no longer needed ->shift the counters right by 1 bit at regular intervals.
MFU(most frequently used)based on the argument that the page with the smallest count was probably just brought in and has yet to be used.
Allocation of Frames
How do we allocate the fixed amount of free memory among the various processes?
Simplest case:single-user system.e.g 128KB of memory composed of pages 1KB in size.This system has 128 frames.The os may take 35KB,leaving 93 frames for the user process.Under pure demand paging,all 93 frames would initially be pur on the free-frame list.When a user process started execution,it would generate a sequence of page faults.The first 93 page faults would all get free frames from the free-frame list.When the free-frame list was exhausted,a page-replacement algorithm would be used to select one of the 93 in-memory pages to be replaced with the 94th,and so on.When the process terminated,he 93 frames would once again be replaced on the free-frame list.
Minimum Number of Frames
One way for allocating at least a minimum number of frames involves performance.As the number of frames allocated to each process decreases,the page fault rate increases,slowing process execution.Inaddition,when a page fault occurs before an executing instruction is complete,the instruction must be restareted.Consequently,we must have enough frames to hold all the different pages that any single instruction can reference.
Whereas the minimum number of frames per process is defined by the architecture,the maximum number is defined by the amount if availabel memory
Global versus Local Allocation
With multiple processes competing for frames,we can classify page-replacement algorithms into 2 broad categories:global replacement and loca replacement
Global ----allows a process to select a replacement frame from the set of all
frames,even if that frame is currently allocated to some other process;that is,
one process can take a frame from another
Local -----requires that each process select from only its own set allocated frames
Thashing
If the number of frames allocated to a low-priority process falls bellow the minimum number required bt the comouter architecture,we must suspend that process's execution.We must then page out its remaining pages,freeing all its allocated frames.This provision introduces a swap-in,swap-out level of intermediate CPU scheduling.
Buddy System
It allows memory from a fixed-size segment consisting
consisting of physically contiguous pages.Memory is allocated from this segment using a power-of-2 allocator,which satisfies requests in units sized as a power of 2(4KB,8KB,16KB,and so forth).A request in units not appropriately sized is rounded up to the next highest power of 2.
Slab Allocation
A slab is made up of one or more physically contiguous pages.
A cache consists of one or more slabs.
There is a single cache for each unique kernek data structure
---e.g,a separate cache for the data structure representing
process descriptors,a separate cache for file objects,a separate cache
for file objects,a separate cache for semaphores,and so forth.Each
cache is populated with objects that are instantiations of the
kernel data structure the cache represents.e.g,the cache representing
semaphores stores instances of semaphores objects.The below figure
shows 2 kernel objects 3 KB in size and three objects 7KB in size
2 main benifits:
1.No memory is wasted due to fragmentation.Each unique kernel data
structure has an associated cache and each cache is composed of
one or more slabs that are divided into chunks the size of the objects
being represented.Thus,when the kernel requests memory for an object,the
slab allocator returns the exact amount of memory required to represent
the object.
2.Memory requests can be satisfied quickly.
Other considerations
Prepaging
An obvious property of pure demand paging is the large number of
page faults that occur when a process is started,
which is due to trying to get the initial locality into memory.
prepaging is an attempt to prevent this high level of initial paging.
The strategy is to bring into memory at one time all the pages that
will be needed.
Page Size
1.to minimize internal fragmentation,then,we need a small page size.
2.the time required to read or write a page.IO time,transfer time.
3....
no best answers.
TLB Reach
Recall that the hit ratio for the TLB refers to the percentage of virtual address
translations that are resolved in the TLB rather than the page table.
Related to the hit ratio is a similar metric:the TLB reach,which refers to the amount if memory accessible from the TLB and is simply the number of entries
multiplied by the page size.
Ideally,the working set for a process is stored in the TLB,if not,the process will spend a considerable amount of time resolving memory references in the page
table rather than the TLB.
Another approach to increase the TLB reach is to:
---- increase the size of the page
---- provide multiple page sizes.->may lead to an increase in fragmentation for
some applications that do not require such a large page size as 32KB. Alternatively,an os may provide several different page sizes.
Program Structure
Demand paging is designed to be transparent to the user program.In many cases,
the user is completely unaware of the paged nature of memory.In other cases,how-
ever,system performance can be improved if the use(or compiler)has an awareness of the underlying demand paging.
I/O interlock
The reason why frames used for I/O must be in memory.
Locked pages cannot be replaced.When the I/O is complete,the pages aare unlocked.
The virtual address space is what an individual program sees when it executes. Depending on how the program has been configured this address space will be as large as the maximum the operating system supports.
The operating system kernel is then responsible for mapping addresses in the vas to physical memory, be that RAM, or system page files.
With this design, the programs themselves remain unaware of resources and real addresses, and can operate as if they had all system memory to themselves, or at least the maximum memory a single process can use.
In a nutshell a program works with VAS, and the operating system handles mapping VAS to real storage so that this is invisible to the running program. The running program sees only its VAS.
A virtual address is a number in that enables a process to use a location in (main memory) independently of other processes and to use more space than actually exists in primary storage by temporarily relegating some contents to a or internal .
In a computer that incorporates , the virtual address differs from the, which is the data location on an that corresponds to a particular cell of primary storage or to a particular register in a (input/output) device.
In a computer with both physical and virtual memory, a so-called (memory management unit) coordinates and controls all of the memory resources, assigning portions called to various running to optimize system performance. By translating between virtual addresses and physical addresses, the MMU allows every running process to "think" that it has all the primary storage to itself.