【操作系统】虚拟内存+存储管理选择题
Chapter 9虚拟内存
1、基本概念
（1）定义：
虚拟存储器是具有请求调入功能和置换功能，能仅把进程的一部分装入内存便可运行进程的存储管理系统，它能从逻辑上对内存容量进行扩充的一种虚拟的存储器系统
（2）局部性原理：
①时间局部性
②空间局部性
2、Demand paging
只有当进程需要这个页的时候才把它调入内存。
3、缺页
EAT = (1 – p) x physical-memory-access +p x ( page-fault-overhead +swap-page-out +swap-page-in +restart-overhead )
4、进程创建
写时拷贝（COW）技术：父子进程可以共享一个页，当其中一个修改这个页，这个被修改的页就会被拷贝出来供这个进程使用，原来的页不变。示意图：
5、页面置换
大概的过程：
（1）FIFO
谁先进来谁就先被替换。
帧数（frame）越多，缺页次数就越多（Belady's anomaly）。
（2）OPT
没有办法实际实现。
每次替换的时候看最远访问的是谁，替换最远被访问的那个。例如701后面的2，往后看，先找到0，然后是1，最后找到7，所以2替换7.
（3）LRU
最近最少使用的先被替换。找的时候可以倒着找回去。
栈是如何变化的：最先访问的被放在栈顶，余下的依次调整。
（4）LRU近似算法
reference bit：开始设置为0，这个页被访问过就置为1。
①附加引用位算法
②second chance（clock算法）
③enhanced second-chance algorithm
mactintosh中用。
（reference bit，modified bit）：（0，0）（0，1）（1，0）（1，1）
④Counting algorithm
用一个counter来计数
a、LFU
b、MFU
（5）页面缓冲算法
六：帧分配
1、固定分配
（1）平均分配
（2）按比例分配
2、优先级分配
3、置换策略
（1）全局置换
（2）局部置换
七、Thrashing
a process is busy swapping pages in and out.
（1）工作集（WS）
八、内存映射
九、其他
—————————————————————————————————————（练习）
问题 2
Consider a demand-paging system with the following time-measured utilizations:
CPU utilization 20%
Paging disk 97.7%
Other I/O devices 5%
Which (if any) of the following will (probably) improve CPU utilization?
Explain your answer.
a. Install a faster CPU.
b. Install a bigger paging disk.
c. Increase the degree of multiprogramming.
d. Decrease the degree of multiprogramming.
e. Install more main memory.
f. Install a faster hard disk or multiple controllers with multiple hard disks.
g. Add prepaging to the page fetch algorithms.
h. Increase the page size.
答案略
Assume we have a demand-paged memory. The page table is held in registers. It takes 8milliseconds to service a page fault if an empty page is available or the replaced page is not modified, and 20 milliseconds if the replaced page is modified（在存在空闲页帧的条件下，处理一次缺页的时间是8毫秒。如果没有空闲页面，但待换出页面并未更改，处理一次缺页的时间也是8毫秒。如果待换出页面已被更改，则需要20毫秒。） . Memory access time is 100 nanoseconds.
Assume that the page to be replaced is modified 70 percent of the time. What is the maximum acceptable page-fault rate for an effective access time of no more than 200 nanoseconds?
答案：
A page-replacement algorithm should minimize the number of page faults. We can do this minimization by distributing heavily used pages evenly over all of memory, rather than having them compete for a small number of page frames.We can associate with each page frame a counter of the number of pages that are associated with that frame. Then, to replace a page, we search for the page frame with the smallest counter.
a. Define a page-replacement algorithm using this basic idea. Specifically address the problems of (1) what the initial value of the counters is,
(2) when counters are increased,
(3) when counters are decreased, and
(4) how the page to be replaced is selected.
b. How many page faults occur for your algorithm for the following reference string, for four page frames?
1, 2, 3, 4, 5, 3, 4, 1, 6, 7, 8, 7, 8, 9, 7, 8, 9, 5, 4, 5, 4, 2.
c. What is the minimum number of page faults for an optimal page replacement strategy for the reference string in part b with four page frames?
Consider the following page reference string:
1, 2, 3, 4, 2, 1, 5, 6, 2, 1, 2, 3, 7, 6, 3, 2, 1, 2, 3, 6.
How many page faults would occur for the following replacement algorithms, assuming three, four frames? Remember all frames are initially empty, so your first unique pages will all cost one fault each.
LRU replacement
FIFO replacement
Optimal replacement