- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
Modern Operating Systems
21
存储管理
▪ 7. 一个计算机有4个页帧，装入时间、上次访问时间
和每个页面的R位和M位如下表所示（时间以时钟滴
答为单位）：页面 装入时间 上次访问时间 R
M
0
126
280
1
0
1
140
270
0
0
3
110
285
1
1
– (1) NRU算法将置换哪个页面？
Modern Operating Systems
存储管理
12
存储管理
虚拟地址 20 4100 8300
页号 0 1 2
偏移量 页帧（起始地址） 物理地址
20
2（8K）
8K+20 = 8212
4
1（4K）
4K+4 = 4100
108
6（24K）
24K+108 = 24684
Modern Operating Systems
Modern Operating Systems
9
存储管理
▪ 1. Consider a swapping system in which memory consists of the following hole size in memory order: 10KB, 4KB, 20KB, 18KB, 7KB, 9KB, 12KB, and 15KB. Which hole is taken for successive segment requests of 12KB, 10KB, 9KB for first fit? Now repeat for best fit, worst fit and next fit.
▪ For (a) assume that the system is multiprogrammed, and that each job gets its fair share of the CPU. For (b) through (d) assume that only one job at a time runs, until it finishes. All jobs are completely CPU bound.
Modern Operating Systems
15
– FIFO
432
444 33 2
存储管理
1 4 3 54 3 2 1 5
1115 3444 2233
55 22 31
➢ LRU
432
444 33 2
1 4 3 54 3 2 1 5
1115 3444 2233
222 411 335
Modern Operating Systems
3
调度算法
▪ (b)Priority scheduling
B
E
A
CD
0
6
14
24 26
30
作业 A B C D E
运行时间 10 6 2 4 8
优先级 3 5 2 1 4
– TA = 24, TB = 6, TC = 26, TD = 30, TE = 14 – T = 20
▪ (c)First-come, first-served(run in order 10, 6, 2, 4, 8)
000010 1001011100 → 页号2，对应页帧11 – 物理地址：
0010 1110 0101 1100 → 2E5C
Modern Operating Systems
14
存储管理
▪ 5. 设某进程的执行过程中有以下的页面号引用串（页 面走向）：4, 3, 2, 1, 4, 3, 5, 4, 3, 2, 1, 5 （1）当为进程分配3个页帧时，分别给出采用FIFO、 LRU算法时的页面置换过程。 （2）当为进程分配4个页帧时，分别给出采用FIFO、 LRU算法时的页面置换过程。
软件学院2012年秋季本科课程
Chapter3 Memory Management (Exercise)
调度算法
▪ Five batch jobs A through E, arrive at a computer center at almost the same time. They have estimated running times of 10, 6, 2, 4 and 8 minutes. Their priorities are 3, 5, 2, 1 and 4, respectively, with 5 being the highest priority. For each of following scheduling algorithms, determine the mean process turn-around time. Ignore process switching overhead. (a) Round robin; (b)Priority scheduling; (c)First-come, first-served(run in order 10, 6, 2, 4, 8); (d)Shortest job first
Modern Operating Systems
2
调度算法
▪ (a) Round robin, assume that the system is multiprogrammed, and that each job gets its fair share of the CPU
– 5个作业共享CPU，每个作业各获得1/5的
Modern Operating Systems
20
存储管理
▪ NRU算法
– 根据页面的R位和M位，将页面分为4类：
▪ 第0类：没有被访问，也没有被修改 ▪ 第1类：没有被访问，已被修改 ▪ 第2类：已被访问，没有被修改 ▪ 第3类：已被访问，已被修改
– NRU算法随机地从编号最小的非空类中挑选一个页面 淘汰。
▪ 置换页面2
Modern Operating Systems
22
存储管理
▪ 7. 一个计算机有4个页帧，装入时间、上次访问时间
和每个页面的R位和M位如下表所示（时间以时钟滴
答为单位）：页面 装入时间 上次访问时间 R
– T = 14
作业 运行时间 优先级
A
10
3
B
6
5
C
2
2
D
4
1
E
8
4
Modern Operating Systems
5
UNIX中的调度
▪ UNIX有两级调度算法
– 高级调度算法：在内存和磁盘之间移动进程以保证所有的进 程都有机会进入内存运行。
– 低级调度算法：从内存中的一组进程选取某个进程运行。
少？
▪ 页面访问串：0 0 1 1 0 3 1 2 2 4 4 3 ▪ 页帧数：2
Modern Operating Systems
18
▪ FIFO ➢ LRU
存储管理
001
0
0
1
1 0 3 12 2 4 4 3
3
3
4
4
1
2
2
3
001
0
0
1
1 0 3 12 2 4 4 3
0 11
4
4
3 32
2
3
Modern Operating Systems
(a)12KB (b)10KB (c)9KB
First fit 20KB 10KB 18KB
Best fit 12KB 10KB 9KB
Worst Fit 20KB 18KB 15KB
Next fit 20KB 18KB 9KB
Modern Operating Systems
10
存储管理
▪ 2.For each of the following decimal virtual addresses,
▪ 普通用户只能在0~19之间调整，超级用户有权调整更高的优先 权值。
Modern Operating Systems
8
▪ ps –l
Linux中的调度
– UID：代表执行者的身份 – PID：这个进程的进程号 – PPID：该进程的父进程号 – PRI：该进程的优先级，值越小越早被执行 – NI：该进程的nice值。
16
存储管理
– FIFO
➢ LRU
432 444
33 2
1 4 3 54 3 2 1 5
4
555 5 1 1
3
344 4 4 5
2
223 3 3 3
1
111 2 2 2
432 444
33 2
1 4 3 54 3 2 1 5
4
4
44 5
3
3
33 3
2
5
51 1
1
1
22 2
Modern Operating Systems
作业 A B C
运行时间 10 6 2
优先级 3 5 2
CPU时间。C结束需要10分钟。（ TC = 10）
D
4
1
– 4个作业共享CPU，每个作业各获得1/4的
E
8
4
CPU时间。D结束需要8分钟。（ TD = 10 + 8 = 18） – 3个作业共享CPU，每个作业各获得1/3的CPU时间。B结束需要6分钟。
4
3616
2
3616
32768 页号 偏移量
8
0
4
0
60000 页号 偏移量
