Silberschatz,Galvin,and Gagne?199910.1Applied Operating System Concepts
Module 10,Virtual Memory
Background（ 背景）
Demand Paging（ 请求页式）
Performance of Demand Paging（ 请求页式的性能）
Page Replacement（ 页置换）
Page-Replacement Algorithms（ 页置换算法）
Allocation of Frames （ 页框的分配）
Thrashing（ 颠簸）
Other Considerations（ 其他考虑）
Demand Segmenation（ 请求段式）
Silberschatz,Galvin,and Gagne?199910.2Applied Operating System Concepts
Background
Virtual memory – separation of user logical memory from
physical memory.（ 虚拟内存 —物理内存和用户逻辑内存的区分）
– Only part of the program needs to be in memory for
execution（ 只有部分运行的程序需要在内存中）,
– Logical address space can therefore be much larger than
physical address space（ 因此，逻辑地址空间能够比物理地址空间大）,
– Need to allow pages to be swapped in and out（ 必须允许页面能够被换入和换出）,
Virtual memory can be implemented via（ 虚拟内存能够通过以下手段来执行）,
– Demand paging （ 请求页式）
– Demand segmentation（ 请求段式）
Silberschatz,Galvin,and Gagne?199910.3Applied Operating System Concepts
Demand Paging
Bring a page into memory only when it is needed（ 只有在一个页需要的时候才把它换入内存）,
– Less I/O needed（ 需要很少的 I/O）
– Less memory needed （ 需要很少的内存）
– Faster response（ 快速响应）
– More users（ 多用户）
Page is needed （ 需要页）?reference to it（ 查阅此页）
– invalid reference（ 无效的访问）? abort（ 中止）
– not-in-memory（ 不在内存）? bring to memory（ 换入内存
）
Silberschatz,Galvin,and Gagne?199910.4Applied Operating System Concepts
Valid-Invalid Bit
With each page table entry a valid–invalid bit is associated
(1? in-memory,0? not-in-memory)（ 在每一个页表的表项有一个有效 - 无效位相关联,1表示在内存,0表示不内存）
Initially valid–invalid but is set to 0 on all entries（ 在所有的表项，这个位被初始化为 0）,
Example of a page table snapshot（ 一个页表映象的例子）,
During address translation,if valid–invalid bit in page table entry is
0（ 在地址转换中，如果页表表项位的值是 0）? page fault（ 缺页）,
1
1
1
1
0
0
0
Frame # valid-invalid bit
page table
Silberschatz,Galvin,and Gagne?199910.5Applied Operating System Concepts
Page Fault
If there is ever a reference to a page,first reference will trap to OS（ 如果有对一个页的访问，第一个访问要陷入 OS）?page fault（ 缺页）
OS looks at another table to decide（ OS查看另一个表来决定）,
– Invalid reference（ 无效引用）? abort（ 终止）,
– Just not in memory（ 仅仅不在内存）,
Get empty frame（ 得到空的页框）,
Swap page into frame（ 把页换入页框）,
Reset tables,validation bit = 1（ 重新设置页表，把位设为 1）,
Restart instruction（ 重启指令）,Least Recently Used （ 最近未使用）
– block move（ 块移动）
– auto increment/decrement location
（ 区域自动增长 /缩减）
Silberschatz,Galvin,and Gagne?199910.6Applied Operating System Concepts
What happens if there is no free frame?
Page replacement – find some page in memory,but not really in
use,swap it out（ 页置换 —找到内存中并没有使用的一些页，换出）
.
– Algorithm（ 算法）
– Performance（ 性能） – want an algorithm which will result in
minimum number of page faults（ 找出一个导致最小缺页数的算法）,
Same page may be brought into memory several times（ 同一个页可能会被装入内存多次）,
Silberschatz,Galvin,and Gagne?199910.7Applied Operating System Concepts
Performance of Demand Paging
Page Fault Rate 0? p? 1.0（ 缺页率 0? p? 1.0）
– if p = 0 no page faults （ 如果 p = 0,没有缺页）
– if p = 1,every reference is a fault（ 每次访问都缺页）
Effective Access Time (EAT)（ 有效存取时间）
EAT = (1 – p) x memory access
+ p (page fault overhead
+ [swap page out ]
+ swap page in
+ restart overhead)
Silberschatz,Galvin,and Gagne?199910.8Applied Operating System Concepts
Demand Paging Example
Memory access time = 1 microsecond （ 存取内存的时间）
50% of the time the page that is being replaced has been
modified and therefore needs to be swapped out（ 50%的时间，
所置换的页被修改，因此需要被换出）,
Swap Page Time = 10 msec = 10,000 msec（ 交换页的时间）
EAT = (1 – p) x 1 + p (15000)
1 + 15000P (in msec)
Silberschatz,Galvin,and Gagne?199910.9Applied Operating System Concepts
Page Replacement
Prevent over-allocation of memory by modifying page-fault
service routine to include page replacement（ 通过修改缺页服务例程，来包含页置换，防止分配过多）,
Use modify (dirty) bit to reduce overhead of page transfers – only
modified pages are written to disk（ 修改（脏）位来防止页面转移过多 —只有被修改的页面才写入磁盘）,
Page replacement completes separation between logical memory
and physical memory – large virtual memory can be provided on
a smaller physical memory（ 页置换完善了逻辑内存和物理内存的划分 —在一个较小的物理内存基础之上可以提供一个大的虚拟内存,
Silberschatz,Galvin,and Gagne?199910.10Applied Operating System Concepts
Page-Replacement Algorithms
Want lowest page-fault rate（ 需要一个最小的缺页率）,
Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page
faults on that string（ 通过运行一个内存访问的特殊序列（访问序列），计算这个序列的缺页次数）,
In all our examples,the reference string is （ 在所有的例子中，访问序列是）
1,2,3,4,1,2,5,1,2,3,4,5.
Silberschatz,Galvin,and Gagne?199910.11Applied Operating System Concepts
First-In-First-Out (FIFO) Algorithm
Reference string,1,2,3,4,1,2,5,1,2,3,4,5
3 frames (3 pages can be in memory at a time per process)
4 frames
FIFO Replacement – Belady’s Anomaly（ FIFO算法可能会产生 Belady异常）
– more frames? less page faults（ 页就是更多的页框相反会产生更多的缺页）
1
2
3
1
2
3
4
1
2
5
3
4
9 page faults
1
2
3
1
2
3
5
1
2
4
5 10 page faults
44 3
Silberschatz,Galvin,and Gagne?199910.12Applied Operating System Concepts
Optimal Algorithm
Replace page that will not be used for longest period of time（ 被置换的页将是之前最长时间不被使用的页）,
4 frames example
1,2,3,4,1,2,5,1,2,3,4,5
How do you know this?（ 怎样知道的）
Used for measuring how well your algorithm performs（ 用来衡量你的算法的效率）,
1
2
3
4
6 page faults
4 5
Silberschatz,Galvin,and Gagne?199910.13Applied Operating System Concepts
Least Recently Used (LRU) Algorithm
Reference string,1,2,3,4,1,2,5,1,2,3,4,5
Counter implementation（ 计数器的实现）
– Every page entry has a counter; every time page is
referenced through this entry,copy the clock into the
counter（ 每一个页表项 有一个计数器，每次页通过这个表项被访问，把记录拷贝到计数器中）,
– When a page needs to be changed,look at the counters to
determine which are to change（ 当一个页需要改变是，查看计数器来觉得改变哪一个页 0.）
1
2
3
5
4
4 3
5
Silberschatz,Galvin,and Gagne?199910.14Applied Operating System Concepts
LRU Algorithm (Cont.)
Stack implementation – keep a stack of page numbers in a
double link form（ 栈实现 —在一个双链表中保留一个记录页数目的栈）,
– Page referenced（ 被访问的页）,
move it to the top（ 移到栈顶）
requires 6 pointers to be changed（ 需要改变 6个指针）
– No search for replacement（ 没有为置换进行查找）
Silberschatz,Galvin,and Gagne?199910.15Applied Operating System Concepts
LRU Approximation Algorithms
Reference bit（ 访问位）
– With each page associate a bit,initially -= 0（ 每个页都与一个位相关联，初始值位 0）
– When page is referenced bit set to 1（ 当页是访问位是设位 1）,
– Replace the one which is 0 (if one exists),We do not know the
order,however（,如果存在的话置换位为 0的页。然而我们并不知道这个置换顺序）,
Second chance（ 二次机会）
– Need reference bit.（ 需要访问位）
– Clock replacement.（ 时钟置换）
– If page to be replaced (in clock order) has reference bit = 1,
Then（ 如果将要（以顺时针）交换的访问位是 1，则）,
set reference bit 0（ 把访问位设位 0）,
leave page in memory（ 把页留在内存中）,
replace next page (in clock order),subject to same rules（
以同样的规则，替换下一个页）,
Silberschatz,Galvin,and Gagne?199910.16Applied Operating System Concepts
Counting Algorithms
Keep a counter of the number of references that have been made
to each page.（用一个计数器记录对每一个页的访问次数。）
LFU Algorithm,replaces page with smallest count（ 以最小的计数置换一个页）,
MFU Algorithm,based on the argument that the page with the
smallest count was probably just brought in and has yet to be
used（ 以下面的观点为基础，最小计数的页也许刚刚被换入和使用
）,
Silberschatz,Galvin,and Gagne?199910.17Applied Operating System Concepts
Allocation of Frames
Each process needs minimum number of pages（ 每个进程所需要的最少的页的数目）,
Example,IBM 370 – 6 pages to handle SS MOVE instruction:
– instruction is 6 bytes,might span 2 pages.
– 2 pages to handle from.
– 2 pages to handle to.
Two major allocation schemes（ 两个主要的分配策略）,
– fixed allocation（ 固定分配）
– priority allocation（ 优先分配）
Silberschatz,Galvin,and Gagne?199910.18Applied Operating System Concepts
Fixed Allocation
Equal allocation（ 平均分配） – e.g.,if 100 frames and 5
processes,give each 20 pages（ 例：如果有 100个页框，和 5个进程，则每个进程分给 20个页）,
Proportional allocation（ 按比率分配） – Allocate according to
the size of process（ 根据每个进程的大小来分配）,
m
S
s
pa
m
sS
ps
i
ii
i
ii
f o r a llo c a t io n
f r a m e s of n u m b e r t o t a l
p r o c e s s of s iz e
5964
1 3 7
1 2 7
564
1 3 7
10
1 2 7
10
64
2
1
2
a
a
s
s
m
i
Silberschatz,Galvin,and Gagne?199910.19Applied Operating System Concepts
Priority Allocation
Use a proportional allocation scheme using priorities rather than
size（ 根据优先级而不是大小来使用比率分配策略）,
If process Pi generates a page fault,（ 如果进程 Pi产生一个缺页）
– select for replacement one of its frames（ 选择替换其中的一个页框）,
– select for replacement a frame from a process with lower
priority number（ 从一个较低优先级的进程中选择一个页面来替换）,
Silberschatz,Galvin,and Gagne?199910.20Applied Operating System Concepts
Global vs,Local Allocation
Global replacement（ 全局替换） – process selects a
replacement frame from the set of all frames; one process can
take a frame from another（ 进程在所有的页中选择一个替换页面；一个进程可以从另一个进程中获得页面）,
Local replacement （ 局部替换） –each process selects from
only its own set of allocated frames（ 每个进程只从属于它自己的页中选择）,
Silberschatz,Galvin,and Gagne?199910.21Applied Operating System Concepts
Thrashing
If a process does not have,enough” pages,the page-fault rate is
very high,This leads to（ 如果一个进程没有足够的页，那么缺页率将很高，这将导致）,
– low CPU utilization（ CPU利用率低下）,
– operating system thinks that it needs to increase the degree
of multiprogramming（ 操作系统认为需要增加多道程序设计的道数）,
– another process added to the system（ 系统中将加入一个新的进程）,
Thrashing（ 颠簸）? a process is busy swapping pages in and
out（ 一个进程的页面经常换入换出）,
Silberschatz,Galvin,and Gagne?199910.22Applied Operating System Concepts
Thrashing Diagram
Why does paging work?（ 为什么分页工作）
Locality model（ 位置模式）
– Process migrates from one locality to another（ 进程从一个位置移到另一个位置）,
– Localities may overlap（ 位置可能重叠）,
Why does thrashing occur?（ 为什么颠簸会发生）
size of locality > total memory size
Silberschatz,Galvin,and Gagne?199910.23Applied Operating System Concepts
Working-Set Model
working-set window? a fixed number of page references
Example,10,000 instruction
WSSi (working set of Process Pi) =
total number of pages referenced in the most recent? (varies in
time)
– if? too small will not encompass entire locality.
– if? too large will encompass several localities.
– if? = will encompass entire program.
D =? WSSi? total demand frames
if D > m? Thrashing
Policy if D > m,then suspend one of the processes.
Silberschatz,Galvin,and Gagne?199910.24Applied Operating System Concepts
Keeping Track of the Working Set
Approximate with interval timer + a reference bit（ 近似的一个内部时钟和一个访问位）
Example,? = 10,000
– Timer interrupts after every 5000 time units.（ 每 5000个时钟单位时钟中断）
– Keep in memory 2 bits for each page.（ 为每个页在内存中保留两个位）
– Whenever a timer interrupts copy and sets the values of all reference
bits to 0.（ 任何时候一个时钟中断拷贝，把所有访问位设为 0）
– If one of the bits in memory = 1? page in working set.（ 如果一个在内存中的位是 0，说明页在工作集）
Why is this not completely accurate?（ 为什么不是非常的精确）
Improvement = 10 bits and interrupt every 1000 time units.（ 提高：用 10个位
，以及每 1000个时钟单位中断）
Silberschatz,Galvin,and Gagne?199910.25Applied Operating System Concepts
Page-Fault Frequency Scheme
Establish,acceptable” page-fault rate（ 设置可接受的缺页率）,
– If actual rate too low,process loses frame（ 如果缺页率太低
，回收一些进程的页框）,
– If actual rate too high,process gains frame（ 如果缺页率太高，就分给进程一些页框）,
Silberschatz,Galvin,and Gagne?199910.26Applied Operating System Concepts
Other Considerations
Prepaging （ 预先调页）
Page size selection（ 页面尺寸选择）
– Fragmentation（ 碎片）
– table size （ 表大小）
– I/O overhead（ I/O开销）
– Locality（ 位置）
Silberschatz,Galvin,and Gagne?199910.27Applied Operating System Concepts
Other Consideration (Cont.)
Program structure（ 程序结构）
– Array A[1024,1024] of integer
– Each row is stored in one page
– One frame
– Program 1 for j,= 1 to 1024 do
for i,= 1 to 1024 do
A[i,j],= 0;
1024 x 1024 page faults
– Program 2 for i,= 1 to 1024 do
for j,= 1 to 1024 do
A[i,j],= 0;
1024 page faults
I/O interlock and addressing（ I/O连接和地址）
Silberschatz,Galvin,and Gagne?199910.28Applied Operating System Concepts
Demand Segmentation
Used when insufficient hardware to implement demand paging（
当请页的硬件不充足时使用）,
OS/2 allocates memory in segments,which it keeps track of
through segment descriptors（ 操作系统以段来分配内存，它通过段描述符来进行跟踪）
Segment descriptor contains a valid bit to indicate whether the
segment is currently in memory（ 段描述符有一个有效位来说明段是否以在内存）,
– If segment is in main memory,access continues（ 如果段已在主存中，继续存取）,
– If not in memory,segment fault（ 如果不在内存中，缺段中断）,
Module 10,Virtual Memory
Background（ 背景）
Demand Paging（ 请求页式）
Performance of Demand Paging（ 请求页式的性能）
Page Replacement（ 页置换）
Page-Replacement Algorithms（ 页置换算法）
Allocation of Frames （ 页框的分配）
Thrashing（ 颠簸）
Other Considerations（ 其他考虑）
Demand Segmenation（ 请求段式）
Silberschatz,Galvin,and Gagne?199910.2Applied Operating System Concepts
Background
Virtual memory – separation of user logical memory from
physical memory.（ 虚拟内存 —物理内存和用户逻辑内存的区分）
– Only part of the program needs to be in memory for
execution（ 只有部分运行的程序需要在内存中）,
– Logical address space can therefore be much larger than
physical address space（ 因此，逻辑地址空间能够比物理地址空间大）,
– Need to allow pages to be swapped in and out（ 必须允许页面能够被换入和换出）,
Virtual memory can be implemented via（ 虚拟内存能够通过以下手段来执行）,
– Demand paging （ 请求页式）
– Demand segmentation（ 请求段式）
Silberschatz,Galvin,and Gagne?199910.3Applied Operating System Concepts
Demand Paging
Bring a page into memory only when it is needed（ 只有在一个页需要的时候才把它换入内存）,
– Less I/O needed（ 需要很少的 I/O）
– Less memory needed （ 需要很少的内存）
– Faster response（ 快速响应）
– More users（ 多用户）
Page is needed （ 需要页）?reference to it（ 查阅此页）
– invalid reference（ 无效的访问）? abort（ 中止）
– not-in-memory（ 不在内存）? bring to memory（ 换入内存
）
Silberschatz,Galvin,and Gagne?199910.4Applied Operating System Concepts
Valid-Invalid Bit
With each page table entry a valid–invalid bit is associated
(1? in-memory,0? not-in-memory)（ 在每一个页表的表项有一个有效 - 无效位相关联,1表示在内存,0表示不内存）
Initially valid–invalid but is set to 0 on all entries（ 在所有的表项，这个位被初始化为 0）,
Example of a page table snapshot（ 一个页表映象的例子）,
During address translation,if valid–invalid bit in page table entry is
0（ 在地址转换中，如果页表表项位的值是 0）? page fault（ 缺页）,
1
1
1
1
0
0
0
Frame # valid-invalid bit
page table
Silberschatz,Galvin,and Gagne?199910.5Applied Operating System Concepts
Page Fault
If there is ever a reference to a page,first reference will trap to OS（ 如果有对一个页的访问，第一个访问要陷入 OS）?page fault（ 缺页）
OS looks at another table to decide（ OS查看另一个表来决定）,
– Invalid reference（ 无效引用）? abort（ 终止）,
– Just not in memory（ 仅仅不在内存）,
Get empty frame（ 得到空的页框）,
Swap page into frame（ 把页换入页框）,
Reset tables,validation bit = 1（ 重新设置页表，把位设为 1）,
Restart instruction（ 重启指令）,Least Recently Used （ 最近未使用）
– block move（ 块移动）
– auto increment/decrement location
（ 区域自动增长 /缩减）
Silberschatz,Galvin,and Gagne?199910.6Applied Operating System Concepts
What happens if there is no free frame?
Page replacement – find some page in memory,but not really in
use,swap it out（ 页置换 —找到内存中并没有使用的一些页，换出）
.
– Algorithm（ 算法）
– Performance（ 性能） – want an algorithm which will result in
minimum number of page faults（ 找出一个导致最小缺页数的算法）,
Same page may be brought into memory several times（ 同一个页可能会被装入内存多次）,
Silberschatz,Galvin,and Gagne?199910.7Applied Operating System Concepts
Performance of Demand Paging
Page Fault Rate 0? p? 1.0（ 缺页率 0? p? 1.0）
– if p = 0 no page faults （ 如果 p = 0,没有缺页）
– if p = 1,every reference is a fault（ 每次访问都缺页）
Effective Access Time (EAT)（ 有效存取时间）
EAT = (1 – p) x memory access
+ p (page fault overhead
+ [swap page out ]
+ swap page in
+ restart overhead)
Silberschatz,Galvin,and Gagne?199910.8Applied Operating System Concepts
Demand Paging Example
Memory access time = 1 microsecond （ 存取内存的时间）
50% of the time the page that is being replaced has been
modified and therefore needs to be swapped out（ 50%的时间，
所置换的页被修改，因此需要被换出）,
Swap Page Time = 10 msec = 10,000 msec（ 交换页的时间）
EAT = (1 – p) x 1 + p (15000)
1 + 15000P (in msec)
Silberschatz,Galvin,and Gagne?199910.9Applied Operating System Concepts
Page Replacement
Prevent over-allocation of memory by modifying page-fault
service routine to include page replacement（ 通过修改缺页服务例程，来包含页置换，防止分配过多）,
Use modify (dirty) bit to reduce overhead of page transfers – only
modified pages are written to disk（ 修改（脏）位来防止页面转移过多 —只有被修改的页面才写入磁盘）,
Page replacement completes separation between logical memory
and physical memory – large virtual memory can be provided on
a smaller physical memory（ 页置换完善了逻辑内存和物理内存的划分 —在一个较小的物理内存基础之上可以提供一个大的虚拟内存,
Silberschatz,Galvin,and Gagne?199910.10Applied Operating System Concepts
Page-Replacement Algorithms
Want lowest page-fault rate（ 需要一个最小的缺页率）,
Evaluate algorithm by running it on a particular string of memory
references (reference string) and computing the number of page
faults on that string（ 通过运行一个内存访问的特殊序列（访问序列），计算这个序列的缺页次数）,
In all our examples,the reference string is （ 在所有的例子中，访问序列是）
1,2,3,4,1,2,5,1,2,3,4,5.
Silberschatz,Galvin,and Gagne?199910.11Applied Operating System Concepts
First-In-First-Out (FIFO) Algorithm
Reference string,1,2,3,4,1,2,5,1,2,3,4,5
3 frames (3 pages can be in memory at a time per process)
4 frames
FIFO Replacement – Belady’s Anomaly（ FIFO算法可能会产生 Belady异常）
– more frames? less page faults（ 页就是更多的页框相反会产生更多的缺页）
1
2
3
1
2
3
4
1
2
5
3
4
9 page faults
1
2
3
1
2
3
5
1
2
4
5 10 page faults
44 3
Silberschatz,Galvin,and Gagne?199910.12Applied Operating System Concepts
Optimal Algorithm
Replace page that will not be used for longest period of time（ 被置换的页将是之前最长时间不被使用的页）,
4 frames example
1,2,3,4,1,2,5,1,2,3,4,5
How do you know this?（ 怎样知道的）
Used for measuring how well your algorithm performs（ 用来衡量你的算法的效率）,
1
2
3
4
6 page faults
4 5
Silberschatz,Galvin,and Gagne?199910.13Applied Operating System Concepts
Least Recently Used (LRU) Algorithm
Reference string,1,2,3,4,1,2,5,1,2,3,4,5
Counter implementation（ 计数器的实现）
– Every page entry has a counter; every time page is
referenced through this entry,copy the clock into the
counter（ 每一个页表项 有一个计数器，每次页通过这个表项被访问，把记录拷贝到计数器中）,
– When a page needs to be changed,look at the counters to
determine which are to change（ 当一个页需要改变是，查看计数器来觉得改变哪一个页 0.）
1
2
3
5
4
4 3
5
Silberschatz,Galvin,and Gagne?199910.14Applied Operating System Concepts
LRU Algorithm (Cont.)
Stack implementation – keep a stack of page numbers in a
double link form（ 栈实现 —在一个双链表中保留一个记录页数目的栈）,
– Page referenced（ 被访问的页）,
move it to the top（ 移到栈顶）
requires 6 pointers to be changed（ 需要改变 6个指针）
– No search for replacement（ 没有为置换进行查找）
Silberschatz,Galvin,and Gagne?199910.15Applied Operating System Concepts
LRU Approximation Algorithms
Reference bit（ 访问位）
– With each page associate a bit,initially -= 0（ 每个页都与一个位相关联，初始值位 0）
– When page is referenced bit set to 1（ 当页是访问位是设位 1）,
– Replace the one which is 0 (if one exists),We do not know the
order,however（,如果存在的话置换位为 0的页。然而我们并不知道这个置换顺序）,
Second chance（ 二次机会）
– Need reference bit.（ 需要访问位）
– Clock replacement.（ 时钟置换）
– If page to be replaced (in clock order) has reference bit = 1,
Then（ 如果将要（以顺时针）交换的访问位是 1，则）,
set reference bit 0（ 把访问位设位 0）,
leave page in memory（ 把页留在内存中）,
replace next page (in clock order),subject to same rules（
以同样的规则，替换下一个页）,
Silberschatz,Galvin,and Gagne?199910.16Applied Operating System Concepts
Counting Algorithms
Keep a counter of the number of references that have been made
to each page.（用一个计数器记录对每一个页的访问次数。）
LFU Algorithm,replaces page with smallest count（ 以最小的计数置换一个页）,
MFU Algorithm,based on the argument that the page with the
smallest count was probably just brought in and has yet to be
used（ 以下面的观点为基础，最小计数的页也许刚刚被换入和使用
）,
Silberschatz,Galvin,and Gagne?199910.17Applied Operating System Concepts
Allocation of Frames
Each process needs minimum number of pages（ 每个进程所需要的最少的页的数目）,
Example,IBM 370 – 6 pages to handle SS MOVE instruction:
– instruction is 6 bytes,might span 2 pages.
– 2 pages to handle from.
– 2 pages to handle to.
Two major allocation schemes（ 两个主要的分配策略）,
– fixed allocation（ 固定分配）
– priority allocation（ 优先分配）
Silberschatz,Galvin,and Gagne?199910.18Applied Operating System Concepts
Fixed Allocation
Equal allocation（ 平均分配） – e.g.,if 100 frames and 5
processes,give each 20 pages（ 例：如果有 100个页框，和 5个进程，则每个进程分给 20个页）,
Proportional allocation（ 按比率分配） – Allocate according to
the size of process（ 根据每个进程的大小来分配）,
m
S
s
pa
m
sS
ps
i
ii
i
ii
f o r a llo c a t io n
f r a m e s of n u m b e r t o t a l
p r o c e s s of s iz e
5964
1 3 7
1 2 7
564
1 3 7
10
1 2 7
10
64
2
1
2
a
a
s
s
m
i
Silberschatz,Galvin,and Gagne?199910.19Applied Operating System Concepts
Priority Allocation
Use a proportional allocation scheme using priorities rather than
size（ 根据优先级而不是大小来使用比率分配策略）,
If process Pi generates a page fault,（ 如果进程 Pi产生一个缺页）
– select for replacement one of its frames（ 选择替换其中的一个页框）,
– select for replacement a frame from a process with lower
priority number（ 从一个较低优先级的进程中选择一个页面来替换）,
Silberschatz,Galvin,and Gagne?199910.20Applied Operating System Concepts
Global vs,Local Allocation
Global replacement（ 全局替换） – process selects a
replacement frame from the set of all frames; one process can
take a frame from another（ 进程在所有的页中选择一个替换页面；一个进程可以从另一个进程中获得页面）,
Local replacement （ 局部替换） –each process selects from
only its own set of allocated frames（ 每个进程只从属于它自己的页中选择）,
Silberschatz,Galvin,and Gagne?199910.21Applied Operating System Concepts
Thrashing
If a process does not have,enough” pages,the page-fault rate is
very high,This leads to（ 如果一个进程没有足够的页，那么缺页率将很高，这将导致）,
– low CPU utilization（ CPU利用率低下）,
– operating system thinks that it needs to increase the degree
of multiprogramming（ 操作系统认为需要增加多道程序设计的道数）,
– another process added to the system（ 系统中将加入一个新的进程）,
Thrashing（ 颠簸）? a process is busy swapping pages in and
out（ 一个进程的页面经常换入换出）,
Silberschatz,Galvin,and Gagne?199910.22Applied Operating System Concepts
Thrashing Diagram
Why does paging work?（ 为什么分页工作）
Locality model（ 位置模式）
– Process migrates from one locality to another（ 进程从一个位置移到另一个位置）,
– Localities may overlap（ 位置可能重叠）,
Why does thrashing occur?（ 为什么颠簸会发生）
size of locality > total memory size
Silberschatz,Galvin,and Gagne?199910.23Applied Operating System Concepts
Working-Set Model
working-set window? a fixed number of page references
Example,10,000 instruction
WSSi (working set of Process Pi) =
total number of pages referenced in the most recent? (varies in
time)
– if? too small will not encompass entire locality.
– if? too large will encompass several localities.
– if? = will encompass entire program.
D =? WSSi? total demand frames
if D > m? Thrashing
Policy if D > m,then suspend one of the processes.
Silberschatz,Galvin,and Gagne?199910.24Applied Operating System Concepts
Keeping Track of the Working Set
Approximate with interval timer + a reference bit（ 近似的一个内部时钟和一个访问位）
Example,? = 10,000
– Timer interrupts after every 5000 time units.（ 每 5000个时钟单位时钟中断）
– Keep in memory 2 bits for each page.（ 为每个页在内存中保留两个位）
– Whenever a timer interrupts copy and sets the values of all reference
bits to 0.（ 任何时候一个时钟中断拷贝，把所有访问位设为 0）
– If one of the bits in memory = 1? page in working set.（ 如果一个在内存中的位是 0，说明页在工作集）
Why is this not completely accurate?（ 为什么不是非常的精确）
Improvement = 10 bits and interrupt every 1000 time units.（ 提高：用 10个位
，以及每 1000个时钟单位中断）
Silberschatz,Galvin,and Gagne?199910.25Applied Operating System Concepts
Page-Fault Frequency Scheme
Establish,acceptable” page-fault rate（ 设置可接受的缺页率）,
– If actual rate too low,process loses frame（ 如果缺页率太低
，回收一些进程的页框）,
– If actual rate too high,process gains frame（ 如果缺页率太高，就分给进程一些页框）,
Silberschatz,Galvin,and Gagne?199910.26Applied Operating System Concepts
Other Considerations
Prepaging （ 预先调页）
Page size selection（ 页面尺寸选择）
– Fragmentation（ 碎片）
– table size （ 表大小）
– I/O overhead（ I/O开销）
– Locality（ 位置）
Silberschatz,Galvin,and Gagne?199910.27Applied Operating System Concepts
Other Consideration (Cont.)
Program structure（ 程序结构）
– Array A[1024,1024] of integer
– Each row is stored in one page
– One frame
– Program 1 for j,= 1 to 1024 do
for i,= 1 to 1024 do
A[i,j],= 0;
1024 x 1024 page faults
– Program 2 for i,= 1 to 1024 do
for j,= 1 to 1024 do
A[i,j],= 0;
1024 page faults
I/O interlock and addressing（ I/O连接和地址）
Silberschatz,Galvin,and Gagne?199910.28Applied Operating System Concepts
Demand Segmentation
Used when insufficient hardware to implement demand paging（
当请页的硬件不充足时使用）,
OS/2 allocates memory in segments,which it keeps track of
through segment descriptors（ 操作系统以段来分配内存，它通过段描述符来进行跟踪）
Segment descriptor contains a valid bit to indicate whether the
segment is currently in memory（ 段描述符有一个有效位来说明段是否以在内存）,
– If segment is in main memory,access continues（ 如果段已在主存中，继续存取）,
– If not in memory,segment fault（ 如果不在内存中，缺段中断）,
