[操作系统] 自习第八章、第九章

段式地址：段号+段内地址

页式地址：页号+页内偏移量

• 段号位数决定了每个进程最多可以分几个段
• 页号位数决定了每个段最多有多少页
• 页内偏移量决定了页面大小、内存块大小是多少

段表：存储界限、基地址

传统存储管理方式：

一次性：作业必须一次性全部装入内存后才能开始运行。这会造成两个问题（1）作业很大不能全部装入内存，导致大作业无法运行。（2）当大量作业要求运行时，由于内存无法容纳所有作业，因此只有少量作业能运行，导致多道程序并发度下降。

驻留性：一旦作业被装入内存，就会一直驻留在内存中，直到作业运行结束。浪费了内存的资源。

局部性原理(principle of locality)

指程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。表现为：

• 时间局部性：一条指令的一次执行和下次执行，一个数据的一次访问和下次访问都集中在一个较短时期内；
• 空间局部性：当前指令和邻近的几条指令，当前访问的数据和邻近的数据都集中在一个较小区域内。

虚拟存储器是具有请求调入功能和置换功能，能仅把进程的一部分装入内存便 可运行进程的存储管理系统，它能从逻辑上对内存容量进行扩充的一种虚拟的存储器系统。

Demand Paging 请求调页：

页表项：

Page fault 缺页中断

页面不在内存时，产生缺页中断，缺页进程阻塞，进入阻塞队列，调页完成后再将其唤醒，放回就绪队列。

换入换出外存需要进行慢速I/O操作，换入内存的页面表项会直接加入快表。

缺页率 page fault rate = p ~[0,1]

有效访存时间 effective memory-access time = (1 – p) x physical-memory-access + p x ( page-fault-overhead + swap-page-out + swap-page-in + restart-overhead )

Three major components of the page-fault service time

• Service the page-fault interrupt(缺页中断服务时间)
• Read in the page(将缺页读入时间)
• Restart the process(重新启动进程时间)

写时拷贝 Copy-on-Write

父进程和子进程共享一个页面，在需要进行写操作时复制这个共享页，而不是直接在父进程的页面上进行修改。eg： Windows、Linux、Solaris

页面置换算法

最佳置换算法 OPT 

每次选择淘汰的页面将是以后永不使用，或是在最长时间内不再被访问的页面，这样可以保证最低的缺页率。

需要知道之后要依次访问的页面序列，因此，最佳置换算法是无法实现的。

先进先出置换算法 FIFO

每次选择淘汰的页面是最早进入内存的页面。

Belady异常：当为进程分配物理块数增大时，缺页次数不减反增的异常现象。

最近最少使用算法 LRU

每次淘汰的页面是最近最久未使用的页面。

实现方法：

• Conter 在页面条目上，每次引用时更新/复制时钟时间。
• Stack 按访问顺序入栈，长时间未访问的在栈低，将栈低的置换出去。

由于需要记录页面使用时间，硬件开销太大。

近似LRU算法 LRUA

reference bit 引用位初始为0，当被访问时，置1。

1.附加引用位算法

被访问时左边最高位置1，定期右移并且最高位补0，于是寄存器数值最小的是最久未使用页面。

2.第二次机会算法/Clock算法

如果访问位为0，表示很长时间未被使用，访问位为1，表示最近访问过。

需要选择更换时，如果为0，则换出；若不为0，则置0，往后检查。

当全部为1时，则依次置0，再进行第二轮扫描。

3.增强二次机会算法 Enhanced Second-Chance

使用引用位和修改位：引用过或修改过置成1

• (Reference bit, modified bit) ：
• (0,0): best page to replace
• (0,1): not quite good for replacement
• (1,0): will be used soon
• (1,1): worst page to replace.
• 淘汰次序：(0,0)->(0,1)->(1,0)->(1,1)

基于计数的页置换 Counting Algorithm

最不经常使用算法 LFU

经常使用算法 MFU 基于这样一种观点，即计数最小的页面可能是刚刚引入的，尚未使用。

页面缓冲算法

通过被置换页面的缓冲，有机会找回刚被置换的页面

• 被置换页面的选择和处理：用FIFO算法选择被置换页，把被置换的页面放入两个链表之一 。即：如果页面未被修改，就将其归入到空闲页面链表的末尾，否则将其归入到已修改页面链表。
• 需要调入新的页面时，将新页面内容读入到空闲页面链表的第一项所指的页面，然后将第 一项删除。
• 空闲页面和已修改页面，仍停留在内存中一段时间，如果这些页面被再次访问，这些页面 还在内存中。
• 当已修改页面达到一定数目后，再将它们一起调出到外存，然后将它们归入空闲页面链表 。
• VAX/VMS系统使用 ， Windows、Linux页面置换算法是基于页面缓冲算法。

帧分配 Allocation of Frames

Fixed Allocation 固定分配

Equal allocation 平均分配算法 ：把帧平均分配给每个进程

Proportional allocation 按比例分配算法 ：Allocate according to the size of process

Priority 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

分配策略：

• 固定分配
• 可变分配

组合成三种策略：

• 固定分配局部置换策略
• 可变分配全局置换策略
• 可变分配局部置换

系统颠簸/抖动

a process is busy swapping pages in and out 系统忙于换页

原因：进程频繁访问的页面数目高于可用的物理块数。

Working-set Model 工作集模型：

• working set (WS)工作集：The set of pages in the most recent Δ page references
• Δ = working-set window(工作集窗口) = a fixed number of page references Example: 10,000 instruction
• WSSi (working set size 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; m = total available frames
• if D > m -> Thrashing
• Policy if D > m, then suspend one of the processes

统计缺页频率 Page-fault frequency PFF