程序代写 CSC501-myshell$ ");

Virtual Memory (III) — Policies

Recap: Demand paging
instruction

each of this is a fix-sized page
instruction data
0x0 0x80000000
0x80008000
Page fault! 0x0 Page fault!
Virtual Addre
Page fault!
Virtual Address Space for Chrome
Page fault! for
Instructions
Instructions

Recap: Demand paging + Swapping
0x000000000000
(5) map the requesting page to the freed space
(2) page fault! — exception
page table
Static Data
(1) an instruction accesses virtual address 0xDEADBEEF
Virtual memory 0xFFFFFFFFFFFF
(3) running out of space on DRAM
Physical memory
(4) kick some page out and store it in the secondary storage

Recap: Hierarchical page table to make paging feasible
63:48 (16 bits) 47:39 (9 bits) 38:30 (9 bits) 29:21 (9 bits) 20:12 (9 bits) 11:0 (12 bits)
page offset
X86 Processor
512 entries
512 entries
512 entries
Make page table “nodes” demand-pagable — not all of them has to
512 entries
be residual in main memory
Save the space for nodes belong to addresses not being use
Upon a context switch, program the CR3 reg (PTBR) and load the physical page # 4
11:0 (12 bits)
root node of the hierarchical page table
page offset

Recap: Page replacement policy
Implementation Goal: Minimize the amount of software and hardware overhead
Goal: Identify page to remove that will avoid future page faults (i.e. utilize
locality as much as possible)
Memory (i.e. RAM) access time: 100ns
Disk access time: 10ms
Pf: probability of a page fault
Effective Access Time = 10-7 + Pf * 10-3
Takeaway: Disk access tolerable only when it is extremely rare
When Pf = 0.001:
Effective Access Time = 10,100ns

What VAX/VMS proposed to achieve these goals?
Considering the optimization goals and the proposed VAX/ VMS mechanisms, which of the following combinations is incorrect?
Process startup cost
Goal Optimization
Process performance interference
Page table lookup overhead
Paging load on disks
Demand-zero & copy-on-refernce
Process-local replacement
Page caching
Page clustering
also helps reduce disk loads
We’re still using their proposed techniques almost everyday!
It’s basically the baseline UNIX VM design 6

Machine-Independent Virtual Memory Management for Paged Uniprocessor and Multiprocessor Architectures
, , , , , , , and
Carnegie- , NeXT, University of Rochester

virtual address space
address map
memory object #,
protection,
inheritance,
*prev, *next
memory objects
hash bucket
Resident page table
Virtual memory space of Task #2
Recap: Overview of Mach’s VM
accessing 0xDEADBEEF
Virtual memory space of Task #1
Nothing in this slide is machine dependent!
offset in an memory object
Memory object #2
Page Page Page
Memory object #3
a memory object could be anything — a file, a network buffer, remote network memory, device buffer, or physical DRAM

Recap: Address allocation is sparse in multithreading model!
static data
Virtual memory
address map

Page replacement policies
Page replacement policy once used in UNIX: Converting a Swap-Based System to do Paging in an Architecture Lacking Page-Reference Bits
Another popular page replacement policy: WSClcok – A Simple
and Effective Algorithm for Virtual Memory Management

Page replacement policies from textbooks

Page replacement policy
We need to determine: Which page(s) to remove
When to remove the page(s) •
Identify page to remove that will avoid future page faults (i.e. utilize Minimize the amount of software and hardware overhead
locality as much as possible)

FIFO: Replace the oldest page
Page replacement algorithms
LRU: Replace page that was the least recently used (longest
since last use)

Assume your OS uses FIFO policy when handle page faults. Also assume that we have 3 physical memory pages available. Compared with the same machine using an OS with LRU page replacement police, how many more page faults will you see for the FIFO based OS in the following page reference sequence?
FIFO v.s. LRU
0 1 2 3 4 5 6 7 8 9 10 11
A. 0 B. 1 C. 2 D. 3 E. 4
https://www.pollev.com/hungweitseng close in

FIFO v.s. LRU
Implementation Execution overhead Performance
Easy — circular queue
May require hardware support or linked list or additional timestamps in page tables
High — you need to manipulate the list or update every counter
Usually not as good as LRU
Usually better than FIFO

Converting a Swap-Based System to do Paging
in an Architecture Lacking Page-Reference Bits
Özalp Babaoglu and *
Cornell University and University of California, Berkeley

The VMS/Old UNIX VM
Regarding the original UNIX VM (basically the VMS), please identify how many
of the following statements are correct.
1 VAXmachineprovidesnohardwaresupportforpagereplacementpolicies
2 VMSimplementsFIFOpolicyforpagereplacement
3 Aprocess’sresidentsetcannotbeadjustedeventhoughthatprocessistheonly process in the system
4 VMSswapsoutallmemorypagebelongtoaprocesswhenthatprocessis switched out
https://www.pollev.com/hungweitseng close in

The VMS/Old UNIX VM
Regarding the original UNIX VM (basically the VMS), please identify how many
of the following statements are correct.
1 VAXmachineprovidesnohardwaresupportforpagereplacementpolicies
2 VMSimplementsFIFOpolicyforpagereplacement
3 Aprocess’sresidentsetcannotbeadjustedeventhoughthatprocessistheonly process in the system
4 VMSswapsoutallmemorypagebelongtoaprocesswhenthatprocessis
— Really inefficient if you have frequent context switches or if you have many applications in-fly
switched out

The Why of Babaoglu new UNIX VM
The original UNIX is a swap-based system
Whenever you have a context switch, swap the whole process out
from the memory
Really inefficient if you have frequent context switches or if you
have many applications in-fly
Imply that the modern UNIX or Linux does not do this
Efficient page replacement policies and other virtual optimization techniques cannot be implemented easily without appropriate hardware support

The page replacement policy proposed
How many of following statements fit the page replacement policy that the paper
implements?
1 ItusesLRU(least-recently-used)asthepagereplacementpolicy
2 Pagereplacementpolicyareonlytriggeredwheneverapagefaultoccurs
3 Itattachesatimestamptoeachpagetableentryinsteadofusingthereferencebit from hardware
4 Processesareallocatedafixedsetofpagesandswapin/outto/fromthosepages
5 Thepagereplacementpolicyhelpstoguaranteetheresponsetimeofshortprograms
https://www.pollev.com/hungweitseng close in

Clock algorithm
attach a “reference bit” to each PTE, set to true when the page is referenced
Clock hand move sequentially to swap out the first page without reference bit set. Clear the reference bit when it’s set

Clock algorithm in motion
Where to put
Clock hand move sequentially to swap out the first page without reference bit set. Clear the reference bit when it’s set

Clock algorithm in motion
Where to put
C will be selected to swap out,but Rs of A and B are cleared
Clock hand move sequentially to swap out the first page without reference bit set. Clear the reference bit when it’s set

Assume your OS uses LRU policy when handle page faults. Also assume that we have 3 physical memory pages available. How many page faults will you see in the following page reference sequence?
Recap: LRU
0 1 2 3 4 5 6 7 8 9 10 11

Assume your OS uses the clock policy when handle page faults. Also assume that we have 3 physical memory pages available. How many page faults will you see in the following page reference sequence?
How good is clock?
0 1 2 3 4 5 6 7 8 9 10 11
A. 5 B. 6 C. 7 D. 8 E. 9
https://www.pollev.com/hungweitseng close in

Assume your OS uses the clock policy when handle page faults. Also assume that we have 3 physical memory pages available. How many page faults will you see in the following page reference sequence?
How good is clock?
0 1 2 3 4 5 6 7 8 9 10 11
C. 7 D. 8 E. 9
+ means the reference bit is set * means the current hand

Reduces the demand of accessing disks
Recap: Page caching to cover the performance loss
Evicted pages will be put into one of the lists in DRAM Free list: clean pages
Modified list: dirty pages — needs to copy data to the disk •
Page fault to any of the page in the lists will bring the page back
page fault!
RS of Process A
page fault!
page fault!
RS of Process B
Modified List
Physical Memory

Free list in Babaoglu’s UNIX
How many of the following statements regarding the “free list” is/are
1 Itcanimprovethelatencyofapagefault
2 Itcanreducethelatencyofswappingoutapage
3 Itcanincurdiskaccesseswithoutpagefaults
4 Itdoesn’tallowapageinthelisttobeusedforotherpurpose A. 0
https://www.pollev.com/hungweitseng close in

Free list in Babaoglu’s UNIX
How many of the following statements regarding the “free list” is/are 1 Itcanimprovethelatencyofapagefault
— instead of swapping a page during the page fault, just take one from the free list
2 Itcanreducethelatencyofswappingoutapage
— No! This completely depend on how fast your disk/storage is!
3 Itcanincurdiskaccesseswithoutpagefaults
— No! You can use those pages as disk caches!
— Do you remember how UNIX page replacement is triggered?
4 Itdoesn’tallowapageinthelisttobeusedforotherpurpose

When we need a page, take one from the free list
So far, we need to trigger clock policy and swap in/out on each page
Why don’t we prepare more free pages each time so that we can Free list
feed page faults with pages from the list?
Have a daemon running the background, managing this free list — you
can do this when system is not loaded
If size of free list gets too small, trigger the clock algorithm to add pages
into the free list (by swapping out to disk)
Free list can be used as a disk cache 48

The page replacement policy proposed
How many of following statements fit the page replacement policy that the paper 1 ItusesLRU(least-recently-used)asthepagereplacementpolicy
implements?
2 Pagereplacementpolicyareonlytriggeredwheneverapagefaultoccurs
from hardware
4 Processesareallocatedafixedsetofpagesandswapin/outto/fromthosepages
5 Thepagereplacementpolicyhelpstoguaranteetheresponsetimeofshortprograms
3 Itattachesatimestamptoeachpagetableentryinsteadofusingthereferencebit
reference bit
free list is under a threshold

The page replacement policy proposed
How many of following statements fit the page replacement policy that the paper 1 ItusesLRU(least-recently-used)asthepagereplacementpolicy
implements?
2 Pagereplacementpolicyareonlytriggeredwheneverapagefaultoccurs
3 Itattachesatimestamptoeachpagetableentryinsteadofusingthereferencebit
Process just get a page from the free list whenever it needs
free list is under a threshold
reference bit
from hardware
4 Processesareallocatedafixedsetofpagesandswapin/outto/fromthosepages
5 Thepagereplacementpolicyhelpstoguaranteetheresponsetimeofshortprograms

Say, we want to implement a shell that interprets command line commands and executes “./a” The following program can serve for this purpose:
int main(int argc, char *argv[]) {
int child_pid;
char cmd[1024];
memset(cmd, 0 , 1024);
fprintf(stderr,”CSC501-myshell$ “);
while(fgets_wrapper(cmd,1024,stdin)) {
if(strcmp(“exit”,cmd)==0)
child_pid = fork();
if (child_pid == 0)
execvp(cmd,NULL);
fprintf(stderr,”CSC501-myshell$ “);
memset(cmd, 0 , 1024);
Do we actually need the code segment of the parent? 51
How to implement a simple shell?

Create a new page table
Copy data page-by-page
80% of fork occurs in shell command interpreter
What happens on a fork?

Poll close in
How many of the following statements regarding “vfork” is/are correct?
1 vforkcanimprovetheresponsetimeoftheparentprocess
2 vforkdoesnotcreateanewaddressspaceuponthecreationofnewprocess
3 vforkallowsthechildprocesstoexecutewithintheparent’smemory address
4 Thechildprocesscreatedbyvforkcanpotentiallycorrupttheparentprocess
virtual fork — vfork

virtual fork — vfork
How many of the following statements regarding “vfork” is/are correct?
1 vforkcanimprovetheresponsetimeoftheparentprocess
hurt, because it delays the parent until exec()
2 vforkdoesnotcreateanewaddressspaceuponthecreationofnewprocess
3 vforkallowsthechildprocesstoexecutewithintheparent’smemory address
4 Thechildprocesscreatedbyvforkcanpotentiallycorrupttheparentprocess

WSClcok – A Simple and Effective
Algorithm for Virtual Memory Management Richard Carr and

Brief recap: what policies are used?
VAX/VMS Original UNIX
UNIX after Babaoglu Mach
Local: select one page from the same process’ physical pages
for storing the demanding page when swapping is necessary
Global: select any page that was previously belong to any
process when swapping is necessary

Degree of parallelism and performance
How many of the following would happen in Babaoglu’s UNIX VM if we keep increase the amount of concurrent processes and assume each process uses some virtual memory in the system?
1 TheCPUutilizationwillkeepincreasingandstayat100%
2 Thesystemmayspendmoretimeincontextswitchingthanrealcomputation 3 Thesystemmayspendmoretimeinswapin/outthanrealcomputation
4 Someprocessmaynotrespondduetothehighpagingoverhead
https://www.pollev.com/hungweitseng close in

Degree of parallelism and performance
How many of the following would happen in Babaoglu’s UNIX VM if we keep increase the amount of concurrent proces

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

Related Posts