CS代写 - PowCoder代写

Virtual Memory
Virtual memory allows the separation of logical memory from physicalmemory-thisallowsforanextremely largevirtual memoryareatobeprovidedtoprocesses evenwhenphysical memoryismuchsmaller.

This makes the life of the programmer easier as they donot needtothinkabouthowmuchphysical memoryisactually availablewhenwritingtheir programs.

Virtual Memory
The virtual address space is used to refer to the logical (or virtual) view that a process has of memory.
This virtual address space is viewed as a large contiguous space that can be accessed easily.
The actual pages of memory may be stored in memory or may be stored in some backing store.

Virtual Memory
Virtual memory space that exceeds physicalmemory:

Virtual Memory
Virtual Address Space of a Process in Memory Memory
The heap is allowed to grow upwards, as it is used for dynamic memory allocation The stack is allowed to grow downwards, as through successive function calls.
The hole between the heap and the stack is part of the virtual address space, but will require physical pages only if the heap or stack grows.
Part of the
virtual address space

Virtual Memory
Virtual Address Space of a Process in Memory Memory
Virtual memory allows files and memory to be shared by multiple processes through page sharing (e.g. dynamically link libraries).
e.g. Standard C library

Virtual Memory
Virtual memory is almost always implemented with paging – the pages of a process in virtual memory may either be stored in physical memory or stored in the backing store.
If a process accesses a page stored in memory, it will simply access that physical memory.
If the page is not in physical memory, it must be loaded from the backing store and can then be accessed.

Page table with valid/invalid bit:
Page Table

Demand Paging
If a page is not currently loaded into memory, the valid bit for the page table entry will not be set.
Whenaprocessattemptstoaccessapage,thevalidbitfor the page table entry will be checked. If it is not set then the page is not loaded into memory it will need to load it from the backing store. This event is called a page fault.

3. Findafreeframein memory.
Demand Paging
When a page fault occurs, the operating system will need to perform the following steps:
1. Check the process is actually allowed to access that page (is it a valid / invalid memory access).
2. Iftheprocessreferencedaninvalidaddress,terminatethe process. Otherwise, proceed to page it in: go to Step 3.
4. Schedule a disk operation to read the page into the frame.
5. Updatethepagetabletorecordthatthepageisin memory.
6. Restarttheinstructionthatcausedthepagefault.

Demand Paging
From the point of view of the user process, a memory transaction was issued and then fulfilled. Whether the page was stored in memory or had to be loaded from the backing store into memory is not important.
In most cases this doesn’t affect the user either, their program runsasexpected.However,loadingpagesfromabacking store is slower than loading from memory so if many page faults occur it will have a negative effect on performance.

Demand Paging
With a demand paging system, pages needed for a process are only loaded into memory when they are accessed.
The previous discussion of this assumed that each page can simplybeloadedintomemoryandwillremainthere until the process ends.
In this system, each page of memory will cause at most one page fault (when it is first referenced).

Demand Paging
However, what happens if a page fault occurs and the operating system determines that there are no free frames available? For example, if process 1 wants to access page B.

Demand Paging
If there are no free frames available, then there are a few possible actions the operating system could take:
1. Terminate the process
2. Swap the entire process out of memory
3. Select a page to swap out of memory
By far the most common solution is the last one – page replacement.

Page Replacement
The basic idea for page replacement (if there are no free frames available) is to find a page that is not currently being used and free it.
A frame can be freed by copying the contents onto the backing store and updating the page table to indicate the page is no longerin memory.
This free frame can then be used to load the page that caused the page-fault.

Page Replacement
The process for dealing with a page-fault becomes:
1. Find the location of the desired page on disk.
2. Find a free frame:
a. Ifthereisafreeframe, useit.
b. if there is no free frame, use a page-replacement
algorithm to select a victim frame.
c. Write the victim frame to disk, update the page and
frame tables.
3. Readthedesiredpageintothefreeframe,updatethe page and frame tables.
4. Continuetheuserprocessfromwherethepagefault occurred.

Page Replacement
Note the effect that this will have on the page-fault service time if there are no free frames available.
In this case there will be two page transfers required(1 copyingapageoutofmemoryand1 copying it in).
This will effectively double the page-fault service time and will impact the effective access time.

Page Replacement
One way to try to reduce this impact is to make use of the modified or dirty bit in the page table entry.
Whenever a page is written to, this bit will be set to indicate that the contents have been changed since the page was loaded into memory.
When a page is selected for replacement, the modify bit is examined and the page is only written back to disk if it has been modified. Otherwise the old copy of the page in the disk can be used.

Page Replacement
Page replacement is a vital part of implementing demand paging – it provides the separation between logical and physical memory.
With this system a very large virtual address space can be providedwithmuchsmallerphysical memory.
Swapping pages in and out of memory can be performed without the user’s knowledge.

Page Replacement
Therearetwoproblemsthatstillneedtobesolvedto implement demandpaging-aframe-allocationalgorithm andapage- replacement algorithm.
The frame-allocation algorithm decides how many frames to allocate to each process.
Thepage-replacementalgorithmdecideswhichframewill be selected as a victim when pagereplacement is required.

Page Replacement
Page-replacement algorithms can have a very large effect on performance – we want the algorithm that gives the lowest page- fault rate.
Algorithms can be evaluated by running them on a string of memoryreferencesandcountingthenumberofpagefaults each algorithm would cause.
These memory references could be generated randomly or by tracing real programs and recording their memory transactions.

Page Replacement
We are not interested in the entire memory address of each transaction, just the page that they access.
We will use the following sequence of page accesses as an example:
7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1

First-In-First-Out
The simplest page-replacement algorithm is a first-in-first-out algorithm that records the order the pages were brought into memory.
Whenever the algorithm needs to select a victim page, it will always choose the oldest one (the one at the head of a FIFO queue).
Wheneverapageisbroughtintomemoryitwillbeaddedto the tail of this queue.

sequence of page accesses
70120304230321201701
system with 3 memory frames
7772 224440 00 777 000 333222 11 100
action Victim frame
xxxx xxxxxx xx xxx 7 012304 23 012
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
Toevaluatethealgorithmwewillseehowit performswithour referencestringfora system that has three memory frames (all initially empty).
We shall keep track of the content of the
11 100033 32 221
memory frames.
7770 123042 30 127 001 230423 01 270 12 304230 12 701

system with 3 memory frames
7772 224440 00 777 000 333222 11 100 11 100033 32 221
action Victim frame
We shall keep track of the action taken by
xxxx xxxxxx xx xxx
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
Toevaluatethealgorithmwewillseehowit performswithour referencestringfora system that has three memory frames (all initially empty).
sequence of page accesses
70120304230321201701
the page replacement algorithm, to
indicate if it is loading a frame into memory
7 012304 23 012
or replacing an existing frame.
7770 123042 30 127 001 230423 01 270 12 304230 12 701

sequence of page accesses
70120304230321201701
system with 3 memory frames
7772 224440 00 777 000 333222 11 100 11 100033 32 221
action Victim frame
xxxx xxxxxx xx xxx
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
Toevaluatethealgorithmwewillseehowit performswithour referencestringfora system that has three memory frames (all initially empty).
We shall keep track of the Victim Frame.
7 012304 23 012
The frame that is selected to be replaced.
7770 123042 30 127 001 230423 01 270 12 304230 12 701

system with 3 memory frames
7772 000 11
224440 00 777 333222 11 100 100033 32 221
action Victim frame
xxxxxx xx xxx 012304 23 012
front of Q
This is a FIFO Q.
This Q will tell us later which among the existing
memory‐resident page of memory.
X – load into frame
X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
7770 001 12
123042 30 127
First-In-First-Out
Toevaluatethealgorithmwewillseehowit performswithour referencestringfora system that has three memory frames (all initially empty).
sequence of page accesses
70120304230321201701
frames can be replaced when there is a page fault 230423 01 270
– meaning when there is a reference to a non‐
304230 12 701

sequence of page accesses
7 120304230321201701
system with 3 memory frames
7772 224440 00 777 000 333222 11 100 11 100033 32 221
action Victim frame
xxxx xxxxxx xx xxx added to the tail of the Q.
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
When the first page (7) is accessed, it will cause a page fault; therefore, it must be loaded into a frame.
The first page(7) will be
7 012304 23 012
7770 123042 30 127 001 230423 01 270 12 304230 12 701

sequence of page accesses
701 0304230321201701
system with 3 memory frames
7772 224440 00 777 000 333222 11 100 11 100033 32 221
action Victim frame
xxxx xxxxxx xx xxx memory frames are all full.
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
For the first three pages there will be a frame available to load the page into
At this stage, the 3
7 012304 23 012
7770 123042 30 127 001 230423 01 270 12 304230 12 701

system with 3 memory frames
7772 224440 000 333222 11 100033
00 777 11 100
action Victim frame
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
Whenthefourthpage(2)isloaded,thereisnofreeframe availablesoapagemustbe replaced.
sequence of page accesses
7012 304230321201701
xxxx xxxxxx 7 012304
(7) is selected for replacement.
7770 123042 001 230423 12 304230
30 127 01 270 12 701
The first page loaded
The Q shows us that page(2) is added at the
back of the Q.

system with 3 memory frames
We are keeping
action Victim frame
xxxx xxxxxx frame x x xxx 7 012304 23 012
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
Whenthefourthpage(2)isloaded,thereisnofreeframe availablesoapagemustbe replaced.
sequence of page accesses
7012 304230321201701 7772 224440 00 777
000 333222 11 100
11 100033 32 221
7770 123042 30 127 001 230423 01 270 12 304230 12 701
track of the
actions taken, as well as the victim

system with 3 memory frames
No page replacement
action Victim frame
xxxx xxxxxx xx xxx 7 012304 23 012
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
When page(0) is accessed, it is already residing in memory, and so no page replacement is required.
sequence of page accesses
70120 04230321201701 7772 224440 00 777
000 333222 11 100
11 100033 32 221
The Q has not changed
7770 123042 30 127 001 230423 01 270 12 304230 12 701

available so a page must be replaced.
no free frame available; therefore, replace an
sequence of page accesses
701203 4230321201701 existing frame (victim
system with 3 memory frames
77722224440 0000333222 111100033
00 777 11 100 32 221
action Victim frame
replacement as it is positioned at the head of
front of Q
added to the tail of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
When page(3) is accessed, we have another page fault. There is no frame
xxxx xxxxxx 7 012304
Page(0) is selected for
7770 123042 001 230423 12 304230
30 127 01 270 12 701
frame is page 0)
Consequently, page(3) is

sequence of page accesses
70120304230321201701
system with 3 memory frames
7772 224440 00 777 000 333222 11 100 11 100033 32 221
action Victim frame
xxxx xxxxxx xx xxx 7 012304 23 012
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
The process continues until all the way to the end of the reference string.
7770 123042 30 127 001 230423 01 270 12 304230 12 701

sequence of page accesses
70120304230321201701
system with 3 memory frames
How many page faults did this algorithm cause? 15
action Victim frame
xxxx xxxxxx xx xxx 7 012304 23 012
front of Q
X – load into frame X – no free frame available; therefore, replace an existing frame (pick the one in front of Q)
First-In-First-Out
The process continues all the way to the end of the reference string.
7772 224440 00 777 000 333222 11 100 11 100033 32 221
7770 123042 30 127 001 230423 01 270 12 304230 12 701

First-In-First-Out
The number of page-faults that occur will obviously depend on thereferencestringandthenumberofmemoryframesthat are available.
In general we expect that having more memory frames available for a process will improve the performance.
This is not always true – Belady’s Anomaly.

Belady’s Anomaly
Consider the FIFO algorithm with following reference string for three and four memory frames:
Four memory frames causes more page faults than three!

First-In-First-Out
In general the FIFO algorithm does not give very good performance, just because a page was loaded a long time ago doesn’t mean it isn’t still needed.
Note that even if we choose to replace a page that is currently being used, the results will still be correct.
If a victim page is immediately accessed after being selected, it willsimplycauseapagefaultandreloadthe page.

Optimal Algorithm
There is an optimal algorithm for the page-replacement problem – it will always give the lowest page-fault rate and doesnotsufferfromBelady’s anomaly.
The page chosen to replace will be the one that is not used for the longest period of time.

system with 3 memory frames
777222227 00004000 1133311
action Victim frame
xxxxxxxxx 710432
front of Q
The elements in this Q are ordered according to
higher the waiting time, the higher the priority.
X – load into frame
X – no free frame available; therefore, replace an existing frame (look ahead technique)
Optimal Algorithm
Let us have a look at the details of algorithm execution.
sequence of page accesses
70120304230321201701
This is a priority Q.
the length of waiting time, from when they are
placed in the Q, to a time in the future when they
will be used again – a look ahead strategy. The

sequence of page accesses
7 120304230321201701
system with 3 memory frames
777222227 00004000
action Victim frame
x x x 710432
front of Q
X – load into frame X – no free frame available; therefore,

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts